Advanced square detection (with connected region)

Question

if the squares has connected region in image, how can I detect them.

I have tested the method mentioned in OpenCV C++/Obj-C: Advanced square detection

It did not work well.

Any good ideas ?

import cv2
import numpy as np

def angle_cos(p0, p1, p2):
    d1, d2 = (p0-p1).astype('float'), (p2-p1).astype('float')
    return abs( np.dot(d1, d2) / np.sqrt( np.dot(d1, d1)*np.dot(d2, d2) ) )

def find_squares(img):
    squares = []
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    # cv2.imshow("gray", gray)

    gaussian = cv2.GaussianBlur(gray, (5, 5), 0)

    temp,bin = cv2.threshold(gaussian, 80, 255, cv2.THRESH_BINARY)
    # cv2.imshow("bin", bin)

    contours, hierarchy = cv2.findContours(bin, cv2.RETR_CCOMP, cv2.CHAIN_APPROX_SIMPLE)

    cv2.drawContours( gray, contours, -1, (0, 255, 0), 3 )

    #cv2.imshow('contours', gray)
    for cnt in contours:
        cnt_len = cv2.arcLength(cnt, True)
        cnt = cv2.approxPolyDP(cnt, 0.02*cnt_len, True)
        if len(cnt) == 4 and cv2.contourArea(cnt) > 1000 and cv2.isContourConvex(cnt):
            cnt = cnt.reshape(-1, 2)
            max_cos = np.max([angle_cos( cnt[i], cnt[(i+1) % 4], cnt[(i+2) % 4] ) for i in xrange(4)])
            if max_cos < 0.1:
                squares.append(cnt)
    return squares

if __name__ == '__main__':
    img = cv2.imread('123.bmp')

    #cv2.imshow("origin", img)

    squares = find_squares(img)  
    print "Find %d squres" % len(squares)
    cv2.drawContours( img, squares, -1, (0, 255, 0), 3 )
    cv2.imshow('squares', img)

    cv2.waitKey()

I use some method in the opencv example, but the result is not good.

Solution 1

Applying a Watershed Transform based on the Distance Transform will separate the objects:

Handling objects at the border is always problematic, and often discarded, so that pink rectangle at top left not separated is not a problem at all.

Given a binary image, we can apply the Distance Transform (DT) and from it obtain markers for the Watershed. Ideally there would be a ready function for finding regional minima/maxima, but since it isn't there, we can make a decent guess on how we can threshold DT. Based on the markers we can segment using Watershed, and the problem is solved. Now you can worry about distinguishing components that are rectangles from those that are not.

import sys
import cv2
import numpy
import random
from scipy.ndimage import label

def segment_on_dt(img):
    dt = cv2.distanceTransform(img, 2, 3) # L2 norm, 3x3 mask
    dt = ((dt - dt.min()) / (dt.max() - dt.min()) * 255).astype(numpy.uint8)
    dt = cv2.threshold(dt, 100, 255, cv2.THRESH_BINARY)[1]
    lbl, ncc = label(dt)

    lbl[img == 0] = lbl.max() + 1
    lbl = lbl.astype(numpy.int32)
    cv2.watershed(cv2.cvtColor(img, cv2.COLOR_GRAY2BGR), lbl)
    lbl[lbl == -1] = 0
    return lbl


img = cv2.cvtColor(cv2.imread(sys.argv[1]), cv2.COLOR_BGR2GRAY)
img = cv2.threshold(img, 0, 255, cv2.THRESH_OTSU)[1]
img = 255 - img # White: objects; Black: background

ws_result = segment_on_dt(img)
# Colorize
height, width = ws_result.shape
ws_color = numpy.zeros((height, width, 3), dtype=numpy.uint8)
lbl, ncc = label(ws_result)
for l in xrange(1, ncc + 1):
    a, b = numpy.nonzero(lbl == l)
    if img[a[0], b[0]] == 0: # Do not color background.
        continue
    rgb = [random.randint(0, 255) for _ in xrange(3)]
    ws_color[lbl == l] = tuple(rgb)

