By dom


2012-05-10 11:40:55 8 Comments

A while ago I asked a question about square detection and karlphillip came up with a decent result.

Now I want to take this a step further and find squares which edge aren't fully visible. Take a look at this example:

example

Any ideas? I'm working with karlphillips code:

void find_squares(Mat& image, vector<vector<Point> >& squares)
{
    // blur will enhance edge detection
    Mat blurred(image);
    medianBlur(image, blurred, 9);

    Mat gray0(blurred.size(), CV_8U), gray;
    vector<vector<Point> > contours;

    // find squares in every color plane of the image
    for (int c = 0; c < 3; c++)
    {
        int ch[] = {c, 0};
        mixChannels(&blurred, 1, &gray0, 1, ch, 1);

        // try several threshold levels
        const int threshold_level = 2;
        for (int l = 0; l < threshold_level; l++)
        {
            // Use Canny instead of zero threshold level!
            // Canny helps to catch squares with gradient shading
            if (l == 0)
            {
                Canny(gray0, gray, 10, 20, 3); // 

                // Dilate helps to remove potential holes between edge segments
                dilate(gray, gray, Mat(), Point(-1,-1));
            }
            else
            {
                    gray = gray0 >= (l+1) * 255 / threshold_level;
            }

            // Find contours and store them in a list
            findContours(gray, contours, CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE);

            // Test contours
            vector<Point> approx;
            for (size_t i = 0; i < contours.size(); i++)
            {
                    // approximate contour with accuracy proportional
                    // to the contour perimeter
                    approxPolyDP(Mat(contours[i]), approx, arcLength(Mat(contours[i]), true)*0.02, true);

                    // Note: absolute value of an area is used because
                    // area may be positive or negative - in accordance with the
                    // contour orientation
                    if (approx.size() == 4 &&
                            fabs(contourArea(Mat(approx))) > 1000 &&
                            isContourConvex(Mat(approx)))
                    {
                            double maxCosine = 0;

                            for (int j = 2; j < 5; j++)
                            {
                                    double cosine = fabs(angle(approx[j%4], approx[j-2], approx[j-1]));
                                    maxCosine = MAX(maxCosine, cosine);
                            }

                            if (maxCosine < 0.3)
                                    squares.push_back(approx);
                    }
            }
        }
    }
}

4 comments

@user3452134 2014-10-29 06:27:50

  1. convert to lab space
  2. use kmeans for 2 clusters
  3. detect suqares one internal cluster it will solve many thing in the rgb space

@Andrey Rubshtein 2015-01-20 08:40:19

How would that be helpful?

@user3452134 2015-02-01 10:03:58

use command : cv::cvtColor(image, LABImage, CV_RGB2Lab); in the lab color you have more separation and it is less sensitive to light conditions.

@mevatron 2012-05-10 13:26:46

You might try using HoughLines to detect the four sides of the square. Next, locate the four resulting line intersections to detect the corners. The Hough transform is fairly robust to noise and occlusions, so it could be useful here. Also, here is an interactive demo showing how the Hough transform works (I thought it was cool at least :). Here is one of my previous answers that detects a laser cross center showing most of the same math (except it just finds a single corner).

You will probably have multiple lines on each side, but locating the intersections should help to determine the inliers vs. outliers. Once you've located candidate corners, you can also filter these candidates by area or how "square-like" the polygon is.

EDIT : All these answers with code and images were making me think my answer was a bit lacking :) So, here is an implementation of how you could do this:

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <iostream>
#include <vector>

using namespace cv;
using namespace std;

Point2f computeIntersect(Vec2f line1, Vec2f line2);
vector<Point2f> lineToPointPair(Vec2f line);
bool acceptLinePair(Vec2f line1, Vec2f line2, float minTheta);

