Graph Spectral Image Processing. Gene Cheung

Чтение книги онлайн.

СКАЧАТЬ

      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 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 СКАЧАТЬ