Front cover -- Title page -- Copyright page -- Table of contents -- Preface -- Audience -- Course Use -- Approach -- Learning from This Book -- Content and Organization -- A Personal View -- Acknowledgments -- 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 -- 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 -- 2.3.4 Composite Source Model -- 2.4 Coding -- 2.4.1 Uniquely Decodable Codes -- 2.4.2 Prefix Codes -- 2.4.3 The Kraft-McMillan Inequality -- 2.5 Algorithmic Information Theory -- 2.6 Minimum Description Length Principle -- 2.7 Summary -- 2.8 Projects and Problems -- 3 Huffman Coding -- 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 -- 3.10 Projects and Problems -- 4 Arithmetic Coding -- 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 Ef f iciency of the Arithmetic Code -- 4.4.2 Algorithm Implementation.

4.4.3 Integer Implementation -- 4.5 Comparison of Huffman and Arithmetic Coding -- 4.6 Adaptive Arithmetic Coding -- 4.7 Applications -- 4.8 Summary -- 4.9 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 -- 5.4.2 The LZ78 Approach -- 5.5 Applications -- 5.5.1 File Compression-UNIX -- 5.5.2 Image Compression-The Graphics Interchange Format (GIF) -- 5.5.3 Image Compression-Portable Network Graphics (PNG) -- 5.5.4 Compression over Modems-V.42 bis -- 5.6 Summary -- 5.7 Projects and Problems -- 6 Context-Based Compression -- 6.1 Overview -- 6.2 Introduction -- 6.3 Prediction with Partial Match (ppm) -- 6.3.1 The Basic Algorithm -- 6.3.2 The Escape Symbol -- 6.3.3 Length of Context -- 6.3.4 The Exclusion Principle -- 6.4 The Burrows-Wheeler Transform -- 6.4.1 Move-to-Front Coding -- 6.5 Associative Coder of Buyanovsky (ACB) -- 6.6 Dynamic Markov Compression -- 6.7 Summary -- 6.8 Projects and Problems -- 7 Lossless Image Compression -- 7.1 Overview -- 7.2 Introduction -- 7.2.1 The Old JPEG Standard -- 7.3 CALIC -- 7.4 JPEG-LS -- 7.5 Multiresolution Approaches -- 7.5.1 Progressive Image Transmission -- 7.6 Facsimile Encoding -- 7.6.1 Run-Length Coding -- 7.6.2 CCITT Group 3 and 4-Recommendations T.4 and T.6 -- 7.6.3 JBIG -- 7.6.4 JBIG2-T.88 -- 7.7 MRC-T.44 -- 7.8 Summary -- 7.9 Projects and Problems -- 8 Mathematical Preliminaries for Lossy Coding -- 8.1 Overview -- 8.2 Introduction -- 8.3 Distortion Criteria -- 8.3.1 The Human Visual System -- 8.3.2 Auditory Perception -- 8.4 Information Theory Revisited -- 8.4.1 Conditional Entropy -- 8.4.2 Average Mutual Information -- 8.4.3 Differential Entropy -- 8.5 Rate Distortion Theory -- 8.6 Models -- 8.6.1 Probability Models -- 8.6.2 Linear System Models.

8.6.3 Physical Models -- 8.7 Summary -- 8.8 Projects and Problems -- 9 Scalar Quantization -- 9.1 Overview -- 9.2 Introduction -- 9.3 The Quantization Problem -- 9.4 Uniform Quantizer -- 9.5 Adaptive Quantization -- 9.5.1 Forward Adaptive Quantization -- 9.5.2 Backward Adaptive Quantization -- 9.6 Nonuniform Quantization -- 9.6.1 pdf-Optimized Quantization -- 9.6.2 Companded Quantization -- 9.7 Entropy-Coded Quantization -- 9.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs -- 9.7.2 Entropy-Constrained Quantization -- 9.7.3 High-Rate Optimum Quantization -- 9.8 Summary -- 9.9 Projects and Problems -- 10 Vector Quantization -- 10.1 Overview -- 10.2 Introduction -- 10.3 Advantages of Vector Quantization over Scalar Quantization -- 10.4 The Linde-Buzo-Gray Algorithm -- 10.4.1 Initializing the LBG Algorithm -- 10.4.2 The Empty Cell Problem -- 10.4.3 Use of LBG for Image Compression -- 10.5 Tree-Structured Vector Quantizers -- 10.5.1 Design of Tree-Structured Vector Quantizers -- 10.5.2 Pruned Tree-Structured Vector Quantizers -- 10.6 Structured Vector Quantizers -- 10.6.1 Pyramid Vector Quantization -- 10.6.2 Polar and Spherical Vector Quantizers -- 10.6.3 Lattice Vector Quantizers -- 10.7 Variations on the Theme -- 10.7.1 Gain-Shape Vector Quantization -- 10.7.2 Mean-Removed Vector Quantization -- 10.7.3 Classified Vector Quantization -- 10.7.4 Multistage Vector Quantization -- 10.7.5 Adaptive Vector Quantization -- 10.8 Trellis-Coded Quantization -- 10.9 Summary -- 10.10 Projects and Problems -- 11 Differential Encoding -- 11.1 Overview -- 11.2 Introduction -- 11.3 The Basic Algorithm -- 11.4 Prediction in DPCM -- 11.5 Adaptive DPCM -- 11.5.1 Adaptive Quantization in DPCM -- 11.5.2 Adaptive Prediction in DPCM -- 11.6 Delta Modulation -- 11.6.1 Constant Factor Adaptive Delta Modulation (CFDM) -- 11.6.2 Continuously Variable Slope Delta Modulation.