int main(int argc, char* argv[])
{
    Mat occludedSquare = imread("Square.jpg");

    resize(occludedSquare, occludedSquare, Size(0, 0), 0.25, 0.25);

    Mat occludedSquare8u;
    cvtColor(occludedSquare, occludedSquare8u, CV_BGR2GRAY);

    Mat thresh;
    threshold(occludedSquare8u, thresh, 200.0, 255.0, THRESH_BINARY);

    GaussianBlur(thresh, thresh, Size(7, 7), 2.0, 2.0);

    Mat edges;
    Canny(thresh, edges, 66.0, 133.0, 3);

    vector<Vec2f> lines;
    HoughLines( edges, lines, 1, CV_PI/180, 50, 0, 0 );

    cout << "Detected " << lines.size() << " lines." << endl;

    // compute the intersection from the lines detected...
    vector<Point2f> intersections;
    for( size_t i = 0; i < lines.size(); i++ )
    {
        for(size_t j = 0; j < lines.size(); j++)
        {
            Vec2f line1 = lines[i];
            Vec2f line2 = lines[j];
            if(acceptLinePair(line1, line2, CV_PI / 32))
            {
                Point2f intersection = computeIntersect(line1, line2);
                intersections.push_back(intersection);
            }
        }

    }

    if(intersections.size() > 0)
    {
        vector<Point2f>::iterator i;
        for(i = intersections.begin(); i != intersections.end(); ++i)
        {
            cout << "Intersection is " << i->x << ", " << i->y << endl;
            circle(occludedSquare, *i, 1, Scalar(0, 255, 0), 3);
        }
    }

    imshow("intersect", occludedSquare);
    waitKey();

    return 0;
}

bool acceptLinePair(Vec2f line1, Vec2f line2, float minTheta)
{
    float theta1 = line1[1], theta2 = line2[1];

    if(theta1 < minTheta)
    {
        theta1 += CV_PI; // dealing with 0 and 180 ambiguities...
    }

    if(theta2 < minTheta)
    {
        theta2 += CV_PI; // dealing with 0 and 180 ambiguities...
    }

    return abs(theta1 - theta2) > minTheta;
}

// the long nasty wikipedia line-intersection equation...bleh...
Point2f computeIntersect(Vec2f line1, Vec2f line2)
{
    vector<Point2f> p1 = lineToPointPair(line1);
    vector<Point2f> p2 = lineToPointPair(line2);

    float denom = (p1[0].x - p1[1].x)*(p2[0].y - p2[1].y) - (p1[0].y - p1[1].y)*(p2[0].x - p2[1].x);
    Point2f intersect(((p1[0].x*p1[1].y - p1[0].y*p1[1].x)*(p2[0].x - p2[1].x) -
                       (p1[0].x - p1[1].x)*(p2[0].x*p2[1].y - p2[0].y*p2[1].x)) / denom,
                      ((p1[0].x*p1[1].y - p1[0].y*p1[1].x)*(p2[0].y - p2[1].y) -
                       (p1[0].y - p1[1].y)*(p2[0].x*p2[1].y - p2[0].y*p2[1].x)) / denom);

    return intersect;
}

vector<Point2f> lineToPointPair(Vec2f line)
{
    vector<Point2f> points;

    float r = line[0], t = line[1];
    double cos_t = cos(t), sin_t = sin(t);
    double x0 = r*cos_t, y0 = r*sin_t;
    double alpha = 1000;

    points.push_back(Point2f(x0 + alpha*(-sin_t), y0 + alpha*cos_t));
    points.push_back(Point2f(x0 - alpha*(-sin_t), y0 - alpha*cos_t));

    return points;
}

NOTE : The main reason I resized the image was so I could see it on my screen, and speed-up processing.

Canny

This uses Canny edge detection to help greatly reduce the number of lines detected after thresholding.

enter image description here

Hough transform

Then the Hough transform is used to detect the sides of the square. enter image description here

Intersections

Finally, we compute the intersections of all the line pairs. enter image description here

Hope that helps!

@karlphillip 2012-05-10 13:47:07

+1 Interesting approach.

@dom 2012-05-10 20:54:36

+1 Solid approach, I'll test it tomorrow. I need a robust solution, which is resistent to noise.

@mevatron 2012-05-10 21:15:17

Right now the code relies on thresholding to isolate the square. If you'd rather isolate the square post-intersection detection you'll need to start testing the intersection points maybe using cv::approxPoly as was already mentioned.

@iKT 2013-04-23 05:59:57

Hi @mevatron, How to do this in iOS (objective c) ?

