Color quantization

In computer graphics, color quantization or color image quantization is quantization applied

to color spaces; it 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.[1] 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.

The name "color quantization" is primarily used in computer graphics research literature; in
applications, terms such as optimized palette generation, optimal palette generation, or
decreasing color depth are used. Some of these are misleading, as the palettes generated by
standard algorithms are not necessarily the best possible.

Algorithms
Most standard techniques treat color quantization as 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. 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 three color channels are usually red, green, and blue,
but another popular choice is the Lab color space, in which Euclidean distance is more
consistent with perceptual difference.
An example image in 24-bit RGB color

The same image reduced to a palette of 16

colors specifically chosen to best represent
the image; the selected palette is shown by
the squares at the bottom of the image.

The most popular algorithm by far for color quantization, invented by Paul Heckbert in 1979,
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 Purgathofer and improved by Xerox PARC researcher Dan
Bloomberg.
A small photograph that has had
its blue channel removed. This
means all of its pixel colors lie in a
two-dimensional plane in the color The color space of the photograph to the left, along
cube. with a 16-color optimized palette produced by
Photoshop. The Voronoi regions of each palette
entry are shown.

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" or "nearest color" 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
and , we want to minimize the Euclidean distance:

This effectively decomposes the color cube into a Voronoi diagram, where the palette entries
are the points and a cell contains all colors mapping to a single palette entry. There are
efficient algorithms from computational geometry for computing Voronoi diagrams and
determining which region a given point falls in; in practice, indexed palettes are so small that
these are usually overkill.
 A colorful image reduced to 4 colors using
spatial color quantization.

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 palette selection with dithering in one stage, rather than perform them
independently.

A number of other much less frequently used methods have been invented that use entirely
different approaches. The Local K-means algorithm, conceived by Oleg Verevka in 1995, is
designed for use in windowing systems where a core set of "reserved colors" is fixed for use
by the system and many images with different color schemes might be displayed
simultaneously. It is a post-clustering scheme that makes an initial guess at the palette and
then iteratively refines it.

In the early days of color quantization, the k-means clustering algorithm was deemed
unsuitable because of its high computational requirements and sensitivity to initialization. In
2011, M. Emre Celebi reinvestigated the performance of k-means as a color quantizer.[2] He
demonstrated that an efficient implementation of k-means outperforms a large number of
color quantization methods.

Portrait of Ada Lovelace - Faithful

representation and several versions
processed by k-means color-
quantization.

Original

2 colors
5 colors

10 colors
 15 colors

100 colors

The high-quality but slow NeuQuant algorithm reduces images to 256 colors by training a
Kohonen neural network "which self-organises through learning to match the distribution of
colours in an input image. Taking the position in RGB-space of each neuron gives a high-
quality colour map in which adjacent colours are similar."[3] It is particularly advantageous for
images with gradients.

