学位論文 動的輪郭モデルの分散協調化に 関する研究

学位論文
動的輪郭モデルの分散協調化に
関する研究
松本 倫子
埼玉大学大学院理工学研究科情報数理科学専攻
指導教員：吉田紀彦 教授
平成 18 年 9 月
目次
1
概要
第1章
4
序論
1.1 研究背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2 研究目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3 本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
第2章
動的輪郭モデル Snake
7
2.1 Snake の原理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2 問題点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3 関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.4 複数の Snake の協調による輪郭抽出 . . . . . . . . . . . . . . . . .
10
2.4.1
分散協調処理による領域分割 . . . . . . . . . . . . . . . . .
11
2.4.2
MDL に基づく成長と競合による領域分割 . . . . . . . . . .
12
2.4.3
複数の Snake の競合による領域分割 . . . . . . . . . . . . .
13
2.4.4
問題点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.5 Snake についてのまとめ . . . . . . . . . . . . . . . . . . . . . . . .
14
第3章
15
分散協調処理
3.1 分散人工知能とエージェント
. . . . . . . . . . . . . . . . . . . . .
15
3.2 分散協調の概略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
i
分散協調探索 . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.3 画像理解システムにおける分散協調方式の概観 . . . . . . . . . . . .
26
3.4 分散協調についてのまとめ . . . . . . . . . . . . . . . . . . . . . . .
36
3.2.1
第4章
Snake と分散協調
38
4.1 分散協調型 Snake の枠組 . . . . . . . . . . . . . . . . . . . . . . . .
38
4.2 Snake の分散協調化 . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.3 分散協調型 Snake のまとめ . . . . . . . . . . . . . . . . . . . . . .
44
第5章
複数パラメータ Snake の分散協調
45
5.1 方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
5.2 検証 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
5.3 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
第6章
複数データ Snake の分散協調
60
6.1 方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.2 検証 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
6.3 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
6.4 RGB 各色データ画像を与えられたパラメータの
異なる Multi-Snake . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
6.5 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
6.6 複数データ Snake のリモートセンシングへの応用 . . . . . . . . . .
72
6.7 各スペクトルを与えた Multi-Snake による検証 . . . . . . . . . . .
73
6.8 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
第7章
複数関数 Snake の分散協調
82
7.1 モデル導入による高精度化 . . . . . . . . . . . . . . . . . . . . . . .
ii
82
7.2 方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.3 検証 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
7.4 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
第8章
95
結論
8.1 研究成果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
8.2 残された課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
99
謝辞
公表論文
100
参考文献
101
iii
図目次
2.1 Active Contour Model . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2 Energy function . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.3 Wada’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4 Zhu’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.5 Matsuzawa’s approach . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.1 Problem Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.2 Search in Solution Space . . . . . . . . . . . . . . . . . . . . . . . .
20
3.3 Cooperative Multi-Point Search . . . . . . . . . . . . . . . . . . . .
23
3.4 Multitarget Motion Analysis by Decentralized Cooperation . . . . .
25
3.5 Avarage Square Error Convergence . . . . . . . . . . . . . . . . . .
25
3.6 AVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.7 Ukita’s AVA system . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.8 Nakazawa’s system . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.9 Kato’s recognition system . . . . . . . . . . . . . . . . . . . . . . .
30
3.10 Functional Distribution . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.11 Matsuyama’s Blackboard System . . . . . . . . . . . . . . . . . . .
32
3.12 The Schema System . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.13 VIC stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.14 VIC face analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
iv
3.15 Spacial Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.1 Related approach . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.2 Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.3 Exchanging information by agents . . . . . . . . . . . . . . . . . . .
40
4.4 Decision of new control points: original Snake . . . . . . . . . . . .
41
4.5 Decision of new control points: Multi-Snake . . . . . . . . . . . . .
43
4.6 Vibration control . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
5.1 Energy function with different parameters . . . . . . . . . . . . . .
46
5.2 The track of Multi-Snake . . . . . . . . . . . . . . . . . . . . . . . .
47
5.3 (1,0,0),(0,1,0),(0,0,1) Multi-Snake . . . . . . . . . . . . . . . . . . .
48
5.4 Energy function of each agent . . . . . . . . . . . . . . . . . . . . .
48
5.5 Simulation result: case 1 . . . . . . . . . . . . . . . . . . . . . . . .
51
5.6 Simulation result: case 2 . . . . . . . . . . . . . . . . . . . . . . . .
51
5.7 Simulation result: case 3 . . . . . . . . . . . . . . . . . . . . . . . .
52
5.8 Simulation result: case 4 . . . . . . . . . . . . . . . . . . . . . . . .
52
5.9 Simulation result: case 5 . . . . . . . . . . . . . . . . . . . . . . . .
53
5.10 Simulation result: case 6 . . . . . . . . . . . . . . . . . . . . . . . .
54
5.11 Simulation result: case 7 . . . . . . . . . . . . . . . . . . . . . . . .
55
5.12 Simulation result: case 8 . . . . . . . . . . . . . . . . . . . . . . . .
55
5.13 Experiment with different parameter sets: real image . . . . . . . .
56
6.1 Energy function with different data . . . . . . . . . . . . . . . . . .
62
6.2 Simulation result: RGB decomposed images . . . . . . . . . . . . .
63
6.3 Experiment with RGB decomposed images: real image . . . . . . .
64
6.4 Experiment with HSI decomposed images: real image . . . . . . . .
66
v
6.5 Experiment with Ohta’s color decomposed images: real image . . .
67
6.6 Experiment with para+RGB Multi-Snake: real image . . . . . . . .
70
6.7 The target images of multi-spectral remote-sensing . . . . . . . . .
74
6.8 Experiment with multi-spectral remote-sensing images (1) . . . . .
76
6.9 Experiment with multi-spectral remote-sensing images: enlarged (1)
77
6.10 Experiment with multi-spectral remote-sensing images: enlarged (2)
78
7.1 Around the concave boundary region . . . . . . . . . . . . . . . . .
83
7.2 Principle of Curvature Snake . . . . . . . . . . . . . . . . . . . . . .
85
7.3 Curvature Snake Only . . . . . . . . . . . . . . . . . . . . . . . . .
87
7.4 CMS: (α, β, γ)+(0, 0, 0, δ) . . . . . . . . . . . . . . . . . . . . . . .
88
7.5 CMS: (α, β, γ)+(α, β, γ, δ) . . . . . . . . . . . . . . . . . . . . . . .
89
7.6 CMS: Original Snake (1 or 2 agents) ＋ Curvature Snake (1 or 2 agents) 90
7.7 Effects of the Number of Representative Points . . . . . . . . . . . .
91
7.8 CMS (α, β, γ)+(α, β, γ, δ): real . . . . . . . . . . . . . . . . . . . .
92
vi
表目次
5.1 Experiment results using artificial images . . . . . . . . . . . . . . .
50
5.2 The number of control point . . . . . . . . . . . . . . . . . . . . . .
50
5.3 Performances of experiments:(1) Parameter cooperation . . . . . . .
58
6.1 Intensity of the experiment image . . . . . . . . . . . . . . . . . . .
63
6.2 Performances of experiments:(2) decomposed images
. . . . . . . .
68
6.3 Multi-Snake: Loop . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
6.4 Performances of experiments . . . . . . . . . . . . . . . . . . . . . .
79
7.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
vii
概要
画像から意味のある特徴を完全に抽出するのは非常に難しく, 画像理解は不完全で
不正確な情報に基づいて推定を行うことでしか実現できていない現状がある. その
ため, 重要な中心課題となるのが領域抽出であり, その結果の良否は画像理解システ
ム全体の結果に大きな影響を与える.
Kass らによって提案された動的輪郭モデル Snake は, 画像中の対象物の輪郭に
最も近い形状において最小となるエネルギー関数を定義し, 対象物の輪郭を求める
問題をエネルギー最小化問題として解くものである. このエネルギー関数は, 対象
の形状に関するエネルギー項と画像濃度に関するエネルギー項からなり, 各エネル
ギーのバランスを決定付けるパラメータを適切に調整することで様々な形状の抽出
を可能にする. Snake は原理が単純であることに加え, 閉じた輪郭をモデル化して
いるため閉領域を安定して抽出でき, また, 対象物の特徴についての知識を抽出処理
に埋め込むことが可能である. このような優れた性質をもつため盛んに研究が行わ
れている. しかしながら一般に Snake は, 初期閉曲線によって解が変化することや,
目的の輪郭に適したパラメータの選定が難しいこと, さらに輪郭に沿った局所的な
画像特徴の情報に強く依存し, 対象と背景において特徴量分布が複雑な場合や特徴
量が不足している場合に抽出精度が低下するといった問題がある. これらの Snake
の精度を低下させる最大の要因の 1 つとして, 対象画像の特徴量分布とパラメータ
調整されたエネルギー関数によって設定される Snake の解空間が多峰性の複雑な形
状になり, 局所解が多数存在することが挙げられる. 本論文では, このような問題を
改善するために分散協調を取り入れた Snake を提案する.
分散協調処理とは, 独立性, 自律性をもつ複数の知的エージェントに問題解決を
分散化し, エージェント間での情報の共有と協調を行い, これによって与えられた解
空間における局所解への誤収束を回避し, 最適解に到達する可能性を高める方策で
ある. 各エージェントはそれぞれ問題解決を並行して進め, 同時に解候補を探索す
る. 探索途中, 各エージェントはその途中経過情報を他のエージェントと交換し, 他
のエージェントから受け取った情報に基づいて自身の探索経過を修正する. 分散協
調処理では以上のような情報の共有と協調動作によって, エージェントのどれか 1
1
つが局所解に陥りそうになっても全体としてそれを回避し, 高度な探索能力を実現
する.
一般的に, 分散協調化がもたらす効用は, (1) 多数のエージェントが協力して問題
解決を行うため, 全体の処理能力, 処理効率が向上する, (2) 単体では問題解決の不可
能な問題でも, 多数のエージェントによる協調動作によって問題解決が可能になる,
(3) あるエージェントが問題解決に適していない場合であっても, 他のエージェント
によって補うことが可能であり, より柔軟な問題解決が可能になる, (4) エージェン
トの追加によって容易に拡張, 機能追加が可能になる, などが挙げられる.
本論文で提案する分散協調型 Snake は, 上記のような分散協調を輪郭抽出処理に
取り入れることによって輪郭抽出処理における柔軟性と拡張性の実現を目指す. す
なわち, Snake のもつパラメータ組や局所的な画像特徴量への依存性といった脆弱
性を改善し, より安定した抽出処理を行うことによって抽出精度の向上を図る.
具体的に本論文では, 複数の Snake を適用して協調させるが, 単一領域に設定さ
れた同一の初期閉曲線から探索を行うエージェントによる分散協調について論じる.
これらのエージェントには, パラメータ組を変えるもしくは与える画像データを変
えるなどして異なる解空間を与える. 各エージェントは与えられた解空間を独自に
探索し, その過程においてエージェント間でエネルギー勾配情報を共有, その情報に
従って自身の探索過程を修正する. 以上のような動作によって, 局所解すなわち偽
の輪郭への誤収束を回避し, より高精度な輪郭抽出を目指すことが可能になる. 本
手法はこのように, 非常に簡素な設計でありながら, それだけでも精度向上をもた
らすだけでなく, 様々に提案されてきた従来の Snake の改善手法と排他的に競合す
ることなく, 併用して更なる精度向上を見込むことができるという大きな特徴を有
する, 拡張性のある輪郭抽出手法である. 本論文では, 実験を通して本手法の有効
性を検証し, また, 応用としてリモートセンシングのマルチスペクトル画像におけ
る輪郭抽出実験を行い, 本手法の有効性を示す. さらに, ユーザーが設定する初期
閉曲線から得られる対象物の形状情報をモデルとしてエネルギー関数に導入した新
たな Curvature Snake とオリジナルの Snake を協調させた Curvature Multi-Snake
(CMS) を提案する.
本論文は次のように構成される. 第 2 章では, 動的輪郭モデルの原理と問題点, ま
た Snake の改善手法として提案された従来手法について述べる. 第 3 章では, 分散
協調処理の概要と画像理解システムにおける分散協調システムの概要を述べること
により, 本研究の着眼点を明確にする. また, 第 4 章で Snake に分散協調処理を適用
した新たな方式について述べ, 第 5 章で複数パラメータ協調の方式について述べ, 人
工画像と実画像を用いた実験を通して本手法の有効性の検証, 性能評価, また第 6 章
2
で複数データ協調の方式について述べ, 人工画像と実画像を用いた実験を通して本
手法の有効性の検証, 性能評価, また, リモートセンシングにおけるマルチスペクト
ル画像を対象とした応用, 実験を通した検証, 性能評価について論じる. さらに, 第 7
章では, Curvature Snake とオリジナル Snake によって分散協調を行う Curvature
Multi-Snake (CMS) の方式について述べ, 人工画像を用いた実験を通してその有効
性を検証を行う. 最後に第 8 章は, 本論文の研究成果と残された課題である.
3
第1章
1.1
序論
研究背景
画像中から興味ある物体の領域とその輪郭を正確に抽出することは, 画像理解に
おける最も重要な問題でありながら, 解決の困難な課題である. 画像をある一定の
特徴を持つ小領域に分割する手法はこれまでに様々な手法が提案されており, それ
らは大きく分けて, クラスタリングによる領域分割手法と輪郭線追跡手法の 2 つに
分けることができる [1].
前者の領域分割手法は, さらに 3 つに細分化することができる. すなわち, 画像特
徴を特徴空間に写像して分類する手法, 統計的特徴量によって解析するテクスチャ
解析, 領域拡張法 (Region Growing) に代表される近接する領域の類似度を用いて
領域を統合もしくは分割する手法である.
一方で, 後者の輪郭線追跡手法の一つとして, まずフィルタなどを用いてエッジ抽
出を行い, 抽出されたエッジ点を追跡, 接続することによって輪郭線を抽出するもの
がある. しかしながら一般に実画像においては, 検出されたエッジが不連続である
場合や対象物以外のノイズが存在する場合に目的の輪郭が得られず, また対象物の
輪郭の全ての点で明確な輪郭線を得られることは稀であるため, 局所的なエッジの
接続から正確な輪郭を得ることは非常に困難である. これを克服するためには, な
にがしかのヒューリスティックな情報に基づいた接続を行わなければならない.
このような制限を取り除くため, Kass らによって動的輪郭モデル Snake [2](以下,
単に Snake と呼ぶ) が提案されている. これは, 輪郭が画像中の対象物体の輪郭に
最も近い形状の時に最小となるエネルギー関数を定義し, そのエネルギー最小化問
題として, 対象の輪郭抽出を行うものである. エネルギーは, 対象の形状に関するエ
ネルギー項と画像濃度に関するエネルギー項からなり, Snake はこれら 2 つのエネ
ルギーのバランスを決定するパラメータを適切に設定することによって, 様々な形
状の抽出を行う. Snake は原理が単純であることに加え, 閉領域を安定して抽出で
きること, 対象物の特徴についての知識を抽出処理に埋め込むことができること, な
4
どに優れており盛んに研究が行われている [3, 4].
また, エッジを用いた輪郭抽出法には, 事前知識から得られた対象のモデルを用
いて形状に制限を設け対象物を抽出する手法があるが, Snake は自身の輪郭線を変
形させることによって目的の輪郭線を抽出するため, 抽出対象の形状に制約を与え
ないといった利点があり, その適用範囲は広い.
Snake の応用範囲は, 輪郭抽出のみならず, 動画像における動体追跡や, 三次元形
状復元など多岐にわたる. しかしながら, Snake は一般的に, ユーザーが設定する初
期閉曲線から逐次処理によって対象輪郭を抽出するため, 初期閉曲線によってその抽
出結果が左右されることや, 目的の輪郭に適したパラメータの決定が難しいという
問題がある. この問題を解決するために提案された従来の手法では, 抽出対象の事前
知識から得られたモデルを利用することによるパラメータ決定の労力とパラメータ
への依存性の軽減が図られてきたが, これらの手法では対象物の形状や画像が事前
知識から得られたモデルで十分によく近似できることを前提としている. したがっ
て, 抽出対象をある程度限定することによる精度向上を目指しているが, Snake の動
的な性質を削いでしまう. また, Snake は輪郭に沿った局所的な画像特徴量に強く依
存し, 対象領域と背景領域の内外それぞれにおいて複雑な特徴量分布がみられる場
合など, 望むようなエッジを得られない場合には輪郭抽出が困難になり, 抽出精度が
低下してしまう. このような問題を解決するために, 複数の Snake を複数の領域に
適用する手法が提案されている. これらの手法は, 画像全体を分割することになり,
大局的な特徴抽出を可能にするが, 適切な数の初期閉曲線を適切な箇所に設定する
ことが必要であり, 使用者の労力の増大が引き起こされるといった欠点をもつ.
1.2
研究目的
本研究では, Snake の輪郭抽出処理における柔軟性と拡張性の実現に関する研究
を行う. ここでいう「柔軟性」とは, Snake がもつパラメータ組や画像特徴量への
依存性といった Snake 自身や対象画像への制約を軽減することを指し, 特定の対象
への抽出精度を向上させるのではなく, その代わりにどんなものでも安定した抽出
が可能な Snake の実現を目指す. すなわちパラメータ組の不適合による抽出の精度
低下を回避し, また必要な情報が不完全であったり不適当であるような場合にも, う
まく抽出できる方式を提案する.
分散協調処理とは, 問題解決を, 独立性, 自律性をもつ複数の知的エージェントに
分散化し, 与えられた解空間における局所解への誤収束を回避し最適解に至る可能
5
性を高める方策である. エージェントはそれぞれ, ほぼ同一の問題解決を並行して
進め, 同時に解候補を探索していく. そうして複数のエージェントから得られた複
数の解候補に基づいて, 相互に途中経過情報を授受し, 受け取った情報に基づいて自
身の探索経過を修正する. このような情報の共有と協調動作によって, たとえどれ
か 1 つのエージェントが局所解に陥りそうになっても, 全体としてそれを回避し高
度な探索能力を実現しようとするものである. 本研究では, 単一領域に複数の Snake
を適用して協調させるものであり, 複数領域にそれぞれ Snake を適用するという分
散協調処理ではない. 従って, 非常に簡素な設計でありながら, それだけでも精度向
上をもたらすだけでなく, そのシンプルさ故に, 様々に提案されてきた従来の Snake
の改善手法と排他的に競合することなく, 併用して, 更なる精度向上を見込むことが
できるという大きな特徴を有し, 拡張性のある輪郭抽出手法である. また本手法の
応用として, リモートセンシングのマルチスペクトル画像における輪郭抽出実験を
行い, 本手法の有効性を示す.
1.3
本論文の構成
本論文は次のように構成される. 第 2 章では, 動的輪郭モデルの原理と問題点, ま
た Snake の改善手法として提案された従来手法について述べる. 第 3 章では, 分散
協調処理の概要と画像理解システムにおける分散協調システムの概要を述べること
により, 本研究の着眼点を明確にする. また, 第 4 章で Snake に分散協調処理を適
用した新たな方式について述べ, 第 5 章で複数パラメータ協調の方式について述べ,
人工画像と実画像を用いた実験を通して本手法の有効性の検証, 性能評価, また第 6
章で複数データ協調の方式について述べ, 人工画像と実画像を用いた実験を通して
本手法の有効性の検証, 性能評価, また, リモートセンシングにおけるマルチスペク
トル画像を対象とした応用, 実験を通した検証, 性能評価について論じる. さらに,
第 7 章では, 新たに提案する Curvature Snake とオリジナル Snake によって分散協
調を行う Curvature Multi-Snake (CMS) の方式について述べ, 人工画像を用いた実
験を通してその有効性を検証を行う. 最後に第 8 章は, 本論文の研究成果と残され
た課題である.
6
第2章
動的輪郭モデル Snake
画像中から, ある一定の特徴をもつ小領域に分割する領域分割は, 対象領域を意味あ
る特徴として完全に抽出することが非常に難しく, 画像理解の過程において必要不
可欠な処理でありながら, 未解決な問題である.
従来の領域分割法の中に, エッジ情報を用いた輪郭抽出に分類される動的輪郭モ
デル (Active Contour Model) Snake [2] がある. この手法は, 従来のエッジに基づ
く輪郭抽出のような, 前処理を行ってそのエッジの接続点を求めるといったボトム
アップ型の輪郭抽出とは異なり, 目的の輪郭付近で最小となるエネルギー関数を用
いて, ユーザーが与えた初期値に基づき対象の輪郭抽出を行うトップダウン型輪郭
抽出を行う. すなわち, 適当な初期値から最小値 (最適解) を探索する, エネルギー
最小化原理に基づく輪郭抽出法である. この手法は, 原理が単純であり, 閉じた輪郭
をモデル化しているため閉領域を安定して抽出でき, また対象物の特徴についての
知識を抽出処理に埋め込むことができる手法として幅広く研究されている [3–5].
2.1
Snake の原理
Snake は, 画像中のある閉曲線 v(s) = [x(s), y(s)], s ∈ [0, 1] に対して, 対象領域の
輪郭でエネルギーが最小となるようなエネルギー関数を定義し, これを最小化する
ことによって輪郭抽出を行う手法である.
一般に, エネルギー関数は, 式 (2.1) に示すように, 閉曲線の内部エネルギー
Eint (v(s)) (式 (2.2)) と, 外部エネルギー Eext (v(s)) (式 (2.3)) との線形和の積分
で以下のように定義される.
{Eint (v(s)) + Eext (v(s))}ds
(2.1)
Eint (v(s)) = (α|vs (s)|2 + β|vss (s)|2 ) / 2
(2.2)
Eext (v(s)) = −γ|∇I(v(s))|2
(2.3)
Esnake =
7
図 2.1: Active Contour Model
ここで vs (s), vss (s) はそれぞれ閉曲線 v(s) の一次微分, 二次微分を表し, ∇I は輝
度勾配を, α, β, γ (> 0) は各々重み係数を表す. 内部エネルギーは輪郭の形状およ
び滑らかさを制御し, 各項にかけられたパラメータを調整することによって, 様々な
形状の抽出を可能にする. 一方外部エネルギーは, 閉曲線 v(s) に沿った画像の濃度
勾配の大きさであり, Snake を対象領域の輪郭付近に引き付け, 目的輪郭で収束させ
る. つまりエネルギー関数全体では, そのパラメータの設定にもよるが, 閉曲線の形
状が円ければ円いほど, その周囲長が短ければ短いほど, また輝度勾配が大きければ
大きいほど小さな値を持つことになる.
Snake は, 図 2.1 に示すように, ユーザーが与える初期閉曲線からエネルギー関数
に基づいて, Snake 自身 (輪郭線) そのものを動的に移動させながら輪郭抽出を行う
ものであり, 対象物のエッジ情報だけではなくその周囲の大局的な性質をうまく利
用した輪郭抽出手法である. 具体的には, 閉曲線上の各点, すなわち各制御点におい
て, それぞれ微小な移動後の関数値の変化を計算し, その勾配が最大となる方向に制
御点を移動させることで輪郭抽出を行う.
2.2
問題点
2.1 で述べたように, Snake は対象物の輪郭に沿ったエッジ情報だけでなく, 輪郭
の形状や滑らかさといった情報を用いて大局的な情報に基づくこと, また閉曲線を
モデル化しているため閉領域を安定して抽出できるなどの優れた性質があり, 対象
領域の輪郭線が鮮明で, ノイズがないなど対象となる画像の性質が良ければ大変良
8
好な抽出結果を与える. しかし, 一般的に以下の問題がある.
• 初期閉曲線への依存
一般に Snake は, 利用者によって与えられた初期閉曲線から, 逐次的に探索
を行うため, 抽出結果が初期閉曲線に左右されやすい. すなわち初期輪郭の位
置によって解が変化するが, これは対象画像の特徴量分布とパラメータを調整
されたエネルギー関数によって形成される解空間が変化し, またその初期閉曲
線の位置によって各制御点の探索経路が変化することが原因であると考えら
れる.
• パラメータ選定
式 (2.2), 式 (2.3) のパラメータ α, β, γ によって内部エネルギーと外部エネル
ギーのバランスを調整することによって Snake は様々な形状の抽出を可能に
する. しかし反面, パタメータによって解が変化するため, 目的の輪郭に適し
たパラメータの決定が難しいという問題点がある. すなわち, パラメータの組
合せにはその抽出する輪郭の形状に一定の傾向が存在し, それが対象物の形状
と適合しない場合, たとえ対象領域と背景領域の境界において十分に輝度勾配
が存在したとしても精度の高い抽出が難しい. また, 対象が部分的に尖鋭部や
凹部をもつ場合は, 最もパラメータの決定が難しく Snake は尖鋭部や凹部へ
の脆弱性をもつといえる.
• 画像特徴量への強い依存
式 (2.3) で表されるように, 対象輪郭付近に引き付けるための外部エネルギー
は, 閉曲線に沿った輝度勾配という局所的な情報を利用するため, 対象や背景
が複雑な画像特徴量をもつ場合や, ノイズが存在する場合, また対象と背景の
輝度変化が極小さい場合などには対象の抽出が困難になる.
2.3
関連研究
2.2 で述べた Snake の問題は, 互いに関係しており各々独立した問題ではないが,
このような問題に対して, 幾つかの方向からのアプローチが提案されている. 本節
では代表的な手法を幾つか示す.
画像からある閉領域の輪郭を抽出する処理では, 抽出対象の形状に関する事前知
識が得られていることが多いため, このような知識を用いてよりノイズに強く, より
安定した輪郭抽出を目指す手法として, サンプル輪郭を用いる手法 [6] や, 統計的モ
9
図 2.2: Energy function
デルを利用する手法 [7] などが提案されている. しかしこれらの手法は, 対象物の形
状や画像が事前知識から得られたモデルで十分によく近似できることを前提として
おり, また輪郭形状の回転不変性などが問題になる.
対象の形状に着目した手法として, トポロジの変化に対応する手法 [8], 凹領域の
内部に輪郭を引き寄せる新たなエネルギー項を加えた手法 [9, 10], また, 複数の抽出
対象を包含する初期閉曲線を許容し, 交差判定を行い, Snake を分裂をさせることに
よって複数の物体を抽出する手法 [11] などが挙げられる.
対象や背景の色, テクスチャに着目した手法は, 目的の輪郭に引き付けるエネル
ギー項を加えた手法として [12–15] が挙げられる. また, 初期閉曲線を対象物の内部
に配置させ, 対象輪郭付近以外のエッジは通過するような膨張エネルギー項を用い
る手法 [16], また, 与えられた初期閉曲線から対象領域と背景領域をクラスタリング
し, 各画素の尤度から Snake の変形を誘導する手法 [17] などが挙げられる.
高速計算法としては, 輪郭線を構成する各点に対して, その点が 8 近傍に移動し
た場合のエネルギー関数の変化を用い, 動的計画法により順次移動する点を決定す
る手法 [18], また同様の手法で Greedy Algorithm を用いる手法 [19] が提案されて
いる.
2.4
複数の Snake の協調による輪郭抽出
2.2 で述べたような Snake の問題の最大の要因の 1 つは, 画像特徴量の分布とパ
ラメータを調整されたエネルギー関数によって形成される解空間が複雑な多峰性の
10
図 2.3: Wada’s approach
解空間, 例えば図 2.2 のような複雑な形状をもち, 単純な山登り法や最急降下法で
は最小化が難しいことである. 関数形に極小値すなわち局所解が多数存在し, それ
らは偽の解となるため, 推定がそのような極小値に誤収束することによって最小値
すなわち最適解に到達することができなくなる. この問題は, Snake が到達した解
が局所解であるか, 最適解であるかを判断することができれば対処することができ,
そのためには複数の Snake を用いてそれらを協調させることが必要である.
このような考え方に基づき, 複数の Snake を用いて協調ないしは競合を行う手法
として, 分散協調処理による領域分割法 [20] や, MDL [21] に基づき成長・競合させ
ることで対象領域を抽出する手法 [22], 複数の Snake を競合させる手法 [23] などが
提案されている. 以下で, これらの手法の概要と問題点について述べる.
2.4.1
分散協調処理による領域分割
和田ら [20] が提案した手法では, 図 2.3 に示すように, 複数の領域にそれぞれ
Snake を実行するエージェントを配置し, それを暫定領域とする. 各エージェント
は, 自身の属する領域と他のエージェントの属する領域との境界を推定し, その推
定境界の位置と自身の現在の暫定領域とのずれを表すエネルギー項を加えたエネル
ギー関数を用いる. このエネルギー関数は, Snake を膨張させるよう定義されてい
る. またこの手法は, エージェントが推定した推定境界に対する暫定領域の到達度
に基づき, エネルギー関数におけるパラメータ α, β の動的な調整を行う. これによ
11
(a) Input image
(b) Seed region
(c) Competition
(d) Segmentation result
図 2.4: Zhu’s approach
り, 内部エネルギーと外部エネルギーの影響力を各エージェントの収束段階に応じ
て調整することができ, より安定した抽出を目指す.
従来の領域分割法と比べ, ノイズにロバストであり, 画像全体を分割する手法と
してはより効率的な輪郭抽出を実現するが, しかしながら, 初期に与える暫定領域
が目的の輪郭に対して適切な箇所に, 必要な個数設定される必要があり, また図 2.3
中に示すように, 他の領域との境界位置の推定にステップエッジを仮定しているた
め, 対象輪郭がそれ以外のエッジをもつ場合に抽出が難しいといった問題がある.
2.4.2
MDL に基づく成長と競合による領域分割
Zhu らは, balloon モデルの Snake [16] と Region Growing を応用して, 図 2.4
の (b) に示すような種とよぶ多数の小領域を画像全体に配置し, これらの小領域が
MDL [21] に基づき (c) に示すような成長と競合を行い, (d) のような複数の小領域
の集合として領域分割を行う手法を提案した [22].
12
この手法は, 対象や背景が異なる特徴からなる複数の領域で構成されている場合
に有効であるが, 多くの種を必要とする他, その種の位置によって抽出結果が変化す
ることなど, 初期設定を行うユーザーの労力は大きく, また対象を滑らかな輪郭線を
もつ領域として抽出できないなどの問題がある.
2.4.3
複数の Snake の競合による領域分割
松澤らは, 図 2.5 (b) に示すように, 対象物体の内外に複数の初期曲線を設定する
手法を提案した [23]. 初期設定の段階では閉曲線である必要はないことが特徴的で
ある. この手法は, 初期曲線に沿った画像特徴量 (R, G, B の輝度等) を取得し, そ
の特徴量の分散が最大となるよう大津の判別基準 [24] に基づき, あらかじめ定めら
れた分割数だけ初期曲線を自動で分割する. それらを元に, 同図 (c) のように複数
の初期閉曲線を生成することにより, 初期設定を行うユーザの労力軽減を図ってい
る. また, 面積項を追加したエネルギー関数をもつ Snake [10] を用いて各 Snake を
膨張させ, 他の Snake と交差した際に, 各 Snake が囲む領域の画像特徴量分布情報
を用いて競合させる.
この手法は, 対象や背景が複数の領域から構成されるような場合にも, クラスタ
リングといった特別な前処理や, 特徴量が一定の領域に適切な数の Snake を設定す
る必要がなく, 画像から得られる特徴量分布情報を用いているため安定した抽出を
実現するが, 初期曲線が特徴量の均一な領域をすべて通過する必要があり, またあら
かじめ適切な数の分割数を決定する必要がある. また, 分割数の違いによって抽出
結果が変化するといった問題点がある.
2.4.4
問題点
前述のこれらの手法は, 対象や背景が複数の領域から構成されている場合におい
ても対象の抽出が可能な手法である. これらの手法は, 複数の Snake を複数の領域
に適用し, 互いに協調もしくは競合をしながら領域分割を行う. また, 対象画像全
体を複数の小領域の集合として抽出する手法であり, 大局的な画像領域分割手法で
ある.
しかしながら, いずれの手法も, 暫定領域, 種, 分割数等によって抽出結果が左右
され, 適切な数の Snake を適切な箇所に設定するといった, ユーザーの負担を増加
させるといった面がある.
13
(a) Input image
(b) Setting and dividing initial curves
(c) Making initial contours
(d) Segmentation result
図 2.5: Matsuzawa’s approach
2.5
Snake についてのまとめ
本章では, まず動的輪郭モデル Snake の原理について述べるとともに, 従来研究
の紹介をした. Snake は原理が単純であり, 閉領域の安定した抽出や対象物の特徴
を抽出処理に埋め込むことを可能にする有効な輪郭抽出手法である. しかしながら
一方で, 初期閉曲線への依存性, パタメータによる解の変化, 閉曲線に沿った局所的
な輝度勾配への強い依存といった問題点があり, これは Snake の解空間が多峰性の
複雑な解空間になることが最大の要因の一つであることを指摘した.
そして, このような問題に対処するために, 複数の Snake による協調が必要であ
ることを述べ, この方針に基づき提案された従来研究を紹介した.
14
第3章
分散協調処理
Snake を含む最適化計算を用いた計算法では, 通常は適当な初期値から始まる反復
計算により最適値を計算する方法が用いられており, この場合, 解空間の単調性が重
要になる.
解空間が複雑な非線形性をもっている場合に, 推定ないし最適化の問題を一般的
に解決し, 局所解へ陥ることによる誤収束をできる限り避けて, 最適解を得る可能性
を高める方法として様々な手法がある. 特に焼鈍し法 (Simulated Annealing) や遺
伝的アルゴリズムなどの確率的手法が用いられることが多いが, しかしながら, それ
らは処理時間の大幅な増加を招く.
一方で, 複数の可能性を並行に探索していく多点探索の一つである分散協調型
の探索も有効な手法であって, 分散人工知能 [25, 28] の分野で勢力的な研究がなさ
れており, 理論的枠組みや多体軌跡推定への応用などでの成果が報告されてきてい
る [29–31].
本章では, まず分散協調の概略を示し, 次に画像理解分野においてこれまでに提案
されてきた分散協調型システムを示すことによって, 本研究の着眼点を明確にする.
3.1
分散人工知能とエージェント
分散協調は, 分散人工知能 (DAI: Distributed Artificial Intelligence) の分野で盛
んに研究がなされている. 分散人工知能では, 単一ではそれほど高度な能力をもた
ない問題解決器 (エージェント) が協調することにより, 複雑な問題をいかに速く,
正確に, そして柔軟に解くことができるのかということに焦点をあてて研究が進め
られている. つまり人間社会のような知的なエージェント群の相互作用を研究対象
としているといえるが, その目標とする構成は中央集権的な構成のない完全に平等
な形態ではなく, もともと独立に存在するエージェントを陽に意識し必要に応じて
組織し, 統合し, また協力関係を築いていくことを目標としており [25], エージェン
15
トはその自律性と相互作用性が強調されている.
エージェントは, ある問題において複数に分割された下位問題の解決を試み, そ
の性質は, 自律性, 社会性, 反応性, 自発性が挙げられる [26].
• 自律性
エージェントは, 他のシステムや人間からの直接の制御を受けることなく, 独
立して動作することができる. すなわち, エージェントは知識や問題解決機能
をもち, 自己の行動を決定する能力をもつ.
• 社会性
エージェントは, 他のエージェントと協力して自己の目的を達成する. そのた
め, エージェントは, 互いに理解可能な言語や, 協調や交渉のためのプロトコ
ルを共有する.
• 反応性
エージェントは, 自分の置かれた環境を認識し, そこで発生するさまざまな変
化に対して, あらかじめ決められた行動をする.
• 自発性
エージェントは目標や行動規範をもち, 自分の状態や外部の状況に対応して自
発的な行動を行う. 外部から与えられるデータやイベントによって受動的に
動作する従来のプログラムとは異なり, 能動的に行動することが可能である.
以上の全ての性質を兼ね備えるエージェントの実現は難しいが, その動作によって
以下のように分類することができる.
(a) 個々のエージェントの自律性に関する分類
• 自律的エージェント
まわりの状況を理解し意思決定原理をもち, これに基づいて自発的に行動を行
うエージェントの総称.
• 知的エージェント
自律的エージェントであり, かつ知的問題解決を行うエージェントの総称. 高
度なものは, 擬人化された心理状態をもち, さらに学習などの機能をもつ.
16
• 反応型エージェント
反射的な刺激–反応行動を行う自律的エージェントで, 心的状態や知的な問題
解決機構はもたない. 個々の振舞いは知的ではないが, それらの相互作用の結
果, 全体として知的振舞いを行っているように観察できる.
(b) エージェントの集団の問題解決の様式に関する分類
• マルチエージェントシステム
一般に, 個々のエージェントの問題解決能力はそれほど高くないが, それらの
協調や交渉などの相互作用により, 複雑な問題の解決を行うことが可能なエー
ジェントの集団をマルチエージェントシステムという.
– 協調問題解決型マルチエージェントシステム
複数のエージェントが共通の目標をもつマルチエージェントシステム. こ
のエージェントシステムでは, 組織を構成することにより協調して全体
で共通の目標を達成する.
– 均衡化型マルチエージェントシステム
個々のエージェントが独立の目標をもつマルチエージェントシステム. こ
の場合, 異なる目標をもつことによって発生するエージェント間の競合
を解消し, システム全体として好ましい均衡を保ちながらそれぞれの目
標を達成する.
(c) エージェントの役割に関する分類
• 利用者エージェント
インターフェースエージェントとも呼ぶ. 利用者のコンピュータやネットワー
クの使いやすさを促進する役割を果たすエージェント. 利用者の要求を理解
し, これに基づいてコンピュータやネットワークを操作し情報処理や検索を行
い, その処理結果を利用者にわかりやすい形式で提示する.
• タスク処理エージェント
計算, 検索などのタスクを処理する問題解決のためのエージェント. 他のタス
ク処理エージェントや利用者エージェントと協調して, 複雑な問題解決を行う.
エキスパートシステム, CAD システム, データベースや科学技術計算などさ
まざまな領域へ適用される.
17
• 通信エージェント
利用者やエージェント間の通信の役割を果たすエージェント. あるいは, 通信
システムやコンピュータネットワークシステムの保守, 運用を支援する役割も
もつ.
(d) その他の用法
• ネットワークエージェント
コンピュータネットワークの中に存在し, さまざまなサービスを行うエージェ
ントの総称.
• 移動エージェント
ネットワークのなかを移動して, 目的とする作業を実行するエージェント. 移
動後は通信回線を切断しても, その環境の中で自立的に作業を続ける.
• 擬人的エージェント
人間のもつ知性や心理状態をもつエージェント.
• コンポーネントエージェント
エージェント指向に基づいて構成されるソフトウェアの部品エージェント.
人工知能の一分野である分散人工知能が注目を浴び始めた理由としては, 単一の
人工知能システムでの処理能力の限界や, ネットワーク環境の充実, 情報処理アーキ
テクチャとしての妥当性などが挙げられる.
3.2
分散協調の概略
分散協調は, その名の表すように協調問題解決型マルチエージェントシステムの
範疇に入る. 「分散」の概念は, エージェントが複数に分離して存在することを示
し, 分散協調の本質であるが, 一方「協調」はもっと多様な概念である. つまり, エー
ジェント同士が協力し合って解を求めるのか, 競合しあって安定状態を作ろうとす
るのか, といった問題の種類に依存した概念の全てを協調という一語が担っている
場合がある. 協調の典型的な問題は, 探索問題であり, これは既に解空間が与えられ
ている場合においていかに効率的に最適解を求めるかを定式化したものである. 一
方, 競合の典型的な問題は, 各エージェントとしては最適な状態でなくとも, 全体と
18
(a) 単一のエージェントによる問題解決
(b) 分散協調による問題解決
図 3.1: Problem Solving
して安定, 調和している状態を求めるものである. つまり分散協調とは, 複数の独立
性, 自律性をもつエージェント (プロセス) をもち, 各エージェントはある程度シス
テム全体を意識しながらそれらの間で協調関係を築くことで, 最適な解 (もしくは
状態) を求める機構を指す [31].
一般に複雑な問題に対しては図 3.1(a) に示すように幾つかの部分問題に分割し,
それを順に解決して最後にそれらの部分解を統合することにより, 目的とした問題
の解を得る方法が有効である. 一方で同図 (b) に示すような問題解決法では, 分割
された部分問題をそれぞれ異なる複数のエージェントに割当てることにより, 個々
のエージェントは比較的小規模で単純なソフトウェアシステムとなるため, その実
現と保守は容易になり, 全体の処理時間も軽減される. 個々のエージェントが, ネッ
トワークで接続された複数の計算機に分散され実行される場合は, 問題解決に要す
る時間のさらなる短縮も期待できる.
図 3.1(a) に示すような問題解決では一般に, 対象を状態と, 次の状態を生成する
推論機能である作用素から構成されるグラフ (状態空間) で表し, 初期状態から目標
状態に至る経路を探索する問題と定義されている. ここで状態の集合である状態空
間を S, 初期状態の集合 I, 目標状態 G, とすると図 3.1(a) のようなエージェントに
よる問題解決システムは図 3.2(a) のように表すことができ, エージェントは状態空
間を探索することにより解に到達する. しかし状態空間が大きくなると, 1 つのエー
19
(a) 問題解決システムと状態空間の探索
(b) エージェントによる状態空間の分割
図 3.2: Search in Solution Space
ジェントだけでは解の探索が難しくなるといった問題がある. 一方で, これに対し
て図 3.2(b) のように, 状態空間を幾つかの領域に分割してそれぞれの領域を多数の
エージェントで分担することにより, 解の探索効率を向上させることができる可能
性がある.
エージェント A1 –A6 は, 図中に示すようにそれぞれが担当する領域内での初期
状態の 1 つから目標状態の 1 つ (A1 における s1 ∈ I1 から s2 ∈ G1 , A2 における
s2 ∈ I2 から s3 ∈ G2 , A3 における s3 ∈ I3 から s4 ∈ G4 ,...) に至る経路を発見し
ていたとすれば, 源問題の初期状態の 1 つ s1 から s4 に至る経路を 3 つのエージェ
ント A1 – A3 の協調によって発見されたことになる. このような分散協調方式が
図 3.2(a) の単一のエージェントによる問題解決に比べ効率的である理由は以下のこ
とが挙げられる.
1. 各エージェントの探索領域が小さくなり, 並列探索と結果統合により全体の探
索時間が短縮される.
2. 各エージェントの探索領域が小さいため, 各エージェントがもつべき知識の種
類と量が減少する.
しかしながら, このような問題分割の方式には, 各エージェント Ai の初期状態集合
Ii と目標状態集合 Gi をどのように定めるか, という課題が残されている. すなわ
ち, それらの決め方次第で探索効率が大きく差が出るため, 各エージェントは探索領
20
域, 初期状態集合, 目標状態集合を決定するために, 互いに情報を交換し協調するこ
とが必要になる.
一般的に協調的な問題解決の過程は, 問題の分割と割当て, 副問題の解決, 解の統
合の 3 つの段階より成り立っている [27]. 各段階は次のようになっている.
(a) 問題の分割と割当て
分割統治法のように, 問題を分割して解決する手法は従来から見られるが, これら
従来の問題解決では問題やシステムの能力が固定的である静的な環境を前提として
いるのに対し, 分散協調型のシステムではそれらが変化する動的な環境を前提とし
ている. すなわち, どのような問題がいつ与えられるのかが既知であるとは限らず,
割当てた副問題の正確な解決時間の推定ができないことや, 突然の故障などによる
エージェントの種類や数の変化といった状況への対処が不可欠である. したがって,
分散協調型のシステムでは, 最適な問題分割や割当てをあらかじめ求めることより
も, エージェントの状況や環境の変化に応じて動的に問題の分割や割当てを行う手
法が有用になる.
(b) 副問題の解決
もし問題が独立した副問題に分割されていれば, エージェントは単に割当てられ
た副問題の解決に専念すればよい. しかし, 副問題間になんらかの制約関係が残さ
れている場合には, それらを調整しながら解決をしていく必要がある. ここでは副
問題の解決の際のエージェント間での調整機構が重要になる.
(c) 解の統合
問題が独立な副問題に分割されていれば, その解は部分解を組み合わせるだけの
単純なものになる. しかし, 問題の分割がエージェント間で重複を含んだり, 副問
題の解決に利用されるデータに曖昧さを含んだりするような場合には, それぞれの
エージェントにおいて, 冗長であったり不正確であったりするような部分解が得ら
れる場合がある. そのような場合には, 部分解の選択や統合を適切に行う機構が重
要になる.
以上の過程は再帰的に実行されることもある. すなわち部分問題を割当てられた
エージェントはさらに問題を分割し, 他のエージェントに割当てることも可能であ
る. また, あらゆる協調問題解決が必ずしも上記 3 つの段階を経るとは限らず, 問
題によっては必ずしも 3 つの全てのステップを実行する必要のないものもある. こ
のような複数のエージェントによる分散協調問題解決は, タスク共有と結果共有と
呼ばれる 2 つの問題解決手法に整理できる.
21
タスク共有手法は, 問題解決の負荷をあらかじめ複数のエージェントに分割して
割当て, 各エージェントは与えられたサブタスク (副問題) を解決することを目標に
する. したがって, 問題解決の過程の制御はゴール駆動であり, サブタスクの解決が
エージェント間の調整により適切に行われれば, 実行した結果がそのまま全体解と
なり, 解の統合は自明である. すなわちタスク共有では, 不定期に発生するタスクを
いかに適切なエージェントに割当てるか, またその実行時にいかにエージェント間
で調整するかが重要な課題であり, 問題の分割と割当ての過程が中心となる問題解
決手法といえる. タスク共有が有効な手法は, 工場内に存在する複数の機械とそれ
を管理するエージェントからなる工場スケジューリングが代表的なものとして挙げ
られる.
一方, 結果共有手法は, 解統合の過程が中心となる問題解決手法であり, 複数の
エージェントが各自に与えられたサブタスクの解を持ち寄り, タスク自体を解決し
ていくという協調の手法をとる. すなわち各エージェントは, 他のエージェントか
ら与えられる情報を参考にして, 自分自身のタスクを遂行する. したがって, 問題解
決過程の制御はデータ駆動である. この手法を利用する場合には, エージェント間
で情報を交換するための枠組みが必要になる. 結果共有が有効な代表的問題事例は
センサネットワークである. センサネットワークでは, 地理的に分散したセンサと
それを管理するエージェントから構成され, その情報をもとに動体の進路予測を行
う. 分散して存在するエージェントはセンサからの情報を統合して, 全体的な解釈
(解) を導き出す. つまりセンサネットワークにおいてはエージェントは既に配置さ
れており, そのセンサ領域も決定されているので, エージェントが実行すべきサブタ
スク (センサ領域内の信号処理と解釈) は既に自明となっている. そして問題解決の
重要な点は, 各センサの情報を統合して, 全体的な解釈を行う解統合の過程にある.
3.2.1
分散協調探索
問題解決の分散化の意義は, 観測者などが地理的, 物理的距離をもって分散して
いる場合における問題解決や, 問題を複数に分解して同時に解決を進めるような問
題解決 (機能分散), また探索の効率化, が可能になることなどが挙げられる. 特に,
探索の効率化を目指す方策としての分散探索があり, これはさらに 2 つのアプロー
チに細分化できる. すなわち, 複数のエージェントがトップダウン探索とボトムアッ
プ探索をそれぞれ実行し, 相互に探索経過情報を授受することによって解候補の削
減する方式と, もう 1 つには, 複数のエージェントがほぼ同一の問題解決を進め, 同
時に複数の解候補を探索していく途中で相互に探索経過情報を授受することによっ
て, どれか 1 つが局所解に誤収束しそうになっても全体としてそれを回避すること
22
図 3.3: Cooperative Multi-Point Search
23
によって, 局所解へ陥る恐れを減じて最適解に至る可能性を高める方式 (協調型多
点探索, 図 3.3) である. 厳密に言えば, これら 2 つの手法は互いに関係をもつもの
であり, いずれも探索の効率化に向けた有力な手法である.
後者のように, 単体でも探索可能なプロセス (エージェント) がそれぞれ解候補集
合 (探索空間) をもち, 全体では複数の可能性を並行に探索していく多点探索におい
ては, 探索する解空間の単調性が重要になる. もし解空間が単調性を示せば, 各エー
ジェントはそれぞれ局所的な探索を行い, 解を統合するだけでよい. しかし, 解空間
が非線形の複雑な形状となる場合, 問題は複雑になる. 協調型の多点探索はこのよ
うな問題に対して解法を与えようとするものであり, エージェントは探索途中で自
身の中間探索結果などの情報の授受を行う. そのようにして, 他のエージェントの
探索経過を知り, 自らの探索過程を修正していく. これは分散インタプリテーショ
ンにおける中間モデルの交換と協調, 分散プランニングにおける中間プランの交換
と協調に相当する.
一般的に, このようなエージェント間での情報の共有によって探索経過への制約
を与え, それを満たしていくと解は必ず一つに絞ることが可能である, といった前提
は正しくない. 解が無数に存在する場合や, 局所解が無数に存在する場合には, エー
ジェント間で適切な情報を選択し共有しなければ, 全体として最適解に到達するこ
とは非常に難しく, 情報共有の手法が常に成功するとは限らない. しかしだからと
いって, エージェント自身は解くべき問題や状況についての完全な情報を保持する
必要はなく, いかに適切な情報を選択するかが重要である. 例えば, 何らかの評価値
を最小化するような問題では, その時点での評価値そのもの, または評価値の勾配を
授受するのが効果的である. 分散人工知能の分野では, 代表的な探索手法である A
∗ 探索アルゴリズムの分散協調化に評価値交換手法を適用し, 共通例題である迷路
探索で効果を立証した初期の研究事例 [33] などを端緒として, その後様々な展開が
図られている. つまり各エージェントは, 自身がもつ部分的な情報に従い解を探索
し, 他のエージェントとの情報共有により自身の探索経過を修正しながら, 最終的に
システム全体としての最適解を得る.
協調型の探索では, 上記のような並行動作と連携により, いずれかのエージェン
トが局所解に陥った場合に, 他のエージェントからの情報によってそこから脱出し,
全てのエージェントができるだけ最適な解を目指すことを可能にする. したがって,
誤収束の低減による探索性能の向上が期待できるようになる.
このような枠組みに基づいて吉田らは, 分散協調による多体軌跡追跡手法を提案
し [30], 分散協調の理論的枠組みや分散協調システムの有効性を検証している.
多体軌跡追跡 (図 3.4(a)) では限られたセンサ情報から, センサ情報とターゲット
24
Y
B 1, 2(k)
TARGET2
PROCESSOR
TARGET1
B 1,3(k)
SENSOR
TARGET3
B 1,1(k)
SENSOR
B 2,2 (k)
B 2,3(k)
B 2,1(k)
SENSOR
SENSOR
PROCESSOR
SENSOR1
SENSOR2
PROCESSOR
X
(a) Multitarget Motion Analysis
(b) Grouping of Scensors
図 3.4: Multitarget Motion Analysis by Decentralized Cooperation
’cent’
’lo’
’iso’
140
120
’SA’
’lo’
600
500
100
ASE
ASE
400
80
300
60
200
40
100
20
0
0
0
2
4
6
8
iteration
10
12
14
0
(a) Centralized, Isolated vs. Cooperative
10
20
30
60
70
(b) Annealed vs. Cooperative
図 3.5: Avarage Square Error Convergence
25
40
50
iteration
80
の対応付け, その対応付けに基づくターゲットの軌跡推定を行う必要がある. これは
一般的に NP 困難であり弛緩法による段階的最適化が多く用いられるが, 偽の解す
なわち局所解が多数存在し, 真の解すなわち最適解を得ることが難しい. この問題
を解決するため, 焼き鈍し法を用いた確率的探索法による改良手法 [32] が提案され
成果を収めたが, しかしながら処理時間の大幅な増加を招いている. 吉田らのシス
テムは図 3.4(b) に示すようにセンサをグループに分割し各グループに 1 つのプロ
セッサを配置, センサ情報を近傍プロセッサに送りプロセッサ間で中間推定結果を適
宜通信交換しながら処理を進める. 文献 [30] では, 従来の集中処理型, 焼き鈍し法,
センサをグループ分けして複数プロセッサを配置するが協調は行わない分散孤立型,
分散協調型の 4 手法の性能評価を行い, そのシミュレーション実験によって, 十分な
解の品質を焼き鈍し法よりも効果的に達成し得ることが示されている (図 3.5). す
なわち文献 [30] は, 多体軌跡推定への新たなアプローチを提案したのみならず, 分
散協調の有効性を多体軌跡推定という実際的問題で検証したものであり, 分散協調
型探索の一般的, 理論的研究に対する裏づけ事例の 1 つになっている.
以上のように分散協調探索は, 複数のエージェントがほぼ同一の問題解決を進め,
同時に複数の解候補を探索していく途中で相互に探索経過情報を授受することに
よって, エージェントの誤収束を回避し, 全体として局所解へ陥る恐れを減じて最適
解に至る可能性を高める方式であり, 焼き鈍し法といった確率的手法と同様に十分
な解の品質を, より効率的に求めることが可能な手法である.
3.3
画像理解システムにおける分散協調方式の概観
前節で述べたように, 分散協調型のシステム構成は, 現実世界の多様性や不確実
性, つまりは無数に存在する解や多数の局所解などをもつような世界における問題
の解決に適しているといえ, 画像理解システムでの応用が試みられている. 本研究
が対象としている Snake は, 画像処理, 特徴抽出であって画像理解の前段階に位置
づけられるが, 分散協調を利用した画像理解システムの概観を述べることによって,
分散協調処理の具体例を示し, また本研究の着眼点を明確にする.
画像理解システムにおける, これまでに提案された分散処理方式を, エージェン
トを何とするかによって分類すると, 以下のように 2 つに大別される [34, 35].
(1) 分散観測方式
分散環境下における画像理解の方式であり, 具体的には観測ステーション (エー
ジェント) を地理的に離れた場所に配置し, それぞれが画像を観測, 解析を行う中で
26
図 3.6: AVA
互いにその結果を交換することによって, 対象空間の状況を理解, また, 空間内を移
動する物体の追跡を行う方式である.
分散観測方式の代表的システムとして, 分散協調視覚システム [36] がある. こ
れは, 首振り角やズームなどの制御可能なアクティブカメラを備え, 相互にネット
ワーク結合された計算機の論理モデルである能動視覚エージェント (Active Vision
Agent: 略して AVA) の集合として構成される (図 3.6). また, AVA は視覚, 行動,
通信モジュールからなり, この AVA を観測空間中に分散配置し, それら AVA 群の
協調により動的に変化する世界の状況を多角的に観測し, 広範囲の動的な理解と多
用途のシーンの視覚化を実現するものである. この着想に基づいたシステムとして,
複数対象の実時間追跡システム [37, 40] や, 顔認識システム [39] が提案されている.
浮田らは, 分散協調視覚の着想に基づき非同期アクティブカメラ群による複数対
象の実時間追跡システムを提案している [37]. このシステムでは, AVA と追跡対象
は一対一の関係にあり, AVA 群により対象の 3 次元情報の獲得と広範囲における継
続追跡を行う. 具体的には, 同一対象を注視する AVA は同一グループ (エージェン
シ) に属し, AVA 間で情報の授受を行い協調して追跡を実行する. また, 対象領域
に複数の人物が存在する場合は, 複数のエージェンシが構成されエージェンシ間で
の情報の授受と協調を行う. すなわちこのシステムは, AVA が単独で追跡を行う層,
AVA 間の協調によるエージェンシ内での AVA 管理と協調動作を行う層, エージェ
ンシ間での協調により AVA の追加, 脱退, 移籍を行う層の 3 層構造を構成してい
る. このような各層における協調処理によって, 各 AVA が適応的に役割を変更す
ることによって複数対象の追跡を実現している. しかしながら文献 [37] で提案され
ているシステムでは, エージェント間で追跡対象の識別のための情報交換において,
必要最低限の情報のみを授受していたため追跡対象に制限があり, またカメラで観
測されているにもかかわらず破棄されている情報があった. そこでこれらの問題を
27
図 3.7: Ukita’s AVA system
解決するために, 情報交換に伴う通信量の増加を抑えたまま, さらに密な情報交換を
実現する協調追跡プロトコルが提案されている [38].
一方で中澤ら [40] は, アクティブカメラと計算機を観測ステーション, 観測ステー
ション上で対象を観測する実体 (ソフトウェア) を観測エージェントと分離して考
え (図 3.8), 観測ステーション上で観測される追跡対象と観測エージェントをを一
対一に割り当てる. つまり, 観測ステーション上には, 観測される追跡対象の数だけ
エージェントが生成され, 複数の観測エージェントが動作する. これにより 1 台の
観測ステーションで複数対象の同時追跡を可能にし, またよりロバストな追跡を実
現している.
また同様に分散協調視覚 [36] の枠組みで, 人物検出, 追跡, 顔画像の登録を統合
的に実現する顔認識システムが提案されている [39]. このシステムは, 認識対象人
物に関する事前の辞書登録を必要とせず, 未登録の人物が観測された際に人物を検
出, 追跡すると共に新たに分散協調による効果的な顔画像の辞書登録を行うもので
ある. このシステムではエージェントを, 同じ対象人物を追跡, 登録を行うエージェ
ントの集合である追跡エージェンシと, 観測範囲内に新たに登場する人物の検出を
28
図 3.8: Nakazawa’s system
行うエージェントの集合である検出エージェンシの 2 つのエージェンシにそのタス
クによって分け, 各エージェンシ間での大域的な協調によって, エージェンシが対象
としている人物の登録済みの顔画像が認識処理に十分な多様性をもっているかどう
かを判定し, 各時刻における登録画像の状態と, 対象人物とエージェントの位置関係
からエージェンシの構成を動的に変化させることによって, より効果的な登録画像
の取得を実現している (図 3.9).
(2) 分散解析方式
画像解析もしくは認識において, 異なる機能・特性をもたせた複数の解析 (認識)
プロセスをエージェントとし, それらを協調させることによって, より柔軟で信頼性
の高い画像理解を目指す方式である. この分散解析方式はさらに, 以下の 3 つに分
けられる.
• 機能分散
異なる機能, すなわち画像理解のための画像処理, 特徴抽出, パターン分類, モデ
ル照合などの画像処理・理解アルゴリズムをエージェントの単位とする方式であり,
互いに独立して分散的に配置される. 各エージェントは並列・非同期的に動作し,
個々の機能を入力画像に対して適用する. このように各解析を行う処理プロセスで
29
図 3.9: Kato’s recognition system
あるエージェントの協調動作によって, より柔軟な解析過程の制御を実現する方法
である [41].
この方式は, 画像理解システムに特有の方式ではなく, システムをエージェント
に分解する方式の一応用である. この方式は, 図 3.10 に示すように, システムに関
する分散協調の方式と言える. そのため, エージェントの数や種類はシステム設計
時に決まり, エージェントの構成は静的である.
エージェントの性質には以下のような共通点がある.
1. 特定の対象に適用された場合にのみ正しい解を得ることができ, それ以外の場
合の挙動は保証されない.
2. エージェントが正しい解を得ることができる対象に適用されるかどうかを事前
に判断することは, 一般的に難しい.
つまり, 機能分散型の画像理解システムとは, このような性質をもつエージェントを
統合し, 互いに協調的な動作を行うことにより複雑なシーンを解釈させるための枠
組みである.
具体的なシステムとしては, 黒板モデルの枠組みを利用したもの [43–46] が提案
されている. 黒板モデルは, 音声認識システム Hearsay-II [42] において用いられた
ことで有名だが, 黒板と呼ばれる共有メモリと, 黒板の周りに配置される複数のエー
30
図 3.10: Functional Distribution
ジェントによって構成される. エージェントはシステムの中においては対象物を認
識するための知識と見なすことができ knowledge source とも呼ばれ, 例えば “エッ
ジ抽出をする” や “エッジから平行エッジを抽出する” といった互いに独立した機
能をもつ. このエージェントの独立性から, 黒板モデルはエージェントの追加によ
るシステムの拡張が容易であるという特徴がある. 各エージェントは黒板を常に監
視し, 自らが処理を行うべきデータが黒板に書き込まれると起動し, 処理結果を黒板
に書き込む. このように黒板の内容に応じて適切なエージェントが処理を行う機構
が実現されており, 黒板を通して他のエージェントとの相互作用を実現する. しか
しながら, 各エージェントが独自の判断で黒板に書き込みを行うと黒板内で矛盾す
るデータが書き込まれ, 整合性が保たれなくなる場合があるため, 黒板モデルでは
黒板へのアクセス制御が必要になる. 一見簡単に並列処理化できそうであるが, 並
列化によるアクセス制御機構が複雑になってしまうという短所をもつ. 長所として
は, 黒板の内容に応じてエージェントが選択的に起動し, 柔軟な解析過程の制御が可
能であること, 複数のエージェントの存在によって自然なアルゴリズム統合が可能
であること, エージェントの追加による簡単な機能拡張が可能であることが挙げら
れる.
松山ら [43] が提案したシステムは, 領域分割を行った航空写真に対して, 田畑や
森, 住宅地などを認識するシステムを提案した. このシステムでは基本領域, 特徴領
域, 対象物, 対象物カテゴリーの 4 階層からなる黒板に対して, 複数の特徴領域抽出
エージェントと複数の対象物認識エージェントを配置している (図 3.11). 特徴領域
抽出エージェントは, 基本領域からテクスチャ領域や均一な大領域などの顕著な特
徴領域を抽出し, 一方, 対象物認識エージェントは各特徴領域の特性や空間的関係を
用いて道路, 森といった対象物を認識する.
Draper ら [44, 45] が提案したシステムは, 風景画像から対象物を認識するシステ
31
図 3.11: Matsuyama’s Blackboard System
ムであり, このシステムのエージェントは schema と呼んでいる. schema は松山
ら [43] における特徴領域抽出エージェントと対象物認識エージェントを 1 つにまと
めたような機能をもち, エージェントは特徴領域の抽出から認識までを行う. また
このシステムは階層的な黒板モデルの構成になっている. すなわち各 schema は内
部にも局所的な黒板をもっており, それ自身が黒板システムになっている (図 3.12).
また, 上述のように, 黒板モデルでは並列性を実現するための規定はなく, システ
ム全体の処理の整合性を保つための別の制御システムが必要になるといった問題点
もある. これらの点を考慮し, 中村らは並列エージェントの協調的な処理による並
列特徴抽出システム PAFE [46] を提案している.
• アルゴリズム分散
同じ機能をもつがそれぞれ異なるアルゴリズムに基づいて画像を解析するプロセ
スをエージェントの単位とする方式であり, 複数の特性の異なる解析アルゴリズム
であるエージェントを同一の画像に並列に適用し, それらの結果を統合する. それ
により結果として, 画像全体に対する解析結果の信頼性向上を図る方法である. こ
の方式は, 複数の異なる処理方法によって同一の構造を処理し, 結果を統合する方式
といえ, 認識対象自身, または部分領域の抽出方法が複数ある場合には, 幾つかの抽
出方法を並行して適用し, その結果を統合することもできる.
アルゴリズム分散を画像理解において主張した最初のシステムは, 渡辺ら, 角ら
の協調的画像理解システム [47, 48] があり, これらは VIC (Vision module/model
Integration in Concurrency/Cooperation) [49] の枠組みに基づいて構成されている.
32
図 3.12: The Schema System
VIC におけるエージェントは, それぞれ特定の条件の下で効果を発揮し, その独立
性が強調されている. 各エージェントは並列, 非同期的に動作し, それぞれが独自の
方法でシーンを解析するが, 他のエージェントとの通信によって協調的に動作し, 共
通の問題を解決しようとする. 文献 [47, 48] は, システムを提案するとともに, それ
ら実験システムによって VIC の有効性と問題点の検証を行ったものである.
渡辺らは, ステレオによる 3 次元空間の認識に対して複数の特性の異なるアルゴ
リズムの処理結果や中間結果を統合して利用するシステムを提案している [47]. ス
テレオによる 3 次元空間の認識においては, 左右の画像の対応点を求めることが最
重要問題であるが, 画像中に類似した特徴をもつ点が多く存在するために解決の困
難な問題である. これに対して, 特定の環境もしくは用途に応じて多数の対応点探
索アルゴリズムが提案されており, このシステムではこれらの異なる環境に適用す
る 3 つの対応点探索アルゴリズムをそれぞれエージェントとし並列に実行, 協調動
作を行う (図 3.13). 各エージェントは, 不足した情報を他のエージェントの処理結
果や中間結果から補うことによって協調し, また結果の統合は, 各エージェントが自
ら独自の確信度を算出し, その自己評価の最も高いものを選出することで実現して
いる.
角らの提案したシステムは顔認識システム [48] であり, 対象の正面からの顔認識
モデル, 斜めからの顔認識モデルなど複数の認識モデルをあらかじめ用意し, それら
を同時にトップダウン解析を行い, それらの中で最も尤度の高い出力を導き出した
モデルを採用している. 前述の渡辺ら [47] のシステムとの相違点は, 渡辺らのシス
33
図 3.13: VIC stereo
テムが他のエージェントの中間結果, 処理結果を参照することによって協調動作を
行っているのに対して, 角らのシステムでは, ある特定の状況でしか認識不可能な
アルゴリズムを複数組み合わせている. 具体的には人物の正面から撮影された顔画
像に対しても, 正面の顔画像を解析するアルゴリズムだけでなく, 他方向の顔画像
を解析するアルゴリズムをも解析を行うような “冗長” 処理をあえて加えることに
よって結果として多様な入力画像への柔軟な対応が可能になる. つまりこのシステ
ムは, アルゴリズムの選択は実際の処理結果から判断するしかないという考えに基
づく並行トップダウン処理システムである (図 3.14).
• 空間分散
処理の対象となる画像や情景は, 様々な線やテクスチャ, 領域といった画像特徴や
対象が存在する空間的な広がりをもつ. 空間分散方式は, こういった画像の画像特徴
や認識された対象など, 画像空間中に分散している局所情報からいかに画像全体の
構造を理解するかという観点に立っており, 画像中の各要素をエージェントの単位
とする方式である. つまり, 前処理と画像解析を行い, 画像の構成をあらかじめ簡単
に抽出, その各構成要素をエージェントとする (図 3.15). エージェントは他のエー
ジェントと協調し, 動的に生成, 消滅, 併合を行いながら, 初期の解析で発見できな
かった構成要素を発見し, またより大きな構成要素を発見する. このようにエージェ
ントの構成を動的に変化しながら, エージェント間の協調処理によって画像や情景
の大局的な構造を認識, 理解する.
空間分散と機能分散を合わせた粒度の細かい分散形態を提案しているものとして
松山らによる SIGMA [50] がある. SIGMA は汎用な画像理解システムであり, こ
のシステムでは, 画像を構成する部分のそれぞれに対して 1 つのエージェントが割
34
図 3.14: VIC face analysis
当てられ, 各エージェントは画像中の認識対象物の構造的な関係に関する知識に基
づいて画像の構造を認識, すなわち他の対象物がシーン中のどこに存在するのかの
仮説を生成し推論を行う. 仮説と整合する別のエージェントが既に存在する場合は,
エージェント間にボトムアップ的な “関係付け” を行う. また複数の仮説が整合して
いる場合には, それらの仮説が示す位置にトップダウン解析による特徴抽出が実行
される. 以上のような基本動作により, エージェントをノードとする関係付けのネッ
トワークを構築し, 複雑なシーンを解釈するシステムである. このように, SIGMA
では, エージェントの協調による推論過程を通じて, トップダウン解析とボトムアッ
プ解析の統合を実現しており, 実際のアプリケーションとして航空写真の認識を行っ
ている.
本研究では, 複数の Snake を用いて, それらに分散協調処理を適用することで輪
郭抽出の高精度化を図る. その詳細は次章以降で詳述するが, Snake は画像処理, 特
徴抽出の一手法であり, 上記の画像理解という大局的な観点で分類されたものと同
じレベルで論じるのは浅慮である. しかし, 本論文で提案する分散協調型 Snake の
着眼点を明確にするために上記の分類で区分すれば, 本手法は画像中のある 1 つの
対象に対して, 異なる解空間をもたせた Snake を実行する複数のエージェントを適
用するため, アルゴリズム分散のアプローチに近い. すなわち, 各エージェントが,
自身に与えられたそれぞれの性質に基づいて探索を進める中で, 他のエージェント
との間で授受された情報に基づいて, より信頼性の高い結果を得ることを目的とし
ている.
35
図 3.15: Spacial Distribution
3.4
分散協調についてのまとめ
本章では, 分散協調におけるエージェント, すなわち分散人工知能におけるエー
ジェントの性質と役割, 分散協調の概略と, 本論文で提案する分散協調型 Snake の
着眼点を明確にするために画像理解システムにおける従来手法の分散協調化の分類
を述べた.
エージェントとは, ある問題において複数に分割された部分問題の解決を試み, そ
の性質は自律性, 社会性, 反応性, 自発性などが挙げられる. このような性質をもつ
複数のエージェントは, 互いにその存在を意識し, 必要に応じて組織化, 統合, また
は協力関係を築く.
分散協調ではこのような複数のエージェントが, ある程度システムの全体を意識
しながらエージェントの間で協調関係を築くことで, 最適な解を求める機構であり,
分散協調化することによって, 局所解への誤収束を回避し最適解に到達する可能性
が高まるため, 全体の処理効率が向上する. これは吉田らの多体軌跡推定手法 [30]
などによって検証され, 焼き鈍し法といった確率的手法と同等の解の品質をより効
率的に求めることが可能であることが実証されている. 分散協調化によって, 多数
のエージェントの協調により全体の処理能力が向上するだけでなく, 単体では問題
解決の難しい問題でもエージェント間の協調動作により問題解決が可能になる場合
があり, また耐故障性の向上やエージェントを追加することが容易になりシステム
の拡張, 機能追加が行えるといった利点もある.
画像理解といった現実世界の多様性や不確実性を含む問題を扱うのに, 分散協調型
のシステムは適していると言え, これまでに幾つかの手法が提案されてきている. そ
こで, 次に画像理解システムにおける従来手法の分散協調化の分類について述べた.
36
画像理解システムにおける従来手法の分散協調化の分類には, 大きく分散観測方
式と分散解析方式があり, 分散解析方式はさらに機能分散, アルゴリズム分散, 空間
分散に分けられる. 本章ではそれぞれの代表的システムを紹介した.
本論文で提案する分散協調型 Snake は, 上記の分類でいえばアルゴリズム分散の
観点と根を同じくし, 各エージェントが, 自身に与えられたそれぞれの性質に基づい
て探索を進める中で, 他のエージェントとの間で授受された情報に基づいて, より信
頼性の高い結果を得ることを目標としている.
37
第4章
Snake と分散協調
基本的な Snake による輪郭抽出では, 原画像中にある 1 つの抽出対象に対して 1 組
のパラメータ組に基づくエネルギー関数を用いて輪郭抽出を行っており, 2 章で述
べたように, 対象画像中のノイズやテクスチャ, 抽出対象の輪郭の形状とパラメータ
の不適合によって, 偽の輪郭すなわち局所解に陥り誤収束する恐れがある.
このような精度低下の最大の要因は, エネルギー関数におけるパラメータ組, ま
た抽出処理の対象となる画像中の特徴量によって生成される探索解空間が多峰性の
複雑な形状をもつことにある. すなわち, 関数が多数の局所解をもち, それらが偽
の解となるため, Snake はそのような局所解に陥り抜け出せなくなる. この問題は,
Snake が到達した解が局所解であるか, 最適解であるかを判断することができれば
対処することができ, そのためには複数の Snake を用いてそれらを協調させること
が必要である.
そこで, ある抽出対象に対してそれぞれ Snake を実行する複数のエージェントが
同時に分散協調的に輪郭抽出を進めることを考える.
4.1
分散協調型 Snake の枠組
本研究では, 柔軟性と拡張性をもたせることによって, より安定した輪郭抽出を
実現する分散協調型 Snake (以下, Multi-Snake と呼ぶ) を提案する.
Multi-Snake では, 上記の多峰性解空間の探索において, 最適解に到達する可能性
を高めるために, 複数のエージェントで同時に探索を進めていき, エージェント間で
情報の授受と協調を行う. このような情報の共有と協調から, 局所解への誤収束を
回避することによって, 画像特徴量の分布や初期閉曲線, パラメータ組の抽出形状の
傾向に左右されやすいという Snake の脆弱性を改善し, より柔軟で安定した抽出を
実現することを目指す.
本手法は 2.4.1 でも言及した和田らの研究 [20] における分散協調化とは相補的な
38
図 4.1: Related approach
図 4.2: Our approach
関係にある. すなわち, 本手法における Snake の分散協調化は, 2.4 で言及したよ
うな複数の Snake による輪郭抽出のように, 複数の Snake を複数領域に割当てる
(図 4.1) のではなく, 図 4.2 に示すように複数の Snake を単一領域に割当てる.
本手法では, ユーザーは基本的な Snake における設定と同様, 対象となる抽出物
体の周辺に一つの初期閉曲線を設定する. 各エージェントはその初期閉曲線から, パ
ラメータなどエネルギー関数における解空間を変化させる, もしくは, 与えるデータ
を変えることによって解空間を変化させるなどした, 自身に与えられた異なる解空
間をそれぞれ探索していく. その探索途中, エージェント間で, エネルギー勾配を授
受し, それに基づいて各エージェントは探索経過を修正する. これにより, 初期閉曲
線設定の労力の増加を避けつつ, 分散協調化による抽出処理の精度向上が見込める
だけでなく, これまでに様々に提案されてきた Snake の改善手法と排他的に競合す
ることなく, 併用して更なる精度向上を見込むことができるという, 拡張性をもつ
Snake が実現できる.
初期閉曲線の設定から輪郭抽出に至る全体の処理は, 次のとおりである.
ユーザによる初期輪郭の設定
do
for 輪郭上の全ての制御点について
各エージェントで新制御点の候補を選出
情報を交換して最適値を判定
全エージェントで新制御点を決定
until 収束
次節以降で, より詳細な分散協調化について述べる.
39
図 4.3: Exchanging information by agents
4.2
Snake の分散協調化
まず, Snake を分散協調化するにあたり必要な決定事項を列挙する.
• エージェントの決定
分散協調化するにあたって, 複数のエージェントを決定する必要がある. 本手法
におけるエージェントは, 単体でも十分に輪郭抽出が可能であるような Snake を実
行する. すなわち, 十分な探索能力を持っていれば, どのような Snake でも良い.
本論文で提案する Multi-Snake では, 前節で述べたように, 基本的な Snake と同
様, 1 つの抽出対象に対して 1 つの初期閉曲線を設定し, 全てのエージェントは同
一の初期閉曲線を用いて, そこから抽出処理を開始する. すなわち, 本手法の探索の
様子は, 3.2.1 で紹介した初期値の異なる協調型の多点探索 (図 3.3) のような探索で
はなく, 図 4.3 に示すように, エージェントに異なる解空間を与え, Snake の解空間
の多峰性を積極的に利用した分散協調を行う.
エネルギー関数の解空間は, 抽出対象の画像特徴量の分布とパラメータ調整をさ
れたエネルギー関数によって定まる. 異なる解空間を与えることの意義は, ある解
空間を探索しているいずれかのエージェントがエネルギー関数における極小値, す
なわち局所解に陥ろうとする場合に, 同時に異なる解空間で探索を進めている他の
エージェントには局所解が存在しない可能性があり, そのエージェントからの情報
によって, 局所解に陥ろうとするエージェントを救出することが可能になることに
ある.
Multi-Snake のエージェント決定における制限は上記のように, 輪郭抽出能力を
もつ Snake であること, 各エージェントが異なる解空間を与えられていること, の
みである. すなわち, Multi-Snake は, これまでに様々に提案されている Snake の改
40
図 4.4: Decision of new control points: original Snake
良方式をエージェントとすることも可能であるという大きな特徴を有する拡張性あ
る Snake といえる.
ここでどのように Snake を複数化するか, すなわち異なる解空間をどのように与
えてやるかには以下のようなケースが考えられる. 4. については 2.4 で紹介したよ
うな 分散協調や競合, MDL 等の類似した手法が既に提案されているので本論文で
は取り上げない. また, 3. については 7 章で提案する.
1. Esnake のパラメータを変えた複数の Snake
2. 関連する複数の画像に適用した複数の Snake
3. エネルギー関数が異なる複数の Snake
4. 異なる初期閉曲線をもつ複数の Snake
すなわち, パラメータの違い, またはデータの違いなどから異なる解空間をもつ Snake
同士を並行に動作させ, 中間推定結果情報を相互に交換することで推定過程を修正
していく. なお, 1. と 2. については各エージェントが計算するエネルギー関数は
同一のものを用いるとする.
• 情報の授受
どのような情報を授受すれば, 最適解に到達する可能性を向上させることができ
るかは, エージェントが選定されれば一意に決まるというものではない. しかしな
がら, この情報の授受は, どのエージェントが示す推定輪郭が最適なものかを選定す
る基準となり, 非常に重要であり, 適切な情報を授受しなければ, 全体として最適解
に到達することが難しくなる.
41
本論文では, 具体例として Esnake におけるパラメータを変えた Multi-Snake と,
関連する複数の画像に適用した Multi-Snake, 初期閉曲線から得られるモデルを導
入した新たなエネルギー関数を加えた, エネルギー関数の異なる Multi-Snake を提
案するが, これらは同一の初期閉曲線を全てのエージェントで用いる. すなわち探
索の開始地点は同一であり, 探索過程における各エージェントの様子を図式的に表
すと, 図 4.3 のようになる. 例えばエージェント B のように, あるエージェントで
計算したエネルギー関数の勾配 (一次微分) が小さくなることは, 極小値または最小
値に近づきつつあることを意味すると考えられる. しかし, 同じ制御点において, 他
のエージェントにおいて算出されたエネルギー勾配が大きいまま (図 4.3, Agent A)
ならば, エージェント B が到達したのは最小値すなわち最適な輪郭ではなく, 極小
値であろうと推測される.
そこで, 本手法では, 各エージェントがそれぞれ自身の解空間に基づき, 制御点の
周囲八方の内でエネルギー値が最小になる点へ移動しようとする, その時に生じる
エネルギー勾配を互いに授受することとする. このエネルギー勾配を比較すること
によって, エージェントが現在陥っている極小値が, 最適解であるか, 局所解である
かを判定することが可能になる.
• 探索経過修正
基本的な Snake の輪郭の変形は, 図 4.4 に示すように, Snake を構成する各制御
点に対して, その点が 8 近傍に移動した場合のエネルギー関数の値が最小になる点
を新制御点として制御点を移動させていくことによって実現する.
Multi-Snake においても同様に周囲八方の中でエネルギー勾配が最大となる新制
御点を各エージェントで決定し, その際エネルギー勾配を授受し, その中で最大のエ
ネルギー勾配をもつエージェントの新制御点候補に全てのエージェントが従うこと
によって, 探索経過を修正する. その様子を図 4.5 に示す. このような探索経過の修
正によって, 結果的に全てのエージェントが局所解を回避し, 最適解を目指すように
なる.
このような情報の授受と探索経過の修正は, 制御点を移動する度に行う.
• 追加機能
また, Snake を分散協調化するにあたって, 制御点の振動抑制機能を追加した. 振
動は, 基本的な Snake 単体でも観測される場合があるが, 上記のような分散協調化
による制御点の振動も予測される. よって, Multi-Snake ではそれを抑制する機能も
実装する. 具体的には, 図 4.6 のように, 同じ制御点を往復する振動を検知した場合
は, 振動している当該制御点は検知された時刻の座標に一時固定する. また, 周りの
42
図 4.5: Decision of new control points: Multi-Snake
図 4.6: Vibration control
43
制御点の座標が変化することによるエネルギー場の変化が検出された際には, その
固定を解除し新制御点候補への移動を再開する.
以上のように, 情報の授受とエージェントの探索経過の修正を行う協調動作によっ
て, Multi-Snake は局所解への誤収束を回避し, 最適解に到達する可能性を高め, そ
の結果として画像特徴量の局所的分布や初期閉曲線, パラメータへの依存性という
Snake のもつ脆弱性を改善し, より柔軟で安定した抽出を実現する.
4.3
分散協調型 Snake のまとめ
Snake の多峰性解空間の探索において, 最適解に到達する可能性を高めるために,
Multi-Snake では, Snake を実行する複数のエージェントで同時に探索を進め, エー
ジェント間で情報の授受と協調を行う.
Multi-Snake では, 対象となる抽出物体の周辺に 1 つの初期閉曲線を設定する.
エージェントは, 十分に抽出能力をもつ Snake であること, 各エージェントは異な
る解空間をもつように選定すること, という制約のみをもつ. 具体的には, エネル
ギー関数におけるパラメータ組 (α, β, γ) をそれぞれ変える, または, 対象画像に関
連する複数の画像をエージェントにそれぞれに与えることによって解空間を変化さ
せる, といった方法によって各エージェントに異なる解空間をもたせることが可能
である. そのようなエージェントが同時にそれぞれの解空間にしたがって輪郭抽出
処理を進め, その途中エージェント間で適宜エネルギー勾配を授受, それに基づき各
エージェントはその推定輪郭を変更していく.
このように, Multi-Snake の枠組は非常にシンプルな構成になっており, 初期閉曲
線設定の労力の増加を避けつつ, 分散協調化による抽出処理の精度向上が見込める
という特徴をもつ. また, 柔軟な輪郭抽出を実現できるだけでなく, これまでに様々
に提案されてきた Snake の改善手法と排他的に競合することなく, 併用して更なる
精度向上を見込むことができるという, 拡張性をもつ Snake である.
44
第5章
複数パラメータ Snake の分散
協調
Snake は, 式 (2.2) および (2.3) にあるパラメータ α, β, γ の値を調整することに
よって, 様々な対象画像中の様々な対象物を抽出することができるが, 2.2 で述べた
ように, 抽出したい対象物と画像に適したパラメータを選定するのが難しい. これ
はパラメータ組と画像特徴量分布によって定まるエネルギー関数の解空間, すなわ
ちパラメータ組のもつ収束傾向が, 対象輪郭の形状と画像特徴量に適合しないこと
が原因である.
そこで前述の Multi-Snake の枠組みに基づいて, 複数のパラメータ組による協調
の方式を提案する. これは 4.2 で述べた “Snake の複数化” の 1. にあたり, 異なる
パラメータ組を与えた複数のエージェントによる Multi-Snake について議論し, そ
の検証と性能評価を行う.
5.1
方式
複数パラメータ協調では, パラメータの違いからエージェントに異なる解空間を
もたせ, 4.2 で述べた協調を行うことによって, 局所解に陥りそうなエージェントを
救出し, 最適解への到達を目指す.
この様子を図式的に図 5.1 に示す. 図中に示すように, 各エージェントが探索す
る解空間はパラメータを変えることによって, 例えば図のように変化する. したがっ
ていずれか 1 つのエネルギー関数のみに基づく, 1 つの Snake では局所解に陥って
最適解が得られないような状況にも対処できるようになる.
また一般に, 例えば実画像では, エネルギー関数に大きな影響を及ぼす輝度勾配
がノイズやテクスチャなどで望ましい傾向を示さずに, 局所解の原因となることが
多い. 1 つの Snake による輪郭抽出では, それに対処するパラメータの選定が非常
45
図 5.1: Energy function with different parameters
に難しい. だが, Multi-Snake では, 異なる γ をもたせることで, 対処が可能になる.
以上のように, 各エージェントが計算するエネルギー関数におけるパラメータ組
を変えた Multi-Snake は, パラメータ組のもつ抽出形状の傾向を緩和し, 最適解に
到達する可能性の向上が期待でき, 結果的に, 単一の Snake ではパラメータ組の候
補から試行錯誤的に選定されてきたパラメータ決定におけるユーザの労力軽減が期
待できる.
また, 本手法がどのようにエージェントを選択するか, すなわちどのように Snake
の制御点を移動させていくかを視覚的に捉えるために, 後に示す人工画像 case 7
(図 5.11) の輪郭抽出処理におけるエージェント選択の様子を図 5.2 に示す. これ
は, 図 (a) 中の青く囲んだ領域内に存在した制御点を追跡し, またその制御点におけ
る新制御点候補を矢印で示し, またどれが選択されたかを図示しているものである.
このように, 各エージェントは自身のもつパラメータ組に基づいて, 次の制御点候補
を選出し, そのエネルギー勾配を他のエージェントと授受, それが最大となるエー
ジェントに従い, 制御点を移動させていく. 但し, 各エージェントが算出したエネル
ギー値が, 制御点を移動させずその場に留まった方が良いと判断した場合は, 制御点
を囲む丸で表している. このような処理を繰り返すことで Multi-Snake は輪郭抽出
を実現する.
5.2
検証
複数パラメータ協調を行う Multi-Snake について, 有効性を検証するための実験
を行った. すなわち, それぞれ異なるパラメータ組をもつ Snake を複数個用意し, そ
れぞれ単一で動作させた抽出結果と, 複数のエージェント分散協調で動作させた抽
46
(a) Target region
(b) Candidates of agents
図 5.2: The track of Multi-Snake
出結果の比較を行う. エージェントの個数は幾つでも動作が可能であり, 個数に制
限はないが今回は 3 つのエージェントによる Multi-Snake の実行結果について議論
する.
なお, 実際に複数のプロセッサを用いる分散協調ではなく, 一つのプロセッサ上で
のシミュレーションである. 収束計算には Amini [18] の動的計画法を用いている.
人工画像, およびデジタルカメラで撮影した実画像を用い, 人工画像は 100 × 100 画
素, 実画像は 640 × 480 画素であり, いずれも 256 階調である. また, 実験に用いた
パラメータ組は, 経験的に求めたものを用いている.
まず, 人工画像として 8 ケースを用意した. 対象となる画像は, 背景領域と対象
領域において十分に輝度勾配が得られるものとし, 単体の Snake でも抽出が容易な
単純な形状をもつ対象物と, 複雑な形状で抽出の難しい対象物を用意した.
前節までに述べたような Multi-Snake の協調動作において, Multi-Snake は目的
の輪郭を抽出するが, パラメータ (α, β, γ) として各エージェントに (1.0, 0.0, 0.0),
(0.0, 1.0, 0.0), (0.0, 0.0, 1.0) というパラメータ組を与えたら, すなわち各エージェン
トがエネルギー関数 (式 2.1) における各項のみをもち, それらのエネルギー項を算
47
(a) Simple shape
(b) Complex shape
図 5.3: (1,0,0),(0,1,0),(0,0,1) Multi-Snake
図 5.4: Energy function of each agent
出する 3 つのエージェントで分散協調を実行すると, Multi-Snake はどのような挙
動を示すだろうか. そのような Multi-Snake による例として, 単純形状 (case 4, 図 5.8), 複雑形状
(case 7, 図 5.11) を対象とした輪郭抽出結果を図 5.3 に示す. 図中にある緑の領域
が対象領域であり, それぞれ図 5.8(a), 図 5.11(a) に示す初期閉曲線と同一の初期閉
曲線を用い, また図中の赤画素が収束結果を表している. 上記のようなパラメータ
組を与えた Multi-Snake では, 1 点ないしは数画素で作られる直線まで収束してし
まい, 目的の輪郭の抽出には至らない.
これは, 注目する制御点を v(i) とし, 最近傍の制御点をそれぞれ v(i − 1), v(i + 1)
と表すと, 背景領域においては画像特徴量の変化がないことから, 各エージェントは
以下の式に従いエネルギーを算出する (式 2.1).
agent1 (1.0, 0.0, 0.0): |v(i − 1) − v(i)|2
48
agent2 (0.0, 1.0, 0.0): |v(i + 1) − 2v(i) + v(i − 1)|2
agent3 (0.0, 0.0, 1.0): 0.0 (変化なし)
そのため, 実質は agent1 と agent2 の協調動作になり, この 2 つのエージェント
においてより小さいエネルギー値を算出するエージェントに従うことになる.
一方で, 対象輪郭付近においては, 各エージェントは以下のようになる.
agent1 (1.0, 0.0, 0.0): |v(i − 1) − v(i)|2
agent2 (0.0, 1.0, 0.0): |v(i + 1) − 2 × v(i) + v(i − 1)|2
agent3 (0.0, 0.0, 1.0): −|∇I(v(s))|2
ここで初めて 3 つのエージェントによる協調動作になるが, このようなエージェ
ントの協調によって目的の輪郭の抽出が可能であるかというとそうではない. なぜ
なら, agent3 において輝度勾配が得られた際に, 同時に求められた agent1, agent2
のエネルギー勾配が agent3 によって求められるエネルギー勾配より大きな値を算
出すれば, agent3 によって検知された対象物の輪郭を乗り越えて制御点が移動する
可能性も十分にあり, そのような場合は, agent3 の影響をほとんど受けることはな
い. その結果, 1 点ないしは数画素で構成される直線に収束するということが起こ
る. これは, これらのエージェントが例えば図 5.4 に示すような解空間をそれぞれ
探索しているのであって, 探索過程で “エネルギー勾配” を授受しても, 輝度勾配で
作られる最適解では収束しないことが原因である.
Kass らの提案する Snake が目的輪郭の抽出を可能にするのは, 各エネルギー項
の線形和の積分で作られる Esnake の解空間が目的の輪郭付近で最小値を形成する
からであり, またそのようにエネルギー関数を定義している. Multi-Snake において
も同じことが言え, 解空間が目的の輪郭付近で最小値になるエネルギー関数を, 少な
くとも 1 つのエージェントが形成している必要があり, そのような解空間が一つで
もあれば, エージェント間のエネルギー勾配の授受によって最適解への到達が可能
になる. それに対して上記の実験で用いたようなパラメータ組では, 各エージェン
トが探索する解空間が目的輪郭付近で最適解を形成することは有り得ず, 制御点の
移動に伴う輪郭の変形は起こるが目的の輪郭の抽出は不可能である.
つまり 4.2 で述べた “単体でも十分に輪郭抽出が可能であるような Snake ” とい
うエージェントへの制約は妥当な制約だと言え, またその制約により, エネルギー勾
配の授受による探索経過修正が有効になることが判る.
次に, 単純形状, 複雑形状の抽出実験の結果をまとめたものを表 5.1 に示す. A,
B, C は 3 つの Snake エージェント, A+B+C はそれらの分散協調処理を行った
49
表 5.1: Experiment results using artificial images
case
simple
1
2
3
4
simple ave.
complex 5
6
7
8
complex ave.
all ave.
Original Snake
Multi-Snake
A
B
C
A+B+C
0.00 0.00 0.00
0.00
0.17 0.17 0.17
0.17
0.27 0.14 0.14
0.14
0.00 0.00 0.00
0.00
0.09
0.08
11.68 7.48 12.31
2.02
3.50 3.55 4.97
3.87
9.49 25.75 9.30
4.70
6.64 5.60 6.88
4.43
8.93
3.76
4.51
1.93
表 5.2: The number of control point
num
num
case 1 case 2
230
198
case 5
155
case 3
218
case 4
174
case 6 case 7 case 8 real
214
208
196
1077
Multi-Snake を表す. 数値は抽出精度であり, その精度評価式は, Rarea = |N (Y ) −
N(X)| / N(X) × 100 で評価する. ここで, X は正しい対象領域を, Y は抽出され
た領域を表し, N(Z) で領域 Z 内の画素数を表す. すなわち Rarea の値が小さいほ
ど精度が高い.
表から見て取れるように, 単純形状における輪郭抽出では, 単一の Snake でも十
分に抽出できており, Multi-Snake でも同程度の精度を得ている. 一方で, 複雑形
状における輪郭抽出では, 単一の Snake では十分な精度が得られず, 4 ケース中 3
ケースが Multi-Snake で精度が向上している. しかしながら, case 6 のように単一
の Snake の精度を下回る場合があった.
50
(a) Initial contour
(c) (0.4, 0.6, 1.0)
(b) Multi-Snake
(d) (0.5, 0.5, 1.0)
(e) (0.6, 0.4, 1.0)
図 5.5: Simulation result: case 1
(a) Initial contour
(c) (0.4, 0.6, 1.0)
(b) Multi-Snake
(d) (0.5, 0.5, 1.0)
(e) (0.6, 0.4, 1.0)
図 5.6: Simulation result: case 2
51
(a) Initial contour
(c) (0.4, 0.6, 1.0)
(b) Multi-Snake
(d) (0.5, 0.5, 1.0)
(e) (0.6, 0.4, 1.0)
図 5.7: Simulation result: case 3
(a) Initial contour
(c) (0.4, 0.6, 1.0)
(b) Multi-Snake
(d) (0.5, 0.5, 1.0)
(e) (0.6, 0.4, 1.0)
図 5.8: Simulation result: case 4
52
(a) Initial contour
(c) (0.2, 0.8, 1.0)
(b) Multi-Snake
(d) (0.4, 0.6, 1.0)
(e) (0.8, 0.2, 1.0)
図 5.9: Simulation result: case 5
表 5.1 に挙げた単純形状の抽出結果を図 5.5, 5.6, 5.7, 5.8 に, そして複雑形状の
抽出結果を図 5.9, 5.10, 5.11, 5.12 に示す. 全結果において, (a) は初期状態を表
し, 初期閉曲線を図中に示してある. 下段の (c)–(e) はそれぞれ付記したパラメータ
(α, β, γ) をもつ単一の Snake による抽出結果, 一方で (b) はそれぞれ (c), (d), (e)
と同じパラメータをもつ 3 つの Snake を分散協調させた Multi-Snake の抽出結果
である.
また, 各対象物にそれぞれ設定した Snake の閉曲線を構成する制御点の数は, 表 5.2
に示すとおりである.
case 5 (図 5.9) の抽出実験では, パラメータ組の抽出形状の傾向が両極になるよう
なパラメータ組を用いているため, 単一の Snake による抽出結果はそれぞれ異なる
抽出傾向を示している. これらをエージェントと用いることによって Multi-Snake
では, そのパラメータ組のもつ抽出形状の傾向を緩和し, より安定した抽出結果を得
ている.
case 6 (図 5.10) では, 抽出対象が大きな凹部分をもつ. このような深い窪みをも
つ対象は Snake が最も不得意とする形状である. これは, 凹領域内で向かい合う輪
郭によって形成されるエネルギー場が, 最も窪んだ輪郭によって形成されるエネル
ギー場よりも小さくなり, 向かい合う輪郭どうしで引き付け合うような形で最小と
なることが原因である. このような形状の抽出を試みるため, パラメータ α, β のバ
53
(a) Initial contour
(c) (0.1, 0.4, 1.0)
(b) Multi-Snake
(d) (0.3, 0.7, 1.0)
(e) (0.4, 0.6, 1.0)
図 5.10: Simulation result: case 6
ランスは, β に比べ α が小さくなるよう選定しているが, やはり単一の Snake では
その領域での誤収束が見られ, Multi-Snake でも同様の原因で誤収束している.
また, その精度も表 5.1 にあるように, 単一の Snake の最良の精度と比較し MultiSnake の精度低下が見られる. 図 5.10 の凹領域における抽出結果を比較すると,
Multi-Snake が単一の各 Snake の抽出結果の中間をとったような抽出結果となって
いることが原因である. このように, Multi-Snake はパラメータ組のもつ抽出傾向の
緩和による安定した輪郭抽出を実現するものではあるが, Snake の凹領域への脆弱
性を完全に解決するものではないことが判る.
case 7 (図 5.11) では, case 6 (図 5.10) と比較すると浅い窪みではあるが, 凹領域
を 2 つもち, 全体の形状が非常に複雑なものになっている. このような形状から (α,
β, γ) のパラメータ組の抽出形状の傾向が両極になるようなパラメータ組を用いて
輪郭抽出を行った. 抽出結果では, 単一の Snake では, 各パラメータ組によってそ
の抽出結果に傾向があるが, Multi-Snake ではその抽出結果の最良の部分のみを合
成したような結果になっている. 単一の Snake に比べ, 抽出結果の精度は向上して
いるものの, 完全な輪郭の抽出には至っていない.
case 8 (図 5.12) の抽出対象は, 屈曲の大きい領域だけでなく, 尖鋭部も含まれて
おり, 丸みをもたすエネルギー項をもつ Snake はこのような尖鋭部も不得意とする
領域である. またこの形状は同時に凹領域も存在し, こういった形状におけるパラ
54
(a) Initial contour
(c) (0.3, 0.2, 1.0)
(b) Multi-Snake
(d) (0.4, 0.6, 1.0)
(e) (0.7, 0.5, 1.0)
図 5.11: Simulation result: case 7
(a) Initial contour
(c) (0.3, 0.7, 1.0)
(b) Multi-Snake
(d) (0.1, 0.9, 1.0)
(e) (0.2, 0.8, 1.0)
図 5.12: Simulation result: case 8
55
(a) Initial contour
(c) (0.8, 0.7, 0.6)
(b) Multi-Snake
(d) (0.6, 0.9, 0.8)
(e) (0.7, 0.6, 0.7)
図 5.13: Experiment with different parameter sets: real image
メータ決定は非常に困難なものである.
通常, 尖鋭部をもつ対象に対してパラメータを設定する場合, 丸みをもたそうとす
るエネルギー項へのパラメータ β を小さくすることが対応策としてあるが, 今回は
対象の形状が非常に複雑であるため全体の抽出がより安定した結果を得たパラメー
タ組をもつ Snake をエージェントとしている. この対象物においても, Multi-Snake
を用いても抽出に至らず誤収束している領域があるが, その抽出結果は他のエージェ
ントの抽出結果から最適な部分を合成したような結果になっている.
次に, 実画像における輪郭抽出の結果を図 5.13 に示す. 同図 (a)–(e) は, 図 5.9–
5.12 を踏襲して示している. また, 制御点の数は表 5.2 real に示すとおりである.
このように, 実画像でも人工画像と同様に, 分散協調による精度向上がみられる.
また, この実画像における抽出実験では, エージェントに与えるパラメータ組におい
て輝度勾配のエネルギー項へのパラメータ γ をそれぞれ変えたものを与えている.
これにより, より安定した抽出を実現している.
表 5.3 に, いくつかの実験の実行時間をまとめる. ここで, “Snake” は単一の Snake
を表しており, “Multi” は Multi-Snake を, “Time” は抽出処理全体の時間, “Loop”
はプログラムの回転数を, 更に “time/loop” は 1 回のループに費やされた時間を表
56
している. また, 使用した CPU は Celeron 2.50 GHz である.
“Time/Loop” では, Multi-Snake の実行時間は, 人工画像, 実画像ともに単一の
Snake とほぼ同程度の実行時間であった. これは複数のパラメータ協調の MultiSnake では, 式 (2.2) , (2.3) 中の各項 |vs (s)|2 , |vss (s)|2 , |∇I(v(s))|2 が全てのエー
ジェントで同じであるため, 各エージェントは異なるパラメータ α, β, γ の異なる
Esnake だけを計算するからである.
ループ数は, Snake の輪郭抽出過程に非常に強く依存するため, 単純に比較するこ
とはできないが, Multi-Snake を用いることによってループ数が減少するパラメー
タ組があった一方で, 増加するパラメータ組があった.
減少については, 単一の Snake ではパラメータ組と輪郭の形状とが不適合であっ
た場合に望まない形状にまで輪郭の変形が進んでしまっていたのを, 他のエージェ
ントからの情報によってそのような冗長的な変形過程を辿らない, すなわち目的輪
郭への速い到達が可能になったことが原因と考えられる.
また増加については, 単一の Snake ではループが少ない段階で局所解ないしは
最適解で (すなわち目的輪郭の抽出に至ったか否かに関わらず) 収束していたが,
Multi-Snake では他のエージェントによって複数の可能性を探索することになり, よ
り変形が進んだことが原因と考えられる. これは Multi-Snake の抽出結果が, 各パ
ラメータ組の抽出結果の最適部分を合成したような形状で収束したことによっても
裏付けられると考察できる.
5.3
考察
人工画像と実画像を用いて, 単一の Snake による輪郭抽出実験と, パラメータ組
の異なるエージェントによる Multi-Snake を用いた輪郭抽出実験を行い, その結果
を比較した.
単一の Snake では, 高い抽出精度を得るためのパラメータ決定が抽出対象の輪郭
の形状と画像特徴量分布を見極め, 適切なパラメータを求めることが難しい. それ
は形状が複雑になればなるほど困難であって, 輪郭の形状とパラメータ組の示す抽
出傾向が一致しない場合は, たとえ対象物が背景との間で十分な輝度勾配を示すよ
うな場合でも抽出ができない.
それに対して異なるパラメータ組を用いた Multi-Snake では, 抽出精度の向上が
みられた. 具体的には, 本手法は各エージェントに異なるパラメータ組を与えること
57
表 5.3: Performances of experiments:(1) Parameter cooperation
Time(sec)
different parameters
Art (Fig.5.9)
(0.2,0.8,1.0)
(0.4,0.6,1.0)
(0.8,0.2,1.0)
Multi
Art (Fig.5.11) (0.3,0.2,1.0)
(0.4,0.6,1.0)
(0.7,0.5,1.0)
Multi
Real (Fig.5.13) (0.8,0.7,0.6)
(0.6,0.9,0.8)
(0.7,0.6,0.7)
Multi
0.0154
0.0154
0.0466
0.0532
0.0468
0.047
0.131
0.047
3.07
2.82
3.33
3.68
Loop Time/Loop
16
13
47
12
31
28
87
31
324
295
347
334
0.000963
0.00118
0.00101
0.00127
0.0015
0.00168
0.00151
0.00152
0.00947
0.00955
0.00959
0.0110
によって, 各エージェントが探索する解空間の形状を少しずつ変化させ, 各々探索を
進める中でエネルギー勾配を互いに授受し, 最大のエネルギー勾配を算出したエー
ジェントに従い変形を繰り返す. このような協調動作により Multi-Snake は, パラ
メータ組のもつ抽出傾向の緩和という性質をもつ.
しかしながらこの Multi-Snake は, Snake のもつ凹領域や尖鋭部への脆弱性を完
全に克服するものではなく, あくまで各パラメータ組の抽出結果の最適部分を合成
したような結果に留まった. これはまた, Snake のもつ初期閉曲線への依存性といっ
た脆弱性と密接な関わりをもつことになる. つまり, Multi-Snake では, 全てのエー
ジェントで同一の初期閉曲線を用いており, この点は再考の余地があると考えられ
る. すなわち, 1 つの対象物に対して異なる初期閉曲線をもつ Multi-Snake を用い
ることによって, 改善される問題だと考える.
さらに, エージェントとして組み合わせたときに最適なパラメータ組を決定する
ことは, その抽出対象の多様性から一意に決定することはできない上, 完全なパラ
メータ組の組合せは存在しないと推測されるが, どんな対象物でも安定した抽出を
実現するようなパラメータ組の組合せ方法を論じることは可能だろうと考える. 本
実験を通して, パラメータ組の組合せは, 抽出形状として両極の傾向を示すパラメー
タ組をエージェントに与えた時に, より安定した抽出結果を示した. これは, 解空間
58
の多様性が, 誤収束の可能性を減じたことが原因と考えられる.
また一般に, 実画像を用いた実験では, 輝度勾配に対するパラメータ γ に異なる
値を与えたことによって, 単一の Snake による輪郭抽出では難しいパラメータの選
定が軽減されることを示した. これは, 輝度勾配によって与えられるエネルギー空
間の形状が変化することによって, Multi-Snake のエージェント間の情報の共有と
協調によって誤収束の可能性が減じたことが要因と考えらる. 結果として本手法は
実画像のもつパラメータへの対処が容易になると考えられる.
59
第6章
複数データ Snake の分散協調
Snake のエネルギー関数の定義式から, Snake はその輪郭に沿った局所的な輝度勾
配に強く依存し, 望むような輝度勾配が得られないような場合, 例えば対象領域と背
景領域の輝度勾配が小さい画像では輪郭抽出が困難になる. このような場合, エネ
ルギー関数の外部エネルギーが最適解を導くに十分な極小値をもたず, その解空間
では解を求めることができないことが原因と考えられる.
そこで前述の Multi-Snake の枠組みに基づいて, 複数データ協調の方式を提案す
る. これは 4.2 で述べた “Snake の複数化” の 2. にあたり, 異なるデータを与えた複
数のエージェントによる Multi-Snake について議論し, その検証と性能評価を行う.
6.1
方式
Snake は望むような輝度勾配が得られないような場合, 例えば対象領域と背景領
域の輝度勾配が小さい画像では輪郭抽出が困難になるが, 抽出対象がカラー画像の
場合には, 原画像から得られる輝度としては十分な輝度勾配が得られない場合でも,
表色系 (RGB, HSI など) の各色データでは, 対象物の輪郭で強度変化をもつ場合が
ある. つまり, 原画像にそのまま単一の Snake を実行しても十分な輝度勾配が得ら
れずに低い抽出精度でしか抽出できないような対象でも, その各表色データ画像に
Snake を適用すると, それぞれの Snake は与えられるデータの違いから異なる解空
間, すなわち異なる収束傾向を示す.
原画像を色データで分解した画像は, 同一の対象を捉えたものであることから, 互
いに関連をもつ. そのように関連性をもつが異なる画像データをエージェントに与
え, それらの協調を行うことによって Multi-Snake では, 単一の Snake では抽出の
困難な対象の輪郭抽出が可能にさせることが期待できる. 更に, このようなアプロー
チでは, 各色データ画像は, 原画像と同一の対象を同一の視点で捉えたものであるた
め, ユーザーによって設定される初期閉曲線も全ての色データ画像で同じものを用
いることが可能である.
60
すなわち, 関連する複数の画像に適用した Multi-Snake では表色系の各色データ
画像をそれぞれエージェントに与えてやることによって, 各エージェントの探索す
る解空間を変化させ, それらの協調を行う. 例えば 3 つのエージェントによる探索
の様子を図 5.1 と同様に図式的に示すと, 図 6.1 のようになる. 互いに関連するが異
なるデータをエージェント (A, B, C) に与えることで, 各エージェントが探索する
エネルギー関数は, 例えば図に示すようにエージェント間で形を変え, 解を求めるこ
とが可能になる. したがって, 単純に輝度勾配を与えた一つの Snake では望ましい
輝度勾配を得られないような状況においても, 本手法により対処できるようになる.
さまざまな表象系があるが, 本論文では RGB, HSI, 大田らによって提案された 3
次元表色系 [4, 52] への 3 種類を取り上げる.
HSI (色相, 彩度, 明度) に基づく座標系は, カラー画像認識課題における色特徴量
として扱いやすく, この表色系は一様な色領域への分割にとどまらず, より詳細な分
割や物体抽出に利用できる表色系である [4]. RGB から HSI への変換には 6 角錐
モデル [51] を用いた. 変換式は以下のように定義されている.
V = max{R, G, B}
S = (V − min{R, G, B})/V








