Object Detection Fundamentals

Object detection is the task of predicting, for a given image, a variable-length set of detections, each consisting of a bounding box — typically parameterized as $(x_{\min}, y_{\min}, x_{\max}, y_{\max})$ or $(x_{\text{center}}, y_{\text{center}}, w, h)$ — a class label from a fixed category set, and a confidence score in $[0,1]$ expressing the model's certainty. This is fundamentally different from image classification, which produces exactly one label (or one probability vector) per image regardless of how many objects it contains. Detection must handle images with zero, one, or dozens of objects, of different classes, sizes, and overlapping arrangement, using an output structure whose size is not fixed in advance. To decide whether a predicted box is "correct," detection needs a notion of geometric agreement between two boxes. The standard measure is Intersection over Union (IoU), also called the Jaccard index:

where $A$ and $B$ are the pixel regions enclosed by two boxes. IoU is $1$ for identical boxes, $0$ for non-overlapping boxes, and smoothly interpolates in between — crucially, it is scale-invariant (a tiny box overlapping perfectly scores the same as a huge one) and penalizes both under- and over-sized predictions, unlike pixel-distance measures that only penalize translation. A prediction is declared a true positive (TP) if (a) its class matches a ground-truth object's class, and (b) its IoU with that ground-truth box exceeds a chosen threshold $\tau$ (commonly $\tau = 0.5$). Each ground-truth box can be matched at most once — greedily, in order of confidence — so a second detector output claiming the same object becomes a false positive (FP), since it is a duplicate. Ground-truth objects with no matching prediction above threshold are false negatives (FN). This bookkeeping, class by class and image by image, is the substrate on which precision, recall, Average Precision (AP), and finally mean Average Precision (mAP) — the field's single most quoted number — are built.

The evaluation pipeline for object detection proceeds in five stages, run independently per class and then combined.

Stage 1 — Collect all predictions and ground truths. Across the entire test set, gather every predicted box for a class $c$ (with its confidence score) and every ground-truth box labeled $c$.

Stage 2 — Sort predictions by confidence, descending. This ordering determines the order in which predictions get a chance to claim a ground-truth match — high-confidence predictions are matched first, mirroring how a real system would be used (trusting its most confident outputs first).

Stage 3 — Greedily match. Walk down the sorted list. For each prediction, find the unmatched ground-truth box of the same class in the same image with highest IoU. If that IoU exceeds $\tau$, mark it TP and mark the ground-truth box as "used." Otherwise mark the prediction FP.

Stage 4 — Build the precision-recall curve. At each rank $k$ in the sorted list, compute cumulative precision and recall using only the first $k$ predictions:

Stage 5 — Integrate to get AP, then average to get mAP. AP is the area under the (interpolated, monotonic) precision-recall curve for class $c$; mAP averages AP over all classes (and, in modern benchmarks, over several IoU thresholds). ```

# ---- IoU between two axis-aligned boxes ---- function IoU(boxA, boxB): xA = max(boxA.x1, boxB.x1) yA = max(boxA.y1, boxB.y1) xB = min(boxA.x2, boxB.x2) yB = min(boxA.y2, boxB.y2) interW = max(0, xB - xA) interH = max(0, yB - yA) interArea = interW interH areaA = (boxA.x2 - boxA.x1) (boxA.y2 - boxA.y1) areaB = (boxB.x2 - boxB.x1) * (boxB.y2 - boxB.y1) unionArea = areaA + areaB - interArea if unionArea == 0: return 0.0 return interArea / unionArea

# ---- AP for a single class, given all predictions & ground truths ---- function ComputeAP(predictions, groundTruths, iouThreshold):

# predictions: list of (image_id, box, score)

# groundTruths: dict image_id -> list of boxes (each with a "matched" flag) sort predictions by score descending numGT = total count of ground-truth boxes across all images TP = array of zeros, length = len(predictions) FP = array of zeros, length = len(predictions) for i, (imgId, predBox, score) in enumerate(predictions): candidates = groundTruths[imgId] # only this image's GT boxes bestIoU = 0 bestIdx = -1 for j, gtBox in enumerate(candidates): if gtBox.matched: continue iou = IoU(predBox, gtBox.box) if iou > bestIoU: bestIoU = iou bestIdx = j if bestIoU >= iouThreshold: candidates[bestIdx].matched = true TP[i] = 1 else: FP[i] = 1 cumTP = cumulative_sum(TP) cumFP = cumulative_sum(FP) precision = cumTP / (cumTP + cumFP) # elementwise recall = cumTP / numGT # elementwise return AreaUnderPRCurve(precision, recall)

# ---- 11-point / all-point interpolation of the PR curve ---- function AreaUnderPRCurve(precision, recall):

# Make precision monotonically non-increasing from the right:

# p_interp(r) = max precision at recall >= r for i from len(precision)-2 down to 0: precision[i] = max(precision[i], precision[i+1])

# Integrate via the change in recall (all-point interpolation, PASCAL VOC 2010+ / COCO style) area = 0 prevRecall = 0 for i from 0 to len(precision)-1: area += precision[i] * (recall[i] - prevRecall) prevRecall = recall[i] return area

# ---- mAP over classes (and, for COCO-style, over IoU thresholds) ---- function ComputeMAP(allPredictions, allGroundTruths, classList, iouThresholds): classAPs = [] for c in classList: thresholdAPs = [] for tau in iouThresholds: ap = ComputeAP(allPredictions[c], allGroundTruths[c], tau) thresholdAPs.append(ap) classAPs.append(mean(thresholdAPs)) return mean(classAPs) ``` The precision-monotonizing step deserves emphasis: raw precision is a jagged, non-monotonic function of recall (it can dip and recover as more predictions are added), so both the PASCAL VOC and COCO protocols replace $p(r)$ with $\max_{r' \ge r} p(r')$ before integrating, producing a stable, comparable area. COCO's mAP additionally averages over ten IoU thresholds ($0.5, 0.55, \dots, 0.95$), rewarding detectors whose boxes are not merely "roughly right" but tightly localized.

