Bei einer Liste von Rechtecken, wie finden Sie alle Rechtecke, die vollständig in anderen enthalten sind?

Question

Ich habe einen Computer-Vision-Algorithmus, der um erkannte Objekte Begrenzungsrahmen platziert. Die Begrenzungskästen Liste geht wie folgt:

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

wobei x und y sind Koordinaten der oberen linken Ecke, h und w sind die Höhe und Breite der Schachtel. Ich bin jedoch nicht an Kästen interessiert, die vollständig in anderen größeren Kästen enthalten sind. Was ist eine effiziente Methode, um diese zu erkennen?

Answer 1

Wie Sie in den Kommentaren unter der Frage bestätigt haben, müssen Sie die Boxen identifizieren und entfernen, die in einem einzigen anderen Kasten enthält. Wenn eine Box in einer anderen Box enthalten ist, aber keine andere Box enthält, sollte sie nicht entfernt werden (z. B. im Fall boxes = [[0, 0, 2, 4], [1, 1, 3, 3], [2, 0, 4, 4]] ist die zweite Box in der Union der ersten und dritten Box enthalten). aber es sollte nicht entfernt werden).

---

Der naive (brute-force) Algorithmus für diese Aufgabe ist sehr einfach. Hier ist der Pseudo-Code:

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

Die Komplexität dieses Algorithmus ist offensichtlich O(n^2). Dieser Algorithmus ist sehr einfach zu implementieren und wird empfohlen, wenn die Anzahl der Boxen klein ist (etwa 100 bis 500 oder sogar 1000, wenn Sie keine Echtzeitleistung für die Videoverarbeitung benötigen).

---

Die Komplexität des schnellen Algorithmus ist O(n log n), die ich glaube, auch die minimale theoretische Komplexität für dieses Problem ist. Formal nimmt der erforderliche Algorithmus die folgende Eingabe und gibt die folgende Ausgabe:

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. 

Der Pseudo-Code für den schnellen Algorithmus:

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 

nun der schwierige Teil ist Schritt (4) dieses Algorithmus. Es scheint schwierig zu sein, eine solche Datenstruktur zu implementieren. Es gibt jedoch eine wunderbare Implementierung in der C++ - Standardbibliothek mit der Bezeichnung std::map. Die Suchoperationen, die in O(log n) funktionieren, sind std::map::lower_bound und std::map::upper_bound.

Dieser Algorithmus hat eine durchschnittliche Komplexität von O(n log n), Worst-Case-Komplexität von O(n^2) und, wenn die Anzahl der Boxen und deren Größe relativ klein sind, um die Bildgröße zu vergleichen, die Komplexität ist in der Nähe von O(n).