Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bounding box of multiple overlapping rectangles

enter image description here

How can I get the bounding boxes of multiple overlapping rectangles? There might be multiple bounding boxes if there are rectangles that don't overlap.

I have an array containing n objects representing the rectangles. Each object is representing a rectangle the following way: {left: 178, top: 67, width: 20, height: 14} They can be represented other ways as well like leftX, topY, rightX, bottomY; it can be converted easily.

I'm not looking for non-max surpression algorithm. Is there a specific algorithm in literature that can achieve this? I'll try to convert it after in JavaScript.

Edit: AuxTaco solution works as long as the rectangles are overlapping one after the other; if you draw the rectangles in the order specified like in the picture below you get 3 bounding areas.

enter image description here

Edit2: Maybe an interesting case would be the following: enter image description here

Rectangle 1 and 2 overlap and their bounding box overlaps rectangle 3; however I'm not interested in this particular case and 3 could be treated as a separate rectangle.

like image 370
Shury Avatar asked Aug 15 '19 16:08

Shury


People also ask

Can bounding boxes overlap?

In object detection, it is usual to have bounding box targets to identify objects in images. These bounding boxes may sometimes overlap. In some models like Mask RCNN the bounding boxes are predicted directly and the overlap of the bounding boxes in not a problem.

How do you check if bounding boxes overlap?

Two axes aligned boxes (of any dimension) overlap if and only if the projections to all axes overlap. The projection to an axis is simply the coordinate range for that axis. The blue and the green boxes in the image above overlap because their projections to both axes overlap.

How do you check if two rectangles overlap with each other in python?

If we have two (axis-aligned) rectangles, we have to check whether they overlap or not. So, if the input is like R1 = [0,0,2,2], R2 = [1,1,3,3], then the output will be True. otherwise, return True.

Why are there multiple bounding boxes in an array of objects?

There might be multiple bounding boxes if there are rectangles that don't overlap. I have an array containing n objects representing the rectangles.

Do the bounding boxes of a neural network model overlap?

In object detection, it is usual to have bounding box targets to identify objects in images. These bounding boxes may sometimes overlap. In some models like Mask RCNN the bounding boxes are predicted directly and the overlap of the bounding boxes in not a problem.

How to find out if given rectangles overlap?

1) One rectangle is above top edge of other rectangle. 2) One rectangle is on left side of left edge of other rectangle. We need to check above cases to find out if given rectangles overlap or not.

What is a minimum bounding rectangle?

Minimum bounding rectangle. The minimum bounding rectangle (MBR), also known as bounding box (BBOX) or envelope, is an expression of the maximum extents of a 2-dimensional object (e.g. point, line, polygon) or set of objects within its (or their) 2-D (x, y) coordinate system, in other words min(x), max(x), min(y), max(y).


2 Answers

So I have laid out a approach, which should work for you. The summary of approach is below

  • Start with a empty collision array
  • Each element in collision array will store array of rectangles which collide with any of the rectangles
  • Run through list of rectangles we have
  • If rectangle doesn't collide with any element append it to collision
  • If rectangle collides with exactly one element then append it to that element of collision array
  • If rectangle collides with multiple elements in array then we merge all such elements into one and then remove rest of the elements
  • Finally the collision array has only elements which are collision arrays
  • Then you can compute bounding rectangle for each of these collisions, which is just a min/max problem

Now to the code

function doRectsCollide(a, b) {
    return !(
        ((a.top + a.height) < (b.top)) ||
        (a.top > (b.top + b.height)) ||
        ((a.left + a.width) < b.left) ||
        (a.left > (b.left + b.width))
    );
}

var collisions = [];

var rectangles = [
    {left: 74, top: 66.89999389648438, width: 80.5, height: 71},
    {left: 111.5, top: 95.89999389648438, width: 125, height: 84},
    {left: 177, top: 120.89999389648438, width: 168.5, height: 90},
    {left: 93, top: 258.8999938964844, width: 81.5, height: 81},
    {left: 265.5, top: 320.8999938964844, width: 92, height: 83},
    {left: 393, top: 210.89999389648438, width: 88.5, height: 95}
];

for (rectangle of rectangles) {
    var collisions_indexes = [];

    index = 0;
    for (currentColission of collisions) {
        for (rect of currentColission) {
            if (doRectsCollide(rect, rectangle) === true) {
                collisions_indexes.push(index)
                break
            }
        }
        index++;
    }

    if (collisions_indexes.length == 0) {
        // this rectangle collides with none and should be appened to collisions array
        collisions.push([rectangle])
    } else if (collisions_indexes.length >= 1) {
        // there is just one collision, we can merge the same
        collisions[collisions_indexes[0]].push(rectangle)

        // now we have got multiple collisions, so we need to merge all the collisions with the first one
        // and remove the colission ones
        for (var i = 1; i < collisions_indexes.length; i++) {
            // we use - (i - 1) because we will remove the collision once we merge it
            // so after each merge the collision index actually shift by -1

            var new_index = collisions_indexes[i] - (i - 1);
            // extend the first colliding array with the new collision match
            collisions[collisions_indexes[0]].push(...collisions[new_index])

            // now we remove the element from our collision since it is merged with some other
            collisions.splice(new_index, 1);
        }

    }
}

console.log(JSON.stringify(collisions, null, 2));
//now we have a array of collision which will have all colliding ones
for (collision of collisions) {
    // compute bounding rectangle from rectangles array in collision
}

Now the output of the same is

[
    [
        {"left":74,"top":66.89999389648438,"width":80.5,"height":71},
        {"left":111.5,"top":95.89999389648438,"width":125,"height":84},
        {"left":177,"top":120.89999389648438,"width":168.5,"height":90}
    ],
    [{"left":93,"top":258.8999938964844,"width":81.5,"height":81}],
    [{"left":265.5,"top":320.8999938964844,"width":92,"height":83}],
    [{"left":393,"top":210.89999389648438,"width":88.5,"height":95}]
]
like image 149
Tarun Lalwani Avatar answered Oct 09 '22 17:10

Tarun Lalwani


I don't know the name of a specific algorithm, but this can be reduced to 2D collision detection:

function combineRects (rect1, rect2) {
  return a rectangle object representing the bounding box of the union of rect1 and rect2;
}
function doRectsCollide (rect1, rect2) {
  return true if rect1 and rect2 intersect;
}

const rectangles = [ your rectangle objects ];
const boundingBoxes = rectangles.reduce((boxes, rect) => {
  // Start with an empty array of bounding boxes.
  // For each rectangle, find the bounding box it intersects.
  const boundingBoxIndex = boxes.findIndex(doRectsCollide.bind(null, rect));
  if (boundingBoxIndex === -1) {
    // If there is none, push the rectangle into the bounding box array.
    boxes.push(rect);
    return boxes;
  } else {
    // Otherwise,
    // replace the intersected bounding box with a new box that includes the rectangle.
    boxes[boundingBoxIndex] = combineRects(boxes[boundingBoxIndex], rect);
    return boxes;
  }
}, []);

This is pretty efficient in your example (each rectangle is compared to a maximum of 3 others), but slows down to O(n^2) in the worst case, no overlapping rectangles. It can be improved by using something better than a raw array to store the bounding boxes.

like image 25
AuxTaco Avatar answered Oct 09 '22 16:10

AuxTaco