@mehfoos yacoob 2013-08-21 15:46:02

Thanks for the idea. What about scenarios with multiple rectangles? Won't the intersections create a lot of false positives?

@Mukesh 2015-06-03 10:20:13

how to plot these corners points in device coordinates.currently i am able to find these cv::point which is not in device cordinates

@rew 2015-09-28 15:16:06

Doesn't this have a bug in acceptpair? If one theta is < minTheta and the other just above (less than 2*mintheta), the "deal with ..." lines will move one point "away" and leave the other alone.

@karlphillip 2012-05-10 13:28:30

1st: start experimenting with threshold techniques to isolate the white paper sheet from the rest of the image. This is a simple way:

Mat new_img = imread(argv[1]);

double thres = 200;
double color = 255;
threshold(new_img, new_img, thres, color, CV_THRESH_BINARY);

imwrite("thres.png", new_img);

but there are other alternatives that could provide better result. One is to investigate inRange(), and another is to detect through color by converting the image to the HSV color space.

This thread also provides an interest discussion on the subject.

2nd: after you execute one of this procedures, you could try to feed the result directly into find_squares():

An alternative to find_squares() is to implement the bounding box technique, which has the potential to provide a more accurate detection of the rectangular area (provided that you have a perfect result of threshold). I've used it here and here. It's worth noting that OpenCV has it's own bounding box tutorial.

Another approach besides find_squares(), as pointed by Abid on his answer, is to use the convexHull method. Check OpenCV's C++ tutorial on this method for code.

@mevatron 2012-05-10 13:43:06

+1 cool range of techniques here :)

@Abid Rahman K 2012-05-10 14:14:07

I tried to use convex hull method which is pretty simple.

Here you find convex hull of the contour detected. It removes the convexity defects at the bottom of paper.

Below is the code (in OpenCV-Python):

import cv2
import numpy as np

img = cv2.imread('sof.jpg')
img = cv2.resize(img,(500,500))
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

ret,thresh = cv2.threshold(gray,127,255,0)
contours,hier = cv2.findContours(thresh,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)

for cnt in contours:
    if cv2.contourArea(cnt)>5000:  # remove small areas like noise etc
        hull = cv2.convexHull(cnt)    # find the convex hull of contour
        hull = cv2.approxPolyDP(hull,0.1*cv2.arcLength(hull,True),True)
        if len(hull)==4:
            cv2.drawContours(img,[hull],0,(0,255,0),2)

cv2.imshow('img',img)
cv2.waitKey(0)
cv2.destroyAllWindows()

(Here, i haven't found square in all planes. Do it yourself if you want.)

Below is the result i got:

enter image description here

I hope this is what you needed.

@karlphillip 2012-05-10 14:47:33

+1 I have to upvote this one too for it's simplicity. Nice work!

@mevatron 2012-05-10 19:27:33

+1 I do like the simplicity of this approach.

@alandalusi 2012-11-28 07:12:02

@abidrahmank I tried to rewrite this code in C++ but it keeps failing, any ideas what the problem is? stackoverflow.com/questions/13599695/…

@user1914692 2013-12-02 07:37:13

If the bottle is white, then the contour will extend to the contour of the bottle, so the convexhull will not work.

@justin.yqyang 2018-01-11 09:37:35

this solution may fail when there are multiple squares

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] The Definitive C++ Book Guide and List

  • 2008-12-23 05:23:56
  • grepsedawk
  • 2018213 View
  • 4251 Score
  • 1 Answer
  • Tags:   c++ c++-faq

5 Answered Questions

21 Answered Questions

[SOLVED] What is the "-->" operator in C++?

23 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

33 Answered Questions

1 Answered Questions

[SOLVED] openCV: cannot detect small shapes using findContours

  • 2017-10-08 07:40:30
  • Vic
  • 643 View
  • 1 Score
  • 1 Answer
  • Tags:   python opencv

1 Answered Questions

[SOLVED] OpenCV Java : Card Extraction from Image

0 Answered Questions

1 Answered Questions

[SOLVED] OpenCV C++/Obj-C: Proper object detection

1 Answered Questions

[SOLVED] How to find contours in an image in OpenCV?

Sponsored Content