Non-Maximum Suppression (NMS)

hardPROObject DetectionDetectionCV: Recognition

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) = \frac{|A \cap B|}{|A \cup B|}$

Boxes with IoU > threshold are considered to be detecting the same object.

Example

Input

boxes = [[0,0,10,10,0.9], [1,1,11,11,0.8], [50,50,60,60,0.7]]
iou_threshold = 0.5

Output

[0, 2]

Reasoning

Input: three detections, each a box given by its top-left corner $(x_1, y_1)$ and bottom-right corner $(x_2, y_2)$ plus a confidence. Boxes 0 and 1 are $10 \times 10$ squares shifted one pixel diagonally; box 2 is far away.
Most confident first: box 0 (score $0.9$ ) is the strongest detection, so it survives no matter what.
Box 1 vs box 0: they overlap on the square from $(1,1)$ to $(10,10)$ , so $|A \cap B| = 9 \times 9 = 81$ . Each box has area $100$ , so $|A \cup B| = 100 + 100 - 81 = 119$ and $IoU = 81/119 \approx 0.68 > 0.5$ . Box 1 is a duplicate of box 0 and is suppressed.
Box 2 vs box 0: no overlap at all, so $IoU = 0 \le 0.5$ . Box 2 is a separate object and is kept.
Output: the surviving indices in ascending order, [0, 2].
Notice that box 1's score of $0.8$ is high on its own; it is dropped only because a more confident box already covers the same object.

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

Learn this in

RecognitionCV Study Plan

More from CV: Recognition

Face Alignment with Landmarkshard Cosine Similarity Face Matchingmedium Mean Intersection over Union (mIoU)hard Top-K Accuracy Computationhard Optimal Verification Thresholdmedium

Concept primerPREVIEW

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 $(x_1, y_1, x_2, y_2)$ (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) = \frac{|A \cap B|}{|A \cup 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:].

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results