Computer Vision

How programs extract information from images. Images as arrays of numbers and the main vision tasks, why a plain network suits images poorly, convolution worked by hand on a handwritten 7 with ReLU and max pooling, convolutional networks from LeNet-5 to AlexNet, MNIST, ImageNet and what its benchmark did and did not measure, a seeded experiment in which shifting test digits by one pixel costs logistic regression 54 points of accuracy and a small convolutional network 37, and the shortcuts and biases that limit vision models in practice.

To a program, the handwritten 7 below is 64 numbers. It comes from the digits data shipped with scikit-learn, 1,797 images of 8 by 8 pixels scanned from forms filled in by volunteers (Alpaydin and Kaynak, 1998), and each pixel holds a gray level from 0 (background) to 16 (full ink):

 0  0  7  8 13 16 15  1
 0  0  7  7  4 11 12  0
 0  0  0  0  8 13  1  0
 0  4  8  8 15 15  6  0
 0  2 11 15 15  4  0  0
 0  0  0 16  5  0  0  0
 0  0  9 15  1  0  0  0
 0  0 13  5  0  0  0  0

A person sees a horizontal bar at the top, a short bar crossing the middle, and a stroke falling to the lower left, and so a 7. Nothing in the table says "bar" or "stroke". Computer vision is the part of artificial intelligence that builds programs to get from arrays like this one to statements about what they show: which digit, whether there is a pedestrian in front of the car, where the tumor's boundary lies. This article describes the representation, the operation at the center of modern vision models, convolution, worked by hand on this 7, the networks built from it, the benchmark that made them famous, an experiment on what they do and do not buy, and the ways vision models fail.

Images as arrays

A grayscale image of height $H$ and width $W$ is an $H \times W$ array of intensities. A color image stores three such arrays, one each for red, green and blue, so it is an $H \times W \times 3$ array; James, Witten, Hastie and Tibshirani (2021, §10.3) call such a three-dimensional array a feature map, with two spatial axes and a third channel axis. A photograph of 4,000 by 4,000 pixels therefore holds 48 million numbers. A video is a sequence of such arrays over time. The pixel values are usually rescaled before modeling, to the interval 0 to 1 or to mean 0 and standard deviation 1, for the same reasons inputs are standardized in any distance-based or gradient-trained model.

The array is all a program receives, which is why vision was long considered hard. Lighthill's 1972 survey of artificial intelligence found that "even the recognition of printed and typewritten characters posed a quite surprising degree of difficulty, while the recognition of handwritten characters appears completely out of reach" (Lighthill, 1973, §3). The rest of this article is in part the story of how that changed.

The tasks

Vision systems are built for several kinds of output.

Task Input Output Example
Image classification an image one label (or a ranked list of labels) for the whole image which digit; which of 1,000 object categories
Object detection an image a labeled box around each object of interest pedestrians and cyclists in a street scene
Segmentation an image a label for every pixel, or a division into regions the outline of an organ in a scan
Captioning an image a sentence describing it "a dog sitting on grass"
Generation text, noise or another image a new image an image from a written description; see Generative AI

The ImageNet challenge discussed below ran classification, single-object localization and object detection tasks (Russakovsky et al., 2015, §2). Segmentation comes in two forms: semantic segmentation assigns a class label to each pixel ("road", "car", "sky"), while segmentation in the older, unsupervised sense divides an image into coherent regions without naming them, which is clustering applied to pixels. Captioning and generation join vision to language, and the language article covers the other half.

Why a plain network suits images poorly

Any supervised method can be applied to images by flattening each one into a vector, 64 numbers for the digits, and treating the pixels as ordinary inputs. Logistic regression on the 64 digit pixels is already accurate, about 96% in the experiment below. LeCun, Bottou, Bengio and Haffner (1998, §II) explain why this approach does not scale to real images. First, a fully connected layer needs a weight for every pair of pixel and unit, so on images of several hundred pixels a first layer of 100 units already has several tens of thousands of weights, and such a network has no built-in invariance to shifts or local distortions of the input, which they call its main deficiency. Second, such a network ignores the image's layout: "the input variables can be presented in any (fixed) order without affecting the outcome of the training", whereas in images "variables (or pixels) that are spatially or temporally nearby are highly correlated" (LeCun et al., 1998, §II). A model that treats pixel (3, 4) and pixel (3, 5) as unrelated inputs must learn separately, from data, that a stroke is a stroke wherever it falls.

