Share Email Print

Proceedings Paper

Search algorithms for vector quantization and nearest-neighbor classification
Author(s): Thomas W. Ryan; Steven Pothier; William E. Pierson Jr.
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 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.

Paper Details

Date Published: 27 August 2001
PDF: 10 pages
Proc. SPIE 4382, Algorithms for Synthetic Aperture Radar Imagery VIII, (27 August 2001); doi: 10.1117/12.438220
Show Author Affiliations
Thomas W. Ryan, Science Applications International Corp. (United States)
Steven Pothier, Science Applications International Corp. (United States)
William E. Pierson Jr., Air Force Research Lab. (United States)

Published in SPIE Proceedings Vol. 4382:
Algorithms for Synthetic Aperture Radar Imagery VIII
Edmund G. Zelnio, Editor(s)

© SPIE. Terms of Use
Back to Top