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 . 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 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 . 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: