Lucas–Kanade method for Optical Flow

DeepSORT is one of the finest object tracking algorithm. However, there are some assumptions in DeepSORT, for example, there should be no ego-motion. Ego-motion in simple words mean that camera should be stationary. Also, DeepSORT tracks only person. For any other object we would need to train it again.

Optical Flow

The actual or observed (relative motion) between objects and observer (camera) is known as optical flow. If the camera is moving and the object is stationary then also we will stay that we have optical flow. Generally speaking, optical flow is caused by the movement of the foreground object itself, the movement of the — camera, or the joint movement of the two in the scene. Lucas-Kanade method is the preferred algorithm to track points on a video.

Lucas-Kanade

Lucas Kanade Method is based on something known as Brightness constancy assumption. The key idea here is that pixel level brightness won’t change a lot in just one frame. It assumes that the color of an object does not change significantly and significantly in the previous two frames.

Optical flow is only valid in regions where

When eigenvalues are small, there is no gradient in all directions, it is likely we are looking at pixels over a flat area that don’t show any correlation, like the river in the image above. When eigenvalues show a large ratio, 1 strong, 1 weak gradient, it means we’re looking at an edge, eg the riverbank. This collection is only useful for determining either u or v but not both since we can clearly see when we move laterally, but if we move up the edge, from the camera’s point-of-view we might not be moving at all.

Where we find large eigenvalues, that’s where we know it is a highly textured region of the image that serves as a good collection of pixels to track.

Another assumption made by single-level Lucas-Kanade method is that the motion of the moving object(s) in between consecutive frames is slow. If the motion amplitude of the pixel is too large and it moves outside the local window, the algorithm will not be able to find it.

This problem has led to the development of the pyramid-LK algorithm, which starts tracking from the lowest detail of the image pyramid and gradually tracks to finer details. The tracking image pyramid allows large movements to be captured by the partial window.

It is realized by reducing the speed of the objects in the image. An intuitive way is to reduce the size of the image. Suppose that when the image is 400×400, the object speed is [16 16], then when the image is reduced to 200×200, the speed becomes [8,8]. Therefore, optical flow can be obtained by generating a pyramid image of the original image, solving layer by layer, and continuously accurate.

Optical Flow Function:

def optical_flow(I1, I2, , input_point, window_size, max_level,τ) # returns (next_point)

Parameters

I1, I2 — Two images taken at times t = 1 and t = 2 respectively.

window_size — Size of the search window at each pyramid level.

input_point — Vector of 2D points for which the flow needs to be found.

max_level — 0-based maximal pyramid level number; if set to 0, pyramids are not used (single level), if set to 1, two levels are used, and so on.

τ — Threshold such that if τ is larger than the smallest eigenvalue of A’A, then the optical flow at that position should not be computed.

next_point — Output vector of 2D points (x and y components of optical flow) containing the calculated new positions of input features in the second image.

This article gave a conceptual introduction to optical flow and Lucas-Kanade method to track objects using multiple-scale version Lucas-Kanade with image pyramids. Next articles will give a practical demonstration of Lucas-Kanade method to track objects in a video.