Finally, one of the newer methods is spatial color quantization, conceived by Puzicha, Held,
Ketterer, Buhmann, and Fellner of the University of Bonn, which combines dithering with
palette generation and a simplified model of human perception to produce visually
impressive results even for very small numbers of colors. It does not treat palette selection
strictly as a clustering problem, in that the colors of nearby pixels in the original image also
affect the color of a pixel. See sample images (https://web.archive.org/web/2016042613530
6/www.cs.berkeley.edu/~dcoetzee/downloads/scolorq/#sampleimages) .
History and applications
In the early days of PCs, it was common for video adapters to support only 2, 4, 16, or
(eventually) 256 colors due to video memory limitations; they preferred to dedicate the video
memory to having more pixels (higher resolution) rather than more colors. Color quantization
helped to justify this tradeoff by making it possible to display many high color images in 16-
and 256-color modes with limited visual degradation. Many operating systems automatically
perform quantization and dithering when viewing high color images in a 256 color video
mode, which was important when video devices limited to 256 color modes were dominant.
Modern computers can now display millions of colors at once, far more than can be
distinguished by the human eye, limiting this application primarily to mobile devices and
legacy hardware.

Nowadays, color quantization is mainly used in GIF and PNG images. GIF, for a long time the
most popular lossless and animated bitmap format on the World Wide Web, only supports up
to 256 colors, necessitating quantization for many images. Some early web browsers
constrained images to use a specific palette known as the web colors, leading to severe
degradation in quality compared to optimized palettes. PNG images support 24-bit color, but
can often be made much smaller in filesize without much visual degradation by application of
color quantization, since PNG files use fewer bits per pixel for palettized images.

The infinite number of colors available through the lens of a camera is impossible to display
on a computer screen; thus converting any photograph to a digital representation necessarily
involves some quantization. Practically speaking, 24-bit color is sufficiently rich to represent
almost all colors perceivable by humans with sufficiently small error as to be visually identical
(if presented faithfully), within the available color space. However, the digitization of color,
either in a camera detector or on a screen, necessarily limits the available color space.
Consequently there are many colors that may be impossible to reproduce, regardless of how
many bits are used to represent the color. For example, it is impossible in typical RGB color
spaces (common on computer monitors) to reproduce the full range of green colors that the
human eye is capable of perceiving.

With the few colors available on early computers, different quantization algorithms produced
very different-looking output images. As a result, a lot of time was spent on writing
sophisticated algorithms to be more lifelike.
Quantization for image compression
Many image file formats support indexed color.

A whole-image palette typically selects 256 "representative" colors for the entire image,
where each pixel references any one of the colors in the palette, as in the GIF and PNG file
formats.

A block palette typically selects 2 or 4 colors for each block of 4x4 pixels, used in BTC, CCC,
S2TC, and S3TC.

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
fewer colors. Most of these implementations allow the user to set exactly the number of
desired colors. Examples of such support include:

Photoshop's Mode→Indexed Color

function 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.

In GIMP 2.8, the Convert Image to

Indexed Colors Option
(Image→Mode→Indexed..) allows
generation of an optimum palette with
a choice in the number of colors from
2 to 256, the option of using a web-
optimized palette, using a black and
white palette (1 bit) or using a custom
palette. It allows unused colors to be
 removed from the palette and it offers
a variety of dithering options: None,
Floyd-Steinberg (normal), Floyd-
Steinberg (reduced color bleeding) and
Positioned as well as the ability to
enable dithering of transparency.
Color quantization is also used to create posterization effects, although posterization has the
slightly different goal of minimizing the number of colors used within the same color space,
and typically uses a fixed palette.

Some vector graphics editors also utilize color quantization, especially for raster-to-vector
techniques that create tracings of bitmap images with the help of edge detection.

Inkscape's Path→Trace Bitmap:

Multiple Scans: Color function uses
octree quantization to create color
traces.[4]

See also

Indexed color
 Palette (computing)

List of software palettes — Adaptive

palettes section.

Dithering

Quantization (image processing)

Image segmentation

References

1. Celebi, M. E. (2011). "Forty Years of Color

Quantization: A Modern, Algorithmic
Survey". Artificial Intelligence Review. 56:
13953–14034. doi:10.1007/s10462-023-
10406-6 (https://doi.org/10.1007%2Fs104
62-023-10406-6) .

2. Celebi, M. E. (2011). "Improving the

performance of k-means for color
 quantization". Image and Vision
Computing. 29 (4): 260–271.
arXiv:1101.0395 (https://arxiv.org/abs/11
01.0395) . Bibcode:2011arXiv1101.0395E
(https://ui.adsabs.harvard.edu/abs/2011a
rXiv1101.0395E) .
doi:10.1016/j.imavis.2010.10.002 (http
s://doi.org/10.1016%2Fj.imavis.2010.10.0
02) . S2CID 9557537 (https://api.semanti
cscholar.org/CorpusID:9557537) .

3. "NeuQuant: Neural Image Quantization" (h

ttps://web.archive.org/web/20060614072
845/http://members.ozemail.com.au/~de
kker/NEUQUANT.HTML) . Archived from
the original (http://members.ozemail.co
m.au/~dekker/NEUQUANT.HTML) on
2006-06-14. Retrieved 2006-05-02.
 4. Bah, Tavmjong (2007-07-23). "Inkscape »
Tracing Bitmaps » Multiple Scans" (http://
tavmjong.free.fr/INKSCAPE/MANUAL/ht
ml/Trace-Multi.html) . Retrieved
2008-02-23.

Further reading

Paul S. Heckbert. Color Image

Quantization for Frame Buffer Display
(https://web.archive.org/web/2005060
6233131/http://citeseer.ist.psu.edu/he
ckbert80color.html) . ACM SIGGRAPH
'82 Proceedings. First publication of
the median cut algorithm.

Dan Bloomberg. Color quantization

using octrees (https://web.archive.org/
web/20030718130054/http://www.lept
onica.com/papers/colorquant.pdf) .
Leptonica.

Oleg Verevka. Color Image

Quantization in Windows Systems with
Local K-means Algorithm (http://citese
er.ist.psu.edu/100440.html) .
Proceedings of the Western Computer
Graphics Symposium '95.

J. Puzicha, M. Held, J. Ketterer, J. M.

Buhmann, and D. Fellner. On Spatial
Quantization of Color Images (https://
web.archive.org/web/2011101909311
4/http://www.iai.uni-bonn.de/III/forsch
ung/publikationen/tr/abstracts/IAI-TR-
98-1.abstract-en.html) . (full text .ps.gz
(https://web.archive.org/web/2007060
 9233403/http://www.informatik.uni-bo
nn.de/III/forschung/publikationen/tr/re
ports/IAI-TR-98-1.ps.gz) ) Technical
Report IAI-TR-98-1, University of Bonn.
1998.

Retrieved from
"https://en.wikipedia.org/w/index.php?
title=Color_quantization&oldid=1221150995"

This page was last edited on 28 April 2024, at

05:42 (UTC). •
Content is available under CC BY-SA 4.0 unless
otherwise noted.