Fast Explicit Diffusion (FED)

There are two popular ways to implement anisotropic diffusion filters with a diffusion tensor: Explicit finite difference schemes are simple but become inefficient due to severe time step size restrictions, while semi-implicit schemes are more efficient but require to solve large linear systems of equations. We present a novel class of algorithms that combine the advantages of both worlds: They are based on simple explicit schemes, while being more efficient than semi-implicit approaches.

Fast Explicit Diffusion (FED) is a simple explicit scheme that uses varying time step sizes [1]. It is substantially faster than usual explicit schemes: Up to 50% of its time step sizes exceed the stability limit, and the stopping time grows quadratically in the number of steps. Thus, a few steps suffice to obtain astonishing stopping times. Another advantage of FED is the simplicity of implementation. Any explicit scheme can easily be converted into FED by adding two simple precomputation steps: Deriving the time step sizes, and choosing a suitable rearrangement in order to tame rounding errors.

Besides being very efficient on sequential hardware, FED is also very well suited for massively parallel architectures, such as GPUs. Due to its simplicity, even complex diffusion-like processes such as highly accurate optic flow methods can easily be realised [2]. The resulting algorithms for GPUs beat the most sophisticated numerical solvers on CPUs by two to three orders of magnitude.

We have developed a library which offers the highly efficient FED functionality for arbitrary diffusion processes. It can readily be used in C and C++ programmes, and is published as open source software under the terms of the GNU General Public License (Version 3).

Our package contains the FED library, a detailed documentation, and a sample programme. It can be downloaded here:

Source Code with Documentation (TGZ, 236 kB)

If you intend to use this library in the preparation of an own publication, please cite our paper [1] as a reference for FED.

1. S. Grewenig, J. Weickert, A. Bruhn:
   From box filtering to fast explicit diffusion.
   In M. Goesele, S. Roth, A. Kuijper, B. Schiele, K. Schindler (Eds.): Pattern Recognition.
   Lecture Notes in Computer Science, Vol. 6376, 533-542, Springer, Berlin, 2010.
   Awarded the DAGM 2010 Main Prize (Best Paper Award).
2. P. Gwosdek, H. Zimmer, S. Grewenig, A. Bruhn, J. Weickert:
   A highly efficient GPU implementation for variational optic flow based on the Euler-Lagrange framework.
   Proc. 2010 ECCV Workshop on Computer Vision with GPUs (September 2010, Heraklion, Greece).
   Revised version of Technical Report No. 267, Department of Mathematics, Saarland University, Saarbrücken, Germany, July 2010.

MIA Group
©2001-2012
The author is not
responsible for
the content of
external pages.