Translator Disclaimer
13 March 1996 Fast nearest-neighbor search algorithm
Author Affiliations +
Proceedings Volume 2669, Still-Image Compression II; (1996)
Event: Electronic Imaging: Science and Technology, 1996, San Jose, CA, United States
The nearest neighbor search procedure has numerous applications in pattern classification and image coding, specifically for vector quantization methods. Despite its good result performance it is normally avoided because of its expensive computational complexity (O(kN) arithmetic operations where N is the number of vectors and k is the vector dimension). Several methods have been proposed in the literature to speedup the search process, some of which do not guarantee to find the closest neighbor. This may cause misclassification for recognition applications and introduce higher image distortion levels for coding applications. In this paper we present a nearest neighbor search algorithm that utilizes some of the vectors statistical features, that could be computed off-line, to quickly reject quite a few vectors that can never be closest candidates to the given vector. In fact, most of the time, the off-line built lookup table index yields the closest neighbor immediately without any further search. The algorithm is, thus almost, O(k) arithmetic operations and is guaranteed to find the same closer vector that results from a full search method. Results of applying the algorithm to vector quantize few images will be reported.
© (1996) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Ahmed M. Darwish "Fast nearest-neighbor search algorithm", Proc. SPIE 2669, Still-Image Compression II, (13 March 1996);

Back to Top