[IEEE Trans. on Signal Processing, February 1992, pp. 310-322]
Globally Optimal Vector Quantizer Design by Stochastic Relaxation
Kenneth Zeger, Jacques Vaisey, & Allen Gersho
Abstract
This paper presents a unified formulation and study of vector quantizer design
methods that couple Stochastic Relaxation (SR) techniques with the Generalized
Lloyd Algorithm. Two new SR techniques are investigated and compared:
Simulated Annealing (SA), and a reduced-complexity approach that modifies the
traditional acceptance criterion for Simulated Annealing to an unconditional
acceptance of perturbations. It is shown that four existing techniques all fit
into a general methodology for vector quantizer design aimed at finding a
globally optimal solution. Comparisons of each algorithms' performance when
quantizing Gauss-Markov processes, speech, and image sources are given. The SA
method is guaranteed to perform in a globally optimal manner, and the SR
technique gives empirical results equivalent to those of SA. Both techniques
result in significantly better performance than that obtained with the
Generalized Lloyd Algorithm.