Mathematical Image Analysis Group, Saarland University

Efficient Sequential Algorithms

For many tasks in the area of image processing and computer vision a fast and accurate computation of the results is required. One may claim that the rapid progress in the sector of computer engineering will solve this problem by allowing algorithms to become faster year by year. However, these accelerations are rather small compared to those obtained by state-of-the-art numerical methods.

Our Contributions

Our research in the area of efficient sequential algorithms includes the following main topics:

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 [5] [6] we developed such 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 [7] and high accuracy methods with warping [8]. An overview of multigrid implementations for a variety of variational optic flow prototypes is given in [9].
Splitting Schemes
A second numerical approach for the acceleration of algorithms is the use of so called splitting schemes. They allow for a decomposition of a single problem into multiple problems that offer certain advantages compared to the original one. In general, the resulting problems can be solved very efficiently with standard numerical methods. Some of them even offer advantages regarding a possible parallelisation. Our research mainly focuses on additive operator splitting (AOS) schemes, which have the advantage of being rotationally invariant compared to their multiplicative counterparts. In [1] such an AOS scheme is presented for the first time to the image processing and computer vision community. Apart from nonlinear diffusion filtering, variants for regularisation methods [2] and optic flow computation [3] have been developed. Recently, we also used AOS schemes successfully in the context of active contour models [4].

Publications

J. Weickert, B.M. ter Haar Romeny, M.A. Viergever:
Efficient and reliable schemes for nonlinear diffusion filtering.
IEEE Transactions on Image Processing, Vol. 7, 398-410, 1998.
J. Weickert:
Efficient image segmentation using partial differential equations and morphology.
Pattern Recognition, Vol. 34, No. 9, 1813-1824, September 2001.
Also available as Technical Report No. 3/2000. Computer Science Series, University of Mannheim, Germany, February 2000.
J. Weickert, C. Schnörr:
Variational optic flow computation with a spatio-temporal smoothness constraint.
Journal of Mathematical Imaging and Vision, Vol. 14, No. 3, 245-255, May 2001.
Revised version of Technical Report No. 15/2000. Computer Science Series, University of Mannheim, Germany, July 2000.
J. Weickert, G. Kühne:
Fast methods for implicit active contour models.
In S. Osher, N. Paragios (Eds.): Geometric Level Set Methods in Imaging, Vision and Graphics. Springer, 2003.
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.
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.
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.
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.
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.

Demo

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 [9].