Lucas-Kanade

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

The algorithm makes the following assumptions:

• Brightness does not change between consecutive images;
• The two images must be close in time so that 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 next image. Using a first-order Taylor series 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 a change in the brightness of a pixel in the scene is fully compensated for by the scene's own gradient, 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)$.

A single pixel clearly does not contain enough information to solve this problem. To gather more observations, we assume that the pixels in a neighborhood move together, 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 whose motion is to be 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 interest points used by Shi-Tomasi or Harris (see 6.2): points selected using this matrix can be tracked reliably with the Lucas-Kanade algorithm.

When motion exceeds one pixel, an iterative algorithm is needed to solve the problem, along 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 consecutive images is small enough to be approximated by a first-order Taylor expansion. When motion exceeds a few pixels, this assumption no longer holds, and the procedure may converge to undesirable local minima.

Image pyramids are commonly used to overcome this limitation. Motion is first estimated at lower resolutions, where apparent displacements are smaller, and 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 is the choice of points to track. As observed by Tomasi and Kanade, not all image points provide reliable motion estimates. Uniform regions or those containing a single edge produce ill-conditioned systems and unstable results. It is therefore useful to first select keypoints with significant intensity variation in multiple directions.

This observation led to the development of the Kanade-Lucas-Tomasi (KLT) tracker, which uses a keypoint detector, typically Shi-Tomasi or Harris, to select features to track, while Lucas-Kanade estimates 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.