Finding the union of multiple overlapping rectangles - OpenCV python

Question

I have several overlapping bounding boxes that encompass a single object, however they overlap minimally in some places. Taken as a whole, they encompass the entire object, but openCV's groupRectangles function does not return a box encompassing the object. The bounding boxes I have are shown in blue, and bounding boxes I would like to return are shown in red here

I would like to get the union of only the overlapping rectangles but am unsure about how to iterate through the list without combining every rectangle. I have union and intersect functions shown below, and a list of the rectangles represented by (x y w h), where x and y are the coordinates of the top left corner of the box.

def union(a,b):
  x = min(a[0], b[0])
  y = min(a[1], b[1])
  w = max(a[0]+a[2], b[0]+b[2]) - x
  h = max(a[1]+a[3], b[1]+b[3]) - y
  return (x, y, w, h)

def intersection(a,b):
  x = max(a[0], b[0])
  y = max(a[1], b[1])
  w = min(a[0]+a[2], b[0]+b[2]) - x
  h = min(a[1]+a[3], b[1]+b[3]) - y
  if w<0 or h<0: return () # or (0,0,0,0) ?
  return (x, y, w, h)

My function for combining is currently as follows:

def combine_boxes(boxes):
    noIntersect = False
    while noIntersect == False and len(boxes) > 1:
        a = boxes[0]
        print a
        listBoxes = boxes[1:]
        print listBoxes
        index = 0
        for b in listBoxes:
            if intersection(a, b):
                newBox = union(a,b)
                listBoxes[index] = newBox
                boxes = listBoxes
                noIntersect = False
                index = index + 1
                break
            noIntersect = True
            index = index + 1

    print boxes
    return boxes.astype("int")

This gets most of the way there, as shown here

there are still a few nested bounding boxes that I'm not sure how to continue iterating through.

Answer 1

I haven't worked with openCV, so the object may need more mangling, but maybe use itertools.combinations to make the combine_boxes function simpler:

import itertools
import numpy as np
def combine_boxes(boxes):
    new_array = []
    for boxa, boxb in itertools.combinations(boxes, 2):
        if intersection(boxa, boxb):
            new_array.append(union(boxa, boxb))
        else:
            new_array.append(boxa)
    return np.array(new_array).astype('int')

EDIT (you may actually need zip instead)

for boxa, boxb in zip(boxes, boxes[1:])

everything is the same.

Answer 2

Thank you, salparadise (https://stackoverflow.com/users/62138/salparadise). Very helpful to find a way out.

But the solution looks rectangles could be repeated added into the new_array. e.g. A B C has no intersection to each other, A B C will be added twice respectively. So the new_array will contain A B A C B C. Please refer to the revised code. Hope it helps.

Had tested it on multiple test cases. It looks working fine.

    def merge_recs(rects):
        while (1):
            found = 0
            for ra, rb in itertools.combinations(rects, 2):
                if intersection(ra, rb):
                    if ra in rects:
                        rects.remove(ra)
                    if rb in rects:
                        rects.remove(rb)
                    rects.append((union(ra, rb)))
                    found = 1
                    break
            if found == 0:
                break

        return rects