Graph Spectral Image Processing. Gene Cheung

if

.

      The vertex domain filtering in equations [1.9] and [1.10] requires the determination of filter coefficients, in general; moreover, it sometimes needs increased computational complexity. Typically, [H]_n,k may be parameterized in the following form:

[1.11]

      where h_p is a real value and

is a masked adjacency matrix that only contains p-hop neighborhood elements of W. It is formulated as

[1.12]

The number of parameters required in equation [1.12] is P, which is significantly smaller than that required in equation [1.10].

One may find a similarity between the time domain filtering in equation [1.2] and the parameterized vertex domain filtering in equation [1.11]. In fact, if the underlying graph is a cycle graph, equation [1.11] coincides with equation [1.2] with a proper definition of W_p. However, they do not coincide in general cases: It is easily confirmed that the sum of each row of the filter coefficient matrix in equation [1.11] is not constant due to the irregular nature of the graph, whereas

is a constant in time-domain filtering. Therefore, the parameters of equation [1.11] should be determined carefully.

      1.3.2. Spectral domain filtering

      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]