Determining Optical Flow

“Determining Optical Flow” by Berthold K. P. Horn and Brian G. Schunck of the MIT Artificial Intelligence Laboratory first appeared as MIT AI Memo 572 in April 1980 and was published in the journal Artificial Intelligence in 1981. It described a complete scheme for computing a dense optical flow field from an image sequence, at a time when, by the authors’ account, no such scheme had been specified: the brightness change at each pixel supplies one constraint on the two velocity components, and an assumption that the flow varies smoothly supplies the second. Its formulation, a data term plus a smoothness term minimized over the whole image, is the starting point of the variational approach to motion estimation described in the Horn–Schunck method article.

Problem

By 1980, several lines of work took optical flow as given. Following Gibson, it was seen as carrying information about scene layout and observer motion; Koenderink and van Doorn, Longuet-Higgins and Prazdny, and others showed how to recover motion and sometimes shape from it. As Horn and Schunck pointed out, these papers assumed the flow was already known, and no specific scheme for computing it from images had been described. Fennema and Thompson’s clustering method assumed constant velocity within regions, which cannot represent rotating objects.

The difficulty is local underdetermination. Brightness changes at a point give a single equation in the two velocity components, so only the component along the brightness gradient can be recovered there, a limitation now called the aperture problem. Some additional constraint is required.

Contribution

• The brightness change constraint. Assuming that the brightness of a moving point stays constant, the chain rule gives $E_x u + E_y v + E_t = 0$, where $E$ is image brightness. The paper states it explicitly, with a geometric reading: the velocity must lie on a line perpendicular to the brightness gradient (brightness constancy).
• A global smoothness constraint. For opaque objects undergoing rigid motion or deformation, neighbouring image points have similar velocities, so the flow varies smoothly almost everywhere. The paper uses this as the missing second constraint and imposes it over the whole image rather than in a fixed window.
• An energy and an iterative solver. The two constraints are combined in one minimization, solved by a simple iteration based on local averages of the flow.
• An analysis of behaviour. How flow fills in uniform regions, how many iterations that needs, how to weight the smoothness term, and where smoothness fails.

Method

The paper restricts the domain to a flat surface under uniform illumination, with smoothly varying reflectance and no occlusion, so that brightness patterns move with the surface.

The journal version minimizes

$$\iint \Big[ \big( E_x u + E_y v + E_t \big)^2 + \alpha^2 \big( \lVert \nabla u \rVert^2 + \lVert \nabla v \rVert^2 \big) \Big] \, \mathrm{d}x \, \mathrm{d}y ,$$

writing the error in the constraint and the squared magnitude of the flow gradient as separate terms, with the weight $\alpha^2$ on the smoothness term. It mentions the sum of squared Laplacians of $u$ and $v$ as an alternative measure. The 1980 memo had instead expressed smoothness as the squared difference between the flow at a point and its local average, which it called equivalent to the squared Laplacians, and set derivatives to zero point by point. The journal version also adds the explicit exclusion of occlusion, a warning about occluding edges, a note that the iteration resembles Netravali and Robbins’ pixel-recursive equations for television coding, and thanks to two colleagues for spotting a conceptual error in an earlier draft. The calculus of variations in the journal version gives two coupled equations per pixel, which the paper discretizes and solves as follows:

• Derivatives. $E_x$, $E_y$, and $E_t$ are estimated at the centre of a $2 \times 2 \times 2$ cube of samples from two frames, each as the average of four first differences, so that all three refer to the same point in space and time.
• Laplacian. The Laplacian of the flow is approximated by a weighted local average minus the central value, with weights of $1/6$ for edge neighbours and $1/12$ for diagonal ones.
• Iteration. Solving the system directly was impractical, so, citing iterative methods such as Gauss–Seidel, the paper updates each pixel from the local average of the previous estimate, moving it toward its constraint line by an amount proportional to how badly the average violates the constraint.

The paper also sets $\alpha^2$ to about the expected noise level of $E_x^2 + E_y^2$, rejects the limit $\alpha \to 0$ because derivative estimates are noisy, and compares iterating to convergence on one frame pair with a single iteration per new frame, starting from the previous flow. It recommends the latter, since noise averages out over time and the gradient direction at a point changes as the pattern drifts past. The update equations are derived in the Horn–Schunck method article.

Results

All experiments used synthetic sequences of $32 \times 32$ pixels, chosen so that the computed flow could be compared with exact values. Brightness was corrupted with about 1% noise and quantized to 256 levels; the surface patterns were smooth combinations of sinusoids, illuminated so that there was no shading. Results were presented as needle diagrams.

• Translation. From two frames and many iterations, the estimates approached the true flow; after about 32 iterations errors were around 10%, mostly underestimates, with the worst errors where the gradient was small. With one iteration per new frame, errors fell to about 7% after 16 steps, and the average over the image was within 1% of the true value.
• Rotation and contraction of the pattern were also recovered.
• Singular flows. Flow around a line vortex and into a sink, whose speed grows without bound toward the centre, gave the worst errors near the singularity.
• Rigid bodies. For a rotating cylinder and a rotating sphere, the Laplacian of one flow component becomes infinite on the occluding boundary, and the worst errors occurred there; the authors expected the fraction of badly estimated points to fall as resolution increases.

On this evidence the abstract claims robustness to coarse sampling in space and time and to brightness quantization and added noise. No real image sequences were tested.

Impact

The paper is widely cited and is the standard reference for the variational formulation of optical flow. Together with the Lucas–Kanade paper of the same year, it defined the two classical differential approaches, global and local, that most later optical flow estimation methods build on or are compared against. Its structure, a pixelwise data term derived from brightness constancy plus a regularizer, minimized over the whole image, remained the template for hand-designed flow methods for decades. In 1993 the authors revisited it in a short retrospective for a special volume of Artificial Intelligence in which authors of the journal’s most influential papers looked back on them.

Limitations

The journal version anticipates the main weakness: a smoothness assumption will struggle at occluding edges, where the flow is discontinuous, and the rigid-body experiments show the largest errors there. Its summary adds that the flow, computed from noisy, quantized data, is somewhat inaccurate, so recovering shape from derivatives of the flow may prove impractical.

Later work identified further limitations. The quadratic data term lets pixels that violate brightness constancy, such as occlusions and highlights, distort the flow around them. The linearized constraint holds only for motions of about a pixel or less unless estimation proceeds coarse to fine with warping. The best $\alpha$ depends on image content and intensity scale, convergence of the plain iteration is slow, and the output carries no confidence measure.

What Came After

The paper’s descendants keep its energy-minimization structure and change its parts. Black and Anandan made both penalties robust, tolerating outliers and motion boundaries. Brox, Bruhn, Papenberg, and Weickert (2004) kept the brightness constancy assumption without linearization, added gradient constancy, used robust convex penalties, and showed that the resulting fixed-point scheme amounts to coarse-to-fine warping, greatly improving accuracy. Zach, Pock, and Bischof (2007) used an $L^1$ data term with total-variation regularization (TV-L1), which allows sharp discontinuities, and minimized it in real time on a GPU. Combined local–global methods merged the smoothness term with the window-based data term of Lucas–Kanade.

Learned methods eventually displaced hand-designed energies, though RAFT (2020) echoes the variational approach: it refines a single flow field through many iterations of an update its authors liken to a step of a first-order optimizer, with the data and smoothness behaviour learned from training data rather than specified by hand.