Download the software systems.

Preface

1. Introduction 1-1

1.1 Images 1-2

1.2 The image compression problem 1-3

1.3 Information, entropy, and data modeling 1-4

1.4 Scalar and vector quantization 1-5

1.5 Transform methods 1-7

1.6 Color images 1-8

1.7 The focus of this book 1-9

PART 1: FRACTAL IMAGE COMPRESSION

2. Iterated Function Systems 2-1

2.1 Iterated function systems as the motivation for fractal image compression

2.2 Metric spaces 2-2

2.2.1 Basic concepts 2-2

2.2.2 Compact sets and Hausdorff space 2-4

2.2.3 Contraction mappings 2-6

2.3 Iterated function systems 2-8

2.3.1 Introduction 2-8

2.3.2 The Collage Theorem 2-9

2.3.3 What the Collage Theorem says 2-9

2.3.4 Affine transformations 2-11

2.4 Implementation of an iterated function system 2-12

2.4.1 Points and transformations 2-12

2.4.2 Affine coefficients 2-14

2.4.3 Computing the fractat attractor image from the IFS 2-15

2.4.3.1 Deterministic algorithm 2-15

2.4.3.2 Random algorithm 2-18

2.5 Examples 2-24

2.5.1 Sierpinski triangle 2-24

2.5.1.1 Fractal dimension 2-25

2.5.2 Constructing an IFS from a real image 2-27

2.5.3 A few more EFS examples 2-28

3. Fractal Encoding of Grayscale Images 3-1

3.1 A metric space for grayscale images 3-1

3.2 Partitioned iterated function systems (PIFS)3-2

3.2.1 Affine transformations on grayscale images 3-2

3.2.2 Contraction mappings on grayscale images 3-3

3.2.3 Contraction mapping theorem for grayscale images 3-3

3.2.4 Collage Theorem for grayscale images 3-5

3.3 Fractal image encoding 3-6

3.3.1 Domain cells 3-8

3.3.2 Quadtree partitioning of range cells 3-9

3.3.2.1 A scheme for keeping track of quadtree partitioning 3-11

3.3.3 Mapping domains to ranges 3-12

3.3.4 Encoding times 3-14

3.4 Image decoding 3-15

3.4.1 Measuring the error 3-16

3.5 Storing the encoded image 3-18

3.5.1 Range file format 3-18

3.5.2 Binary range file format 3-19

3.5.2.1 Efficient quadtree storage 3-20

3.5.2.2 Bit structure for storing range information 3-21

3.5.2.3 Transmission robustness 3-22

3.6 Resolution independence 3-23

3.7 Operator representation of fractal image encoding 3-24

3.7.1 "Get-block" and "put-block" operators 3-24

3.7.2 Operator formulation 3-25

3.7.3 Solution of the operator equation 3-26

3.7.4 Error analysis 3-27

4. Speeding Up Fractal Encoding 4-1

4.1 Feature extraction 4-1

4.1.1 Feature definitions 4-1

4.1.2 Encoding algorithm using feature extraction 4-3

4.1.3 Sample results using feature extraction 4-6

4.2 Domain classification 4-11

4.2.1 Self-organizing neural networks4-12

4.2.2 Fractal image encoding using self-organizing domain classification

4.2.3 Sample results using self-organizing domain classifier 4-16

4.3 Other approaches for speeding up fractal encoding 4-20

PART II: WAVELET IMAGE COMPRESSION

5. Simple Wavelets 5-1

5.1 Introduction 5-1

5.2 Averaging and detail 5-2

5.3 Scaling functions and wavelet functions 5-4

5.4 Multiresolution analysis 5-9

5.5 Normalization 5-12

5.6 Wavelet transform 5-13

5.7 Inverse wavelet transform5-17

5.8 Wavelet transform in two dimensions5-19

5.8.1 What a wavelet transform looks like5-21

5.8.2 Simple wavelet compression scheme5-24

6. Daubechies Wavelets 6-1

6.1 Weighted averages and differences 6-1

6.1.1 Lowpass and highpass filtering 6-1

6.1.2 Matrix representation 6-2

6.2 Properties and conditions on the coefficients 6-3

6.3 Wavelet transform 6-4

6.4 Scaling functions and wavelet functions 6-5

6.5 Daubechies wavelets 6-6

6.6 Simple image compression with Daubechies wavelets 6-8

6.7 Summary 6-11

