| 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 best matches for other image portions called
ranges. Our theory developed here shows that this basic 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 classification 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 simulations 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]. |