Data Compression: The Complete Reference, 3E

Data compression is one of the most important fields and tools in modern computing. From archiving data, to CD ROMs, and from coding theory to image analysis, many facets of modern computing rely upon data compression. Data Compression provides a comprehensive reference for the many different types and methods of compression. Included are a detailed and helpful taxonomy, analysis of most common methods, and discussions on the use and comparative benefits of methods and description of "how to" use them. The presentation is organized into the main branches of the field of data compression: run length encoding, statistical methods, dictionary-based methods, image compression, audio compression, and video compression. Detailed descriptions and explanations of the most well-known and frequently used compression methods are covered in a self-contained fashion, with an accessible style and technical level for specialists and nonspecialists. Topics and features: coverage of video compression, including MPEG-1 and H.261; thorough coverage of wavelets methods, including CWT, DWT, EZW and the new Lifting Scheme technique; complete audio compression; QM coder used in JPEG and JBIG, including new JPEG 200 standard; image transformations and detailed coverage of discrete cosine transform and Haar transform; coverage of EIDAC method for compressing simple images; prefix image compression; ACB and FHM curve compression; geometric compression and edgebreaker technique.Data Compression provides an invaluable reference and guide for all computer scientists, computer engineers, electrical engineers, signal/image processing engineers and other scientists needing a comprehensive compilation for a broad range of compression methods. DATA COMPRESSION: THE COMPLETE REFERENCE, 3E......Page 1 Title page......Page 6 Copyright......Page 7 Preface to the Third Edition......Page 9 Preface to the Second Edition......Page 13 Preface to the First Edition......Page 17 Contents......Page 19 Introduction......Page 23 1.1 Intuitive Compression......Page 37 1.2 Run-Length Encoding......Page 42 1.3 RLE Text Compression......Page 43 1.4 RLE Image Compression......Page 47 1.5 Move-to-Front Coding......Page 57 1.6 Scalar Quantization......Page 61 2 Statistical Methods......Page 65 2.1 Information Theory Concepts......Page 66 2.2 Variable-Size Codes......Page 72 2.3 Prefix Codes......Page 73 2.4 The Golomb Code......Page 79 2.5 The Kraft-MacMillan Inequality......Page 87 2.7 Shannon-Fano Coding......Page 88 2.8 Huffman Coding......Page 90 2.9 Adaptive Huffman Coding......Page 106 2.10 MNP5......Page 112 2.11 MNP7......Page 117 2.12 Reliability......Page 118 2.13 Facsimile Compression......Page 121 2.14 Arithmetic Coding......Page 128 2.15 Adaptive Arithmetic Coding......Page 142 2.16 The QM Coder......Page 146 2.17 Text Compression......Page 155 2.18 PPM......Page 156 2.19 Context-Tree Weighting......Page 178 3 Dictionary Methods......Page 187 3.1 String Compression......Page 189 3.2 Simple Dictionary Compression......Page 190 3.3 LZ77 (Sliding Window)......Page 191 3.4 LZSS......Page 195 3.5 Repetition Times......Page 198 3.6 QIC-122......Page 200 3.7 LZX......Page 202 3.8 File Differencing: VCDIFF......Page 205 3.9 LZ78......Page 207 3.10 LZFG......Page 210 3.11 LZRW1......Page 213 3.12 LZRW4......Page 216 3.13 LZW......Page 217 3.14 LZMW......Page 228 3.15 LZAP......Page 230 3.16 LZY......Page 231 3.17 LZP......Page 233 3.18 Repetition Finder......Page 240 3.19 UNIX Compression......Page 243 3.20 GIF Images......Page 244 3.22 Various LZ Applications......Page 245 3.23 Deflate: Zip and Gzip......Page 246 3.24 PNG......Page 258 3.25 XML Compression: XMill......Page 262 3.26 EXE Compressors......Page 264 3.27 CRC......Page 265 3.29 Data Compression Patents......Page 268 3.30 A Unification......Page 270 4 Image Compression......Page 273 4.1 Introduction......Page 275 4.2 Approaches to Image Compression......Page 281 4.3 Intuitive Methods......Page 295 4.4 Image Transforms......Page 296 4.5 Orthogonal Transforms......Page 301 4.6 The Discrete Cosine Transform......Page 311 4.7 Test Images......Page 347 4.8 JPEG......Page 351 4.9 JPEG-LS......Page 368 4.10 Progressive Image Compression......Page 374 4.11 JBIG......Page 382 4.12 JBIG2......Page 391 4.13 Simple Images: EIDAC......Page 402 4.14 Vector Quantization......Page 404 4.15 Adaptive Vector Quantization......Page 412 4.16 Block Matching......Page 417 4.17 Block Truncation Coding......Page 421 4.18 Context-Based Methods......Page 427 4.19 FELICS......Page 430 4.20 Progressive FELICS......Page 433 4.21 MLP......Page 437 4.22 Adaptive Golomb......Page 445 4.23 PPPM......Page 446 4.24 CALIC......Page 448 4.25 Differential Lossless Compression......Page 451 4.26 DPCM......Page 453 4.27 Context-Tree Weighting......Page 458 4.28 Block Decomposition......Page 459 4.29 Binary Tree Predictive Coding......Page 463 4.30 Quadtrees......Page 470 4.31 Quadrisection......Page 487 4.32 Space-Filling Curves......Page 495 4.33 Hilbert Scan and VQ......Page 496 4.34 Finite Automata Methods......Page 499 4.35 Iterated Function Systems......Page 516 4.36 Cell Encoding......Page 533 5.1 Fourier Transform......Page 535 5.2 The Frequency Domain......Page 536 5.3 The Uncertainty Principle......Page 540 5.4 Fourier Image Compression......Page 543 5.5 The CWT and Its Inverse......Page 546 5.6 The Haar Transform......Page 552 5.7 Filter Banks......Page 571 5.8 The DWT......Page 581 5.9 Multiresolution Decomposition......Page 594 5.10 Various Image Decompositions......Page 595 5.11 The Lifting Scheme......Page 602 5.12 The IWT......Page 613 5.13 The Laplacian Pyramid......Page 615 5.14 SPIHT......Page 619 5.16 EZW......Page 631 5.17 DjVu......Page 635 5.18 WSQ, Fingerprint Compression......Page 638 5.19 JPEG 2000......Page 644 6.1 Analog Video......Page 659 6.2 Composite and Components Video......Page 665 6.3 Digital Video......Page 667 6.4 Video Compression......Page 671 6.5 MPEG......Page 683 6.6 MPEG-4......Page 705 6.7 H.261......Page 710 7 Audio Compression......Page 713 7.1 Sound......Page 714 7.2 Digital Audio......Page 717 7.3 The Human Auditory System......Page 720 7.4 u-Law and A-Law Companding......Page 726 7.5 ADPCM Audio Compression......Page 732 7.6 MLP Audio......Page 734 7.7 Speech Compression......Page 739 7.8 Shorten......Page 747 7.9 MPEG-1 Audio Layers......Page 751 8 Other Methods......Page 777 8.1 The Burrows-Wheeler Method......Page 778 8.2 Symbol Ranking......Page 783 8.3 ACB......Page 787 8.4 Sort-Based Context Similarity......Page 794 8.5 Sparse Strings......Page 799 8.6 Word-Based Text Compression......Page 811 8.7 Textual Image Compression......Page 815 8.8 Dynamic Markov Coding......Page 821 8.9 FHM Curve Compression......Page 830 8.10 Sequitur......Page 833 8.11 Triangle Mesh Compression: Edgebreaker......Page 838 8.12 SCSU: Unicode Compression......Page 849 Bibliography......Page 857 Glossary......Page 877 Joining the Data Compression Community......Page 899 Index......Page 901 Colophon......Page 921 Data compression is one of the most important fields and tools in modern computing. From archiving data, to CD ROMs, and from coding theory to image analysis, many facets of modern computing rely upon data compression. Data Compression provides a comprehensive reference for the many different types and methods of compression. Included are a detailed and helpful taxonomy, analysis of most common methods, and discussions on the use and comparative benefits of methods and description of "how to" use them. The presentation is organized into the main branches of the field of data run length encoding, statistical methods, dictionary-based methods, image compression, audio compression, and video compression. Detailed descriptions and explanations of the most well-known and frequently used compression methods are covered in a self-contained fashion, with an accessible style and technical level for specialists and nonspecialists. Topics and coverage of video compression, including MPEG-1 and H.261; thorough coverage of wavelets methods, including CWT, DWT, EZW and the new Lifting Scheme technique; complete audio compression; QM coder used in JPEG and JBIG, including new JPEG 200 standard; image transformations and detailed coverage of discrete cosine transform and Haar transform; coverage of EIDAC method for compressing simple images; prefix image compression; ACB and FHM curve compression; geometric compression and edgebreaker technique. Data Compression provides an invaluable reference and guide for all computer scientists, computer engineers, electrical engineers, signal/image processing engineers and other scientists needing a comprehensive compilation for a broad range of compression methods. "This substantially enhanced reference is an essential resource and companion for all computer scientists, computer electrical, and signal image processing engineers, and scientists needing a comprehensive compilation of compression methods. It requires only a minimum of mathematics and is well suited to nonspecialists and general readers."--Jacket