Universität des Saarlandes

Many successful methods in image processing and computer vision involve

parabolic and elliptic partial differential equations (PDEs). Thus, there

is a growing demand for simple and highly efficient numerical algorithms

that work for a broad class of problems. Moreover, these methods should

also be well-suited for low-cost parallel hardware such as GPUs.

In this talk we show that two of the simplest methods for the numerical

analysis of PDEs can lead to remarkably efficient algorithms when they

are only slightly modified: To this end, we consider cyclic variants of

the explicit finite difference scheme for approximating parabolic problems,

and of the Jacobi overrelaxation method for solving systems of linear

equations.

Although cyclic algorithms have been around in the numerical analysis

community for a long time, they have never been very popular for a number

of reasons. We argue that most of these reasons have become obsolete and

that cyclic methods ideally satisfy the needs of modern image processing

applications. Interestingly this transfer of knowledge is not a one-way

road from numerical analysis to image analysis: By considering a

factorisation of general smoothing filters, we introduce novel, signal

processing based ways of deriving cycle parameters. They lead to hitherto

unexplored methods with alternative parameter cycles. These methods offer

better smoothing properties than classical numerical concepts such as

Super Time Stepping and the cyclic Richardson algorithm.

We present a number of prototypical applications that demonstrate the

wide applicability of our cyclic algorithms. They include isotropic

and anisotropic nonlinear diffusion processes, higher dimensional

variational problems, and higher order PDEs.