Introduction to Data Compression, 5th Edition

Introduction to Data Compression, 5th Edition

by Khalid Sayood
Released October 2017
Publisher(s): Morgan Kaufmann
ISBN: 9780128097052

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Introduction to Data Compression, Fifth Edition, builds on the success of what is widely considered the best introduction and reference text on the art and science of data compression.

Data compression techniques and technology are ever-evolving with new applications in image, speech, text, audio and video. This new edition includes all the latest developments in the field.

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, the book includes lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, and scalar and vector quantization.

The book provides a comprehensive working knowledge of data compression, giving the reader the tools to develop a complete and concise compression package.

  • Explains established and emerging standards in- depth, including JPEG 2000, JPEG-LS, MPEG-2, H.264, JBIG 2, ADPCM, LPC, CELP, MELP, iLBC and the new HEVC standard
  • Includes more coverage of lattices in vector quantization
  • Contains improved and expanded end-of-chapter problems
  • Source code is provided via a companion website that gives readers the opportunity to build their own algorithms and choose and implement techniques in their own applications

Table of contents

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

Product information

  • Title: Introduction to Data Compression, 5th Edition
  • Author(s): Khalid Sayood
  • Release date: October 2017
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780128097052