How to check if four points form a rectangle

Question

I am working on a shape recognition app. At this moment a set of points (x,y) is determined by corner detector (red points, img. 2.). Four of these points (in red frames, img. 2.) are vertices of a rectangle (sometimes a little deformed rectangle). What would be the best way to find them among others?

Here is an example of an input image:

And it looks like this after corner detection:

Fleshy

Answer 1

This is not an answer to your question - it's just suggestion.

In my opinion corner detector is a bad way to detect rectangles - it will take much time to calculate all point distances as mathematician1975 suggested. You have to use another technique in this situation:

1. That stamp is violet color, so first thing you should do is color segmentation.
2. After you've done with step 1 you can use Houhg transform to detect lines on binary image. Or find all contours in image.
3. And the final step is to detect rectangle.

Update:

Here's another solution that should also work in gray images.

1. Do a threshold to convert image to 1bit (I used 200 from 255 as threshold).
2. Find all contours in new image which have area bigger than some constant (I took 1000).
3. Find bounding rectangle for each contour and do a check:

ContourArea / BoundingReactangleArea > constant

I take this constant as 0.9.

And this algorithm gave me next result:

Here's OpenCV code:

Mat src = imread("input.jpg"), gray, result;
vector<vector<Point> > contours;
vector<Vec4i> hierarchy;

result = Mat(src.size(), CV_8UC1);

cvtColor(src, src, CV_BGR2GRAY);
threshold(src, gray, 200, 255, THRESH_BINARY_INV);
findContours(gray, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0));

result = Scalar::all(0);
for (size_t i=0; i<contours.size(); i++)
{
    Rect rect = boundingRect(contours[i]);
    if (rect.area() > 1000)
    {
        double area = contourArea(contours[i]);
        if (area/rect.area() > 0.9)
        {
            drawContours(result, contours, i, Scalar(255), -1);
        }
    }
}

Strahan

Yeah, as you pointed out calculating all distances consumes a lot of time even for small input image. I have already checked that solution. Color segmentation would not be useful with grayscale images (examples are a bit confusing, sorry) but I used it for RGB ones. As for the Hough transform I did some tests and it works pretty well, but the detected lines do not intersects with each other as shown here: hough. – Fleshy

This work pretty well in most cases so I am going to mark it as answer. However in some situations it fails because there is no closed area. Morphological operations come in handy then, but for almost each case they need different parameters, which makes them not so useful. Any ideas how to solve that problem? Here is an example of such situation: click – Fleshy

@HighPerformanceMark you can use minAreaRect. – Strahan

Indeed, but that's not what your solution does. – Bermejo

@Fleshy what about changing threshold to 210? Or threshold can also be different in different situations? – Strahan

@HighPerformanceMark Yes, but if you take extreme points of contour area you can draw lines on image and then fill created holes inside of that area. – Fleshy

@Astor, threshold level takes values from 80 to 230 in other documents. – Fleshy

@Fleshy so you use Otsu threshold? Or some constant every time? – Strahan

I just got 10 images for testing, so I change it manually until it gives any results. – Fleshy

@Fleshy I mean do you set it for each image manually or you set one constant for all? If you set manually than use needed threshold (in that case 210 is acceptable). – Strahan

I set it manually for each image, it can't be done with one constant value for all, because in same cases there won't be any data to process (too high/low thresh). – Fleshy

So setting correct value will fix that issue with this image, isn't it? – Strahan

Yes it will, the problem is that the app should work without user input, so I will need to find three most common values for thresh and change it if there is no output area. This means additional computations, but should be alright. Thanks for help. – Fleshy

Answer 2

Calculate the set of 6 lengths that you will have between each pair of 4 distinct points. Within that set of 6 lengths if there are more than 3 distinct values, you do not have a rectangle (2 equal side lengths plus equal diagonal lengths)

Contrarious

Good solution, but not really useful in this exact problem. Calculating all distances takes a lot of time even if there is 100 points and I usually get around 2500. – Fleshy

WAIT A SECOND. You said you have FOUR points, not 2500. This answer tells you if FOUR points form a rectangle, and seems a valid solution for that task. If your problem is not as you describe, then you need to be more specific. – Forbearance

Yeah, but also said that these four points are not the only ones and I need to find proper points first. – Fleshy

@Fleshy I see - perhaps you could clarify the question a little as the question title itself asks for a way to detect rectangle from 4 points, not 4 out of an arbitrary number. – Contrarious

You can reduce the complexity a bit. First you could consider just 3 points - which need to be an right triangle (maybe use Pythagoras). Second for the fourth point in many cases it will be enough to calculate just one distance to exclude it. – Estimation

Answer 3

You are aware that by visually inspecting the point cloud you can already distinguish a multitude of rectangles? In other words, you will likely find many rectangles if you don't do a sort of pre-selection routine...

Anyway, aside from the method already given by @mathematician1975, you can also just check if the sides are (more or less) parallel.

Let's call @mathematician1975's method method 1 and parallel-check method 2. Then:

%# method 1: 
n1 = |u1-u2|    %#  3 sub., 3 mult, 2 add. per distance
n2 = |u3-u2|    %#  total of 6 distances to compute.
n3 = |u4-u3|    %#  then max 5+4+3+2+1 = 15 comp. to find unique distances
n4 = |u1-u4|    
n5 = |u4-u2|    %#  Total:
n6 = |u3-u1|    %#  12 sub., 18 mult., 12 add, 15 comp



%# method 2:
w1 = u1-u2       %#  3 subtractions per vector
w2 = u3-u2       %#  total of 4 vectors to compute 
w3 = u3-u2
w4 = u1-u4                
                        %#  12 sub.
abs(w1-w3) == [0 0 0]   %#  3 sub., 3 comp., 1 sign.
abs(w2-w4) == [0 0 0]   %#  3 sub., 3 comp., 1 sign.

                        %# Total: 18 sub., 6 comp. 2 sign.

Note that these are both worst-case; with a bit of bookkeeping you can drastically reduce the cost of both.

Note also that method 2 needs to know beforehand that the vertices are already in the right order. If this is not the case, it'll increase the cost by a factor of 4, which is more that method 1..

May I ask how you are computing the distances?

Loose

Yes I know that having that amount of points will form a lot of rectangles, but I am not sure if there is anything I can do about it at this stage (later on I will calculate some statistics that would allow me to choose only proper rectangles). The distance between two points is computed as Euclidean distance: distance = sqrt( (x2-x1)^2 + (y2-y1)^2 ); and I'm not sure if it is 2500x4, because you have to choose one point, then another 3, compute distances, then for the same fist point you choose another 3 points (different than the previous ones) that is way beyond 2500x4 combinations. – Fleshy

@Fleshy Try norm -- it should be a lot faster. Or, if you want, just leave out the square root -- comparing distance squared or distance doesn't matter. Or, use city-block distances: abs(x2-x1) + abs(y2-y1). This will give a very rough but way faster approximation to the distance, that, in case of a rectangle, will also have to be equal. – Loose

Answer 4

Consider you should have got number 8 but you got number 7, then you are going to add number 1 (called delta or error correction) to correct it.

In a similar manner have a delta rectangle coordinates to correct the rectangle. Check that point(coordinate) falls inside delta rectangle.

The rectangle coordinates are as mentioned below:

x+delta,y+delta
x-delta,y+delta
x+delta,y-delta
x-delta,y-delta

Let me know if this works fine for you or if you find a better solution

Maraschino