cv2.imwrite(sys.argv[2], ws_color)

From the above image you can consider fitting ellipses in each component to determine rectangles. Then you can use some measurement to define whether the component is a rectangle or not. This approach has a greater chance to work for rectangles that are fully visible, and will likely produce bad results for partially visible ones. The following image shows the result of such approach considering that a component is a rectangle if the rectangle from the fitted ellipse is within 10% of component's area.

# Fit ellipse to determine the rectangles.
wsbin = numpy.zeros((height, width), dtype=numpy.uint8)
wsbin[cv2.cvtColor(ws_color, cv2.COLOR_BGR2GRAY) != 0] = 255

ws_bincolor = cv2.cvtColor(255 - wsbin, cv2.COLOR_GRAY2BGR)
lbl, ncc = label(wsbin)
for l in xrange(1, ncc + 1):
    yx = numpy.dstack(numpy.nonzero(lbl == l)).astype(numpy.int64)
    xy = numpy.roll(numpy.swapaxes(yx, 0, 1), 1, 2)
    if len(xy) < 100: # Too small.
        continue

    ellipse = cv2.fitEllipse(xy)
    center, axes, angle = ellipse
    rect_area = axes[0] * axes[1]
    if 0.9 < rect_area / float(len(xy)) < 1.1:
        rect = numpy.round(numpy.float64(
                cv2.cv.BoxPoints(ellipse))).astype(numpy.int64)
        color = [random.randint(60, 255) for _ in xrange(3)]
        cv2.drawContours(ws_bincolor, [rect], 0, color, 2)

cv2.imwrite(sys.argv[3], ws_bincolor)

Solution 2

Solution 1:

Dilate your image to delete connected components. Find contours of detected components. Eliminate contours which are not rectangles by introducing some measure (ex. ratio perimeter / area).

This solution will not detect rectangles connected to borders.

Solution 2:

Dilate to delete connected components. Find contours. Approximate contours to reduce their points (for rectangle contour should be 4 points). Check if angle between contour lines is 90 degrees. Eliminate contours which have no 90 degrees.

This should solve problem with rectangles connected to borders.

Solution 3

You have three problems:

1. The rectangles are not very strict rectangles (the edges are often somewhat curved)
2. There are a lot of them.
3. They are often connected.

It seems that all your rects are essentially the same size(?), and do not greatly overlap, but the pre-processing has connected them.

For this situation the approach I would try is:

1. dilate your image a few times (as also suggested by @krzych) - this will remove the connections, but result in slightly smaller rects.
2. Use scipy to label and find_objects - You now know the position and slice for every remaining blob in the image.
3. Use minAreaRect to find the center, orientation, width and height of each rectangle.

You can use step 3. to test whether the blob is a valid rectangle or not, by its area, dimension ratio or proximity to the edge..

This is quite a nice approach, as we assume each blob is a rectangle, so minAreaRect will find the parameters for our minimum enclosing rectangle. Further we could test each blob using something like humoments if absolutely neccessary.

Here is what I was suggesting in action, boundary collision matches shown in red.

Code:

import numpy as np
import cv2
from cv2 import cv
import scipy
from scipy import ndimage

im_col = cv2.imread('jdjAf.jpg')
im = cv2.imread('jdjAf.jpg',cv2.CV_LOAD_IMAGE_GRAYSCALE)

im = np.where(im>100,0,255).astype(np.uint8)
im = cv2.erode(im, None,iterations=8)
im_label, num = ndimage.label(im)
for label in xrange(1, num+1):
    points = np.array(np.where(im_label==label)[::-1]).T.reshape(-1,1,2).copy()
    rect = cv2.minAreaRect(points)
    lines = np.array(cv2.cv.BoxPoints(rect)).astype(np.int)
    if any([np.any(lines[:,0]<=0), np.any(lines[:,0]>=im.shape[1]-1), np.any(lines[:,1]<=0), np.any(lines[:,1]>=im.shape[0]-1)]):
        cv2.drawContours(im_col,[lines],0,(0,0,255),1)
    else:
        cv2.drawContours(im_col,[lines],0,(255,0,0),1)

