Efficient Predictive Algorithms for Image Compression

This book discusses efficient prediction techniques for the current state-of-the-art High Efficiency Video Coding (HEVC) standard, focusing on the compression of a wide range of video signals, such as 3D video, Light Fields and natural images. The authors begin with a review of the state-of-the-art predictive coding methods and compression technologies for both 2D and 3D multimedia contents, which provides a good starting point for new researchers in the field of image and video compression. New prediction techniques that go beyond the standardized compression technologies are then presented and discussed. In the context of 3D video, the authors describe a new predictive algorithm for the compression of depth maps, which combines intra-directional prediction, with flexible block partitioning and linear residue fitting. New approaches are described for the compression of Light Field and still images, which enforce sparsity constraints on linear models. The Locally Linear Embedding-based prediction method is investigated for compression of Light Field images based on the HEVC technology. A new linear prediction method using sparse constraints is also described, enabling improved coding performance of the HEVC standard, particularly for images with complex textures based on repeated structures. Finally, the authors present a new, generalized intra-prediction framework for the HEVC standard, which unifies the directional prediction methods used in the current video compression standards, with linear prediction methods using sparse constraints. Experimental results for the compression of natural images are provided, demonstrating the advantage of the unified prediction framework over the traditional directional prediction modes used in HEVC standard. Presents a state-of-the-art review of existing prediction technologies for compression of both 2D and 3D multimedia content; Discusses the most recent advances beyond the current, standardized technologies for image and video compression, such as using the HEVC standard in the context of natural images, 3D and Light Field content; Includes new prediction methods based on alternative techniques and concepts, including flexible block partitioning, linear prediction, sparse representation Contents 5 List of Figures 8 List of Tables 13 Acronyms 15 1 Introduction 18 1.1 Motivation 18 1.2 Objectives and Contributions of the Book 20 1.3 Outline of the Book 22 2 Prediction Techniques for Image and Video Coding 24 2.1 Digital Video Representation 24 2.2 Image Prediction Overview 26 2.3 State-of-the-Art Prediction Methods 30 2.3.1 Intra-Frame Prediction 30 2.3.1.1 Directional Prediction Modes 31 2.3.1.2 Planar and DC Prediction Modes 31 2.3.1.3 Sample Smoothing 32 2.3.1.4 Prediction Mode Coding 33 2.3.1.5 Chroma Intra Prediction 34 2.3.2 Inter-Frame Prediction 34 2.3.2.1 Motion Compensation Using Block-Matching Algorithm 34 2.3.2.2 Merge Mode 36 2.3.2.3 Motion Vector Prediction 37 2.4 Least-Squares Prediction Methods 37 2.4.1 Linear Prediction of Images and Video Using LSP 38 2.4.2 Context-Based Adaptive LSP 39 2.4.3 Block-Based LSP 40 2.4.4 Spatio-Temporal LSP 41 2.5 Sparse Representation for Image Prediction 42 2.5.1 Sparse Prediction Problem Formulation 43 2.5.2 Matching Pursuit Methods 45 2.5.2.1 Orthogonal Matching Pursuit 46 2.5.3 Template Matching Algorithm 46 2.5.4 Neighbour Embedding Methods 47 2.5.4.1 Image Prediction Based on LLE 48 2.6 Conclusions 50 3 Image and Video Coding Standards 51 3.1 Hybrid Video Compression 51 3.2 Compression of 2D Video 53 3.2.1 H.265/HEVC Standard 54 3.2.1.1 HEVC Coding Structures 55 3.2.1.2 Intra-Frame Prediction 57 3.2.1.3 Inter-Frame Prediction 58 3.2.1.4 Transform and Quantisation 59 3.2.1.5 Entropy Coding 59 3.2.1.6 In-Loop Filters 60 3.2.1.7 HEVC Screen Content Coding Extensions 60 3.2.2 Experimental Results 62 3.3 Compression of 3D Video 65 3.3.1 3D Video Systems 65 3.3.1.1 Stereo Video 67 3.3.1.2 Multiview Video 69 3.3.1.3 Multiview Video+Depth 70 3.3.1.4 Holoscopic Video 72 3.3.2 3D Video Coding Standards 74 3.3.2.1 Dependent View Coding Tools 75 3.3.2.2 Depth Map Coding Tools 76 3.3.3 Experimental Results 77 3.4 Conclusions 80 4 Compression of Depth Maps Using Predictive Coding 81 4.1 Overview of Intra Techniques for Depth Map Coding 82 4.1.1 Directional Intra Prediction 83 4.1.2 Depth Modelling Modes 84 4.1.3 Depth Lookup Table 85 4.1.4 Segment-Wise DC Coding 85 4.1.5 Single Depth Intra Mode 86 4.1.6 View Synthesis Optimisation 86 4.2 Overview of Predictive Depth Coding 87 4.3 Coding Techniques of PDC Algorithm 89 4.3.1 Flexible Block Partitioning 89 4.3.2 Directional Intra Prediction Framework 91 4.3.3 Constrained Depth Modelling Mode 93 4.3.4 Residual Signal Coding 95 4.3.5 Bitstream Syntax and Context Modelling 97 4.4 PDC Encoder Control 99 4.5 Experimental Results 100 4.5.1 Evaluation of PDC Algorithm for Intra Coding 101 4.5.2 Evaluation of PDC Algorithm Using VSO Metric 107 4.5.3 Evaluation of PDC Algorithm Combined with 3D-HEVC Standard 109 4.6 Conclusions 111 5 Sparse Representation Methods for Image Prediction 112 5.1 3D Holoscopic Image Coding Using LLE-Based Prediction 113 5.1.1 Proposed HEVC Encoder Using LLE-Based Prediction 114 5.1.2 Experimental Results 116 5.2 The Sparse-LSP Method for Intra Prediction 119 5.2.1 Algorithm Description 120 5.2.2 Mathematical Interpretation 122 5.3 Application of Sparse-LSP to HEVC Standard 124 5.3.1 Implementation Details 125 5.3.2 Experimental Results 126 5.4 Conclusions 130 6 Generalised Optimal Sparse Predictors 131 6.1 Two-Stage Interpretation of Directional Prediction 132 6.2 Generalising Directional Prediction 136 6.3 Sparse Model Estimation Algorithms 138 6.3.1 Matching Pursuit Algorithms 139 6.3.2 Least Angle Regression 139 6.3.3 LASSO Regression 140 6.3.4 Elastic Net Regression 141 6.4 Proposed Algorithm Based on Adaptive Sparse Predictors for HEVC 142 6.5 Experimental Results 144 6.5.1 Effect of Sparsity Constraints 145 6.5.2 Regularisation Parameters for Optimal RD Performance 147 6.5.3 RD Performance Relative to Other Intra Prediction Methods 154 6.6 Conclusions 157 7 Conclusions and Other Research Directions 158 A Test Signals 162 A.1 Test Images 162 A.2 Holoscopic Images 166 References 169 Index 176 Front Matter....Pages i-xix Introduction....Pages 1-6 Prediction Techniques for Image and Video Coding....Pages 7-33 Image and Video Coding Standards....Pages 35-64 Compression of Depth Maps Using Predictive Coding....Pages 65-95 Sparse Representation Methods for Image Prediction....Pages 97-115 Generalised Optimal Sparse Predictors....Pages 117-143 Conclusions and Other Research Directions....Pages 145-148 Back Matter....Pages 149-169