4

Python で十分に近い色の連続領域を検出しようとしています。私は独自に、8 方向の再帰的フラッド フィル アルゴリズム (見つかった RGB カラーと目的の RGB カラーの間のユークリッド距離がしきい値を超えると終了する) に出くわしました。

スタック オーバーフローとウィキペディアは、答えとして走査線の塗りつぶしを指摘していますが、私が見つけたすべての説明は、C++ または既知の頂点で多角形を塗りつぶすことに関するものです。誰かが、再帰的なフラッド フィルに似た状況の適切な疑似コードの説明を教えてもらえますか?

画像セグメンテーションの研究で壁にぶち当たります。形式的な数学が不足しているためです (私は高校生です)。K-Means などの平易な英語の説明があれば、それも素晴らしいことです。OpenCVは有望に見えましたが、色が平坦化された画像しか得られないようです。私が気にするのは、オブジェクトの x、y のピクセルのリストだけです。

4

1 に答える 1

8

スキャンライン フラッド フィルの考え方は次のとおりです。

  1. 初期点（シード）（x、y）が与えられます
  2. ピクセル (x-1, y) が塗りつぶされなくなるか、x=0 になるまで、できるだけ左に移動します。
  3. 到達した x がスキャンラインの開始点になります。「上にある洞窟を探す」と「下にある洞窟を探す」という 2 つのフラグを保持し、どちらも true に初期化します
  4. これは走査線ループの始まりです。(x, y-1) の上のピクセルを塗りつぶすかどうかを確認し、ルックアバウト フラグとピクセルを考慮すると、次の 4 つのケースがあります。
    • 「上を見る」が true でピクセルが塗りつぶされる場合、「新しい洞窟」が見つかり、(x, y-1) を「to-do リスト」に保存し、「上を見る」を false としてマークします。
    • 「look above」が false で、ピクセルが塗りつぶされない場合、現在の洞窟は完成しており、別の洞窟を探す必要があるため、「look_above」を true としてマークするだけです
    • それ以外の場合 (上を見て true でピクセルを塗りつぶさないか、上を見て false でピクセルを塗りつぶす必要がある場合)、何もしません。
  5. 「下を見る」フラグとピクセルの色 (x, y+1) を使用して、同じ推論を繰り返します。
  6. ピクセル (x, y) をペイントし、(x+1, y) に移動します。移動先のピクセルがペイントされない場合を除き、(5) から繰り返します。
  7. 「やることリスト」に何かある場合は、それを選んで、やることリストで見つけた座標を (x, y) として (1) に戻ります。

これは、4 つ接続されたフラッド フィルのバージョンです。8 連結の塗りつぶしの場合、スキャンラインを開始するときに (x-1, y-1) と (x-1, y+1) の洞窟もチェックする必要があり、洞窟 (x+1, y -1) および (x+1, y+1) (対応するフラグが true の場合)。

スキャンライン上を移動するときにやりたいことは、画像の緑色の点を To Do リストに追加することです。

                                                         加工例

シードの数は「最小」ではないことに注意してください (たとえば、例の最初の 2 つの「シードの上」は同じ洞窟になるため、実際に必要なのはそのうちの 1 つだけです)。それでも、それらを格納するために必要なスタックの量は、通常、ピクセルごとの再帰的アプローチに必要な量よりもはるかに少なくなります。

必要なメモリ量を制限する別の方法として、フロンティア ペインティング アルゴリズムを使用する方法があります。

  1. 初期シード (x, y) をcurrent_activeリストに入れてペイントします
  2. next_activeリストを空に初期化する
  3. リスト内のすべてのピクセルについて、current_activeペイントする必要がある隣接ピクセルをチェックします。1 つ見つかったら、それをペイントしてnext_activeリストに追加します。
  4. 完了したら、current_activeリストをnext_activeリストに設定し、リストが空でない限り2から繰り返します

このビデオで、2 つのアルゴリズムの動作例を確認できます。

于 2012-08-29T23:10:49.807 に答える