Lucas-Kanade

The Lucas-Kanade optical-flow estimation method (LK81) estimates the motion of salient features in successive frames of a video. Its objective is to associate a motion vector $(u,v)$ with each “interesting” pixel in the scene by comparing two consecutive images.

The algorithm makes the following assumptions:

• The brightness does not change between consecutive images;
• The two images must be sufficiently close in time that the objects do not undergo significant displacement (the algorithm works well with slowly moving objects);
• The image contains objects with sufficient grayscale texture (the original algorithm does not explicitly use color) whose gradient changes gradually.

Starting from the optical-flow equation for each point $(x,y)$:

$$I (x + u\delta t, y + v\delta t, t + \delta t) = I(x,y,t)$$ (8.2)

where $I(t)$ is an image and $I(t + \delta t)$ is the subsequent one. Using a first-order Taylor expansion:

$$\begin{array}{l} I (x + u\delta t, y + v\delta t, t + \delt... ...,y,t) v + \frac{\partial I}{\partial t} (x,y,t) = 0 \end{array}$$ (8.3)

The Lucas-Kanade algorithm assumes that the change in a scene pixel's brightness is fully compensated by the scene gradient itself, that is,

$$I_x u + I_y v + I_t = 0$$ (8.4)

given the temporal gradient $I_t$ and the spatial gradient $(I_x,I_y)$.

Obviously, a single pixel does not contain enough information to solve this problem. To collect more observations, it is assumed that a neighborhood of the pixel undergoes the same motion, that is,

$$\begin{bmatrix} I_x(\mathbf{p}_1) & I_y(\mathbf{p}_1) \\ ... ... (\mathbf{p}_2) \\ \vdots \\ I_t (\mathbf{p}_n) \end{bmatrix}$$ (8.5)

where $\mathbf{p}_1 \ldots \mathbf{p}_n$ are the points in the neighborhood of the point being estimated. The solution can be obtained using the normal equations method:

$$\begin{bmatrix} \sum I_x^2 & \sum I_x I_y \\ \sum I_x I_... ... \begin{bmatrix} \sum I_x I_t \\ \sum I_y I_t \end{bmatrix}$$ (8.6)

This is also the matrix of keypoints subsequently used by Shi-Tomasi or Harris (see 6.2): the keypoints associated with this matrix are points that can be tracked easily with the Lucas-Kanade algorithm.

When the motion is greater than one pixel, an iterative algorithm is required to solve the problem, together with a coarse-to-fine approach to avoid local minima: there will be a scale at which the pixel motion is less than one pixel.

The original Lucas-Kanade algorithm assumes that the displacement between two consecutive images is sufficiently small to be approximated by a first-order Taylor expansion. When the motion exceeds a few pixels, this assumption is no longer valid, and the procedure may converge to undesirable local minima.

Image pyramids are normally used to overcome this limitation. The motion is initially estimated at the lowest resolutions, where the apparent displacements are smaller, and is then refined at higher levels of detail. This approach, known as Pyramidal Lucas-Kanade, remains one of the most widely used implementations of the method.

Another issue concerns the choice of points to track. As observed by Tomasi and Kanade, not all image points provide a reliable motion estimate. Uniform regions or regions containing a single edge produce ill-conditioned systems and unstable results. For this reason, it is preferable to select in advance keypoints that exhibit significant intensity variations in multiple directions.

This observation led to the development of the Kanade-Lucas-Tomasi (KLT) tracker, in which a keypoint detector, typically Shi-Tomasi or Harris, is used to select the features to track, while Lucas-Kanade is used to estimate their motion between successive images. For many years, the KLT tracker was one of the fundamental tools for visual odometry, local feature tracking, and Structure from Motion applications.