Mathematical Image Analysis Group, Saarland University

Optic Flow

Correspondence problems are one of the key problems in computer vision. They appear for example in motion analysis, image matching, or stereo vision. The goal is to assign structures in one image to structures in a second image, in a way that corresponding structures are as similar as possible. In the case of motion analysis, for instance, this means that pixels are tracked in a sequence by finding the shift vector for each pixel from one image to the next. For this, some property of the pixels has to be assumed to stay constant over time.
Correspondence problems are in general ill-posed, as everybody can imagine there are several possibilities to match structures. To deal with this problem additional smoothness assumptions have to be applied, which can considerably affect the outcome.

This figure shows two frames of the famous Yosemite test sequence and the shift vectors computed by one of our algorithms. Here the shift vectors are shown in a coloured orientation plot where the colour represents the orientation of the vector and brightness stands for its magnitude.

Our Contributions

In our group, we focus mainly on motion analysis, in particular on variational approaches and their numerical realisation. But we also look into the very related areas of image matching and stereo vision.

Smoothness Assumptions for Variational Optic Flow Estimation
During the years, a large amount of different smoothness assumptions have been proposed in the literature. This goes from homogeneous, over image-driven to flow-driven smoothness terms, which can again be both isotropic or anisotropic. A classification of all these techniques helps to understand similarities and differences of methods much better [1].
Combination of Local and Global Methods
There are two different ways to motion estimation. In local methods the optic flow within a neighbourhood is assumed to be smooth and the flow is computed also respecting only this neighbourhood. In global methods, on the other hand, a global energy functional is minimised that respects all the given data to determine the resulting flow field. Both approaches have their advantages and drawbacks. We succeeded in combining both strategies, what allows to take over the best properties from both worlds. So we are able to ensure dense flow fields which are still robust under noise [2] [9].
Optic Flow Estimation with the Nonlinear Structure Tensor
Local methods are often based on the so-called structure tensor. This structure tensor is obtained by smoothing the outer product of the image gradient with a Gaussian kernel. Instead we apply nonlinear diffusion for the smoothing, therefore using the nonlinear structure tensor. This leads to a higher accuracy in the estimation [3].
Higher Order Optic Flow Constraints
Real world image sequences often suffer under slight brightness changes. Applying the standard optic flow constraint, which assumes the grey value of corresponding pixels to stay constant from one image to the next, is not a good way to go. This is because due to the bringhtness change, the basic assumption of this constraint is not valid anymore. Therefore, we apply measures that are less dependent on brightness, such as the image gradient or the Laplacian [6] [7] [13] [16].
Theory for Warping
Warping has become a very popular strategy for optic flow estimation in the presence of large displacements. So far warping has only algorithmically been motivated. We found out, that warping can also be seen as a numerical scheme which solve the original non-linearised constancy assumption, instead of the widely used linearised term. The consequent implementation of this scheme leads to very accurate results like those shown in the images above [7] [14] [16].
Efficient Algorithms
Variational approaches require to solve large linear or nonlinear systems of equations. This results in long computation times, if implemented in a naive way. In our group we developed many techniques that speed up the computation considerabl such as multigrid method [4] [10] [12] [14] [19] and domain decomposition techniques [5] [8] [15] For more information see our research pages on efficient sequential and efficient parallel algorithms.
Joint Motion Estimation and Segmentation
In order to allow for a precise estimation of multiple moving objects, a simultaneous estimation and segmentation of the observed flow fields is useful. To this end, we proposed to embed the approach from [14] into a spatiotemporal level-set formulation for multiple regions. The resulting approach yields the currently most accurate flow fields in the literature [17].
Photometric Invariants
While constancy assuptions on higher order derivatives improve the performance under global additive illumination changes, they may not be optimal for real world applications: There, illumination artifacts are often local and have a multipicative nature. A suitable solution for this problem are so called photometric invariants. These expressions make use of the fact that for colour images actually three measurements are available in each pixel (R,G,B). By suitably combining the three colour channels, one can achieve different degrees of robustness under local and global illumination changes. In [20] we obtained excellent results by embedding different photometric invariants in the high accuracy method of [7].

