On the Inverse Problem of Fractal Compression

Hannes Hartenstein (), Matthias Ruhl (), Dietmar Saupe () and Edward R. Vrscay ()
Additional contact information
Hannes Hartenstein: NEC Europe Ltd., Computer & Communication Research Lab
Matthias Ruhl: Massachusetts Institute of Technology, Laboratory of Computer Science
Dietmar Saupe: Universität Leipzig, Institut für Informatik
Edward R. Vrscay: University of Waterloo, Department of Applied Mathematics

A chapter in Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, 2001, pp 617-647 from Springer

Abstract: 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 codingstrategy 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 differentiate 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.

Keywords: Inverse Problem; Fractal Compression; Collage Code; Iterate Function System; Discrete Optimization Problem (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-56589-2_26

Ordering information: This item can be ordered from
http://www.springer.com/9783642565892

DOI: 10.1007/978-3-642-56589-2_26

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().