OpenCV  4.5.2
Open Source Computer Vision
Optical Flow

Prev Tutorial: Meanshift and Camshift
Next Tutorial: Cascade Classifier

Goal

In this chapter,

  • We will understand the concepts of optical flow and its estimation using Lucas-Kanade method.
  • We will use functions like cv.calcOpticalFlowPyrLK() to track feature points in a video.
  • We will create a dense optical flow field using the cv.calcOpticalFlowFarneback() method.

Optical Flow

Optical flow is the pattern of apparent motion of image objects between two consecutive frames caused by the movement of object or camera. It is 2D vector field where each vector is a displacement vector showing the movement of points from first frame to second. Consider the image below (Image Courtesy: Wikipedia article on Optical Flow).

image

It shows a ball moving in 5 consecutive frames. The arrow shows its displacement vector. Optical flow has many applications in areas like :

  • Structure from Motion
  • Video Compression
  • Video Stabilization ...

Optical flow works on several assumptions:

  1. The pixel intensities of an object do not change between consecutive frames.
  2. Neighbouring pixels have similar motion.

Consider a pixel \(I(x,y,t)\) in first frame (Check a new dimension, time, is added here. Earlier we were working with images only, so no need of time). It moves by distance \((dx,dy)\) in next frame taken after \(dt\) time. So since those pixels are the same and intensity does not change, we can say,

\[I(x,y,t) = I(x+dx, y+dy, t+dt)\]

Then take taylor series approximation of right-hand side, remove common terms and divide by \(dt\) to get the following equation:

\[f_x u + f_y v + f_t = 0 \;\]

where:

\[f_x = \frac{\partial f}{\partial x} \; ; \; f_y = \frac{\partial f}{\partial y}\]

\[u = \frac{dx}{dt} \; ; \; v = \frac{dy}{dt}\]

Above equation is called Optical Flow equation. In it, we can find \(f_x\) and \(f_y\), they are image gradients. Similarly \(f_t\) is the gradient along time. But \((u,v)\) is unknown. We cannot solve this one equation with two unknown variables. So several methods are provided to solve this problem and one of them is Lucas-Kanade.

Lucas-Kanade method

We have seen an assumption before, that all the neighbouring pixels will have similar motion. Lucas-Kanade method takes a 3x3 patch around the point. So all the 9 points have the same motion. We can find \((f_x, f_y, f_t)\) for these 9 points. So now our problem becomes solving 9 equations with two unknown variables which is over-determined. A better solution is obtained with least square fit method. Below is the final solution which is two equation-two unknown problem and solve to get the solution.

\[\begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} \sum_{i}{f_{x_i}}^2 & \sum_{i}{f_{x_i} f_{y_i} } \\ \sum_{i}{f_{x_i} f_{y_i}} & \sum_{i}{f_{y_i}}^2 \end{bmatrix}^{-1} \begin{bmatrix} - \sum_{i}{f_{x_i} f_{t_i}} \\ - \sum_{i}{f_{y_i} f_{t_i}} \end{bmatrix}\]

( Check similarity of inverse matrix with Harris corner detector. It denotes that corners are better points to be tracked.)

So from the user point of view, the idea is simple, we give some points to track, we receive the optical flow vectors of those points. But again there are some problems. Until now, we were dealing with small motions, so it fails when there is a large motion. To deal with this we use pyramids. When we go up in the pyramid, small motions are removed and large motions become small motions. So by applying Lucas-Kanade there, we get optical flow along with the scale.

Lucas-Kanade Optical Flow in OpenCV

OpenCV provides all these in a single function, cv.calcOpticalFlowPyrLK(). Here, we create a simple application which tracks some points in a video. To decide the points, we use cv.goodFeaturesToTrack(). We take the first frame, detect some Shi-Tomasi corner points in it, then we iteratively track those points using Lucas-Kanade optical flow. For the function cv.calcOpticalFlowPyrLK() we pass the previous frame, previous points and next frame. It returns next points along with some status numbers which has a value of 1 if next point is found, else zero. We iteratively pass these next points as previous points in next step. See the code below:

