Abstract: Focusing on the issue that [K]-Means costs lots of CPU time when reducing colors, a fast [K]-Means method accelerated by the mean quantization error vectors for color reduction is proposed. In this method, a palette is generated randomly with [K] colors as initialization firstly, and then a quantized version is obtained by the color table. According to the mean quantization error vectors between the current quantized version and the input image, a better color table is evolved. Through several iterations of updating, the evolving process converge to the last color table, correspondingly, the final quantized image by the palette is obtained. Experimental results show that the accelerated algorithm can speed up to 70-150 times as much as the [K]-Means used to, meanwhile, the quality of quantization is kept.

Key words: color quantization, [K]-means, mean quantization error vector, acceleration, palette

摘要： 针对[K]-Means色彩量化方法在运行时间上过于冗长的问题，提出一种用平均误差向量加速的色彩量化方法。随机生成[K]种色彩作为初始的调色盘，用该调色盘对欲量化的图像进行一次量化。根据量化后的版本，计算其每个颜色分量的量化误差，获得平均误差向量。用该平均误差向量对调色盘进行更新，获得另一更优的调色盘。通过若干次迭代运算，获得最终收敛的调色盘，并用该调色盘进行最后的色彩量化。实验结果表明，该加速算法能对[K]-Means量化方法平均加速70~150倍，同时，原有[K]-Means方法的量化效果还得到了保持。

关键词: 色彩量化, [K]-Means, 平均误差向量, 加速, 调色盘