Efficient way to combine intersecting bounding rectangles

Question

I'm trying to simplify the following image using OpenCV:

What we have here are lots of red shapes. Some of them completely contain others. Some of them intersect their neighbors. My goal is to unify all intersecting shapes by replacing any two intersecting shapes with the bounding box of their union's polygon. (repeating until there are no more intersecting shapes).

By intersecting I mean also touching. Hope this makes it 100% clear:

I'm trying to do this efficiently using standard morphology operations; obviously it can be done naively in O(N^2), but that'll be too slow. Dilation doesn't help because some shapes are only 1px apart and I don't want them merged if they're not intersecting.

Answer 1

UPDATE: I misunderstood the question earlier. We don't want to remove rectangles which are completely inside others. We only want to replace the intersecting rectangles. Therefore for the first case, we have to do nothing.

New api (2.4.9) supports & and | operators.

From opencv doc:

• rect = rect1 & rect2 (rectangle intersection)
• rect = rect1 | rect2 (minimum area rectangle containing rect2 and rect3 )

It also supports equality comparision (==)

• rect == rect1

So it is now very easy to accomplish the task. For every pair of rectangle rect1 and rect2,

if((rect1 & rect2) == rect1) ... // rect1 is completely inside rect2; do nothing.
else if((rect1 & rect2).area() > 0) // they intersect; merge them.
    newrect = rect1 | rect2;
    ... // remove rect1 and rect2 from list and insert newrect.

UPDATE 2: (for translating in java)

I know java very little. I also never used the java API. I am giving here some psudo-code (which I think can be easily translated)

For & operator, we need a method which finds the intersect of two rectangles.

Method: Intersect (Rect A, Rect B)
left = max(A.x, B.x)
top  = max(A.y, B.y)
right = min(A.x + A.width, B.x + B.width)
bottom = min(A.y + A.height, B.y + B.height)
if(left <= right && top <= bottom) return Rect(left, top, right - left, bottom - top)
else return Rect()

For | operator, we need a similar method

Method: Merge (Rect A, Rect B)
left = min(A.x, B.x)
top  = min(A.y, B.y)
right = max(A.x + A.width, B.x + B.width)
bottom = max(A.y + A.height, B.y + B.height)
return Rect(left, top, right - left, bottom - top)

For == operator, we can use overloaded equals method.

Answer 2

To accomplish what you want we'll be using findContours. The key point here is to understand how it works when mode is set to CV_RETR_TREE. In this case, hierarchy is constructed in a way that every even depth level contains external contours, while odd depth levels contain internal contours. What we need here is to traverse the hierarchy tree printing the contours associated with even depth levels.

First we find the contours of an image called original

typedef std::vector<std::vector<cv::Point> > Contours;
typedef std::vector<cv::Vec4i> Hierarchy;

Contours contours;
Hierarchy hierarchy;
cv::findContours(original, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_NONE);

To print the external contours on an image called processed we need a recursive function.

void printExternalContours(cv::Mat img, Contours const& contours, Hierarchy const& hierarchy, int const idx)
{
    //for every contour of the same hierarchy level
    for(int i = idx; i >= 0; i = hierarchy[i][0])
    {
        //print it
        cv::drawContours(img, contours, i, cv::Scalar(255));

        //for every of its internal contours
        for(int j = hierarchy[i][2]; j >= 0; j = hierarchy[j][0])
        {
            //recursively print the external contours of its children
            printExternalContours(img, contours, hierarchy, hierarchy[j][2]);
        }
    }
}

printExternalContours(processed, contours, hierarchy, 0);

The result is shown bellow, where original and processed are displayed side by side.

If you absolutely need rectangular shapes, you just need to use boundingRect to get the minimum enclosing rectangle given a set of points (every single contour in this case) and use rectangle for the drawing. In other words, substitute

cv::drawContours(img, contours, i, cv::Scalar(255));

by

cv::rectangle(img, cv::boundingRect(contours[i]), cv::Scalar(255));

findContours expects a single 8-bit image, sou you could either make a gray image from your originals and then threshold it to get a perfect black background or, perhaps it would suffice to use the red channel in your case, just make sure the background is perfectly black.

Regarding the complexity of findContours, I can't attest it is any better than O(N^2), nor haven't I found any input on that after a quick google search, but I trust OpenCV implements the best known algorithm.

Answer 3

Given two bounding box contours in the form of (x,y,w,h), here's a function to create a single bounding box (assuming the boxes are touching or within each other). Returns (x,y,w,h) of the combined bounding box i.e, top-left x, top-left y, width, and height. Here's an illustration

(x1,y1)       w1                           (x3,y3)         w3
  ._____________________.                    .____________________________.
  |                     |                    |                            | 
  |                     |  h1                |                            |
  |   (x2,y2)           |                    |                            |
  |     ._______________|_______.      -->   |                            |
  |     |               |       |            |                            |  h3
  ._____|_______________.       |            |                            |
        |                       |  h2        |                            |
        |                       |            |                            |
        |           w2          |            |                            |
        ._______________________.            .____________________________.

Code

def combineBoundingBox(box1, box2):
    x = min(box1[0], box2[0])
    y = min(box1[1], box2[1])
    w = box2[0] + box2[2] - box1[0]
    h = max(box1[1] + box1[3], box2[1] + box2[3]) - y
    return (x, y, w, h)

---

Example

With these two bounding boxes,

>>> print(box1)
>>> print(box2)
(132, 85, 190, 231)
(264, 80, 121, 230)

>>> new = combineBoundingBox(box1, box2) 
>>> print(new)
(132, 80, 253, 236)

Here's the visual result: Before -> After