Localization An interactive monograph on object detection

Localization

How a computer is taught to find the objects in an image, draw a box around each one, and say what it is.

An interactive monograph in ten sections, with six live figures. Reading time roughly forty minutes. The figures are operable by mouse, touch and keyboard, and the document conforms to WCAG 2.2 AA. Built as a single static page in vanilla HTML, CSS and JavaScript, with no framework and no build step.

Abstract

Object detection asks a machine to report what is present in an image and where each thing lies. This document builds the subject from its foundations. It begins with the representation that every detector shares, the bounding box, and the geometric measure used to judge one, intersection over union. It then reviews the historical development of the field, tracing how each generation of method was a response to a specific failure of the one before it. The remaining sections treat the components common to modern detectors: exhaustive search and why it was abandoned, learned features, the suppression of duplicate predictions, the evaluation of a detector through precision and recall, and the grid of anchors that underpins single-stage systems.

Every figure is interactive and runs on a synthetic scene of geometric shapes. The synthetic setting is deliberate: it allows the geometry under discussion, the overlap of boxes and the counting of correct and incorrect predictions, to be computed exactly rather than estimated by a trained model whose behaviour would itself need explaining.

1Three tasks, one image

It is useful to separate three questions that can be asked of a single photograph, because the computer-vision literature treats them as distinct problems with distinct solutions. The first is classification: given an image, return a label naming the most prominent kind of thing it contains. The second is localization: assuming the image contains one object of interest, return the rectangle that encloses it. The third, and the subject of this document, is detection: return a rectangle and a label for every object present, with no prior knowledge of how many objects there are or where they sit.

The figure below shows a synthetic scene. Switching its view from the plain image to image-level labels and then to per-object boxes makes the progression concrete. A classifier would report only that discs, squares and triangles are present somewhere. A detector commits to a position for each instance, and is wrong in a measurable way when that position is poor.

The difficulty of detection grows from a single structural fact. The number of objects is not known in advance, so the output is not a fixed-length vector but a list of variable length. A classifier maps an image to one of a fixed set of labels, a problem with a clean and well-studied shape. A detector must decide how many predictions to make, commit each to a location, and avoid both missing real objects and inventing objects that are not there. Most of the machinery in the sections that follow exists to manage that variable-length output in a way that can be trained and evaluated.

One further task sits just beyond detection and is worth naming so that it can be set aside. Instance segmentation asks not for a rectangle but for the exact set of pixels belonging to each object. It is a refinement of detection rather than a departure from it, and the systems that perform it are extensions of the detectors described here. This document stops at the rectangle.

2The bounding box

A detector's notion of "where" is the bounding box: the smallest axis-aligned rectangle that contains an object. It is described by four numbers. Two conventions are in common use. The first records the coordinates of the top-left corner together with a width and a height. The second records the coordinates of the centre together with a width and a height. The two are interchangeable, and a given codebase will usually fix one and convert at its boundaries.

The box is a crude description of an object, and its crudeness is the point. A rectangle is cheap to store, cheap to compare, and differentiable enough in its coordinates to be the output of a trained regressor. A boundary that followed an object's true outline would be a far better description and a far worse engineering choice, because almost every operation a detector performs on its predictions, from measuring their quality to removing their duplicates, reduces to arithmetic on these four numbers.

In the figure below a single object is shown with a movable box. Bringing the box into agreement with the object is the elementary act of localization. The quality of the agreement is reported as a score between zero and one; that score is the intersection over union, and section six is devoted to it. For now it is enough to observe that the score rewards a box that is neither too loose nor too tight.

Ground truth
The human-supplied annotation that a prediction is compared against. Throughout this document the ground-truth box is drawn with a dashed outline. A detector never sees the ground truth at the moment of prediction; it is used only to train the system and, later, to score it.

3A history of the field: a literature review

The components described in the rest of this document did not arrive together. Each was introduced to repair a specific, identified weakness in the methods that preceded it, and the modern detector is best understood as the residue of that sequence of repairs. This section traces it. The account is deliberately causal: in each case the question is not only what a method did but which earlier failure it was built to answer.

