doc/tutorials/video/optical_flow/optical_flow.markdown

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