NationMaster - Encyclopedia: Lucas Kanade method

FACTOID # 64: Saudi diplomats have 367 unpaid parking fines in Britain.

Interesting crime facts »

Home

Encyclopedia

WHAT'S NEW

RECENT ARTICLES

More Recent Articles »

Encyclopedia > Lucas Kanade method

Lucas-Kanade method of estimating optical flow

Optical flow methods try to calculate the motion between two image frames which are taken at times t and $t + δ t$ at every pixel position. As a pixel at location (x,y,z,t) with intensity I(x,y,z,t) will have moved by $δ x$ , $δ y$ , $δ z$ and $δ t$ between the two frames, following image constraint equation can be given: Optical flow is a concept for considering the motion of objects within a visual representation. ...

I (x, y, z, t) = I (x + δ x, y + δ y, z + δ z, t + δ t)

Assuming the movement to be small enough, we can develop the image constraint at $I (x, y, z, t)$ with Taylor series 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 we achieve:

$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$

$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. We will write $I x$ , $I y$ , $I z$ and $I t$ for the derivatives in the following.

Thus

I x V x + I y V y + I z V z = - I t

$nabla 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 we need another set of equations which is 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 times m times m$ with $m > 1$ , which is centered at voxel $x, y, z$ and numbering the pixels as $1... n$ we get a set of equations:

$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 we get more then three equations for the three unknowns and thus an over-determined system. We get:

$begin{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} begin{bmatrix} V_x V_y V_z end{bmatrix} = begin{bmatrix} -I_{t_1} -I_{t_2} vdots -I_{t_n} end{bmatrix}$

$Avec{v}=-b$

To solve the over-determined system of equations we use the least squares method:

$A^TAvec{v}=A^T(-b)$ or

$vec{v}=(A^TA)^{-1}A^T(-b)$

$begin{bmatrix} V_x V_y V_z end{bmatrix} = begin{bmatrix} I_x^2 & I_xI_y & I_xI_z I_xI_y & I_y^2 & I_yI_z I_xI_z & I_yI_z & I_z^2 end{bmatrix}^{-1}(-A^TI_t)$

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.

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 roboustness in presence of noise.

Reference

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

COMMENTARY

Share your thoughts, questions and commentary here

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.