Lucas Kanade method
Encyclopedia
In computer vision
, the Lucas–Kanade method is a widely used differential method for optical flow
estimation developed by Bruce D. Lucas and Takeo Kanade
. It assumes that the flow is essentially constant in a local neighbourhood of the pixel
under consideration, and solves the basic optical flow equations for all the pixels in that neighbourhood, by the least squares criterion.
By combining information from several nearby pixels, the Lucas-Kanade method can often resolve the inherent ambiguity of the optical flow equation. It is also less sensitive to image noise than point-wise methods. On the other hand, since it is a purely local method, it cannot provide flow information in the interior of uniform regions of the image.
can be assumed to hold for all pixels within a window centered at p. Namely, the local image flow (velocity) vector
must satisfy
where
are the pixels inside the window, and 
are the partial derivatives of the image 
with respect to position x, y and time t, evaluated at the point 
and at the current time.
These equations can be written in matrix
form
, where
This system has more equations than unknowns and thus it is usually over-determined. The Lucas-Kanade method obtains a compromise solution
by the least squares principle. Namely, it solves the 2×2 system
or
where
is the transpose of matrix 
. That is, it computes
with the sums running from i=1 to n.
The matrix
is often called the structure tensor
of the image at the point p.
in the window. In practice it is usually better to give more weight to the pixels that are closer to the central pixel p. For that, one uses the weighted version of the least squares equation,
or
where
is an n×n diagonal matrix
containing the weights
to be assigned to the equation of pixel 
. That is, it computes
The weight
is usually set to a Gaussian function of the distance between 
and p.
s" (grossly wrong data values, that do not follow the "ordinary" Gaussian error distribution), one may use statistical analysis to detect them, and reduce their weight accordingly.
The Lucas-Kanade method per se can be used only when the image flow vector
between the two frames is small enough for the differential equation of the optical flow to hold, which is often less than the pixel spacing. When the flow vector may exceed this limit, such as in stereo matching or warped document registration, the Lucas-Kanade method may still be used to refine some coarse estimate of the same, obtained by other means; for example, by extrapolating
the flow vectors computed for previous frames, or by running the Lucas-Kanade algorithm on reduced-scale versions of the images. Indeed, the latter method is the basis of the popular Kanade-Lucas-Tomasi (KLT) feature matching algorithm.
A similar technique can be used compute differential affine deformations of the image contents.
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
, the Lucas–Kanade method is a widely used differential method for optical flow
Optical flow
Optical flow or optic flow is the pattern of apparent motion of objects, surfaces, and edges in a visual scene caused by the relative motion between an observer and the scene. The concept of optical flow was first studied in the 1940s and ultimately published by American psychologist James J....
estimation developed by Bruce D. Lucas and Takeo Kanade
Takeo Kanade
is a Japanese computer scientist and one of the world's foremost researchers in computer vision. He is currently U.A. and Helen Whitaker Professor at Carnegie Mellon University...
. It assumes that the flow is essentially constant in a local neighbourhood of the pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
under consideration, and solves the basic optical flow equations for all the pixels in that neighbourhood, by the least squares criterion.
By combining information from several nearby pixels, the Lucas-Kanade method can often resolve the inherent ambiguity of the optical flow equation. It is also less sensitive to image noise than point-wise methods. On the other hand, since it is a purely local method, it cannot provide flow information in the interior of uniform regions of the image.
Concept
The Lucas-Kanade method assumes that the displacement of the image contents between two nearby instants (frames) is small and approximately constant within a neighborhood of the point p under consideration. Thus the optical flow equationOptical flow
Optical flow or optic flow is the pattern of apparent motion of objects, surfaces, and edges in a visual scene caused by the relative motion between an observer and the scene. The concept of optical flow was first studied in the 1940s and ultimately published by American psychologist James J....
can be assumed to hold for all pixels within a window centered at p. Namely, the local image flow (velocity) vector
must satisfywhere
are the pixels inside the window, and are the partial derivatives of the image with respect to position x, y and time t, evaluated at the point and at the current time.These equations can be written in matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
form
, whereThis system has more equations than unknowns and thus it is usually over-determined. The Lucas-Kanade method obtains a compromise solution
by the least squares principle. Namely, it solves the 2×2 system
orwhere
is the transpose of matrix . That is, it computeswith the sums running from i=1 to n.
The matrix
is often called the structure tensorStructure tensor
In mathematics, the structure tensor, also referred to as the second-moment matrix, is a matrix derived from the gradient of a function. It summarizes the predominant directions of the gradient in a specified neighborhood of a point, and the degree to which those directions are coherent...
of the image at the point p.
Weighted window
The plain least squares solution above gives the same importance to all n pixels in the window. In practice it is usually better to give more weight to the pixels that are closer to the central pixel p. For that, one uses the weighted version of the least squares equation,or
where
is an n×n diagonal matrixDiagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...
containing the weights
to be assigned to the equation of pixel . That is, it computesThe weight
is usually set to a Gaussian function of the distance between and p.Improvements and extensions
The least-squares approach implicitly assumes that the errors in the image data have a Gaussian distribution with zero mean. If one expects the window to contain a certain percentage of "outlierOutlier
In statistics, an outlier is an observation that is numerically distant from the rest of the data. Grubbs defined an outlier as: An outlying observation, or outlier, is one that appears to deviate markedly from other members of the sample in which it occurs....
s" (grossly wrong data values, that do not follow the "ordinary" Gaussian error distribution), one may use statistical analysis to detect them, and reduce their weight accordingly.
The Lucas-Kanade method per se can be used only when the image flow vector
between the two frames is small enough for the differential equation of the optical flow to hold, which is often less than the pixel spacing. When the flow vector may exceed this limit, such as in stereo matching or warped document registration, the Lucas-Kanade method may still be used to refine some coarse estimate of the same, obtained by other means; for example, by extrapolatingExtrapolation
In mathematics, extrapolation is the process of constructing new data points. It is similar to the process of interpolation, which constructs new points between known points, but the results of extrapolations are often less meaningful, and are subject to greater uncertainty. It may also mean...
the flow vectors computed for previous frames, or by running the Lucas-Kanade algorithm on reduced-scale versions of the images. Indeed, the latter method is the basis of the popular Kanade-Lucas-Tomasi (KLT) feature matching algorithm.
A similar technique can be used compute differential affine deformations of the image contents.
See also
- Optical flowOptical flowOptical flow or optic flow is the pattern of apparent motion of objects, surfaces, and edges in a visual scene caused by the relative motion between an observer and the scene. The concept of optical flow was first studied in the 1940s and ultimately published by American psychologist James J....
- Horn–Schunck method
- The Shi and Tomasi corner detection algorithm
External links
- Dor's Image Processing Site, Mandatory site for IP algorithm developers, by Dor Barber. Tel Aviv University. Updated 31 December 2010.
- The image stabilizer plugin for ImageJ based on the Lucas–Kanade method
- Mathworks Lucas-Kanade Matlab implementation of inverse and normal affineAffineAffine may refer to:*Affine cipher, a special case of the more general substitution cipher*Affine combination, a certain kind of constrained linear combination*Affine connection, a connection on the tangent bundle of a differentiable manifold...
Lucas-Kanade - The French Aerospace Lab : GPU implementation of a Lucas-Kanade based optical flow
- Lucas-Kanade for the iPhone by Success Labs. A modified and enhanced port of the OpenCV lkdemo sample application to the iPhone.
- KLT: An Implementation of the Kanade–Lucas–Tomasi Feature Tracker
- Takeo Kanade