Introduction to Data Compression
Regular price
33.000 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Table of contentsvii
- Prefacexvii
- Audiencexvii
- Course Usexviii
- Approachxviii
- Learning from This Bookxix
- Content and Organizationxix
- A Personal Viewxx
- Acknowledgmentsxxi
- 1 Introduction1
- 1.1 Compression Techniques3
- 1.1.1 Lossless Compression4
- 1.1.2 Lossy Compression5
- 1.1.3 Measures of Performance5
- 1.2 Modeling and Coding6
- 1.3 Summary10
- 1.4 Projects and Problems11
- 2 Mathematical Preliminaries for Lossless Compression13
- 2.1 Overview13
- 2.2 A Brief Introduction to Information Theory13
- 2.2.1 Derivation of Average Information18
- 2.3 Models23
- 2.3.1 Physical Models23
- 2.3.2 Probability Models23
- 2.3.3 Markov Models24
- 2.3.4 Composite Source Model27
- 2.4 Coding27
- 2.4.1 Uniquely Decodable Codes28
- 2.4.2 Prefix Codes31
- 2.4.3 The Kraft-McMillan Inequality32
- 2.5 Algorithmic Information Theory35
- 2.6 Minimum Description Length Principle36
- 2.7 Summary37
- 2.8 Projects and Problems38
- 3 Huffman Coding41
- 3.1 Overview41
- 3.2 The Huffman Coding Algorithm41
- 3.2.1 Minimum Variance Huffman Codes46
- 3.2.2 Optimality of Huffman Codes48
- 3.2.3 Length of Huffman Codes49
- 3.2.4 Extended Huffman Codes51
- 3.3 Nonbinary Huffman Codes55
- 3.4 Adaptive Huffman Coding58
- 3.4.1 Update Procedure59
- 3.4.2 Encoding Procedure62
- 3.4.3 Decoding Procedure63
- 3.5 Golomb Codes65
- 3.6 Rice Codes67
- 3.6.1 CCSDS Recommendation for Lossless Compression67
- 3.7 Tunstall Codes69
- 3.8 Applications of Huffman Coding72
- 3.8.1 Lossless Image Compression72
- 3.8.2 Text Compression74
- 3.8.3 Audio Compression75
- 3.9 Summary77
- 3.10 Projects and Problems77
- 4 Arithmetic Coding81
- 4.1 Overview81
- 4.2 Introduction81
- 4.3 Coding a Sequence83
- 4.3.1 Generating a Tag84
- 4.3.2 Deciphering the Tag91
- 4.4 Generating a Binary Code92
- 4.4.1 Uniqueness and Ef f iciency of the Arithmetic Code93
- 4.4.2 Algorithm Implementation96
- 4.4.3 Integer Implementation102
- 4.5 Comparison of Huffman and Arithmetic Coding109
- 4.6 Adaptive Arithmetic Coding112
- 4.7 Applications112
- 4.8 Summary113
- 4.9 Projects and Problems114
- 5 Dictionary Techniques117
- 5.1 Overview117
- 5.2 Introduction117
- 5.3 Static Dictionary118
- 5.3.1 Digram Coding119
- 5.4 Adaptive Dictionary121
- 5.4.1 The LZ77 Approach121
- 5.4.2 The LZ78 Approach125
- 5.5 Applications133
- 5.5.1 File Compression„UNIX133
- 5.5.2 Image Compression„The Graphics Interchange Format (GIF)133
- 5.5.3 Image Compression„Portable Network Graphics (PNG)134
- 5.5.4 Compression over Modems„V.42 bis136
- 5.6 Summary138
- 5.7 Projects and Problems139
- 6 Context-Based Compression141
- 6.1 Overview141
- 6.2 Introduction141
- 6.3 Prediction with Partial Match (ppm)143
- 6.3.1 The Basic Algorithm143
- 6.3.2 The Escape Symbol149
- 6.3.3 Length of Context150
- 6.3.4 The Exclusion Principle151
- 6.4 The Burrows-Wheeler Transform152
- 6.4.1 Move-to-Front Coding156
- 6.5 Associative Coder of Buyanovsky (ACB)157
- 6.6 Dynamic Markov Compression158
- 6.7 Summary160
- 6.8 Projects and Problems161
- 7 Lossless Image Compression163
- 7.1 Overview163
- 7.2 Introduction163
- 7.2.1 The Old JPEG Standard164
- 7.3 CALIC166
- 7.4 JPEG-LS170
- 7.5 Multiresolution Approaches172
- 7.5.1 Progressive Image Transmission173
- 7.6 Facsimile Encoding178
- 7.6.1 Run-Length Coding179
- 7.6.2 CCITT Group 3 and 4„Recommendations T.4 and T.6180
- 7.6.3 JBIG183
- 7.6.4 JBIG2„T.88189
- 7.7 MRC„T.44190
- 7.8 Summary193
- 7.9 Projects and Problems193
- 8 Mathematical Preliminaries for Lossy Coding195
- 8.1 Overview195
- 8.2 Introduction195
- 8.3 Distortion Criteria197
- 8.3.1 The Human Visual System199
- 8.3.2 Auditory Perception200
- 8.4 Information Theory Revisited201
- 8.4.1 Conditional Entropy202
- 8.4.2 Average Mutual Information204
- 8.4.3 Differential Entropy205
- 8.5 Rate Distortion Theory208
- 8.6 Models215
- 8.6.1 Probability Models216
- 8.6.2 Linear System Models218
- 8.6.3 Physical Models223
- 8.7 Summary224
- 8.8 Projects and Problems224
- 9 Scalar Quantization227
- 9.1 Overview227
- 9.2 Introduction227
- 9.3 The Quantization Problem228
- 9.4 Uniform Quantizer233
- 9.5 Adaptive Quantization244
- 9.5.1 Forward Adaptive Quantization244
- 9.5.2 Backward Adaptive Quantization246
- 9.6 Nonuniform Quantization253
- 9.6.1 pdf-Optimized Quantization253
- 9.6.2 Companded Quantization257
- 9.7 Entropy-Coded Quantization264
- 9.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs265
- 9.7.2 Entropy-Constrained Quantization265
- 9.7.3 High-Rate Optimum Quantization266
- 9.8 Summary269
- 9.9 Projects and Problems270
- 10 Vector Quantization273
- 10.1 Overview273
- 10.2 Introduction273
- 10.3 Advantages of Vector Quantization over Scalar Quantization276
- 10.4 The Linde-Buzo-Gray Algorithm282
- 10.4.1 Initializing the LBG Algorithm287
- 10.4.2 The Empty Cell Problem294
- 10.4.3 Use of LBG for Image Compression294
- 10.5 Tree-Structured Vector Quantizers299
- 10.5.1 Design of Tree-Structured Vector Quantizers302
- 10.5.2 Pruned Tree-Structured Vector Quantizers303
- 10.6 Structured Vector Quantizers303
- 10.6.1 Pyramid Vector Quantization305
- 10.6.2 Polar and Spherical Vector Quantizers306
- 10.6.3 Lattice Vector Quantizers307
- 10.7 Variations on the Theme311
- 10.7.1 Gain-Shape Vector Quantization311
- 10.7.2 Mean-Removed Vector Quantization312
- 10.7.3 Classified Vector Quantization313
- 10.7.4 Multistage Vector Quantization313
- 10.7.5 Adaptive Vector Quantization315
- 10.8 Trellis-Coded Quantization316
- 10.9 Summary321
- 10.10 Projects and Problems322
- 11 Differential Encoding325
- 11.1 Overview325
- 11.2 Introduction325
- 11.3 The Basic Algorithm328
- 11.4 Prediction in DPCM332
- 11.5 Adaptive DPCM337
- 11.5.1 Adaptive Quantization in DPCM338
- 11.5.2 Adaptive Prediction in DPCM339
- 11.6 Delta Modulation342
- 11.6.1 Constant Factor Adaptive Delta Modulation (CFDM)343
- 11.6.2 Continuously Variable Slope Delta Modulation345
- 11.7 Speech Coding345
- 11.7.1 G.726347
- 11.8 Image Coding349
- 11.9 Summary351
- 11.10 Projects and Problems352
- 12 Mathematical Preliminaries for Transforms, Subbands, and Wavelets355
- 12.1 Overview355
- 12.2 Introduction355
- 12.3 Vector Spaces356
- 12.3.1 Dot or Inner Product357
- 12.3.2 Vector Space357
- 12.3.3 Subspace359
- 12.3.4 Basis360
- 12.3.5 Inner Product„Formal Definition361
- 12.3.6 Orthogonal and Orthonormal Sets361
- 12.4 Fourier Series362
- 12.5 Fourier Transform365
- 12.5.1 Parseval’s Theorem366
- 12.5.2 Modulation Property366
- 12.5.3 Convolution Theorem367
- 12.6 Linear Systems368
- 12.6.1 Time Invariance368
- 12.6.2 Transfer Function368
- 12.6.3 Impulse Response369
- 12.6.4 Filter371
- 12.7 Sampling372
- 12.7.1 Ideal Sampling„Frequency Domain View373
- 12.7.2 Ideal Sampling„Time Domain View375
- 12.8 Discrete Fourier Transform376
- 12.9 Z-Transform378
- 12.9.1 Tabular Method381
- 12.9.2 Partial Fraction Expansion382
- 12.9.3 Long Division386
- 12.9.4 Z-Transform Properties387
- 12.9.5 Discrete Convolution387
- 12.10 Summary389
- 12.11 Projects and Problems390
- 13 Transform Coding391
- 13.1 Overview391
- 13.2 Introduction391
- 13.3 The Transform396
- 13.4 Transforms of Interest400
- 13.4.1 Karhunen-Loéve Transform401
- 13.4.2 Discrete Cosine Transform402
- 13.4.3 Discrete Sine Transform404
- 13.4.4 Discrete Walsh-Hadamard Transform404
- 13.5 Quantization and Coding of Transform Coefficients407
- 13.6 Application to Image Compression„JPEG410
- 13.6.1 The Transform410
- 13.6.2 Quantization411
- 13.6.3 Coding413
- 13.7 Application to Audio Compression„The MDCT416
- 13.8 Summary419
- 13.9 Projects and Problems421
- 14 Subband Coding423
- 14.1 Overview423
- 14.2 Introduction423
- 14.3 Filters428
- 14.3.1 Some Filters Used in Subband Coding432
- 14.4 The Basic Subband Coding Algorithm436
- 14.4.1 Analysis436
- 14.4.2 Quantization and Coding437
- 14.4.3 Synthesis437
- 14.5 Design of Filter Banks438
- 14.5.1 Downsampling440
- 14.5.2 Upsampling443
- 14.6 Perfect Reconstruction Using Two-Channel Filter Banks444
- 14.6.1 Two-Channel PR Quadrature Mirror Filters447
- 14.6.2 Power Symmetric FIR Filters449
- 14.7 M-Band QMF Filter Banks451
- 14.8 The Polyphase Decomposition454
- 14.9 Bit Allocation459
- 14.10 Application to Speech Coding„G.722461
- 14.11 Application to Audio Coding„MPEG Audio462
- 14.12 Application to Image Compression463
- 14.12.1 Decomposing an Image465
- 14.12.2 Coding the Subbands467
- 14.13 Summary470
- 14.14 Projects and Problems471
- 15 Wavelet-Based Compression473
- 15.1 Overview473
- 15.2 Introduction473
- 15.3 Wavelets476
- 15.4 Multiresolution Analysis and the Scaling Function480
- 15.5 Implementation Using Filters486
- 15.5.1 Scaling and Wavelet Coefficients488
- 15.5.2 Families of Wavelets491
- 15.6 Image Compression494
- 15.7 Embedded Zerotree Coder497
- 15.8 Set Partitioning in Hierarchical Trees505
- 15.9 JPEG 2000512
- 15.10 Summary513
- 15.11 Projects and Problems513
- 16 Audio Coding515
- 16.1 Overview515
- 16.2 Introduction515
- 16.2.1 Spectral Masking517
- 16.2.2 Temporal Masking517
- 16.2.3 Psychoacoustic Model518
- 16.3 MPEG Audio Coding519
- 16.3.1 Layer I Coding520
- 16.3.2 Layer II Coding521
- 16.3.3 Layer III Coding„mp3522
- 16.4 MPEG Advanced Audio Coding527
- 16.4.1 MPEG-2 AAC527
- 16.4.2 MPEG-4 AAC532
- 16.5 Dolby AC3 (Dolby Digital)533
- 16.5.1 Bit Allocation534
- 16.6 Other Standards535
- 16.7 Summary536
- 17 Analysis/Synthesis and Analysis by Synthesis Schemes537
- 17.1 Overview537
- 17.2 Introduction537
- 17.3 Speech Compression539
- 17.3.1 The Channel Vocoder539
- 17.3.2 The Linear Predictive Coder (Government Standard LPC-10)542
- 17.3.3 Code Excited Linear Predicton (CELP)549
- 17.3.4 Sinusoidal Coders552
- 17.3.5 Mixed Excitation Linear Prediction (MELP)555
- 17.4 Wideband Speech Compression„ITU-T G.722.2558
- 17.5 Image Compression559
- 17.5.1 Fractal Compression560
- 17.6 Summary568
- 17.7 Projects and Problems569
- 18 Video Compression571
- 18.1 Overview571
- 18.2 Introduction571
- 18.3 Motion Compensation573
- 18.4 Video Signal Representation576
- 18.5 ITU-T Recommendation H.261582
- 18.5.1 Motion Compensation583
- 18.5.2 The Loop Filter584
- 18.5.3 The Transform586
- 18.5.4 Quantization and Coding586
- 18.5.5 Rate Control588
- 18.6 Model-Based Coding588
- 18.7 Asymmetric Applications590
- 18.8 The MPEG-1 Video Standard591
- 18.9 The MPEG-2 Video Standard„H.262594
- 18.9.1 The Grand Alliance HDTV Proposal597
- 18.10 ITU-T Recommendation H.263598
- 18.10.1 Unrestricted Motion Vector Mode600
- 18.10.2 Syntax-Based Arithmetic Coding Mode600
- 18.10.3 Advanced Prediction Mode600
- 18.10.4 PB-frames and Improved PB- frames Mode600
- 18.10.5 Advanced Intra Coding Mode600
- 18.10.6 Deblocking Filter Mode601
- 18.10.7 Reference Picture Selection Mode601
- 18.10.8 Temporal, SNR, and Spatial Scalability Mode601
- 18.10.9 Reference Picture Resampling601
- 18.10.10 Reduced-Resolution Update Mode602
- 18.10.11 Alternative Inter VLC Mode602
- 18.10.12 Modified Quantization Mode602
- 18.10.13 Enhanced Reference Picture Selection Mode603
- 18.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Coding603
- 18.11.1 Motion-Compensated Prediction604
- 18.11.2 The Transform605
- 18.11.3 Intra Prediction605
- 18.11.4 Quantization606
- 18.11.5 Coding608
- 18.12 MPEG-4 Part 2609
- 18.13 Packet Video610
- 18.14 ATM Networks610
- 18.14.1 Compression Issues in ATM Networks611
- 18.14.2 Compression Algorithms for Packet Video612
- 18.15 Summary613
- 18.16 Projects and Problems614
- A Probability and Random Processes615
- A.1 Probability615
- A.1.1 Frequency of Occurrence615
- A.1.2 A Measure of Belief616
- A.1.3 The Axiomatic Approach618
- A.2 Random Variables620
- A.3 Distribution Functions621
- A.4 Expectation623
- A.4.1 Mean624
- A.4.2 Second Moment625
- A.4.3 Variance625
- A.5 Types of Distribution625
- A.5.1 Uniform Distribution625
- A.5.2 Gaussian Distribution626
- A.5.3 Laplacian Distribution626
- A.5.4 Gamma Distribution626
- A.6 Stochastic Process626
- A.7 Projects and Problems629
- B A Brief Review of Matrix Concepts631
- B.1 A Matrix631
- B.2 Matrix Operations632
- C The Root Lattices637
- Bibliography639
- Index655
Each edition of Introduction to Data Compression has widely been considered the best introduction and reference text on the art and science of data compression, and the third edition continues in this tradition. Data compression techniques and technology are ever-evolving with new applications in image, speech, text, audio, and video. The third edition includes all the cutting edge updates the reader will need during the work day and in class.
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 Introduction to Data Compression, includes lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, scalar and vector quantization. Khalid Sayood provides a working knowledge of data compression, giving the reader the tools to develop a complete and concise compression package upon completion of his book.
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 Introduction to Data Compression, includes lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, scalar and vector quantization. Khalid Sayood provides a working knowledge of data compression, giving the reader the tools to develop a complete and concise compression package upon completion of his book.
*New content added on the topic of audio compression including a description of the mp3 algorithm *New video coding standard and new facsimile standard explained *Completely explains established and emerging standards in depth including JPEG 2000, JPEG-LS, MPEG-2, Group 3 and 4 faxes, JBIG 2, ADPCM, LPC, CELP, and MELP *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