コンピュータビジョン特論B － Graph Cuts － 永橋知行

Min-Cut/Max-Flow Algorithms はじめに エネルギー最小化問題 ラベリング問題 Image　Restoration Stereo Image Segmentation Multi-camera reconstruction Min-Cut/Max-Flow Algorithms エネルギー関数の最小とする解 → Graph Cuts Algorithm

ラベリング問題 ラベリング対象 Depth 物体（領域） etc.. エネルギー関数の定義

エネルギー最小化モデル Potts Interaction Energy Model Liner Interaction Energy Model

Min-Cut/Max-Flow Algorithmsとは ネットワーク流問題（最大流問題） 与えられたネットワークに対して，最大の流れを求める問題 Ford-Fulkerson's method Push-Relabel method

グラフの基礎 Flow：流れ Capacity：そのEdgeに流すことができるFlowの容量 Source：Flowが発生する場所 Sink：Flowが到着する場所 Network Edge Node Flow 1/1 Capacity Source 4/4 2/6 Sink 1/3 2/5 t S 0/2 1/3 2/2 2/2

s-t cut エッジを切断してsとtを分割 → s-t cut 1+3+2+2=8 1+5+3=9 1+3+2=6 6+2=8 1 4 6 3 5 t S 2 3 2 2 ・カットの容量が最小となるs-t cutを求める → 最小カット問題

最小カットと最大フロー 目的 最大フロー・最小カットの定理 最小のエネルギーとなるように分割したい → 最小カット問題 最大フロー・最小カットの定理 最大フローの値　=　最小カットの値 → 最大フロー問題と最小カット問題は同じ 　　 （最大フローが求まれば最小カットも求められる）

Ford-Fulkerson's method フローが最大のときの条件 残余ネットワーク上で s-t path が存在しない →　s-t　pathが存在すればフローは増加可能 Step1：全ての枝のフローを0で初期化 Step2：現在のフローに関する残余ネットワークを作成 Step3：残余ネットワークにs-t pathが存在場合は終了 Step4：残余ネットワークのs-t pathをひとつ求め、 それを用いて現在のフローを更新 Step5：Step2へ戻る

残余ネットワーク フローが流れているネットワークがあとどれだけのフローを流せるかを表したネットワーク 1/1 4/4 2/6 1/3 2/5 t ネットワーク S 0/2 1/3 2/2 2/2 1 4 4 2 2 2 3 2 S 1 t 残余ネットワーク 2 2 2 1

Ford-Fulkerson‘s methodの例 0/4 0/3 0/2 S t 0/3 0/2 4 3 ネットワーク 2 S t 3 2 残余ネットワーク

Ford-Fulkerson‘s methodの例 3/4 3/3 0/2 S t 0/3 0/2 1 ネットワーク 3 3 2 S t 3 2 残余ネットワーク

Ford-Fulkerson‘s methodの例 4/4 3/3 1/2 S t 0/3 1/2 ネットワーク 4 3 1 1 S t 1 3 1 残余ネットワーク

Ford-Fulkerson‘s methodの例 4/4 3/3 1/2 S t 1/3 2/2 ネットワーク 4 3 1 1 S t 1 2 2 残余ネットワークにs-t pathが存在しない → 最大フロー　5 残余ネットワーク

Graph Cuts Segmentation 係数 領域(Region)の関数 境界(Boundary)の関数 Object or Background ラベル Object or Backgroundでない確率 近傍との差　大：　B{p,q}=小 近傍との差　小：　B{p,q}=大

グラフの作成(n-link) n-links Edge Weight Condition n-link {p, q} B{p, q} {p, q}∈N t-link {p, s} λ ∙ Rp(“bkg”) p∈P, p∈OUB K p∈O p∈B t-link {p, t} λ ∙ Rp (“obj”)

グラフの作成(t-link) n-links t s Edge Weight Condition n-link {p, q} B{p, q} {p, q}∈N t-link {p, s} λ ∙ Rp(“bkg”) p∈P, p∈OUB K p∈O p∈B t-link {p, t} λ ∙ Rp (“obj”)

グラフの作成(t-link) n-links t s Edge Weight Condition n-link {p, q} B{p, q} {p, q}∈N t-link {p, s} λ ∙ Rp(“bkg”) p∈P, p∈OUB K p∈O p∈B t-link {p, t} λ ∙ Rp (“obj”)

グラフの分割 n-links t background cut s object Edge Weight Condition n-link {p, q} B{p, q} {p, q}∈N t-link {p, s} λ ∙ Rp(“bkg”) p∈P, p∈OUB K p∈O p∈B t-link {p, t} λ ∙ Rp (“obj”)

Graph Cuts Segmentation 結果（2D）

Graph Cuts Segmentation 結果（3D）

Graph Cuts Stereo ステレオ ピクセル間の対応付け → ラベリング問題

グラフの作成

Graph Cuts Stereo 結果

まとめ Graph Cuts Algorithm Min-Cut/Max-Flow Algorithms を用いて，エネルギー関数を 最小化 セグメンテーションやステレオなど幅広く利用

おしまい