--- title: Vision and Perception module: Frontiers moduleNumber: 6 lessonNumber: 1 order: 601 summary: > Perception connects an agent to the physical world. We follow one modality — vision — from the physics of image formation (the pinhole camera, perspective projection, lenses, shading, color) through the early operations that turn a pixel array into edges, texture, and motion, and into recognition by appearance. The recurring problem is inversion: a camera collapses a 3-D world onto a 2-D grid, and an agent that wants to act must build the scene back up. Rebuilding the scene is the subject of the companion lesson. topics: [Frontiers] sources: - book: AIMA ref: "Ch. 24 — Perception; §24.1 Image Formation, §24.2 Early Image-Processing Operations" - book: AIMA ref: "§24.3 Object Recognition by Appearance" --- **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](/artificial-intelligence/uncertainty/making-decisions) 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. $$ % caption: The pinhole camera. A scene point $P=(X,Y,Z)$ projects along the ray % through the pinhole $O$ to the image point $P'=(x,y)$ a distance $f$ behind it; % the ray crossing at $O$ inverts the image left-right and up-down. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % optical axis \draw[black, dashed] (-2.6,0) -- (7.4,0) node[right, black, font=\footnotesize] {Z axis}; % image plane (behind pinhole, at left) \draw[black, thick] (-2.2,-1.6) -- (-2.2,1.6); \node[black, font=\scriptsize, anchor=south] at (-2.2,1.6) {image plane}; % pinhole \fill[acc] (0,0) circle (2pt); \node[acc, anchor=south east, font=\footnotesize] at (0,0.05) {O (pinhole)}; % scene point P (upper right) \fill[red] (6.2,1.15) circle (2.4pt); \node[red, anchor=west, font=\footnotesize] at (6.3,1.15) {P = (X, Y, Z)}; % ray from P through O to image \draw[red, thick, ->] (6.2,1.15) -- (0,0); \draw[red, thick, ->] (0,0) -- (-2.2,-0.408); \fill[acc] (-2.2,-0.408) circle (2pt); \node[acc, anchor=east, font=\footnotesize] at (-2.28,-0.408) {P' = (x, y)}; % focal length bracket \draw[black, <->] (-2.2,-1.85) -- (0,-1.85) node[midway, below, black, font=\footnotesize] {f}; \end{tikzpicture} $$ 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'$ with coordinates $(x, y)$ on the image plane a distance $f$ (the focal length) behind the hole. Similar triangles give the projection equations $$ \frac{-x}{f} = \frac{X}{Z}, \qquad \frac{-y}{f} = \frac{Y}{Z} \qquad \Longrightarrow \qquad x = \frac{-fX}{Z}, \qquad y = \frac{-fY}{Z} . $$ 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 $$ \parens{\, f\,\frac{X_0 + \lambda U}{Z_0 + \lambda W},\;\; f\,\frac{Y_0 + \lambda V}{Z_0 + \lambda W} \,} . $$ As $\lambda \to \pm\infty$ this tends to $p_\infty = (fU/W,\, fV/W)$, provided $W \neq 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$: $$ f\,\frac{X_0 + \lambda U}{Z_0 + \lambda W} = f\,\frac{X_0/\lambda + U}{Z_0/\lambda + W} \;\xrightarrow[\lambda \to \pm\infty]{}\; f\,\frac{U}{W} , $$ 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 $$ x = \frac{-fX}{Z} = \frac{-(0.05)(0.5)}{4} = -6.25\text{ mm}, \qquad y = \frac{-fY}{Z} = \frac{-(0.05)(0.3)}{4} = -3.75\text{ mm}. $$ 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. $$ % caption: The worked projection. A scene point $P=(0.5,0.3,4)$ m through a % $50$-mm lens lands at $(-6.25, -3.75)$ mm on the sensor (about $(-1250,-750)$ % pixels at a $5$-micrometer pitch); halving $Z$ to $2$ m doubles the image % coordinates to $(-12.5,-7.5)$ mm. The point moves along its ray, image size % scales as $1/Z$. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % optical axis \draw[black, dashed] (-2.6,0) -- (7.6,0) node[right, black, font=\footnotesize] {Z axis}; % sensor plane \draw[black, thick] (-2.2,-1.7) -- (-2.2,1.7); \node[black, font=\scriptsize, anchor=south] at (-2.2,1.7) {sensor}; % pinhole / lens center \fill[acc] (0,0) circle (2pt); \node[acc, anchor=south, font=\scriptsize] at (0,0.12) {O}; % far point P at Z=4 (up-right) \fill[red] (6.6,1.2) circle (2.2pt); \node[red, anchor=west, font=\scriptsize] at (6.7,1.2) {P at Z=4 m}; % near point at Z=2 (same ray, closer, higher) \fill[red] (3.3,0.6) circle (2.2pt); \node[red, anchor=south, font=\scriptsize] at (3.3,0.72) {Z=2 m}; % ray from far P through O \draw[red, thick] (6.6,1.2) -- (0,0); % projected far point (small) \draw[red, thick, ->] (0,0) -- (-2.2,-0.40); \fill[acc] (-2.2,-0.40) circle (1.8pt); \node[acc, anchor=east, font=\scriptsize] at (-2.28,-0.40) {-6.25 mm}; % projected near point (twice as far from axis) \draw[red, thick, dashed, ->] (0,0) -- (-2.2,-0.80); \fill[acc] (-2.2,-0.80) circle (1.8pt); \node[acc, anchor=east, font=\scriptsize] at (-2.28,-0.86) {-12.5 mm}; % focal length bracket \draw[black, <->] (-2.2,-1.95) -- (0,-1.95) node[midway, below, black, font=\footnotesize] {f = 50 mm}; \end{tikzpicture} $$ ### 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. $$ % caption: A lens collects light leaving one scene point over a range of % directions and focuses it to a single image point. Only points within the depth % of field, around the focal plane, are in focus; the eye refocuses by reshaping % the lens, a camera by moving it. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % image plane \draw[black, thick] (-3.4,-1.5) -- (-3.4,1.5); \node[black, font=\scriptsize, anchor=south] at (-3.4,1.5) {image plane}; % lens (an ellipse) \draw[acc, thick] (0,0) ellipse (0.28 and 1.15); \node[acc, font=\footnotesize, anchor=north] at (0,-1.2) {lens}; % scene point on focal plane \fill[red] (3.6,0) circle (2.4pt); \node[red, anchor=west, font=\footnotesize] at (3.7,0) {scene point}; % rays diverging from point to lens, converging to image point \foreach \y in {-1.0,-0.5,0,0.5,1.0} { \draw[red] (3.6,0) -- (0,\y); \draw[red] (0,\y) -- (-3.4,0); } \fill[acc] (-3.4,0) circle (2pt); % focal plane marker \draw[black, dashed] (3.6,-1.45) -- (3.6,1.45); \node[black, font=\scriptsize, anchor=south] at (3.6,1.45) {focal plane}; % depth of field band \draw[black, <->] (2.7,-1.75) -- (4.5,-1.75) node[midway, below, black, font=\scriptsize] {depth of f\/ield}; \end{tikzpicture} $$ 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. $$ % caption: Two patches under a distant point source. Patch A is tilted away % (angle to the normal near 90 degrees) and cuts few rays per unit area, so it is % dark; patch B faces the source (angle near 0) and collects more, so it is bright. % Lambert's cosine law: brightness is proportional to the cosine of that angle. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % parallel light rays coming down-right \foreach \x in {-0.5,0.3,1.1,1.9,2.7,3.5,4.3,5.1} { \draw[black, ->] (\x,2.6) -- ++(-0.9,-1.4); } % patch A: tilted steeply (near vertical), dark \draw[red, very thick] (0.0,0.0) -- (0.55,1.4); \node[red, font=\footnotesize, anchor=north] at (0.3,-0.05) {A (dark)}; % normal of A (points up-left, nearly across the rays) \draw[acc, thick, ->] (0.28,0.7) -- ++(-0.75,0.4); \node[acc, font=\scriptsize, anchor=east] at (-0.5,1.1) {normal}; % patch B: nearly horizontal, facing source, bright \draw[red, very thick] (3.9,0.0) -- (5.3,0.35); \node[red, font=\footnotesize, anchor=north] at (4.6,-0.02) {B (light-facing)}; % normal of B points up \draw[acc, thick, ->] (4.6,0.18) -- ++(0.35,1.0); \end{tikzpicture} $$ 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 $$ I = \rho\, I_0 \cos\theta , $$ 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. | $\theta$ | $\cos\theta$ | snow, $\rho = 0.90$ | charcoal, $\rho = 0.05$ | | --- | --- | --- | --- | | $0^\circ$ | $1.000$ | $0.900$ | $0.050$ | | $30^\circ$ | $0.866$ | $0.779$ | $0.043$ | | $60^\circ$ | $0.500$ | $0.450$ | $0.025$ | | $80^\circ$ | $0.174$ | $0.156$ | $0.009$ | 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. $$ % caption: The four kinds of scene discontinuity that produce edges: (1) depth, % where an object boundary sits in front of a farther surface; (2) surface % orientation, a crease; (3) reflectance, a painted marking; (4) illumination, % the boundary of a cast shadow. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % a box (cube-ish) casting a shadow \draw[black, thick] (0,0) rectangle (2.4,2.0); % front face \draw[black, thick] (0,2.0) -- (0.7,2.6) -- (3.1,2.6) -- (2.4,2.0); % top \draw[black, thick] (2.4,0) -- (3.1,0.6) -- (3.1,2.6); % right % reflectance marking on the front face \draw[red, very thick] (0.5,0.5) -- (0.5,1.5); % shadow on the ground \draw[black] (0,0) -- (-1.4,-0.7) -- (1.0,-0.7) -- (2.4,0); % labels with leader-free callouts placed outside \node[acc, font=\footnotesize, anchor=east] at (-0.15,1.2) {1: depth}; \node[acc, font=\footnotesize, anchor=south] at (1.9,2.62) {2: orientation}; \node[red, font=\footnotesize, anchor=west] at (0.62,1.0) {3: ref\/lectance}; \node[acc, font=\footnotesize, anchor=north] at (-0.4,-0.72) {4: illumination}; \end{tikzpicture} $$ 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'(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. $$ % caption: An edge profile. Top: intensity $I(x)$ across an edge near $x=50$, a % noisy step. Middle: the raw derivative $I'(x)$ peaks at the edge but also at % noise, e.g. near $x=75$. Bottom: convolving with the derivative-of-Gaussian % $N'_\sigma$ smooths first, so only the true peak survives. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % ---- top: noisy step I(x) ---- \begin{scope}[yshift=4.6cm] \draw[black, ->] (0,-0.2) -- (0,1.3); \draw[black, ->] (0,0) -- (6.4,0) node[right, black, font=\scriptsize] {x}; \node[black, font=\scriptsize, anchor=east] at (-0.05,1.15) {I(x)}; \draw[acc, thick] (0,0.15) -- (0.5,0.05) -- (1.0,0.2) -- (1.5,0.1) -- (2.0,0.22) -- (2.5,0.12) -- (3.0,0.75) -- (3.5,0.95) -- (4.0,0.88) -- (4.5,1.0) -- (5.0,0.92) -- (5.5,0.98) -- (6.0,0.9); \draw[black, dashed] (3.0,-0.15) -- (3.0,1.2); \node[black, font=\scriptsize, anchor=north] at (3.0,-0.15) {50}; \end{scope} % ---- middle: raw derivative I'(x) ---- \begin{scope}[yshift=2.3cm] \draw[black, ->] (0,-0.55) -- (0,0.9); \draw[black, ->] (0,0) -- (6.4,0) node[right, black, font=\scriptsize] {x}; \node[black, font=\scriptsize, anchor=east] at (-0.05,0.8) {I'(x)}; \draw[red, thick] (0,0.05) -- (0.4,-0.2) -- (0.8,0.25) -- (1.2,-0.15) -- (1.6,0.1) -- (2.0,-0.1) -- (2.5,0.05) -- (3.0,0.7) -- (3.3,0.1) -- (3.8,-0.15) -- (4.2,0.4) -- (4.6,-0.1) -- (5.0,0.1) -- (5.5,-0.05) -- (6.0,0.0); \node[red, font=\scriptsize, anchor=south] at (4.35,0.4) {noise}; \end{scope} % ---- bottom: smoothed derivative (I * N'_sigma) ---- \begin{scope}[yshift=0cm] \draw[black, ->] (0,-0.55) -- (0,0.9); \draw[black, ->] (0,0) -- (6.4,0) node[right, black, font=\scriptsize] {x}; \node[black, font=\scriptsize, anchor=east] at (-0.05,0.8) {smoothed}; \draw[acc, thick] (0,0.03) plot[smooth] coordinates {(0,0.03) (0.6,0.05) (1.2,-0.02) (1.8,0.03) (2.4,0.08) (3.0,0.72) (3.6,0.2) (4.2,0.04) (4.8,0.02) (5.4,0.01) (6.0,0.0)}; \end{scope} \end{tikzpicture} $$ 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, $$ N_\sigma(x) = \frac{1}{\sqrt{2\pi}\,\sigma}\, e^{-x^2 / 2\sigma^2} \quad\text{(1-D)}, \qquad N_\sigma(x, y) = \frac{1}{2\pi\sigma^2}\, e^{-(x^2 + y^2)/2\sigma^2} \quad\text{(2-D)}. $$ 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)' = f \ast g'$. So instead of smoothing and then differentiating we can convolve the image once with the **derivative of the Gaussian**, $N'_\sigma$, and mark as edges the peaks above a threshold. The bottom panel above is exactly $(I \ast N_\sigma)' = I \ast N'_\sigma$; 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$: $$ I = [\,10,\; 12,\; 9,\; 20,\; 9,\; 11,\; 40,\; 42,\; 41\,] . $$ 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 $$ d = [\,\cdot,\; 2,\; -3,\; 11,\; -11,\; 2,\; 29,\; 2,\; -1\,] . $$ 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] = \tfrac{1}{2}\bigl(I[i+1] - I[i-1]\bigr)$ — a central difference over a two-sample span, so it lightly smooths as it differentiates: $$ I \ast g = [\,\cdot,\; -0.5,\; 4.0,\; 0.0,\; -4.5,\; 15.5,\; 15.5,\; 0.5,\; \cdot\,] . $$ 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$ 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 $$ \nabla I = \parens{\begin{array}{c} \partial I / \partial x \\ \partial I / \partial y \end{array}} = \parens{\begin{array}{c} I_x \\ I_y \end{array}} , $$ 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_ $\norm{\nabla I}$ is large. The gradient's _direction_ defines the edge **orientation**, $$ \frac{\nabla I}{\norm{\nabla I}} = \parens{\begin{array}{c} \cos\theta \\ \sin\theta \end{array}} , $$ 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. $$ % caption: A texture is summarized by a histogram of local edge orientations. % A brick wall concentrates orientation near horizontal and vertical (two peaks); % leopard spots spread orientation broadly. The summary is largely invariant to % illumination, which makes texture a stable cue. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % --- left histogram: bricks, two peaks --- \draw[black, ->] (0,0) -- (0,2.2) node[above, black, font=\scriptsize] {count}; \draw[black, ->] (0,0) -- (3.0,0) node[right, black, font=\scriptsize] {orientation}; \foreach \x/\h in {0.2/1.7, 0.55/0.4, 0.9/0.25, 1.25/0.3, 1.6/1.6, 1.95/0.35, 2.3/0.25} \fill[acc!70] (\x,0) rectangle ++(0.28,\h); \node[black, font=\scriptsize, anchor=north] at (1.4,-0.15) {bricks}; % --- right histogram: spots, flat --- \begin{scope}[xshift=4.4cm] \draw[black, ->] (0,0) -- (0,2.2) node[above, black, font=\scriptsize] {count}; \draw[black, ->] (0,0) -- (3.0,0) node[right, black, font=\scriptsize] {orientation}; \foreach \x/\h in {0.2/0.7, 0.55/0.85, 0.9/0.75, 1.25/0.8, 1.6/0.7, 1.95/0.82, 2.3/0.75} \fill[red!55] (\x,0) rectangle ++(0.28,\h); \node[black, font=\scriptsize, anchor=north] at (1.4,-0.15) {leopard spots}; \end{scope} \end{tikzpicture} $$ 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** $$ \mathrm{SSD}(D_x, D_y) = \sum_{(x, y)} \bigl( I(x, y, t) - I(x + D_x,\, y + D_y,\, t + D_t) \bigr)^2 , $$ 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. $$ % caption: Two dual routes to segmentation. Boundary-based: classify each pixel and % orientation as boundary-or-not from the contrast between two half-disks of a % local window (features of brightness, color, texture). Region-based: treat pixels % as graph nodes with similarity-weighted edges and cut the graph to keep similar % pixels together. \begin{tikzpicture}[>=stealth, font=\footnotesize, hdr/.style={font=\small}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % --- left: boundary via two half-disks --- \node[hdr, anchor=south] at (1.1,1.55) {boundary detection}; \draw[black, thick] (1.1,0) circle (1.1); \draw[red, very thick] (1.1,-1.1) -- (1.1,1.1); % dividing diameter \node[acc, font=\scriptsize] at (0.5,0.0) {half}; \node[acc, font=\scriptsize] at (1.7,0.0) {half}; \node[black, font=\scriptsize, anchor=north] at (1.1,-1.2) {compare the two}; % --- right: region via graph cut --- \begin{scope}[xshift=5.0cm] \node[hdr, anchor=south] at (1.1,1.55) {region clustering}; \foreach \i/\x/\y in {a/0/1, b/1/1.2, c/2/0.9, d/0.2/0, e/1.3/0.1, f/2.1/-0.2} { \fill[acc] (\x,\y) circle (2pt); } \draw[black] (0,1) -- (1,1.2); \draw[black] (1,1.2) -- (2,0.9); \draw[black] (0.2,0) -- (1.3,0.1); \draw[black] (1.3,0.1) -- (2.1,-0.2); % the cut \draw[red, very thick, dashed] (1.05,1.55) -- (1.15,-0.6); \node[red, font=\scriptsize, anchor=west] at (1.2,-0.5) {cut}; \end{scope} \end{tikzpicture} $$ 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. $$ % caption: The appearance-recognition pipeline (a face detector). Slide a % fixed-size window over scaled copies of the image; correct each window's % illumination; a regressor estimates and corrects face orientation; features feed % a classifier; non-maximum suppression merges overlapping detections into one. \begin{tikzpicture}[>=stealth, font=\footnotesize, b/.style={draw, minimum width=18mm, minimum height=9mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[b] (win) at (0,0) {slide window\\(over scales)}; \node[b] (illum) at (2.9,0) {correct\\illumination}; \node[b] (orient) at (5.8,0) {estimate +\\correct orient.}; \node[b] (feat) at (8.6,0) {compute\\features}; \node[b, draw=acc, text=acc, thick] (clf) at (11.3,0) {classi\/f\/ier}; \node[b] (nms) at (11.3,-1.9) {non-max\\suppression}; \draw[->, acc, thick] (win) -- (illum); \draw[->, acc, thick] (illum) -- (orient); \draw[->, acc, thick] (orient) -- (feat); \draw[->, acc, thick] (feat) -- (clf); \draw[->, acc, thick] (clf) -- (nms); \node[b] (out) at (7.5,-1.9) {f\/inal\\detections}; \draw[->, acc, thick] (nms) -- (out); \end{tikzpicture} $$ 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 $\norm{\nabla I_{\mathbf{x}}}$ for the gradient magnitude at point $\mathbf{x}$ and $\mathcal{C}$ for the cell whose histogram we compute, a natural weight is $$ w_{\mathbf{x}, \mathcal{C}} = \frac{\norm{\nabla I_{\mathbf{x}}}}{\sum_{\mathbf{u} \in \mathcal{C}} \norm{\nabla I_{\mathbf{u}}}} . $$ 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. > **Definition (HOG feature).** A descriptor of an image window formed by tiling it > into cells, building a histogram of edge orientations in each cell weighted by > relative gradient magnitude, and concatenating the cell histograms. It preserves > coarse spatial layout while tolerating small shifts and illumination change. Modern object recognition has largely replaced these hand-built features. A [convolutional neural network](/deep-learning/architectures/convolutional-networks) 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 $\phi$ 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](/artificial-intelligence/frontiers/reconstructing-the-3d-world).