Data Compression The Complete Reference

Team DDU......Page 1
Preface to the Third Edition......Page 8
Preface to the Second Edition......Page 12
Preface to the First Edition......Page 16
Contents......Page 18
Introduction......Page 22
1.1 Intuitive Compression......Page 36
1.2 Run-Length Encoding......Page 41
1.3 RLE Text Compression......Page 42
1.4 RLE Image Compression......Page 46
1.5 Move-to-Front Coding......Page 56
1.6 Scalar Quantization......Page 60
2 Statistical Methods......Page 64
2.1 Information Theory Concepts......Page 65
2.2 Variable-Size Codes......Page 71
2.3 Prefix Codes......Page 72
2.4 The Golomb Code......Page 78
2.5 The Kraft-MacMillan Inequality......Page 86
2.7 Shannon-Fano Coding......Page 87
2.8 Huffman Coding......Page 89
2.9 Adaptive Huffman Coding......Page 105
2.10 MNP5......Page 111
2.11 MNP7......Page 116
2.12 Reliability......Page 117
2.13 Facsimile Compression......Page 120
2.14 Arithmetic Coding......Page 127
2.15 Adaptive Arithmetic Coding......Page 141
2.16 The QM Coder......Page 145
2.17 Text Compression......Page 154
2.18 PPM......Page 155
2.19 Context-Tree Weighting......Page 177
3 Dictionary Methods......Page 186
3.1 String Compression......Page 188
3.2 Simple Dictionary Compression......Page 189
3.3 LZ77 (Sliding Window)......Page 190
3.4 LZSS......Page 194
3.5 Repetition Times......Page 197
3.6 QIC-122......Page 199
3.7 LZX......Page 201
3.8 File Differencing: VCDIFF......Page 204
3.9 LZ78......Page 206
3.10 LZFG......Page 209
3.11 LZRW1......Page 212
3.12 LZRW4......Page 215
3.13 LZW......Page 216
3.14 LZMW......Page 227
3.15 LZAP......Page 229
3.16 LZY......Page 230
3.17 LZP......Page 232
3.18 Repetition Finder......Page 239
3.19 UNIX Compression......Page 242
3.20 GIF Images......Page 243
3.22 Various LZ Applications......Page 244
3.23 Deflate: Zip and Gzip......Page 245
3.24 PNG......Page 257
3.25 XML Compression: XMill......Page 261
3.26 EXE Compressors......Page 263
3.27 CRC......Page 264
3.29 Data Compression Patents......Page 267
3.30 A Unification......Page 269
4 Image Compression......Page 272
4.1 Introduction......Page 274
4.2 Approaches to Image Compression......Page 280
4.3 Intuitive Methods......Page 294
4.4 Image Transforms......Page 295
4.5 Orthogonal Transforms......Page 300
4.6 The Discrete Cosine Transform......Page 310
4.7 Test Images......Page 346
4.8 JPEG......Page 350
4.9 JPEG-LS......Page 367
4.10 Progressive Image Compression......Page 373
4.11 JBIG......Page 381
4.12 JBIG2......Page 390
4.13 Simple Images: EIDAC......Page 401
4.14 Vector Quantization......Page 403
4.15 Adaptive Vector Quantization......Page 411
4.16 Block Matching......Page 416
4.17 Block Truncation Coding......Page 420
4.18 Context-Based Methods......Page 426
4.19 FELICS......Page 429
4.20 Progressive FELICS......Page 432
4.21 MLP......Page 436
4.22 Adaptive Golomb......Page 444
4.23 PPPM......Page 445
4.24 CALIC......Page 447
4.25 Differential Lossless Compression......Page 450
4.26 DPCM......Page 452
4.27 Context-Tree Weighting......Page 457
4.28 Block Decomposition......Page 458
4.29 Binary Tree Predictive Coding......Page 462
4.30 Quadtrees......Page 469
4.31 Quadrisection......Page 486
4.32 Space-Filling Curves......Page 494
4.33 Hilbert Scan and VQ......Page 495
4.34 Finite Automata Methods......Page 498
4.35 Iterated Function Systems......Page 515
4.36 Cell Encoding......Page 532
5.1 Fourier Transform......Page 534
5.2 The Frequency Domain......Page 535
5.3 The Uncertainty Principle......Page 539
5.4 Fourier Image Compression......Page 542
5.5 The CWT and Its Inverse......Page 545
5.6 The Haar Transform......Page 551
5.7 Filter Banks......Page 570
5.8 The DWT......Page 580
5.9 Multiresolution Decomposition......Page 593
5.10 Various Image Decompositions......Page 594
5.11 The Lifting Scheme......Page 601
5.12 The IWT......Page 612
5.13 The Laplacian Pyramid......Page 614
5.14 SPIHT......Page 618
5.16 EZW......Page 630
5.17 DjVu......Page 634
5.18 WSQ, Fingerprint Compression......Page 637
5.19 JPEG 2000......Page 643
6.1 Analog Video......Page 658
6.2 Composite and Components Video......Page 664
6.3 Digital Video......Page 666
6.4 Video Compression......Page 670
6.5 MPEG......Page 682
6.6 MPEG-4......Page 704
6.7 H.261......Page 709
7 Audio Compression......Page 712
7.1 Sound......Page 713
7.2 Digital Audio......Page 716
7.3 The Human Auditory System......Page 719
7.4 ¦Ì-Law and A-Law Companding......Page 725
7.5 ADPCM Audio Compression......Page 731
7.6 MLP Audio......Page 733
7.7 Speech Compression......Page 738
7.8 Shorten......Page 746
7.9 MPEG-1 Audio Layers......Page 750
8 Other Methods......Page 776
8.1 The Burrows-Wheeler Method......Page 777
8.2 Symbol Ranking......Page 782
8.3 ACB......Page 786
8.4 Sort-Based Context Similarity......Page 793
8.5 Sparse Strings......Page 798
8.6 Word-Based Text Compression......Page 810
8.7 Textual Image Compression......Page 814
8.8 Dynamic Markov Coding......Page 820
8.9 FHM Curve Compression......Page 829
8.10 Sequitur......Page 832
8.11 Triangle Mesh Compression: Edgebreaker......Page 837
8.12 SCSU: Unicode Compression......Page 848
Bibliography......Page 856
Glossary......Page 876
Joining the Data Compression Community......Page 898
Index......Page 900