Lucas-Kanade Optical Flow

The starting point is the brightness constancy assumption: a point on a physical surface preserves its intensity as it moves between frames, so $I(x, y, t) = I(x + dx, y + dy, t + dt)$. A first-order Taylor expansion of the right side, dropping second-order terms, produces the optical flow constraint equation,

where $I_x, I_y$ are the spatial image gradients, $I_t$ is the temporal derivative, and $(u, v)$ is the flow velocity at that pixel. This single equation constrains motion only along the gradient direction — the aperture problem — because any $(u,v)$ satisfying it lies on a line in velocity space, not a point. Prerequisite treatments of Optical Flow Fundamentals establish this constraint and its ambiguity; Lucas-Kanade is the classical resolution. The Lucas-Kanade method resolves the ambiguity with a local constancy assumption: all pixels within a small window $W$ around a point share the same flow $(u, v)$. Instead of one equation per pixel, this yields one equation per pixel inside the window, all sharing the same two unknowns. If the window has $n$ pixels, this gives an $n \times 2$ overdetermined linear system, solved by ordinary least squares. The system is well-posed exactly when the window contains gradients pointing in at least two independent directions — geometrically, when the window sits on a corner or richly textured patch rather than a flat region or a straight edge. This is the same structural condition tested by the Harris corner response, which is why Lucas-Kanade trackers are almost always seeded at Harris (or Shi-Tomasi) corners: the matrix that must be inverted here is identical to the second-moment matrix used there. Because the Taylor linearization is only accurate for small displacements, practical Lucas-Kanade implementations wrap the core least-squares solve in two extensions: an iterative Newton-style refinement that re-linearizes around the current estimate until convergence, and a coarse-to-fine image pyramid that estimates large motions at low resolution and refines them at higher resolution, where the linear approximation is locally valid.

Step 1 — Compute image derivatives. For each frame, compute spatial gradients $I_x, I_y$ (e.g., via Sobel filters) and, using the next frame, the temporal derivative $I_t$.

Step 2 — Build the per-window normal equations. For a window $W$ of $n$ pixels around a tracked point, stack the constraint equation from each pixel $i$:

Write this as $A d = -b$, an $n \times 2$ system. Since $n > 2$ generally, solve it in the least-squares sense by the normal equations:

which is a $2 \times 2$ linear system:

The matrix $A^\top A$ is exactly the structure tensor (second-moment matrix) from Harris corner detection. Its two eigenvalues measure gradient energy along two orthogonal directions: two large eigenvalues mean a well-conditioned corner-like window, one large and one near-zero means an edge (aperture problem persists along the edge direction), and two small eigenvalues mean a flat, untrackable region.

