Graph Spectral Image Processing. Gene Cheung

its approximation accuracy gets significantly worse when λ is away from 0. Since the maximum eigenvalue λ_max highly depends on the graph used, it is better to use different approximation methods like the Chebyshev approximation, which is introduced in section 1.6.

      1.4.2. Edge-preserving smoothing

      Edge-preserving image smoothing is widely used for various tasks, as well as for image restoration (Nagao and Matsuyama 1979; Pomalaza-Raez and McGillem 1984; Weickert 1998; Tomasi and Manduchi 1998; Barash 2002; Durand and Dorsey 2002; Farbman et al. 2008; Xu et al. 2011; He et al. 2013). Image restoration aims to approximate an unknown ground-truth image from its degraded version(s). In contrast, edge-preserving smoothing is typically used to yield a user-desired image from the original one. The resulting image is not necessarily close to the original one.

      In the graph setting, we need to define pixel-wise or patch-wise relationships as a distance between pixels or patches, and it is used to construct a graph. The following distances are often considered (Milanfar 2013b), where i and j are pixel or patch indices and

is some nonnegative function:

      1) Geometric distance:

, where p_i is the ith pixel coordinate.

2) Photometric distance:

, where

is the pixel value (often three dimensional) of the ith pixel/patch.

      3) Saliency distance:

where s_i is the ith saliency value.

      4) Combinations of the above.

Figure 1.2. Comparison of approximation errors in . For a color version of this figure, see www.iste.co.uk/cheung/graph.zip

      Saliency of the image/region/pixel is designed to simulate perceptual behavior (Itti et al. 1998; Harel et al. 2006). A popular choice of φ(·) is the Gaussian weight

      [1.23]

      where σ controls the spread of the filter kernel.

      Suppose that the filter coefficients are determined based on the above features, and that they are symmetric, i.e. the output pixel value y_i is represented as

      [1.24]

      where

      [1.25]

Here, d_k(·, ·) is one of the distance metrics mentioned earlier and K is the number of features we considered. The scaling factor D_i normalizes the filter weights as . For example, the bilateral filter is K = 2 for d_g(·, ·) and d_p(·, ·).

      The Fourier domain representation of such pixel-dependent filters cannot be calculated in a classical sense because it is no longer shift-invariant: the filter matrix W cannot be diagonalized by the DFT matrix. In contrast, GSP provides a frequency-like notion in the graph frequency domain. In general, the weight matrix W in equation [1.24] can be regarded as an adjacency matrix because all d_k(·, ·) are assumed to be distances between pixels. Suppose that there is no self-loop in W, for simplicity. In general, the smoothed image in equation [1.24] is represented in the following matrix form:

      [1.26]

      where D = diag(D₀,...,D_N−1). This can be rewritten by using the relationship L = D − W as (Gadde et al. 2013):

      [1.27]

      [1.28]

[1.29]

      where

is a degree-normalized signal. Let us denote the eigendecomposition of L_n as

. The above filtering in equation [1.29] is further rewritten as:

      [1.30]

      [1.31]

      [1.32]

      where y := D^1/2y and the graph spectral filter is defined as

Moreover,

for the symmetric normalized graph Laplacian; therefore, it acts as a linear decay low-pass filter in the graph frequency domain.

      This graph spectral representation of a pixel-dependent filter suggests that the pixel-dependent filter W implicitly and simultaneously designs the underlying graph (and therefore, the GFT basis) and the spectral response of the graph filter. In other words, the GSP expression of the pixel-dependent filter is free to design the spectral response

, apart from the linear decay one, once we determine W. For example, let us consider the following spectral response:

      [1.33]

where

is an arbitrary graph high-pass filter and η > 0 is a parameter. In this case,

works as a graph low-pass filter and its spectral shape is controlled by

In fact, Gadde et al. (2013) show that equation [1.33] is the optimal solution for the following signal restoration problem:

      [1.34]

      where