"""Box overlap, non-maximum suppression and precision/recall for object detection. Boxes are rows (x1, y1, x2, y2) in pixels with x1 < x2 and y1 < y2. Coordinates are continuous, so a box's area is (x2 - x1) * (y2 - y1) with no "+1". Run as a script for the worked example from the lesson: python iou.py """ from __future__ import annotations import numpy as np from numpy.typing import ArrayLike, NDArray def box_area(boxes: ArrayLike) -> NDArray[np.float64]: """Area of each box in an (N, 4) array.""" b = np.asarray(boxes, dtype=float).reshape(-1, 4) return np.clip(b[:, 2] - b[:, 0], 0.0, None) * np.clip(b[:, 3] - b[:, 1], 0.0, None) def iou_matrix(boxes_a: ArrayLike, boxes_b: ArrayLike) -> NDArray[np.float64]: """Intersection over union between every box in A (N, 4) and every box in B (M, 4).""" a = np.asarray(boxes_a, dtype=float).reshape(-1, 4) b = np.asarray(boxes_b, dtype=float).reshape(-1, 4) # Corners of the intersection rectangle, broadcast to (N, M). x1 = np.maximum(a[:, None, 0], b[None, :, 0]) y1 = np.maximum(a[:, None, 1], b[None, :, 1]) x2 = np.minimum(a[:, None, 2], b[None, :, 2]) y2 = np.minimum(a[:, None, 3], b[None, :, 3]) inter = np.clip(x2 - x1, 0.0, None) * np.clip(y2 - y1, 0.0, None) union = box_area(a)[:, None] + box_area(b)[None, :] - inter return np.divide(inter, union, out=np.zeros_like(inter), where=union > 0) def iou(box_a: ArrayLike, box_b: ArrayLike) -> float: """Intersection over union of two single boxes.""" return float(iou_matrix(box_a, box_b)[0, 0]) def nms(boxes: ArrayLike, scores: ArrayLike, iou_threshold: float = 0.5) -> NDArray[np.int64]: """Greedy non-maximum suppression. Repeatedly keep the highest-scoring remaining box and drop every remaining box whose IoU with it is greater than iou_threshold. Returns the kept indices, highest score first. Run it separately for each class. """ b = np.asarray(boxes, dtype=float).reshape(-1, 4) s = np.asarray(scores, dtype=float).ravel() order = np.argsort(-s, kind="stable") keep: list[int] = [] while order.size > 0: best = int(order[0]) keep.append(best) rest = order[1:] overlaps = iou_matrix(b[best], b[rest])[0] order = rest[overlaps <= iou_threshold] return np.array(keep, dtype=np.int64) def match_detections( pred_boxes: ArrayLike, pred_scores: ArrayLike, gt_boxes: ArrayLike, iou_threshold: float = 0.5, ) -> tuple[NDArray[np.bool_], NDArray[np.float64]]: """Label each prediction as true positive (True) or false positive (False). Predictions are processed from highest to lowest score. Each one is matched to the unmatched ground-truth box with the highest IoU, if that IoU is at least iou_threshold. A second prediction on an already matched object is a false positive (a duplicate). Returns (is_tp, scores), both sorted by descending score. """ p = np.asarray(pred_boxes, dtype=float).reshape(-1, 4) s = np.asarray(pred_scores, dtype=float).ravel() g = np.asarray(gt_boxes, dtype=float).reshape(-1, 4) order = np.argsort(-s, kind="stable") p, s = p[order], s[order] is_tp = np.zeros(len(p), dtype=bool) if len(g) == 0 or len(p) == 0: return is_tp, s ious = iou_matrix(p, g) taken = np.zeros(len(g), dtype=bool) for i in range(len(p)): cand = np.where(taken, -1.0, ious[i]) j = int(np.argmax(cand)) if cand[j] >= iou_threshold: is_tp[i] = True taken[j] = True return is_tp, s def precision_recall( pred_boxes: ArrayLike, pred_scores: ArrayLike, gt_boxes: ArrayLike, score_threshold: float = 0.5, iou_threshold: float = 0.5, ) -> tuple[float, float, int, int, int]: """Precision and recall when only predictions with score >= score_threshold are kept. Returns (precision, recall, tp, fp, fn). Precision is defined as 1.0 when nothing is predicted, and recall as 1.0 when there is nothing to find. """ is_tp, s = match_detections(pred_boxes, pred_scores, gt_boxes, iou_threshold) kept = s >= score_threshold tp = int(np.sum(is_tp & kept)) fp = int(np.sum(~is_tp & kept)) n_gt = len(np.asarray(gt_boxes, dtype=float).reshape(-1, 4)) fn = n_gt - tp precision = tp / (tp + fp) if tp + fp > 0 else 1.0 recall = tp / n_gt if n_gt > 0 else 1.0 return precision, recall, tp, fp, fn def pr_curve( is_tp: ArrayLike, scores: ArrayLike, n_gt: int ) -> tuple[NDArray[np.float64], NDArray[np.float64]]: """Precision and recall after each prediction, sweeping the score threshold downwards. is_tp and scores may come from several images concatenated; they are re-sorted here. """ t = np.asarray(is_tp, dtype=bool).ravel() s = np.asarray(scores, dtype=float).ravel() order = np.argsort(-s, kind="stable") tp_cum = np.cumsum(t[order]) fp_cum = np.cumsum(~t[order]) precision = tp_cum / (tp_cum + fp_cum) recall = tp_cum / max(n_gt, 1) return precision, recall def average_precision(precision: ArrayLike, recall: ArrayLike) -> float: """Area under the precision-recall curve with the precision envelope (all-point method). Precision at each recall level is replaced by the highest precision at any higher recall, then the area is summed over the recall steps. """ p = np.concatenate(([0.0], np.asarray(precision, dtype=float), [0.0])) r = np.concatenate(([0.0], np.asarray(recall, dtype=float), [1.0])) p = np.maximum.accumulate(p[::-1])[::-1] steps = np.where(r[1:] != r[:-1])[0] return float(np.sum((r[steps + 1] - r[steps]) * p[steps + 1])) def main() -> None: a = [100, 100, 200, 200] b = [120, 110, 220, 210] print(f"IoU(A, B) = {iou(a, b):.4f}") boxes = np.array([a, b, [300, 120, 380, 200], [105, 95, 195, 205]], dtype=float) scores = np.array([0.92, 0.85, 0.60, 0.40]) print("IoU matrix:\n", np.round(iou_matrix(boxes, boxes), 3)) print("kept by NMS (threshold 0.5):", nms(boxes, scores, 0.5).tolist()) gt = np.array([[102, 104, 204, 206], [298, 118, 382, 204], [450, 300, 520, 380]], dtype=float) for thr in (0.3, 0.5, 0.9): p, r, tp, fp, fn = precision_recall(boxes, scores, gt, score_threshold=thr) print(f"score >= {thr}: TP={tp} FP={fp} FN={fn} precision={p:.3f} recall={r:.3f}") if __name__ == "__main__": main()