A new scheme for codebook generation of image VQ

Vector quantization (VQ) is an effective means of data compression for it maps a set of real numbers into a single integer. A novel scheme for VQ codebook generation, namely the balance evolution (BE) algorithm, is presented. The proposed scheme decomposes an initial codebook into several sub-sets of closely located codevectors and then designs each sub-codebook using the generalized Lloyd algorithm (GLA) based on a carefully chosen cluster of signal vectors inside the training set. It reduces the variance in contributions of different sub-codebooks to the coding performance by adapting the composition of each training sub-set. Convergence of the proposed procedure is ensured via decreasing the total number of sub-codebooks gradually to one. Experiments show that the BE algorithm outperforms the Linde, Buzo, Gray (1980) algorithm and GLA. However, the achievement is accompanied by an increase in off-line computational complexity.