Lucas Kanade method

From Wikipedia, the free encyclopedia

{tooshort} {context}

The Lucas-Kanade method is the still most popular version 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 + δ 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 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:

I (x, y, z, t) = I (x + δ x, y + δ y, z + δ z, t + δ 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$

$\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 x V x + I y V y + I z V z = - I t

$\nabla I\cdot\vec{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 \times m \times m$ with $m > 1$ , which is centered at voxel $x, y, z$ and numbering the pixels as $1... n$ , 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:

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

$A\vec{v}=-b$

To solve the over-determined system of equations, the least squares method is used:

$A^TA\vec{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} \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} \begin{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 Lukas-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.

[edit] 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.
KLT: An Implementation of the Kanade-Lucas-Tomasi Feature Tracker
Lucas B D 1984, Generalized Image Matching by the Method of Differences, doctoral dissertation

Retrieved from "http://en.wikipedia.org../../../l/u/c/Lucas_Kanade_method_90b1.html"

Category: Computer vision

Lucas Kanade method

From Wikipedia, the free encyclopedia

[edit] References

Views

Navigation

interaction

Search