---
title: "Vision: Reconstructing the 3D World"
module: Frontiers
moduleNumber: 6
lessonNumber: 2
order: 602
summary: >
  A camera collapses a three-dimensional world onto a flat grid; this lesson
  inverts that collapse. We build the camera projection matrix (intrinsics and
  extrinsics), triangulate a point from two views, then work through the toolbox
  of depth cues — motion parallax, binocular stereopsis, multiple views, texture,
  shading, and contour — that turn an ambiguous image back into a scene. We add
  structural recognition (pictorial-structure "cardboard people"), the task-driven
  use of vision in cars and robots, and the shift from hand-built pipelines to
  learned deep-vision networks.
topics: [Frontiers]
sources:
  - book: AIMA
    ref: "Ch. 24 — Perception; §24.4 Reconstructing the 3D World"
  - book: AIMA
    ref: "§24.5 Object Recognition from Structural Information, §24.6 Using Vision"
---

This builds on [Vision and Perception](/artificial-intelligence/frontiers/vision-and-perception),
which took us from the physics of image formation through early image-processing
and recognition by appearance. That lesson ran the pipeline forward, from pixels to
categories. Here we run it the other way: from a flat image back to the
three-dimensional scene that cast it, and from there to the tasks — navigation,
manipulation, and the learned deep-vision systems — that use the recovered world.

## Reconstructing the 3D world

We now invert projection: go from the two-dimensional image back to a
three-dimensional model of the scene. The fundamental difficulty is that all scene
points on one ray to the pinhole project to the same image point, so a single image
under-determines depth. Two ideas address this. With two or more images from different
camera positions we can _triangulate_ to fix a point's position. And we can exploit
background knowledge: given an object model $\mathbf{P}(Scene)$ and a rendering model
$\mathbf{P}(Image \mid Scene)$, compute a posterior $\mathbf{P}(Scene \mid Image)$.
No single unified theory of reconstruction exists; instead there is a toolbox of
visual **cues** — motion, binocular stereopsis, multiple views, texture, shading,
contour, and familiar objects. Each relies on assumptions about physical scenes to
turn an ambiguous image into a near-unambiguous interpretation.

### The camera matrix: intrinsics and extrinsics

Triangulation needs one thing the pinhole equations left implicit: a bookkeeping of
_which_ camera, sitting _where_, produced a given image point. The pinhole model
$x = -fX/Z$ measured the scene from a frame pinned to the pinhole, with the optical
axis along $Z$ and lengths in the sensor's own millimeters. A real reconstruction
juggles several cameras in a shared world frame and reads coordinates in pixels.
Folding both changes into the projection turns the two scalar equations into one
matrix, the **camera projection matrix**, which every multiple-view method below
assumes. Writing points in **homogeneous coordinates** — append a $1$, so a 3-D
point is $\widetilde{\mathbf{X}} = (X, Y, Z, 1)^\top$ and an image point is
$\widetilde{\mathbf{x}} = (u, v, 1)^\top$ up to scale — perspective projection
becomes a single linear map,

$$
\lambda\,\widetilde{\mathbf{x}} = \mathbf{K}\,[\,\mathbf{R} \mid \mathbf{t}\,]\,\widetilde{\mathbf{X}},
$$

where $\lambda$ is the unknown depth that the homogeneous scale absorbs (dividing
through by the third coordinate recovers the pixel address $(u, v)$). The map splits
into two independent pieces that answer two different questions.

The **extrinsic** matrix $[\,\mathbf{R} \mid \mathbf{t}\,]$ — a $3\times 3$ rotation
$\mathbf{R}$ beside a translation $\mathbf{t}$ — places the camera in the world. It
carries a world point into the camera's own frame, $\mathbf{X}_{\text{cam}} =
\mathbf{R}\,\mathbf{X}_{\text{world}} + \mathbf{t}$, so $\mathbf{R}$ encodes the
camera's orientation ($3$ rotational DOFs) and $\mathbf{t}$ its position ($3$
translational DOFs). Two cameras looking at the same scene differ only in their
extrinsics; recovering that relative $\mathbf{R}$ and $\mathbf{t}$ between frames is
the **relative orientation** problem named later in this section.

The **intrinsic** matrix $\mathbf{K}$ turns a direction in the camera frame into a
pixel, absorbing everything about the sensor:

$$
\mathbf{K} = \begin{pmatrix}
f_x & s & c_x \\
0 & f_y & c_y \\
0 & 0 & 1
\end{pmatrix}.
$$

Its five numbers each name one physical fact. The **focal lengths** $f_x, f_y$ are
the focal length $f$ measured in pixels — $f$ divided by the pixel pitch — and they
differ only when the photosites are non-square, so their ratio $f_x/f_y$ is the pixel
**aspect ratio**. The **principal point** $(c_x, c_y)$ is where the optical axis
pierces the sensor, near but rarely exactly at the pixel array's center; it appears
because pixel addresses count from a corner while the projection equations measured
from the axis. The **skew** $s$ is nonzero only if the sensor's rows and columns are
not perpendicular, which for any modern sensor means $s = 0$. Set $f_x = f_y = f$,
$s = 0$, and the principal point at the origin, and $\mathbf{K}$ collapses back to
the bare $x = fX/Z$ scaling the pinhole section derived — the intrinsics collect
the corrections that separate that idealized model from a real camera. **Calibration**
is the process of measuring $\mathbf{K}$ (and any lens distortion) for a specific
camera, typically by photographing a known checkerboard from several angles.

