Adaptive approximate nearest neighbor search for fractal image compression

Chong Sze TONG*, Man Wong

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

59 Citations (Scopus)


Fractal image encoding is a computationally intensive method of compression due to its need to find the best match between image subblocks by repeatedly searching a large virtual codebook constructed from the image under compression. One of the most innovative and promising approaches to speed up the encoding is to convert the range-domain block matching problem to a nearest neighbor search problem. This paper presents an improved formulation of approximate nearest neighbor search based on orthogonal projection and pre-quantization of the fractal transform parameters. Furthermore, an optimal adaptive scheme is derived for the approximate search parameter to further enhance the performance of the new algorithm. Experimental results showed that our new technique is able to improve both the fidelity and compression ratio, while significantly reduce memory requirement and encoding time.

Original languageEnglish
Pages (from-to)605-615
Number of pages11
JournalIEEE Transactions on Image Processing
Issue number6
Publication statusPublished - Jun 2002

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Adaptive approximate nearest neighbor search for fractal image compression'. Together they form a unique fingerprint.

Cite this