Introduction to Data Compression
4th Edition
Table of Contents
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
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.
Key Features
- 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
Readership
Professionals, software and hardware engineers, students; digital libraries, multimedia
Details
- No. of pages:
- 768
- Language:
- English
- Copyright:
- © Morgan Kaufmann 2013
- Published:
- 16th October 2012
- Imprint:
- Morgan Kaufmann
- eBook ISBN:
- 9780124160002
- Hardcover ISBN:
- 9780124157965
Reviews
This text is a truly introductory treatment of the entire field of data compression, including lossless coding, speech coding, and audio coding, which are often neglected in other data compression books. Sayood’s book has the very best tutorial treatment of lossless source coding anywhere, with detailed coverage of Lempel-Ziv, arithmetic, Golumb, and Tunstall coding, in addition to treatments of fixed and adaptive Huffman coding and context-based methods. Additionally, the book contains material on M-band quadrature mirror filter banks, the polyphase decomposition, and wavelets beyond what is normally found in any introductory text. I have used Sayood’s book for a reference and as a text for a course on signal compression. I highly recommend it for adoption. --Jerry D. Gibson, Professor of Electrical and Computer Engineering, University of California, Santa Barbara
Khalid Sayood's book has long been the standard academic reference for those interested in Data Compression. I am very pleased to see his ongoing effort to keep the content timely with the release of the fourth edition this fall. If you want to be well versed in state of the art, ranging from simple lossless coding up to complex video compression, this is the only book I know that will stay with you on every step of the journey. --Mark Nelson, Engineer at Cisco Systems, Inc and Senior Member of IEEE
Ratings and Reviews
About the Authors
Khalid Sayood Author
Khalid Sayood received his BS and MS in Electrical Engineering from the University of Rochester in 1977 and 1979, respectively, and his Ph.D. in Electrical Engineering from Texas A&M University in 1982. In 1982, he joined the University of Nebraska, where he is the Heins Professor of Engineering. His research interests include data compression, joint source channel coding, and bioinformatics.
Affiliations and Expertise
Department of Electrical and Computer Engineering, University of Nebraska, Lincoln, Nebraska, USA