|
|
From "Advances
in Fractal Compression for Multimedia Applications" Note : this writing has a few problems. Shortly after Mandelbrot’s work, mathematicians searched for a framework underlying fractal geometry. As John Hutchinson demonstrated in 1981, it is the branch of mathematics known as Iterated Function Theory. Later in the decade Michael Barnsley authored Fractals Everywhere, another keystone work. The book presents the mathematics of Iterated Functions Systems (IFSs), and develops a result known as the Collage Theorem. The Collage Theorem states what conditions an Iterated Function System must satisfy in order to represent an image. Image to an Iterated Function System that can generate the original (or at least closely resemble it), is known as the inverse problem. In its general form, the inverse problem remains unsolved. According to the testimony in Barnsley’s colleague Alan Sloan was the first to see the potential of IFS theory for image compression. Together they applied for (and were later granted) a software patent for the purpose of commercializing technology based upon their work. At that time, however, fractal compression software required excessive human intervention and the method described in the first patent failed to become viable. In search of something practical, Arnaud Jacquin, one of Barnsley’s students, arrived at a modified scheme for representing images using Partitioned Iterated Function Systems (PIFSs). In his PhD thesis, Jacquin developed the necessary mathematical foundations and implemented the new approach in software, a description of which appears in his landmark 1992 paper "Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations". The algorithm was not sophisticated, and was computationally expensive, but it was fully automatic. All contemporary fractal image compression programs are based upon Jacquin’s breakthrough. An elegant way of introducing the notion of Iterated Functions Systems is by the metaphor of a Multiple Reduction Copying Machine. A MRCM is imagined to be a regular copying machine except that:
Figure 2 depicts this process for Sierpinski’s Triangle one of the simplest (and most well known) Iterated Function Systems. It is comprised of three component functions ("lenses"), each of which shrinks the input image by one half and translates it to a new position. This contractive property is crucial, for it guarantees convergence of the iterative process. Because all initial images are "drawn towards" the same final result, it is variously referred to as the attractor of the IFS, or the fixed point image. Mathematically, each reducing lens is represented as a contractive affine transformation, w i , that acts to scale, rotate, shear, and translate a copy of the input image, i.e.
so that a point in the initial image (x,y) will transform to new coordinates (x', y').
The symbols a ... f denote the transform coefficients. The three transforms that produce the Sierpinski Triangle of Figure 2 are:
Here, the first four coefficients (a ... d) are identical but this need not be the case in general. Just so long as the determinant of each transform is strictly less than one,
then the IFS as a whole, W, will converge to the attractor image Iw w from any initial image I o .
As Figure 2 indicates, and equation (5) implies, each application of W produces detail at progressively finer levels as the limit is approached. Indeed, the image possess geometric self-similarity between different scales. This is why IFSs are said to generate fractal images. The promise of employing fractals for image compression, then, rests on four suppositions.
|
