Fast Explicit Diffusion (FED) and Fast-Jacobi (FJ)

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.
However, such ideas are not restricted to parabolic problems only. They can also be adapted for solving elliptic PDEs that arise e.g. as Euler-Lagrange equations in variational image analysis. Also in this context, we propose a modification of the simplest iterative solver, namely the Jacobi method. This time, we introduce cycles of varying relaxation parameters that can be linked to our FED time step sizes. As a result, we obtain highly efficient methods for the elliptic case, so-called Fast-Jacobi (FJ) schemes

Besides being very efficient on sequential hardware, FED and FJ are also very well suited for massively parallel architectures, such as GPUs. Due to their simplicity, even complex processes such as highly accurate optic flow methods can easily be realised [3]. 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 and Fast-Jacobi for elliptic problems. They can readily be used in C and C++ programmes, and are published as open source software under the terms of the GNU General Public License (Version 3).

Our package contains the FED/Fast-Jacobi library, a detailed documentation, and two sample programmes for both FED and Fast-Jacobi. It can be downloaded here:

Source Code with Documentation

If you intend to use this library in the preparation of an own publication, please cite our papers [1] and [2] as references for FED and Fast-Jacobi.

1. J. Weickert, S. Grewenig, C. Schroers, A. Bruhn:
   Cyclic schemes for PDE-based image analysis.
   International Journal of Computer Vision, Vol. 118, No. 3, 275-299, July 2016.
   Also available as Technical Report No. 327 (revised), Department of Mathematics, Saarland University, Saarbrücken, Germany, April 2015.
2. 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).
3. 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.
   In K. N. Kutulakos (Ed.): Trends and Topics in Computer Vision.
   Lecture Notes in Computer Science, Vol. 6554, 372-383, Springer, Berlin,
   November 2012.
   Revised version of Technical Report No. 267, Department of Mathematics, Saarland University, Saarbrücken, Germany, July 2010.

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

Imprint - Data protection