Non-Maximum Suppression

A detection is a tuple $(b, s, c)$: a bounding box $b$, a confidence score $s \in [0,1]$, and (in a multi-class setting) a class label $c$. A raw detector output is a large set $D = \{d_1, \dots, d_n\}$ of such tuples, typically thousands per image before filtering, because dense anchor grids or sliding windows generate many boxes near every true object. The goal of NMS is to reduce $D$ to a much smaller set $D^*$ that contains, ideally, exactly one box per real object, discarding the near-duplicates. The key notion of "near-duplicate" is Intersection-over-Union, also called the Jaccard index applied to boxes:

IoU is $1$ for identical boxes, $0$ for disjoint boxes, and smoothly interpolates in between. It is scale-invariant (doubling both boxes' sizes proportionally does not change IoU) and symmetric, which makes it a natural similarity measure independent of object size. NMS declares two boxes "duplicates of the same object" when $\mathrm{IoU}(b_1, b_2)$ exceeds a chosen threshold $\tau$ (commonly $0.3$–$0.7$ depending on the dataset and task). The algorithm itself is a greedy set cover by confidence rank: always trust the most confident remaining box as evidence of a real object, then remove everything that overlaps it enough to plausibly be describing the same object. This is applied independently per class in multi-class detection, since two boxes of different classes (say "person" and "skateboard") are allowed to overlap heavily without being duplicates of each other.

NMS operates on one class at a time (run it once per class, or once globally if class-agnostic suppression is desired). The steps are: 1. Collect all detections for the class, each with a box and a score. 2. Sort them by descending confidence score. 3. Take the highest-scoring box, add it to the output (kept) list, and remove it from the pending list. 4. Compute IoU between this kept box and every remaining pending box. 5. Discard (suppress) any pending box whose IoU with the kept box exceeds threshold $\tau$. 6. Repeat from step 3 with whatever remains, until the pending list is empty. ``` function NMS(boxes, scores, iou_threshold):

# boxes: list of n bounding boxes (x1, y1, x2, y2)

# scores: list of n confidence scores, same order as boxes

# returns: indices of boxes to KEEP order = argsort(scores, descending=True) # O(n log n) keep = [] while order is not empty: i = order[0] # index of current highest-scoring box keep.append(i) rest = order[1:] survivors = [] for j in rest: if IoU(boxes[i], boxes[j]) <= iou_threshold: survivors.append(j) # box j is NOT a duplicate of i, keep pending

# else: box j overlaps too much with i, suppress it permanently order = survivors return keep

function IoU(boxA, boxB): xi1 = max(boxA.x1, boxB.x1) yi1 = max(boxA.y1, boxB.y1) xi2 = min(boxA.x2, boxB.x2) yi2 = min(boxA.y2, boxB.y2) inter_w = max(0, xi2 - xi1) inter_h = max(0, yi2 - yi1) intersection = inter_w inter_h areaA = (boxA.x2 - boxA.x1) (boxA.y2 - boxA.y1) areaB = (boxB.x2 - boxB.x1) * (boxB.y2 - boxB.y1) union = areaA + areaB - intersection if union <= 0: return 0.0 return intersection / union ``` Two implementation details deserve emphasis because they are frequent sources of bugs. First, IoU must be computed against the just-kept box, never against a box that has already been suppressed — a suppressed box carries no further authority. Second, the clamp `max(0, ...)` on intersection width and height is essential: when boxes do not overlap, `xi2 - xi1` or `yi2 - yi1` can be negative, and without clamping, "negative area" would corrupt the intersection computation. For multi-class detection, the whole procedure is wrapped in a loop over classes, and for large box counts, a per-class limit (e.g., only the top 1000 boxes by score) is applied before sorting to control cost. ``` function MultiClassNMS(all_boxes, all_scores, all_classes, iou_threshold): final_keep = [] for each class c in distinct(all_classes): idx = indices where all_classes == c kept_local = NMS(all_boxes[idx], all_scores[idx], iou_threshold) final_keep.extend(idx[kept_local]) return final_keep ```

Time complexity. Let $n$ be the number of candidate boxes for a given class. Sorting by score costs $O(n \log n)$. The main loop, in the worst case, keeps one box per iteration while comparing it against all remaining boxes: iteration $k$ compares against roughly $n-k$ boxes, giving

in the worst case, which occurs when almost no boxes overlap (nothing gets suppressed early, so the pending list shrinks by only one per round). In the best case — when the first box suppresses nearly everything — the loop terminates in $O(n)$ comparisons after one round. In practice, detectors cap the number of pre-NMS boxes per class (e.g., top-$k$ by score, $k \approx 1000$) precisely to bound this worst case, since raw anchor counts can reach $10^4$–$10^5$ per image. Overall cost is therefore $O(n \log n + n^2)$, dominated by the quadratic term for large $n$; with a top-$k$ cap it becomes $O(n \log n + k^2)$.

Space complexity. $O(n)$ to store boxes, scores, and the sorted order; no auxiliary structure grows the space beyond this, since IoU is computed on the fly.

Correctness argument. NMS is not solving an explicitly stated optimization problem with a proven-optimal solution — it is a heuristic — but its greedy design is justifiable via an exchange argument under a natural model of detector behavior. Assume: (1) every true object generates a cluster of detections whose pairwise IoUs (and IoU with the true box) are high, (2) detections from different objects have IoU near $0$ unless the objects are physically close and heavily occluding each other, and (3) within a cluster, the detector's highest-confidence box is (probabilistically) the best localization of the true object. Under these assumptions, consider any cluster of detections belonging to one object. Because IoU within the cluster exceeds $\tau$ by assumption (1), once the highest-scoring member of the cluster is chosen as "kept" (which happens because sorting processes it before any weaker member of the same cluster, and no earlier unrelated kept box can suppress it if assumption (2) holds), every other member of the cluster has IoU $> \tau$ with it and is therefore suppressed in that same round. Hence each cluster contributes exactly one kept box, and it is the best-localized one by assumption (3). Boxes belonging to different, well-separated objects have IoU near $0$ with each other, so assumption (2) guarantees they never suppress one another, and each survives to be kept in its own right. The two failure modes of the algorithm map exactly onto violations of these assumptions: if two true objects are close enough that assumption (2) fails (crowded scenes, occlusion), NMS can wrongly suppress a correct detection of the second object because its IoU with the first object's box exceeds $\tau$. If assumption (1) fails — the detector produces two disjoint clusters for what is truly one irregularly-shaped or elongated object — NMS can leave duplicate boxes standing. These are inherent to the hard IoU-threshold rule, not implementation bugs, and they motivate the soft variants discussed below.

Honest tradeoff. NMS trades a small, bounded risk of over-suppression (crowded scenes) for a large, reliable reduction in duplicate detections, and it does so with no learned parameters beyond the single threshold $\tau$, making it cheap, interpretable, and dataset-agnostic — but also brittle to $\tau$'s exact value and non-differentiable, which complicates end-to-end training of detection heads.

Suppose a detector outputs five boxes for the class "car" in one image, given as $(x_1, y_1, x_2, y_2)$ with confidence score, and we run NMS with $\tau = 0.5$.

Round 1. Sorted order by score: A, B, C, D, E. Pop A (score 0.95), add to `keep`. Compute IoU(A, X) for remaining boxes:

• IoU(A, B): intersection $x$-overlap $= \min(260,270)-\max(100,120)=140$, $y$-overlap $=\min(200,205)-\max(100,110)=90$, intersection $=12{,}600$. Area(A) $=160\times100=16{,}000$; Area(B) $=150\times95=14{,}250$. Union $=16{,}000+14{,}250-12{,}600=17{,}650$. IoU $=12{,}600/17{,}650 \approx 0.714$. This exceeds $\tau=0.5$ → suppress B.
• IoU(A, C): $x$-overlap $=\min(260,250)-\max(100,95)=155$, $y$-overlap $=\min(200,190)-\max(100,90)=90$, intersection $=13{,}950$. Area(C) $=155\times100=15{,}500$. Union $=16{,}000+15{,}500-13{,}950=17{,}550$. IoU $=13{,}950/17{,}550\approx 0.795$ → suppress C.
• IoU(A, D): boxes occupy disjoint $x$-ranges ($260 < 400$) → intersection $=0$ → IoU $=0$ → D survives.
• IoU(A, E): disjoint $x$-ranges similarly → IoU $=0$ → E survives.

Pending list after round 1: `{D, E}`. Kept so far: `{A}`.

Round 2. Pop D (score 0.77, the top of what remains), add to `keep`.

• IoU(D, E): $x$-overlap $=\min(550,555)-\max(400,410)=140$, $y$-overlap $=\min(200,205)-\max(100,105)=95$, intersection $=13{,}300$. Area(D)$=150\times100=15{,}000$; Area(E)$=145\times100=14{,}500$. Union $=15{,}000+14{,}500-13{,}300=16{,}200$. IoU $=13{,}300/16{,}200\approx0.821$ → exceeds $\tau$ → suppress E.

Pending list empty. Final `keep = {A, D}` — exactly the two real cars, correctly recovered from five raw boxes, matching the two well-separated clusters {A, B, C} and {D, E}.

A harder case (crowded scene). Now suppose box D actually belongs to a second, distinct car standing close to the first car, but a detector artifact makes IoU(A, D) $= 0.55$ instead of $0$ (e.g., the two cars visually overlap due to camera angle). With $\tau = 0.5$, D would be wrongly suppressed by A in round 1, and the detector would report only one car where two exist. This is the textbook failure mode of hard-threshold NMS in crowded or occluded scenes, and it is exactly why Soft-NMS (which decays D's score rather than deleting it outright) or class-specific/learned suppression is used in pedestrian-detection and crowd-counting pipelines.

Non-Maximum Suppression predates deep learning by decades: it originates in classical edge detection and template matching, where multiple pixel-level responses cluster around a single true edge or feature, and the same greedy peak-picking logic is needed to collapse them. The bounding-box version used in modern object detection is a direct descendant of this signal-processing idea, popularized in vision through the Viola–Jones face detector and later formalized as a standard component of the R-CNN line of detectors and every subsequent single-shot architecture.

Every production object detector that outputs bounding boxes — from smartphone camera face detection, to warehouse robotics picking systems, to autonomous-vehicle perception stacks, to video surveillance analytics — runs some form of NMS as the final inference step before boxes reach a downstream consumer. Frameworks such as torchvision, Detectron2, the TensorFlow Object Detection API, and YOLO's reference implementations all ship a fused, hardware-accelerated NMS kernel, since it runs once per image on real-time video streams and its cost must stay negligible next to the network's forward pass. Medical imaging pipelines that detect tumors or cells, retail analytics that count shelf products, and traffic-monitoring systems that detect and track vehicles all depend on NMS to avoid double-counting. Its continued ubiquity, despite being older and simpler than nearly everything else in a modern detection pipeline, is a reminder that a correct, cheap, interpretable post-processing step can outlive many generations of the learned models that feed it.

Ask the tutor: How would you modify the pseudocode above to implement Soft-NMS with a Gaussian score-decay penalty?