Share Email Print

Proceedings Paper

Fast generalized Lloyd iteration for VQ codebook design
Author(s): Ioannis Katsavounidis; C.-C. Jay Kuo; Zhen Zhang
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 3 March 1995
PDF: 12 pages
Proc. SPIE 2418, Still-Image Compression, (3 March 1995); doi: 10.1117/12.204118
Show Author Affiliations
Ioannis Katsavounidis, Univ. of Southern California (United States)
C.-C. Jay Kuo, Univ. of Southern California (United States)
Zhen Zhang, Univ. of Southern California (United States)

Published in SPIE Proceedings Vol. 2418:
Still-Image Compression
Majid Rabbani; Edward J. Delp; Sarah A. Rajala, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?