OpenCV groupRectangles - getting grouped and ungrouped rectangles

Question

I'm using OpenCV and want to group together rectangles that have significant overlap. I've tried using groupRectangles for this, which takes a group threshold argument. With a threshold of 0 it doesn't do any grouping at all, and with a threshold of 1 is only returns rectangles that were the result of at least 2 rectangles. For example, given the rectangles on the left in the image below you end up with the 2 rectangles on the right:

What I'd like to end up with is 3 rectangles. The 2 on the right in the image above, plus the rectangle in the top right of the image to the left that doesn't overlap with any other rectangles. What's the best way to achieve this?

Answer 1

The solution I ended up going with was to duplicate all of the initial rectangles before calling groupRectangles. That way every input rectangle is guaranteed to be grouped with at least one other rectangle, and will appear in the output:

int size = rects.size();
for( int i = 0; i < size; i++ )
{
    rects.push_back(Rect(rects[i]));
}
groupRectangles(rects, 1, 0.2);

Answer 2

A little late to the party, however "duplicating" solution did not properly work for me. I also had another problem where merged rectangles would overlap and would need to be merged.

So I came up with an overkill solution (might require C++14 compiler). Here's usage example:

std::vector<cv::Rect> rectangles, test1, test2, test3;

rectangles.push_back(cv::Rect(cv::Point(5, 5), cv::Point(15, 15)));
rectangles.push_back(cv::Rect(cv::Point(14, 14), cv::Point(26, 26)));
rectangles.push_back(cv::Rect(cv::Point(24, 24), cv::Point(36, 36)));

rectangles.push_back(cv::Rect(cv::Point(37, 20), cv::Point(40, 40)));
rectangles.push_back(cv::Rect(cv::Point(20, 37), cv::Point(40, 40)));

test1 = rectangles;
test2 = rectangles;
test3 = rectangles;

//Output format: {Rect(x, y, width, height), ...}

//Merge once
mergeRectangles(test1);
//Output rectangles: test1 = {Rect(5, 5, 31, 31), Rect(20, 20, 20, 20)} 

//Merge until there are no rectangles to merge
mergeRectangles(test2, true);
//Output rectangles: test2 = {Rect(5, 5, 35, 35)} 

//Override default merge (intersection) function to merge all rectangles
mergeRectangles(test3, false, [](const cv::Rect& r1, const cv::Rect& r2) {
    return true;
});
//Output rectangles: test3 = {Rect(5, 5, 35, 35)} 

Function:

void mergeRectangles(std::vector<cv::Rect>& rectangles, bool recursiveMerge = false, std::function<bool(const cv::Rect& r1, const cv::Rect& r2)> mergeFn = nullptr) {
    static auto defaultFn = [](const cv::Rect& r1, const cv::Rect& r2) {
        return (r1.x < (r2.x + r2.width) && (r1.x + r1.width) > r2.x && r1.y < (r2.y + r2.height) && (r1.y + r1.height) > r2.y);
    };

    static auto innerMerger = [](std::vector<cv::Rect>& rectangles, std::function<bool(const cv::Rect& r1, const cv::Rect& r2)>& mergeFn) {
        std::vector<std::vector<std::vector<cv::Rect>::const_iterator>> groups;
        std::vector<cv::Rect> mergedRectangles;
        bool merged = false;

        static auto findIterator = [&](std::vector<cv::Rect>::const_iterator& iteratorToFind) {
            for (auto groupIterator = groups.begin(); groupIterator != groups.end(); ++groupIterator) {
                auto foundIterator = std::find(groupIterator->begin(), groupIterator->end(), iteratorToFind);
                if (foundIterator != groupIterator->end()) {
                    return groupIterator;
                }
            }
            return groups.end();
        };

        for (auto rect1_iterator = rectangles.begin(); rect1_iterator != rectangles.end(); ++rect1_iterator) {
            auto groupIterator = findIterator(rect1_iterator);

            if (groupIterator == groups.end()) {
                groups.push_back({rect1_iterator});
                groupIterator = groups.end() - 1;
            }

            for (auto rect2_iterator = rect1_iterator + 1; rect2_iterator != rectangles.end(); ++rect2_iterator) {
                if (mergeFn(*rect1_iterator, *rect2_iterator)) {
                    groupIterator->push_back(rect2_iterator);
                    merged = true;
                }
            }
        }

        for (auto groupIterator = groups.begin(); groupIterator != groups.end(); ++groupIterator) {
            auto groupElement = groupIterator->begin();

            int x1 = (*groupElement)->x;
            int x2 = (*groupElement)->x + (*groupElement)->width;
            int y1 = (*groupElement)->y;
            int y2 = (*groupElement)->y + (*groupElement)->height;

            while (++groupElement != groupIterator->end()) {
                if (x1 > (*groupElement)->x)
                    x1 = (*groupElement)->x;
                if (x2 < (*groupElement)->x + (*groupElement)->width)
                    x2 = (*groupElement)->x + (*groupElement)->width;
                if (y1 >(*groupElement)->y)
                    y1 = (*groupElement)->y;
                if (y2 < (*groupElement)->y + (*groupElement)->height)
                    y2 = (*groupElement)->y + (*groupElement)->height;
            }

            mergedRectangles.push_back(cv::Rect(cv::Point(x1, y1), cv::Point(x2, y2)));
        }

        rectangles = mergedRectangles;
        return merged;
    };

    if (!mergeFn)
        mergeFn = defaultFn;

    while (innerMerger(rectangles, mergeFn) && recursiveMerge);
}