结合交叉边界矩形的有效方法

Question

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

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

通过交叉我的意思是触摸.希望这使它100%清晰:

我正在努力使用标准的形态学操作来有效地做到这一点; 显然它可以在O(N ^ 2)中天真地完成,但那太慢了.扩张没有帮助,因为一些形状只相差1px,如果它们没有相交,我不希望它们合并.

Answer 1

更新:我之前误解了这个问题.我们不想删除完全在其他内部的矩形.我们只想替换相交的矩形.因此,对于第一种情况,我们不得不采取任何行动.

新api(2.4.9)支持&和| 运营商.

来自opencv doc:

• rect = rect1&rect2(矩形交叉点)
• rect = rect1 | rect2(包含rect2和rect3的最小区域矩形)

它还支持平等比较(==)

• rect == rect1

所以现在很容易完成任务.对于每对矩形rect1和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.

更新2 :(用于在java中翻译)

我非常了解java.我也从未使用过java API.我在这里给出一些psudo代码(我认为可以轻松翻译)

对于&运算符,我们需要一个找到两个矩形相交的方法.

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()

对于|运营商,我们需要一种类似的方法

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)

对于==运算符,我们可以使用重载equals方法.

Answer 2

为了实现你想要的我们将要使用的findContours.这里的关键是要了解mode设置时的工作原理CV_RETR_TREE.在这种情况下,hierarchy构造的方式是每个均匀深度级别包含外部轮廓,而奇数深度级别包含内部轮廓.我们在这里需要的是遍历层次树,打印与甚至深度级别相关的轮廓.

首先,我们找到一个被称为图像的轮廓 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);

要在图像上打印外部轮廓,processed我们需要一个递归函数.

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);

结果示波纹管,其中,original与processed由侧显示侧.

如果您绝对需要矩形形状,则只需使用boundingRect给定一组点(在这种情况下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实现最有名的算法.

Answer 3

给定 形式的两个边界框轮廓(x,y,w,h)，这是一个创建单个边界框的函数（假设这些框相互接触或在彼此内部）。返回(x,y,w,h)组合边界框，即左上角 x、左上角 y、宽度和高度。这是一个例子

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

代码

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)

例子

有了这两个边界框，

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

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

这是视觉结果：之前->之后