Introduction to Data Compression

Editor Board

Dedication

Preface

1 Audience

2 Course Use

3 Approach

4 Learning from This Book

5 Content and Organization

6 A Personal View

Acknowledgments

Introduction

1.1 Compression Techniques

1.2 Modeling and Coding

1.3 Summary

1.4 Projects and Problems

References

Mathematical Preliminaries for Lossless Compression

2.1 Overview

2.2 A Brief Introduction to Information Theory

2.3 Models

2.4 Coding

2.5 Algorithmic Information Theory

2.6 Minimum Description Length Principle

2.7 Summary

2.8 Projects and Problems

References

Huffman Coding

3.1 Overview

3.2 The Huffman Coding Algorithm

3.3 Nonbinary Huffman Codes

3.4 Adaptive Huffman Coding

3.5 Golomb Codes

3.6 Rice Codes

3.7 Tunstall Codes

3.8 Applications of Huffman Coding

3.9 Summary

Further Reading

3.10 Projects and Problems

References

Arithmetic Coding

4.1 Overview

4.2 Introduction

4.3 Coding a Sequence

4.4 Generating a Binary Code

4.5 Adaptive Arithmetic Coding

4.6 Binary Arithmetic Coding

4.7 Comparison of Huffman and Arithmetic Coding

4.8 Applications

4.9 Summary

4.10 Projects and Problems

References

Dictionary Techniques

5.1 Overview

5.2 Introduction

5.3 Static Dictionary

5.4 Adaptive Dictionary

5.5 Applications

5.6 Beyond Compression—Lempel-Ziv Complexity

5.7 Summary

5.8 Projects and Problems

References

Context-Based Compression

6.1 Overview

6.2 Introduction

6.3 Prediction with Partial Match (ppm)

6.4 The Burrows-Wheeler Transform

6.5 Associative Coder of Buyanovsky (ACB)

6.6 Dynamic Markov Compression

6.7 Summary

6.8 Projects and Problems

References

Lossless Image Compression

7.1 Overview

7.2 Introduction

7.3 CALIC

7.4 JPEG-LS

7.5 Prediction Using Conditional Averages

7.6 Multiresolution Approaches

7.7 Facsimile Encoding

7.8 MRC–T.44

7.9 Summary

7.10 Projects and Problems

References

Mathematical Preliminaries for Lossy Coding

8.1 Overview

8.2 Introduction

8.3 Distortion Criteria

8.4 Information Theory Revisited

8.5 Rate Distortion Theory

8.6 Models

8.7 Summary

8.8 Projects and Problems

References

Scalar Quantization

9.1 Overview

9.2 Introduction

9.3 The Quantization Problem

9.4 Uniform Quantizer

9.5 Adaptive Quantization

9.6 Nonuniform Quantization

9.7 Entropy-Coded Quantization

9.8 Summary

9.9 Projects and Problems

References

Vector Quantization

10.1 Overview

10.2 Introduction

10.3 Advantages of Vector Quantization over Scalar Quantization

10.4 The Linde-Buzo-Gray Algorithm

10.5 Tree-Structured Vector Quantizers

10.6 Structured Vector Quantizers

10.7 Variations on the Theme

10.8 Trellis-Coded Quantization

10.9 Summary

Further Reading

10.10 Projects and Problems

References

Differential Encoding

11.1 Overview

11.2 Introduction

11.3 The Basic Algorithm

11.4 Prediction in DPCM

11.5 Adaptive DPCM

11.6 Delta Modulation

11.7 Speech Coding

11.8 Image Coding

11.9 Summary

11.10 Projects and Problems

References

Mathematical Preliminaries for Transforms, Subbands, and Wavelets

12.1 Overview

12.2 Introduction

12.3 Vector Spaces

12.4 Fourier Series

12.5 Fourier Transform

12.6 Linear Systems

12.7 Sampling

12.8 Discrete Fourier Transform

12.9 Z-Transform

12.10 Summary

12.11 Projects and Problems

References

Transform Coding

13.1 Overview

13.2 Introduction

13.3 The Transform

13.4 Transforms of Interest

13.5 Quantization and Coding of Transform Coefficients

13.6 Application to Image Compression– JPEG

13.7 Application to Audio Compression–The MDCT

13.8 Summary

13.9 Projects and Problems

References

Subband Coding

14.1 Overview

14.2 Introduction

14.3 Filters

14.4 The Basic Subband Coding Algorithm

14.5 Design of Filter Banks

14.6 Perfect Reconstruction Using Two-Channel Filter Banks

14.7 M-Band QMF Filter Banks

14.8 The Polyphase Decomposition

14.9 Bit Allocation

14.10 Application to Speech Coding—G.722

14.11 Application to Audio Coding—MPEG Audio

14.12 Application to Image Compression

14.13 Summary

14.14 Projects and Problems

References

Wavelets

15.1 Overview

15.2 Introduction

15.3 Wavelets

15.4 Multiresolution Analysis and the Scaling Function

15.5 Implementation Using Filters

15.6 Biorthogonal Wavelets

15.7 Lifting

15.8 Summary

Further Reading

15.9 Projects and Problems

References

Wavelet-Based Image Compression

16.1 Overview

16.2 Introduction

16.3 Embedded Zerotree Coder

16.4 Set Partitioning in Hierarchical Trees

16.5 JPEG 2000

16.6 Summary

16.7 Projects and Problems

References

Audio Coding

17.1 Overview

17.2 Introduction

17.3 MPEG Audio Coding

17.4 MPEG Advanced Audio Coding

17.5 Dolby AC-3 (Dolby Digital)

17.6 Other Standards

17.7 Summary

References

Analysis/Synthesis and Analysis by Synthesis Schemes

18.1 Overview

18.2 Introduction

18.3 Speech Compression

18.4 Wideband Speech Compression—ITU-T G.722.2

18.5 Coding of Speech for Internet Applications

18.6 Image Compression

18.7 Summary

18.8 Projects and Problems

References

Video Compression

19.1 Overview

19.2 Introduction

19.3 Motion Compensation

19.4 Video Signal Representation

19.5 ITU-T Recommendation H.261

19.6 Model-Based Coding

19.7 Asymmetric Applications

19.8 The MPEG-1 Video Standard

19.9 The MPEG-2 Video Standard—H.262

19.10 ITU-T Recommendation H.263

19.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Coding

19.12 MPEG-4 Part 2

19.13 Packet Video

19.14 Summary

19.15 Projects and Problems

References

Appendix A. Probability and Random Processes

A.1 Probability

A.2 Random Variables

A.3 Distribution Functions

A.4 Expectation

A.5 Types of Distribution

A.6 Stochastic Process

A.7 Projects and Problems

References

Appendix B. A Brief Review of Matrix Concepts

B.1 A Matrix

B.2 Matrix Operations

References

Appendix C. The Root Lattices

References

Bibliography

Index

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

Professionals, software and hardware engineers, students; digital libraries, multimedia