Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization - todo314 @ ウィキ

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] $$
    • 1変数モジュラ＋2変数劣モジュラ
  • 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 \}) $$

提案手法

• 多様性の満たす条件
  1. node-wise: ピクセル毎独立（M変数関数ではある）
  2. permutation-invariant: M変数の順序に依らない
     • つまりM個のi座標の0の「個数」のみに依存する
  3. concave: 「個数についての関数」は差分が単調減少
• 結局 $$ \Delta^M(\{y\}) = \sum_{v}g_v(m_v^0) $$
  • $$m_v^0$$ := 0の個数
• 大体Δは劣モジュラ、とはいえ最小化は難しい
• 主定理: M個の（グラフカットで解ける）最小化問題を解いてくっつければOK
  • 速くなりそう
  • [Kirillov+ ICCV'15]はkV頂点のグラフの最小カット

実験

• [Kirillov+ ICCV'15]より速い（確信）

NIPS 劣モジュラ

2016/12/07