Computer vision: Detector precision, recall and AP

Benchmarks rank detectors by average precision. Compute it from scratch.

What to build

A program that matches predictions to ground truth and reports precision, recall and average precision.

Requirements

  • Process predictions from the highest score down (equal scores in input order). Each matches the not-yet-matched ground-truth box with the largest IoU (the earliest on ties); if that IoU is at least t, the prediction is TP and the box becomes matched, otherwise it is FP.
  • After each prediction print prediction i: TP|FP, precision P, recall R (i is the input index; P = TPs so far ÷ predictions so far; R = TPs so far ÷ ground-truth boxes), with three decimal places.
  • Then print AP A with three decimal places, where A = Σ (Rₖ − Rₖ₋₁) × max(Pₖ, Pₖ₊₁, …) over the predictions in processing order, starting from R₀ = 0.

Input

Line 1: G, P and t. Then G lines x1 y1 x2 y2. Then P lines x1 y1 x2 y2 score.

Output

P lines and the AP line.

Constraints

1 ≤ G, P ≤ 100; 0 < t ≤ 1.

Example

Input:

2 3 0.5
0 0 10 10
20 20 30 30
0 0 10 10 0.9
21 21 31 31 0.8
50 50 60 60 0.7

Output:

prediction 0: TP, precision 1.000, recall 0.500
prediction 1: TP, precision 1.000, recall 1.000
prediction 2: FP, precision 0.667, recall 1.000
AP 1.000

Why it works

Processing by score mimics lowering the detector's threshold step by step; recall grows only at true positives, and weighting each recall step by the best precision still reachable gives the area under the interpolated precision-recall curve.

Examples

Example 1 · Input
2 3 0.5
0 0 10 10
20 20 30 30
0 0 10 10 0.9
21 21 31 31 0.8
50 50 60 60 0.7
Expected output
prediction 0: TP, precision 1.000, recall 0.500
prediction 1: TP, precision 1.000, recall 1.000
prediction 2: FP, precision 0.667, recall 1.000
AP 1.000
Example 2 · Input
1 2 0.5
0 0 10 10
40 40 50 50 0.9
1 0 11 10 0.6
Expected output
prediction 0: FP, precision 0.000, recall 0.000
prediction 1: TP, precision 0.500, recall 1.000
AP 0.500

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

Hints

Hint 1

Sort predictions by score (high first, input order on ties). For each, find the unmatched ground-truth box with the largest IoU; it is a true positive if that IoU is at least t.

Hint 2

AP: for each prediction k in order, add (recall_k − recall_(k−1)) × the largest precision among predictions k and later.

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)


g, p, t = input().split()
g, p, t = int(g), int(p), float(t)
truth = [list(map(float, input().split())) for _ in range(g)]
preds = []
for i in range(p):
    v = input().split()
    preds.append((list(map(float, v[:4])), float(v[4]), i))
preds.sort(key=lambda q: (-q[1], q[2]))
matched = [False] * g
tp = 0
precisions, recalls = [], []
for k, (box, score, i) in enumerate(preds, 1):
    best, best_j = 0.0, -1
    for j in range(g):
        if not matched[j]:
            v = iou(box, truth[j])
            if v > best:
                best, best_j = v, j
    if best_j >= 0 and best >= t:
        matched[best_j] = True
        tp += 1
        kind = "TP"
    else:
        kind = "FP"
    precisions.append(tp / k)
    recalls.append(tp / g)
    print(f"prediction {i}: {kind}, precision {tp / k:.3f}, recall {tp / g:.3f}")
ap, last = 0.0, 0.0
for k in range(len(preds)):
    ap += (recalls[k] - last) * max(precisions[k:])
    last = recalls[k]
print(f"AP {ap:.3f}")

Lesson: Object detection metrics and segmentation →