The cold fusion of image compression begins to get some respect

Suppose you could mathematically grow a picture from a seed. That is what image compression based on fractal geometry can accomplish. Derided as the “cold fusion of compression” by skeptics for years, the fractal alternative to the JPEG/MPEG Discrete Cosine Transform (DCT) method is now demanding that it be taken seriously.

Development of image compression technology based on fractal geometry is spearheaded by Iterated Systems, Inc., of Norcross, GA, founded in 1987 by two former Georgia Tech mathematicians, Michael Barnsley and Alan Sloan. This team discovered the underlying mathematics of fractal compression and has refined the algorithms to the point where Iterated Systems is now shipping MS-DOS and Windows fractal compression hardware and software for still images and motion video.

ADVANTAGES OF FRACTAL COMPRESSION

JPEG and MPEG approaches compress image data in part by breaking an image into 858 pixel tiles, then eliminating increasing amounts of the information contained in each tile. Fractal techniques, by contrast, reduce an image to a set of formulas, which, by repeated computations, can replicate the structure of the image without specifically reproducing the original pixel map. With the original fractal products the result is rather like an oil painting produced with daubs of color. Indeed, at very high compression ratios a fractal image can still resemble an impressionist painting more than a photograph.

While JPEG DCT methods have the prestige of standards committees behind them, fractal proponents claim several important advantages.

Decompression in software. Although fractal compression is relatively compute-intensive, decompression is comparatively quick and easy. Fractal decompression can now be accomplished completely in software. For still images, this does not even require a particularly fast computer. A ‘286 machine with VGA monitor will do the job. The fact that color photographic images stored in Fractal Image Format (FIF) can be displayed on desktop PCs without need to invest in hardware add-ons has obvious appeal.

With software decompression, fractal compression might become a market reality in CD-ROM and floppy disk titles before JPEG chips are common. Although JPEG decompression-in-software is becoming available too, Iterated Systems claims that fractal beats JPEG hands down in speed for software decompression.

Iterated claims that full motion video with software decompression is now also a reality. Motion video requires high-end PCs, and the products on the market do not yet produce NTSC quality, but fractal motion video is evolving rapidly. Interated claims that it will be able to achieve software-only decompression results that will be competitive with hardware-assisted MPEG or DVI chips. (See News, p. 13.)

Scalable, and resolution independent. Because they are regenerated from fractal formulas, rather than decoded from a representation of the pixel map as in JPEG, fractal images are scalable and resolution independent. In other words, the apparent quality of fractal images is independent of the resolution at which the image was scanned, and it is possible to rescale fractal images to fill the screen or to occupy just a small window. You can also zoom in infinitely on the fractal image without obvious loss of detail, although after a point this detail is mathematically predicted.

With appropriate software drivers, files in FIF can be displayed effectively on monitors of differing resolution — without file conversion. Since it is pixel-based, JPEG, by comparison, is inherently resolution dependent.

In theory, fractal images can also be printed at higher resolution than the original scanned images. Iterated Systems does not yet provide direct printer support, however, for the high-resolution output required for publishing applications.

For developers of multimedia titles, resolution independence also implies that fractal image files created today will be easier than JPEG/MPEG images to use across platforms and to view on the improved graphics displays of the future.

Better than JPEG at high rates. At higher compression ratios, fractal methods claim clear superiority over JPEG. (See illustration on p. 11.) If you must squeeze a 24-bit color, 6405400-resolution image into 10 KB (a 75:1 compression ratio,) then fractal compression, say its advocates, is the only way to go. And, Iterated Systems expects to squeeze that down to only 2.5 KB by June 1992. That would be a 300:1 compression ratio, but, supposedly, with quality acceptable for many applications.

Looking toward future evolution of compression technology, fractal proponents maintain that fractal compression becomes relatively more effective vs. JPEG/MPEG as the amount of raw image data goes beyond the current VGA or NTSC standards.

FRACTAL VS. DCT

Given the advantages of fractal techniques there are also several yardsticks by which compression technologies can be directly compared, including the amount of information lost, file compression ratios, compression speed, decompression speed and cost. At this point, fractal compression and JPEG are still in the same ballpark on these benchmarks –although fractal advocates have in the past claimed astronomical compression ratios based on best-case examples, such as 10,000:1.

