Cyclic Schemes for PDE-Based Image Analysis

We investigate a class of efficient numerical algorithms for many partial differential equations (PDEs) in image analysis. They are applicable to parabolic or elliptic PDEs that have bounded coefficients and lead to space discretisations with symmetric matrices. Our schemes are easy to implement and well-suited for parallel implementations on GPUs, since they are based on the explicit diffusion scheme in the parabolic case, and the Jacobi method in the elliptic case. By supplementing these methods with cyclically varying time step sizes or relaxation parameters, we achieve efficiency gains of several orders of magnitude. We call the resulting algorithms Fast Explicit Diffusion (FED) and Fast Jacobi (FJ) methods. To achieve a good compromise between efficiency and accuracy, we show that one should use parameter cycles that result from factorisations of box filters. For these cycles we establish stability results in the Euclidean norm. Our schemes perform favourably in a number of applications, including isotropic nonlinear diffusion filters with widely varying diffusivities as well as anisotropic diffusion methods for image filtering, inpainting, and regularisation in computer vision. Moreover, they are equally suited for higher dimensional problems as well as higher order PDEs, and they can also be interpreted as efficient first order methods for smooth optimisation problems.