Vision: Reconstructing the 3D World

This builds on 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 $\tilde{\mathbf{X}}=(X,Y,Z,1{)}^{\top }$ and an image point is $\tilde{\mathbf{x}}=(u,v,1{)}^{\top }$ up to scale — perspective projection becomes a single linear map,

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:

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.

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.

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 $\Vert x_1-{\Pi }_1(P){\Vert }^2+\Vert x_2-{\Pi }_2(P){\Vert }^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

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^{\prime }=x-T_x/T_z$ and $y^{\prime }=y-T_y/T_z$. Then $x{T}_z=(x^{\prime }+T_x/T_z)T_z=x^{\prime }{T}_z+T_x$, so the numerator $-T_x+x{T}_z$ becomes just $x^{\prime }{T}_z$, and the flow takes a clean radial form,

The flow at each point now aims straight along the ray from the focus of expansion, with a length proportional to the distance $r^{\prime }=\sqrt{x^{\prime 2}+y^{\prime 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.

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.

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

Put the two fractions over a common denominator:

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

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:

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 \frac{\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:

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:

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,-f{h}_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,\dots ,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$,

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.

Two things score a configuration. A function ${\varphi }_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

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. 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. 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.

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.

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 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, choosing how to act on it is decision-making under uncertainty, and the machinery that turns those choices into movement in the physical world is the subject of robotics. Perception is the first link in that chain: the point where the computer meets the physical world.