コンピュータビジョングラフのカット: コンピューター ビジョンでのグラフ カットの探索

By Fouad Sabry

コンピュータービジョングラフカットとは

コンピュータ ビジョンの分野で応用されているように、グラフ カットの最適化を使用すると、画像のスムージング、ステレオ対応問題、画像のセグメンテーション、オブジェクトの共同セグメンテーションなど、さまざまな低レベルのコンピュータ ビジョンの問題を効率的に解決できます。 エネルギー最小化の観点から定式化できるコンピュータ ビジョンの問題。 これらのエネルギー最小化問題の多くは、グラフ内の最大流量問題を解くことで近似できます。 コンピュータ ビジョンにおけるこのような問題のほとんどの定式化では、最小エネルギー解は解の最大事後推定値に対応します。 多くのコンピューター ビジョン アルゴリズムにはグラフのカットが含まれますが、「グラフ カット」という用語は、最大フロー/最小カットの最適化を採用するモデルに特に適用されます。

どのようなメリットがあるのか

(I) 以下のトピックに関する洞察と検証:

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

第 2 章: 最大流量最小カット定理

第 3 章: 画像のセグメンテーション

第 4 章：カット（グラフ理論）

第 5 章: ミニマムカット

第 6 章：流域（画像処理）

第 7 章: グラブカット

第 8 章: ランダム ウォーカー アルゴリズム

第 9 章: グラフカットの最適化

第 10 章: ビデオ マッティング

(II) コンピュータ ビジョン グラフ カットに関する一般のよくある質問に答える。

(III) 多くの分野でのコンピュータ ビジョン グラフ カットの使用例。

この本は誰に向けたものなのか

専門家、大学生、大学院生、愛好家、趣味人、そしてあらゆる種類のコンピューター ビジョン グラフ カットに関する基本的な知識や情報を超えたいと考えている人。

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: May 11, 2024

Book preview

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

グラフカット最適化は、コンピュータビジョンの主題に適用すると、広範囲の低レベルのコンピュータビジョンの問題(早期ビジョンの問題とも呼ばれる)に効果的かつ効率的な方法で対処するために使用できます(したがって、最大流量の最小カット定理によって、グラフの最小カットを定義します)。コンピュータビジョンでこの種の問題を定式化するためのアプローチの大部分は、エネルギー消費量が最も少ない答えが、解の事後推定値として最も高いものに対応することに同意しています。多くのコンピューター ビジョン アルゴリズムにはグラフの切り取り (正規化された切り取りなど) が含まれていますが、グラフの切り取り というフレーズは、特に最大流量/最小カットの最適化を使用するモデルを指します。これは、多くのコンピュータビジョン手法がグラフの切り取りを伴うためです(他のグラフ切り取りアルゴリズムは、グラフ分割アルゴリズムと見なすことができます)。

この方法を使用すると、バイナリ画像のノイズ除去などの「バイナリ」問題を正確に解決できます。ステレオ対応やグレースケール画像のノイズ除去など、ピクセルに2つ以上の異なるラベルを付けることができる問題は、正確に解決することはできません。ただし、生成される解は、通常、大域最適解に非常に近いものです。

ダラム大学のGreig、Porteous、Seheultは、この画期的な研究で、グラフカットの考え方をコンピュータビジョンを最適化するプロセスに初めて適用した人物です。グラフカットは最適化の手法です。アラン・セヒュートとブルース・ポルテウスは、ジュリアン・ベサグとピーター・グリーン(統計学者)が率いる、当時賞賛されていたダーラムの統計グループのメンバーであり、最適化の専門家であるマーガレット・グレイグは、ダーラム数理科学部門の史上初の女性スタッフとして有名でした。

ノイズの多い(または破損した)画像を平滑化するベイズ統計的文脈において、彼らは、ソースとシンクの導入を含む関連する画像ネットワークを通る流れを最大化することによって、バイナリ画像の事後推定の最大値を正確に得る方法を示しました。これにより、バイナリ画像の事後推定の最大値を正確に取得する方法を実証することができました。その結果、問題が正常に解決される可能性があることが示されました。この発見の前には、Geman兄弟によって提示されたシミュレーテッドアニーリングのような近似アプローチが、同様の画像平滑化の問題に取り組むために利用されていました。しかし、このソリューションができたので、これらの問題をより正確に解決できます。

Greigのアプローチでは、一般的な k 色の問題は未解決のままです k>2, が、PorteousとSeheultは、一般的なコンピュータビジョンの問題に幅広い応用が期待されます。

Greig: 一連のバイナリ問題に対してPorteous法とSeheult法を反復的に使用するのが一般的であり、多くの場合、理想に非常に近いソリューションが得られます。

