||n fractal image compression a contractive affine mapping whose
fixed point is an approximation to the original image has to be determined.
Usually, this mapping is found in a heuristic way. In this paper, we discuss
rate-distortion based fractal image coding where the code corresponding to the
mapping is optimal in the sense that it guarantees the lowest collage error (distortion
between the original image and its first iterate) over a large set of admissible
codes subject to a rate constraint. We show how optimal codes can e±ciently be
obtained. We begin with a fine scale partition of the image which gives a fractal
encoding with many bits and a low collage error. The partition is hierarchical,
thus, corresponds to a tree. We use a pruning strategy based on the generalized
BFOS algorithm where we extract subtrees corresponding to partitions and fractal
encodings which are optimal. We give results for fractal image compression
with rectangular partitions. We also provide a comparison with heuristic techniques
and review other rate-distortion based approaches.