Introduction to Data Compression, Fourth Edition

Cover......Page 1
Halftitle......Page 2
Series......Page 3
 References......Page 0
Copyright......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 18
Introduction......Page 26
 1.1 Compression Techniques......Page 28
  1.1.1 Lossless Compression......Page 29
  1.1.3 Measures of Performance......Page 30
 1.2 Modeling and Coding......Page 31
 1.4 Projects and Problems......Page 35
 2.2 A Brief Introduction to Information Theory......Page 38
  2.2.1 Derivation of Average Information......Page 45
  2.3.2 Probability Models......Page 50
  2.3.3 Markov Models......Page 51
 2.4 Coding......Page 54
  2.4.1 Uniquely Decodable Codes......Page 55
  2.4.2 Prefix Codes......Page 58
  2.4.3 The Kraft-McMillan Inequality......Page 59
 2.5 Algorithmic Information Theory......Page 62
 2.6 Minimum Description Length Principle......Page 63
 2.7 Summary......Page 64
 2.8 Projects and Problems......Page 65
 3.2 The Huffman Coding Algorithm......Page 68
  3.2.1 Minimum Variance Huffman Codes......Page 72
  3.2.2 Canonical Huffman Codes......Page 75
  3.2.3 Length-Limited Huffman Codes......Page 77
  3.2.4 Optimality of Huffman Codes......Page 80
  3.2.5 Length of Huffman Codes......Page 81
  3.2.6 Extended Huffman Codes......Page 83
  3.2.7 Implementation of Huffman Codes......Page 86
 3.3 Nonbinary Huffman Codes......Page 90
 3.4 Adaptive Huffman Coding......Page 92
  3.4.1 Update Procedure......Page 93
  3.4.2 Encoding Procedure......Page 96
  3.4.3 Decoding Procedure......Page 98
 3.5 Golomb Codes......Page 100
 3.6 Rice Codes......Page 101
  3.6.1 CCSDS Recommendation for Lossless Compression......Page 102
 3.7 Tunstall Codes......Page 104
  3.8.1 Lossless Image Compression......Page 106
  3.8.2 Text Compression......Page 108
  3.8.3 Audio Compression......Page 110
 3.9 Summary......Page 111
 3.10 Projects and Problems......Page 112
 4.2 Introduction......Page 116
 4.3 Coding a Sequence......Page 118
  4.3.1 Generating a Tag......Page 119
  4.3.2 Deciphering the Tag......Page 126
 4.4 Generating a Binary Code......Page 127
  4.4.1 Uniqueness and Efficiency of the Arithmetic Code......Page 128
  4.4.2 Algorithm Implementation......Page 131
  4.4.3 Integer Implementation......Page 136
 4.5 Adaptive Arithmetic Coding......Page 144
 4.6 Binary Arithmetic Coding......Page 145
  4.6.2 The MQ Coder......Page 150
  4.6.3 The M Coder......Page 151
 4.7 Comparison of Huffman and Arithmetic Coding......Page 152
 4.8 Applications......Page 155
 4.10 Projects and Problems......Page 156
 5.2 Introduction......Page 160
 5.3 Static Dictionary......Page 161
  5.3.1 Digram Coding......Page 162
  5.4.1 The LZ77 Approach......Page 164
  5.4.2 The LZ78 Approach......Page 168
 5.5 Applications......Page 175
  5.5.2 Image Compression\'227The Graphics Interchange Format (GIF)......Page 176
  5.5.3 Image Compression\'227Portable Network Graphics (PNG)......Page 177
  5.5.4 Compression over Modems\'227V.42 bis......Page 178
 5.6 Beyond Compression4pt\'0137\'0137Lempel-Ziv Complexity......Page 181
 5.7 Summary......Page 183
 5.8 Projects and Problems......Page 184
 6.2 Introduction......Page 188
  6.3.1 The Basic Algorithm......Page 190
  6.3.2 The Escape Symbol......Page 195
  6.3.3 Length of Context......Page 197
  6.3.4 The Exclusion Principle......Page 198
 6.4 The Burrows-Wheeler Transform......Page 199
  6.4.1 Move-to-Front Coding......Page 202
 6.5 Associative Coder of Buyanovsky (ACB)......Page 203
 6.6 Dynamic Markov Compression......Page 204
 6.8 Projects and Problems......Page 207
 7.2 Introduction......Page 208
  7.2.1 The Old JPEG Standard......Page 209
 7.3 CALIC......Page 211
 7.4 JPEG-LS......Page 215
 7.5 Prediction Using Conditional Averages......Page 217
  7.6.1 Progressive Image Transmission......Page 218
 7.7 Facsimile Encoding......Page 223
  7.7.1 Run-Length Coding......Page 224
  7.7.2 CCITT Group 3 and 4\'227Recommendations T.4 and T.6......Page 225
  7.7.3 JBIG......Page 228
  7.7.4 Comparison of MH, MR, MMR, and JBIG......Page 233
  7.7.5 JBIG2\'226T.88......Page 234
 7.8 MRC\'226T.44......Page 236
 7.9 Summary......Page 238
 7.10 Projects and Problems......Page 239
 8.2 Introduction......Page 242
 8.3 Distortion Criteria......Page 245
  8.3.1 The Human Visual System......Page 248
  8.3.2 Auditory Perception......Page 249
  8.4.1 Conditional Entropy......Page 250
  8.4.2 Average Mutual Information......Page 253
  8.4.3 Differential Entropy......Page 254
 8.5 Rate Distortion Theory......Page 257
  8.6.1 Probability Models......Page 265
  8.6.2 Linear System Models......Page 268
 8.7 Summary......Page 273
 8.8 Projects and Problems......Page 274
 9.2 Introduction......Page 276
 9.3 The Quantization Problem......Page 277
 9.4 Uniform Quantizer......Page 282
 9.5 Adaptive Quantization......Page 293
  9.5.1 Forward Adaptive Quantization......Page 294
  9.5.2 Backward Adaptive Quantization......Page 296
 9.6 Nonuniform Quantization......Page 302
  9.6.1 pdf-Optimized Quantization......Page 303
  9.6.2 Companded Quantization......Page 307
 9.7 Entropy-Coded Quantization......Page 312
  9.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs......Page 313
  9.7.3 High-Rate Optimum Quantization......Page 314
 9.8 Summary......Page 317
 9.9 Projects and Problems......Page 318
 10.2 Introduction......Page 320
 10.3 Advantages of Vector Quantization over Scalar Quantization......Page 323
 10.4 The Linde-Buzo-Gray Algorithm......Page 329
  10.4.1 Initializing the LBG Algorithm......Page 334
  10.4.3 Use of LBG for Image Compression......Page 340
 10.5 Tree-Structured Vector Quantizers......Page 345
  10.5.1 Design of Tree-Structured Vector Quantizers......Page 348
 10.6 Structured Vector Quantizers......Page 349
  10.6.1 Pyramid Vector Quantization......Page 351
  10.6.2 Polar and Spherical Vector Quantizers......Page 352
  10.6.3 Lattice Vector Quantizers......Page 353
  10.7.2 Mean-Removed Vector Quantization......Page 357
  10.7.3 Classified Vector Quantization......Page 358
  10.7.4 Multistage Vector Quantization......Page 359
  10.7.5 Adaptive Vector Quantization......Page 360
 10.8 Trellis-Coded Quantization......Page 362
 10.9 Summary......Page 365
 10.10 Projects and Problems......Page 367
 11.2 Introduction......Page 370
 11.3 The Basic Algorithm......Page 373
 11.4 Prediction in DPCM......Page 377
 11.5 Adaptive DPCM......Page 382
  11.5.2 Adaptive Prediction in DPCM......Page 383
 11.6 Delta Modulation......Page 386
  11.6.1 Constant Factor Adaptive Delta Modulation (CFDM)......Page 388
  11.6.2 Continuously Variable Slope Delta Modulation......Page 389
 11.7 Speech Coding......Page 390
  11.7.1 G.726......Page 391
 11.8 Image Coding......Page 394
 11.10 Projects and Problems......Page 396
 12.2 Introduction......Page 398
 12.3 Vector Spaces......Page 399
  12.3.2 Vector Space......Page 400
  12.3.4 Basis......Page 402
  12.3.6 Orthogonal and Orthonormal Sets......Page 404
 12.4 Fourier Series......Page 405
 12.5 Fourier Transform......Page 407
  12.5.2 Modulation Property......Page 409
 12.6 Linear Systems......Page 410
  12.6.2 Transfer Function......Page 411
  12.6.3 Impulse Response......Page 412
  12.6.4 Filter......Page 413
  12.7.1 Ideal Sampling\'226Frequency Domain View......Page 415
  12.7.2 Ideal Sampling\'227Time Domain View......Page 417
 12.8 Discrete Fourier Transform......Page 419
 12.9 Z-Transform......Page 421
  12.9.2 Partial Fraction Expansion......Page 424
  12.9.3 Long Division......Page 428
  12.9.5 Discrete Convolution......Page 429
 12.10 Summary......Page 431
 12.11 Projects and Problems......Page 432
 13.2 Introduction......Page 434
 13.3 The Transform......Page 439
  13.4.1 Karhunen-Loéve Transform......Page 443
  13.4.2 Discrete Cosine Transform......Page 445
  13.4.4 Discrete Walsh-Hadamard Transform......Page 448
 13.5 Quantization and Coding of Transform Coefficients......Page 449
  13.5.1 Operational Rate-Distortion Bit Allocation......Page 453
  13.6.2 Quantization......Page 457
  13.6.3 Coding......Page 459
  13.6.4 Format4pt\'0137\'0137JFIF......Page 463
 13.7 Application to Audio Compression4pt\'0137\'0137The MDCT......Page 465
 13.8 Summary......Page 468
 13.9 Projects and Problems......Page 469
 14.2 Introduction......Page 472
 14.3 Filters......Page 477
  14.3.1 Some Filters Used in Subband Coding......Page 481
  14.4.1 Analysis......Page 484
  14.4.3 Synthesis......Page 486
 14.5 Design of Filter Banks......Page 487
  14.5.1 Downsampling......Page 488
  14.5.2 Upsampling......Page 491
 14.6 Perfect Reconstruction Using Two-Channel Filter Banks......Page 492
  14.6.1 Two-Channel PR Quadrature Mirror Filters......Page 495
  14.6.2 Power Symmetric FIR Filters......Page 497
 14.7 M-Band Quadrature Mirror Filter Banks......Page 499
 14.8 The Polyphase Decomposition......Page 502
 14.9 Bit Allocation......Page 507
 14.10 Application to Speech Coding4pt\'0137\'0137G.722......Page 509
 14.11 Application to Audio Coding4pt\'0137\'0137MPEG Audio......Page 510
 14.12 Application to Image Compression......Page 511
  14.12.1 Decomposing an Image......Page 513
  14.12.2 Coding the Subbands......Page 515
 14.13 Summary......Page 517
 14.14 Projects and Problems......Page 518
 15.2 Introduction......Page 522
 15.3 Wavelets......Page 525
 15.4 Multiresolution Analysis and the Scaling Function......Page 529
 15.5 Implementation Using Filters......Page 535
  15.5.1 Scaling and Wavelet Coefficients......Page 538
 15.6 Biorthogonal Wavelets......Page 541
 15.7 Lifting......Page 548
 15.8 Summary......Page 552
 15.9 Projects and Problems......Page 553
 16.2 Introduction......Page 554
 16.3 Embedded Zerotree Coder......Page 557
 16.4 Set Partitioning in Hierarchical Trees......Page 565
 16.5 JPEG 2000......Page 572
  16.5.1 Color Component Transform......Page 573
  16.5.3 Wavelet Transform......Page 574
  16.5.4 Quantization......Page 576
  16.5.5 Tier I Coding......Page 577
  16.5.6 Tier II Coding......Page 584
  16.5.7 JPEG 2000 bitstream......Page 586
 16.7 Projects and Problems......Page 593
 17.2 Introduction......Page 594
  17.2.1 Spectral Masking......Page 595
  17.2.2 Temporal Masking......Page 596
  17.2.3 Psychoacoustic Model......Page 597
  17.3.1 Layer I Coding......Page 598
  17.3.2 Layer II Coding......Page 600
  17.3.3 Layer III Coding\'227mp3......Page 602
 17.4 MPEG Advanced Audio Coding......Page 606
  17.4.1 MPEG-2 AAC......Page 607
  17.4.2 MPEG-4 AAC......Page 611
 17.5 Dolby AC-3 (Dolby Digital)......Page 612
  17.5.1 Bit Allocation......Page 613
 17.7 Summary......Page 614
 18.2 Introduction......Page 616
 18.3 Speech Compression......Page 618
  18.3.1 The Channel Vocoder......Page 619
  18.3.2 The Linear Predictive Coder (Government Standard LPC-10)......Page 621
  18.3.3 Code-Excited Linear Predicton (CELP)......Page 628
  18.3.4 Sinusoidal Coders......Page 631
  18.3.5 Mixed Excitation Linear Prediction (MELP)......Page 633
 18.4 Wideband Speech Compression4pt\'0137\'0137ITU-T G.722.2......Page 636
  18.5.1 iLBC......Page 638
  18.5.2 G.729......Page 643
  18.5.3 SILK......Page 646
 18.6 Image Compression......Page 648
 18.7 Summary......Page 656
 18.8 Projects and Problems......Page 657
 19.2 Introduction......Page 658
 19.3 Motion Compensation......Page 660
 19.4 Video Signal Representation......Page 663
  19.5.1 Motion Compensation......Page 669
  19.5.2 The Loop Filter......Page 671
  19.5.4 Quantization and Coding......Page 672
 19.6 Model-Based Coding......Page 674
 19.7 Asymmetric Applications......Page 675
 19.8 The MPEG-1 Video Standard......Page 677
 19.9 The MPEG-2 Video Standard4pt\'0137\'0137H.262......Page 680
 19.10 ITU-T Recommendation H.263......Page 683
  19.10.2 Syntax-Based Arithmetic Coding Mode......Page 685
  19.10.6 Deblocking Filter Mode......Page 686
  19.10.11 Alternative Inter VLC Mode......Page 687
  19.10.13 Enhanced Reference Picture Selection Mode......Page 688
  19.11.1 Motion-Compensated Prediction......Page 689
  19.11.2 The Transform......Page 690
  19.11.4 Quantization......Page 691
  19.11.5 Coding......Page 693
 19.12 MPEG-4 Part 2......Page 694
 19.13 Packet Video......Page 695
  19.13.2 Compression Issues in ATM Networks......Page 696
  19.13.3 Compression Algorithms for Packet Video......Page 697
 19.14 Summary......Page 698
 19.15 Projects and Problems......Page 699
  A.1.1 Frequency of Occurrence......Page 700
  A.1.2 A Measure of Belief......Page 701
  A.1.3 The Axiomatic Approach......Page 703
 A.2 Random Variables......Page 705
 A.3 Distribution Functions......Page 706
 A.4 Expectation......Page 708
  A.5.4 Gamma Distribution......Page 710
 A.6 Stochastic Process......Page 712
 A.7 Projects and Problems......Page 714
 B.1 A Matrix......Page 716
 B.2 Matrix Operations......Page 717
The Root Lattices......Page 722
Bibliography......Page 724
 A......Page 742
 B......Page 743
 C......Page 744
 D......Page 746
 E......Page 747
 F......Page 748
 G......Page 749
 H......Page 750
 I......Page 751
 J......Page 752
 L......Page 753
 M......Page 755
 N......Page 757
 P......Page 758
 Q......Page 759
 S......Page 760
 T......Page 762
 U......Page 763
 V......Page 764
 Z......Page 765