Lucas–Kanade method

In computer vision, the Lucas–Kanade method is a two-frame differential method for optical flow estimation developed by Bruce D. Lucas and Takeo Kanade

Optical flow algorithms estimate the deformations between two image frames. The basic assumption for the optical flow calculation is that of the conservation of pixel or voxel intensity. It is assumed that the intensity, or color, of the objects has not changed significantly between the two frames. Based on this idea, an image constraint equation can be given. Different optical flow algorithms solve the problem of optical flow by postulating additional conditions.

Detailed treatment

The Lucas–Kanade method is still one of the most popular versions of two-frame differential methods for motion estimation (which is also called optical flow estimation). Such methods try to calculate the motion between two image frames which are taken at times "t" and $t+delta\; t$ at every pixel position. These methods are called differential since they are based on local Taylor series approximations of the image signal, that is: they use partial derivatives with respect to the spatial and temporal coordinates. As a voxel at location "(x, y,z, t)" with intensity "I(x, y,z, t)" will have moved by $delta\; x$, $delta\; y$, $delta\; z$ and $delta\; t$ between the two frames, following "image constraint equation" can be given: :$I(x,y,z,t)\; =\; I(x+delta\; x,y\; +\; delta\; y,z\; +\; delta\; z,t\; +\; delta\; t)$

Assuming the movement to be small enough, the image constraint at $I(x,y,z,t)$ with Taylor series can be developed to get::$I(x+delta\; x,y+delta\; y,z+delta\; z,t+delta\; t)\; =\; I(x,y,z,t)\; +\; frac\{partial\; I\}\{partial\; x\}delta\; x+frac\{partial\; I\}\{partial\; y\}delta\; y+frac\{partial\; I\}\{partial\; z\}delta\; z+frac\{partial\; I\}\{partial\; t\}delta\; t+H.O.T.$ where H.O.T. means higher order terms, which are small enough to be ignored. From these equations it follows that::$frac\{partial\; I\}\{partial\; x\}delta\; x+frac\{partial\; I\}\{partial\; y\}delta\; y+frac\{partial\; I\}\{partial\; z\}delta\; z+frac\{partial\; I\}\{partial\; t\}delta\; t\; =\; 0$ or:$frac\{partial\; I\}\{partial\; x\}frac\{delta\; x\}\{delta\; t\}+frac\{partial\; I\}\{partial\; y\}frac\{delta\; y\}\{delta\; t\}+frac\{partial\; I\}\{partial\; z\}frac\{delta\; z\}\{delta\; t\}+frac\{partial\; I\}\{partial\; t\}frac\{delta\; t\}\{delta\; t\}\; =\; 0$which results in :$frac\{partial\; I\}\{partial\; x\}V\_x+frac\{partial\; I\}\{partial\; y\}V\_y+frac\{partial\; I\}\{partial\; z\}V\_z+frac\{partial\; I\}\{partial\; t\}\; =\; 0$ where $V\_x,V\_y,V\_z$ are the $x$,$y$ and $z$ components of the velocity or optical flow of $I(x,y,z,t)$ and $frac\{partial\; I\}\{partial\; x\}$, $frac\{partial\; I\}\{partial\; y\}$, $frac\{partial\; I\}\{partial\; z\}$ and $frac\{partial\; I\}\{partial\; t\}$ are the derivatives of the image at $(x,y,z,t)$ in the corresponding directions. $I\_x$,$I\_y$, $I\_z$ and $I\_t$ can be written for the derivatives in the following.

Thus:$I\_xV\_x+I\_yV\_y+I\_zV\_z=-I\_t$or :$abla\; Icdotvec\{V\}\; =\; -I\_t$This is an equation in three unknowns and cannot be solved as such. This is known as the "aperture problem" of the optical flow algorithms. To find the optical flow another set of equations is needed, given by some additional constraint. The solution as given by Lucas and Kanade is a non-iterative method which assumes a locally constant flow.

Assuming that the flow $(V\_x,V\_y,V\_z)$ is constant in a small window of size $m\; imes\; m\; imes\; m$ with $m>1$, which is centered at voxel $x,y,z$ and numbering the pixels within as $1...n$, $n=m^3$, a set of equations can be found::$I\_\{x\_1\}\; V\_x\; +\; I\_\{y\_1\}\; V\_y\; +\; I\_\{z\_1\}\; V\_z\; =\; -I\_\{t\_1\}$:$I\_\{x\_2\}\; V\_x\; +\; I\_\{y\_2\}\; V\_y\; +\; I\_\{z\_2\}\; V\_z\; =\; -I\_\{t\_2\}$:$vdots$:$I\_\{x\_n\}\; V\_x\; +\; I\_\{y\_n\}\; V\_y\; +\; I\_\{z\_n\}\; V\_z\; =\; -I\_\{t\_n\}$

With this there are more than three equations for the three unknowns and thus the system is over-determined. Hence::or:$Avec\{v\}=-b$To solve the over-determined system of equations, the least squares method is used in the Lucas–Kanade optical flow estimation::$A^TAvec\{v\}=A^T(-b)$ or:$vec\{v\}=(A^TA)^\{-1\}A^T(-b)$or:with the sums running from i=1 to n.

This means that the optical flow can be found by calculating the derivatives of the image in all four dimensions. A weighting function "W(i, j,k)", with $i,j,k\; in\; [1,m]$ should be added to give more prominence to the center pixel of the window. Gaussian functions are preferred for this purpose. Other functions or weighting schemes are possible. Besides for computing local translations, the flow model can also be extended to affine image deformations.

When applied to image registration, such as stereo matching, the Lucas–Kanade method is usually carried out in a coarse-to-fine iterative manner, in such a way that the spatial derivatives are first computed at a coarse scale in scale-space (or a pyramid), one of the images is warped by the computed deformation, and iterative updates are then computed at successively finer scales.

One of the characteristics of the Lucas–Kanade algorithm, and that of other local optical flow algorithms, is that it does not yield a very high density of flow vectors, i.e. the flow information fades out quickly across motion boundaries and the inner parts of large homogenous areas show little motion. Its advantage is the comparative robustness in presence of noise.

See also

* Optical flow
* Horn–Schunck method
* The Shi and Tomasi corner detection algorithm

References

* Lucas B D and Kanade T 1981, An iterative image registration technique with an application to stereo vision. "Proceedings of Imaging understanding workshop", pp 121--130 ( [http://www-cse.ucsd.edu/classes/sp02/cse252/lucaskanade81.pdf pdf] ).
* Lucas B D 1984, " [http://www.ri.cmu.edu/pubs/pub_5610.html Generalized Image Matching by the Method of Differences] ", doctoral dissertation
* [http://www.ces.clemson.edu/~stb/klt/ KLT] : An Implementation of the Kanade–Lucas–Tomasi Feature Tracker
* [http://www.ri.cmu.edu/people/kanade_takeo.html] : Takeo Kanade