GLOBALLY OPTIMAL VECTOR QUANTIZER DESIGN BY STOCHASTIC RELAXATION

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.