INTRODUCTION TO DATA COMPRESSION, 2ND ED.

0.0

About this Title Will include coverage of important new developments in the compression field, such as the new JPEG standard, MPEG-4 and MPEG-7, subband coding, wavelets, and fractals. Table of Contents Preface Introduction Compression Techniques Lossless Compression Lossy Compression Measures of Performance Modeling and Coding Summary Projects and Problems Mathematical Preliminaries for Lossless Compression Overview A Brief Introduction to Information Theory Derivation of Average Information * Models Physical Models Probability Models Markov Models Composite Source Model Coding Uniquely Decodable Codes Prefix Codes The Kraft-McMillan Inequality * Summary Projects and Problems Huffman Coding Overview The Huffman Coding Algorithm Minimum Variance Huffman Codes Optimality of Huffman Codes * Length of Huffman Codes * Extended Huffman Codes * Nonbinary Huffman Codes * Adaptive Huffman Coding Update Procedure Encoding Procedure Decoding Procedure Golomb Codes Rice Codes CCSDS Recommendation for Lossless Compression Tunstall Codes Applications of Huffman Coding Lossless Image Compression Text Compression Audio Compression Summary Projects and Problems Arithmetic Coding Overview Introduction Coding a Sequence Generating a Tag Deciphering the Tag Generating a Binary Code Uniqueness and Efficiency of the Arithmetic Code Algorithm Implementation Integer Implementation Comparison of Huffman and Arithmetic Coding Applications Bi-level Image Compression---The JBIG Standard JBIG2 Image Compression Summary Projects and Problems Dictionary Techniques Overview Introduction Static Dictionary Digram Coding Adaptive Dictionary The LZ77 Approach The LZ78 Approach Applications File Compression---UNIX Compress Image Compression---The Graphics Interchange Format (GIF) Compression over Modems---V.42 bis Summary Projects and Problems Predictive Coding Overview Introduction Prediction with Partial Match (ppm) The Basic Algorithm The Escape Symbol Length of Context The Exclusion Principle The Burrows-Wheeler Transform Move-to-Front Coding CALIC JPEG-LS ``Current'' Standard ``New'' Standard Multiresolution Approaches Progressive Image Transmission Facsimile Encoding Run-Length Coding CCITT Group 3 and 4---Recommendations T.4 and T.6 Comparison of MH, MR, MMR, and JBIG Dynamic Markov Compression Summary Projects and Problems Mathematical Preliminaries for Lossy Coding Overview Introduction Distortion Criteria The Human Visual System Auditory Perception Information Theory Revisited * Conditional Entropy Average Mutual Information Differential Entropy Rate Distortion Theory * Models Probability Models Linear System Models Physical Models Summary Projects and Problems Scalar Quantization Overview Introduction The Quantization Problem Uniform Quantizer Adaptive Quantization Forward Adaptive Quantization Backward Adaptive Quantization Nonuniform Quantization pdf-Optimized Quantization Companded Quantization Entropy-Coded Quantization Entropy Coding of Lloyd-Max Quantizer Outputs Entropy-Constrained Quantization * High-Rate Optimum Quantization * Summary Projects and Problems Vector Quantization Overview Introduction Advantages of Vector Quantization over Scalar Quantization The Linde-Buzo-Gray Algorithm Initializing the LBG Algorithm The Empty Cell Problem Use of LBG for Image Compression Tree-Structured Vector Quantizers Design of Tree-Structured Vector Quantizers Pruned Tree-Structured Vector Quantizers Structured Vector Quantizers Pyramid Vector Quantization Polar and Spherical Vector Quantizers Lattice Vector Quantizers Variations on the Theme Gain-Shape Vector Quantization Mean-Removed Vector Quantization Classified Vector Quantization Multistage Vector Quantization Adaptive Vector Quantization Trellis-Coded Quantization Summary Projects and Problems Differential Encoding Overview Introduction The Basic Algorithm Prediction in DPCM Adaptive DPCM Adaptive Quantization in DPCM Adaptive Prediction in DPCM Delta Modulation Constant Factor Adaptive Delta Modulation (CFDM) Continuously Variable Slope Delta Modulation Speech Coding G.726 Image Coding Summary Projects and Problems Mathematical Preliminaries for Transforms, Subbands, and Wavelets Overview Introduction Vector Spaces Dot or Inner Product Vector Space Subspace Basis Inner Product---Formal Definition Orthogonal and Orthonormal Sets Fourier Series Fourier Transform Parseval's Theorem Modulation Property Convolution Theorem Linear Systems Time Invariance Transfer Function Impulse Response Filter Sampling Ideal Sampling---Frequency Domain View Ideal Sampling---Time Domain View Discrete Fourier Transform Z-Transform Tabular Method Partial Fraction Expansion Long Division Z-Transform Properties Discrete Convolution Summary Projects and Problems Transform Coding Overview Introduction The Transform Transforms of Interest Karhunen-Loeve Transform Discrete Cosine Transform Discrete Sine Transform Discrete Walsh-Hadamard Transform Quantization and Coding of Transform Coefficients Application to Image Compression---JPEG The Transform Quantization Coding Application to Audio Compression Summary Projects and Problems Subband Coding Overview Introduction Filters Some Filters Used in Subband Coding The Basic Subband Coding Algorithm Analysis Quantization and Coding Synthesis Design of Filter Banks * Downsampling * Upsampling * Perfect Reconstruction Using Two-Channel Filter Banks * Two-Channel PR Quadrature Mirror Filters * Power SymmetricFIR Filters * M-Band QMF Filter Banks * The Polyphase Decomposition * Bit Allocation Application to Speech Coding---G.722 Application to Audio Coding---MPEG Audio Application to Image Compression Decomposing an Image Coding the Subbands Summary Projects and Problems Wavelet-Based Compression Overview Introduction Wavelets Multiresolution Analysis and the Scaling Function Implementation Using Filters Scaling and Wavelet Coefficients Families of Wavelets Image Compression Embedded Zerotree Coder Set Partitioning in Hierarchical Trees JPEG 2000 Summary Projects and Problems Analysis/Synthesis Schemes Overview Introduction Speech Compression The Channel Vocoder The Linear Predictive Coder (Government Standard LPC-10) Code Excited Linear Prediction (CELP) Sinusoidal Coders Mixed Excitation Linear Prediction (MELP) Image Compression Fractal Compression Summary Projects and Problems Video Compression Overview Introduction Motion Compensation Video Signal Representation Algorithms for Videoconferencing and Videophones ITU-T Recommendation H.261 Model-Based Coding Asymmetric Applications The MPEG-1 Video Standard The MPEG-2 Video Standard MPEG-4 MPEG-7 Packet Video ATM Networks