如何提高洪水填充例程的性能？
我正在我的应用程序中实现四路洪水填充，下面给出的伪代码
Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
4. Return
它有点慢，有时会填充调用堆栈！而且我真的没能计算出这个算法的复杂度。
有人可以建议更好的算法来实现它吗？
I'm implementing the four way flood fill in my application, pseudo code given below
Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
4. Return
It's kind of slow and sometimes fills the call stack! And I'm really failed to calculate the complexity of this algorithm.
Can anyone suggest better algorithm to implement it, please?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我无法帮助您使用 C#，因为我只在 Delphi 中完成此操作，但我可以帮助您解决调用堆栈问题。诀窍是不使用递归算法。相反，通过维护需要审查的点堆栈来使用基于堆栈的方法。
基本上，您将“起点”添加到堆栈中（并更改其颜色）。然后，当堆栈不为空时，从堆栈中取出最后一个点（即弹出它）。对所有 4 个方向（左、右、上、下）进行比较。如果任何相邻像素需要翻转为新颜色，请进行翻转，然后将该相邻点添加到堆栈中。在下一次循环中，堆栈上应该有更多的点。继续循环，直到栈为空。
I cant help you with C# since I've only done this in Delphi, but I can help you with the call stack problem. The trick is to not use a recursive algorithm. Rather, use a stack based approach by maintaining a stack of points that need to be reviewed.
Basically, you add the 'start point' to the stack (and change its color). Then while the stack is not empty, take the last point off the stack (ie, Pop it). Do your comparisons for all 4 directions (left, right, up, down). If any of the neighboring pixels need to flip to the new color, do the flip, and then add that neighboring point to the stack. On your next loop through, there should be more points then on the stack. Continue looping until the stack is empty.
当前最先进的洪水填充算法（自 2006 年左右）基于查找连接组件的轮廓（最外层边界），将轮廓转换为水平像素游程（并检测并从连接的组件中去除内部孔），然后填充像素运行。好处是大大减少了内存需求（和/或堆栈级别）并且速度更快（内部像素保证只读取一次并写入一次）。然而，该算法并不简单。您需要阅读一些研究论文才能实施它。
The current state-of-the-art floodfill algorithm (since 2006 or so) is based on finding the contour (the outermost boundary) of the connected component, converting the contour into horizontal pixel runs (and detecting and removing of internal holes from the connected component), then fill the pixel runs. The benefits are vastly reduced memory requirements (and/or stack level) as well as being faster (interior pixels are guaranteed to be read exactly once and written once). However the algorithm is not trivial. You'll need to read some research papers in order to implement it.
通过使用较大的项目（水平线而不是单个像素），可以减少堆栈上通常需要的项目数量。
每次从堆栈/队列中获取一行时，请向北一个像素和向南一个像素扫描该行的整个长度，以形成许多附加的水平线以添加到堆栈中。这些线的最东边和最西边可能会向东/西延伸到比原始线的边界更远，所以这样做。然后将所有这些附加行添加到堆栈/队列中。
在添加到队列之前，起点还应该向东和向西延伸一条线。
编码比一次像素洪水填充要复杂一些，但通常需要担心的水平线比像素少得多。但也有不正当的情况。
It may be possible to reduce the number of items you typically need on the stack, by using larger items - horizontal lines rather than single pixels.
Each time you get a line from the stack/queue, scan the full length of this line one-pixel-north and one-pixel-south to form a number of additional horizontal lines to add to the stack. The eastmost and westmost of these lines may be able to grow east/west further than the bounds of the original line, so do this. Then add all these additional lines to the stack/queue.
The start point should also be extended to a line east and west before being added to the queue.
Coding will be a little trickier than a pixel-at-a-time flood-fill, but there are typically far fewer horizontal lines to worry about than pixels. There are perverse cases, though.
它认为您处理的是一个图表，据我了解，您应该更改每个节点的颜色，并仅在目标颜色匹配时将其替换为另一个节点。
该算法的复杂度用 Big O 表示为 O( 4^n )，因此我建议您尝试实现 BFS 算法，这样您可以避免在没有更改的情况下留下未连接的节点，并且还可以避免在任何顶点上多次传递。这样你应该能够执行类似 O( | E | + | V | ) 的操作，其中 |E|是边数，|V|是顶点数。
这里是维基百科解释的链接，它非常简单，所以看看这个！
PS：如果您需要该算法，我将非常乐意为您提供帮助！
it think that what your dealing with is a graph and as i come to uderstand you should change the color of each node and replace it with another only if the target-color matches.
The complexity of this algorithm expressed in Big O is O( 4^n ) so i would recommend you try to implement a BFS algorithm, this way you might avoid leaving an unconneted node without changind and also avoid passing more than once on any vertice. That way you should be able to perfom in something like O( | E | + | V | ) where |E| is the number of edges and |V| is the number of vertices.
Here its a link to wikipedia explanation, and its quite simple so check this out!
PS: If you need a had with the algorithm i'd be more than happy to help you!
你可以尝试实现这个例程，它每秒填充 400 万像素。
在 2017 年的 I7 上，这相当于每秒 900 万像素，因此使用 10-15MB 内存，可以在大约 0.1 秒内处理 1024x1024 像素图像：
https://www.youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be
http://unity3dmc.blogspot.com/2017/02/ultimate- 3d-floodfill-scanline.html?m=1
You can try implementing this routine, it fills 4 million pixels per second.
On an I7 from 2017, that's equivalent to 9 million flooded pixels per second, so a 1024x1024 pixel image can be processed in about 0.1 seconds,using 10-15MB memory:
https://www.youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be
http://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?m=1