调整扫描线填充以检测离散对象

Question

我正试图在Python中检测到足够接近颜色的连续区域.我独立地偶然发现了8路递归泛光填充算法(当发现的和所需的RGB颜色之间的欧几里德距离超过阈值时终止),这在小规模下工作得很好,但是在200万像素图像上导致堆栈溢出.

Stack Overflow和Wikipedia指向扫描线填充作为答案,但我发现的每个解释都是在C++中或者用已知顶点填充多边形.有人能指出一个类似于递归洪水填充的情况的良好伪代码解释吗？

由于缺乏正式的数学,我正在研究图像分割(我在高中时.)如果对K-Means有类似的简单英语解释,那就太棒了.OpenCV看起来很有前途,但看起来我得到的只是一个颜色扁平的图像; 所有我关心的是x,y对象中的像素列表.

Answer 1

扫描线洪水填充的想法如下

1. 给你初始点(种子)(x,y)
2. 尽可能向左走,直到像素(x-1,y)不被填充或你到达x = 0
3. 你到达的x将是扫描线的开始; 保持两个标志"寻找上面的洞穴"和"寻找下面的洞穴",两者都初始化为真
4. 这是扫描线循环的开始.检查上面的像素(x,y-1)是否要填充,现在考虑上面的标志和像素有4种情况:
   • 如果"看上面"是真的并且要填充像素,那么你找到了一个"新的洞穴",在"待办事项列表"中存储(x,y-1)并将"看上面"标记为假
   • 如果"look above"为false且像素未填充则当前洞穴已完成,您需要查找另一个洞穴,因此只需将"look_above"标记为true即可
   • 在其他情况下(看上面是真的,像素不填充或看上面是假的,像素是要填补)你什么都不做
5. 使用"look below"标志和像素颜色(x,y + 1)重复相同的推理
6. 绘制像素(x,y)并移动到(x + 1,y),从(5)重复,除非您移动的像素不会被绘制.
7. 如果"待办事项列表"中有任何内容,请选择并使用您在待办事项列表中找到的坐标(1,y)返回(1)

这是4连接洪水填充的版本.对于8连接填充,您还需要在启动扫描线时检查(x-1,y-1)和(x-1,y + 1)处的洞穴,并且需要检查洞穴(x + 1,y) -1)和扫描线末端的(x + 1,y + 1)(如果相应的标志为真).

在扫描线上移动时,您要做的是将图片中的绿点添加到待办事项列表中:

                                                         

请注意,种子的数量不会是"最小的"(例如,示例中的前两个"上面的种子"将最终在同一个洞穴中,因此实际上只需要其中一个).存储它们所需的堆栈量通常远小于逐像素递归方法所需的量.

限制所需内存量的另一种可能方法是使用前沿绘制算法:

1. 您将初始种子(x,y)放在current_active列表中并绘制它
2. 将next_active列表初始化为空
3. 对于current_active列表中的每个像素,检查需要绘制的邻居:当您找到一个绘制它并将其添加到next_active列表中时
4. 当你完成设置current_active列表next_active列表并从2重复,除非列表为空

您可以在此视频中看到两种算法的示例.