Non‑maximum suppression

Non‑maximum suppression (NMS) – algorytm używany w widzeniu komputerowym do redukcji liczby wykrytych obiektów lub krawędzi poprzez odrzucenie tych, które nie są lokalnymi maksimum w określonym otoczeniu. Metoda jest kluczowym elementem wielu systemów, m.in. w detekcji krawędzi (np. w detektorze Canny'ego) oraz w detekcji obiektów opartych na sieciach konwolucyjnych.

Historia

Pierwsze zastosowanie NMS pojawiło się w latach 80. w kontekście algorytmu Canny'ego, opisanym w pracach Johna F. Canny'ego (1986). W kolejnych dekadach metoda została zaadaptowana do przetwarzania wyników klasyfikatorów obiektów, zwłaszcza w systemach bazujących na przesuwanym oknie oraz w nowoczesnych sieciach Region Proposal Network.

Podstawowa idea

Algorytm przyjmuje jako wejście listę wykrytych elementów, z których każdy ma:

• lokalizację (np. prostokąt ograniczający – bounding box),
• wartość wiarygodności (np. confidence score).

Proces polega na:

1. Posortowaniu elementów malejąco wg wartości wiarygodności.
2. Iteracyjnym wybraniu elementu o najwyższym wyniku i odrzuceniu wszystkich pozostałych, które zachodzą na niego w stopniu większym niż ustalony próg.

Miara zachodzenia najczęściej jest wyrażana jako Intersection over Union (IoU). Jeśli IoU pomiędzy dwoma obiektami przekracza określony próg (np. 0,5), mniej wiarygodny z nich zostaje usunięty.

Algorytm – krok po kroku

function NMS(boxes, scores, iouThreshold):
    order = argsort(scores, descending=True)
    keep = []
    while order not empty:
        i = order[0]
        keep.append(i)
        rest = order[1:]
        iou = computeIoU(boxes[i], boxes[rest])
        order = rest[iou < iouThreshold]
    return keep

Powyższy pseudokod obrazuje typową implementację, w której computeIoU zwraca wektor wartości IoU pomiędzy wybranym oknem a wszystkimi pozostałymi.

Zastosowania

• Detekcja krawędzi – po obliczeniu mapy gradientów algorytm usuwa słabe odpowiedzi, pozostawiając jedynie szczytowe punkty gradientu.
• Detekcja obiektów – w systemach YOLO, SSD czy Faster R‑CNN NMS eliminuje wielokrotne wykrycia tego samego obiektu.
• Segmentacja – w metodach Mask R‑CNN NMS stosowany jest do wyboru najbardziej prawdopodobnych masek.
• Śledzenie – w algorytmach Filtru Kalmana i SORT NMS pomaga w wyborze najbardziej wiarygodnych prognoz trajektorii.

Warianty i ulepszenia

W praktyce podstawowy NMS może prowadzić do zbyt agresywnego odrzucania obiektów, szczególnie w sytuacjach, gdy obiekty są blisko siebie. Dlatego opracowano liczne modyfikacje:

• Soft‑NMS – zamiast usuwać zachodzące detekcje, obniża ich wynik w zależności od stopnia zachodzenia (głównie wykorzystywany w detekcji obiektów).
• Adaptive NMS – próg IoU jest dostosowywany dynamicznie w zależności od rozmiaru i kształtu wykrytych elementów.
• Class‑wise NMS – wykonywany oddzielnie dla każdej klasy obiektu, co zmniejsza konflikt pomiędzy różnymi kategoriami.
• Greedy NMS – klasyczna wersja, opisana powyżej, bazująca na podejściu zachłannym.

Implementacje

W bibliotekach TensorFlow, PyTorch oraz OpenCV dostępne są gotowe funkcje:

• tf.image.non_max_suppression – przyjmuje współrzędne w formacie [ymin, xmin, ymax, xmax].
• torchvision.ops.nms – operuje na tensorach PyTorch.
• cv::dnn::NMSBoxes – część modułu DNN w OpenCV.

Zalety i ograniczenia

Zalety	Ograniczenia
Prostota i niska złożoność obliczeniowa (O(N log N) po sortowaniu).	Może usuwać prawdziwe obiekty, gdy są gęsto rozmieszczone.
Łatwa integracja z istniejącymi pipeline'ami detekcji.	Wymaga ręcznego dobrania progu IoU.
Stosunkowo szybka w porównaniu do metod optymalizacyjnych.	Nie uwzględnia kontekstu semantycznego pomiędzy wykryciami.

Praktyczne wskazówki

1. Eksperymentuj z wartością progowania IoU – typowe wartości to 0,3‑0,5 dla bardziej rozproszonych scen oraz 0,7‑0,8 w przypadku bardzo precyzyjnych modeli.
2. W sytuacji dużej liczby detekcji rozważ zastosowanie Soft‑NMS, aby uniknąć utraty słabych, ale istotnych wyników.
3. Używaj Class‑wise NMS przy wielu klasach, aby nie usuwać wykryć różnych obiektów o dużym nachodzeniu.
4. Po zastosowaniu NMS zweryfikuj wyniki wizualnie – często pozwala to wyłapać nieprawidłowo dobrany próg.

Bibliografia

• Canny, J. (1986). “A computational approach to edge detection”. IEEE Transactions on Pattern Analysis and Machine Intelligence.
• Redmon, J., & Farhadi, A. (2018). “YOLOv3: An Incremental Improvement”. arXiv preprint.
• Neubert, P., & Matas, J. (2019). “Soft-NMS – Improving Object Detection With One Line of Code”. ICCV Workshops.