About Opentopia
Opentopia Directory Encyclopedia Tools

Lucas Kanade method

Encyclopedia : L : LU : LUC : Lucas Kanade method

Optical flow methods try to calculate the motion between two image frames which are taken at times t and [t+\delta 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 [\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, 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\delta x+\frac\delta y+\frac\delta z+\frac\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\delta x+\frac\delta y+\frac\delta z+\frac\delta t = 0]
or
[\frac\frac+\frac\frac+\frac\frac+\frac\frac = 0]
which results in
[\fracV_x+\fracV_y+\fracV_z+\frac = 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], [\frac], [\frac] and [\frac] 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_xV_x+I_yV_y+I_zV_z=-I_t]
or
[\nabla I\cdot\vec = -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_ V_x + I_ V_y + I_ V_z = -I_]
[I_ V_x + I_ V_y + I_ V_z = -I_]
[\vdots]
[I_ V_x + I_ V_y + I_ V_z = -I_]
With this we get more then three equations for the three unknowns and thus an over-determined system. We get:
[\beginI_ & I_ & I_\\I_ & I_ & I_\\\vdots & \vdots & \vdots\\I_ & I_ & I_\end \beginV_x\\V_y\\V_z \end = \begin-I_\\ -I_\\ \vdots \\-I_\end ]
or
[A\vec=-b]
To solve the over-determined system of equations we use the least squares method:
[A^TA\vec=A^T(-b)] or
[ \vec=(A^TA)^A^T(-b) ]
or
[\beginV_x\\V_y\\V_z \end =\beginI_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^(-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. 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 compute 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 roboustness in presence of noise.

References

http://www.ces.clemson.edu/~stb/klt/



 





From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.
Search Titles
0123456789
ABCDEFGHIJ
KLMNOPQRST
UVWXYZ?

E-mail this article to:

Personal Message: