Abstract ^*

of Thesis for a Master’s Degree in Computer Science

"Fractal Image Compression Algorithms: Comparison Analysis, Modification"

Author: Alexander V. Bublichenko

Supervisor: c.t.s. Valeriy N. Belovodskiy

Actuality

The effective data compression has always been one of the most challenging problems in information science. With development of digital communications and emergence of Internet it had become even more actual. Thus, a number of algorithms intended for effective digital images compression, transmission and storage were developed since 1980-s [1]. The advance of fractal’s theory and respective mathematical apparatus in the end of XX century lead to invention of fundamentally new algorithm of image compression — fractal image compression. The idea of fractal-based image compression method was stated and patented by M. Barnsley in 1990 [11] and its concept is as follows. For a given image a system of contraction mappings is formed by special rules for which the image is an attractor. Then, due to the Theorem of Fixed Point [10] the iteration process based on these contraction mappings converges to its attractor regardless of initial image used. The compression is achieved due to the fact that only mapping coefficients have to be stored for image restoration.

This compression method has some distinctive features that caused attraction of interest to it for over 20 years. These are the following:

• high compression ratio (the ratio of initial amount of information to amount of code). Thus, for images with comprehensive self-similarity it can be as high as 2000;
• the quality of decoded image does not depend on scale of viewing;
• essential asymmetry: the encoding time is noticeably longer than decoding time.

A comparatively long encoding time caused by considerable number of variations to be searched within remains to be the main disadvantage of this method of compression. Therefore, it is reasonable to develop modifications of this algorithm aimed to reducing its encoding time.

Aims and Tasks

The aim of this work is to make a comparison analysis of basic algorithms in order to identify specifics in domain blocks selection and approbation of its approximation methods. This aim is achieved by introducing modifications in domain block selection methods and means of its approximation.

The idea of this work is development of new modifications of domain blocks selection methods and means of its approximation into rage blocks for improving compression efficiency.

The following tasks are posed and solved to achieve the stated aim:

• 1) literature research and theoretical analysis of lossy image compression algorithms;
• 2) ascertainment of specifics in fractal image compression algorithms, development of appropriate software that implements them;
• 3) formation of set of test images and conduction of computing experiments for identifying specifics in domain blocks selection and its approximation, comparison analysis of results, formulation of conclusions;
• 4) modification of particular algorithm stages, development of its new version;
• 5) development of appropriate software components, conduction of experiments, formulation of comparison results.

The subject of research is algorithms of lossy image compression.

The object of research is fractal image compression algorithms.

The methods of research include computing experiments, comparison analysis of results, numerical methods, mathematical methods of approximation, object-oriented programming.

Supposed scientific novelty consists of the following:

• 1) a proper software is developed that implements basic fractal image compression algorithms and allows to make comparison analysis;
• 2) the computing experiments are conducted, comparison analysis is done and specifics in domain blocks selection in basic algorithms are identified;
• 3) the analysis of nonlinear approximation mappings of image blocks is done;
• 4) new modifications of algorithm that will provide better efficiency are proposed.

Research Summary

The basic and FE-algorithms were researched. These algorithms are well described in [2]. A proper software was developed in C# language with Microsoft .NET 2.0 that implements these algorithms. The software allows to encode bitmap images into fractal images and decode them back by mentioned algorithms. User can specify encoding settings controlling the quality of encoded images. Besides, the developed software includes the following means of analysis:

• 1) display of domains and ranges structure both in table and on the encoded image;
• 2) calculation of average pixel error between initial and encoded image;
• 3) calculation of quantity of processed and used range and domain blocks during encoding;
• 4) measurement of encoding and decoding time;
• 5) display of grid of range blocks on the image;
• 6) automated analysis of results of image encoded by different algorithms.

A series of computing experiments is done. The following conclusions are made basing on results of experiments:

• 1) the FE-algorithms allows to encode images tens’ times faster with the same setting;
• 2) the difference in average pixel errors lies between 5-16% depending on encoding settings;
• 3) in average a 30-40% higher compression ration is achieved with basic algorithm in all the experiments;
• 4) the visual quality of decoded image is noticeably better with FE-algorithm;
• 5) the decoding time of encoded image with different setting is better with basic algorithm in all the experiments.

Conclusions

The following suggestions are made basing on research and experiments:

1. The bounding domain blocks are suggested to be generated and included into initial domain set. It is expected that the use of these domain blocks will enhance the image quality and a search started on these domains will reduce the overall encoding time.

2. Instead of features in FE-algorithm a main criteria is suggested to be used to small copies of image blocks. This will reduce the encoding time and keep the image quality.

3. The use of nonlinear mappings is expected to provide much better approximation of image blocks and is supposed to significantly improve the quality of encoded images.

References

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов. Сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2003
2. С. Уэлстид. Фракталы и вейвлеты для сжатия изображений в действии. Учеб¬ное пособ. — М.: Издательство «Триумф», 2003, с. 77-119
3. А.Н. Авлеева. Фрактальное сжатие изображений. Решение задач сжатия изображений с использованием систем итерированных функций. Магистерская диссертация, ДонНТУ, 2006
4. Д.С. Ватолин. Использование ДКП для ускорения фрактального сжатия изображений. Журнал «Программирование» №3 1999, с. 51-57
5. John Kominek. Algorithm for Fast Fractal Image Compression. Department of Computer Science, University of Waterloo, Canada, 1995
6. Stephen Welstead. Self-Organizing Neural Network Domain Classification for Fractal Image Coding. Proc. of the IASTED International Conference “Artificial Intelligence and Soft Computing”. Banff, Canada, 1997, pp. 248-251
7. Lucia Vences, Isaac Rudomin. Genetic Algorithms for Fractal Image and Image Sequence Compression. Manuscript. Institute of Technology, University of Monterrey, 1997
8. Lifeng Xi,Liangbin Zhang. A Study of Fractal Image Compression Based on an Improved Genetic Algorithm. International Journal of Nonlinear Science. Vol.3, No. 2, 2007, pp. 116-124
9. M. Hassaballah, M.M. Makky, Youssef B. Mahdy. A Fast Fractal Image Compression Method Based Entropy. Electronic Letters on Computer Vision and Image Analysis 5(1), 2005, pp. 30-40
10. P. M. Кроновер. Фракталы и хаос в динамических системах. Основы теории. — М.: Постмаркет, 2000
11. Barnsley, Michael F., Sloan, Alan D., Iterated Systems, Inc. Methods and apparatus for image compression by iterated function system. United States Patent 4941193, July 10, 1990

* — The work is in development for the current day and is planned to be finished by December 1st, 2008. The paper and relevant materials can be obtained either form author or its supervisor after that date.