Abstract
Non-maximum suppression (NMS) is an indispensable post-processing step inobject detection. With the continuous optimization of network models, NMS hasbecome the ``last mile'' to enhance the efficiency of object detection. Thispaper systematically analyzes NMS from a graph theory perspective for the firsttime, revealing its intrinsic structure. Consequently, we propose twooptimization methods, namely QSI-NMS and BOE-NMS. The former is a fastrecursive divide-and-conquer algorithm with negligible mAP loss, and itsextended version (eQSI-NMS) achieves optimal complexity of $\mathcal{O}(n\logn)$. The latter, concentrating on the locality of NMS, achieves an optimizationat a constant level without an mAP loss penalty. Moreover, to facilitate rapidevaluation of NMS methods for researchers, we introduce NMS-Bench, the firstbenchmark designed to comprehensively assess various NMS methods. Taking theYOLOv8-N model on MS COCO 2017 as the benchmark setup, our method QSI-NMSprovides $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 withno compromise in mAP.