Non-Max Suppression (NMS)

Background

Non-Maximum Suppression is the universal de-duplication step in object detection: keep the highest-scoring box, suppress every other box that overlaps it above an IoU threshold, repeat. Without NMS your detector returns dozens of slightly-shifted boxes for the same object.

Problem statement

Implement nms(boxes, scores, iou_threshold). boxes is shape $(n, 4)$ as $(x_1, y_1, x_2, y_2)$. Return a list of indices (kept boxes), in score-descending order.

Greedy: while indices remain, pick the highest-scoring index, add it to the keep list, drop everything with $\text{IoU} \ge \text{threshold}$ to it.

Input

• boxes - array shape $(n, 4)$, $(x_1, y_1, x_2, y_2)$.
• scores - array length $n$.
• iou_threshold - float in $[0, 1]$.

Output

• list[int] of kept indices.

Examples

Input: 3 boxes, the first two overlap heavily, third is distinct
Output: keep box 0 (highest score), suppress box 1, keep box 2

Constraints

• Tie-break by lower index on equal scores.
• Empty input -> empty list.

Notes

• vs soft-NMS. Standard NMS suppresses; soft-NMS down-weights. Soft-NMS is a follow-on; this problem isolates the canonical greedy form.