Algorithm Overview
This article presents a basic Python demonstration of the popular Lucas Kanade tracking algorithm. Lucas Kanade algorithm is an optical flow based feature tracking technique for video. Starting with an assumption that the tracked feature's movement between two sequential frames is very small, this algorithm attempts to calculate the velocity vector \( (u,v) )\ for every tracked feature. The features are usually represented by \( nxn )\ pixel blocks. At the first frame, initial positions of these features are given as algorithm inputs. For every next frame the algorithm updates those positions using a velocity vector calculated at every frame.
The algorithm assumes that the following equation is valid for any pixel in any tracked feature:
$$ \Delta B_x (x,y) \cdot v_x + \Delta B_y (x,y) \cdot v_y = -\Delta B_t (x,y) $$
where:
\( \Delta B_x (x,y) )\ is the increase in brightness in x direction at pixel position \( (x,y) )\
\( \Delta B_y (x,y) )\ is the increase in brightness in y direction at pixel position \( (x,y) )\
\(\Delta B_t (x,y))\ is the increase in brightness between the pixel at position \((x,y))\ in the next frame \( t_{2} )\ and the current frame \( t_{1} )\
The equation above refers to a single pixel inside the tracked region. For all pixels inside the tracked feature, a set of such equations is needed. These equations can be written in a matrix form:
$$ \begin{bmatrix} \Delta B_{x,1} (x,y) & \Delta B_{y,1} (x,y) \\\ \Delta B_{x,2} (x,y) & \Delta B_{y,2} (x,y) \\\ ... & ...\\\ \Delta B_{x,n} (x,y) & \Delta B_{y,n} (x,y) \end{bmatrix} \begin{bmatrix} v_{x} \\\ v_{y} \end{bmatrix} = - \begin{bmatrix} \Delta B_{t,1} (x,y) \\\ \Delta B_{t,2} (x,y) \\\ ... \\\ \Delta B_{t,n} (x,y) \end{bmatrix} $$
The equation above can be also written as:
$$ \boldsymbol {S} \boldsymbol{v} = \boldsymbol{t} $$
The velocity vector \( \boldsymbol{v} )\ can be calculated from this expression. Since this system of linear equations is overdetermined, \( \boldsymbol{v} )\ can be calculated using the least-squares method:
$$ \boldsymbol{v} = (\boldsymbol{S}\boldsymbol{S^T})^{-1} \boldsymbol{S^T} \boldsymbol{t} $$
Once \(\boldsymbol{v})\ for a tracked feature is known, its position can be updated for the next frame.
Sample Frame Render
Here is a sample frame rendered by the program:
The gray boxes represent the starting positions of the tracked areas. The white boxes represent the current positions. The red lines represent the vectors of movement.
Assumptions
1. All the changes in brightness (intensity) between two consecutive frames can be explained by the movement of object relative to the camera or vice versa.
2. If we assume that brightness is increasing from left to right, and from top to bottom, then the total increase of brightness can be expressed as a negative sum of the increase by x and the increase by y for every pixel
3. Not all regions are suited for this algorithm. For example, random pixel regions or empty regions are not good candidates.
4. The suitability of a region ( features ) can be verified by computing the eigenvalues of the matrix \( \boldsymbol{S}\boldsymbol{S^T} )\. If the smallest eigenvalue is very small, the matrix is ill-conditioned and cannot be used for the velocity vector computation. The easiest solution is to change the initial feature position for a trackable one.
5. Speed is represented in x pixels per frame and y pixels per frame
References:
2. Lucas-Kanade method - Wikipedia
Source code:
Source code can be downloaded from GitHub.