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.
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.
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 21/2/2012 Page Address: http://templarseries.fortunecity.com/pracfrac.html |