Codebook Generation Using Partition and Agglomerative Clustering

Abstract

In this paper, we present a codebook generation algorithm to produce a codebook with lower distortion. Our method combines a fast codebook generation algorithm (CGAUCD) with doubling technique and fast agglomerative clustering algorithm (FACA) to generate a codebook with less computing time and lower distortion. Instead of using FACA directly to divide training vectors into M clusters, our proposed method first generates qM clusters from these training vectors, where q>1 is an integer, and then applies FACA to merge these qM clusters into M cells. This is due to the computational complexity of CGAUCD with doubling technique is less than that of FACA. These M cluster centers are used as the initial codebook for CGAUCD. Using three real images as the training set, our method can reduce the MSE and computing time of FPNN+CGAUCD, which is the available best method to our knowledge, by 0.19 to 0.38 and 74.6% to 84.3%, respectively.

Keywords

• codebook generation
• agglomerative clustering
• vector quantization