Normalized cuts and image segmentation.
論文100本ノック 1本目
Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 22(8), 888-905.
Ref: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=868688
Abstract
local features→global impressionを重視した手法,グラフ分割問題においてNormalized Cutというグループ間の非類似性、グループ内の類似性の両方を評価可能な尺度の提案。一般化固有値問題を用いてNomalized Cut を最適化する。画像、動画のフレーム間に適応した結果を提示する。
Summary
1925年 Wertheimer[24]らが部分認知と統合には 類似性・近接性・連続性が重要だと提唱。しかし認知グルーピングは計算的問題が多数発見された、この論文では画像領域分割に注目し解決するフレームワークを提案する。 1. 画像を部分集合として分けれたとして、果たしてどれが正しいのだろうか? Baysian は事前情報を適用することで適切な結果は得ることができるが、 事前情報(Low : blightness,color,texture Mid,High: Symmetric, Object model )をどのように解釈するかが難しい。 2. 部分領域は本質的に階層的な構成。単純な分割ではなく階層構造を意識して分割が必要になる。
dendgram : クラスタの階層構造を木構造により表現。 https://www.wikiwand.com/en/Dendrogram
1970年代、 マルコフランダム領域(MRF)[10]や多数のアプローチが提唱。 効果的に計算するためにどうするか？以前は近傍のものしか見ていない、または木構造の最小部分などに注目し計算量を抑えていた。 このアプローチではdendgram等を用いず、データのグラフからグラフ特性を解析して画像領域分割を行う。
Comments
この論文は実験比較が秀逸。
Spectral Clusteringを扱った論文は山のようにあるが、Spectral Clustering VS K-means などのようにバナナとシチューどっちが美味い?などのように実験デザインが不明瞭な論文が多い。しかしこの論文の実験比較はグラフ分割問題において固有値問題で最適化を行った手法を3つ挙げた上で類似手法の比較を行っていて、類似手法の中でもNCutがどのように優れているのかが分かった。(正確にはクラスタリングの比較ではなく、データの固有値空間への写像の比較)
特にNCutはグラフ構造の中でも正規化した尺度を提案する事により、グラフの切れ目とグラフの部分集合をバランスよく選択できるモデリングがなされているって事がわかって良い。 また画像からグラフを使ってマイニングする際にも、前処理(グラフの構築方法)も重要なことで、その点についての比較も行っている。
途中の式変形はどうやって思いついたのか是非聞いてみたい。
