# Finding squares in Image

I need to find the squares in an image using OpenCV (no problem in matlab or any other, generally what i expect are some ideas).

Consider the test image below :

**I need to find those coloured squares in above image accurately** (not the white long strips).

**What I have done :**

I applied the common method (which comes with OpenCV samples), ie

**find contours**in all color planes, approximate it and check for number of elements=4. It works to some extend that, few squares are detected, especially the dark ones.Next step i did was

**prediction**. ie*this arrangement is fixed*. So, if some are obtained, I can predict remaining ones. It also worked to some further extend. But accuracy was very bad.

But I feel prediction is not a good method here and it doesn't always provide accurate answers as given by the first step.

**What I need :**

1) Is there any other better methods to detect these squares more accurately? Or multiple methods?

One important point is that, **time is not a problem here**. Algorithm can be slow, it doesn't matter. **But accuracy is the major criteria.**

Sometimes, images can be much more blurry.

And one of the major problem I faced is that some squares have almost similar color as that of background (check column 3 first and second squares).

Looking for ideas, thanks in advance

**UPDATE :**

Below is the maximum accurate result I got :

Of course, the result image is resized a little bit.

UPDATE 2 :

I have given a much more better solution in my answer below: https://dsp.stackexchange.com/a/7526/818

## Answers

A first attempt using Matlab:

im = imread('squares.jpg'); im2 = rgb2gray(im); se = strel('disk', 15); for i = 1:16; t = 60+i*5; % try out a range of bw thresholds to see what works best labelled = bwlabel(im2>t); % label regions in the BW image closed = imclose(labelled, se); % close small regions cleared = imclearborder(~closed,4); % clear regions touching the border subplot(4,4,i); imshow(cleared); title(['T = ' num2str(t)]); end

Results in the following regions:

As you can see, selecting the threshold that results in the highest number of regions (T=120) would already give 7 correct locations, some merged locations, one false positive and two false negatives.

This was a fairly simple attempt but I think it shows that the approach works. Adding some stuff to break up elongated regions, or doing this for each color channel separately are just a couple of the things you could do to improve on this.

It would also help if you provided a few more test images.

I had tried something else to improve my result in question. Below solution is on the assumption that first square(orange) is always detected in step 1. And it is practical due to its high contrast color compare to background. Even the result I showed in question has detected it correctly

**Step 1 : Find as many squares possible**

I split the image to R,G,B,H,S,V planes and thresholded the image for different threshold values like multiples of 25. For each image, I found squares in it, and put them on a **"mask image"**. I also found average height and width of the square.

mask image (Total 7/12 squares detected) :

**Step 2 : Form a grid of squares**

Next I found the centroids of these squares in mask image. Sorted them and found the centroid of first square(orange). From close analysis, we can see the gap between two squares is a square in both horizontal and vertical direction. So this way, I made a grid of squares like below and called it **ideal_squares** (it is just a name, it doesn't mean this is the output I need):

ideal_squares :

**Step 3: Remap the ideal_image**

Now we have the ideal_squares centroids and original centroids. I found out the correct matches for each original centroid from ideal_centroids (by taking euclidean distance between them). Then I used Scipy interpolate.griddata for interpolation and remapped ideal_image as per the centroid values (it is almost same as warping done in these Q&A : **How to remove convexity defects in sudoku square** & **Image transformation in OpenCV**). So below is the output I got :

Output :

**Step 4 : OR operate above output with mask image from first step**

Now you can see all the squares are detected, but with a problem mentioned below :

**Problem :**

Look at the output of the Step 3, ie remapped image of square grid. Except two central squares, all other squares are clipped. It is a problem associated with this remapping. I am not sure where is the problem, with scipy.interpolate.griddata() or cv2.remap(). I thought the whole image will be warped, but it is not. It warps only image inside the centroids we gave. If I can correct that, the output will be OK.

So if someone knows a good idea for that, most welcome !!!

Note: This method is going to be really slow.

Generate a mask that looks like the contours of a ideal object. Similar to this:

then slide (position,scale,rotation) the mask over the image and match it with the contour of the real image (perhaps blurred a bit to get softer response) to calculate how similar they are, the (position,scale,rotation) with the highest similarity response should be the (position,scale,rotation) of the real object.

The method doesn't mind squares blending into the background or even partial occlusions of the object, since it considers the entire object.

I have personally used this method successfully to track a mouse snout and whiskers, but I had some presumptions like it was close to the last known position etc. But I think you can bring down the search-space by applying some assumptions like: possible sizes of the object in the camera, how far of from the center it can be or rotation <10degrees etc.

Step 1: Whatever final binary image you are getting from analyzing in B,G,R,H,S,V plane, in that image do a blob counting algorithm.

Step 2: Find the largest blob on basis of area or contour length. Since your blobs will be mostly parallelogram types so area or contour, any one will do.

Step 3: With the largest blob (since largest blob is the best blob resembling your real world squares) try to find the orientation of the blob...this you can get by a fitting a best fit rectangle OR you can get the corner points...get the slope of the lines joining them (in both horizon and vertical direction).

Step 4: Once you get the two slopes draw two lines running through the axis of the blob. for axis you can average the corner points or you can use the centroid (center of mass)...I would go with average of corner points...

Step 5: Since in each horizontal and vertical direction, spacing is equal (ideally horizontal and vertical spacing are also equal as it comes from your ideal square picture but we will not assume it..) just need to locate the possible centroids of the other parallelograms

**BOTTOM LINE:** If any one square gets detected perfectly you can make the whole grid. Just keep marking centers at an interval of 2H (H = horizontal width of biggest blob) along the horizontal axis of the biggest blob and at an interval of 2V (V = vertical height of biggest blob) vertically along the vertical axis of the blob.

Some pics to support

this arrangement is fixed

I don't really know what kind of prediction you did before, but have you tried to focus on the white long strips as a root. Then (if 3 columns of squares are equal-sized), you can detect the height of a square (distance between the two strips) and you can detect the max and min area (height and width) in the image.

Then, try to detect the most common colour inside your whole square and set it to a "non-square" area. The rest is supposed to be the squares you are looking for.

I would suggest using the Hough transform, which is a very robust algorithm for finding simple parametric shapes e.g. lines, circles etc. Detection of lines would be best in your case. You could find the sides of the long white sripes at least; then, with any corner extractor algorithm (Harris or maybe even SIFT or SURF) you could find corners along those lines, even using the fact that the squares are approximately equally spaced.

I tried this problem using opencv, python. Approach involves masking image based on the colors, followed by finding suitable contours.

Code: https://github.com/rbhambriiit/computer_vision/blob/master/find_color_box

[ Missed 1 box but that should come by tuning the masking function]