Introduction to Data Compression

Author： Sayood, Khalid

Publishers： Elsevier Science

Publishing year： 2012

ISBN： 9780124160002

Subject： [TP 自动化技术、计算机技术]

Language： ENG

Introduction

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 we

Chapter

  • Cover

  • Halftitle

  • Series

  • Titlepage

  • Copyright

  • Dedication

  • Contents

  • Preface

  • 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

  • References

  • Mathematical Preliminaries for Lossless Compression

  • 2.1 Overview

  • 2.2 A Brief Introduction to Information Theory

  • 2.2.1 Derivation of Average Information

  • 2.3 Models

  • 2.3.1 Physical Models

  • 2.3.2 Probability Models

  • 2.3.3 Markov Models

  • 2.3.4 Composite Source Model

  • 2.4 Coding

  • 2.4.1 Uniquely Decodable Codes

  • 2.4.2 Prefix Codes

  • 2.4.3 The Kraft-McMillan Inequality

  • 2.5 Algorithmic Information Theory

  • 2.6 Minimum Description Length Principle

  • 2.7 Summary

  • 2.8 Projects and Problems

  • Huffman Coding

  • 3.1 Overview

  • 3.2 The Huffman Coding Algorithm

  • 3.2.1 Minimum Variance Huffman Codes

  • 3.2.2 Canonical Huffman Codes

  • 3.2.3 Length-Limited Huffman Codes

  • 3.2.4 Optimality of Huffman Codes

  • 3.2.5 Length of Huffman Codes

  • 3.2.6 Extended Huffman Codes

  • 3.2.7 Implementation of Huffman Codes

  • 3.3 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

  • 3.10 Projects and Problems

  • 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 Adaptive Arithmetic Coding

  • 4.6 Binary Arithmetic Coding

  • 4.6.1 The QM Coder

  • 4.6.2 The MQ Coder

  • 4.6.3 The M Coder

  • 4.7 Comparison of Huffman and Arithmetic Coding

  • 4.8 Applications

  • 4.9 Summary

  • 4.10 Projects and Problems

  • 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

  • 5.4.2 The LZ78 Approach

  • 5.5 Applications

  • 5.5.1 File Compression'227UNIX compress

  • 5.5.2 Image Compression'227The Graphics Interchange Format (GIF)

  • 5.5.3 Image Compression'227Portable Network Graphics (PNG)

  • 5.5.4 Compression over Modems'227V.42 bis

  • 5.6 Beyond Compression4pt'0137'0137Lempel-Ziv Complexity

  • 5.7 Summary

  • 5.8 Projects and Problems

  • Context-Based Compression

  • 6.1 Overview

  • 6.2 Introduction

  • 6.3 Prediction with Partial Match (ppm)

  • 6.3.1 The Basic Algorithm

  • 6.3.2 The Escape Symbol

  • 6.3.3 Length of Context

  • 6.3.4 The Exclusion Principle

  • 6.4 The Burrows-Wheeler Transform

  • 6.4.1 Move-to-Front Coding

  • 6.5 Associative Coder of Buyanovsky (ACB)

  • 6.6 Dynamic Markov Compression

  • 6.7 Summary

  • 6.8 Projects and Problems

  • Lossless Image Compression

  • 7.1 Overview

  • 7.2 Introduction

  • 7.2.1 The Old JPEG Standard

  • 7.3 CALIC

  • 7.4 JPEG-LS

  • 7.5 Prediction Using Conditional Averages

  • 7.6 Multiresolution Approaches

  • 7.6.1 Progressive Image Transmission

  • 7.7 Facsimile Encoding

  • 7.7.1 Run-Length Coding

  • 7.7.2 CCITT Group 3 and 4'227Recommendations T.4 and T.6

  • 7.7.3 JBIG

  • 7.7.4 Comparison of MH, MR, MMR, and JBIG

  • 7.7.5 JBIG2'226T.88

  • 7.8 MRC'226T.44

  • 7.9 Summary

  • 7.10 Projects and Problems

  • Mathematical Preliminaries for Lossy Coding

  • 8.1 Overview

  • 8.2 Introduction

  • 8.3 Distortion Criteria

  • 8.3.1 The Human Visual System

  • 8.3.2 Auditory Perception

  • 8.4 Information Theory Revisited

  • 8.4.1 Conditional Entropy

  • 8.4.2 Average Mutual Information

  • 8.4.3 Differential Entropy

  • 8.5 Rate Distortion Theory

  • 8.6 Models

  • 8.6.1 Probability Models

  • 8.6.2 Linear System Models

  • 8.6.3 Physical Models

  • 8.7 Summary

  • 8.8 Projects and Problems

  • Scalar Quantization

  • 9.1 Overview

  • 9.2 Introduction

  • 9.3 The Quantization Problem

  • 9.4 Uniform Quantizer

  • 9.5 Adaptive Quantization

  • 9.5.1 Forward Adaptive Quantization

  • 9.5.2 Backward Adaptive Quantization

  • 9.6 Nonuniform Quantization

  • 9.6.1 pdf-Optimized Quantization

  • 9.6.2 Companded Quantization

  • 9.7 Entropy-Coded Quantization

  • 9.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs

  • 9.7.2 Entropy-Constrained Quantization

  • 9.7.3 High-Rate Optimum Quantization

  • 9.8 Summary

  • 9.9 Projects and Problems

  • 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.4.1 Initializing the LBG Algorithm

  • 10.4.2 The Empty Cell Problem

  • 10.4.3 Use of LBG for Image Compression

  • 10.5 Tree-Structured Vector Quantizers

  • 10.5.1 Design of Tree-Structured Vector Quantizers

  • 10.5.2 Pruned Tree-Structured Vector Quantizers

  • 10.6 Structured Vector Quantizers

  • 10.6.1 Pyramid Vector Quantization

  • 10.6.2 Polar and Spherical Vector Quantizers

  • 10.6.3 Lattice Vector Quantizers

  • 10.7 Variations on the Theme

  • 10.7.1 Gain-Shape Vector Quantization

  • 10.7.2 Mean-Removed Vector Quantization

  • 10.7.3 Classified Vector Quantization

  • 10.7.4 Multistage Vector Quantization

  • 10.7.5 Adaptive Vector Quantization

  • 10.8 Trellis-Coded Quantization

  • 10.9 Summary

  • 10.10 Projects and Problems

  • Differential Encoding

  • 11.1 Overview

  • 11.2 Introduction

  • 11.3 The Basic Algorithm

  • 11.4 Prediction in DPCM

  • 11.5 Adaptive DPCM

  • 11.5.1 Adaptive Quantization in DPCM

  • 11.5.2 Adaptive Prediction in DPCM

  • 11.6 Delta Modulation

  • 11.6.1 Constant Factor Adaptive Delta Modulation (CFDM)

  • 11.6.2 Continuously Variable Slope Delta Modulation

  • 11.7 Speech Coding

  • 11.7.1 G.726

  • 11.8 Image Coding

  • 11.9 Summary

  • 11.10 Projects and Problems

  • Mathematical Preliminaries for Transforms, Subbands, and Wavelets

  • 12.1 Overview

  • 12.2 Introduction

  • 12.3 Vector Spaces

  • 12.3.1 Dot or Inner Product

  • 12.3.2 Vector Space

  • 12.3.3 Subspace

  • 12.3.4 Basis

  • 12.3.5 Inner Product'227Formal Definition

  • 12.3.6 Orthogonal and Orthonormal Sets

  • 12.4 Fourier Series

  • 12.5 Fourier Transform

  • 12.5.1 Parseval's Theorem

  • 12.5.2 Modulation Property

  • 12.5.3 Convolution Theorem

  • 12.6 Linear Systems

  • 12.6.1 Time Invariance

  • 12.6.2 Transfer Function

  • 12.6.3 Impulse Response

  • 12.6.4 Filter

  • 12.7 Sampling

  • 12.7.1 Ideal Sampling'226Frequency Domain View

  • 12.7.2 Ideal Sampling'227Time Domain View

  • 12.8 Discrete Fourier Transform

  • 12.9 Z-Transform

  • 12.9.1 Tabular Method

  • 12.9.2 Partial Fraction Expansion

  • 12.9.3 Long Division

  • 12.9.4 Z-Transform Properties

  • 12.9.5 Discrete Convolution

  • 12.10 Summary

  • 12.11 Projects and Problems

  • Transform Coding

  • 13.1 Overview

  • 13.2 Introduction

  • 13.3 The Transform

  • 13.4 Transforms of Interest

  • 13.4.1 Karhunen-Loéve Transform

  • 13.4.2 Discrete Cosine Transform

  • 13.4.3 Discrete Sine Transform

  • 13.4.4 Discrete Walsh-Hadamard Transform

  • 13.5 Quantization and Coding of Transform Coefficients

  • 13.5.1 Operational Rate-Distortion Bit Allocation

  • 13.6 Application to Image Compression4pt'0137'0137JPEG

  • 13.6.1 The Transform

  • 13.6.2 Quantization

  • 13.6.3 Coding

  • 13.6.4 Format4pt'0137'0137JFIF

  • 13.7 Application to Audio Compression4pt'0137'0137The MDCT

  • 13.8 Summary

  • 13.9 Projects and Problems

  • Subband Coding

  • 14.1 Overview

  • 14.2 Introduction

  • 14.3 Filters

  • 14.3.1 Some Filters Used in Subband Coding

  • 14.4 The Basic Subband Coding Algorithm

  • 14.4.1 Analysis

  • 14.4.2 Quantization and Coding

  • 14.4.3 Synthesis

  • 14.5 Design of Filter Banks

  • 14.5.1 Downsampling

  • 14.5.2 Upsampling

  • 14.6 Perfect Reconstruction Using Two-Channel Filter Banks

  • 14.6.1 Two-Channel PR Quadrature Mirror Filters

  • 14.6.2 Power Symmetric FIR Filters

  • 14.7 M-Band Quadrature Mirror Filter Banks

  • 14.8 The Polyphase Decomposition

  • 14.9 Bit Allocation

  • 14.10 Application to Speech Coding4pt'0137'0137G.722

  • 14.11 Application to Audio Coding4pt'0137'0137MPEG Audio

  • 14.12 Application to Image Compression

  • 14.12.1 Decomposing an Image

  • 14.12.2 Coding the Subbands

  • 14.13 Summary

  • 14.14 Projects and Problems

  • Wavelets

  • 15.1 Overview

  • 15.2 Introduction

  • 15.3 Wavelets

  • 15.4 Multiresolution Analysis and the Scaling Function

  • 15.5 Implementation Using Filters

  • 15.5.1 Scaling and Wavelet Coefficients

  • 15.5.2 Families of Wavelets

  • 15.6 Biorthogonal Wavelets

  • 15.7 Lifting

  • 15.8 Summary

  • 15.9 Projects and Problems

  • 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.5.1 Color Component Transform

  • 16.5.2 Tiling

  • 16.5.3 Wavelet Transform

  • 16.5.4 Quantization

  • 16.5.5 Tier I Coding

  • 16.5.6 Tier II Coding

  • 16.5.7 JPEG 2000 bitstream

  • 16.6 Summary

  • 16.7 Projects and Problems

  • Audio Coding

  • 17.1 Overview

  • 17.2 Introduction

  • 17.2.1 Spectral Masking

  • 17.2.2 Temporal Masking

  • 17.2.3 Psychoacoustic Model

  • 17.3 MPEG Audio Coding

  • 17.3.1 Layer I Coding

  • 17.3.2 Layer II Coding

  • 17.3.3 Layer III Coding'227mp3

  • 17.4 MPEG Advanced Audio Coding

  • 17.4.1 MPEG-2 AAC

  • 17.4.2 MPEG-4 AAC

  • 17.5 Dolby AC-3 (Dolby Digital)

  • 17.5.1 Bit Allocation

  • 17.6 Other Standards

  • 17.7 Summary

  • Analysis/Synthesis and Analysis by Synthesis Schemes

  • 18.1 Overview

  • 18.2 Introduction

  • 18.3 Speech Compression

  • 18.3.1 The Channel Vocoder

  • 18.3.2 The Linear Predictive Coder (Government Standard LPC-10)

  • 18.3.3 Code-Excited Linear Predicton (CELP)

  • 18.3.4 Sinusoidal Coders

  • 18.3.5 Mixed Excitation Linear Prediction (MELP)

  • 18.4 Wideband Speech Compression4pt'0137'0137ITU-T G.722.2

  • 18.5 Coding of Speech for Internet Applications

  • 18.5.1 iLBC

  • 18.5.2 G.729

  • 18.5.3 SILK

  • 18.6 Image Compression

  • 18.7 Summary

  • 18.8 Projects and Problems

  • 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.5.1 Motion Compensation

  • 19.5.2 The Loop Filter

  • 19.5.3 The Transform

  • 19.5.4 Quantization and Coding

  • 19.5.5 Rate Control

  • 19.6 Model-Based Coding

  • 19.7 Asymmetric Applications

  • 19.8 The MPEG-1 Video Standard

  • 19.9 The MPEG-2 Video Standard4pt'0137'0137H.262

  • 19.10 ITU-T Recommendation H.263

  • 19.10.1 Unrestricted Motion Vector Mode

  • 19.10.2 Syntax-Based Arithmetic Coding Mode

  • 19.10.3 Advanced Prediction Mode

  • 19.10.4 PB-Frames and Improved PB-Frames Mode

  • 19.10.5 Advanced Intra Coding Mode

  • 19.10.6 Deblocking Filter Mode

  • 19.10.7 Reference Picture Selection Mode

  • 19.10.8 Temporal, SNR, and Spatial Scalability Mode

  • 19.10.9 Reference Picture Resampling

  • 19.10.10 Reduced-Resolution Update Mode

  • 19.10.11 Alternative Inter VLC Mode

  • 19.10.12 Modified Quantization Mode

  • 19.10.13 Enhanced Reference Picture Selection Mode

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

  • 19.11.1 Motion-Compensated Prediction

  • 19.11.2 The Transform

  • 19.11.3 Intra Prediction

  • 19.11.4 Quantization

  • 19.11.5 Coding

  • 19.12 MPEG-4 Part 2

  • 19.13 Packet Video

  • 19.13.1 ATM Networks

  • 19.13.2 Compression Issues in ATM Networks

  • 19.13.3 Compression Algorithms for Packet Video

  • 19.14 Summary

  • 19.15 Projects and Problems

  • Probability and Random Processes

  • A.1 Probability

  • A.1.1 Frequency of Occurrence

  • A.1.2 A Measure of Belief

  • A.1.3 The Axiomatic Approach

  • A.2 Random Variables

  • A.3 Distribution Functions

  • A.4 Expectation

  • A.4.1 Mean

  • A.4.2 Second Moment

  • A.4.3 Variance

  • A.5 Types of Distribution

  • A.5.1 Uniform Distribution

  • A.5.2 Gaussian Distribution

  • A.5.3 Laplacian Distribution

  • A.5.4 Gamma Distribution

  • A.6 Stochastic Process

  • A.7 Projects and Problems

  • A Brief Review of Matrix Concepts

  • B.1 A Matrix

  • B.2 Matrix Operations

  • The Root Lattices

  • Bibliography

  • Index

  • A

  • B

  • C

  • D

  • E

  • F

  • G

  • H

  • I

  • J

  • K

  • L

  • M

  • N

  • O

  • P

  • Q

  • R

  • S

  • T

  • U

  • V

  • W

  • X

  • Y

  • Z

    • 服务邮箱： whx@cnpiec.com.cn

    联系电话：010-65063046；65001305

    京ICP备09090397号-16 京公网安备 11010502049547号