Inside Iterated Systems' Fractal Development Kit

Dino is a senior software engineer specializing in Windows programming and a contributing editor to many Italian programming magazines. He can be reached at [email protected].

In today's world of graphics-intensive computing, it is critical to minimize the space required for storing images -- and fractal-based software provides an efficient way to do just that. Although fractal compression can be time consuming because of the intrinsic asymmetry of the algorithm, decompression is almost immediate. Furthermore, fractals inside applications are resolution independent and scalable. A 30-KB, 700×400-pixel image can decompress to the screen in any size (smaller or larger) in a matter of seconds.

The Fractal Development Kit (FDK) from Iterated Systems is a library that makes it possible for you to embed fractal-imaging capabilities into C/C++ Windows and Macintosh applications. The royalty-free Image Decoder lets you display Fractal Image Format (FIF) files or convert files to other formats. It supports 32-bit Windows (Windows 95/NT/Win32s), 16-bit Windows (Windows 3.x), and MacOS. The decoder is compatible with compilers such as Watcom C/C++ 10.5a, Borland C++ 4.5, and Microsoft Visual C++ 4.0 (and v1.52a for 16-bit) under Windows, and MPW 3.4, CodeWarrior 1.4, Symantec 8.0.3, and Visual C++ 4.0 for the MacOS. The Image Encoder, which requires a license, lets you convert files from other formats to FIF files. It supports 32-bit Windows only.

You can download the complete kit from http://www.iterated.com/. Once you have downloaded the libraries, you simply use two DLLs, one for compressing images and the other for decompressing.

The Decompression Library

The decompression library, deco_32.dll, is a 32-bit Windows library compatible with Win32s. Before decompressing your first fractal image, you should be acquainted with concepts such as FTT files, resolution format, output color table, dithering, and the FIF buffer. The libraries are powerful and flexible, but require work before you can successfully display a decompressed bitmap. The process consists of the following steps:

1. Initializing the engine.

2. Reading the input FIF file.

3. Reading the input FTT file (if required).

4. Setting the output resolution.

5. Allocating a buffer for the image.

6. Invoking the decompressor.

From the software perspective, decompressing involves a request to a server. This server, called "decompressor," is initialized using OpenDecompressor. The handle that is returned represents the session. Each session has a set of properties: output format, color-table format, output color table, and dithering. You can specify the desired format for the pixels of the image and for the image's palette. With SetOutputFormat, you can decide how bits should be returned. For example, if you want a true-color Windows DIB, use a call such as SetOutputFormat(hDeco, BLUE8, GREEN8, RED8, NOT_USED, BOTTOM_LEFT), where the first argument is the handle to the decompressor instance, the next four arguments represent an RGB quadruple (for DIBs the first byte is blue, the second is green, and the third is red), and the last parameter is a flag denoting the order in which you would process the output data. The DIBs are usually bottom-left ordered and require three bytes (B,G,R). For the Macintosh, the call should be changed to SetOutputFormat(hDeco, BLANK8, RED8, GREEN8, BLUE8, TOP_LEFT).

SetOutputFormat gives you full control of how the decompressed bits are organized in the return buffer. You can ask the decompressor for true-color and color-mapped bitmaps. Using SetColorTableFormat, you determine the format of the output color table. The palette is calculated by the library and made available via GetOutputColorTable. Often, you cannot afford an optimized palette for each image because of hardware limitations or interface requirements. The FDK offers a good solution to this kind of problem. SetOutputColorTable lets you define the output palette color by color. You may decide that the ith entry will be dynamically determined by the decompressor, or statically fixed by your software. You need to pass an array of flags, one for each color-table entry. Typical values are CM_DYNAMIC, CM_STATIC, and CM_NOT_USED. Example 1 gets an optimized palette.

Once you have initialized the decompressor, turn to the FIF file. You should provide code to open the file, read it in, and bufferize it. You also have to take care of memory allocation and checking for a valid FIF format (using TestIfFIF). The bytes to decompress must be stored in an internal buffer via SetFIFBuffer. If the FIF file requires a fractal template (FTT file), you read in and set it using SetFTTBuffer.

One advantage of fractals over other compression technologies is the capability of recreating images, scaling from their original size. When you first acquire the image from a photo, slide, book, or wherever, you get a physical bitmap whose dimensions depend upon the density of digitization. The higher the DPI (dots per inch) ratio, the better the quality of the resulting image. Compressing a bitmap such as this usually binds you to a particular width and height; you can provide scaling effects only by means of stretching algorithms. Having fractals inside your apps lets you extract and store in FIF codes just the information needed to reproduce the image at the resolution that best fits your program. In one sense, producing fractal codes from a bitmap is somewhat like extrapolating the inner nature of the image itself. It also allows you to quickly generate the image again and again. The image is not drawn to fit a new size, but it actually has that new size. Previous releases of the FDK allowed only three decompression scales: half, full, and double. With the current release, the image can be scaled by an arbitrary real value using SetOutputResolution. The FDK also contains functions to read the original size of the image (in pixels and before compression) and its physical dimensions. Don't be surprised by the resolution independence. Think of fractal compression the same way you think of a straight line: Once you know its coefficients, you know all of it and you can reproduce it correctly given any interval [x,y]. The advantage of fractals is that you don't have a N×M image stretched to N'×M', but a completely new N'×M' image.

Before decompressing, you should allocate enough memory to hold the DIB. The amount of memory is determined by multiplying the desired width and height by the number of bytes per pixel. The function that actually performs the decompression is DecompressToBuffer, which requires that you pass in the padded width of each scanline (the width is aligned to doublewords). The FDK supports a callback function to monitor the progress of the operation or to abort it. The decompression process returns the actual bits of the DIB and calculates an optimized color table, if required. At this point, all that remains is fusing the bits with the palette, adding a header, and displaying the final DIB.

