An Iterative Image Registration Technique with an Application to Stereo Vision

“An Iterative Image Registration Technique with an Application to Stereo Vision” is a six-page paper by Bruce D. Lucas and Takeo Kanade of Carnegie-Mellon University, published in the proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI) in 1981. It proposed finding the best alignment between two images by following the spatial intensity gradient, in a Newton–Raphson-type iteration, instead of testing candidate displacements one by one. The paper’s own application was stereo vision. Its core step, applied to small windows in consecutive video frames, became the Lucas–Kanade method of optical flow and the tracking step of the KLT feature tracker.

Problem

Image registration, finding the displacement that best aligns two images, was needed for stereo, pattern recognition, and motion analysis. Lucas and Kanade framed it as follows: given images $F(\mathbf{x})$ and $G(\mathbf{x})$, find the disparity vector $\mathbf{h}$ that minimizes a measure of the difference between $F(\mathbf{x} + \mathbf{h})$ and $G(\mathbf{x})$ over a region of interest.

The techniques they surveyed all searched the space of displacements in a fixed order. Exhaustive search evaluates every candidate, at a cost of $O(M^2 N^2)$ for an $N \times N$ image and an $M \times M$ range of displacements; by contrast, the authors state that their iteration, when it converges, takes $O(M^2 \log N)$ steps on average. Hill climbing moves to the best neighbour of the current guess. The sequential similarity detection algorithm of Barnea and Silverman abandons a candidate once its accumulated error is clearly too large. Coarse-to-fine schemes, such as the one in Moravec’s rover work, match at low resolution first to narrow the search. None used the image content to decide where to look next, and most could not handle rotation or other distortions.

Contribution

The central observation is that when two images are already roughly aligned, as they often are, the local intensity gradient indicates which way and how far to move. The contributions were:

• Gradient-directed registration. A linear approximation of the image around the current estimate yields a correction to the displacement directly; shifting and repeating gives what the authors called a type of Newton–Raphson iteration, which evaluates far fewer candidate positions than search.
• Weighting, smoothing, and coarse-to-fine estimation. Points are weighted by how well the linearization holds there, and an analysis of the convergence range motivates smoothing and refining from low to high resolution.
• Generalizations. The same derivation extends to two or more dimensions, to general linear transformations of the coordinates (rotation, scaling, shearing), and to contrast and brightness differences between the images.
• Stereo. The same step solves for object depths and camera parameters together.

Method

The paper first works in one dimension. For a small displacement $h$, $F(x + h) \approx F(x) + h F'(x)$, so each point gives its own estimate $h \approx [G(x) - F(x)] / F'(x)$. Since the linearization is poor where $F$ curves strongly, each estimate is weighted inversely to an estimate of $|F''(x)|$, giving $w(x) = 1 / |G'(x) - F'(x)|$. Shifting $F$ by the estimate and repeating gives the iteration.

Because this first derivation does not carry over to two dimensions and breaks down where $F'(x) = 0$, the paper derives the estimate a second way, by minimizing the squared difference $\sum_x [F(x + h) - G(x)]^2$ under the same linearization. The result has the same form, with weight $F'(x)^2$, and is undefined only if the derivative vanishes everywhere. With both weightings, the iteration reads

$$h_0 = 0, \qquad h_{k+1} = h_k + \frac{\sum_x w(x)\, F'(x + h_k) \big[ G(x) - F(x + h_k) \big]}{\sum_x w(x)\, F'(x + h_k)^2} .$$

In two dimensions the derivative becomes the gradient and the estimate requires accumulating five products of gradients and differences over the region, against one for correlation; the authors argued that evaluating far fewer displacements more than compensates. Derivatives were estimated by first differences, since smoothing already does the work of more elaborate filters. The least-squares form, its structure-tensor interpretation, and the modern algorithm are derived in the Lucas–Kanade article.

