Trying to find an algorithm to detect rectangles in images

Question

At the moment I have detected edges in an image and I am planning to extract line segments from the edges using a hough transform. Once I have the segments I am planning on finding corners where two segments cross over. Is there an algorithm that can detect rectangles from the corners? say I have four corners detected, is it possible to get the relative lengths of the sides of the rectangle that the four corners make up knowing a rectangle has 4 right angles?

The reason I want to do this is so I can extract the texture bound by the rectangle and draw it as a flat rectangle on the screen.

Edit: Thanks for the answers so far, I think I should explain my problem more clearly as I think I was slightly misinterpreted. I am actually trying to transform a warped rectangle into a flat rectangle. I read through some of the aforge articles and saw this function: link. I was wondering if it is possible to determine the ratio between the sides of the rectangle just from the 4 corners?

Answer 1

Her is some code you can use to detect quadrilateral shapes in an image using the AForge.NET Framework:

// get angles between 2 pairs of opposite sides
float angleBetween1stPair = Tools.GetAngleBetweenLines(corners[0], corners[1], corners[2], corners[3]);
float angleBetween2ndPair = Tools.GetAngleBetweenLines(corners[1], corners[2], corners[3], corners[0]);

// check 1st pair for parallelism
if (angleBetween1stPair <= angleError)
{
    subType = PolygonSubType.Trapezoid;

    // check 2nd pair for parallelism
    if (angleBetween2ndPair <= angleError)
    {
        subType = PolygonSubType.Parallelogram;

        // check angle between adjacent sides
        if (Math.Abs(Tools.GetAngleBetweenVectors(corners[1], corners[0], corners[2]) - 90) <= angleError)
            subType = PolygonSubType.Rectangle;

        //get length of 2 adjacent sides
        float side1Length = (float)corners[0].DistanceTo( corners[1] );
        float side2Length = (float)corners[0].DistanceTo( corners[3] );

        if (Math.Abs(side1Length - side2Length) <= maxLengthDiff)
            subType = (subType == PolygonSubType.Parallelogram) ? PolygonSubType.Rhombus : PolygonSubType.Square;
    }
}
else
{
    // check 2nd pair for parallelism - last chence to detect trapezoid
    if (angleBetween2ndPair <= angleError)
    {
        subType = PolygonSubType.Trapezoid;
    }
}

See this article for examples of how to detect various shapes:
http://www.aforgenet.com/articles/shape_checker/

Here's a link to download the AForge.NET Framework:
http://www.aforgenet.com/framework/downloads.html

Answer 2

You're already using the tool you need - the Hough transform.

The standard formulation of the Hough transform is used to identify lines within an image, by translating from the (x,y) space of the image to the (theta,d) solution space of possible lines.

You can do the same thing to identify candidate rectangles by translating from the (x,y) space of the image to the solution space of possible rectangles (theta,d,width,height,rotation).

Taking this approach retains the strengths of the Hough transform to work with partially visible features from your image - a two step approach using the Hough transform to identify edges, and combining those edges in to rectanges, will fail to identify a rectangle if one edge or corner is sufficiently obscured.

Answer 3

try this brother :

http://www.emgu.com/wiki/index.php/Shape_(Triangle,_Rectangle,_Circle,_Line)_Detection_in_CSharp

have fun coding :)