从二进制图像中获取n个最大区域

Question

我给出了一个大的二进制图像（每个像素是1或0）。

我知道在那个图像中有多个区域（一个区域被定义为一组由0包围的相邻1）。

我们的目标是找到最大的（就像素数或封闭区而言，现在两者都可以解决）

我目前的计划方法是：

• 启动一个坐标数组的数组（或0，无论代表'命中'）
• 直到不再有步骤： 对于当前区域（这是一组坐标），请执行以下操作： 查看是否有任何区域与当前区域接口，如果是，则将它们添加到其他区域，如果没有继续下一次迭代

我的问题是：有没有更有效的方法来做到这一点，并且已经测试过（并行或GPU加速的奖励点）实现（在任何大型库中）？

Answer 1

您想使用连通分量分析（a.k.a。标记）。它或多或少是你建议做的，但那里有非常有效的算法。 this question的答案解释了一些算法。另见connected-components。

This library收集不同的有效算法并进行比较。

在Python中，您可能想要使用OpenCV。 cv.connectedComponentsWithStats进行连通分量分析并输出统计数据，其中包括每个连通分量的区域。

关于你的建议：使用像素坐标而不是原始图像矩阵是非常低效的：在图像中寻找相邻像素是微不足道的，在坐标列表中寻找相同的像素需要昂贵的搜索者。

Answer 2

您可以使用唯一ID对每个区域进行Flood Fill，将ID映射到该区域的大小。