doc/tutorials/video/optical_flow/optical_flow.markdown

   1 Optical Flow {#tutorial_optical_flow}
   2 ============
   3
   4 @prev_tutorial{tutorial_meanshift}
   5
   6 Goal
   7 ----
   8
   9 In this chapter,
  10     -   We will understand the concepts of optical flow and its estimation using Lucas-Kanade
  11         method.
  12     -   We will use functions like **cv.calcOpticalFlowPyrLK()** to track feature points in a
  13         video.
  14     -   We will create a dense optical flow field using the **cv.calcOpticalFlowFarneback()** method.
  15
  16 Optical Flow
  17 ------------
  18
  19 Optical flow is the pattern of apparent motion of image objects between two consecutive frames
  20 caused by the movement of object or camera. It is 2D vector field where each vector is a
  21 displacement vector showing the movement of points from first frame to second. Consider the image
  22 below (Image Courtesy: [Wikipedia article on Optical Flow](http://en.wikipedia.org/wiki/Optical_flow)).
  23
  24 ![image](images/optical_flow_basic1.jpg)
  25
  26 It shows a ball moving in 5 consecutive frames. The arrow shows its displacement vector. Optical
  27 flow has many applications in areas like :
  28
  29 -   Structure from Motion
  30 -   Video Compression
  31 -   Video Stabilization ...
  32
  33 Optical flow works on several assumptions:
  34
  35 -#  The pixel intensities of an object do not change between consecutive frames.
  36 2.  Neighbouring pixels have similar motion.
  37
  38 Consider a pixel \f$I(x,y,t)\f$ in first frame (Check a new dimension, time, is added here. Earlier we
  39 were working with images only, so no need of time). It moves by distance \f$(dx,dy)\f$ in next frame
  40 taken after \f$dt\f$ time. So since those pixels are the same and intensity does not change, we can say,
  41
  42 \f[I(x,y,t) = I(x+dx, y+dy, t+dt)\f]
  43
  44 Then take taylor series approximation of right-hand side, remove common terms and divide by \f$dt\f$ to
  45 get the following equation:
  46
  47 \f[f_x u + f_y v + f_t = 0 \;\f]
  48
  49 where:
  50
  51 \f[f_x = \frac{\partial f}{\partial x} \; ; \; f_y = \frac{\partial f}{\partial y}\f]\f[u = \frac{dx}{dt} \; ; \; v = \frac{dy}{dt}\f]
  52
  53 Above equation is called Optical Flow equation. In it, we can find \f$f_x\f$ and \f$f_y\f$, they are image
  54 gradients. Similarly \f$f_t\f$ is the gradient along time. But \f$(u,v)\f$ is unknown. We cannot solve this
  55 one equation with two unknown variables. So several methods are provided to solve this problem and
  56 one of them is Lucas-Kanade.
  57
  58 ### Lucas-Kanade method
  59
  60 We have seen an assumption before, that all the neighbouring pixels will have similar motion.
  61 Lucas-Kanade method takes a 3x3 patch around the point. So all the 9 points have the same motion. We
  62 can find \f$(f_x, f_y, f_t)\f$ for these 9 points. So now our problem becomes solving 9 equations with
  63 two unknown variables which is over-determined. A better solution is obtained with least square fit
  64 method. Below is the final solution which is two equation-two unknown problem and solve to get the
  65 solution.
  66
  67 \f[\begin{bmatrix} u \\ v \end{bmatrix} =
  68 \begin{bmatrix}
  69     \sum_{i}{f_{x_i}}^2  &  \sum_{i}{f_{x_i} f_{y_i} } \\
  70     \sum_{i}{f_{x_i} f_{y_i}} & \sum_{i}{f_{y_i}}^2
  71 \end{bmatrix}^{-1}
  72 \begin{bmatrix}
  73     - \sum_{i}{f_{x_i} f_{t_i}} \\
  74     - \sum_{i}{f_{y_i} f_{t_i}}
  75 \end{bmatrix}\f]
  76
  77 ( Check similarity of inverse matrix with Harris corner detector. It denotes that corners are better
  78 points to be tracked.)
  79
  80 So from the user point of view, the idea is simple, we give some points to track, we receive the optical
  81 flow vectors of those points. But again there are some problems. Until now, we were dealing with
  82 small motions, so it fails when there is a large motion. To deal with this we use pyramids. When we go up in
  83 the pyramid, small motions are removed and large motions become small motions. So by applying
  84 Lucas-Kanade there, we get optical flow along with the scale.
  85
  86 Lucas-Kanade Optical Flow in OpenCV
  87 -----------------------------------
  88
  89 OpenCV provides all these in a single function, **cv.calcOpticalFlowPyrLK()**. Here, we create a
  90 simple application which tracks some points in a video. To decide the points, we use
  91 **cv.goodFeaturesToTrack()**. We take the first frame, detect some Shi-Tomasi corner points in it,
  92 then we iteratively track those points using Lucas-Kanade optical flow. For the function
  93 **cv.calcOpticalFlowPyrLK()** we pass the previous frame, previous points and next frame. It
  94 returns next points along with some status numbers which has a value of 1 if next point is found,
  95 else zero. We iteratively pass these next points as previous points in next step. See the code
  96 below:
  97
  98 @add_toggle_cpp
  99 -   **Downloadable code**: Click
 100     [here](https://github.com/opencv/opencv/tree/3.4/samples/cpp/tutorial_code/video/optical_flow/optical_flow.cpp)
 101
 102 -   **Code at glance:**
 103     @include samples/cpp/tutorial_code/video/optical_flow/optical_flow.cpp
 104 @end_toggle
 105
 106 @add_toggle_python
 107 -   **Downloadable code**: Click
 108     [here](https://github.com/opencv/opencv/tree/3.4/samples/python/tutorial_code/video/optical_flow/optical_flow.py)
 109
 110 -   **Code at glance:**
 111     @include samples/python/tutorial_code/video/optical_flow/optical_flow.py
 112 @end_toggle
 113
 114
 115 @add_toggle_java
 116 -   **Downloadable code**: Click
 117     [here](https://github.com/opencv/opencv/tree/3.4/samples/java/tutorial_code/video/optical_flow/OpticalFlowDemo.java)
 118
 119 -   **Code at glance:**
 120     @include samples/java/tutorial_code/video/optical_flow/OpticalFlowDemo.java
 121 @end_toggle
 122
 123 (This code doesn't check how correct are the next keypoints. So even if any feature point disappears
 124 in image, there is a chance that optical flow finds the next point which may look close to it. So
 125 actually for a robust tracking, corner points should be detected in particular intervals. OpenCV
 126 samples comes up with such a sample which finds the feature points at every 5 frames. It also run a
 127 backward-check of the optical flow points got to select only good ones. Check
 128 samples/python/lk_track.py).
 129
 130 See the results we got:
 131
 132 ![image](images/opticalflow_lk.jpg)
 133
 134 Dense Optical Flow in OpenCV
 135 ----------------------------
 136
 137 Lucas-Kanade method computes optical flow for a sparse feature set (in our example, corners detected
 138 using Shi-Tomasi algorithm). OpenCV provides another algorithm to find the dense optical flow. It
 139 computes the optical flow for all the points in the frame. It is based on Gunner Farneback's
 140 algorithm which is explained in "Two-Frame Motion Estimation Based on Polynomial Expansion" by
 141 Gunner Farneback in 2003.
 142
 143 Below sample shows how to find the dense optical flow using above algorithm. We get a 2-channel
 144 array with optical flow vectors, \f$(u,v)\f$. We find their magnitude and direction. We color code the
 145 result for better visualization. Direction corresponds to Hue value of the image. Magnitude
 146 corresponds to Value plane. See the code below:
 147
 148 @add_toggle_cpp
 149 -   **Downloadable code**: Click
 150     [here](https://github.com/opencv/opencv/tree/3.4/samples/cpp/tutorial_code/video/optical_flow/optical_flow_dense.cpp)
 151
 152 -   **Code at glance:**
 153     @include samples/cpp/tutorial_code/video/optical_flow/optical_flow_dense.cpp
 154 @end_toggle
 155
 156 @add_toggle_python
 157 -   **Downloadable code**: Click
 158     [here](https://github.com/opencv/opencv/tree/3.4/samples/python/tutorial_code/video/optical_flow/optical_flow_dense.py)
 159
 160 -   **Code at glance:**
 161     @include samples/python/tutorial_code/video/optical_flow/optical_flow_dense.py
 162 @end_toggle
 163
 164
 165 @add_toggle_java
 166 -   **Downloadable code**: Click
 167     [here](https://github.com/opencv/opencv/tree/3.4/samples/java/tutorial_code/video/optical_flow/OpticalFlowDenseDemo.java)
 168
 169 -   **Code at glance:**
 170     @include samples/java/tutorial_code/video/optical_flow/OpticalFlowDenseDemo.java
 171 @end_toggle
 172
 173
 174 See the result below:
 175
 176 ![image](images/opticalfb.jpg)