Non-maximum suppression

Deep dive

How it works

In: candidates (box or position, score) + overlap threshold · Out: indices of kept candidates · State: none between calls (one suppressed flag per candidate) · Cost: O(n log n + n·kept), O(n²) worst case

1. Drop candidates with score ≤ min_score; optionally keep only the k best (top-k pre-filter).
2. Sort the rest by score, best first.
3. Take the best remaining candidate, mark it kept.
4. Suppress every remaining candidate whose overlap with it exceeds the threshold (hard NMS), or multiply its score by a decay f(overlap) (Soft-NMS).
5. Repeat from 3 until none are left. Soft-NMS re-picks the maximum each round because scores changed.
6. Per-class NMS runs steps 1-5 per label, so a person box never suppresses the chair it overlaps; class-agnostic NMS runs once and also removes cross-label duplicates.

Overlap measures. IoU = intersection / union. DIoU = IoU − (centre distance)² / (enclosing-box diagonal)²; DIoU-NMS (Zheng et al.) suppresses on DIoU, so two boxes with equal IoU but far-apart centres are more likely both kept. Soft-NMS decays: linear s·(1−iou) above the threshold, or Gaussian s·exp(−iou²/σ), which is continuous and the version coded below.

Ensembles. Weighted Boxes Fusion (Solovyev et al.) clusters boxes from several models by IoU and outputs the confidence-weighted average box, so every model contributes to the final coordinates instead of one box winning.

Beyond boxes.

• 1-D peaks: local maxima, strongest first, drop any closer than min_dist samples to a kept peak (scipy.signal.find_peaks(distance=…) removes smaller peaks first until the condition holds).
• Images: keep a pixel only if it is the maximum of its (2r+1)² window (corner detectors; Canny thins edges by suppressing non-maxima across the gradient direction); Neubeck and Van Gool give fast window algorithms.
• Time: the same loop on 1-D intervals (temporal IoU) for action and event proposals; tracking then starts from cleaned detections.
• Ranking: greedy pick-then-penalise on similarity is maximal marginal relevance; near-identical documents can also be removed up front with MinHash.

Code

Greedy NMS with IoU or DIoU, Gaussian Soft-NMS, top-k pre-filter and 1-D peak picking; std only. Compiled and run (rustc 1.99.1): all asserts pass.

#[derive(Clone, Copy)]
pub struct B { pub x1: f32, pub y1: f32, pub x2: f32, pub y2: f32 }

fn area(b: &B) -> f32 { (b.x2 - b.x1).max(0.0) * (b.y2 - b.y1).max(0.0) }

pub fn iou(a: &B, b: &B) -> f32 {
    let w = (a.x2.min(b.x2) - a.x1.max(b.x1)).max(0.0);
    let h = (a.y2.min(b.y2) - a.y1.max(b.y1)).max(0.0);
    let inter = w * h;
    inter / (area(a) + area(b) - inter + 1e-9)
}

/// DIoU = IoU - (centre distance)^2 / (enclosing-box diagonal)^2
pub fn diou(a: &B, b: &B) -> f32 {
    let (cx, cy) = ((a.x1 + a.x2 - b.x1 - b.x2) / 2.0, (a.y1 + a.y2 - b.y1 - b.y2) / 2.0);
    let (w, h) = (a.x2.max(b.x2) - a.x1.min(b.x1), a.y2.max(b.y2) - a.y1.min(b.y1));
    iou(a, b) - (cx * cx + cy * cy) / (w * w + h * h + 1e-9)
}

/// Drop scores <= min_score, keep the k best. Indices, best first.
pub fn prefilter(scores: &[f32], min_score: f32, k: usize) -> Vec<usize> {
    let mut idx: Vec<usize> = (0..scores.len()).filter(|&i| scores[i] > min_score).collect();
    let cmp = |a: &usize, b: &usize| scores[*b].total_cmp(&scores[*a]);
    if idx.len() > k { idx.select_nth_unstable_by(k, cmp); idx.truncate(k); }
    idx.sort_unstable_by(cmp);
    idx
}

