Master’s Thesis Proposal

Student Information

Family Name:

First Name:



Image Compression using Fractal Interpolation Functions

Aims and scope

The topic of this dissertation lies in the intersection between fractal geometry, image compression and Approximation Theory. Theoretical study, implementation and evaluation of the methods leading to compressed gray-scale images by using 1D Fractal Interpolation Functions, or FIF’s for short, will be presented.

Background/State of the art

IFS image compression was first suggested by Barnsley and Sloan [5] in 1988. However, the first automated compression scheme for real world images using IFS was developed by Jacquin [8] in 1992. Currently, IFS image compression is considered to be comparable to the existing methods at high and moderate bit rates (.5 to 1 bpp) and superior to most methods at low bit rates (< 0.25 bpp). The main disadvantage of the IFS scheme is that the encoding process is computationally very intensive. However, decoding is simple and fast. This method is thus ideally suited for browsing archives where encoding is done only once, while decoding is done often.

Based on a theorem of Hutchinson ( [7] , p. 731) and using iterated-function-systems (IFS) theory [4] , Barnsley introduced a class of functions in [2] (see also [3] ) which he called fractal interpolation functions or FIF's for short. He worked basically with affine FIF's, in the sense that they are obtained using affine transformations. The affine FIF's have in common with elementary functions that they are of a geometrical character and that they can be computed rapidly. The main difference is their fractal character since their graphs usually have non-integral dimension. The graphs of these functions can be used to approximate image components such as the profiles of mountain ranges, the tops of clouds and horizons over forests, to name but a few. Recent applications of this theory include modelling of discrete sequences as in [11] , modelling of speech signals as in [14] and compression of static images as in [1] . There also exist other methods which use fractal interpolation surfaces, for instance [6] , [9] , [12] , [15] .

Problem definition

Image compression is the application of Data compression on digital images. In effect, the objective is to reduce redundancy of the image data in order to be able to store or transmit data in an efficient form.

Image compression can be lossy or lossless. Lossless compression is sometimes preferred for artificial images such as technical drawings, icons or comics. This is because lossy compression methods, especially when used at low bit rates, introduce compression artifacts. Lossless compression methods may also be preferred for high value content, such as medical imagery or image scans made for archival purposes. Lossy methods are especially suitable for natural images such as photos in applications where minor loss of fidelity is acceptable to achieve a substantial reduction in bit rate.

A fractal is generally ‘a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole’. Images of fractals can be created using fractal generating software. Images produced by such software are normally referred to as being fractals even if they do not have the above characteristics, as it is possible to zoom into a region of the image that does not exhibit any fractal properties.

The resolution independence of a fractal-encoded image can be used to increase the display resolution of an image. This process is also known as fractal interpolation. In fractal interpolation, an image is encoded into fractal codes via fractal compression, and subsequently decompressed at a higher resolution. The result is an up-sampled image in which iterated function systems have been used as the interpolant.

Because fractal interpolation operates on geometric information in the image, rather than pixel information, it maintains geometric detail very well compared to other interpolation methods. Fractal interpolation is currently used in Genuine Fractals 5 and is best suited for extreme enlargements.


Before delving into the main study, we first present a review of the FIF theory. Next, the fractal compression scheme using FIF’s will be explained in detail. After a brief explanation of the decoding scheme, the main differences with other image compression schemes will be explained. Finally, an algorithm using the ideas of fractal encoding and decoding using FIF’s will be presented and implemented. For the implementation of the methods a high-level programming language such as C, Pascal, Visual Studio or Delphi will be used, whereas the results will be extracted by using Mathematica or MATLAB.


Fractal Image Compression or FIC for short, based on the use of FIF’s belongs to a class of image compression techniques which offer the advantages of high compression ratio and fast decoding. In this dissertation we present several techniques for the efficacy of FIC.


Six month semester.

March 2009 Pre-study, investigate different techniques and approaches.
April 2009 Analyse and evaluate the different approaches. Investigate existing tools that might facilitate the implementation.
May 2009 Method implementation, recognizing image segments with high accuracy.
June 2009 Evaluate the result and improve the program (increase its functionalities, for example by tagging the data).
July 2009 Present the result in a concordance format; possibility of extracting the tagged data into a database.


The simple Fractal image compression algorithm executed is the most efficient form of compression which we implemented, although research has revealed that JPEG is one of the better, if not the best, forms of compression available today. The question has been posed as to whether or not an optimal Fractal compression algorithm will be discovered that will outperform JPEG. Much research is being done to find faster and more efficient forms of image compression technology.


The aim of this thesis was to investigate the different approaches and find a suitable fractal interpolation method that successfully encodes grey-scale images and decodes them according to their originals. For this purpose a system capable of automatically identifying the map parameters within images was implemented. The method presented relies on already existing identification methods which are seen in different scientific areas, it is therefore not clear how well the method will perform on different images.

The method requirements were achieved, the method is able to identify the map parameters and correctly recognize the similarities between different regions of the image. The conclusions of this theoretical study and evaluation will lead us to the selection of the appropriate FIF’s for encoding and decoding static images taking due note of each method’s distinctiveness.


[1] M. Ali and T. G. Clarkson, Using linear fractal interpolation functions to compress video images, Fractals, Vol. 2, 1994, pp. 417 – 421.
[2] M. F. Barnsley, Fractal functions and interpolation, Constructive Approximation, Vol. 2, 1986, pp. 303–329.
[3] M. F. Barnsley, Fractals everywhere, 2nd ed., Academic Press Professional, 1993.
[4] M. F. Barnsley and S. Demko, Iterated function systems and the global construction of fractals, Proceedings of the Royal Society of London, Vol. 399, No.X, 1985, pp. 243-275.
[5] M. F. Barnsley and A. D. Sloan, A better way to compress images, Byte, Vol. 13, 1988, pp. 215–223.
[6] J. S. Geronimo and D. P. Hardin, Fractal interpolation surfaces and a related 2-D multiresolution analysis, Journal of Mathematical Analysis and Applications, Vol. 176, No. 2, 1993, pp. 561-586.
[7] J. E. Hutchinson, Fractals and self similarity, Indiana University of Mathematics Journal, Vol. 30, No. X, 1981, pp. 713-747.
[8] A. E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Trans. Image Processing, Vol. 1, No. 1, 1992, pp. 18–30.
[9] P. R. Massopust, Fractal surfaces, Journal of Mathematical Analysis and Applications, Vol. 151, No. 1, 1990, pp. 275-290.
[10] P. R. Massopust, Fractal functions, fractal surfaces and wavelets, Academic Press, 1994.
[11] D.S. Mazel and M. H. Hayes, Using iterated function systems to model discrete sequences, IEEE Trans. Signal Processing, Vol. 40, No. 7, 1992, pp. 1724–1734.
[12] Z. Nailiang, Construction and application of fractal interpolation surfaces, The Visual Computer, Vol. 12, No. ?, 1996, pp. 132-146.
[13] J. R. Price and M. H. Hayes III, Resampling and reconstruction with fractal interpolation functions, IEEE Signal Processing Letters, Vol. 5, No. 3, 1998, pp. 228-230.
[14] J. L. Véhel, K. Daoudi and E. Lutton, Fractal modeling of speech signals, Fractals, Vol. 2, 1994, pp. 379–382.
[15] H. Xie and H. Sun, The study on bivariate fractal interpolation functions and creation of fractal interpolated surfaces, Fractals, Vol. 5, 1997, pp. 625-634.

Supervisor Information

Name: V. Drakopoulos

Institution: University of Athens