The transform and data compression handbook

Data compression is one of the main contributing factors in the explosive growth in information technology. Without it, a number of consumer and commercial products, such as DVD, videophone, digital camera, MP3, video-streaming and wireless PCS, would have been virtually impossible. Transforming the data to a frequency or other domain enables even more efficient compression. By illustrating this intimate link, The Transform and Data Compression Handbook serves as a much-needed handbook for a wide range of researchers and engineers.

The authors describe various discrete transforms and their applications in different disciplines. They cover techniques, such as adaptive quantization and entropy coding, that result in significant reduction in bit rates when applied to the transform coefficients. With clear and concise presentations of the ideas and concepts, as well as detailed descriptions of the algorithms, the authors provide important insight into the applications and their limitations. Data compression is an essential step towards the efficient storage and transmission of information. The Transform and Data Compression Handbook provides a wealth of information regarding different discrete transforms and demonstrates their power and practicality in data compression.

1 Karhunen-Loeve Transform	p. 1
1.1 Introduction	p. 1
1.2 Data Decorrelation	p. 2
1.2.1 Calculation of the KLT	p. 9
1.3 Performance of Transforms	p. 11
1.3.1 Information Theory	p. 11
1.3.2 Quantization	p. 13
1.3.3 Truncation Error	p. 13
1.3.4 Block Size	p. 15
1.4 Examples	p. 17
1.4.1 Calculation of KLT	p. 17
1.4.2 Quantization and Encoding	p. 18
1.4.3 Generalization	p. 22
1.4.4 Markov-1 Solution	p. 24
1.4.5 Medical Imaging	p. 25
1.4.6 Color Images	p. 28
1.5 Summary	p. 30
References	p. 34
2 The Discrete Fourier Transform	p. 37
2.1 Introduction	p. 37
2.2 The DFT Matrix	p. 39
2.3 An Example	p. 40
2.4 DFT Frequency Analysis	p. 41
2.5 Selected Properties of the DFT	p. 45
2.5.1 Symmetry Properties	p. 47
2.6 Real-Valued DFT-Based Transforms	p. 49
2.7 The Fast Fourier Transform	p. 55
2.8 The DFT in Coding Applications	p. 58
2.9 The DFT and Filter Banks	p. 60
2.9.1 Cosine-Modulated Filter Banks	p. 63
2.9.2 Complex DFT-Based Filter Banks	p. 66
2.10 Conclusion	p. 68
2.11 FFT Web sites	p. 72
References	p. 74
3 Comparametric Transforms for Transmitting Eye Tap Video with Picture Transfer Protocol (PTP)	p. 79
3.1 Introduction: Wearable Cybernetics	p. 79
3.1.1 Historical Overview of WearComp	p. 80
3.1.2 Eye Tap Video	p. 80
3.2 The Edgertonian Image Sequence	p. 81
3.2.1 Edgertonian versus Nyquist Thinking	p. 81
3.2.2 Frames versus Rows, Columns, and Pixels	p. 82
3.3 Picture Transfer Protocol (PTP)	p. 83
3.4 Best Case Imaging and Fear of Functionality	p. 84
3.5 Comparametric Image Sequence Analysis	p. 88
3.5.1 Camera, Eye, or Head Motion: Common Assumptions and Terminology	p. 91
3.5.2 VideoOrbits	p. 92
3.6 Framework: Comparameter Estimation and Optical Flow	p. 94
3.6.1 Feature-Based Methods	p. 94
3.6.2 Featureless Methods Based on Generalized Cross-Correlation	p. 95
3.6.3 Featureless Methods Based on Spatio-Temporal Derivatives	p. 96
3.7 Multiscale Projective Flow Comparameter Estimation	p. 99
3.7.1 Four Point Method for Relating Approximate Model to Exact Model	p. 101
3.7.2 Overview of the New Projective Flow Algorithm	p. 102
3.7.3 Multiscale Repetitive Implementation	p. 103
3.7.4 Exploiting Commutativity for Parameter Estimation	p. 104
3.8 Performance/Applications	p. 106
3.8.1 A Paradigm Reversal in Resolution Enhancement	p. 106
3.8.2 Increasing Resolution in the "Pixel Sense"	p. 107
3.9 Summary	p. 109
3.10 Acknowledgements	p. 111
References	p. 112
4 Discrete Cosine and Sine Transforms	p. 117
4.1 Introduction	p. 117
4.2 The Family of DCTs and DSTs	p. 118
4.2.1 Definitions of DCTs and DSTs	p. 118
4.2.2 Mathematical Properties	p. 119
4.2.3 Relations to the KLT	p. 121
4.3 A Unified Fast Computation of DCTs and DSTs	p. 122
4.3.1 Definitions of Even-Odd Matrices	p. 123
4.3.2 DCT-II/DST-II and DCT-III/DST-III Computation	p. 124
4.3.3 DCT-I and DST-I Computation	p. 129
4.3.4 DCT-IV/DST-IV Computation	p. 131
4.3.5 Implementation of the Unified Fast Computation of DCTs and DSTs	p. 134
4.4 The 2-D DCT/DST Universal Computational Structure	p. 146
4.4.1 The Fast Direct 2-D DCT/DST Computation	p. 146
4.4.2 Implementation of the Direct 2-D DCT/DST Computation	p. 152
4.5 DCT and Data Compression	p. 161
4.5.1 DCT-Based Image Compression/Decompression	p. 162
4.5.2 Data Structures for Compression/Decompression	p. 166
4.5.3 Setting the Quantization Table	p. 168
4.5.4 Standard Huffman Coding/Decoding Tables	p. 170
4.5.5 Compression of One Sub-Image Block	p. 172
4.5.6 Decompression of One Sub-Image Block	p. 179
4.5.7 Image Compression/Decompression	p. 184
4.5.8 Compression of Color Images	p. 186
4.5.9 Results of Image Compression	p. 188
4.6 Summary	p. 191
References	p. 192
5 Lapped Transforms for Image Compression	p. 197
5.1 Introduction	p. 197
5.1.1 Notation	p. 198
5.1.2 Brief History	p. 198
5.1.3 Block Transforms	p. 199
5.1.4 Factorization of Discrete Transforms	p. 200
5.1.5 Discrete MIMO Linear Systems	p. 201
5.1.6 Block Transform as a MIMO System	p. 203
5.2 Lapped Transforms	p. 204
5.2.1 Orthogonal Lapped Transforms	p. 204
5.2.2 Nonorthogonal Lapped Transforms	p. 210
5.3 LTs as MIMO Systems	p. 210
5.4 Factorization of Lapped Transforms	p. 213
5.5 Hierarchical Connection of LTs: An Introduction	p. 215
5.5.1 Time-Frequency Diagram	p. 215
5.5.2 Tree-Structured Hierarchical Lapped Transforms	p. 217
5.5.3 Variable-Length LTs	p. 219
5.6 Practical Symmetric LTs	p. 222
5.6.1 The Lapped Orthogonal Transform: LOT	p. 222
5.6.2 The Lapped Bi-Orthogonal Transform: LBT	p. 223
5.6.3 The Generalized LOT: GenLOT	p. 226
5.6.4 The General Factorization: GLBT	p. 230
5.7 The Fast Lapped Transform: FLT	p. 233
5.8 Modulated LTs	p. 236
5.9 Finite-Length Signals	p. 240
5.9.1 Overall Transform	p. 241
5.9.2 Recovering Distorted Samples	p. 243
5.9.3 Symmetric Extensions	p. 244
5.10 Design Issues for Compression	p. 246
5.11 Transform-Based Image Compression Systems	p. 248
5.11.1 JPEG	p. 249
5.11.2 Embedded Zerotree Coding	p. 250
5.11.3 Other Coders	p. 252
5.12 Performance Analysis	p. 253
5.12.1 JPEG	p. 253
5.12.2 Embedded Zerotree Coding	p. 255
5.13 Conclusions	p. 258
References	p. 260
6 Wavelet-Based Image Compression	p. 267
6.1 Introduction	p. 267
6.2 Dyadic Wavelet Transform	p. 268
6.2.1 Two-Channel Perfect-Reconstruction Filter Bank	p. 270
6.2.2 Dyadic Wavelet Transform, Multiresolution Representation	p. 272
6.2.3 Wavelet Smoothness	p. 273
6.3 Wavelet-Based Image Compression	p. 274
6.3.1 Lossy Compression	p. 274
6.3.2 EZW Algorithm	p. 278
6.3.3 SPIHT Algorithm	p. 285
6.3.4 WDR Algorithm	p. 294
6.3.5 ASWDR Algorithm	p. 299
6.3.6 Lossless Compression	p. 305
6.3.7 Color Images	p. 305
6.3.8 Other Compression Algorithms	p. 306
6.3.9 Ringing Artifacts and Postprocessing Algorithms	p. 306
References	p. 306
7 Fractal-Based Image and Video Compression	p. 313
7.1 Introduction	p. 313
7.2 Basic Properties of Fractals and Image Compression	p. 314
7.3 Contractive Affine Transforms, Iterated Function Systems, and Image Generation	p. 316
7.4 Image Compression Directly Based on the IFS Theory	p. 318
7.5 Image Compression Based on IFS Library	p. 321
7.6 Image Compression Based on Partitioned IFS	p. 322
7.6.1 Image Partitions	p. 323
7.6.2 Distortion Measure	p. 323
7.6.3 A Class of Discrete Image Transformations	p. 324
7.6.4 Encoding and Decoding Procedures	p. 325
7.6.5 Experimental Results	p. 326
7.7 Image Coding Using Quadtree Partitioned IFS (QPIFS)	p. 326
7.7.1 RMS Tolerance Selection	p. 328
7.7.2 A Compact Storage Scheme	p. 329
7.7.3 Experimental Results	p. 331
7.8 Image Coding by Exploiting Scalability of Fractals	p. 333
7.8.1 Image Spatial Sub-Sampling	p. 334
7.8.2 Decoding to a Larger Image	p. 334
7.8.3 Experimental Results	p. 334
7.9 Video Sequence Compression using Quadtree PIFS	p. 336
7.9.1 Definitions of Types of Range Blocks	p. 336
7.9.2 Encoding and Decoding Processes	p. 338
7.9.3 Storage Requirements	p. 340
7.9.4 Experimental Results	p. 340
7.9.5 Discussion	p. 341
7.10 Other Fractal-Based Image Compression Techniques	p. 341
7.10.1 Segmentation-Based Coding Using Fractal Dimension	p. 341
7.10.2 Yardstick Coding	p. 342
7.11 Conclusions	p. 343
References	p. 343
8 Compression of Wavelet Transform Coefficients	p. 347
8.1 Introduction	p. 347
8.2 Embedded Coefficient Coding	p. 353
8.3 Statistical Context Modeling of Embedded Bit Stream	p. 357
8.4 Context Dilution Problem	p. 359
8.5 Context Formation	p. 360
8.6 Context Quantization	p. 362
8.7 Optimization of Context Quantization	p. 365
8.8 Dynamic Programming for Minimum Conditional Entropy	p. 367
8.9 Fast Algorithms for High-Order Context Modeling	p. 369
8.9.1 Context Formation via Convolution	p. 370
8.9.2 Shared Modeling Context for Signs and Textures	p. 371
8.10 Experimental Results	p. 373
8.10.1 Lossy Case	p. 373
8.10.2 Lossless Case	p. 374
8.11 Summary	p. 374
References	p. 375
Index	p. 379

Available:*

On Order

Summary

Summary

Table of Contents