Part 1 · 1960s to 2011

The classical era of computer vision

From the blocks world to Fisher vectors: fifty years of hand-designed representations, and the ceiling they hit.

Source: notes/02-cv-history-classical-era.md · 1,679 words · 1960s to 2011

Covers the period before deep learning took over vision. The point of this note is to explain what researchers were actually doing for fifty years, and why their approach hit a ceiling. See Neural lineage for the neural network thread that was running in parallel, and The challenge for the specific problem ResNet was built to solve.

#1960s: the optimism phase

Computer vision started with a spectacular misjudgment of difficulty. In 1966, Seymour Papert launched the MIT Summer Vision Project, which proposed to have undergraduates build a system over a single summer that could segment a scene into objects and identify them. The project became the field's founding cautionary tale, because the problem it described casually is still not fully solved sixty years later.

Larry Roberts' 1963 MIT thesis, "Machine Perception of Three-Dimensional Solids," is usually cited as the first real computer vision work. It operated in the "blocks world": scenes of polyhedral objects under controlled lighting, where the system extracted edges and fit 3D models. The underlying assumption of this era was that vision is fundamentally a geometry recovery problem. If you could invert the projection from 3D world to 2D image, understanding would follow.

#1970s and 1980s: geometry and the Marr paradigm

Work through this period stayed close to the geometry framing:

• Line labeling and constraint propagation for blocks-world scenes (Waltz, 1975).
• Generalized cylinders as a shape vocabulary (Binford, 1971).
• Edge detection as a first-class problem, culminating in the Canny detector (1986), still used today.
• Optical flow (Horn and Schunck, 1981; Lucas and Kanade, 1981), stereo correspondence, camera calibration, and structure from motion.

David Marr's posthumous book Vision (1982) gave the era its intellectual frame. Marr argued that any information processing system should be understood at three levels: computational theory (what problem is being solved and why), representation and algorithm (what representation is used), and hardware implementation. He proposed a specific pipeline for vision: a primal sketch of edges and blobs, then a viewer-centered 2.5D sketch of surfaces and depth, then an object-centered 3D model.

The Marr framing was enormously influential and also, in retrospect, a constraint. It treated vision as a sequence of human-designable stages, each of which a researcher could specify by reasoning about the problem. Nothing in it suggested that the representation itself should be learned from data.

#1990s: statistical methods arrive

The 1990s brought machine learning into the pipeline, though usually only at the final classification step:

• Eigenfaces (Turk and Pentland, 1991) applied PCA to face images, treating recognition as a subspace projection problem. This was an early signal that statistics over pixels could beat explicit geometric modeling.
• Normalized cuts (Shi and Malik, 1997) reframed segmentation as a graph partitioning problem.
• Support vector machines and kernel methods arrived and quickly became the default classifier, with strong theory behind them and convex, reproducible training.

#1999 to 2011: the hand-crafted feature pipeline

This is the era that immediately preceded deep learning, and it is the one worth understanding in detail, because it defines what AlexNet and later ResNet were displacing.

#The standard pipeline

Nearly every competitive system from roughly 2003 to 2011 had the same four-stage shape:

1. Detect interest points or sample a dense grid of patches.
2. Describe each patch with a hand-engineered descriptor, most often SIFT or HOG.
3. Encode and pool the descriptors into one fixed-length image vector, using bag-of-visual-words, spatial pyramids, or Fisher vectors.
4. Classify that vector, almost always with an SVM.

Only stage 4 was learned. Stages 1 through 3, the part that determines what information even reaches the classifier, were designed by hand by researchers reasoning about invariance. This is the single most important structural fact about the era.

#The key components

SIFT (Lowe, ICCV 1999, refined in IJCV 2004) described a patch by histograms of gradient orientations over a 4x4 spatial grid, producing a 128-dimensional vector designed to be invariant to scale, rotation, and illumination changes. It was excellent for matching the same physical object across two views, which made wide-baseline stereo and image stitching work well.

HOG (Dalal and Triggs, 2005) applied dense gradient-orientation histograms over a sliding window, with local contrast normalization. It was built for pedestrian detection and made dense sliding-window detection practical. The Dalal-Triggs detector won the 2006 PASCAL detection challenge.

Viola-Jones (2001) deserves separate mention as the era's engineering triumph: Haar wavelet features, AdaBoost feature selection, and a cascade of increasingly expensive classifiers so that easy negatives get rejected immediately. It ran face detection in real time on consumer hardware and shipped in cameras for a decade.