Step 3 — Iterative refinement (Newton's method). Because the Taylor expansion is only locally valid, one linear solve rarely gives the exact displacement for anything but sub-pixel motion. Lucas-Kanade is applied iteratively: warp the second image by the current flow estimate, recompute $I_t$ against the warped image, resolve the linear system for an incremental update, and accumulate updates until they fall below a threshold or a maximum iteration count is reached.

Step 4 — Coarse-to-fine pyramid. For displacements larger than a few pixels, the linearization breaks down entirely before iteration can rescue it. The standard fix builds a Gaussian image pyramid, estimates flow at the coarsest (smallest) level where displacements are small in pixel units, upsamples and scales that estimate as an initial guess for the next finer level, and repeats down to full resolution. This is the algorithm implemented in most production KLT trackers. ``` function LUCAS_KANADE_PYRAMIDAL(I1, I2, point p, levels L, window_radius r, max_iters K, eps):

# Build image pyramids (coarsest last index L-1) pyramid1 = build_gaussian_pyramid(I1, L) pyramid2 = build_gaussian_pyramid(I2, L) total_flow = (0, 0) # accumulated at coarse resolution for level in (L-1) down to 0: scale = 2^level p_level = p / scale # point coordinates at this pyramid level guess = total_flow * 2 # upscale estimate from coarser level Ix, Iy = spatial_gradients(pyramid1[level]) window = extract_window(p_level, r) # fixed neighborhood in I1

# Precompute the 2x2 structure tensor ONCE per level (does not change with iteration) Sxx = sum(Ix[window]^2) Syy = sum(Iy[window]^2) Sxy = sum(Ix[window] Iy[window]) Z = [[Sxx, Sxy], [Sxy, Syy]] if not well_conditioned(Z): # smallest eigenvalue below threshold return FAILURE # flat region: cannot resolve motion Z_inv = invert_2x2(Z) flow = guess for iter in 1..K: warped_point = p_level + flow I2_warped = sample_bilinear(pyramid2[level], window shifted by flow) It = I2_warped - pyramid1[level][window] # temporal difference bx = sum(Ix[window] It) by = sum(Iy[window] * It) delta = Z_inv @ [-bx, -by] # incremental update solving normal equations flow = flow + delta if norm(delta) < eps: break total_flow = flow # becomes the guess for the next finer level return total_flow # final (u, v) displacement at full resolution ``` The inner loop is the classical Lucas-Kanade update; the outer pyramid loop is the Kanade-Lucas-Tomasi (KLT) extension that makes it practical for real motions.

Time complexity. For a single point tracked with a window of $n = (2r+1)^2$ pixels, computing the sums $\sum I_x^2, \sum I_y^2, \sum I_x I_y, \sum I_x I_t, \sum I_y I_t$ costs $O(n)$ per iteration. Inverting the resulting $2 \times 2$ matrix is $O(1)$. With $K$ Newton iterations and $L$ pyramid levels, tracking one point costs $O(L \cdot K \cdot n)$. Tracking $m$ points over a frame is $O(m \cdot L \cdot K \cdot n)$, which is linear in every parameter — the reason KLT trackers run comfortably in real time for hundreds of feature points. Computing dense flow at every pixel of an $N$-pixel image is $O(N \cdot L \cdot K \cdot n)$, still linear in image size, in contrast to global methods like Horn-Schunck that require solving a large sparse linear system (typically $O(N)$ per iteration of an iterative solver, but with much larger hidden constants and slower convergence for the same accuracy).

Space complexity. $O(n)$ per point for the window buffers, plus $O(N)$ for the image pyramid, which is shared across all tracked points. No global system is ever assembled, unlike variational (Horn-Schunck style) approaches, which is the structural reason Lucas-Kanade is far cheaper in memory.

Correctness argument. The method rests on two approximations whose validity conditions can be stated precisely. Well-posedness of the linear solve. The normal-equations matrix $Z = A^\top A$ is symmetric positive semi-definite, so it is invertible iff both eigenvalues $\lambda_1 \geq \lambda_2 > 0$. Since $A^\top A$ is a sum of outer products $\sum \nabla I_i \nabla I_i^\top$, a nonzero smallest eigenvalue $\lambda_2$ requires gradients pointing in at least two independent directions somewhere in the window — precisely the Harris "cornerness" condition. This is not incidental: least-squares here is solving the exact same aperture-resolution problem that motivates corner detection, so seeding Lucas-Kanade tracking at Harris/Shi-Tomasi corners is provably choosing the windows where the underlying linear system is best conditioned, minimizing the amplification of pixel noise into flow error (formally, the error covariance of the least-squares estimate scales with $Z^{-1}$, so small $\lambda_2$ directly inflates estimation variance along that eigendirection). Validity of linearization. The Taylor expansion $I(x+u, y+v, t+dt) \approx I(x,y,t) + I_x u + I_y v + I_t$ has a remainder term of order $O(u^2 + v^2)$ times the local curvature of the intensity surface. The approximation is accurate only when $(u, v)$ is small relative to the scale over which the image gradient itself varies. Iteration corrects for this: re-warping the image by the current estimate and re-linearizing around the new residual reduces the effective displacement being linearized at each step, so if the iteration converges, it converges to a stationary point of the true (non-linearized) sum-of-squared-differences objective

which each Newton step is implicitly minimizing via its local quadratic approximation. Convergence is not guaranteed in general (the true objective can be non-convex with multiple local minima from repeated texture), but it is guaranteed to converge quickly for small residual displacements because the quadratic approximation of $E$ near a good corner is well-conditioned, by the same eigenvalue argument above. The pyramid extension exists precisely to keep the initial residual displacement small at every level, so that this local-convergence guarantee actually applies before any iteration begins.

Honest tradeoffs. Lucas-Kanade is fast and accurate at strong corners but produces no estimate (or an unreliable one) in flat or purely edge-like regions — it deliberately trades completeness for reliability, unlike Horn-Schunck-style global methods that produce a dense flow field everywhere by propagating information from confident regions into ambiguous ones, at higher computational cost and with a smoothing bias.

Consider tracking a small corner feature between two consecutive $5\times 5$ grayscale windows extracted around a candidate point, with pixel intensities (0–255) given below. Frame 1 shows a bright L-shaped corner; frame 2 shows the same pattern shifted by roughly $(0.6, 0.4)$ pixels (sub-pixel, simulating a slow real drift).

Step through the algorithm: 1. Gradients. Using central differences on frame 1, $I_x$ is large and positive (≈190 per 2 pixels of horizontal step) at the column-3/4 boundary where intensity jumps from 10 to 200, and near zero elsewhere; $I_y$ is near zero everywhere in frame 1 because intensity is constant along each row (a pure vertical edge has no vertical gradient). This is deliberately an edge-dominated window at first glance — but the diagonal blur of the transition in frame 2 (see how the boundary bends across rows) means a few pixels near the corner of the L carry non-negligible $I_y$ too, giving the matrix just enough rank. 2. Structure tensor. Summing over the 25 pixels (numeric derivatives computed via Sobel):

Eigenvalues are approximately $\lambda_1 \approx 43000$, $\lambda_2 \approx 2100$. Both are well above a typical noise threshold (commonly a few hundred, depending on sensor noise), so the point is trackable, though the small $\lambda_2$ signals it's edge-leaning rather than a crisp corner. 3. Temporal difference and right-hand side. Subtracting frame 1 from frame 2 pixelwise gives large positive $I_t$ concentrated where the boundary moved (the region that changed from dark 10 to bright ~150–200 as the corner slid rightward/downward). Computing $b = (\sum I_x I_t, \sum I_y I_t) \approx (5200, 1400)$. 4. Solve.

5. Iterate. Warping frame 2 backward by $(-0.58,-0.42)$ and recomputing the residual $I_t$ yields a much smaller correction, typically under $0.05$ pixels, so the loop terminates after 2–3 iterations. The recovered flow $(u,v) \approx (0.58, 0.42)$ matches the simulated ground-truth shift of $(0.6, 0.4)$ to within numerical rounding — exactly the behavior the correctness argument predicts: a well-conditioned $Z$ (both eigenvalues comfortably above noise floor) combined with a small true displacement (well inside the linearization's valid range) yields fast, accurate convergence.

Pyramidal Lucas-Kanade, under the name KLT tracking, is the sparse feature-tracking backbone of countless real-time systems. Visual-inertial odometry pipelines used in drones, mobile robots, and AR headsets track a sparse set of Harris/Shi-Tomasi corners frame to frame with KLT before feeding the resulting 2D correspondences into a bundle adjustment or filtering backend for pose estimation — the natural entry point into Structure from Motion and monocular SLAM. Video stabilization software estimates dominant camera motion by robustly aggregating many local Lucas-Kanade flow vectors. Motion-compensated video codecs and frame-interpolation systems use local flow estimates conceptually descended from this formulation. Optical mice and some industrial machine-vision motion sensors use closely related local gradient-based tracking at the hardware level. Even modern deep optical flow networks (such as those in the FlowNet and RAFT families) are frequently evaluated against, and sometimes initialized or regularized by, the same local-window least-squares intuition that Lucas-Kanade formalized four decades earlier, and many learned trackers still use its coarse-to-fine, iterative-refinement structure as an architectural template.

Ask the tutor: How does the affine (six-parameter) extension of Lucas-Kanade change the structure tensor and the conditions needed for a stable solve?