In this tutorial, we’ll review the Lukas-Kanade method, a widely used computer vision technique for estimating optical flow. First, we explain the concept of optical flow. Then, we provide a mathematical description of the Lukas-Kanade method.
2. Optical Flow
Optical flow is a computer vision tool for describing the motion of objects in a video sequence. It refers to the pattern of apparent motion of objects between two consecutive frames caused by the camera’s movement or the objects themselves. Hence, the optical flow is a vector field describing the displacement of each pixel between two consecutive frames. Hence, it allows for determining how the objects in the scene move.
The optical flow is generally computed using the brightness constancy constraint. This is assumptions states the a point at location and time will have moved by in the short time interval and its brightness remains the same, i.e.:
Using the Taylor expansion of eq. (1) the optical flow equation can be easily obtained:
where , , are the partial derivative of the image intensity respect to , and , while , are the and components of the optical flow. Eq. (2) has two unknowns. Hence it cannot be solved as such. This issue is called the aperture problem.
Optical flow is used in several computer applications, such as object tracking, motion detection, stereo disparity measurement, and video compression.
3. Lucas-Kanade Method
The Lucas-Kanade method assumes that the optical flow , is constant within a small window of size pixels. Hence, the optical flow equation holds for all pixels of coordinates q = (k, l) within the window W:
These equations form a linear system that can be written in matrix form:
where is a matrix of size containing the image gradient components evaluated for each pixel of the window :
is the vector representing the optical flow of the window that we are going to estimate:
and is a vector of size containing image derivative with respect to time evaluated for each pixel of the window :
This linear system has equations and two unknowns. Hence it is over-determined. The Lucas-Kanade method finds the least square solution of eq. (4) by solving the following linear system:
where is the transpose of . The least-square solution is:
4. Working Condition
The optical flow can be estimated if the matrix is invertible and well-conditioned. This latter condition occurs when the eigenvalues and of the matrix are both large and of the same order of magnitude. This is the same condition used for Corner Detection. Hence, the optical flow can be estimated efficiently within a window containing a corner.
Conversely, if the window is a smooth region or contains an edge, the motion cannot be detected safely.
In this article, we reviewed the Lucas-Kanade method, a fundamental technique in computer vision. We explained the concept of optical flow and the mathematical formulation of the Lucas-Kanade method.