Master’s Thesis Proposal
Student Information
Family Name:
First Name:
e-mail:
Title
Fractal Encoding and Decoding using Iterated Function Systems
Aims and scope
The topic of this dissertation lies in the intersection between fractal geometry and image compression. Theoretical study, implementation and evaluation of the methods leading to compressed grey-scale images by using 2D Iterated Function Systems or IFS’s for short will be presented. The conclusions of this theoretical study and evaluation will lead us to the selection of the appropriate IFS for encoding and decoding static images taking due note of each method’s distinctiveness.
Background/State of the art
In the 1980's, a group called the Joint Photographers Expert Group was formed to determine the standards for image compression. Their studies resulted in the JPEG scheme, a lossy form of compression which involves many steps [11] . First the image being compressed is separated into a grey-scale image (the luminance) and the color information. Each of these is compacted separately. For visual purposes, our eyes can spare colour more than luminance. This is because our eyes use the grey-scale edges to define boundaries but allow colour to bleed across boundaries. So, the precision of the colour information is usually reduced to half of the precision used for the brightness values. Then the discrete cosine transform, in which the terms in the expansion are real valued, is applied to square sub-regions in the image. The compression of the image is attained by keeping as few expansion terms as possible [11] . The fewer the number of terms kept, the greater the compression; this also means that the loss of high frequency information is greater. This process can be performed on many areas within the image. Finally more compression can be achieved by truncating the precision of each term, then using a coding scheme that stores repeated strings of numbers. With this method, it is possible to reach a compression ratio of 100:1, although ratios on the range of 10:1 to 20:1 are more typical [11] , [6] . After compression, loss in the sharpness and detail can be detected. Depending on the software or hardware used, the time difference in compression and decompression of an image can vary up to tens of seconds.
A more recent approach pioneered by Michael Barnsley and Alan Sloan [4] is to use the similarities on different scales throughout images to assist in compression. However, the first automated compression scheme for real world images using IFS was developed by Jacquin [8] in 1992. Fractal Image Compression (see [3] , [5] ) enables an incredible amount of data to be stored in highly compressed data files. We will explore the mathematical theory which supports fractal image compression.
One of the most important foundations for fractal image compression is the concept of iterated function systems (IFS); see for instance [2] or [1] . The basic idea of an Iterated Function System is to create a finite set of contraction mappings (see [7] ), written as affine transformations, based on what image one desires to create. If these mappings are contractive, applying the IFS to a seed image will eventually produce an attractor (see [9] ). The choice of the seed image does not affect the resulting fixed point (see [10] ). Through IFS we are able to systematically reproduce fractals that occur in nature. With the theory that will be presented, we will explore the development of an IFS and how one can apply IFS to obtain fractal image compression.
Problem definition
A fractal is a structure that is made up of similar forms and patterns that occur in many different sizes. The term fractal describes repeating patterns that occur in many different structures. These patterns appeared nearly identical in form at any size and occurred naturally in all things. Also these fractals could be described in mathematical terms and could be created using very small and finite algorithms and data.
Fractal encoding is a mathematical process used to encode bitmaps containing a real-world image as a set of mathematical data that describes the fractal properties of the image. Fractal encoding relies on the fact that all natural, and most artificial, objects contain redundant information in the form of similar, repeating patterns or fractals.
The encoding process is extremely computationally intensive. Millions or billions of iterations are required to find the fractal patterns in an image. Depending upon the resolution and contents of the input bitmap data, and output quality, compression time, and file size parameters selected, compressing a single image could take anywhere from a few seconds to a few hours (or more) on even a very fast computer.
Decoding a fractal image is a much simpler process. The hard work was performed finding all the fractals during the encoding process. All the decoding process needs to do is to interpret the fractal codes and translate them into a bitmap image. Iterated function systems or IFS’s are a method of constructing fractals ; the resulting constructions are always self-similar .
Fractals derived by IFS’s can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence ‘function system’). The canonical example is the Sierpinski gasket . The functions are normally contractive which means they bring points closer together and make shapes smaller. Hence the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, ad infinitum . This is the source of its self-similar fractal nature.
Sometimes each function fi is required to be a linear, or more generally an affine transformation and hence represented by a matrix. So, the similarity that exists in different parts of an image could be described in a finite set of instructions and data. By using some image-areas of the image, by rotating, resizing, and stretching them, it is possible to generate other parts of the image.
An image compressed in this way contains a minimal area plus a transformation matrix that contains all required information to reconstruct something similar to the original image by rotating, resizing and stretching this area. Therefore the task of fractal encoding algorithms is to find redundant areas of an image and to reduce these areas to the necessary information about attractor and transformation matrix. To perform this task, the image is divided into 'domains' in coarse or fine resolution depending on the redundancy of the image. Then the routine searches the image for 'ranges' that have a similarity to the domain that can be described by an affine matrix.
Methodology
Before delving into the main study, we first present a review of the IFS theory. Next, the fractal compression scheme using IFS’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 IFS’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 IFS’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. The race has only begun.
Conclusions
The aim of this thesis was to investigate the different approaches and find a suitable method that successfully encodes gray-scale images and decodes them according to their originals. For this purpose a system capable of automatically find similarities within images was
implemented. The method presented relies on already existing methods which are seen in different scientific areas, it is therefore not clear how well the method will perform on different instances.
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 IFS’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