Gene Cheung - Graph Spectral Image Processing

1 Cover

2 Title Page SCIENCES Image , Field Director – Laure Blanc-Feraud Compression, Coding and Protection of Images and Videos , Subject Head – Christine Guillemot

3 Copyright First published 2021 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd 27-37 St George’s Road London SW19 4EU UK www.iste.co.uk John Wiley & Sons, Inc. 111 River Street Hoboken, NJ 07030 USA www.wiley.com © ISTE Ltd 2021 The rights of Gene Cheung and Enrico Magli to be identified as the author of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Control Number: 2021932054 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 978-1-78945-028-6 ERC code: PE7 Systems and Communication Engineering PE7_7 Signal processing

4 Introduction to Graph Spectral Image Processing I.1. Introduction I.2. Graph definition I.3. Graph spectrum I.4. Graph variation operators I.5. Graph signal smoothness priors I.6. References

5 PART 1 Fundamentals of Graph Signal Processing 1 Graph Spectral Filtering 1.1. Introduction 1.2. Review: filtering of time-domain signals 1.3. Filtering of graph signals 1.4. Edge-preserving smoothing of images as graph spectral filters 1.5. Multiple graph filters: graph filter banks 1.6. Fast computation 1.7. Conclusion 1.8. References 2 Graph Learning 2.1. Introduction 2.2. Literature review 2.3. Graph learning: a signal representation perspective 2.4. Applications of graph learning in image processing 2.5. Concluding remarks and future directions 2.6. References 3 Graph Neural Networks 3.1. Introduction 3.2. Spectral graph-convolutional layers 3.3. Spatial graph-convolutional layers 3.4. Concluding remarks 3.5. References

6 PART 2 Imaging Applications of Graph Signal Processing 4 Graph Spectral Image and Video Compression 4.1. Introduction 4.2. Graph-based models for image and video signals 4.3. Graph spectral methods for compression 4.4. Conclusion and potential future work 4.5. References 5 Graph Spectral 3D Image Compression 5.1. Introduction to 3D images 5.2. Graph-based 3D image coding: overview 5.3. Graph construction 5.4. Concluding remarks 5.5. References 6 Graph Spectral Image Restoration 6.1. Introduction 6.2. Discrete-domain methods 6.3. Continuous-domain methods 6.4. Learning-based methods 6.5. Concluding remarks 6.6. References 7 Graph Spectral Point Cloud Processing 7.1. Introduction 7.2. Graph and graph-signals in point cloud processing 7.3. Graph spectral methodologies for point cloud processing 7.4. Low-level point cloud processing 7.5. High-level point cloud understanding 7.6. Summary and further reading 7.7. References 8 Graph Spectral Image Segmentation 8.1. Introduction 8.2. Pixel membership functions 8.3. Matrix properties 8.4. Graph cuts 8.5. Summary 8.6. References 9 Graph Spectral Image Classification 9.1. Formulation of graph-based classification problems 9.2. Toward practical graph classifier implementation 9.3. Feature learning via deep neural network 9.4. Conclusion 9.5. References 10 Graph Neural Networks for Image Processing 10.1. Introduction 10.2. Supervised learning problems 10.3. Generative models for point clouds 10.4. Concluding remarks 10.5. References

7 List of Authors

8 Index

9 End User License Agreement

1 Introduction to Graph Spectral Image Processing Figure I.1. Visual comparison of JPEG dequantization methods for a butterfly at QF = 5. The corresponding PSNR values are also given. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip

2 Chapter 1 Figure 1.1. Left: Star graph with N = 7 . Right: Textured region of Barbara Figure 1.2. Comparison of approximation errors in . For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 1.3. Image denoising example using bilateral filters. From left to right: Original, noisy (PSNR: 20.02 dB), bilateral filter in the pixel domain (PSNR: 26.23 dB), and bilateral filter in the graph frequency domain (PSNR: 27.14 dB). Both bilateral filters use the same parameters Figure 1.4. Framework of graph filter bank

3 Chapter 2Figure 2.1. The different choices of graph lead to different representations of the same signal. The signal forms a smooth representation on the graph (a) as its values vary slowly along the edges of the graph, and it mainly consists of low-frequency components in the graph spectral domain (b). The representation of the same signal is less smooth on the graph (c), which consists of both low and high frequency components in the graph spectral domain (d). Figure from (Dong et al. 2019) with permission. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 2.2. Diffusion processes on the graph defined by a heat diffusion kernel (top right) and a graph shift operator (bottom right). Figure from (Dong et al. 2019) with permission. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 2.3. (a) A graph signal. (b-e) Its decomposition in four localized simple components. Each component is a heat diffusion process (e−τL) at time τ that has started from different network nodes. The size and the color of each ball indicates the value of the signal at each vertex of the graph. Figure from Thanou et al. (2017) with permission. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 2.4. A graph signal x at time step t is modeled as a linear combination of its observations in the past T time steps and a random noise process n[t]. Figure from Dong et al. (2019) with permission. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 2.5. Inferring a graph for image coding. Figure from (Dong et al. 2019) with permission. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip

4 Chapter 3Figure 3.1. Spatial graph-convolutional layer: an edge function weighs the node feature vectors, and an aggregation function merges them. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 3.2. Edge-conditioned convolution. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 3.3. Circulant approximation of a fully connected layer. On the left: A traditional parameter matrix without any structure. On the right: A stack of partial circulant matrices, where the weights in a row are shifted for a number of following rows before being replaced. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip Figure 3.4. Low-rank approximation of the last layer of the network. For a color version of this figure, see www.iste.co.uk/cheung/graph.zip

5 Chapter 4Figure 4.1. Separable and non-separable transforms: (Left) For an N × N block, separable transforms are composed of two (possibly distinct) N ×N transforms, Urow and Ucol, applied to rows and columns of the block. (Right) Non-separable transforms apply a N2×N2 linear transformation using U Figure 4.2. Building blocks of a typical image/video encoder and decoder consisting of three main steps, which are (i) prediction, (ii) transformation, and (iii) quantization and entropy coding. This figure is adapted from Figure 1 in Egilmez et al. (2020a)