11.7 Speech Coding -- 11.7.1 G.726 -- 11.8 Image Coding -- 11.9 Summary -- 11.10 Projects and Problems -- 12 Mathematical Preliminaries for Transforms, Subbands, and Wavelets -- 12.1 Overview -- 12.2 Introduction -- 12.3 Vector Spaces -- 12.3.1 Dot or Inner Product -- 12.3.2 Vector Space -- 12.3.3 Subspace -- 12.3.4 Basis -- 12.3.5 Inner Product-Formal Definition -- 12.3.6 Orthogonal and Orthonormal Sets -- 12.4 Fourier Series -- 12.5 Fourier Transform -- 12.5.1 Parseval's Theorem -- 12.5.2 Modulation Property -- 12.5.3 Convolution Theorem -- 12.6 Linear Systems -- 12.6.1 Time Invariance -- 12.6.2 Transfer Function -- 12.6.3 Impulse Response -- 12.6.4 Filter -- 12.7 Sampling -- 12.7.1 Ideal Sampling-Frequency Domain View -- 12.7.2 Ideal Sampling-Time Domain View -- 12.8 Discrete Fourier Transform -- 12.9 Z-Transform -- 12.9.1 Tabular Method -- 12.9.2 Partial Fraction Expansion -- 12.9.3 Long Division -- 12.9.4 Z-Transform Properties -- 12.9.5 Discrete Convolution -- 12.10 Summary -- 12.11 Projects and Problems -- 13 Transform Coding -- 13.1 Overview -- 13.2 Introduction -- 13.3 The Transform -- 13.4 Transforms of Interest -- 13.4.1 Karhunen-Loéve Transform -- 13.4.2 Discrete Cosine Transform -- 13.4.3 Discrete Sine Transform -- 13.4.4 Discrete Walsh-Hadamard Transform -- 13.5 Quantization and Coding of Transform Coefficients -- 13.6 Application to Image Compression-JPEG -- 13.6.1 The Transform -- 13.6.2 Quantization -- 13.6.3 Coding -- 13.7 Application to Audio Compression-The MDCT -- 13.8 Summary -- 13.9 Projects and Problems -- 14 Subband Coding -- 14.1 Overview -- 14.2 Introduction -- 14.3 Filters -- 14.3.1 Some Filters Used in Subband Coding -- 14.4 The Basic Subband Coding Algorithm -- 14.4.1 Analysis -- 14.4.2 Quantization and Coding -- 14.4.3 Synthesis -- 14.5 Design of Filter Banks -- 14.5.1 Downsampling -- 14.5.2 Upsampling.

14.6 Perfect Reconstruction Using Two-Channel Filter Banks -- 14.6.1 Two-Channel PR Quadrature Mirror Filters -- 14.6.2 Power Symmetric FIR Filters -- 14.7 M-Band QMF Filter Banks -- 14.8 The Polyphase Decomposition -- 14.9 Bit Allocation -- 14.10 Application to Speech Coding-G.722 -- 14.11 Application to Audio Coding-MPEG Audio -- 14.12 Application to Image Compression -- 14.12.1 Decomposing an Image -- 14.12.2 Coding the Subbands -- 14.13 Summary -- 14.14 Projects and Problems -- 15 Wavelet-Based Compression -- 15.1 Overview -- 15.2 Introduction -- 15.3 Wavelets -- 15.4 Multiresolution Analysis and the Scaling Function -- 15.5 Implementation Using Filters -- 15.5.1 Scaling and Wavelet Coefficients -- 15.5.2 Families of Wavelets -- 15.6 Image Compression -- 15.7 Embedded Zerotree Coder -- 15.8 Set Partitioning in Hierarchical Trees -- 15.9 JPEG 2000 -- 15.10 Summary -- 15.11 Projects and Problems -- 16 Audio Coding -- 16.1 Overview -- 16.2 Introduction -- 16.2.1 Spectral Masking -- 16.2.2 Temporal Masking -- 16.2.3 Psychoacoustic Model -- 16.3 MPEG Audio Coding -- 16.3.1 Layer I Coding -- 16.3.2 Layer II Coding -- 16.3.3 Layer III Coding-mp3 -- 16.4 MPEG Advanced Audio Coding -- 16.4.1 MPEG-2 AAC -- 16.4.2 MPEG-4 AAC -- 16.5 Dolby AC3 (Dolby Digital) -- 16.5.1 Bit Allocation -- 16.6 Other Standards -- 16.7 Summary -- 17 Analysis/Synthesis and Analysis by Synthesis Schemes -- 17.1 Overview -- 17.2 Introduction -- 17.3 Speech Compression -- 17.3.1 The Channel Vocoder -- 17.3.2 The Linear Predictive Coder (Government Standard LPC-10) -- 17.3.3 Code Excited Linear Predicton (CELP) -- 17.3.4 Sinusoidal Coders -- 17.3.5 Mixed Excitation Linear Prediction (MELP) -- 17.4 Wideband Speech Compression-ITU-T G.722.2 -- 17.5 Image Compression -- 17.5.1 Fractal Compression -- 17.6 Summary -- 17.7 Projects and Problems -- 18 Video Compression -- 18.1 Overview.

18.2 Introduction.