Muutke küpsiste eelistusi

Introduction to Data Compression 5th edition [Pehme köide]

3.89/5 (36 hinnangut Goodreads-ist)
(Department of Electrical and Computer Engineering, University of Nebraska, Lincoln, Nebraska, USA)
Teised raamatud teemal:
Introduction to Data Compression 5th editionSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780128094747.html

Introduction to Data Compression, Fifth Edition, builds on the success of what is widely considered the best introduction and reference text on the art and science of data compression.

Data compression techniques and technology are ever-evolving with new applications in image, speech, text, audio and video. This new edition includes all the latest developments in the field.

Khalid Sayood 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, the book includes lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, and scalar and vector quantization.

The book provides a comprehensive working knowledge of data compression, giving the reader the tools to develop a complete and concise compression package.

  • Explains established and emerging standards in- depth, including JPEG 2000, JPEG-LS, MPEG-2, H.264, JBIG 2, ADPCM, LPC, CELP, MELP, iLBC and the new HEVC standard
  • Includes more coverage of lattices in vector quantization
  • Contains improved and expanded end-of-chapter problems and MATLAB-based examples
  • Source code is provided via a companion website that gives readers the opportunity to build their own algorithms and choose and implement techniques in their own applications

Muu info

The most comprehensive, up-to-date introduction to data compression available
Preface xvii
Chapter 1 Introduction
1(10)
1.1 Compression Techniques
3(3)
1.1.1 Lossless Compression
4(1)
1.1.2 Lossy Compression
4(1)
1.1.3 Measures of Performance
5(1)
1.2 Modeling and Coding
6(3)
1.3 Summary
9(1)
1.4 Projects and Problems
10(1)
Chapter 2 Mathematical Preliminaries for Lossless Compression
11(30)
2.1 Overview
11(1)
2.2 A Brief Introduction to Information Theory
11(11)
2.2.1 Derivation of Average Information *
17(5)
2.3 Models
22(5)
2.3.1 Physical Models
22(1)
2.3.2 Probability Models
23(1)
2.3.3 Markov Models
23(3)
2.3.4 Composite Source Model
26(1)
2.4 Coding
27(7)
2.4.1 Uniquely Decodable Codes
27(3)
2.4.2 Prefix Codes
30(1)
2.4.3 The Kraft-McMillan Inequality *
31(3)
2.5 Algorithmic Information Theory
34(1)
2.6 Minimum Description Length Principle
34(2)
2.7 Summary
36(1)
2.8 Projects and Problems
36(5)
Chapter 3 Huffman Coding
41(48)
3.1 Overview
41(1)
3.2 The Huffman Coding Algorithm
41(24)
3.2.1 Minimum Variance Huffman Codes
45(2)
3.2.2 Canonical Huffman Codes
47(3)
3.2.3 An In-Place Implementation
50(3)
3.2.4 Length-Limited Huffman Codes
53(2)
3.2.5 Optimality of Huffman Codes *
55(1)
3.2.6 Length of Huffman Codes *
56(3)
3.2.7 Extended Huffman Codes *
59(3)
3.2.8 Implementation of Huffman Codes
62(3)
3.3 Nonbinary Huffman Codes *
65(2)
3.4 Adaptive Huffman Coding
67(8)
3.4.1 Update Procedure
68(3)
3.4.2 Encoding Procedure
71(2)
3.4.3 Decoding Procedure
73(2)
3.5 Golomb Codes
75(1)
3.6 Rice Codes
76(2)
3.6.1 CCSDS Recommendation for Lossless Compression
77(1)
3.7 Tunstall Codes
78(3)
3.8 Applications of Huffman Coding
81(4)
3.8.1 Lossless Image Compression
81(2)
3.8.2 Text Compression
83(1)
3.8.3 Audio Compression
84(1)
3.9 Summary
85(1)
3.10 Projects and Problems
86(3)
Chapter 4 Arithmetic Coding
89(42)
4.1 Overview
89(1)
4.2 Introduction
89(2)
4.3 Coding a Sequence
91(9)
4.3.1 Generating a Tag
92(6)
4.3.2 Deciphering the Tag
98(2)
4.4 Generating a Binary Code
100(16)
4.4.1 Uniqueness and Efficiency of the Arithmetic Code
100(3)
4.4.2 Algorithm Implementation
103(5)
4.4.3 Integer Implementation
108(8)
4.5 Adaptive Arithmetic Coding
116(1)
4.6 Binary Arithmetic Coding
117(8)
4.6.1 The QM Coder
122(1)
4.6.2 The MQ Coder
123(1)
4.6.3 The M Coder
124(1)
4.7 Comparison of Huffman and Arithmetic Coding
125(2)
4.8 Applications
127(1)
4.9 Summary
128(1)
4.10 Projects and Problems
129(2)
Chapter 5 Dictionary Techniques
131(34)
5.1 Overview
131(1)
5.2 Introduction
131(1)
5.3 Static Dictionary
132(2)
5.3.1 Digram Coding
133(1)
5.4 Adaptive Dictionary
134(12)
5.4.1 The LZ77 Approach
135(4)
5.4.2 The LZ78 Approach
139(7)
5.5 Grammar-Based Compression
146(7)
5.5.1 SEQUITUR
147(2)
5.5.2 Irreducible Grammars
149(2)
5.5.3 Re-Pair
151(2)
5.6 Applications
153(5)
5.6.1 File Compression---UNIX compress
153(1)
5.6.2 Image Compression---The Graphics Interchange Format (GIF)
154(1)
5.6.3 Image Compression---Portable Network Graphics (PNG)
155(2)
5.6.4 Compression Over Modems---V.42 bis
157(1)
5.7 Beyond Compression---Lempel--Ziv Complexity *
158(2)
5.8 Summary
160(1)
5.9 Projects and Problems
161(4)
Chapter 6 Context-Based Compression
165(22)
6.1 Overview
165(1)
6.2 Introduction
165(2)
6.3 Prediction With Partial Match (ppm)
167(8)
6.3.1 The Basic Algorithm
167(6)
6.3.2 The Escape Symbol
173(1)
6.3.3 Length of Context
174(1)
6.3.4 The Exclusion Principle
174(1)
6.4 The Burrows-Wheeler Transform
175(6)
6.4.1 Move-to-Front Coding
178(2)
6.4.2 Beyond Compression---Short Read Alignment
180(1)
6.5 Associative Coder of Buyanovsky (ACB)
181(1)
6.6 Dynamic Markov Compression
181(2)
6.7 Summary
183(1)
6.8 Projects and Problems
184(3)
Chapter 7 Lossless Image Compression
187(34)
7.1 Overview
187(1)
7.2 Introduction
187(3)
7.2.1 The Old JPEG Standard
188(2)
7.3 CALIC
190(4)
7.4 JPEG-LS
194(2)
7.5 Prediction Using Conditional Averages
196(1)
7.6 Multiresolution Approaches
197(5)
7.6.1 Progressive Image Transmission
198(4)
7.7 Lossless Image Compression Formats
202(2)
7.8 Facsimile Encoding
204(12)
7.8.1 Run-Length Coding
205(1)
7.8.2 CCITT Group 3 and 4---Recommendations T.4 and T.6
205(3)
7.8.3 JBIG
208(6)
7.8.4 JBIG2-T.88
214(2)
7.9 MRC-T.44
216(2)
7.10 Summary
218(1)
7.11 Projects and Problems
219(2)
Chapter 8 Mathematical Preliminaries for Lossy Coding
221(36)
8.1 Overview
221(1)
8.2 Introduction
221(3)
8.3 Distortion Criteria
224(4)
8.3.1 The Human Visual System
227(1)
8.3.2 Auditory Perception
227(1)
8.4 Information Theory Revisited *
228(9)
8.4.1 Conditional Entropy
229(2)
8.4.2 Average Mutual Information
231(2)
8.4.3 Differential Entropy
233(4)
8.5 Rate Distortion Theory *
237(8)
8.6 Models
245(8)
8.6.1 Probability Models
245(2)
8.6.2 Linear System Models
247(5)
8.6.3 Physical Models
252(1)
8.7 Summary
253(1)
8.8 Projects and Problems
253(4)
Chapter 9 Scalar Quantization
257(42)
9.1 Overview
257(1)
9.2 Introduction
257(1)
9.3 The Quantization Problem
258(5)
9.4 Uniform Quantizer
263(10)
9.5 Adaptive Quantization
273(8)
9.5.1 Forward Adaptive Quantization
273(2)
9.5.2 Backward Adaptive Quantization
275(6)
9.6 Nonuniform Quantization
281(11)
9.6.1 pdf-Optimized Quantization
282(3)
9.6.2 Companded Quantization
285(7)
9.7 Entropy-Coded Quantization
292(4)
9.7.1 Entropy Coding of Lloyd--Max Quantizer Outputs
292(1)
9.7.2 Entropy-Constrained Quantization *
293(1)
9.7.3 High-Rate Optimum Quantization *
293(3)
9.8 Summary
296(1)
9.9 Projects and Problems
297(2)
Chapter 10 Vector Quantization
299(52)
10.1 Overview
299(1)
10.2 Introduction
299(3)
10.3 Advantages of Vector Quantization Over Scalar Quantization
302(5)
10.4 The Linde---Buzo--Gray Algorithm
307(16)
10.4.1 Initializing the LBG Algorithm
312(6)
10.4.2 The Empty Cell Problem
318(1)
10.4.3 Use of LBG for Image Compression
319(4)
10.5 Tree-Structured Vector Quantizers
323(4)
10.5.1 Design of Tree-Structured Vector Quantizers
326(1)
10.5.2 Pruned Tree-Structured Vector Quantizers
327(1)
10.6 Structured Vector Quantizers
327(10)
10.6.1 Pyramid Vector Quantization
328(2)
10.6.2 Polar and Spherical Vector Quantizers
330(1)
10.6.3 Lattice Vector Quantizers
330(7)
10.7 Variations on the Theme
337(4)
10.7.1 Gain-Shape Vector Quantization
337(1)
10.7.2 Mean-Removed Vector Quantization
337(1)
10.7.3 Classified Vector Quantization
337(1)
10.7.4 Multistage Vector Quantization
338(2)
10.7.5 Adaptive Vector Quantization
340(1)
10.8 Trellis-Coded Quantization
341(5)
10.9 Summary
346(1)
10.10 Projects and Problems
347(4)
Chapter 11 Differential Encoding
351(28)
11.1 Overview
351(1)
11.2 Introduction
352(2)
11.3 The Basic Algorithm
354(4)
11.4 Prediction in DPCM
358(5)
11.5 Adaptive DPCM
363(4)
11.5.1 Adaptive Quantization in DPCM
364(1)
11.5.2 Adaptive Prediction in DPCM
364(3)
11.6 Delta Modulation
367(4)
11.6.1 Constant Factor Adaptive Delta Modulation (CFDM)
369(1)
11.6.2 Continuously Variable Slope Delta Modulation
370(1)
11.7 Speech Coding
371(4)
11.7.1 G.726
372(3)
11.8 Image Coding
375(1)
11.9 Summary
376(1)
11.10 Projects and Problems
377(2)
Chapter 12 Mathematical Preliminaries for Transforms, Subbands, and Wavelets
379(38)
12.1 Overview
379(1)
12.2 Introduction
379(1)
12.3 Vector Spaces
380(6)
12.3.1 Dot or Inner Product
381(1)
12.3.2 Vector Space
382(1)
12.3.3 Subspace
383(1)
12.3.4 Basis
384(1)
12.3.5 Inner Product---Formal Definition
385(1)
12.3.6 Orthogonal and Orthonormal Sets
385(1)
12.4 Fourier Series
386(2)
12.5 Fourier Transform
388(3)
12.5.1 Parseval's Theorem
390(1)
12.5.2 Modulation Property
390(1)
12.5.3 Convolution Theorem
391(1)
12.6 Linear Systems
391(5)
12.6.1 Time Invariance
392(1)
12.6.2 Transfer Function
392(1)
12.6.3 Impulse Response
393(2)
12.6.4 Filter
395(1)
12.7 Sampling
396(4)
12.7.1 Ideal Sampling---Frequency Domain View
396(2)
12.7.2 Ideal Sampling---Time Domain View
398(2)
12.8 Discrete Fourier Transform
400(2)
12.9 Z-Transform
402(11)
12.9.1 Tabular Method
405(1)
12.9.2 Partial Fraction Expansion
406(4)
12.9.3 Long Division
410(1)
12.9.4 Z-Transform Properties
411(1)
12.9.5 Discrete Convolution
412(1)
12.10 Summary
413(1)
12.11 Projects and Problems
414(3)
Chapter 13 Transform Coding
417(44)
13.1 Overview
417(1)
13.2 Introduction
418(4)
13.3 The Transform
422(5)
13.4 Transforms of Interest
427(6)
13.4.1 Karhunen-Loeve Transform
427(1)
13.4.2 Discrete Cosine Transform
428(2)
13.4.3 Discrete Sine Transform
430(1)
13.4.4 Discrete Walsh-Hadamard Transform
430(3)
13.5 Quantization and Coding of Transform Coefficients
433(7)
13.5.1 Operational Rate-Distortion Bit Allocation
437(3)
13.6 Application to Image Compression---JPEG
440(8)
13.6.1 The Transform
440(1)
13.6.2 Quantization
441(2)
13.6.3 Coding
443(2)
13.6.4 Format---JFIF
445(3)
13.7 JPEG-XT
448(2)
13.8 Overlapped Transforms
450(5)
13.8.1 Application to Audio Compression---the MDCT
451(2)
13.8.2 Application to Image Compression---JPEG-XR
453(2)
13.9 Summary
455(1)
13.10 Projects and Problems
456(5)
Chapter 14 Subband Coding
461(50)
14.1 Overview
461(1)
14.2 Introduction
461(5)
14.3 Filters
466(6)
14.3.1 Some Filters Used in Subband Coding
469(3)
14.4 The Basic Subband Coding Algorithm
472(3)
14.4.1 Analysis
472(1)
14.4.2 Quantization and Coding
473(2)
14.4.3 Synthesis
475(1)
14.5 Design of Filter Banks *
475(6)
14.5.1 Downsampling *
477(2)
14.5.2 Upsampling *
479(2)
14.6 Perfect Reconstruction Using Two-Channel Filter Banks *
481(7)
14.6.1 Two-Channel PR Quadrature Mirror Filters *
483(2)
14.6.2 Power Symmetric FIR Filters *
485(3)
14.7 M-Band QMF Filter Banks *
488(3)
14.8 The Polyphase Decomposition *
491(4)
14.9 Bit Allocation
495(2)
14.10 Application to Speech Coding---G.722
497(2)
14.11 Application to Audio Coding---MPEG Audio
499(1)
14.12 Application to Image Compression
499(7)
14.12.1 Decomposing an Image
502(2)
14.12.2 Coding the Subbands
504(2)
14.13 Summary
506(1)
14.14 Projects and Problems
506(5)
Chapter 15 Wavelets
511(32)
15.1 Overview
511(1)
15.2 Introduction
511(3)
15.3 Wavelets
514(4)
15.4 Multiresolution Analysis and the Scaling Function
518(6)
15.5 Implementation Using Filters
524(9)
15.5.1 Scaling and Wavelet Coefficients
527(3)
15.5.2 Families of Wavelets
530(3)
15.6 Biorthogonal Wavelets
533(4)
15.7 Lifting
537(4)
15.8 Summary
541(1)
15.9 Projects and Problems
542(1)
Chapter 16 Wavelet-Based Image Compression
543(36)
16.1 Overview
543(1)
16.2 Introduction
543(2)
16.3 Embedded Zerotree Coder
545(8)
16.4 Set Partitioning in Hierarchical Trees
553(6)
16.5 JPEG 2000
559(19)
16.5.1 Color Component Transform
560(1)
16.5.2 Tiling
561(1)
16.5.3 Wavelet Transform
562(1)
16.5.4 Quantization
562(1)
16.5.5 Tier I Coding
563(7)
16.5.6 Tier II Coding
570(2)
16.5.7 JPEG 2000 Bitstream
572(6)
16.6 Summary
578(1)
16.7 Projects and Problems
578(1)
Chapter 17 Audio Coding
579(24)
17.1 Overview
579(1)
17.2 Introduction
579(4)
17.2.1 Spectral Masking
580(1)
17.2.2 Temporal Masking
581(1)
17.2.3 Psychoacoustic Model
582(1)
17.3 MPEG Audio Coding
583(8)
17.3.1 Layer I Coding
583(2)
17.3.2 Layer II Coding
585(1)
17.3.3 Layer III Coding---mp3
586(5)
17.4 MPEG Advanced Audio Coding
591(6)
17.4.1 MPEG-2 AAC
591(4)
17.4.2 MPEG-4 AAC
595(1)
17.4.3 High Efficiency Advanced Audio Coding (HE AAC)
596(1)
17.5 Dolby AC3 (Dolby Digital)
597(4)
17.5.1 Bit Allocation
599(2)
17.6 Other Standards
601(1)
17.7 Summary
601(2)
Chapter 18 Analysis/Synthesis and Analysis by Synthesis Schemes
603(42)
18.1 Overview
603(1)
18.2 Introduction
603(2)
18.3 Speech Compression
605(19)
18.3.1 The Channel Vocoder
605(3)
18.3.2 The Linear Predictive Coder (Government Standard LPC-10)
608(7)
18.3.3 Code Excited Linear Prediction (CELP)
615(5)
18.3.4 Sinusoidal Coders
620(1)
18.3.5 Mixed Excitation Linear Prediction (MELP)
621(3)
18.4 Wideband Speech Compression---ITU-T G.722.2
624(2)
18.5 Coding of Speech for Internet Applications
626(9)
18.5.1 iLBC
626(4)
18.5.2 G.729
630(3)
18.5.3 SILK
633(2)
18.6 Image Compression
635(8)
18.6.1 Fractal Compression
636(7)
18.7 Summary
643(1)
18.8 Projects and Problems
644(1)
Chapter 19 Video Compression
645(56)
19.1 Overview
645(1)
19.2 Introduction
645(2)
19.3 Motion Compensation
647(3)
19.4 Video Signal Representation
650(5)
19.5 ITU-T Recommendation H.261
655(6)
19.5.1 Motion Compensation
656(1)
19.5.2 The Loop Filter
657(2)
19.5.3 The Transform
659(1)
19.5.4 Quantization and Coding
659(1)
19.5.5 Rate Control
660(1)
19.6 Model-Based Coding
661(1)
19.7 Asymmetric Applications
662(1)
19.8 The MPEG-1 Video Standard
663(3)
19.9 The MPEG-2 Video Standard---H.262
666(3)
19.9.1 The Grand Alliance HDTV Proposal
669(1)
19.10 ITU-T Recommendation H.263
669(5)
19.10.1 Unrestricted Motion Vector Mode
671(1)
19.10.2 Syntax-Based Arithmetic Coding Mode
671(1)
19.10.3 Advanced Prediction Mode
672(1)
19.10.4 PB-Frames and Improved PB-Frames Mode
672(1)
19.10.5 Advanced Intra Coding Mode
672(1)
19.10.6 Deblocking Filter Mode
672(1)
19.10.7 Reference Picture Selection Mode
672(1)
19.10.8 Temporal, SNR, and Spatial Scalability Mode
673(1)
19.10.9 Reference Picture Resampling
673(1)
19.10.10 Reduced-Resolution Update Mode
673(1)
19.10.11 Alternative Inter VLC Mode
673(1)
19.10.12 Modified Quantization Mode
674(1)
19.10.13 Enhanced Reference Picture Selection Mode
674(1)
19.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Codin
674(6)
19.11.1 Motion-Compensated Prediction
675(1)
19.11.2 The Transform
676(1)
19.11.3 Intra Prediction
676(1)
19.11.4 Quantization
677(2)
19.11.5 Coding
679(1)
19.12 MPEG-4 Part 2
680(1)
19.13 ITU-T Recommendation H.265, MPEG-H Part 2, High Efficiency Video Coding
681(16)
19.13.1 Block Structure
681(3)
19.13.2 Intra Prediction
684(5)
19.13.3 Inter Prediction
689(3)
19.13.4 Transforms
692(2)
19.13.5 Quantization
694(2)
19.13.6 Entropy Coding
696(1)
19.13.7 Slices and Tiles
696(1)
19.14 Packet Video
697(2)
19.14.1 ATM Networks
697(1)
19.14.2 Compression Issues in ATM Networks
697(1)
19.14.3 Compression Algorithms for Packet Video
698(1)
19.15 Summary
699(1)
19.16 Projects and Problems
700(1)
Appendix A Probability and Random Processes
701(14)
A.1 Probability
701(4)
A.1.1 Frequency of Occurrence
701(1)
A.1.2 A Measure of Belief
702(2)
A.1.3 The Axiomatic Approach
704(1)
A.2 Random Variables
705(1)
A.3 Distribution Functions
706(3)
A.4 Expectation
709(2)
A.4.1 Mean
710(1)
A.4.2 Second Moment
710(1)
A.4.3 Variance
710(1)
A.5 Types of Distribution
711(1)
A.5.1 Uniform Distribution
711(1)
A.5.2 Gaussian Distribution
711(1)
A.5.3 Laplacian Distribution
711(1)
A.5.4 Gamma Distribution
712(1)
A.6 Stochastic Process
712(2)
A.7 Projects and Problems
714(1)
Appendix B A Brief Review of Matrix Concepts
715(6)
B.1 A Matrix
715(1)
B.2 Matrix Operations
716(5)
Appendix C The Root Lattices
721(2)
Bibliography 723(12)
Index 735
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.