In computer vision,–Lucas– the Kanade–Lucas–Tomasi (KLT) feature tracker is an approach to feature extraction. It is proposed mainly for the purpose of dealing with the problem that traditional image registration techniques are generally costly. KLT makes use of spatial intensity information to direct the search for the position that yields the best match. It is faster than traditional techniques for examining far fewer potential matches between the images.
The registration problem
The traditional image registration problem can be characterized as follows: Given two functions and , representing pixel values at each location in two images, respectively, where is a vector. We wish to find the disparity vector that minimizes some measure of the difference between and , for in some region of interest .
Some measures of the difference between and :
L1 norm: L2 norm: Negative of normalized correlation:
Basic description of the registration algorithm
The KLT feature tracker is based on two papers:
In the first paper, Lucas and Kanade developed the idea of a local search using gradients weighted by an approximation to the second derivative of the image.
One-dimensional case
If is the displacement between two images and then the approximation is made that
so that
This approximation to the gradient of the image is only accurate if the displacement of the local area between the two images to be registered is not too large. The approximation to depends on . For combining the various estimates of at various values of , it is natural to average them:
The average can be further improved by weighting the contribution of each term to it, which is inversely proportional to an estimate of , where
For the purpose of facilitating the expression, a weighting function is defined:
The average with weighting is thereby:
Upon obtaining the estimate can be moved by the estimate of . The procedure is applied repeatedly, yielding a type of Newton–Raphson iteration. The sequence of estimates will ideally converge to the best . The iteration can be expressed by
An alternative derivation
The derivation above cannot be generalized well to two dimensions for the 2-D linear approximation occurs differently. This can be corrected by applying the linear approximation in the form:
to find the which minimizes the L2 norm measure of the difference (or error) between the curves, where the error can be expressed as:
To minimize the error with respect to , partially differentiate and set it to zero:
This is basically the same as the 1-D case, except for the fact that the weighting function And the iteration form with weighting can be expressed as:
Performance
To evaluate the performance of the algorithm, we are naturally curious about under what conditions and how fast the sequence of 's converges to the real .
Consider the case:
Both versions of the registration algorithm will converge to the correct for , i.e. for initial misregistrations as large as one-half wavelength. The range of convergence can be improved by suppressing high spatial frequencies in the image, which could be achieved by smoothing the image, that will also undesirably suppress small details of it. If the window of smoothing is much larger than the size of the object being matched, the object may be suppressed entirely, so that a match would be no longer possible.
Since lowpass-filtered images can be sampled at lower resolution with no loss of information, a coarse-to-fine strategy is adopted. A low-resolution smoothed version of the image can be used to obtain an approximate match. Applying the algorithm to higher resolution images will refine the match obtained at lower resolution.
As smoothing extends the range of convergence, the weighting function improves the accuracy of approximation, speeding up the convergence. Without weighting, the calculated displacement of the first iteration with falls off to zero as the displacement approaches one-half wavelength.
Implementation
The implementation requires the calculation of the weighted sums of the quantities and over the region of interest Although cannot be calculated exactly, it can be estimated by:
where is chosen appropriately small.
Some sophisticated technique can be used for estimating the first derivatives, but in general such techniques are equivalent to first smoothing the function, and then taking the difference.
Generalization to multiple dimensions
The registration algorithm for 1-D and 2-D can be generalized to more dimensions. To do so, we try to minimize the L2 norm measure of error: