Object Detection

A classifier answers “what is in this image?”. A detector answers two questions at once: what objects are present, and where each one is, as a box drawn tightly around it. The output is no longer one label but a list of (class, box) pairs whose length is not known in advance. 𐃏

The modern answer was built in a clear sequence, and each step removes the bottleneck of the one before it. Classify thousands of crops; then classify only a couple of thousand proposed crops (R-CNN); then share one convolutional pass among all of them (Fast R-CNN); then let the network propose the crops itself (Faster R-CNN); then drop the proposal stage altogether (YOLO, SSD) and fix the accuracy that cost (focal loss, RetinaNet). Two small tools run through the whole story: IoU to measure a box, and non-maximum suppression to remove duplicate boxes.

The convolutional building blocks are on the From Convolution to CNNs page (and in CNN from scratch). Turning boxes into pixel masks, with Mask R-CNN and RoI Align, is the job of Semantic and Instance Segmentation.

measuring a box: IoU#

A predicted box is never exactly right, so we need one number that says how good it is. Write a box in corner form \(\mathbf b = (x_1, y_1, x_2, y_2)\), top-left and bottom-right.

IoU is the Jaccard index applied to two regions, so it punishes errors in position and in size together. That makes it stricter than it looks.

one object: a class head and a box head#

If the image is known to hold exactly one object, detection is classification (“what”) plus localisation (“where”). Take any classification CNN, keep its feature vector, and attach two heads in parallel: a fully connected layer to class scores, and a second fully connected layer to four box numbers \((x, y, w, h)\). Train with cross-entropy on the class head plus a squared-error loss on the box head, summed into one loss. A network trained on two objectives through one summed loss is a multi-task network, and every detector below is one.

The squared error is only a proxy for what we want, a large IoU: it is easy to differentiate, but two boxes with equal squared error can have quite different IoU.

The two-head network outputs exactly four numbers. An image with two objects needs eight, a herd of zebras needs “many”, and a fixed-size output layer cannot provide a variable number. Everything that follows is a way round this.

many objects: from sliding windows to proposals#

The first fix turns detection back into classification. Cut many crops out of the image (a sliding window at several sizes and aspect ratios), run the CNN on each, and let it answer one of the object classes or background. Every crop not called background is a detection.

The trouble is cost. Objects can sit at any position, at any size and with any aspect ratio, so the number of crops is enormous, and each one is a full CNN forward pass. Every method on this page reduces either the number of crops or the cost of each.

selective search#

A region proposal method looks at the image once and returns a short list of regions likely to contain some object, whatever its class. Selective search, the proposal method of the first CNN detectors, returns about 2000 boxes per image in a few seconds on a CPU.

Its idea is bottom-up: start from an over-segmentation into many small regions of similar colour (Felzenszwalb and Huttenlocher’s graph-based segmentation), assume objects are unions of these pieces, and build the unions greedily.

Three design choices explain the details. Every level of the merge hierarchy contributes boxes, so all object scales are covered. The similarity combines colour, texture, size and fill terms, and the whole procedure is rerun in several colour spaces, because no single cue groups every object (a cat is one texture but many colours, a car one colour but many textures). And a merged region’s histograms and size come from its parts without revisiting pixels, which keeps it fast.

When it fails. Selective search is a fixed, hand-designed grouping. An object whose parts differ from each other but resemble the background (a camouflaged animal, a patterned shirt against a busy wall) may never be formed as one region, and no later stage can recover a missed proposal. It also costs seconds per image, which becomes the bottleneck once the network is fast.

When to use it. When proposals are needed without any training, in a new domain with no box labels. Inside a trained detector, the learned region proposal network below replaces it.

the R-CNN line#

Three detectors, each fixing the previous one’s slowest step. The figure shows them side by side.

R-CNN#

R-CNN (“regions with CNN features”) is crop-and-classify made affordable by proposals.

It works, and it is very slow. Training is three separate stages (fine-tune the CNN on proposals, fit the SVMs, fit the box regressors) that cannot correct each other; the features of every proposal of every training image are written to disk (2.5 GPU-days and hundreds of gigabytes for the 5000 PASCAL VOC 2007 images); and at test time each image needs about 2000 independent forward passes, 47 seconds on a GPU.

why a CNN needs a fixed input size#

The 2000 passes are mostly redundant, since overlapping proposals send the same pixels through the same convolutions again and again. The obvious fix is to run the convolutions once on the whole image and cut each proposal out of the feature map. What stops us is the warp: why does the network need a fixed input at all?

