This chapter presents a new method for smoothing both gray-scale and color images, which relies on the heat diffusion equation on a graph. The image pixel lattice using a weighted undirected graph is presented. The edge weights of the graph are determined by the Gaussian weighted distances between local neighboring windows. The associated Laplacian matrix (the degree matrix minus the adjacency matrix) is computed then. The authors capture anisotropic diffusion across this weighted graph-structure with time by the heat equation, and find the solution, i.e. the heat kernel, by exponentiating the Laplacian eigensystem with time. Image smoothing is accomplished by convolving the heat kernel with the image, and its numerical implementation is realized by using the Krylov subspace technique. The method has the effect of smoothing within regions, but does not blur region boundaries. The relationship is also demonstrated between the authors’ method, standard diffusion-based PDEs, Fourier domain signal processing, and spectral clustering. The effectiveness of the method is illustrated by experiments and comparisons on standard images.
Top1. Introduction
Smoothing is one of the most fundamental and widely studied problems in low-level image processing. The main purpose of image smoothing is to reduce undesirable distortions and noise while preserving important features such as discontinuities, edges, corners and texture. During the last two decades diffusion-based filters have become a powerful and well-developed tool for image smoothing and multi-scale image analysis (Weickert, 1998) (Sapiro, 2001). Witkin (Witkin, 1983) and Koenderink (Koenderink, 1984) were the first to formalise the multi-scale description of images and signals in terms of scale-space filtering. Their basic idea is to use convolutions with the Gaussian filter to generate fine to coarse resolution image descriptions. This is equivalent to evolving the original image using the classical heat equation (Koenderink, 1984) (Babaud, 1986), and is known as isotropic diffusion. Since the diffusivity of the isotropic diffusion is constant in all directions, boundaries and other image features will be blurred while removing the noise. In the influential work of Perona and Malik (P-M) (Perona, 1990), an anisotropic diffusion scheme for scale-space description and image smoothing was developed. The method breaks the isotropy condition and outperforms Gaussian filtering. The basic idea of this nonlinear smoothing method was to smooth images with a direction selective diffusion that preserves edges. Catte et al. (Catte, 1992) and Alvarez et al. (Alvarez, 1992) identified the ill-posedness of the P-M diffusion process and proposed a regularised modification. This nonlinear diffusion technique has been subsequentially extensively analysed and developed (Saint-Marc, 1991) (You, 1996) (Witkin, 1983) (Weickert, 1999) (Black, 1998) (Bao, 2004) (Gilboa, 2004). More recently, diffusion-based PDEs has also been developed for smoothing multi-valued images (Chambolle, 1994) (Sapiro, 1996) (Sochen, 1998) (Blomgren, 1998) (Tschumperle, 2005).
Most diffusion-based PDEs for image smoothing assume that the image is a continuous two dimensional function on R2 and consider discretization for the purpose of numerical implementation. It is desirable that the implementation is fast, accurate, and numerically stable, but these requirements are sometimes difficult to achieve. Moreover, images, and especially noisy ones, may not be sufficiently smooth to give reliable derivatives. Thus, for filtering noisy images it is more natural to consider the image as a smooth function defined on a discrete sampling structure.