As noted above, fractal seems to have the edge when high compression ratios and smallest possible file sizes are needed or when software decompression is desired.

Compressing to one-fifth of JPEG. Andy Sinden, managing director of Origin IQ, Ltd. in Surrey, England, has been involved in a number of projects using Iterated Systems’ fractal technology. He notes that Origin can compress fractal image files down to one-quarter or one-fifth the size of a JPEG file for applications such as transmitting police mugshots. Origin discovered that fractal images at 50:1, 80:1 and 120:1 compression were still usable for some purposes, while JPEG at those compression levels was not acceptable.

Origin is working with Panasonic Business Systems in the UK to develop a picture and document archiving system using fractal compression. Document images that are mostly text will be compressed in more conventional ways, however, since fractal compression is still not optimized for text.

Steve Johnson, sales manager at Kerridge Computer Co. in Berkshire, England, reports that his company switched from JPEG to fractal for a photographic image database product, Fotofile, that Kerridge is marketing. A JPEG file that required 60 KB would yield no better quality than a fractal file compressed to 15 KB or 20 KB, they found.

Johnson acknowledges that with current products fractal compression is slower than JPEG, and suggests that users might want to consider capturing the image as a Targa file and performing the compression overnight in batch mode. It takes three to four minutes to get satisfactory fractal compression of color photos, according to Johnson, if you want to end up with a 15 KB file.

At that small file size, Kerridge has been able to set up an effective color image database on a Novell Netware-based local area network, with the compressed color photos stored on a server and decompressed in software on PC workstations.

Fast machine, fast decompression. Slow fractal compression is not necessarily mirrored by slow decompression; fractal software-based decompression methods claim to compete with JPEG firmware-based ones. On a fast machine with ample RAM and an optimal video board, fractal decompression is claimed to be fast enough to be unnoticed. On a lower-end platform, the waiting time for image decompression can be quite apparent.

Both JPEG and fractal compression are “lossy” techniques that permit tradeoffs to be made between accuracy and data compression. (See Mediascape, p. 21.) In fractal compression, the operator of the compression system must set the desired compression time or target file size. The operator must also bear in mind what the resulting image quality will be on the display system showing the pictures.

Tweaks aren’t easy. Learning to tweak these settings takes some training and experience. Of course, for a batch consisting of similar images, the parameters can be set once and the scanning and compression process can then proceed without much thought.

JPEG/DCT and fractal compression products are still evolving, and it is too early to declare either a clear technical or market winner. Iterated claims that it has more “headroom” for further improvement in its algorithms than does JPEG — a contention that JPEG partisans hotly dispute.

PRODUCTS AND PLANS

For multimedia producers, Iterated Systems’ fractal compression is currently available on a choice of three boards ranging from $1,995 to $8,850. Developers’ software now shipping for use with the boards includes a DOS/still image/color package for $2,995, a Windows development kit for $3,995 and a DOS/motion video kit for $4,990.

The “Floppy Book.” For electronic publishers, a fractal image book-on-disk format puts 100 color images (at 10 KB each) and 100 pages of text on a floppy disk. Iterated developed a prototype of such a “Floppy Book” in cooperation with Jones and Bartlett Publishers. The Floppy Book contains several different kinds of images, including illustrations from a children’s book, computer graphics, synthesized fractal patterns and natural images fractally encoded.

Based on her experience with the first Floppy Book, Alice Peters of Jones and Bartlett sees an important role for fractal compression in permitting publishers to reproduce color pictures inexpensively, as floppy-based supplements to printed works as well as in the form of self-contained Floppy Books.

Iterated Systems and Jones and Bartlett will cooperate on another fractal product, a clip art library of 250 color photos (on three floppy disks) for use in Windows-based presentations and Windows publishing software. The package will include fractal decompression and a conversion utility to transform FIF pictures to raster formats such as TIFF and Targa.

