By David Salomon. Published by Springer (2000). ISBN 0-387-95045-1. LCCN QA76.9.D33 S25 2000. xvi + 823 pages.
The book has been translated in 2003 into Chinese by the publishing house of electronic industry, Beijing with ISBN 7-5053-8247-0.
(See Chinese front and back covers.)
A BibTeX style file and an Errata list are available.
Written February 1998 through September 1999. Produced March 2000 through October 2000. This book is a major extension of the first edition. In addition to error corrections, it includes three new chapters, several sections with new material, and the description of many compression methods not included in the first edition. The book is hardbound with a colorful cover depicting bits of various sizes.
The first new chapter is Chapter 5, on wavelets and their applications to image and audio compression. The chapter opens with an intuitive explanation of wavelets, illustrating the continuous wavelet transform (CWT). It continues with a detailed example that shows how the Haar transform can be applied to the compression of images. This is followed by a general discussion of filter banks and the discrete wavelet transform (DWT), and a listing of the wavelet coefficients of many common wavelet filters. The chapter concludes with a description of important compression methods that either use wavelets or are based on wavelets. Included among them are the Laplacian pyramid, set partitioning in hierarchical trees (SPIHT), embedded coding using zerotrees (EZW), the WSQ method for the compression of fingerprints, and JPEG 2000, a new, promising method for the compression of still images
The second new chapter, Chapter 6, discusses video compression. The chapter opens with a general description of CRT operation and basic analog and digital video concepts. It continues with a general discussion of video compression, and it concludes with a description of MPEG-1 and H.261.
Audio compression is the topic of the third new chapter, Chapter 7. The first topic in this chapter is the properties of the human auditory system and how they can be exploited to achieve lossy audio compression. A discussion of a few simple audio compression methods follows, and the chapter concludes with a description of the three audio layers of MPEG-1, including the very popular mp3 format.
Of the many compression methods included in this edition, the most important ones are JPEG2000, MPEG-1 video, the three MPEG audio layers, JBIG2, and the Q-coder. However, about 20 compression methods have been added to the original material, and their descriptions are included in this 2nd edition. Also, Section 4.31 (Weighted Finite Automata) has been rewritten with help from Karel Culik and Raghavendra Udupa.
In addition to specific compression methods, several general compression topics are included in this edition. The most important among them are scalar and vector quantization, approaches to image compression (including a detailed discussion of orthogonal transforms), and progressive transmission of images. Also, important material concerning data compression patents has been added.
The rest of this web page contains the table of contents and information about auxiliary
material that can be freely downloaded in PDF format.
Preface to the Second Edition vii Preface to the First Edition xi Introduction 1 Chapter 1. Basic Techniques 13 1.1 Intuitive Compression 13 1.2 Run Length Encoding 18 1.3 RLE Text Compression 18 1.4 RLE Image Compression 23 1.5 Move-to-Front Coding 32 1.6 Scalar Quantization 35 Chapter 2. Statistical Methods 39 2.1 Information Theory Concepts 40 2.2 Variable-Size Codes 46 2.3 Prefix Codes 47 2.4 The Golomb Code 53 2.5 The Kraft-MacMillan Inequality 54 2.6 Shannon-Fano Coding 55 2.7 The Counting Argument 57 2.8 Huffman Coding 62 2.9 Adaptive Huffman Coding 76 2.10 MNP5 83 2.11 MNP7 88 2.12 Reliability 89 2.13 Facsimile Compression 91 2.14 Arithmetic Coding 101 2.15 Adaptive Arithmetic Coding 113 2.16 The QM Coder 115 2.17 Text Compression 126 2.18 PPM 127 2.19 Context-Tree Weighting 143 Chapter 3. Dictionary Methods 151 3.1 String Compression 153 3.2 LZ77 (Sliding Window) 154 3.3 LZSS 158 3.4 Repetition Times 161 3.5 QIC-122 163 3.6 LZ78 164 3.7 LZFG 168 3.8 LZRW1 171 3.9 LZRW4 175 3.10 LZW 175 3.11 LZMW 186 3.12 LZAP 189 3.13 LZY 189 3.14 LZP 192 3.15 Repetition Finder 199 3.16 UNIX Compression 202 3.17 GIF Images 203 3.18 The V.42bis Protocol 204 3.19 Zip and Gzip 205 3.20 ARC and PKZip 206 3.21 ARJ and LHArc 211 3.22 EXE Compressors 212 3.23 CRC 212 3.24 Summary 215 3.25 Data Compression Patents 215 3.26 A Unification 218Chapter 4. Image Compression 221 4.1 Introduction 223 4.2 Approaches to Image Compression 229 4.3 Intuitive Methods 242 4.4 Image Transforms 243 4.5 Test Images 269 4.6 JPEG 273 4.7 JPEG-LS 295 4.8 Progressive Image Compression 302 4.9 JBIG 310 4.10 JBIG2 320 4.11 Simple Images: EIDAC 331 4.12 Vector Quantization 333 4.13 Adaptive Vector Quantization 340 4.14 Block Matching 345 4.15 Block Truncation Coding 349 4.16 Context-Based Methods 355 4.17 FELICS 358 4.18 Progressive FELICS 361 4.19 MLP 365 4.20 PPPM 373 4.21 CALIC 375 4.22 Differential Lossless Compression 378 4.23 DPCM 380 4.24 Context-Tree Weighting 385 4.25 Block Decomposition 386 4.26 Binary Tree Predictive Coding 391 4.27 Quadtrees 397 4.28 Quadrisection 410 4.29 Space-Filling Curves 417 4.30 Hilbert Scan and VQ 418 4.31 Finite Automata Methods 421 4.32 Iterated Function Systems 438 4.33 Cell Encoding 455 Chapter 5. Wavelet Methods 457 5.1 Fourier Transform 457 5.2 The Frequency Domain 458 5.3 The Uncertainty Principle 462 5.4 Fourier Image Compression 465 5.5 The CWT and Its Inverse 467 5.6 The Haar Transform 474 5.7 Filter Banks 492 5.8 The DWT 502 5.9 Multiresolution Decomposition 515 5.10 Various Image Decompositions 516 5.11 The Lifting Scheme 523 5.12 The IWT 534 5.13 The Laplacian Pyramid 537 5.14 SPIHT 540 5.15 CREW 552 5.16 EZW 553 5.17 DjVu 558 5.18 WSQ, Fingerprint Compression 561 5.19 JPEG 2000 567 Chapter 6. Video Compression 581 6.1 Analog Video 581 6.2 Composite and Components Video 587 6.3 Digital Video 588 6.4 Video Compression 593 6.5 MPEG 605 6.6 H.261 627
Chapter 7. Audio Compression 631 7.1 Sound 632 7.2 Digital Audio 636 7.3 The Human Auditory System 638 7.4 Mu-Law and A-Law Companding 644 7.5 ADPCM Audio Compression 650 7.6 MPEG-1 Audio Layers 652 Chapter 8. Other Methods 681 8.1 The Burrows-Wheeler Method 682 8.2 Symbol Ranking 687 8.3 ACB 691 8.4 Sort-Based Context Similarity 698 8.5 Sparse Strings 704 8.6 Word-Based Text Compression 715 8.7 Textual Image Compression 720 8.8 Dynamic Markov Coding 726 8.9 FHM Curve Compression 733 8.10 Sequitur 737 8.11 Triangle Mesh Compression: Edgebreaker 743 Bibliography 755 Glossary 773 Joining the Data Compression Community 801 Index 803 Colophon
Contents. (60K) Appendix A. The ASCII Code (128K) Appendix B. Basics of Probability (176K) Appendix C. Curves That Fill Space (192K) Appendix D. Data Structures (184K) Appendix E. Error Correcting Codes 160K) Appendix F. Finite State Automata (128K) Appendix G. Gallery of Images (264K) Appendix H. Human Visual System (272K) Appendix I. Introductory Mathematics (260K) Glossary (196K) Answers to Exercises (568K) Index (44K)
This section contains extra material added by the author from time to time. These documents are intended to to add new material, and to shed new light on material already included in the book.
1. The concept of correlation is basic to image and audio compression. This concept is easy to grasp intuitively, but this document (PDF, 8 pages, 323K) treats it quantitatively.
2. Image compression is achieved by decorrelating the pixels of an image. In statistics, one is normally concerned with calculating the correlation between random variables, but rarely with decorrelations. However, there is a little-known technique, the Mahalanobis transformation, that is used to decorrelate random variable. It is described here (PDF, 6 pages, 332K).
3. Quadtrees and octrees are discussed in Section 4.27 of the book. An efficient algorithm by George Buyanovsky to compress these trees as well as any N-tree structure is described here (PDF, 6 pages, 182K).
4. Run-length encoding (RLE) is a simple approach to compression, but it is not very efficient and is consequently rarely use. Section 2.13 shows how RLE combined with variable-length codes is used in facsimile compression. The document found here (PDF, 7 pages, 9Mb) describes another application of RLE, to the compression of PK fonts. This method exploits the special features of font bitmaps and makes only a minimal use of variable-length codes.
Last Updated 3 November, 2008.