Search algorithms for vector quantization and nearest-neighbor classification

Thomas W. Ryan; Steven Pothier; William E. Pierson Jr.

doi:10.1117/12.438220

27 August 2001 Search algorithms for vector quantization and nearest-neighbor classification

Thomas W. Ryan, Steven Pothier, William E. Pierson Jr.

Proceedings Volume 4382, Algorithms for Synthetic Aperture Radar Imagery VIII; (2001) https://doi.org/10.1117/12.438220
Event: Aerospace/Defense Sensing, Simulation, and Controls, 2001, Orlando, FL, United States

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.

Citation Download Citation

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); https://doi.org/10.1117/12.438220

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