FRACTAL IMAGE COMPRESSION

INTRODUCTION

With the recent rapid growth of multimedia applications, image compression techniques have become a very important subject. Two main motivations are behind image compression - the efficient transmission and storage of digital data.

Uncompressed (bit-mapped) graphic files are often huge. A 512 pixels by 512 pixels (not very high resolution by today's standard) grey-scale image takes up over 260,000 bytes, much more if the image is in color. On the other hand, the network bandwidth of an average computer is very small in comparison. At 28800 bps (bits per second), which is the highest reliable rate for data transmission over standard telephone lines, a PC will need over a minute to send or receive the image described above, without color. With the use of image compression, however, the transmission time is cut down to a fraction of the time previously required.

The large file sizes also cause problem with data storage. A CD- ROM disc, which is the typical graphic storage media, holds about 650+ megabytes of data. While this is more than sufficient to store text (a well-known example is that the entire text of Encyclopedia Britannica can be stored in one disc with space to spare), it falls far short of the requirement of today's multimedia applications, namely the storage of hundreds of color images, video clips, and sound tracks along side of text files. Without data compression in general, and image compression (both for still images and full-motion video), it will be impossible to fit all those graphic and sound files typical of current multimedia titles in one or a few CDs.

IMAGE COMPRESSION

There are two general categories of compression methods - lossless and lossy methods. A lossless method will produce an image that, when decompressed, is identical to the original image down to the last bit. A lossy method, on the other hand, will produce an image that closely resembles but is not an exact duplicate of the original image. The major drawback of lossless methods is that they cannot achieve very high compression ratios (usually about 2 to 1). Hence, for image compression applications where the input files are usually measured in megabytes, and where the losses of very minor graphic details are not critical, lossy methods are mostly used . (For certain applications, such as the compression of text files or executable codes, lossless compression is a necessity, of course.)

One of the lossy image compression methods currently available is the method of fractal image compression, developed by Michael Barnsley and his associates. The method is a proprietary technology of Iterated Systems, Inc., a firm co-founded by Barnsley. Other examples of lossy methods are JPEG (the Joint Photographic Experts Group standard), and GIF (an image compression standard originally developed by CompuServe on-line service).

Image compression methods can also be classified as either symmetrical or asymmetrical. For symmetrical methods, the compression and the decompression processes take roughly the same amount of time/effort. JPEG is one example of such methods. Fractal image compression, on the other hand, is an example of asymmetrical methods. Asymmetric methods take more time/effort compressing an image than decompressing it. The idea is to do most of the work during the compression, thus creating an output file that can be decompressed very quickly.

BASIC CONCEPTS

An affine transformation in Rⁿ is a function consisting of a linear transformation and a translation in Rⁿ. Affine transformations in R², for example, are of the form


             W(x,y) = (ax+by+e,cx+dy+f).

Where the parameters a,b,c, and d form the linear part, which determines the rotation, skew, and scaling; and the parameters e and f are the translation distances in the x and y directions, respectively.

For our purpose, only contractive affine transformations are considered. An affine map is said to be contractive if its contractivity factor s is less than 1, i.e. it "reduces" the size of the domain images.

Given a finite collection of contractive affine maps W₁, W₂,...,W_n, this collection forms an iterated functions system (IFS). If B is a compact, nonempty subset of Rⁿ, then the map


                   W(B) = U W_i(B)

is a contractive map on H, the (complete) metric space of compact sets in Rⁿ. W has a unique fixed point in H, say A. Then A is a compact subset of Rⁿ, and is called the attractor of W.

A collage of B is an IFS W such that W(B) = U W_i(B) is approximately equal to B. The Collage Theorem (Barnsley, 1985) states that if an IFS gives a collage of B which is a very good approximation of B (i.e. B and W(B) are very close in Hausdorff distance), then the attractor will be very close to (looks like) the original set B. See [2] and [5] for more detail.

In this paper the word "image" is used very loosely, it means any picture or graphic (in digital form). It means the same as what Barnsley often calls the support of an image, which he means the projection of a real world image into the Euclidean Plane R², e.g. a photograph is the support of the image it contains.

FRACTAL IMAGE COMPRESSION

Given an original image (in digital, bit-mapped format), say B (here we assume B is nonempty, otherwise there is nothing to be compressed), with a resolution of m by n pixels, the image file consists of a header followed by m n cells of intensity data, one for each pixel. Given the resolution, the spatial coordinates of each pixel are implied (eg. the first n cells represent the top most row of pixels, starting from left, etc.). The size of the cell associated with each pixel varies, depending on the type of the image as described below.

The simplest case is a strictly black-and-white image (such as a weekday newspaper comic strip). Each pixel will have only one bit of data - 0 for white and 1 for black, say. Thus it is a purely two-dimensional set, as the part we are interested in is just the collection of pixels whose bit contains 1, so we only need to keep track of their two implied spatial coordinates. Therefore the image can be considered as a (compact) subset of R². If B is a grey- scale image, it can be considered as a (compact) subset of R³ - the two spatial dimensions and a third one for the intensity of the grey-scale (which is usually between 0 and 255, so each pixel has one byte of associated data). As might be expected, color images require more effort. If B is a color image, then its bit-mapped file can be considered as a (compact) subset of R⁵. In addition to the two spatial dimensions, there are three dimensions for the three RGB color parameters. Here we shall take a brief look at how the color image is displayed on a TV or monitor screen.

The RGB (Red, Green, Blue) system is based on the fact that red, green, and blue form a set of (additive) primary colors for light. By varying the intensity of each of the three colors, one can duplicate any color perceivable by the eyes. For computer applications, each light's intensity is usually divided into 256 discrete levels, numbered 0 to 255. Hence each parameter for RGB is kept in one byte of memory. This gives 256³ (over 16 million) different possible composite colors, from total black (RGB=[0,0,0], i.e. no light at all) to bright white (RGB=[255,255,255], saturation of all three colored light). A short discussion of the RGB system can be found in [5].

In his research, Barnsley observed that real-world images often are rich in affine redundancy. This means that, with a suitable IFS, large parts of an image are similar to finer parts of the same image. This observation and the Collage Theorem were the motivations of the fractal image compression algorithm.

The fractal image compression first partitions the original image into nonoverlapping domain regions (they can be any size or shape). Then a collection of possible range regions is defined. The range regions can overlap and need not cover the entire image, but must be larger than the domain regions, For each domain region the algorithm then searches for a suitable range region that, when applied with an appropriate affine transformation, very closely resembles the domain region. Afterward, a FIF (Fractal Image Format) file is generated for the image. This file contains information on the choice of domain regions, and the list of affine coefficients (i.e. the entries of the transformation matrix) of all associated affine transformations. So all the pixels' data in a given region are compressed into a small set of entries of the transform matrix, with each entry, corresponding to an integer between 0 and 255, taking up one byte.

This process is independent of the resolution of the original image. The output graphic will look like the original at any resolution, since the compressor has found an IFS whose attractor replicates the original one (i.e. a set of equations describing the original image). Of course, the process takes a lot of work, especially during the search for the suitable range regions. But once the compression is done, the FIF file can be decompressed very quickly. Thus, fractal image compression is asymmetrical. The practical implementations of a fractal compressor offer different levels of compression. The lower levels have more relaxed search criteria to cut down processing time, but with the loss of more detail. The higher levels give very good detail, but takes a long time to process each image. [1]

In [6], it is shown in detail how an algorithm called Chaos Games is used to construct an IFS which recreates a fractal replica of a leaf.

DECOMPRESSION

To decompress an image, the compressor first allocates two memory buffers of equal size, with arbitrary initial content. The iterations then begin, with buffer 1 the range image and buffer 2 the domain image. The domain image is partitioned into domain regions as specified in the FIF file. For each domain region, its associated range region is located in the range image. Then the corresponding affine map is applied to the content of the range region, pulling the content toward the map's attractor. Since each of the affine maps is contractive, the range region is contracted by the transformation. This is the reason that the range regions are required to be larger than the domain regions during compression.

For the next iteration, the roles of the domain image and range image are switched. The process of mapping the range regions (now in buffer 2) to their respective domain regions (in buffer 1) is repeated, using the prescribed affine transformations. Then the entire step is repeated again and again, with the content of buffer 1 mapped to buffer 2, then vice versa. At every step, the content is pulled ever closer to the attractor of the IFS which forms a collage of the original image. Eventually the differences between the two images become very small, and the content of the first buffer is the output decompressed image. [1]

FRACTAL IMAGE COMPRESSION vs. JPEG

Since JPEG is currently the most widely used image compression method, it is natural to compare any competing method to it. The underlying compression technique in JPEG standard is DCT (Discrete Cosine Transform). DCT breaks an image into small blocks, usually 8 pixels by 8 pixels, then it converts the intensity data of the pixels into their frequency space equivalents. The result is a set of 64 cosine functions with various amplitudes. The compression is done by discarding higher frequency cosine terms (since, in a typical image, most of the visual information is concentrated in lower frequency terms). This truncation of terms causes the loss of fine (hopefully not readily noticeable) detail. By varying the truncation frequency, one can make the trade-off between high compression ratio and loss of detail. JPEG, as mentioned before, is a symmetrical compression method.

If the image to be compressed contains sharp edges, which are mapped to higher frequency range, then the DCT-processed file will have very noticeable ripples spreading from the edges. Furthermore, the JPEG method is resolution dependent. Higher resolution graphics have more pixels than the same images at lower resolution, hence they partition into more 8 by 8 blocks of pixels. The result is either longer compression and decompression times, or, if one choose to fix the compression and decompression times by increasing the size of the blocks (so the 64 cosine functions will now represent more than 64 pixels), the output graphics will be very blocky due to pixel replication. [1]

Fractal image compression does not suffer from either of the above problems. Furthermore, the fractal method has the benefit of faster decompression speed, having done most of the computation during the compression step, while giving equal or better compression ratio. These advantages mean that fractal image compression is well suited for applications requiring fast access to high-quality images (the most notable of applications using fractal compression is Microsoft's best-selling Encarta multimedia encyclopedia). However, fractal image compression is not without its limitations. For example, its lengthy compression step will preclude it from being used in applications where it is essential to be able to send out the compressed images with minimal delay, such as live broadcast of video over a network, tele-conferencing, and videophone.

REFERENCES

1. Anson, L.F., "Fractal Image Compression", BYTE, Oct. 1993, p. 195-202.
2. Barnsley, M.F., Fractal Everywhere, 2nd ed., Academic Press, San Diego, 1993.
3. Barnsley, M.F., "Fractal Image Compression", Notices of the AMS, June 1996, p. 657-662.
4. Barnsley, M.F., and Demko, S., "Iterated function systems and the global construction of fractals", Proc. R. Soc. London, A 399 (1985), p. 243-275.
5. Barnsley, M.F., and Hurd, L.P., Fractal Image Compression, AK Peters, Ltd., Wellesley, Massachusetts, 1992.
6. Barnsley, M.F., and Sloan, A.D.,"A better way to compress images", BYTE, January 1988, p. 215-218.
7. Bryan, J. "Compression Scoreboard", BYTE, May 1995, p. 107-112.