how to detect intersecting and overlapping bounding box in a lot of bounding box?

Question

I generate a lot of bounding box in an image. How can I merge the overlapping bounding box in an image?

For example,

_________________                   ________________________
|               |                   |                      |
|      —————————|————               |                      | 
|      |        |   |               |                      |
———————|——————————  |         ——>   |                      |  
       |            |               |                      |
       |    ————————|——————         |                      |
       —————|————————     |         |                      |
            |             |         |                      |
            |             |         |                      |
            ————————————————        ________________________

I know use the rectangle 1 | rectangle 2 to generate a new rectangle.

It can detected and merged them in the approach as follow.(From Efficient way to combine intersecting bounding rectangles)

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.

But I mean how to judge which rectangle are overlapped when three or four rectangles overlapped. I though I could use the overlapping area to judge whether they are overlapped.

Is that anything else efficient approach? thank you so much.

Answer 1

Here's a some quick pseudocode

1. Generate binary maps for each rectangle which are the size of the image.
2. Add these binary maps to create a new single merged map. (You might have to threshold them back down to 1's and 0's)
3. Generate a new bounding box for this using your original algorithm (the one you used to get the first 3 bounding boxes)

Answer 2

This function take the contours of the image and return the merged boxes you want:

ae::error_code authenticator::get_boxes(const std::vector<std::vector<cv::Point>>& contours, std::vector<cv::Rect>& boxes){
        std::vector<cv::Rect> bounding_boxes;
        for (const auto& contour_item : contours){
            bounding_boxes.push_back(cv::boundingRect(contour_item));
        }


        auto rect_corners = [](const cv::Rect& rect)->std::vector<cv::Point>{
            return{ cv::Point(rect.x, rect.y),
                cv::Point(rect.x + rect.width, rect.y),
                cv::Point(rect.x + rect.width, rect.y + rect.height),
                cv::Point(rect.x, rect.y + rect.height) };
        };

        auto check_shared_rects = [](const cv::Rect& rect_a, const cv::Rect& rect_b)->bool{
            return (rect_a & rect_b).area() > 0;
        };


        for (size_t rect_idx = 0; rect_idx < bounding_boxes.size() - 1; ++rect_idx){
            for (size_t other_rect_idx = rect_idx + 1; other_rect_idx < bounding_boxes.size(); ++other_rect_idx){
                if (check_shared_rects(bounding_boxes[rect_idx], bounding_boxes[other_rect_idx])){
                    auto new_rect_points(rect_corners(bounding_boxes[rect_idx]));
                    auto temp_points(rect_corners(bounding_boxes[other_rect_idx]));
                    new_rect_points.insert(std::end(new_rect_points), std::begin(temp_points), std::end(temp_points));
                    bounding_boxes.push_back(cv::boundingRect(new_rect_points));
                    bounding_boxes.erase(std::begin(bounding_boxes) + other_rect_idx);
                    bounding_boxes.erase(std::begin(bounding_boxes) + rect_idx);
                    rect_idx = 0;
                    other_rect_idx = rect_idx;
                }
            }
        }
        boxes = bounding_boxes;
        return ae::error_code::ae_error_free;
    }

EDIT : You can dismiss the first part about generating the bounding boxes since you have them already.

Answer 3

Sort your bounding boxes by area : the biggest boxes are the one more likely to overlap.

Failing that, you can do a "not so efficient" drawing all the rectangles by doing a union of all rectangles. You might want to label your overlapping boxes image to select only the overlapping ones and discard the rest.

There might be some trick to use under this idea by using a sort of z-buffer to store which rectangles are drawn on each pixel ?

Answer 4

This is the code i have used for my problem you can use for yours too Enjoy:

 function varargout = isBoxMerg(ReferenceBox,TestBox,isNewBox)

            X = ReferenceBox; Y = TestBox;

            X1 = X(1);Y1 = X(2);W1 = X(3);H1 = X(4);
            X2 = Y(1);Y2 = Y(2);W2 = Y(3);H2 = Y(4);

            if ((X1+W1)>=X2 && (Y2+H2)>=Y1 && (Y1+H1)>=Y2 && (X1+W1)>=X2 && (X2+W2)>=X1)
                Intersection = true;
            else
                Intersection = false;
            end
            if (~isNewBox)
                varargout{1} = Intersection;
            elseif(isNewBox && Intersection)
                varargout{1} = Intersection;

                a = X1;b=X1+W1;c=Y1;d=Y1+H1;
                p = X2;q=X2+W2;r=Y2;s=Y2+H2;



                if a<p
                    newA = a;
                else
                    newA = p;
                end
                if b>q
                    newB = b;
                else
                    newB = q;
                end
                if c<r
                    newC = c;
                else
                    newC = r;
                end
                if d>s
                    newD = d;
                else
                    newD = s;
                end
                newCC = [newA,newC,abs(newA-newB),abs(newC-newD)];
                varargout{2} = newCC;  
            end