Recursive Block Coding for Image Data Compression

This book introduces a new image data compression technique called Recursive Block Coding. The book contains not only theoretical discussion but also simulation studies and suggested design methodologies.

1 Introduction.- 1.1 The Need for Data Compression.- 1.2 Data Compression Techniques.- Predictive Coding―DPCM.- Transform Coding.- Karhunen-Lòeve Transform (KLT).- Hybrid Coding.- Vector Quantization (VQ).- 1.3 The Problem―the Tile Effect.- 1.4 Our Approach―Two Source Decomposition.- 1.5 Organization.- 2 RBC―The Theory behind the Algorithms.- 2.1 Introduction.- 2.2 Modeling.- 2.3 Autoregressive Models.- Example―1st-order AR process.- 2.4 Noncausal Models.- Example―noncausal MVR for a 1st-order AR sequence.- 2.5 Two Source Decomposition.- 2.6 The 1d RBC Algorithm.- 2.7 Boundary Response for First Order AR Models.- Transform Domain Solution.- Spatial Domain Solution.- Simple Algorithm for 1st-Order AR Models.- 2.8 2d Minimum Variance Models.- 2.9 Examples of 2d Noncausal Image Models.- The NC1 Model.- Two Source Decomposition.- 2.10 2d Boundary Response via Transform Methods.- Transform Domain Solution.- 2.11 The 2d RBC Algorithm.- 2.12 Approximate Boundary Response.- Spatial Domain Solution.- The Alternative 2d RBG Algorithm.- Bilinear Patches.- Coon’s Patches.- Bicubic Patches.- 2.13 Advantages of RBC.- Removing Interblock Redundancy.- Reducing the Tile Effect.- 3 Bit Allocation and Quantization for Transform Coding.- 3.1 Introduction.- 3.2 Choice of Transform and Quantizer.- Fidelity Criterion.- Transform Domain Distortion.- Optimal Transformation and Quantization.- Transform.- Amplitude Probability Density Function.- Coefficient Variances.- 3.3 Bit Allocation.- Rate-Distortion Functions.- Optimal Bit Allocation.- Shannon Rate Distortion Function.- Approximations.- Huang and Schultheiss.- Wintz and Kurtenbach.- Segall.- Wang and Jain.- General Approximation For Piecewise Exponentials.- The Integral Constraint.- 3.4 Integer Bit Allocation.- General Integer Bit Allocation.- Comments.- 3.5 Zero Level Quantizers.- 3.6 Choice of RD Function for Bit Allocation.- Shannon versus Lloyd-Max.- 3.7 RBC Rate Distortion Analysis.- Id RBC Rate-Distortion Analysis.- 2d RBC Rate-Distortion Analysis.- Alternative Minimization Strategy.- 3.8 Ensemble Design for DCT and RBC.- RBC Variance Reduction.- Variance Reduction With 2d RBC.- 3.9 Color Coding.- 4 Zonal Coding.- 4.1 Introduction.- 4.2 Original Images.- Color Images.- 4.3 Simulation Facilities.- 4.4 Image Quality Measures.- Hosaka Plots (h-plots).- 4.5 1d Coding Results.- 1d DCT Design.- 1d RBC Design.- Discussion of Results.- Ensemble A.- Tiffany.- Ensemble B.- 4.6 2d Coding Results.- 2d DCT Design.- 2d RBC Design.- Discussion of Results.- 4.7 Hybrid Coding.- DPCM Equations.- Bit Allocation.- Hybrid Coding Results.- Hybrid DCT Design.- Hybrid RBC Design.- Discussion of Results.- 4.8 Conclusions.- 5 Adaptive Coding Based on Activity Classes.- 5.1 Introduction.- 5.2 Adaptive DCT.- Design Methodology.- DC Quantizer.- Standard Normalized Variances.- Performance Curve.- Class Rate Allocation.- Coding Methodology.- 5.3 Adaptive RBC.- Design Methodology.- Coding Methodology.- 5.4 Coding Results.- Ensemble Design.- Individual Design.- 5.5 Conclusions.- Future Work.- 6 Adaptive Coding Based on Quad Tree Segmentation.- 6.1 Introduction.- 6.2 Adaptive Segmentation.- 6.3 The Quad Tree Approach.- Residual.- Overlapping Blocks.- Predictor.- Uniformity.- Mean Residual Energy.- Segmentation.- Choosing the Segmentation Parameters.- 6.4 Coding the Segmentation.- Generating Split and Merge Information.- Split and Merge Bits for Fig. 6.4.2.- Prediction Rate.- 6.5 Reconstruction.- Fast Linear Interpolation for N a Power of 2.- Fast Bilinear Interpolation.- Modified Interpolation.- Examples of Reconstructed Images.- 6.6 Coding the Residual.- Choice of Transform.- Choice of Threshold.- 6.7 Results.- Zero Level Quantizers.- 6.8 Conclusions.- 7 QVQ―Vector Quantization of the Quad Tree Residual.- 7.1 Introduction.- 7.2 Vector Quantization.- Advantages of VQ Over Scalar Quantization.- Vector Methods: Transform Coding and VQ.- VQ Design.- Splitting Codewords.- VQ Coding.- Performance Considerations.- 7.3 Differential and Interpolate VQ.- 7.4 VQ of the Quad Tree Residual.- Choosing the Vector Dimension.- Choosing the Training Sequence.- 7.5 Coding Results.- 7.6 Conclusions.- 8 Conclusions.- 8.1 Introduction.- 8.2 New Results.- 8.3 Coding Recommendations.- 8.4 Future Work.- Appendix A Ordinary and Partial Differential and Difference Equations.- A.1 Introduction.- A.2 Second Order Ordinary Differential Equations.- A.3 Second Order Ordinary Difference Equations.- A.4 Second Order Partial Differential Equations.- A.5 Second Order Partial Difference Equations.- Appendix B Properties of the Discrete Sine Transform.- B.1 Introduction.- Definition.- Notation.- Tridiagonal Toeplitz Matrices.- B.2 DST Evaluation Technique.- B.3 Exponential Sequences.- B.4 Constant Sequences.- B.5 Linear Sequences.- B.6 Hyperbolic Sequences.- B.7 Sinusoidal Sequences.- Appendix C Transform Domain Variance Distributions.- C.1 Introduction.- C.2 1d RBC.- Normalized Variance Distribution.- Variance Reduction Ratio.- C.3 1d DCT.- Appendix D Coding Parameters for Adaptive Coding Based on Activity Classes.- D.1 Introduction.- D.2 Adaptive DCT Coding Parameters.- D.3 Adaptive RBC Coding Parameters.- References.