How to identify incomplete rectangles in openCV

Question

How would I go around identifying and extracting rectangles from an image such as the one shown below.

Note that my rectangles might be incomplete and have some missing edges and some sides might be partial lines.

Thanks !

Faludi

this is part of psychology research called "Gestalt psychology". According to wikipedia, you are looking for the "law of closure". One of the first google hits is: users.acin.tuwien.ac.at/arichtsfeld/files/… but maybe you can find more after some research using those keywords. – Why

Phew. Way beyond my scope of understanding. But I'll check it out if I don't get easier solutions ! Thanks – Faludi

I would say in general it's not a simple task! But there might be simple heuristics sufficient for your application. – Why

Alan Gibson shows some very useful techniques for mending broken lines (albeit using ImageMagick) on the following page - I am sure they could be readily adapted to OpenCV im.snibgo.com/mendbrkln.htm – Moreira

Answer 1

This can be solved using morphological operations such as eroding and dilating. This two operations will help creating closed rectangles. After that you can use the tutorial from this page to detect simple shapes such as rectangles.

I implemented a quick demo which worked for the image you provided.

---

main.py:

import cv2
import numpy as np
from shapeDetector import ShapeDetector
import imutils

img = cv2.imread('t.png')
kernel = np.ones((5,5),np.uint8)
erosion = cv2.erode(img,kernel,iterations = 10)
dilate = cv2.dilate(erosion,kernel,iterations = 10)

The erosion thickens all the lines, so to get back to a normal width we need to dilate after eroding. I recommend to comment the dilate operation once to see how erode works and vice versa. This operations will transform your image like this

The detection algorithm I used expects white lines on black background. Thats why we need to invert the image.

cv2.bitwise_not ( dilate, dilate )

After that, we can use the code from the tutorial.

image = dilate
resized = imutils.resize(image, width=300)
ratio = image.shape[0] / float(resized.shape[0])

# convert the resized image to grayscale, blur it slightly,
# and threshold it
gray = cv2.cvtColor(resized, cv2.COLOR_BGR2GRAY)
blurred = cv2.GaussianBlur(gray, (5, 5), 0)
thresh = cv2.threshold(blurred, 60, 255, cv2.THRESH_BINARY)[1]
#thresh = dilate
# find contours in the thresholded image and initialize the
# shape detector
cnts = cv2.findContours(thresh.copy(), cv2.RETR_EXTERNAL,
    cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if imutils.is_cv2() else cnts[1]
sd = ShapeDetector()

# loop over the contours
for c in cnts:
    # compute the center of the contour, then detect the name of the
    # shape using only the contour
    M = cv2.moments(c)
    cX = int((M["m10"] / M["m00"]) * ratio)
    cY = int((M["m01"] / M["m00"]) * ratio)
    shape = sd.detect(c)

    # multiply the contour (x, y)-coordinates by the resize ratio,
    # then draw the contours and the name of the shape on the image
    c = c.astype("float")
    c *= ratio
    c = c.astype("int")
    cv2.drawContours(image, [c], -1, (0, 255, 0), 2)
    cv2.putText(image, shape, (cX, cY), cv2.FONT_HERSHEY_SIMPLEX,
        0.5, (255, 255, 255), 2)

    # show the output image
    cv2.imshow("Image", image)
    cv2.waitKey(0)

---

shapeDetector.py:

# import the necessary packages
import cv2

class ShapeDetector:
    def __init__(self):
        pass

    def detect(self, c):
        # initialize the shape name and approximate the contour
        shape = "unidentified"
        peri = cv2.arcLength(c, True)
        approx = cv2.approxPolyDP(c, 0.04 * peri, True)
        # if the shape is a triangle, it will have 3 vertices
        if len(approx) == 3:
            shape = "triangle"

        # if the shape has 4 vertices, it is either a square or
        # a rectangle
        elif len(approx) == 4:
            # compute the bounding box of the contour and use the
            # bounding box to compute the aspect ratio
            (x, y, w, h) = cv2.boundingRect(approx)
            ar = w / float(h)

            # a square will have an aspect ratio that is approximately
            # equal to one, otherwise, the shape is a rectangle
            shape = "square" if ar >= 0.95 and ar <= 1.05 else "rectangle"

        # if the shape is a pentagon, it will have 5 vertices
        elif len(approx) == 5:
            shape = "pentagon"

        # otherwise, we assume the shape is a circle
        else:
            shape = "circle"

        # return the name of the shape
        return shape

---

Result:

Donielle

@Jeru Luke The question says: "How would I go around identifying and extracting rectangles [...] . Note that my rectangles MIGHT be incomplete [...]. So I feel like my answer suits it very well. – Donielle

Answer 2

I would recommend taking a Hough transform to identify angles of interest, then identify pairs of angles with large mass in Hough space differing by exactly 90 degrees, then loop over each such pair, identify significantly represented spatial offsets for all such "vertical" and "horizontal" line candidates, and use some heuristics from there to identify likely rectangles from these orthongonal line candidates.

For example, after identifying a set of lines for a given angle pair, you likely have a relatively small number of lines to evaluate, so you can do something more like a brute force O(N^2) search through pairs of lines to look for relevant corners (defined as being "empty" on one side and "dense" on the other in both directions), and then match the corners up to make a list of rectangles.

Transsonic