Normalized Cuts and Image Segmentation (2000)

August 6, 2022

単純無向グラフのクラスタリングを応用して画像をセグメントに分割する。 カットの評価基準としてnormalized cutとその近似解を求め方を提案した。 Normalized cutが最小値のとき、異なるサブグラフにあるノード間の類似度は最小に、同じサブグラフにあるノードの類似度は最大になる。 Normalized cutをレイリー商に変形し、固有値問題をとくことで、Normalized cutの最小値の近似解を求める。

アルゴリズムは、グラフのすべてのノードを2つの素集合\(A, B\)に再帰的に分け、画像をセグメンテーションに分ける。 \(w(u, v)\)をノード\(u, v\)間の重みとして、カットを $$ \textit{cut}(A, B) = \sum_{u\in A, v \in B}w(u, v) $$ と表す。 一方のノードが\(A\)に属する辺の重みの総和を $$ \textit{assoc}(A, V) = \sum_{u\in A, t\in V}w(u, t) $$ とおくとnormalized cut(Ncut)を $$ \begin{align} \textit{Ncut}(A, B) &= \frac{\textit{cut}(A, B)}{\textit{assoc}(A, V)} + \frac{\textit{cut}(A, B)}{\textit{assoc}(B, V)}\\ &=2-\frac{\textit{assoc}(A, A)}{\textit{assoc}(A, V)} - \frac{\textit{assoc}(B, B)}{\textit{assoc}(B, V)} \end{align} $$ とかける。 上の式から、Ncutが最小のとき\(A\), \(B\)内の類似度が最大かつ\(A\), \(B\)間の類似度が最小になる。 Ncutの最小値を求める問題はNP完全であるため、近似解を探す。

ノード\(i\)が\(A\)にあれば\(x_i=1\), \(B\)にあれば\(x_i=-1\)となる長さ\(N=|V|\)のベクトルを\(\boldsymbol{x}\), \(i\)の他のノードへの重みの総和を\(\boldsymbol{d}(i)=\sum_jw(i,j)\)とする。 \(\boldsymbol{d}\)を対角成分とする\(N\times N\)の対角行列\(\mathcal{\rm D}\), \(\mathrm{W}(i, j)=w_{ij}\)を成分とする\(N\times N\)の対称行列\(\mathrm{W}\), すべての成分が1の\(N\times 1\)ベクトルを\(\boldsymbol{1}\), \(b=\frac{\sum_{x_i>0}d_i}{\sum_{x_i<0}d_i}\), \(\boldsymbol{y}=(\boldsymbol{1}+\boldsymbol{x})-b(\boldsymbol{1}-\boldsymbol{x})\)とすると、\(y(i)\in \{1,-b\}かつy^\top\mathrm{\boldsymbol{D1}}=0\)のもとで、 $$ \min_{\boldsymbol{x}}\mathit{Ncut}(\boldsymbol{x})=\min_{\boldsymbol{y}}\frac{\boldsymbol{y}^\top(\mathrm{\boldsymbol{D}}-\mathrm{\boldsymbol{W}})\boldsymbol{\mathcal{y}}}{\boldsymbol{\mathcal{y}}^\top\boldsymbol{\mathrm{D}}\boldsymbol{y}} $$ がなりたつ。

レイリー商\(R(\boldsymbol{x})\)の最小値は最小固有値であり、そのときの\(\boldsymbol{x}\)は、その固有ベクトルになる。 そのため、\(\boldsymbol{y}\)を実数の範囲に限定すると、上の問題は $$ (\boldsymbol{\mathrm D}-\boldsymbol{\rm W})y=\lambda \boldsymbol{\rm D}y $$ の固有値問題としてあつかえる。

しかし、\(\boldsymbol{y}\)にはとりえる範囲の制約があるので、固有ベクトルが制約を満たすかどうかを調べる必要がある。 固有値の方程式を\(z=\mathrm{\boldsymbol{D}}^{\frac{1}{2}}\mathcal{\boldsymbol{y}}\)として $$ \mathrm{\boldsymbol{D}}^{-\frac{1}{2}}(\boldsymbol{\mathrm{D}-\boldsymbol{\mathrm{W}}})\boldsymbol{\mathrm{D}}^{-\frac{1}{2}}z=\lambda z $$ と書き直すと、\(z_0=\boldsymbol{\mathrm{D}^{\frac{1}{2}}}\boldsymbol{1}\)は固有値0の固有ベクトルになる。 ラプラシアン行列は半正定値行列であるため、\(\mathrm{\boldsymbol{D}}^{-\frac{1}{2}}(\boldsymbol{\mathrm{D}-\boldsymbol{\mathrm{W}}})\boldsymbol{\mathrm{D}}^{-\frac{1}{2}}\)は対称な半正定値行列であり、固有値行列の固有値は非負になる。 そのため、\(z_0\)は最小の固有ベクトルであり、すべての固有ベクトルは互いに直交する。 \(\boldsymbol{y}_0=\boldsymbol{1}\)が最小の固有値0の固有ベクトルでありうため、\(\boldsymbol{y}_1\)を二番目に小さい固有値に対応する固有ベクトルとすると\(0=\boldsymbol{y}_1^\top\boldsymbol{\mathrm{D}1}\)がなりたつ。 \(\boldsymbol{x}\)が\(j-1\)番目までの小さい固有値に対応する固有ベクトルと直交する場合、レイリー商は\(\boldsymbol{x}_j\)のときにその固有値\(\lambda_j\)を最小値にとる。 したがって、 $$ z_1 = \underset{z^\top z_0=0}{\operatorname{argmin}}\frac{\boldsymbol{z}^\top\mathrm{\boldsymbol{D}}^{-\frac{1}{2}}(\boldsymbol{\mathrm{D}}-\boldsymbol{\mathrm{W}})\boldsymbol{\mathrm{D}}^{-\frac{1}{2}}\boldsymbol{z}}{\boldsymbol{z}^\top \boldsymbol{z}} $$ より $$ y_1 = \underset{\boldsymbol{y}^\top\boldsymbol{\mathrm{D1}}=0}{\operatorname{argmin}}\frac{\boldsymbol{y}^\top(\boldsymbol{\mathrm{D}}-\boldsymbol{\mathrm{W}})\boldsymbol{y}}{\boldsymbol{y}^\top\mathrm{\boldsymbol{D}}\boldsymbol{y}} $$ となる。

論文へのリンク