名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 高階グラフカット 石川　博 名古屋市立大学 大学院システム自然科学研究科 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム エネルギー最小化 1階（クリークが2画素まで） データ Y X を探す クリーク Y に近い 滑らか 各画素 v に Xv (= 0 or 1)を割り当てる 　各画素 隣接画素 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 高階エネルギー 3階（クリークが4画素まで） 3階（クリークが4画素まで） クリーク クリーク 一般階 C : クリークの集合 クリーク 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 高階エネルギーでより細かく分類 良い（低エネルギー） 悪い（高エネルギー） より良い（低エネルギー） より悪い（高エネルギー） A B C D 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム １階エネルギーで区別できない例 良い（低エネルギー） 悪い（高エネルギー） 良い： 53 良い： 53 悪い： 14 悪い： 14 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム ３階エネルギーを使うと区別できる より良い（低エネルギー） より悪い（高エネルギー） A B C D A: 15 4 1 2 3 A: 16 B: 12 3 4 1 2 B: 6 C: 1 C: 5 D: D: 1 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 本研究の貢献 任意の高階2値マルコフ確率場 を1階に変換 変数を追加 多値の場合には融合移動で対応可能 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 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回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 2階(3次)の場合 Kolmogorov & Zabih. PAMI2004 Freedman & Drineas. CVPR2005 3次 PBF を 2次 に変換．次式を使う B={0,1} x y z 0 0 0 0 0 1 0 1 1 1 1 1 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 2階(3次)の場合 a < 0 なら だから 最小化問題の中（minの内側）では、 を に置き換えられる 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム さらに高階(高次)の場合 ただし a < 0 ならば 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム さらに高階(高次)の場合 a > 0, d > 3 の場合、類似公式は知られていない （殆どのエネルギーは変換できない）→ 本研究の貢献 そのような公式を想像してみる: 左辺は対称式 (２つの変数の値を入れ替えても変わらない) 従って右辺も対称式である必要がある 1次式 2次式 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 対称式 事実 任意の対称式は基本対称式についての 多項式として書くことができる 従って、もし f (x, y, z, t) が2次対称式ならば、 多項式 P(u,v) で次のように書ける： 1次, 2次の 基本対称式 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 4次の場合 1次対称式 2次対称式 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 4次の場合 1次対称式 2次対称式 a, b, c, d, e を虱潰しに探索→ 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 5次の場合 同様に 順次高次の公式を見つけていくと… 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 一般次数の公式 ただし 注意：一般の多項式に含まれる単項式の数は次数に ついて指数的に増える が奇数で　　　の場合 それ以外の場合 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 例 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 多値の場合: 融合移動 ラベルの集合を　　　　　　 とする 配置 Y は各 v にラベル Yv L を与える 融合移動 繰り返し以下のように Y を更新: 1. 提案配置 P を生成する 2. Y とP を合成する 合成は2値問題を定義する： 「各 v についてYvをPvに変えるか変えないか」 Lempitsky et al. ICCV2007 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 多値の場合: 融合移動 融合移動 繰り返し以下のように Y を更新: 1. 提案配置 P を生成する 2. Y とP を合成する 合成は2値問題を定義する： 「各 v についてYvをPvに変えるか変えないか」 1 Y P X 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 多値の場合: 融合移動 融合移動 繰り返し以下のように Y を更新: 1. 提案配置 P を生成する 2. Y とP を合成する 合成は2値問題を定義する： 「各 v についてYvをPvに変えるか変えないか」 1 1 Y P X 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 融合移動とQPBO QPBO (Roof duality) 劣モジュラなエネルギーは大域的に最小化 劣モジュラでなくても、各サイトに 0, 1, or unlabeled を割り当てる 融合移動において、unlabeled となったサイト は変えないようにすると、エネルギーは増えな いことが保障される。 Hammer et al. 1984, Boros et al. 1991, 2006 Kolmogorov & Rother PAMI2007, Rother et al. CVPR2007 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 実験: FoEによる画像復元 FoE (Fields of Experts) Roth&Black　CVPR2005 自然画像のための高階事前分布 C : クリークの集合 C : C : 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 実験: FoEによる画像復元 元画像 ノイズ入り 1階 3階 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 実験: FoEによる画像復元 エネルギー (小さい方がよい) PSNR (大きい方がよい) 45000 32 40000 31 35000 30 30000 29 25000 28 20000 27 15000 26 10000 25 5000 24 Lanら Potetz 本研究 Lanら Potetz 本研究 Lanら ECCV2006 ～8時間 Potetz CVPR2008 ～30分 本研究 1分以内  = 10  = 20 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム まとめ １階（普通のグラフカット） Kolmogorov & Zabih Freedman & Drineas ２階まで変換できるが最小化できない 　 QPBO　　　　　　　　　　　　 ２階まで変換できて、最小化できる 本研究 任意階で変換できて、最小化できる 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム

名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム 御清聴ありがとうございました ソフトウェア公開中 http://www.nsc.nagoya-cu.ac.jp/~hi/indexJ.html 名古屋市立大学大学院システム自然科学研究科 MIRU2009: 第12回 画像の認識・理解シンポジウム