Master’s Thesis Proposal
Student Information
Family Name:
First Name:
e-mail:
Title
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.
Methodology
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.
Objectives
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.
Timescale
Six month semester.
Comparisons/Results
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.
Conclusions
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.
References
Supervisor Information
Name: V. Drakopoulos
Institution: University of Athens
e-mail: vasilios@di.uoa.gr