cv2.imshow('im',im_col)
cv2.imwrite('rects.png',im_col)
cv2.waitKey()

I think the Watershed and distanceTransform approach demonstrated by @mmgp is clearly superior for segmenting the image, but this simple approach can be effective depending upon your needs.

Comments

[fraxel]

yep, true, really nice approach, +1. Its horribly fiddly to get the image indices into the correct format, I used to use the same zip unpack method you show here, but I recently realised it can be a lot slower than transposing and copying (should speed be important..) Unfortunetly, copying seems to be required to avoid an opencv exception (for me at least)..

[mmgp]

The difference is that numpy works by default with (y, x) coords, and OpenCV expects (x, y). @fraxel I didn't measure the performance, but it is likely that the updated code is better in that specific point.

[fraxel]

@mmgp - yeah I know, its damn annoying - But thanks again, your update helps me out! Its is a good deal quicker than your previous approach, and mine too. I will be using that,.. and watershed (should I ever need it..) in future :)

[Yang]

Thank you very much, I think the method is faster then the watershed method, Can you give some comment on the code? like what does "ndimage.label" mean? also "np.array(np.where(im_label==label)[::-1]).T.reshape(-1,1,2)‌​.copy()" ? Thank you for aswer ~

[Yang]

Also "any([np.any(lines[:,0]<=0), np.any(lines[:,0]>=im.shape[1]-1), np.any(lines[:,1]<=0), np.any(lines[:,1]>=im.shape[0]-1)])" I can not understand easily.Thanks!

[fraxel]

@Yang - hey, sure heres a shot: ndimage.label(im) is used to segment the image: every unconnected blobs values are replaced sequentially by an integer, resulting in a new labelled image im_label. np.where(im_label==label) takes this new labelled image and returns the indices of every pixel in that image that equals label - ie. all of the index values for a single blob - note that we are iterating through the blobs, by only considering one label value at a time. The .T.reshape(-1,1,2).copy() is a fiddle to get the data into the correct format to be accepted by minAreaRect

[fraxel]

@Yang - any is a logical operator, equivalent to chained or's. The conditions within it are checking to see if any of the rectangle points fall on or beyond the areas of the image, because if they do then we know its a bordering rectangle, so we colour it red, or can discard it, or whatever... hope that helps ;)

[mmgp]

@Yang are you aware that the answer accepted is not solving the problem in any way ? First, it identifies every component as a rectangle no matter what they are. Second, it arbitrarily erodes n times to disconnect components, this is just waiting to fail. I don't know what is too slow for you, it was never mentioned, it runs fast enough to me.

[Yang]

@mmgp Thanks for your answer, I used your code, it will take about 30s on my computer, the result is really amazing! Also the dealing with the partially visible rects has some problems, I think the erode way can detect almost the position, and then I extend the 4 points, like add 1 pixel each time in the origin pic, to fit more accurate with the rect, can this solve the erode small problem? Thanks again for your help.

[mmgp]

@Yang you should consider changing the computer then, anything that takes more than one third of a second for this code is too outdated or possibly an embedded system. Either that or you are not running the code provided. I don't know what problems about partially visible rects you are mentioning, be clear about what you mean. It is not clear what you are asking in the comment either, but it looks like you don't know what each code is doing.

[Yang]

@mmgp Actually, the picture I used to run is about 15 times bigger then this one, maybe it is the reason that it takes about 30s to run. But the result is really amazing, finally I choose your method to solve my problem. Thanks a lot !

[mmgp]

@Yang thank you. There are faster algorithms for doing these same tasks if it is really crucial for the task.

[sayvortana]

@mmgp Can you implement it in C++? Thank