The abstract of master's thesis
"Fractal image compression. The solution of image compression problems with the help of the iterated function system"

     Development of the Internet, availability of more powerful computers and progress in production engineering of digital cameras, scanners and printers, have led to wide use of digital photos. As a result of this, there is a growth of interest in improvement of algorithms of fractal image compression.
     Data compression is relevant both for data transfer rate and efficiency of data storage. In addition to many kinds of commercial use, compression technologies are interesting for the military, for example, in applications for processing telemetry data, which was obtained from rocket interceptors, or for archiving land map data for simulation of defensive operations.
     The solution of the image compression problem or, in a general sense, image coding, used achievements and stimulated development of many fields of science and technology.

     In December 1992, just before Christmas, Microsoft Corporation released its new compact disc with Microsoft Encarta. Since then, this multimedia encyclopedia, which contains information about animals, flowers, trees and beautiful sceneries, doesn't leave the list of the most popular CD-encyclopedias.
     According to a recent poll, the Microsoft Encarta again took first place, taking the lead over its rival - the Compton multimedia encyclopedia. The reason for such a popularity is usability, good quality of articles, and above all - large quantity of materials. There are 7 hours of music, 100 animations, about 800 scalable maps, as well as 7000 high-quality photos on the disc. And all this is on one disc. Usual compact disc of 650 Mb can hold 56 minutes of high-quality music or 1 hour of video MPEG-1 with resolution of 320x200 pixels, or 700 color images of size 640x480 pixels.
     In order to accomodate more information, it is necessary to use effective compression methods. Let us consider the history of fractal image compression. The birth of fractal geometry is usually bound up with the publication of Mandelbrot's "The fractal geometry of nature" in 1977. One of the main ideas of the book consists in that, it is very difficult to represent natural objects by means of traditional geometry. The fractal geometry can do this easily.
     In 1981, John Hatchinson published the article "Fractal and self-similarity" which contained a theory of fractal building with the help of Iterated Function System (IFS).
     Four years later, appeared the article of Michael Barnsley and Stephan Demko, which defined a theory of IFS. In 1987, Barnsley founded Iterated System Company, the principal activity of which was creation of new algorithms and software using fractals.
     In 1988, he published the fundamental work "Fractals everywhere". The work contained the description of what is now known as the Collage Theorem, which underlies mathematical basis of fractal compression principles. If construction of IFS by an image is the inverse problem. For guide a long time it was considered insoluble.
     The first article about successes of Barnsley in the field of compression appeared in the BYTE magazine in 1988. It didn't describe a solution to the inverse problem, but it contained some images, which were compressed with 1:10000 ratio it was an absolutely stunning result. But, it was noted, that in spite of high-sounding titles ("The dark forest", "Montere coast", "The field of sunflowers") the images had in fact artificial nature. This fact caused many skeptic remarks, that were roused by Barnsley's statement: "the compression of an average image requires about 100 hours of human-aided processing at a powerful dual-processor workstation".
     In 1991, an information about possibility of fractal image compression was published for the first time and this caused a sensation. Michael Barnsley, one of the algorithm authors, asserted that a method of finding coefficients of a fractal, similar to the initial image has been developed.
     Fractals, beautiful images of dynamic systems, were used in computer graphics for building images of sky, leafs, mountaines, grass. A beautiful and, which is more important, natural-looking could be defined by just a number of coefficients. The idea to use fractals for compression appeared earlier, but it was assumed impossible to build an algorithm, which would find coefficients in acceptable time.
     So, in 1991, such an algorithm was found. Besides, his further declared a number of unique features of the new technology. Thus, at the time of unpacking, a fractal archiver allows to change the resolution of image without appearance of grain offect. And what is more, it unpacks not only images but also video much more quickly than its nearest competitor JPEG. As an example, a program was demonstrated, which showed a colour video film at a rate of 20 frames per second on a computer with a processor i386/33 MHz without any hardware support. Unlike JPEG the algorithm has an inherent ability to control a degree of loss in regions with maximum loss of quality. The image compression ratio is approximately equal to that of JPEG, but with some real images the compression ratio was as high as 10000:1! [3]
     In 1992, Arnaud Jacquin described and published a practical algorithm. This algorithm was very slow, but an interference of human was excluded completely. Now all well-known fractal compression algorithms are based on Jacquin's algorithm.
     In 1993, the first commercial product of Iterated System company appeared. In 1994, Yuval Fisher made the text of a research program publicly available. In July, 1995, the first conference devoted to fractal compression took place in Sweden.
     The disadvantage of fractal compression is long coding time. In 1999, D.C. Vatolin offered a solution to this problem in his article "Use of DCT for speeding up fractal image compression", where the developed algorithm was described in detail. [1]

     The objective of this work is the development of an algorithm for reducing the amount of calculation in fractal image compression. The practical value consists in the supposed reduction of computing time and power.