Find the largest convex black area of ​​the image

Question

I have an image that is a small neckline:

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

How can I find the largest convex black area in this image that does not contain a white pixel in it?

Here is a small example with a drawing, which I mean by the largest convex black area:

PS: The image is not noise, it represents primes below 10,000,000 arranged horizontally.

Answer 1

I will draw the correct multiple time algorithm. Undoubtedly, structural improvements to the data are necessary, but I believe that for a better understanding of this problem, in particular, you will need to search for very large data sets (or, possibly, ad-hoc the upper bound of the size of the box containing the polygon).

The main cycle consists in guessing the lowest point p in the largest convex polygon (breaking ties in favor of the leftmost point), and then calculating the largest convex polygon, which can be with p and points q such that (qy> py) || (qy == py & qx> px).

A dynamic program relies on the same geometric facts as Graham scan . Assume, without loss of generality, that p = (0, 0) and sort the q points in the counterclockwise angle order that they make with the x axis (compare the two points by considering the sign of their point product). Let the points q ₁ , ..., q _n sorted in order of magnitude. Let q ₀ = p. For each 0 ≤ i <j ≤ n, we are going to calculate the largest convex polygon at the points q ₀ , the subset q ₁ , ..., q _{i - 1} , q _i and q _j .

The basic cases when i = 0 are easy, since the only “polygon” is the segment of the zero region q ₀ q _j . Inductively, to compute the notation (i, j), we try to use for all 0 ≤ k ≤ i the extension of the polygon (k, i) with (i, j). When can we do this? First, the triangle q ₀ q _i q _j must not contain other points. Another condition is that the angle q _k q _i q _{j was} better not to turn right (check the sign of the corresponding point product again).

At the end, return the largest polygon found. Why does this work? It is easy to prove that convex polygons have the optimal substructure required by the dynamic program, and that the program accurately considers those polygons that satisfy the Graham characteristic of convexity.

Answer 2

Trying to find a maximal convex region is a difficult task. Aren't you going to be fine with finding rectangles with maximum area? This problem is much simpler and can be solved in O (n) - linear time in the number of pixels. The algorithm follows.

Suppose you want to find the largest rectangle of free (white) pixels (sorry, I have images with different colors - white is equivalent to your black, gray corresponds to your white).

You can do this very efficiently using the two- process linear O(n) time algorithm (n is the number of pixels):

1) in the first pass , go through the columns, from bottom to top and for each pixel, indicate the number of consecutive pixels available before that:

repeat until:

2) in the second pass , go line by line, read current_number . For each number k keep track of the sums of consecutive numbers that were >= k (i.e., Potential rectangles with height k ). Close the sums (potential rectangles) for k > current_number and see if the sum (rectangle area) is greater than the current maximum - if so, update the maximum. At the end of each line, close all open potential rectangles (for all k ).

This way you get all the maximum rectangles. Of course, this is not the same as the maximum convex area, but you will probably get some clues (some heuristics) about where to look for the maximum convex areas.

Answer 3

You can try to process pixels as vertices and triangulate Delaunay in the list. Then you will need to find the largest set of connected triangles that does not create a concave shape and has no internal vertices.

Answer 4

If I understand your problem correctly, this is an instance of labeling related components. You can start, for example, through: http://en.wikipedia.org/wiki/Connected-component_labeling

Answer 5

I thought of an approach to solving this problem:

From the set of all points, all possible 3-point subsets are generated. This is the set of all triangles in your space. From this set, remove all triangles that contain another point, and you will get a set of all empty triangles.

For each of the empty triangles, you will increase it to its maximum size. That is, for each point outside the rectangle, you must insert it between the two nearest points of the polygon and check if there are points in this new triangle. If not, you will remember this point and the area that it adds. For each new item you want to add one that maximizes the added area. When can no longer be added, the maximum convex polygon was built. Write down the area for each polygon and remember the one that has the largest area.

Important for the performance of this algorithm is your ability to determine a) whether the point is in the triangle and b) whether the polygon remains convex after adding a certain point.

I think you can reduce b) to be problem a), and you just need to find the most effective method to determine if the point is in the triangle. Reducing the search space can be achieved as follows: Take a triangle and increase all edges to an infinite length in both directions. This separates the area outside the triangle to 6 subregions. The good thing for us is that only 3 of these subregions may contain points that will adhere to the bulge constraint. Thus, for each point you check, you need to determine whether it is in an expanding convex subregion, which again is related to the question of whether it is in a certain triangle.

An entire polygon that develops and approaches the shape of a circle will have smaller and smaller regions that still allow convex expansion. One point in the concave area will not again become part of the expanding expansion area, so you can quickly reduce the number of points that you will have to consider when expanding. In addition, while testing extension points, you can further shorten the list of possible points. If the point is checked falsely, then it is located in the concave subregion of another point, and therefore, all other points of the concave subregion of the tested points should not be considered, since they are also in the concave subregion of the internal point. You can quickly shorten the list of possible points.

However, you need to do this for every empty triangle, of course.

Unfortunately, I cannot guarantee that by always adding the maximum new area, your polygon will become the maximum polygon.