Vector Quantization Codebook Design Using the Law-of-the-Jungle Algorithm

Hiroyuki TAKIZAWA  Taira NAKAJIMA  Kentaro SANO  Hiroaki KOBAYASHI  Tadao NAKAMURA  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.6   pp.1068-1077
Publication Date: 2003/06/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Image Processing, Image Pattern Recognition
vector quantization,  the equidistortion principle,  the law-of-the-jungle algorithm,  the minimax partial distortion criterion,  

Full Text: PDF>>
Buy this Article

The equidistortion principle[1] has recently been proposed as a basic principle for design of an optimal vector quantization (VQ) codebook. The equidistortion principle adjusts all codebook vectors such that they have the same contribution to quantization error. This paper introduces a novel VQ codebook design algorithm based on the equidistortion principle. The proposed algorithm is a variant of the law-of-the-jungle algorithm (LOJ), which duplicates useful codebook vectors and removes useless vectors. Due to the LOJ mechanism, the proposed algorithm can establish the equidistortion condition without wasting learning steps. This is significantly effective in preventing performance degradation caused when initial states of codebook vectors are improper to find an optimal codebook. Therefore, even in the case of improper initialization, the proposed algorithm can achieve minimization of quantization error based on the equidistortion principle. Performance of the proposed algorithm is discussed through experimental results.