⽯川 博
名古屋市⽴⼤学 ⼤学院システム⾃然科学研究科
グラフカットの理論と応⽤
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ
応⽤例の紹介・歴史
グラフカット
別名 s-t mincut
エネルギー最⼩化をする⽅法
トレードオフをエネルギーとして表現
応⽤分野
画像復元 ステレオ
セグメンテーション 動画像解析
テクスチャ合成
フォトモンタージュ
インタラクティブ・セグメンテーション
Rother et.al.
SIGGRAPH2004
インタラクティブ・セグメンテーション
Boykov&Jolly ICCV2001
インタラクティブ・セグメンテーション
Wang et.al. SIGGRAPH2005
テクスチャ合成
Kwatra et.al. SIGGRAPH2003
テクスチャ合成
Kwatra et.al. SIGGRAPH2003
インタラクティブ・フォトモンタージュ
Agarwala et.al. SIGGRAPH2004
ステレオ
Left Right Elevation map
歴史
エネルギー最⼩化には従来SAやICMなどの確率 的⼿法が使われてきた
ORではグラフカットは昔から使われていた 画像処理で80年代末に使われた
ビジョンでは90年代末になって使われはじめた
いくつかの理論的結果が再発⾒（新発⾒も）された
ここ数年グラフィクスでも盛んに使われている
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ
エネルギー最⼩化
例：2値の画像復元
ノイズ除去
与えられるのはノイズの⼊った画像 Y だけ
何を根拠にノイズと判断するか？
元画像はピクセル間であまり激しく変化しないと仮定 与えられた画像 Y に近い、あまり変化しない画像
トレードオフをエネルギーで表現 E( X )
Y X
Y に近い 隣接画素間で変化しない
例：2値の画像復元
Y X
Y に近い 隣接画素間で変化しない
∑
∑
∈ ∈− +
−
=
E v
u
v u
V v
v
v X X X
Y X
E
) , (
|
|
|
| )
(
λ κ
エネルギーを最⼩化する X を⾒つける
ピクセル全部 隣接する
ピクセルの組
各ピクセル v に Xv (= 0 or 1)
例：2値の画像復元
Y X
Y に近い 隣接画素間で変化しない
∑
∑
∈ ∈− +
−
=
E v
u
v u
V v
v
v X X X
Y X
E
) , (
|
|
|
| )
(
λ κ
エネルギーを最⼩化する X を⾒つける
ピクセル全部 隣接する
ピクセルの組
各ピクセル v に Xv (= 0 or 1)
YとX が同じなら0 異なれば λ
X Y
0 0 0 λ 0 0 0 0 λ 0 0 0
例：2値の画像復元
Y X
Y に近い 隣接画素間で変化しない
∑
∑
∈ ∈− +
−
=
E v
u
v u
V v
v
v X X X
Y X
E
) , (
|
|
|
| )
(
λ κ
エネルギーを最⼩化する X を⾒つける
ピクセル全部 隣接する
ピクセルの組
各ピクセル v に Xv (= 0 or 1)
隣同⼠で同じなら0
異なれば κ X
エネルギー最⼩化
⼀般に次の形のエネルギーを考える
ただし、V は場所（サイト）の集合
E は隣接するサイトの組の集合
X はV の各サイトにラベルを与える 1次のマルコフ確率場（MRF)
問題：E(X )を最⼩化するX を⾒つける
データ項 平滑化項
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
エネルギー最⼩化
問題：E(X )を最⼩化するX を⾒つける
可能な X は⾮常に多い
Vの各サイトにラベルをつけるつけ⽅
V：64×64 ラベル 0 or 1 なら 24096 (>101233)通り
⼀般にはNP困難
(指数時間かからない⽅法は⾒つかりそうにない）
従来の⽅法：モンテカルロ
特別な場合にグラフカットで⼤域最⼩化可能
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ 実装例
エネルギー設計のための５項⽬
ノイズ除去の場合 サイト⼀つの画像の画素
隣接関係画素の隣接関係
ラベル画素の⾊
データ項：データをどう反映させるか
与えられた画像の同じ画素の⾊との差を⼩さくする
平滑化項：X に望まれる性質
隣接した画素のラベルとの違いを⼩さくする
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
探す対象 X の空間：
各サイトへのラベルの割り当て⽅
α-β 交換 α 拡張
Boykov et. al. PAMI 2001
実装例（１） ステレオ
Simulated Annealing 視差（ディスパリティ）
サイト⼀つの画像の画素
隣接関係画素の隣接関係
ラベル視差（ディスパリティ）
データ項ディスパリティ分だけずれた画素同⼠を⽐べる
平滑化項隣接した画素間のラベルを滑らかにする 滑らかにしたいがジャンプも許したい
明るさが⼤きく変化するところでは を⼩さくする
実装例（１） ステレオ
∑
∑
∈ − + + ∈=
E v
u
v u
uv V
v
X v
v I X X
I X
E v
) , (
) ,
Potts(
|
| )
(
λ
⎩⎨
⎧ =
= 1
) (
) 0
,
Potts( l m
m
l (l ≠ m)
右画像 左画像
λuv
Boykov&Jolly ICCV2001
実装例（２） セグメンテーション
実装例（２） セグメンテーション
サイト画素
隣接関係画素の隣接関係
ラベル前景か背景 (0 or 1)
データ項そのピクセルの⾊から、前景らしいか背景らしいか
平滑化項隣接した画素間のラベルを滑らかにする
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
実装例（２） セグメンテーション
データ項：ユーザーが指定した前景・背景のサンプ ルからヒストグラムを作り、それから前景（背景）
らしさを評価
: 前景のヒストグラム : 背景
は に正規化
1 , 0
) ), ( ( log )
(l = − I v l l =
gv θ
) 0 ,
θ (c θ (c,1)
θ
∑
( ,0) =∑
( ,1) =1c c
c
c θ
θ
c θ
c
) θ
0 ,
θ (c θ (c,1)
平滑化項：Potts (⾊が違う程ペナルティは⼩さい)
⾊の変化が⼤きいところで切る
⎪⎪
⎩
⎪⎪⎨
⎧
≠ ′
= ′
′ = − −
) ) (
, dist(
) (
0 )
,
( { ( ) ( )}2
l v l
u e
l l
l l
huv κ I u I v λ
実装例（２） セグメンテーション
ラベルによらない
自動
ユーザー 操作
セグメンテーション
Rother et.al.
SIGGRAPH2004
自動
セグメンテーション
実装例（２） セグメンテーション
実装例（３） フォトモンタージュ
Agarwala et.al. SIGGRAPH2004
実装例（３） フォトモンタージュ
Agarwala et.al.
SIGGRAPH2004
実装例（３） フォトモンタージュ
サイト・隣接関係
画素・画素の隣接関係
ラベルどのソース写真から持ってくるか (1,2, ..., k)
データ項ソースが指定されている画素では指定されたラベル以外 に⼀定のペナルティ
その画素でソースが指定されていなければ 0 )
' (
) ' (
) 0
( l l
l l l M
gv
≠
=
⎩⎨
= ⎧
実装例（３） フォトモンタージュ
平滑化項
セグメンテーションとは逆に、境界が⾒えにくくしたい
⾊が近い程ペナルティは⼩さい
⾊以外のもの（例えば⾊の勾配）も合わせればよりよい
)) (
), ( dist(
)) (
), (
dist(
) ,
(l m I u I u I v I v
huv = l m + l m
実装例（４）テクスチャ合成
Kwatra et.al. SIGGRAPH2003
実装例（４）テクスチャ合成
（どこにパッチを持ってくるかは解決済みとする。）
実装例（５）デジタル・タペストリ
Rother et.al.
CVPR2005
実装例（５）デジタル・タペストリ
タペストリもソース画像もブロックに分割 サイト：タペストリ上のブロック
隣接：全サイト＆タペストリ上の隣接関係（後述）
ラベル：（ソース画像，ブロックのシフト）
ソース 1
ソース 2
シフト−2
(1,−2) (1,−2) (2,1)(1,−2) (1,−2) (2,1) (2,1)(2,1) (1,−2) (1,−2) (2,1) (2,1)
実装例（５）デジタル・タペストリ
データ項：ブロックの⽬⽴ち度 (実はコントラスト）
ソース画像の端より中⼼部の⽅を優遇
平滑化項同じソースブロックは⼀度しか使わない (全サイトが隣接）
隣接ブロックの整合性（タペストリ上の隣接関係）
(1,−2) (1,−2) (2,1) (2,1)
ソース 1
ソース 2
シフト−2
(1,−2) (1,−2) (2,1) (2,1) (1,−2) (1,−2) (2,1) (2,1)
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ
グラフとその切断
グラフとその切断
有向グラフ
G = (V, E )
V ：有限集合 E ⊂ V ×V
（頂点） （辺）
グラフの「重み」
c: E → R
u (u,v) v
u c(u,v) = 2 v
1 4
3
グラフとその切断
重みつき有向グラフG の２頂点 s, t を選ぶ
G のs, t についての切断とは、次のように頂点を ２グループ(S,T )に分けること
V = S ∪ T, S ∩ T = ∅ s∈S, t∈T
1 3
2 1
4
3 2
s t
グラフとその切断
重みつき有向グラフG の２頂点 s, t を選ぶ
G のs, t についての切断とは、次のように頂点を ２グループ(S,T )に分けること
V = S ∪ T, S ∩ T = ∅ s∈S, t∈T
1 3
2 1
4
3 2
s t
S T
グラフとその切断
重みつき有向グラフG の２頂点 s, t を選ぶ
G のs, t についての切断とは、次のように頂点を ２グループ(S,T )に分けること
V = S ∪ T, S ∩ T = ∅ s∈S, t∈T
S 側からT 側へ⾏く辺の重み
の総和を(S,T )のコストという
1 3
2 1
4
3 2
s t
S T
コスト: 10
グラフとその切断
重みつき有向グラフG の２頂点 s, t を選ぶ
G のs, t についての切断とは、次のように頂点を ２グループ(S,T )に分けること
V = S ∪ T, S ∩ T = ∅ s∈S, t∈T
S 側からT 側へ⾏く辺の重み
の総和を(S,T )のコストという
1 3
2 1
4
3 2
s t
S T
コスト: 4
G のs, t についての切断のうち、コストが最⼩の ものを最⼩切断という
最⼩切断は最⼤流と等しい
Ford & Fulkersonの定理 (1956) 辺の重みをパイプの太さと考えて
s から t へ流せる最⼤の⽔の流れ 最⼤流で飽和する辺が最⼩切断
グラフの最⼩切断
5 1
3
4 3 2
t
4
3 1
3 1 3
2 s
グラフの最⼩切断
G のs, t についての切断のうち、コストが最⼩の ものを最⼩切断という
最⼩切断は最⼤流と等しい
重みがすべて⾮負のとき、最⼤流は多項式時間で 求められる
切断の数は 2頂点の数 個ある
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ
グラフカットによるエネルギー最⼩化
2値の場合
|
| )
( )
(
) , (
v u
E v
u V
v
v
v X X X
g X
E =
∑
+∑
−∈
∈
κ
グラフでエネルギー最⼩化（2値）
重みつき
s t∑
∑
∈ ∈+
=
E v
u V
v
v
v X
g X
E
) , (
) (
) (
|
| )
( )
(
) , (
v u
E v
u V
v
v
v X X X
g X
E =
∑
+∑
−∈
∈
κ
グラフでエネルギー最⼩化（2値）
v
) 1
v ( g
) 0
v ( g
切断
s
X
v= 0
tX
v= 1
|
| )
( )
(
) , (
v u
E v
u V
v
v
v X X X
g X
E =
∑
+∑
−∈
∈
κ
グラフでエネルギー最⼩化（2値）
κ X
v= 0
X
v= 1
切断
s t
画像平⾯グラフ
２次元の場合
s t
３次元の場合
s t
グラフでエネルギー最⼩化（2値）
Xと切断に1対1対応
エネルギー = 切断のコスト
最⼩切断 → エネルギー最⼩化 重みが全て⾮負である必要
s t
s t
X 0 1 1 0 1 1 1 0 0 1 1 X 1 1 1 0 0 0 0 0 1 0 0
グラフでエネルギー最⼩化（2値）
辺の重みが全て⾮負である必要
は任意の関数でよい
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
( ) (x gv
2 )
0
( = −
gv
5 )
1
( = − gv
3
0 + 5
s t
s t
グラフでエネルギー最⼩化（2値）
辺の重みが全て⾮負である必要
は任意の関数でよい についての条件
劣モジュラ性 (submodularity）
) 0 , 1 ( )
1 , 0 ( )
1 , 1 ( )
0 , 0
( uv uv uv
uv h h h
h + ≤ +
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
( ) (x gv
) ,
(x y huv
グラフでエネルギー最⼩化（2値）
辺の重みが全て⾮負である必要
条件： huv (0,0) + huv (1,1) ≤ huv (0,1) + huv (1,0)
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
u v
) 1 , 1 ( )
0 , 0 (
) 0 , 1 ( )
1 , 0 (
uv uv
uv uv
h h
h h
−
−
+
) 1 , 1 ( )
0 , 1
( uv
uv h
h −
) 0 , 0 ( )
0 , 1
( uv
uv h
h −
u v
0 0 0 1
) 1 , 1 ( )
0 , 1
( uv
uv h
h −
) 1 , 1 ( )
0 , 0 (
) 0 , 1 ( )
1 , 0 (
uv uv
uv uv
h h
h h
−
−
+
1 0
) 1 , 1 (
) 0 , 0 ( )
0 , 1 ( 2
uv
uv uv
h
h h
−
−
1 1 huv(1,0) − huv(0,0)
s t
グラフでエネルギー最⼩化（2値）
辺の重みが全て⾮負である必要
条件：4通りの場合に同じ値を加えるhuv (0,0) + huv (1,1) ≤ huv (0,1) + huv (1,0)
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
s t
v
) 1 , 1 ( )
0 , 0 (
) 0 , 1 ( )
1 , 0 (
uv uv
uv uv
h h
h h
−
−
+ u v
0 0 0 1 1 0
1 1
) 1 , 1 ( )
0 , 1
( uv
uv h
h −
) 0 , 0 ( )
0 , 1
( uv
uv h
h −
) 1 , 0
uv( h
) 0 , 1
uv( h
) 1 , 1
uv( h
) 0 , 0
uv( h
u
グラフでエネルギー最⼩化（2値）
辺の重みが全て⾮負である必要
は任意の関数でよい についての条件
劣モジュラ性 (submodularity）
ORでは知られていた
) 0 , 1 ( )
1 , 0 ( )
1 , 1 ( )
0 , 0
( uv uv uv
uv h h h
h + ≤ +
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
( ) (x gv
) ,
(x y huv
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ
多値の場合（⼤域最⼩化できる場合）
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
グラフでエネルギー最⼩化（多値）
ラベルが3つ以上の場合
ラベルが１列に並んでいる場合：
⼤域最⼩化できる が の凸関数 実際には後述の近似最⼩化の⽅がよく使われる。
} ,
, ,
{l0 l1 lk
L = L
) ,
( i j
uv l l
⇔ h i − j
i
3 2 1 0
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
グラフでエネルギー最⼩化（多値）
s t
gv(l0)
gv(l1) gv(l2) gv(l3)
|
| )
,
(l l i j
huv i j =
κ
−i
3 2 1 0
∑
∑
∈ ∈+
=
E v
u
v u
uv V
v
v
v X h X X
g X
E
) , (
) ,
( )
( )
(
グラフでエネルギー最⼩化（多値）
s t
)
~( )
,
( u v u v
uv X X h X X
h = −
が凸であることが必要⼗分
⽬次
応⽤例の紹介・歴史 エネルギー最⼩化 実装例
グラフとその切断
グラフカットによるエネルギー最⼩化
2値の場合
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
まとめ
多値の場合（近似アルゴリズム）
グラフでエネルギー最⼩化（多値）
平滑化項が凸でなければならない
近似アルゴリズム
α -β 交換・ α 拡張
⼤域最⼩値の2c倍以内にできる
Pottsモデル(同じか違うかだけ)の場合 c =1
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
= ⎛
≠
≠
∈ min ( , )
) ,
( max
max,
v u
X uv X
v u
X uv X V v
u h X X
X X
h c
v u
v u
グラフでエネルギー最⼩化（近似多値）
繰り返しによる近似最⼩化
サイトごとに、次の操作をするかどうかを ２値のグラフカットで決める
α -β 交換
現在値がα,β∈Lのどちらかのところのみ交換を許す 全てのα,β∈Lについて次を満たすとき可能
α 拡張
α に変えることのみを許す
全てのα, β, γ ∈Lについて次を満たすとき可能
) ,
( )
, ( )
, ( )
,
(α α uv β β uv α β uv β α
uv h h h
h + ≤ +
) ,
( )
, ( )
, ( )
,
(α α uv β γ uv α γ uv β α
uv h h h
h + ≤ +
α 拡張
初期解
-拡張 -拡張 -拡張 -拡張 -拡張 -拡張 -拡張
繰り返し毎にラベル“α ”が他のラベルから場所を奪う
毎回エネルギーを最も小さくする拡張を選ぶ： 2値最小化
現在値
α
α 拡張
α 拡張アルゴリズム
1. 任意の初期解から始める
2. 任意の順でラベル “α ” を選び、
1. 最善のα 拡張を見つける (2値グラフカット)
2. エネルギーの減るα 拡張がなければ拡張しない 3. エネルギーの減る拡張がなくなるまで続ける
α 拡張 vs. 標準的離散エネルギー最⼩化法
α 拡張操作
多数のピクセルが同時にラベルを変 えることができる
最適な変化を見つけるのにグラフカッ トを使う
“1ピクセル” 操作
(Simulated Annealing, ICM,…)
一度に一つのピクセルだけが値を変 えることができる
最適な変化を見つけるのは簡単
元画像
α 拡張による
局所最小解
“1ピクセル” 操作 による局所最小解 ノイズ画像
Pottsエネルギー最小化
α 拡張 vs. 標準的離散エネルギー最⼩化法
まとめ
グラフカット：エネルギー最⼩化法
2値の場合（劣モジュラ性が⼤域最⼩化と必要⼗分）
多値の場合（⼤域最⼩化できる場合）
多値の場合（近似アルゴリズム）
エネルギーの形によっては⼤域最⼩化できる より⼀般の場合に使える近似アルゴリズムも 例えばSAより有⽤な場合が多い
どちらの場合もあまり細かいパラメータの 調整をしなくてもよい解が得られる
