Non-Maximum Suppression

Non-Maximum Suppression (NMS, подавление немаксимумов) — это алгоритм постобработки, используемый в компьютерном зрении и машинном обучении для фильтрации множества пересекающихся предсказаний (bounding boxes, масок, ключевых точек) и выбора только наиболее релевантных. Основная цель NMS — устранить дублирующиеся обнаружения одного и того же объекта, оставив одно наилучшее с точки зрения уверенности модели (confidence score).

Принцип работы

Алгоритм NMS основан на простом, но эффективном эвристическом правиле: если два предсказания (например, прямоугольные рамки вокруг одного и того же объекта) сильно перекрываются, то из них выбирается то, для которого модель дала наибольшую оценку уверенности. Остальные отбрасываются. Процесс выполняется итеративно для каждого класса объектов отдельно.

Пошаговое описание (для bounding boxes)

1. Входные данные: список предсказанных ограничивающих рамок (bounding boxes), каждая из которых характеризуется координатами (x, y, ширина, высота или x1, y1, x2, y2) и оценкой уверенности (score). Все рамки принадлежат одному классу.
2. Сортировка: все рамки сортируются по убыванию оценки уверенности.
3. Итерация:

• Выбирается рамка с максимальной оценкой (текущий «лучший» кандидат). Она гарантированно сохраняется.
• Вычисляется показатель перекрытия (Intersection over Union, IoU) между этой рамкой и каждой из оставшихся.
• Если IoU превышает заданный порог (например, 0.5), то соответствующая рамка считается дублирующей и удаляется из списка.
• Выбранная рамка перемещается в список финальных предсказаний.

1. Повтор: шаг 3 повторяется для оставшихся рамок до тех пор, пока список не опустеет.
2. Выходные данные: список финальных рамок, не имеющих значительных перекрытий между собой.

Математическая основа

Ключевым параметром NMS является порог Intersection over Union (IoU). IoU — это метрика, измеряющая степень перекрытия двух областей. Она вычисляется как отношение площади их пересечения к площади их объединения:

\[ IoU = \frac{\text{Площадь пересечения}}{\text{Площадь объединения}} \]

Значение IoU находится в диапазоне от 0 (нет перекрытия) до 1 (полное совпадение). Чем выше порог IoU, тем меньше рамок будет подавлено, и наоборот. Выбор порога зависит от конкретной задачи: для детекции плотно расположенных объектов (например, людей в толпе) требуется более низкий порог (0.3–0.4), для разреженных сцен — более высокий (0.5–0.7).

Разновидности Non-Maximum Suppression

Стандартный NMS (Greedy NMS)

Классический вариант, описанный выше. Прост в реализации, но имеет ряд недостатков: он необратимо удаляет все рамки с высоким перекрытием, даже если они относятся к разным экземплярам одного и того же класса. Это может привести к потере обнаружений в сценах с сильным перекрытием объектов.

Soft-NMS

Модификация, предложенная для смягчения проблемы жёсткого отбрасывания. Вместо полного удаления рамок с высоким IoU, их оценка уверенности понижается (умножается на функцию, зависящую от IoU). Таким образом, рамка, сильно перекрывающаяся с более уверенной, не удаляется, а получает меньший вес. Если она соответствует другому объекту, её оценка может остаться достаточно высокой для прохождения финального порога.

Adaptive NMS

Вариант, в котором порог IoU динамически адаптируется в зависимости от плотности объектов в изображении. В областях с высокой плотностью объектов порог снижается, чтобы избежать подавления разных экземпляров. В разреженных областях порог повышается для более агрессивного удаления дубликатов.

NMS для масок (Mask NMS)

В задачах сегментации экземпляров (instance segmentation) вместо bounding boxes используются маски. NMS для масок работает аналогично, но IoU вычисляется не по прямоугольникам, а по фактическим областям масок. Это более точно, но и более вычислительно затратно.

NMS для ключевых точек (Keypoint NMS)

