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

Question

我有一张图片，这是一个小剪纸：

如您所见，它是黑色背景上的白色像素。我们可以在这些像素（或更好的点）之间画出假想的线。使用这些线，我们可以包围区域。

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

这是我所说的最大凸黑色区域的一个小手绘示例：

PS：图像不是噪声，它代表10000000以下的素数水平排列。

Answer 1

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

假设你想找到最大的自由（白色）像素矩形（对不起，我有不同颜色的图像 - 白色相当于你的黑色，灰色相当于你的白色）。

您可以通过两次通过线性O(n)时间算法（n 是像素数）非常有效地做到这一点：

1）在第一遍中，按列，从下到上，对于每个像素，表示到此为止可用的连续像素数：

重复，直到：

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

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

Answer 2

我将绘制一个正确的多时间算法。毫无疑问，需要对数据结构进行改进，但我相信，尤其需要更好地理解这个问题，以搜索非常大的数据集（或者，也许是包含多边形）。

主循环包括猜测最大凸多边形中的最低点 p（打破平局以支持最左边的点），然后计算可以与 p 和点 q 的最大凸多边形，使得 (qy > py) || （qy == py && qx > px）。

动态程序依赖于与Graham 的扫描相同的几何事实。不失一般性假设 p = (0, 0) 并按照它们与 x 轴形成的逆时针角度的顺序对点 q 进行排序（通过考虑它们的点积的符号来比较两个点）。让排序后的点为 q ₁ , ..., q _n。令 q ₀ = p。对于每个 0 ≤ i < j ≤ n，我们将计算点 q ₀上的最大凸多边形，它是 q ₁、...、q _{i - 1}、q _i和 q _j的子集。

i = 0 的基本情况很简单，因为唯一的“多边形”是零面积段 q ₀ q _j。归纳地，为了计算 (i, j) 项，我们将尝试，对于所有 0 ≤ k ≤ i，用 (i, j) 扩展 (k, i) 多边形。我们什么时候可以做到这一点？首先，三角形 q ₀ q _i q _j不能包含其他点。另一个条件是角度 q _k q _i q _j最好不要右转（再次检查适当点积的符号）。

最后，返回找到的最大多边形。为什么这行得通？不难证明凸多边形具有动态程序所需的最优子结构，并且程序准确地考虑了那些满足格雷厄姆凸性表征的多边形。

Answer 3

您可以尝试将像素视为顶点并对点集执行Delaunay 三角剖分。然后，您需要找到最大的一组连接三角形，该三角形不会创建凹形并且没有任何内部顶点。

Answer 4

如果我正确理解您的问题，这是连接组件标签的一个实例。例如，您可以从以下位置开始：http ://en.wikipedia.org/wiki/Connected-component_labeling

Answer 5

我想到了解决这个问题的方法：

从所有点的集合中生成所有可能的 3 点子集。这是您空间中所有三角形的集合。从此集合中删除所有包含另一个点的三角形，您将获得所有空三角形的集合。

对于每个空三角形，您可以将其增长到最大尺寸。也就是说，对于矩形外的每个点，您都可以将其插入多边形的两个最近点之间，并检查这个新三角形内是否有点。如果没有，您将记住该点及其添加的区域。对于您要添加的每个新点，以最大化添加的区域。当无法添加更多点时，已构建最大凸多边形。记录每个多边形的面积并记住面积最大的那个。

对该算法的性能至关重要的是，您能够确定 a) 一个点是否位于三角形内，以及 b) 添加某个点后多边形是否仍然是凸的。

我认为您可以将 b) 简化为 a) 的问题，然后您只需要找到最有效的方法来确定一个点是否在三角形内。搜索空间的缩小可以通过以下方式实现：取一个三角形并将所有边在两个方向上都增加到无限长。这将三角形以外的区域分成 6 个子区域。对我们有利的是，这些子区域中只有 3 个可以包含符合凸性约束的点。因此，对于您测试的每个点，您需要确定它是否在凸扩展子区域中，这又是它是否在某个三角形中的问题。

整个多边形随着它的演变和接近圆形的形状将具有越来越小的区域，这些区域仍然允许凸扩展。曾经在凹入区域中的点将不会再次成为凸扩展区域的一部分，因此您可以快速减少必须考虑扩展的点数。此外，在测试扩展点时，您可以进一步减少可能点的列表。如果一个点被测试为假，那么它在另一个点的凹子区域中，因此不需要考虑测试点的凹子区域中的所有其他点，因为它们也在内部点的凹子区域中。您应该能够非常快速地减少到可能点的列表。

当然，您仍然需要为每个空三角形执行此操作。

不幸的是，我不能保证通过始终添加最大的新区域，您的多边形成为可能的最大多边形。