Fast generalized Lloyd iteration for VQ codebook design

Ioannis Katsavounidis; C.-C. Jay Kuo; Zhen Zhang

doi:10.1117/12.204118

3 March 1995 Fast generalized Lloyd iteration for vector quantizers (VQ) codebook design

Ioannis Katsavounidis, C.-C. Jay Kuo, Zhen Zhang

Proceedings Volume 2418, Still-Image Compression; (1995) https://doi.org/10.1117/12.204118
Event: IS&T/SPIE's Symposium on Electronic Imaging: Science and Technology, 1995, San Jose, CA, United States

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.

Citation Download Citation

Ioannis Katsavounidis, C.-C. Jay Kuo, and Zhen Zhang "Fast generalized Lloyd iteration for vector quantizers (VQ) codebook design", Proc. SPIE 2418, Still-Image Compression, (3 March 1995); https://doi.org/10.1117/12.204118

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available