$$
% caption: The camera projection matrix factors into extrinsics and intrinsics. The
% extrinsic block $[\mathbf{R} \mid \mathbf{t}]$ moves a world point into the camera's
% frame (where the camera sits and how it is oriented); the intrinsic block
% $\mathbf{K}$ (focal lengths $f_x, f_y$, principal point $c_x, c_y$, skew $s$) turns
% that camera-frame direction into a pixel address. Their product is the single map
% $\lambda\widetilde{\mathbf{x}} = \mathbf{K}[\mathbf{R} \mid \mathbf{t}]\widetilde{\mathbf{X}}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum width=26mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[bx] (world) at (0,0) {world point\\(X, Y, Z, 1)};
  \node[bx, draw=acc, text=acc, thick] (ext) at (3.7,0) {extrinsics\\R (rotate), t (shift)};
  \node[bx] (cam) at (7.4,0) {camera-frame\\direction};
  \node[bx, draw=red, text=red, thick] (intr) at (11.1,0) {intrinsics K\\fx, fy, cx, cy, s};
  \node[bx] (pix) at (11.1,-2.0) {pixel\\(u, v, 1)};
  \draw[->, acc, thick] (world) -- (ext);
  \draw[->, acc, thick] (ext) -- (cam);
  \draw[->, red, thick] (cam) -- (intr);
  \draw[->, red, thick] (intr) -- (pix);
  \node[black, anchor=north, font=\scriptsize] at (3.7,-0.85) {where the camera is};
  \node[black, anchor=north, font=\scriptsize] at (11.1,-0.85) {what the sensor does};
\end{tikzpicture}
$$

A general projection matrix $\mathbf{P} =
\mathbf{K}[\,\mathbf{R} \mid \mathbf{t}\,]$ has $11$ degrees of freedom (a $3\times 4$
matrix defined up to overall scale): $5$ intrinsic, $3$ for the rotation, $3$ for the
translation. Reconstruction from images is the inverse task — recover the $\mathbf{P}$
of each view, and the 3-D points, from the pixels alone.

### Two-view triangulation

With the projection matrix named, the first reconstruction idea, triangulation, is
immediate. Suppose the same scene point $P$ is seen in two calibrated cameras, whose
centers $C_1$ and $C_2$ and orientations are known. A pixel $x_1$ in the first image
does not fix $P$ — it fixes only the **ray** from $C_1$ through $x_1$, since every
point along that ray projects to the same pixel (the depth ambiguity of a single
view). The second camera supplies a second ray, from $C_2$ through the matched pixel
$x_2$. The scene point must lie on both rays at once, so it sits at their
**intersection**. Two rays in space generically meet in one point, and that point is
$P$: two views convert an unknown depth into a fixed 3-D location.

$$
% caption: Two-view triangulation. The scene point $P$ projects to $x_1$ in camera
% $C_1$ and $x_2$ in camera $C_2$. Each pixel back-projects to a ray (the locus of
% points that project there), and $P$ is where the two rays intersect. A single view
% leaves $P$ anywhere on its ray; the second ray pins the depth. Measurement noise
% leaves the rays skew, so in practice $P$ is the midpoint of their common
% perpendicular.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % camera 1 (left)
  \fill[acc] (0,0) circle (2pt);
  \node[acc, anchor=east, font=\scriptsize] at (-0.1,0) {C1};
  % image plane 1 (small tilted segment in front of C1)
  \draw[acc, thick] (1.2,-0.55) -- (1.6,0.75);
  \node[acc, anchor=north, font=\scriptsize] at (1.4,-0.6) {image 1};
  % pixel x1 on plane 1
  \fill[red] (1.44,0.35) circle (1.6pt);
  \node[red, anchor=south east, font=\scriptsize] at (1.5,0.42) {x1};
  % camera 2 (right)
  \fill[acc] (0.4,-2.6) circle (2pt);
  \node[acc, anchor=east, font=\scriptsize] at (0.3,-2.6) {C2};
  % image plane 2 (crosses the C2 ray at x2)
  \draw[acc, thick] (1.75,-1.9) -- (2.7,-0.78);
  \node[acc, anchor=north, font=\scriptsize] at (2.0,-1.95) {image 2};
  % pixel x2 on plane 2, sitting on the C2 ray
  \fill[red] (2.23,-1.334) circle (1.6pt);
  \node[red, anchor=north west, font=\scriptsize] at (2.3,-1.4) {x2};
  % scene point P (upper right, where rays meet)
  \fill[black] (6.6,1.7) circle (2.4pt);
  \node[black, anchor=west, font=\footnotesize] at (6.75,1.7) {P (scene point)};
  % ray 1: from C1 through x1 to P
  \draw[acc, thick, ->] (0,0) -- (6.5,1.68);
  % ray 2: from C2 through x2 to P
  \draw[acc, thick, ->] (0.4,-2.6) -- (6.5,1.62);
  % baseline between camera centers
  \draw[black, dashed] (0,0) -- (0.4,-2.6);
  \node[black, anchor=east, font=\scriptsize] at (0.05,-1.3) {baseline};
  % annotate intersection (placed clear of both rays, to the right of P)
  \node[black, anchor=north west, font=\scriptsize] at (5.4,-0.2) {rays intersect at P};
