コンピュータビジョンにおけるグラフカット

コンピュータビジョンの分野では、グラフカット最適化は、画像の平滑化、ステレオ対応問題、画像のセグメンテーション、オブジェクトのコセグメンテーション、エネルギー最小化の観点から定式化できる他の多くのコンピュータビジョンの問題など、さまざまな低レベルのコンピュータビジョンの問題（初期ビジョン^[1]）を効率的に解決するために使用できます。

これらのエネルギー最小化問題の多くは、グラフ内の最大フロー問題を解くことによって近似することができます^[2]（したがって、最大フロー最小カット定理によって、グラフの 最小カットを定義します）。

コンピューター ビジョンにおけるこのような問題のほとんどの定式化では、最小エネルギー解は、解の 最大事後推定値に対応します。

多くのコンピューター ビジョン アルゴリズムにはグラフのカット (正規化カットなど) が含まれますが、「グラフ カット」という用語は、最大フロー/最小カット最適化を採用するモデルに特に適用されます (他のグラフ カット アルゴリズムは、グラフ分割アルゴリズムと見なされる場合があります)。

「バイナリ」問題 (バイナリ画像のノイズ除去など) は、このアプローチを使用して正確に解決できます。ピクセルに 2 つ以上の異なるラベルを付けることのできる問題 (ステレオ対応やグレースケール画像のノイズ除去など) は正確には解決できませんが、生成されるソリューションは通常、グローバル最適値に近くなります。

グラフカットの基礎理論は、ダーラム大学のグレイグ、ポーテウス、セヘルト^[3]による独創的な論文で初めてコンピュータービジョンに応用されました。アラン・セヘルトとブルース・ポーテウスは、ジュリアン・ベサグとピーター・グリーンが率いる当時ダーラムで高く評価されていた統計グループのメンバーであり、最適化の専門家であるマーガレット・グレイグはダーラム数理科学部初の女性スタッフとして有名でした。

ノイズの多い（または破損した）画像を平滑化するベイズ統計の文脈において、彼らは、ソースとシンクの導入を伴う、関連する画像ネットワークを通るフローを最大化することによって、バイナリ画像の最大事後推定値を正確に得ることができる方法を示しました。したがって、問題は効率的に解決可能であることが示されました。この結果が出る前は、シミュレーテッドアニーリング（ Geman兄弟によって提案された）^[4]や反復条件モード（ Julian Besagによって提案された貪欲アルゴリズムの一種）^[5]などの近似手法が、このような画像平滑化問題を解決するために使用されていました。

一般的な-color 問題はGreig、Porteous、Seheult のアプローチ^[3]では NP 困難ですが、一般的なコンピューター ビジョンの問題に広く適用できることがわかっています^{[6] [7]}。一般的な問題では、Greig、Porteous、Seheult のアプローチは関連するバイナリ問題のシーケンスに反復的に適用されることが多く、通常はほぼ最適なソリューションが得られます。 ${\displaystyle k}$${\displaystyle k>2,}$

2011 年に、C. Couprieら^{[8] は}、「Power Watershed」と呼ばれる一般的な画像セグメンテーション フレームワークを提案しました。これは、0 または 1 に設定されたユーザー シード (または単項) によって制約され、グラフ上での [0,1] からの実数値インジケータ関数を最小化するもので、グラフ上のインジケータ関数の最小化は指数 に関して最適化されます。 のとき、Power Watershed はグラフ カットによって最適化され、Power Watershed が最短経路によって最適化されるとき、はランダム ウォーカー アルゴリズムによって最適化され、 はウォーターシェッドアルゴリズムによって最適化されます。このように、Power Watershed は、他のエネルギー最適化セグメンテーション/クラスタリング アルゴリズムと直接接続できるグラフ カットの一般化と見なすことができます。 ${\displaystyle p}$${\displaystyle p=1}$${\displaystyle p=0}$${\displaystyle p=2}$${\displaystyle p=\infty}$

• 画像：${\displaystyle x\in \{R,G,B\}^{N}}$
• 出力: セグメンテーション（不透明度とも呼ばれる）（ソフトセグメンテーション）。ハードセグメンテーションの場合${\displaystyle S\in R^{N}}$${\displaystyle S\in \{0{\text{ 背景の場合}},1{\text{ 検出する前景/オブジェクトの場合}}\}^{N}}$
• エネルギー関数:ここで、C は色パラメータ、λ はコヒーレンスパラメータです。${\displaystyle E(x,S,C,\lambda )}$
• ${\displaystyle E(x,S,C,\lambda )=E_{\rm {色}}+E_{\rm {コヒーレンス}}}$
• 最適化: セグメンテーションは S 上のグローバル最小値として推定できます。${\displaystyle {\arg \min }_{S}E(x,S,C,\lambda )}$

• 標準グラフカット: セグメンテーション全体のエネルギー関数を最適化します (S 値は不明)。
• 反復グラフカット:

1. 最初のステップでは、K-means を使用してカラー パラメータを最適化します。
2. 2 番目のステップでは、通常のグラフ カット アルゴリズムを実行します。

これら 2 つのステップは収束するまで再帰的に繰り返されます。

• 動的グラフ カット:
  問題を変更した後 (たとえば、ユーザーが新しいシードを追加した後)、アルゴリズムをより高速に再実行できます。

${\displaystyle \Pr(x\mid S)=K^{-E}}$

ここでエネルギーは2つの異なるモデル（および）で構成されています。 ${\displaystyle E}$${\displaystyle E_{\rm {色}}}$${\displaystyle E_{\rm {コヒーレンス}}}$