RGB Constancy Invariant Constancy
Integration of the Epipolar Geometry
In the case of stereo images it make sense to integrate knowledge on the relative position and orientation of the two camers (epipolar geometry). By a suitable parameterisation of the flow components, one can reduce the search space to lines and thus improve the accuracy of the computed flow field [11]. If the information on the orientation and the pose of the camers is not available, one may either use correspondence from high accuracy optic flow methods to estimate the epipolar geometry [21], or one can combine both tasks into a single minimisation framework [22]. For more information see our research page on stereo.
Confidence Measures
Apart from an accurate estimation of the optic flow, one is also interested in rating the local quality of the estimation. In particular if the ground truth is not known measures have to be found that still allow to assess the local confidence of the result. In this context, we proposed to investigate the contribution of the local solution to the engery functional as such a mearuse. As the results show the evaluation of the local energy is both simple and efficient [18].
Sophisticated Numerics: An Adaptive Derivative Discretisation Scheme
The implementation of variational approaches requires to discretise occurring derivatives. Adopting a successful concept from the theory of hyperbolic partial differential equations, we presented in [23] a sophisticated adaptive derivative discretisation scheme. It can improve the quality of results in the same manner as model refinements. For more information see our research page on stereo.
Complementary Smoothness Term
The data and smoothness term of variational optic flow approaches have usually been considered as antagonists. Following ideas from Nagel and Enkelmann in 1986, we introduced the concept of a complementary smoothness term [24] in modern optic flow methods. Our anisotropic regulariser reduces smoothing in data constraint direction and enforces a strong filling-in effect orthogonal to it. This allows optimal complementarity to the data term. As concepts in this data term we used a HSV colour representation with higher order constancy assumptions, a separate constraint normalisation as well as a separate robustification. The precision of this method is demonstrated by top ranking results in the Middlebury benchmark.

Flow field with our
method from [24] Flow field overlaid with
first frame

Publications