The convolutional layers do not care. A convolution slides the same small kernel over any height and width and simply produces a proportionally sized output. The fully connected layers do care: they multiply a vector of fixed length by a weight matrix of fixed shape, so if the feature map changes size the flattened vector changes length and the product is undefined. What is needed is a layer that turns a window of any size into a tensor of fixed size. Spatial pyramid pooling (SPP-Net) did it with several grid levels; Fast R-CNN uses the single-level version.

Fast R-CNN and RoI pooling#

The snap in step 2 shifts the box by a fraction of a cell, which is several pixels at stride 16: projecting \((100, 50, 200, 150)\) from a \(224 \times 224\) image onto a \(14 \times 14\) map gives \((6.25, 3.125, 12.5, 9.375)\), and rounding moves the edges by up to 10 pixels. That is harmless for classification but hurts pixel-accurate masks, which is why Mask R-CNN replaces RoI pooling with RoI Align (see Semantic and Instance Segmentation).

Both heads are trained together with one multi-task loss: log loss on the class plus a robust box loss, the box term switched off for background regions, \[ \mathcal L = -\log p_{c^*} + \lambda\, [c^* \ne \text{background}] \sum_{j \in \{x,y,w,h\}} \operatorname{smooth}_{L_1}(t_j - t_j^*) . \] Smooth \(L_1\) is \(\tfrac12 z^2\) for \(|z| < 1\) and \(|z| - \tfrac12\) otherwise: quadratic near zero, so gradients shrink as the box converges, and linear for large errors, so one badly wrong proposal cannot dominate a batch (\(\operatorname{smooth}_{L_1}(3) = 2.5\) against \(\tfrac12 \cdot 3^2 = 4.5\)).

Training is now end to end and nothing is cached to disk. The timings, after Girshick (2015) and Ren et al. (2015):

Read the Fast R-CNN row: of its 2.3 seconds, about 2 (86%) are selective search. The network is no longer the bottleneck; the proposals are.

Faster R-CNN: learning the proposals#

The feature maps that Fast R-CNN uses to classify regions already encode where objects are, so they can also generate the regions. Faster R-CNN puts a small network on the shared feature map to do that.

The correction is parameterised relative to the anchor’s centre \((x_a, y_a)\) and size \((w_a, h_a)\): \[ t_x = \frac{x - x_a}{w_a}, \quad t_y = \frac{y - y_a}{h_a}, \quad t_w = \log\frac{w}{w_a}, \quad t_h = \log\frac{h}{h_a} . \] Dividing by the anchor size makes the target scale-free, and the logarithm makes doubling and halving equally large corrections. An anchor centred at \((100, 100)\) of size \(128 \times 128\) and a true box centred at \((110, 90)\) of size \(160 \times 120\) give targets \(t^* \approx (0.078, -0.078, 0.223, -0.065)\).

Faster R-CNN is then the RPN plus Fast R-CNN on one shared backbone, trained jointly with four losses: RPN object-or-not, RPN anchor-to-proposal correction, final classification, and final proposal-to-object correction. It detects in about 0.2 s per image, 245 times faster than R-CNN.

the RPN loss and sampling#

Almost every anchor lies on background; trained on all of them the network would mostly learn what background looks like. The R-CNN family therefore samples: the RPN’s mini-batch is 256 anchors, 128 positive and 128 negative, padded with negatives when an image has fewer positives (40 positives give 216 negatives); the detector stage keeps negatives to at most three per positive, or uses online hard example mining, which samples the anchors with the highest current loss.

non-maximum suppression#

Every detector above fires several times on one object: neighbouring anchors or proposals all overlap it and all score highly. Non-maximum suppression (NMS) keeps the best box of each overlapping group. (It shares a name, and nothing else, with the edge-thinning step in Canny.)

When it fails. The threshold trades two errors. A high \(\tau\) removes only near-duplicates and can leave two boxes on one object; a low \(\tau\) removes more duplicates but can delete a genuine second object that overlaps the first: two people walking side by side, or anyone in a crowd. No single threshold is right for both a sparse street and a packed stadium.

one-stage detectors: SSD and YOLO#

Every R-CNN-style detector has two stages: propose regions, then classify and refine each one. A one-stage detector replaces both with a single network that maps the image straight to boxes and classes at every position.

SSD#

The single shot multibox detector removes proposals and resampling with three changes: small convolutional filters, not fully connected layers, predict class scores and box offsets at every position; each default box shape has its own predictor; and predictors sit on several feature maps of decreasing resolution, each covering one range of object sizes.

The large maps (\(38 \times 38\), small receptive fields) catch small objects and the small maps catch large ones. Data augmentation turned out to be crucial, and more default box shapes and more output layers both helped.

YOLO#

“You only look once” treats detection as one regression problem, from pixels straight to box coordinates and class probabilities, solved by one network applied once to the whole image.

