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

Let us begin with the history before the GSP era. In the mid-1990s, Taubin proposed seminal works on smoothing using graph spectral analysis for 3D mesh processing (Taubin 1995; Taubin et al. 1996)³. He determined the edge weights of polygon meshes using the Euclidean (geometric) distance between nodes. Assuming as a 3-D coordinate of the ith node, the edge weight is then defined as

[1.20]

where η is the normalizing factor and φ(p_i, p_j) is a non-negative function, which assigns a large weight if p_i and p_j are close. The typical choice of φ(p_i, p_j) will be

The matrix W is symmetric. If we choose φ(p_i, p_i) = 0, its diagonal elements would become zero, and as a result, W could be viewed as a normalized adjacency matrix. The coordinates are then smoothed by a graph low-pass filter, after computing the GFT basis U. Similar approaches to this method have been used in several computer graphics/vision tasks (Zhang et al. 2010; Vallet and Lévy 2008; Desbrun et al. 1999; Fleishman et al. 2003; Kim and Rossignac 2005).

For image smoothing, filtering with a heat kernel represented in the graph frequency domain has also been proposed by Zhang and Hancock (2008). In this work, the edge weights of the pixel graph are computed according to photometric distance, i.e. large weights are assigned to the edges whose ends have similar pixel values and vice versa. Additionally, the graph spectral filter is defined as a solution for the heat equation on the graph, and is expressed as follows:

[1.21]

where t > 0 is an arbitrary parameter that helps control the spreading speed caused by diffusion. Note that this method still needs eigendecomposition of the graph Laplacian if we decide to implement equation [1.21] naïvely. Instead, (Zhang and Hancock 2008) represent equation [1.21] using the Taylor series around the origin as follows:

[1.22]

By truncating the above equation with an arbitrary order K, we can approximate the heat kernel as a finite-order polynomial (Hammond et al. 2011; Shuman et al. 2013). In Zhang and Hancock (2008), the Krylov subspace method is used, along with equation [1.22] to approximate the graph filter. The polynomial method for graph spectral smoothing is detailed in section 1.6.5.

Figure 1.2 depicts the approximation error of the heat kernel using the Taylor series. Clearly, its approximation accuracy gets significantly worse when λ is away from 0. Since the maximum eigenvalue λ_max highly depends on the graph used, it is better to use different approximation methods like the Chebyshev approximation, which is introduced in section 1.6.