Abstract
In this paper, we propose an algorithm, named hashing-based non-maximum suppression (HNMS) to efficiently suppress the non-maximum boxes for object detection. Non-maximum suppression (NMS) is an essential component to suppress the boxes at closely located locations with similar shapes. The time cost tends to be huge when the number of boxes becomes large, especially for crowded scenes. The basic idea of HNMS is to firstly map each box to a discrete code (hash cell) and then remove the boxes with lower confidences if they are in the same cell. Considering the intersection-over-union (IoU) as the metric, we propose a simple yet effective hashing algorithm, named IoUHash, which guarantees that the boxes within the same cell are close enough by a lower IoU bound. For two-stage detectors, we replace NMS in region proposal network with HNMS, and observe significant speed-up with comparable accuracy. For one-stage detectors, HNMS is used as a pre-filter to speed up the suppression with a large margin. Extensive experiments are conducted on CARPK, SKU-110K, CrowdHuman datasets to demonstrate the efficiency and effectiveness of HNMS. Code is released at https://github.com/microsoft/hnms.git.
Introduction
Standard Non-Maximum Suppression (NMS) is a critical post-processing step in object detection, responsible for thinning out redundant candidate bounding boxes. However, traditional NMS algorithms rely on pairwise comparisons, leading to a quadratic time complexity of $O(N^2)$. While manageable for sparse images, this becomes a significant computational bottleneck in crowded scenes where the number of boxes $N$ is high. In datasets like CARPK (aerial parking lots) or SKU-110K (dense retail shelves), NMS can consume a disproportionate amount of total inference time, particularly on CPUs.
Methods
The proposed Hashing-based NMS (HNMS) addresses this complexity by treating suppression as a hashing task, reducing the complexity to $O(N)$.
IoUHash Function
The core of HNMS is IoUHash, a data-independent hashing algorithm designed specifically for the Intersection-over-Union (IoU) metric. It quantizes a box's dimensions (width and height) on a logarithmic scale and its spatial offsets ($x$ and $y$) on a natural scale relative to its size. This ensures that boxes with similar shapes and locations are mapped to the same "hash cell."
The hashing logic is grounded in the observation that for two boxes to have a high IoU, they must have similar sizes and small relative offsets. As shown in Figure 3, the IoU can be bounded by comparing widths and center distances.
Implementation Strategies
To handle the "boundary problem"—where similar boxes might fall into different cells due to grid lines—the authors employ Multi-HNMS, running the process $K$ times with varying grid offsets. HNMS can be integrated into existing architectures in two ways:
- Two-stage detectors: Replacing NMS entirely within the Region Proposal Network (RPN).
- One-stage detectors: Serving as a fast "pre-filter" to reduce the box count before a final standard NMS pass.
Experimental Results
The researchers evaluated HNMS on high-density benchmarks including CARPK, SKU-110K, and CrowdHuman.
- Speedup: HNMS achieved a 7.4x speedup on the CARPK dataset using a CPU and a 6.8x speedup on a GPU. For one-stage detectors like RetinaNet, it reduced suppression time from ~260ms to ~34ms on CPU.
- Accuracy: HNMS maintained comparable Mean Average Precision (mAP) to traditional NMS. Interestingly, the efficiency of HNMS allows for processing more candidate boxes (e.g., increasing from 1,000 to 9,000 on CARPK), which actually improved mAP by nearly 2 points.
Conclusion
HNMS provides a scalable solution for object detection in crowded environments by achieving linear time complexity. While it is an approximation of the greedy NMS algorithm, its theoretical IoU bounds and empirical performance demonstrate its effectiveness. Future work may involve extending this hashing approach to other metrics or integrating it into more diverse detection architectures.
Summary updated