The transform and data compression handbook

Kamisetty Ramam Rao, Pat Yip9780849336928, 0-8493-36929

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.

---

Table of contents :
THE TRANSFORM AND DATA COMPRESSION HANDBOOK……Page 2
Preface……Page 6
Outline of Chapters……Page 7
Acknowledgements……Page 10
List of Acronyms……Page 11
Contributors……Page 13
Contents……Page 14
1.1 Introduction……Page 20
1.2 Data Decorrelation……Page 21
Calculation of Eigenvectors……Page 28
Markov-1 Solution……Page 29
1.3.1 Information Theory……Page 30
1.3.3 Truncation Error……Page 32
1.3.4 Block Size……Page 34
1.4.1 Calculation of KLT……Page 36
1.4.2 Quantization and Encoding……Page 37
1.4.3 Generalization……Page 41
1.4.4 Markov-1 Solution……Page 43
1.4.5 Medical Imaging……Page 44
1.4.6 Color Images……Page 47
1.5 Summary……Page 49
References……Page 53
2.1 Introduction……Page 57
2.2 The DFT Matrix……Page 59
2.3 An Example……Page 60
2.4 DFT Frequency Analysis……Page 61
2.5 Selected Properties of the DFT……Page 65
2.5.1 Symmetry Properties……Page 67
2.6 Real-Valued DFT-Based Transforms……Page 69
2.7 The Fast Fourier Transform……Page 75
2.8 The DFT in Coding Applications……Page 78
2.9 The DFT and Filter Banks……Page 80
2.9.1 Cosine-Modulated Filter Banks……Page 83
2.9.2 Complex DFT-Based Filter Banks……Page 86
2.10 Conclusion……Page 88
2.11 FFT Web sites……Page 92
References……Page 94
3.1 Introduction: Wearable Cybernetics……Page 99
3.1.2 Eye Tap Video……Page 100
3.2.1 Edgertonian versus Nyquist Thinking……Page 101
3.2.2 Frames versus Rows, Columns, and Pixels……Page 102
3.3 Picture Transfer Protocol (PTP)……Page 103
3.4 Best Case Imaging and Fear of Functionality……Page 104
3.5 Comparametric Image Sequence Analysis……Page 108
3.5.1 Camera, Eye, or Head Motion: Common Assumptions and Terminology……Page 111
Projective Group in 1-D……Page 112
Projective Group in 2-D……Page 113
3.6.1 Feature-Based Methods……Page 114
3.6.2 Featureless Methods Based on Generalized Cross-Correlation……Page 115
Optical Flow — Translation Flow……Page 116
Affine Fit and Affine Flow: a New Relationship……Page 117
Projective Fit and Projective Flow: New Techniques……Page 118
3.7 Multiscale Projective Flow Comparameter Estimation……Page 119
3.7.1 Four Point Method for Relating Approximate Model to Exact Model……Page 121
3.7.2 Overview of the New Projective Flow Algorithm……Page 122
3.7.3 Multiscale Repetitive Implementation……Page 123
3.7.4 Exploiting Commutativity for Parameter Estimation……Page 124
3.8.1 A Paradigm Reversal in Resolution Enhancement……Page 126
3.8.2 Increasing Resolution in the “Pixel Sense”……Page 127
3.9 Summary……Page 129
3.10 Acknowledgements……Page 131
References……Page 132
4.1 Introduction……Page 138
4.2.1 Definitions of DCTs and DSTs……Page 139
4.2.2 Mathematical Properties……Page 140
The Convolution-Multiplication Property……Page 141
4.2.3 Relations to the KLT……Page 142
4.3 A Unified Fast Computation of DCTs and DSTs……Page 143
Even-Odd Permutation Matrices……Page 144
4.3.2 DCT-II/DST-II and DCT-III/DST-III Computation……Page 145
4.3.3 DCT-I and DST-I Computation……Page 150
4.3.4 DCT-IV/DST-IV Computation……Page 152
4.3.5 Implementation of the Unified Fast Computation of DCTs and DSTs……Page 155
Computer Program for the Fast DCT-II/DST-II and DCT-III/DST-III Compu-tation……Page 156
Computer Program for the Fast DCT-I Computation……Page 160
Computer Program for the Fast DST-I Computation……Page 162
Computer Program for the Fast DCT-IV/DST-IV Computation……Page 164
4.4.1 The Fast Direct 2-D DCT/DST Computation……Page 167
4.4.2 Implementation of the Direct 2-D DCT/DST Computation……Page 173
4.5 DCT and Data Compression……Page 182
4.5.1 DCT-Based Image Compression/Decompression……Page 183
4.5.2 Data Structures for Compression/Decompression……Page 187
4.5.3 Setting the Quantization Table……Page 189
4.5.4 Standard Huffman Coding/Decoding Tables……Page 191
4.5.5 Compression of One Sub-Image Block……Page 193
Coding the DC and AC Coefficients……Page 196
4.5.6 Decompression of One Sub-Image Block……Page 200
4.5.7 Image Compression/Decompression……Page 205
4.5.8 Compression of Color Images……Page 207
4.5.9 Results of Image Compression……Page 209
4.6 Summary……Page 212
References……Page 213
5.1 Introduction……Page 218
5.1.2 Brief History……Page 219
5.1.3 Block Transforms……Page 220
5.1.4 Factorization of Discrete Transforms……Page 221
5.1.5 Discrete MIMO Linear Systems……Page 222
5.1.6 Block Transform as a MIMO System……Page 224
5.2.1 Orthogonal Lapped Transforms……Page 225
5.3 LTs as MIMO Systems……Page 231
5.4 Factorization of Lapped Transforms……Page 234
5.5.1 Time-Frequency Diagram……Page 236
5.5.2 Tree-Structured Hierarchical Lapped Transforms……Page 238
5.5.3 Variable-Length LTs……Page 240
5.6.1 The Lapped Orthogonal Transform: LOT……Page 243
5.6.2 The Lapped Bi-Orthogonal Transform: LBT……Page 244
5.6.3 The Generalized LOT: GenLOT……Page 247
5.6.4 The General Factorization: GLBT……Page 251
5.7 The Fast Lapped Transform: FLT……Page 254
5.8 Modulated LTs……Page 257
5.9 Finite-Length Signals……Page 261
5.9.1 Overall Transform……Page 262
5.9.2 Recovering Distorted Samples……Page 264
5.9.3 Symmetric Extensions……Page 265
Coding Gain……Page 267
Attenuation at Mirror Frequencies……Page 268
5.11 Transform-Based Image Compression Systems……Page 269
5.11.1 JPEG……Page 270
5.11.2 Embedded Zerotree Coding……Page 271
Embedded zerotree coding as a bit-plane refinement scheme…….Page 272
5.11.3 Other Coders……Page 273
5.12.1 JPEG……Page 274
5.12.2 Embedded Zerotree Coding……Page 276
5.13 Conclusions……Page 279
References……Page 281
6.1 Introduction……Page 288
6.2 Dyadic Wavelet Transform……Page 289
6.2.1 Two-Channel Perfect-Reconstruction Filter Bank……Page 291
6.2.2 Dyadic Wavelet Transform, Multiresolution Representation……Page 293
6.2.3 Wavelet Smoothness……Page 294
6.3.1 Lossy Compression……Page 295
6.3.2 EZW Algorithm……Page 299
6.3.3 SPIHT Algorithm……Page 306
6.3.4 WDR Algorithm……Page 315
6.3.5 ASWDR Algorithm……Page 320
6.3.7 Color Images……Page 326
References……Page 327
7.1 Introduction……Page 334
7.2 Basic Properties of Fractals and Image Compression……Page 335
Contractive Affine Transforms……Page 337
Iterated Function Systems……Page 338
7.4 Image Compression Directly Based on the IFS Theory……Page 339
7.5 Image Compression Based on IFS Library……Page 342
7.6 Image Compression Based on Partitioned IFS……Page 343
7.6.2 Distortion Measure……Page 344
Brightness Shift……Page 345
7.6.4 Encoding and Decoding Procedures……Page 346
7.7 Image Coding Using Quadtree Partitioned IFS (QPIFS)……Page 347
7.7.1 RMS Tolerance Selection……Page 349
7.7.2 A Compact Storage Scheme……Page 350
7.7.3 Experimental Results……Page 352
7.8 Image Coding by Exploiting Scalability of Fractals……Page 354
7.8.3 Experimental Results……Page 355
7.9.1 Definitions of Types of Range Blocks……Page 357
Type Three Range Blocks……Page 358
7.9.2 Encoding and Decoding Processes……Page 359
7.9.4 Experimental Results……Page 361
7.10.1 Segmentation-Based Coding Using Fractal Dimension……Page 362
7.10.2 Yardstick Coding……Page 363
References……Page 364
8.1 Introduction……Page 368
8.2 Embedded Coefficient Coding……Page 374
8.3 Statistical Context Modeling of Embedded Bit Stream……Page 378
8.4 Context Dilution Problem……Page 380
8.5 Context Formation……Page 381
8.6 Context Quantization……Page 383
8.7 Optimization of Context Quantization……Page 386
8.8 Dynamic Programming for Minimum Conditional Entropy……Page 388
8.9 Fast Algorithms for High-Order Context Modeling……Page 390
8.9.1 Context Formation via Convolution……Page 391
8.9.2 Shared Modeling Context for Signs and Textures……Page 392
8.10.1 Lossy Case……Page 394
8.11 Summary……Page 395
References……Page 396