Find the corners of a deformed rectangle?

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.

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.

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 2 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.

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.

This looks like a convex hull problem. en.wikipedia.org/wiki/Convex_hull Your problem is simpler but the same solution should work.

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" research.microsoft.com/en-us/um/people/z... for a more advanced solution for quadrangle detection I have asked a related question, which tries to solve the perspective transform: stackoverflow.com/questions/1194352/prop....

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.

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.

He doesn't need to know which corner is which to do perspective correction. – Nosredna Jun 25 '09 at 16:27.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.