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

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.