## On the inverse problem of fractal compression

2001
##### Authors
Hartenstein, Hannes
Ruhl, Matthias
Vrscay, Edward R.
##### Publication type
Contribution to a collection
##### Published in
Ergodic theory, analysis and efficient simulation of dynamical Systems / Fiedler, Bernold (ed.). - Berlin [u.a.] : Springer, 2001. - pp. 617-647. - ISBN 3-540-41290-5
##### 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 differential methods. The differentiability of the attractor as a function of its luminance parameters is established. We also comment on the approximating behaviour of collage coding, state a lower bound for the optimal attractor error, and outline an annealing scheme for improved fractal coding.
##### Subject (DDC)
004 Computer Science
##### Cite This
ISO 690HARTENSTEIN, Hannes, Matthias RUHL, Dietmar SAUPE, Edward R. VRSCAY, 2001. On the inverse problem of fractal compression. In: FIEDLER, Bernold, ed.. Ergodic theory, analysis and efficient simulation of dynamical Systems. Berlin [u.a.]:Springer, pp. 617-647. ISBN 3-540-41290-5
BibTex
@incollection{Hartenstein2001inver-23256,
year={2001},
title={On the inverse problem of fractal compression},
isbn={3-540-41290-5},
publisher={Springer},
booktitle={Ergodic theory, analysis and efficient simulation of dynamical Systems},
pages={617--647},
editor={Fiedler, Bernold},
author={Hartenstein, Hannes and Ruhl, Matthias and Saupe, Dietmar and Vrscay, Edward R.}
}

RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/23256/2/hartenstein_232562.pdf"/>
<dc:creator>Ruhl, Matthias</dc:creator>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-05-28T09:55:22Z</dcterms:available>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Vrscay, Edward R.</dc:contributor>
<dc:creator>Hartenstein, Hannes</dc:creator>
<dcterms:title>On the inverse problem of fractal compression</dcterms:title>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:language>eng</dc:language>
<dcterms:bibliographicCitation>Ergodic theory, analysis and efficient simulation of dynamical Systems / Bernold Fiedler (ed.). - Berlin [u.a.] : Springer, 2001. - S. 617-647. - ISBN 3-540-41290-5</dcterms:bibliographicCitation>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/23256/2/hartenstein_232562.pdf"/>
<dcterms:issued>2001</dcterms:issued>
<dc:rights>terms-of-use</dc:rights>
<dc:contributor>Saupe, Dietmar</dc:contributor>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dc:creator>Saupe, Dietmar</dc:creator>
<dc:contributor>Ruhl, Matthias</dc:contributor>
<dc:creator>Vrscay, Edward R.</dc:creator>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/23256"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Hartenstein, Hannes</dc:contributor>
<dcterms:abstract xml:lang="eng">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 differential methods. The differentiability of the attractor as a function of its luminance parameters is established. We also comment on the approximating behaviour of collage coding, state a lower bound for the optimal attractor error, and outline an annealing scheme for improved fractal coding.</dcterms:abstract>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-05-28T09:55:22Z</dc:date>
</rdf:Description>
</rdf:RDF>

No