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

Question

我正在尝试在 Python 中检测颜色足够接近的连续区域。我独立地偶然发现了 8 路递归洪水填充算法（当找到的和所需的 RGB 颜色之间的欧几里得距离超过阈值时终止），它在小规模上效果很好，但会导致 2 兆像素图像的堆栈溢出。

Stack Overflow 和 Wikipedia 将扫描线填充作为答案，但我发现的每一个解释都是用 C++ 或关于用已知顶点填充多边形的。有人可以为类似于递归洪水填充的情况指出一个很好的伪代码解释吗？

由于缺乏形式数学（我在高中），我在研究图像分割方面遇到了困难。如果有对 K-Means 或类似内容的简单英语解释，那也很棒。OpenCV 看起来很有希望，但似乎我得到的只是一个颜色扁平化的图像；我只关心对象中 x,y 处的像素列表。

Answer 1

扫描线洪水填充的思路如下

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

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