Abstract A fast codebook training algorithm without the computation of distortion by the property of centroid sequence convergence is presented in this paper. The performance of the new algorithm is tested by typical test image Lena. The result shows that the PSNR difference between the new algorithm and LBG is O.ldB, but the running time of it is at most one half of LBG.