Color image quantization for display applications

Full resolution digital color display devices often use 24 bits to represent the color at each pixel of an image. This allows a choice of over 16 million colors at each pixel. However, due to reasons of economy in data representation and constraints on the size of the video memory, many low-cost display devices can only display a small number of colors simultaneously. In this case, it is necessary to quantize the image to a small set of colors, called a palette. In this thesis, we investigate three color quantization techniques: pairwise nearest neighbor merging (PNN); binary splitting (BSP); and sequential scalar quantization (SSQ). All three methods are based on vector quantization (VQ), and are designed to minimize an objective error criterion in an image dependent manner. While the first two techniques are straightforward applications of existing VQ algorithms, to our knowledge, SSQ has not received much attention in the VQ literature. Hence, we perform a detailed theoretical analysis of this technique. We then apply the results of the analysis to the color quantization problem. With all three techniques, we use simple heuristics that account for some properties of the human visual system and hence improve visual quality. Considerable emphasis is placed on minimizing the computational time and memory required for quantization. The algorithm complexity is greatly reduced with the use of efficient data structures for histogramming and palette design. All three techniques yield visually transparent image quality. Of the three methods, SSQ is by far the most efficient technique, followed by BSP and PNN. SSQ also outperforms other standard color quantization algorithms both in terms of visual quality and computational speed