Introduction to Data Compression

Highlights: - New chapter on Wavelets and their application; to image compression (EZW, SPIHT, JPEG 2000): - Significantly expanded coverage of subband coding.: - A new mathematical preliminaries chapter which; provides the mathematical backgrund necessary; for the wavelet and new subband coding material.: - New chapter on predictive lossless techniques; including ppm, BWT, CALIC, DMC, JPEG-LS: - Updated treatment of Huffman coding variants; including Tunstall codes, Golomb codes and Rice codes.: - Expanded the treatment of information theory and coding; concepts.: - Increased the number of exercises in almost all chapters.:; --: 1 Introduction: 1.1 Compression Techniques: 1.1.1 Lossless Compression: 1.1.2 Lossy Compression: 1.1.3 Measures of Performance: 1.2 Modeling and Coding: 1.3 Summary: 1.4 Projects and Problems: 2 Mathematical Preliminaries for Lossless Compression:; Highlights: Expanded the section on Information Theory: Moved introduction to coding from Chapter 3: Added proof of the Kraft-McMillan inequality: Added test for uniquely decodable codes;: 2.1 Overview: 2.2 A Brief Introduction to Information Theory: 2.2.1 Derivation of Average Information: 2.3 Models: 2.3.1 Physical Models: 2.3.2 Probability Models: 2.3.3 Markov Models: Markov Models in Text Compression: 2.3.4 Composite Source Model: 2.4 Coding: 2.4.1 Uniquely Decodable Codes: A Test for Unique Decodability: 2.4.2 Prefix Codes: 2.4.3 The Kraft-McMillan Inequality: 2.5 Summary: Further Reading: 2.6 Projects and Problems:: 3 Huffman Coding: Highlights: Added Proof of optimality of Huffman codes: Added description and discussions of: Tunstall Codes: Golomb codes: Rice Codes: Added description of the Space Data Systems Lossless: Compresion Standard;: 3.1 Overview: 3.2 The Huffman Coding Algorithm: 3.2.1 Minimum Variance Huffman Codes: 3.2.2 Optimality of Huffman Codes: 3.2.3 Length of Huffman Codes: 3.2.4 Extended Huffman Codes: 3.3 Nonbinary Huffman Codes: 3.4 Adaptive Huffman Coding: 3.4.1 Update Procedure: 3.4.2 Encoding Procedure: 3.4.3 Decoding Procedure: 3.5 Golomb Codes: 3.6 Rice Codes: 3.6.1 CCSDS Recommendation for Lossless Compression: 3.7 Tunstall Codes: 3.8 Applications of Huffman Coding: 3.8.1 Lossless Image Compression: 3.8.2 Text Compression: 3.8.3 Audio Compression: 3.9 Summary: Further Reading: 3.10 Projects and Problems:; 4 Arithmetic Coding:; Highlights: Improved descriptions of the coding procedures: 4.1 Overview: 4.2 Introduction: 4.3 Coding a Sequence: 4.3.1 Generating a tag: 4.3.2 Deciphering the tag: 4.4 Generating a Binary Code: 4.4.1 Uniqueness and Efficiency of the Arithmetic Code: 4.4.2 Algorithm Implementation: 4.4.3 Integer Implementation: Encoder Implementation: Decoder Implementation: 4.5 Comparison of Huffman and Arithmetic Coding: 4.6 Applications: 4.6.1 Bi-Level Image Compression - The JBIG Standard: Lossless Compression: Progressive Transmission: 4.6.2 Image Compression: 4.7 Summary;; 4.8 Projects and Problems:; 5 Dictionary Techniques: 5.1 Overview: 5.2 Introduction: 5.3 Static Dictionary: 5.3.1 Digram Coding: 5.4 Adaptive Dictionary: 5.4.1 The LZ77 Approach: Variations on the LZ77 theme: 5.4.2 The LZ78 Approach: Variations on the LZ78 Theme - The LZW Algorithm: 5.5 Applications: 5.5.1 File Compression-UNIX \sc Compress: 5.5.2 Image Compression-the Graphic Interchange Format (GIF): 5.5.3 Compression Over Modems-V.42 bis: 5.6 Summary: Further Reading: 5.7 Projects and Problems: 6 Predictive Coding: Highlights: This is essentially a new chapter covering some of the latest and currently most popular lossless coding techniques.: These include: CALIC (lossless image compression): JPEG-LS (lossless image compression): ppm and its variants: Burrows-Wheeler transform: Dynamic Markov Compression;:; 6.1 Introduction: 6.2 Prediction with Partial Match (ppm): 6.2.1 The Basic Algorithm: 6.2.2 The Escape Symbol: 6.2.3 Length of Context: 6.2.4 The Exclusion Principle: 6.3 The Burrows-Wheeler Transform: 6.3.1 Move-to-Front Coding: 6.4 CALIC: 6.5 JPEG-LS: 6.5.1 Current'' Standard: 6.5.2 New'' Standard: 6.6 Multiresolution Approaches: 6.6.1 Progressive Image Transmission: 6.7 Facsimile Encoding: 6.7.1 Run Length Coding: 6.7.2 CCITT Group 3 and 4 - Recommendations T.4 and T.6: 6.7.3 Comparison of MH, MR, MMR, and JBIG: 6.8 Dynamic Markov Compression: 6.9 Summary: Further reading: 6.10 Projects and Problems:; 7 Mathematical Preliminaries for Lossy Coding: 7.1 Overview: 7.2 Introduction: 7.3 Distortion Criteria: 7.3.1 The Human Visual System: 7.3.2 Auditory Perception: 7.4 Information Theory Revisited: 7.4.1 Conditional Entropy: 7.4.2 Average Mutual Information: 7.4.3 Differential Entropy: 7.5 Rate Distortion Theory: 7.6 Models: 7.6.1 Probability Models: 7.6.2 Linear System Models: 7.6.3 Physical Models: Speech Production: 7.7 Summary: Further Reading: 7.8 Projects and Problems: 8 Scalar Quantization: 8.1 Overview: 8.2 Introduction: 8.3 The Quantization Problem: 8.4 Uniform Quantizer: Uniform quantization of a uniformly distributed source: Uniform quantization of non-uniform sources: Mismatch Effects: 8.5 Adaptive Quantization: 8.5.1 Forward Adaptive Quantization: 8.5.2 Backward Adaptive Quantization: 8.6 Non-uniform Quantization: 8.6.1 PDF Optimized Quantization: Mismatch Effects: 8.6.2 Companded Quantization: 8.7 Entropy Coded Quantization: 8.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs: 8.7.2 Entropy Constrained Quantization: 8.7.3 High Rate Optimum Quantization: 8.8 Summary: 8.9 Projects and Problems: 9 Vector Quantization:; Highlights: - Added description of Trellis Coded Quantization (TCQ): 9.1 Overview: 9.2 Introduction: 9.3 Advantages of Vector Quantization over Scalar Quantization: 9.4 The Linde-Buzo-Gray Algorithm: 9.4.1 Initializing the LBG Algorithm: 9.4.2 The Empty Cell Problem: 9.4.3 Use of LBG for Image Compression: 9.5 Tree-Structured Vector Quantizers: 9.5.1 Design of Tree Structured Vector Quantizers: 9.5.2 Pruned Tree-Structured Vector Quantizers: 9.6 Structured Vector Quantizers: 9.6.1 Pyramid Vector Quantization: 9.6.2 Polar and Spherical Vector Quantizers: 9.6.3 Lattice Vector Quantizers: 9.7 Variations on the Theme: 9.7.1 Gain-Shape Vector Quantization: 9.7.2 Mean-Removed Vector Quantization: 9.7.3 Classified Vector Quantization: 9.7.4 Multi-stage Vector Quantization: 9.7.5 Adaptive Vector Quantization: 9.8 Trellis Coded Quantization: 9.9 Summary: Further Reading: 9.10 Projects and Problems: Appendix: Lattices: $D_L$: $A_L$: $E_L$:; 10 Differential Encoding:; Highlights: Added a section on Image Compression using DPCM: 10.1 Overview: 10.2 Introduction: 10.3 The Basic Algorithm: 10.4 Prediction in DPCM: 10.5 Adaptive DPCM: 10.5.1 Adaptive Quantization in DPCM: 10.5.2 Adaptive Prediction in DPCM: DPCM with Forward Adaptive Prediction (DPCM-APF): DPCM with backward adaptive prediction (DPCM-APB): 10.6 Delta Modulation: 10.6.1 Constant Factor Adaptive Delta Modulation (CFDM): 10.6.2 Continuously Variable Slope Delta Modulation: 10.7 Speech Coding: 10.7.1 G.726: The Quantizer: The Predictor: 10.8 Image Coding: 10.9 Summary: Further Reading: 10.10 Projects and Problems:; 11 Mathematical Preliminaries for Transforms, Subbands, and Wavelets:; Highlights: This is a new chapter which introduces the mathematical background; required to appreciate some of the material in subbnad coding; and wavelets. This is in keeping with the idea of keeping the; book self contained.: 11.1 Overview: 11.2 Introduction: 11.3 Vector Space: Dot or Inner Product: Vector Space: Subspace: Basis: Theorem: Inner Product - Formal Definition: Orthogonal and Orthonormal Sets: 11.4 Fourier Series: 11.5 Fourier Transform: Parseval's Theorem: Modulation Property: Convolution Theorem: 11.6 Linear Systems: Time Invariance: Transfer Function: Impulse Response: Filter: 11.7 Sampling: Ideal Sampling - Frequency Domain View: Ideal Sampling - Time Domain View: 11.8 Discrete Fourier Transform: 11.9 Z - Transform: Z-Transform Properties: Discrete Convolution: 11.10 Summary: 11.11 Problems:; 12 Transform Coding: 12.1 Overview: 12.2 Introduction: 12.3 The Transform: 12.4 Transforms of Interest: 12.4.1 Karhunen-Loeve Transform: 12.4.2 Discrete Cosine Transform: 12.4.3 Discrete Sine Transform: 12.4.4 Discrete Walsh-Hadamard Transform: 12.5 Quantization and Coding of Transform Coefficients: 12.6 Application to Image Compression - JPEG: 12.6.1 The Transform: 12.6.2 Quantization: 12.6.3 Coding: 12.7 Application to Audio Compression: 12.8 Summary: 12.9 Projects and Problems: 13 Subband Coding:; Highlights: Almost half of this chapter is new material. The chapter now includes a significant amount of new information about filter design. It introduces the concept of perfect reconstruction and describes various approaches to the design of filters that satisfy the perfect reconstruction requirements. We have also included the latest bit allocation techniques.: 13.1 Overview: 13.2 Introduction: 13.3 Filters: 13.3.1 Some Filters Used in Subband Coding: 13.4 The Basic Subband Coding Algorithm: Analysis: Quantization and Coding: Synthesis: 13.5 Design of Filter Banks: 13.5.1 Downsampling: 13.5.2 Upsampling: 13.6 Perfect Reconstruction Using Two-Channel Filter Banks: 13.6.1 Two Channel PR Quadrature Mirror Filters: 13.6.2 Power Symmetric FIR Filters: 13.7 M-Band QMF Filter Banks: 13.8 The Polyphase Decomposition: 13.9 Bit Allocation: 13.10 Application to Speech Coding - G.722: 13.11 Application to Audio Coding - MPEG Audio: 13.12 Application to Image Compression: 13.12.1 Decomposing an Image: 13.12.2 Coding the Subbands: 13.13 Summary: 13.14 Projects and Problems:; 14 Wavelets:; Highlights: This is a completely new chapter which introduces the concepts of; wavelets, multiresolution analysis, and wavelet transforms.: Also included in the chapter are the latest wavelet based image; compression techniques (EZW, SPIHT).: 14.1 Overview: 14.2 Introduction: 14.3 Wavelets: 14.4 Multiresolution Analysis and the Scaling Function: 14.5 Implementation Using Filters: 14.5.1 Scaling and Wavelet Coefficients: 14.5.2 Families of Wavelets: 14.6 Image Compression: 14.7 Embedded Zerotree Coder: 14.8 Set Partitioning In Hierarchical Trees: First Pass: Second Pass: Third Pass: 14.9 JPEG 2000: 14.10 Summary: 14.11 Projects and Problems:; 15 Analysis/Synthesis Schemes:; Highlights: - Increased coverage of fractal image compression.: 15.1 Overview: 15.2 Introduction: 15.3 Speech Compression: 15.3.1 The Channel Vocoder: 15.3.2 The Linear Predictive Coder (Gov. Std. LPC-10): The Voiced/Unvoiced Decision: Estimating the Pitch Period: Obtaining the vocal tract filter: Transmitting the parameters: Synthesis: 15.3.3 Code Excited Linear Predicton (CELP): Federal Standard 1016: CCITT G.728 Speech Standard: 15.3.4 Sinusoidal Coders: 15.3.5 Mixed Excitation Linear Prediction: 15.4 Image Compression: 15.4.1 Fractal Compression: 15.5 Summary: 15.6 Projects and Problems:: 16 Video Compression:; Highlights: - Inclusion of description of compression aspects of MPEG-4 and MPEG-7 standards.:; 16.1 Overview: 16.2 Introduction: 16.3 Motion Compensation: 16.4 Video Signal Representation: 16.5 Algorithms for Videoconferencing and Videophones: 16.5.1 ITU-T Recommendation H.261: Motion Compensation: The Loop Filter: The Transform: Quantization and Coding: Rate Control: 16.5.2 Model Based Coding: 16.6 Asymmetric Applications: 16.6.1 The MPEG-1 Video Standard: The MPEG-2 Video Standard: The Grand Alliance HDTV Proposal: 16.6.2 MPEG-4: 16.6.3 MPEG-7: 16.7 Packet Video: 16.7.1 ATM Networks: 16.7.2 Compression Issues in ATM Networks: 16.7.3 Compression Algorithms for Packet Video: 16.8 Summary: 16.9 Projects and Problems:; A Probability and Random Processes;; A.1 Probability: Frequency of Occurrence: A Measure of Belief: The axiomatic approach: A.2 Random Variables: A.3 Distribution Functions: A.4 Expectation: Mean: Second Moment: Variance: A.5 Types of Distribution: Uniform Distribution: Gaussian Distribution: Laplacian Distribution: Gamma Distribution: A.6 Stochastic Process: A.7 Exercises: B A Brief Review of Matrix Concepts: Highlights: - Revised most of the material to make it more accessible:; B.1 A Matrix: B.2 Matrix Operations