Research map / Detection and segmentation / CNN features
Accelerating Non-Maximum Suppression: A Graph Theory Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes NMS as a DAG over boxes and proposes QSI-NMS, eQSI-NMS (O(n log n)) and BOE-NMS, plus the NMS-Bench benchmark, achieving up to ~10x speedups over original NMS with little or no mAP loss.
Problem
Non-maximum suppression is a post-processing bottleneck in object detection; existing NMS speedups rely on parallel hardware or lose accuracy, and NMS methods lack a unified evaluation framework.
Approach
Model NMS as a directed acyclic graph of suppression relations, solve it via dynamic programming over topological order, and exploit weakly connected component structure with a quicksort-style divide-and-conquer (QSI-NMS, eQSI-NMS via a Cartesian/QSI tree) and a geometric locality bound that skips non-overlapping box pairs (BOE-NMS).
Key results
- On YOLOv8-N with MS COCO 2017, QSI-NMS gives 6.2x speed of original NMS with a 0.1% mAP drop, and eQSI-NMS gives 10.7x with a 0.3% drop (per abstract).
- BOE-NMS achieves 5.1x speed of original NMS on YOLOv8-N with no mAP loss.
- On Open Images V7, eQSI-NMS reaches about 10.2x the speed of original NMS, with about 0.2% mAP decrease for QSI/eQSI-NMS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BOE-NMS instead of original NMS | YOLOv8-N · MS COCO 2017 | Average Latency (μs): 906.9 -> 176.8 | Helped |
| Use BOE-NMS instead of original NMS | YOLOv8-N · MS COCO 2017 | AP 0.5:0.95 (%): 37.2 -> 37.2 | No clear effect |
| Use QSI-NMS instead of original NMS | YOLOv8-N · MS COCO 2017 | Average Latency (μs): 906.9 -> 146.8 | Helped |
| Use QSI-NMS instead of original NMS | YOLOv8-N · MS COCO 2017 | AP 0.5:0.95 (%): 37.2 -> 37.1 | Hurt |
| Use eQSI-NMS instead of original NMS | YOLOv8-N · MS COCO 2017 | Average Latency (μs): 906.9 -> 85.0 | Helped |
| Use eQSI-NMS instead of original NMS | YOLOv8-N · MS COCO 2017 | AP 0.5:0.95 (%): 37.2 -> 36.9 | Hurt |
| Use BOE-NMS instead of original NMS | YOLOv8-N · Open Images V7 | Average Latency (μs): 1627.9 -> 260.2 | Helped |
| Use BOE-NMS instead of original NMS | YOLOv8-N · Open Images V7 | AP 0.5:0.95 (%): 18.1 -> 18.1 | No clear effect |
| Use QSI-NMS instead of original NMS | YOLOv8-N · Open Images V7 | Average Latency (μs): 1627.9 -> 231.8 | Helped |
| Use eQSI-NMS instead of original NMS | YOLOv8-N · Open Images V7 | Average Latency (μs): 1627.9 -> 132.3 | Helped |
| Use eQSI-NMS instead of original NMS | YOLOv8-N · Open Images V7 | AP 0.5:0.95 (%): 18.1 -> 18.0 | Hurt |
Surprising findings
- Fast NMS, despite being parallelizable, has Theta(n^2) implementation complexity, higher than original NMS in practice.
- PSRR-MaxpoolNMS loses 1-2% mAP on Faster R-CNN and YOLOv5 in the authors' comparison.
Limitations
- QSI-NMS and eQSI-NMS incur a small mAP drop (0.1-0.5%) relative to original NMS.
- BOE-NMS remains O(n^2) in worst-case complexity, although near-linear in practice.
- Speed measured on the authors' platform; hardware-specific results are not fully characterized.
Experimental setup
Datasets: MS COCO 2017 Open Images V7
Benchmarks: MS COCO 2017 Open Images V7 NMS-Bench
Metrics: AP 0.5:0.95 average latency per image (microseconds)
Baselines: original NMS Fast NMS Cluster-NMS PSRR-MaxpoolNMS
Builds on: Soft-NMS Cluster-NMS Fast NMS quicksort
Closest papers by meaning
- Learning Non-Maximum Suppression (CVPR 2017 · similarity 0.91)
- MaxpoolNMS: Getting Rid of NMS Bottlenecks in Two-Stage Object Detectors (CVPR 2019 · similarity 0.89)
- GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection (CVPR 2021 · similarity 0.89)
- PSRR-MaxpoolNMS: Pyramid Shifted MaxpoolNMS With Relationship Recovery (CVPR 2021 · similarity 0.88)
- YOLOv10: Real-Time End-to-End Object Detection (NeurIPS 2024 · similarity 0.86)
- SAFDNet: A Simple and Effective Network for Fully Sparse 3D Object Detection (CVPR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.