You are previewing Introduction to Data Compression, 4th Edition.
O'Reilly logo
Introduction to Data Compression, 4th Edition

Book Description

Each edition of Introduction to Data Compression has widely been considered the best introduction and reference text on the art and science of data compression, and the fourth edition continues in this tradition. Data compression techniques and technology are ever-evolving with new applications in image, speech, text, audio, and video. The fourth edition includes all the cutting edge updates the reader will need during the work day and in class.

Khalid Sayood provides an extensive introduction to the theory underlying today’s compression techniques with detailed instruction for their applications using several examples to explain the concepts. Encompassing the entire field of data compression, Introduction to Data Compression includes lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, scalar and vector quantization. Khalid Sayood provides a working knowledge of data compression, giving the reader the tools to develop a complete and concise compression package upon completion of his book.

  • New content added to include a more detailed description of the JPEG 2000 standard
  • New content includes speech coding for internet applications
  • Explains established and emerging standards in depth including JPEG 2000, JPEG-LS, MPEG-2, H.264, JBIG 2, ADPCM, LPC, CELP, MELP, and iLBC
  • Source code provided via companion web site that gives readers the opportunity to build their own algorithms, choose and implement techniques in their own applications

Table of Contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Editor Board
  5. Copyright
  6. Dedication
  7. Preface
    1. 1 Audience
    2. 2 Course Use
    3. 3 Approach
    4. 4 Learning from This Book
    5. 5 Content and Organization
    6. 6 A Personal View
    7. Acknowledgments
  8. Introduction
    1. 1.1 Compression Techniques
    2. 1.2 Modeling and Coding
    3. 1.3 Summary
    4. 1.4 Projects and Problems
    5. References
  9. Mathematical Preliminaries for Lossless Compression
    1. 2.1 Overview
    2. 2.2 A Brief Introduction to Information Theory
    3. 2.3 Models
    4. 2.4 Coding
    5. 2.5 Algorithmic Information Theory
    6. 2.6 Minimum Description Length Principle
    7. 2.7 Summary
    8. 2.8 Projects and Problems
    9. References
  10. Huffman Coding
    1. 3.1 Overview
    2. 3.2 The Huffman Coding Algorithm
    3. 3.3 Nonbinary Huffman Codes
    4. 3.4 Adaptive Huffman Coding
    5. 3.5 Golomb Codes
    6. 3.6 Rice Codes
    7. 3.7 Tunstall Codes
    8. 3.8 Applications of Huffman Coding
    9. 3.9 Summary
    10. Further Reading
    11. 3.10 Projects and Problems
    12. References
  11. Arithmetic Coding
    1. 4.1 Overview
    2. 4.2 Introduction
    3. 4.3 Coding a Sequence
    4. 4.4 Generating a Binary Code
    5. 4.5 Adaptive Arithmetic Coding
    6. 4.6 Binary Arithmetic Coding
    7. 4.7 Comparison of Huffman and Arithmetic Coding
    8. 4.8 Applications
    9. 4.9 Summary
    10. 4.10 Projects and Problems
    11. References
  12. Dictionary Techniques
    1. 5.1 Overview
    2. 5.2 Introduction
    3. 5.3 Static Dictionary
    4. 5.4 Adaptive Dictionary
    5. 5.5 Applications
    6. 5.6 Beyond Compression—Lempel-Ziv Complexity
    7. 5.7 Summary
    8. 5.8 Projects and Problems
    9. References
  13. Context-Based Compression
    1. 6.1 Overview
    2. 6.2 Introduction
    3. 6.3 Prediction with Partial Match (ppm)
    4. 6.4 The Burrows-Wheeler Transform
    5. 6.5 Associative Coder of Buyanovsky (ACB)
    6. 6.6 Dynamic Markov Compression
    7. 6.7 Summary
    8. 6.8 Projects and Problems
    9. References
  14. Lossless Image Compression
    1. 7.1 Overview
    2. 7.2 Introduction
    3. 7.3 CALIC
    4. 7.4 JPEG-LS
    5. 7.5 Prediction Using Conditional Averages
    6. 7.6 Multiresolution Approaches
    7. 7.7 Facsimile Encoding
    8. 7.8 MRC–T.44
    9. 7.9 Summary
    10. 7.10 Projects and Problems
    11. References
  15. Mathematical Preliminaries for Lossy Coding
    1. 8.1 Overview
    2. 8.2 Introduction
    3. 8.3 Distortion Criteria
    4. 8.4 Information Theory Revisited
    5. 8.5 Rate Distortion Theory
    6. 8.6 Models
    7. 8.7 Summary
    8. 8.8 Projects and Problems
    9. References
  16. Scalar Quantization
    1. 9.1 Overview
    2. 9.2 Introduction
    3. 9.3 The Quantization Problem
    4. 9.4 Uniform Quantizer
    5. 9.5 Adaptive Quantization
    6. 9.6 Nonuniform Quantization
    7. 9.7 Entropy-Coded Quantization
    8. 9.8 Summary
    9. 9.9 Projects and Problems
    10. References
  17. Vector Quantization
    1. 10.1 Overview
    2. 10.2 Introduction
    3. 10.3 Advantages of Vector Quantization over Scalar Quantization
    4. 10.4 The Linde-Buzo-Gray Algorithm
    5. 10.5 Tree-Structured Vector Quantizers
    6. 10.6 Structured Vector Quantizers
    7. 10.7 Variations on the Theme
    8. 10.8 Trellis-Coded Quantization
    9. 10.9 Summary
    10. Further Reading
    11. 10.10 Projects and Problems
    12. References
  18. Differential Encoding
    1. 11.1 Overview
    2. 11.2 Introduction
    3. 11.3 The Basic Algorithm
    4. 11.4 Prediction in DPCM
    5. 11.5 Adaptive DPCM
    6. 11.6 Delta Modulation
    7. 11.7 Speech Coding
    8. 11.8 Image Coding
    9. 11.9 Summary
    10. 11.10 Projects and Problems
    11. References
  19. Mathematical Preliminaries for Transforms, Subbands, and Wavelets
    1. 12.1 Overview
    2. 12.2 Introduction
    3. 12.3 Vector Spaces
    4. 12.4 Fourier Series
    5. 12.5 Fourier Transform
    6. 12.6 Linear Systems
    7. 12.7 Sampling
    8. 12.8 Discrete Fourier Transform
    9. 12.9 Z-Transform
    10. 12.10 Summary
    11. 12.11 Projects and Problems
    12. References
  20. Transform Coding
    1. 13.1 Overview
    2. 13.2 Introduction
    3. 13.3 The Transform
    4. 13.4 Transforms of Interest
    5. 13.5 Quantization and Coding of Transform Coefficients
    6. 13.6 Application to Image Compression– JPEG
    7. 13.7 Application to Audio Compression–The MDCT
    8. 13.8 Summary
    9. 13.9 Projects and Problems
    10. References
  21. Subband Coding
    1. 14.1 Overview
    2. 14.2 Introduction
    3. 14.3 Filters
    4. 14.4 The Basic Subband Coding Algorithm
    5. 14.5 Design of Filter Banks
    6. 14.6 Perfect Reconstruction Using Two-Channel Filter Banks
    7. 14.7 M-Band QMF Filter Banks
    8. 14.8 The Polyphase Decomposition
    9. 14.9 Bit Allocation
    10. 14.10 Application to Speech Coding—G.722
    11. 14.11 Application to Audio Coding—MPEG Audio
    12. 14.12 Application to Image Compression
    13. 14.13 Summary
    14. 14.14 Projects and Problems
    15. References
  22. Wavelets
    1. 15.1 Overview
    2. 15.2 Introduction
    3. 15.3 Wavelets
    4. 15.4 Multiresolution Analysis and the Scaling Function
    5. 15.5 Implementation Using Filters
    6. 15.6 Biorthogonal Wavelets
    7. 15.7 Lifting
    8. 15.8 Summary
    9. Further Reading
    10. 15.9 Projects and Problems
    11. References
  23. Wavelet-Based Image Compression
    1. 16.1 Overview
    2. 16.2 Introduction
    3. 16.3 Embedded Zerotree Coder
    4. 16.4 Set Partitioning in Hierarchical Trees
    5. 16.5 JPEG 2000
    6. 16.6 Summary
    7. 16.7 Projects and Problems
    8. References
  24. Audio Coding
    1. 17.1 Overview
    2. 17.2 Introduction
    3. 17.3 MPEG Audio Coding
    4. 17.4 MPEG Advanced Audio Coding
    5. 17.5 Dolby AC-3 (Dolby Digital)
    6. 17.6 Other Standards
    7. 17.7 Summary
    8. References
  25. Analysis/Synthesis and Analysis by Synthesis Schemes
    1. 18.1 Overview
    2. 18.2 Introduction
    3. 18.3 Speech Compression
    4. 18.4 Wideband Speech Compression—ITU-T G.722.2
    5. 18.5 Coding of Speech for Internet Applications
    6. 18.6 Image Compression
    7. 18.7 Summary
    8. 18.8 Projects and Problems
    9. References
  26. Video Compression
    1. 19.1 Overview
    2. 19.2 Introduction
    3. 19.3 Motion Compensation
    4. 19.4 Video Signal Representation
    5. 19.5 ITU-T Recommendation H.261
    6. 19.6 Model-Based Coding
    7. 19.7 Asymmetric Applications
    8. 19.8 The MPEG-1 Video Standard
    9. 19.9 The MPEG-2 Video Standard—H.262
    10. 19.10 ITU-T Recommendation H.263
    11. 19.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Coding
    12. 19.12 MPEG-4 Part 2
    13. 19.13 Packet Video
    14. 19.14 Summary
    15. 19.15 Projects and Problems
    16. References
  27. Appendix A. Probability and Random Processes
    1. A.1 Probability
    2. A.2 Random Variables
    3. A.3 Distribution Functions
    4. A.4 Expectation
    5. A.5 Types of Distribution
    6. A.6 Stochastic Process
    7. A.7 Projects and Problems
    8. References
  28. Appendix B. A Brief Review of Matrix Concepts
    1. B.1 A Matrix
    2. B.2 Matrix Operations
    3. References
  29. Appendix C. The Root Lattices
    1. References
  30. Bibliography
  31. Index