\end{tikzpicture}
$$

Two practical points complicate triangulation. First, it needs the
**correspondence** already solved: knowing that $x_1$ and $x_2$ are images of the
_same_ $P$ is the hard part, the same block-matching problem optical flow and stereo
face below. Second, real measurements are noisy, so the two back-projected rays
almost never meet exactly — they pass close but skew. The standard fix takes $P$ as
the midpoint of the shortest segment joining the two rays, or, better, the point
minimizing the sum of squared **reprojection errors** $\lVert x_1 - \Pi_1(P)\rVert^2 +
\lVert x_2 - \Pi_2(P)\rVert^2$, the pixel distance between each measured point and
where the estimated $P$ actually projects. Binocular stereopsis, next, is the special
case where the two cameras are calibrated, parallel, and a known baseline apart, which
reduces the ray intersection to the one-dimensional disparity computation.

### Motion parallax

If the camera moves relative to the scene, the optical flow it induces is a source
of information about both camera motion and depth. Relating flow to the viewer's
translational velocity $\mathbf{T}$ and the depth $Z(x, y)$, the flow components are

$$
v_x(x, y) = \frac{-T_x + x\,T_z}{Z(x, y)}, \qquad
v_y(x, y) = \frac{-T_y + y\,T_z}{Z(x, y)} .
$$

