Optical Flow · Projects · Amittai Siavava

Optical flow is the apparent motion of the scene across a video, whether the objects move or the camera does. This project builds three trackers for it from first principles: a translation-only Lucas-Kanade solver (LucasKanade), a six-parameter affine version (LucasKanadeAffine), and its inverse-compositional counterpart (InverseCompositionAffine, the Matthews-Baker formulation). All three sample the image and its gradients at subpixel locations with a RectBivariateSpline, and iterate up to a hundred times or until the parameter update drops below tolerance.

All three rest on one equation. Assume a pixel keeps its brightness as it moves; expanding $I (x + u, y + v, t + 1) = I (x, y, t)$ to first order gives the brightness-constancy constraint

I_{x} u + I_{y} v + I_{t} = 0,

one equation in two unknowns per pixel — the aperture problem: motion along an edge is invisible. Lucas-Kanade resolves it by assuming the flow is constant over a small window $W$ and solving all of the window's constraints at once, in least squares:

A^{⊤} A [\sum I_{x}^{2} \sum I_{x} I_{y} \sum I_{x} I_{y} \sum I_{y}^{2}] [u v] = - [\sum I_{x} I_{t} \sum I_{y} I_{t}] .

The window around a tracked corner keeps its intensity pattern — brightness constancy — as it drifts across the frames; dashed squares mark where the patch sat before, and each arrow is one frame-to-frame flow

(u, v)

. Lucas-Kanade recovers each displacement by solving the window's stacked gradient constraints in least squares, and tracking chains the solves.

The translation tracker reduces to a $2 \times 2$ solve per window, and the matrix $A^{⊤} A$ is exactly the Harris corner matrix, which is why corners are the pixels worth tracking: the system is well-conditioned precisely where the image has structure in two directions. The affine version widens the warp to six parameters, so each pixel's Jacobian is the $2 \times 6$ block $[x 0 y 010; 0 x 0 y 01]$ and the per-step update comes from the pseudo-inverse of the $6 \times 6$ Hessian.

Algorithm:

\textsc{Lucas-Kanade}(I, J, p)

— iterative flow for one window

1
input: frames $I, J$ , window center $p$ , initial flow $w \gets 0$
2
repeat
3
warp $J$ by current flow $w$ around $p$
4
$b \gets$ residuals $I - J_{warped}$ over the window
5
solve $(A^\top A)\, \Delta = A^\top b$ for the update $\Delta$
6
$w \gets w + \Delta$
7
until $\lVert \Delta \rVert$ is below tolerance
8
return $w$

The classical affine loop re-evaluates the image gradient and rebuilds the Hessian on the warped frame every iteration. The inverse-compositional trick (Matthews-Baker) swaps template and image so the gradient, Jacobian, and Hessian depend only on the template: InverseCompositionAffine computes them once before the loop, and each iteration solves against the precomputed pseudo-inverse, then folds the incremental warp in by composing with its inverse, $W \leftarrow W (Δ W)^{- 1}$ . The iteration reaches the same fixed point at a fraction of the cost. The write-up with derivations and results is available as a PDF report.

References

Project repository
Reference notes: Linear Algebra

╌╌ END ╌╌