Average Precision

The problem, from first principles

How good is a detector? Accuracy does not apply because a detector outputs a ranked list of boxes with scores, and the number of objects found depends on where you cut the list. Average precision (AP) summarizes the whole list. Sort the detections of one class by confidence. Walk down the list, marking each detection as a true positive (it matches a previously unmatched ground-truth box with IoU above a threshold) or a false positive. After each step compute precision (TP / detections so far) and recall (TP / total ground truths). Plotting precision against recall gives a zig-zag curve, and AP is the area under it after replacing each precision by the best precision at any higher recall, which removes the zig-zag. Averaging AP over classes gives mAP.

From theory to code

Implement average_precision.

Constraints

• scores is a length-D array of detection confidences, is_tp is a length-D boolean array saying whether each detection is a true positive (matching has already been done), and n_gt is the number of ground-truth boxes (n_gt >= 1).
• Sort by descending score (stable). Compute cumulative tp and fp, recall = tp / n_gt and precision = tp / (tp + fp).
• Use the all-point interpolation of Pascal VOC 2010+: prepend recall = 0 and precision = 1, append recall = 1 and precision = 0, make precision monotone non-increasing from right to left (precision[i] = max(precision[i], precision[i+1])), and sum (recall[i+1] - recall[i]) * precision[i+1] over the points where recall changes.
• Return a float. With no detections, return 0.0.

Hints