J. Weickert, C. Schnörr:
A theoretical framework for convex regularizers in PDE-based computation of image motion.
International Journal of Computer Vision, Vol. 45, No. 3, 245-264, December 2001.
Revised version of Technical Report No. 13/2000, Computer Science Series, University of Mannheim, Germany, June 2000.
A. Bruhn, J. Weickert, C. Schnörr:
Combining the advantages of local and global optic flow methods.
In L. Van Gool (Ed.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 2449, Springer, Berlin, 454-462, 2002.
Awarded a DAGM 2002 Paper Prize.

T. Brox, J. Weickert:
Nonlinear matrix diffusion for optic flow estimation,
In L. Van Gool (Ed.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 2449, Springer, Berlin, 446-453, 2002.
A. Bruhn, J. Weickert, C. Feddern, T. Kohlberger and C. Schnörr:
Real-time optic flow computation with variational methods.
In N. Petkov, M. A. Westenberg (Eds.): Computer Analysis of Images and Patterns. Lecture Notes in Computer Science, Vol. 2756, Springer, Berlin, 222-229, 2003.

T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
Domain decomposition for parallel variational optic flow computation.
In B. Michaelis, G. Krell (Eds.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 2781, Springer, Berlin, 196-202, 2003.

J. Weickert, A. Bruhn, N. Papenberg, T. Brox:
Variational Optic Flow Computation: From Continuous Models to Algorithms.
In L. Alvarez (Ed.): IWCVIA '03: International Workshop on Computer Vision and Image Analysis, Universidad de Las Palmas de Gran Canaria, Dec. 4-6, 2003.
T. Brox, A. Bruhn, N. Papenberg, J. Weickert:
High accuracy optical flow estimation based on a theory for warping.
In T. Pajdla, J. Matas (Eds.): Computer Vision - ECCV 2004. Lecture Notes in Computer Science, Vol. 3024, Springer, Berlin, 25-36, 2004.
Awarded the "Longuet-Higgins Prize" by the ECCV (Best Paper Award).

T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
Parallel variational motion estimation by domain decomposition and cluster computing..
In T. Pajdla, J. Matas (Eds.): Computer Vision - ECCV 2004. Lecture Notes in Computer Science, Vol. 3024, Springer, Berlin, 205-216, 2004.

A. Bruhn, J. Weickert, C. Schnörr:
Lucas/Kanade meets Horn/Schunck: Combining local and global optic flow methods. Updated version with errata.
International Journal of Computer Vision, Vol. 61, No. 3, 211-231, February/March 2005.
A. Bruhn, J. Weickert, T. Kohlberger, C. Schnörr:
Discontinuity-preserving computation of variational optic flow in real-time.
In R. Kimmel, N. Sochen, J. Weickert (Eds.): Scale-Space and PDE Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 3459, Springer, Berlin, 279-290, 2005.
N. Slesareva, A. Bruhn, J. Weickert:
Optic flow goes stereo: A variational method for estimating discontinuity-preserving dense disparity maps.
In W. Kropatsch, R. Sablatnig, A. Hanbury (Eds.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 3663, 33-40, Springer, Berlin, 2005.
Awarded a DAGM 2005 Paper Prize.
A. Bruhn, J. Weickert, C. Feddern, T. Kohlberger, C. Schnörr:
Variational optic flow computation in real-time.
IEEE Transactions on Image Processing, Vol. 14, No. 5, 608-615, May 2005.
Revised version of Technical Report No. 89, Department of Mathematics, Saarland University, Saarbrücken, Germany, June 2003.
J. Weickert, A. Bruhn, T. Brox, N. Papenberg:
A Survey on Variational Methods for Small Displacements.
In O. Scherzer (Ed.): Mathematical Models for Registration and Applications to Medical Imaging, Mathematics in Industry, Vol. 10, Springer, Berlin, to appear.
Revised version of Technical Report No. 152, Department of Mathematics, Saarland University, Saarbrücken, Germany, September 2005.
A. Bruhn, J. Weickert:
Towards ultimate motion estimation: Combining highest accuracy with real-time performance.
In Proc. Tenth IEEE International Conference on Computer Vision, Vol. 1, 749-755, IEEE Computer Society Press, 2005.
T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
Domain decomposition for variational optical flow computation..
IEEE Transactions on Image Processing, Vol. 14, No. 8, 1125-1137, August 2005.
N. Papenberg, A. Bruhn, T. Brox, S. Didas, J. Weickert:
Highly accurate optic flow computation with theoretically justified warping.
International Journal of Computer Vision, Vol. 67, No. 2, 141-158, April 2006.
T. Brox, A. Bruhn, J. Weickert:
Variational Motion Segmentation with Level Sets.
In H. Bischof, A. Leonardis, A. Pinz (Eds.): Computer Vision – ECCV 2006. Lecture Notes in Computer Science, Vol. 3951, 471–483. Springer, Berlin, 2006.

A. Bruhn, J. Weickert:
A confidence measure for variational optic flow methods.
In R. Klette, R. Kozera, L. Noakes, J. Weickert (Eds.): Geometric Properties from Incomplete Data, 283-297, Springer, Dordrecht, 2006.
Revised version of Technical Report No. 106, Department of Mathematics, Saarland University, Saarbrücken, Germany, July 2004.
A. Bruhn, J. Weickert, T. Kohlberger, C. Schnörr:
A multigrid platform for real-time motion computation with discontinuity-preserving variational methods.
International Journal of Computer Vision, Vol. 70, No. 3, 257-277, December 2006.
Y. Mileva, A. Bruhn, J. Weickert:
Illumination-robust variational optical flow with photometric invariants.
In F. A. Hamprecht, C. Schnörr, B. Jähne (Eds.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 4713, 152-162, Springer, Berlin, 2007.

M. Mainberger, A. Bruhn, J. Weickert:
Is dense optic flow useful to compute the fundamental matrix?
Updated version with errata. In A. Campilho, M. Kamel (Eds.): Image Analysis and Recognition. Lecture Notes in Computer Science, Vol. 5112, 630-639, Springer, Berlin, 2008.

L. Valgaerts, A. Bruhn, J. Weickert:
A variational approach for the joint recovery of the fundamental matrix and the optical flow.
In G. Rigoll (Ed.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 5096, 314-324, Springer, Berlin, 2008.

H. Zimmer, M. Breuß, J. Weickert, H.-P. Seidel:
Hyperbolic numerics for variational approaches to correspondence problems.
In X.-C. Tai et al. (Eds.): Scale-Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 5567, 636-647, Springer, Berlin, 2009.

H. Zimmer, A. Bruhn, J. Weickert, L. Valgaerts, A. Salgado, B. Rosenhahn, and H.-P. Seidel:
Complementary Optic Flow.
In D.Cremers, Y.Boykov, A.Blake, F.R.Schmidt (Eds.): Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR). Lecture Notes in Computer Science, Vol. 5681, 207-220, Springer, Berlin, 2009.