The Compression Library

The library for creating FIFs is comp_32.dll. The steps required to use it are similar to decompression, although the parameters are set differently. Those steps are:

1. Initializing the engine.

2. Reading the input file.

3. Allocating buffer for the FIF.

4. Setting the quality and speed.

5. Invoking the compressor.

The function OpenCompressor initializes an instance of the engine. Keep in mind that fractal compression is ultimately an exhaustive search that, starting from a partition of the image, compares each portion of the image to all the others in order to capture any significant redundancy. For performance reasons, hardware compression, which requires a specialized add-in card, was commonly used in the past to perform most of the searching. Hardware support can be helpful and, based on a previous release of the FDK, reduces the time needed to compress an image by up to one minute per megabyte. However, because of the availability of high-performance processors, the current release of the FDK doesn't support hardware solutions, and compression is software only. Still, the current decompressor can handle all the FIFs created with older compressors (including hardware), although the current compressor is not backward compatible. That is, the FIFs created cannot be decompressed with previous versions of the fractal decoder.

Once you've successfully started the session, you need to fill the input buffer with the actual image data. First, you need to indicate the format in which your data will be represented. You call SetInputFormat(hComp, BLUE8, GREEN8, RED8, NOT_USED, BOTTOM_LEFT) if you want the compressor to receive the bits as they are stored in a Windows DIB. SetImageBuffer must be assigned the input data in the aforementioned format. The engine needs to know the dimensions (in pixels) of the image being compressed and, optionally, its physical size in inches or meters (SetImageResolution). Before launching compression, you should allocate enough memory to hold the resulting fractal codes. The FDK provides the function GetMaxFIFSize, which protects you from having a buffer that is too small! It returns the maximum size of the FIF file depending on the data registered with SetImageResolution.

There are also parameters to control the speed and quality of the compressor. Both are specified with a value of 1 to 100, where 1 means low speed, low quality, and small size; and 100 means high speed, best quality, and large sizes. There is no direct relation between speed and quality: If you vary the compression speed, the quality remains constant and vice versa. On the other hand, both speed and quality affect the file size. The necessary functions are SetCompressionSpeed and CompressToBuffer. The latter is also the routine you need to invoke to actually produce fractal code. It is recommended that you set a callback function to give feedback to the user. The function should have the prototype long_cdecl CompProc(long h, long percDone), where the first argument is the handle to the compressor instance and the second is an estimate of the job already done. CompressToBuffer requires the pointer to the buffer where the FIF code will be stored, together with a variable to let you know the exact size of the FIF generated.

Other Issues

The FTTs (Fractal Transform Templates) are files that can help speed up the compressor. In reality, they are collections of small fragments (usually 32×32 pixels) of the images they refer to. There is at most one FTT for each image and multiple images may share the same FTT file. This means that the small pieces of bitmaps may come from different images but they should be related to the same subject. For example, an FTT can be a collection of details of faces such as noses, eyes, or mouths. Fortunately, the FDK supports FTTs only in decompression and only for compatibility purposes. When decompressing old images, a common error code is "FTT needed but not provided"; so, make sure the required FTTs are in the same path as the FIF files.

If users required a color-mapped image, a considerable amount of decompressing time is spent calculating a half-tone palette. You can reduce this time to zero by storing a precalculated palette inside the FIF. The function that lets you do this is SetFIFColorTable. By default, the color format of the FIF file is the same as the color format of the input file, but you can ask the compressor to use a grayscale table for the image (SetFIFFormat).

The Sample Code

Available electronically (see "Availability," page 3) are the source and executables for a program called FRACTAL.EXE, which illustrates image compression/decompression using the FDK 1.1. I've compiled this version of the program with MS Visual C++ 4.x. To run or recompile FRACTAL.EXE, you need the FDK 1.x.

You should note that the compressor supports only 24-bit BMP files in input, and the decompressor returns only 8-bit colormapped DIBs. These are limits of the program, not of the FDK or the technology. FRACTAL's compression ratio is low (less than 10:1) because of the speed/quality settings used by the program. The values passed maximize the speed over the file size (85) and require an average quality (65). Finally, the program accepts a BMP true-color image and returns a FIF file with the same name in the same directory.

Progressive Compression/Decompression

Both compression and decompression can occur incrementally. Incremental compression can be useful for limiting the amount of memory needed to hold a large 24-bit image, and incremental decompression is especially useful for Internet programming. An incremental variant gives users the possibility of piecemeal processing. Incremental compression requires less memory but a little more time, whereas the decompression occurs little by little as the file comes in. The progressive compression divides the image into rectangles and handles them separately. A final step gathers all the data in a single FIF file.

Progressive decompression uses the data received to prepare either a small and well-defined image or a full-size but blurred image. In the first case, the size will increase step by step; in the second, the image will be progressively focused. The incremental technology doesn't give you a different image from the standard. The APIs are different, but the programming approach is the same.

The Evolution of the Libraries

Nowadays only JPEG and FIF ensure high compression ratios. They're based on different algorithms but try to offer the same advantages to end users -- high compression, scalability, resolution independence, and video support. Deciding which of them better fits your needs is up to you, but consider that the potential of fractal compression technology has barely been explored.

References

Anson, Louisa. "Fractal Image Compression." BYTE, October 1993.

Barnsley, Michael F. and Alan Sloane. "A Better Way to Compress Images." BYTE, January 1988.

Barnsley, Michael F. and Lyman P. Hurd. Fractal Image Compression. Wellesley, MA: AK Peters, 1993.

McGregor, D.R, R.J. Fryer, P. Cockshott, and P. Murray. "Faster Fractal Compression." Dr. Dobb's Journal, January 1996.

DDJ