How can I get the corner points from a series of points in a square shape?

Question

I'm trying to extract the corners of a square in an image, I've managed to extract all the pixels around the square as x,y coordinates. Problem is now that I need to filter those down to only 4 corners I'm not sure what the best approach would be.

My first thought was to get the angles between each point and if the angle differs more than, say, 45 degrees it would mark a corner. Problem with this would be that since I'm working with pixels every other pixel would probably have a angle diff of more than 45 degrees.

Take this ASCII example of a corner of the square:

0000011111111111
0000011111111111
0000011111111111
00000X11X1111111
0000000011111111
0000000011111111
00000000X1111111
0000000000000000
0000000000000000

The X:s in there would all be considered a corner when what I'd really like is the part of the square to be considered only one corner, not 3.

Or this ASCII example of a part of a "slightly rotated" square with some errors in the pixels:

0011111111111
0001111111111
0000111111111
0000011111111
0000000011111 <-- A "missing pixel error"; using the ">45-degrees-diff"-method this would be a corner, right? 
0000000011111
0000000001111

I'm sure there's some cool (much better) algorithms to find these so I'd love to hear your ideas on how to accomplish this sort of filtering. Or maybe there's better ways in finding the corners of a square in an image without extracting the points around it?

Edit: I forgot to clearify that the "square" in the image might be rotated, tilted and/or in a perspective.

Answer 1

Have you looked at the OpenCV APIs related to corner detection documented here, particularly cvGoodFeaturesToTrack()?

This stackoverflow question regarding rectangle detection in OpenCV might also be useful.

Answer 2

If you're talking about 2d space, and if I understand your question correctly, then you could merely take from all point coords: min(x),min(y) for the lower left corner, min(x), max(y) for upper left corner, max(x), min(y) for lower right and max(x), max(y) for upper right for upper right.

Answer 3

Super inefficient (roughly n^2), but this would probably work.

Compute the distance from each pixel to each other pixel. Keep track of the top "n" point pairs (p1,p2) with the greatest distance between them. When you are done, those point pairs should contain your 4 corners.

Of course they'll likely contain some other points as well that are close to the corners but not quite. So you'll likely need to do another iteration over those to find the "best" corners.

Answer 4

I would think about whether I could, e.g., convolve the image with an edge-detection kernel (actually, probably 4 of them: NS, EW, NE-SW NW-SE, ORing the results). Then I might scan the image rasterwise until hitting an edge, follow the edge on the image, and keep track of its direction for the last some-number of positions (some flavor of boxcar average). Watch for pi/2 changes in direction of line segments. Save. Erase the line from the edge image. Continue scanning until done.

On the other hand, having the results from the convolutions, I might also look at whether lines on the NS-edges image met (or nearly met) lines on the EW-edges image. (Also for the other pair of directions: NE-SW, NW-SE) Then I would look at the candidates more closely: are they in fact connected by one of your rounded/eroded corners, do they come close to meeting? Then I'd look more closely at the lines' directions. (Or do that earlier, if it seems more efficient.)

As an aside, the convolution can actually take the form of going through the source image and bitstacking the 3x3 neighborhood of each pixel, saving the result. Then, pass that result through a lookup table (LUT) which embodies the particular kernel you want to use. (It can be useful to have a library of these LUTs.)

Another aside: are you dealing with images which have extractable features, each of which you want to classify as square/not-square? Think: confetti scattered on paper of a contrasting color, the confetti pieces being circles, squares, lunes, and so on. If that's the case, I might extract all the features, each into a separate list or its own (sub-)image. This might involve filling in a profile; if the profiles are "porous", it is possible to use a "fuzzy" probe which is too big to fit through the "holes". Then, it becomes a matter of shape analysis. Find the C.G., then ask whether the boundary pixels are all at (approximately) the same distance from the C.G. or not. If they are, you're probably looking at a disc. If they aren't, then it might be a polygon, so, ask whether the boundary pixels farthest away (or closest in) look like they are placed the way the corners (or side midpoints) of a square would be.

Answer 5

Can you try this pseudocode?

if x coord of min(y) == x coord of max(y) then
  c1 = min(x), min(y)
  c2 = max(x), min(y)
  c3 = min(x), max(y)
  c4 = max(x), max(y)
else // rotated
  c1 = min(x), y coord of min(x)
  c2 = max(x), y coord of max(x)
  c3 = x coord of min(y), min(y)
  c4 = x coord of max(y), max(y)

Based on Rich.Carpenter answer.

Answer 6

If it truly is a square, couldn't you just define one edge/line, decide on which side of the line the square occupies, and then calculate the corners from that?

Answer 7

Identify border pixels, collect all pixels that are apprixmately on a line (yielding four distinct sets of border pixels), fit a line through the collected pixels and estimate the corner points as the intersections of the calculated lines.