Find the corners of a deformed rectangle

Question

I am trying to make a program that automatically corrects the perspective of a rectangle. I have managed to get the silhouette of the rectangle, and have the code to correct the perspective, but I can't find the corners. The biggest problem is that, because it has been deformed, I can't 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 wouldn't work with this situation (X represents a corner):

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

Does anyone know how to do this?

Answer 1

If you only have a list of the four X-coord values and a list of the four Y-coord values, with no relationship between them, then this is an indeterminate problem. Depending on assumptions that you would have to make, you could end up with 4 different shapes for the polygon you have shown.

Based on the information you have given, there is no exact solution for your problem.

Answer 2

Farthest point from the center will give you one corner. Farthest point from the first corner will give you another corner, which may be either adjacent or opposite to the first. Farthest point from the line between those two corners (a bit more math intensitive) will give you a third corner. I'd use distance from center as a tie breaker. For finding the 4th corner, it'll be the point outside the triangle formed by the first 3 corners you found, farthest from the nearest line between those corners.

This is a very time consuming way to do it, and I've never tried it, but it ought to work.

Answer 3

You could try to use a scanline algorithm - For every 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 the line before. If it changed (use some tolerance here), you are at a corner of the rectangle (or close to it). That won't work for all cases, as the slope can't be that exact because of low resolution, but for large rectangles and slopes 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 with the top of the rectangle where you get two different values for l and r, so you already have two of the corners. On the left side, for the first three lines you'll get deltax = 1, but after it, you'll get deltax = 3, so there is a corner at (3, 3). On the right side, nothing changes, deltax = 0, so you only get the point at the end.

Note that you're "collecting" corners here, so if you don't have 4 corners at the end, the slopes were too similar (or you have a picture of a triangle) and you can switch to a different (more exact) algorithm or just give an error. The same if you have more than 4 corners or some other strange things like holes in the rectangle. It seems some kind of image detection is involved, so these cases can occur, right?

There are cases in which a simple deltax = (x - lastx) won't work good, see this example for the left side of a 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 is 1. It's better to use the slope of the line from the actual point to the top left/right point (deltay / deltax). Using it, you'll still have to stick with a tolerance, but your values will get more exact with each new line.

Answer 4

This looks like a convex hull problem.

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

Your problem is simpler but the same solution should work.

Answer 5

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

These are easy to distinguish: pick any point inside the quadrangle, and check if the line from this point to each of the 6 intersection points intersects any of the lines. If not, then that intersection point is a corner.

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

en.wikipedia.org/wiki/Hough_transform

Example CImg Code

I would be very interested in your results. I have been thinking about writing something like this myself, to correct photos of paper sheets taken at an angle. I am currently struggling to think of a way to correct the perspective if the 4 points are known

p.s.

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 solution for quadrangle detection

I have asked a related question, which tries to solve the perspective transform: http://stackoverflow.com/questions/1194352/proportions-of-a-perspective-deformed-rectangle