A new vector quantization clustering algorithm
- 1 October 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Acoustics, Speech, and Signal Processing
- Vol. 37 (10) , 1568-1575
- https://doi.org/10.1109/29.35395
Abstract
The pairwise nearest neighbor (PNN) algorithm is presented as an alternative to the Linde-Buzo-Gray (1980, LBG) (generalized Lloyd, 1982) algorithm for vector quantization clustering. The PNN algorithm derives a vector quantization codebook in a diminishingly small fraction of the time previously required, without sacrificing performance. In addition, the time needed to generate a codebook grows only O(N log N) in training set size and is independent of the number of code words desired. Using this method, one can either minimize the number of code words needed subject to a maximum rate. The PNN algorithm can be used with squared error and weighted squared error distortion measure. Simulations on a variety of images encoded at 1/2 b/pixel indicate that PNN codebooks can be developed in roughly 5% of the time required by the LBG algorithm.< >Keywords
This publication has 11 references indexed in Scilit:
- Fast algorithms for vector quantization picture codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Image coding using vector quantizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Binary search trees for vector quantisationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- An improvement of the minimum distortion encoding algorithm for vector quantizationIEEE Transactions on Communications, 1985
- Vector quantizationIEEE ASSP Magazine, 1984
- Vector quantiser of video signalsElectronics Letters, 1982
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982
- On the structure of vector quantizersIEEE Transactions on Information Theory, 1982
- An Algorithm for Vector Quantizer DesignIEEE Transactions on Communications, 1980
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977