Image registration by the intensity gradient
In April 1981 Bruce Lucas and Takeo Kanade presented a way of aligning two images that does not test candidate displacements, but uses the spatial intensity gradient to correct the current estimate at each step. Exhaustive search over an M by M range of displacements on an N by N picture costs O(M²N²); this method converges in O(M² log N) steps on the average.
Why it matters
Finding the correspondence between two images stopped being a search. Instead of scoring every possible displacement, the algorithm reads out of the image itself which way to move, and this is what both feature tracking in video and stereo matching were later built on.
The iteration is of Newton-Raphson form. The paper shows a stereo experiment: two hand-selected regions given an initial depth of 7.0 in units of the distance between cameras; after seven depth adjustments the computed distances were 6.05 and 5.86. At one octave higher five more points were selected, and after five iterations the depths were 5.96, 5.98, 5.77, 5.76 and 6.09. The record does not claim convergence in "fewer than 5 iterations", nor a sub-pixel error "under 0.1 pixel". Neither figure is in the paper. The date is disputed, and this disagreement is worth recording. The first presentation was at the DARPA IUW in April 1981, pages 121-130; a shorter version went to IJCAI-81 in Vancouver on 24-28 August, pages 674-679. The record sits on the first of those under the rule of primary publication, although Carnegie Mellon's own catalogue asks that citations point at the second. The original version on the university server is an image scan with no text layer, so the figures here were read from the IJCAI version.