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

The vertex domain filtering introduced above intuitively parallels time-domain filtering. However, it has a major drawback in a frequency perspective. As mentioned in section 1.2, time-domain filtering and frequency domain filtering are identical up to the DTFT. Unfortunately, in general, such a simple relationship does not hold in GSP. As a result, the naïve implementation of the vertex domain filtering equation [1.10] does not always have a diagonal response in the graph frequency domain. In other words, the filter coefficient matrix H is not always diagonalizable by the GFT matrix U, i.e. U^THU is not diagonal in general. Therefore, the graph frequency response of H is not always clear when filtering is performed in the vertex domain. This is a clear difference between the filtering of discrete-time signals and that of the graph signals.

From the above description, we can come up with another possibility for the filtering of graph signals: graph signal filtering defined in the graph frequency domain. This is an analog of filtering in the Fourier domain in equation [1.5]. This spectral domain definition of graph signal filtering has many desirable properties listed as follows:

 – diagonal graph frequency response;

 – fast computation;

 – interpretability of pixel-dependent image filtering as graph spectral filtering.

These properties are described further.

As shown in equation [1.5], the convolution of h_n and x_n in the time domain is a multiplication of ĥ(ω) and in the Fourier domain. Filtering in the graph frequency domain utilizes such an analog to define generalized convolution (Shuman et al. 2016b):

[1.13]

where is the ith GFT coefficient of x and the GFT basis u_i is given by the eigendecomposition of the chosen graph operator equation [I.2]. Furthermore, is the graph frequency response of the graph filter. The filtered signal in the vertex domain, y[n], can be easily obtained by transforming ŷ back to where [u_i]_n is the nth element of u_i. This is equivalently written in the matrix form as

[1.14]

where

[1.15]

is a projection matrix in which σ(λ) is a set of indices for repeated eigenvalues, i.e. a set of indices such that Lu_k = λu_k.

For simplicity, let us assume that all eigenvalues are distinct. Under a given GFT basis U, graph frequency domain filtering in equation [1.13] is realized by specifying N graph frequency responses in . Since this is a diagonal matrix, as shown in equation [1.14], its frequency characteristic becomes considerably clear in contrast to that observed in vertex domain filtering. Note that the naïve realization of equation [1.13] requires specific values of λ_i, i.e. graph frequency values. Therefore, the eigenvalues of the graph operator must be given prior to the filtering. Instead, in this case, we can parameterize a continuous spectral response for the range λ ∈ [λ_min, λ_max]. This graph-independent design procedure has been widely implemented in many spectral graph filters, since the eigenvalues often vary significantly in different graphs.

For the classical Fourier domain filtering, it is enough to consider the frequency range ω ∈ [−π, π] (or an arbitrary 2π interval). However, graph frequency varies according to an underlying graph and/or the chosen graph operator. For example, symmetric normalized graph Laplacians have eigenvalues within [0, 2], whereas combinatorial graph Laplacians do not have such a graph-independent maximum bound. The simple maximum bound of combinatorial graph Laplacian is, for example, given as (Anderson Jr and Morley 1985)

[1.16]

where d_u is the degree of the vertex u. Several other improvements on the bound are also found in literature. Although the graph Laplacians mentioned above have a bound of the largest eigenvalue, such bounds are not applicable to the adjacency matrix. Considering this, appropriate care of the graph frequency range must be taken while designing graph filters.

As mentioned, graph frequency domain filtering is an analog of Fourier domain filtering. However, this does not mean we always obtain a vertex domain expression of this similar to equation [1.9]. Hence, we need to compute the GFT of the input signal, which raises a computational issue described as follows. For the GFT, the eigenvector matrix U has to be calculated from the graph operator. The eigendecomposition requires complexity for a dense matrix². This calculation often becomes increasingly complex, especially for big data applications, including image processing.

Typically, graph spectral image processing vectorizes image pixels. Let us assume that we have a grayscale image of size W × H pixels. Its vectorized version is and its corresponding graph operator would be . For example, 4K ultra-high-definition resolution corresponds to W = 3, 840 and H = 2, 160, which leads to WH > 8 × 10⁶: this is too large to perform eigendecomposition, even for a recent high-spec computer. In section 1.6, several fast computation methods of graph spectral filtering will be discussed to alleviate this problem.