Fast clustering algorithm for codebook production in image vector quantization

作者：Al Otum HM^*

来源：Journal of Electronic Imaging, 2001, 10(2): 409-417.

DOI：10.1117/1.1351821

In this paper, a fast clustering algorithm (FCA) is proposed to be implemented in vector quantization codebook production. This algorithm gives the ability to avoid iterative averaging of vectors and is based on collecting vectors with similar or closely similar characters to produce corresponding clusters. FCA gives an increase in peak signal-to-noise ratio (PSNR) about 0.3-1.1 dB, over the LEG algorithm and reduces the computational cost for codebook production (10%-60%) at different bit rates. Here, two FCA modifications are proposed: FCA with limited cluster size 1&2 (FCA-LCS1 and FCA-LCS2, respectively). FCA-LCS1 tends to subdivide large clusters into smaller ones while FCA-LCS2 reduces a predetermined threshold by a step to reach the required cluster size. The FCA-LCS1 and FCA-LCS2 give an increase in PSNR of about 0.9-1.0 and 0.9- 1.1 dB, respectively, over the FCA algorithm, at the expense of about 15%-25% and 18%-28% increase in the cutout codebook size.

• 出版日期2001-4