Problems

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

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

Computing IoU

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

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.

\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 Box Anchor Box Generation Roi Pooling Bilinear Interpolation Mean Average Precision

Prev Next

Non-Maximum Suppression

Computer Vision

Medium

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

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

Computing IoU

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

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.

\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 Box Anchor Box Generation Roi Pooling Bilinear Interpolation Mean Average Precision

Case 1

Case 2

boxes =

Accepts: array

scores =

Accepts: array

iou_threshold =

Accepts: number

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

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

Computing IoU

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

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.

\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.