/// Greedy NMS. `order` = candidates sorted best first; `ov` = iou or diou.
pub fn nms(boxes: &[B], order: &[usize], thr: f32, ov: fn(&B, &B) -> f32) -> Vec<usize> {
    let mut keep: Vec<usize> = Vec::new();
    for &i in order {
        if keep.iter().all(|&j| ov(&boxes[i], &boxes[j]) <= thr) { keep.push(i); }
    }
    keep
}

/// Gaussian Soft-NMS: take the best box, decay the rest by exp(-iou^2/sigma), repeat.
pub fn soft_nms(boxes: &[B], scores: &[f32], sigma: f32, min_score: f32) -> Vec<(usize, f32)> {
    let mut pool: Vec<(usize, f32)> = scores.iter().copied().enumerate().collect();
    let mut out = Vec::new();
    while let Some(m) = (0..pool.len()).max_by(|&a, &b| pool[a].1.total_cmp(&pool[b].1)) {
        let (bi, bs) = pool.swap_remove(m);
        if bs < min_score { break; } // the best is below the floor, so are all others
        out.push((bi, bs));
        for p in pool.iter_mut() {
            let o = iou(&boxes[bi], &boxes[p.0]);
            p.1 *= (-o * o / sigma).exp();
        }
    }
    out
}

/// 1-D peaks: local maxima, strongest first, kept if >= min_dist from all kept. Sorted by position.
pub fn peaks(x: &[f32], min_dist: usize) -> Vec<usize> {
    let mut cand: Vec<usize> = (1..x.len().saturating_sub(1)).filter(|&i| x[i] > x[i - 1] && x[i] >= x[i + 1]).collect();
    cand.sort_by(|&a, &b| x[b].total_cmp(&x[a]).then(a.cmp(&b)));
    let mut keep: Vec<usize> = Vec::new();
    for i in cand {
        if keep.iter().all(|&j| i.abs_diff(j) >= min_dist) { keep.push(i); }
    }
    keep.sort_unstable();
    keep
}

fn main() {
    let b = |x: f32| B { x1: x, y1: 0.0, x2: x + 10.0, y2: 10.0 };
    // A, near-duplicate D (IoU 0.82 with A), true neighbour N (IoU 0.67 with A), far box C
    let boxes = [b(0.0), b(1.0), b(2.0), b(50.0)];
    let scores = [0.9, 0.8, 0.85, 0.7];
    let order = prefilter(&scores, 0.05, 100);
    assert_eq!(order, vec![0, 2, 1, 3]);
    assert_eq!(nms(&boxes, &order, 0.5, iou), vec![0, 3]); // D and N both dropped
    assert_eq!(nms(&boxes, &order, 0.7, iou), vec![0, 2, 3]); // looser: N kept, D still dropped
    assert!(diou(&boxes[0], &boxes[2]) < iou(&boxes[0], &boxes[2]));
    let soft = soft_nms(&boxes, &scores, 0.5, 0.25);
    let sc = |i| soft.iter().find(|p| p.0 == i).map(|p| p.1);
    assert_eq!((sc(0), sc(3)), (Some(0.9), Some(0.7))); // best and distant box untouched
    assert!(sc(1).is_none()); // duplicate decayed below the floor
    let n = sc(2).expect("neighbour survives");
    assert!(n < 0.85 && n > 0.3, "decayed but kept: {n}");
    let x = [0., 1., 5., 1., 0., 4., 0., 0., 3., 3.5, 0.];
    assert_eq!(peaks(&x, 3), vec![2, 5, 9]);
    assert_eq!(peaks(&x, 4), vec![2, 9]); // 4@5 is only 3 from the stronger 5@2
}

Complexity and constants

• Greedy: sort O(n log n) plus n × |kept| overlap tests. Worst case (nothing overlaps) n²/2; the fewer boxes survive, the cheaper the loop.
• Soft-NMS: O(n²) because every pick rescans the pool; the paper states the same order as NMS.
• The loop is compare-bound, not memory-bound, for n up to a few thousand (boxes fit in L1/L2).
• Matrix NMS (Wang et al., SOLOv2) computes all pairwise IoUs as one n×n matrix and derives decays from it with parallel ops: O(n²) work but no sequential dependency, a good fit for GPUs.

