Graph Spectral Image Processing

Gene Cheung received his PhD in Electrical Engineering and Computer Science from the University of California, Berkeley, USA. He is Associate Professor at York University, Canada, and an IEEE fellow. His research interests include image and graph signal processing.Enrico Magli is Full Professor at Politecnico di Torino, Italy, and is an IEEE fellow. His research interests are within the field of graph signal processing and deep learning for image and video analysis.

• Introduction to Graph Spectral Image Processing xiGene CHEUNG and Enrico MAGLIPart 1. Fundamentals of Graph Signal Processing 1Chapter 1. Graph Spectral Filtering 3Yuichi TANAKA1.1. Introduction 31.2. Review: filtering of time-domain signals 41.3. Filtering of graph signals 51.3.1. Vertex domain filtering 61.3.2. Spectral domain filtering 81.3.3. Relationship between graph spectral filtering and classical filtering 101.4. Edge-preserving smoothing of images as graph spectral filters 111.4.1. Early works 111.4.2. Edge-preserving smoothing 121.5. Multiple graph filters: graph filter banks 151.5.1. Framework 161.5.2. Perfect reconstruction condition 171.6. Fast computation 201.6.1. Subdivision 201.6.2. Downsampling 211.6.3. Precomputing GFT 221.6.4. Partial eigendecomposition 221.6.5. Polynomial approximation 231.6.6. Krylov subspace method 261.7. Conclusion 261.8. References 26Chapter 2. Graph Learning 31Xiaowen DONG, Dorina THANOU, Michael RABBAT and Pascal FROSSARD2.1. Introduction 312.2. Literature review 332.2.1. Statistical models 332.2.2. Physically motivated models 352.3. Graph learning: a signal representation perspective 362.3.1. Models based on signal smoothness 382.3.2. Models based on spectral filtering of graph signals 432.3.3. Models based on causal dependencies on graphs 482.3.4. Connections with the broader literature 502.4. Applications of graph learning in image processing 522.5. Concluding remarks and future directions 552.6. References 57Chapter 3. Graph Neural Networks 63Giulia FRACASTORO and Diego VALSESIA3.1. Introduction 633.2. Spectral graph-convolutional layers 643.3. Spatial graph-convolutional layers 663.4. Concluding remarks 713.5. References 72Part 2. Imaging Applications of Graph Signal Processing 73Chapter 4. Graph Spectral Image and Video Compression 75Hilmi E. EGILMEZ, Yung-Hsuan CHAO and Antonio ORTEGA4.1. Introduction 754.1.1. Basics of image and video compression 774.1.2. Literature review 784.1.3. Outline of the chapter 794.2. Graph-based models for image and video signals 794.2.1. Graph-based models for residuals of predicted signals 814.2.2. DCT/DSTs as GFTs and their relation to 1D models 874.2.3. Interpretation of graph weights for predictive transform coding 884.3. Graph spectral methods for compression 894.3.1. GL-GFT design 894.3.2. EA-GFT design 924.3.3. Empirical evaluation of GL-GFT and EA-GFT 974.4. Conclusion and potential future work 1004.5. References 101Chapter 5. Graph Spectral 3D Image Compression 105Thomas MAUGEY, Mira RIZKALLAH, Navid MAHMOUDIAN BIDGOLI, Aline ROUMY and Christine GUILLEMOT5.1. Introduction to 3D images 1065.1.1. 3D image definition 1065.1.2. Point clouds and meshes 1065.1.3. Omnidirectional images 1075.1.4. Light field images 1095.1.5. Stereo/multi-view images 1105.2. Graph-based 3D image coding: overview 1105.3. Graph construction 1155.3.1. Geometry-based approaches 1175.3.2. Joint geometry and color-based approaches 1215.3.3. Separable transforms 1255.4. Concluding remarks 1265.5. References 128Chapter 6. Graph Spectral Image Restoration 133Jiahao PANG and Jin ZENG6.1. Introduction 1336.1.1. A simple image degradation model 1336.1.2. Restoration with signal priors 1356.1.3. Restoration via filtering 1376.1.4. GSP for image restoration 1406.2. Discrete-domain methods 1416.2.1. Non-local graph-based transform for depth image denoising 1416.2.2. Doubly stochastic graph Laplacian 1426.2.3. Reweighted graph total variation prior 1456.2.4. Left eigenvectors of random walk graph Laplacian 1506.2.5. Graph-based image filtering 1556.3. Continuous-domain methods 1556.3.1. Continuous-domain analysis of graph Laplacian regularization 1566.3.2. Low-dimensional manifold model for image restoration 1636.3.3. LDMM as graph Laplacian regularization 1656.4. Learning-based methods 1676.4.1. CNN with GLR 1696.4.2. CNN with graph wavelet filter 1716.5. Concluding remarks 1726.6. References 173Chapter 7. Graph Spectral Point Cloud Processing 181Wei HU, Siheng CHEN and Dong TIAN7.1. Introduction 1817.2. Graph and graph-signals in point cloud processing 1837.3. Graph spectral methodologies for point cloud processing 1857.3.1. Spectral-domain graph filtering for point clouds 1857.3.2. Nodal-domain graph filtering for point clouds 1887.3.3. Learning-based graph spectral methods for point clouds 1897.4. Low-level point cloud processing 1907.4.1. Point cloud denoising 1917.4.2. Point cloud resampling 1937.4.3. Datasets and evaluation metrics 1987.5. High-level point cloud understanding 1997.5.1. Data auto-encoding for point clouds 1997.5.2. Transformation auto-encoding for point clouds 2067.5.3. Applications of GraphTER in point clouds 2117.5.4. Datasets and evaluation metrics 2117.6. Summary and further reading 2137.7. References 214Chapter 8. Graph Spectral Image Segmentation 221Michael NG8.1. Introduction 2218.2. Pixel membership functions 2228.2.1. Two-class problems 2228.2.2. Multiple-class problems 2268.2.3. Multiple images 2278.3. Matrix properties 2308.4. Graph cuts 2328.4.1. The Mumford–Shah model 2348.4.2. Graph cuts minimization 2358.5. Summary 2378.6. References 237Chapter 9. Graph Spectral Image Classification 241Minxiang YE, Vladimir STANKOVIC, Lina STANKOVIC and Gene CHEUNG9.1. Formulation of graph-based classification problems 2439.1.1. Graph spectral classifiers with noiseless labels 2439.1.2. Graph spectral classifiers with noisy labels 2469.2. Toward practical graph classifier implementation 2479.2.1. Graph construction 2479.2.2. Experimental setup and analysis 2499.3. Feature learning via deep neural network 2559.3.1. Deep feature learning for graph construction 2589.3.2. Iterative graph construction 2609.3.3. Toward practical implementation of deep feature learning 2629.3.4. Analysis on iterative graph construction for robust classification 2679.3.5. Graph spectrum visualization 2699.3.6. Classification error rate comparison using insufficient training data 2709.3.7. Classification error rate comparison using sufficient training data with label noise 2709.4. Conclusion 2719.5. References 272Chapter 10. Graph Neural Networks for Image Processing 277Giulia FRACASTORO and Diego VALSESIA10.1. Introduction 27710.2. Supervised learning problems 27810.2.1. Point cloud classification 27810.2.2. Point cloud segmentation 28110.2.3. Image denoising 28310.3. Generative models for point clouds 28610.3.1. Point cloud generation 28610.3.2. Shape completion 29110.4. Concluding remarks 29410.5. References 294List of Authors 299Index 301