Lucas–Kanade method

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} = 0which 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_tor : abla Icdotvec{V} = -I_tThis 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::egin{bmatrix}I_{x_1} & I_{y_1} & I_{z_1}\I_{x_2} & I_{y_2} & I_{z_2}\vdots & vdots & vdots\I_{x_n} & I_{y_n} & I_{z_n}end{bmatrix} egin{bmatrix}V_x\V_y\V_z end{bmatrix} = egin{bmatrix}-I_{t_1}\ -I_{t_2}\ vdots \-I_{t_n}end{bmatrix} or:Avec{v}=-bTo 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:egin{bmatrix}V_x\V_y\V_z end{bmatrix} =egin{bmatrix}sum I_{x_i}^2 & sum I_{x_i}I_{y_i} & sum I_{x_i}I_{z_i} \sum I_{x_i}I_{y_i} & sum I_{y_i}^2 & sum I_{y_i}I_{z_i} \sum I_{x_i}I_{z_i} & sum I_{y_i}I_{z_i} & sum I_{z_i}^2 \end{bmatrix}^{-1}egin{bmatrix}-sum I_{x_i}I_{t_i} \-sum I_{y_i}I_{t_i} \-sum I_{z_i}I_{t_i}end{bmatrix}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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Lucas–Kanade — Алгоритм Лукаса Канаде широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока. Как известно, основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено.… …   Википедия

  • Lucas-Kanade-Methode — Die Lucas Kanade Methode zur Berechnung des optischen Flusses geht auf die beiden Forscher Bruce D Lucas und Takeo Kanade zurück. Sie schlugen diese Methode erstmals 1981 vor. Die Methode ist ein beliebtes Verfahren, das noch heute weite… …   Deutsch Wikipedia

  • Takeo Kanade — Infobox Scientist name = Takeo Kanade caption = birth date = 1945 birth place = Hyogo, Japan death date = death place = residence = United States citizenship = nationality = Japanese ethnicity = fields = Computer vision Robotics workplaces =… …   Wikipedia

  • Horn–Schunck method — The Horn–Schunck method of estimating optical flow is a global method which introduces a global constraint of smoothness to solve the aperture problem (see Lucas–Kanade method for further description).A global energy function is sought to be… …   Wikipedia

  • Takeo Kanade — (金出 武雄, Kanade Takeo?, né le 24 octobre 1945 à Hyōgo) est un informaticien japonais. Professeur à l Université Carnegie Mellon, il est l un des spécialistes parmi les plus reconnus en vision par ordinateur. Il a publié environ 300 articles de… …   Wikipédia en Français

  • Алгоритм Лукаса — Канаде широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока. Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса Канаде обходит… …   Википедия

  • Optical flow — The optic flow experienced by a rotating observer (in this case a fly). The direction and magnitude of optic flow at each location is represented by the direction and length of each arrow. Image taken from.[1] Optical flow or optic flow is the… …   Wikipedia

  • Structure tensor — Structure tensors (or second moment matrices) are matrix representations of partial derivatives. In the field of image processing and computer vision, they are typically used to represent gradients, edges or similar information. Structure tensors …   Wikipedia

  • Visual odometry — In robotics and computer vision, visual odometry is the process of determining the position and orientation of a robot by analyzing the associated camera images. It has been used in a wide variety of robotic applications, such as on the Mars… …   Wikipedia

  • History of robots — The history of robots date at least as far back as the ancient legends.Robotics in AntiquityLikely fictional, the Iliad illustrates the concept of robotics by stating that the god Hephaestus made talking mechanical handmaidens out of gold. cite… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”