Multigrid Methods

Multigrid methods are well-known to be among the fastest and most accurate numerical schemes for the solution of linear and nonlinear system of equations. By creating a sophisticated coarse-to-fine hierarchy starting from the original equation system they offer much better error reduction properties than frequently used non-hierarchical solvers. Thus, very accurate results are already obtained within a few iterations.

In [1] [2] we have developed multigrid schemes for the purpose of real-time optic flow estimation. As a result up to 42 dense flow fields of size 200 x 200 could be computed on a standard desktop PC within a single second. Compared to the frequently used Gauss-Seidel method this equals an acceleration of two to three orders of magnitude. Similar speedups can also be obtained for discontinuity-preserving regularisers [3] and high accuracy methods with warping [4]. An overview of multigrid implementations for a variety of variational optic flow prototypes is given in [5].

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

A comparison of the quality and the speed of recent multigrid implementations for several optic flow protypes can be found here. For more information we refer to the correponding paper [5].

MIA Group
The author is not
responsible for
the content of
external pages.

Imprint - Data protection