7. Wavelet Image Compression Techniques 7-1

7.1 Introduction 7-1

7.2 Wavelet zerotrees 7-3

7.2.1 An implementation of wavelet zerotree coding 7-5

7.2.1.1 Terminology: Which way is up? 7-6

7.2.1.2 Handling the insignificant coefficients 7-8

7.2.1.3 The zerotree encoding algorithm 7-12

7.2.1.4 Bit planes7-13

7.2.2 Decoding a zerotree encoded image 7-14

7.2.3 Where is the compression? 7-21

7.2.4 Encoding speed 7-22

7.3 Hybrid fractal-wavelet coding7-23

7.3.1 Operator approach to hybrid fractal-wavelet coding 7-24

7.3.2 Other hybrid approaches 7-26

8. Comparison of Fractal and Wavelet Image Compression 8-1

8.1 Rate distortion 8-1

8.2 Encodincy speed 8-4

8.3 Larger imaores 8-5

8.4 Conclusions 8-8

References

Appendix A: Using the Accompanying Software A-1

A.1 IFS System A-1

A.1.1 Points window A-1

A.1.2 Transformation window A-3

A.1.3 IFS window A-5

A.2 IMG System: Fractal Image Compression A-8

A.2.1 Encode window A-9

A.2.1.1 Encode setup A-10

A.2.1.2 Running image encoding A- 12

A.2.2 Self-organizing encoding window A-13

A.2.2.1 Setting up the self-organizing network A- 14

A.2.2.2 Running self-organized image encoding A- 15

A.2.3 Decode window A- 15

A.2.4 Subtraction window A- 17

A.2.5 Plot window A- 17

A.3 WAV System: Wavelet Image Compression A-20

A.3.1 Wavelet compression window A-20

A.3.2 Wavelet zerotree encoding A-22

A.3.3 Wavelet zerotree decoding A-23

A.3.4 Image subtraction with the WAV System A-24

A.3.5 Wavelet plotting window A-24

A.3.3.1 Setting Up the Graph Parameters A-25

Appendix B: Utility Windows Library (UWL) B-1

B.1 Windows Programming B-1

B.1.1 Multiple Document Interface (MDI) B-2

B.1.2 Dialogs B-3

B.1.2.1 Modal vs. modeless dialogs B-3

B.1.2.2 Windows Common Dialogs B-4

B.2 Utility Windows Library (UWL) B-5

B.2.1 The t-window class B-6

B.2.2 MDI frame window B-8

B.2.3 MDI windows B-11

B.2.4 Graph window B-13

B.2.5 WinMain in a UWL application B-15

B.2.6 UWL dialogs B-20

B.2.7 Building UWL B-21

B.3 Windows Programming References B-23

Appendix C: Organization of the Accompanying Software Source Code C-1

C.1 IFS System C-1

C.1.1 IFS classes C-1

C.1.2 IFS code files C-3

C.1.3 UTM Library C-4

C.2 IMG System C-5

C.2.1 IMG classes C-5

C.2.2 IMG code files C-6

C.3 WAV System C-8

C.3.1 WAV classes C-8

C.3.2 WAV code files C-9

Preface

This book is a tutorial text that examines the techniques behind fractal and wavelet approaches to image compression. The field of image compression has experienced an explosion of interest recently because of the growth of the Internet and other multimedia applications. While standard image and data compression methods exist and are in extensive use today, the demand for ever increasing storage requirements and transmission speed have spurred continued research for improved methods. Fractals and wavelets provide two different avenues for such research. For scientists, engineers, students and researchers interested in learning more about fractal and wavelet image compression, this book provides both an introduction to the subject matter and implementation details sufficient for beginning their own investigations into these exciting new technologies.

In addition to learning the theory behind fractal and wavelet image compression, readers of this book will have access to software that will enable them to explore these ideas on their own. Three complete Windows-compatible software systems are included with the accompanying software. The IFS System allows readers to create their own fractal images using iterated function systems. The IMG System compresses images using fractal techniques, displays the decoded images, and computes the error between the original and decoded images through image subtraction. The WAV System performs similar functions on images using wavelet techniques, and, in addition, displays the wavelet transform of an image. Each system uses a standard Windows interface and includes options for saving and retrieving information from files. The programs run on 32-bit Windows systems, including Windows NT, 95 and 98. Finally, to enable readers to explore beyond the boundaries of the included software, complete C/C++ source code is provided.