Convolution worked by hand

A filter, or kernel, is a small array of weights. Convolution slides it across the image and, at each position, multiplies the kernel's weights by the pixels beneath them and adds the products. With a $3 \times 3$ kernel $K$ and image $X$, the output at row $i$ and column $j$ is

$$F_{ij} = \sum_{u=0}^{2} \sum_{v=0}^{2} K_{uv} \, X_{i+u,\, j+v}.$$

The output array $F$ is again called a feature map. If the kernel stays entirely inside the image (a "valid" convolution), an $8 \times 8$ image gives a $6 \times 6$ map. Strictly, this formula is cross-correlation; the convolution of signal processing flips the kernel first, using $K_{2-u,\,2-v}$. Neural network libraries compute the formula above and call it convolution, and since the kernel's weights are learned, the flip makes no difference to what a network can represent.

Take the kernel

$$K = \begin{pmatrix} -1 & 0 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{pmatrix},$$

a vertical-edge detector (the Prewitt kernel). It subtracts the column on the left of each $3 \times 3$ window from the column on the right, so it is large and positive where the image gets brighter from left to right, large and negative where it gets darker, and near zero where the image is uniform. For the window whose top-left corner is at row 1, column 2 (counting from 0), the pixels and their products with $K$ are

$$\begin{pmatrix} 7 & 7 & 4 \\ 0 & 0 & 8 \\ 8 & 8 & 15 \end{pmatrix} \longrightarrow \begin{pmatrix} -7 & 0 & 4 \\ 0 & 0 & 8 \\ -8 & 0 & 15 \end{pmatrix}, \qquad F_{1,2} = -7 + 4 + 8 - 8 + 15 = 12.$$

Doing the same at all 36 positions gives the feature map

 14  15  11  25   3 -39
 15  11  12  24  -8 -39
 19  17  19   9 -31 -32
 19  33  16 -20 -29 -19
 20  44   1 -42 -21  -4
 22  36 -16 -36  -6   0

The positive values trace the left edge of the 7, where ink begins; the negative values trace its right edge, where ink ends. The diagonal of large negative values from the top right to the bottom center is the right-hand side of the falling stroke. The same kernel transposed, with $-1$s in the top row and $1$s in the bottom, responds to horizontal edges instead, and for this image it is largest (33) at the upper edge of the short bar across the middle.

Two more operations complete the basic building block. A ReLU replaces negative values by zero, keeping only the "ink begins here" responses (Nonlinear Activation Functions covers ReLU and its alternatives). Max pooling then divides the map into $2 \times 2$ blocks and keeps the largest value of each, halving the height and width:

$$\text{ReLU, then pool:}\quad \begin{pmatrix} 15 & 25 & 3 \\ 33 & 19 & 0 \\ 44 & 1 & 0 \end{pmatrix}.$$

The handwritten 7 (left), the 6 × 6 map produced by the vertical-edge kernel, with positive responses in blue along the left edge of the ink and negative responses in orange along the right edge, the map after ReLU, and the 3 × 3 result of 2 × 2 max pooling. The yellow box marks the window worked in the text and the map entry it produces, 12.
The handwritten 7 (left), the 6 × 6 map produced by the vertical-edge kernel, with positive responses in blue along the left edge of the ink and negative responses in orange along the right edge, the map after ReLU, and the 3 × 3 result of 2 × 2 max pooling. The yellow box marks the window worked in the text and the map entry it produces, 12.

The pooled map says, coarsely, where in the image there are left edges of strokes: strongly in the lower left and the upper middle, hardly at all on the right. Pooling discards exactly where within each $2 \times 2$ block the edge was, which is the point. In LeCun et al.'s words, once a feature has been detected "its exact location becomes less important. Only its approximate position relative to other features is relevant" (1998, §II.A).

