セグメンテーションに基づくオブジェクト分類

任意の特徴空間内の点の集合は、重み付き無向完全グラフ G = (V, E) として表現できます。ここで、グラフのノードは特徴空間内の点です。重みは${\displaystyle w_{ij}}$端の${\displaystyle (i,j)\in E}$ノード間の類似性の関数である${\displaystyle i}$そして${\displaystyle j}$この文脈では、画像分割問題を、分割を求めるグラフ分割問題として定式化できます。${\displaystyle V_{1},\cdots ,V_{k}}$頂点集合の${\displaystyle V}$、ある尺度によれば、任意の集合の頂点は${\displaystyle V_{i}}$高い類似性があり、2つの異なるセットの頂点${\displaystyle V_{i},V_{j}}$類似性が低い。

G = ( V , E , w ) を重み付きグラフとする。${\displaystyle A}$そして${\displaystyle B}$2つの頂点部分集合とする。

させて：

${\displaystyle w(A,B)=\sum \limits _{i\in A,j\in B}w_{ij}}$

${\displaystyle \operatorname {ncut} (A,B)={\frac {w(A,B)}{w(A,V)}}+{\frac {w(A,B)}{w(B,V)}}}$

${\displaystyle \operatorname {nassoc} (A,B)={\frac {w(A,A)}{w(A,V)}}+{\frac {w(B,B)}{w(B,V)}}}$

正規化カットアプローチでは、^{[ 2 ]}任意のカットに対して${\displaystyle (S,{\overline {S}})}$で${\displaystyle G}$、${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$異なる部分間の類似性を測定し、${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$同じ部分内の頂点の全体的な類似性を測定します。

以来${\displaystyle \operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})}$カット${\displaystyle (S^{*},{\overline {S}}^{*})}$最小限に抑える${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$また最大限に活用する${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$。

カットを計算する${\displaystyle (S^{*},{\overline {S}}^{*})}$最小限に抑える${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$これはNP困難問題である。しかし、多項式時間でカットを見つけることができる。${\displaystyle (S,{\overline {S}})}$正規化された小さな重量${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$スペクトル技術を用いて。

させて：

$\displaystyle d(i)=\sum \limits _{j}w_{ij}}$

また、Dを${\displaystyle n\times n}$対角行列${\displaystyle d}$対角線上に、そして${\displaystyle W}$になる${\displaystyle n\times n}$対称行列${\displaystyle w_{ij}=w_{ji}}$。

いくつかの代数的な操作の後、次の式が得られます。

${\displaystyle \min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(DW)y}{y^{T}Dy}}}$

以下の制約条件に従う：

• $\displaystyle y_{i}\in \{1,-b\}}$ある定数に対して${\displaystyle -b}$
• $\displaystyle y^{t}D1=0}$

最小化${\displaystyle {\frac {y^{T}(DW)y}{y^{T}Dy}}}$上記の制約の下ではNP困難である。問題を扱いやすくするために、以下の制約を緩和する。${\displaystyle y}$そして、実数値をとることを許容する。緩和された問題は、一般化固有値問題を解くことによって解決できる。${\displaystyle (D-W)y=\lambda Dy}$2番目に小さい一般化固有値の場合。

分割アルゴリズム：

1. 与えられた特徴量に基づいて、重み付きグラフを作成する。${\displaystyle G=(V,E)}$各エッジの重みを計算し、情報を要約します。${\displaystyle D}$そして${\displaystyle W}$。
2. 解決する${\displaystyle (D-W)y=\lambda Dy}$2番目に小さい固有値を持つ固有ベクトルについて。
3. 2番目に小さい固有値を持つ固有ベクトルを使用して、グラフを二分割します（例えば、符号に基づいてグループ化します）。
4. 現在のパーティションをさらに分割するかどうかを決定します。
5. 必要に応じて、分割された部分を再帰的に分割します。

すべての固有ベクトルに対する標準的な固有値問題を解くには（例えばQRアルゴリズムを使用して）、${\displaystyle O(n^{3})}$時間。これは、次のような画像セグメンテーション アプリケーションには非現実的です。${\displaystyle n}$は画像内のピクセル数です。

非カットアルゴリズムでは、2番目に小さい一般化固有値に対応する固有ベクトルのみが使用されるため、対応する固有値問題の解を行列フリー方式、つまり、ランチョスアルゴリズムのように行列Wを明示的に操作したり計算したりすることなく実行すれば、効率を劇的に向上させることができます。行列フリー方式では、各反復で与えられたベクトルに対して行列とベクトルの積を実行する関数のみが必要です。画像セグメンテーションの場合、行列Wは通常疎行列であり、非ゼロ要素が多数存在します。${\displaystyle O(n)}$なので、このような行列ベクトル積は${\displaystyle O(n)}$時間。

高解像度画像の場合、第2固有値はしばしば条件が悪く、ランチョス法などの反復固有値ソルバーの収束が遅くなります。前処理は、例えば行列フリーLOBPCG法において、収束を加速する重要な技術です。最適に前処理された行列フリー法を使用して固有ベクトルを計算するには、${\displaystyle O(n)}$最適な複雑さである時間、固有ベクトルは${\displaystyle n}$コンポーネント。

scikit-learn ^{[ 3 ]}は、 SciPyのLOBPCG を代数的マルチグリッド前処理とともに使用し、グラフ ラプラシアンの固有値問題を解いて、スペクトルグラフ分割による画像セグメンテーションを実行します。これは^{[ 4 ]}で最初に提案され、 ^{[ 5 ]および[ 6 ]}で実際にテストされました。

1. 画像Dが与えられた場合、例えば牛や馬といった物体のカテゴリが選択される。
2. 対応するLPSモデルをDに合わせ、サンプルを取得する。${\displaystyle \Theta _{1},\cdots ,\Theta _{s}}$
3. 式(2)で与えられる目的関数は、計算によって決定される。${\displaystyle E(m,\Theta _{i})}$そして使用する${\displaystyle w_{i}=g(\Theta _{i}|Z)}$
4. 目的関数は単一のMINCUT操作を使用して最小化され、セグメンテーションmを取得します。