機能するフラッドフィル アルゴリズムを見つけようとしています。私が試した多くのアルゴリズムのうち、「再帰的な行の塗りつぶし」だけが、時々スタックを吹き飛ばすという主な注意事項を除いて、本来の動作をします。:(
私が見つけた多くの非再帰的な実装を試してみましたが、それらはすべて非常に気まぐれでした: 奇妙な場所にギャップを残すか、領域全体をあふれさせます (それらを囲む必要がある場合)。
C (または OOP が重すぎず、簡単に解きほぐすことができる C++) で記述された非再帰的なフラッドフィルで動作するソースコードを持っている人はいますか?
スタックに一定のサイズ（ピクセル単位の画像のサイズやその平方根など）の配列を使用してintペアのスタックを実装し、intで上部を追跡するだけです。
フラッドフィルを非再帰的に実装するC＃コードを次に示します。
private static void Floodfill(byte[,] vals, Point q, byte SEED_COLOR, byte COLOR)
{
int h = vals.GetLength(0);
int w = vals.GetLength(1);
if (q.Y < 0 || q.Y > h - 1 || q.X < 0 || q.X > w - 1)
return;
Stack<Point> stack = new Stack<Point>();
stack.Push(q);
while (stack.Count > 0)
{
Point p = stack.Pop();
int x = p.X;
int y = p.Y;
if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
continue;
byte val = vals[y, x];
if (val == SEED_COLOR)
{
vals[y, x] = COLOR;
stack.Push(new Point(x + 1, y));
stack.Push(new Point(x - 1, y));
stack.Push(new Point(x, y + 1));
stack.Push(new Point(x, y - 1));
}
}
}
これがあなたが望むことをするいくつかのC++コードです。キューを使用し、キューへの挿入に関してより効率的です。
connectedRegion(const Point& source, RegionType& region, const Color target)
{
Color src_color = color_of(source, region);
if (region.count(source) == 0 || src_color == target)
return;
std::queue<Point> analyze_queue;
analyze_queue.push(source);
while (!analyze_queue.empty())
{
if (color_of(analyze_queue.front()) != src_color)
{
analyze_queue.pop();
continue;
}
Point leftmost_pt = analyze_queue.front();
leftmost_pt.col -= 1;
analyze_queue.pop();
Point rightmost_pt = leftmost_pt;
rightmost_pt.col += 2;
while (color_of(leftmost_pt, region) == src_color)
--leftmost_pt.col;
while (color_of(rightmost_pt, region) == src_color)
++rightmost_pt.col;
bool check_above = true;
bool check_below = true;
Point pt = leftmost_pt;
++pt.col;
for (; pt.col < rightmost_pt.col; ++pt.col)
{
set_color(pt, region, target);
Point pt_above = pt;
--pt_above.row;
if (check_above)
{
if (color_of(pt_above, region) == src_color)
{
analyze_queue.push(pt_above);
check_above = false;
}
}
else // !check_above
{
check_above = (color_of(pt_above, region) != src_color);
}
Point pt_below = pt;
++pt_below.row;
if (check_below)
{
if (color_of(pt_below, region) == src_color)
{
analyze_queue.push(pt_below);
check_below = false;
}
}
else // !check_below
{
check_below = (color_of(pt_below, region) != src_color);
}
} // for
} // while queue not empty
return connected;
}
簡単にグーグル検索すると、再帰的ではない疑似コードの実装を含むフラッド フィルに関するウィキペディアの記事が表示されます。以下は、C での基本的なキューの実装を開始するのに役立つコードです。
typedef struct queue_ { struct queue_ *next; } queue_t;
typedef struct ffnode_ { queue_t node; int x, y; } ffnode_t;
/* returns the new head of the queue after adding node to the queue */
queue_t* enqueue(queue_t *queue, queue_t *node) {
if (node) {
node->next = queue;
return node;
}
return NULL;
}
/* returns the head of the queue and modifies queue to be the new head */
queue_t* dequeue(queue_t **queue) {
if (queue) {
queue_t *node = (*queue);
(*queue) = node->next;
node->next = NULL;
return node;
}
return NULL;
}
ffnode_t* new_ffnode(int x, int y) {
ffnode_t *node = (ffnode_t*)malloc(sizeof(ffnode_t));
node->x = x; node->y = y;
node->node.next = NULL;
return node;
}
void flood_fill(image_t *image, int startx, int starty,
color_t target, color_t replacement) {
queue_t *head = NULL;
ffnode_t *node = NULL;
if (!is_color(image, startx, starty, target)) return;
node = new_ffnode(startx, starty);
for ( ; node != NULL; node = (ffnode_t*)dequeue(&head)) {
if (is_color(image, node->x, node->y, target)) {
ffnode_t *west = node, *east = node;
recolor(image, node->x, node->y, replacement);
/* 1. move w to the west until the color of the node to the west
no longer matches target */
...
}
}
}
ローカルデータを使用してスタックを模倣することにより、すべての再帰関数を反復関数として実装できるという証拠はどこかにありませんか? おそらく std::vector を使用して、ヒープを使用するため、スタックを吹き飛ばすことなくアルゴリズムのスタックのような動作を作成できます。
編集:Cを使用していることに気付きました.std::vectorの代わりに、使用するデータ構造のローカル「スタック」に要素を追加する必要があるため、reallocを介して同様の動作を実装できます。
私の答えがあなたの質問に完全に関連しているかどうかはわかりませんが、今後、再帰呼び出しを使用しない Flood-Fill アルゴリズムの C バージョンを提案します。
2017 年 1 月 11 日: 新しいバージョン。2 つのビットマップで正常にテストされました。
新しいポイントのオフセットのキューのみを使用し、ウィンドウで動作します: ダブルバッファの WinnOffs-(WinDimX,WinDimY): *VBuffer (画面または画像のコピー) および、オプションで、マスクを書き込みますフラッド フィルの結果 (*ExtraVBuff)。ExtraVBuff は、呼び出しの前に 0 で埋める必要があります (マスクが必要ない場合は、ExtraVBuff= NULL を設定できます)。呼び出し後に使用すると、グラデーション塗りつぶしやその他のペイント効果を実行できます。NewFloodFill は 32 ビット/ピクセルで動作し、C 関数です。私は 1991 年にこのアルゴリズムを再発明しました (私は Pascal で書きました) が、現在はピクセルあたり 32 ビットの C で動作します。また、関数呼び出しを使用せず、キューからの各「ポップ」後に除算のみを行い、キューがオーバーフローすることはありません。つまり、正しい方法でサイズが設定されている場合 (画像のピクセルの約 1/4)、いつでもどの領域でも正しく塗りつぶすことができます。c 関数 (FFILL.C) の前、テスト プログラム (TEST.C) の後を示します。
#define IMAGE_WIDTH 1024
#define IMAGE_HEIGHT 768
#define IMAGE_SIZE IMAGE_WIDTH*IMAGE_HEIGHT
#define QUEUE_MAX IMAGE_SIZE/4
typedef int T_Queue[QUEUE_MAX];
typedef int T_Image[IMAGE_SIZE];
void NewFloodFill(int X,
int Y,
int Color,
int BuffDimX,
int WinOffS,
int WinDimX,
int WinDimY,
T_Image VBuffer,
T_Image ExtraVBuff,
T_Queue MyQueue)
/* Replaces all pixels adjacent to the first pixel and equal to this; */
/* if ExtraVBuff == NULL writes to *VBuffer (eg BUFFER of 786432 Pixel),*/
/* otherwise prepare a mask by writing on *ExtraVBuff (such BUFFER must */
/* always have the same size as *VBuffer (it must be initialized to 0)).*/
/* X,Y: Point coordinates' of origin of the flood-fill. */
/* WinOffS: Writing start offset on *VBuffer and *ExtraVBuff. */
/* BuffDimX: Width, in number of Pixel (int), of each buffer. */
/* WinDimX: Width, in number of Pixel (int), of the window. */
/* Color: New color that replace all_Pixel == origin's_point. */
/* WinDimY: Height, in number of Pixel (int), of the window. */
/* VBuffer: Pointer to the primary buffer. */
/* ExtraVBuff: Pointer to the mask buffer (can be = NULL). */
/* MyQueue: Pointer to the queue, containing the new-points' offsets*/
{
int VBuffCurrOffs=WinOffS+X+Y*BuffDimX;
int PixelIn=VBuffer[VBuffCurrOffs];
int QueuePnt=0;
int *TempAddr=((ExtraVBuff) ? ExtraVBuff : VBuffer);
int TempOffs1;
int TempX1;
int TempX2;
char FLAG;
if (0<=X && X<WinDimX && 0<=Y && Y<WinDimY) do
{
/* Fill to left the current line */
TempX2=X;
while (X>=0 && PixelIn==VBuffer[VBuffCurrOffs])
{
TempAddr[VBuffCurrOffs--]=Color;
--X;
}
TempOffs1=VBuffCurrOffs+1;
TempX1=X+1;
/* Fill to right the current line */
VBuffCurrOffs+=TempX2-X;
X=TempX2;
while (X+1<WinDimX && PixelIn==VBuffer[VBuffCurrOffs+1])
{
++X;
TempAddr[++VBuffCurrOffs]=Color;
}
TempX2=X;
/* Backward scan of the previous line; puts new points offset in Queue[] */
if (Y>0)
{
FLAG=1;
VBuffCurrOffs-=BuffDimX;
while (X-->=TempX1)
{
if (PixelIn!=VBuffer[VBuffCurrOffs] ||
ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs])
FLAG=1;
else
if (FLAG)
{
FLAG=0;
if (QueuePnt<QUEUE_MAX)
MyQueue[QueuePnt++]=VBuffCurrOffs;
}
--VBuffCurrOffs;
}
}
/* Forward scan of the next line; puts new points offset in Queue[] */
if (Y<WinDimY-1)
{
FLAG=1;
VBuffCurrOffs=TempOffs1+BuffDimX;
X=TempX1;
while (X++<=TempX2)
{
if (PixelIn!=VBuffer[VBuffCurrOffs] ||
ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs])
FLAG=1;
else
if (FLAG)
{
FLAG=0;
if (QueuePnt<QUEUE_MAX)
MyQueue[QueuePnt++]=VBuffCurrOffs;
}
++VBuffCurrOffs;
}
}
/* Gets a new point offset from Queue[] */
if (--QueuePnt>=0)
{
VBuffCurrOffs=MyQueue[QueuePnt];
TempOffs1=VBuffCurrOffs-WinOffS;
X=TempOffs1%BuffDimX;
Y=TempOffs1/BuffDimX;
}
/* Repeat the main cycle until the Queue[] is not empty */
} while (QueuePnt>=0);
}
ここにテストプログラムがあります：
#include <stdio.h>
#include <malloc.h>
#include "ffill.c"
#define RED_COL 0xFFFF0000
#define WIN_LEFT 52
#define WIN_TOP 48
#define WIN_WIDTH 920
#define WIN_HEIGHT 672
#define START_LEFT 0
#define START_TOP 671
#define BMP_HEADER_SIZE 54
typedef char T_Image_Header[BMP_HEADER_SIZE];
void main(void)
{
T_Image_Header bmpheader;
T_Image *image;
T_Image *mask;
T_Queue *MyQueue;
FILE *stream;
char *filename1="ffill1.bmp";
char *filename2="ffill2.bmp";
char *filename3="ffill3.bmp";
int bwritten;
int bread;
image=malloc(sizeof(*image));
mask=malloc(sizeof(*mask));
MyQueue=malloc(sizeof(*MyQueue));
stream=fopen(filename1,"rb");
bread=fread(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bread=fread((char *)image, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
memset(mask,0,IMAGE_SIZE<<2);
NewFloodFill(START_LEFT,
START_TOP,
RED_COL,
IMAGE_WIDTH,
IMAGE_WIDTH*WIN_TOP+WIN_LEFT,
WIN_WIDTH,
WIN_HEIGHT,
*image,
NULL,
*MyQueue);
stream=fopen(filename2,"wb+");
bwritten=fwrite(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bwritten=fwrite((char *)image, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
stream=fopen(filename3,"wb+");
bwritten=fwrite(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bwritten=fwrite((char *)mask, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
free(MyQueue);
free(mask);
free(image);
}
表示されているテスト プログラムの入力には、次の Windows 非圧縮 .BMP イメージ (ffill1.bmp) を使用しました。
次のように、示されているテスト プログラムによって入力されます (ffill2.bmp):
NULL の代わりに「マスク」を使用すると、出力ビットマップは次のようになります (ffill3.bmp):
明示的なスタックまたはキューを作成し、そこに作業をロード/プルオフすることで、再帰アルゴリズムを反復アルゴリズムに変換できます。
必要なのは、実行する作業の適切でコンパクトな表現を選択することだけです。最悪の場合:struct通常は再帰バージョンに渡す引数を保持する を作成します...
3D ボリュームでのフラッドフィルの実装が大量のメモリを消費していることに気付きました。そのため、次の方法でコードを変更しました (大幅な改善がありました)。
開始点の周りに半径 = 10 vox の球を作成し、その半径内のすべてのボクセルを「訪問先」としてマークします。
現在のボクセル > しきい値の場合は、1 を挿入します。
neighbor.getVoxVal = 0 (ターゲット ボリュームの初期化値) の場合、隣接する [+1, -1, 0] に移動します (いずれのボクセルも再訪しないことも確認します)。球、座標を別のスタックに挿入します。(これが次の領域の出発点になります)
半径 = 半径 + 10 (ボクセル)
そのため、一度にフラッドフィルは同心球に取り組み、ボリューム全体の一部であるものを埋めます。前述のように、これによりメモリ消費が大幅に削減されましたが、まだ実装/アイデアを探していますそのほうがいい。
非再帰的なフラッド フィルがありますが、宿題の解決策なので投稿しません。しかし、ここにヒントがあります。自然なアルゴリズムである深さ優先検索は、幅優先検索よりもはるかに多くの補助スペースを使用します。当時の私が書いたものは次のとおりです（適切に削除されています）。
単純な再帰による深さ優先探索は試しません。再帰の深さは編集済みによってのみ制限されますが、私の実験では、編集済みの問題には 100 万を超えるスタックの深さが必要になる可能性があることが示されています。そこで、スタックを補助データ構造に入れました。明示的なスタックを使用すると、実際には幅優先検索も簡単に試すことができ、幅優先検索は深さ優先検索の 40 分の 1 のスペースしか使用できないことがわかります。
私のデータ構造にはSeq_T、Dave Hanson のC Interfaces and Implementationsを使用しました。深さ優先から幅優先に変更するには、関数呼び出しを 1 つだけ変更する必要があります。
以下は、フラッド フィルの問題に対する BFS ベースの反復的な C++ メソッドです。
// M is the input matrix, with every entry(pixel) have a color
// represented with an integer value.
// (x, y) row and column of seed point respectively
// k: The new color to fill the seed and its adjacent pixels
void floodFill(vector<vector<int>> &M, int x, int y, int k) {
queue<pair<int, int>> nodeQ;
nodeQ.push({x, y});
int oldCol = M[x][y];
while(!nodeQ.empty()) {
pair<int, int> currNode = nodeQ.front();
nodeQ.pop();
if(M[currNode.first][currNode.second] == oldCol) {
M[currNode.first][currNode.second] = k;
if(currNode.first > 0) nodeQ.push({currNode.first-1, currNode.second});
if(currNode.first < (M.size()-1)) nodeQ.push({currNode.first+1, currNode.second});
if(currNode.second > 0) nodeQ.push({currNode.first, currNode.second-1});
if(currNode.second < (M[0].size()-1)) nodeQ.push({currNode.first, currNode.second+1});
}
}
}