Back to Publications

Author(s) Saupe, D.
Title Breaking the time complexity of fractal image compression
Abstract 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 Saupe94b.pdf