Optical Flow (Lucas-Kanade)

Every time you watch a video, your brain effortlessly decides which parts of the scene are moving and which are still. Computers cannot afford that luxury — they get only a grid of brightness values changing from frame to frame. Optical flow is the name for the apparent velocity field that explains those changes: for every pixel, how far did it shift between two consecutive frames?

The question sounds simple, but it is fundamentally ill-posed. Imagine a perfectly uniform gray disk sliding across a white background. Looking at a single pixel in isolation you cannot tell whether it moved up or sideways — a problem known as the aperture problem. Some additional assumption is always needed to pin down a unique answer.

In 1981, Bruce D. Lucas and Takeo Kanade proposed the cleanest possible assumption: brightness constancy. A surface patch keeps roughly the same brightness as it moves a short distance in a short time. This turns motion estimation into a small system of linear equations — solvable in milliseconds for every pixel in the image.

The Lucas-Kanade method has been refined, extended, and combined with deep-learning pipelines for forty years. It remains the foundation that anyone studying dimensionality reduction or pattern matching in vision should know first.

The canvas below shows two consecutive synthetic frames. A bright blob moves a few pixels each step — press Play to animate it, or use Step to advance one frame at a time. The arrows drawn on each pixel show the velocity $(u, v)$ that Lucas-Kanade estimates at that location.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<canvas id="canvas" width="320" height="240"></canvas>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-play" type="button">{{btn_play}}</button>
  <button id="btn-step" type="button" class="ghost">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #000; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice that arrows inside the blob track its true motion while arrows on the featureless background stay near zero — exactly what the algorithm predicts: it can only recover motion where the image has both horizontal and vertical intensity gradients (i.e., corners or edges, not flat regions).

The brightness-constancy constraint

Let $I(x, y, t)$ be the brightness of pixel $(x, y)$ at time $t$. If pixel $(x, y)$ moves to $(x + u, y + v)$ by time $t + 1$, brightness constancy says:

$$I(x, y, t) = I(x + u, y + v, t + 1)$$

Taylor-expanding the right side and keeping only first-order terms gives the optical flow constraint equation:

$$I_x \, u + I_y \, v + I_t = 0$$

where $I_x$, $I_y$ are spatial gradients and $I_t$ is the temporal gradient at that pixel. One equation, two unknowns — that is the aperture problem in mathematical form.

The Lucas-Kanade fix: a local window

Lucas and Kanade assume the flow $(u, v)$ is constant over a small $w \times w$ window around each pixel. With $w^2$ pixels in the window you have $w^2$ equations and still only two unknowns — an over-determined system. They solve it in the least-squares sense:

$$\begin{pmatrix} \sum I_x^2 & \sum I_x I_y \\ \sum I_x I_y & \sum I_y^2 \end{pmatrix} \begin{pmatrix} u \\ v \end{pmatrix} = -\begin{pmatrix} \sum I_x I_t \\ \sum I_y I_t \end{pmatrix}$$

The $2 \times 2$ matrix on the left is called the structure tensor (or Harris matrix). The system has a unique solution exactly when the tensor is invertible — which happens when the window contains gradients in at least two independent directions, i.e., a corner or textured region.

• Flat regions: both eigenvalues near zero — flow is undefined.
• Edges: one large eigenvalue — flow is constrained only perpendicular to the edge (aperture problem).
• Corners: both eigenvalues large — flow is fully determined.

Computational cost

At each pixel: compute three gradients, accumulate a $2 \times 2$ matrix over the window, invert it. That is $O(w^2)$ per pixel and $O(N w^2)$ total for an $N$-pixel image — a constant multiplied by the image size, fully parallelizable on a GPU.

Per-pixel motion is one of the most useful signals in visual computing:

• Video compression: MPEG and H.264/H.265 use motion vectors — computed by variants of this idea — to encode only the difference between frames. Without optical flow, streaming video would be 10–50× larger.
• Autonomous driving: cameras on self-driving cars track how the road, pedestrians, and obstacles appear to move. Combined with dimensionality reduction and depth estimation, flow reveals the 3-D structure of the scene.
• Medical imaging: echocardiography and MRI motion analysis use optical flow to track heart-wall motion across time, quantifying cardiac function without invasive procedures.
• Action recognition: instead of classifying raw pixels, many systems first compute flow and classify the motion pattern — dramatically reducing the complexity and improving generalization.
• Augmented reality: anchoring virtual objects to a real scene requires knowing exactly how every surface point moves; optical flow provides the dense estimate that sparse feature trackers miss.

Modern deep-learning approaches (FlowNet, RAFT) replace the structure tensor with learned filters but still train on the same brightness-constancy intuition. Understanding Lucas-Kanade is the fastest path into that literature.

Lucas-Kanade optical flow is a masterclass in turning a hard, ill-posed problem into a tractable one with a single physical assumption: pixels keep their brightness as they move. That one sentence becomes a linear system, the linear system becomes a $2 \times 2$ matrix inverse, and the matrix inverse becomes a real-time algorithm used in billions of devices today.

The limits are just as instructive as the successes: flat regions give no information, large motions break the Taylor expansion, and occlusions violate brightness constancy entirely. Each limitation has spawned decades of follow-on research — pyramidal Lucas-Kanade, robust estimation, deep flow networks — but every one of them traces its roots to the elegant constraint equation $I_x u + I_y v + I_t = 0$.

Next time you pause a video and notice the streaks of motion blur, remember: a computer is solving thousands of $2 \times 2$ systems to understand exactly what you are seeing.