Introduction to Data Compression [5th ed.]

Description

Preface......Page 3 1 Introduction......Page 10 1.1 Compression Techniques......Page 12 1.1.2 Lossy Compression......Page 13 1.1.3 Measures of Performance......Page 14 1.2 Modeling and Coding......Page 15 1.3 Summary......Page 18 1.4 Projects and Problems......Page 19 2.2 A Brief Introduction to Information Theory......Page 20 2.2.1 Derivation of Average Information......Page 26 2.3.1 Physical Models......Page 31 2.3.3 Markov Models......Page 32 Markov Models in Text Compression......Page 34 2.3.4 Composite Source Model......Page 35 2.4.1 Uniquely Decodable Codes......Page 36 A Test for Unique Decodability......Page 38 2.4.2 Prefix Codes......Page 39 2.4.3 The Kraft-McMillan Inequality......Page 40 2.6 Minimum Description Length Principle......Page 43 2.8 Projects and Problems......Page 45 3.2 The Huffman Coding Algorithm......Page 49 3.2.1 Minimum Variance Huffman Codes......Page 53 3.2.2 Canonical Huffman Codes......Page 55 3.2.3 An In-place Implementation......Page 58 3.2.4 Length-Limited Huffman Codes......Page 61 3.2.5 Optimality of Huffman Codes......Page 63 3.2.6 Length of Huffman Codes......Page 64 3.2.7 Extended Huffman Codes......Page 67 3.2.8 Implementation of Huffman Codes......Page 70 3.3 Nonbinary Huffman Codes......Page 73 3.4 Adaptive Huffman Coding......Page 75 3.4.1 Update Procedure......Page 76 3.4.2 Encoding Procedure......Page 79 3.4.3 Decoding Procedure......Page 81 3.5 Golomb Codes......Page 83 3.6 Rice Codes......Page 84 3.6.1 CCSDS Recommendation for Lossless Compression......Page 85 3.7 Tunstall Codes......Page 86 3.8.1 Lossless Image Compression......Page 89 3.8.2 Text Compression......Page 91 3.8.3 Audio Compression......Page 92 Further Reading......Page 93 3.10 Projects and Problems......Page 94 4.2 Introduction......Page 97 4.3 Coding a Sequence......Page 99 4.3.1 Generating a Tag......Page 100 4.3.2 Deciphering the Tag......Page 106 4.4.1 Uniqueness and Efficiency of the Arithmetic Code......Page 108 4.4.2 Algorithm Implementation......Page 111 4.4.3 Integer Implementation......Page 116 Encoder Implementation......Page 117 Decoder Algorithm......Page 122 4.5 Adaptive Arithmetic Coding......Page 124 4.6 Binary Arithmetic Coding......Page 125 4.6.1 The QM Coder......Page 130 4.6.2 The MQ Coder......Page 131 4.6.3 The M Coder......Page 132 4.7 Comparison of Huffman and Arithmetic Coding......Page 133 4.8 Applications......Page 135 Further Reading......Page 136 4.10 Projects and Problems......Page 137 5.2 Introduction......Page 139 5.3 Static Dictionary......Page 140 5.3.1 Digram Coding......Page 141 5.4 Adaptive Dictionary......Page 142 5.4.1 The LZ77 Approach......Page 143 Variations on the LZ77 Theme......Page 146 5.4.2 The LZ78 Approach......Page 147 Variations on the LZ78 Theme-The LZW Algorithm......Page 148 5.5 Grammar-Based Compression......Page 154 5.5.1 SEQUITUR......Page 155 5.5.2 Irreducible Grammars......Page 157 5.5.3 Re-Pair......Page 159 5.6.1 File Compression-UNIX compress......Page 161 5.6.2 Image Compression-The Graphics Interchange Format (GIF)......Page 162 5.6.3 Image Compression-Portable Network Graphics (PNG)......Page 163 5.6.4 Compression Over Modems-V.42 bis......Page 165 5.7 Beyond Compression-Lempel-Ziv Complexity......Page 166 Further Reading......Page 168 5.9 Projects and Problems......Page 169 6.2 Introduction......Page 172 6.3.1 The Basic Algorithm......Page 174 6.3.2 The Escape Symbol......Page 180 6.3.4 The Exclusion Principle......Page 181 6.4 The Burrows-Wheeler Transform......Page 182 6.4.1 Move-to-Front Coding......Page 185 6.4.2 Beyond Compression-Short Read Alignment......Page 187 6.6 Dynamic Markov Compression......Page 188 6.7 Summary......Page 190 6.8 Projects and Problems......Page 191 7.2 Introduction......Page 193 7.2.1 The Old JPEG Standard......Page 194 7.3 CALIC......Page 196 7.4 JPEG-LS......Page 200 7.5 Prediction Using Conditional Averages......Page 202 7.6 Multiresolution Approaches......Page 203 7.6.1 Progressive Image Transmission......Page 204 7.7 Lossless Image Compression Formats......Page 208 7.8 Facsimile Encoding......Page 210 7.8.2 CCITT Group 3 and 4-Recommendations T.4 and T.6......Page 211 7.8.3 JBIG......Page 214 Typical Prediction......Page 215 Arithmetic Coding......Page 217 Comparison of MH, MR, MMR, and JBIG......Page 219 7.8.4 JBIG2-T.88......Page 220 Generic Decoding Procedures......Page 221 7.9 MRC-T.44......Page 222 7.10 Summary......Page 224 7.11 Projects and Problems......Page 225 8.2 Introduction......Page 227 8.3 Distortion Criteria......Page 230 8.3.2 Auditory Perception......Page 233 8.4 Information Theory Revisited......Page 234 8.4.1 Conditional Entropy......Page 235 8.4.2 Average Mutual Information......Page 237 Beyond Compression-Average Mutual Information as a Species Signature......Page 238 8.4.3 Differential Entropy......Page 239 8.5 Rate Distortion Theory......Page 243 8.6.1 Probability Models......Page 251 8.6.2 Linear System Models......Page 253 Speech Production......Page 258 8.8 Projects and Problems......Page 259 9.2 Introduction......Page 262 9.3 The Quantization Problem......Page 263 Uniform Quantization of a Uniformly Distributed Source......Page 268 Uniform Quantization of Nonuniform Sources......Page 272 Mismatch Effects......Page 276 9.5.1 Forward Adaptive Quantization......Page 278 9.5.2 Backward Adaptive Quantization......Page 280 9.6 Nonuniform Quantization......Page 286 9.6.1 pdf-Optimized Quantization......Page 287 9.6.2 Companded Quantization......Page 290 9.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs......Page 297 9.7.3 High-Rate Optimum Quantization......Page 298 9.8 Summary......Page 301 9.9 Projects and Problems......Page 302 10.2 Introduction......Page 304 10.3 Advantages of Vector Quantization Over Scalar Quantization......Page 307 10.4 The Linde-Buzo-Gray Algorithm......Page 312 10.4.1 Initializing the LBG Algorithm......Page 317 10.4.2 The Empty Cell Problem......Page 323 10.4.3 Use of LBG for Image Compression......Page 324 10.5 Tree-Structured Vector Quantizers......Page 328 10.5.1 Design of Tree-Structured Vector Quantizers......Page 331 10.6 Structured Vector Quantizers......Page 332 10.6.1 Pyramid Vector Quantization......Page 333 10.6.3 Lattice Vector Quantizers......Page 335 10.7.3 Classified Vector Quantization......Page 342 10.7.4 Multistage Vector Quantization......Page 343 10.7.5 Adaptive Vector Quantization......Page 345 10.8 Trellis-Coded Quantization......Page 346 Further Reading......Page 351 10.10 Projects and Problems......Page 352 11.1 Overview......Page 355 11.2 Introduction......Page 356 11.3 The Basic Algorithm......Page 358 11.4 Prediction in DPCM......Page 362 11.5 Adaptive DPCM......Page 367 11.5.2 Adaptive Prediction in DPCM......Page 368 DPCM With Backward Adaptive Prediction (DPCM-APB)......Page 369 11.6 Delta Modulation......Page 371 11.6.1 Constant Factor Adaptive Delta Modulation (CFDM)......Page 373 11.6.2 Continuously Variable Slope Delta Modulation......Page 374 11.7 Speech Coding......Page 375 The Quantizer......Page 376 The Predictor......Page 378 11.8 Image Coding......Page 379 11.9 Summary......Page 380 11.10 Projects and Problems......Page 381 12.2 Introduction......Page 383 12.3 Vector Spaces......Page 384 12.3.1 Dot or Inner Product......Page 385 12.3.2 Vector Space......Page 386 12.3.3 Subspace......Page 387 12.3.4 Basis......Page 388 12.3.6 Orthogonal and Orthonormal Sets......Page 389 12.4 Fourier Series......Page 390 12.5 Fourier Transform......Page 392 12.5.2 Modulation Property......Page 394 12.6 Linear Systems......Page 395 12.6.2 Transfer Function......Page 396 12.6.3 Impulse Response......Page 397 12.6.4 Filter......Page 399 12.7.1 Ideal Sampling-Frequency Domain View......Page 400 12.7.2 Ideal Sampling-Time Domain View......Page 402 12.8 Discrete Fourier Transform......Page 404 12.9 Z-Transform......Page 406 12.9.1 Tabular Method......Page 409 12.9.2 Partial Fraction Expansion......Page 410 12.9.3 Long Division......Page 414 12.9.4 Z-Transform Properties......Page 415 12.9.5 Discrete Convolution......Page 416 12.10 Summary......Page 417 12.11 Projects and Problems......Page 418 13.1 Overview......Page 421 13.2 Introduction......Page 422 13.3 The Transform......Page 426 13.4.1 Karhunen-Loéve Transform......Page 431 13.4.2 Discrete Cosine Transform......Page 432 13.4.4 Discrete Walsh-Hadamard Transform......Page 434 13.5 Quantization and Coding of Transform Coefficients......Page 437 13.5.1 Operational Rate-Distortion Bit Allocation......Page 441 13.6.1 The Transform......Page 444 13.6.2 Quantization......Page 445 13.6.3 Coding......Page 447 13.6.4 Format-JFIF......Page 449 13.7 JPEG-XT......Page 452 13.8 Overlapped Transforms......Page 454 13.8.1 Application to Audio Compression-the MDCT......Page 455 13.8.2 Application to Image Compression-JPEG-XR......Page 457 13.9 Summary......Page 459 13.10 Projects and Problems......Page 460 14.2 Introduction......Page 464 14.3 Filters......Page 469 14.3.1 Some Filters Used in Subband Coding......Page 472 14.4.1 Analysis......Page 475 14.4.2 Quantization and Coding......Page 476 14.5 Design of Filter Banks......Page 478 14.5.1 Downsampling......Page 480 14.5.2 Upsampling......Page 482 14.6 Perfect Reconstruction Using Two-Channel Filter Banks......Page 484 14.6.1 Two-Channel PR Quadrature Mirror Filters......Page 486 14.6.2 Power Symmetric FIR Filters......Page 488 14.7 M-Band QMF Filter Banks......Page 491 14.8 The Polyphase Decomposition......Page 494 14.9 Bit Allocation......Page 498 14.10 Application to Speech Coding-G.722......Page 500 14.12 Application to Image Compression......Page 502 14.12.1 Decomposing an Image......Page 505 14.12.2 Coding the Subbands......Page 507 14.14 Projects and Problems......Page 509 15.2 Introduction......Page 513 15.3 Wavelets......Page 516 15.4 Multiresolution Analysis and the Scaling Function......Page 520 15.5 Implementation Using Filters......Page 526 15.5.1 Scaling and Wavelet Coefficients......Page 529 15.5.2 Families of Wavelets......Page 532 15.6 Biorthogonal Wavelets......Page 535 15.7 Lifting......Page 539 Further Reading......Page 543 15.9 Projects and Problems......Page 544 16.2 Introduction......Page 545 16.3 Embedded Zerotree Coder......Page 547 16.4 Set Partitioning in Hierarchical Trees......Page 555 16.5 JPEG 2000......Page 561 16.5.1 Color Component Transform......Page 562 16.5.2 Tiling......Page 563 16.5.4 Quantization......Page 564 Block Coding......Page 565 Rate Control......Page 572 Delimiting markers......Page 574 Functional Markers......Page 575 Pointer Markers......Page 576 Informational Marker......Page 578 16.7 Projects and Problems......Page 580 17.2 Introduction......Page 581 17.2.1 Spectral Masking......Page 582 17.2.2 Temporal Masking......Page 583 17.2.3 Psychoacoustic Model......Page 584 17.3.1 Layer I Coding......Page 585 17.3.2 Layer II Coding......Page 587 17.3.3 Layer III Coding-mp3......Page 588 17.4.1 MPEG-2 AAC......Page 593 Block Switching and MDCT......Page 594 Spectral Processing......Page 595 Stereo Coding......Page 596 TwinVQ......Page 597 Spectral Band Replication (SBR)......Page 598 17.5 Dolby AC3 (Dolby Digital)......Page 599 17.5.1 Bit Allocation......Page 601 The D25 and D45 Methods......Page 602 Further Reading......Page 603 18.2 Introduction......Page 604 18.3.1 The Channel Vocoder......Page 606 The Voiced/Unvoiced Decision......Page 609 Estimating the Pitch Period......Page 610 Obtaining the Vocal Tract Filter......Page 611 Synthesis......Page 615 18.3.3 Code Excited Linear Prediction (CELP)......Page 616 Federal Standard 1016......Page 617 CCITT G.728 Speech Standard......Page 619 18.3.4 Sinusoidal Coders......Page 621 18.3.5 Mixed Excitation Linear Prediction (MELP)......Page 622 18.4 Wideband Speech Compression-ITU-T G.722.2......Page 625 18.5.1 iLBC......Page 627 18.5.2 G.729......Page 631 18.5.3 SILK......Page 634 18.6 Image Compression......Page 636 18.6.1 Fractal Compression......Page 637 18.7 Summary......Page 644 18.8 Projects and Problems......Page 645 19.2 Introduction......Page 646 19.3 Motion Compensation......Page 648 19.4 Video Signal Representation......Page 651 19.5 ITU-T Recommendation H.261......Page 656 19.5.1 Motion Compensation......Page 657 19.5.2 The Loop Filter......Page 658 19.5.4 Quantization and Coding......Page 660 19.5.5 Rate Control......Page 661 19.6 Model-Based Coding......Page 662 19.7 Asymmetric Applications......Page 663 19.8 The MPEG-1 Video Standard......Page 664 19.9 The MPEG-2 Video Standard-H.262......Page 667 19.10 ITU-T Recommendation H.263......Page 670 19.10.2 Syntax-Based Arithmetic Coding Mode......Page 672 19.10.7 Reference Picture Selection Mode......Page 673 19.10.11 Alternative Inter VLC Mode......Page 674 19.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Coding......Page 675 19.11.1 Motion-Compensated Prediction......Page 676 19.11.3 Intra Prediction......Page 677 19.11.4 Quantization......Page 678 19.11.5 Coding......Page 680 19.12 MPEG-4 Part 2......Page 681 19.13.1 Block Structure......Page 682 DC Prediction......Page 685 Planar Prediction......Page 686 Angular Prediction......Page 687 19.13.3 Inter Prediction......Page 690 Advanced Motion Vector Prediction Mode......Page 692 19.13.4 Transforms......Page 693 19.13.5 Quantization......Page 695 19.13.7 Slices and Tiles......Page 697 19.14.2 Compression Issues in ATM Networks......Page 698 19.14.3 Compression Algorithms for Packet Video......Page 699 19.15 Summary......Page 700 19.16 Projects and Problems......Page 701 A.1.1 Frequency of Occurrence......Page 702 A.1.2 A Measure of Belief......Page 703 A.1.3 The Axiomatic Approach......Page 705 A.2 Random Variables......Page 706 A.3 Distribution Functions......Page 707 A.4 Expectation......Page 710 A.4.3 Variance......Page 711 A.5.3 Laplacian Distribution......Page 712 A.6 Stochastic Process......Page 713 A.7 Projects and Problems......Page 715 B.1 A Matrix......Page 716 B.2 Matrix Operations......Page 717 Further Reading......Page 721 Root Lattices......Page 722 Biblio......Page 724 Index......Page 735