Quantization of color images using the modified median cut algorithm

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


Many digital display devices allow only a limited number of colors to be displayed concurrently. Digitized color images typically contain several hundred to several thousand different colors. If these color images are to be viewed on displays with a limited color palette, the number of colors used to represent the image must be reduced to satisfy the display limits. This process is known as color quantization and is a special case of vector quantization. It has been shown that images containing large numbers of colors can be quantized to a very small color palette with little degradation in visual quality. This thesis presents a new algorithm, based on Heckbert's original median cut procedure, for creating near-original quality images using a small color palette. We have found that slight changes to Heckbert's original algorithm yield dramatic improvements in quantizer performance. The color quantization problem is considered in two parts: the selection of the optimal color palette, and the optimal mapping of each image pixel to a color from the palette. The method to be described is an image dependent quantizer in ROB color space. Resulting image quality is measured both subjectively and with a squared error metric.