##
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

### Abstract

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