Читать книгу Graph Spectral Image Processing - Gene Cheung - Страница 30

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).