Data_Compression+The+Complete+Reference+4th+edition

1 Basic Techniques 17 1.1 Intuitive Compression 17 1.2 Run-Length Encoding 22 1.3 RLE Text Compression 23 1.4 RLE Image Compression 27 1.5 Move-to-Front Coding 37 1.6 Scalar Quantization 40 1.7 Recursive Range Reduction 42 2 Statistical Methods 47 2.1 Information Theory Concepts 48 2.2 Variable-Size Codes 54 2.3 Prefix Codes 55 2.4 Tunstall Code 61 2.5 The Golomb Code 63 2.6 The Kraft-MacMillan Inequality 71 2.7 Shannon-Fano Coding 72 2.8 Huffman Coding 74 2.9 Adaptive Huffman Coding 89 2.10 MNP5 95 2.11 MNP7 100 2.12 Reliability 101 2.13 Facsimile Compression 104 2.14 Arithmetic Coding 112 xxii Contents 2.15 Adaptive Arithmetic Coding 125 2.16 The QM Coder 129 2.17 Text Compression 139 2.18 PPM 139 2.19 Context-Tree Weighting 161 3 Dictionary Methods 171 3.1 String Compression 173 3.2 Simple Dictionary Compression 174 3.3 LZ77 (Sliding Window) 176 3.4 LZSS 179 3.5 Repetition Times 182 3.6 QIC-122 184 3.7 LZX 187 3.8 LZ78 189 3.9 LZFG 192 3.10 LZRW1 195 3.11 LZRW4 198 3.12 LZW 199 3.13 LZMW 209 3.14 LZAP 212 3.15 LZY 213 3.16 LZP 214 3.17 Repetition Finder 221 3.18 UNIX Compression 224 3.19 GIF Images 225 3.20 RAR and WinRAR 226 3.21 The V.42bis Protocol 228 3.22 Various LZ Applications 229 3.23 Deflate: Zip and Gzip 230 3.24 LZMA and 7-Zip 241 3.25 PNG 246 3.26 XML Compression: XMill 251 3.27 EXE Compressors 253 3.28 CRC 254 3.29 Summary 256 3.30 Data Compression Patents 256 3.31 A Unification 259 Contents xxiii 4 Image Compression 263 4.1 Introduction 265 4.2 Approaches to Image Compression 270 4.3 Intuitive Methods 283 4.4 Image Transforms 284 4.5 Orthogonal Transforms 289 4.6 The Discrete Cosine Transform 298 4.7 Test Images 333 4.8 JPEG 337 4.9 JPEG-LS 354 4.10 Progressive Image Compression 360 4.11 JBIG 369 4.12 JBIG2 378 4.13 Simple Images: EIDAC 389 4.14 Vector Quantization 390 4.15 Adaptive Vector Quantization 398 4.16 Block Matching 403 4.17 Block Truncation Coding 406 4.18 Context-Based Methods 412 4.19 FELICS 415 4.20 Progressive FELICS 417 4.21 MLP 422 4.22 Adaptive Golomb 436 4.23 PPPM 438 4.24 CALIC 439 4.25 Differential Lossless Compression 442 4.26 DPCM 444 4.27 Context-Tree Weighting 449 4.28 Block Decomposition 450 4.29 Binary Tree Predictive Coding 454 4.30 Quadtrees 461 4.31 Quadrisection 478 4.32 Space-Filling Curves 485 4.33 Hilbert Scan and VQ 487 4.34 Finite Automata Methods 497 4.35 Iterated Function Systems 513 4.36 Cell Encoding 529 xxiv Contents 5 Wavelet Methods 531 5.1 Fourier Transform 532 5.2 The Frequency Domain 534 5.3 The Uncertainty Principle 538 5.4 Fourier Image Compression 540 5.5 The CWT and Its Inverse 543 5.6 The Haar Transform 549 5.7 Filter Banks 566 5.8 The DWT 576 5.9 Multiresolution Decomposition 589 5.10 Various Image Decompositions 589 5.11 The Lifting Scheme 596 5.12 The IWT 608 5.13 The Laplacian Pyramid 610 5.14 SPIHT 614 5.15 CREW 626 5.16 EZW 626 5.17 DjVu 630 5.18 WSQ, Fingerprint Compression 633 5.19 JPEG 2000 639 6 Video Compression 653 6.1 Analog Video 653 6.2 Composite and Components Video 658 6.3 Digital Video 660 6.4 Video Compression 664 6.5 MPEG 676 6.6 MPEG-4 698 6.7 H.261 703 6.8 H.264 706 7 Audio Compression 719 7.1 Sound 720 7.2 Digital Audio 724 7.3 The Human Auditory System 727 7.4 WAVE Audio Format 734 7.5 μ-Law and A-Law Companding 737 7.6 ADPCM Audio Compression 742 7.7 MLP Audio 744 7.8 Speech Compression 750 7.9 Shorten 757 7.10 FLAC 762 7.11 WavPack 772 7.12 Monkey’s Audio 783 7.13 MPEG-4 Audio Lossless Coding (ALS) 784 7.14 MPEG-1/2 Audio Layers 795 7.15 Advanced Audio Coding (AAC) 821 7.16 Dolby AC-3 847 Contents xxv 8 Other Methods 851 8.1 The Burrows-Wheeler Method 853 8.2 Symbol Ranking 858 8.3 ACB 862 8.4 Sort-Based Context Similarity 868 8.5 Sparse Strings 874 8.6 Word-Based Text Compression 885 8.7 Textual Image Compression 888 8.8 Dynamic Markov Coding 895 8.9 FHM Curve Compression 903 8.10 Sequitur 906 8.11 Triangle Mesh Compression: Edgebreaker 911 8.12 SCSU: Unicode Compression 922 8.13 Portable Document Format (PDF) 928 8.14 File Differencing 930 8.15 Hyperspectral Data Compression 941 Answers to Exercises 953 Bibliography 1019 Glossary 1041 Joining the Data Compression Community 1067 Index 1069