**A
Reprogrammable Processor**

**for Fractal
Image Compression**

Department of Computer Science

United States Air Force Academy

2354 Fairchild Drive Suite 6K41

USAF Academy, Colorado 80840-6234 USA

Pichet Chintrakulchai

Thayer School of Engineering

Dartmouth College

Hanover, NH 03755-8000 USA

**Abstract. **Fractal
image compression appears to be a good candidate for implementation with a
reprogrammable processor. It is
computationally intensive, slow on existing technology, and employs a few basic, well-defined functions that are
clear candidates for hardware implementation.
We discuss our implementation of a reconfigurable processor for fractal
image compression, used to evaluate the utility of different compression
methods faster than a software-only
approach.

**1 Introduction**

Fractal image compression has recently been proposed
as an alternative to JPEG and other compression techniques [1,2,3]. By identifying an appropriate set of affine
transformations, images can be stored as mathematical functions which can then
be iterated on an arbitrary initial data set to approximate the original
image. The challenge is to construct the
transformation set. Because the search
space is large, fractal image compression is
computationally intensive.
Fractal image compression of a 128 x 128 color image can take over 4
hours on an RS/6000.

The long turnaround time for a software-only implementation
enhances the difficulty of experimentation with different search and comparison
functions. We require both 1) improved
performance of frequently executed functions, and 2) the ability to evaluate
different functions as candidates for use in fractal image compression. This suggests the use of a reconfigurable
coprocessor.

**2
Architecture**

Our coprocessor system is designed to work with the
Apple Power Macintosh computer using the NuBus interface [4], as shown in
Figure 1:

**Fig. 1.**** ** Coprocessor Architecture

The coprocessor functions in either in compute mode or program mode.
In program mode, the user feeds configuration data for a particular candidate
function through the NuBus into the FPGAs.
In compute mode, the host computer pumps input data through the NuBus
which is then fed through the programmable functional unit. Output results are stored in the buffer
memory. The functional unit is
user-programmable and set up according to the directed acyclic graph (DAG) of
the candidate operation. This DAG is the
data flow pipeline of the candidate operation where many basic units can
operate in parallel. Data dependency is
the only limit for the degree of parallelism in each stage; results dependent
upon the outputs of the current stage become the next stage of the
pipeline. This way, we are able to
exploit the parallelism both within a single stage of the pipe and across the
entire pipeline where results are pumped out of the pipe every cycle after the
pipe is filled.

**3
Candidate Operation**

Profile results gathered from running a fractal
compression program on sample images on IBM RS6000/340 workstation show that
the program spends more than 80% of total run time computing the absolute error
between image blocks. This suggests that
this function is a good candidate for hardware implementation.

Figure 2 shows the DAG for absolute error
computation. Our calculations indicate
implementation requirements of 123 CLB's and 64 I/O pins, easily within the
limits of a Xilinx 4000-series FPGA [5].
Our results indicate that this routine can be sped up by approximately a
factor of 50. Applying Amdahl's Law
reduces the speedup to an approximate factor of 4, still a significant
improvement. We are looking to
incorporate other candidate functions into hardware, including genetic
algorithms for searching the problem space and user-defined functions for
determining similarity between portions of images.

This work was supported by the National Science
Foundation under award # MIP - 9222643.

**Fig. 2. ** DAG for 2x2 Pixel Error Computation

**References**

1. Barnsley, M.F. and Hurd, L.P., *Fractal Image Compression*, A.K. Peters, 1993.

2. Fisher, Y.,
Jacobs, E.W. and Boss, R.D., *Fractal
Image Compression using Iterated Transforms*, Image and Text Compression, J.
A. Storer Editor, Kluwer Academic Publishers, 1992.

3. Jacquin,
A.E., *Image Coding Based on a Fractal
Theory of Iterated Contractive Image Transformations*, IEEE Trans. on Image
Processing, Vol. 1 (1), 1992, p. 18-30.

4. Apple Computer, Inc., *Designing Cards and Drivers for the Macintosh Family* (3rd Edition),
Addison-Wesley, 1992

5. Xilinx Inc.,
*The Programmable Logic Data Book*, San
Jose, CA, 1993.