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
©2001-2023
The author is not
responsible for
the content of
external pages.

Imprint - Data protection