Introduction to Data Compression
- 2nd Edition - March 23, 2000
- Latest edition
- Author: Khalid Sayood
- Language: English
The second edition of Introduction to Data Compression builds on the features that made the first the logical choice-for practitioners who need a comprehensive guide to compressi… Read more
Purchase options
The second edition of Introduction to Data Compression builds on the features that made the first the logical choice-for practitioners who need a comprehensive guide to compression for all types of multimedia and instructors who want to equip their students with solid foundations in these increasingly important and diverse techniques.This book provides an extensive introduction to the theory underlying today's compression techniques, with detailed, instruction for their application. All of the coverage has been updated to reflect the state of the art in data compression, including both new algorithms and older methods for which new uses are being found.
- Fully updated to cover the most recent lossy and lossless compression techniques, including wavelets, subband coding, predictive lossless techniques, and Huffman coding variants.
- Explains established and emerging standards in depth: JPEG 2000, JPEG-LS, MPEG 2, Group 3 and 4 Faxes, JBIG 2, ADPCM, LPC, CELP, and MELP.
- Includes an new chapter providing the mathematical background required for understanding wavelets and subband coding.
Practitioners who need a comprehensive guide to compression for all types of multimedia and instructors who want to equip their students with solid foundations in these increasingly important and diverse techniques.
Highlights:
- New chapter on Wavelets and their application
to image compression (EZW, SPIHT, JPEG 2000)
- Significantly expanded coverage of subband coding.
- A new mathematical preliminaries chapter which
provides the mathematical backgrund necessary
for the wavelet and new subband coding material.
- New chapter on predictive lossless techniques
including ppm, BWT, CALIC, DMC, JPEG-LS
- Updated treatment of Huffman coding variants
including Tunstall codes, Golomb codes and Rice codes.
- Expanded the treatment of information theory and coding
concepts.
- Increased the number of exercises in almost all chapters.
--------------------------------------------------------------------------------
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 Summary
1.4 Projects and Problems
2 Mathematical Preliminaries for Lossless Compression
Highlights: Expanded the section on Information Theory
Moved introduction to coding from Chapter 3
Added proof of the Kraft-McMillan inequality
Added test for uniquely decodable codes
2.1 Overview
2.2 A Brief Introduction to Information Theory
2.2.1 $\star $ Derivation of Average Information
2.3 Models
2.3.1 Physical Models
2.3.2 Probability Models
2.3.3 Markov Models
Markov Models in Text Compression
2.3.4 Composite Source Model
2.4 Coding
2.4.1 Uniquely Decodable Codes
$\star $ A Test for Unique Decodability
2.4.2 Prefix Codes
2.4.3 $\star $ The Kraft-McMillan Inequality
2.5 Summary
Further Reading
2.6 Projects and Problems
3 Huffman Coding
Highlights: Added Proof of optimality of Huffman codes
Added description and discussions of:
Tunstall Codes
Golomb codes
Rice Codes
Added description of the Space Data Systems Lossless
Compresion Standard
3.1 Overview
3.2 The Huffman Coding Algorithm
3.2.1 Minimum Variance Huffman Codes
3.2.2 $\star $ Optimality of Huffman Codes
3.2.3 $\star $Length of Huffman Codes
3.2.4 $\star $Extended Huffman Codes
3.3 $\star $ Nonbinary Huffman Codes
3.4 Adaptive Huffman Coding
3.4.1 Update Procedure
3.4.2 Encoding Procedure
3.4.3 Decoding Procedure
3.5 Golomb Codes
3.6 Rice Codes
3.6.1 CCSDS Recommendation for Lossless Compression
3.7 Tunstall Codes
3.8 Applications of Huffman Coding
3.8.1 Lossless Image Compression
3.8.2 Text Compression
3.8.3 Audio Compression
3.9 Summary
Further Reading
3.10 Projects and Problems
4 Arithmetic Coding
Highlights: Improved descriptions of the coding procedures
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
Encoder Implementation
Decoder Implementation
4.5 Comparison of Huffman and Arithmetic Coding
4.6 Applications
4.6.1 Bi-Level Image Compression - The JBIG Standard
Lossless Compression
Progressive Transmission
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 Digram Coding
5.4 Adaptive Dictionary
5.4.1 The LZ77 Approach
Variations on the LZ77 theme
5.4.2 The LZ78 Approach
Variations on the LZ78 Theme - The LZW Algorithm
5.5 Applications
5.5.1 File Compression---UNIX \sc Compress
5.5.2 Image Compression---the Graphic Interchange Format (GIF)
5.5.3 Compression Over Modems---V.42 bis
5.6 Summary
Further Reading
5.7 Projects and Problems
6 Predictive Coding
Highlights: This is essentially a new chapter covering some of the latest and currently most popular lossless coding techniques.
These include
CALIC (lossless image compression)
JPEG-LS (lossless image compression)
ppm and its variants
Burrows-Wheeler transform
Dynamic Markov Compression
6.1 Introduction
6.2 Prediction with Partial Match (ppm)
6.2.1 The Basic Algorithm
6.2.2 The Escape Symbol
6.2.3 Length of Context
6.2.4 The Exclusion Principle
6.3 The Burrows-Wheeler Transform
6.3.1 Move-to-Front Coding
6.4 CALIC
6.5 JPEG-LS
6.5.1 ``Current'' Standard
6.5.2 ``New'' Standard
6.6 Multiresolution Approaches
6.6.1 Progressive Image Transmission
6.7 Facsimile Encoding
6.7.1 Run Length Coding
6.7.2 CCITT Group 3 and 4 - Recommendations T.4 and T.6
6.7.3 Comparison of MH, MR, MMR, and JBIG
6.8 Dynamic Markov Compression
6.9 Summary
Further reading
6.10 Projects and Problems
7 Mathematical Preliminaries for Lossy Coding
7.1 Overview
7.2 Introduction
7.3 Distortion Criteria
7.3.1 The Human Visual System
7.3.2 Auditory Perception
7.4 $\star $ Information Theory Revisited
7.4.1 Conditional Entropy
7.4.2 Average Mutual Information
7.4.3 Differential Entropy
7.5 $\star $ Rate Distortion Theory
7.6 Models
7.6.1 Probability Models
7.6.2 Linear System Models
7.6.3 Physical Models
Speech Production
7.7 Summary
Further Reading
7.8 Projects and Problems
8 Scalar Quantization
8.1 Overview
8.2 Introduction
8.3 The Quantization Problem
8.4 Uniform Quantizer
Uniform quantization of a uniformly distributed source
Uniform quantization of non-uniform sources
Mismatch Effects
8.5 Adaptive Quantization
8.5.1 Forward Adaptive Quantization
8.5.2 Backward Adaptive Quantization
8.6 Non-uniform Quantization
8.6.1 PDF Optimized Quantization
Mismatch Effects
8.6.2 Companded Quantization
8.7 Entropy Coded Quantization
8.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs
8.7.2 $\star $ Entropy Constrained Quantization
8.7.3 $\star $ High Rate Optimum Quantization
8.8 Summary
8.9 Projects and Problems
9 Vector Quantization
Highlights: - Added description of Trellis Coded Quantization (TCQ)
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.5.2 Pruned 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 Multi-stage Vector Quantization
9.7.5 Adaptive Vector Quantization
9.8 Trellis Coded Quantization
9.9 Summary
Further Reading
9.10 Projects and Problems
Appendix: Lattices
$D_L$
$A_L$
$E_L$
10 Differential Encoding
Highlights: Added a section on Image Compression using DPCM
10.1 Overview
10.2 Introduction
10.3 The Basic Algorithm
10.4 Prediction in DPCM
10.5 Adaptive DPCM
10.5.1 Adaptive Quantization in DPCM
10.5.2 Adaptive Prediction in DPCM
DPCM with Forward Adaptive Prediction (DPCM-APF)
DPCM with backward adaptive prediction (DPCM-APB)
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
The Quantizer
The Predictor
10.8 Image Coding
10.9 Summary
Further Reading
10.10 Projects and Problems
11 Mathematical Preliminaries for Transforms, Subbands, and Wavelets
Highlights: This is a new chapter which introduces the mathematical background
required to appreciate some of the material in subbnad coding
and wavelets. This is in keeping with the idea of keeping the
book self contained.
11.1 Overview
11.2 Introduction
11.3 Vector Space
Dot or Inner Product
Vector Space
Subspace
Basis
Theorem
Inner Product - Formal Definition
Orthogonal and Orthonormal Sets
11.4 Fourier Series
11.5 Fourier Transform
Parseval's Theorem
Modulation Property
Convolution Theorem
11.6 Linear Systems
Time Invariance
Transfer Function
Impulse Response
Filter
11.7 Sampling
Ideal Sampling - Frequency Domain View
Ideal Sampling - Time Domain View
11.8 Discrete Fourier Transform
11.9 Z - Transform
Z-Transform Properties
Discrete Convolution
11.10 Summary
11.11 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 Subband Coding
Highlights: Almost half of this chapter is new material. The chapter now includes a significant amount of new information about filter design. It introduces the concept of perfect reconstruction and describes various approaches to the design of filters that satisfy the perfect reconstruction requirements. We have also included the latest bit allocation techniques.
13.1 Overview
13.2 Introduction
13.3 Filters
13.3.1 Some Filters Used in Subband Coding
13.4 The Basic Subband Coding Algorithm
Analysis
Quantization and Coding
Synthesis
13.5 $\star $ Design of Filter Banks
13.5.1 $\star $ Downsampling
13.5.2 $\star $ Upsampling
13.6 $\star $ Perfect Reconstruction Using Two-Channel Filter Banks
13.6.1 $\star $ Two Channel PR Quadrature Mirror Filters
13.6.2 $\star $ Power Symmetric FIR Filters
13.7 $\star $ M-Band QMF Filter Banks
13.8 $\star $ The Polyphase Decomposition
13.9 Bit Allocation
13.10 Application to Speech Coding - G.722
13.11 Application to Audio Coding - MPEG Audio
13.12 Application to Image Compression
13.12.1 Decomposing an Image
13.12.2 Coding the Subbands
13.13 Summary
13.14 Projects and Problems
14 Wavelets
Highlights: This is a completely new chapter which introduces the concepts of
wavelets, multiresolution analysis, and wavelet transforms.
Also included in the chapter are the latest wavelet based image
compression techniques (EZW, SPIHT).
14.1 Overview
14.2 Introduction
14.3 Wavelets
14.4 Multiresolution Analysis and the Scaling Function
14.5 Implementation Using Filters
14.5.1 Scaling and Wavelet Coefficients
14.5.2 Families of Wavelets
14.6 Image Compression
14.7 Embedded Zerotree Coder
14.8 Set Partitioning In Hierarchical Trees
First Pass:
Second Pass:
Third Pass:
14.9 JPEG 2000
14.10 Summary
14.11 Projects and Problems
15 Analysis/Synthesis Schemes
Highlights: - Increased coverage of fractal image compression.
15.1 Overview
15.2 Introduction
15.3 Speech Compression
15.3.1 The Channel Vocoder
15.3.2 The Linear Predictive Coder (Gov. Std. LPC-10)
The Voiced/Unvoiced Decision
Estimating the Pitch Period
Obtaining the vocal tract filter
Transmitting the parameters
Synthesis
15.3.3 Code Excited Linear Predicton (CELP)
Federal Standard 1016
CCITT G.728 Speech Standard
15.3.4 Sinusoidal Coders
15.3.5 Mixed Excitation Linear Prediction
15.4 Image Compression
15.4.1 Fractal Compression
15.5 Summary
15.6 Projects and Problems
16 Video Compression
Highlights: - Inclusion of description of compression aspects of MPEG-4 and MPEG-7 standards.
16.1 Overview
16.2 Introduction
16.3 Motion Compensation
16.4 Video Signal Representation
16.5 Algorithms for Videoconferencing and Videophones
16.5.1 ITU-T Recommendation H.261
Motion Compensation
The Loop Filter
The Transform
Quantization and Coding
Rate Control
16.5.2 Model Based Coding
16.6 Asymmetric Applications
16.6.1 The MPEG-1 Video Standard
The MPEG-2 Video Standard
The Grand Alliance HDTV Proposal
16.6.2 MPEG-4
16.6.3 MPEG-7
16.7 Packet Video
16.7.1 ATM Networks
16.7.2 Compression Issues in ATM Networks
16.7.3 Compression Algorithms for Packet Video
16.8 Summary
16.9 Projects and Problems
A Probability and Random Processes
A.1 Probability
Frequency of Occurrence
A Measure of Belief
The axiomatic approach
A.2 Random Variables
A.3 Distribution Functions
A.4 Expectation
Mean
Second Moment
Variance
A.5 Types of Distribution
Uniform Distribution
Gaussian Distribution
Laplacian Distribution
Gamma Distribution
A.6 Stochastic Process
A.7 Exercises
B A Brief Review of Matrix Concepts
Highlights: - Revised most of the material to make it more accessible
B.1 A Matrix
B.2 Matrix Operations
- New chapter on Wavelets and their application
to image compression (EZW, SPIHT, JPEG 2000)
- Significantly expanded coverage of subband coding.
- A new mathematical preliminaries chapter which
provides the mathematical backgrund necessary
for the wavelet and new subband coding material.
- New chapter on predictive lossless techniques
including ppm, BWT, CALIC, DMC, JPEG-LS
- Updated treatment of Huffman coding variants
including Tunstall codes, Golomb codes and Rice codes.
- Expanded the treatment of information theory and coding
concepts.
- Increased the number of exercises in almost all chapters.
--------------------------------------------------------------------------------
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 Summary
1.4 Projects and Problems
2 Mathematical Preliminaries for Lossless Compression
Highlights: Expanded the section on Information Theory
Moved introduction to coding from Chapter 3
Added proof of the Kraft-McMillan inequality
Added test for uniquely decodable codes
2.1 Overview
2.2 A Brief Introduction to Information Theory
2.2.1 $\star $ Derivation of Average Information
2.3 Models
2.3.1 Physical Models
2.3.2 Probability Models
2.3.3 Markov Models
Markov Models in Text Compression
2.3.4 Composite Source Model
2.4 Coding
2.4.1 Uniquely Decodable Codes
$\star $ A Test for Unique Decodability
2.4.2 Prefix Codes
2.4.3 $\star $ The Kraft-McMillan Inequality
2.5 Summary
Further Reading
2.6 Projects and Problems
3 Huffman Coding
Highlights: Added Proof of optimality of Huffman codes
Added description and discussions of:
Tunstall Codes
Golomb codes
Rice Codes
Added description of the Space Data Systems Lossless
Compresion Standard
3.1 Overview
3.2 The Huffman Coding Algorithm
3.2.1 Minimum Variance Huffman Codes
3.2.2 $\star $ Optimality of Huffman Codes
3.2.3 $\star $Length of Huffman Codes
3.2.4 $\star $Extended Huffman Codes
3.3 $\star $ Nonbinary Huffman Codes
3.4 Adaptive Huffman Coding
3.4.1 Update Procedure
3.4.2 Encoding Procedure
3.4.3 Decoding Procedure
3.5 Golomb Codes
3.6 Rice Codes
3.6.1 CCSDS Recommendation for Lossless Compression
3.7 Tunstall Codes
3.8 Applications of Huffman Coding
3.8.1 Lossless Image Compression
3.8.2 Text Compression
3.8.3 Audio Compression
3.9 Summary
Further Reading
3.10 Projects and Problems
4 Arithmetic Coding
Highlights: Improved descriptions of the coding procedures
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
Encoder Implementation
Decoder Implementation
4.5 Comparison of Huffman and Arithmetic Coding
4.6 Applications
4.6.1 Bi-Level Image Compression - The JBIG Standard
Lossless Compression
Progressive Transmission
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 Digram Coding
5.4 Adaptive Dictionary
5.4.1 The LZ77 Approach
Variations on the LZ77 theme
5.4.2 The LZ78 Approach
Variations on the LZ78 Theme - The LZW Algorithm
5.5 Applications
5.5.1 File Compression---UNIX \sc Compress
5.5.2 Image Compression---the Graphic Interchange Format (GIF)
5.5.3 Compression Over Modems---V.42 bis
5.6 Summary
Further Reading
5.7 Projects and Problems
6 Predictive Coding
Highlights: This is essentially a new chapter covering some of the latest and currently most popular lossless coding techniques.
These include
CALIC (lossless image compression)
JPEG-LS (lossless image compression)
ppm and its variants
Burrows-Wheeler transform
Dynamic Markov Compression
6.1 Introduction
6.2 Prediction with Partial Match (ppm)
6.2.1 The Basic Algorithm
6.2.2 The Escape Symbol
6.2.3 Length of Context
6.2.4 The Exclusion Principle
6.3 The Burrows-Wheeler Transform
6.3.1 Move-to-Front Coding
6.4 CALIC
6.5 JPEG-LS
6.5.1 ``Current'' Standard
6.5.2 ``New'' Standard
6.6 Multiresolution Approaches
6.6.1 Progressive Image Transmission
6.7 Facsimile Encoding
6.7.1 Run Length Coding
6.7.2 CCITT Group 3 and 4 - Recommendations T.4 and T.6
6.7.3 Comparison of MH, MR, MMR, and JBIG
6.8 Dynamic Markov Compression
6.9 Summary
Further reading
6.10 Projects and Problems
7 Mathematical Preliminaries for Lossy Coding
7.1 Overview
7.2 Introduction
7.3 Distortion Criteria
7.3.1 The Human Visual System
7.3.2 Auditory Perception
7.4 $\star $ Information Theory Revisited
7.4.1 Conditional Entropy
7.4.2 Average Mutual Information
7.4.3 Differential Entropy
7.5 $\star $ Rate Distortion Theory
7.6 Models
7.6.1 Probability Models
7.6.2 Linear System Models
7.6.3 Physical Models
Speech Production
7.7 Summary
Further Reading
7.8 Projects and Problems
8 Scalar Quantization
8.1 Overview
8.2 Introduction
8.3 The Quantization Problem
8.4 Uniform Quantizer
Uniform quantization of a uniformly distributed source
Uniform quantization of non-uniform sources
Mismatch Effects
8.5 Adaptive Quantization
8.5.1 Forward Adaptive Quantization
8.5.2 Backward Adaptive Quantization
8.6 Non-uniform Quantization
8.6.1 PDF Optimized Quantization
Mismatch Effects
8.6.2 Companded Quantization
8.7 Entropy Coded Quantization
8.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs
8.7.2 $\star $ Entropy Constrained Quantization
8.7.3 $\star $ High Rate Optimum Quantization
8.8 Summary
8.9 Projects and Problems
9 Vector Quantization
Highlights: - Added description of Trellis Coded Quantization (TCQ)
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.5.2 Pruned 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 Multi-stage Vector Quantization
9.7.5 Adaptive Vector Quantization
9.8 Trellis Coded Quantization
9.9 Summary
Further Reading
9.10 Projects and Problems
Appendix: Lattices
$D_L$
$A_L$
$E_L$
10 Differential Encoding
Highlights: Added a section on Image Compression using DPCM
10.1 Overview
10.2 Introduction
10.3 The Basic Algorithm
10.4 Prediction in DPCM
10.5 Adaptive DPCM
10.5.1 Adaptive Quantization in DPCM
10.5.2 Adaptive Prediction in DPCM
DPCM with Forward Adaptive Prediction (DPCM-APF)
DPCM with backward adaptive prediction (DPCM-APB)
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
The Quantizer
The Predictor
10.8 Image Coding
10.9 Summary
Further Reading
10.10 Projects and Problems
11 Mathematical Preliminaries for Transforms, Subbands, and Wavelets
Highlights: This is a new chapter which introduces the mathematical background
required to appreciate some of the material in subbnad coding
and wavelets. This is in keeping with the idea of keeping the
book self contained.
11.1 Overview
11.2 Introduction
11.3 Vector Space
Dot or Inner Product
Vector Space
Subspace
Basis
Theorem
Inner Product - Formal Definition
Orthogonal and Orthonormal Sets
11.4 Fourier Series
11.5 Fourier Transform
Parseval's Theorem
Modulation Property
Convolution Theorem
11.6 Linear Systems
Time Invariance
Transfer Function
Impulse Response
Filter
11.7 Sampling
Ideal Sampling - Frequency Domain View
Ideal Sampling - Time Domain View
11.8 Discrete Fourier Transform
11.9 Z - Transform
Z-Transform Properties
Discrete Convolution
11.10 Summary
11.11 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 Subband Coding
Highlights: Almost half of this chapter is new material. The chapter now includes a significant amount of new information about filter design. It introduces the concept of perfect reconstruction and describes various approaches to the design of filters that satisfy the perfect reconstruction requirements. We have also included the latest bit allocation techniques.
13.1 Overview
13.2 Introduction
13.3 Filters
13.3.1 Some Filters Used in Subband Coding
13.4 The Basic Subband Coding Algorithm
Analysis
Quantization and Coding
Synthesis
13.5 $\star $ Design of Filter Banks
13.5.1 $\star $ Downsampling
13.5.2 $\star $ Upsampling
13.6 $\star $ Perfect Reconstruction Using Two-Channel Filter Banks
13.6.1 $\star $ Two Channel PR Quadrature Mirror Filters
13.6.2 $\star $ Power Symmetric FIR Filters
13.7 $\star $ M-Band QMF Filter Banks
13.8 $\star $ The Polyphase Decomposition
13.9 Bit Allocation
13.10 Application to Speech Coding - G.722
13.11 Application to Audio Coding - MPEG Audio
13.12 Application to Image Compression
13.12.1 Decomposing an Image
13.12.2 Coding the Subbands
13.13 Summary
13.14 Projects and Problems
14 Wavelets
Highlights: This is a completely new chapter which introduces the concepts of
wavelets, multiresolution analysis, and wavelet transforms.
Also included in the chapter are the latest wavelet based image
compression techniques (EZW, SPIHT).
14.1 Overview
14.2 Introduction
14.3 Wavelets
14.4 Multiresolution Analysis and the Scaling Function
14.5 Implementation Using Filters
14.5.1 Scaling and Wavelet Coefficients
14.5.2 Families of Wavelets
14.6 Image Compression
14.7 Embedded Zerotree Coder
14.8 Set Partitioning In Hierarchical Trees
First Pass:
Second Pass:
Third Pass:
14.9 JPEG 2000
14.10 Summary
14.11 Projects and Problems
15 Analysis/Synthesis Schemes
Highlights: - Increased coverage of fractal image compression.
15.1 Overview
15.2 Introduction
15.3 Speech Compression
15.3.1 The Channel Vocoder
15.3.2 The Linear Predictive Coder (Gov. Std. LPC-10)
The Voiced/Unvoiced Decision
Estimating the Pitch Period
Obtaining the vocal tract filter
Transmitting the parameters
Synthesis
15.3.3 Code Excited Linear Predicton (CELP)
Federal Standard 1016
CCITT G.728 Speech Standard
15.3.4 Sinusoidal Coders
15.3.5 Mixed Excitation Linear Prediction
15.4 Image Compression
15.4.1 Fractal Compression
15.5 Summary
15.6 Projects and Problems
16 Video Compression
Highlights: - Inclusion of description of compression aspects of MPEG-4 and MPEG-7 standards.
16.1 Overview
16.2 Introduction
16.3 Motion Compensation
16.4 Video Signal Representation
16.5 Algorithms for Videoconferencing and Videophones
16.5.1 ITU-T Recommendation H.261
Motion Compensation
The Loop Filter
The Transform
Quantization and Coding
Rate Control
16.5.2 Model Based Coding
16.6 Asymmetric Applications
16.6.1 The MPEG-1 Video Standard
The MPEG-2 Video Standard
The Grand Alliance HDTV Proposal
16.6.2 MPEG-4
16.6.3 MPEG-7
16.7 Packet Video
16.7.1 ATM Networks
16.7.2 Compression Issues in ATM Networks
16.7.3 Compression Algorithms for Packet Video
16.8 Summary
16.9 Projects and Problems
A Probability and Random Processes
A.1 Probability
Frequency of Occurrence
A Measure of Belief
The axiomatic approach
A.2 Random Variables
A.3 Distribution Functions
A.4 Expectation
Mean
Second Moment
Variance
A.5 Types of Distribution
Uniform Distribution
Gaussian Distribution
Laplacian Distribution
Gamma Distribution
A.6 Stochastic Process
A.7 Exercises
B A Brief Review of Matrix Concepts
Highlights: - Revised most of the material to make it more accessible
B.1 A Matrix
B.2 Matrix Operations
- Edition: 2
- Latest edition
- Published: March 23, 2000
- Language: English
KS
Khalid Sayood
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