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.
Author(s): Kamisetty Ramam Rao, Pat Yip
Edition: 1
Publisher: CRC Press
Year: 2000
Language: English
Pages: 391
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 19
1.2 Data Decorrelation......Page 20
Calculation of Eigenvectors......Page 27
Markov-1 Solution......Page 28
1.3.1 Information Theory......Page 29
1.3.3 Truncation Error......Page 31
1.3.4 Block Size......Page 33
1.4.1 Calculation of KLT......Page 35
1.4.2 Quantization and Encoding......Page 36
1.4.3 Generalization......Page 40
1.4.4 Markov-1 Solution......Page 42
1.4.5 Medical Imaging......Page 43
1.4.6 Color Images......Page 46
1.5 Summary......Page 48
References......Page 52
2.1 Introduction......Page 55
2.2 The DFT Matrix......Page 57
2.3 An Example......Page 58
2.4 DFT Frequency Analysis......Page 59
2.5 Selected Properties of the DFT......Page 63
2.5.1 Symmetry Properties......Page 65
2.6 Real-Valued DFT-Based Transforms......Page 67
2.7 The Fast Fourier Transform......Page 73
2.8 The DFT in Coding Applications......Page 76
2.9 The DFT and Filter Banks......Page 78
2.9.1 Cosine-Modulated Filter Banks......Page 81
2.9.2 Complex DFT-Based Filter Banks......Page 84
2.10 Conclusion......Page 86
2.11 FFT Web sites......Page 90
References......Page 92
3.1 Introduction: Wearable Cybernetics......Page 96
3.1.2 Eye Tap Video......Page 97
3.2.1 Edgertonian versus Nyquist Thinking......Page 98
3.2.2 Frames versus Rows, Columns, and Pixels......Page 99
3.3 Picture Transfer Protocol (PTP)......Page 100
3.4 Best Case Imaging and Fear of Functionality......Page 101
3.5 Comparametric Image Sequence Analysis......Page 105
3.5.1 Camera, Eye, or Head Motion: Common Assumptions and Terminology......Page 108
Projective Group in 1-D......Page 109
Projective Group in 2-D......Page 110
3.6.1 Feature-Based Methods......Page 111
3.6.2 Featureless Methods Based on Generalized Cross-Correlation......Page 112
Optical Flow — Translation Flow......Page 113
Affine Fit and Affine Flow: a New Relationship......Page 114
Projective Fit and Projective Flow: New Techniques......Page 115
3.7 Multiscale Projective Flow Comparameter Estimation......Page 116
3.7.1 Four Point Method for Relating Approximate Model to Exact Model......Page 118
3.7.2 Overview of the New Projective Flow Algorithm......Page 119
3.7.3 Multiscale Repetitive Implementation......Page 120
3.7.4 Exploiting Commutativity for Parameter Estimation......Page 121
3.8.1 A Paradigm Reversal in Resolution Enhancement......Page 123
3.8.2 Increasing Resolution in the “Pixel Sense”......Page 124
3.9 Summary......Page 126
3.10 Acknowledgements......Page 128
References......Page 129
4.1 Introduction......Page 134
4.2.1 Definitions of DCTs and DSTs......Page 135
4.2.2 Mathematical Properties......Page 136
The Convolution-Multiplication Property......Page 137
4.2.3 Relations to the KLT......Page 138
4.3 A Unified Fast Computation of DCTs and DSTs......Page 139
Even-Odd Permutation Matrices......Page 140
4.3.2 DCT-II/DST-II and DCT-III/DST-III Computation......Page 141
4.3.3 DCT-I and DST-I Computation......Page 146
4.3.4 DCT-IV/DST-IV Computation......Page 148
4.3.5 Implementation of the Unified Fast Computation of DCTs and DSTs......Page 151
Computer Program for the Fast DCT-II/DST-II and DCT-III/DST-III Compu-tation......Page 152
Computer Program for the Fast DCT-I Computation......Page 156
Computer Program for the Fast DST-I Computation......Page 158
Computer Program for the Fast DCT-IV/DST-IV Computation......Page 160
4.4.1 The Fast Direct 2-D DCT/DST Computation......Page 163
4.4.2 Implementation of the Direct 2-D DCT/DST Computation......Page 169
4.5 DCT and Data Compression......Page 178
4.5.1 DCT-Based Image Compression/Decompression......Page 179
4.5.2 Data Structures for Compression/Decompression......Page 183
4.5.3 Setting the Quantization Table......Page 185
4.5.4 Standard Huffman Coding/Decoding Tables......Page 187
4.5.5 Compression of One Sub-Image Block......Page 189
Coding the DC and AC Coefficients......Page 192
4.5.6 Decompression of One Sub-Image Block......Page 196
4.5.7 Image Compression/Decompression......Page 201
4.5.8 Compression of Color Images......Page 203
4.5.9 Results of Image Compression......Page 205
4.6 Summary......Page 208
References......Page 209
5.1 Introduction......Page 213
5.1.2 Brief History......Page 214
5.1.3 Block Transforms......Page 215
5.1.4 Factorization of Discrete Transforms......Page 216
5.1.5 Discrete MIMO Linear Systems......Page 217
5.1.6 Block Transform as a MIMO System......Page 219
5.2.1 Orthogonal Lapped Transforms......Page 220
5.3 LTs as MIMO Systems......Page 226
5.4 Factorization of Lapped Transforms......Page 229
5.5.1 Time-Frequency Diagram......Page 231
5.5.2 Tree-Structured Hierarchical Lapped Transforms......Page 233
5.5.3 Variable-Length LTs......Page 235
5.6.1 The Lapped Orthogonal Transform: LOT......Page 238
5.6.2 The Lapped Bi-Orthogonal Transform: LBT......Page 239
5.6.3 The Generalized LOT: GenLOT......Page 242
5.6.4 The General Factorization: GLBT......Page 246
5.7 The Fast Lapped Transform: FLT......Page 249
5.8 Modulated LTs......Page 252
5.9 Finite-Length Signals......Page 256
5.9.1 Overall Transform......Page 257
5.9.2 Recovering Distorted Samples......Page 259
5.9.3 Symmetric Extensions......Page 260
Coding Gain......Page 262
Attenuation at Mirror Frequencies......Page 263
5.11 Transform-Based Image Compression Systems......Page 264
5.11.1 JPEG......Page 265
5.11.2 Embedded Zerotree Coding......Page 266
Embedded zerotree coding as a bit-plane refinement scheme.......Page 267
5.11.3 Other Coders......Page 268
5.12.1 JPEG......Page 269
5.12.2 Embedded Zerotree Coding......Page 271
5.13 Conclusions......Page 274
References......Page 276
6.1 Introduction......Page 282
6.2 Dyadic Wavelet Transform......Page 283
6.2.1 Two-Channel Perfect-Reconstruction Filter Bank......Page 285
6.2.2 Dyadic Wavelet Transform, Multiresolution Representation......Page 287
6.2.3 Wavelet Smoothness......Page 288
6.3.1 Lossy Compression......Page 289
6.3.2 EZW Algorithm......Page 293
6.3.3 SPIHT Algorithm......Page 300
6.3.4 WDR Algorithm......Page 309
6.3.5 ASWDR Algorithm......Page 314
6.3.7 Color Images......Page 320
References......Page 321
7.1 Introduction......Page 327
7.2 Basic Properties of Fractals and Image Compression......Page 328
Contractive Affine Transforms......Page 330
Iterated Function Systems......Page 331
7.4 Image Compression Directly Based on the IFS Theory......Page 332
7.5 Image Compression Based on IFS Library......Page 335
7.6 Image Compression Based on Partitioned IFS......Page 336
7.6.2 Distortion Measure......Page 337
Brightness Shift......Page 338
7.6.4 Encoding and Decoding Procedures......Page 339
7.7 Image Coding Using Quadtree Partitioned IFS (QPIFS)......Page 340
7.7.1 RMS Tolerance Selection......Page 342
7.7.2 A Compact Storage Scheme......Page 343
7.7.3 Experimental Results......Page 345
7.8 Image Coding by Exploiting Scalability of Fractals......Page 347
7.8.3 Experimental Results......Page 348
7.9.1 Definitions of Types of Range Blocks......Page 350
Type Three Range Blocks......Page 351
7.9.2 Encoding and Decoding Processes......Page 352
7.9.4 Experimental Results......Page 354
7.10.1 Segmentation-Based Coding Using Fractal Dimension......Page 355
7.10.2 Yardstick Coding......Page 356
References......Page 357
8.1 Introduction......Page 360
8.2 Embedded Coefficient Coding......Page 366
8.3 Statistical Context Modeling of Embedded Bit Stream......Page 370
8.4 Context Dilution Problem......Page 372
8.5 Context Formation......Page 373
8.6 Context Quantization......Page 375
8.7 Optimization of Context Quantization......Page 378
8.8 Dynamic Programming for Minimum Conditional Entropy......Page 380
8.9 Fast Algorithms for High-Order Context Modeling......Page 382
8.9.1 Context Formation via Convolution......Page 383
8.9.2 Shared Modeling Context for Signs and Textures......Page 384
8.10.1 Lossy Case......Page 386
8.11 Summary......Page 387
References......Page 388
