A method to obtain better codebooks for vector quantizers than those achieved by the generalized lloyd algorithm

Abstract

The most widely used technique for designing a vector quantizer (VQ) is the Generalized Lloyd Algorithm (GLA), which is an iterative down-hill search in which some distortion function is being minimized. The major drawback of the GLA is that a local minimum of the distortion function, which heavily depends on the initial guess, is generally found. Unfortunately, in many practical applications, repeating the GLA using several different initial guesses generally yields only marginal improvement of the outcome codebook and does not always justify the increase in computation. In this paper we introduce an alternative approach to VQ design that produces better codebooks than the GLA (in the sense of lower distortion). The method is based on an on-line design technique (similar to the Kohonen learning scheme) which incorporates principles of stochastic relaxation. It is called the Soft Competition Scheme (SCS). The SCS is a deterministic on-line design procedure. In contrast to the Kohonen winner-take-all competition carried out between the candidate codevectors, it performs a "soft" competition where each codevector is assigned a winning score and all the codevectors are updated simultaneously according to these scores. A temperature schedule is used to control the speed of convergence versus the quality of the codebook.