Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization
-
Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy
-
NIPS 2016
概要
-
Joint M-best-diverse labeling 問題をパラメトリック劣モジュラ最小化問題に帰着して解く
動機づけ・問題定式化
-
2値画像のノイズ除去・画像分割
-
エネルギー関数最小化として定式化
-
エネルギー関数: データ項= 「入力と出力の近さ」+平滑化項=「出力の滑らかさ」
-
例 $$ E(y) = \sum_{v \in V}b_v [x_v \neq y_v] + \sum_{(u,v) \in F}c_{u,v}[y_u \neq y_v] $$
-
2値の場合は最小カット
-
Q. どこまで効率的に解ける?
-
A. 「1変数関数の和」+「2変数劣モジュラ関数の和」
-
M-best labelings
-
そもそも最小化したのが良いか謎→良さ気なM個を提示→互いに似すぎ
-
2値画像の場合一ピクセルだ違うだけとか
-
M-best diverse labelings [Batra+ ECCV'12]
-
(エネルギー)-(∑現在の各解との遠さ)の最小のものを順次追加→多様性UP
-
ピクセル毎独立な遠さとしてHamming距離とか
-
Joint M-best diverse labelings [Kirillov+ ICCV'15]
-
M個の多様性(diversity)を同時に考慮
-
逐次的では無くまとめて欲しい
-
多様性: $$ \Delta^M(\{ y^1, \ldots, y^M \}) $$
提案手法
-
多様性の満たす条件
-
node-wise: ピクセル毎独立(M変数関数ではある)
-
permutation-invariant: M変数の順序に依らない
-
concave: 「個数についての関数」は差分が単調減少
-
結局 $$ \Delta^M(\{y\}) = \sum_{v}g_v(m_v^0) $$
-
大体Δは劣モジュラ、とはいえ最小化は難しい
-
主定理: M個の(グラフカットで解ける)最小化問題を解いてくっつければOK
-
速くなりそう
-
[Kirillov+ ICCV'15]はkV頂点のグラフの最小カット
実験
-
[Kirillov+ ICCV'15]より速い(確信)
NIPS 劣モジュラ
2016/12/07
最終更新:2016年12月08日 02:29