Prior knowledge of image compression, fractal geometry or wavelet concepts is not necessary to benefit from this book. The level of mathematical presentation is accessible to advanced undergraduate or beginning graduate students in technical fields. Mathematical concepts that would be helpful to know include the idea of convergence of a sequence, multiple integrals, linear independence and basis vectors. Experienced image processing practitioners will probably be disappointed at the minimal amount of coverage devoted to traditional techniques such as the discrete cosine transform and entropy coding. These topics are covered in depth in other books. For example, entropy coding, which can be applied to the output of any compression algorithm, including fractal and wavelet approaches, is not included in the system applications developed here. The present book focuses on the mathematical aspects of fractal and wavelet image compression.

The source code for the accompanying software is written in a combination of C and C++. It is not necessary to know either of these languages to benefit from the ideas of this book or to run the programs included with the software. There are a few code examples listed with the text. For the most part, the computational code is written in C. When there is an obvious benefit to exploiting the object-oriented characteristics of C++, then that language is used. In either case, the computational code is kept separate from the user-interface and display code modules that access Windows. Thus, the computational source code, with perhaps minor modifications, should be portable to other platforms, such as UNIX. The user-interface code, where there is an obvious benefit to using object-oriented properties such as inheritance, is written in C++. The source code includes its own C++ application framework for developing simple Windows applications, It does not depend on Microsoft's Foundation Classes (MFC) or other third-party frameworks. The code here was developed using Borland's C++ for Windows, version 4.5.2. It should be possible to re-compile the code with any C++ compiler that accesses the Windows Application Programming Interface (API).

Outline of Topics

The book begins with an overview of the image compression problem, including a brief discussion of general topics such as information and entropy, arithmetic coding, and a look at current compression approaches such as JPEG. These general topics are introduced in order to place fractal and wavelet image compression techniques in the context of the overall theory of image compression. The remainder of the book is devoted to fractal and wavelet topics, and will not focus on general compression topics, such as entropy coding, which are covered in other texts.

Fractal image compression is motivated by initially looking at iterated function systems (IFS). The mathematics of IFS theory, including the contraction mapping theorem, Barnsley's collage theorem, and affine transformations, is covered here. These topics are important to understanding why fractal image compression works. Computer examples show how to use IFS techniques to synthesize fractal images resembling natural objects.

Partitioned iterated function systems extend the ideas of IFS theory to more general real-world images, and enable fractal encoding and compression of these images. Once the theory behind fractal encoding has been established, the book considers practical implementation issues, such as how to set up a system of domain and range subimages, and the transformations between these subimages. Computer examples illustrate concepts such as quadtree partitioning of range cells and the convergence of image sequences to an attractor image.

Long encoding times have hindered the acceptance of fractal techniques for image compression. Two approaches for speeding up the encoding process have received recent attention in the literature. Feature extraction reduces the number of computations needed for domain-range comparisons. Classification of domains reduces search times for finding a good domain-range match. This book examines techniques for feature extraction and the use of neural networks for domain classification. Examples show that these techniques reduce encoding times from hours to seconds and make PC implementation viable.

The book then introduces wavelets as an alternative approach to image compression. Basic Haar wavelets illustrate the idea of wavelet decomposition as a process of averaging and detail extraction at different resolution levels. The book presents a unifying approach to the seemingly disparate multiple entry points into wavelet analysis. Image resolution leads the reader from the ideas of averaging and detail extraction on discrete sequences to scaling functions and wavelet functions. The fact that these functions form basis sets in certain vector spaces leads to the idea of multiresolution analysis. The wavelet transform can be derived from any of these entry points. Averaging and detail extraction can be represented as matrix operators, which leads to a particularly simple formulation of the wavelet transform. The essential features of these operators can be extended to more general highpass and lowpass filtering operators. This analysis leads to more complex wavelet systems, such as the Daubechies wavelets, which provide high compression of commonly occurring signal and image components. With the wavelet framework established the book examines wavelet image compression techniques, beginning with simple wavelet coefficient quantization schemes and moving on to more complex schemes such as wavelet zerotree encoding. Code samples will illustrate key implementation steps, and computer examples will show how the techniques work. The book also discusses recent research in hybrid techniques which apply the ideas of fractal encoding to data in the wavelet transform domain. Computer examples compare the performance of fractal, wavelet, and hybrid image compression techniques.

Stephen T. Welstead