Download presentation
Presentation is loading. Please wait.
1
コンピュータビジョン特論B － Graph Cuts － 永橋知行
2
Min-Cut/Max-Flow Algorithms
はじめに エネルギー最小化問題 ラベリング問題 Image Restoration Stereo Image Segmentation Multi-camera reconstruction Min-Cut/Max-Flow Algorithms エネルギー関数の最小とする解 → Graph Cuts Algorithm
3
ラベリング問題 ラベリング対象 Depth 物体（領域） etc.. エネルギー関数の定義
4
エネルギー最小化モデル Potts Interaction Energy Model
Liner Interaction Energy Model
5
Min-Cut/Max-Flow Algorithmsとは
ネットワーク流問題（最大流問題） 与えられたネットワークに対して，最大の流れを求める問題 Ford-Fulkerson's method Push-Relabel method
6
グラフの基礎 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
7
s-t cut エッジを切断してsとtを分割 → s-t cut
=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を求める → 最小カット問題
8
最小カットと最大フロー 目的 最大フロー・最小カットの定理
最小のエネルギーとなるように分割したい → 最小カット問題 最大フロー・最小カットの定理 最大フローの値 = 最小カットの値 → 最大フロー問題と最小カット問題は同じ （最大フローが求まれば最小カットも求められる）
9
Ford-Fulkerson's method
フローが最大のときの条件 残余ネットワーク上で s-t path が存在しない → s-t pathが存在すればフローは増加可能 Step1：全ての枝のフローを0で初期化 Step2：現在のフローに関する残余ネットワークを作成 Step3：残余ネットワークにs-t pathが存在場合は終了 Step4：残余ネットワークのs-t pathをひとつ求め、 それを用いて現在のフローを更新 Step5：Step2へ戻る
10
残余ネットワーク フローが流れているネットワークがあとどれだけのフローを流せるかを表したネットワーク 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
11
Ford-Fulkerson‘s methodの例
0/4 0/3 0/2 S t 0/3 0/2 4 3 ネットワーク 2 S t 3 2 残余ネットワーク
12
Ford-Fulkerson‘s methodの例
3/4 3/3 0/2 S t 0/3 0/2 1 ネットワーク 3 3 2 S t 3 2 残余ネットワーク
13
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 残余ネットワーク
14
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 残余ネットワーク
15
Graph Cuts Segmentation
係数 領域(Region)の関数 境界(Boundary)の関数 Object or Background ラベル Object or Backgroundでない確率 近傍との差 大： B{p,q}=小 近傍との差 小： B{p,q}=大
16
グラフの作成(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”)
17
グラフの作成(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”)
18
グラフの作成(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”)
19
グラフの分割 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”)
20
Graph Cuts Segmentation 結果（2D）
21
Graph Cuts Segmentation 結果（3D）
22
Graph Cuts Stereo ステレオ ピクセル間の対応付け → ラベリング問題
23
グラフの作成
24
Graph Cuts Stereo 結果
25
まとめ Graph Cuts Algorithm Min-Cut/Max-Flow Algorithms を用いて，エネルギー関数を 最小化
セグメンテーションやステレオなど幅広く利用
26
おしまい
Similar presentations
