The "cold fusion" of compression is about to get very hot indeed.
In a vast warehouse somewhere in Denver, cable-TV giant TCI is conducting a test of interactive television. A video-on-demand service lets Denver residents select a movie from an onscreen listing of hundreds. Click on a title with your handheld remote, and a few minutes later, the flick plays on your screen. What kind of advanced computer setup does TCI engage for this futuristic application?
Sneaker net: A bell rings in the warehouse, and - no kidding - a clerk runs to fetch the video tape, which is placed in a standard VCR. The VCRUs output is then piped down the cable to your set.
Computers provide an obvious alternative to this ludicrous scenario - but the technology to accomplish the task hasn't been perfected. It would take a breakthrough in computer software - particularly in the field of compression technology - to make the digital storage and transmission of movies possible over cable lines, or even a phone line. That breakthrough, called "fractal compression," is about to happen.
Data compression is nothing new - it's used by most modems. If you download information from computer bulletin boards, you probably will be using some sort of utility, such as PKZip or StuffIt, to decompress the information. These utilities preserve all of the information in the original file - performing what's technically called "loss-less compression" - which is obviously important if you're compressing a program file or formatted text document.
Compression of graphic images, on the other hand, does not preserve all of a file's data. "Lossy compression" sacrifices precision in order to make the resulting file more compact. The assumption is that most people don't notice the loss of small details, especially if they're watching a video or looking at a newspaper-style photograph.
The standard method of lossy compression employs the JPEG technology, named for the Joint Photographic Experts Group, which first approved the standard. JPEG breaks down an image into a grid and uses a fairly simple mathematical formula to simplify the visual information contained in each square of the grid. This reduces the space needed to store the image, but degrades the quality of the image, often making it look blocky. A higher compression ratio equals greater image distortion.
Fractal compression could change the assumptions behind lossy and lossless compression. Invented in the 1980s by Michael Barnsley and Alan Sloan, two mathematicians at Georgia Tech, fractal compression is based on the discovery by Benoit Mandelbrot, an IBM scientist, that a hidden geometry exists in apparently random patterns of nature. Further studies of fractals revealed that images - from mountains to clouds to snowflakes - can be built from simple fractal patterns.
In fractal theory, the formula needed to create part of the structure can be used to build the entire structure. For example, the formula to create the pattern for a tiny piece of a fern frond can be used to create the entire fern leaf. Barnsley's discovery, described in his book _Fractals Everywhere_, was that the process could be used in reverse. Barnsley patented a technology that takes real-world images, analyzes them, and breaks them down into groups of fractals, which can be stored as a series of fractal instructions. These instructions take up much less space than the bit-mapped images used in jpeg technology.
It took Barnsley's company, Iterated Systems, almost six years to perfect the technique of fractal compression to the point where it was commercially viable. Ridicule met the company's initial claims that it could achieve compression ratios of 20,000 to 1 - the concept was dubbed the "cold fusion of compression." It wasn't until the Comdex computer show in Atlanta, Georgia, this past spring that the company was really taken seriously.
Fractal compression technology from Iterated Systems does indeed provide higher compression ratios and better image quality than anything else on the market. Photographic images can be compressed from 20:1 and 50:1 with no noticeable loss in resolution, and the company also claims that it can compress images with a ratio of more than 200:1 and maintain acceptable resolution. This is unmatched by jpeg or any other current technology and holds a tremendous amount of promise for delivering a wide range of graphics and multimedia technologies, from color fax transmission, to full- length movies on CD-ROM, to full-motion video over telephone lines.
Because fractal images are stored as mathematical formulas rather than as bit maps, they can be decompressed to resolutions that are higher or lower than those of the original. The ability to scale images without distortion is one of fractal compression's important advantages over jpeg. Fractal compression can also improve as you apply more processing power - that is, you can improve both the amount of compression as well as the quality of the image by just letting the system chew on the image longer. This upfront processing requirement is fractal compression's biggest drawback. On a typical microcomputer, it would take about 900 hours to compress a single hour of video. This underscores the fact that fractal compression is an asymmetric system - it takes ages to compress, but decompressing is quick. jpeg, on the other hand, is a symmetric compression system - it takes the same amount of time to compress and decompress a file. This makes jpeg more suitable for some applications, but makes fractal compression ideal for applications like video-on-demand.
Iterated also has stumbled on another revolutionary aspect of the technology called "fractal image enhancement" - a process that can actually add details missing from the uncompressed scanned image or digital file. The process works by calculating what information was probably left out of the image when it was originally broken down into a grid of pixels. This technique could also allow images to be greatly enlarged without showing pixel chunks or otherwise losing detail - think wall-sized HDTV.
Potentially, we'll also have the ability to store up to 100,000 images on a CD-ROM - a Holy Grail for the future makers of new CD-ROM players, devices that would resemble a VCR but accept CDs. Sony bought Columbia Pictures and TriStar, and Matsushita acquired MCA because it envisioned a booming market in cd players as music and movie videos become available in the new format.
Microsoft was so impressed with Iterated Systems's advances, it licensed the company's fractal compression technology for use in its groundbreaking Encarta CD-ROM, a multimedia encyclopedia that contains more than 10,000 color images. And the us Commerce Department recently granted the company $2 million to develop a low-cost fractal decompression chip that can keep pace with the frame rate of television. Iterated predicts that commercial versions of this chip will be available in 1995.
It may be possible to improve fractal compression technology even further by refining the formulas that recognize fractal patterns. There's a problem, though: Iterated Systems has obtained a patent on its compression technology, but is currently unwilling to reveal the exact nature of the algorithms (which are trade secrets) used in the process. This means that the technology will only advance at whatever rate a single company - Iterated - decides to set.