Fractal and Wavelet Image Compression Techniques / Edition 1

by Stephen T. Welstead

Overview

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.

Product Details

ISBN-13:	9780819435033
Publisher:	SPIE Press
Publication date:	11/01/1999
Series:	Tutorial Texts in Optical Engineering Series
Edition description:	New Edition
Pages:	254
Product dimensions:	7.04(w) x 10.02(h) x 0.62(d)

Table of Contents

	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

Editorial Reviews

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)

Booknews