Find where the flow is zero. Set $v_x = 0$: the fraction vanishes only when its
numerator does, so $-T_x + x\,T_z = 0$, i.e. $x = T_x / T_z$. The same on the other
axis gives $y = T_y / T_z$. Both components vanish at this single image point — the
**focus of expansion**, the point the flow radiates from. Move the image origin there,
writing $x' = x - T_x / T_z$ and $y' = y - T_y / T_z$. Then $x\,T_z = (x' + T_x/T_z)T_z
= x'\,T_z + T_x$, so the numerator $-T_x + x\,T_z$ becomes just $x'\,T_z$, and the flow
takes a clean radial form,

$$
v_x(x', y') = \frac{x'\,T_z}{Z(x', y')}, \qquad
v_y(x', y') = \frac{y'\,T_z}{Z(x', y')} .
$$

The flow at each point now aims straight along the ray from the focus of expansion,
with a length proportional to the distance $r' = \sqrt{x'^2 + y'^2}$ from that focus and
inversely proportional to depth. Driving forward, the point you are heading toward sits
still while everything streams outward past it, faster near the edges of the frame and
faster for near objects.

$$
% caption: Radial optical flow under forward motion. The flow vanishes at the focus
% of expansion (FOE) and points outward along each ray; its length grows with distance
% from the FOE and shrinks with depth Z, so the same object flows faster when nearer.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % frame
  \draw[black] (-3.0,-1.9) rectangle (3.0,1.9);
  % focus of expansion
  \fill[red] (0,0) circle (2pt);
  \node[red, font=\scriptsize, anchor=south west] at (0.1,0.08) {FOE};
  % radial flow arrows (short near center, long near edge)
  \foreach \a in {0,30,...,330} {
    \draw[acc, thick, ->] ({0.9*cos(\a)},{0.9*sin(\a)}) -- ({1.9*cos(\a)},{1.9*sin(\a)});
  }
  \node[black, font=\scriptsize, anchor=west] at (2.05,1.55) {longer near edge};
\end{tikzpicture}
$$

There is a scale-factor ambiguity: double the camera speed, the object sizes, and
their distances all at once, and the flow field is identical. But useful ratios
survive. A fly landing on a wall needs its **time to contact** $Z / T_z$ — the
instantaneous flow gives neither $Z$ nor $T_z$ alone, yet it gives their ratio,
which is enough to control the approach, and many animals exploit this. And for two
points at depths $Z_1, Z_2$, the inverse ratio of their flow magnitudes recovers the
depth ratio $Z_1 / Z_2$ — this is **motion parallax**, the cue that tells you, from a
moving car window, that the slow-moving parts of the landscape are the far ones.

### Binocular stereopsis

Most vertebrates have two eyes; predators put them in front to use **binocular
stereopsis**. The idea resembles motion parallax except the two images are separated
in space, not time. Because a scene feature sits at a different place relative to the
$z$-axis of each image plane, superposing the two images reveals a **disparity** —
the shift in the feature's location between them.

$$
% caption: Binocular disparity. A scene point $P$ at depth $Z$ projects to $P_L$
% and $P_R$ in the two eyes, whose centers are a baseline $b$ apart and which
% fixate $P_0$. The angular disparity between the projections is $\delta\theta$,
% and by similar triangles $\delta\theta \approx b\,\delta Z / Z^2$.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % left and right eye centers
  \fill[acc] (0,1.0) circle (2pt);  \node[acc, font=\footnotesize, anchor=east] at (-0.1,1.0) {left eye};
  \fill[acc] (0,-1.0) circle (2pt); \node[acc, font=\footnotesize, anchor=east] at (-0.1,-1.0) {right eye};
  % baseline
  \draw[black, <->] (-0.55,1.0) -- (-0.55,-1.0) node[midway, left, black, font=\footnotesize] {b};
  % fixation point P0 and farther point P
  \fill[black] (4.6,0) circle (2pt); \node[black, font=\footnotesize, anchor=south west] at (4.9,0.7) {P0};
  \fill[red] (6.4,0) circle (2.4pt); \node[red, font=\footnotesize, anchor=west] at (6.5,0) {P};
  % rays to fixation
  \draw[black] (0,1.0) -- (4.6,0);
  \draw[black] (0,-1.0) -- (4.6,0);
  % rays to P
  \draw[red] (0,1.0) -- (6.4,0);
  \draw[red] (0,-1.0) -- (6.4,0);
  % depth annotations
  \draw[black, <->] (0,-1.85) -- (4.6,-1.85) node[midway, below, black, font=\footnotesize] {Z};
  \draw[black, <->] (4.6,-1.85) -- (6.4,-1.85) node[midway, below, black, font=\footnotesize] {dZ};
\end{tikzpicture}
$$

Measuring disparity means solving the same correspondence problem as optical flow —
find the point in the right image that is the projection of the same scene point as a
given point in the left — and simple methods again compare pixel blocks by SSD, while
practice uses more sophisticated algorithms with extra constraints. Given disparity,
how does depth follow? Take both optical axes parallel, so the right camera is the
left camera displaced along the $x$-axis by the **baseline** $b$; treat that as a
translation $\mathbf{T}$ with $T_x = b/\delta t$, $T_y = T_z = 0$ acting for time
$\delta t$. The horizontal disparity is $H = v_x\,\delta t = b / Z$ and the vertical
disparity is zero. Knowing $b$, measure $H$ and recover $Z$.

Under normal viewing humans **fixate**: the two optical axes intersect at some scene
point $P_0$ at distance $Z$. A point $P$ that is $\delta Z$ farther projects to $P_L$
and $P_R$, and the angular displacement between them is the disparity $\delta\theta$.
Each eye sits a half-baseline $b/2$ off the axis of symmetry, so the ray to a point at
depth $Z$ makes an angle $\theta$ with that axis where $\tan\theta = (b/2)/Z$. The
farther point at $Z + \delta Z$ subtends the slightly smaller angle
$\theta - \delta\theta/2$, giving $\tan(\theta - \delta\theta/2) = (b/2)/(Z + \delta Z)$.
Work the difference of the two tangent equations line by line. For the small angles of
normal fixation $\tan\alpha \approx \alpha$, so

$$
\frac{\delta\theta}{2}
= \theta - \Bigl(\theta - \frac{\delta\theta}{2}\Bigr)
= \frac{b/2}{Z} - \frac{b/2}{Z + \delta Z} .
$$

Put the two fractions over a common denominator:

$$
\frac{b/2}{Z} - \frac{b/2}{Z + \delta Z}
= \frac{b}{2}\cdot\frac{(Z + \delta Z) - Z}{Z\,(Z + \delta Z)}
= \frac{b}{2}\cdot\frac{\delta Z}{Z^2 + Z\,\delta Z} .
$$

For a small depth increment, $\delta Z \ll Z$, the term $Z\,\delta Z$ is negligible
against $Z^2$, so the denominator collapses to $Z^2$ and

$$
\frac{\delta\theta}{2} \approx \frac{b\,\delta Z}{2 Z^2},
\qquad \text{giving} \qquad
\text{disparity} = \delta\theta = \frac{b\,\delta Z}{Z^2} .
$$

The $Z^2$ in the denominator determines the character of stereo vision: disparity
falls off as the _square_ of depth, so binocular depth sense is precise up close and
useless far away.

#### Worked example: how fast depth resolution decays

Turn the formula around. The eye can resolve angular differences down to some smallest
detectable disparity $\delta\theta_{\min}$, set by receptor spacing; below it two
points fuse. Solve for the corresponding depth step:

$$
\delta Z_{\min} = \frac{\delta\theta_{\min}\, Z^2}{b} .
$$

Use the human numbers: baseline $b \approx 6$ cm $= 60$ mm and a smallest detectable
disparity of about $5$ seconds of arc. Convert to radians —
$\delta\theta_{\min} = 5 \times \tfrac{\pi}{180 \times 3600} \approx 2.42 \times 10^{-5}$
rad — and evaluate at a few depths. Because $\delta Z_{\min}$ grows with $Z^2$, the
numbers climb fast:

| Depth $Z$ | $\delta Z_{\min}$ | Interpretation |
| --- | --- | --- |
| $30$ cm | $0.036$ mm | thread a needle |
| $1$ m | $0.40$ mm | line up a signature |
| $2$ m | $1.6$ mm | judge a handshake |
| $5$ m | $10$ mm | tell a step apart |
| $10$ m | $40$ mm | little help; a curb blurs into the road |

At arm's length the eye splits depths a needle's-eye apart; at ten meters it can
barely tell a stair from flat ground, so a person walking a dim corridor leans on other
cues. Doubling the distance quadruples $\delta Z_{\min}$: from $2$ m to $4$ m the
smallest resolvable depth step jumps from $1.6$ mm to $6.5$ mm. A stereo camera rig
buys back resolution the only way the formula allows — by widening the baseline $b$,
which is why survey and self-driving rigs mount their two cameras far apart.

### Multiple views, texture, shading, and contour

Optical flow and binocular disparity are two instances of a broader idea: exploit
**multiple views** to recover depth, from two cameras or from thousands. Three
subproblems recur — the **correspondence** problem (which features across images are
projections of the same 3-D point), the **relative orientation** problem (the
rotation and translation between camera frames), and the **depth estimation** problem
(the depths of points seen in at least two views). Robust matching plus stable
solvers for orientation and depth is one of the success stories of computer vision;
reconstructing a detailed 3-D model of a monument from a pile of tourist photos is
now routine.

Several single-image cues fill in when multiple views are unavailable, each relying
on a physical assumption:

| Cue | Assumption exploited | What it recovers |
| --- | --- | --- |
| Motion parallax | rigid scene, moving camera | relative depth from flow ratios |
| Binocular stereopsis | known baseline $b$ | metric depth from disparity |
| Texture gradient | the surface texture is uniform | surface slant and orientation |
| Shading | albedo known, normals vary smoothly | local surface shape |
| Contour | generic viewpoint, opaque objects | figure–ground, occlusion order |
| Familiar size | object's true size is known | absolute distance |

**Texture** was used to segment; it also estimates distance. A uniform scene texture
produces varying **texels** in the image for two reasons: distant texels shrink by a
factor $1/Z$, and texels viewed at a steeper angle foreshorten by $\cos\sigma$, where
$\sigma$ is the slant (the angle between the viewing axis and the surface normal
$\mathbf{n}$). Inverting the variation recovers surface orientation. **Shading**
inverts Lambert's law: from image brightness, recover geometry and reflectance. It is
hard — a dark patch could be a normal tilted from the light _or_ a low-albedo surface
— and interreflections make it harder, since two patches with the same normal can
differ in brightness because one faces a bright wall. The standard assumption is that
normals vary smoothly. **Contour** recovers 3-D structure from a line drawing through
generic constraints: at an **occluding contour** one side is figure (nearer) and the
other ground (farther), so contour cues solve the **figure–ground** problem;
**T-junctions** signal that a nearer opaque object interrupts a farther one; and a
**ground plane** anchors objects, since gravity keeps them resting on it rather than
floating. On the ground plane, an object of height $\delta Y$ resting at
$(X, -h_c, Z)$ (with the camera at height $h_c$) has its bottom project to
$(fX/Z,\, -fh_c/Z)$ and its top to $(fX/Z,\, f(\delta Y - h_c)/Z)$: nearer objects
(small $Z$) sit lower in the image, farther ones creep toward the horizon.

### Structure from motion and the alignment method

Shape from flow and from disparity are special cases of **structure from motion**:
track features across a moving camera's frames and jointly solve for the 3-D point
positions and the camera path. When the object is _familiar_, we can do more than
find distance — we can recover its **pose**, its position and orientation relative to
the viewer, which an industrial robot needs before it can grasp a part. For rigid
objects the **alignment method** solves this. Represent the object by $M$
distinguished 3-D points $m_1, \ldots, m_M$ (say the vertices of a polyhedron). An
unknown rotation $\mathbf{R}$, translation $\mathbf{t}$, and projection $\Pi$ carry
them to image points, so each model point relates to its image point by a single
transformation $Q$,

$$
p_i = \Pi(\mathbf{R}\, m_i + \mathbf{t}) = Q(m_i) ,
$$

the _same_ $Q$ for every point because the object is rigid. Three noncollinear model
points and their scaled-orthographic projections determine $Q$ up to a two-fold
reflection ambiguity, by a closed-form solution. Identify the correspondence for
three points and the pose falls out. Orientation splits into two senses — the
orientation of the object as a whole (a 3-D rotation of its frame relative to the
camera) and the local orientation of a surface at a point, its normal $\mathbf{n}$,
described by **slant** (angle between the $Z$-axis and $\mathbf{n}$) and **tilt**
(angle between the $X$-axis and $\mathbf{n}$'s projection). The object's **shape** is
the property invariant under rotations and translations, and shape together with
color and texture is the strongest cue for recognition.

## Object recognition from structural information

A box around a pedestrian is enough to avoid hitting them, but to tell what someone
is _doing_ we need to know where their arms, legs, torso, and head lie. Individual
body parts are hard to detect alone: a forearm can be two pixels wide, and its color
and texture vary widely. To address this, represent what is connected to what, so that
easy-to-find parts (the torso) point to where the hard-to-find parts should be.

A **deformable template** encodes which configurations are legal — the elbow bends,
but the head never joins the foot. Model the body as a tree of eleven rectangular
segments (upper and lower arms and legs, torso, face, hair), rooted at the torso,
where each segment's pose is independent of the rest given its parent's pose. These
"cardboard people" models let us find the best match with inference for a
[tree-structured Bayes net](/artificial-intelligence/uncertainty/bayesian-networks).

$$
% caption: A pictorial structure ("cardboard person") model. Rectangular body
% segments form a tree rooted at the torso; each edge scores the spatial relation
% between a segment and its parent, each node scores how well an image rectangle
% matches that segment. Dynamic programming finds the best whole-body match.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  seg/.style={draw, fill=blue!5, minimum width=8mm, minimum height=6mm}]
  \definecolor{acc}{HTML}{2348F2}
  \tikzset{seg/.append style={draw=acc}}
  % torso (root)
  \node[seg, minimum width=10mm, minimum height=16mm] (torso) at (0,0) {};
  % head + hair above
  \node[seg, minimum width=7mm, minimum height=7mm] (head) at (0,1.7) {};
  \node[black, font=\scriptsize, anchor=south] at (0,2.1) {head};
  % root label placed clear, below the whole figure
  \node[acc, font=\scriptsize, anchor=north] at (0,-2.6) {torso (root)};
  % upper arms
  \node[seg, minimum width=6mm, minimum height=12mm] (lua) at (-1.5,0.4) {};
  \node[seg, minimum width=6mm, minimum height=12mm] (rua) at (1.5,0.4) {};
  % lower arms
  \node[seg, minimum width=5mm, minimum height=11mm] (lla) at (-2.7,0.2) {};
  \node[seg, minimum width=5mm, minimum height=11mm] (rla) at (2.7,0.2) {};
  % upper legs
  \node[seg, minimum width=6mm, minimum height=12mm] (lul) at (-0.6,-1.8) {};
  \node[seg, minimum width=6mm, minimum height=12mm] (rul) at (0.6,-1.8) {};
  % tree edges
  \draw[acc, thick] (torso) -- (head);
  \draw[acc, thick] (torso) -- (lua); \draw[acc, thick] (lua) -- (lla);
  \draw[acc, thick] (torso) -- (rua); \draw[acc, thick] (rua) -- (rla);
  \draw[acc, thick] (torso) -- (lul);
  \draw[acc, thick] (torso) -- (rul);
\end{tikzpicture}
$$

Two things score a configuration. A function $\phi_i$ scores how well image rectangle
$m_i$ matches body segment $i$; a function $\psi_{i, \mathrm{pa}(i)}$ scores how well
the relation between a segment and its parent matches the expected geometry. Because
the dependencies form a tree, the cost of allocating rectangle $m_i$ to segment $i$
is

$$
\sum_{i \in \text{segments}} \phi_i(m_i)
\;+\; \sum_{i \in \text{segments}} \psi_{i, \mathrm{pa}(i)}\bigl(m_i,\, m_{\mathrm{pa}(i)}\bigr) ,
$$

and dynamic programming finds the best match, the tree structure making it tractable.
This is the **pictorial structure model**. In a single image the most useful feature
for scoring a segment is color (loose clothing folds disrupt texture), so we need an
**appearance model** — a description of what this person looks like. With one image we
bootstrap: start with a rough appearance model, estimate configuration, re-estimate
appearance, iterate.

Video makes this much easier and connects recognition to
[tracking over time](/artificial-intelligence/uncertainty/reasoning-over-time).
People accelerate fast, so frame $i$ barely constrains frame $i+1$ and plain
filtering struggles. But **appearance** changes slowly from frame to frame. So scan
the video for an easy, reliable configuration — a lateral walking pose — read off
which pixels belong to each body segment, build a discriminative appearance model of
each part, tie them into a pictorial structure model of _this_ individual, detect
that model in every frame, and link the detections across time into a track. This
tracks fast, complicated body configurations despite motion blur that defeats
frame-to-frame filtering.

## Using vision

A vision system that could analyze video and infer what people are doing would let
an agent design better public spaces, build less intrusive surveillance, commentate
sports, and drive interfaces that watch and react. Some pieces are well understood.
When people are small in a stable-background frame, **background subtraction** — flag
a pixel as foreground when its absolute difference from a stored background image is
large — finds them, and linking foreground blobs over time yields a track. Structured
behaviors with fixed vocabularies (ballet, gymnastics, tai chi) against a plain
background can be recognized by pooling HOG-style features into histogram buckets over
time as well as space. The open problem is linking body-and-object observations to the
goals and intentions of moving people; we lack a simple vocabulary of behavior, we
do not know which features expose what is happening, and the usual training/test
guarantees fail because rare but important events (someone mounting a bicycle) may be
absent from the data.

### Reconstruction, navigation, and manipulation

Multiple-view reconstruction is now highly developed. From point correspondences
across views one can recover camera parameters and 3-D point positions with high
accuracy, generalizing well beyond the orthographic two-view case. Applications
include **model-building** (turn a video into a textured 3-D mesh — the Statue of
Liberty rebuilt from photos found online), **matching moves** (recover the real
camera's motion so computer-graphics characters can be composited into footage), and
**path reconstruction** (a mobile robot recovers where it has been by reconstructing
the rigid world it moved through).

The oldest use of vision is controlling movement — grasping and manipulating objects,
and navigating while avoiding obstacles — present in the most primitive animal visual
systems. Consider a vision system for a car on a freeway. It must handle **lateral
control** (stay in the lane or change smoothly), **longitudinal control** (keep a safe
distance to the vehicle ahead), and **obstacle avoidance** (watch neighbors and be
ready to evade). For lateral control, edge detection finds the lane-marker segments,
smooth curves fit to them encode the car's lateral position and heading, and that,
with the car's dynamics, drives the steering controller. For longitudinal control,
binocular stereopsis or optical flow measures the distance to the car ahead;
vision-controlled cars can drive reliably at highway speeds.

The general problem of a robot navigating indoor and outdoor environments has been
studied too, and **localization** — placing the robot in its own map — now has good
solutions. A common design tracks feature points in 3-D from two forward-looking
stereo cameras (or one pair front and one back, for robustness against a featureless
patch) to reconstruct the robot's position relative to the environment. An inertial
measurement unit provides a backup: integrate sensed acceleration twice to track
position change, and fuse the visual and inertial estimates by
[Kalman filtering](/artificial-intelligence/uncertainty/reasoning-over-time). **Visual
odometry** drifts as errors accumulate, so the robot corrects its estimate against
landmarks whenever it revisits a mapped location, reaching accuracies of centimeters.

The driving example carries the lesson of the whole chapter: _for a specific task,
one need not recover everything an image could in principle yield_. The car does not
solve shape-from-texture on the roadside grass. A vision system should compute just
what the task needs, and no more.

## Deep vision

The pipeline this lesson built runs bottom-up through a fixed sequence: gradients give
edges, edges pooled into histograms give texture and HOG descriptors, descriptors feed
a learned classifier, and geometric cues lift the result into three dimensions. Every
stage between the pixels and the classifier was designed by hand. AIMA's chapter closes
just as a different answer arrived — leave the whole feature hierarchy to be learned
from data. The classical pipeline and the learned one compute the same kind of thing;
the difference is who writes the intermediate stages.

The dataset came first. Deng, Dong, Socher, Li, Li, and Fei-Fei introduced **ImageNet**
(Deng et al., CVPR 2009), a database eventually holding over fourteen million labeled
images across thousands of categories, and the associated ImageNet Large Scale Visual
Recognition Challenge gave the field a common benchmark. On that benchmark, Krizhevsky,
Sutskever, and Hinton entered a deep **convolutional neural network** — since called
**AlexNet** — in "ImageNet Classification with Deep Convolutional Neural Networks"
(NeurIPS 2012). It reported a top-5 error of about $15.3\%$, far below the roughly
$26\%$ of the best hand-engineered entries that year. The network learned its own
filters: the first convolutional layer settled on oriented edge and color-blob
detectors that look much like the Gaussian-derivative operators of edge detection, and
later layers composed those into texture, part, and object detectors — the same
$\text{edges} \to \text{texture} \to \text{parts} \to \text{objects}$ ladder, now
discovered rather than specified.

$$
% caption: The same feature ladder, hand-built versus learned. Top: the classical
% route fixes each stage (Gaussian-derivative edges, orientation histograms, HOG,
% then a trained SVM). Bottom: a convolutional network learns every stage end-to-end
% by backpropagating the classification error, so early filters resemble edge
% operators and later ones respond to parts and whole objects.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum width=17mm, minimum height=8mm, align=center, font=\scriptsize},
  lx/.style={draw=acc, text=acc, thick, minimum width=17mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- top row: hand-engineered ---
  \node[black, font=\scriptsize, anchor=east] at (-0.4,1.6) {hand-built:};
  \node[bx] (p1) at (0.7,1.6)  {pixels};
  \node[bx] (e1) at (3.0,1.6)  {edges\\(Gauss deriv)};
  \node[bx] (t1) at (5.5,1.6)  {texture\\histograms};
  \node[bx] (h1) at (7.9,1.6)  {HOG\\descriptor};
  \node[lx] (c1) at (10.3,1.6) {SVM\\classi\/f\/ier};
  \draw[->, black] (p1) -- (e1);
  \draw[->, black] (e1) -- (t1);
  \draw[->, black] (t1) -- (h1);
  \draw[->, black] (h1) -- (c1);
  % --- bottom row: learned ---
  \node[black, font=\scriptsize, anchor=east] at (-0.4,0) {learned:};
  \node[bx] (p2) at (0.7,0)  {pixels};
  \node[lx] (e2) at (3.0,0)  {conv 1\\(edge-like)};
  \node[lx] (t2) at (5.5,0)  {conv mid\\(texture)};
  \node[lx] (h2) at (7.9,0)  {conv deep\\(parts)};
  \node[lx] (c2) at (10.3,0) {dense\\classi\/f\/ier};
  \draw[->, acc, thick] (p2) -- (e2);
  \draw[->, acc, thick] (e2) -- (t2);
  \draw[->, acc, thick] (t2) -- (h2);
  \draw[->, acc, thick] (h2) -- (c2);
  % gradient feedback arrow under the learned row
  \draw[red, thick, ->] (c2.south) to[out=-90,in=-90] (e2.south);
  \node[red, font=\scriptsize, anchor=north] at (6.5,-1.15) {error backpropagates to train every stage};
\end{tikzpicture}
$$

Depth in these networks was limited by optimization: past a couple dozen layers,
training error would _rise_, not from overfitting but because the signal degraded
through the stack. He, Zhang, Ren, and Sun removed the ceiling with **residual
learning** in "Deep Residual Learning for Image Recognition" (CVPR 2016). A **ResNet**
layer computes $\mathbf{y} = \mathcal{F}(\mathbf{x}) + \mathbf{x}$, adding its input
back to its output through a skip connection, so a layer that has nothing useful to add
can settle on $\mathcal{F} \approx 0$ and pass its input straight through. With that
change the authors trained networks over a hundred layers deep and reported an ImageNet
top-5 error around $3.57\%$ for an ensemble — below the roughly $5\%$ often quoted for a
trained human on the same task.

$$
% caption: Reported ImageNet top-5 error, as stated by each system's authors. A
% pre-deep hand-engineered pipeline sat near 26 percent in 2011; AlexNet reported
% about 15.3 percent in 2012; ResNet reported about 3.57 percent (ensemble) in 2015.
% Bars show the reported figures, not a controlled re-run.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[black, ->] (0,0) -- (0,3.1) node[above, black, font=\scriptsize] {top-5 error};
  \draw[black, ->] (0,0) -- (7.2,0) node[right, black, font=\scriptsize] {system};
  % y gridlines at 10, 20 percent (scale: 0.1 unit per percent)
  \foreach \p in {10,20} {
    \draw[black, dashed] (0,\p*0.1) -- (7,\p*0.1);
    \node[black, font=\scriptsize, anchor=east] at (-0.08,\p*0.1) {\p};
  }
  % bars: pre-deep 26, AlexNet 15.3, ResNet 3.57
  \fill[black] (0.7,0) rectangle ++(1.1,2.6);
  \node[black, font=\scriptsize, anchor=south] at (1.25,2.62) {26.0};
  \node[black, font=\scriptsize, anchor=north, align=center] at (1.25,-0.08) {hand-built\\2011};
  \fill[acc!70] (3.0,0) rectangle ++(1.1,1.53);
  \node[black, font=\scriptsize, anchor=south] at (3.55,1.55) {15.3};
  \node[black, font=\scriptsize, anchor=north, align=center] at (3.55,-0.08) {AlexNet\\2012};
  \fill[red!60] (5.3,0) rectangle ++(1.1,0.357);
  \node[black, font=\scriptsize, anchor=south] at (5.85,0.38) {3.57};
  \node[black, font=\scriptsize, anchor=north, align=center] at (5.85,-0.08) {ResNet\\2015};
\end{tikzpicture}
$$

Recognition tells you _what_ is in an image; detection asks _where_, the sliding-window
problem this lesson framed around faces and pedestrians. Learned detectors replaced the
sweep-and-score-with-HOG pipeline. Girshick, Donahue, Darrell, and Malik's **R-CNN**
(CVPR 2014) ran a CNN classifier on a few thousand region proposals per image rather
than a dense window sweep. Ren, He, Girshick, and Sun folded proposal generation into
the network itself with **Faster R-CNN** (NeurIPS 2015), sharing convolutional features
between proposing and classifying. Redmon, Divvala, Girshick, and Farhadi's **YOLO**
(CVPR 2016) went further, predicting all boxes and classes in a single forward pass over
a grid, fast enough for video. Each is the non-maximum-suppression detector of this
chapter with its hand-built feature stage swapped for a learned one; the postprocessing
that merges overlapping detections carried straight over.

The convolution itself is not required. Dosovitskiy and colleagues showed with the
**Vision Transformer** (Dosovitskiy et al., ICLR 2021) that cutting an image into fixed
patches and feeding them to a transformer — the same architecture used for language —
matches or beats convolutional networks when trained on enough data, trading the
built-in locality of convolution for attention learned across the whole image. The
sibling lesson on
[convolutional networks](/deep-learning/architectures/convolutional-networks) develops
the mechanics of the learned feature hierarchy: how a convolution shares weights across
positions, how pooling builds the shift-tolerance a HOG histogram gave by hand, and how
the whole stack is fit by backpropagation.

Two caveats apply. The reported error figures come from each
system's own paper on the ImageNet benchmark and are not from a single controlled
re-run — different preprocessing, ensembling, and test protocols move them by points.
And the geometric half of vision did not vanish. Multiple-view reconstruction, the
stereo and structure-from-motion math above, still underlies 3-D scanning, augmented
reality, and robot mapping, now often paired with learned features for the
correspondence step. The learned era changed who designs the features; it did not
repeal projective geometry.

## The bridge to action

Perception is the inverse of graphics. Graphics takes a 3-D scene and _renders_ an
image, a well-understood forward computation; vision takes the image and must
_invert_ it into a scene an agent can act on — the harder direction, made tractable
only by the physical assumptions each cue smuggles in. That inversion is where
perception meets the rest of the agent. The image gradient becomes edges, edges and
texture become regions, regions and features become recognized objects, and the cues
of motion, stereo, texture, shading, and contour lift the flat pixel array into a
three-dimensional scene. Once the scene exists, tracking it over time is
[reasoning under uncertainty over time](/artificial-intelligence/uncertainty/reasoning-over-time),
choosing how to act on it is
[decision-making under uncertainty](/artificial-intelligence/uncertainty/making-decisions),
and the machinery that turns those choices into movement in the physical world is the
subject of [robotics](/artificial-intelligence/frontiers/robotics). Perception is the
first link in that chain: the point where the computer meets the physical world.