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

Question

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

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

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

Answer 1

正如您在问题下的评论中确认的那样，您需要识别并删除包含在单个其他框中的框。如果一个框包含在其他框的 union 中，但没有其他单个框包含它，则不应删除它（例如，在 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)，我相信这也是这个问题的最小理论复杂度。形式上，所需算法采用以下输入和 returns 以下输出：

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. The search operations that works in O(log n) are std::map::lower_bound and std::map::upper_bound.

该算法的平均复杂度为 O(n log n)，最坏情况的复杂度为 O(n^2)，如果框的数量及其大小与图像大小相比相对较小，则复杂度为O(n).

附近

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

Given a list of rectangles, how to find all rectangles that are fully contained within other ones?

python

computer-vision

cv2