C + +アルゴリズムは、バイナリ画像を埋めるための洪水 - c + +、matlab、画像処理、flood-fill

バイナリイメージ（1と0の2Dマトリックス）を塗りつぶすためのmatlab関数「imfill」をシミュレートしようとしています。

マトリックスで開始点を指定し、4つの接続されたバージョンのimfillのように塗りつぶします。

これはC ++の世界のどこかにすでに存在しますか？そうでない場合、これを実装する最も効率的な方法は何でしょうか？

回答：

画像が1と0の2D配列にすぎない場合、実際のグラフィックライブラリは必要ないと思います。

過去に単純なグリッドを埋めたとき、STLキューを使用してポイントのリストを保存し、それらを処理しただけです。キューは最初のポイントから開始し、隣接するポイントをテストします。隣接するポイントを「洪水」に含める必要がある場合は、キューに追加します。次のようなものです。

// using this data structure
struct Point {
int x;
int y;
};

//
void fillGrid(Point orig, byte** grid, int width, int height) {
std::queue<Point> q;
q.push(orig);

// the main flood loop
while(!q.empty()) {
Point pnt = q.front();
q.pop();

// grab adjacent points
Point adj[4];
adj[0].x = pnt.x;   adj[0].y = pnt.y-1;   // up
adj[1].x = pnt.x+1; adj[1].y = pnt.y;     // right
adj[2].x = pnt.x;   adj[2].y = pnt.y+1;   // down
adj[3].x = pnt.x-1; adj[3].y = pnt.y;     // left

for(int i = 0; i < 4; i++) {
// don"t forget boundaries!
if(adj[i].x < 0 || adj[i].x >= width ||
adj[i].y < 0 || adj[i].y >= height)
continue;

// if adjacent point meets some criteria, then set
// its value and include it in the queue
if(includePoint(adj[i], grid)) {
setPoint(adj[i], grid);
q.push(adj[i]);
}
}
}
}

C ++で画像処理を行いたい場合は、 OpenCV （オープンソースコンピュータービジョン）。

「画像/動画処理用の優れたクロスプラットフォームライブラリであり、探しているものが揃っています。この質問を確認してください。

OpenCVの穴を埋める

次のコード例を参照してください このページ（「QuickFill：効率的なフラッドフィルアルゴリズム」）

最初のいくつかのコード例では、ピクセルは塗りつぶし（または境界線）の色があり、関数が4つ（または8つ）のすべての隣接ピクセルに対して再帰的に呼び出すかどうかを確認します（実際、最初のいくつかの例は、最初の再帰呼び出しはむしろまったく同じパラメーターを使用して関数自体を再度呼び出す代わりに、新しいピクセルを設定する関数）。

次のいくつかの例では、再帰について説明しますスキャンライン方式。最初に可能な限り水平方向のラインを埋めてから、隣接するライン（上下のライン）に移動するため、各ピクセルの訪問頻度が低くなります。

最後に、提案します QuickFill これは、スキャンライン方式の最適化されたバリアントのように見えます。

Aforge Libraryには次の機能があります

AForge.Imaging.Filters.FillHoles(...)

Matlabのimfillと同じことを行います。