数据压缩导论（英文版·第3版）

1 Introduction 1
1.1 Compression Techniques 3
1.1.1 Lossless Compression 4
1.1.2 Lossy Compression 5
1.1.3 Measures of Performance 5
1.2 Modeling and Coding 6
1.3 Summary 10
1.4 Projects and Problems 11
2 Mathematical Preliminaries for Lossless Compression 13
2.1 Overview 13
2.2 A Brief Introduction to Information Theory 13
2.2.1 Derivation of Average Information 18
2.3 Models 23
2.3.1 Physical Models 23
2.3.2 Probability Models 23
2.3.3 Markov Models 24
2.3.4 Composite Source Model 27
2.4 Coding 27
2.4.1 Uniquely Decodable Codes 28
2.4.2 Prefix Codes 31
2.4.3 The Kraft-McMillan Inequality 32
2.5 Algorithmic Information Theory 35
2.6 Minimum Description Length Principle 36
2.7 Summary 37
2.8 Projects and Problems 38
3 Huffman Coding 41
3.1 Overview 41
3.2 The Huffman Coding Algorithm 41
3.2.1 Minimum Variance Huffman Codes 46
3.2.2 Optimality of Huffman Codes 48
3.2.3 Length of Huffman Codes 49
3.2.4 Extended Huffman Codes 51
3.3 Nonbinary Huffman Codes 55
3.4 Adaptive Huffman Coding 58
3.4.1 Update Procedure 59
3.4.2 Encoding Procedure 62
3.4.3 Decoding Procedure 63
3.5 Golomb Codes 65
3.6 Rice Codes 67
3.6.1 CCSDS Recommendation for Lossless Compression 67
3.7 Tunstall Codes 69
3.8 Applications of Huffman Coding 72
3.8.1 Lossless Image Compression 72
3.8.2 Text Compression 74
3.8.3 Audio Compression 75
3.9 Summary 77
3.10 Projects and Problems 77
4 Arithmetic Coding 81
4.1 Overview 81
4.2 Introduction 81
4.3 Coding a Sequence 83
4.3.1 Generating a Tag 84
4.3.2 Deciphering the Tag 91
4.4 Generating a Binary Code 92
4.4.1 Uniqueness and Efficiency of the Arithmetic Code 93
4.4.2 Algorithm Implementation 96
4.4.3 Integer Implementation 102
4.5 Comparison of Huffman and Arithmetic Coding 109
4.6 Adaptive Arithmetic Coding 112
4.7 Applications 112
4.8 Summary 113
4.9 Projects and Problems 114
5 Dictionary Techniques 117
5.1 Overview 117
5.2 Introduction 117
5.3 Static Dictionary 118
5.3.1 Digram Coding 119
5.4 Adaptive Dictionary 121
5.4.1 The LZ7.7 Approach 121
5.4.2 The LZ78 Approach 125
5.5 Applications 133
5.5.1 File Compression-UNIX compress 133
5.5.2 Image Compression-The Graphics Interchange Format (GIF) 133
5.5.3 Image Compression-Portable Network Graphics (PNG) 134
5.5.4 Compression over Modems-V.42 bis 136
5.6 Summary 138
5.7 Projects and Problems 139
6 Context-Based Compression 141
6.1 Overview 141
6.2 Introduction 141
6.3 Prediction with Partial Match (ppm) 143
6.3.1 The Basic Algorithm 143
6.3.2 The Escape Symbol 149
6.3.3 Length of Context 150
6.3.4 The Exclusion Principle 151
6.4 The Burrows-Wheeler Transform 152
6.4.1 Move-to-Front Coding 156
6.5 Associative Coder of Buyanovsky (ACB) 157
6.6 Dynamic Markov Compression 158
6.7 Summary 160
6.8 Projects and Problems 161
7 Lossless Image Compression 163
7.1 Overview 163
7.2 Introduction 163
7.2.1 The Old JPEG Standard 164
7.3 CALIC 166
7.4 JPEG-LS 170
7.5 Multiresolution Approaches 172
7.5.1 Progressive Image Transmission 173
7.6 Facsimile Encoding 178
7.6.1 Run-Length Coding 179
7.6.2 CCITT Group 3 and 4-Recommendations T.4 and T.6 180
7.6.3 JBIG 183
7.6.4 JBIG2-T.88 189
7.7 MRC-T.44 190
7.8 Summary 193
7.9 Projects and Problems 193
8 Mathematical Preliminaries for Lossy Coding 195
8.1 Overview 195
8.2 Introduction 195
8.3 Distortion Criteria 197
8.3.1 The Human Visual System 199
8.3.2 Auditory Perception 200
8.4 Information Theory Revisited 201
8.4.1 Conditional Entropy 202
8.4.2 Average Mutual Information 204
8.4.3 Differential Entropy 205
8.5 Rate Distortion Theory 208
8.6 Models 215
8.6.1 Probability Models 216
8.6.2 Linear System Models 218
8.6.3 Physical Models 223
8.7 Summary 224
8.8 Projects and Problems 224
9 Scalar Quantization 227
9.1 Overview 227
9.2 Introduction 227
9.3 The Quantization Problem 228
9.4 Uniform Quantizer 233
9.5 Adaptive Quantization 244
9.5.1 Forward Adaptive Quantization 244
9.5.2 Backward Adaptive Quantization 246
9.6 Nonuniform Quantization 253
9.6.1 pdf-Optimized Quantization 253
9.6.2 Companded Quantization 257
9.7 Entropy-Coded Quantization 264
9.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs 265
9.7.2 Entropy-Constrained Quantization 265
9.7.3 High-Rate Optimum Quantization 266
9.8 Summary 269
9.9 Projects and Problems 270
10 Vector Quantization 273
10.1 Overview 273
10.2 Introduction 273
10.3 Advantages of Vector Quantization over Scalar Quantization 276
10.4 The Linde-Buzo-Gray Algorithm 282
10.4.1 Initializing the LBG Algorithm 287
10.4.2 The Empty Cell Problem 294
10.4.3 Use of LBG for Image Compression 294
10.5 Tree-Structured Vector Quantizers 299
10.5.1 Design of Tree-Structured Vector Quantizers 302
10.5.2 Pruned Tree-Structured Vector Quantizers 303
10.6 Structured Vector Quantizers 303
10.6.1 Pyramid Vector Quantization 305
10.6.2 Polar and Spherical Vector Quantizers 306
10.6.3 Lattice Vector Quantizers 307
10.7 Variations on the Theme 311
10.7.1 Gain-Shape Vector Quantization 311
10.7.2 Mean-Removed Vector Quantization 312
10.7.3 Classified Vector Quantization 313
10.7.4 Multistage Vector Quantization 313
10.7.5 Adaptive Vector Quantization 315
10.8 Trellis-Coded Quantization 316
10.9 Summary 321
10.10 Projects and Problems 322
11 Differential Encoding 325
11.1 Overview 325
11.2 Introduction 325
11.3 The Basic Algorithm 328
11.4 Prediction in DPCM 332
11.5 Adaptive DPCM 337
11.5.1 Adaptive Quantization in DPCM 338
11.5.2 Adaptive Prediction in DPCM 339
11.6 Delta Modulation 342
11.6.1 Constant Factor Adaptive Delta Modulation (CFDM) 343
11.6.2 Continuously Variable Slope Delta Modulation 345
11.7 Speech Coding 345
11.7.1 G.726 347
11.8 Image Coding 349
11.9 Summary 351
11.10 Projects and Problems 352
12 Mathematical Preliminaries for Transforms， Subbands， and Wavelets 355
12.1 Overview 355
12.2 Introduction 355
12.3 Vector Spaces 356
12.3.1 Dot or Inner Product 357
12.3.2 Vector Space 357
12.3.3 Subspace 359
12.3.4 Basis 360
12.3.5 Inner Product-Formal Definition 361
12.3.6 Orthogonal and Orthonormal Sets 361
12.4 Fourier Series 362
12.5 Fourier Transform 365
12.5.1 Parseval’s Theorem 366
12.5.2 Modulation Property 366
12.5.3 Convolution Theorem 367
12.6 Linear Systems 368
12.6.1 Time Invariance 368
12.6.2 Transfer Function 368
12.6.3 Impulse Response 369
12.6.4 Filter 371
12.7 Sampling 372
12.7.1 Ideal Sampling-Frequency Domain View 373
12.7.2 Ideal Sampling-Time Domain View 375
12.8 Discrete Fourier Transform 376
12.9 Z-Transform 378
12.9.1 Tabular Method 381
12.9.2 Partial Fraction Expansion 382
12.9.3 Long Division 386
12.9.4 Z-Transform Properties 387
12.9.5 Discrete Convolution 387
12.10 Summary 389
12.11 Projects and Problems 390
13 Transform Coding 391
13.1 Overview 391
13.2 Introduction 391
13.3 The Transform 396
13.4 Transforms of Interest 400
13.4.1 Karhunen-Loéve Transform 401
13.4.2 Discrete Cosine Transform 402
13.4.3 Discrete Sine Transform 404
13.4.4 Discrete Walsh-Hadamard Transform 404
13.5 Quantization and Coding of Transform Coefficients 407
13.6 Application to Image Compression-JPEG 410
13.6.1 The Transform 410
13.6.2 Quantization 411
13.6.3 Coding 413
13.7 Application to Audio Compression-the MDCT 416
13.8 Summary 419
13.9 Projects and Problems 421
14 Subband Coding 423
14.1 Overview 423
14.2 Introduction 423
14.3 Filters 428
14.3.1 Some Filters Used in Subband Coding 432
14.4 The Basic Subband Coding Algorithm 436
14.4.1 Analysis 436
14.4.2 Quantization and Coding 437
14.4.3 Synthesis 437
14.5 Design of Filter Banks 438
14.5.1 Downsampling 440
14.5.2 Upsampling 443
14.6 Perfect Reconstruction Using Two-Channel Filter Banks 444
14.6.1 Two-Channel PR Quadrature Mirror Filters 447
14.6.2 Power Symmetric FIR Filters 449
14.7 M-Band QMF Filter Banks 451
14.8 The Polyphase Decomposition 454
14.9 Bit Allocation 459
14.10 Application to Speech Coding-G.722 461
14.11 Application to Audio Coding-MPEG Audio 462
14.12 Application to Image Compression 463
14.12.1 Decomposing an Image 465
14.12.2 Coding the Subbands 467
14.13 Summary 470
14.14 Projects and Problems 471
15 Wavelet-Based Compression 473
15.1 Overview 473
15.2 Introduction 473
15.3 Wavelets 476
15.4 Multiresolution Analysis and the Scaling Function 480
15.5 Implementation Using Filters 486
15.5.1 Scaling and Wavelet Coefficients 488
15.5.2 Families of Wavelets 491
15.6 Image Compression 494
15.7 Embedded Zerotree Coder 497
15.8 Set Partitioning in Hierarchical Trees 505
15.9 JPEG 2000 512
15.10 Summary 513
15.11 Projects and Problems 513
16 Audio Coding 515
16.1 Overview 515
16.2 Introduction 515
16.2.1 Spectral Masking 517
16.2.2 Temporal Masking 517
16.2.3 Psychoacoustic Model 518
16.3 MPEG Audio Coding 519
16.3.1 Layer I Coding 520
16.3.2 Layer II Coding 521
16.3.3 Layer III Coding-mp3 522
16.4 MPEG Advanced Audio Coding 527
16.4.1 MPEG-2 AAC 527
16.4.2 MPEG-4 AAC 532
16.5 Dolby AC3 (Dolby Digital) 533
16.5.1 Bit Allocation 534
16.6 Other Standards 535
16.7 Summary 536
17 Analysis/Synthesis and Analysis by Synthesis Schemes 537
17.1 Overview 537
17.2 Introduction 537
17.3 Speech Compression 539
17.3.1 The Channel Vocoder 539
17.3.2 The Linear Predictive Coder (Government Standard LPC-10) 542
17.3.3 Code Excited Linear Predicton (CELP) 549
17.3.4 Sinusoidal Coders 552
17.3.5 Mixed Excitation Linear Prediction (MELP) 555
17.4 Wideband Speech Compression-ITU-T G.722.2 558
17.5 Image Compression 559
17.5.1 Fractal Compression 560
17.6 Summary 568
17.7 Projects and Problems 569
18 Video Compression 571
18.1 Overview 571
18.2 Introduction 571
18.3 Motion Compensation 573
18.4 Video Signal Representation 576
18.5 ITU-T Recommendation H.261 582
18.5.1 Motion Compensation 583
18.5.2 The Loop Filter 584
18.5.3 The Transform 586
18.5.4 Quantization and Coding 586
18.5.5 Rate Control 588
18.6 Model-Based Coding 588
18.7 Asymmetric Applications 590
18.8 The MPEG-1 Video Standard 591
18.9 The MPEG-2 Video Standard-H.262 594
18.9.1 The Grand Alliance HDTV Proposal 597
18.10 ITU-T Recommendation H.263 598
18.10.1 Unrestricted Motion Vector Mode 600
18.10.2 Syntax-Based Arithmetic Coding Mode 600
18.10.3 Advanced Prediction Mode 600
18.10.4 PB-frames and Improved PB-frames Mode 600
18.10.5 Advanced Intra Coding Mode 600
18.10.6 Deblocking Filter Mode 601
18.10.7 Reference Picture Selection Mode 601
18.10.8 Temporal， SNR， and Spatial Scalability Mode 601
18.10.9 Reference Picture Resampling 601
18.10.10 Reduced-Resolution Update Mode 602
18.10.11 Alternative Inter VLC Mode 602
18.10.12 Modified Quantization Mode 602
18.10.13 Enhanced Reference Picture Selection Mode 603
18.11 ITU-T Recommendation H.264， MPEG-4 Part 10， Advanced Video Coding 603
18.11.1 Motion-Compensated Prediction 604
18.11.2 The Transform 605
18.11.3 Intra Prediction 605
18.11.4 Quantization 606
18.11.5 Coding 608
18.12 MPEG-4 Part 2 609
18.13 Packet Video 610
18.14 ATM Networks 610
18.14.1 Compression Issues in ATM Networks 611
18.14.2 Compression Algorithms for Packet Video 612
18.15 Summary 613
18.16 Projects and Problems 614
A Probability and Random Processes 615
A.1 Probability 615
A.1.1 Frequency of Occurrence 615
A.1.2 A Measure of Belief 616
A.1.3 The Axiomatic Approach 618
A.2 Random Variables 620
A.3 Distribution Functions 621
A.4 Expectation 623
A.4.1 Mean 624
A.4.2 Second Moment 625
A.4.3 Variance 625
A.5 Types of Distribution 625
A.5.1 Uniform Distribution 625
A.5.2 Gaussian Distribution 626
A.5.3 Laplacian Distribution 626
A.5.4 Gamma Distribution 626
A.6 Stochastic Process 626
A.7 Projects and Problems 629
B A Brief Review of Matrix Concepts 631
B.1 A Matrix 631
B.2 Matrix Operations 632
C The Root Lattices 637
Bibliography 639
Index 655