Time complexity of one IoU computation. Computing the intersection and union of two axis-aligned boxes involves a constant number of comparisons and arithmetic operations, so it is $O(1)$.

Time complexity of AP computation for one class. With $N$ predictions and $M$ ground-truth boxes for a class, the naive greedy matcher (as written above) compares each prediction against every ground-truth box in its image. In the worst case (all boxes in one image) this is $O(N \cdot M)$. Since $N$ and $M$ are typically at most a few thousand per class per dataset (not per image), this is entirely tractable; restricting the inner loop to ground-truth boxes within the same image (as real implementations do) makes the practical cost far smaller, since $M$ per image is usually small (tens of objects). Sorting the $N$ predictions costs $O(N \log N)$, which dominates asymptotically. The cumulative-sum and monotonizing passes are $O(N)$.

Time complexity of full mAP. Over $C$ classes and $K$ IoU thresholds (COCO uses $K=10$), total cost is $O(C \cdot K \cdot N \log N)$ where $N$ is now the per-class prediction count — linear-ish in the total number of detections produced, which is exactly the resource budget a detector consumes at inference time, so evaluation never becomes the bottleneck.

Space complexity is $O(N + M)$ per class: one flag per ground-truth box (matched/unmatched) and one score/label pair per prediction. No auxiliary structure grows faster than the input.

Why greedy matching by descending confidence is the correct protocol, not an arbitrary choice. The precision-recall curve is meant to simulate operating the detector at every possible confidence threshold simultaneously: if you deployed the system and only trusted detections above some cutoff, that cutoff corresponds exactly to truncating the sorted list at some rank $k$. Matching greedily in this order guarantees that TP/FP counts at rank $k$ equal exactly the TP/FP counts you would get by literally thresholding the detector at that confidence value. Matching in a different order (e.g., by IoU) would silently change what "operating point" each rank represents, breaking the correspondence to real deployment behavior. The "each ground-truth box may be matched once" rule is what forces detectors to be penalized for duplicate detections — without it, a detector could spam the same object with ten boxes and get ten true positives, which is not the desired incentive; this rule, in fact, is the direct evaluation-side reason Non-Maximum Suppression must exist on the prediction side, since a detector that fails to suppress duplicates will see its extra copies scored as false positives.

Why AP (an integral) rather than a single precision/recall number. A detector's raw output score threshold is a knob a user could set anywhere; a single precision or recall number depends arbitrarily on where that knob sits. AP marginalizes over the entire operating range by integrating precision against recall, giving a threshold-free summary — mathematically, it approximates

which equals the average precision value observed each time recall increases by matching a new ground-truth object, exactly analogous to the area under an ROC curve for binary classification but adapted to the class-imbalanced, ranking-based nature of detection (there is no fixed "negative class count" the way there is in classification, since the number of possible negative boxes in an image is unbounded).

Tradeoffs and honesty about limitations. IoU thresholding is a hard cutoff: a box at IoU $0.49$ scores identically to one at IoU $0.05$ (both FP), while a box at IoU $0.51$ is treated as fully correct — a discontinuity that has motivated softer alternatives (e.g., soft-NMS scoring, GIoU/DIoU losses) used during training even though the evaluation metric remains threshold-based. mAP also treats all classes equally regardless of real-world frequency or safety criticality, which can misrepresent performance on rare-but-important classes (e.g., pedestrians in a street scene dominated by "car" instances) — a known and debated limitation of the metric's design.

