How to discard overlapping rectangles in an image?

user_13905071 0
Viewed 462

I used the openCV library to detect an object of the image (Fig 1), see below. Fig 1

To do this, I have written the following codes:

import matplotlib.pyplot as plt
import cv2 

# source data
img_file= "Fig1.jpg"

# create an OpenCV image
img= cv2.imread(img_file)

# convert color image to grey image
gray_img=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

im_gauss = cv2.GaussianBlur(gray_img, (5, 5), 0)
ret, thresh = cv2.threshold(im_gauss, 127, 255, 0)
# get contours
contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

margin = 40
# calculate area and filter 
for con in contours:
    area = cv2.contourArea(con)
    if 100 < area < 500:
        x,y,w,h = cv2.boundingRect(con)
        cv2.rectangle(img, (x-margin, y-margin), (x + w+margin, y + h+margin), (0,255,0), 2)
        
plt.imshow(img, cmap='gray')

These codes will able to give you an image with the detected object see below figure Fig 2.

Now here you can see, while detecting objects, some rectangles are overlapping. This is not the expected outcome. I want a Figure which discards all overlap rectangles and comes with another figure that includes only those rectangle which is not overlapping. Any idea how to do this? Thanks in advance.

computer-vision opencv python
1 Answers

Assuming you have x, y, width, and height for each rectangle, you'll need pairwise comparisons for each two rectangles, checking for overlaps by comparing if

  • x of rectangle #1 is between x and x + width of rectangle #2, or
  • y of rectangle #1 is between y and y + height of rectangle #2, or
  • ...

Fortunately, you can use NumPy's vectorization abilities to avoid nested loops.

In the following code, I generate some random rectangles, and filter out those overlapping:

import cv2
import numpy as np

# Randomly generate n white rectangles on black background
n = 20
rects = [[np.random.randint(0, 350),
          np.random.randint(0, 250),
          np.random.randint(10, 50),
          np.random.randint(10, 50)] for i in range(n)]

img = np.zeros((300, 400), np.uint8)

for rect in rects:
    img = cv2.rectangle(img, (rect[0], rect[1]),
                        (rect[0] + rect[2], rect[1] + rect[3]), 255, 1)

# Calculate left, right, top, bottom limits
rects = np.array(rects)
left = np.expand_dims(rects[:, 0], axis=1)
right = np.expand_dims(rects[:, 0] + rects[:, 2], axis=1)
top = np.expand_dims(rects[:, 1], axis=1)
bottom = np.expand_dims(rects[:, 1] + rects[:, 3], axis=1)

# Check for left limit intrusions, right limit intrusions, ...
check_l = (left <= left.T) & (left.T <= right)
check_r = (left <= right.T) & (right.T <= right)
check_t = (top <= top.T) & (top.T <= bottom)
check_b = (top <= bottom.T) & (bottom.T <= bottom)

# Check for combinations of left-top intrusions, left-bottom intrusions, ...
check_lt = check_l & check_t
check_lb = check_l & check_b
check_rt = check_r & check_t
check_rb = check_r & check_b

# Get all combinations; get rid of self identical matches
check = check_lt | check_lb | check_rt | check_rb
check = np.bitwise_xor(check, np.eye(n).astype(bool))
check = np.argwhere(check)

# Get unique indices of corrupted rectangles
corrupted = np.unique(check)

# Draw cleaned image
img_clean = np.zeros_like(img)
for i, rect in enumerate(rects):
    if i not in corrupted:
        img_clean = cv2.rectangle(img_clean, (rect[0], rect[1]),
                                  (rect[0] + rect[2], rect[1] + rect[3]), 255, 1)

# Output
cv2.imshow('Original image', img)
cv2.imshow('Cleaned image', img_clean)
cv2.waitKey(0)
cv2.destroyAllWindows()

First, let's have a look at the "input" and "output":

Input

Output

Basically, the left, right, top, and bottom limit of each rectangle is computed. Then, each combination of rectangle #1 "intrudes" into rectangle #2 from the left, or from the top, or from the right, and so on, is calculated.

Several bool matrices of size (n, n), with n is the number of rectangles, are stored intermediately, but I guess, for n <= 2000 or so, the memory consumption should be negligible. Due to the vectorization, this approach is quite fast.

----------------------------------------
System information
----------------------------------------
Platform:      Windows-10-10.0.16299-SP0
Python:        3.9.1
NumPy:         1.20.2
OpenCV:        4.5.1
----------------------------------------
user_110899320
Related