Company gets NIST grant, shows fractal image enhancement, compression

Last month was a big one for Iterated Systems Inc. of Norcross, GA. The company, whose cofounder discovered the Fractal Transform technique for describing digital images in 1988, received a $2 million research and development grant from the Advanced Technology Program of the U.S. Department of Commerce and the National Institute of Standards and Technology (NIST), and also released its first still-image, software-only fractal compression package.

The $2 million is earmarked for development of a “very low-cost” fractal decompression chip that is fast enough to keep up with the frame rate of television. Iterated expects commercial versions of the resulting chip to be available in early 1995. In March 1993, Iterated plans to produce a low-cost fractal decompression chip that can be used to extract full-motion video from CD-ROM. Between now and the fall of 1993, Iterated also expects to market two new fractal compression chips, paired with decompression software.

Compression software ships. In early April, Iterated released its first software package for fractal compression, called Images Incorporated, and demonstrated it at Windows World in Chicago. While slower than Iterated’s hardware compression boards, the software incorporates Iterated’s most advanced compression and decompression algorithms and is priced to encourage wide experimentation by users. It runs under Windows, with a list price of $299.

The new Images Incorporated package can also convert images to and from a variety of image file formats and provides a number of image editing tools plus a clip art library of 250 fractally compressed images for desktop publishing use. A related developer’s kit for linking software-compressed and decompressed fractal images to DOS and Windows applications is expected to be available by the end of April 1993.

A SURPRISE: IT ENHANCES IMAGES TOO

The most important news, though, is that Images Incorporated claims a surprising and highly significant new capability for its fractal encoding technology: image enhancement. Former math professor Michael Barnsley, chairman of Iterated, showed fractal enhancement at work in Chicago, restoring to a scanned image detail and sharpness that was assumed lost when the picture was originally digitized.

Iterated has been claiming that its fractal encoding processes can compress still image and motion video data into fewer bytes than competing technologies such as JPEG and MPEG. Furthermore, Iterated has been stressing that fractally compressed images can be scaled to higher or lower resolutions and color depths, when decompressed, without showing obvious pixelation.

No “blockiness.” A picture that has been fractally encoded, Iterated says, can be enlarged without the annoying “blockiness” that betrays its digital origin, and it can be printed from the same data file at higher resolution than the image as originally captured or as displayed on a computer monitor.

Barnsley, a cofounder of Iterated, discovered the Fractal Transform in 1988. The Fractal Transform is a mathematical procedure for analyzing an image into collections of shapes that resemble each other, except for size and orientation. Once identified, each collection can be summarized and reproduced by a formula that starts with the largest shape and repeatedly displaces and shrinks it.

Because such formulas are concise recipes for reproducing areas of the picture, describing a picture in terms of these “fractal” collections is a way to compress the image data. Following or applying the formulas regenerates (decompresses) the picture. Fractal procedures have two major advantages as a technique for digitally encoding pictures: high compression ratios and resolution independence.

Gain, not loss, of quality. These are familiar claims. The startling new development is the discovery by Barnsley of the phenomenon of fractal image enhancement. Barnsley says that his research team has found that when the fractal transform is applied to an image bitmap (such as a TIFF or Targa file), the process can add detail that was absent in the original digital file, but was present in the original image itself.

Adding detail as such is not really surprising, since this is an instance of fractal’s property of resolution independence. The surprising new claim is that this predicted detail is accurate as well as plausible to the eye, a “good guess” or correct mathematical interpolation of information that was left out when an image was digitally broken into a mosaic of pixels.

The discovery, in other words, is that applying fractal compression and decompression to an image file can result in a gain rather than a loss of image quality and accuracy as a higher-resolution version of the image is created.

WHAT MIGHT IT MEAN?

Barnsley claimed the ramifications of using fractal technology for image enhancement may be quite significant:

• Fractal enhancement could add resolution independence to existing digital photo images, giving even pictures that had not been originally compressed as fractals the capability to be rescaled easily, displayed or printed with accuracy and without artifacts at differing resolutions and sizes.

The same digital photo could be enlarged to poster size without calling attention to its pixels, or it could be shrunk to a screen thumbnail, much as chemical film images can be enlarged or reduced (within limits) without making the grain obtrusive. For the first time, publishers working with digital images would have some of the flexibility they are accustomed to with film.

• Applying this fractal enhancement process to motion video could in theory give resolution independence to digital HDTV reception, says Barnsley, even if the broadcast was not fractally encoded, so that wall-size HDTV would appear to have the same fine detail as a tabletop set.

• Fractal enhancement, Barnsley says, could in theory enhance even analog NTSC video at the receiving end to HDTV resolution (if not its aspect ratio), without changing the broadcast standards or spectrum allocation at all. The fractal circuitry would have to digitize the incoming frames and then apply the fractal image enhancement procedures to them, all at thirty frames per second. This sounds unlikely, but fractal motion video at less than full-screen/full-motion rates is already a reality with software-only decompression on PCs. A new government grant, discussed below, will fund development of a full-screen, full-motion fractal video decompression chip.

For fractal technology to achieve motion video on CD-ROM, movies-on- demand over phone lines, video conferencing, and other multimedia goals that have important data rate and file size constraints, fractal advocates still propose the option of compressing the images initially as fractal image format (FIF) files. With the discovery of fractal enhancement, however, they may be able to offer to improve the flexibility and quality of anyone’s digital pictures, not just those that are originally encoded as fractals.

GAINING ACCEPTANCE

Following Iterated’s licensing of fractal compression to Microsoft’s Multimedia Publishing Group for use in multimedia titles (see Digital Media, Vol. 1, No. 11, p. 18) came an announcement that Amaze Inc. will utilize fractal compression in providing the Gary Larson cartoon “refills” for future years of The Far Side Computer Calendar for DOS, Windows and the Macintosh.

Simultaneous with the Amaze announcement, Iterated Systems disclosed that it would supply fractal decompression software for the Mac before July of this year.

For fractal motion video, Iterated explicitly plans to use MPEG inter-frame algorithms, replacing only the discrete cosine transform intra-frame compression with the fractal methodology. This will allow manufacturers of MPEG decoders to incorporate fractal firmware or software modules with relative ease. The benefits of high compression ratios and resolution independence will apply to fractal motion video compression, as they do to fractal still-image compression, according to Barnsley.

Bernard Banet