100,000 images on a CD-ROM. If 100 high-quality color images on a floppy disk is insufficient for your needs, consider that CD-ROM will hold 60,000-100,000 fractally compressed color slides on one disc.

Now that fractal techniques have permitted decompression via software of highly compressed photographic images, when will fractal compression be possible without a fractal encoder board? Iterated says that the answer is “soon.” It expects that “fractal for the masses” in the form of a software fractal compression module will be available in the first quarter of 1992. Also, look for important advances during 1992 in the application of fractal geometry to motion video and gray-scale images, and progress in moving fractal hardware to the single-chip level.

IS FRACTAL FOR REAL?

Although the actual nuts and bolts of how it all works are still something of a secret, the apparent magic that fractal compression/decompression can accomplish in shrinking still and motion pictures down to manageable size seems real enough. It is not the panacea that its more partisan advocates would have you believe. Nor is it the “right” answer for every application. But it does appear to be both real and useful. We are going to be very interested in seeing how Iterated does in extending and refining the technology over the coming year.

WHAT’S A FRACTAL, ANYWAY?

Fractal geometry studies a class of geometric patterns, fractals, that are generated from simple formulas. Fractals are produced by starting with an initial shape and infinitely adding new shapes created by repeated simple transformations, such as shrink-move-rotate. Fractal models have been widely used in recent years to study phenomena as diverse as air flow and commodity prices. Fractal concepts have become an important tool for the analysis of nonlinear processes (see James Gleick, Chaos: Making a New Science, 1987) and for describing biological as well as physical structures.

Fractal patterns exhibit the peculiar property of looking similar at whatever scale they are viewed. For example, fractal snowflakes can be generated by repeatedly repositioning and shrinking a triangle. Such “snowflakes” have edges that contain shapes that are miniature replicas of the larger snowflake pattern. On closer inspection, these small snowflakes have snowflake shapes on their edges … ad infinitum. At any one scale, the snowflakes get smaller until they become dots, but if you change the scale and zoom in on them, there they are again.

Benoit Mandelbrot, the inventor of fractal geometry and coiner of the term “fractal,” showed in The Fractal Geometry of Nature (1977) that remarkably natural-looking landscapes, clouds, vegetation, galaxies, etc. could be synthesized as computer graphics by using fractal formulas. These artificial shapes generated by fractal geometry can mimic the irregularity of nature so well that they have been used as “scenery” in Hollywood films.

HOW FRACTAL COMPRESSION WORKS

In the key discovery related to fractal compression, Michael Barnsley demonstrated in the mid-1980s that any image can be imitated by a set of fractal patterns similar to the infinitely shrinking snowflakes described above. (See Michael Barnsley’s textbook, Fractals Everywhere, 1988.)

Since this breakthrough in the mid-1980s, called the Fractal Transform, Barnsley and his colleagues have developed and continued to improve computer algorithms that can rapidly and automatically translate pictures into fractal formulas. Not all of these procedures have yet been fully revealed by the developers, but it is known that the program analyzes a picture into collections of shapes that resemble each other, except for location, size and orientation. Each such collection of similar shapes can be precisely described as a fractal formula with certain parameters. Barnsley et al. have also developed programs that can regenerate images efficiently from those fractal formulas.

Measured in bytes, fractal formulas turn out to be a much more compact recipe for reproducing a picture than a raster bit map; hence, fractal encoding is fractal compression.

The redundancy that fractal compression depends on is called “affine redundancy” (as in “affinity”), the surprising similarity of shapes that are apparently scattered throughout any image. (See above illustration.) An image that has low “affine redundancy” can be hard to compress, yielding a relatively large file, but, with fractal techniques, this can be compensated for by allowing more time for the compression programs to run. The time it takes to decompress the image is not affected by this size/time tradeoff during the compression stage.

The encoding and decoding algorithms are not simply the same procedures run backwards. The process, in other words, is “asymmetric.” In the current implementation, the encoding stage takes much longer to accomplish than the decoding stage. Fractal encoding, at this writing, still requires a hardware fractal compression board and takes several seconds to several minutes per still image or one second per video frame. As noted above, decoding of both still and motion video is accomplished in software alone.

Bernard Banet