Abstract: Aiming at the problem of giving the number of quantization in advance and poor in-time performance of the conventional K-mean clustering, this paper proposes a color image quantization algorithm based on KD-tree clustering and NBS distance. Firstly, the original image is quantized using the middlecut algorithm. Secondly, based on the quantitative relation of the NBS distance and the color difference of human visual, the initial clustering centers and number are determined automatically. Thirdly, the K-mean clustering algorithm using the KD-tree data structure is applied to the color quantization, and then, a fast color image quantization effect is achieved. At last, simulations are performed on the presented algorithm, and the simulation result shows that the presented algorithm performs better in quantization effect and faster in running time.

Key words: image, quantization, middlecut, K-mean clustering, KD-tree