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

Vertex domain filtering is an analog of filtering in the time domain. However, GSP systems are not shift-invariant: This means node indices do not have any physical meaning, in general. Therefore, the shift of graph signals based on the indices of nodes, similar to that used for discrete-time signals, would be inappropriate. Moreover, the underlying graph will exhibit a highly irregular connectivity, i.e. the degree in each node will vary significantly. For example, the star graph shown in Figure 1.1 has one center node and N − 1 surrounding nodes. It is clear that N − 1 edges are connected to the center node, i.e. the center node has degree N − 1, whereas all of the surrounding nodes have degree 1. In an image processing perspective, such an irregularity comes from the edge and texture regions. An example is provided on the right side of Figure 1.1. Suppose that we construct a graph based on pixel intensity, i.e. pixels are nodes, and they are connected by edges with higher weights when their pixel values are closer. In this situation, pixels along edge/texture directions will be connected to each other strongly with a large degree, whereas those across edge/texture directions may have weaker edges, or may even be disconnected. Filtering based on such a graph will therefore reflect structures in the vertex (i.e. pixel) domain.

Figure 1.1. Left: Star graph with N = 7. Right: Textured region of Barbara

Vertex domain filtering can be defined more formally as follows. Let be a set of p-hop neighborhood nodes of the nth node. Clearly varies according to n.

Vertex domain filtering may be typically defined as a local linear combination of the neighborhood samples

[1.9]

Since varies according to n, [H]_n,k should be appropriately determined for all n. The matrix form of equation [1.9] may be represented as

[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.