Mathematical Image Analysis Group, Saarland University

Hyperbolic Schemes

The design and understanding of numerical algorithms plays a key role in building high-quality methods for image processing and computer vision. This especially holds true for numerical methods for hyperbolic partial differential equations (PDEs), as the resolution of discontinuous solution features easily inspires oscillations in numerical approximations.

Besides the construction of schemes for specific purposes in image processing and computer vision, we also perform fundamental research on numerical methods for hyperbolic PDEs.

Our Contributions

Hyperbolic Schemes in Mathematical Morphology

PDE-based mathematical morphology relies on the hyperbolic equations of dilation/erosion. This holds true for grey-scale images as well as for images composed of matrix-valued data sets (so-called tensor fields). Click here for more information on mathematical morphology.

Shock-Capturing Schemes for PDEs in Greyscale Morphology
In [1] we develop a novel flux corrected transport (FCT) scheme that can accurately cope with the peculiarities of the morphological processes of dilation and erosion. Later on, this method has been extended to deal with general convex structuring elements [2]. In the mentioned works, it is shown that the method performs better than other PDE-based schemes in the field. Also, the FCT scheme is competitive to set-based, algebraic solutions.

Schemes for Matrix-Valued PDEs
For the appropriate numerical treatment of recently modeled matrix-valued PDEs we devised matrix-valued generalisations of known real-valued schemes, see especially [3]. Also, the FCT-scheme introduced in [1] for processing grey value images has been successfully extended to this setting showing superior resolution of edge-like structures compared with other methods.
We have also shown that our methods can be made locally adaptive to the data of the evolved image, cf. [4].

Hyperbolic Methods for the Inverse Problem of Shape from Shading

The shape from shading (SFS) task is a classic inverse problem in computer vision. It amounts to compute at hand of information on illumination and reflectance the 3-D shape of objects in a single given image. Modern models for SFS are described by hyperbolic Hamilton-Jacobi equations. For more information on that topic, click here.

Schemes for Lambertian Shape from Shading
In [5] we introduce an efficient iterative solver for the state-of-the-art Lambertian SFS model, and we prove conditional stability. An extensive numerical comparison of recent SFS solvers including our own approach as well as the optimal control approaches of Prados et al. and Cristiani et al. is performed in [6]. The latter work is extended by [7], where we also analysed for the first time numerical acceleration techniques like fast sweeping and cascading multigrid methods for all solvers.

Schemes for Non-Lambertian Shape from Shading
We extend the Lambertian SFS model of Prados et al. in the work [8] and propose a numerical solver. The detailed derivation of the model plus a conditional stability criterion for an efficient iterative solver is derived in [9]. In the latter work, we also perform for the first time in the computer vision literature a numerical scale analysis of the underlying PDE that reveals important information on the relative size of diffusive and specular reflection terms.

Fast Marching Schemes for Non-Lambertian Shape from Shading
In [10] we construct a fast marching method for our new non-Lambertian SfS model. By using this we can solve the SFS task on large images with computational times of about a minute with usual hardware.

Adaptive Hyperbolic Schemes for Variational Correspondence Problems

A High-Resolution-type Method for Variational Computer Vision Tasks
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 [13] a sophisticated adaptive derivative discretisation scheme. It blends central and correctly oriented one-sided (upwind) differences based on a smoothness measure. It can improve the quality of results in the same manner as model refinements. For more information see our research page on stereo.

Fundamental Research on Hyperbolic Schemes

Implicit Schemes for Hyperbolic PDEs
A novel, mathematically justified theory of implicit monotone methods is presented in [11]. There it is shown that an Euler implicit time discretisation does not give automatically unconditional stability in terms of monotonicity even if the numerical flux function describes a monotone scheme in the explicit case.

Novel Parallelisation Approach for Fast Marching Methods
In [12] we describe a novel parallelisation approach that is based on the understanding of the physical workings of hyperbolic PDEs. It avoids the traditional domain-decomposition approach and is much easier to implement than that.

Publications

M. Breu�, J. Weickert:
A shock-capturing algorithm for the differential equations of dilation and erosion.
Journal of Mathematical Imaging and Vision, Vol. 25, 187-201, (2006).
Revised version of Technical Report No. 153, Department of Mathematics, Saarland University, Saarbr�cken, Germany, September 2005.
M. Breuß, J. Weickert:
Highly accurate PDE-based morphology for general structuring elements.
In X.-C. Tai et al. (Eds.): Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 5567, 758 - 769, Springer, Berlin, 2009.

B. Burgeth, M. Breuß, S. Didas, J. Weickert:
PDE-based morphology for matrix fields: Numerical solution schemes.
Tensors in Image Processing and Computer Vision, Advances in Pattern recognition, pp. 125--150. Springer, London, 2009.
Revised version of Technical Report No. 220, Department of Mathematics, Saarland University, Saarbrücken, Germany, September 2008.
L. Pizarro, B. Burgeth, M. Breuß, J. Weickert:
A directional Rouy-Tourin scheme for adaptive matrix-valued morphology.
In M.H.F. Wilkinson and J.B.T.M. Roerdink (Eds.): Proc. Ninth International Symposium on Mathematical Morphology (ISMM 2009), Lecture Notes in Computer Science, vol. 5720, pp. 250 -260, Springer, Berlin, 2009.
© Springer-Verlag Berlin Heidelberg 2009.

O. Vogel, M. Breuß, J. Weickert:
A Direct Numerical Approach to Perspective Shape-from-Shading
In H. Lensch, B. Rosenhahn, H.-P. Seidel, P. Slusallek, J. Weickert (Eds.): Vision, Modeling, and Visualization 2007. Saarbrücken, Germany, 91-100, November 2007.

M. Breuß, O. Vogel, J. Weickert:
Efficient numerical techniques for perspective shape from shading.
In A. Handlovicova, P. Frolkovic, K. Mikula, D. Sevcovic (Eds.): Algoritmy 2009 (Podbanske, Slovakia, March 2009), pp. 11-20, Slovak University of Technology, Bratislava, 2009.

M. Breuß, E. Cristiani, J.-D. Durou, M. Falcone, O. Vogel:
Numerical Algorithms for Perspective Shape from Shading.
To appear in Kybernetika (2009).
Revised version of Technical Report No. 240, Department of Mathematics, Saarland University, Saarbrücken, Germany, August 2009.

O. Vogel, M. Breuß, J. Weickert:
Perspective shape from shading with non-Lambertian reflectance.
In G. Rigoll (Ed.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 5096, 517-526, Springer, Berlin, 2008.
M. Breuß, O. Vogel, J. Weickert:
Perspective shape from shading for Phong-type non-Lambertian surfaces.
Technical Report No. 216, Faculty of Mathematics and Computer Science, Saarland University, Saarbrücken, Germany, August 2008.

O. Vogel, M. Breuß, T. Leichtweis, J. Weickert:
Fast shape from shading for Phong-type surfaces.
In X.-C. Tai et al. (Eds.): Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 5567, 733 - 744, Springer, Berlin, 2009.
© Springer-Verlag Berlin Heidelberg 2009.

M. Breuß:
Monotonicity of Implicit Finite Difference Methods for Hyperbolic Conservation Laws.
Technical Report No. 253, Department of Mathematics, Saarland University, Saarbrücken, Germany, November 2009.

M. Breuß, E. Cristiani, P. Gwosdek, O. Vogel:
A Domain-Decomposition-Free Parallelisation of the Fast Marching Method.
Technical Report No. 250, Department of Mathematics, Saarland University, Saarbrücken, Germany, October 2009.

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.