Color quantization

Color quantization is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as visually similar as possible to the original image. Computer algorithms to perform color quantization on bitmaps have been studied since the 1970s. Color quantization is critical for displaying images with many colors on devices that can only display a limited number of colors, usually due to memory limitations, and enables efficient compression of certain types of images.

Algorithms

At its core, color quantization is essentially a problem of clustering points in three-dimensional space, where the points represent colors found in the original image and the three axes represent the three color channels (usually red, green, blue). For this reason, almost any three-dimensional clustering algorithm can be applied to color quantization, and vice versa. After the clusters are located, typically the points in each cluster are averaged to obtain the representative color that all colors in that cluster are mapped to.

The most popular algorithm by far for color quantization, invented by Paul Heckbert in 1980, is the median cut algorithm. Many variations on this scheme are in use. Before this time, most color quantization was done using the population algorithm or population method, which essentially constructs a histogram of equal-sized ranges and assigns colors to the ranges containing the most points. A more modern popular method is clustering using octrees, first conceived by Gervautz and Pergathofer and improved by Xerox PARC researcher Dan Bloomberg.

If the palette is fixed, as is often the case in real-time color quantization systems such as those used in operating systems, color quantization is usually done using the "straight-line distance" algorithm, which simply takes each color in the original image and finds the closest palette entry, where distance is determined by the distance between the two corresponding points in three-dimensional space. In other words, if the colors are $(r_{1},g_{1},b_{1})$ and $(r_{2},g_{2},b_{2})$, we want to minimize:

${\sqrt {(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}}}$

This process can be sped up using indexing data structures that rapidly narrow down the possible choices for the correct palette entry. Also, it's typical to not actually take square roots but merely compare the squares of the distances.

Color quantization is frequently combined with dithering, which can eliminate unpleasant artifacts such as banding that appear when quantizing smooth gradients and give the appearance of a larger number of colors. Some modern schemes for color quantization attempt to combine it with dithering in one stage, rather than perform them independently.

Editor support

Many bitmap graphics editors contain built-in support for color quantization, and will automatically perform it when converting an image with many colors to an image format with less colors. Examples of such support include:

• Photoshop's Mode→Indexed Color function, which supplies a number of quantization algorithms ranging from the fixed Windows system and Web palettes to the proprietary Local and Global algorithms for generating palettes suited to a particular image or images.
• Paint Shop Pro, in its Colors→Decrease Color Depth dialog, supplies three standard color quantization algorithms: median cut, octree, and the fixed standard "web safe" palette.
• The GIMP's "Generate Optimal Palette with 256 Colours" option, known to use the median cut algorithm.

References

• Paul S. Heckbert. Color Image Quantization for Frame Buffer Display. ACM SIGGRAPH '82 Proceedings. First publication of the median cut algorithm.
• Dan Bloomberg. Color quantization using octrees. Leptonica.