D. Saupe. Breaking the time complexity of fractal image compression. Research Report Institut für Informatik, Universität Freiburg, No 53, 1994.
In fractal image compression the encoding step is computationally expensive. A large number of sequential searches through a list of domains (portions of the image) are carried out while trying to find a best match for another image portion. We show that this step can be replaced by multi-dimensional nearest neighbor search which runs in logarithmic time instead of linear time required for the common sequential search.
Download paper:
Adobe PDF
Download supplementary information. (link)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
@TechReport{Saup94a,
Author = {Saupe, D.},
Title = {Breaking the time complexity of fractal image compression},
Number = {53},
Institution = {Institut für Informatik, Universität Freiburg},
Year = {1994}
}