Translator Disclaimer
27 August 2001 Search algorithms for vector quantization and nearest-neighbor classification
Author Affiliations +
The problem of finding the stored template that is closest to a given input pattern is a typical problem in vector quantization (VQ) encoding and nearest neighbor (NN) pattern classification. This paper presents a new Triangle Inequality Nearest Neighbor Search (TINNS) algorithm that significantly reduces the number of distance calculations. This algorithm is appropriate in applications for which the computational cost of making a distance calculation is relatively expensive. Automatic Target Recognition (ATR) is one such application. This new algorithm achieves improved performance by guiding the order in which templates are tested, and using inequality constraints to prune the search space. We compare TINNS with another competing approach, as well as exhaustive search, and show that there is an appropriate application domain for each algorithm. Results are given for three applications, VQ for image compression, NN search over random templates, and target recognition in synthetic aperture radar image data.
© (2001) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Thomas W. Ryan, Steven Pothier, and William E. Pierson Jr. "Search algorithms for vector quantization and nearest-neighbor classification", Proc. SPIE 4382, Algorithms for Synthetic Aperture Radar Imagery VIII, (27 August 2001);

Back to Top