Color quantization is a process of choosing a set of
Krepresentative colors to approximate the Ncolors of an image, K < N, such that the resulting K-color image looks as much like the original N-color image as possible. This is an optimization problem known to be NP-complete in K. However, this paper shows that by ordering the Ncolors along their principal axis and partitioning the color space with respect to this ordering, the resulting constrained optimization problem can be solved in O( N+ KM2 ) time by dynamic programming (where Mis the intensity resolution of the device).
Traditional color quantization algorithms recursively bipartition the color space. By using the above dynamic-programming algorithm, we can construct a globally optimal
K-partition, K>2, of a color space in the principal direction of the input data. This new partitioning strategy leads to smaller quantization error and hence better image quality. Other algorithmic issues in color quantization such as efficient statistical computations and nearest-neighbor searching are also studied. The interplay between luminance and chromaticity in color quantization with and without color dithering is investigated. Our color quantization method allows the user to choose a balance between the image smoothness and hue accuracy for a given K.