Algorithm to find a square shape in an image?

Suppose I have an image with, say, a circle and a square. Is there a way to find the square given the matrix of the image? (there is only one square, and time is not really an issue开发者_Python百科). Thanks.

Let's divide all points into "lit" and "dark".

Look for points which are lit, and the points above and below are also lit. Those are likely to be a part of an edge.

Similarly: if a point (x,y) is lit and points (x+1,y), (x+2,y) are also lit, but (x-1,y) and (y-1,y) are dark, and analogously in the Y-direction, then you've most likely found an upper-left corner. And so on. In this way you can find the corners and then find the square from them - seems to be a simple approach.

Something like this?

for (x,y of every black pixel) {
 #those methods should return true if the lines length is more than one pixel
 if (hasLineToRight(x,y)&&hasLineToBottom(x,y)) {
  otherx=highestXOfLineToRight();
  othery=highestYOfLineToBottom();
  if (isLine(x,y,x,othery)&&isLine(x,y,otherx,y)) {
   addBoxToList(x,y,otherx,othery);
  }
 }
}

You propably want to use the box with the highest width and height values.

If the square in the image is perfect, check that there is a border in the expected position. The pseudocode in thejh's answer should work fine.

What about flood filling starting at random points until you found your rectangle ?