高階グラフカット

高階グラフカット
石川博
名古屋市立大学
大学院システム自然科学研究科
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
エネルギー最小化
1階（クリークが2画素まで）
データ
Y
X を探す
クリーク
滑らか
Y に近い
クリーク
E ( X )   g v ( X v )   huv ( X u , X v )
vV
( u ,v )
各画素
各画素
名古屋市立大学大学院システム自然科学研究科
隣接画素
v
に
Xv (= 0 or 1)を割り当てる
MIRU2009: 第12回画像の認識・理解シンポジウム
高階エネルギー
3階（クリークが4画素まで）
E ( X )   g v ( X v )   huv ( X u , X v )
vV
( u ,v )

クリーク
k
( u , v , s ,t )
uvst
クリーク
(Xu, Xv, Xs, Xt )
クリーク
一般階
E( X ) 
C f
C
C
( XC )
クリーク
名古屋市立大学大学院システム自然科学研究科
C
: クリークの集合
X C  ( X v )vC
MIRU2009: 第12回画像の認識・理解シンポジウム
高階エネルギーでより細かく分類
良い（低エネルギー）
悪い（高エネルギー）
より良い（低エネルギー）
より悪い（高エネルギー）
A
C
B
名古屋市立大学大学院システム自然科学研究科
D
MIRU2009: 第12回画像の認識・理解シンポジウム
１階エネルギーで区別できない例
良い（低エネルギー）
悪い（高エネルギー）
良い： 53
良い： 53
悪い： 14
悪い： 14
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
３階エネルギーを使うと区別できる
より良い（低エネルギー）
より悪い（高エネルギー）
A
C
B
D
A: 15
03
421
A: 160
43012
B: 12
B: 60
C: 10
C: 50
D: 0
D: 10
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
本研究の貢献
任意の高階2値マルコフ確率場
E ( X )  E ( X 1 , , X n ) 
を1階に変換
C f
C
C
(XC )
~
~
E ( X )  E ( X 1 ,, X n ,, X m)   g v ( X v )   huv ( X u , X v )
vV
( u ,v )
変数を追加
多値の場合には融合移動で対応可能
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
2値変数の関数
擬ブール関数 (PBF Pseudo-Boolean Function)
２値変数(0 or 1)の実数値関数
常に多項式として一意に書ける
1変数 x : E(x) = E0 (1x) + E1 x
2変数 x, y : E(x,y) =
E00 (1x) (1y) + E01 (1x) y + E10 x (1y) + E11 x y
3変数 x, y, z : E(x, y, z) =
E000 (1x) (1y) (1z) + E001 (1x) (1y) z +…+ E111 x y z
n階2値MRF = (n+1)次PBF
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
2階(3次)の場合
Kolmogorov & Zabih. PAMI2004
Freedman & Drineas. CVPR2005
3次 PBF を 2次に変換．次式を使う
xyz  max w( x  y  z  2 )
w
={0,1}
xyz
000
0  max w  ( 2 )  max{ 0,  2}  0
001
0  max w  (  1 )  max{ 0,  1}  0
011
0  max w  0  max{ 0,0}  0
w
w
w
111
1  max w  1  max{ 0, 1}  1
w
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
2階(3次)の場合
xyz  max w( x  y  z  2)
w
a < 0 なら
だから
a xyz  min a w( x  y  z  2)
w
min a xyz  min a w( x  y  z  2)
x , y , z
x , y , z , w
最小化問題の中（minの内側）では、
a xyz を
a w( x  y  z  2) に置き換えられる
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
さらに高階(高次)の場合
xyz  max w( x  y  z  2)
w
xyzt  max w( x  y  z  t  3)
w
xyztu  max w( x  y  z  t  u  4)
w
x1  xd  max wx1    xd  (d  1) 
w
min a x1  xd  min a wx1    xd  (d  1) 
ただし a < 0 ならば
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
さらに高階(高次)の場合
a > 0, d > 3 の場合、類似公式は知られていない
（殆どのエネルギーは変換できない）→ 本研究の貢献
そのような公式を想像してみる:
xyzt  min w( 1次式 )  ( 2次式 )
w
左辺は対称式
(２つの変数の値を入れ替えても変わらない)
従って右辺も対称式である必要がある
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
対称式
事実
任意の対称式は基本対称式についての
多項式として書くことができる
従って、もし f (x, y, z, t) が2次対称式ならば、
多項式 P(u,v) で次のように書ける：
f ( x, y, z, t )  P(s1 ,s2)
1次, 2次の  s1  x  y  z  t

基本対称式  s 2  xy  yz  zx  xt  yt  zt
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
4次の場合
xyzt  min w( 1次対称式 )  ( 2次対称式 )
w
xyzt  min w(Pa(ss11) b )Q( sc1s,1s
2 )d s2  e
w
P( s1 )  a s1  b
Q(s1 , s2 )  s12   s1   s2  
 s1  x  y  z  t

