Vision and Perception

Perception gives an agent information about the world it inhabits by interpreting the response of sensors. A sensor measures some aspect of the environment in a form the agent program can use as input — a switch reporting one bit, or an eye reporting millions. Artificial agents share vision, hearing, and touch with humans, and add modalities the unaided human lacks: radar, infrared, GPS. This lesson covers one modality in depth, the richest one: vision.

A decision-theoretic agent in a partially observable world already carries a sensor model — a distribution $\mathbf{P}(E\mid S)$ over the evidence its sensors produce given a world state $S$. For vision that model factors into two parts. An object model describes the things that inhabit the visual world (people, buildings, cars) — perhaps a precise CAD mesh, perhaps a vague constraint like human eyes sit 5 to 7 cm apart. A rendering model describes the physical and statistical process that turns a scene into a stimulus. Rendering is ambiguous: a white object in dim light can match a black object in bright light; a small nearby object can match a large distant one. Without further evidence you cannot tell a toy Godzilla filling the frame from a real monster far away. Prior knowledge resolves some of it (Godzilla is not real, so the image must be a toy); an agent can also just choose to ignore ambiguity it need not resolve, since it is unlikely to crash into an object miles away.

The problem for a vision-capable agent is a question of relevance: a video camera can produce ten gigabytes a minute, and which aspects of that torrent should shape the agent's action choices, and which should be ignored? Vision, like all perception, serves the agent's goals; it is not an end in itself. Three broad approaches carve up the work. Feature extraction applies simple local computations directly to the sensor readings — the reflex path a fly uses to land on a wall. Recognition draws category distinctions among the objects encountered (is this Grandma's face?). Reconstruction builds a geometric model of the world from one image or many. The rest of the lesson runs through the physics that makes all three possible and then through each in turn.

Image formation

Imaging distorts appearance. A photograph down a straight railway suggests the rails converge and meet; a hand held at arm's length blocks out the moon, which is not smaller than the hand; tilt the hand and it seems to shrink in the image without changing size in the world. Modelling these effects is the precondition for both recognition and reconstruction, so we start with the geometry of how light becomes a picture.

The pinhole camera and perspective projection

Image sensors gather light scattered from objects in a scene and form a two-dimensional image. In the eye the image lands on the retina; in a camera it lands on an image plane — a grid of a few million photosensitive pixels, each a CMOS or CCD element that reports a weighted average of the light arriving at it. To get a focused image, all the photons from one spot in the scene must arrive at approximately one spot in the plane. The simplest device that achieves this for stationary objects is a pinhole camera: a small opening $O$ at the front of a box and an image plane at the back. Because every photon that reaches the plane must pass through the pinhole, if the hole is small enough then nearby scene points map to nearby image points, and the image is in focus.

Put the origin of a 3-D coordinate frame at the pinhole, with the $Z$-axis along the optical axis. A scene point $P$ has coordinates $(X,Y,Z)$ and projects to a point $P^{\prime }$ with coordinates $(x,y)$ on the image plane a distance $f$ (the focal length) behind the hole. Similar triangles give the projection equations

These define perspective projection. Two facts follow directly. The $Z$ in the denominator means the farther away an object is, the smaller its image — this is why a hand can cover the moon. And the minus signs mean the image is inverted, both left-right and up-down, relative to the scene.

Perspective explains why parallel lines appear to converge. Take a line in the scene through $(X_0,Y_0,Z_0)$ with direction $(U,V,W)$, i.e. the points $(X_0+\lambda U,Y_0+\lambda V,Z_0+\lambda W)$ as $\lambda$ ranges over the reals. Its projection is

As $\lambda \to \pm \infty$ this tends to $p_{\infty }=(fU/W,fV/W)$, provided $W\ne 0$ — a limit that depends only on the direction $(U,V,W)$, not on the starting point $(X_0,Y_0,Z_0)$. So all lines sharing a direction converge to the same vanishing point $p_{\infty }$. Railway tracks meet on the horizon because every parallel family collapses to a single point.

Take the limit apart to see why the starting point drops out. Divide numerator and denominator of each image coordinate by $\lambda$:

because $X_0/\lambda \to 0$ and $Z_0/\lambda \to 0$. The tail of the line — the part far from its anchor point — dominates, and the tail of every line with direction $(U,V,W)$ heads to the same image point. A family of rails, all pointing the same way, therefore converges to one dot. Two families pointing in two directions give two vanishing points; the line joining them, the locus of all directions parallel to the ground, is the horizon.

Worked example: projecting one point

Carry a single scene point through the equations with real numbers. Put a lamp post tip at $P=(X,Y,Z)=(0.5\text{ m},0.3\text{ m},4\text{ m})$ — half a meter right of the optical axis, $0.3$ m up, four meters ahead — and use a $50$-millimeter lens, $f=0.05$ m. The projection equations give

The signs flip both coordinates: a point up and to the right lands down and to the left, the inversion the pinhole forces. To turn millimeters on the sensor into pixel addresses, divide by the pixel pitch, the center-to-center spacing of the photosites — take five micrometers, $0.005$ mm. Then $x=-6.25/0.005=-1250$ and $y=-3.75/0.005=-750$, so relative to the image center the tip lands $1250$ pixels left and $750$ pixels down.

Now halve the depth: walk the camera to $Z=2$ m. Both image coordinates double, $x=-12.5$ mm $=-2500$ px and $y=-7.5$ mm $=-1500$ px. The whole image of the post grows by the same factor because $x$ and $y$ scale as $1/Z$: approaching an object makes its image grow hyperbolically.

Lenses and focus

The pinhole forces a tradeoff. A small hole keeps the image sharp but lets in few photons, so the image is dark; worse, over a long exposure any moving object smears across the plane as motion blur. Widen the hole for more light and a single scene patch now spreads over a patch of image — blur again, this time spatial. Lens systems in vertebrate eyes and modern cameras resolve the dilemma: a large opening is covered by a lens that steers the light leaving a scene point, from a whole range of directions, back to a single point in the image plane.

A lens has a limited depth of field: it can focus only points lying within some range of depths, centred on a focal plane. Objects outside that range blur. To move the focal plane, the camera slides its lens back and forth; the eye instead reshapes its lens with specialized muscles.

When perspective effects are mild, the full projection can be simplified. Spots on a distant leopard all sit at nearly the same depth $Z_0\pm \Delta Z$ with $\Delta Z\ll Z_0$, so the scaling factor $f/Z$ is nearly a constant $s=f/Z_0$, and the projection collapses to scaled orthographic projection, $x=sX$ and $y=sY$. It is a good model for a shallow, distant patch — the face of a far building — and a poor one when the scene has serious internal depth.

Light and shading

The brightness of an image pixel is a function of the brightness of the scene patch that projects to it. Assuming a linear sensor (real ones saturate at the extremes but are linear in the middle), image brightness is a strong, if ambiguous, cue to an object's shape, and from shape to identity. Three causes of varying brightness are worth separating.

The first is the overall intensity of the light. Even though a white object in shadow may reflect less than a black object in sunlight, people perceive the white one as white — the visual system discounts illumination. The second is that different surface points reflect more or less of the incident light, which reads as texture or markings. The third is shading: patches facing the light are brighter than patches tilted away, an effect that comes from the object's geometry.

Most surfaces reflect by diffuse reflection, scattering light evenly in all outgoing directions, so a diffuse surface looks equally bright from any viewpoint — cloth, matte paint, rough wood, vegetation. A perfect mirror is the opposite, specular reflection, where what you see depends on viewing angle. Brushed metal, plastic, and wet floors show small bright specularities where specular reflection dominates. For most purposes it suffices to model every surface as diffuse with a few specularities.

The dominant outdoor light source is the sun, whose rays are effectively parallel: a distant point light source. The energy a surface patch collects then depends on the angle $\theta$ between the illumination direction and the surface normal.

A diffuse patch reflects a fraction of what it collects, its diffuse albedo$\rho$ — about $0.90$ for snow or white paper, about $0.05$ for charcoal or black velvet. Lambert's cosine law states that the brightness of a diffuse patch is

where $I_0$ is the source intensity and $\theta$ the angle between the light direction and the surface normal. Bright pixels come from patches facing the light; dark pixels from patches seeing it only tangentially — so shading carries shape, a cue we exploit later. A patch the light never reaches is in shadow, seldom uniformly black because scattered light (the sky outdoors, other surfaces indoors) still reaches it. These interreflections are often folded into a constant ambient illumination term added to the predicted intensity.

Worked example: albedo, angle, and the shadow crossover

Fix the source intensity at $I_0=1$ (a normalized unit) and tabulate $I=\rho I_0\cos \theta$ for the two extreme albedos as the surface tilts away from the light.

Head-on the snow is $18$ times brighter than the charcoal ($0.900$ versus $0.050$), exactly the albedo ratio $0.90/0.05$. But brightness is the product of albedo and geometry, and the two can trade off. Ask when snow tilted steeply matches charcoal facing the sun: set $0.90\cos \theta =0.05$, so $\cos \theta =0.0556$ and $\theta \approx 86.8^{\circ }$. A snowbank turned almost edge-on to the sun sends the camera the same brightness as a lump of charcoal pointed straight at it. Measured pixel brightness alone therefore cannot separate a white surface in near-shadow from a black one in full sun. The visual system discounts illumination to recover albedo, and shape-from-shading algorithms make the opposite bet: hold albedo fixed and read the $\cos \theta$ variation as surface tilt.

Color

Light arriving at the eye carries different energy at different wavelengths, a spectral energy density. Human eyes respond across roughly the 380–750 nm band with three types of color receptor, peaking near 420 nm (blue), 540 nm (green), and 570 nm (red) — the eye captures only a coarse three-number summary of the full spectrum, enough to tell a ripe fruit from an unripe one. The principle of trichromacy states that for any spectral energy density, however complicated, one can construct a mixture of just three primaries (usually red, green, blue) that a human cannot distinguish from it. This is why displays get by with R/G/B elements, and why vision algorithms model each surface with three albedos and each source with three intensities, applying Lambert's law to each channel.

The same surface produces different image colors under differently colored light, yet human observers largely discount this and estimate the surface's color under white light — color constancy. Reasonable color-constancy algorithms now exist; a simple version is the auto white balance in a camera.

Early image-processing operations

Light reflecting off scene surfaces yields an image of, say, five million 3-byte pixels, corrupted by sensor noise and highly redundant. The first operations in the vision pipeline are early or low-level: they act locally (using only a few nearby pixels) and without knowledge of what objects might be present. That locality makes them good candidates for parallel hardware — a GPU, or an eye. We cover three local operations — edge detection, texture, and optical flow — and one mid-level operation, segmentation.

Edge detection

Edges are lines or curves in the image plane across which image brightness changes sharply. Detecting them abstracts the messy multi-megabyte array toward a compact representation, because edge contours in the image tend to correspond to important contours in the scene. Not all edges have the same physical cause: they arise at depth discontinuities (an object boundary against a farther background), surface-orientation discontinuities (a crease), reflectance discontinuities (a painted marking), and illumination discontinuities (a shadow's edge). Edge detection does not distinguish these; later processing must.

How do we find edges? An edge is a location where brightness changes fast, so a naive plan is to differentiate the image and flag places where the magnitude of the derivative $I^{\prime }(x)$ is large. Consider the brightness profile $I(x)$ along a one-dimensional cross-section cutting across an edge — say the boundary between a desk and the wall behind it. It shows a step, but a noisy one, and its raw derivative peaks at the true edge yet also spikes at spurious noise locations.

To address this, smooth before differentiating. Sensor noise is well modelled as an independent Gaussian perturbation at each pixel; averaging a pixel with its neighbors cancels it, and the best weighting keeps the nearest pixels heaviest. This weighting is the Gaussian filter, using the Gaussian of standard deviation $\sigma$ and mean zero,

Smoothing replaces $I(x_0,y_0)$ with a weighted sum of nearby pixels — a convolution of the image with the Gaussian, $I\ast N_{\sigma }$. A $\sigma$ of one pixel erases a little noise; two pixels erases more at the cost of detail. There is a useful identity: for any $f$ and $g$, $(f\ast g{)}^{\prime }=f\ast g^{\prime }$. So instead of smoothing and then differentiating we can convolve the image once with the derivative of the Gaussian, $N_{\sigma }^{\prime }$, and mark as edges the peaks above a threshold. The bottom panel above is exactly $(I\ast N_{\sigma }{)}^{\prime }=I\ast N_{\sigma }^{\prime }$; the spurious peak at $x=75$ is gone.

Worked example: a 1-D edge through two kernels

For example, run a short signal through both kernels. Take nine intensity samples with a step near the middle and one bad pixel — a noise blip — at index $3$:

The true edge is the jump from about $11$ to about $40$ between indices $5$ and $6$; the $20$ at index $3$ is noise. A raw difference, the two-tap kernel $[-1,+1]$ that gives $d[i]=I[i]-I[i-1]$, produces

The real edge shows up as $29$ at index $6$ — but the lone bad pixel throws off a $+11$ then a $-11$ (indices $3$ and $4$), a spurious pair a third the size of the true peak. Threshold at anything below $11$ and you flag the noise as an edge; threshold above it and you keep only the strongest edges. Now use a three-tap derivative-of-Gaussian kernel $g=(-0.5,0,+0.5)$, which computes $(I\ast g)[i]=\frac{1}{2}(I[i+1]-I[i-1])$ — a central difference over a two-sample span, so it lightly smooths as it differentiates:

The true edge is now a clean pair of $15.5$ at indices $5$ and $6$, while the blip collapses to a $\pm 4$ ripple — the wider stencil averaged the outlier against its neighbors before differencing. The edge-to-noise gap widened from $29:11$ (a ratio of $2.6$) to $15.5:4.5$ (a ratio of $3.4$), so a single threshold now separates edge from noise cleanly. This is $I\ast N_{\sigma }^{\prime }$ at a tiny $\sigma$ acting on one row; the two-dimensional detector does the same thing with the partial derivatives of a $2$-D Gaussian.

In two dimensions an edge can run at any angle. Treating brightness as a scalar function of $x$ and $y$, its gradient is a vector

and, as before, we compute $\nabla (I\ast N_{\sigma })$ in one step by convolving with the partial derivatives of a Gaussian. Edges are where the gradient magnitude$\Vert \nabla I\Vert$ is large. The gradient's direction defines the edge orientation,

giving a $\theta =\theta (x,y)$ at every pixel. A pixel is an edge point when its gradient magnitude is a local maximum along the gradient direction (so the edge sits exactly on the crest, not its flank) and exceeds a threshold. A final linking stage joins neighboring edge pixels with consistent orientations into continuous edge curves.

Texture

In computational vision texture is a spatially repeating pattern that can be sensed visually — windows on a building, stitches on a sweater, spots on a leopard, pebbles on a beach. Sometimes the repetition is nearly periodic; often it is only statistical. Where brightness is a property of a single pixel, texture only makes sense for a multi-pixel patch. A natural summary computes the edge orientation at each pixel of a patch and forms a histogram of orientations: bricks give two peaks (vertical and horizontal), leopard spots give a broad spread.

Orientation histograms are largely invariant to changes in illumination, which makes texture a stable clue for recognition where brightness edges are not: the same markings survive a change in lighting. Texture also rescues segmentation on textured objects, where the important boundaries can be lost among the texture elements — you miss the tiger for the stripes. A patch on the tiger and a patch on the grass have very different orientation histograms, so comparing texture properties recovers the boundary between them.

Optical flow

Give the camera a video instead of a single frame. When an object moves, or the camera moves relative to an object, the resulting apparent motion in the image is optical flow — the direction and speed of image features, measured in pixels per second. Flow encodes scene structure: from a moving train, distant scenery drifts slowly and near scenery streaks by, so the rate of apparent motion carries distance. Flow also exposes actions; the fastest-flowing regions of a tennis video are the racket and the front leg.

The flow field at a point $(x,y)$ has components $v_x(x,y)$ and $v_y(x,y)$. To measure it we match corresponding points between one frame and the next. A simple method exploits that image patches around corresponding points have similar intensity: take a block centred on $(x_0,y_0)$ at time $t_0$ and compare it to blocks centred on $(x_0+D_x,y_0+D_y)$ at $t_0+D_t$, using the sum of squared differences

with $(x,y)$ ranging over the block. The displacement $(D_x,D_y)$ that minimizes SSD gives the flow $(v_x,v_y)=(D_x/D_t,D_y/D_t)$. This needs texture: on a uniform white wall the SSD is nearly equal for every candidate, so the match is a blind guess. The best flow algorithms add further constraints where the scene is only partly textured.

Segmentation of images

Segmentation breaks an image into regions of similar pixels. Within one object, or one part, attributes like brightness, color, and texture vary little; across an inter-object boundary one or more of them jumps. Two dual approaches exist: detect the boundaries of regions, or detect the regions themselves.

For boundaries, note a boundary through pixel $(x,y)$ has an orientation $\theta$, so detecting boundaries becomes classification: from features of a local neighborhood, predict the probability $P_b(x,y,\theta )$ that a boundary of orientation $\theta$ runs through the pixel. Center a disk on $(x,y)$, split it into two half-disks by a diameter at angle $\theta$, and if a boundary really lies there the halves should differ in their histograms of brightness, color, and texture. A classifier trained on natural images that humans hand-marked can predict $P_b$ far better than simple edge detection — but thresholding $P_b$ need not yield closed curves, and it uses only local context.

The region approach instead clusters pixels by brightness, color, and texture. Treat each pixel as a graph node, put an edge between pixels weighted $W_{ij}$ by how similar they are, and partition the graph to minimize a normalized cut: cut few of the strong edges, keep similar pixels grouped. Purely local, low-level segmentation cannot deliver the correct object boundaries by itself; reliably finding them needs high-level knowledge of the likely objects. A common compromise is to over-segment into hundreds of small homogeneous superpixels, then hand off to knowledge-based algorithms that reason over superpixels rather than millions of raw pixels. Exploiting object knowledge is the subject of recognition, next.

Object recognition by appearance

Appearance is shorthand for what an object tends to look like. Some categories vary little in appearance (a baseball looks about the same under most circumstances); for those we can compute a set of features describing images likely to contain the object and test them with a classifier. Other categories — houses, ballet dancers — vary greatly, and a useful abstraction treats such objects as collections of local patterns that move around with respect to one another; we then find the object by looking at local histograms of detector responses that reveal whether a part is present while suppressing exactly where.

Sliding-window detection

The general method is to test each image window with a learned classifier. It works especially well for frontal faces: at low resolution and under reasonable lighting all such faces look similar — round, bright compared to the sunken eye sockets, with a dark slash for the mouth. Consider first faces where the nose is vertical. Sweep a round window of fixed size over the image, compute features for each placement, and present them to a classifier — the sliding window. To find faces at different sizes, repeat the sweep over larger and smaller scaled copies of the image; then postprocess the responses across scales and locations.

Postprocessing matters because the chosen window size rarely matches a face exactly, so several overlapping windows each report a match. A classifier that reports a strength of response (logistic regression or a support vector machine) lets us combine nearby partial matches into one high-quality detection — non-maximum suppression. To handle rotated faces, add two steps: train a regressor to estimate the best orientation of any face in a window, reorient the window, then test for a vertical face. Features must be robust to shadows and illumination, so one strategy builds them from gradient orientations, another estimates and corrects the illumination per window. Training data is cheap: marked-up face sets exist, and slightly perturbing each example window (in orientation, center, or scale) manufactures more. Frontal face detectors built this way now run in inexpensive cameras.

Features: histograms of gradient orientation

Many objects show more complex patterns than faces because several effects move features around: foreshortening (a slanted pattern is distorted), aspect (an object looks different from different directions — a doughnut is an oval from the side, an annulus from above), occlusion (parts hidden from some viewpoints, including self-occlusion), and deformation (internal degrees of freedom, as when a person moves their limbs). Still, the search across location and scale works, because some structure is preserved: a car image shows some arrangement of headlights, wheels, windows. This suggests modelling objects as collections of pattern elements — parts that may shift a little but appear roughly in place.

The obvious representation, a histogram of which pattern elements appear, throws away too much: the French, UK, and Netherlands flags have nearly identical color histograms though they arrange the same colors very differently. The representation must keep some spatial detail (headlights tend to be at the front, wheels at the bottom) while still summarizing.

Pedestrian detection is the canonical application: car accidents kill about 1.2 million people a year, roughly two thirds of them pedestrians, so a car that detects and avoids pedestrians could save many lives. At low resolution a walking pedestrian has a characteristic appearance — a lollipop (wide torso, legs together) or a scissor (legs mid-stride). Contrast against the background is often weak, so orientations beat edges; and because limbs swing, a histogram is used to suppress spatial detail. Break the window into overlapping cells and build an orientation histogram in each: the feature reports whether the head-and-shoulders curve sits at the top of the window without changing when the head shifts slightly.

One refinement remains. Because orientation features ignore brightness, the distinctive boundary curves of a pedestrian would otherwise count the same as fine clothing texture and drown in noise. Recover contrast by weighting each orientation vote by how strong its gradient is relative to others in the cell. Writing $\Vert \nabla I_{\mathbf{x}}\Vert$ for the gradient magnitude at point $\mathbf{x}$ and $\mathcal{C}$ for the cell whose histogram we compute, a natural weight is

Gradients large relative to their neighbors get more weight. The resulting feature is the HOG feature (Histogram Of Gradient orientations). With it, a pedestrian detector is otherwise just a face detector: sweep a window, compute HOG, classify, apply non-maximum suppression. Similar constructions detect a wide variety of objects; an earlier relative, the SIFT feature (Scale-Invariant Feature Transform), matches distinctive keypoints between a model image and a test scene.

Modern object recognition has largely replaced these hand-built features. A convolutional neural network learns the whole feature hierarchy end-to-end from data, discovering edge, texture, part, and object detectors that a human once had to engineer — the same sliding sweep and score, but with $\varphi$ trained rather than designed. The appearance pipeline above is the classical form of a computation that CNNs now perform implicitly, and it is worth understanding as the scaffold the learned version replaced.

So far every operation has run forward, from pixels toward a label — edges, texture, features, a category. But knowing that a patch of image is a face or a car does not tell an agent where that object sits in space, and an agent that must grasp or avoid it needs the geometry, not just the name. That is the inverse problem: rebuild the three-dimensional scene from its 2-D projection. This continues in Vision: Reconstructing the 3D World.