1 November 2001 Practical methods for speeding-up the pairwise nearest neighbor method
Author Affiliations +
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.
© (2001) Society of Photo-Optical Instrumentation Engineers (SPIE)
Olli Virmajoki, Pasi Franti, Timo Kaukoranta, "Practical methods for speeding-up the pairwise nearest neighbor method," Optical Engineering 40(11), (1 November 2001). https://doi.org/10.1117/1.1412423 . Submission:
JOURNAL ARTICLE
10 PAGES


SHARE
Back to Top