Compression for Multimedia

Providing a thorough theoretical understanding of lossy compression techniques for image, video, speech, and audio compression, this book also covers the key features of each system, as well as practical applications, implementation issues, and design trade-offs. It presents comparisons of multimedia standards in terms of achieving known theoretical limits, whilst common and distinguishing features of the existing standards are explained and related to the background theory. There is detailed coverage of such topics as the H.264 video coding standard, low-complexity code-based vector quantizers, and the Blahut rate-distortion algorithm. Examples based on real multimedia data are also included, plus end-of-chapter problems to test understanding, algorithms that allow the reader to represent speech and audio signals efficiently, and an appendix on the basics of lossless coding. With an excellent balance of theory and practice, this book is ideal for undergraduate and graduate students, and is also a useful reference for practitioners. Half title......Page 3 Title......Page 5 Copyright......Page 6 Dedication......Page 7 Contents......Page 9 Preface......Page 11 1 Introduction......Page 13 2.1 Analog and digital signals......Page 17 2.1.1 Sampling theorem......Page 20 2.1.2 Historical background......Page 22 2.1.3 Aliasing......Page 23 2.2 Scalar quantization......Page 27 2.2.1 Uniform scalar quantization......Page 29 2.2.2 Nonuniform optimal scalar quantization......Page 30 2.2.3 The Lloyd–Max procedure......Page 34 2.3 Vector quantization......Page 35 2.3.1 Optimal vector quantization with a given size of codebook. The Linde–Buzo–Gray procedure......Page 37 2.3.2 Lattice vector quantizers......Page 40 Problems......Page 52 3.1 Rate-distortion function......Page 54 3.2 The Blahut algorithm......Page 61 3.3 The Shannon lower bound and high-resolution approximations......Page 66 3.4 Comparison of quantization procedures......Page 70 3.5 Characteristics of digital speech, audio, image, and video signals......Page 75 Problems......Page 76 4.1 Discrete-time filters......Page 78 4.1.1 Description by means of recurrent equations......Page 79 4.1.2 Description by means of the z-transform......Page 82 4.1.3 Inverse z-transform......Page 84 4.1.4 Frequency function......Page 87 4.2 Linear predictive coding......Page 90 4.2.1 Autocorrelation method......Page 94 4.2.2 Covariance method......Page 95 4.2.3 Algorithms for the solution of the Yule–Walker equations......Page 97 Problems......Page 101 5 Transform coding......Page 103 5.1 Properties of transforms......Page 104 5.2 The Karhunen–Loeve transform......Page 107 5.3 The discrete Fourier transform......Page 110 5.4 The discrete cosine transform......Page 116 Problems......Page 120 6.1 Linear filtering as a linear transform......Page 122 6.2 ``Moving average'' filtering as a linear transform......Page 124 6.3 “Moving difference” filtering as a linear transform......Page 126 6.4 The Haar filter bank......Page 127 6.5 Wavelet transform and wavelet filter bank......Page 133 6.6 Hierarchical wavelet filtering as a linear transform. Properties of wavelet filtering......Page 138 6.8 Application of wavelet filtering to image compression......Page 144 6.9 Embedded zerotree coding and set partitioning in hierarchical trees......Page 147 Problems......Page 150 7 Speech coding: techniques and standards......Page 153 7.1 Direct sample-by-sample quantization: Standard G.711......Page 157 7.2 ADPCM coders: Standards G.726, G.727......Page 159 7.3 Linear prediction analysis-by-synthesis coders (LPC-AS)......Page 164 7.4 LPC vocoders. MELP standard......Page 174 7.5 An algorithm for computing linear spectral parameters......Page 177 Problems......Page 181 8 Image coding standards......Page 183 8.1 Coding of bi-level fax images: JBIG Standard......Page 184 8.2 Coding of halftone images: JPEG Standard......Page 189 8.3 JPEG-LS......Page 198 8.4 Standard JPEG-2000......Page 200 Problems......Page 207 9.1 Motion compensation method......Page 209 9.2 Overview of video-coding standards......Page 212 9.2.1 H.261 and its derivatives......Page 213 9.2.2 MPEG-1, MPEG-2, and MPEG-4......Page 214 9.2.3 Standard H.264......Page 220 Problems......Page 233 10.1 Basics of perceptual coding......Page 235 10.2 Overview of audio standards......Page 239 Problems......Page 248 A.1 Symbol-by-symbol lossless coding......Page 250 A.2 Lossless block coding......Page 253 A.3 Arithmetic coding......Page 255 A.4 Decoding issues......Page 258 A.5 Context lossless coding for sources with memory......Page 261 A.6 QM-coder......Page 263 A.7.2 Golomb code......Page 266 A.7.3 Gallager–vanVoorhis codes......Page 267 A.7.4 Levenstein codes......Page 268 A.8 Binarization......Page 269 A.9 Adaptive coding......Page 270 References......Page 273 Index......Page 277 Half title 3 Title 5 Copyright 6 Dedication 7 Contents 9 Preface 11 1 Introduction 13 2 Analog to digital conversion 17 2.1 Analog and digital signals 17 2.1.1 Sampling theorem 20 2.1.2 Historical background 22 2.1.3 Aliasing 23 2.2 Scalar quantization 27 2.2.1 Uniform scalar quantization 29 2.2.2 Nonuniform optimal scalar quantization 30 2.2.3 The Lloyd–Max procedure 34 2.3 Vector quantization 35 2.3.1 Optimal vector quantization with a given size of codebook. The Linde–Buzo–Gray procedure 37 2.3.2 Lattice vector quantizers 40 Problems 52 3 Elements of rate-distortion theory 54 3.1 Rate-distortion function 54 3.2 The Blahut algorithm 61 3.3 The Shannon lower bound and high-resolution approximations 66 3.4 Comparison of quantization procedures 70 3.5 Characteristics of digital speech, audio, image, and video signals 75 Problems 76 4 Scalar quantization with memory 78 4.1 Discrete-time filters 78 4.1.1 Description by means of recurrent equations 79 4.1.2 Description by means of the z-transform 82 4.1.3 Inverse z-transform 84 4.1.4 Frequency function 87 4.2 Linear predictive coding 90 4.2.1 Autocorrelation method 94 4.2.2 Covariance method 95 4.2.3 Algorithms for the solution of the Yule–Walker equations 97 Problems 101 5 Transform coding 103 5.1 Properties of transforms 104 5.2 The Karhunen–Loeve transform 107 5.3 The discrete Fourier transform 110 5.4 The discrete cosine transform 116 Problems 120 6 Filter banks and wavelet filtering 122 6.1 Linear filtering as a linear transform 122 6.2 ``Moving average'' filtering as a linear transform 124 6.3 “Moving difference” filtering as a linear transform 126 6.4 The Haar filter bank 127 6.5 Wavelet transform and wavelet filter bank 133 6.6 Hierarchical wavelet filtering as a linear transform. Properties of wavelet filtering 138 6.7 Historical background 144 6.8 Application of wavelet filtering to image compression 144 6.9 Embedded zerotree coding and set partitioning in hierarchical trees 147 Problems 150 7 Speech coding: techniques and standards 153 7.1 Direct sample-by-sample quantization: Standard G.711 157 7.2 ADPCM coders: Standards G.726, G.727 159 7.3 Linear prediction analysis-by-synthesis coders (LPC-AS) 164 7.4 LPC vocoders. MELP standard 174 7.5 An algorithm for computing linear spectral parameters 177 Problems 181 8 Image coding standards 183 8.1 Coding of bi-level fax images: JBIG Standard 184 8.2 Coding of halftone images: JPEG Standard 189 8.3 JPEG-LS 198 8.4 Standard JPEG-2000 200 Problems 207 9 Video-coding standards 209 9.1 Motion compensation method 209 9.2 Overview of video-coding standards 212 9.2.1 H.261 and its derivatives 213 9.2.2 MPEG-1, MPEG-2, and MPEG-4 214 9.2.3 Standard H.264 220 Problems 233 10 Audio-coding standards 235 10.1 Basics of perceptual coding 235 10.2 Overview of audio standards 239 Problems 248 A Lossless-coding techniques 250 A.1 Symbol-by-symbol lossless coding 250 A.2 Lossless block coding 253 A.3 Arithmetic coding 255 A.4 Decoding issues 258 A.5 Context lossless coding for sources with memory 261 A.6 QM-coder 263 A.7 Monotonic codes 266 A.7.1 Unary code 266 A.7.2 Golomb code 266 A.7.3 Gallager–vanVoorhis codes 267 A.7.4 Levenstein codes 268 A.8 Binarization 269 A.9 Adaptive coding 270 References 273 Index 277 0521114322,9780521114325,0511769903,9780511769900

