Computer Vision
One problem, taken all the way through: a camera watches a ball roll across a table, and the question is where the ball is, in centimetres, in every frame. The early lessons use real photos; every lesson follows the same five steps as the controls lab, and the last two run on your own camera.
1 · Arrive See that a picture is a grid of numbers, and what fewer pixels or fewer levels throw away. about 5 min
2 · Reactivate A camera turns light into numbers, the way a sensor turns a position into a voltage. Every later step works on these numbers.
3 · Inform A picture is numbers
Each pixel stores how much red, green and blue light reached one spot on the sensor, as a byte from 0 to 255. Pixel size averages blocks of pixels together (fewer samples); bits rounds each value to fewer levels. Both lose detail that no later step can get back. Sensor noise is the random error every real camera adds.
Try it
You can now: read a picture as numbers, and say what fewer pixels or fewer levels throw away.
1 · Arrive Average away noise with a convolution, and see what it costs at the edges. about 7 min
2 · Reactivate You saw sensor noise speckle every pixel. Neighbouring pixels usually belong to the same surface, so they should agree. Builds on: Pixels
3 · Inform Slide a kernel over the picture
A convolution slides a small grid of weights, the kernel, over the picture; each output pixel is the weighted sum of the pixels under it. A box weights its square evenly; a Gaussian weights the middle most, so it blurs without the box's blocky marks. Weights that add up to 1 keep the brightness. A wider kernel removes more noise and blurs edges by as much.
Try it
Show the math
out(x, y) = Σi,j k(i, j) · in(x + i, y + j). The Gaussian is k(i, j) ∝ exp(−(i² + j²) / 2σ²). It is a row times a column, so it runs as two 1-D passes: 2n multiplications per pixel instead of n². Averaging n pixels divides the noise's σ by √n.
You can now: blur with a kernel, and trade noise against detail.
1 · Arrive Find edges as the places where brightness changes fast, with the Sobel filter. about 8 min
2 · Reactivate A blur is a kernel whose weights add up to 1. A kernel whose weights add up to 0 ignores flat areas and measures change instead. Builds on: Blur
3 · Inform A kernel that measures change
The Sobel kernels take the difference across a pixel (−1, 0, +1), smoothed along the other direction (1, 2, 1). Gx responds to edges that run up and down, Gy to edges that run across. Together they give the slope's size, √(Gx² + Gy²), and its direction. A threshold on the size turns it into an edge map.
Try it
Show the math
Gx = [−1 0 1; −2 0 2; −1 0 1] and Gy is the same turned on its side. Each is a smoothing [1 2 1] times a difference [−1 0 1]. Direction θ = atan2(Gy, Gx) points from dark to bright, across the edge.
You can now: find edges with Sobel, and keep noise out of them with a blur.
1 · Arrive Find corners, points you can find again in another picture, with the Harris detector. about 8 min
2 · Reactivate Sobel gives the slope at each pixel. An edge has a strong slope in one direction; a corner has strong slopes in two. Builds on: Edges
3 · Inform Slopes in two directions
Harris gathers the slopes (Ix, Iy) in a small window and measures their spread with a 2 × 2 matrix. Its eigenvalues λ₁ and λ₂ are the spread along its two main directions: both small on a flat patch, one large on an edge, both large at a corner. Instead of computing them, Harris scores R = λ₁λ₂ − k(λ₁ + λ₂)² and keeps the local peaks of R above a threshold.
Try it
Show the math
M = Σ w · [Ix² IxIy; IxIy Iy²], summed with a Gaussian weight w of width σ. det M = λ₁λ₂ and trace M = λ₁ + λ₂, so R needs no eigenvalues. k is usually 0.04 to 0.06.
You can now: find corners with Harris, and read flat, edge or corner off λ₁ and λ₂.
1 · Arrive Find the ball in the table camera by thresholding its colour, joining pixels into blobs and picking the round one. about 8 min
2 · Reactivate Each pixel has red, green and blue numbers. The ball is the only thing on the table whose red is well above its green and blue. Builds on: Pixels
3 · Inform Colour, threshold, blobs
Redness is red minus the mean of green and blue: near 0 for grey, below 0 for the green felt, high for the ball. A threshold keeps the pixels above a value, and the histogram shows where to put it. Touching pixels join into blobs; each has an area, a centre and a roundness (1 for a disc, near 0 for a line). The ball's centre, in pixels, is the first answer to the running problem.
Try it
You can now: find a coloured object with a threshold and blobs, and say why a fixed threshold is fragile.
1 · Arrive Turn the camera's slanted view into a flat, to-scale map of the table, and read the ball's position in centimetres. about 10 min
2 · Reactivate You found the ball in pixels. A pixel near the far edge covers more table than one near the camera, so pixels are not centimetres. Builds on: Find the ball
3 · Inform Four points fix a flat surface
A flat surface seen by a camera maps onto the picture by a homography: a 3 × 3 matrix H with 8 free numbers (its scale doesn't matter). Each corner you place gives two equations, so four corners fix H. Its bottom row divides by distance, which is what perspective does. Apply H⁻¹ to the ball's pixel and you get centimetres on the table.
Try it
Show the math
[u, v, w]ᵀ = H [x, y, 1]ᵀ, and the pixel is (u/w, v/w). With h₃₃ = 1, each pair (x, y) → (u, v) gives u(h₃₁x + h₃₂y + 1) = h₁₁x + h₁₂y + h₁₃ and the same for v: two linear equations. Four pairs give eight, and one solve gives H.
You can now: straighten a flat surface with a homography from four points, and read positions in real units.
1 · Arrive Find the same points in two views automatically, and fit the homography between them without placing any corners by hand. about 10 min
2 · Reactivate You placed four corners to get a homography. Harris finds a hundred corners; if the computer can tell which corner in one view is which in the other, it can fit H itself. Builds on: Corners, Homography
3 · Inform Describe, match, then vote
Each corner gets a descriptor: its surroundings sampled on an 8 × 8 grid, minus their mean and scaled to length 1, so lighting changes don't matter. A match is the nearest descriptor in the other view, kept only if the second nearest is clearly worse (the ratio test). Some matches are still wrong, so RANSAC fits H to four random matches many times and keeps the fit most matches agree with. The second view is made from the photo with a known H, so the page can tell right matches from wrong ones.
Try it
You can now: match features between two views, and fit a model through wrong matches with RANSAC.
1 · Arrive Measure depth with two cameras by finding how far a point shifts between them, then triangulating. about 10 min
2 · Reactivate Matching found the same point in two views. With two cameras side by side, how far that point shifts tells you how far away it is. Builds on: Match features
3 · Inform Depth from a shift
Two identical cameras a baseline B apart, facing the same way, see each point on the same row, shifted sideways by its disparity d. Similar triangles give the depth, Z = f·B / d, where f is the focal length in pixels. To find d, slide a small window along the row of the right image and keep the shift where the two windows differ least (block matching). The error grows as Z², and a wider baseline shrinks it.
Try it
Show the math
Z = f·B / d, so δZ ≈ Z² · δd / (f·B). Here f = 150 px. With B = 10 cm, half a pixel of error at 90 cm is about ±3 cm, and at 180 cm about ±11 cm.
You can now: find disparity by block matching, turn it into depth, and say why depth gets worse with distance.
1 · Arrive Watch gradient descent find a filter's nine weights from examples alone. Every neural network is built on this idea. about 7 min
2 · Reactivate Sobel's nine weights were designed by hand. Here you only give examples of what the output should be, and the weights are learned. Builds on: Edges
3 · Inform Walk downhill
The filter starts with random weights. Each training step measures the mean squared difference between its output and the target, works out how that error changes with each weight (the gradient), and moves every weight a little downhill. After a few hundred steps the weights settle. The step size sets how far each move goes: too small is slow, too large overshoots.
Try it
Show the math
E = mean over pixels of (Σ wk xk + b − t)². ∂E/∂wk = 2 · mean of (error · xk), where xk is the pixel under weight k. The page uses Adam, which scales each step by a running estimate of the gradient's size.
You can now: train a filter by gradient descent, and say what a learned convolution layer is.
1 · Arrive Train a two-layer convolutional network to find the ball where the colour threshold fails, in dim light and next to a red pencil. about 10 min
2 · Reactivate One learned filter can only copy one kernel. Stack filters with a bend (ReLU) between them and they can learn what a ball looks like. Builds on: Learn a filter, Find the ball
3 · Inform Filters on filters
Layer 1 has six 5 × 5 colour filters like the one you trained, each followed by a ReLU (negative values become 0). Layer 2 combines those six maps with more 5 × 5 filters into one map, squashed to between 0 and 1: "ball here". It trains on random frames (the ball anywhere, any lamp, often the pencil) against a target that is 1 on the ball and 0 elsewhere. The blue square is the threshold from Find the ball, for comparison.
Try it
You can now: train a small CNN to find an object, and say why it copes where a threshold doesn't.
1 · Arrive Follow the ball through noisy and missing measurements with a Kalman filter. about 10 min
2 · Reactivate The detector gives a position in centimetres each frame, with some error, and nothing at all when the ball is hidden. The ball can't jump, so past frames help. Builds on: Homography
3 · Inform Predict, then correct
The filter keeps an estimate of position and velocity, and how unsure it is (the ring is 2σ). Each frame it predicts (move on by velocity × time, grow the uncertainty by q), then updates with the detector's fix, weighted by the Kalman gain: trust the fix more when the prediction is unsure, less when the detector is noisy (r). The gate ignores fixes that are too surprising. It is the same filter as in Estimate the speed on the controls lab, run in two dimensions.
Try it
Show the math
State [x, y, vx, vy]. Predict x⁻ = F x, P⁻ = F P Fᵀ + Q. Update K = P⁻Hᵀ(H P⁻Hᵀ + R)⁻¹, x = x⁻ + K(z − H x⁻), P = (I − K H) P⁻. The gate drops z when the surprise (z − Hx⁻)ᵀ S⁻¹ (z − Hx⁻) is above 9.2, which a right fix exceeds only 1% of the time.
You can now: track an object through noise and gaps with a Kalman filter, and trade q against r.
1 · Arrive Run the blur, edge and corner filters on your own camera, live. about 5 min
2 · Reactivate Every filter so far was one formula run on every pixel. It works the same on any picture, yours included. Builds on: Blur, Edges, Corners
3 · Inform Your own pictures
Your camera's frames are shrunk to 192 × 144 and run through the same code as the lessons above. Nothing leaves this page, and the camera stops when you open another lesson. Blur trades noise for detail as before, edges follow your outline, and corners cluster where there is texture.
Try it
You can now: run the filters on real video, and spot where each one struggles.
1 · Arrive Track a coloured object you hold, with a colour mask, a blob and a Kalman filter. about 7 min
2 · Reactivate On the table the ball was red, and the filter followed it under the card. Here you pick the colour. Builds on: Find the ball, Track
3 · Inform Pick a colour
Click your object to take its colour. Pixels whose colour is within the tolerance form a mask (brightness is divided out first, so shadows matter less). The biggest blob's centre is the fix, and the Kalman filter smooths it, in pixels.
Try it
You can now: track a real object by its colour, and tune the tolerance and the filter.
Photos (CC0, via Wikimedia Commons): coloured pencils by Artsy Crafty, red bicycle by Dakota Corbin, Hong Kong facade by Wilfredor.