Yuri Y. Boykov Marie-Pierre Jolly

Presentation on theme: "Yuri Y. Boykov Marie-Pierre Jolly"— Presentation transcript:

1 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

2 やりたいこと 画像をオブジェクトと背景へ分割したい ユーザによる大まかな指定に基づく ユーザによる大まかな指定 オブジェクト (大脳部分)

3 核となるアイディア 画像をグラフとしてみて、最小カットを計算する オブジェクト 最小カット 背景

4 ※ 辺に向きがある場合もあるが、この資料は向き無しで説明する
グラフとは？ ノードとその隣接を表した抽象的な構造 ノード : 画素 辺 : 画素の隣接 (4 か 8 隣接が一般的) ノード 辺 画像の場合 ※ 辺に向きがある場合もあるが、この資料は向き無しで説明する

5 カットとは？ ソースノードとシンクノードを選び、 それらの間の流れを分断する辺の集まり 選び方は沢山ある S T 流れ カット 1 流れ
ソースノードとシンクノードを選び、 　 それらの間の流れを分断する辺の集まり 選び方は沢山ある 流れ S カット 1 T 流れ カット 2

6 最小カットとは？ 辺にコストを考え、コストの和が最小になるカット
コストを辺の強度と考えて、ソースとシンクを逆側 　　　　　に引っ張ると、最も弱いところで分断される 最小カット= =14 10 3 S 5 1 7 8 8 4 5 2 6 12 3 6 3 4 3 T 10 5

7 沢山流そうとしてもここの 流れがいっぱいになってしまう
最小カット・最大フローの定理 コストをノード間の流れの容量と考えると、 ソースからシンクへ流せる容量(最大フロー) は最小カットと同じになる 最小カット= =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

8 画像の場合:グラフのカット 各画素がノードになる ターミナル(=ソース・シンク)ノードは追加する カット 背景に 選ばれた画素 背景
オブジェクトに 選ばれた画素 オブジェクト カット

9 辺のコストの決め方の例 ターミナルノードへの辺 : 選ばれた画素の輝度値に近いほど大きい 隣接する画素間の辺 : 輝度の差が大きいほど小さい
ターミナルノードへの辺 : 選ばれた画素の輝度値に近いほど大きい 隣接する画素間の辺 : 輝度の差が大きいほど小さい 輝度差があると コストは小 オブジェクトに選択された 画素は必ず オブジェクト側になる 背景の輝度値に 近いのでコスト大

10 グラフカットの目的関数 カットに属する辺に関する和 領域の輝度値に関する項 境界線に関する項 グラフカット 大 小

11 3次元画像への適用結果 CT・MRI (x,y,z)-データ 三次元の格子として隣接を考える 1スライス上で領域指定 結果の3次元表示

12 3次元画像への適用結果 動画 (x,y,時間)-データ 時間軸を z 軸とみなして隣接を定義する

13 繰り返し分割の結果 腎臓の3次元画像 1回目 : 黒と赤 2回目 : 赤と青 3回目 : 青と緑

14 グラフカットのまとめ 任意の離散データの分割の問題に対して、 隣接関係が定義できるなら適用可能 ライブラリは WEB 上に公開されている
任意の離散データの分割の問題に対して、 　 隣接関係が定義できるなら適用可能 ライブラリは WEB 上に公開されている 計算に局所性がないため 大量のデータへの適用は自明でない (100万ノードにつき約1GBytes のメモリが必要)