IMAGE and VIDEO COMPRESSION for MULTIMEDIA ENGINEERING Fundamentals, Algorithms,

Contents Section I Fundamentals Chapter 1 Introduction 1.1 Practical Needs for Image and Video Compression 1.2 Feasibility of Image and Video Compression 1.2.1 Statistical Redundancy 1.2.2 Psychovisual Redundancy 1.3 Visual Quality Measurement 1.3.1 Subjective Quality Measurement 1.3.2 Objective Quality Measurement 1.4 Information Theory Results 1.4.1 Entropy 1.4.2 Shannon’s Noiseless Source Coding Theorem 1.4.3 Shannon’s Noisy Channel Coding Theorem 1.4.4 Shannon’s Source Coding Theorem 1.4.5 Information Transmission Theorem 1.5 Summary 1.6 Exercises References Chapter 2 Quantization 2.1 Quantization and the Source Encoder 2.2 Uniform Quantization 2.2.1 Basics 2.2.2 Optimum Uniform Quantizer 2.3 Nonuniform Quantization 2.3.1 Optimum (Nonuniform) Quantization 2.3.2 Companding Quantization 2.4 Adaptive Quantization 2.4.1 Forward Adaptive Quantization 2.4.2 Backward Adaptive Quantization 2.4.3 Adaptive Quantization with a One-Word Memory 2.4.4 Switched Quantization 2.5 PCM 2.6 Summary 2.7 Exercises References Chapter 3 Differential Coding 3.1 Introduction to DPCM 3.1.1 Simple Pixel-to-Pixel DPCM 3.1.2 General DPCM Systems 3.2 Optimum Linear Prediction (C) 2000 by CRC Press LLC 3.2.1 Formulation 3.2.2 Orthogonality Condition and Minimum Mean Square Error 3.2.3 Solution to Yule-Walker Equations 3.3 Some Issues in the Implementation of DPCM 3.3.1 Optimum DPCM System 3.3.2 1-D, 2-D, and 3-D DPCM 3.3.3 Order of Predictor 3.3.4 Adaptive Prediction 3.3.5 Effect of Transmission Errors 3.4 Delta Modulation 3.5 Interframe Differential Coding 3.5.1 Conditional Replenishment 3.5.2 3-D DPCM 3.5.3 Motion-Compensated Predictive Coding 3.6 Information-Preserving Differential Coding 3.7 Summary 3.8 Exercises References Chapter 4 Transform Coding 4.1 Introduction 4.1.1 Hotelling Transform 4.1.2 Statistical Interpretation 4.1.3 Geometrical Interpretation 4.1.4 Basis Vector Interpretation 4.1.5 Procedures of Transform Coding 4.2 Linear Transforms 4.2.1 2-D Image Transformation Kernel 4.2.2 Basis Image Interpretation 4.2.3 Subimage Size Selection 4.3 Transforms of Particular Interest 4.3.1 Discrete Fourier Transform (DFT) 4.3.2 Discrete Walsh Transform (DWT) 4.3.3 Discrete Hadamard Transform (DHT) 4.3.4 Discrete Cosine Transform (DCT) 4.3.5 Performance Comparison 4.4 Bit Allocation 4.4.1 Zonal Coding 4.4.2 Threshold Coding 4.5 Some Issues 4.5.1 Effect of Transmission Errors 4.5.2 Reconstruction Error Sources 4.5.3 Comparison Between DPCM and TC 4.5.4 Hybrid Coding 4.6 Summary 4.7 Exercises References Chapter 5 Variable-Length Coding: Information Theory Results (II) 5.1 Some Fundamental Results (C) 2000 by CRC Press LLC 5.1.1 Coding an Information Source 5.1.2 Some Desired Characteristics 5.1.3 Discrete Memoryless Sources 5.1.4 Extensions of a Discrete Memoryless Source 5.2 Huffman Codes 5.2.1 Required Rules for Optimum Instantaneous Codes 5.2.2 Huffman Coding Algorithm 5.3 Modified Huffman Codes 5.3.1 Motivation 5.3.2 Algorithm 5.3.3 Codebook Memory Requirement 5.3.4 Bounds on Average Codeword Length 5.4 Arithmetic Codes 5.4.1 Limitations of Huffman Coding 5.4.2 Principle of Arithmetic Coding 5.4.3 Implementation Issues 5.4.4 History 5.4.5 Applications 5.5 Summary 5.6 Exercises References Chapter 6 Run-Length and Dictionary Coding: Information Theory Results (III) 6.1 Markov Source Model 6.1.1 Discrete Markov Source 6.1.2 Extensions of a Discrete Markov Source 6.1.3 Autoregressive (AR) Model 6.2 Run-Length Coding (RLC) 6.2.1 1-D Run-Length Coding 6.2.2 2-D Run-Length Coding 6.2.3 Effect of Transmission Error and Uncompressed Mode 6.3 Digital Facsimile Coding Standards 6.4 Dictionary Coding 6.4.1 Formulation of Dictionary Coding 6.4.2 Categorization of Dictionary-Based Coding Techniques 6.4.3 Parsing Strategy 6.4.4 Sliding Window (LZ77) Algorithms 6.4.5 LZ78 Algorithms 6.5 International Standards for Lossless Still Image Compression 6.5.1 Lossless Bilevel Still Image Compression 6.5.2 Lossless Multilevel Still Image Compression 6.6 Summary 6.7 Exercises References Section II Still Image Compression Chapter 7 Still Image Coding Standard: JPEG 7.1 Introduction 7.2 Sequential DCT-Based Encoding Algorithm (C) 2000 by CRC Press LLC 7.3 Progressive DCT-Based Encoding Algorithm 7.4 Lossless Coding Mode 7.5 Hierarchical Coding Mode 7.6 Summary 7.7 Exercises References Chapter 8 Wavelet Transform for Image Coding 8.1 Review of the Wavelet Transform 8.1.1 Definition and Comparison with Short-Time Fourier Transform 8.1.2 Discrete Wavelet Transform 8.2 Digital Wavelet Transform for Image Compression 8.2.1 Basic Concept of Image Wavelet Transform Coding 8.2.2 Embedded Image Wavelet Transform Coding Algorithms 8.3 Wavelet Transform for JPEG-2000 8.3.1 Introduction of JPEG-2000 8.3.2 Verification Model of JPEG-2000 8.4 Summary 8.5 Exercises References Chapter 9 Nonstandard Image Coding 9.1 Introduction 9.2 Vector Quantization 9.2.1 Basic Principle of Vector Quantization 9.2.2 Several Image Coding Schemes with Vector Quantization 9.2.3 Lattice VQ for Image Coding 9.3 Fractal Image Coding 9.3.1 Mathematical Foundation 9.3.2 IFS-Based Fractal Image Coding 9.3.3 Other Fractal Image Coding Methods 9.4 Model-Based Coding 9.4.1 Basic Concept 9.4.2 Image Modeling 9.5 Summary 9.6 Exercises References Section III Motion Estimation and Compression Chapter 10 Motion Analysis and Motion Compensation 10.1 Image Sequences 10.2 Interframe Correlation 10.3 Frame Replenishment 10.4 Motion-Compensated Coding 10.5 Motion Analysis 10.5.1 Biological Vision Perspective 10.5.2 Computer Vision Perspective 10.5.3 Signal Processing Perspective (C) 2000 by CRC Press LLC 10.6 Motion Compensation for Image Sequence Processing 10.6.1 Motion-Compensated Interpolation 10.6.2 Motion-Compensated Enhancement 10.6.3 Motion-Compensated Restoration 10.6.4 Motion-Compensated Down-Conversion 10.7 Summary 10.8 Exercises References Chapter 11 Block Matching 11.1 Nonoverlapped, Equally Spaced, Fixed Size, Small Rectangular Block Matching 11.2 Matching Criteria 11.3 Searching Procedures 11.3.1 Full Search 11.3.2 2-D Logarithm Search 11.3.3 Coarse-Fine Three-Step Search 11.3.4 Conjugate Direction Search 11.3.5 Subsampling in the Correlation Window 11.3.6 Multiresolution Block Matching 11.3.7 Thresholding Multiresolution Block Matching 11.4 Matching Accuracy 11.5 Limitations with Block Matching Techniques 11.6 New Improvements 11.6.1 Hierarchical Block Matching 11.6.2 Multigrid Block Matching 11.6.3 Predictive Motion Field Segmentation 11.6.4 Overlapped Block Matching 11.7 Summary 11.8 Exercises References Chapter 12 PEL Recursive Technique 12.1 Problem Formulation 12.2 Descent Methods 12.2.1 First-Order Necessary Conditions 12.2.2 Second-Order Sufficient Conditions 12.2.3 Underlying Strategy 12.2.4 Convergence Speed 12.2.5 Steepest Descent Method 12.2.6 Newton-Raphson’s Method 12.2.7 Other Methods 12.3 Netravali-Robbins Pel Recursive Algorithm 12.3.1 Inclusion of a Neighborhood Area 12.3.2 Interpolation 12.3.3 Simplification 12.3.4 Performance 12.4 Other Pel Recursive Algorithms 12.4.1 The Bergmann Algorithm (1982) 12.4.2 The Bergmann Algorithm (1984) 12.4.3 The Cafforio and Rocca Algorithm 12.4.4 The Walker and Rao Algorithm (C) 2000 by CRC Press LLC 12.5 Performance Comparison 12.6 Summary 12.7 Exercises References Chapter 13 Optical Flow 13.1 Fundamentals 13.1.1 2-D Motion and Optical Flow 13.1.2 Aperture Problem 13.1.3 Ill-Posed Inverse Problem 13.1.4 Classification of Optical Flow Techniques 13.2 Gradient-Based Approach 13.2.1 The Horn and Schunck Method 13.2.2 Modified Horn and Schunck Method 13.2.3 The Lucas and Kanade Method 13.2.4 The Nagel Method 13.2.5 The Uras, Girosi, Verri, and Torre Method 13.3 Correlation-Based Approach 13.3.1 The Anandan Method 13.3.2 The Singh Method 13.3.3 The Pan, Shi, and Shu Method 13.4 Multiple Attributes for Conservation Information 13.4.1 The Weng, Ahuja, and Huang Method 13.4.2 The Xia and Shi Method 13.5 Summary 13.6 Exercises References Chapter 14 Further Discussion and Summary on 2-D Motion Estimation 14.1 General Characterization 14.1.1 Aperture Problem 14.1.2 Ill-Posed Inverse Problem 14.1.3 Conservation Information and Neighborhood Information 14.1.4 Occlusion and Disocclusion 14.1.5 Rigid and Nonrigid Motion 14.2 Different Classifications 14.2.1 Deterministic Methods vs. Stochastic Methods 14.2.2 Spatial Domain Methods vs. Frequency Domain Methods 14.2.3 Region-Based Approaches vs. Gradient-Based Approaches 14.2.4 Forward vs. Backward Motion Estimation 14.3 Performance Comparison Among Three Major Approaches 14.3.1 Three Representatives 14.3.2 Algorithm Parameters 14.3.3 Experimental Results and Observations 14.4 New Trends 14.4.1 DCT-Based Motion Estimation 14.5 Summary 14.6 Exercises References (C) 2000 by CRC Press LLC Section IV Video Compression Chapter 15 Fundamentals of Digital Video Coding 15.1 Digital Video Representation 15.2 Information Theory Results (IV): Rate Distortion Function of Video Signal 15.3 Digital Video Formats 15.4 Current Status of Digital Video/Image Coding Standards 15.5 Summary 15.6 Exercises References Chapter 16 Digital Video Coding Standards — MPEG-1/2 Video 16.1 Introduction 16.2 Features of MPEG-1/2 Video Coding 16.2.1 MPEG-1 Features 16.2.2 MPEG-2 Enhancements 16.3 MPEG-2 Video Encoding 16.3.1 Introduction 16.3.2 Preprocessing 16.3.3 Motion Estimation and Motion Compensation 16.4 Rate Control 16.4.1 Introduction of Rate Control 16.4.2 Rate Control of Test Model 5 (TM5) for MPEG-2 16.5 Optimum Mode Decision 16.5.1 Problem Formation 16.5.2 Procedure for Obtaining the Optimal Mode 16.5.3 Practical Solution with New Criteria for the Selection of Coding Mode 16.6 Statistical Multiplexing Operations on Multiple Program Encoding 16.6.1 Background of Statistical Multiplexing Operation 16.6.2 VBR Encoders in StatMux 16.6.3 Research Topics of StatMux 16.7 Summary 16.8 Exercises References Chapter 17 Application Issues of MPEG-1/2 Video Coding 17.1 Introduction 17.2 ATSC DTV Standards 17.2.1 A Brief History 17.2.2 Technical Overview of ATSC Systems 17.3 Transcoding with Bitstream Scaling 17.3.1 Background 17.3.2 Basic Principles of Bitstream Scaling 17.3.3 Architectures of Bitstream Scaling 17.3.4 Analysis 17.4 Down-Conversion Decoder 17.4.1 Background 17.4.2 Frequency Synthesis Down-Conversion (C) 2000 by CRC Press LLC 17.4.3 Low-Resolution Motion Compensation 17.4.4 Three-Layer Scalable Decoder 17.4.5 Summary of Down-Conversion Decoder 17.4.6 DCT-to-Spatial Transformation 17.4.7 Full-Resolution Motion Compensation in Matrix Form 17.5 Error Concealment 17.5.1 Background 17.5.2 Error Concealment Algorithms 17.5.3 Algorithm Enhancements 17.5.4 Summary of Error Concealment 17.6 Summary 17.7 Exercises References Chapter 18 MPEG-4 Video Standard: Content-Based Video Coding 18.1 Introduction 18.2 MPEG-4 Requirements and Functionalities 18.2.1 Content-Based Interactivity 18.2.2 Content-Based Efficient Compression 18.2.3 Universal Access 18.2.4 Summary of MPEG-4 Features 18.3 Technical Description of MPEG-4 Video 18.3.1 Overview of MPEG-4 Video 18.3.2 Motion Estimation and Compensation 18.3.3 Texture Coding 18.3.4 Shape Coding 18.3.5 Sprite Coding 18.3.6 Interlaced Video Coding 18.3.7 Wavelet-Based Texture Coding 18.3.8 Generalized Spatial and Temporal Scalability 18.3.9 Error Resilience 18.4 MPEG-4 Visual Bitstream Syntax and Semantics 18.5 MPEG-4 Video Verification Model 18.5.1 VOP-Based Encoding and Decoding Process 18.5.2 Video Encoder 18.5.3 Video Decoder 18.6 Summary 18.7 Exercises Reference Chapter 19 ITU-T Video Coding Standards H.261 and H.263 19.1 Introduction 19.2 H.261 Video-Coding Standard 19.2.1 Overview of H.261 Video-Coding Standard 19.2.2 Technical Detail of H.261 19.2.3 Syntax Description 19.3 H.263 Video-Coding Standard 19.3.1 Overview of H.263 Video Coding 19.3.2 Technical Features of H.263 19.4 H.263 Video-Coding Standard Version 2 (C) 2000 by CRC Press LLC 19.4.1 Overview of H.263 Version 2 19.4.2 New Features of H.263 Version 2 19.5 H.263++ Video Coding and H.26L 19.6 Summary 19.7 Exercises References Chapter 20 MPEG System — Video, Audio, and Data Multiplexing 20.1 Introduction 20.2 MPEG-2 System 20.2.1 Major Technical Definitions in MPEG-2 System Document 20.2.2 Transport Streams 20.2.3 Transport Stream Splicing 20.2.4 Program Streams 20.2.5 Timing Model and Synchronization 20.3 MPEG-4 System 20.3.1 Overview and Architecture 20.3.2 Systems Decoder Model 20.3.3 Scene Description 20.3.4 Object Description Framework 20.4 Summary 20.5 Exercises References