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

Question

私は、このようなセグメンテーションの結果を保持するイメージを持っています。

パッチの色々な色のグラフを作成する必要があります。 その結果、私は次のここ

番号は別々のパッチを表す表現、構造が欲しい、とのラインがパッチの近傍を表します。 現在のところ、どこから始めるべきかわからない、どのキーワードをGoogleにするか。

誰でも便利なものを提案できますか？

画像はOpenCVのcv :: Matクラスに保存されています。グラフはBoost.Graphライブラリを使用します。

コードサンプルやアルゴリズム、キーワードへのリンクを教えてください。

ありがとうございました。

更新。 休憩といくつかの議論の後、次のことが私の頭に浮かんだ。

1. 各ノードが各画像ピクセルに対応し、リンクが8つまたは4つの隣接ピクセルを接続する大きな格子グラフを構築します。
2. 各グラフノードに対応するピクセル値を付けます。
3. ノードを同じラベルでマージしようとします。

私のもう1つの問題は、私がBGLに慣れていないことです（ただし、本は途中です:)）。

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

アップデート2 おそらく、このlinkは助けることができます。

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

Answer 1

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

1. は、領域（グラフのあなたの番号）

   • を定義します（0 /で領域番号
   • スタートを格納2次元配列を作ります0）、1に設定する（領域番号）
   • floodfillアルゴリズムなどを使用して領域全体を1に設定します。
   • floodfill中に、おそらく異なる色の座標が発生します。それらをキューに格納します。これらの座標から塗りつぶしを開始し、前回塗りつぶしが行われた場合は領域番号を増やします。

   。

2. はあなたの2次元配列を通じて地域

   • 反復間のリンクを作成します。
   • 隣の番号がある場合は、番号のペアを格納します（ソートされた方法で、ペアがすでに存在するかどうかを確認する必要があります）。左から右へ進む場合は、下の要素、右の要素、右の対角要素をチェックするだけです。

私は..私はこのトピックについての事を知らないだけで、私のシンプルなアイデアを認めざるを得ないけど...

Answer 2

私はあなたのカラーパッチがランダムので、あなたはおそらく意志であればと思いますあなたが望むことをするには強引な力のアルゴリズムが必要です。考え方は次のとおりです。

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

これは、パッチ番号の違いがそれぞれ一意であるために機能します。たとえば、Bで3,6,7という数字で終わると、パッチ（4,1）、（8,2）と（8,1）の間に接点があることを意味します。値0は、同じパッチの隣に2つのピクセルがあることを意味するので、無視します。

Answer 3

BFSを使用して領域にマークを付けることができます。

cv :: MatをBGLに公開するには、たくさんのコードを書く必要があります。自分のbfsを書くのははるかに簡単だと思います。

2つのネブバーブすべてに対して、std::set<std::pair<mark_t, mark_t>>にマークを書き込みます。 それからグラフを作成するよりも。