「Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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 \}) $$
* 提案手法
- 多様性の満たす条件
++ node-wise: ピクセル毎独立(M変数関数ではある)
++ permutation-invariant: M変数の順序に依らない
--- つまりM個のi座標の0の「個数」のみに依存する
++ concave: 「個数についての関数」は差分が単調減少
- 結局 $$ \Delta^M(\{y\}) = \sum_{v}g_v(m_v^0) $$
-- $$m_v^0$$ := 0の個数
- 大体Δは劣モジュラ、とはいえ最小化は難しい
- 主定理: M個の(グラフカットで解ける)最小化問題を解いてくっつければOK
-- 速くなりそう
-- [Kirillov+ ICCV'15]はkV頂点のグラフの最小カット
* 実験
- [Kirillov+ ICCV'15]より速い(確信)
&tags()
2016/12/07