Convolutional networks

A convolutional neural network (CNN) is a neural network whose early layers are convolutions. Instead of fixing kernels such as the edge detector above, it learns their weights by backpropagation, like any other weights. LeCun et al. (1998, §II.A) name the three architectural ideas: local receptive fields (each unit sees only a small patch of the layer below), shared weights (the same kernel is applied at every position, so a feature learned in one place is detected everywhere), and spatial subsampling, of which pooling is the common modern form. A layer applies many kernels at once, producing one feature map per kernel, and the next layer's kernels look across all of those maps, so that later layers combine edges into strokes, strokes into parts and parts into objects. After several such layers the maps are flattened and passed to ordinary fully connected layers that make the final prediction.

Weight sharing is what makes the approach economical. The small network trained in the experiment below has 8 kernels of $3 \times 3$ weights plus a bias each, 80 parameters, followed by a dense layer from the $3 \times 3 \times 8 = 72$ pooled values to 10 classes, 730 parameters: 810 in all. A network with one fully connected hidden layer of 64 units on the same images needs 4,810.

Shared weights also give convolution a useful property. LeCun et al. (1998, §II.A) put it this way: "if the input image is shifted, the feature map output will be shifted by the same amount, but will be left unchanged otherwise". Convolution is equivariant to shifts: move the 7 one pixel to the right and its edge map moves one pixel to the right too. Pooling then makes the summary partly invariant, unchanged by small shifts, though only partly, since a shift that crosses a pooling block boundary still changes the result.

An experiment: shifting the digits by one pixel

