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

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.