Practical Fractal

Mandelbrot's equations compress digital images

When IBM researcher Benoit B. Mandelbrot published The Fractal Geometry of Nature a decade ago, few imagined that the beautiful, infinitely detailed designs he called Fractals might one day also improve television reception and help make pictures a part of everyday computing.Two who did were Michael F. Barnsley and Alan D. Sloan, mathematicians at the Georgia Institute of Technology. They reasoned that because images of the real world tend to consist of many complex patterns that recur at various sizes- In other words, fractals- there ought to be a way to translate pictures into Fractal equations. Images so coded would require fewer data and thus less disk space to store and less time to transmit.

By 1987 the researchers had worked out enough details to patent their idea, garner $500,000 in start-up capital from Norwegian investors and form Iterated Systems in Norcross, Ga.But turning potential to profit proved difficult. Iterated found a formidable competitor in JPEG, an image compression technique developed by the International Standards Organization's Joint photographic Experts Group. JPEG uses a well-understood mathematical procedure, the discrete cosine transform, to compress files by 90 to 95 percent-equivalent to compression ratios of 10:1 to 20:1. JPEG enjoys another advantage: because it is an industry standard, it is free.

The mathematics behind fractal compression, on the other hand, has only recently left the crib. "Relatively speaking,very little research has been done to date," Barnsley admits. "Two or three years ago, when people looked at my pictures, they said, This stuff looks terrible; it isn't going to work-you're dreaming."But we bet on continual dramatic improvement, and we've seen it."

Indeed, fractal compression has at last begun to challenge JPEG in the three areas that matter : speed, quality and strength. To a certain extent, the three are mutually exclusive-stronger compression yields a smaller image file but takes longer and creates more artifacts. JPEG takes as long to decompress an image as to compress it, and it produces blocky "pixelation" as compression ratios rise above about 20:1.

Iterated takes a different tack. Its algorithm works by treating an image as a jigsaw puzzle composed of many overlapping pieces, some of which are similar. The software takes each piece and, using a fractal formula, transforms its shape, size and colour until it matches another part of the picture. To do this for each piece of the puzzle takes some time; actual compression is quite slow. But it produces a much smaller image file which contains just the numbers needed to specify the mathematical relations between the pieces, and not those needed to actually draw each piece.

This approach has some unique advantages. Reconstructing the image from the numbers is relatively quick work: Iterated's video software can decompress tens of images each second without any special hardware. Quality depends on the accuracy of the numbers; giving the compression algorithm more time or a dedicated computer processor thus yields better pictures. And the artifacts generated at higher compression ratios add an impressionistic blur, rather than blockiness, to the image. What is more, because fractal images are encoded by equations they have no inherent size-an attractive quality to publishers who want their products to work as well on a laptop screen as on a 21 -inch monitor. Barnsley expects that in the long term, such resolution independence will prove irresistible. So far, however, most of Iterated's customers have chosen fractal compression for its brute power. Microsoft licensed Iterated's software to compress the nearly 10,000 pictures it put on Encarta, its CD-ROM encyclopaedia, because "fractal compression produced much more aesthetically pleasing results than JPEG at high compression ratios," says Jay Gibson, who manages the project. Racal Radio in Reading, England, put fractal compression into its PICTOR system for similar reasons." We wanted to send data files over high-frequency radio, which is currently limited to some hundreds of bits per second," explains Peter W Goddard, Racal's marketing manager. " Using fractals, we were able to get a 768-kilobyte picture file down to 10 kilobytes or lower-small enough to transmit in two to three minutes."

FRACTAL COMPRESSION technique patented by Iterated Systems reduces data by translating a picture into fractal equations. The higher the compression, the more the image is distorted. Clockwise from top left: King of spades at original, 2.4-megabyte size, then compressed, 129, 63 and 31 kilobytes.