${\displaystyle E_{\rm {色}}}$— 各色の可能性を表す単項項。

• この用語は、以下で説明するさまざまなローカル (例: テクソン) またはグローバル (例: ヒストグラム、GMM、Adaboost 尤度) アプローチを使用してモデル化できます。

• シードとしてマークされたピクセルの強度を使用して、オブジェクト (前景) と背景の強度分布のヒストグラム (P(I|O) と P(I|B)) を取得します。
• 次に、これらのヒストグラムを使用して、地域ペナルティを負の対数尤度として設定します。

• 通常、背景モデリング用と前景ピクセル用の 2 つの分布を使用します。
• これら 2 つの分布をモデル化するには、ガウス混合モデル (5 ～ 8 個のコンポーネント) を使用します。
• 目標: これら 2 つの分布を分離してみます。

• テクソン (またはテキストン) は、特定の特性を持ち、画像内で繰り返されるピクセルのセットです。
• 手順:

1. テクスチャ要素に適した自然なスケールを決定します。
2. 強度またはガボール フィルター応答のいずれかに基づいて、モデル内部テクソンの非パラメトリック統計を計算します。

• 例:
  • 変形可能モデルに基づくテクスチャ付きオブジェクトのセグメンテーション
  • 画像セグメンテーションのための輪郭とテクスチャの分析

${\displaystyle E_{\rm {コヒーレンス}}}$— 近隣ピクセル間の一貫性を表すバイナリ用語。

• 実際には、ピクセルは、水平、垂直、または対角線（2D 画像の場合は 4 方向の接続または 8 方向の接続）に隣接している場合に隣接ピクセルとして定義されます。
• コストは、ローカル強度勾配、ラプラシアンゼロ交差、勾配方向、色混合モデルなどに基づいて決定できます。
• さまざまなエネルギー関数が定義されています。
  • 標準マルコフランダムフィールド: 不一致のピクセルに、それらのセグメンテーションラベル(境界の長さの粗い尺度)の差を評価することによってペナルティを関連付けます。BoykovとKolmogorov ICCV 2003を参照してください。
  • 条件付きランダムフィールド: 色が大きく異なる場合は、境界を設定するのに適した場所である可能性があります。Lafferty et al. 2001、Kumar and Hebert 2003 を参照してください。

グラフカット法は、輪郭線の位置を最適化するためのレベルセットベースのアプローチの代替として人気が高まっています（詳細な比較については^[9]を参照）。しかし、グラフカットアプローチは、いくつかの問題で文献で批判されてきました。

• メトリック化アーティファクト: 画像が 4 連結格子で表現されている場合、グラフカット法では望ましくない「ブロック化」アーティファクトが発生する可能性があります。この問題に対処するために、追加のエッジを使用する^[10]や、連続空間で最大フロー問題を定式化するなど、さまざまな方法が提案されています。^[11]
• 縮小バイアス：グラフカットは最小カットを見つけるため、アルゴリズムは小さな輪郭を生成する方向に偏る可能性があります。^[12] たとえば、このアルゴリズムは血管のような細い物体のセグメンテーションには適していません（提案された修正については^{[13]を参照）。}
• 複数ラベル: グラフカットは、前景/背景画像のセグメンテーションなどのバイナリラベリング（つまり、2つのラベル）問題に対してのみグローバル最適値を見つけることができる。マルチラベルグラフカット問題の近似解を見つけることができる拡張が提案されている。^[7]
• メモリ: グラフカットのメモリ使用量は、画像サイズが大きくなるにつれて急速に増加します。例として、ボイコフ-コルモゴロフ最大フローアルゴリズムv2.2は、バイト（およびはそれぞれグラフ内のノードとエッジの数）を割り当てます。ただし、最大フロー計算の前にグラフを縮小するという方向で、最近、ある程度の研究が行われています。^{[14] [15] [16]}${\displaystyle 24n+14m}$${\displaystyle n}$${\displaystyle m}$

• 最小化は、標準の最小カット アルゴリズムを使用して行われます。
• 最大フロー最小カット定理により、ネットワーク上のフローを最大化することでエネルギー最小化を解決できます。最大フロー問題は、容量でラベル付けされたエッジを持つ有向グラフで構成され、ソースとシンクの 2 つの異なるノードがあります。直感的に、最大フローはボトルネックによって決定されることが簡単にわかります。

Wikibookアルゴリズム実装には、グラフ/最大フロー/ボイコフとコルモゴロフに関するページがあります。

ボイコフ-コルモゴロフアルゴリズム^[17]は、コンピュータビジョン関連のグラフの最大フローを計算する効率的な方法です。

Sim Cutアルゴリズム^[18]は最小グラフカットを近似する。このアルゴリズムは電気回路網のシミュレーションによって解を実装する。これはセダーバウムの最大フロー定理^{[19] [20]}で示唆されたアプローチである。このアルゴリズムは並列計算 によって高速化できる。

• http://pub.ist.ac.at/~vnk/software.html — ウラジミール・コルモゴロフ著「コンピュータビジョンにおけるエネルギー最小化のための Min-Cut/Max-Flow アルゴリズムの実験的比較」で説明されている maxflow アルゴリズムの実装
• http://vision.csd.uwo.ca/code/ — いくつかのグラフカットライブラリと MATLAB ラッパー
• http://gridcut.com/ — グリッドのようなグラフに最適化された高速マルチコア max-flow/min-cut ソルバー
• http://virtualscalpel.com/ — Sim Cutの実装。超並列方式で最小 st カットの近似解を計算するアルゴリズム。