7

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?

dutchflyboy
  • 641
  • 4
  • 10
  • Why wouldn't what you have work? You'll need to find the real max and real min (by examining all the points you have before deciding which is really the max and min) but at some point you're going to have to rely on some of the data to tell you what the rectangle _should_ look like. – Michael Todd Jun 25 '09 at 16:03
  • How did you obtain the silhouette of the rectangle without having point coordinates for the corners? – Stewbob Jun 25 '09 at 16:10
  • I have a picture as input, with a threshold function I can seperate the interesting part from the background. – dutchflyboy Jun 25 '09 at 16:24
  • What information do you have exactly for the rectangle corners, and is it in screen space or a world space (floating point)? – Ron Warholic Jun 25 '09 at 16:25
  • I only have a picture as information, I don't know anything about the corners, I want to find those. – dutchflyboy Jun 25 '09 at 16:29

4 Answers4

5

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.

David
  • 2,164
  • 13
  • 11
  • This assumes that the center is known. If the corners are undefined, then the geometric center of the polygon is still a variable. – Stewbob Jun 25 '09 at 16:16
  • 4
    I think any point you choose as your center, the farthest point from it will be a corner. – David Jun 25 '09 at 16:21
  • You can always average all your 'rectangle' points to get a good center point. This assumes your rectangle mask is relatively error-free of course. – Ron Warholic Jun 25 '09 at 16:31
  • 1
    Even if you don't have a center, can't you find at least 1 corner by looking for max/mins? And you can go from there. – Albert Jun 25 '09 at 16:38
  • You're really close to the O(N-Log N) version of the convex hull solution. You only need two points on the hull to find all the points on the hull. And the resultant points will be the corners. – Dan Blair Jun 25 '09 at 16:41
4

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.

schnaader
  • 49,103
  • 10
  • 104
  • 136
3

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: proportions of a perspective-deformed rectangle

Community
  • 1
  • 1
HugoRune
  • 13,157
  • 7
  • 69
  • 144
  • I think I'll try using this in a later stage, but I thought I'd first concentrate on the rather easy case where you can find the silhouette of the rectangle simply by applying a threshold, it simplifies the code. To straighten the image, I've tried using a 2x2 matrix with a movement (don't know the exact mathematical term) (MxV + T; M: Matrix; V: Vector; T: Movement vector). This calculation only takes in account 3 of the 4 points however, as one point will always disappear. I'm now trying to get the math working with a 3x3 Matrix (a 3D transformation), but it's not working completely yet. – dutchflyboy Jul 29 '09 at 22:02
2

This looks like a convex hull problem.

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

Your problem is simpler but the same solution should work.

Dan Blair
  • 2,399
  • 3
  • 21
  • 32