by Alexander Davidson December 2000 (This was my final project for an undergrad course called Pure Math 370 - Chaos & Fractals)
by Alexander Davidson December 2000 (This was my final project for an undergrad course called Pure Math 370 - Chaos & Fractals)
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.zip - FractalSqueeze executable (for Windows NT, 9x)
fractalsqueeze-src.zip - FractalSqueeze source code (Win32 - MS Developer Studio)
Note that FractalSqueeze makes use of the freeware PNG library libpng. This is available at: http://www.libpng.org/
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).
Conclusions
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:
http://inls.ucsd.edu/y/Fractals/book.html