On the Inverse Problem of Fractal Compression

Hannes Hartenstein, Matthias Ruhl, Dietmar Saupe and Edward R. Vrscay

Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems
Bernold Fiedler (ed.), Springer Verlag, August 2001


The inverse problem of fractal compression amounts to determining a contractive operator such that the corresponding fixed point approximates a given target function. The standard method based on the collage coding strategy is known to represent a suboptimal method. Why does one not search for optimal fractal codes? We will prove that optimal fractal coding, when considered as a discrete optimization problem, constitutes an NP-hard problem, i.e., it cannot be solved in a practical amount of time. Nevertheless, when the fractal code parameters are allowed to vary continuously, we show that one is able to improve on collage coding by fine-tuning some of the fractal code parameters with the help of differentiable methods. The differentiability of the attractor as a function of its luminance parameters is established. We also comment on the approximating behavior of collage coding, state a lower bound for the optimal attractor error, and outline an annealing scheme for improved fractal coding.

Back to publications