Graph Spectral Image Processing. Gene Cheung

is nothing but the Moore–Penrose pseudo inverse of E⁴. This GSP system is generally asymmetric: while the analysis transform has graph filters and possible sampling, the synthesis transform does not have such a clear notion of filtering and upsampling. In general, the asymmetric structure requires a matrix inversion. Additionally, the N × N matrix E^TE is usually dense, which leads to complexity.

      Therefore, symmetric structures are often desired instead, and they are similar to those that are widely used in classical signal processing. The synthesis transform with a symmetric structure has the following form:

      [1.41]

      where g_k(L) is the kth synthesis filter and is an upsampling matrix. As a result, each subband has the following input–output relationship:

[1.42]

      reconstruction, it must be x.The resulting output is therefore represented as and for perfect reconstruction, it must be x.

      1.5.2.1. Design of perfect reconstruction transforms: undecimated case

      There are various methods available for designing perfect reconstruction graph transforms. First, let us consider undecimated transforms that exhibit symmetrical structure.

      An undecimated transform has no sampling, i.e. S_k = I_N for all k. Therefore, the analysis and synthesis transforms, respectively, are represented in the following simple forms:

      [1.43]

      [1.44]

Accordingly, the perfect reconstruction condition can also be simple. The input–output relationship in equation [1.42] is reduced to

      [1.45]

      Assuming p_k(L) := g_k(L)h_k(L) as the kth product filter, the output signal is thus given by

      [1.46]

      Therefore, the product filters must satisfy the following condition for perfect reconstruction:

[1.47]

      where c is some constant.

      Suppose that h_k(L) and g_k(L) are parameterized as and g_k(L) = Uĝ_k(Λ)U^T, respectively. In this case, equation [1.47] can be further reduced to

[1.48]

      where This condition is similar to that considered in biorthogonal FIR filter banks in classical signal processing (Vaidyanathan 1993; Vetterli and Kovacevic 1995; Strang and Nguyen 1996). When and the filter set satisfies equation [1.48], the filter bank is called a tight frame because the perfect reconstruction condition can be rewritten as

      [1.49]

      If c = 1, the frame is called a Parseval frame. In this case, it conserves the energy of the original signal in the transformed domain. Tight spectral graph filter banks can be constructed by employing the design methods of tight frames in classical signal processing. Examples can be found in Leonardi and Van De Ville (2013); Shuman et al. (2015); Sakiyama et al. (2016).

      1.5.2.2. Design of perfect reconstruction transforms: decimated case

      Constructing perfect reconstruction graph transforms with sampling is much more difficult than the undecimated version. However, it is required as the storage cost can be increased tremendously for the undecimated versions, especially for signals on a very large graph. Though the general condition is given by equation [1.42], the challenges are designing and choosing the appropriate sampling operator S_k and the appropriate filters h_k(L) and g_k(L). The perfect reconstruction condition can be satisfied with proper sets of these.

      Various methodologies have been proposed in literature with different strategies. The recent methods of such transforms are summarized in Sakiyama et al. (2019c). We have omitted these details because they are beyond the scope of this chapter. Instead, some design guidelines are listed as follows:

       – Sampling operator: In GSP, two different definitions of sampling operators exist (Tanaka et al. 2020; Tanaka 2018; Tanaka and Eldar 2020). One is vertex domain sampling, which is an analog of time-domain sampling. The other is graph frequency domain sampling, which is a counterpart of the Fourier domain expression of sampling. Both are not interchangeable in general, and have their own advantages and disadvantages.

       – Localized transform: As mentioned later in section 1.6.5, polynomial filters are localized in the vertex domain. Furthermore, if all filters are polynomials, the entire transform can be eigendecomposition free, and thus, its computation decreases significantly.

       – Flexible design adapting various spectra: Different graphs have unique eigenvalue distributions, and different graph operators have unique characteristics. Additionally, we sometimes encounter repeated eigenvalues. A unified design strategy is required for representing various graph signals sparsely.

1.6. Fast computation

      As we mentioned in the previous sections, a naïve implementation of spectral graph filters often requires a high computational complexity. Since we often need to process high-resolution images, reducing such a complexity would be a high priority. Moreover, spectral filtering is often iteratively employed for image restoration, like an internal algorithm for convex optimization problems. In this section, we describe a workaround to alleviate computational burden for graph spectral filtering.

      1.6.1. Subdivision

Digital image processing has a long history, and the subdivision