组合相交边界矩形的有效方法 [英] Efficient way to combine intersecting bounding rectangles

问题描述

我正在尝试使用 OpenCV 简化以下图像:

我们这里有很多红色的形状.其中一些完全包含其他.其中一些与邻居相交.我的目标是通过将任意两个相交形状替换为其并集多边形的边界框来统一所有 相交 形状.(重复直到没有更多相交的形状).

相交的意思是也接触.希望这使它 100% 清楚:

我正在尝试使用标准形态学操作有效地做到这一点；显然它可以在 O(N^2) 中天真地完成，但这太慢了.膨胀无济于事，因为某些形状仅相距 1px，如果它们不相交，我不希望它们合并.

解决方案

为了完成你想要的，我们将使用 获取给定一组点(在本例中为每个轮廓)的最小封闭矩形并使用 rectangle 用于绘图.换句话说，替换

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

由

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

findContours 需要单个 8 位图像，因此您可以从原始图像制作灰色图像，然后对其进行阈值处理以获得完美的黑色背景，或者使用红色就足够了在你的情况下，只要确保背景是完全黑色的.

关于 findContours 的复杂性，我不能证明它比 O(N^2) 更好，我也没有发现任何输入经过快速的谷歌搜索，但我相信 OpenCV 实现了最著名的算法.

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.

解决方案

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.

这篇关于组合相交边界矩形的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！