Two High Speed Color Quantization Algorithms

Luc Brun &
Myriam Mokhtari.

Color image quantization has been widely studied for the last fifteen years. Most of existing quantization algorithms use pure top-down or bottom-up approaches, in this paper we present a two-pass quantization method using a split stage followed by a merge one. The split stage uses a uniform quantization algorithm to generate N initial clusters. These clusters are then combined during the merge stage into K<<N final clusters. Finally, these clusters are used by an inverse colormap algorithm to create the output image. Two different inverse colormap algorithms are proposed leading to two quantization algorithms. These quantization algorithms are more efficient than pure split or pure merge algorithms. Moreover, the difference between the number of clusters produced by the split stage and the number of final clusters allows users to control efficiently the quality/time ratio.