gital communica
tions technologies become more widespread, how can Web developers help traditional modems sip from this fire hose of multimedia information?
One answer might be new compression algorithms that use fractal and wavelet technologies, which are specifically suited to still images and video. They could bring us closer to fast-loading multimedia Web pages. Fractals, wavelets, and a combination of the two offer shorter download times and more tightly compressed files than what GIF, JPEG, and MPEG offer. The trade-off? It takes a comparatively long time to compress files with fractals and wavelets before you send them over the Web. Also, fractal and wavelet files are unreadable unless your audience has a special viewer to decompress the files. Nevertheless, fractals and wavelets represent a step forward from GIF and JPEG files, which use lossless Lempel-Ziv-Welch (LZW) and lossy algorithms, respectively.
Fractals in Action
This is the essence of fractal compression: Rathe
r than transmit the image, you transmit the much-smaller algorithm parameters for creating that image. To understand how this algorithm is created, consider an equilateral triangle. On each of its three sides, erect equilateral triangles one-third the size of the original. On each of the smaller triangle sides, erect equilateral triangles one-third their size. Continue this process an infinite number of times, or until you can't tell one iteration from the next. You will end up with something resembling a snowflake (called a Koch snowflake) that is a fractal: Its dimension is not a whole number but lies between 1 and 2.
This illustration exhibits two of the main features of fractals: self-similarity and recursion. Self-similarity because if you expand any part of the snowflake, it looks the same: namely, little triangles constructed on bigger triangles. Recursion because you are repeating the same algorithm over and over to create it.
Now suppose someone sees your snowflake, decides to make it the com
pany logo, and asks you to put it on your Web site. You could just make a GIF of the image itself and put that image on the site. Or you could put the algorithm that created the image on the site and distribute viewer programs so that when someone accesses it, the algorithm generates the image on the viewer's machine. Clearly the algorithm parameters would take up far less space than the GIF.
The real "aha!" for fractals comes when you realize that you can turn the original triangle into a triangle of different size and orientation simply by turning, stretching, and expanding or contracting the original (mathematicians call this an
affine transformation
). In other words, rather than needing detailed information about the second triangle, you need only its turning, stretching, and expansion or contraction parameters. You can compress a picture into a list of these parameters. To decompress the image, you simply take the parameters, plug them into the algorithm, and generate the image again.
Th
e big plus here is speed. The parameters arrive nearly instantaneously, and the picture begins generating immediately. No more coffee breaks while you wait for a jumbo GIF to waddle on down.
You can also zoom in or out on fractal images to examine details. Unlike other formats that clearly show their dots or blocks as you blow them up, the fractal image is
resolution-independent
, so an expanded version of the image is as sharp as a tiny image. There is one proviso. A Web site manager may well limit image resolution; expanding even a fractal image will make it look dotty and blocky.
Sharp Images
Fractal images differ from, say, GIFs in several ways. First, GIFs start out blurry and get sharper as more of the file downloads. Fractal images start out sharp and stay sharp. This is important for Web surfers. You don't have to waste download time to see the image clearly enough to decide if you're interested in it or not.
Fractal compression can range from 20:1
to 50:1, depending on the complexity of the image. Since fractals work by self-similarity, the more complex the image, the less compression is possible.
One downside to fractal compression is the length of time (sometimes 5 minutes for a 4- by 3-inch image) and considerable processing power required to shrink images with fractal technology. Therefore, fractal compression is useful for still images and prerecorded video, but it isn't practical for live video.
Another problem is that fractal compression is lossy compression: The original and the decompressed image will not match pixel by pixel. However, this is important only when creating perfect compressed archives of images, which is not typically important for the Web, where the images will look good enough.
To create a fractal-compression algorithm for your Web graphics, you'll need a commercial fractal-compression tool, such as Fractal Imager from Iterated Systems ($40 to download, $70 to buy the CD-ROM). With Iterated's compression process, y
ou first break down the original image into regions with similar features, using standard edge detection, texture variation, and other algorithms. For example, if you were compressing a photo of a person's face, some regions might contain just skin, some regions might contain just hair, and so forth. You then fractally compress each of these regions by expressing each part of the region as a turned, stretched, and expanded/contracted version of another part. You record the regions, the "standard" image for each region, and the parameters to generate all the other images in the region. This takes time and is clearly an off-line, non-real-time process.
But the results are striking. You can compress some images up to 250 times smaller than the original, and the images can load up to four times faster over the Internet. The resulting image looks nearly identical to the original.
Fractal Imager turns still images into fractal image format (FIF) files. You can then place these images on your Web site just a
s you would a GIF or a JPEG image. To view them, however, your guest will need Fractal Viewer, which Iterated distributes for free.
Wavelet Compression
Another important compression option for the Web is wavelet technology, which works similarly to Fourier analysis. Fourier analysis, used extensively in signal analysis, represents an input signal as a combination of simple sine and cosine basis functions. If the input signal were a single frequency, the output would be a single number, namely the coefficient of the particular sine or cosine function corresponding to that frequency. If the input had several frequencies present, the result would be several coefficients.
Fourier analysis works best for continuous input and repetitive patterns. Unfortunately, most inputs are neither continuous nor repetitive, resulting in very large sets of coefficients. For many real-world applications, like compressing graphics, Fourier analysis requires too many coefficients to be practical for rep
resenting an image.
Wavelets also represent input images with coefficients of basis functions. However, the basis functions for wavelets are much more complicated than the simple sines and cosines of Fourier analysis. Plus, the wavelet basis functions can effectively represent noncontinuous and nonrepetitive inputs, like the edges and other features of real-world images. Thus, wavelets can represent real-world images using only a small set of coefficients, resulting in excellent compression. To decompress the image, you simply use those coefficients with the wavelet basis functions to generate the image.
But wavelet compression shares problems similar to fractal compression: Lengthy compression time on the front end and use of lossy techniques. Also, wavelet compression lacks fractal compression's resolution independence. When you expand wavelet-compressed images, you get artifacts, but they'll be imperceptible in most cases.
OLiVR (for On Line Interactive Virtual Reality), a company that has deve
loped a new architecture specifically for streaming media, uses a wavelet/fractal combination, taking advantage of each technology's scalability and resolution features. OLiVR's technology works for both still images and video.
Video over the Web
Compressing video is a lot like compressing a series of still images. However, video offers even more compression opportunities. Images may not change much from frame to frame, and you may need to compress only the differences in succeeding frames. This clearly works better for some applications, like an unmoving camera recording a university lecture, than it does for others, like a Hollywood action movie.
The advantage of fractal or wavelet compression is streaming video: The clip starts playing as soon as you click on it. With ClearFusion, Iterated's streaming video viewer, you can watch video as it downloads into a box of approximately 2 by 3 inches, but movements are jerky on a 28.8-Kbps modem connection. Any associated audio will be
of acceptable quality. Even if you prefer to download the whole file before viewing, the size of the file is far smaller.
For example, a video clip that would be about 1200 KB in MPEG format is only 290 KB in fractal format. In addition to fractals used to compress Web-page video, Iterated expects to see the technology used for entertainment and corporate training applications.
When OLiVR movies begin downloading, you can see what the picture is with less than 5 percent of the file present. Detail fills in as the remainder of the file arrives. You can rotate the image and zoom in and out on the quarter-screen images. These seem ideal to show products: For example, by rotating an image of a disk drive, I could check out what ports it had on the back.
VDOnet's VDOLive also uses wavelet compression for streaming video. At least one major news organization, CBS News, uses VDOLive to broadcast its Up-To-The-Minute news snippets on the Web (
see the screen
).
Coming at You
As the Web moves beyond text delivery to becoming a viable multimedia medium, we need better ways to compress still images and video. Otherwise, all that stuff gets bogged down and can't traverse modem connections quickly enough. By sending descriptions of these images, fractals and wavelets use today's thin pipes efficiently to take us a step closer to bringing the Web to life.
Where to Find
Iterated Systems
Atlanta, GA
Phone: (404) 264-8000
Internet:
http://www.iterated.com
Walking, Talking Web
