用图论优化目标检测中的非极大值抑制，速度提升超10倍且精度损失极小。
Accelerating Non-Maximum Suppression: A Graph Theory Perspective
- 从图论角度解析NMS结构，提出分治递归与局部性优化新算法
- 最快达10.7倍加速，仅损失0.3% mAP；另一方法无精度损失，提速5.1倍
- 开源首个全面评估NMS的基准测试平台NMS-Bench，适配研究者快速验证
非极大值抑制（NMS）是目标检测中不可或缺的后处理步骤。随着网络模型持续优化，NMS已成为提升检测效率的“最后一公里”。本文首次从图论视角系统分析NMS的内在结构，据此提出两种优化方法：QSI-NMS与BOE-NMS。前者为快速递归分治算法，几乎无mAP损失，其扩展版eQSI-NMS达到最优复杂度$/mathcal{O}(n/log n)$；后者聚焦NMS局部性，实现常数级优化且无mAP损失。此外，为便于研究人员快速评估，我们引入首个全面评估NMS方法的基准——NMS-Bench。以YOLOv8-N在MS COCO 2017上的设置为例，QSI-NMS相较原NMS提速6.2倍，mAP下降0.1%；最优版本eQSI-NMS仅损失0.3% mAP，提速达10.7倍；而BOE-NMS提速5.1倍，精度无损。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。