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 {hk(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
[1.35]
The entire analysis transform is given as follows:
[1.36]
The size of
– ρ = 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 Sk = IN, 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 ck for a target application. For example, small magnitude elements in ck are thresholded to denoise or compress the signal. Let us denote
The synthesis transform combines
[1.37]
where
[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−1 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