D. Saupe. Fractal image compression via nearest neighbor search. In Conf. Proc. NATO ASI Fractal Image Encoding and Analysis, Trondheim, July 1995, Y. Fisher (ed.), Berlin Heidelberg, 1998.
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 best matches for other image portions called ranges. Our theory developed here shows that this procedure of fractal image compression is equivalent to multi-dimensional nearest neighbor search in a space of feature vectors. 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 up to about 50 depending on image and domain pool size with negligible or minor degradation in both image quality and compression ratio. Furthermore, as compared to plain classifikation our method is demonstrated to be able to search through larger portions of the domain pool without increasing the computation time. In this way both image quality and compression ratio can be improved at reduced computation time. We also consider the application of a unitary transformation of the feature vectors which results in a reduction of the dimensionality of the search space. New results from numerical simultions are reported. Also we provide a brief overview of related work and other complexity reduction methods. This paper is an extended version of the article [34].
Download paper:
Adobe PDF
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.
@InProceedings{Saup95b,
Author = {Saupe, D.},
Title = {Fractal image compression via nearest neighbor search},
BookTitle = {Conf. Proc. NATO ASI {Fractal Image Encoding and Analysis}, Trondheim, July 1995},
editor = {Fisher, Y.},
Publisher = {Springer-Verlag},
Address = {Berlin Heidelberg},
Year = {1998}
}