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