Introduction to Data Compression

by Khalid Sayood Ph.D.

Overview

The need to efficiently store, manipulate, and transmit large masses of information is growing more rapidly than the capacity of systems to handle it. Engineers and computer scientists need a solid understanding of compression in order to work with the burgeoning variety of data types and increasingly data-intensive applications. This uniquely comprehensive book explains the fundamental theories and techniques of data compression, with the most complete coverage available of both lossy and lossless methods. Rather than simply describing current approaches, Sayood explains the theoretical underpinnings of the algorithms so that readers learn how to model structures in data and design compression packages of their own.

Practitioners, researchers, and students will benefit from the balanced presentation of theoretical material and implementations.

Features:

• Covers both lossy and lossless compression techniques with applications to image, speech, text, audio, and video compression.
• Official compression standards for video, audio, text, and facsimile are discussed in order to illustrate the techniques: includes JPEG, MPEG, G.728, H.261, and Group 3 and 4 fax standards.
• Detailed examples follow each new concept or algorithm.
• Software implementations and sample data sets are available, allowing readers to work through the examples in the book and to experiment with various compression techniques on their own.
• Optional starred sections provide enhanced technical or theoretical discussions.
• Appendices on probability theory, random processes, and matrix concepts are included for reference.

Product Details

ISBN-13:	9780080509259
Publisher:	Elsevier Science
Publication date:	12/15/2005
Series:	The Morgan Kaufmann Series in Multimedia Information and Systems
Sold by:	Barnes & Noble
Format:	eBook
Pages:	704
File size:	29 MB
Note:	This product may take a few minutes to download.

About the 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.

Table of Contents

Introduction to Data Compression
by Khalid Sayood

Preface
1 Introduction
1.1 Compression Techniques
1.1.1 Lossless Compression
1.1.2 Lossy Compression
1.1.3 Measures of Performance
1.2 Modeling and Coding
1.3 Organization of This Book
1.4 Summary
1.5 Projects and Problems

2 Mathematical Preliminaries
2.1 Overview
2.2 A Brief Introduction to Information Theory
2.3 Models
2.3.1 Physical Models
2.3.2 Probability Models
2.3.3. Markov Models
2.3.4 Summary
2.5 Projects and Problems

3 Huffman Coding
3.1 Overview
3.2 "Good" Codes
3.3. The Huffman Coding Algorithm
3.3.1 Minimum Variance Huffman Codes
3.3.2 Length of Huffman Codes
3.3.3 Extended Huffman Codes
3.4 Nonbinary Huffman Codes
3.5 Adaptive Huffman Coding
3.5.1 Update Procedure
3.5.2 Encoding Procedure
3.5.3 Decoding Procedure
3.6 Applications of Huffman Coding
3.6.1 Lossless Image Compression
3.6.2 Text Compression
3.6.3 Audio Compression
3.7 Summary
3.8 Projects and Problems

4 Arithmetic Coding
4.1 Overview
4.2 Introduction
4.3 Coding a Sequence
4.3.1 Generating a Tag
4.3.2 Deciphering the Tag
4.4 Generating a Binary Code
4.4.1 Uniqueness and Efficiency of the Arithmetic Code
4.4.2 Algorithm Implementation
4.4.3 Integer Implementation
4.5 Comparison of Huffman and Arithmetic Coding
4.6 Applications
4.6.1 Bi-Level Image Compression-The JBIG Standard
4.6.2 Image Compression
4.7 Summary
4.8 Projects and Problems

5 Dictionary Techniques
5.1 Overview
5.2 Introduction
5.3 Static Dictionary
5.3.1 Diagram Coding
5.4 Adaptive Dictionary
5.4.1 The LZ77 Approach
5.4.2 The LZ78 Approach
5.5 Applications
5.5.1 File Compression-UNIX COMPRESS
5.5.2 Image Compression-the Graphics Interchange Format (GIF)
5.5.3 Compression over Modems-V.42 bis
5.6 Summary
5.7 Projects and Problems

6 Lossless Image Compression
6.1 Overview
6.2 Introduction
6.3 Facsimile Encoding
6.3.1 Run-Length Coding
6.3.2 CCITT Group 3 and 4-Recommendations T.4 and T.6
6.3.3 Comparison of MH, MR, MMR, and JBIG
6.4 Progressive Image Transmission
6.5 Other Image Compression Approaches
6.5.1 Linear Prediction Models
6.5.2 Context Models
6.5.3 Multiresolution Models
6.5.4 Modeling Prediction Errors
6.6 Summary
6.7 Projects and Problems

7 Mathematical Preliminaries
7.1 Overview
7.2 Introduction
7.3 Distortion Criteria
7.3.1 The Human Visual System
7.3.2 Auditory Perception
7.4 Information Theory Revisted
7.4.1 Conditional Entropy
7.4.2 Average Mutual Information
7.4.3 Differential Entropy
7.5 Rate Distortion Theory
7.6 Models
7.6.1 Probability Models
7.6.2 Linear System Models
7.6.3 Physical Models
7.7 Summary
7.8 Projects and Problems

