Lucas-Kanade Method: Tracking Pixel Patches, Not Points

Why it exists

Tracking a single pixel's motion between two video frames is often impossible. A point on a uniform edge could have slid anywhere along that edge. This ambiguity, known as the aperture problem, means we need more information than one pixel provides to determine motion accurately.

The mental model

Instead of tracking one ambiguous pixel, track a small, rigid window of pixels around it. The Lucas-Kanade method assumes this entire patch (e.g., 5x5 pixels) moves as a single unit. By observing the intensity changes across all pixels in the patch, it can find the one motion vector that best explains the collective shift, turning an ill-posed problem into a solvable one.

How it works

The method is built on the brightness constancy assumption: a point's brightness doesn't change as it moves between frames. For a patch of pixels, it sets up an equation for each pixel relating its intensity gradient (how sharply the brightness changes) to the unknown motion vector (dx, dy). This creates an overdetermined system—many equations (one for each pixel) for just two unknowns. The system is then solved using a least-squares fit to find the single motion vector that minimizes the error for the entire patch.

When to use it

Use Lucas-Kanade for estimating optical flow where motion between consecutive frames is small. It's computationally efficient and a workhorse for tasks like video stabilization, facial feature tracking, and as a building block in more complex algorithms like SLAM (Simultaneous Localization and Mapping).

When not to use it

Avoid it for scenes with fast motion, as the small-motion assumption will be violated. It also performs poorly with significant lighting changes, in textureless regions like a blank wall (where gradients are zero), and when features are occluded. For larger motions, a pyramidal (multi-scale) version of the algorithm is required.

One canonical example

In video stabilization, an application tracks a set of feature points across frames using Lucas-Kanade. It calculates the dominant motion from these points to estimate the camera's jitter. It then applies an inverse transformation to each frame to cancel this unwanted movement, resulting in a smoother video.