6

単純か複雑かに関係なく、すべてのペイント プログラムには塗りつぶしツールが付属しています。これは基本的に、閉じた領域の色を別の色に置き換えます。これを行うためのさまざまな API があることは知っていますが、アルゴリズムに興味があります。このツールを実装するための効率的なアルゴリズムは何ですか?

私がすぐに考えることができるいくつかのことは次のとおりです。

  1. イメージをバイナリ マップに変換します。ここで、置き換えられる色のピクセルは で1あり、他のすべての色は0です。
  2. 内側のすべてのピクセルが 1 で、隣接するすべてのピクセルが 0 になるように、変更するポイントの周りに閉じた領域を見つけます。

サンプル画像

4

6 に答える 6

10

多くの実装は、再帰的な征服および除算アルゴリズムとして行われます。「フラッド フィル アルゴリズム」を簡単にグーグルで検索すると、トピックに関する優れたウィキペディア ページを含む多くのリソースが見つかります。

于 2008-11-08T02:15:04.570 に答える
7

Flood Fill アルゴリズムは、最も一般的に使用されるアルゴリズムです。以下は、Hearn Baker の第 3 版による私の古い大学の教科書「OpenGL を使用したコンピューター グラフィックス」からそのまま引用した単純なバージョンです。

void floodFill4 (int x, int y, int fillColor, int interiorColor)
{
  int color;

  /* Set current color to fillColor, then perform the following operations */
  getPixel(x, y, color);
  if (color == interiorColor) 
  {
    setPixel(x,y);  // Set color of pixel to fillColor.
    floodFill4(x + 1, y, fillColor, interiorColor);
    floodFill4(x - 1, y, fillColor, interiorColor);
    floodFill4(x, y + 1, fillColor, interiorColor);
    floodFill4(x, y - 1, fillColor, interiorColor);
  }
}

ただし、大きな画像の場合、上記の方法では、ピクセルごとに再帰するため、スタック オーバーフロー エラーが発生する可能性があります。多くの場合、このアルゴリズムは、ピクセルの行を塗りつぶすときに反復を使用してから、上下の行を再帰的に塗りつぶすように変更されます。@kasperjj が述べたように、ウィキペディアにはこれに関する良い記事があります。

于 2008-11-08T04:15:46.807 に答える
3

これらの種類のアルゴリズムについては、Computer Graphics: Principles and Practiceで詳しく説明しています。DirectX や OpenGL API を使用せずにラインをラスタライズし、ポリゴンを塗りつぶし、3D コードを記述する方法を理解したい場合は、この本を強くお勧めします。もちろん、実際のアプリケーションでは、おそらく既存のライブラリを使用したいと思うでしょうが、これらのライブラリがどのように機能するかについて興味があるなら、これはすばらしい読み物です。

于 2008-11-08T04:20:07.797 に答える
1

一般的な考え方はFlood Fill Algorithmとして説明されており、さまざまな変更が加えられています。一般的なのはスキャンライン フィルです。関連する質問「スキャンライン ベースの 2D レンダリング エンジンはどのように機能しますか?」を参照してください。

于 2010-01-23T23:30:07.220 に答える
1

連結成分のラベル付けについてもお読みください。これは、すべてのピクセルに 2 回アクセスするだけで、接続されたピクセルを見つける効率的な方法です。

ウィキペディアの記事。

これの利点は、ピクセル値が必ずしも同じである必要がないこと、または接続されているピクセルを記述する関数が生の値以外のものである可能性があることです-おそらく勾配。

于 2008-11-11T13:50:29.903 に答える
1

メモリ効率をあまり気にしない時間効率の良いアルゴリズムが必要な場合は、次の方法で実行できます。

1) 既にアクセスしたセルのブール値を保持する:Vis[]

2) すでに訪れたが、まだ近隣にマークを付けていないポイントのリストを保持する:Busy[]

3）両方を空として開始します

4）開始点を追加しますBusy

5)

while you have a point P in Busy:
{
    for each neighbour N of the point P for which Vis[N] is still false
    {
       if appropriate (not crossing the boundary of the fill region)
       {
           set Vis[N] to true
           update the colour of N in the bitmap
           add N to the end of Busy[]
       }
       remove P from Busy[]
    }
}
于 2008-11-08T02:18:20.630 に答える