Advanced square detection (with connected region)

Yang picture Yang · Feb 21, 2013 · Viewed 9.2k times · Source

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 ?

squares that has Connected region

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.

Answer

mmgp picture mmgp · Feb 21, 2013

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

enter image description here

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.

enter image description here

# 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)