Non-Maximum Suppression (NMS)
You are given a list of bounding box detections with confidence scores and must apply Non-Maximum Suppression to remove redundant overlapping detections.
Object detectors often produce multiple overlapping boxes for the same object. NMS keeps only the most confident detection and removes boxes that overlap significantly with it.
The algorithm:
- Sort all boxes by confidence score (descending)
- Select the highest-scoring box, add to keep list
- Remove all boxes with IoU > threshold with the selected box
- Repeat steps 2-3 until no boxes remain
- Return indices of kept boxes
IoU(A,B)=∣A∪B∣∣A∩B∣
Boxes with IoU > threshold are considered to be detecting the same object.
Example:
boxes = [[0,0,10,10,0.9], [1,1,11,11,0.8], [50,50,60,60,0.7]] iou_threshold = 0.5
[0, 2]
-
Sort by score: boxes are already sorted (0.9, 0.8, 0.7)
-
Iteration 1:
- Select box 0 (score=0.9), add to keep: [0]
- Check IoU with remaining boxes:
- IoU(box0, box1) ≈ 0.68 > 0.5 → suppress box 1
- IoU(box0, box2) = 0 ≤ 0.5 → keep box 2
- Remaining: [box 2]
-
Iteration 2:
- Select box 2 (score=0.7), add to keep: [0, 2]
- No remaining boxes
-
Return sorted indices: [0, 2]
Box 1 was suppressed because it overlaps significantly with the higher-scoring box 0.
Constraints:
- boxes: list of [x1, y1, x2, y2, score] where score is confidence
- iou_threshold: boxes with IoU > threshold are suppressed (typically 0.5)
- Return list of indices of kept boxes, sorted in ascending order
You can view this as a classic greedy filtering problem over intervals in 2D, where the filtering rule is defined by IoU and confidence scores.
1. Background Knowledge
In object detection, a model predicts many candidate bounding boxes for each object, each with a confidence score (how likely it is that a box contains an object of a given class). These boxes are axis-aligned rectangles, usually represented as (x1,y1,x2,y2) (top-left and bottom-right corners) or (x,y,w,h) (top-left plus width/height).
Because detectors are conservative, they output many overlapping boxes around the same object. To obtain a clean set of detections, we use Non-Maximum Suppression (NMS): keep the best (highest-score) box and remove nearby boxes that overlap “too much” with it. Overlap is measured by Intersection over Union (IoU):
IoU(A,B)=∣A∪B∣∣A∩B∣If IoU is above a chosen threshold (e.g., 0.5), the boxes are considered duplicates and the lower-score one is suppressed.
NMS is a post-processing step used by many detectors (e.g., Faster R-CNN, SSD, YOLO) to turn dense proposals into a compact set of final detections. It is usually applied per class (i.e., run NMS separately for each object category).
2. Algorithm / Approach Pattern
The standard pattern (Greedy NMS):
- Sort all boxes by confidence score in descending order.
- Iterate from highest-score to lowest:
- Take the current highest-score box (not yet removed).
- Compute IoU with all remaining boxes.
- Keep this box.
- Suppress (remove) any boxes whose IoU with this box is greater than the threshold.
- Continue until no boxes remain.
- Return the indices of the kept boxes (in original order or sorted by score, depending on the problem).
Key characteristics:
- Greedy: once a box is kept, it is never removed later.
- Local rule: overlap is computed pairwise using IoU.
- Threshold-based: behavior is controlled by a single IoU threshold.
3. Step-by-Step Strategy for Implementation
Assume input:
- boxes: array of shape [N, 4] (bounding boxes)
- scores: array of shape [N]
- threshold: IoU threshold
Step 1: Preprocess and sort
- Create an array of indices idx = [0, 1,..., N-1].
- Sort indices in descending order of scores:
idx = sorted(idx, key=lambda i: scores[i], reverse=True)
- Initialize an empty list keep = [].
Step 2: Main NMS loop
While idx is not empty:
- Pick top index:
current = idx
keep.append(current)
- Compute IoU between boxes[current] and all other boxes in idx[1:].
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.