2011年、C.

Couprie等。

画像セグメンテーションのための包括的なフレームワークが提示され、しばしば「パワーウォーターシェッド」と呼ばれ、ユーザーが植えた種(または単項項)によって制限されたグラフ上の[0,1]から、グラフ上の指標関数の最小化が指数に対して最適化される0または1までの範囲の実数値指標関数に対して可能な限り最良の結果を達成しました p 。

の場合 p=1 、グラフ カットによって電力集水域の最適化が可能になり、 p=0 電力集水域が最短パスによって最適化され、 p=2 ランダム ウォーカー アルゴリズムによって最適化 p=\infty され、集水域 (画像処理) アルゴリズムによって最適化されます。

この場合、電力分水域はグラフカットの延長線上にあると考えることができ、他のいくつかのエネルギー最適化セグメンテーション/クラスタリング手法に簡単にリンクできます。

画像： x\in \{R,G,B\}^{N}

出力: セグメンテーション (不透明度とも呼ばれます) S\in R^{N} (ソフト セグメンテーション)。

ハードセグメンテーションの場合

S\in \{0{\text{ for background}},1{\text{ for foreground/object to be detected}}\}^{N}

エネルギー関数: E(x,S,C,\lambda ) ここで、Cは色パラメータ、λはコヒーレンスパラメータです。

E(x,S,C,\lambda )=E_{{{\rm {color}}}}+E_{{{\rm {coherence}}}}

最適化: セグメンテーションは S 上の大域的最小値として推定できます。 {\arg \min }_{S}E(x,S,C,\lambda )

標準グラフのカットは、セグメンテーション(未知のS値)におけるエネルギー関数の効率を最大化することを目的としています。

反復グラフのカット:

最初のフェーズでは、色パラメーターに対して K 平均法の最適化が実行されます。

グラフをカットするための標準アルゴリズムは、第2段階で実行されます。

これら 2 つのプロセスは、収束に達するまで再帰的に実行されます。

動的グラフカットを使用すると、課題が変更された後(たとえば、ユーザーによって新しいシードが追加された後)に、この手法を大幅に迅速に再実行できます。

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

ここで、エネルギーは E 2つの異なるモデル( E_{{{\rm {color}}}} および E_{{{\rm {coherence}}}} )で構成されています。

E_{{{\rm {color}}}} — 各色の尤度を表す単項項。

この用語は、局所的なもの(テキソンなど)やグローバルなもの(ヒストグラム、GMM、Adaboostの尤度など)など、さまざまな方法で表すことができますが、そのすべてについて以下で詳しく説明します。

物体(前景)と背景の強度分布のヒストグラムを生成するために、シードとして識別されたピクセルの強度であるP(I|O)とP(I|B)の両方を利用します。

その後、これらのヒストグラムを使用し、負の対数尤度として設定することにより、地域的なペナルティを決定します。

ほとんどの場合、背景のモデリング用と前景のピクセル用の2つの分布を使用します。

これら 2 つの分布を表すには、5 から 8 の成分を持つ混合ガウス モデルを使用する必要があります。

目標は、2 つの分布を可能な限り区別することです。

テキソンは、しばしばテキストと綴られ、画像内で繰り返され、共通の特定のプロパティを持つピクセルのグループです。

ステップス：

テクスチャのコンポーネントに適した自然なスケールを見つけます。

強度またはガボール フィルター応答のいずれかに着目して、モデルの内部テキソンのノンパラメトリック統計量を計算します。

例：

変形モデルに基づくテクスチャオブジェクトのセグメンテーション

セグメンテーションのための画像の輪郭と質感の分析

E_{{{\rm {coherence}}}} — 近傍ピクセル間のコヒーレンスを表すバイナリ項。

実際には、2 つのピクセルが水平、垂直、または斜めの 3 次元のいずれかで隣り合っている場合、2 つのピクセルは隣接と見なされます (2D 画像の場合は 4 方向接続または 8 方向接続)。

局所的な強度勾配、ラプラシアンゼロクロッシング、勾配方向、混色モデルなどはすべて、何かのコストを決定する役割を果たす可能性があります。

さまざまなエネルギー関数が定義されています。

標準マルコフ確率フィールド: それぞれのセグメンテーションラベルの差を計算することにより、互いに一致しないピクセルにペナルティを割り当てます(境界の長さの大まかな尺度)。Boykov and Kolmogorov ICCV 2003を参照

条件付きランダム フィールド: 色が互いに大きく異なる場合、その領域が境界線の適切な場所である可能性があります。Lafferty