providing A Thorough Theoretical Understanding Of Lossy Compression Techniques For Image, Video, Speech, And Audio Compression, This Book Also Covers The Key Features Of Each System, As Well As Practical Applications, Implementation Issues, And Design Trade-offs. It Presents Comparisons Of Multimedia Standards In Terms Of Achieving Known Theoretical Limits, Whilst Common And Distinguishing Features Of The Existing Standards Are Explained And Related To The Background Theory. There Is Detailed Coverage Of Such Topics As The H.264 Video Coding Standard, Low-complexity Code-based Vector Quantizers, And The Blahut Rate-distortion Algorithm. Examples Based On Real Multimedia Data Are Also Included, Together With End-of-chapter Problems To Test Understanding; Algorithms That Allow The Reader To Represent Speech And Audio Signals Efficiently; And An Appendix On The Basics Of Lossless Coding. With An Excellent Balance Of Theory And Practice, This Book Is Deal For Undergraduate And Graduate Students, And Is Also A Useful Reference For Practitioners.

Provides a thorough theoretical understanding of lossy compression techniques and systems, plus key features, applications, implementation issues, and design trade-offs. It also includes detailed comparisons of multimedia standards and their common and distinguishing features, examples based on real multimedia data, end-of-chapter review problems, and the basics of lossless coding.