Consider a single class, "cat," evaluated on a small test set with 3 ground-truth cats total (across two images), and a detector producing 5 predictions, sorted by confidence.

Walking through the logic: at rank 1, the prediction overlaps GT-1 with IoU $0.78 \ge 0.5$, so it's a TP and GT-1 becomes "used." At rank 2, the only candidate in img1 is GT-1 again, but it's already matched, so this prediction has no eligible ground truth to claim (treated as IoU $0$ against remaining candidates) — a duplicate detection, correctly punished as FP. Rank 3 matches GT-2 in img2 with IoU $0.61$, a clean TP. Rank 4 finds GT-3 but with IoU only $0.20 < 0.5$, so despite being the best available match it is FP — the location is simply too far off. Rank 5 has no unmatched ground truth left in its image, so it is FP by default.

Monotonizing precision (replace each precision value with the max of itself and all precisions at equal-or-higher recall, scanning from the end):

Concretely: recall reaches $0.333$ first at rank 1 (precision $1.00$) and again at rank 2 (precision $0.50$) — we keep track of the precision at the moment recall changes. Recall changes to $0.333$ at rank 1 (precision $1.00$), stays there through rank 2, changes to $0.667$ at rank 3 (precision $0.667$), stays there through ranks 4-5. The interpolation rule sets precision at recall $0.333$ to $\max(1.00, 0.667) = 1.00$ wait — carefully: interpolated precision at a recall level is the maximum precision for any recall $\ge$ that level. At recall $0.333$: candidates are precision values at recall $\ge 0.333$, i.e. $\{1.00, 0.50, 0.667, 0.50, 0.40\}$, max is $1.00$. At recall $0.667$: candidates at recall $\ge 0.667$ are $\{0.667, 0.50, 0.40\}$, max is $0.667$.

Integrating:

So $\text{AP}_{\text{cat}}^{@0.5} \approx 0.556$. Repeating this whole procedure for every class and averaging gives mAP@0.5; repeating again at $\tau = 0.55, 0.60, \dots, 0.95$ and averaging those ten values per class (then across classes) gives the stricter COCO-style mAP@[0.5:0.95], which will always be numerically lower than mAP@0.5 because higher thresholds convert former true positives into false positives.

The modern detection-evaluation protocol crystallized through a sequence of benchmark challenges rather than a single paper, each contributing a piece of the machinery described above.

Everingham's PASCAL VOC challenge (running annually from 2005 through 2012) established the IoU $\ge 0.5$ convention, the greedy-matching protocol, and the 11-point interpolated AP that later evolved into the all-point interpolation used today. The Microsoft COCO benchmark, introduced by Tsung-Yi Lin and collaborators, later tightened the metric by averaging AP over ten IoU thresholds and introducing size-stratified breakdowns, pushing the field toward tighter localization rather than merely "roughly right" boxes — directly foreshadowing the precision demands that motivated architectures built around Anchor Boxes and iterative box refinement in the R-CNN Family.

Every published object detector — from the original R-CNN to YOLO variants to DETR-style transformer detectors — is compared using exactly the IoU-and-mAP machinery described here; without a shared, precisely defined metric, claims of "state of the art" would be incomparable across papers. Autonomous vehicle perception stacks use IoU thresholds directly at runtime, not just for evaluation: a tracking module decides whether two boxes across consecutive frames refer to the same object using IoU-based association, and safety validation reports frequently cite per-class AP for pedestrians and cyclists as a regulatory-adjacent metric. Medical imaging systems that localize tumors or lesions in radiographs report AP at clinically relevant IoU thresholds, since a "close enough" bounding box may still be clinically meaningless if it misses the lesion's boundary by too much. Retail and industrial inspection systems (shelf-monitoring, defect detection) tune their deployed confidence threshold by inspecting the precision-recall curve directly, picking an operating point suited to whether false positives or false negatives are more costly in that application. Dataset curators and challenge organizers (COCO, Open Images, LVIS, Cityscapes) all publish their official rankings using variants of the mAP protocol built directly from IoU matching, cementing this evaluation framework as the lingua franca of the field.

:::quiz[Why does COCO's mAP@[0.5:0.95] tend to be lower than VOC-style mAP@0.5 for the same detector?]

• COCO uses a smaller test set
• Averaging over stricter IoU thresholds converts many former true positives into false positives ✓
• COCO does not use precision-recall curves
• mAP@[0.5:0.95] only evaluates large objects

Ask the tutor: How would the AP computation change if two predictions tie exactly in confidence score?