Accelerating Non-Maximum Suppression: A Graph Theory Perspective

• URL: http://arxiv.org/abs/2409.20520v1
• Date: Mon, 30 Sep 2024 17:20:49 GMT
• Title: Accelerating Non-Maximum Suppression: A Graph Theory Perspective
• Authors: King-Siong Si, Lu Sun, Weizhan Zhang, Tieliang Gong, Jiahao Wang, Jiang Liu, Hao Sun,
• Abstract summary: Non-maximum suppression (NMS) is an indispensable post-processing step in object detection. This paper systematically analyzes NMS from a graph theory perspective for the first time, revealing its intrinsic structure. We introduce NMS-Bench, the first benchmark designed to comprehensively assess various NMS methods.
• Score: 24.34791528442417
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) aims to classify both base and novel images using labeled base data. Current approaches inadequately address the intrinsic optimization of the co-occurrence matrix $barA$ based on cosine similarity. We propose a Non-Negative Generalized Category Discovery (NN-GCD) framework to address these deficiencies.
  arXiv  Detail & Related papers  (2024-10-29T07:24:11Z)
• Fast Graph Sharpness-Aware Minimization for Enhancing and Accelerating Few-Shot Node Classification [53.727688136434345]
  Graph Neural Networks (GNNs) have shown superior performance in node classification. We present Fast Graph Sharpness-Aware Minimization (FGSAM) that integrates the rapid training of Multi-Layer Perceptrons with the superior performance of GNNs. Our proposed algorithm outperforms the standard SAM with lower computational costs in FSNC tasks.
  arXiv  Detail & Related papers  (2024-10-22T09:33:29Z)
• Entanglement Distribution Delay Optimization in Quantum Networks with Distillation [51.53291671169632]
  Quantum networks (QNs) distribute entangled states to enable distributed quantum computing and sensing applications. QS resource allocation framework is proposed to enhance the end-to-end (e2e) fidelity and satisfy minimum rate and fidelity requirements.
  arXiv  Detail & Related papers  (2024-05-15T02:04:22Z)
• Improved Optimization for the Neural-network Quantum States and Tests on the Chromium Dimer [11.985673663540688]
  Neural-network Quantum States (NQS) has significantly advanced wave function ansatz research. This work introduces three algorithmic enhancements to reduce computational demands of VMC optimization using NQS.
  arXiv  Detail & Related papers  (2024-04-14T15:07:57Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• SymNMF-Net for The Symmetric NMF Problem [62.44067422984995]
  We propose a neural network called SymNMF-Net for the Symmetric NMF problem. We show that the inference of each block corresponds to a single iteration of the optimization. Empirical results on real-world datasets demonstrate the superiority of our SymNMF-Net.
  arXiv  Detail & Related papers  (2022-05-26T08:17:39Z)
• NMS-Loss: Learning with Non-Maximum Suppression for Crowded Pedestrian Detection [39.417540296897194]
  We propose a novel NMS-Loss making the NMS procedure can be trained end-to-end without any additional network parameters. Our NMS-Loss punishes two cases when FP is not suppressed and FN is wrongly eliminated by NMS. With the help of NMS-Loss, our detector, namely NMS-Ped, achieves impressive results with Miss Rate of 5.92% on Caltech dataset and 10.08% on CityPersons dataset.
  arXiv  Detail & Related papers  (2021-06-04T12:06:46Z)
• PSRR-MaxpoolNMS: Pyramid Shifted MaxpoolNMS with Relationship Recovery [17.704037442897004]
  Non-maximum Suppression (NMS) is an essential postprocessing step in modern convolutional neural networks for object detection. The de-facto standard for NMS, namely GreedyNMS, cannot be easily parallelized. MaxpoolNMS is introduced as a parallelizable alternative to GreedyNMS.
  arXiv  Detail & Related papers  (2021-05-27T08:24:21Z)
• Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalization [89.7882166459412]
  gradient noise (SGN) acts as implicit regularization for deep learning. Some works attempted to artificially simulate SGN by injecting random noise to improve deep learning. For simulating SGN at low computational costs and without changing the learning rate or batch size, we propose the Positive-Negative Momentum (PNM) approach.
  arXiv  Detail & Related papers  (2021-03-31T16:08:06Z)
• ASAP-NMS: Accelerating Non-Maximum Suppression Using Spatially Aware Priors [26.835571059909007]
  Non Maximum Suppression (or Greedy-NMS) is a crucial module for object-detection pipelines. For the region proposal stage of two/multi-stage detectors, NMS is turning out to be a latency bottleneck due to its sequential nature. We use ASAP-NMS to improve the latency of the NMS step from 13.6ms to 1.2 ms on a CPU without sacrificing the accuracy of a state-of-the-art two-stage detector.
  arXiv  Detail & Related papers  (2020-07-19T21:15:48Z)
• Visibility Guided NMS: Efficient Boosting of Amodal Object Detection in Crowded Traffic Scenes [7.998326245039892]
  Modern 2D object detection frameworks predict multiple bounding boxes per object that are refined using Non-Maximum-Suppression (NMS) to suppress all but one bounding box. Our novel Visibility Guided NMS (vg-NMS) leverages both pixel-based as well as amodal object detection paradigms and improves the detection performance especially for highly occluded objects with little computational overhead. We evaluate vg-NMS using KITTI, VIPER as well as the Synscapes dataset and show that it outperforms current state-of-the-art NMS.
  arXiv  Detail & Related papers  (2020-06-15T17:03:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.