We propose to look at large-displacement optical flow from a discrete point of view. Motivated by the observation that sub-pixel accuracy is easily obtained given pixel-accurate optical flow, we conjecture that computing the integral part is the hardest piece of the problem. Consequently, we formulate optical flow estimation as a discrete inference problem in a conditional random field, followed by sub-pixel refinement. Naive discretization of the 2D flow space, however, is intractable due to the resulting size of the label set. In this work, we therefore investigate three different strategies, each able to reduce computation and memory demands by several orders of magnitude (see illustration above): The combination of these strategies allows us to estimate large-displacement optical flow both accurately and efficiently and demonstrates the potential of discrete optimization for optical flow. We obtain state-of-the-art performance on MPI Sintel and KITTI.

Below, we show quantitative results of our method on MPI Sintel flow and KITTI flow 2012 using the same parameter setting for both datasets. Note that on Sintel methods are ranked according to average end-point error while KITTI ranks the entries according to the number of outliers at 3 px error threshold. We only show the top performing methods of each dataset, for the full tables please refer to the respective benchmark websites.



The images below show qualitative results of our method on the MPI Sintel flow (top) and KITTI flow 2012 (bottom) datasets. The reference frame is shown on the left. The middle column depicts our color-coded optical flow results. On the right, we show the error images where small errors are shown in blue and large errors are shown in red colors. Please refer to the paper for more details.



The source code for this project has been tested on Ubuntu 14.04 and Matlab 2013b and is published under the GNU General Public License. If you find this project useful, we would be happy if you cite us:
@inproceedings{Menze2015GCPR,
  author = {Moritz Menze and Christian Heipke and Andreas Geiger},
  title = {Discrete Optimization for Optical Flow},
  booktitle = {German Conference on Pattern Recognition (GCPR)},
  year = {2015}
}