1 November 2001 Practical methods for speeding-up the pairwise nearest neighbor method
Author Affiliations +
Optical Engineering, 40(11), (2001). doi:10.1117/1.1412423
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.
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
JOURNAL ARTICLE
10 PAGES


SHARE
Back to Top