Loading......

Preface
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
2i C O N T E N T S
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
C O N T E N T S    3
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
4 C O N T E N T S
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
C O N T E N T S    5
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
6i C O N T E N T S
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
C O N T E N T S    7
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
8v C O N T E N T S
1.7  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
C O N T E N T S    9
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