FIASCO—An Open-Source Fractal Image and Sequence Codec

A picture is worth a thousand words—a frequently used sentence to introduce the need for digital image processing. And indeed, a wide variety of aspects in our life is influenced by digital images in the meantime. For instance, in the World Wide Web not only still pictures but also small video sequences are used to enhance the design of web pages. However, the usage of digital images has a major drawback. An enormous amount of data has to be transmitted and stored each time an image or video is requested.

For example, a single uncompressed frame of a high definition television (HDTV) screen (resolution of 1280×720 pixels, 24 bits per pixel) requires more than 2MB memory. When assuming a display rate of 60 frames per second (HDTV), one second of a video movie already requires more than 165MB, summing up to a total of 2,000 compact discs for a movie of 120 minutes! Clearly, downloading such an uncompressed video stream is impossible, even though fast Internet connections like asymmetric digital subscriber line (ADSL) are getting more popular now.

So image and video compression systems—like FIASCO, the fractal image and video codec—are mandatory in handling such enormous amount of data.

Different solutions are applicable to compress image data: for instance, the resolution of the frames can be reduced as well as the frame rate. However, this reduction is not sufficient. In general, image sequences typically contain three different types of redundancy that can be exploited (see Resources):

The goal of any image compression system is to recognize and remove these redundancies. The following two compression approaches are widely used:

Hence, lossy compression is mandatory for very low bit-rate Internet video applications (16-64KBps). Several lossy image and video coding standards have emerged in the last ten years, e.g., JPEG, MPEG and H.263. Most of these standards got a face-lift to incorporate the results of the current research in this area, e.g., JPEG2000, MPEG-4 and H.263+ (see Resources). Moreover, a lot of new algorithms have been investigated that have not found a way into a standard, although they are quite appealing. Wavelet-based image coders currently define the state-of-the-art in image coding. However, these codecs still suffer from a slow runtime of the decoder, making real-time (software-based) video decoding nearly impossible. Additionally, most of these new methods are covered by patents and proprietary formats, prohibiting open-source solutions.

FIASCO—the fractal image and sequence codec—is intended as a replacement for JPEG and MPEG for very low bit rates (see Resources). It provides the following features:

FIASCO compressed images are typically much smaller than JPEG files (at low bit rates), while the image quality is still acceptable. For example, see Figure 1 where you see images compressed by JPEG and FIASCO (1:220 in Figure 1A and 1B and 1:100 in Figure 1C and 1D compression ratio, i.e., 0.5% and 1% respectively, of the original file size).

The coding method of FIASCO is basically a straightforward generalization of the JPEG method. The JPEG algorithm subdivides an image into a set of image blocks of 8×8 pixels. Each of these blocks is then independently encoded by a linear combination of 64 basis images (the cosine basis, see Resources for details) as shown in Figure 2. The coefficients of these block approximations are then quantized and stored in the output file.

In Figure 2 the image is subdivided into 8×8 pixel blocks. Each of them is approximated by a linear combination of the cosine basis. The approximation coefficients (a and b in the figure) are then quantized and stored in the JPEG file. FIASCO extends this concept in the following ways:

FIASCO exploits self-similarities within single pictures, and also sequences of pictures, to remove spatial, spectral and temporal redundancies, making it a typical fractal coding method.

The FIASCO package is released under the terms of the GNU General Public License and is built up of command line applications and a library to compress, decode and visualize images and videos. You just have to run the typical GNU build process (./configure;make;make install) to compile and install the FIASCO package. FIASCO is entirely written in ANSI C and should compile on most UNIX platforms.

Usage of the commandline FIASCO coder and decoder is similar to the cjpeg and djpeg applications of the IJPEG package (Independent JPEG group), which should be part of every Linux distribution.

cfiasco --quality=10 --output=video.fco frame0*.ppm

The above encodes the given video files (in raw PNM format) with quality ten, writing a single FIASCO file video.fco. Please note that you cannot compare the quality settings of FIASCO with JPEG. The typical quality range of FIASCO is 1-100, which corresponds to a JPEG quality less than five. FIASCO is intended for very low bit rates only; i.e., you cannot compute compressed images that correspond to a JPEG quality of 75.

dfiasco, the FIASCO decoder, is also used like djpeg:

dfiasco --output=image.ppm image.fco

This decodes the given FIASCO file and writes a new image in PNM format. But dfiasco also contains a display module to show video frames in an X11 window. Currently, only an Xlib-based window with the typical set of control buttons is available (play, stop, forward, etc.). Hopefully, this simple decoder and the FIASCO library provides a good starting point for developers to support the FIASCO format in their favorite image and video programs (Mozilla, GIMP, etc.). Please visit the home page of FIASCO to get some compressed images and videos (see Resources).

The coding and decoding functionality of FIASCO is available in a shared library. Data type definitions and function prototypes are provided by the include file fiasco.h, which is installed in the $prefix/include directory.

You can simply compress images or videos in your application by a function call:

fiasco_coder (image_names, fiasco_name, quality, NULL)

This call compresses the image file(s) given by the array image_names with the predefined approximation quality (1.0-100.0) and creates the new FIASCO output file fiasco_name. Several advanced compression parameters can be adjusted by using an optional parameter object which I don’t describe here, see the FIASCO manual pages for details.

In order to decode a FIASCO file in your application, you have to instantiate an object of the decoder class fiasco_decoder_t with a call of the constructor function fiasco_decoder_new (fiasco_name, NULL). fiasco_name specifies the file to decode whereas the second parameter is an optional parameter object to adjust the behavior of the decoder.

Individual frames are then decoded by subsequent calls of the method fiasco_decoder_get_frame. These frames are returned in an internal FIASCO format, which then can be rendered in different ways to fit the needs of your application. For more information about the compression library, refer to the manual pages shipped with FIASCO.

FIASCO provides a powerful compression library that is intended to replace JPEG and MPEG for low bit-rate applications. FIASCO is an asymmetric compression method; you get software-based, real-time decoding at the cost of slow encoding times. FIASCO is especially suited in an application context where images or videos are compressed only once but requested and decoded several times (e.g., world wide web applications). Finally, if FIASCO were to be combined with an open-source sound and speech compression (e.g. Vorbis, see Resources), a complete video compression system for low bit rates would be available for free.

@aa:Ullrich Hafner (hafner@bigfoot.de, ulli.linuxave.net) has been a software engineer in the software management & design AG (sd&m), Germany since 1999. He developed FIASCO for his PhD thesis Low Bit-Rate Image and Video Coding with Weighted Finite Automats (see Resources) from 1994—1999.