3 March 1995 Fast generalized Lloyd iteration for vector quantizers (VQ) codebook design
Author Affiliations +
Abstract
The generalized Lloyd algorithm (GLA) plays an important role in the design of vector quantizers (VQ) for lossy data compression, and in feature clustering for pattern recognition. In the VQ context, this algorithm provides a procedure to iteratively improve a codebook and results in a local minimum which minimizes the average distortion function. We present a set of ideas that provide the basis for the acceleration of the GLA, some of which are equivalent to the exhaustive nearest neighbor search and some that may trade-off performance for the execution speed. More specifically, we use the maximum distance initialization technique in conjunction with either the partial distortion method or the fast tree-structured nearest neighbor encoding or the candidate-based constrained nearest neighbor search. As it is shown by the numerical experiments, all these methods provide significant improvement of the execution time of the GLA, in most cases together with an improvement of its performance. This improvement is of the order of 0.4 dB in the MSE, 15% in the entropy and more than 100 times in the execution time for some of the results presented.
© (1995) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Ioannis Katsavounidis, Ioannis Katsavounidis, C.-C. Jay Kuo, C.-C. Jay Kuo, Zhen Zhang, Zhen Zhang, "Fast generalized Lloyd iteration for vector quantizers (VQ) codebook design", Proc. SPIE 2418, Still-Image Compression, (3 March 1995); doi: 10.1117/12.204118; https://doi.org/10.1117/12.204118
PROCEEDINGS
12 PAGES


SHARE
Back to Top