Graph Spectral Image Processing. Gene Cheung

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

СКАЧАТЬ labeled from 1 to N,we can simply treat a graph signal as a vector x ∈ R^N .

I.3. Graph spectrum

      Denote by W ∈ R^N×N an adjacency matrix, where the (i, j)th entry is W_i,j = w_i,j. Next, denote by D ∈ R^N×N a diagonal degree matrix, where the (i, i)th entry is D_i,i = j W_i,j. A combinatorial graph Laplacian matrix L is L = D − W (Shuman et al. 2013). Because L is real and symmetric, one can show, via the spectral theorem, that it can be eigen-decomposed into:

      [I.2]

where Λ is a diagonal matrix containing real eigenvalues λ_k along the diagonal, and U is an eigen-matrix composed of orthogonal eigenvectors u_i as columns. If all edge weights w_i,j are restricted to be positive, then graph Laplacian L can be proven to be positive semi-definite (PSD) (Chung 1997)², meaning that λ_k ≥ 0, ∀k and xLx ≥ 0, ∀x. Non-negative eigenvalues λ_k can be interpreted as graph frequencies, and eigenvectors U can be interpreted as corresponding graph Fourier modes. Together they define the graph spectrum for graph G.

      The set of eigenvectors U for L collectively form the GFT (Shuman et al. 2013), which can be used to decompose a graph signal x into its frequency components via α = Ux. In fact, one can interpret GFT as a generalization of known discrete transforms like the Discrete Cosine Transform (DCT) (see Shuman et al. 2013 for details).

      Note that if the multiplicity m_k of an eigenvalue λ_k is larger than 1, then the set of eigenvectors that span the corresponding eigen-subspace of dimension m_k is non-unique. In this case, it is necessary to specify the graph spectrum as the collection of eigenvectors U themselves.

      If we also consider negative edge weights w_i,j that reflect inter-pixel dissimilarity/anti-correlation, then graph Laplacian L can be indefinite. We will discuss a few recent works (Su et al. 2017; Cheung et al. 2018) that employ negative edges in later chapters.

I.4. Graph variation operators

      Closely related to the combinatorial graph, Laplacian L, are other variants of Laplacian operators, each with their own unique spectral properties. A normalized graph Laplacian L_n = D^−1/2LD^−1/2 is a symmetric normalized variant of L. In contrast, a random walk graph Laplacian L_r = D⁻¹L is an asymmetric normalized variant of L.A generalized graph Laplacian L_g = L + diag(D) is a graph Laplacian with self-loops d_i,i at nodes i – called the loopy graph Laplacian in Dörfler and Bullo (2013) – resulting in a general symmetric matrix with non-positive off-diagonal entries for a positive graph (Biyikoglu et al. 2005). Eigen-decomposition can also be performed on these operators to acquire a set of graph frequencies and graph Fourier modes. For example, normalized variants L_n and L_r (which are similarity transforms of each other) share the same eigenvalues between 0 and 2. While L and L_n are both symmetric, L_n does not have the constant vector as an eigenvector. Asymmetric L_r can be symmetrized via left and right diagonal matrix multiplications (Milanfar 2013a). Different variation operators will be used throughout the book for different applications.

I.5. Graph signal smoothness priors

      Traditionally, for graph G with positive edge weights, signal x is considered smooth if each sample x_i on node i is similar to samples x_j on neighboring nodes j with large w_i,j. In the graph frequency domain, it means that x mostly contains low graph frequency components, i.e. coefficients α = Ux are zeros (or mostly zeros) for high frequencies. The smoothest signal is the constant vector – the first eigenvector u₁ for L, corresponding to the smallest eigenvalue λ₁ = 0.

      Mathematically, we can declare that a signal x is smooth if its graph Laplacian regularizer (GLR) xLx is small (Pang and Cheung 2017). GLR can be expressed as:

      [I.3]

      Because L is PSD, xLx is lower bounded by 0 and achieved when x = cu₁ for some scalar constant c. One can also define GLR using the normalized graph Laplacian L_n instead of L, resulting in xL_nx. The caveats is that the constant vector u₁ – typically the most common signal in imaging – is no longer the first eigenvector, and thus

.

      In Chen et al. (2015), the adjacency matrix W is interpreted as a shift operator, and thus, graph signal smoothness is instead defined as the difference between a signal x and its shifted version Wx. Specifically, graph total variation (GTV) based on l_p-norm is:

[I.4]

where λ_max is the eigenvalue of W with the largest magnitude (also called the spectral radius), and p is a chosen integer. As a variant to equation [I.4], a quadratic smoothness prior is defined in Romano et al. (2017), using a row-stochastic version W_n = D⁻¹W of the adjacency matrix W:

[I.5]

To avoid confusion, we will call equation [I.5] the graph shift variation (GSV) prior. GSV is easier to use in practice than GTV, since the computation of λ_max is required for GTV. Note that GSV, as defined in equation [I.5], can also be used for signals on directed graphs.

СКАЧАТЬ