c++ - C++でスーパーピクセルの近傍を見つけて保存するためのアルゴリズムとデータ構造

Question

このようなセグメンテーションの結果を保持している画像があります。

パッチの近隣のグラフをさまざまな色で作成する必要があります。結果として、次のような構造が必要です。

ここで、数字は個別のパッチを表し、線はパッチの近傍を表します。現在、どこから始めればよいのか、どのキーワードをグーグルで検索するのかがわかりません。

誰かが何か役に立つことを提案できますか？

画像はOpenCVのcv::Matクラスに保存されますが、グラフはBoost.Graphライブラリを使用する予定です。

それで、コードサンプルとアルゴリズム、またはキーワードへのリンクをいくつか教えてください。

ありがとう。

更新します。コーヒーブレイクといくつかの議論の後、次のことが頭に浮かびました。

1. 大きな格子グラフを作成します。各ノードは各画像ピクセルに対応し、リンクは8つまたは4つの隣接ピクセルを接続します。
2. 各グラフノードに対応するピクセル値のラベルを付けます。
3. どういうわけか同じラベルのノードをマージしてみてください。

私のもう一つの問題は、私がBGLに精通していないことです（しかし、本は途中です:)）。

では、このソリューションについてどう思いますか？

Update2 おそらく、このリンクが役立つでしょう。

ただし、解決策はまだ見つかりません。

Answer 1

あなたはそれをそのように解決することができます：

1. 地域を定義する（グラフ内のあなたの番号）

   • 地域番号を格納する2D配列を作成します
   • （0/0）から開始し、1（リージョン番号）に設定します
   • 塗りつぶしアルゴリズムなどを使用して、領域全体を1に設定します。
   • 塗りつぶし中に、おそらく異なる色の座標に遭遇します。それらをキュー内に保存します。これらの座標から塗りつぶしを開始し、前の塗りつぶしが完了したら、領域番号をインクリメントします。

   。

2. 地域間のリンクを作成します

   • 2D配列を繰り返し処理します。
   • 隣接する番号がある場合は、番号のペアを保存します（おそらく、ソートされた方法で、ペアがすでに存在するかどうかも確認する必要があります）。左から右に進む場合は、下の要素、右の要素、および右の対角線の要素を確認するだけで済みます。

私はこのトピックについて何も知らないことを認めなければなりませんが..私の単純な考えだけです..

Answer 2

BFSを使用して領域をマークできます。

cv :: MatをBGLに公開するには、多くのコードを作成する必要があります。独自のbfsを作成する方がはるかに簡単だと思います。

あなたより2人のネガボーごとに彼らのマークをに書いてくださいstd::set<std::pair<mark_t, mark_t>>。そして、そこからグラフを作成するよりも。

Answer 3

カラーパッチがそれほどランダムである場合、あなたが望むことをするためにおそらくブルートフォースアルゴリズムが必要になると思います。アイデアは次のようになります。

• 最初のブルートフォースパスを実行します。これは、すべてのパッチを識別する必要があります。たとえば、画像と同じサイズの行列Aを作成し、それを0に初期化します。まだゼロである各ピクセルについて、それから開始して新しいパッチとしてマークし、ブルートフォースアプローチを試して全体を見つけます。パッチの範囲。各マトリックスセルは、その中にあるパッチの数に等しい値を持ちます。
• パッチ番号は2^N、たとえば1、2、4、8、..である必要があります。
• 画像のサイズの別の行列Bを作成しますが、各セルは2つの値を保持します。これは、ピクセル間の接続を表します。行列Bの各セルの場合、最初の値は、ピクセル内のパッチ番号と隣接するピクセルのパッチ番号との絶対差になります。最初の値は下のピクセルとの差で、2番目の値は左のピクセルとの差です。
• 行列Bのすべての一意の値を選択すると、すべての接続が可能になります。

これは、パッチ番号間のそれぞれの違いが一意であるために機能します。たとえば、Bで3、6、7の番号が付けられた場合、パッチ（4,1）、（8,2）、および（8,1）の間に連絡先があることを意味します。もちろん、値0は、同じパッチ内に2つのピクセルが隣接していることを意味するため、それらを無視します。