Bag of visual words (Sivic and Zisserman's "Video Google," ~2003) borrowed from text retrieval. Run k-means on a large pool of SIFT descriptors to build a visual vocabulary, assign each descriptor in an image to its nearest cluster, and represent the image as a histogram of those cluster counts. It was the dominant classification method at PASCAL VOC 2007. Spatial pyramid matching (Lazebnik et al., 2006) fixed its worst flaw, the total loss of spatial layout, by pooling histograms over a coarse grid at multiple scales.

Fisher vectors (Perronnin and Dance, CVPR 2007, matured through 2013) replaced hard k-means assignment with a generative model. Fit a Gaussian mixture model to the descriptor distribution, then encode a patch by its deviation from that model, specifically the gradient of the log-likelihood with respect to the GMM parameters. This captured first- and second-order statistics instead of just counts, worked well with cheap linear classifiers, and was the strongest pre-deep-learning image representation.

Deformable part models (Felzenszwalb et al., 2008, PAMI 2010) were the peak of classical object detection. A DPM used a coarse HOG "root" filter for the whole object plus finer-resolution HOG part filters that could shift relative to the root, each displacement paying a learned deformation cost. Training used a latent SVM formulation, since part locations were never annotated, plus hard negative mining. Later versions added mixture components to handle viewpoint variation, bounding box regression, and contextual rescoring. DPMs won PASCAL detection in 2007, 2008, and 2009 and remained the reference method through VOC 2012. Felzenszwalb and Girshick received a PASCAL VOC lifetime achievement award in 2010.

One underrated reason DPMs dominated: the authors released high-quality MATLAB and C++ code. A generation of PhD students built their papers on that codebase, which compounded the method's influence well beyond its accuracy.

#The benchmarks that disciplined the field

PASCAL VOC (2005 to 2012) was the first standardized, competitive vision benchmark. It covered 20 everyday object classes; the two versions most used for detection are VOC2007 (about 5k training images, 12k annotated objects) and VOC2012 (about 11k training images, 27k objects). It introduced the practice of a held-out test server and annual workshop comparison, which is the template every later benchmark copied.

ImageNet (Deng, Dong, Socher, Li, Li, and Fei-Fei, CVPR 2009) was a change in kind, not degree. Organized around WordNet noun synsets and labeled via Amazon Mechanical Turk, it grew to roughly 14 million labeled images across more than 20,000 categories. Annotation precision was measured at about 99.7%. ILSVRC, the annual challenge subset launched in 2010, used 1,000 classes with roughly 1.2 million training images and scored submissions by top-5 error, meaning the fraction of images where the true label was not among the model's five best guesses. Top-5 was chosen because ImageNet contains many fine-grained confusable classes, including about 120 dog breeds, and images often contain multiple objects.

The first two ILSVRC results are the high-water mark of the classical pipeline:

Those numbers are worth sitting with. On roughly three out of ten images, the best system in the world could not get the right answer into five guesses.

#Why the classical approach hit a ceiling

#The semantic gap and nuisance variability

Instances of a category vary along many axes that must not change the label: viewpoint, scale, illumination, articulation and deformation, occlusion, background clutter, and intra-class appearance variation. SIFT and HOG are invariant to a couple of these, by construction, and blind to the rest. There is no obvious way to hand-design invariance to "different breeds of dog in different poses." The mapping from pixels to semantics is too complex to write down, and writing it down was exactly what the methodology required.

#The representation could not learn

This is the core critique. If a HOG-based detector fails on your data, you cannot improve HOG by showing it more data, because HOG has no parameters fit to your task. The only adaptive component sat at the very end of the pipeline, on top of a representation that had already thrown away whatever it was going to throw away. Practitioners spent their effort on feature engineering, encoding tricks, and ensembling, which is why progress at VOC came in increments of a couple of mAP points per year.

#Datasets and compute were too small to support the alternative

Learning a representation end-to-end requires far more labeled data and compute than learning a final-layer classifier. Caltech-101 (2004) had about 9,000 images, which is nowhere near enough to fit millions of parameters without catastrophic overfitting. So the obvious rebuttal to "why not learn the features too" was empirically correct for most of the era: it did not work yet. ImageNet in 2009 and cheap GPU compute around 2010 removed both halves of that objection within about two years of each other, which is why the transition, when it came, was so abrupt.

#Takeaway

By 2011 the field had a mature, well-understood, carefully engineered pipeline that was improving slowly and was structurally incapable of the improvement it needed. The limitation was not any individual component. It was that humans, rather than data, were choosing the representation.