找到最大的凸黑色区域在图像中 [英] Find the largest convex black area in an image

问题描述

我有一个形象，这是其中一个小切口：

I have an image of which this is a small cut-out:

正如你可以看到它是在黑色背景上的白色像素。我们可以借鉴这些像素（或更好，点）之间的假想线。有了这些线路，我们可以封装领域。

As you can see it are white pixels on a black background. We can draw imaginary lines between these pixels (or better, points). With these lines we can enclose areas.

我怎样才能找到最大的 凸 黑区在此图像不包含在其一个白色像素？

How can I find the largest convex black area in this image that doesn't contain a white pixel in it?

下面是什么，我的意思是最大的凸黑色区域的小手绘例如：

Here is a small hand-drawn example of what I mean by the largest convex black area:

PS：该图像是不是噪音，它重新presents下面10000000素水平下令

P.S.: The image is not noise, it represents the primes below 10000000 ordered horizontally.

推荐答案

我会画出正确的，聚时间算法。毫无疑问有数据结构改进的地方，但我相信，一个更好的了解，特别是这个问题将需要搜索大型数据集（或者也许是一个特设的上限含包装盒的尺寸多边形）。

I'll sketch a correct, poly-time algorithm. Undoubtedly there are data-structural improvements to be made, but I believe that a better understanding of this problem in particular will be required to search very large datasets (or, perhaps, an ad-hoc upper bound on the dimensions of the box containing the polygon).

主环路由猜测的最低点p的最大凸多边形（断裂有利于最左边的点的关系），然后计算最大凸多边形，可以是具有p和点的q使得（QY>吡啶） || （q.y == p.y和放大器;＆功放; q.x> p.x）。

The main loop consists of guessing the lowest point p in the largest convex polygon (breaking ties in favor of the leftmost point) and then computing the largest convex polygon that can be with p and points q such that (q.y > p.y) || (q.y == p.y && q.x > p.x).

动态程序依赖于相同的几何事实 Graham的扫描。假定不失一般性是p =（0，0）和排序的点中的q阶的反时针角度它们与x轴线（通过考虑它们的点积的符号比较两个分）使损失。让我们在有序的点为Q ₁ ，...，Q <子> N 。设q <子> 0 = P。对于每一个0≤I＆LT; Ĵ≤N，我们要计算在点q <子> 0 ，Q <子>的一个子集的最大凸多边形1 ，...，Q <子>我 - 1 ，Q <子>我和Q <子>Ĵ。

The dynamic program relies on the same geometric facts as Graham's scan. Assume without loss of generality that p = (0, 0) and sort the points q in order of the counterclockwise angle they make with the x-axis (compare two points by considering the sign of their dot product). Let the points in sorted order be q₁, …, q_n. Let q₀ = p. For each 0 ≤ i < j ≤ n, we're going to compute the largest convex polygon on points q₀, a subset of q₁, …, q_{i - 1}, q_i, and q_j.

该基地情况下，I = 0是很容易的，因为唯一的多边形是零面积段q <子> 0 问：<子>Ĵ。感应，计算（I，J）项，我们将尽力为所有0≤ķ≤我，延伸（K，I）多边形（I，J）。我们什么时候才能做到这一点？首先，三角q <子> 0 问：<子>我①<子>Ĵ不得包含其他的点。另一个条件是，角q <子> K 问：<子>我①<子>Ĵ最好不要右转（再次，检查的标志适当的点积）。

The base cases where i = 0 are easy, since the only "polygon" is the zero-area segment q₀q_j. Inductively, to compute the (i, j) entry, we're going to try, for all 0 ≤ k ≤ i, extending the (k, i) polygon with (i, j). When can we do this? In the first place, the triangle q₀q_iq_j must not contain other points. The other condition is that the angle q_kq_iq_j had better not be a right turn (once again, check the sign of the appropriate dot product).

最后，返回发现的最大的多边形。为什么这项工作？不难证明凸多边形必须由动态程序所需的最优子结构和程序认为正是这些多边形满足凸性格雷厄姆的表征。

At the end, return the largest polygon found. Why does this work? It's not hard to prove that convex polygons have the optimal substructure required by the dynamic program and that the program considers exactly those polygons satisfying Graham's characterization of convexity.

这篇关于找到最大的凸黑色区域在图像中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！