Yuri Y. Boykov Marie-Pierre Jolly 形状データ処理工学 ラスタデータ処理(2)に関係した 論文紹介 Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images ICCV 2001 Yuri Y. Boykov Marie-Pierre Jolly
やりたいこと 画像をオブジェクトと背景へ分割したい ユーザによる大まかな指定に基づく ユーザによる大まかな指定 オブジェクト (大脳部分)
核となるアイディア 画像をグラフとしてみて、最小カットを計算する オブジェクト 最小カット 背景
※ 辺に向きがある場合もあるが、この資料は向き無しで説明する グラフとは？ ノードとその隣接を表した抽象的な構造 ノード : 画素 辺 : 画素の隣接 (4 か 8 隣接が一般的) ノード 辺 画像の場合 ※ 辺に向きがある場合もあるが、この資料は向き無しで説明する
カットとは？ ソースノードとシンクノードを選び、 それらの間の流れを分断する辺の集まり 選び方は沢山ある S T 流れ カット 1 流れ ソースノードとシンクノードを選び、 それらの間の流れを分断する辺の集まり 選び方は沢山ある 流れ S カット 1 T 流れ カット 2
最小カットとは？ 辺にコストを考え、コストの和が最小になるカット コストを辺の強度と考えて、ソースとシンクを逆側 に引っ張ると、最も弱いところで分断される 最小カット=3+1+2+3+5=14 10 3 S 5 1 7 8 8 4 5 2 6 12 3 6 3 4 3 T 10 5
沢山流そうとしてもここの 流れがいっぱいになってしまう 最小カット・最大フローの定理 コストをノード間の流れの容量と考えると、 ソースからシンクへ流せる容量(最大フロー) は最小カットと同じになる 最小カット=3+1+2+3+5=14 沢山流そうとしてもここの 流れがいっぱいになってしまう 8/10 流れ 3/3 11 S 6 3/5 1/1 3/7 6/8 6/8 4/4 6 3 6 流れ/容量 5 2/2 0/5 3/6 6/12 0/6 3/3 0/3 1/4 ノードを 通過する 流れ 3/3 T 流れ 6 8 8/10 5/5
画像の場合:グラフのカット 各画素がノードになる ターミナル(=ソース・シンク)ノードは追加する カット 背景に 選ばれた画素 背景 オブジェクトに 選ばれた画素 オブジェクト カット
辺のコストの決め方の例 ターミナルノードへの辺 : 選ばれた画素の輝度値に近いほど大きい 隣接する画素間の辺 : 輝度の差が大きいほど小さい ターミナルノードへの辺 : 選ばれた画素の輝度値に近いほど大きい 隣接する画素間の辺 : 輝度の差が大きいほど小さい 輝度差があると コストは小 オブジェクトに選択された 画素は必ず オブジェクト側になる 背景の輝度値に 近いのでコスト大
グラフカットの目的関数 カットに属する辺に関する和 領域の輝度値に関する項 境界線に関する項 グラフカット 大 小
3次元画像への適用結果 CT・MRI (x,y,z)-データ 三次元の格子として隣接を考える 1スライス上で領域指定 結果の3次元表示
3次元画像への適用結果 動画 (x,y,時間)-データ 時間軸を z 軸とみなして隣接を定義する
繰り返し分割の結果 腎臓の3次元画像 1回目 : 黒と赤 2回目 : 赤と青 3回目 : 青と緑
グラフカットのまとめ 任意の離散データの分割の問題に対して、 隣接関係が定義できるなら適用可能 ライブラリは WEB 上に公開されている 任意の離散データの分割の問題に対して、 隣接関係が定義できるなら適用可能 ライブラリは WEB 上に公開されている http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software.html 計算に局所性がないため 大量のデータへの適用は自明でない (100万ノードにつき約1GBytes のメモリが必要)