Find the corners of a deformed rectangle

Question

I am trying to create a program that automatically corrects the perspective of a rectangle. I managed to get the silhouette of the rectangle, and I have the code to fix the perspective, but I can not find the corners. The biggest problem is that since it was deformed, I cannot use the following "code":

c1 = min(x), min(y) c2 = max(x), min(y) c3 = min(x), max(y) c4 = max(x), max(y) 

This will not work with this situation (X represents the angle):

 X0000000000X .00000000000 ..X000000000 .....0000000 ........0000 ...........X 

Does anyone know how to do this?

Answer 1

The farthest point from the center will give you one angle. The farthest point from the first corner will give you another angle, which may be adjacent or opposite to the first. The farthest point from the line between these two corners (a bit more intense math) will give you a third angle. I would use the distance from the center as a tie-breaker. To search for the 4th corner, it will be a point outside the triangle formed by the first three angles that you found, further from the nearest line between these corners.

This is a very laborious way to do this, and I have never tried, but it should work.

Answer 2

You can try to use the scanning algorithm. For each line of the polygon (so y = min (y) .. max (y)), get l = min (x) and r = max (x). Calculate the left / right slope (deltax) and compare it with the slope of the line to. If it has changed (use some tolerance here), you are in the corner of the rectangle (or next to it). This will not work for all cases, since the slope may not be accurate due to low resolution, but for large rectangles and slopes are not too similar, this should work.

At least it works well for your example:

 X0000000000X l = 0, r = 11 .00000000000 l = 1, r = 11, deltaxl = 1, deltaxr = 0 ..X000000000 l = 2, r = 11, deltaxl = 1, deltaxr = 0 .....0000000 l = 5, r = 11, deltaxl = 3, deltaxr = 0 ........0000 l = 8, r = 11, deltaxl = 3, deltaxr = 0 ...........X l = 11, r = 11, deltaxl = 3, deltaxr = 0 

You start at the top of the rectangle, where you get two different values ​​for l and r, so you already have two corners. On the left side for the first three lines you will get deltax = 1, but after that you will get deltax = 3, so there is an angle (3, 3). Nothing changes on the right side, deltax = 0, so you only get a point at the end.

Note that you are collecting corners here, so if you do not have 4 corners at the end, the slopes were too similar (or you have a triangle image), and you can switch to another (more accurate) algorithm or just give an error. The same thing if you have more than 4 corners or some other strange things, such as holes in a rectangle. There seems to be some kind of image definition, so these cases can happen, right?

There are cases where a simple deltax = (x - lastx) will not work well, see this example for the left side of the rectangle:

 xxxxxx xxxxx deltax = 1 dy/dx = 1/1 = 1 xxxxx deltax = 0 dy/dx = 2/1 = 2 xxxx deltax = 1 dy/dx = 3/2 = 1.5 xxxx deltax = 0 dy/dx = 4/2 = 2 xxx deltax = 1 dy/dx = 5/3 = 1.66 

Sometimes deltax is 0, sometimes it is 1. It is better to use the slope of the line from the actual point to the upper left / right point (deltay / deltax). Using it, you still have to adhere to the tolerance, but your values ​​will be more accurate with each new line.

Answer 3

You can use the hough transform to find the 4 most prominent lines in a masked image. These lines will be the sides of the quadrangle. The lines will intersect at 6 points, which are 4 corners and two vanishing points of perspective.

They are easy to distinguish: select any point inside the quadrangle and check if the line intersects from this point to each of the 6 intersection points of any of the lines. If not, then the intersection is an angle.

This has the advantage that it works well even for noisy or partially blocked images or if your segmentation is not accurate.

en.wikipedia.org/wiki/Hough_transform

CImg Code Example

I would really like your results. I was thinking of writing something like this myself in order to correct photographs of sheets of paper taken at an angle. I am currently struggling to come up with a way to correct the point of view if 4 points are known

ps

Also check out Zhengyou Zhang, Li-Wei He, "Whiteboard Scanning and Image Enhancement" http://research.microsoft.com/en-us/um/people/zhang/papers/tr03-39.pdf for a more advanced detection solution quadrangles

I asked the corresponding question that the perspective transformation is trying to solve: the proportions of the perspective-deformed rectangle

Answer 4

It looks like a convex hull problem.

http://en.wikipedia.org/wiki/Convex_hull

Your task is simpler, but the same solution should work.