How much does that matter in practice? The experiment trains three classifiers on half of the 1,797 digits and tests them on the other half, as drawn and shifted by one pixel in each of four directions, over 30 random splits. The classifiers are multinomial logistic regression on the 64 pixels, a multilayer perceptron with one hidden layer of 64 ReLU units (scikit-learn's MLPClassifier), and the small convolutional network described above (8 learned $3 \times 3$ kernels, ReLU, $2 \times 2$ max pooling, a softmax output), written in NumPy for this article, checked against finite differences (largest relative error $1.6 \times 10^{-5}$), and trained with Adam for 60 epochs. None of them saw a shifted image in training.

Model Parameters Accuracy, test digits as drawn Accuracy, shifted one pixel Drop
Logistic regression 650 0.961 (IQR 0.008) 0.422 (IQR 0.013) 0.539
MLP, 64 hidden units 4,810 0.971 (IQR 0.008) 0.454 (IQR 0.024) 0.518
Small CNN 810 0.973 (IQR 0.011) 0.601 (IQR 0.031) 0.373

Values are medians over the 30 splits; the shifted accuracy is the mean over the four directions, and the drop is the median of the per-split differences.

Test accuracy of three classifiers on 899 handwritten digits, as drawn (circles) and shifted by one pixel (squares), with medians and interquartile ranges over 30 splits. All three are about equally accurate on digits drawn the way they were trained on. A one-pixel shift costs logistic regression and the MLP more than half their accuracy; the convolutional network loses much less, but still loses over a third.
Test accuracy of three classifiers on 899 handwritten digits, as drawn (circles) and shifted by one pixel (squares), with medians and interquartile ranges over 30 splits. All three are about equally accurate on digits drawn the way they were trained on. A one-pixel shift costs logistic regression and the MLP more than half their accuracy; the convolutional network loses much less, but still loses over a third.

On digits like the training digits, the three models are nearly equally good, and the convolutional network's advantage is small. On shifted digits the difference is large: logistic regression and the MLP fall to about 42% and 45%, the convolutional network to 60%. The network's structure, not its size, accounts for this: it has fewer parameters than the MLP. The experiment also shows the limit of that structure. On images only eight pixels wide, a shift of one pixel moves the digit by an eighth of its width, and one layer of $2 \times 2$ pooling absorbs only part of that. The network is more robust to shifts, not immune to them.

The standard remedy is to show the model what it should ignore. Data augmentation replicates each training image with small natural distortions such as shifts, zooms, rotations and flips, a form of regularization that James et al. (2021, §10.3.4) compare in spirit to ridge regression. LeCun et al. (1998, §III.B) did this for their digit recognizer, adding 540,000 randomly distorted copies to the 60,000 training images.

MNIST, ImageNet and AlexNet

MNIST. The benchmark that LeCun et al. (1998, §III.A) assembled from two US National Institute of Standards and Technology databases, one written by Census Bureau employees and one by high-school students, is the Modified NIST set: 60,000 training and 10,000 test images of handwritten digits, size-normalized and centered in $28 \times 28$ fields. Their convolutional network LeNet-5 reached a test error of 0.95% on it (§III.B), and the same paper reports a recognizer of this kind deployed commercially to read checks. Neural networks had been reading handwritten digits since LeCun and colleagues' work on postal ZIP codes at the end of the 1980s (LeCun et al., 1989); MNIST, published with the 1998 paper, became the standard test set for the next fifteen years.

ImageNet. Digits are a small, clean problem. Deng, Dong, Socher, Li, Li and Fei-Fei (2009) set out to build a dataset at the scale of the visual world: an image collection organized by the noun hierarchy of the WordNet lexical database, with the goal of 500 to 1,000 clean, full-resolution images for each of WordNet's roughly 80,000 noun concepts. At publication it held 3.2 million images in 5,247 categories, collected from the web and checked by workers on Amazon Mechanical Turk (Deng et al., 2009, abstract and §3). From 2010 the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) used a subset of 1,000 categories with about 1.2 million training images and ran as an annual competition (Russakovsky et al., 2015, §1 and §3.1). Between 2010 and 2014 the winning classification error fell from 28.2% to 6.7% (Russakovsky et al., 2015, §6.1). Classification error on ImageNet is usually reported as top-5 error, the share of test images whose correct label is not among the model's five most probable labels, since many images contain several objects and some categories are hard to tell apart.

AlexNet. The largest single step came in 2012. Krizhevsky, Sutskever and Hinton (2012) trained a convolutional network with 60 million parameters and 650,000 neurons, in five convolutional layers, some followed by max pooling, and three fully connected layers ending in a 1,000-way softmax. Several of its choices became standard: ReLU activations, which they report trained several times faster than tanh units (§3.1); dropout, which zeroes each hidden unit's output with probability 0.5 during training, to reduce overfitting in the fully connected layers (§4.2); data augmentation by cropping and reflecting the images (§4.1); and training on graphics processors, two of them for five to six days (§1). A variant entered in ILSVRC-2012 achieved a winning top-5 test error of 15.3%, against 26.2% for the second-best entry (abstract). The 2014 winner, GoogLeNet, was again a convolutional network, with a design that allowed its builders to increase both its depth and its width (Russakovsky et al., 2015, §5.1).

What the benchmark measured. Russakovsky et al. (2015, §6.4) compared the 2014 winner, GoogLeNet, with people. One expert annotator who had trained on 500 images labeled 1,500 test images with a top-5 error of 5.1%, against 6.8% for GoogLeNet on the same images; a second annotator, trained on 100 images, had 12.0% on 258 images, with most of the errors coming from failing to consider the correct category among the 1,000 at all. The comparison is often summarized as "computers surpassed humans on ImageNet" in the years after, and the details show why such summaries need care: the human figure comes from one or two trained annotators, and top-5 error on a fixed set of categories is a narrow task. Geirhos et al. (2020, §6.1) make the general point: a dataset like ImageNet was intended to measure object recognition, but models can score well on it by means other than recognizing objects the way people do, and "a dataset is useful only for as long as it is a good proxy for the ability one is actually interested in".

Where vision models fail

Shortcuts. Geirhos et al. (2020) collect many cases of what they call shortcut learning: decision rules that perform well on standard benchmarks but fail under slightly different conditions (abstract). A classifier that has seen cows mostly on grass may fail on a cow at the beach, because "grass" was a reliable predictor in its training data (§1, §4.1). A model that detected pneumonia well in X-rays from the hospitals it was trained on did poorly on scans from new hospitals; it had learned to identify the hospital system, for example from a hospital-specific metal token on the scan, and combined that with each hospital's pneumonia rate (§1, describing Zech et al., 2018). Standard ImageNet-trained networks also rely heavily on texture, so an image of a cat with the surface texture of an elephant is classified as an elephant (§4.2). The shift experiment above is a small, controlled case of the same thing: a model that is right for the wrong reasons on data like its training data.

Adversarial examples and small perturbations. Shifting an image by a few pixels, rotating it, adding a little noise or blur, or changing the background can change a network's prediction completely, and adversarial examples, tiny changes chosen deliberately, can derail it while remaining invisible to people (Geirhos et al., 2020, §4.3).

Unequal performance across groups. Buolamwini and Gebru (2018) evaluated three commercial systems that classify the gender of a face on a benchmark balanced by gender and skin type. All three had their highest error rates for darker-skinned women, up to 34.7%, while the largest error for lighter-skinned men was 0.8% (abstract and Table 4). They also found the two face datasets they examined composed overwhelmingly of lighter-skinned subjects, 79.6% and 86.2% (abstract). The risks article takes up how such disparities are measured and why they arise.

None of these failures is visible in an aggregate accuracy on a test set drawn like the training set. Checking a vision model means testing it on the conditions it will meet: other hospitals, other cameras, other lighting, other populations, and deliberately shifted or corrupted versions of the test images.

In Python

The worked convolution is one call in SciPy, whose correlate2d computes the formula above (and convolve2d the flipped version, which for this kernel gives the same map with the signs reversed):

import numpy as np
from scipy.signal import correlate2d
from sklearn.datasets import load_digits

img = load_digits().images[7]                 # the 7, gray levels 0-16
K = np.array([[-1, 0, 1]] * 3)                # vertical-edge (Prewitt) kernel
F = correlate2d(img, K, mode="valid")         # 6 x 6 feature map
pooled = np.maximum(F, 0).reshape(3, 2, 3, 2).max(axis=(1, 3))
print(F.astype(int), pooled.astype(int), sep="\n\n")

Real convolutional networks are built with a deep learning library such as PyTorch (whose torchvision package adds image datasets, transforms and pretrained models) or Keras, which provide convolution, pooling, automatic differentiation and GPU training. The worked example, the network written from scratch, its gradient check and the shift experiment are computed by tools/experiments/data-science/computer-vision.py in the site's repository; the library's Building Self-Attention Step by Step shows the same from-scratch approach for the attention layers used in language models.

References

  • Alpaydin, E., and Kaynak, C. (1998). Optical Recognition of Handwritten Digits [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C50P49. The scikit-learn digits are a copy of its test part. record · 2 pages
  • Buolamwini, J., and Gebru, T. (2018). Gender shades: Intersectional accuracy disparities in commercial gender classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency, PMLR 81, 77–91. record · 2 pages
  • Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009). ImageNet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 248–255). record
  • Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., and Wichmann, F. A. (2020). Shortcut learning in deep neural networks. Nature Machine Intelligence, 2, 665–673. Read in the arXiv version, arXiv:2004.07780v5. record · 2 pages
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. §10.3. record · 30 pages
  • Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012). ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems 25 (pp. 1097–1105). record · 2 pages
  • LeCun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W., and Jackel, L. D. (1989). Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4), 541–551. Cited by attribution; not read for this article. record
  • LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324. record · 2 pages
  • Lighthill, J. (1973). Artificial intelligence: A general survey. In Artificial Intelligence: A Paper Symposium. Science Research Council. Report dated July 1972. record · 2 pages
  • Russakovsky, O., Deng, J., Su, H., et al. (2015). ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115(3), 211–252. Read in the arXiv version, arXiv:1409.0575v3. record
  • Zech, J. R., et al. (2018). Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: A cross-sectional study. PLoS Medicine, 15, e1002683. Cited as described by Geirhos et al. (2020); not read for this article. record