Looking once makes it fast. The published comparison on PASCAL VOC 2007 (Redmon et al., 2016):

The error analysis against Fast R-CNN is the interesting part. YOLO makes far more localisation errors (right class, IoU between 0.1 and 0.5: 19.0% of its top detections against 8.6%), because each coarse cell predicts only two boxes. It makes far fewer background errors (firing on nothing: 4.75% against 13.6%), because it sees the whole image and so the context of every box. YOLO has since become a large family, from YOLOv2 and v3 through v4 to v11 and variants such as YOLOX and YOLO-World.

why one-stage detectors trailed in accuracy#

Both families face an extreme imbalance between object and background candidates, but handle it differently. In a two-stage detector the proposal stage cuts the candidates to about 2000, discarding most background, and the second stage then fixes the foreground-to-background ratio at \(1{:}3\) or mines hard examples. A one-stage detector must score about 100,000 candidates densely covering positions, scales and shapes, and almost all are easy background. Each easy negative has a tiny loss, but there are so many that their sum swamps the training signal from the few objects.

focal loss, feature pyramids and RetinaNet#

The cure has two parts: a loss that ignores easy examples, and features that are semantically strong at every resolution.

focal loss#

The factor \((1 - p_t)^\gamma\) is near 0 for well-classified examples and near 1 for badly classified ones, so it silences the easy examples and leaves the hard ones almost untouched.

feature pyramid networks#

Deeper in a CNN, feature maps lose resolution and gain meaning: early maps are sharp but know little about objects, late maps know what is there but only coarsely where. SSD predicts from several resolutions, but its high-resolution maps are semantically weak, which is why it struggles with small objects.

RetinaNet#

RetinaNet is a one-stage detector built from both remedies: a ResNet backbone with an FPN, plus focal loss. At every pyramid level two small fully convolutional subnetworks (four \(3 \times 3\) convolutions of 256 channels each, shared across levels) predict, for every position and anchor, the class probabilities and the box offset. The result on COCO (Lin et al., 2017; AP is COCO’s metric, below):

The largest RetinaNet beats the best two-stage detector listed, and the RetinaNet curve lies above every other detector at every speed in the paper. With the imbalance handled, one stage is as accurate as two.

how detectors are scored: AP and mAP#

A detector outputs ranked, scored boxes, so it is scored by how its precision and recall trade off as the confidence threshold falls. A predicted box is a true positive if its IoU with an unmatched ground-truth box of the same class reaches the threshold (commonly 0.5); otherwise it is a false positive, and every ground-truth box left unmatched is a false negative.

AP rewards a detector that finds every object (high final recall) and ranks its correct boxes above its mistakes (high precision early). Benchmarks differ in the matching threshold: PASCAL VOC uses IoU 0.5, while COCO’s headline “AP” averages over thresholds \(0.50, 0.55, \dots, 0.95\) and also reports AP\(_{50}\), AP\(_{75}\) and AP for small, medium and large objects. A COCO AP of 37.8 and a VOC mAP of 73.2 are therefore not comparable numbers.

which detector, and where each fails#

• Faster R-CNN (with an FPN backbone) when accuracy matters more than speed: small or overlapping objects in still images.
• YOLO for real-time video, but each coarse cell predicts only a couple of boxes and one set of class probabilities, so it localises loosely and under-detects several small objects whose centres share a cell (a flock of birds).
• SSD fails on small objects because its high-resolution maps are semantically weak; an FPN is the fix.
• RetinaNet gives one-stage speed with two-stage accuracy. Like every anchor-based detector it regresses poorly for shapes no anchor resembles (very elongated objects), and like every detector that ends in NMS it can delete a true object overlapping another by more than \(\tau\).

Since 2018 the field has moved on to anchor-free and end-to-end detectors (CornerNet, CenterNet, DETR), which predict object centres or corners, or a set of boxes directly, and some of which need no NMS at all. Open implementations of everything on this page are in Detectron2 and MMDetection.

further reading#

• Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., §6.3.3 (object detection).
• Girshick et al., Rich feature hierarchies for accurate object detection (R-CNN, 2014).
• Girshick, Fast R-CNN (2015).
• Ren et al., Faster R-CNN (2015).
• Redmon et al., You Only Look Once (2016).
• Liu et al., SSD: Single Shot MultiBox Detector (2016).
• Lin et al., Feature Pyramid Networks for Object Detection (2017).
• Lin et al., Focal Loss for Dense Object Detection (RetinaNet, 2017).

see also#

• From Convolution to CNNs – the backbones every detector runs on
• Semantic and Instance Segmentation – Mask R-CNN and RoI Align, from boxes to masks
• Classical Segmentation – the over-segmentation behind selective search