How can I find the largest quadrangle

Question

How can I find the largest quadrangle in this case?

In the attached image you can see what I have (in the left) and what I wantto get (in the rigth).

This code won't work because the largest rectangle has crosses instead of corners.

int GameController::GetIndexOfExternalContour(vector<vector<Point>> contours)
{
    int largest_area=0;
int largest_contour_index=0;

for( int i = 0; i< contours.size(); i++ )           // iterate through each contour. 
{
    double a = contourArea(contours[i], false);     //  Find the area of contour
    if(a > largest_area)
    {
        largest_area = a;
        largest_contour_index = i;                  //Store the index of largest contour
    }
}

Answer 1

I wanted to add a convexity defects approach.

Find largest contour, get defect points, connect the extremes.

// stl
#include <algorithm>
#include <iterator>
#include <limits>
using namespace std;

// cv
#include <opencv2/opencv.hpp>
using namespace cv;

int main()
{
    Mat sample = imread("path/to/sample.jpg");
    imshow("window", sample);
    waitKey(0);

    // images to work on
    Mat black = Mat(sample.rows, sample.cols, CV_8UC1, Scalar(0));
    Mat clone = sample.clone();

    // binarization
    Mat gray;
    cvtColor(sample, gray, CV_BGR2GRAY);
    threshold(gray, gray, 127, 255, CV_THRESH_OTSU);

    // find and fill the largest contour
    vector<vector<Point> > contours;
    vector<double> areas;
    findContours(gray, contours, CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE);
    for(unsigned int i = 0; i < contours.size(); i++)
    {
        areas.push_back(abs(contourArea(contours[i])));
    }
    vector<double>::iterator biggest = max_element(areas.begin(), areas.end());
    unsigned int ID = distance(areas.begin(), biggest);
    drawContours(black, contours, ID, Scalar(255), -1);
    imshow("window", black);
    waitKey(0);

    // get convexity defects of thelargest contour
    vector<Point> external = contours[ID];
    vector<int> hull;
    vector<Vec4i> defects;
    convexHull(external, hull);
    convexityDefects(external, hull, defects);

    // show defect points
    for(unsigned int i = 0; i < defects.size(); i++)
    {
        circle(clone, external[defects[i][1]], 1, Scalar(0, 255, 255), 3);
    }
    imshow("window", clone);
    waitKey(0);

    // find extremes
    Point tl, tr, bl, br;
    Point p;
    double d_tl, d_tr, d_bl, d_br;
    double m_tl = numeric_limits<double>::max();
    double m_tr = numeric_limits<double>::max();
    double m_bl = numeric_limits<double>::max();
    double m_br = numeric_limits<double>::max();
    for(unsigned int i = 0; i < defects.size(); i++)
    {
        p = external[defects[i][2]];
        d_tl = (double)sqrt((double)pow((double)(p.x),2) + pow((double)(p.y),2));
        d_tr = (double)sqrt((double)pow((double)(sample.cols - p.x),2) + pow((double)(p.y),2));
        d_bl = (double)sqrt((double)pow((double)(p.x),2) + pow((double)(sample.rows - p.y),2));
        d_br = (double)sqrt((double)pow((double)(sample.cols - p.x),2) + pow((double)(sample.rows - p.y),2));
        if(d_tl < m_tl)
        {
            tl = p;
            m_tl = d_tl;
        }
        if(d_tr < m_tr)
        {
            tr = p;
            m_tr = d_tr;
        }
        if(d_bl < m_bl)
        {
            bl = p;
            m_bl = d_bl;
        }
        if(d_br < m_br)
        {
            br = p;
            m_br = d_br;
        }
    }

    // draw rectangle
    line(sample, tl, tr, Scalar(0, 255, 255), 3);
    line(sample, tr, br, Scalar(0, 255, 255), 3);
    line(sample, br, bl, Scalar(0, 255, 255), 3);
    line(sample, bl, tl, Scalar(0, 255, 255), 3);
    imshow("window", sample);
    waitKey(0);

    return 0;
}

you just need to try some another approach for the last step (find extreme defects)

Answer 2

Another solution/explanation based on Hough:

1) preprocessing - applying hough as is without some "cleaning" will generally lead to a lot of noise in the Hough domain. You can do preprocessing such as first perform average filter, then after edge detection (Canny edge detector for instance, of simpler such as Sobel). Also as marked in comments.

2) use parameteric hough transform - H( rho, theta)

3) use threshold on H to be left with only 10 points.

4) in the H - pick the 4 points that has the biggest rho. (rho is one of the axes, and represent the distance from the centre of the image in the parameteric representation of the line)

5) The 4 picked points are the 4 lines of the contour in the image domain

As an alternative to Hough transform, I would like to point to look at the corner detection methods - Harris corner detector is the most frequently used (as I know) (but there are many others as well)-

open-cv_harris_detector

Answer 3

I have one idea:

1) perform Hough transform, and by doing so all the straight lines will fall into a point in the transform domain. I noticed that the line is not really straight, so remember to perform averaging filtering on the hough transform image or when you perform hough transform reduce the sampling rate.

2) analyze the hough transform image and try to find local maximum points in the nearly horizontal direction and nearly vertical direction respectively. If this goes on well, there should have 5 local maximum points on both direction.

3) Among these local maximum points in each direction, select the two points that lead to the maximum distance when they are transformed into lines in the image domain.

4) With selected lines, calculate the intersections of the lines. They correspond to the corners of the largest rectangle.