Authors: Stephen T. Welstead
ISBN-13: 9780819435033, ISBN-10: 0819435031
Format: Paperback
Publisher: SPIE Press
Date Published: November 1999
Edition: New Edition
Interest in image compression for Internet and other multimedia applications has spurred research into compression techniques that will increase storage capabilities and transmission speed. This tutorial provides a practical guide to fractal and wavelet approaches--two techniques with exciting potential. It is intended for scientists, engineers, researchers, and students. It provides both introductory information and implementation details. Three Windows-compatible software systems are included so that readers can explore the new technologies in depth. Complete C/C++ source code is provided, enabling readers to go beyond the accompanying software. The mathematical presentation is accessible to advanced undergraduate or beginning graduate students in technical fields.
A tutorial text on the techniques behind fractal and wavelet approaches to image compression. Welstead (mathematics, U. of Alabama- Huntsville) assumes no previous knowledge of image compression, fractal geometry, or wavelet concepts, and figures that the mathematics should be apprehensible to advanced undergraduates and beginning graduates in technical fields. He includes three software packages for Windows, along with the complete C/C++ source code for those who want to color outside the lines. Annotation c. Book News, Inc., Portland, OR (booknews.com)
Preface | ||
1. | Introduction | 1 |
1.1 | Images | 2 |
1.2 | The image compression problem | 3 |
1.3 | Information, entropy, and data modeling | 4 |
1.4 | Scalar and vector quantization | 5 |
1.5 | Transform methods | 7 |
1.6 | Color images | 8 |
1.7 | The focus of this book | 9 |
Part 1 | Fractal Image Compression | |
2. | Iterated Function Systems | 1 |
2.1 | Iterated function systems as the motivation for fractal image compression | |
2.2 | Metric spaces | 2 |
2.2.1 | Basic concepts | 2 |
2.2.2 | Compact sets and Hausdorff space | 4 |
2.2.3 | Contraction mappings | 6 |
2.3 | Iterated function systems | 8 |
2.3.1 | Introduction | 8 |
2.3.2 | The Collage Theorem | 9 |
2.3.3 | What the Collage Theorem says | 9 |
2.3.4 | Affine transformations | 11 |
2.4 | Implementation of an iterated function system | 12 |
2.4.1 | Points and transformations | 12 |
2.4.2 | Affine coefficients | 14 |
2.4.3 | Computing the fractat attractor image from the IFS | 15 |
2.4.3.1 | Deterministic algorithm | 15 |
2.4.3.2 | Random algorithm | 18 |
2.5 | Examples | 24 |
2.5.1 | Sierpinski triangle | 24 |
2.5.1.1 | Fractal dimension | 25 |
2.5.2 | Constructing an IFS from a real image | 27 |
2.5.3 | A few more EFS examples | 28 |
3. | Fractal Encoding of Grayscale Images | 1 |
3.1 | A metric space for grayscale images | 1 |
3.2 | Partitioned iterated function systems (PIFS) | 2 |
3.2.1 | Affine transformations on grayscale images | 2 |
3.2.2 | Contraction mappings on grayscale images | 3 |
3.2.3 | Contraction mapping theorem for grayscale images | 3 |
3.2.4 | Collage Theorem for grayscale images | 5 |
3.3 | Fractal image encoding | 6 |
3.3.1 | Domain cells | 8 |
3.3.2 | Quadtree partitioning of range cells | 9 |
3.3.2.1 | A scheme for keeping track of quadtree partitioning | 11 |
3.3.3 | Mapping domains to ranges | 12 |
3.3.4 | Encoding times | 14 |
3.4 | Image decoding | 15 |
3.4.1 | Measuring the error | 16 |
3.5 | Storing the encoded image | 18 |
3.5.1 | Range file format | 18 |
3.5.2 | Binary range file format | 19 |
3.5.2.1 | Efficient quadtree storage | 20 |
3.5.2.2 | Bit structure for storing range information | 21 |
3.5.2.3 | Transmission robustness | 22 |
3.6 | Resolution independence | 23 |
3.7 | Operator representation of fractal image encoding | 24 |
3.7.1 | "Get-block" and "put-block" operators | 24 |
3.7.2 | Operator formulation | 25 |
3.7.3 | Solution of the operator equation | 26 |
3.7.4 | Error analysis | 27 |
4. | Speeding Up Fractal Encoding | 1 |
4.1 | Feature extraction | 1 |
4.1.1 | Feature definitions | 1 |
4.1.2 | Encoding algorithm using feature extraction | 3 |
4.1.3 | Sample results using feature extraction | 6 |
4.2 | Domain classification | 11 |
4.2.1 | Self-organizing neural networks | 12 |
4.2.2 | Fractal image encoding using self-organizing domain classification | |
4.2.3 | Sample results using self-organizing domain classifier | 16 |
4.3 | Other approaches for speeding up fractal encoding | 20 |
Part II | Wavelet Image Compression | |
5. | Simple Wavelets | 1 |
5.1 | Introduction | 1 |
5.2 | Averaging and detail | 2 |
5.3 | Scaling functions and wavelet functions | 4 |
5.4 | Multiresolution analysis | 9 |
5.5 | Normalization | 12 |
5.6 | Wavelet transform | 13 |
5.7 | Inverse wavelet transform | 17 |
5.8 | Wavelet transform in two dimensions | 19 |
5.8.1 | What a wavelet transform looks like | 21 |
5.8.2 | Simple wavelet compression scheme | 24 |
6. | Daubechies Wavelets | 1 |
6.1 | Weighted averages and differences | 1 |
6.1.1 | Lowpass and highpass filtering | 1 |
6.1.2 | Matrix representation | 2 |
6.2 | Properties and conditions on the coefficients | 3 |
6.3 | Wavelet transform | 4 |
6.4 | Scaling functions and wavelet functions | 5 |
6.5 | Daubechies wavelets | 6 |
6.6 | Simple image compression with Daubechies wavelets | 8 |
6.7 | Summary | 11 |
7. | Wavelet Image Compression Techniques | 1 |
7.1 | Introduction | 1 |
7.2 | Wavelet zerotrees | 3 |
7.2.1 | An implementation of wavelet zerotree coding | 5 |
7.2.1.1 | Terminology: Which way is up? | 6 |
7.2.1.2 | Handling the insignificant coefficients | 8 |
7.2.1.3 | The zerotree encoding algorithm | 12 |
7.2.1.4 | Bit planes | 13 |
7.2.2 | Decoding a zerotree encoded image | 14 |
7.2.3 | Where is the compression? | 21 |
7.2.4 | Encoding speed | 22 |
7.3 | Hybrid fractal-wavelet coding | 23 |
7.3.1 | Operator approach to hybrid fractal-wavelet coding | 24 |
7.3.2 | Other hybrid approaches | 26 |
8. | Comparison of Fractal and Wavelet Image Compression | 1 |
8.1 | Rate distortion | 1 |
8.2 | Encodincy speed | 4 |
8.3 | Larger imaores | 5 |
8.4 | Conclusions | 8 |
References | ||
Appendix A | Using the Accompanying Software | 1 |
A.1 | IFS System | 1 |
A.1.1 | Points window | 1 |
A.1.2 | Transformation window | 3 |
A.1.3 | IFS window | 5 |
A.2 | IMG System: Fractal Image Compression | 8 |
A.2.1 | Encode window | 9 |
A.2.1.1 | Encode setup | 10 |
A.2.1.2 | Running image encoding | 12 |
A.2.2 | Self-organizing encoding window | 13 |
A.2.2.1 | Setting up the self-organizing network | 14 |
A.2.2.2 | Running self-organized image encoding | 15 |
A.2.3 | Decode window | 15 |
A.2.4 | Subtraction window | 17 |
A.2.5 | Plot window | 17 |
A.3 | WAV System: Wavelet Image Compression | 20 |
A.3.1 | Wavelet compression window | 20 |
A.3.2 | Wavelet zerotree encoding | 22 |
A.3.3 | Wavelet zerotree decoding | 23 |
A.3.4 | Image subtraction with the WAV System | 24 |
A.3.5 | Wavelet plotting window | 24 |
A.3.3.1 | Setting Up the Graph Parameters | 25 |
Appendix B | Utility Windows Library (UWL) | 1 |
B.1 | Windows Programming | 1 |
B.1.1 | Multiple Document Interface (MDI) | 2 |
B.1.2 | Dialogs | 3 |
B.1.2.1 | Modal vs. modeless dialogs | 3 |
B.1.2.2 | Windows Common Dialogs | 4 |
B.2 | Utility Windows Library (UWL) | 5 |
B.2.1 | The t-window class | 6 |
B.2.2 | MDI frame window | 8 |
B.2.3 | MDI windows | 11 |
B.2.4 | Graph window | 13 |
B.2.5 | WinMain in a UWL application | 15 |
B.2.6 | UWL dialogs | 20 |
B.2.7 | Building UWL | 21 |
B.3 | Windows Programming References | 23 |
Appendix C | Organization of the Accompanying Software Source Code | 1 |
C.1 | IFS System | 1 |
C.1.1 | IFS classes | 1 |
C.1.2 | IFS code files | 3 |
C.1.3 | UTM Library | 4 |
C.2 | IMG System | 5 |
C.2.1 | IMG classes | 5 |
C.2.2 | IMG code files | 6 |
C.3 | WAV System | 8 |
C.3.1 | WAV classes | 8 |
C.3.2 | WAV code files | 9 |