Fractals and wavelets offer new ways to compress images
By Barry Phillips, Contributing Editor
Advances in wavelet and fractal image compression are increasing compression ratios without introducing visual artifacts.
In many applications, the well-established Joint Photographic Experts Group (JPEG) standard provides lossless compression ratios ranging from approximately 4:1 to 8:1. Now, using novel fractal- and wavelet-based methods, developers are abandoning the JPEG standard for higher 20:1 to 50:1 compression ratios.
Fractal and wavelet algorithms offer significant side benefits beyond high compression ratios. One feature, progressive image transformation, cuts decompression times for lower-resolution image rendering. Fractal and wavelet methods are also resolution-independent, enabling the same encoded file to be viewed at multiple resolutions.
Compression with fractals
Fractal image compression is based on mathematical theory developed by Michael Barnsley and Alan Sloan, cofounders of Iterated Systems (Atlanta, GA). In 1991, Barnsley patented the Partitioned Iterated Function System (PIFS), an algorithm that automatically converts images into PIFSs, compressing them in the process. Fractal compression partitions images into nonoverlapping range blocks. The fractal coder then finds a larger block of the same image (a domain block) for every range block. A transformation of the domain block is then used to approximate the range block.
Fractal compression is similar to vector quantization, which exploits the fact that some patterns in an image occur at greater frequencies than others. A set of common patterns is stored in a separate file called a "codebook." Decompressing the image is accomplished by assembling codebook entries. With PIFS-based fractal compression, the codebook is not stored. Instead, the "affine transforms" that make up the PIFS act as a "virtual codebook."
Fractal image compression has two advantages. First, fractals support customizable compression ratios. By configuring the compression process (size of the range and domain block), the desired compression ratio can be chosen. Second, fractals provide the additional benefit of resolution independence, which allows images to be displayed at almost any resolution. The same image can be viewed as an icon or at a size larger than its pixel-based counterpart. Users can display the same fractal file at multiple resolutions and zoom without `blocky` artifacts. Fractally compressed images can be magnified infinitely, yet be expressed mathematically with small data sets. Images compressed with fractal techniques require less data; average 24-bit color images can be compressed from 8:1 to 50:1.
Iterated Systems technology is available as a Windows DLL, a still image product called Fractal Imager, and a video product called Clear Video. The Altamira Group (Burbank, CA) also sells Genuine Fractals as a plug-in for Photoshop.
Fractal image format
Fractal image format (FIF) provides more compression than either JPEG or GIF formats at the same visual quality levels (see figure below). The same file compressed using Photoshop`s maximum-quality 24-bit JPEG setting produced a 351-kbyte file similar in image quality to the 132-kbyte FIF, while the 8-bit GIF required 193 kbyte.
The FIF format supports resolution-independent reconstruction of images without using the interpolation techniques of GIF and JPEG. Large-format output sizes can be rendered from tiny FIF files. For example, a 17-Mbyte image can be FIF compressed to 4.2 Mbytes (4:1 compression) and then rendered as a 25 ¥ 36-in. format image at 300 dpi resolution (a 235-Mbyte file).
"Fractal compression is an active research area," says Jean Michael Marie-Julie, a scientist at LETI (Saclay, France), a developer of image database software." Researchers are improving image quality and optimizing compression processes using vector quantization, wavelet transforms, nearest-neighbor search, neural networks, and genetic algorithms."
LETI`s system for context-based access to image databases uses fractal coding to make pattern recognition easy to use (see "Content-based image indexing uses fractal trans- forms, " p. 52). "Images are indexed with their compressed data code and the index used for searching and reconstruction of stored images. The technology allows LETI to rapidly locate multiple images with user-defined characteristics."
Wavelet compression
Technologies based on embedded wavelet coding are emerging as a viable technique for medical-imaging applications. The Compression with Reversible Embedded Wavelets (CREW) system from Ricoh California Research Center (Menlo Park, California) is structured for interactive decompression of wavelet files based on the information needed for the target resolution required or the frequency information needed to run a particular filter such as edge detection (see "Embedded wavelets provide lossless compression, " p. 53).
At last year`s Radiologic Society of North America exhibition, the M. D. Anderson Cancer Center (Houston, TX) demonstrated the interactive use of CREW with radiology images. CREW was used to display a region-of-interest section in lossless mode, while extraneous information along the edges was rendered at lower resolution.
"With JPEG, high-frequency components can be disregarded as encoding takes place. But if an edge-detection algorithm then needs to be run, the original must be recalled. With CREW, images are compressed once and saved with complete accuracy," says Michael Gormish, principal scientist at Ricoh. "Ricoh CREW provides all the benefits of wavelets-a higher signal-to-noise ratio, less offending artifacts, and progressive transmission," says Ernest Yeung, a researcher at the University of Waterloo (Waterloo, Ont., Canada). Because decompression is user-programmable, the user can determine the quality and rate of decompression.
Wavelets target mammography
Another important wavelet system designed by Amir Said of the State University of Campinas (Campinas, Brazil) and William A. Pearlman of Rensselaer Polytechnic Institute (Troy, MI) is based on a wavelet coding technique called Set Partitioning In Hierarchical Trees (SPIHT). Pearlman and his colleagues accomplished 80:1 compression using the technique. Even at this ratio, compressed images appear at high resolution. "SPIHT was the first method to allow gradual, efficient transmission starting from low bit rates and finishing with lossless recovery, using a single compressed file," adds Said.
CREW and SPIHT are both full-featured image-compression systems that provide good lossy and lossless performance, progressive transmission, and selectable resolution. Both Ricoh and Rensselaer offer toolkits and evaluation code to qualified organizations.
DCTs strike back
Wavelet and fractal transforms may have their rivals in some applications. If the goal of compression is to produce small icons of larger images, compression ratios of up to 250:1 can be achieved using overlapping Discreet Cosine Transforms (DCTs).
According to R. J. Henery, a professor at Strathclyde University (Glasgow, Scotland), "Using compressed cosine transforms and interpolation, lapped cosine transforms can provides high compression without the well-known `quilting` effect of JPEG-style compression." Henery`s overlapping DCT method uses DCT in blocks with uniform band limits over the whole image. "Results are comparable to the best wavelet methods at extremely high compression ratios," he claims.
Wavelet compression on the Web
Overview of wavelet resources on the Web: http://www.amara.com/current/wavelet.html
The Matlab wavelet toolbox by The MathWorks: http://www.mathworks.com/ wavelet. html
Rice University`s Matlab wavelet toolbox: http://www-dsp.rice.edu/software/RWT/
About Wolfram Research`s Wavelet Explorer: http://www.wolfram.com/applications/wavelet/index.html
Welcome to Fractals (book): http://www.iterated.com/support/intro/tover.htm
Content-based image indexing uses fractal transforms
Jean Michel Marie-Julie and Hassane Essafi
LETI (CEA-Technologies Avancées)
DEIN - CEA Saclay F91191
Gif sur Yvette, France
E-mail: [email protected]
Because digital-image databases can contain vast amounts of data, automatic indexing and content-based retrieval can speed the process of identifying specific image characteristics. Retrieving all the images in a database containing specific patterns (or sub images) is the task of designers of medical-imaging or document-management systems.
Fractal methods use "iconic-symbolic" image representations as an index to search patterns in sets of images. Because the method works in fractal-image space, interactive searching can be rapidly accomplished.
The index allows images to be reconstructed, compressed, and automatically indexed. Because only relevant parts of the image are used in the search process and the index is structured as a tree, database query process time is reduced. In addition, the search process can find images with different orientations or scales. Response times to queries are dependent upon the size of the image that is matched (see table).
Using this method, a 64 ¥ 64-pixel pattern in a one hundred 512 ¥ 512-pixel image database can be retrieved in three seconds on a SunSparc 20 workstation. The software can also be combined with other content-based indexing and retrieval techniques, based on texture, color, or shape analysis.
To search for a particular feature in an image database, the pattern of interest is first compressed using the Fractal Transform and then compared with each fractal image in the database.
