algorithm - 找到图像中最大的凸黑色区域

Question

我有一张图片，其中有一个小切口:

如您所见，它是黑色背景上的白色像素。我们可以在这些像素(或更好的点)之间绘制假想线。通过这些线，我们可以封闭区域。

如何找到最大的 convex此图像中的黑色区域不包含白色像素？

这是我所说的最大凸黑色区域的意思的手绘小例子:

P.S.:图像不是噪声，它表示水平排列的 10000000 以下的素数。

Answer 1

试图找到最大的凸面区域是一项艰巨的任务。找到具有最大面积的矩形 不是很好吗？这个问题要容易得多，可以在 O(n) - 像素数的线性时间中解决。算法如下。

假设您想找到最大的自由(白色)像素矩形(抱歉，我有不同颜色的图像 - 白色相当于黑色，灰色相当于白色)。

您可以通过两次线性 O(n) 时间 算法(n 是像素数)非常有效地完成此操作:

1) 在第一遍中，按列从下到上，对于每个像素，表示直到该像素可用的连续像素数:

重复，直到:

2) 在第二遍中，逐行阅读current_number。对于每个 k 的数字，跟踪 >= k 的连续数字的总和(即高度 k 的潜在矩形)。关闭 k > current_number 的总和(潜在矩形)并查看总和(~ 矩形区域)是否大于当前最大值 - 如果是，则更新最大值。在每一行的末尾，关闭所有打开的潜在矩形(对于所有 k)。

这样您将获得所有最大矩形。它当然与最大凸面区域不同，但可能会给您一些提示(一些启发式方法)，告诉您在哪里寻找最大凸面区域。