The earliest practical detector to see wide use was the boosted cascade of Viola and Jones [1], published in 2001 and applied first to faces. Its contribution was less a new idea of what to detect than a new idea of how to afford the search. A detector of that era examined a great many candidate windows, and the overwhelming majority of those windows contained no object. Viola and Jones arranged their classifier as a cascade of stages, ordered so that a cheap early stage could reject an obvious non-object after only a few arithmetic operations, and only the rare promising window was passed to the expensive later stages. The method worked because it spent its computation where the difficulty actually was. Its weakness was that its features were simple intensity contrasts, well suited to the regular structure of a face and poorly suited to object categories with more variable appearance.

The need for a richer description of local appearance was met by the histogram of oriented gradients of Dalal and Triggs [2], introduced in 2005 for the detection of pedestrians. Their descriptor recorded the distribution of edge orientations in each small cell of an image, a representation that was stable under small changes of lighting and pose while remaining discriminative. Paired with a linear classifier it set the standard for several years. It did not, however, address a second weakness: a single rigid template cannot represent an object whose parts move relative to one another, such as a person whose limbs change configuration.

That weakness was the explicit target of the deformable part model of Felzenszwalb and colleagues [3]. A deformable part model represented an object as a coarse root template together with several higher-resolution part templates, each allowed to shift within a learned range at a learned penalty. It dominated the PASCAL VOC benchmark [11] for several years. Its limitation was shared with everything before it. The features were still designed by hand, and a hand-designed feature encodes only the regularities its designer anticipated.

The decisive change came from outside detection. In 2012 a deep convolutional network trained on the ImageNet classification benchmark [4] reduced the classification error rate by a margin that earlier methods had not approached, and it did so with features that were learned from data rather than specified in advance. The open question became how to bring a learned representation of that strength to bear on detection, where the output is a variable-length list of boxes rather than a single label.

The first influential answer was R-CNN, the region-based convolutional network of Girshick and colleagues [5] in 2014. R-CNN sidestepped the cost of searching every window by first generating a few thousand class-agnostic region proposals with the selective search algorithm [14], then running the convolutional network on each proposed region to classify it and refine its box. Accuracy rose sharply. Speed, however, was poor, because the network was run from scratch on every one of the thousands of proposals, with no sharing of computation between overlapping regions.

Fast R-CNN [6] removed that redundancy in 2015. It ran the convolutional network once over the whole image to produce a single feature map, then extracted a fixed-size descriptor for each proposal directly from that shared map. The cost of the network no longer scaled with the number of proposals. This exposed the next bottleneck cleanly: the proposals themselves were still produced by selective search, an algorithm external to the network and now the slowest part of the pipeline.

Faster R-CNN [7], later in 2015, closed that gap by introducing the region proposal network, a small network that generated proposals from the same shared feature map. For the first time the entire detector, proposal and classification alike, was a single network trained end to end. Faster R-CNN also introduced the anchor, a set of reference boxes of fixed sizes and aspect ratios tiled across the feature map, against which the network predicted only small corrections. Anchors are the subject of section nine.

Faster R-CNN and its descendants are two-stage detectors: one stage proposes regions, a second classifies them. A parallel line of work asked whether the two stages could be collapsed into one. YOLO [8] and SSD [9], both from 2016, predicted boxes and labels directly from the feature map in a single pass, dividing the image into a grid and assigning each cell responsibility for the objects centred within it. These single-stage detectors were markedly faster and, at first, less accurate. The accuracy gap was diagnosed by Lin and colleagues [10] in 2017 as a problem of class imbalance: a single-stage detector scores an enormous number of locations, almost all of them background, and the easy background cases dominate the training signal. Their focal loss reshaped the training objective to attend to the rare hard cases, and the gap largely closed.

