Object detectors fire many overlapping guesses for every real object. A cleanup step called non-maximum suppression (NMS) then keeps one box per object and discards the duplicates. Two families of NMS methods have grown apart. Accurate methods resolve crowds, where real neighbors legitimately overlap, by fitting statistical models to the candidate boxes, but they are slow. Fast methods make the cleanup near-linear in the number of boxes, but they only reproduce the simple greedy rule that fails in crowds. This gap matters more as detectors search over many scales and resolutions to catch small objects, because that search multiplies the number of candidate boxes. There is also direct evidence that keeping more candidates helps in dense scenes, provided the cleanup can keep up.
We propose to split the candidate set exactly into independent "overlap components", meaning groups of boxes that could possibly interact. These groups are found in near-linear time using geometric bounds on box overlap. The expensive crowd-aware resolver then runs inside each group separately. Its cost becomes the sum of squared group sizes rather than the square of the total box count. The open question that decides whether this works is empirical: do these groups stay small in genuinely crowded scenes, or do they merge into one giant group spanning a whole retail shelf? We answer that question first and build the rest around the answer.
Core Claim
Fast NMS papers have shown that suppression structure is sparse. Accelerating Non-Maximum Suppression: A Graph Theory Perspective treats greedy NMS as a directed graph over boxes and finds that, on COCO-style detector outputs, this graph breaks into small weakly connected pieces. It uses that finding only to speed up greedy NMS (BOE-NMS, a 5.1× speedup on YOLOv8-N with 0.0% mAP loss). Hashing-based Non-Maximum Suppression for Crowded Object Detection hashes boxes by log-scale and scale-relative position to reach linear time, again approximating greedy NMS. Separately, Precise Detection in Densely Packed Scenes replaces greedy NMS with an Expectation-Maximization (EM) merger that fits a Gaussian mixture to candidate boxes. It reaches 0.492 AP on SKU-110K against a 0.455 RetinaNet baseline, but runs at about 0.23 FPS versus 0.5 FPS for standard NMS on CPU.
Our claim is that the sparsity these acceleration papers found can serve as a computational substrate for crowd-aware resolution, not only for greedy NMS. If that holds, EM-style or learned suppression becomes affordable at the large candidate counts that multi-scale search produces. That in turn would let crowded-scene detectors keep the extra candidates that HNMS reports are worth nearly 2 mAP on CARPK when going from 1,000 to 9,000 boxes. Prior work joins sparsity to greedy NMS, and crowd modeling to full quadratic or global computation. Nobody in the file joins sparsity to crowd modeling.
Research Program
The first piece is an exact component builder. Two boxes $A$ and $B$ can only reach overlap $\text{IoU}(A,B) \ge \tau$, for an edge threshold $\tau$, if their areas are comparable. Since the intersection is no larger than the smaller box and the union is no smaller than the larger box,
$$\frac{\min(|A|,|B|)}{\max(|A|,|B|)} \ge \tau ,$$
where $|A|$ is the area of box $A$. The same argument bounds their centroid offset in units of box size. We bin boxes on a log-scale grid in width and height and a scale-relative grid in position, as IoUHash does. Unlike HNMS, we query all neighboring cells that the bounds allow rather than only the box's own cell. Retrieval is therefore exact: every pair with $\text{IoU} \ge \tau$ is found, and HNMS's bin-boundary misses disappear. A union-find pass over the retrieved edges then yields the components.
This builder works for anchor-free outputs and for boxes merged across pyramid levels, because it uses only box geometry. That removes the anchor-lattice dependence of ASAP-NMS. The size-compatibility bound also makes the builder automatically scale-aware. It never links boxes whose scales differ by more than $1/\tau$, which loosely echoes the scale "valid band" of SNIP.
The second piece is component-local resolution. Inside each component we run one of two resolvers. The first is the EM Gaussian-mixture merger of Goldman et al., unchanged except that it is fit per component. The second is a small learned rescorer in the spirit of Learning Non-maximum Suppression, which passes messages between boxes using only coordinates and scores. If $C_1,\dots,C_m$ are the components, resolution cost scales as
$$\text{cost} \propto \sum_{c=1}^{m} |C_c|^2 ,$$
because each resolver is at worst pairwise within a group. The gain over global resolution is therefore governed entirely by the component size distribution.
Splitting is exactly lossless for greedy NMS whenever $\tau$ equals the suppression threshold. For EM it is only an approximation, since Gaussians in different components still interact weakly. We will measure that approximation error directly rather than assume it away.
The third piece is the central measurement. We will measure component size distributions as a function of $\tau$ on cached detector outputs from SKU-110K, CARPK, CrowdHuman and COCO, at single-scale and multi-scale inference. The risk is percolation. At low $\tau$, adjacent shelf items chain into one giant component and the method collapses to global EM. CrowdHuman's statistics are mildly reassuring: the dataset paper CrowdHuman reports an average of 2.4 ground-truth pairs per image with IoU above 0.5. SKU-110K, at 147 objects per image, is the real test.
If components percolate at the low $\tau$ that EM needs, we change the design to a two-threshold scheme. A high threshold builds exact components. A thin, bounded halo of lower-overlap neighbors is passed to each component's resolver as fixed context, so it can see them without merging with them. We report which regime holds.
Baselines
The naive reference point is standard greedy NMS at a tuned IoU threshold, applied to the same cached candidates. On SKU-110K this corresponds to the RetinaNet baseline of 0.455 AP reported in Precise Detection in Densely Packed Scenes.
The strongest accuracy competitor is global EM-Merger from the same paper, at 0.492 AP on SKU-110K and a CARPK counting mean absolute error reduced from 16.62 to 6.77. It is the method our component-local version must match. We re-run it on identical cached boxes on the same CPU. Beating it means matching its AP within noise at several times its throughput. It also means exceeding its AP once both are allowed the larger candidate pools that only the fast version can process within a fixed time budget.
The strongest speed competitor is HNMS, which reduces RetinaNet suppression time from about 260 ms to about 34 ms on CPU on CARPK; we use the official Microsoft code. Alongside it we run BOE-NMS from the graph-theory paper. For CrowdHuman, no reported HNMS accuracy number was found on Lacuna, so we will measure it ourselves. Our method must stay within a small constant factor of HNMS latency while clearly exceeding its AP and log-miss rate in crowds.
For learned suppression, GossipNet reports +4.8 AP over tuned greedy NMS on PETS and about +1.0 mAP on COCO, at about 14 ms per image on GPU. We compare our learned per-component rescorer against a global version trained identically.
Two ablations isolate the key ingredient. First, we replace exact component retrieval with HNMS's single-cell hashing, which tests whether exactness matters. Second, we replace components with fixed spatial tiles of matched average size, which tests whether geometry-aware grouping matters versus arbitrary splitting. All methods get the same detector, the same cached candidates per NMS-Bench protocol, the same hardware, and the same threshold-tuning budget on a validation split.
Why not just…?
Why not just cap the candidate count at the top-k boxes and run EM globally? This is the most serious threat, because truncation is trivial to implement. The HNMS result that moving from 1,000 to 9,000 candidates on CARPK adds nearly 2 mAP suggests truncation discards useful boxes in crowds. We test it directly by plotting AP against wall-clock time for truncated global EM and component-local EM across many values of k. If truncated EM matches our curve, the proposal fails, and we will say so.
Why not just use Soft-NMS? Soft-NMS decays scores instead of deleting boxes. HNMS's authors note that it keeps more candidates alive and so does not reduce comparisons. Goldman et al. report that score decay still leaves misaligned overlapping boxes on SKU-110K. We include Soft-NMS as a baseline on all three crowded datasets rather than rely on those reports.
Why not just brute-force everything on a GPU? Parallel pairwise matrices keep quadratic work. Both ASAP-NMS (CPU NMS taking 13.6 ms on an 800×1280 image) and the graph-theory paper argue that post-processing often runs on a CPU while the GPU is busy with the backbone. We report CPU and GPU timings separately. If a batched GPU implementation of global EM matches our accuracy-time curve, the contribution narrows to CPU and edge settings.
Why not just tile the image and run EM per tile? Tiles cut objects at their borders and create the duplicated detections along stitching seams documented in Symbol Spotting on Digital Architectural Floor Plans. The matched-size tile ablation measures exactly this.
Proposed Experiments
Using NMS-Bench-style caching, we store raw candidates from RetinaNet and an anchor-free one-stage detector on SKU-110K, CARPK, CrowdHuman and COCO. We store them at one input scale and at a three-scale pyramid, so that candidate counts span roughly $10^3$ to beyond $10^4$ per image. We report AP, $\text{AP}_{50}$ and $\text{AP}_{75}$ on SKU-110K and COCO, log-miss rate and AP on CrowdHuman, counting error on CARPK, and per-image suppression latency on CPU and GPU.
The first decisive check is the component size distribution against $\tau$ on SKU-110K. If the largest component stays a small fraction of $N$ at the threshold EM needs, the approach is viable as designed; otherwise we report the two-threshold halo variant.
The second check is accuracy against time budget. At equal wall-clock budget, component-local EM over a multi-scale candidate pool should exceed global EM over a truncated pool on SKU-110K and CARPK.
The third check is a per-image measurement of the error introduced by splitting EM: the gap between global and component-local fits on identical candidates.
The fourth check verifies that exact retrieval reproduces greedy NMS output bit-for-bit at $\tau=0.5$, confirming the component builder before any crowd claims are made.
References
- Accelerating Non-Maximum Suppression: A Graph Theory Perspective
- Hashing-based Non-Maximum Suppression for Crowded Object Detection
- Precise Detection in Densely Packed Scenes.
- ASAP-NMS: Accelerating Non-Maximum Suppression Using Spatially Aware Priors
- An Analysis of Scale Invariance in Object Detection SNIP
- Learning Non-maximum Suppression
- CrowdHuman: A Benchmark for Detecting Human in a Crowd
- Symbol Spotting on Digital Architectural Floor Plans Using a Deep Learning-based Framework