Accelerating Non-Maximum Suppression: A Graph Theory Perspective
<|reference_start|>Accelerating Non-Maximum Suppression: A Graph Theory Perspective: Non-maximum suppression (NMS) is an indispensable post-processing step in object detection. With the continuous optimization of network models, NMS has become the ``last mile'' to enhance the efficiency of object detection. This paper systematically analyzes NMS from a graph theory perspective for the first time, revealing its intrinsic structure. Consequently, we propose two optimization methods, namely QSI-NMS and BOE-NMS. The former is a fast recursive divide-and-conquer algorithm with negligible mAP loss, and its extended version (eQSI-NMS) achieves optimal complexity of $\mathcal{O}(n\log n)$. The latter, concentrating on the locality of NMS, achieves an optimization at a constant level without an mAP loss penalty. Moreover, to facilitate rapid evaluation of NMS methods for researchers, we introduce NMS-Bench, the first benchmark designed to comprehensively assess various NMS methods. Taking the YOLOv8-N model on MS COCO 2017 as the benchmark setup, our method QSI-NMS provides $6.2\times$ speed of original NMS on the benchmark, with a $0.1\%$ decrease in mAP. The optimal eQSI-NMS, with only a $0.3\%$ mAP decrease, achieves $10.7\times$ speed. Meanwhile, BOE-NMS exhibits $5.1\times$ speed with no compromise in mAP.<|reference_end|>
@article{si2024accelerating,
    title={Accelerating Non-Maximum Suppression: A Graph Theory Perspective},
    author={King-Siong Si, Lu Sun, Weizhan Zhang, Tieliang Gong, Jiahao Wang,
  Jiang Liu, Hao Sun},
    journal={arXiv preprint arXiv:2409.20520},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.20520},
    primaryClass={cs.CV cs.LG}
}