Two threads run through this history and are worth stating plainly. The first is that the search for objects has been made progressively cheaper, from the cascade that rejected easy windows early to the single shared feature map of the one-stage detectors. The second is that the description of appearance moved from hand-designed features to learned ones, and never moved back. A more recent line of work, the detection transformer of Carion and colleagues [13], has questioned a further assumption, removing the hand-designed anchor and the suppression of duplicates in favour of a set-based objective. That development is beyond the scope of this document, but it belongs to the same pattern: a fixed piece of machinery, identified as a limitation, replaced by something learned.

Return to contents

4Exhaustive search and the sliding window

Before a detector can classify an object it must propose a region to classify, and the most direct proposal strategy is to try every region. The sliding window does exactly this. A rectangle of fixed size is moved across the image at a regular stride, and at each position the contents of the rectangle are scored for the presence of an object. The figure below carries out such a sweep and reports, for each window, an objectness score; here that score is the overlap of the window with the nearest true object, which stands in for the response a trained classifier would give.

The sweep makes the cost of the strategy visible. A single pass evaluates a number of windows proportional to the image area divided by the square of the stride. Worse, an object may appear at any size, so the sweep must be repeated for windows of many sizes, conventionally by rescaling the image and sweeping again, which is the image pyramid. The total number of windows reaches the hundreds of thousands for a modest image. Every one of them is passed to the classifier.

Two observations about this cost shaped the history reviewed above. The first is that nearly every window is empty, which is the observation the Viola-Jones cascade exploited by rejecting empty windows cheaply. The second is that adjacent windows overlap heavily and so their classifier inputs share most of their content, which is the redundancy that Fast R-CNN removed by computing one feature map for the whole image. The sliding window is therefore not merely an old method; it is the baseline whose two inefficiencies, wasted effort on background and repeated effort on overlapping regions, named the problems that the next two decades of work set out to solve.

5From hand-crafted descriptors to learned features

A window of raw pixels is a poor input to a classifier. The same object under a slightly different light, or shifted by a few pixels, produces a numerically very different array of intensities, and a classifier given raw pixels must somehow learn to ignore those variations while remaining sensitive to the differences that separate one category from another. The role of a feature is to perform that first reduction: to map a window of pixels to a representation in which the irrelevant variation has been suppressed and the useful variation preserved.

The hand-crafted descriptors named in the literature review were careful answers to this problem. The histogram of oriented gradients discarded absolute intensity and kept the distribution of edge orientations, on the reasoning that the shape of an object is carried by its edges and not by its brightness. This was a sound piece of reasoning, and it was also a ceiling. A hand-designed feature can only encode the invariances its designer thought to build in, and a designer cannot anticipate every way that an object's appearance varies.

A convolutional network removes the designer from this step. It applies a stack of learned filters, each of which is a small pattern swept across its input, interleaved with operations that reduce spatial resolution. The filters are not specified; they are adjusted during training so that the representation they produce is the one most useful for the task. Examined after training, the early filters tend to respond to oriented edges, much as the hand-crafted descriptors did, and the later layers respond to progressively larger and more abstract configurations. The network arrives at a hierarchy of features comparable in kind to the hand-crafted ones, but fitted to the data rather than guessed in advance.

For detection the important property of this stack is that it is itself a sliding operation. Because every filter is applied identically at every position, a single pass of the network over a whole image produces a feature map in which each location summarises the appearance of the corresponding region of the input. The detector can then read its predictions from that one map. This is the precise sense in which the learned feature and the shared computation of Fast R-CNN are the same advance seen from two sides: the network that learns the feature is also the network that computes it once for the entire image.

6Measuring overlap: intersection over union

A detector that returns a box must be told how good that box is, both during training and during evaluation, and the answer must be a single number. The measure the field has settled on is intersection over union, often abbreviated to IoU and also called the Jaccard index. For two boxes it is the area of their intersection divided by the area of their union.

The figure below computes it for two boxes that can be moved and resized independently. The construction has three properties worth drawing out. It is zero when the boxes do not touch, because the intersection is then empty. It is one only when the boxes coincide exactly, because only then are intersection and union equal. And it falls between those extremes in a way that penalises a box for being too large as much as for being too small, because enlarging a box adds to the union without adding to the intersection.

