||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. Our theory developed here shows that this basic
procedure of fractal image compression is equivalent to multi-dimensional nearest neighbor search.
This result is useful for accelerating the encoding procedure in fractal image compression. The
traditional sequential search takes linear time whereas the nearest neighbor search can be organized
to require only logarithmic time. The fast search has been integrated into an existing state-of-the-art
classification method thereby accelerating the searches carried out in the individual domain classes.
In this case we record acceleration factors from 1.3 up to 11.5 depending on image and domain pool
size with negligible or minor degradation in both image quality and compression ratio. Furthermore,
as compared to plain classification our method is demonstrated to be able to search through larger
portions of the domain pool without increased the computation time. In this way both image quality
and compression ratio can be improved at reduced computation time.