(This code doesn't check how correct are the next keypoints. So even if any feature point disappears in image, there is a chance that optical flow finds the next point which may look close to it. So actually for a robust tracking, corner points should be detected in particular intervals. OpenCV samples comes up with such a sample which finds the feature points at every 5 frames. It also run a backward-check of the optical flow points got to select only good ones. Check samples/python/lk_track.py).

See the results we got:

image

Dense Optical Flow in OpenCV

Lucas-Kanade method computes optical flow for a sparse feature set (in our example, corners detected using Shi-Tomasi algorithm). OpenCV provides another algorithm to find the dense optical flow. It computes the optical flow for all the points in the frame. It is based on Gunner Farneback's algorithm which is explained in "Two-Frame Motion Estimation Based on Polynomial Expansion" by Gunner Farneback in 2003.

Below sample shows how to find the dense optical flow using above algorithm. We get a 2-channel array with optical flow vectors, \((u,v)\). We find their magnitude and direction. We color code the result for better visualization. Direction corresponds to Hue value of the image. Magnitude corresponds to Value plane. See the code below:

See the result below:

image
cv::RNG::uniform
int uniform(int a, int b)
returns uniformly distributed integer random number from [a,b) range
cv::String
std::string String
Definition: cvstd.hpp:150
cv::Mat::clone
Mat clone() const CV_NODISCARD
Creates a full copy of the array and the underlying data.
cv::TermCriteria
The class defining termination criteria for iterative algorithms.
Definition: types.hpp:852
cv::NORM_MINMAX
@ NORM_MINMAX
flag
Definition: base.hpp:207
cv::cvtColor
void cvtColor(InputArray src, OutputArray dst, int code, int dstCn=0)
Converts an image from one color space to another.
cv::samples::findFile
cv::String findFile(const cv::String &relative_path, bool required=true, bool silentMode=false)
Try to find requested data file.
cv::Mat::zeros
static MatExpr zeros(int rows, int cols, int type)
Returns a zero array of the specified size and type.
cv::split
void split(const Mat &src, Mat *mvbegin)
Divides a multi-channel array into several single-channel arrays.
cv::goodFeaturesToTrack
void goodFeaturesToTrack(InputArray image, OutputArray corners, int maxCorners, double qualityLevel, double minDistance, InputArray mask=noArray(), int blockSize=3, bool useHarrisDetector=false, double k=0.04)
Determines strong corners on an image.
cv::normalize
void normalize(const SparseMat &src, SparseMat &dst, double alpha, int normType)
cv::VideoCapture
Class for video capturing from video files, image sequences or cameras.
Definition: videoio.hpp:664
cv::waitKey
int waitKey(int delay=0)
Waits for a pressed key.
cv::TermCriteria::COUNT
@ COUNT
the maximum number of iterations or elements to compute
Definition: types.hpp:860
cv::TermCriteria::EPS
@ EPS
the desired accuracy or change in parameters at which the iterative algorithm stops
Definition: types.hpp:862
CV_8U
#define CV_8U
Definition: interface.h:73
video.hpp
cv::calcOpticalFlowFarneback
void calcOpticalFlowFarneback(InputArray prev, InputArray next, InputOutputArray flow, double pyr_scale, int levels, int winsize, int iterations, int poly_n, double poly_sigma, int flags)
Computes a dense optical flow using the Gunnar Farneback's algorithm.
highgui.hpp
core.hpp
cv::Mat::convertTo
void convertTo(OutputArray m, int rtype, double alpha=1, double beta=0) const
Converts an array to another data type with optional scaling.
cv::Size
Size2i Size
Definition: types.hpp:347
cv::line
void line(InputOutputArray img, Point pt1, Point pt2, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
Draws a line segment connecting two points.
CV_32F
#define CV_32F
Definition: interface.h:78
cv::COLOR_HSV2BGR
@ COLOR_HSV2BGR
backward conversions HSV to RGB/BGR with H range 0..180 if 8 bit image
Definition: imgproc.hpp:605
cv::Mat::size
MatSize size
Definition: mat.hpp:2118
CV_32FC2
#define CV_32FC2
Definition: interface.h:119
cv::magnitude
void magnitude(InputArray x, InputArray y, OutputArray magnitude)
Calculates the magnitude of 2D vectors.
uint
uint32_t uint
Definition: interface.h:42
cv::imshow
void imshow(const String &winname, InputArray mat)
Displays an image in the specified window.
cv::merge
void merge(const Mat *mv, size_t count, OutputArray dst)
Creates one multi-channel array out of several single-channel ones.
cv::Scalar
Scalar_< double > Scalar
Definition: types.hpp:669
cv::RNG
Random Number Generator.
Definition: core.hpp:2782
cv::Point
Point2i Point
Definition: types.hpp:194
cv::Mat
n-dimensional dense array class
Definition: mat.hpp:801
cv::imshow
void imshow(const String &winname, const ogl::Texture2D &tex)
Displays OpenGL 2D texture in the specified window.
cv::goodFeaturesToTrack
void goodFeaturesToTrack(InputArray image, OutputArray corners, int maxCorners, double qualityLevel, double minDistance, InputArray mask, OutputArray cornersQuality, int blockSize=3, int gradientSize=3, bool useHarrisDetector=false, double k=0.04)
Same as above, but returns also quality measure of the detected corners.
cv::CommandLineParser
Designed for command line parsing.
Definition: utility.hpp:799
cv::COLOR_BGR2GRAY
@ COLOR_BGR2GRAY
convert between RGB/BGR and grayscale, color conversions
Definition: imgproc.hpp:551
cv::imwrite
bool imwrite(const String &filename, InputArray img, const std::vector< int > &params=std::vector< int >())
Saves an image to a specified file.
cv
"black box" representation of the file storage associated with a file on disk.
Definition: affine.hpp:51
imgproc.hpp
cv::calcOpticalFlowPyrLK
void calcOpticalFlowPyrLK(InputArray prevImg, InputArray nextImg, InputArray prevPts, InputOutputArray nextPts, OutputArray status, OutputArray err, Size winSize=Size(21, 21), int maxLevel=3, TermCriteria criteria=TermCriteria(TermCriteria::COUNT+TermCriteria::EPS, 30, 0.01), int flags=0, double minEigThreshold=1e-4)
Calculates an optical flow for a sparse feature set using the iterative Lucas-Kanade method with pyra...
cv::Mat::ones
static MatExpr ones(int rows, int cols, int type)
Returns an array of all 1's of the specified size and type.
cv::gapi::mask
GMat mask(const GMat &src, const GMat &mask)
Applies a mask to a matrix.
cv::normalize
static Vec< _Tp, cn > normalize(const Vec< _Tp, cn > &v)
cv::add
void add(InputArray src1, InputArray src2, OutputArray dst, InputArray mask=noArray(), int dtype=-1)
Calculates the per-element sum of two arrays or an array and a scalar.
videoio.hpp
cv::cartToPolar
void cartToPolar(InputArray x, InputArray y, OutputArray magnitude, OutputArray angle, bool angleInDegrees=false)
Calculates the magnitude and angle of 2D vectors.
cv::circle
void circle(InputOutputArray img, Point center, int radius, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
Draws a circle.