That last property is the reason intersection over union is preferred to the simpler measure of how much of the true object a box covers. A box that covered the whole image would cover the whole object, and so would score perfectly under a coverage measure, while being useless as a localization. Intersection over union forbids this, because the enormous union of such a box drives the ratio toward zero.

A threshold on intersection over union converts the continuous score into a verdict. A prediction is conventionally counted as correct if its overlap with a true object reaches one half. The choice of one half is a convention rather than a law, and stricter evaluations report performance averaged over a range of thresholds, a point taken up in section eight. The threshold also appears inside the detector, where the next section uses it to decide when two predictions are close enough to be considered duplicates.

7Duplicate predictions and non-maximum suppression

A detector does not produce one box per object. Because it scores many overlapping windows or anchors, and because several of them will overlap any given object well enough to fire, the raw output is a cluster of boxes around each true object, each carrying a confidence score. Left alone, this would be counted as many detections of one object, which is both wrong and, as section eight shows, heavily penalised. The cluster must be reduced to a single box.

The standard reduction is non-maximum suppression. Its procedure is short. Take the candidate with the highest confidence and accept it. Discard every other candidate whose intersection over union with the accepted box exceeds a threshold, on the reasoning that such a candidate is describing the same object. Repeat with the highest-confidence candidate among those that remain, and continue until none are left. The figure below runs this procedure one step at a time over a scene whose candidates have been clustered around the true objects.

The threshold governs a real trade-off, and the figure's slider makes it adjustable. Set it low and the algorithm suppresses aggressively; this cleanly removes duplicates but risks discarding the legitimate detection of a second object that genuinely overlaps the first, as happens in a crowd. Set it high and the algorithm suppresses timidly; this preserves detections of closely spaced objects but allows some duplicates to survive. There is no setting that is correct for every image, which is why non-maximum suppression is one of the hand-designed components that later work, including the detection transformer, has sought to remove.

8Confidence, precision, recall and mean average precision

Every box a detector emits carries a confidence score, an estimate of how likely it is that the box marks a real object. The scores are not decisions; they become decisions only when a threshold is applied, and every prediction above the threshold is reported while every prediction below it is withheld. The choice of threshold is therefore a choice about the kind of mistake the detector should prefer.

Two quantities measure those mistakes. Precision is the fraction of reported boxes that are correct; it falls when the detector reports objects that are not there. Recall is the fraction of true objects that were reported; it falls when the detector misses objects that are there. The figure below evaluates a fixed set of detections against a known ground truth and lets the confidence threshold be moved.

Moving the threshold reveals that precision and recall are opposed. A high threshold reports only the most confident boxes, which are usually correct, so precision is high; but it withholds the less confident boxes, some of which were correct, so recall is low. A low threshold reports almost everything, recovering most true objects at the cost of admitting many false ones. Because no single threshold is best, a detector is not evaluated at one threshold. It is evaluated by the whole curve that precision and recall trace as the threshold is swept, shown in the right-hand panel of the figure.

The area under that curve is a single number summarising the curve, and it is called the average precision. Averaging the average precision over every object category gives the mean average precision, the figure by which detectors are compared and ranked. The two benchmarks that standardised this evaluation, PASCAL VOC [11] and later Microsoft COCO [12], differ in the strictness of the overlap threshold they require: COCO averages the score over several thresholds from a lenient one half to a strict nineteen twentieths, and so rewards a detector for the precise placement of its boxes and not only for their rough presence.

9Anchors and single-stage detection

The sliding window of section four had to be repeated at many sizes because an object can be large or small. The anchor is the device that folds that repetition into the network. At each location of the shared feature map a fixed set of reference boxes is defined, differing in size and in aspect ratio, and the detector does not predict a box from nothing. It predicts, for each anchor, whether an object is present and a small correction to the anchor's coordinates. A wide object is captured by adjusting a wide anchor; a tall object, a tall one.

