Share Email Print

Proceedings Paper

Fast nearest-neighbor search algorithm
Author(s): Ahmed M. Darwish
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 13 March 1996
PDF: 5 pages
Proc. SPIE 2669, Still-Image Compression II, (13 March 1996); doi: 10.1117/12.234757
Show Author Affiliations
Ahmed M. Darwish, Cairo Univ. (Egypt)

Published in SPIE Proceedings Vol. 2669:
Still-Image Compression II
Robert L. Stevenson; Alexander I. Drukarev; Thomas R. Gardos, Editor(s)

© SPIE. Terms of Use
Back to Top