Home | english  | Impressum | Sitemap | KIT
On the Inverse Problem of Fractal Compression
Autor: H. Hartenstein, M. Ruhl, D. Saupe, E. Vrscay Links:
Quelle: Fiedler, B. (Hrsg.), Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, Springer-Verlag, 2001
The inverse problem of fractal compression amounts to determining a contractive operator such that the corresponding xed 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 ne-tuning some of the fractal code parameters with the help of dierentiable methods. The dierentiability 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.