Problems
Loading...
1 / 1

Non-Maximum Suppression

Computer Vision
Medium

Object detectors often produce multiple overlapping bounding boxes for the same object. Non-Maximum Suppression (NMS) filters these duplicates by keeping only the highest-scoring box in each cluster of overlapping detections.

Given a list of bounding boxes (each as [x1, y1, x2, y2]), their confidence scores, and an IoU threshold, apply NMS and return the indices of the kept boxes.

Algorithm

  1. Sort all boxes by confidence score in descending order.
  2. Pick the box with the highest score and add its index to the output.
  3. Remove all remaining boxes whose IoU with the picked box is >= the threshold.
  4. Repeat from step 2 until no boxes remain.

Computing IoU

To compare two boxes, compute Intersection over Union. The intersection rectangle has corners:

x1′=max⁡(x1A,  x1B)y1′=max⁡(y1A,  y1B)x2′=min⁡(x2A,  x2B)y2′=min⁡(y2A,  y2B)x_1' = \max(x_1^A,\; x_1^B) \qquad y_1' = \max(y_1^A,\; y_1^B) \qquad x_2' = \min(x_2^A,\; x_2^B) \qquad y_2' = \min(y_2^A,\; y_2^B)

The intersection area is max(0, x2' - x1') * max(0, y2' - y1'). If the boxes do not overlap, this is zero.

IoU=IntersectionArea(A)+Area(B)−Intersection\text{IoU} = \frac{\text{Intersection}}{\text{Area}(A) + \text{Area}(B) - \text{Intersection}}

Return a list of the original indices of the kept boxes, in the order they were selected (highest score first). Return an empty list if the input is empty.

Loading visualization...

Examples

Input:

boxes = [[0, 0, 4, 4], [1, 0, 5, 4]] scores = [0.9, 0.8] iou_threshold = 0.5

Output: [0]

Box 0 (score 0.9) is selected first. Box 1 has IoU of 0.6 with Box 0, which exceeds the threshold, so it is suppressed.

Input:

boxes = [[0, 0, 2, 2], [5, 5, 7, 7], [10, 10, 12, 12]] scores = [0.7, 0.9, 0.8] iou_threshold = 0.5

Output: [1, 2, 0]

No boxes overlap, so all are kept. They are returned in order of decreasing score.

Hint 1

Sort indices by score first, then greedily select and filter.

Hint 2

You need an IoU function as a subroutine. Boxes that are suppressed should not suppress other boxes later.

Requirements

  • Process boxes in order of decreasing confidence score
  • Suppress boxes whose IoU with the selected box meets or exceeds the threshold
  • Return original indices of kept boxes in selection order
  • Handle empty input

Constraints

  • 0 <= len(boxes) <= 1000
  • Boxes are [x1, y1, x2, y2] with x1 <= x2, y1 <= y2
  • 0.0 <= scores[i] <= 1.0
  • 0.0 < iou_threshold <= 1.0
  • Time limit: 300 ms
Try Similar Problems
Iou Bounding BoxAnchor Box GenerationRoi PoolingBilinear InterpolationMean Average Precision
PrevNext