The figure below overlays a grid on the scene. Each cell is responsible for the objects whose centre falls within it, and at each cell the candidate anchors are drawn. A coarse grid is cheap to evaluate but cannot separate two objects whose centres share a cell; a fine grid resolves them at greater cost. The slider makes the trade-off visible.

This arrangement is what allows a single-stage detector to do its work in one pass. There is no separate proposal step, because the anchors are a fixed, pre-tiled set of proposals. The network classifies and refines all of them at once, and non-maximum suppression then reduces the result. The cost of the design is the imbalance noted in the literature review: the anchors number in the tens of thousands and almost all of them are background, which is the imbalance the focal loss [10] was introduced to correct. The anchor is thus a clear example of the pattern that runs through this whole document, a hand-designed structure that buys a concrete efficiency and, in doing so, creates the next problem to be solved.

10Conclusion

The modern object detector is an assembly of parts, and this document has taken the parts one at a time. The bounding box is the shared representation. Intersection over union is the measure that judges it. The sliding window is the search whose two inefficiencies, wasted effort on background and repeated effort on overlapping regions, set the agenda for everything that followed. Learned features replaced the hand-crafted descriptors and, by their nature as a sliding operation, supplied the shared feature map. Non-maximum suppression reduces the resulting cluster of predictions to one box per object. Precision, recall and their summary, the mean average precision, are how the finished detector is judged. Anchors tile the feature map with reference boxes and make single-pass detection possible.

The literature review argued that this assembly is not arbitrary. Each part was introduced to answer a documented failure of the part before it, and the same is true of the parts that will eventually replace these. Non-maximum suppression and the anchor are hand-designed, and the history of the field is largely the history of hand-designed components being identified as limitations and then learned. A reader who has followed the argument here is equipped to read that continuing history, because the questions it asks are the questions this document has posed: how is the search made affordable, how is appearance described, and how is a variable-length list of boxes trained and judged.

Return to contents

RReferences

  1. Viola, P. and Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
  2. Dalal, N. and Triggs, B. (2005). Histograms of oriented gradients for human detection. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
  3. Felzenszwalb, P., Girshick, R., McAllester, D. and Ramanan, D. (2010). Object detection with discriminatively trained part-based models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(9).
  4. Krizhevsky, A., Sutskever, I. and Hinton, G. (2012). ImageNet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems.
  5. Girshick, R., Donahue, J., Darrell, T. and Malik, J. (2014). Rich feature hierarchies for accurate object detection and semantic segmentation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
  6. Girshick, R. (2015). Fast R-CNN. Proceedings of the IEEE International Conference on Computer Vision.
  7. Ren, S., He, K., Girshick, R. and Sun, J. (2015). Faster R-CNN: towards real-time object detection with region proposal networks. Advances in Neural Information Processing Systems.
  8. Redmon, J., Divvala, S., Girshick, R. and Farhadi, A. (2016). You only look once: unified, real-time object detection. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
  9. Liu, W., Anguelov, D., Erhan, D., Szegedy, C., Reed, S., Fu, C.-Y. and Berg, A. (2016). SSD: single shot multibox detector. European Conference on Computer Vision.
  10. Lin, T.-Y., Goyal, P., Girshick, R., He, K. and Dollár, P. (2017). Focal loss for dense object detection. Proceedings of the IEEE International Conference on Computer Vision.
  11. Everingham, M., Van Gool, L., Williams, C., Winn, J. and Zisserman, A. (2010). The PASCAL visual object classes (VOC) challenge. International Journal of Computer Vision, 88(2).
  12. Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P. and Zitnick, C. (2014). Microsoft COCO: common objects in context. European Conference on Computer Vision.
  13. Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A. and Zagoruyko, S. (2020). End-to-end object detection with transformers. European Conference on Computer Vision.
  14. Uijlings, J., van de Sande, K., Gevers, T. and Smeulders, A. (2013). Selective search for object recognition. International Journal of Computer Vision, 104(2).