Efficiency

• Cost: measured on Apple M4 Pro, one thread, f32, synthetic data (20 jittered boxes per object, IoU 0.5), n = 1,000 candidates: about 100 µs (about 10 M boxes/s, 111 kept). n = 10,000 with no pre-filter: about 8.0 ms (about 1.2 M boxes/s, 1,123 kept). n = 10,000 with top-k = 1,000: about 0.54 ms (about 18 M input boxes/s; 555 kept). Bound: compute, n × kept tests. The pre-filter run also drops half the survivors, so it changes the output.
• Levers:
  • top-k / score pre-filter — about 15× here (measured), accuracy risk if k is below the true object count — when n ≫ objects.
  • batch per class with one call (offset boxes by class id, or batched_nms) — one launch instead of C — many classes, GPU.
  • spatial grid or sorted x-intervals over the kept set — checks only nearby kept boxes (cf. spatial hashing, sweep and prune) — n and kept both large.
  • bitmask / matrix formulation on GPU — removes the sequential loop (SOLOv2) — thousands of candidates per image.
  • NMS-free model — removes the stage and its threshold (DETR) — when you can train it.
• Naive → standard → state of the art:
  • all-pairs IoU matrix, then repeated scans · O(n²) time and memory
  • top-k, sort, greedy against kept set · O(n log n + n·kept), the library default
  • GPU matrix/bitmask NMS, or a set-prediction head that needs none · one parallel pass or none

Implementation notes

• Sort once with total_cmp; NaN scores otherwise panic or reorder. Use a stable order so ties give reproducible output.
• Structure-of-arrays boxes (x1[], y1[], x2[], y2[]) let SIMD test one candidate against many kept boxes.
• The 1e-9 in the union stops zero-area boxes giving NaN.
• Compare <= vs < consistently with the reference library; IoU exactly at the threshold happens with integer boxes.
• Start at IoU 0.5 and σ = 0.5 for Gaussian Soft-NMS; tune the threshold on a validation set.

Pitfalls

• Crowds: a true neighbour at IoU 0.6 with the best box vanishes at threshold 0.5. Raise it, use Soft-NMS or DIoU-NMS, or accept the recall cost.
• Soft-NMS never deletes, so it needs a final score floor, and its output length varies.
• Scores are not comparable across classes or models; calibrate or use per-class thresholds.
• NMS runs after training and is not differentiable; evaluate with AP/mAP at the deployed threshold.
• Class-agnostic NMS removes legitimate overlapping objects of different classes.
• Peak picking on noise: pair min_dist with a prominence or height threshold, or every ripple is a candidate.

Variants and alternatives

In production

• Object detectors in vision pipelines (driving, retail, surveillance, medical imaging): torchvision.ops.nms / batched_nms, OpenCV cv::dnn::NMSBoxes.
• Signal analysis: scipy.signal.find_peaks with distance; spectral, seismic and onset pickers use the same minimum-spacing rule.
• Feature detectors: window non-maximum suppression in corner detection; Canny edge thinning.
• Competition ensembles on Open Images and COCO used WBF (the authors report top results).

Implementations

Sources

• Bodla, Singh, Chellappa, Davis, Soft-NMS: Improving Object Detection With One Line of Code, ICCV 2017. paper · code
• Zheng et al., Distance-IoU Loss: Faster and Better Learning for Bounding Box Regression, AAAI 2020. paper · code
• Solovyev, Wang, Gabruseva, Weighted boxes fusion: Ensembling boxes from different object detection models, Image and Vision Computing 2021 (arXiv 2019). paper · code
• Wang, Zhang, Kong, Li, Shen, SOLOv2: Dynamic and Fast Instance Segmentation, NeurIPS 2020 (Matrix NMS). paper
• Carion et al., End-to-End Object Detection with Transformers, arXiv 2020. paper
• Neubeck, Van Gool, Efficient Non-Maximum Suppression, ICPR 2006, pp. 850-855. paper
• Canny, A Computational Approach to Edge Detection, IEEE TPAMI 8(6), 679-698, 1986. paper
• torchvision.ops.nms · batched_nms · scipy.signal.find_peaks · imageproc::suppress