Share Email Print

Optical Engineering

Practical methods for speeding-up the pairwise nearest neighbor method
Author(s): Olli Virmajoki; Pasi Franti; Timo Kaukoranta
Format Member Price Non-Member Price
PDF $20.00 $25.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 pairwise nearest neighbor (PNN) method is a simple and well-known method for codebook generation in vector quantization. In its exact form, it provides a good-quality codebook but at the cost of high run time. Afast exact algorithm was recently introduced to implement the PNN an order of magnitude faster than the original O(N3K) time algorithm. The run time, however, is still lower bounded by O(N2K), and therefore, additional speed-ups may be required in applications where time is an important factor. We consider two practical methods to reduce the amount of work caused by the distance calculations. Through experiments, we show that the run time can be reduced to 10 to 15% that of the original method for data sets in color quantization and in spatial vector quantization.

Paper Details

Date Published: 1 November 2001
PDF: 10 pages
Opt. Eng. 40(11) doi: 10.1117/1.1412423
Published in: Optical Engineering Volume 40, Issue 11
Show Author Affiliations
Olli Virmajoki, University of Joensuu (Finland)
Pasi Franti, Univ. of Joensuu (Finland)
Timo Kaukoranta, Univ. of Turku (Finland)

© SPIE. Terms of Use
Back to Top