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

A graph G(V, E, W) contains a set V of N nodes and a set E of M edges. While directed graphs are also possible, in this book we more commonly assume an undirected graph, where each existing edge (i, j) ∈ E is undirected and contains an edge weight w_i,j ∈ R, which is typically positive. A large positive edge weight w_i,j would mean that samples at nodes i and j are expected to be similar/correlated.

There are many ways to compute appropriate edge weights. Especially common for images, edge weight w_i,j can be computed using a Gaussian kernel, as done in the bilateral filter (Tomasi and Manduchi 1998):

[I.1]

where l_i ∈ R² is the location of pixel i on the 2D image grid, x_i ∈ R is the intensity of pixel i, and and are two parameters. Hence, 0 ≤ w_i,j ≤ 1. Larger geometric and/or photometric distances between pixels i and j would mean a smaller weight w_i,j . Edge weights can alternatively be defined based on local pixel patches, features, etc. (Milanfar 2013b). To a large extent, the appropriate definition of edge weight is application dependent, as will be discussed in various forthcoming chapters.

A graph signal x on G is a discrete signal of dimension N – one sample x_i ∈ R for each node¹ i in V. Assuming that nodes are appropriately labeled from 1 to N,we can simply treat a graph signal as a vector x ∈ R^N .