Each edition of Introduction to Data Compression has widely been considered the best introduction and reference text on the art and science of data compression, and the third edition continues in this tradition. Data compression techniques and technology are ever-evolving with new applications in image, speech, text, audio, and video. The third edition includes all the cutting edge updates the reader will need during the work day and in class. Khalid Sayood provides an extensive introduction to the theory underlying today's compression techniques with detailed instruction for their applications using several examples to explain the concepts. Encompassing the entire field of data compression Introduction to Data Compression, includes lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, scalar and vector quantization. Khalid Sayood provides a working knowledge of data compression, giving the reader the tools to develop a complete and concise compression package upon completion of his book. *New content added on the topic of audio compression including a description of the mp3 algorithm *New video coding standard and new facsimile standard explained *Completely explains established and emerging standards in depth including JPEG 2000, JPEG-LS, MPEG-2, Group 3 and 4 faxes, JBIG 2, ADPCM, LPC, CELP, and MELP *Source code provided via companion web site that gives readers the opportunity to build their own algorithms, choose and implement techniques in their own applications
Author(s): Khalid Sayood
Series: Morgan Kaufmann series in multimedia information and systems
Edition: 3
Publisher: Morgan Kaufmann
Year: 2005
Language: English
Pages: 703
Title page......Page 4
Copyright page......Page 5
Contents......Page 8
Audience......Page 18
Approach......Page 19
Content and Organization......Page 20
A Personal View......Page 21
Acknowledgments......Page 22
1 Introduction......Page 24
1.1 Compression Techniques......Page 26
1.1.1 Lossless Compression......Page 27
1.1.3 Measures of Performance......Page 28
1.2 Modeling and Coding......Page 29
1.3 Summary......Page 33
1.4 Projects and Problems......Page 34
2.2 A Brief Introduction to Information Theory......Page 36
2.2.1 Derivation of Average Information......Page 41
2.3.2 Probability Models......Page 46
2.3.3 Markov Models......Page 47
2.4 Coding......Page 50
2.4.1 Uniquely Decodable Codes......Page 51
2.4.2 Prefix Codes......Page 54
2.4.3 The Kraft-McMillan Inequality......Page 55
2.5 Algorithmic Information Theory......Page 58
2.6 Minimum Description Length Principle......Page 59
2.7 Summary......Page 60
2.8 Projects and Problems......Page 61
3.2 The Huffman Coding Algorithm......Page 64
3.2.1 Minimum Variance Huffman Codes......Page 69
3.2.2 Optimality of Huffman Codes......Page 71
3.2.3 Length of Huffman Codes......Page 72
3.2.4 Extended Huffman Codes......Page 74
3.3 Nonbinary Huffman Codes......Page 78
3.4 Adaptive Huffman Coding......Page 81
3.4.1 Update Procedure......Page 82
3.4.2 Encoding Procedure......Page 85
3.4.3 Decoding Procedure......Page 86
3.5 Golomb Codes......Page 88
3.6.1 CCSDS Recommendation for Lossless Compression......Page 90
3.7 Tunstall Codes......Page 92
3.8.1 Lossless Image Compression......Page 95
3.8.2 Text Compression......Page 97
3.8.3 Audio Compression......Page 98
3.10 Projects and Problems......Page 100
4.2 Introduction......Page 104
4.3 Coding a Sequence......Page 106
4.3.1 Generating a Tag......Page 107
4.3.2 Deciphering the Tag......Page 114
4.4 Generating a Binary Code......Page 115
4.4.1 Uniqueness and Ef f iciency of the Arithmetic Code......Page 116
4.4.2 Algorithm Implementation......Page 119
4.4.3 Integer Implementation......Page 125
4.5 Comparison of Huffman and Arithmetic Coding......Page 132
4.7 Applications......Page 135
4.8 Summary......Page 136
4.9 Projects and Problems......Page 137
5.2 Introduction......Page 140
5.3 Static Dictionary......Page 141
5.3.1 Digram Coding......Page 142
5.4.1 The LZ77 Approach......Page 144
5.4.2 The LZ78 Approach......Page 148
5.5.2 Image Compression—The Graphics Interchange Format (GIF)......Page 156
5.5.3 Image Compression—Portable Network Graphics (PNG)......Page 157
5.5.4 Compression over Modems—V.42 bis......Page 159
5.6 Summary......Page 161
5.7 Projects and Problems......Page 162
6.2 Introduction......Page 164
6.3.1 The Basic Algorithm......Page 166
6.3.2 The Escape Symbol......Page 172
6.3.3 Length of Context......Page 173
6.3.4 The Exclusion Principle......Page 174
6.4 The Burrows-Wheeler Transform......Page 175
6.4.1 Move-to-Front Coding......Page 179
6.5 Associative Coder of Buyanovsky (ACB)......Page 180
6.6 Dynamic Markov Compression......Page 181
6.7 Summary......Page 183
6.8 Projects and Problems......Page 184
7.2 Introduction......Page 186
7.2.1 The Old JPEG Standard......Page 187
7.3 CALIC......Page 189
7.4 JPEG-LS......Page 193
7.5 Multiresolution Approaches......Page 195
7.5.1 Progressive Image Transmission......Page 196
7.6 Facsimile Encoding......Page 201
7.6.1 Run-Length Coding......Page 202
7.6.2 CCITT Group 3 and 4—Recommendations T.4 and T.6......Page 203
7.6.3 JBIG......Page 206
7.6.4 JBIG2—T.88......Page 212
7.7 MRC—T.44......Page 213
7.9 Projects and Problems......Page 216
8.2 Introduction......Page 218
8.3 Distortion Criteria......Page 220
8.3.1 The Human Visual System......Page 222
8.3.2 Auditory Perception......Page 223
8.4 Information Theory Revisited......Page 224
8.4.1 Conditional Entropy......Page 225
8.4.2 Average Mutual Information......Page 227
8.4.3 Differential Entropy......Page 228
8.5 Rate Distortion Theory......Page 231
8.6 Models......Page 238
8.6.1 Probability Models......Page 239
8.6.2 Linear System Models......Page 241
8.6.3 Physical Models......Page 246
8.8 Projects and Problems......Page 247
9.2 Introduction......Page 250
9.3 The Quantization Problem......Page 251
9.4 Uniform Quantizer......Page 256
9.5.1 Forward Adaptive Quantization......Page 267
9.5.2 Backward Adaptive Quantization......Page 269
9.6.1 pdf-Optimized Quantization......Page 276
9.6.2 Companded Quantization......Page 280
9.7 Entropy-Coded Quantization......Page 287
9.7.2 Entropy-Constrained Quantization......Page 288
9.7.3 High-Rate Optimum Quantization......Page 289
9.8 Summary......Page 292
9.9 Projects and Problems......Page 293
10.2 Introduction......Page 296
10.3 Advantages of Vector Quantization over Scalar Quantization......Page 299
10.4 The Linde-Buzo-Gray Algorithm......Page 305
10.4.1 Initializing the LBG Algorithm......Page 310
10.4.3 Use of LBG for Image Compression......Page 317
10.5 Tree-Structured Vector Quantizers......Page 322
10.5.1 Design of Tree-Structured Vector Quantizers......Page 325
10.6 Structured Vector Quantizers......Page 326
10.6.1 Pyramid Vector Quantization......Page 328
10.6.2 Polar and Spherical Vector Quantizers......Page 329
10.6.3 Lattice Vector Quantizers......Page 330
10.7.1 Gain-Shape Vector Quantization......Page 334
10.7.2 Mean-Removed Vector Quantization......Page 335
10.7.4 Multistage Vector Quantization......Page 336
10.7.5 Adaptive Vector Quantization......Page 338
10.8 Trellis-Coded Quantization......Page 339
10.9 Summary......Page 344
10.10 Projects and Problems......Page 345
11.2 Introduction......Page 348
11.3 The Basic Algorithm......Page 351
11.4 Prediction in DPCM......Page 355
11.5 Adaptive DPCM......Page 360
11.5.1 Adaptive Quantization in DPCM......Page 361
11.5.2 Adaptive Prediction in DPCM......Page 362
11.6 Delta Modulation......Page 365
11.6.1 Constant Factor Adaptive Delta Modulation (CFDM)......Page 366
11.7 Speech Coding......Page 368
11.7.1 G.726......Page 370
11.8 Image Coding......Page 372
11.9 Summary......Page 374
11.10 Projects and Problems......Page 375
12.2 Introduction......Page 378
12.3 Vector Spaces......Page 379
12.3.2 Vector Space......Page 380
12.3.3 Subspace......Page 382
12.3.4 Basis......Page 383
12.3.6 Orthogonal and Orthonormal Sets......Page 384
12.4 Fourier Series......Page 385
12.5 Fourier Transform......Page 388
12.5.2 Modulation Property......Page 389
12.5.3 Convolution Theorem......Page 390
12.6.2 Transfer Function......Page 391
12.6.3 Impulse Response......Page 392
12.6.4 Filter......Page 394
12.7 Sampling......Page 395
12.7.1 Ideal Sampling—Frequency Domain View......Page 396
12.7.2 Ideal Sampling—Time Domain View......Page 398
12.8 Discrete Fourier Transform......Page 399
12.9 Z-Transform......Page 401
12.9.1 Tabular Method......Page 404
12.9.2 Partial Fraction Expansion......Page 405
12.9.3 Long Division......Page 409
12.9.5 Discrete Convolution......Page 410
12.10 Summary......Page 412
12.11 Projects and Problems......Page 413
13.2 Introduction......Page 414
13.3 The Transform......Page 419
13.4 Transforms of Interest......Page 423
13.4.1 Karhunen-Loéve Transform......Page 424
13.4.2 Discrete Cosine Transform......Page 425
13.4.4 Discrete Walsh-Hadamard Transform......Page 427
13.5 Quantization and Coding of Transform Coefficients......Page 430
13.6.1 The Transform......Page 433
13.6.2 Quantization......Page 434
13.6.3 Coding......Page 436
13.7 Application to Audio Compression—The MDCT......Page 439
13.8 Summary......Page 442
13.9 Projects and Problems......Page 444
14.2 Introduction......Page 446
14.3 Filters......Page 451
14.3.1 Some Filters Used in Subband Coding......Page 455
14.4.1 Analysis......Page 459
14.4.3 Synthesis......Page 460
14.5 Design of Filter Banks......Page 461
14.5.1 Downsampling......Page 463
14.5.2 Upsampling......Page 466
14.6 Perfect Reconstruction Using Two-Channel Filter Banks......Page 467
14.6.1 Two-Channel PR Quadrature Mirror Filters......Page 470
14.6.2 Power Symmetric FIR Filters......Page 472
14.7 M-Band QMF Filter Banks......Page 474
14.8 The Polyphase Decomposition......Page 477
14.9 Bit Allocation......Page 482
14.10 Application to Speech Coding—G.722......Page 484
14.11 Application to Audio Coding—MPEG Audio......Page 485
14.12 Application to Image Compression......Page 486
14.12.1 Decomposing an Image......Page 488
14.12.2 Coding the Subbands......Page 490
14.13 Summary......Page 493
14.14 Projects and Problems......Page 494
15.2 Introduction......Page 496
15.3 Wavelets......Page 499
15.4 Multiresolution Analysis and the Scaling Function......Page 503
15.5 Implementation Using Filters......Page 509
15.5.1 Scaling and Wavelet Coefficients......Page 511
15.5.2 Families of Wavelets......Page 514
15.6 Image Compression......Page 517
15.7 Embedded Zerotree Coder......Page 520
15.8 Set Partitioning in Hierarchical Trees......Page 528
15.9 JPEG 2000......Page 535
15.11 Projects and Problems......Page 536
16.2 Introduction......Page 538
16.2.2 Temporal Masking......Page 540
16.2.3 Psychoacoustic Model......Page 541
16.3 MPEG Audio Coding......Page 542
16.3.1 Layer I Coding......Page 543
16.3.2 Layer II Coding......Page 544
16.3.3 Layer III Coding—mp3......Page 545
16.4.1 MPEG-2 AAC......Page 550
16.4.2 MPEG-4 AAC......Page 555
16.5 Dolby AC3 (Dolby Digital)......Page 556
16.5.1 Bit Allocation......Page 557
16.6 Other Standards......Page 558
16.7 Summary......Page 559
17.2 Introduction......Page 560
17.3.1 The Channel Vocoder......Page 562
17.3.2 The Linear Predictive Coder (Government Standard LPC-10)......Page 565
17.3.3 Code Excited Linear Predicton (CELP)......Page 572
17.3.4 Sinusoidal Coders......Page 575
17.3.5 Mixed Excitation Linear Prediction (MELP)......Page 578
17.4 Wideband Speech Compression—ITU-T G.722.2......Page 581
17.5 Image Compression......Page 582
17.5.1 Fractal Compression......Page 583
17.6 Summary......Page 591
17.7 Projects and Problems......Page 592
18.2 Introduction......Page 594
18.3 Motion Compensation......Page 596
18.4 Video Signal Representation......Page 599
18.5 ITU-T Recommendation H.261......Page 605
18.5.1 Motion Compensation......Page 606
18.5.2 The Loop Filter......Page 607
18.5.4 Quantization and Coding......Page 609
18.6 Model-Based Coding......Page 611
18.7 Asymmetric Applications......Page 613
18.8 The MPEG-1 Video Standard......Page 614
18.9 The MPEG-2 Video Standard—H.262......Page 617
18.9.1 The Grand Alliance HDTV Proposal......Page 620
18.10 ITU-T Recommendation H.263......Page 621
18.10.5 Advanced Intra Coding Mode......Page 623
18.10.9 Reference Picture Resampling......Page 624
18.10.12 Modified Quantization Mode......Page 625
18.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Coding......Page 626
18.11.1 Motion-Compensated Prediction......Page 627
18.11.3 Intra Prediction......Page 628
18.11.4 Quantization......Page 629
18.11.5 Coding......Page 631
18.12 MPEG-4 Part 2......Page 632
18.14 ATM Networks......Page 633
18.14.1 Compression Issues in ATM Networks......Page 634
18.14.2 Compression Algorithms for Packet Video......Page 635
18.15 Summary......Page 636
18.16 Projects and Problems......Page 637
A.1.1 Frequency of Occurrence......Page 638
A.1.2 A Measure of Belief......Page 639
A.1.3 The Axiomatic Approach......Page 641
A.2 Random Variables......Page 643
A.3 Distribution Functions......Page 644
A.4 Expectation......Page 646
A.4.1 Mean......Page 647
A.5.1 Uniform Distribution......Page 648
A.6 Stochastic Process......Page 649
A.7 Projects and Problems......Page 652
B.1 A Matrix......Page 654
B.2 Matrix Operations......Page 655
C The Root Lattices......Page 660
Bibliography......Page 662
Index......Page 678