8 Scalar Quantization
8.1 Overview
8.2 Introduction
8.3 The Quantization Problem
8.4 Uniform Quantizer
8.5 Adaptive Quantization
8.5.1 Forward Adaptive Quantization
8.5.2 Backward Adaptive Quantization
8.6 Nonuniform Quantization
8.6.1 pdf-Optimized Quantization
8.6.2 Companded Quantization
8.7 Entropy-Coded Quantization
8.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs
8.7.2 Entropy-Constrained Quantization
8.7.3 High-Rate Optimum Quantization
8.8 Summary
8.9 Projects and Problems

9 Vector Quantization
9.1 Overview
9.2 Introduction
9.3 Advantages of Vector Quantization over Scalar Quantization
9.4 The Linde-Buzo-Gray Algorithm
9.4.1 Initializing the LBG Algorithm
9.4.2 The Empty Cell Problem
9.4.3 Use of LBG for Image Compression
9.5 Tree-Structured Vector Quantizers
9.5.1 Design of Tree-Structured Vector Quantizers
9.6 Structured Vector Quantizers
9.6.1 Pyramid Vector Quantization
9.6.2 Polar and Spherical Vector Quantizers
9.6.3 Lattice Vector Quantizers
9.7 Variations on the Theme
9.7.1 Gain-Shape Vector Quantization
9.7.2 Mean-Removed Vector Quantization
9.7.3 Classified Vector Quantization
9.7.4 Multistage Vector Quantization
9.7.5 Adaptive Vector Quantization
9.8 Summary
9.9 Projects and Problems

10 Differential Encoding
10.1 Overview
10.2 Introduction
10.3 The Basic Algorithm
10.4 Prediction in DPCM
10.5 Adaptive DPCM (ADPCM)
10.5.1 Adaptive Quantization in DPCM
10.5.2 Adaptive Prediction in DPCM
10.6 Delta Modulation
10.6.1 Constant Factor Adaptive Delta Modulation (CFDM)
10.6.2 Continuously Variable Slope Delta Modulation
10.7 Speech Coding
10.7.1 G.726
10.8 Summary
10.9 Projects and Problems

11 Subband Coding
11.1 Overview
11.2 Introduction
11.3 The Frequency Domain and Filtering
11.3.1 Filters
11.4 The Basic Subband Coding Algorithm
11.4.1 Bit Allocation
11.5 Application to Speech Coding-G.722
11.6 Application to Audio Coding-MPEG Audio
11.7 Application to Image Compression
11.7.1 Decomposing an Image
11.7.2 Coding the Subbands
11.8 Wavelets
11.8.1 Families of Wavelets
11.8.2 Wavelets and Image Compression
11.9 Summary
11.10 Projects and Problems

12 Transform Coding
12.1 Overview
12.2 Introduction
12.3 The Transform
12.4 Transforms of Interest
12.4.1 Karhunen-Loeve Transform
12.4.2 Discrete Cosine Transform
12.4.3 Discrete Sine Transform
12.4.4 Discrete Walsh-Hadamard Transform
12.5 Quantization and Coding of Transform Coefficients
12.6 Application to Image Compression-JPEG
12.6.1 The Transform
12.6.2 Quantization
12.6.3 Coding
12.7 Application to Audio Compression
12.8 Summary
12.9 Projects and Problems

13 Analysis/Synthesis Schemes
13.1 Overview
13.2 Introduction
13.3 Speech Compression
13.3.1 The Channel Vocoder
13.3.2 The Linear Predictive Coder (Gov.Std.LPC-10)
13.3.3 Code Excited Linear Prediction (CELP)
13.3.4 Sinusoidal Coders
13.4 Image Compression
13.4.1 Fractal Compression
13.5 Summary
13.6 Projects and Problems

14 Video Compression
14.1 Overview
14.2 Introduction
14.3 Motion Compensation
14.4 Video Signal Representation
14.5 Algorithms for Videoconferencing and Videophones
14.5.1 ITU_T Recommendation H.261
14.5.2 Model-Based Coding
14.6 Asymmetric Applications
14.6.1 The MPEG Video Standard
14.7 Packet Video
14.7.1 ATM Networks
14.7.2 Compression Issues in ATM Networks
14.7.3 Compression Algorithms for Packet Video
14.8 Summary
14.9 Projects and Problems

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

B A Brief Review of Matrix Concepts
B.1 A Matrix
B.2 Matrix Operations

C Codes for Facsimile Encoding
D The Root Lattices
Bibliography
Index

What People are Saying About This

From the Publisher

The most comprehensive, up-to-date introduction to data compression available

Editorial 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

From the Publisher