Graph Spectral Image Processing. Gene Cheung

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

СКАЧАТЬ target="_blank" rel="nofollow" href="#ulink_3fb6141d-ddd2-5807-a264-1fe2a22474a7">[1.10]

      where h(W) is a matrix containing filter coefficients h[n, k](n k) as a function of the adjacency matrix W, in which [h(W)]_n,k = 0 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 СКАЧАТЬ