Technical Report No. 53, May 1994 - Abstract

Dietmar Saupe:
Breaking the Time Complexity of Fractal Image Compression

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.