В задачах оценки позы человека (pose estimation) NMS применяется для фильтрации множества предсказанных ключевых точек (суставов). Здесь IoU может вычисляться по области, ограниченной минимальным прямоугольником, охватывающим все ключевые точки, или по специальным метрикам, учитывающим конфигурацию скелета.

Применение

NMS является обязательным этапом постобработки в большинстве современных детекторов объектов, таких как:

• Семейство R-CNN (Fast R-CNN, Faster R-CNN, Mask R-CNN): применяется после региональной сети предложений (RPN) и финальной классификации.
• Одностадийные детекторы (YOLO, SSD, RetinaNet): используется для фильтрации множества предсказаний, генерируемых на сетке признаков.
• Трансформерные детекторы (DETR, Deformable DETR): хотя DETR изначально не требует NMS благодаря механизму внимания, на практике его часто применяют для улучшения качества на сценах с сильным перекрытием.

Помимо детекции объектов, NMS используется в:

• Сегментации экземпляров: для выбора одной маски на объект.
• Оценке позы человека: для устранения дублирующихся скелетов.
• Обнаружении текста (OCR): для фильтрации перекрывающихся текстовых блоков.
• Автономном вождении: в системах обнаружения пешеходов, транспортных средств и дорожных знаков.

Ограничения и критика

Несмотря на широкое распространение, NMS имеет ряд недостатков:

1. Необратимость: ошибочное подавление правильной рамки не может быть исправлено.
2. Зависимость от порога: выбор порога IoU является гиперпараметром, который требует ручной настройки и не всегда оптимален для всех сцен.
3. Чувствительность к плотности объектов: при сильном перекрытии объектов (например, в толпе) стандартный NMS часто удаляет правильные обнаружения.
4. Необходимость постобработки: NMS не является частью обучения нейронной сети, что может приводить к неоптимальному поведению на этапе вывода.
5. Вычислительная сложность: в худшем случае (O(n²)) может быть узким местом для систем реального времени.

Альтернативы

Для преодоления ограничений NMS были предложены альтернативные подходы:

• End-to-end детекторы: модели, которые учатся избегать дублирующихся предсказаний без явной постобработки (например, DETR, OneNet).
• Методы на основе обучения: нейронные сети, обучающиеся предсказывать, какие рамки следует подавить (например, Network NMS).
• Методы кластеризации: группировка перекрывающихся рамок с последующим усреднением их параметров (Weighted NMS, Cluster NMS).

Интересные факты

• Алгоритм NMS был впервые предложен в контексте обнаружения объектов в 2006 году в работе P. Felzenszwalb и др. «Object Detection with Discriminatively Trained Part Based Models» (DPM).
• В задачах, где требуется высокая скорость (например, в мобильных приложениях), используются аппаратно-оптимизированные реализации NMS на GPU (CUDA, TensorRT).
• NMS является недифференцируемой операцией, что затрудняет её прямое включение в процесс обучения нейронных сетей. Для решения этой проблемы существуют аппроксимации, такие как Soft-NMS, которые могут быть дифференцируемыми.

Источники

• Felzenszwalb, P. F., Girshick, R. B., McAllester, D., & Ramanan, D. (2010). Object detection with discriminatively trained part-based models. IEEE transactions on pattern analysis and machine intelligence, 32(9), 1627-1645.
• Bodla, N., Singh, B., Chellappa, R., & Davis, L. S. (2017). Soft-NMS – improving object detection with one line of code. Proceedings of the IEEE international conference on computer vision.
• Liu, S., Huang, D., & Wang, Y. (2019). Adaptive NMS: Refining pedestrian detection in a crowd. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition.
• Redmon, J., & Farhadi, A. (2018). YOLOv3: An incremental improvement. arXiv preprint arXiv:1804.02767.
• Ren, S., He, K., Girshick, R., & Sun, J. (2015). Faster R-CNN: Towards real-time object detection with region proposal networks. Advances in neural information processing systems, 28.