Data Compression: The Complete Reference.

2nd Edition.

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.)

cover.jpg

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

1-4.jpg

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.

1-4.jpg

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. lena.jpg

Table of Contents

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                           218
DCT.JPEG

Chapter 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 peppers.jpg

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

Auxiliary Material

Because of cost considerations, more than 200 pages of auxiliary material did not go into the book. This material consists of nine appendixes, answers to (almost) all the exercises, and an index (just for the auxiliary material). This material is available here in PDF format, and can be downloaded either as a single file (1.3Mb) or in separate installments

Baboon.jpg


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)

Extra Material

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.