s2  xy  yz  zx  xt  yt  zt
s1  ( x  y  z  t ) 2  x 2  y 2  z 2  t 2  2s2
 s1  2s2 ( x 2  x, y 2  y, etc.)
2
Q(s1 , s2 )  c s1  d s2  e
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
4次の場合
xyzt  min w( 1次対称式 )  ( 2次対称式 )
w
xyzt  min w( a s1  b )  c s1  d s2  e
w
a, b, c, d, e を虱潰しに探索→
xyzt  min w(  2s1  3)  s2
w
 min w 2( x  y  z  t )  3
w
 xy  yz  zx  xt  yt  zt
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
5次の場合
同様に
xyztu  min v(2r1  3)  w(r1  3) r2
( v , w)
 r1  x  y  z  t  u

r2  xy  yz  zx  xt  yt  zt  xu  yu  zu  tu
順次高次の公式を見つけていくと…
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
一般次数の公式


d
x1  xd  min  wi ki ( S1  2i)  1   S 2
w1 ,, wnd
 i 1

nd
S1   xi ,
i 1
 d  1
nd  

2



d 1
d
ただし

d
S 2    xi x j
i 1 j i 1
が奇数でi  ndの場合
1 d k 
2 それ以外の場合
d
i
注意：一般の多項式に含まれる単項式の数は次数に
ついて指数的に増える
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
例
xyz  min w ( x  y  z )  1  xy  yz  zx
w
xyzt  min w 2( x  y  z  t )  3
w
 xy  yz  zx  xt  yt  zt
min xy  yz  2 xyz 3 xyzt  
x , y , z ,t
{
xy  yz  2v ( x  y  z)  1  2( xy  yz  zx)
x , y , z ,t ,v , w
min
 3w 2( x  y  z  t )  3  3xy  yz  zx  xt  yt  zt }
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
多値の場合: 融合移動
ラベルの集合を L  {l1 ,, l N }とする
配置 Y は各 v にラベル Yv L を与える
融合移動
Lempitsky et al. ICCV2007
繰り返し以下のように Y を更新:
1. 提案配置 P を生成する
2. Y とP を合成する
合成は2値問題を定義する：
「各 v についてYvをPvに変えるか変えないか」
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
多値の場合: 融合移動
0
1
0
1
Y
P
1
0
1
1
0
1
1
0
0
0
0
0
X
融合移動
繰り返し以下のように Y を更新:
1. 提案配置 P を生成する
2. Y とP を合成する
合成は2値問題を定義する：
「各 v についてYvをPvに変えるか変えないか」
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
多値の場合: 融合移動
0
01
10
1
Y
P
10
0
1
1
0
01
01
10
01
0
0
10
X
融合移動
繰り返し以下のように Y を更新:
1. 提案配置 P を生成する
2. Y とP を合成する
合成は2値問題を定義する：
「各 v についてYvをPvに変えるか変えないか」
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
融合移動とQPBO
QPBO (Roof duality)
Hammer et al. 1984, Boros et al. 1991, 2006
Kolmogorov & Rother PAMI2007, Rother et al. CVPR2007
劣モジュラなエネルギーは大域的に最小化
劣モジュラでなくても、各サイトに
0, 1, or unlabeled
を割り当てる
融合移動において、unlabeled となったサイト
は変えないようにすると、エネルギーは増えな
いことが保障される。
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
実験: FoEによる画像復元
FoE (Fields of Experts) Roth&Black CVPR2005
自然画像のための高階事前分布
E (Y ) 
C f
C
C
C
(YC )
: クリークの集合
YC  (Yv ) vC
 1
2
f C (YC )    i log 1  J i  YC  
 2

i 1
2
( N v  Yv )
f{v} (Y{v} ) 
2
2
K
C:
C:
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
実験: FoEによる画像復元
元画像
名古屋市立大学大学院システム自然科学研究科
ノイズ入り
1階
3階
MIRU2009: 第12回画像の認識・理解シンポジウム
実験: FoEによる画像復元
エネルギー (小さい方がよい)
PSNR (大きい方がよい)
45000
40000
35000
32
30000
25000
29
31
30
28
20000
27
15000
10000
5000
26
25
24
0
Lanら
 = 10
 = 20
Potetz
本研究
Lanら
Lanら ECCV2006
Potetz CVPR2008
本研究
名古屋市立大学大学院システム自然科学研究科
Potetz
本研究
～8時間
～30分
1分以内
MIRU2009: 第12回画像の認識・理解シンポジウム
まとめ
１階（普通のグラフカット）
Kolmogorov & Zabih
Freedman & Drineas
２階まで変換できるが最小化できない
QPBO
２階まで変換できて、最小化できる
本研究
任意階で変換できて、最小化できる
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム
御清聴ありがとうございました
ソフトウェア公開中
http://www.nsc.nagoya-cu.ac.jp/~hi/indexJ.html
名古屋市立大学大学院システム自然科学研究科
MIRU2009: 第12回画像の認識・理解シンポジウム

Download Report