python - 给定一个矩形列表，如何找到完全包含在其他矩形中的所有矩形？

Question

我有一种计算机视觉算法，可以在检测到的对象周围放置边界框。边界框列表如下:

bounding_boxes = [[x, y, w, h], [x2, y2, w2, h2], ...]

其中x和y是左上角的坐标，h和w是盒子的高度和宽度。但是，我对完全包含在任何其他较大盒子中的盒子不感兴趣。检测这些的有效方法是什么？

Answer 1

正如您在问题下的评论中所确认的那样，您需要识别并删除单个其他框中包含的框。如果一个框包含在其他框的联合中，但没有其他单个框包含它，则不应删除它(例如，在 boxes = [[0, 0, 2 , 4], [1, 1, 3, 3], [2, 0, 4, 4]]，第二个框包含在第一个和第三个框的并集中，但不应将其删除)。

<小时/>

此任务的简单(暴力)算法非常简单。这是伪代码:

for i in [0, 1, ..., n]:
    for j in [i+1, i+2, ..., n]:
        check if box[i] contains in box[j] and otherwise.

这个算法的复杂度显然是O(n^2)。该算法非常容易实现，如果盒子数量较少(100-500左右，如果不需要视频处理的实时性能，甚至1000个)，建议使用该算法。

<小时/>

快速算法的复杂度是O(n log n)，我相信这也是这个问题的最小理论复杂度。形式上，所需的算法采用以下输入并返回以下输出:

Input: boxes[] - Array of n Rectangles, Tuples of (x1, y1, x2, y2), where 
                 (x1, y1) is coordinates of the left bottom corner, (x2, y2)
                 is the coordinates of the top right corner.
Output: inner_boxes[] - Array of Rectangles that should be removed.

快速算法的伪代码:

1) Allocate an Array events[] with the length 2*n, the elements of which are 
   Tuples (y, corresponding_box_index, event). 

2) For i in [0, 1, ..., n]:
     events[2 * i    ] = Tuple(boxes[i].y1, i, 'push')
     events[2 * i + 1] = Tuple(boxes[i].y2, i, 'pop')

3) Sort events[] by the ascending of y coordinate (from smaller to larger).
   If there are equal y coordinates, Then:
   - Tuples with 'pop' event are smaller thant Tuples with 'push' event.
   - If two Tuples has the same event, they are sorted by the ascending of
     the width of their corresponding boxes.

4) Create a Map cross_section_map[], that maps a Key (Value) x to a Tuple
   (corresponding_box_index, type), where type can be either 'left' or 'right'.
   Make sure that the 'insert' and 'erase' operation of this data structure 
   has the complexity O(log n), it is iterable, the elements are iterated in 
   an key-ascending manner, and you can search for a key in O(log n) time.

5) For step in [0, 1, ..., 2*n]:
     If events[step].event is 'push':
       - Let i = events[step].corresponding_box_index
       - Insert a map boxes[i].x1 -> (i, 'left') to cross_section_map[]
       - Insert a map boxes[i].x2 -> (i, 'right') to cross_section_map[]
       - Search for a 'right'-typed key with x value no less than boxes[i].x2
       - Iterate from that key until you found a key, which corresponds to
         a box that contains boxes[i], or the x1 coordinate of which is larger
         than the x1 coordinate of a newly added box. In the first case, add
         boxes[i] to inner_boxes[].
     If events[step].event is 'pop':
       - Let i = events[step].corresponding_box_index
       - Erase the elements with the keys boxes[i].x1 and boxes[i].x2

现在，棘手的部分是该算法的步骤(4)。实现这样的数据结构似乎很难。然而，C++ 标准库中有一个开箱即用的精彩实现，称为 std::map 。在 O(log n) 中工作的搜索操作是 std::map::lower_bound和std::map::upper_bound .

该算法的平均复杂度为O(n log n)，最坏情况复杂度为O(n^2)，并且如果盒子的数量和与图像大小相比，它们的大小相对较小，复杂度接近O(n)。