Computer vision: Non-maximum suppression

Detectors draw several boxes around each object. Non-maximum suppression keeps one.

What to build

A program that runs greedy non-maximum suppression.

Requirements

  • Visit boxes from the highest score to the lowest (equal scores in input order). Keep a box if its IoU with every already-kept box is at most the threshold t; otherwise remove it.
  • Print kept: … with the kept indices (from 0) in the order they were kept, then removed: … with the removed indices in increasing order, or removed: none.

Input

Line 1: N and t. Then N lines x1 y1 x2 y2 score.

Output

Two lines.

Constraints

1 ≤ N ≤ 200; 0 < t < 1.

Example

Input:

6 0.5
10 10 50 50 0.9
12 14 52 54 0.8
60 20 90 60 0.75
8 8 48 46 0.7
62 22 92 58 0.6
30 70 40 80 0.3

Output:

kept: 0 2 5
removed: 1 3 4

Why it works

The highest-scoring box is the most trusted guess for its object, and any box overlapping it heavily is probably the same object, so removing those leaves one box per object.

Examples

Example 1 · Input
6 0.5
10 10 50 50 0.9
12 14 52 54 0.8
60 20 90 60 0.75
8 8 48 46 0.7
62 22 92 58 0.6
30 70 40 80 0.3
Expected output
kept: 0 2 5
removed: 1 3 4
Example 2 · Input
3 0.3
0 0 10 10 0.2
1 1 11 11 0.9
50 50 60 60 0.5
Expected output
kept: 1 2
removed: 0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Sort the indices by score from high to low, keeping the input order for equal scores (Python's `sorted` is stable).

Hint 2

Keep a box when its IoU with every box kept so far is at most the threshold.

Solution

Show one correct solution (try it yourself first)
def iou(a, b):
    w = max(0.0, min(a[2], b[2]) - max(a[0], b[0]))
    h = max(0.0, min(a[3], b[3]) - max(a[1], b[1]))
    inter = w * h
    return inter / ((a[2] - a[0]) * (a[3] - a[1]) + (b[2] - b[0]) * (b[3] - b[1]) - inter)


n, t = input().split()
n, t = int(n), float(t)
boxes, scores = [], []
for _ in range(n):
    v = list(map(float, input().split()))
    boxes.append(v[:4])
    scores.append(v[4])
order = sorted(range(n), key=lambda i: -scores[i])
kept = []
for i in order:
    if all(iou(boxes[i], boxes[j]) <= t for j in kept):
        kept.append(i)
removed = sorted(i for i in range(n) if i not in kept)
print("kept: " + " ".join(map(str, kept)))
print("removed: " + (" ".join(map(str, removed)) if removed else "none"))

Lesson: Object detection metrics and segmentation →