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

Downsampling is another typical approach for reducing the computation cost, and this has been used everywhere in image processing applications. A challenge for graph-based image processing is to find a good low-resolution graph, which properly reflects the original pixel structure.

Reducing the size of a graph is called graph reduction or graph coarsening. It is divided into two phases:

 1) Phase 1: reducing the number of nodes;

 2) Phase 2: reconnecting edges for the downsampled pixels.

In image processing, Phase 1 is relatively straightforward. We can assume the original image pixels are nodes on a uniform grid. As in usual image processing, picking up every other node (when the image signal is downsampled by two) will be reasonable.

For more general graphs like those used in point cloud processing, we need to select the “best” set of nodes. This problem is called sampling set selection. Although this is beyond our scope in this chapter, please refer to (Tanaka et al. 2020; Sakiyama et al. 2019c) and references therein.

In contrast to Phase 1, Phase 2 is not very straightforward. If pixels in the original image/block are associated with a graph, the downsampled one should be reconnected by edges, such that the reduced-size graph reflects the original structure. In the general

GSP study, desiderata for the reduced-size graphs have been suggested in Shuman et al. (2016a) as follows:

 1) the reduced-size graph has non-negative edge weights;

 2) the connectivity of the original graph is preserved in the reduced-size graphs;

 3) the spectrum of the reduced-size graph is representative of the original graph;

 4) the reduced-size graph preserves the original structural properties;

 5) if two nodes are connected in the original graph, they should have a similar edge weights in the reduced-size graph;

 6) it is tractable in terms of implementation and computational complexity;

 7) the reduced-size graph preserves the sparsity (i.e. the ratio between the number of nonzero edges and that of pixels) of the original one.

Existing reconnection methods do not always satisfy all of these simultaneously; however, they do exhibit some of these properties. The order of the desired properties depends on applications considered. Major approaches have been summarized in Shuman et al. (2016a).