Optical Flow: Lucas-Kanade Method

1. Overview

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 (x,y) and time will have moved by $\Delta x, \Delta y)$ in the short time interval $\Delta t$ and its brightness remains the same, i.e.:

(1) $\begin{equation*}{ I(x, y, t)=I(x+\Delta x, y+\Delta y, t+\Delta t) .$$ }\end{equation*}$

Using the Taylor expansion of eq. (1) the optical flow equation can be easily obtained:

(2) $\begin{equation*} I_x v_x + I_y v_y+I_t=0 \end{equation*}$

where I_x , I_y , I_t are the partial derivative of the image intensity respect to , and , while v_x , v_y 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 $\mathbf{v_x}$ , $\mathbf{v_y}$ is constant within a small window $\mathbf{W}$ of size $\mathbf{n \times n}$ pixels. Hence, the optical flow equation holds for all pixels of coordinates q = (k, l) within the window W:

(3) $\begin{equation*} I_x(q) v_x + I_y(q) v_y= - I_t(q) \ \ \ \ \forall q=(k, l) \in W \end{equation*}$

These equations form a linear system that can be written in matrix form:

(4) $\begin{equation*} A v=b \end{equation*}$

where is a matrix of size $n^2 \times 2$ containing the image gradient components evaluated for each pixel of the window :

(5) $\begin{equation*} A=\left[\begin{array}{cc} I_x\left(q_1\right) & I_y\left(q_1\right) \\ I_x\left(q_2\right) & I_y\left(q_2\right) \\ \vdots & \vdots \\ I_x\left(q_n\right) & I_y\left(q_n\right) \end{array}\right] \end{equation*}$

is the vector representing the optical flow of the window that we are going to estimate:

(6) $\begin{equation*} v=\left[\begin{array}{c} v_x \\ v_y \end{array}\right] \end{equation*}$

and is a vector of size n^2 containing image derivative with respect to time evaluated for each pixel of the window :

(7) $\begin{equation*} b=\left[\begin{array}{c} -I_t\left(q_1\right) \\ -I_t\left(q_2\right) \\ \vdots \\ -I_t\left(q_n\right) \end{array}\right] . \end{equation*}$

This linear system has n^2 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 $\mathbf{2 \times 2}$ linear system:

(8) $\begin{equation*} A^T A v= A^T b \end{equation*}$

where A^T is the transpose of . The least-square solution is:

(9) $\begin{equation*} \mathrm{v}=\left(A^T A\right)^{-1} A^T b = \left[\begin{array}{cc}\sum_i I_x\left(q_i\right)^2 & \sum_i I_x\left(q_i\right) I_y\left(q_i\right) \\ \sum_i I_y\left(q_i\right) I_x\left(q_i\right) & \sum_i I_y\left(q_i\right)^2\end{array}\right]^{-1}\left[\begin{array}{c}-\sum_i I_x\left(q_i\right) I_t\left(q_i\right) \\ -\sum_i I_y\left(q_i\right) I_t\left(q_i\right)\end{array}\right] \end{equation*}$

4. Working Condition

The optical flow $\mathbf{v}$ can be estimated if the matrix $\mathbf{A^T A}$ is invertible and well-conditioned. This latter condition occurs when the eigenvalues $\lambda_1$ and $\lamda_2$ of the matrix A^T A 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.

5. Conclusion

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.

Persistence

REST

Security

1. Overview

2. Optical Flow

3. Lucas-Kanade Method

4. Working Condition

5. Conclusion