Other companies are attempting even higher compression ratios. Kalman Technologies used fractal compression to add video mail to its HydraWorks communications software." We found compression ratios of about 600: 1 , which is what we need to send video mail cost effectively across public telephone lines," says company president Steve Swift. Tayson Information president Peter A. Richardson says his company routinely obtained 100:1 compression when it added fractals to its education software, used by the University of Guelph in Ontario to create more than 500 undergraduate course modules. We chose fractals because JPEG is pushing the limit of its capabilities," Richardson says. "Fractals can go and go and go."

How far they can go is a matter of some dispute. Barnsley has claimed "effective" compression ratios of up to 2,500:1. But " sometimes people expand the image and then claim compression relative to the expanded image," notes Michael F. Shlesinger, who as director of physics at the Office of Naval Research which funded Barnsley's early research. "It's just a trick." That trick has some mathematicians crying fraud and heaping scorn on Barnsley. Shlesinger attributes the controversy to a conflict of personalities. "Barnsley stopped playing the role of professor and started playing the role of entrepreneur," he explains. He'll come to meetings and give a sales pitch for 45 minutes instead of a mathematics talk. This drives mathematicians up the wall."

Academic ire does not seem to be hindering Iterated's business, however. Five years and $18 million after its inception, Iterated finally started making money. "At the end of last year, we passed breakeven, and cash revenues have increased by over 10 percent a month each of the past six months," boasts Louisa Anson, a vice president. "Our goal is to go public in 1995." The company has grown to more than 56 employees (32 of whom work in research and development), offers half a dozen or so image compression products and is working to establish a foothold in the nascent computer video market.

Video will pose a greater challenge than still-image compression. The current video compression standard recently finalised by the Motion picture Experts Group (MPEG) is well entrenched and near a second version. AT&T , Microsoft, Philips and numerous other giants have announced plans to sell MPEG-based video decoders within the year.

Barnsley cares little. If nothing else, he maintains, the resolution independence of fractals will triumph in the end. Iterated's long-term goal is to produce MPEG-compatible chips that use fractals to improve television reception and from there push into broadcasting. To that end, the company sought and received a $2-million grant from the National Institute of Standards and Technology to help it develop a fractal compression chip for high-definition television. "Once we get the reception circuitry in place, we're in a position to offer better transmission as well," Barnsley says. "It's kind of a Trojan-horse strategy."

In the meantime, Barnsley sees a niche in CD-ROM video for computers.MPEG requires special decompression chips to play video. Iterated has teamed up with TMM in Thousand Oaks, Calif., to develop software that plays broadcast- quality video straight from a CD-ROM. We're going out full blast at Comdex [the computer trade show] with video," Barnsley beams. "By this fall we'll be a major player in the desktop computer video market." But first Barnsley and his mathematicians must finish their homework.

-W. Wayt Gibbs

Fractals are beautiful and complex geometric structures that occur naturally around us - the fronds of a fern plant are a good example. The shape of each frond is replicated in the smaller fronds, and those in turn are made of even smaller fronds of the same shape. The same pattern occurs from the visible to the invisible.

These patterns can be turned into mathematical equations, which can be used to convey information like music or pictures in a condensed from that is very efficient. These fractal equations are being used to revolutionise the way images are being stored and manipulated.

Most images that you see on the internet are stored digitally using jpeg files. These images are made up of small squares or pixels, so when it is enlarged it becomes blocky and poor quality. This has made multiple scans a necessity for many printing jobs - slowing down the process and requiring extra storage space.

The new software converts digital images into fractal formulas. Just as fractal images have repeating patterns, so do real pictures. The fractal formula only stores the parts of the image that are different so the amount of data stored is much smaller. But when reconstructing the image, the fractal formula is able to fill in the gaps. This means that the image can be enlarged to any desired size and resolution - from postage stamp size to outdoor billboards.

Scientific American Jul1993 File Info: Created Updated 12/7/2001 Page Address: http://www.fortunecity.com/emachines/e11/86/pracfrac.html