Efficient way to combine intersecting bounding rectangles
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.
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
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.