H=







π(b − g)
R = V のとき
3
π(2 + r − b)
G = V のとき
3
π(4 + g + r)
B = V のとき
3
ここで, c = V − min{R, G, B} とすると, r = (V − R)/c, g = (V − G)/c,
b = (V − B)/c である. また H < 0 のときには H に 2π を加える.
また, 大田らは, 領域分割に有効な, RGB 値から線形変換によって簡便な 3 次元
表色系を提案している [4, 52]. これらの 3 量は直交座標系であり次式で定義されて
いる.
I1 =
R+G+B
3
R−B
3
2G − R − B
I3 =
4
I2 =
61
図 6.1: Energy function with different data
この系は, 直交変換である Karhunen-Loeve 変換を多くのカラー画像に適用する
ことにより実験的に定められており, また I1 は明度に対応し, I1 , I2 , I3 は無相関に
近い.
6.2
検証
複数データ協調を行う Multi-Snake について, 有効性を検証するための実験を行っ
た. すなわち, 輝度勾配が少ない対象画像を用意し, その原画像に直接 Snake を適
用した抽出結果と, それを表色系の各色データからなる画像をそれぞれ Snake を実
行するエージェントに与えて分散協調処理を行う Multi-Snake の抽出結果の比較を
行う.
なお, 前章における実験同様, 実際に複数のプロセッサを用いる分散協調ではな
く, 一つのプロセッサ上でのシミュレーションである. 収束計算には Amini [18] の
動的計画法を用いている. 人工画像, およびデジタルカメラで撮影した実画像を用
い, 人工画像は 100 × 100 画素, 実画像は 640 × 480 画素であり, いずれも 256 階調
である. また, 実験に用いたパラメータ組は, 経験的に求めたものを用いている.
本節では, 3 つのエージェントを用いて, 各色データからなる画像を与えたエー
ジェントによる Multi-Snake の検証を行う. なお, 各エージェントに与えるパラメー
タ組は全て同一である.
(1) RGB 各色データ画像による Multi-Snake
まず人工画像として, 前節で用いた画像の一つ (図 5.9) において, 対象領域と背景
領域の輝度勾配ができるだけ小さくなるように色配置を行った画像を用意した. パ
62
(a) Original Snake
(b) Multi-Snake
図 6.2: Simulation result: RGB decomposed images
表 6.1: Intensity of the experiment image
I(intensity value) R
G
B
background
164.93
51 255 0
target
164.63
153 153 255
ラメータ組および初期閉曲線は, 前節の実験において十分な輝度勾配が得られる色
配置を行った場合に, 単一の Snake でも輪郭抽出に最適であったものをそのまま用
いた.
対象画像における RGB 各色データを各エージェントに与え分散協調による輪郭
抽出を行った結果を図 6.2 に示す. 対象領域と背景領域の色配置は, 表 6.1 のよう
になっている. 図 6.2 中の (a) は原画像にそのまま単一の Snake を適用した結果を,
(b) には RGB 分解画像を各エージェントにそれぞれ与えた Multi-Snake の抽出結
果を示している.
このように, 対象物と背景の間で輝度勾配が非常に小さい場合は, 対象の形状に
適したパラメータを用いた場合でも輪郭を抽出することが難しい. Multi-Snake で
は, 安定した抽出を実現している.
次に, 実画像における輪郭抽出の結果を, 図 6.3 に示す. 同図 (a) に入力画像,
(b) に入力画像の輝度をグラデーションで表しているが, このようにこの対象画像
は例えばぬいぐるみの背の部分にみられるように, 輝度勾配の乏しい輪郭部分を含
む. また (f) に示す初期閉曲線から, 単一の Snake で輪郭抽出を行った結果を (g)
に, RGB 各色データ画像をそれぞれエージェントに与えた Multi-Snake の輪郭抽
出結果を (h) に示す. なお, 全制御点数は 1268 点であり, Multi-Snake における全
エージェントのパラメータ組は, 単一の Snake (g) と同一である. このように, 原画
63
(a) Input image
(b) Gradation of intensity
(c) Red
(d) Green
(e) Blue
(f) Initial contor
(g) (0.8, 0.7, 1.2)
(h) Multi-Snake
図 6.3: Experiment with RGB decomposed images: real image
64
像において十分な輝度勾配が得られない領域を持つような場合, 単に輝度勾配の値
だけからの輪郭抽出は難しいが, RGB 各色データ画像では (c), (d), (e) に示すよう
なデータを得ることができ, 各エージェントはこれらから輪郭抽出に十分な強度勾
配が得られ, エージェント全体で輪郭を検知し十分な精度をもって対象を抽出して
いる. このように原画像の各色データからなる画像をエージェントに与え情報の共
有と協調動作を行うことにより, 不足した情報を他のエージェントから補うことに
よって Multi-Snake はより安定した輪郭抽出処理を実現している.
(2) HSI 各色データ画像による Multi-Snake
どのようなデータを各エージェントに与えたかを視覚的に捉えるため図 6.4(a)–
(c) に, HSI それぞれに分解し 0–255 の値範囲に正規化した画像を示す. RGB 各色
データ画像による実験で用いたものと同じ初期閉曲線を用い, 使用したパラメータは
(0.9, 0.7, 1.2) である. 比較のために, 単一の Snake に上記のパラメータを与えた抽
出結果を (d) に示し, HSI 各データをそれぞれのエージェントに与えた Multi-Snake
の抽出結果を (e) に示す.
単一の Snake では誤収束しているが, HSI をそれぞれ与えたエージェントによ
る Multi-Snake では対象の輪郭を検出しており, RGB 各色データ画像での実験同
様不足した情報を他のエージェントに与えられた各色データから補うことによって
Multi-Snake はより安定した輪郭抽出処理を実現している.
(3) 大田らの 3 次元表色系の各色データ画像による Multi-Snake
(2) の HSI と同様に, どのようなデータを各エージェントに与えたかを視覚的に
捉えるため図 6.5(a), (b), (c) に I1 , I2 , I3 それぞれに分解し 0–255 の範囲に正規化
した画像を示す. RGB の実験で用いたものと同じ初期閉曲線を用いて, 各データを
それぞれのエージェントに与えた Multi-Snake の抽出結果を (e) に示す. また, 本
実験で使用したパラメータは (0.8, 0.6, 1.0) である.
図に示すように, 単一の Snake では誤収束しているが, 各色データ画像をそれぞ
れ付与したエージェントによる Multi-Snake では対象の輪郭を検出している. 本実
験においても RGB 各色データ画像での実験同様不足した情報を他のエージェント
に与えられた各色データから補うことによって Multi-Snake はより安定した輪郭抽
出処理を実現している.
表 6.2 に, RGB 各色データ画像における Multi-Snake の実行時間を表 5.3 を踏
襲してまとめる. また, 使用した CPU は同様に, Celeron 2.50 GHz である.
“Time/Loop” では, Multi-Snake (case 2) は, 人工画像, 実画像の全てにおいて,
単一の Snake と比べ約 3 倍の時間であった. これはシミュレーションシステムの構
65
(a) Hue
(b) Saturation
(e) Intensity
(d) (0.9, 0.7, 1.2)
(e) Multi-Snake
図 6.4: Experiment with HSI decomposed images: real image
66
(a) I1
(b) I2
(c) I3
(d) (0.8, 0.6, 1.0)
(e) Multi-Snake
図 6.5: Experiment with Ohta’s color decomposed images: real image
67
表 6.2: Performances of experiments:(2) decomposed images
Time(sec)
decomposed images
Art (Fig.6.2) Snake 0.0406
Multi 0.0602
Real (Fig.6.3) Snake 18.2
Multi 38.0
Loop Time/Loop
42
22
1998
1395
0.000967
0.00301
0.00910
0.0273
成に起因する. すなわち本システムでは, 全てのエージェントで |vs (s)|2 , |vss (s)|2 ,
|∇I(v(s))|2 をそれぞれ計算しているため, Multi-Snake はその分単一の Snake に比
べ Time/Loop が約 3 倍の時間を費やしている.
ループ数は Snake の輪郭抽出過程に非常に強く依存し, 単純な比較はできないが,
実験において Multi-Snake を用いることによってループ数の減少がみられた. これ
は, エージェント間の情報の共有と協調動作によってその探索の効率化が果たされ
たことが原因と考えられる. すなわち, 輝度勾配が十分に得られない対象画像での
単一の Snake では, 外部エネルギーの影響が極端に減ることによって相対的に内部
エネルギーの影響が大きくなる. すなわち内部エネルギーの輪郭をより円く短い周
囲長にしようとする働きによって望まない形状にまで輪郭の変形が進んでしまう一
方で, Multi-Snake では各表色データ画像からもたらされる情報の共有とエージェ
ントの協調によって望む輪郭に収束しており, そのため単一の Snake に比べループ
数が減少したものと考えられる.
6.3
考察
対象物と背景領域での輝度勾配が非常に小さい人工画像と実画像の抽出実験を
行った. 人工画像, 実画像ともに, 単一の Snake と同じパラメータ組を用いたエー
ジェントに, RGB, HSI, 大田らの 3 次元表色系を対象に, 各表色系における各色デー
タ画像をそれぞれ与えた Multi-Snake を用いることによって高い精度の輪郭抽出を
実現した.
これは, エネルギー関数において輝度勾配は Snake を対象輪郭に引き付ける働き
をし, その情報が部分的, もしくは全体的に欠落することは Snake の対象物検知が
難しいということを表している. 一般的に, このような輝度勾配の欠落が生じた場
68
合は, 輝度勾配を表すエネルギー項を調整する γ を大きな値にすることで抽出精度
の向上を図る. しかしながら, パラメータ組は α, β, γ の比率によって収束傾向が変
わるため, γ を単純に大きな値にすれば, 必ず対象物を抽出できるというものではな
い. このように, 輝度勾配の小さな対象画像においては, その輪郭抽出が難しく, ま
たパラメータ選定が非常に難しくなる.
それに対して, 表色系における各色データ画像を各エージェントに与え, それら
のデータに基づいて動作する Multi-Snake は, 目的輪郭における各色データの強度
変化を検知し十分な精度で対象物を抽出している. 結果的に Multi-Snake において
は, パラメータ決定はより簡単になり, 輝度勾配の極小さな対象物に対しての対処が
容易になる.
また, RGB, HSI, 大田らの提案する表色系のいずれが最も適しているかは, 対象
物と背景によって変化すると考えられ, 一概には述べられない. HSI, 大田らの表色
系は, 影に影響をうけない色データがあることや, 入力画像の色調の変化が直感的に
理解できるため, 一般的な領域分割において利用しやすいといった性質をもつ. し
かしながら, それらの各色データ画像を用いて Multi-Snake による輪郭抽出を行っ
た際は, 対象データの強度勾配が輪郭抽出に大きく影響するため, 対象と背景が非常
に近い色の変化しか得られないない場合に検出しにくい傾向にある. それは明度変
化の乏しい領域においても同様であるが, 影などの存在が認められる画像において
は有効である. また RGB では, 各色データの変化を入力画像の色調から直感的に
理解することが難しいという性質をもつが, 近い色調の変化でも RGB 各色ではそ
れぞれデータが変化するため検出が容易になる傾向にある. このように, 対象画像
によってどのような表色系を対象にするべきかは対象画像に依存し, どれが最適か
と述べるに至らない. しかしながら, 表色系における各色データ画像を各エージェ
ントに与えることによって Snakes の輪郭抽出精度が向上し, 本手法は対象画像の
画像特徴量の変化が極小さい対象の抽出を可能にする効果的な手法であると考えら
れる.
6.4
RGB 各色データ画像を与えられたパラメータの
異なる Multi-Snake
前節までの実験では, エージェントを 3 つとしていたが, エージェント数を増や
すことによってどのような影響があるだろうか.
本節では, 2 組の異なるパラメータ組を用意し, 各パラメータ組をもつエージェ
69
(a) (0.9, 1.0, 1.0)
(b) (0.9, 1.0, 1.0) RGB coop ( 3 agents )
(c) (0.8, 0.7, 1.2)
(d) (0.9, 1.0, 1.0) + (0.8, 0.7, 1.2)
図 6.6: Experiment with para+RGB Multi-Snake: real image
ントに RGB の各色データ画像を与える, すなわち計 6 つのエージェントによる
Multi-Snake の検証を行う. この検証を通して, 分散協調化による Snake の輪郭抽
出処理安定化の要因, またエージェント数による抽出精度の変化の有無を調査する.
実験に, パラメータ組 (0.9, 1.0, 1.0) と (0.8, 0.7, 1.2) の 2 つを用いるので, 単一
Snakes の (0.9, 1.0, 1.0) の抽出結果を (a) に, このパラメータをもつエージェント
に RGB データを与えた 3 つのエージェントによる抽出結果を (b) に示す. このよ
うに, 新たに加えた (0.9, 1.0, 1.0) のパラメータ組をもつエージェントに RGB 各色
データ画像を与えた 3 つのエージェントによる Multi-Snake では, ぬいぐるみの背
中の部分で誤収束している領域がある. また, (0.8, 0.7, 1.2) のパラメータ組による
抽出結果は (c) に再掲する.
さらに, エージェントとして RGB 各色データ画像を与えられた (0.9, 1.0, 1.0) の
パラメータ組をもつエージェント 3 つと, 同様に RGB 各色データ画像を与えられ
た (0.8, 0.7, 1.2) のパラメータ組をもつエージェント 3 つのエージェントの計 6 つ
のエージェントによる Multi-Snake の抽出結果を (d) に示す.
70
表 6.3: Multi-Snake: Loop
Parameter set Loop ( 3 agents )
(0.8, 0.7, 1.2)
1395
(0.9, 1.0, 1.0)
439
Loop ( 6 agents )
535
(0.9, 1.0, 1.0) のパラメータ組をもつエージェントに RGB 各色データ画像を与
えた 3 つのエージェントによる Multi-Snake では, ぬいぐるみの背中の部分で誤収
束している領域があったが, パラメータを組み合わせた計 6 つのエージェントによ
る Multi-Snake ではその領域も抽出に至っている. このように, 複数の可能性を探
索する Multi-Snake では, 抽出結果に安定性が増した.
また, このような収束結果に至るまでのループ数と, 前節の 3 つのエージェント
によるループ数を表 6.3 に示す.
6.5
考察
エージェント数を増やすことによる影響を検証するために本節では, 2 組の異な
るパラメータ組を用意し, 各パラメータ組をもつエージェントに RGB 各色データ
画像を与える, すなわち計 6 つのエージェントによる Multi-Snake の輪郭抽出実験
を行った.
本実験のようにエージェントを増やすことによる効果は以下の点が挙げられる. 1
つには, パラメータ組を変えたエージェントがもつ “パラメータ組のもつ抽出傾向を
緩和する” 性質によって, より多くの可能性を探索することによって目的の輪郭への
収束可能性が増すこと, 2 つめは, 画像エネルギーに対するパラメータの違いによっ
て, 各色データ画像から輪郭上の強度変化を検出, もしくは排除することによって,
より早く目的輪郭上で収束することが可能になることが挙げられる. これは収束ま
でのループ数にも変化を及ぼしている.
また, Snake を分散協調化し, 複数の可能性を並行に探索し協調動作を実行するこ
とによる影響と言えるが, 各制御点上でエネルギー値を算出する際に, 丸い形状の
部分ではそれに適したパラメータ組をもつエージェントが選択され, また屈曲のあ
る領域ではより適したパラメータ組をもつエージェントが選択されるといったよう
に, Snake 自身の形状や画像特徴量の変化への柔軟性が増すことなどが挙げられる.
71
このような理由により, 表 6.3 にみられるような収束までのループ数の変化が見ら
れると考察される.
6.6
複数データ Snake のリモートセンシングへの応用
原画像を表色系における各色データ画像をそれぞれエージェントに与えた MultiSnake は, 原画像からでは情報が不足するような場合でも, 各色データ画像から得ら
れる情報で補足し安定した抽出を実現した. Snake を実行する各エージェントがそ
れぞれ単一の色データ画像を扱い, 互いに協調しあう Mutli-Snakes は, リモートセ
ンシングにおけるマルチスペクトル画像での観測対象領域の抽出にそのまま応用す
ることが可能である. 本節では Multi-Snake の応用として, リモートセンシングの
マルチスペクトル画像を対象とした実験結果を示し, 本手法の有効性を検証する.
リモートセンシングとは, 航空機や人工衛星を用いて, 地球の環境または地形, 海
洋などの状態観測を行うシステムであり, 森林調査, 農地調査, 環境調査, 海洋水調
査を行う. これら調査の過程において, 森, 農地, 海洋中の寒暖領域や汚染領域, と
いった領域を正確に抽出することは最も重要な処理の一つである.
リモートセンシングの大きな特徴の一つとして, 観測に取得波長領域の異なる複
数のセンサーを用いるため, 調査対象の一つの領域を観測したスペクトルの異なる
複数の画像が得られることが挙げられる. マルチスペクトル・リモートセンシング
における従来の領域分割では, 単一スペクトルにおいて領域分割, 複数のスペクトル
画像を重ねあわせたカラー合成画像で領域分割 [53], リニアメント (画像内の線状
物体) 抽出 [54, 55], モルフォロジーを利用した手法 [56], 構造記述を用いた手法 [57]
などがある.
また, マルチスペクトル画像ではないが, 飛行機から撮影した航空写真を対象か
らの地形抽出に Snake を応用した例としては, Fua [58] が代表的な手法として挙げ
られる. 文献 [58] では, Polygonal Snake, Smooth Snakes and Ribbons, Network
Snake が詳述されている. これらはほぼ等間隔に置かれた “頂点” によってモデル
化した輪郭を使用し, それら頂点の調整項を加えたエネルギー関数を用いる Snake
であり, 2 次元を対象とした際はそれらを Polygonal Snake, または Smooth Snakes
と呼んでいる. また, Ribbons とは, 長尺形の輪郭とその中心座標, 幅をエネルギー
関数をさらに加えたものであり主に道路といったある一定の幅をもって存在する地
形の抽出に適した Snake である. Polygonal Snake を 3 次元に拡張した Network
Snake では, 他の地形を抽出した Snake もしくは他の角度から撮影された航空写真
72
から同じ地形を抽出した Snake のトポロジー情報から, それらを連結させることに
よって 3 次元建物の抽出を可能にしている. しかしながら, この手法は前に述べた
ように, 単一スペクトル画像, カラー合成画像, あるいは航空写真を抽出対象として
いる. その他にも, Fua らの Ribbons を拡張した Ribbon Snakes を用いて航空写真
から道路領域を自動抽出する手法 [59], ゼンリンのデジタル地図に描きこまれた建
築物の形状を初期閉曲線とする手法 [60,61] などがある. しかしながら我々の知る限
り, 複数のスペクトル画像を対象にして, 重ね合わせといった合成や前処理を行うこ
となく, 入手された複数のスペクトル画像から直接領域を推定する効果的な Snake
は未だ提案されていない.
異なるスペクトル画像を用いた Multi-Snake は, エージェント間の情報の共有に
より, 単一のスペクトル画像からでは不足してしまう情報やノイズ等不必要な情報
を, 他のエージェントに与えられたスペクトル画像から補填し修正しあうことが可
能である. したがって, マルチスペクトル画像の総合的な形状の解析が期待でき, ま
た十分な精度をもって観測対象を抽出することができると考えられる.
6.7
各スペクトルを与えた Multi-Snake による検証
検証実験では ASTER (Advanced Spaceborne Thermal emission and Reflection
Radiometer) を用いて長崎の橘湾を観測した画像を対象画像とする. ASTER とは,
NASA Jet Propulsion Laboratory の EOS 計画における衛星の 1 つである Terra
に搭載されており, 可視から熱赤外領域までに 14 バンドを有する高性能光学セン
サである. 本実験には, 0.5µm (緑), 0.6µm (赤), 0.7µm (近赤外) の 3 つの単一スペ
クトル画像を用いる. 各スペクトル画像を, 図 6.7 (a)–(c) に示す. これらの画像を
対象に, 本実験では 4 つの抽出結果の比較, すなわち, 単一スペクトル画像を対象と
したオリジナルの Snake の抽出結果, 従来手法のカラー合成画像を利用した領域分
割手法と提案手法との比較のために 0.5µm に緑, 0.6µm に青, 0.7µm に赤を割当て
たカラー合成画像 (図 6.7(d)) を対象としたオリジナルの Snake の抽出結果, 各スペ
クトル画像をエージェントに与えた 3 つのエージェントによる Multi-Snake の抽出
結果, 2 組の異なるパラメータ組をもつ 6 つのエージェントによる Multi-Snake の
抽出結果の比較を行う.
抽出対象は, 橘湾内に存在する “水質の均一な領域” とする. この領域は, 目視で
図 6.7(a) において最も確認しやすい. 湾内の海領域に対して, それ以外の海洋領域
に見られる縞のような模様な海洋汚染であり, このような海洋の汚染領域は地球各
所で観測される. 年々このような汚染領域は海流の影響などの理由で拡大しており,
73
(a) 0.5µm (green)
(b) 0.6µm (red)
(c) 0.7µm (infrared)
(d) color composite image
図 6.7: The target images of multi-spectral remote-sensing
74
陸近くの湾, もしくは陸地境界付近の水質の変化, または汚染を拡大する海流の境界
を検知することは海洋調査において重要な前処理の 1 つである. また, このような
海洋領域における水質の境界の特徴的なこととして, 一定の特徴をもつ海洋領域同
士の境界が直線的な境界になることが挙げられる.
そこで, このような海洋中に存在する水質の変化を表す境界を検出する目的で橘
湾内に Snake を適用し, 水質の均質な領域の抽出を試みる.
その結果を図 6.8 に示す. 単一のスペクトルからの領域抽出として, 目視において
最も汚染領域との境界が確認できる 0.5µm 画像を用いて, オリジナルの Snake を
用いて抽出を行った結果を図 6.8(a) に示す. 0.5µm 画像は, 目視では境界をハッキ
リ読み取ることはできるが, 境界付近に波などで生じる光の反射といったノイズが
あり, Snake はそれら海洋中の局所的な強度勾配に強い影響を受け, 目的の境界の抽
出に失敗している. この領域の輪郭を正確に抽出するためには, 0.5µm のスペクト
ルデータだけではなく, 反射などのノイズのより少ない 0.6µm や 0.7µm から得ら
れる情報もまた必要である.
(b) にカラー合成画像を対象としたオリジナルの Snake による抽出結果を示す.
カラー合成画像は, 得られた複数のスペクトル画像を重ね合わせることによって得
られる画像であるため, 各スペクトルによって観測された同一の対象領域の特徴を
総合的に分析することが可能である. すなわち 0.6µm や 0.7µm の情報も統合され
ているため, 0.7µm の近赤外で明瞭に得られる陸地境界など, 各スペクトル画像の
もつ強度勾配も抽出処理に導入することが可能である. しかしながら, 海洋中に存
在する反射などのノイズも同時に統合されるため, 単一スペクトルによるオリジナ
ルの Snake の抽出結果と同様に目的境界の抽出に失敗している.
次に, 0.5µm, 0.6µm, 0.7µm の各単一スペクトル画像をエージェントに与えた
Multi-Snake を用いて抽出を行った結果を図 6.8 (c) に示す. また, 6.4 で述べた 6
つのエージェント, すなわち 2 つのパラメータ組を用意しそれらをもつエージェン
トに各スペクトルデータを与えた Multi-Snake による実験結果を図 6.8(d) に示す.
さらに, より詳細な抽出結果の比較を行うために図 6.7 の一部領域を拡大したも
のとして, 図 6.9 には, 海洋部分における境界部分を, 図 6.10 には陸地境界部分を
示す.
図 6.9 において, (a) には, 0.5µm のスペクトル画像に対して汚染領域と湾内水
質領域との境界を人の手によって描いたものを白画素で示してある. (b) には単一
スペクトル画像を用いた Snake による抽出結果を, (c) にはカラー合成画像を用い
た Snake による抽出結果を, さらに (d) には Multi-Snake による抽出結果を, (e) に
75
(a) Single-Snake Result
using 0.5µm data
(b) Single-Snake using color composite image
(c) Multi-Snake ( 3 agents )
(0.4, 0.4, 0.3)
(0.4, 0.4, 0.3) + (0.5, 0.6, 0.5)
(d) Multi-Snake ( 6 agents )
図 6.8: Experiment with multi-spectral remote-sensing images (1)
76
(a) Desired contour
(b) Original Snake
(c) Original Snake using color composite image
(d) Multi-Snake ( 3 agents )
(e) Multi-Snake ( 6 agents )
図 6.9: Experiment with multi-spectral remote-sensing images: enlarged (1)
77
(a) Original Snake
(b) Color composite
(c) Multi-Snake ( 3 agents )
(d) Multi-Snake ( 6 agents )
(e) Original Snake
(f) Color composite
(g) Multi-Snake ( 3 agents )
(h) Multi-Snake ( 6 agents )
図 6.10: Experiment with multi-spectral remote-sensing images: enlarged (2)
78
表 6.4: Performances of experiments
ASTER (Fig.6.7)
Snake
Multi
Time(sec)
15.0
33.8
Loop Time/Loop
803 0.0187
657 0.0514
は 6 つのエージェントによる Multi-Snake による抽出結果の拡大画像を示してい
る. 単一のスペクトル画像に単一の Snake, カラー合成画像に単一の Snake の抽出
結果では, 望む領域の境界を得られず輪郭周辺のノイズで誤収束している. 一方で,
Multi-Snake では, 他のスペクトルからの情報によってこのような誤収束を避け, 目
的の輪郭で収束しているのが確認できる.
次に図 6.10(a) には単一のスペクトル画像を用いた Snake による海岸の抽出結果
を, (b) にはカラー合成画像を用いた Snake による抽出結果を, (c) には 3 つのエー
ジェントに各スペクトルデータを与えた Multi-Snake による抽出結果を, (d) には 6
つのエージェントによる抽出結果の拡大画像を示す. Snake は, 陸地内に存在するよ
り大きな輝度勾配にひきつけられ, 望まない領域まで変形しているが, Multi-Snake
では目的の海岸境界を抽出している.
また, (e)–(h) は (a)–(d) を踏襲して示している. この領域では, 陸地–海境界の岸
の形状が複雑な形をしており, 単一の Snake での誤収束だけでなく, 3 つの MultiSnake を用いても誤収束してしまっている. これはパラメータの抽出傾向と境界の
形状が適合せず目的輪郭を越えて陸地内部まで Snake の変形が生じている. この
領域において, 2 つのパラメータ組をもつ 6 つのエージェントによる抽出結果では,
(g) に示すようにより高精度な抽出を実現している.
さらに, 表 5.3 を踏襲して, 表 6.4 に実行時間を示す. 使用した CPU も同様に
Celeron 2.50 GHz である. 表に示すように, リモートスペクトル画像を対象とした本
実験は, RGB スペクトル分解画像での実験同様, “Time/Loop” では, 単一の Snake
と比べ約 3 倍の時間を要し, 一方でループ数の減少がみられ, これらはスペクトル
分解画像での実験と同様の理由で生じたものと考察される.
79
6.8
考察
本実験では, リモートセンシングにおけるマルチスペクトル画像を用いた抽出実験
を行い, 単一スペクトルに適用した Snake の抽出結果と, 3 つのスペクトル画像を用
いた Multi-Snake, 異なるパラメータをもつ 6 つのエージェントによる Multi-Snake
の抽出結果を比較した.
単一スペクトルに適用した Snake の抽出では, 境界付近に存在するノイズに捕ま
り誤収束し, また, カラー合成画像においては, 合成によって全スペクトルから得ら
れる情報を統合した画像による輪郭抽出を実現するが, しかしながらノイズもまた
統合されるため, 誤収束した. それに対して, Multi-Snake を用いることによって目
的の輪郭の抽出が実現できている. これは, 0.5µm では, 目視で明確な境界が確認
できる一方, 境界の付近にノイズが存在することが原因である. それに対して, 他の
スペクトル 0.6µm, 0.7µm の画像では, 目視で汚染領域との明確な境界の確認は難
しいが境界付近のノイズは存在しない. Multi-Snake では, これら他のスペクトル
画像から得られる情報によってノイズの影響を排除したことによって, 十分な精度
をもって目的の境界を検知することが可能になったと考えられる. このように, 単
一のスペクトルを用いた領域分割やカラー合成をした領域抽出に比べ, Multi-Snake
は全てのスペクトル画像から得られる情報を共有することができ, 総合的な形状の
解析が可能である.
しかしながら, この実験から Multi-Snake を用いても, 複雑な海岸線を完全に正
しく抽出することが難しいことが判る. これは, 異なるパラメータ組をもつ 6 つの
エージェントによる Multi-Snake によって精度向上がみられたが, 全ての海岸線に
おいて完全に正確な抽出には至っていない. エネルギー関数の性質上, Snake は複雑
な輪郭の抽出に不向きであることが大きな要因の 1 つと考えられるが, 本手法は, 複
雑形状に特化したエネルギー関数を加えた提案手法など, 他の提案手法をエージェ
ントに加えることによる統合が可能であり, それによって改善されると考えている.
また人工衛星から得られたリモートセンシングでは, 衛星で観測されたデータが
実際に地上で計測されたデータとどの程度まで一致しているかを評価する地上で測
定されたデータ (Truth data, 陸域データは Ground truth, 海域データは Sea truth
と呼ぶ) が存在する. 本手法は, この Truth data をエージェントに与え, 抽出処理
に組み込むことが可能であり, これにより更なる精度向上が期待できる.
具体的には, Ground truth data として輪郭上のある特徴点の位置情報が明確に
なっている場合には, 周囲 8 近傍とのエネルギー勾配を極めて大きくすることによっ
て, 意図的に Ground truth 上に位置を固定させた特殊なエージェントを用意する.
80
この特殊エージェントは, そのエネルギー勾配の影響を強く受け, その位置から移動
することができない. また, 他の輪郭上の通常エージェントは, 特殊エージェントの
常駐する Ground truth にさしかかった場合は, その特殊エージェントと協調するこ
とによって通常エージェントも Ground truth から逃れることはできず, 結果的に
Ground truth を含む輪郭での収束が可能になり, より安定した目的領域の抽出が期
待できる.
81
第7章
複数関数 Snake の分散協調
本論文 4.2 において, Snake の分散協調化には以下のようなケースが考えられると
述べた.
1. Esnake のパラメータを変えた複数の Snake
2. 関連する複数の画像に適用した複数の Snake
3. エネルギー関数が異なる複数の Snake
4. 異なる初期閉曲線をもつ複数の Snake
前章まではこれらの 1. と 2. について議論し, また複数の実験を通して本手法を検
証し, その有効性を確認した. 本章では, 3. エネルギー関数の異なるエージェント
による複数の Snake について議論し, 幾つかの実験を通してその有効性を検証して
いく.
7.1
モデル導入による高精度化
Snake は, 初期閉曲線への依存性やパラメータと形状の不適合によって誤収束が
起こるといった脆弱性をもっているおり, また凹領域や尖鋭部を含む対象物の抽出
が困難である性質をもつ. 特に凹領域の抽出は, パラメータの調節だけでは抽出に
は至らない場合が多く, 肌理細やかな初期閉曲線の設定をユーザーに要求し, 非常に
大きな問題として残されている.
この凹領域への脆弱性がどのような原因で生じるかを捉えるために, 図 7.1(a) に
凹領域におけるエネルギーポテンシャルがどのようになるかを図式的に示す. 図中
の矢印は輪郭に引き付ける力を大きさをもって表している. 図のように凹領域内の
最凹部を抽出したければ対象物に非常に近づけて初期閉曲線を設定しなければなら
ず, Snake が最凹部に存在する対象物に向かうポテンシャル場傾斜から出てしまう
と, 例えば図 (b) のように直線状に収束してしまう. これが Snake の凹領域への脆
弱性の本質である.
82
(a) Energy potential
(b) Snake movement
(c) Our idea
図 7.1: Around the concave boundary region
このような凹領域を安定して抽出するために, 本論文では, “Snake を実行する際
にユーザーが与える初期閉曲線は, ユーザーが望む対象物の大まかな形状という情
報が含まれる (あるいは容易に含ませ得る) ” ことに着目し, この情報をモデルとし
て利用し Snake の制御に反映することを考える.
対象領域の形状情報を事前知識として, サンプルを用いた学習やプロトタイプ
を Snake に導入する従来の手法には, 利用者が作成したプロトタイプ [62, 63] の提
示により対象領域の抽出に適した Eint を事前に決定し, 各対象領域ごとの形状情
報を抽出処理に反映させる手法や, 複数のサンプルから対象領域の平均的な形状と
形状のばらつきを推定, 領域抽出の際に許容すべき形状のずれの範囲を決定する手
法 [7, 64–66], また, ユーザーの求める領域をより効率的, 効果的に導入する手法と
してユーザーが与える初期輪郭線に着目し, そこから得られる知識を抽出処理に導
入する手法 [67] などがある.
特に, 松澤らの手法 [67] は, 初期閉曲線から得られる “コーナー”, “直線”,“曲線”,
“線分”,“円弧” といった知識を記号化して記述し, この記号列に基づき Snake の制
御点に形状情報を各々割当て, 各割当てのもとで適切な制御点位置の探索を行うこ
とにより, 対象領域の形状に関する知識を Snake の制御へ反映させている. このよ
うに, ユーザーが設定する初期閉曲線に含まれる情報に基づいて, 対象物のモデルを
獲得するアプローチでは, Snake の汎用性や利便性を損なうことなく, モデルを輪郭
抽出処理へ導入し得るという優れた性質をもつ.
そこで松澤らの研究を参考に, 図 7.1(c) に示すように, 初期閉曲線の断片形状を
モデル化することを考え, そのモデルを Snake の制御に導入することを考える. 但
し, 松澤らの手法では, 各部位の “線分”,“円弧” といった記号列に基づく Snake の
制御であり, この記号化では細かい特徴を記述できない. よって本手法では, より具
体的に, 各部位での曲率を用いることにした.
本論文では, 曲率モデルに基づくエネルギー項を新たにエネルギー関数に加えた
83
Curvature Snake をエージェントとして導入し, 複数のエージェントによる分散協調
型の輪郭抽出処理を行うことによって, より高精度な輪郭抽出を実現する Curvature
Multi-Snake を提案する.
7.2
方式
ユーザーの設定する初期閉曲線には対象に関する情報が含まれており, 本手法で
は初期閉曲線上での各部位, 具体的には各特徴点ごとの曲率をモデルと考え, そのモ
デルに従う Snake を本論文では Curvature Snake と呼ぶこととする.
Curvature Snake では, 次式の曲率エネルギー項 Ecurvature を式 (2.1) の右辺に加
えたエネルギー関数を用いる.
Ecurvature (v(s)) = δ|Einitialcurv − Ecurrentcurv |
(7.1)
Einitialcurv は初期閉曲線上の特徴点で算出される曲率であり, 図 7.2(a) に示すように,
初期閉曲線を等間隔に分割して得られた特徴点を用いて算出する. また, Ecurrentcurv
は初期特徴点と対応付けられた各時刻の輪郭上の特徴点における曲率である.
Snake の制御点は収束に従って移動し, 輪郭に沿って移動することもあるため, 初
期閉曲線上の特徴点から得られた曲率モデルを, 各時刻における Snake の輪郭上の
どの制御点と対応付けるかが問題となる. そこで Curvature Snake では, 特徴点ご
とに対応する基準線を導入する. 各時刻における Snake の輪郭上の特徴点は, 制御
点がその基準線に重なった点とし, 特徴点では Curvature Snake のエネルギー関数
を用い, 特徴点間の Snake の制御点では オリジナルの Snake のエネルギー関数を
用いることとする.
すなわち, 各時刻の Snake の制御点が基準線に重なったときは, Curvature Snake
を実行するエージェントとオリジナルの Snake を実行するエージェントの 2 つが
協調して動作する. このような関数形の異なる 2 種類のエージェントによる分散協
調 (Curvature Multi-Snake: CMS) を考える.
基準線はさまざまなものが考えられ, 例えば初期輪郭に対する法線, 初期閉曲線
の重心点からの線分などが挙げられるが, ここでは, Snake の変形に伴い大きく屈曲
している領域に多くの特徴点が集まる (図 7.2(b)) という理由から, 後者を採用する.
Curvature Multi-Snake は, このように対応付けられた特徴点上でモデルに従う
ことにより, Snake のもつ凹部への脆弱性を改善する一方, Snake のもつ抽出結果に
滑らかさをもつという性質を欠くことなくより安定した抽出が可能になるだろうと
84
(a) 初期閉曲線上の特徴点と基準線
(b) 収束過程の特徴点
図 7.2: Principle of Curvature Snake
予測される.
ここで, Curvature Multi-Snake の処理全体は以下のような流れになる.
ユーザによる初期輪郭の設定
初期輪郭の重心を算出
初期輪郭を等間隔 ∆s で M 個に分割し特徴点を獲得
do
for 輪郭上の全ての制御点について
if 基準線上の制御点
Curvature Snake と Snake による協調
else 通常のエネルギー関数による新制御点候補の選出
until 収束するまで
初期閉曲線から重心座標を求めるには, 初期閉曲線の制御点の座標を (xi , yi ), 制
御点の個数を n とするとガウスの発散定理を応用した以下の式を用いる.
n
1
(xi yi+1 − xi+1 yi )(xi+1 + xi )
6 i=1
x0 =
A
n
1
(xi yi+1 − xi+1 yi )(yi+1 + yi )
6 i=1
y0 =
A
85
(7.2)
(7.3)
ただし, A は曲線内の面積にあたり, 以下の式で求める.
A=
n
1
(xi yi+1 − xi+1 yi )
2 i=1
(7.4)
次に, 初期閉曲線を等間隔 ∆s で M 等分した M + 1 個の特徴点から曲率を求め
るには, 以下の式を用いる. 但し, 特徴点 Si の座標を (xi , yi ) とすると輪郭パラメー
タ s による 1 次, 2 次導関数は次式により計算できる.
dxi
xi+1 − xi−1
≈
ds
2∆s2
dyi
yi+2 − yi−1
≈
ds
2∆s2
d2 xi
xi+1 − 2xi + xi−1
≈
ds2
∆s2
yi+1 − 2yi + yi−1
d2 y i
≈
2
ds
∆s2
ここで,
求まる.
(7.5)
(7.6)
(7.7)
(7.8)
dxi
d2 xi
を xs ,
を xss と表記すれば, 特徴点 Si の曲率 ki は次式により
ds
ds2
ki =
yss xs − xss ys
3
(x2s + ys2) 2
(7.9)
一方で, 抽出過程にある時刻 t における輪郭上の特徴点では, 特徴点間の距離が
一定には保たれず変化してしまうため, 上述の 1 次微分, 2 次微分式をそのまま利
用することができない. しかしながら各時刻 t の曲率は, 常に正確な曲率を求める
必要はなく近似値で十分であるので, 上述の式から得られる以下の近似式を用いる.
ここで, 用いられる変数 ∆si は, 座標 (xi , yi ) に存在する特徴点を Si とすれば, ∆si
は, その時刻での特徴点 Si と Si+1 間の弧の長さを表す (図 7.2).
xi+1 − xi−1
dxi
≈
ds
∆si−1 + ∆si
(7.10)
yi+2 − yi−1
dyi
≈
ds
∆si−1 + ∆si
(7.11)
xi+1 − 2xi + xi−1
d2 xi
≈
2
ds
∆si−1 · ∆si
(7.12)
d2 y i
yi+1 − 2yi + yi−1
≈
2
ds
∆si−1 · ∆si
(7.13)
86
(a) (0.4, 0.6, 1.0, 1.0)
(b) (0.4, 0.6, 1.0, 1.5)
(c) (0.7, 0.5, 1.0, 1.0)
図 7.3: Curvature Snake Only
以上の式を用いて, 各時刻における各特徴点の曲率を求める. 各特徴点では式
( 2.1) に式 ( 7.1) を加えたエネルギー関数を用いてエネルギー値を求め, 新制御点
候補を選出する.
なお, 初期閉曲線が凹部を含む形状の場合, 各時刻の Snake 上の特徴点との対応
付けにおいて, 複数の初期特徴点と対応付けがされる場合がある. このような場合
は, 現時刻での特徴点と初期特徴点との距離を比較し, より距離が短い初期特徴点と
対応付けを行うこととする.
7.3
検証
対象画像は, 5 章の複数パラメータの協調による輪郭抽出実験において, 異なるパ
ラメータ組を用いた Multi-Snake でも誤収束した図 5.8(case 4), 図 5.11(case 7) を
用い, 初期閉曲線も同一のものを用いる.
まず, 単一の Curvature Snake による抽出実験を行う. すなわち, 各時刻において
基準線上に存在する特徴点では曲率エネルギー項を加えたエネルギー関数を用い,
それ以外の制御点ではオリジナルの Esnake を用いて輪郭抽出処理を進める単一の
Snake による輪郭抽出実験を行い, 曲率項を加えたエネルギー関数が有効であるか
どうかを検証する.
図 7.3 にその結果を示す. 初期閉曲線を黒画素, 収束結果を緑画素で表し, 各閉曲
線上に存在する赤い画素が, 特徴点である. なお, 特徴点は 30 点としている.
(a),(b) においては, 曲率エネルギー項の重み付けを行う δ の値が違うが, どちら
87
(a) (0.4, 0.6, 1.0)
+ (0.0, 0.0, 0.0, 1.0)
(b) (0.7, 0.5, 1.0)
+ (0.0, 0.0, 0.0, 1.0)
図 7.4: CMS: (α, β, γ)+(0, 0, 0, δ)
も目的の輪郭を十分な精度をもって抽出している. それに対して (c) のように曲率
モデルを導入しても誤収束してしまうような場合もあった. これは, 誤収束領域で
は特徴点が 1 点しかなく, また, 曲率モデルとの対応付けも凹部の凹みの方向へ働
くモデルではなかったため, 望むとおりの働きがなされなかったことが原因と考え
られる. このように, 対象物の形状や, Snake 自身の変形によっては, 狙い通りの対
応付けが得られない対象物の形状がある.
では, (0.0, 0.0, 0.0, δ) のパラメータを与えた Curvature Snake と (α, β, γ) をも
つオリジナルの Snake を実行するエージェントで協調させると Curvature MultiSnake はどのような挙動を示すだろうか. すなわち, この実験では Curvature Snake
は, Eint や Eext のエネルギーを影響を受けないため, 各特徴点上では, Ecurvature の
みの影響で動作するエージェントと, 式 ( 2.1) に示す Esnake を用いて動作するエー
ジェントとの協調になる. その結果を図 7.4 に示す.
同図 (a) に, パラメータ (0.4, 0.6, 1.0) をもつオリジナルの Snake エージェント
と, (0.0, 0.0, 0.0, 1.0) をもつ Curvature Snake エージェントによる Curvature MultiSnake の抽出結果を, (b) についても同様に, (0.7, 0.5, 1.0) のパラメータをもつオリ
ジナルの Snake エージェントと (0.0, 0.0, 0.0, 1.0) の Curvature Snake エージェン
トによる Curvature Multi-Snake の抽出結果を示す. (a), (b) どちらの形状において
も, その抽出精度が改善が見られる.
また, (0.0, 0.0, 0.0, δ) ではなく, (α, β, γ, δ) の Curvature Snake エージェントと
(α, β, γ) のパラメータ組をもつオリジナルの Snake エージェントによる Curvature
Multi-Snake でも同様の実験を行い, 抽出精度の改善が見られた (図 7.5).
88
(a) (0.4, 0.6, 1.0)
+ (0.4, 0.6, 1.0, 1.0)
(b) (0.4, 0.6, 1.0)
+ (0.4, 0.6, 1.0, 1.5)
(c) (0.7, 0.5, 1.0)
+ (0.7, 0.5, 1.0, 1.0)
図 7.5: CMS: (α, β, γ)+(α, β, γ, δ)
ここで, 各特徴点上でオリジナルの Snake を実行するエージェントと, Curvature
Snake エージェントの協調動作において, 収束過程でどちらのエージェントの結果
が選択されたかを調査すると, 収束が近づいていくにつれてオリジナルの Snake を
選択する傾向があった.
Curvature Snake 単体による抽出実験 (図 7.3) では, (α, β, γ, δ) のパラメータのみ
を用いているため, 特徴点上では必ず曲率エネルギーの影響を受けることになる. そ
れに対して, オリジナルの Snake と Curvature Snake との分散協調では, 各時刻の
輪郭の形状や輝度勾配に応じて適切なエージェントが選択される. これは動的に δ
を調整していることを意味し, Curvature Multi-Snake は, 曲率モデルによって望ま
ない形状への変形を防ぐだけでなく, 対象領域付近ではより滑らかな輪郭を抽出す
るため, 単一の曲率項をもつ Snake より安定した抽出が可能である.
しかしながら, 全てのパラメータ組においてこの Curvature Multi-Snake が図 7.5
のように正確な抽出を実現できるわけではない. 誤収束してしまうパラメータ組の
例を図 7.6(a), (b) に示す. このようなパラメータ組への依存性は, 5 章で述べた複
数パラメータ協調の方式のように, 異なるパラメータ組をもつオリジナルの Snake
エージェントを 2 つ, Curvature Snake エージェントを 1 つの計 3 つのエージェント
による Curvature Multi-Snake を用いることで, 改善されるだろうか. その実験結果
を図 7.6(c) に示す. このような 3 つのエージェントによる Curvature Multi-Snake
では, 曲率モデルによって凹部抽出への安定性が向上するだけでなく, パラメータ組
のもつ抽出傾向を緩和することによってパラメータ組への依存性を改善し, より安
定した抽出処理を実現できる.
また, 1 つのオリジナル Snake エージェントと 2 つの Curvature Snake エージェ
89
(a) (0.1, 0.4, 1.0)
+ (0.1, 0.4, 1.0, 1.0)
(b) (0.3, 0.7, 1.0)
+ (0.3, 0.7, 1.0, 1.0)
(c) (0.1, 0.4, 1.0)
+ (0.3, 0.7, 1.0)
+ (0.4, 0.6, 1.0, 1.0)
(d) (0.3, 0.7, 1.0)
+ (0.3, 0.7, 1.0, 1.0)
+ (0.3, 0.7, 1.0, 1.5)
図 7.6: CMS: Original Snake (1 or 2 agents) ＋ Curvature Snake (1 or 2 agents)
ントによる分散協調の結果でも抽出精度に改善が見られた (図 7.6(d))
以上の実験においては, 特徴点の個数を 30 点としていたが, 特徴点の個数を変化
させると抽出結果にどのような変化が見られるだろうか. 特徴点数を変化させた実
験の結果を図 7.7 に示し, 実行時間を表 7.1 に示す. ただし, これらは, (0.6, 0.4, 1.0)
のパラメータ組をもつオリジナル Snake エージェント 1 つと (0.4, 0.6, 1.0, 1.0) の
パラメータ組をもつ Curvature Snake エージェント 1 つの計 2 つのエージェントに
よる Curvature Multi-Snake である.
図 7.7 に示すように, 特徴点の個数はその抽出結果に大きな影響を及ぼすことが判
る. また, 表 7.1 において, Loop はループ数を, Time は実行時間を, また Time/Loop
は 1 回のループに要した時間を表している. Time/Loop において, CMS はオリジ
ナルの Snake の約 3 倍の時間を必要としている. これは, 各特徴点における曲率を
90
(a) 特徴点数 10
(b) 特徴点数 20
図 7.7: Effects of the Number of Representative Points
表 7.1: Performance
Point num
Original Snake
CMS 10
CMS 20
CMS 30
Loop
103
98
78
62
Time Time/Loop
0.157
0.00152
0.422
0.00431
0.359
0.00460
0.328
0.00529
求める計算に要した時間と Ecurvature 計算に要した時間が影響している.
次に実画像における抽出結果を図 7.8 に示す. (a) には, 対象画像の輝度値をグラ
デーションで表したもの, (b) には初期閉曲線を示し, 全制御点数は 1784 点である.
それに対して, 特徴点数は 180 点であり, オリジナル Snake の抽出結果とパラメー
タ組 (α, β, γ, δ) の Curvature Snake による Curvature Multi-Snake の抽出結果の比
較を行う.
(c) には, パラメータが (0.6, 0.4, 0.5) オリジナルの Snake の抽出結果を示し, ま
た (b) には同じパラメータ組をもつオリジナルの Snake と (0.6, 0.4, 0.5, 1.5) のパラ
メータをもつ Curvature Snake の抽出結果を示す. このパラメータ組では Curvature
Multi-Snake を用いても誤収束しており, これは凹領域の最深部において対象領域
と背景領域の輝度勾配が小さくなっており, その輝度勾配とパラメータ組によって
形成される Snake の輪郭を引き付ける力が弱いことが原因と考えられる. それに
対して, 画像特徴量に関するエネルギー項へのパラメータである γ を大きくした
(0.6, 0.4, 1.0) をもつ Snake の抽出結果を (e) に, (0.6, 0.4, 1.0, 1.5) のパラメータを
91
(a) Intensity of target image
(b) Initial contour
(c) (0.6, 0.4, 0.5)
(d) CMS: (0.6, 0.4, 0.5, 1.5)
(e) (0.6, 0.4, 1.0)
(f) CMS: (0.6, 0.4, 1.0, 1.5)
図 7.8: CMS (α, β, γ)+(α, β, γ, δ): real
92
もつ Curvature Snake との協調を行う Curvature Multi-Snake の抽出結果を (f) に
示す. このように, Curvature Multi-Snake では凹領域での安定性が見られ, より精
度の高い抽出を実現している.
7.4
考察
Snake のもつ凹部への脆弱性を取り除くために, 初期閉曲線から得られる形状情
報として, 特徴点上の曲率モデルをエネルギー関数に導入した Curvature Snake を
提案し, この Curvature Snake エージェントとオリジナルの Snake エージェントと
の分散協調を行う Curvature Multi-Snake の有効性の検証を行った.
まず, 単一の Curvature Snake による実験では, 曲率エネルギー項の導入によっ
て凹部に対する Snake の脆弱性が改善することが確認できた. しかしながら初期閉
曲線の重心と特徴点を結ぶ基準線による対応付けが難しく, 精度向上には至らない
形状もあった.
Curvature Snake エージェントとオリジナルの Snake エージェントが協調動作を
行う Curvature Multi-Snake による実験では, より安定した抽出を実現している. こ
の Curvature Multi-Snake の特徴として, Snake の収束の各段階において Curvature
Snake エージェントとオリジナルの Snake エージェントのどちらの探索結果が選択
されたかを調査すると, 収束の初期段階と比較して, 最終段階 (輪郭付近) ではオリ
ジナルの Snake を選択する傾向にあった. この傾向は, 輪郭の形状や対象領域と背
景領域の輝度勾配に応じて適切なエージェントが選択されることによって, 輪郭を
滑らかに抽出することができるという Snake の性質を損なうことなく抽出が可能
であることを示している.
また, 初期閉曲線が凹部を含む形状の場合, 各時刻の Snake 上の特徴点との対応
付けにおいて, 複数の初期特徴点と対応付けられる場合があり, Curvature Snake で
は対処として, 現時刻での特徴点と初期特徴点との距離をそれぞれ比較し, より距
離が短い初期特徴点と対応付けることにしている. しかしながら, このような対応
付けによって誤収束が発生する場合には, オリジナルの Snake エージェントと, 特
徴点が 30 点の Curvature Snake エージェント, 特徴点が 20 点の Curvature Snake
エージェントでの協調によりその問題は回避し得ると考えられる.
さらに, 実画像における抽出実験においても Curvature Multi-Snake による抽出
精度の向上がみられた. 今回の実験対象とした手のような凹領域を多くもつ抽出対
象では, オリジナルの Snake では初期閉曲線設定, パラメータ決定が非常に難しく
93
ユーザーに多大な労力を課す. Curvature Multi-Snake においても初期閉曲線は工
夫される必要がある. すなわち, 対象物の形状に近い曲率を維持させるために, 対象
物のもつ凹凸には忠実に初期閉曲線を設定する必要がある. また, 後者のパラメー
タ決定は一般に, 試行錯誤的に行われる場合が多いが, Curvature Multi-Snake では,
Curvature Snake エージェントを選択した特徴点上において, 曲率エネルギー項に
よる形状固定力が働き, オリジナルの Snake における形状に関するパラメータの影
響が軽減するため, 結果的にパラメータ決定が容易になる効果がある.
以上のように, 初期閉曲線から得られる形状情報を, 曲率モデルとの差分であるエ
ネルギー項を加えることによって, その抽出精度に改善が見られ, またそれをエージェ
ントとして, オリジナルの Snake との分散協調を行うことに Curvature Multi-Snake
では, より安定した抽出が実現できると言える.
94
第8章
8.1
結論
研究成果
本研究では, 動的輪郭モデル Snake に分散協調処理を取り入れることによって,
柔軟性と拡張性をもち, より高い抽出精度を実現する輪郭抽出手法の研究を行った.
すなわち, 異なる解空間をもつエージェントを複数用意し, 各エージェントはユー
ザーが設定する 1 つの初期閉曲線から並行に複数の解候補を探索していく. その途
中でエージェントは互いに情報を交換し, 受け取った情報に基づいて自身の推定輪
郭を修正していく. このような処理により, 局所解への誤収束を回避し, 目的の輪郭
まで到達する可能性を高めることができる.
本手法は, ある特定の対象への抽出精度を向上させるというものではなく, どんな
対象物でも安定した抽出を実現する Snake である. 具体的には, Snake のもつパラ
メータ組の不適合や Snake の輪郭に沿った局所的な情報への依存, また凹領域の抽
出が難しいといった Snake の脆弱性を改善することによって, より高精度な抽出を
実現する. 分散協調を取り入れることによって, 本手法は以下のような特性をもつ.
• 多数のエージェントが協力して輪郭抽出を行うため, 全体の処理効率が向上
する.
• 単体では誤収束してしまう対象でも多数のエージェントが協調動作を行うこ
とにより抽出が可能になる.
• あるエージェントの性質が対象に対して不適合であっても, 他のエージェント
により誤収束を回避することができ, 柔軟な輪郭抽出が可能になる.
• エージェントの追加によって容易に拡張, 機能追加が行える.
また本手法は, 非常に簡素な設計でありながら, それだけでも精度向上をもたら
すだけでなく, これまで提案されてきたエネルギー項を追加した Snake やモデルを
95
利用した Snake といった, 様々な従来手法と排他的に競合することなく, 併用して
更なる精度向上を見込むことができるという大きな特徴を有する.
本論文では, 具体的な分散協調型の Snake として, 異なるパラメータ組をもたせ
たエージェントによる Multi-Snake と, 原画像を表色系による各色データ画像へと
分解し各色データ画像を与えたエージェントによる Multi-Snake の実験を通して本
手法の有効性を検証した. また, ユーザーが与える初期閉曲線に含まれる (もしく
は容易に含ませ得る) 対象の大まかな形状という情報を Snake の制御に導入する
Curvature Multi-Snake を提案し, 幾つかの実験を通して検証を行った.
複数パラメータによる協調, すなわち異なるパラメータ組をもたせたエージェン
トによる分散協調では, 人工画像と実画像を用いた抽出実験を行った. 実験では,
Multi-Snake を用いることによる抽出精度の向上がみられ, 複数のパラメータ組の
抽出傾向を緩和し, より安定性が増すことを確認した. 単一の Snake では高い抽出
精度を得るためのパラメータは, 抽出対象の輪郭の形状と画像特徴量分布を考慮せ
ねばならず, 求めることは難しい. たとえ対象物が背景との間で十分な輝度勾配を
もち, ノイズが存在しないような理想状態においても, 輪郭の形状とパラメータ組
の示す抽出傾向が一致しない場合は, 目的の輪郭の抽出ができない. それに対して,
異なるパラメータ組を用いた Multi-Snake では, エネルギー勾配の授受と探索経過
の修正によって, 複数のパラメータ組の抽出傾向を緩和し, その抽出処理に安定性
が増す. この異なるパラメータ組のもつ抽出傾向の緩和という性質により, 単一の
Snake のパラメータ設定の難しさを Multi-Snake では軽減し, より安定した抽出結
果を得た.
また本論文では, 異なるパラメータ組をもたせたエージェントによる Multi-Snake
における, エージェントとして組み合わせたときに最適なパラメータ組についての
議論も行った. 本実験を通して, パラメータ組の組合せは, 抽出形状として両極の傾
向を示すパラメータ組をエージェントに与えた時に, より安定した抽出結果を示し
た. これは, パラメータ組によって作られる解空間が多様になり, 局所解の発見の
機会を増やすことによって, 結果的に誤収束の可能性を減じたことが原因と考えら
れる.
望ましい輝度勾配が得られない画像について, それを表色系における各色データ
画像へと分解し, 各色データ画像をそれぞれ与えられた複数の Snake を分散協調さ
せる Multi-Snake では, 人工画像, 実画像ともに, 単一の Snake と同じパラメータ組
を用いたエージェントに, 各色データ画像をそれぞれ与えた Multi-Snake を用いる
ことによって高精度の輪郭抽出を実現した. これは, 輝度勾配としては対象の輪郭
を検出できずに単一の Snake では誤収束してしまうのを, エージェントは与えられ
96
た RGB, HSI, 大田らの提案する 3 次元表色系における各色データから強度変化を
検知し, その情報の共有と協調によって安定した抽出処理を実現したと考えられる.
また, エージェントを増やすことによる影響を調査するために, RGB 各色データ
画像を与えられたパラメータの異なる Multi-Snake による抽出実験を行った. エー
ジェントを増やすことによる効果は, 1 つにはパラメータ組を変えたエージェント
がもつ “パラメータ組のもつ抽出傾向を緩和” する性質により, より多くの可能性を
探索することによって目的の輪郭への収束可能性が増すこと, 2 つめは, 画像エネル
ギーに対するパラメータの違いによって, 各色データ画像から輪郭上の強度変化を
検出, もしくは排除することによって, より早く目的輪郭上で収束することが可能に
なることが挙げられる. また, Snake を分散協調化し, 複数の可能性を並行に探索し
協調動作を実行することによる影響と言えるが, 各制御点で協調動作を行う際, 円い
形状の部分ではそれに適したパラメータ組をもつエージェントが選択され, また屈
曲のある領域ではより適したパラメータ組をもつエージェントが選択されるといっ
たように, Snake 自身の形状や画像特徴量の変化への柔軟性が増すことなどが挙げ
られる.
さらに, 本論文で示した表色系における各色データ画像をそれぞれ与えられたエー
ジェントによる分散協調手法は, リモートセンシングにおいて重要な処理の一つで
ある観測対象の領域分割にそのまま応用することができ, リモートセンシング分野
においてこれまで行われてきた単一スペクトル画像を使って領域抽出を行う手法や,
各スペクトル画像を重ねたカラー合成画像から領域抽出を行う手法に比べ, 本手法
はより安定した抽出を行うことを検証実験を通して示した.
最後に, Snake のもつ凹領域への脆弱性を改善する目的で, Snake を実行する際
にユーザーが与える初期閉曲線にはユーザーが望む対象物の大まかな形状という情
報が含まれる (或いは容易に含ませ得る) ことに着目し, この情報をモデルとして利
用し Snake の制御に反映した Curvature Multi-Snake を提案した. これは, 初期閉
曲線の各部位の曲率をモデルとし, 各時刻の Snake の輪郭上の特徴点においては,
曲率モデルとの差である曲率エネルギー項を加えたエネルギー関数に基づき動作す
る Curvature Snake をエージェントとし, オリジナルの Snake と協調動作を行う
Multi-Snake である. 複数パラメータ協調の方式でも抽出に至らなかった対象画像
で, 初期閉曲線も同一のものを用いた実験では, 凹部を含む目的輪郭の抽出に成功
し, またその収束過程においてもループ数の減少が見られ, より安定した収束過程を
辿ることが確認された. また, エージェントとしての Curvature Snake, オリジナル
の Snake の組合せはさまざまなものが考えられ, また, その個数にも制限はないこ
とを幾つかの実験を通して示した.
97
8.2
残された課題
現在のところ, 本研究で提案した分散協調処理の手法は, Snake の初期閉曲線への
依存性という弱点を解決できていない. 適切な初期閉曲線を設定して高い推定精度
を得るには, 労力と試行錯誤を要するという課題が残っている.
例えば, 異なるパラメータ組をもたせたエージェントによる Multi-Snake では,
Snake のもつ凹領域や尖鋭部への脆弱性を完全に克服するものではなく, あくまで
各パラメータ組の抽出結果の最適部分を合成したような結果に留まった. これもま
た, Snake のもつ初期閉曲線への依存性といった脆弱性と密接な関わりをもつ. こ
のような凹領域や尖鋭部における抽出精度を向上させるには, 1 つの対象物に対し
て異なる初期閉曲線をもつエージェントを用いた Multi-Snake などの改善手法や,
他の関連手法と有効に併用することができるという特徴を生かすなどして, この問
題に対応することが考えられる.
Curvature Multi-Snake においては, 人工画像, 実画像のいずれの実験においても
より詳細なデータ解析が必要であり, また, その結果更なる改良の可能性がありこれ
を今後の課題とする.
98
謝辞
本論文を纏める機会を与えてくださり, また本研究を行うにあたり, 日頃より温かい
御指導, 御鞭撻, 格別の御配慮を賜りました埼玉大学大学院理工学研究科数理電子情
報部門 吉田 紀彦 教授に心より厚くお礼申し上げます.
埼玉大学大学院理工学研究科数理電子情報部門 前川 仁 教授, 同 大澤 裕 教授, 同
久野 義徳 教授 には, 本論文をまとめるにあたり懇切なご指導, ご鞭撻, 有益なご助
言をいただき, 深く感謝申し上げます.
様々な面での御教授, 温かい励ましを賜りました長崎大学工学部情報システム工
学科 楢崎 修二 助教授に深く感謝申し上げます.
また, 長崎大学工学部情報システム工学科 森山 雅雄 助教授には, 公私共に多く
の有益なご意見をいただき, またリモートセンシング画像をご提供いただき, 深く感
謝申し上げます.
日頃よりお世話になり, 本研究に対して様々な御意見・御指導をいただいた研究
室の皆様に厚くお礼申し上げます. また, 温かい言葉, 激励をいただいた全ての方々
に感謝いたします.
99
公表論文
審査制度のある学術誌等掲載論文
• 松本 倫子, 吉田 紀彦, 楢崎 修二: “動的輪郭モデル Snakes の分散協調による
高精度化” 画像電子学会論文誌, Vol.34, No.6, pp.747–752, 2005.11
審査制度のある国際会議論文集掲載論文
• Noriko Matsumoto, Norihiko Yoshida, Shuji Narazaki: “Cooperative Active
Contour Model and Its Application to Remote Sensing” Proc. ACM 21st
Annual Symp. on Applied Computing, pp.44–45, 2006.4
口頭発表
• 松本 倫子, 吉田 紀彦, 楢崎 修二: “動的輪郭モデル Snakes の分散協調による
高精度化” 情報処理学会/電子情報通信学会 情報科学技術フォーラム 2004 論
文集, Vol.3, pp.117–119, 2004.9
• 松本 倫子, 吉田 紀彦, 楢崎 修二: “分散協調型の動的輪郭モデル Snake” 画像
電子学会 第 33 回年次大会論文集, pp.5–6, 2005.6
• 松本 倫子, 吉田 紀彦, 楢崎 修二: “分散協調型動的輪郭モデル Snakes の評価”
情報処理学会/電子情報通信学会 情報科学技術フォーラム 2005 論文集, Vol.3,
pp.61-63, 2005.9
100
参考文献
[1] 安居院 猛, 長尾 智晴: 画像の処理と認識, 昭晃堂 (1992).
[2] M. Kass, A. Witkin and D. Terzopoulos: “Snakes: Active contour model”,
Int.J. Computer Vision, Vol.1, No.4, pp.321–331 (1988).
[3] 美濃 導彦, 天野 晃: “Snakes: 現在・過去・未来”, 信学技報, PRMU97-184 (1997).
[4] 松山 隆司, 久野 義徳, 井宮 淳 (編): コンピュータビジョン: 技術評論と将来展
望, 新技術コミュニケーションズ (1998).
[5] A. Blake, M. Isard: Active Contours, Springer (1998).
[6] 天野 晃, 坂口 嘉之, 美濃 導彦, 池田 克夫: “サンプル輪郭モデルを利用した
Snakes”, 信学論 (D-II), Vol.J76-D-II, No.6, pp.1168–1176, June (1993).
[7] T.F. Cootes, C.J. Taylor, D.H. Cooper and J. Graham: “Active shape model Their training and application”, Computer Vision and Image Understanding,
Vol.61, No.1, pp.38–59 (1995).
[8] T. McInerney, D. Terzopoulos: “Topologically Adaptable Snakes”, 5th International Conference on Computer Vision, pp.840–845 (1995).
[9] 坂口 嘉之, 美濃 導彦, 池田 克夫: “圧力エネルギーを持つ SNAKES”, 信学春季
全大, D-523 (1990).
[10] 坂口 俊文, 大山 公一: “面積項を持つスネーク”, 信学春季全大, D-555 (1991).
[11] 荒木 昭一, 横矢 直和, 岩佐 英彦, 竹村 治雄: “複数物体の抽出を目的とした交
差判定により分裂する動的輪郭モデル”, 信学論, Vol.J79-D-II, No.10, pp.1704–
1711 (1996).
101
[12] R. Ďurikovič, K. kaneda and H. Yamashita: “Dynamic contour a texture approach and contour operations”, The Visual Computer, Vol.11, No.6, pp.277–
289 (1995).
[13] R. Ronfard: “Region-Based Strategies for Active Contour Models”, International Journal of Computer Vision, Vol.13, No.2, pp.229–251 (1994).
[14] T. Gevers, S. Ghebreab and A.W.M. Smeulders: “Color Invariant Snakes”,
Proc. Ninth British Machine Vision Conf., P.H. Lewis and M.S. NLxon, eds.,
pp.659–670 (1998).
[15] C. Xu, J.L. Prince: “Gradient Vector Flow: A New External Force for Snakes”,
IEEE Proc. Conf. on Computer Vision and Pattern Recognition, pp.66–71
(1997)
[16] L.D. Cohen: “On Active Contour Models and Balloons”, CVGIP: Image Understanding, Vol.53, No.2, pp.211–218, March (1991).
[17] 栄藤 念, 白井 良明, 浅田 稔: “クラスタリングから得られる領域の記述に基
づく動的な領域抽出”, 信学論 (D-II), Vol.J75-D-II, No.7, pp.1111–1119, July
(1992).
[18] A. Amini, A. Tehrani and T.E. Weymouth: “Using dynamic programming for
minimizing the energy of active contours in the presence of hard constrains”,
Proc. of Int. Conf on Computer vision, pp.95-99 (1988)
[19] D.J. Williams, M. Shah: “A Fast Algorithm for Active Contours and Curvature
Estimation”, CVGIP: Image Understanding, Vol.55, No.1, pp.14–26, January
(1992).
[20] 和田 俊和, 野村 圭弘, 松山 隆司: “分散協調処理による画像の領域分割法”, 情
報処理学会論文誌, Vol.36, No.4, pp.879–891, April (1995).
[21] J. Rissanen: An introduction to the MDL Principle http://www.mdlresearch.org/jorma.rissanen/
[22] S. Zhu, A. Yuille: “Region competition: Unifying snakes, region growing, and
bayes/MDL for multiband inage segmentation”, IEEE Trans., PAMI, Vol.18,
No.9, pp.884–900 (1996).
102
[23] 松澤 悠樹, 阿部 亨: “複数の動的輪郭モデルの競合による領域抽出”, 信学論
(D-II), Vol.J83-D-II, No.4, pp.1100–1109, April (2000).
[24] 大津 展之: “判別および最小 2 乗基準に基づく自動しきい値決定法”, 信学論
(D-II), Vol.J63-D-II, No.4, pp.349–356, April (1980).
[25] 石田 亨, 桑原 和宏: 分散人工知能 (1): 協調問題解決, 人工知能学会誌, Vol.7,
No.6, pp.945–954 (1992).
[26] 菅原 研次: 人工知能, 森北出版株式会社 (1997).
[27] 西田 豊明, 木下 哲男, 北村 泰彦, 間瀬 健二, 共著: IT Text エージェント工学,
オーム社 (2002).
[28] 石田 亨, 他: 分散人工知能, コロナ社 (1996).
[29] S. Narazaki, H. Yamamura and N. Yoshida: “Strategies for Selecting Communication Structures in Cooperative Search”, Int’l J. of Cooperative Information
Systems, Vol.4, No.4, pp.405–422 (1995).
[30] 吉田 紀彦, 三谷 彰男: “分散協調による多体軌跡推定”, 情報処理学会論文誌,
Vol.38, No.2, pp.206–214 (1997).
[31] 吉田 紀彦: やわらかい情報処理 - 生物に学ぶ最適化法 -, サイエンス社 (2003).
[32] P. Ting, R. Iltis: “Multitarget Motion Analysis in a DSN”, IEEE Trans. Systems, Man and Cybernetics, Vol.21, No.5, pp.1125–1139 (1991).
[33] K. Knight: “Are Many Reactive Agents Better Than a Few Deliberative
Ones?”, Proc. 13th International Joint Conference on Artificial Intelligence,
pp.432–437 (1993).
[34] 松山 隆司: “分散協調処理による画像理解”, 計測と制御, Vol.31, No.11, pp.1149–
1154 (1992).
[35] 松山 隆司, 大田 友一 編: 小特集「並列・分散協調画像理解」, 人工知能学会誌,
Vol.9, No.5, pp.629–643 (1994).
[36] T. Matsuyama: “Cooperative Distributed Vision - Dynamic Integration of
Visual Perception, Action, and Communication -”, Proc. DARPA Image Understanding Workshop 98, pp.365–384 (1998).
103
[37] N. Ukita, T. Matsuyama: “Real-time multi-target tracking by cooperative
distributed active vision agents”, Proc. 1st International Joint Conference on
Autonomous Agents and Multi-Agent Systems (AAMAS) 2002, pp.829–828
(2002).
[38] 浮田 宗伯: “能動視覚エージェント群の密な情報交換による多数対象の実時間
協調追跡”, 信学論 (D-I), Vol.J88-D-I, No.9, pp.1438–1447 (2005).
[39] 加藤 丈和, 向川 康博, 尺長 建: “安定な顔認識のための分散協調登録”, 信学論
(D-II), Vol.J84-D-II, No.3, pp.500–508 (2001).
[40] 中澤 篤志, 日浦 慎作, 加藤 博一, 佐藤 康介, 井口 征二: “分散観測エージェン
トによる複数人物の追跡”, 画像の認識・理解シンポジウム (MIRU2000), 講演
論文集 I-15-20 (2000)
[41] 角 保志: “画像理解システムにおける機能分散的協調処理”, 人工知能学会誌,
Vol.9, No.5, pp.631–636 (1994).
[42] L. Erman, F. hayes-Rogh, V. Lesser, D. Reddy: “The hearsay-II speechunderstanding system: Integrating knowledge to resolve uncertainty”, ACM
Computing survey, Vol.12, No.2, pp.213–253 (1980).
[43] 松山 隆司, 長尾 真: “航空写真の構造解析”, 情報処理, Vol.21, No.5, pp.468–480
(1980).
[44] B. Draper, R.Collins, J. Brolio, A. Hanson, and E. Riseman: “Issues in the development of a blackboard-based schema system for image understanding”,
In R.Englemore and T.Morgan, editors, Blackboard Systems, pp.189–218,
Addison-wesley, London (1988).
[45] B. Draper, A. Hanson, E. Riseman: “Learning Blackboard Based Scheduling
Algorithms for Computer Vision”, International Journal of Pattern Recognition and Artificial Intelligence, Vol.7, No.2, pp.309–328 (1993).
[46] 中村 裕一, 長尾 真: “並列探索による画像特徴抽出 - PAFE における並列オブ
ジェクト探索 - ”, 人工知能学会誌, Vol.8, No.1, pp.65–78 (1993).
[47] 渡辺 正規, 大田 友一: “複数ステレオ対応探索アルゴリズムの協調的統合”, 信
学論 (D-II), Vol.J73-D-II, No.10, pp.1666–1676 (1990).
104
[48] 角 保志, 大田 友一: “多様な入力を許容する顔画像解析システムの一構成法”,
信学論 (D-II), Vol.J75-D-II, No.2, pp.236–245 (1992).
[49] Y. Ohta, M. Watanabe, Y. Sumi: “Approaches to Parallel Computer Vision”,
IEICE Trans., Vol.Vol.E74-D, No.2, pp.417–426 (1991).
[50] 松山 隆司, ビンセント ハング: “画像理解システム SIGMA - ボトムアップ,
トップダウン解析の統合 - ”, 情報処理学会論文誌, Vol.26, No.5, pp.877–889
(1985).
[51] 鎌田 清一郎: 画像処理 - 画像表現・圧縮・フラクタル -, サイエンス社 (2003).
[52] Y. Ohta, T. Kanade, T. Sakai: “Color information for region segmentation”,
Computer Graphics and Image Processing, Vol.13, pp.224–241 (1980).
[53] 三浦 弘之, 翠川 三郎: “建物 GIS データの更新を目的とした高分解能衛星画像
からの建物の自動検出手法” 地域安全学会論文集, No.5, pp.37–44 (2003).
[54] D.W. O’leary, J.D. Friendman, H.A. Pohn: “Lineament, linear, lineation:
Some proposed new standards for old terms”, Geological Society of America
Bulletin, Vol.87, No.10, pp.1463–1469 (1976).
[55] 景山 陽一, 西田 眞, 大井 貴文: “リモートセンシングデータを用いたリニアメン
ト抽出のための線分要素解析”, 電気学会論文誌 C, Vol.122-c, No.4, pp.639–647
(2002).
[56] P. Soille, M. Pesaresi: “Advances in Mathematical Morphology Applied to Geoscience and Remote Sensing”, IEEE Trans. on Geoscience and remote sensing,
Vol.40, No.9, pp.2042–2055 (2002).
[57] A. Baumgartner, S. Hinz: “Multi-scale road extraction using local and global
grouping criteria”, International Archives of Photogrammetry and Remote
Sensing, Vol.33, Part B3/1, Part 3, pp.58–65 (2000).
[58] P. Fua: “Model-based optimization: An approach to fast, accurate, and consistent Site Modeling from imagery”, RADIUS: Image Understanding for Intelligence Imagery, O. Firschein and I.M. Strat, Morgan Kaufmann, pp.903–908
(1997).
[59] H. Mayer, I. Laptev, A. Baumgartner, C. Steger: “Automatic road extraction
based on multi-scale modeling, context, and snakes”, International Archieves of
Photogrammetry and Remote Sensing, Vol.32, Part3–2W3, pp.106–113 (1997).
105
[60] 中川 雅史, 柴崎亮介: “TLS (Three Line Sensor) を用いた三次元建物データ構
築手法の開発”, CVIM(コンピュータビジョンとメディア) 研究会 (2004).
[61] 中川 雅史, 趙 卉菁, 柴崎 亮介: “デジタル地図を用いた建物抽出のためのモデ
ルフィッティング手法に関する研究”, 全国測量技術大会学生フォーラム (2006).
[62] L. Staib, J. Duncan: “Boundary finding with parametrically deformable models”, IEEE Trans. PAMI, Vol.14, No.11, pp.1061–1075 (1992).
[63] 梅山 伸二: “複素自己回帰モデルに基づく輪郭抽出手法”, 信学論 (D-II), Vol.J79D-II, No.3, pp.358–364 (1996).
[64] k. Lai, R. Chin: “Deformable contours: Modeling and extraction”, IEEE Trans.
PAMI, Vol.17, No.11, pp.1084–1090 (1995).
[65] Y. Wang, L. Staib: “Boundary finding with prior shape and smoothness models”, IEEE Trans. PAMI, Vol.22, No.7, pp.738–743 (2000).
[66] B. Olstad, A. Torp: “Encoding of a priori information in active contour models”, IEEE Trans. PAMI, Vol.18, No.9, pp.863–872 (1996).
[67] 松澤 悠樹, 阿部 亨, 熊沢 逸夫: “初期輪郭線から得られる形状情報を用いた動
的輪郭モデル”, 信学論 (D-II), Vol.J85-D-II, No.9, pp.1436–1445 (2002).
106