← All problems
#117 Non Max Suppression Hard

Implement Non-Maximum Suppression (NMS), the post-processing pass that every object detector runs after the network forward pass: the model emits thousands of overlapping candidate boxes, and NMS collapses them down to one box per object. Given N boxes in corner format (x1, y1, x2, y2) together with their confidence scores, walk the boxes from the highest score to the lowest; every box that has not been suppressed yet is kept, and it suppresses all lower-scoring boxes whose intersection over union (IoU) with it is greater than iou_threshold. Write a 1 into keep[i] for a surviving box and a 0 for a suppressed one.

6 candidates 0.90 0.75 0.95 0.60 0.55 0.50 NMS IoU > 0.5 3 survivors 0.90 0.75 0.95 0.60 0.55 0.50 keep = [1, 0, 1, 0, 1, 0] solid = kept, dashed = suppressed

The overlap of two boxes \(a\) and \(b\) is measured by their intersection over union:

\[ \text{IoU}(a, b) = \frac{|a \cap b|}{|a| + |b| - |a \cap b|} \] \[ |a| = (x_2^a - x_1^a)\,(y_2^a - y_1^a), \qquad |a \cap b| = w \cdot h \] \[ w = \max\!\left(0,\; \min(x_2^a, x_2^b) - \max(x_1^a, x_1^b)\right), \qquad h = \max\!\left(0,\; \min(y_2^a, y_2^b) - \max(y_1^a, y_1^b)\right) \]

Algorithm

  1. Order the box indices by score, from highest to lowest. Boxes with equal scores are ordered by increasing index.
  2. Traverse that order. If the current box has already been suppressed, skip it. Otherwise set its keep entry to 1 and suppress every box that appears later in the order whose IoU with it is greater than iou_threshold.
  3. Every suppressed box gets a keep entry of 0.

A suppressed box never suppresses anything itself, so the decisions are chained: whether box \(j\) survives depends on which higher-scoring boxes survived before it.

Implementation Requirements

Example

Six candidates covering three objects, with iou_threshold = 0.5:

\[ \text{boxes} = \begin{bmatrix} 0 & 0 & 40 & 40 \\ 5 & 5 & 45 & 45 \\ 60 & 0 & 100 & 40 \\ 65 & 5 & 105 & 45 \\ 30 & 50 & 70 & 90 \\ 35 & 55 & 75 & 95 \end{bmatrix}, \qquad \text{scores} = \begin{bmatrix} 0.90 & 0.75 & 0.95 & 0.60 & 0.55 & 0.50 \end{bmatrix} \] \[ \text{keep} = \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 \end{bmatrix} \]

Box 2 has the highest score, so it is kept and suppresses box 3 (\(\text{IoU} = \tfrac{1225}{1975} \approx 0.62\)). Box 0 is kept next and suppresses box 1 by the same overlap, and box 4 is kept and suppresses box 5. Boxes from different objects never overlap here, so all three winners survive.

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.