For convergence, the paper analyses $F(x) = \sin x$ and states that both versions of the iteration converge to the correct displacement for initial errors below half a wavelength ($|h| < \pi$). Suppressing high frequencies therefore widens the range of convergence, at the cost of accuracy and of objects smaller than the smoothing window. Since smoothed images can be subsampled, this suggests a coarse-to-fine strategy (coarse-to-fine estimation). The weighting, in turn, makes the first step more accurate for large disparities and so speeds convergence.

The generalization compares $F(\mathbf{x} A + \mathbf{h})$ with $G(\mathbf{x})$, where the matrix $A$ is a linear transformation of the coordinates, and then with $\alpha G(\mathbf{x}) + \beta$, where $\alpha$ and $\beta$ are a contrast and a brightness adjustment. Ignoring $A$, minimizing this error is equivalent to maximizing the correlation coefficient; ignoring $\alpha$ and $\beta$ as well, it reduces to the plain squared difference. Linearizing in the corrections to $A$, $\mathbf{h}$, $\alpha$, and $\beta$ again gives a quadratic error and a linear system. Linear transformations are justified as an orthographic model of how a small planar patch distorts between viewpoints.

For stereo, the authors parametrize the position of each object in the second image by its depth and by five camera parameters (azimuth, elevation, pan, tilt, and roll, following Gennery), and apply the same linearization through the chain rule to update depth and camera parameters.

Results

The results are a demonstration, not a quantitative evaluation. The implemented system could solve for object distances, the five camera parameters, and a scene-wide brightness and contrast, or any subset of them, and the authors described it as working well under human supervision. It converged when the initial estimates placed each object in the second image to within about the object’s own size.

In the illustrated session, the camera parameters were determined beforehand from hand-selected matching points with Gennery’s calibration program, and the images were bandpass filtered, which the authors preferred because the lowest spatial frequencies mostly reflect shading. Two hand-selected regions, started at a depth of 7.0 baselines, converged in seven iterations to depths of about 6.05 and 5.86. In a band one octave higher, five new hand-selected points, initialized from those depths, converged in five iterations to depths between about 5.8 and 6.1. No ground truth or timings are reported.

Impact

The lasting influence came from motion analysis, one of the applications its introduction lists, rather than stereo:

• Feature tracking. Tomasi and Kanade (1991) built point tracking on the Lucas–Kanade step, and Shi and Tomasi (1994) chose features by the condition that makes its equations well conditioned and monitored them with an affine model. The resulting Kanade–Lucas–Tomasi (KLT) tracker remains a standard way to follow points through video (feature tracking).
• Local optical flow. Applied in a small window at each point, the method became one of the two classical differential approaches to optical flow estimation, alongside the global method of Horn and Schunck published the same year, and was among the methods in Barron, Fleet, and Beauchemin’s 1994 evaluation.
• Image alignment. Two decades later, Baker and Matthews’ review (2004) counted image alignment among the most used techniques in computer vision, with uses from optical flow and tracking to mosaicking and face modelling.

Limitations

The paper itself listed what its system lacked: it needed considerable hand guidance, initial depth estimates, interest points selected by hand, a way to turn sparse depths into a depth map, heuristics for depth discontinuities at object boundaries, and better handling of appearance differences between views.

Later work made other limitations explicit. The method finds only a local optimum and converges only within a basin set by the image’s dominant frequencies. A translation-only window cannot represent several motions, and it is ill conditioned where gradients point in only one direction (aperture problem), which the paper does not discuss beyond noting that the least-squares estimate is undefined only if the derivative vanishes everywhere. The squared error is sensitive to outliers such as occluded pixels.

What Came After

Coarse-to-fine refinement on image pyramids, which the paper suggested, became the standard way to handle larger motions; most feature trackers run pyramidal Lucas–Kanade. The linear-transformation generalization grew into direct alignment with affine and projective warps for mosaicking, stabilization, and template tracking. Baker and Matthews’ framework, built around their efficient inverse compositional algorithm, became the reference treatment of the family. On the optical flow side, combined local–global methods merged the Lucas–Kanade data term with the smoothness term of Horn–Schunck, and modern deep networks such as RAFT still refine flow iteratively, though with learned rather than gradient-derived updates.