Fast nearest-neighbor search algorithm

Ahmed M. Darwish

doi:10.1117/12.234757

13 March 1996 Fast nearest-neighbor search algorithm

Ahmed M. Darwish

Proceedings Volume 2669, Still-Image Compression II; (1996) https://doi.org/10.1117/12.234757
Event: Electronic Imaging: Science and Technology, 1996, San Jose, CA, United States

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.

Citation Download Citation

Ahmed M. Darwish "Fast nearest-neighbor search algorithm", Proc. SPIE 2669, Still-Image Compression II, (13 March 1996); https://doi.org/10.1117/12.234757

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available