Graph Spectral Image Processing. Gene Cheung

+ n with additive noise n and

.

      Image filtering sometimes needs numerous iterations to smooth out the details, in case of textured and/or noisy images. Therefore, to boost up the smoothing effect, the trilateral filter method (Choudhury and Tumblin 2003) first smooths the gradients of the image, and subsequently, the smoothed gradient is utilized to smooth the intensities. Its counterpart in the graph spectral domain is also proposed in Onuki et al. (2016) with the parameter optimization method for ρ in equation [1.33], which minimizes MSE after denoising it.

Figure 1.3. Image denoising example using bilateral filters. From left to right: Original, noisy (PSNR: 20.02 dB), bilateral filter in the pixel domain (PSNR: 26.23 dB), and bilateral filter in the graph frequency domain (PSNR: 27.14 dB). Both bilateral filters use the same parameters

Figure 1.3 depicts an example of image denoising by the bilateral filter in the graph frequency domain (Gadde et al. 2013). The image is degraded by additive white Gaussian noise. The bilateral filter in the graph frequency domain uses the spectral filter parameterized in equation [1.33], with ĥ_HPF = λ and η = 5. It is clear that the graph spectral version efficiently removes noise while preserving image edges.

1.5. Multiple graph filters: graph filter banks

In the previous sections, we only considered the case where a single graph spectral filter was applied. Several image processing applications, such as compression and restoration, often require multiple filters that have different passbands (typically low-pass and high-pass). This signal processing system – so-called filter banks – is also important for GSP. In this section, the spectral domain design of graph filter banks is briefly introduced.

Figure 1.4. Framework of graph filter bank

      1.5.1. Framework

A typical framework of a graph filter bank is illustrated in Figure 1.4. The analysis transform decomposes the input signal into some graph frequency components using a set of graph filters {h_k(L)} (k = 0,...,M − 1). We assume that the graph operator is a graph Laplacian L; however, in general, any graph operator can be applied. The decomposed coefficients (called transformed coefficients) are often downsampled by the sampling matrix , where M_k is the sampling ratio, to reduce the number of coefficients. As a result, the transformed coefficients in each subband are represented as

      [1.35]

      The entire analysis transform is given as follows:

      [1.36]

      The size of is often called the redundancy of the transform. The redundancies of transforms are classified as follows:

       – ρ = 1: critically sampled transform. The number of transformed coefficients is the same as N, i.e. the number of elements in x.

       – ρ > 1: oversampled transform. The number of transformed coefficients is larger than N.

       – ρ < 1: undersampled transform. The number of transformed coefficients is smaller than N.

      If S_k = I_N, i.e. no sampling is performed, ρ = M, and the transform is called an undecimated transform. In general, undersampled transforms will lose the information of the original signal. They cannot recover the original signal x from the transformed coefficients.

      After the analysis transformation, an arbitrary linear and nonlinear operation is performed to c_k for a target application. For example, small magnitude elements in c_k are thresholded to denoise or compress the signal. Let us denote as processed coefficients.

      The synthesis transform combines to reconstruct the signal. This is represented as

      [1.37]

      where is the synthesis transform matrix. The perfect reconstruction transform is defined as the transform that recovers the original signal perfectly, when no processing is performed between the analysis and synthesis transforms. Formally, it satisfies the following condition:

[1.38]

      The details of perfect reconstruction graph filter banks are provided in the next section.

      While R can be arbitrary, one may need a symmetric structure: the synthesis transform represented by multiple filters and upsampling as a counterpart of the analysis transform. In classical signal processing, most filter banks are designed to be symmetric, which, in contrast, is difficult for the graph versions, mainly due to the sampling operations. Several design methods make it possible to design perfect reconstruction graph transforms with a symmetric structure (Narang and Ortega 2012; Narang and Ortega 2013; Shuman et al. 2015; Leonardi and Van De Ville 2013; Tanaka and Sakiyama 2014; Sakiyama and Tanaka 2014; Sakiyama et al. 2016; Sakiyama et al. 2019a; Teke and Vaidyanathan 2016; Sakiyama et al. 2019b).

      1.5.2. Perfect reconstruction condition

      Suppose that the redundancy is ρ ≥ 1 and the columns of E are linearly independent. The perfect reconstruction condition equation [1.38] is clearly rewritten as

      [1.39]

The critically sampled system constrains that E is a square matrix; therefore, R must be E⁻¹ for perfect reconstruction. For the oversampled system, we generally have an infinite number of R satisfying the condition in equation [1.39]. The most simple and well-known solution is the least squares solution, which is expressed as

      [1.40]

This