用C编写的工作非递归填充算法?

我一直试图找到一个有效的填充算法。 在许多算法中,我只尝试过“递归线填充”,其中一个行为完全符合应有的主要警告,它偶尔会打击堆栈。 🙁

我已经尝试了很多我发现的非递归实现,并且它们都非常温和:要么在奇怪的地方留下空隙,要么泛滥整个区域(当它们应该被封闭时)。

任何人都有一个用C语言编写的非递归填充工作源代码(或者c ++不是太大的OOP而且我可以很容易地解开)?

这里有一些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 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; } 

只需实现一堆int对,其中包含一些固定大小的数组(例如,像素的大小或像素的平方根),并使用int跟踪顶部。

以下是一些非递归实现floodfill的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 (qY < 0 || qY > h - 1 || qX < 0 || qX > w - 1) return; Stack stack = new Stack(); stack.Push(q); while (stack.Count > 0) { Point p = stack.Pop(); int x = pX; int y = pY; 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)); } } } 

一个快速的谷歌搜索引出维基百科有关Flood Fill的文章,其中包括非递归的伪代码实现。 下面是一些可以帮助您入门的代码,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,所以你可以通过realloc实现类似的行为,而不是std :: vector,因为你需要在你所使用的任何数据结构的本地“堆栈”中添加更多元素。

您可以通过创建显式堆栈或队列并将工作加载到其上/将其拉出来将任何递归算法转换为迭代。

您所需要的只是选择一个漂亮,紧凑的工作表示。 最坏的情况:创建一个包含通常传递给递归版本的参数的struct

我们注意到我们在3d卷上的Floodfill实现消耗了很多内存; 所以我们通过以下方式修改了代码(有了很大的改进):

  1. 在起点周围创建一个半径= 10 voxs的球体,并将该半径内的所有体素标记为“要被访问”

  2. 如果当前体素>阈值,则插入1。

  3. 转到邻居[+ 1,-1,0](也检查一个没有重新访问任何体素),如果neighbor.getVoxVal = 0(目标卷的初始化值),则它落在边界处球体,将坐标插入不同的堆栈。 (这将成为我们下一个领域的起点)

  4. radius = radius + 10(体素)

所以,在同一时间,我们的洪水填充是在一个同心的领域和填充,这是整个卷的一部分,正如我所说,这已经大大减少了内存消耗,但我仍在寻找一个实现/想法那会更好。

我有一个非递归填充,但我不会发布它,因为它是家庭作业的解决方案。 但这里有一个提示:深度优先搜索,这是一种自然算法,使用的远比首先搜索广度更多的辅助空间。 这是我当时写的(适当删除):

我不敢通过简单的递归尝试深度优先搜索; 递归的深度仅受删除限制,我的实验表明,问题删除可能需要超过一百万的堆栈深度。 所以我把堆栈放在一个辅助数据结构中。 使用显式堆栈实际上也可以轻松尝试广度优先搜索,事实certificate,广度优先搜索可以比深度优先搜索使用少40倍的空间。

对于我的数据结构,我使用了Dave Hanson的C接口和实现中的Seq_T ; 从深度优先到广度优先改变只需要改变一个函数调用。

我不知道我的回答是否与您提出的问题完全相关,但此后我提出了我的C版Flood-Fill算法,它不使用递归调用。

1-11-2017:NEW-VERSION; 成功测试了两个BITMAPS。

它只使用新点的偏移队列,它在窗口上工作:双缓冲区的WinnOffs-(WinDimX,WinDimY):* VBuffer(屏幕或图像的副本),并且可选地,它写一个掩码洪水填充的结果(* ExtraVBuff)。 在调用之前必须用0填充ExtraVBuff(如果你不需要掩码,你可以设置ExtraVBuff = NULL); 在通话后使用它你可以做渐变式填充或其他绘画效果。 NewFloodFill使用32位/像素,它是一个C函数。 我在1991年重新编写了这个算法(我用Pascal写的),但现在它在C中工作,每像素32位; 也没有使用任何函数调用,只是在队列中每次“弹出”之后只进行一次除法,并且永远不会溢出队列,如果它以正确的方式resize(大约是图像的1/4像素),它允许始终要正确填写任何区域; 我在测试程序(TEST.C)之后显示c函数(FFILL.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=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+10) { FLAG=1; VBuffCurrOffs-=BuffDimX; while (X-->=TempX1) { if (PixelIn!=VBuffer[VBuffCurrOffs] || ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs]) FLAG=1; else if (FLAG) { FLAG=0; 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  #include  #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):

在此处输入图像描述

使用“mask”而不是NULL,输出位图是(ffill3.bmp):

在此处输入图像描述

下面是我基于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> &M, int x, int y, int k) { queue> nodeQ; nodeQ.push({x, y}); int oldCol = M[x][y]; while(!nodeQ.empty()) { pair 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}); } } } 

您可以快速将递归填充转换为超高性能的伪递归…不要编辑行,只需添加新行:将递归函数放在XY循环中以添加结构。 将找到的邻居记录到“找到的邻居数组”而不是内存,因此您将开始将递归的4-16-64样式树打包到XY数组中。 内存使用率从1千兆字节到2兆字节。 还使用名为“填充邻居数组”的2D数组…中止“填充邻居数组”中标记为填充的任何像素的函数,每次重复使用2条指令,每次填充操作使用20条指令,并迭代填充向左和向上像多米诺骨牌,疯狂地迅速。

1024×1024使用大约1百万* 20条指令,单核为0.1秒。

我通过这种方式在i7上实现了每秒900万像素的填充像素,我有一个video作为证据,以及一个包含代码和理论解释的博客页面:

http://www.youtube.com/watch?v=4hQ1wA4Sl4c

这是一个我尝试解释它是如何工作的页面。 http://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?m=1

和代码。

如果它们保持有序,递归将是最快的。

如果您通过数据网格(图像)进行递归,则也可以以网格格式存储递归处理,因为处理的步骤表示来自网格的像素,而不是将结果分解为树格式。