矩形のリストが与えられたら、他の矩形に完全に含まれるすべての矩形を見つける方法は？

Question

私は、検出されたオブジェクトの周囲にバウンディングボックスを置くコンピュータビジョンアルゴリズムを持っています。次のようにバウンディングボックスリストが行く：

xおよびyは左上隅の座標で

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

、hおよびwはボックスの高さと幅です。しかし、私は他の大きな箱の中に完全に入っている箱には興味がありません。それらを検出する効率的な方法は何ですか？

Answer 1

質問の下のコメントで確認したように、単一ののボックスに含まれるボックスを特定して削除する必要があります。あるボックスが他のボックスのユニオンに含まれていて、それ以外のボックスが含まれていない場合は、削除しないでください（たとえば、boxes = [[0, 0, 2, 4], [1, 1, 3, 3], [2, 0, 4, 4]]の場合、2番目のボックスは1番目と3番目のボックス、削除しないでください）。

---

このタスクの単純な（ブルートフォース）アルゴリズムは非常に簡単です。ここで擬似コードは次のとおりです。

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)に近い、O(n log n)の平均複雑さ、O(n^2)の最悪の場合の複雑性を有すると。