Introduction to Data Compression, 4th Edition

Book description

Introduction to Data Compression, Fourth Edition, is a concise and comprehensive guide to the art and science of data compression. This new edition includes all the cutting edge updates the reader will need during the work day and in class. It 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, this book covers lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, scalar and vector quantization. New to this fourth edition is a more detailed description of the JPEG 2000 standard as well as speech coding for internet applications. A source code is also provided via a companion web site that gives readers the opportunity to build their own algorithms, choose and implement techniques in their own applications.

This text will appeal to professionals, software and hardware engineers, students, and anyone interested in digital libraries and multimedia.
  • 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

Product information

  • Title: Introduction to Data Compression, 4th Edition
  • Author(s): Khalid Sayood
  • Release date: October 2012
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780124160002