1

C++ で maxflow アルゴリズムを使用してフォアグラウンド/バックグラウンド セグメンテーションを行う必要があります。( http://wiki.icub.org/iCub/contrib/dox/html/poeticon_2src_2objSeg_2src_2maxflow-v3_802_2maxflow_8cpp_source.html )。RBGに従ってpngファイルからピクセルの配列を取得しますが、次のステップは何ですか。このアルゴリズムを問題に使用するにはどうすればよいですか?

4

1 に答える 1

14

私はそのソースをよく知っています。それが Boykov-Kolmogorov Graph Cuts ライブラリです。まず最初に彼らの論文を読むことをお勧めします。

Graph Cuts は、インタラクティブな画像セグメンテーション アルゴリズムです。オブジェクトに属していると思われるもの (前景) とオブジェクトに属さないもの (背景)について、イメージ内のピクセルをマークします。それがまず必要です。これを行うと、Graph Cuts アルゴリズムは、画像内の他のピクセルのラベルが何であるかを最もよく推測します。基本的に、ラベル付けされていない他の各ピクセルを調べて、それらが前景と背景に属しているかどうかを判断します。

Graph Cuts の背後にある全体的な前提は、画像のセグメンテーションがエネルギーの最小化に似ているということです。画像セグメンテーションは、次の 2 つの項を合計したコスト関数として定式化できます。

  1. 自己ペナルティ: これは、各ピクセルを前景または背景として割り当てるコストです。これは、データ コストとも呼ばれます。
  2. 隣接ペナルティ: これにより、隣接するピクセルが多かれ少なかれ同じ分類ラベルを共有する必要があります。これは、平滑化コストとも呼ばれます。

この種の定式化は、最大事後マルコフ確率場分類問題 (MAP-MRF)としてよく知られています。目標は、そのコスト関数を最小限に抑えて、可能な限り最良の画像セグメンテーションを実現することです。これは実際にはNP 困難な問題であり、実際には Clay Math Institute から資金提供を受けている問題の 1 つです。

Boykov と Kolmogorov は、MAP-MRF 問題がグラフ理論に変換できることを理論的に証明しました。MAP-MRF 問題を解決することは、画像を取得して、ソース リンクとシンク リンク、および隣接するリンクを接続するリンクを含むグラフに形成することに似ています。一緒にピクセル。MAP-MRF を解決するには、最大フロー/最小カット アルゴリズムを実行します。これを行うには多くの方法がありますが、Boykov / Kolmogorov は、Push-Relabel、Ford-Fulkenson などの確立されたアルゴリズムよりもはるかに高速で効率的な方法を見つけました。

自己ペナルティはtリンクとして知られているものであり、隣接ペナルティはnリンクとして知られているものです。これらがどのように計算されるかを理解するために論文を読む必要がありますが、tリンクは分類ペナルティを説明しています。基本的に、各ピクセルを前景または背景に属するものとして分類するのにかかるコスト。これらは通常、画像の負の対数確率分布に基づいています。あなたがすることは、前景として分類されたものの分布のヒストグラムと、背景として分類されたものの分布のヒストグラムを作成することです.

通常、フォアグラウンドとバックグラウンドの両方で各カラー チャネルを均一に量子化するだけで十分です。次に、これらを PDF に変換しますが、各ヒストグラムの要素の総数で割ります。次に、各ピクセルの t リンクを計算するときに、色にアクセスし、ヒストグラムのどこにあるかを確認してから、負の対数を取得します。これにより、そのピクセルを前景または背景に分類するのにかかる費用がわかります。

隣接するピクセルのコストはより直感的です。通常、あるピクセルと隣接するピクセルの間のユークリッド距離を取得し、この距離をガウス分布に適用します。簡単にするために、通常は 4 ピクセルの近傍 (北、南、東、西) が使用されます。

コストの計算方法がわかったら、次の手順に従います。

  1. ピクセルを前景または背景としてマークします。
  2. ライブラリを使用してグラフ構造を作成する
  3. 前景ピクセルと背景ピクセルのヒストグラムを計算する
  4. T リンクを計算してグラフに追加する
  5. nリンクを計算してグラフに追加
  6. グラフでルーチンを呼び出してmaxflow画像をセグメント化する
  7. 各ピクセルを調べて、ピクセルが前景に属しているか背景に属しているかを判断します。
  8. これを反映するバイナリ マップを作成し、バイナリ マップが true である画像ピクセルをコピーします。false の場合はこれを行わないでください。

の元のソースはmaxflowここにあります: http://pub.ist.ac.at/~vnk/software/maxflow-v3.03.src.zip

また、README も含まれているため、サンプル画像を使用してライブラリがどのように機能するかを確認できます。

消化しなければならないことはたくさんありますが、Graph Cuts は最も強力なインタラクティブなセグメンテーション ツールの 1 つです。

幸運を！

于 2014-06-06T02:19:42.657 に答える