by Alexander Davidson
December 2000

(This was my final project for an undergrad course called Pure Math 370 - Chaos & Fractals)


  1. Introduction
  2. Quad-Tree Fractal Compression
  3. Files
  4. Project Description
  5. Other Fractal Compression Schemes
  6. Conclusions
  7. References


The intent of my project was to create a useful program that lets the user compress image files. The FractalSqueeze program is for Windows and supports reading and writing of the PNG (Portable Network Graphics) lossless image format. The compression method used is Yuval Fisher's quad-tree fractal compression algorithm. FractalSqueeze is limited to grayscale images.

Quad-Tree Fractal Compression

As discussed in my review of the article "A Hitchhiker's Guide to 'Fractal-Based' Function Approximation and Image Compression", a fractal image can be compactly represented by the contractive transformations used to generate the image. Yuval Fisher wrote a working fractal encoder and decoder to go with his book, Fractal Image Compression: Theory and Application [1]. The algorithm he used is a quad-tree based method. This scheme classifies the domains and ranges of the image into a quad-tree structure. This means that we cover the planar region of interest by a square, then recursively partition squares (domain blocks) into smaller squares (range blocks) until each square contains a suitably uniform subset of the input. Then we can generate the various affine transformations of the range blocks to the domain blocks by finding the most suitable match. If our tolerance is not met we can improve the technique by further subdividing in order to get a better match at the cost of encoding speed.

Files - FractalSqueeze executable (for Windows NT, 9x) - FractalSqueeze source code (Win32 - MS Developer Studio)

Note that FractalSqueeze makes use of the freeware PNG library libpng. This is available at:

Project Description

Figure 1. FractalSqueeze About Box

The FractalSqueeze program will appear as in Figure 2. From the file menu, four functions are available. FractalSqueeze allows you to load any grayscale PNG files via the "Load Image" menu. Loaded images can be saved in PNG format using "Save Image". Loaded images can be compressed and saved as a FSQ file. And finally FractalSqueeze will decompress and display any FSQ file (which can subsequently be saved as a PNG file).

Figure 2. FractalSqueeze Interface

When an image is loaded the user will be presented with the dialog in Figure 3. After a PNG file has been selected, FractalSqueeze will display that file as in Figure 4.

Figure 3. FractalSqueeze Open Image Dialog

Figure 4. FractalSqueeze displaying an uncompressed Vince Carter

Once an image has been loaded, the user can choose to compress it and save it as an FSQ file. An FSQ file can be decompressed and the resulting image will be displayed in FractalSqueeze as in Figure 5. Notice the degradation in quality of the image.

Figure 5. FractalSqueeze displaying a decompressed Vince Carter

Here are the actual input and output files used in the above demo:

Figure 6. vince.png input file

Figure 7. vince-output.png generated by FractalSqueeze

And this is the compressed data file generated. The file vince.png is 40KB and vince.fsq is a mere 8KB representing a compression ratio of 5 times. (Note that since the PNG format utilizes its own compression the file vince-output.png is only 36KB.)

Other Fractal Compression Schemes

There are methods of fractal image compression other than Fisher's quad-tree scheme. The excellent fractal compression program called Mars by Mario Polvere supports Fisher's method as well as five others. I used this program to generate images of Vince to compare the different methods. (Since Mars only supports RAW data I first converted vince.png to vince.raw using the shareware program Paint Shop Pro and then converted the resulting RAW images back to PNG format for display here.)

Figure 8. Mars using Fisher method

Figure 9. Mars using Hurtgen method

Figure 9. Mars using Mass Center method

Figure 10. Mars using Saupe method

Figure 11. Mars using Saupe-Fisher method

Figure 12. Mars using Saupe-Mass Center method

Each of these methods generated an intermediate format file of between 7 and 8KB although the times taken to compress varied more. Notice the superior quality of the images using Saupe and Saupe-Fisher (Figures 10 & 11).


The FractalSqueeze program is useful and easy to use. It will generate compressed images with a ratio of around 5-10 times depending on the image. This compression is not necessarily as good as JPEG but as shown in the tests with Mars, we can get very good results using other fractal compression schemes.

Possible future improvements for FractalSqueeze:


[1] Yuval Fisher's Website:

back to

Contents ©2001 Alexander Davidson