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

Question

我有一个图像,这是一个小切口:

如你所见,它是黑色背景上的白色像素.我们可以在这些像素(或更好的点)之间绘制虚线.通过这些线,我们可以包围区域.

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

这是一个小手绘的例子,我的意思是最大的凸黑区域:

PS:图像不是噪声,它代表水平排序的10000000以下的素数.

Answer 1

我将描绘一个正确的多时间算法.毫无疑问,要使其数据结构上的改进,但我相信,尤其是这一问题的更好的理解将需要搜索大型数据集(或者也许是一个特设的上限含包装盒的尺寸多边形).

主循环在于最大凸多边形猜测的最低点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 2

试图找到最大凸面是一项艰巨的任务.你找到最大面积的矩形不是很好吗？这个问题要容易得多,并且可以用O(n) - 像素数的线性时间来解决.该算法如下.

假设你想找到最大的自由(白色)像素矩形(对不起,我有不同颜色的图像 - 白色相当于你的黑色,灰色相当于你的白色).

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

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

重复,直到:

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

这样您将获得所有最大矩形.它当然与最大凸面区域不同,但可能会给你一些关于在哪里寻找最大凸面区域的提示(一些启发式).

Answer 3

您可以尝试将像素视为顶点并执行点集的Delaunay三角剖分.然后,您需要找到最大的连接三角形集,这些三角形不会创建凹形,也没有任何内部顶点.