The premise underlying `-colormap` is that images probably do not use all 16,777,216 colors available to them in three 8 bit channels (281,474,976,710,656 colors for 16 bits). For many images, certain hues, saturations and lightnesses are more prevalent than others. It is likely that colors cluster around various medians, and it may even be that the clustering is quite “tight”, that is, not much variation around these means. If we were to plot all the colors of such an image in an RGB color cube^{*}, the points would form clouds around (perhaps just a few) centers and much of the remaining color space would be nearly empty.

The game is to find the clusters. G'MIC harnesses two well-known algorithms from statistics and computer vision. The *median-cut algorithm* is the workhorse; it estimates an initial palette that suffices for many purposes.

For the picky, there is the *k-means algorithm*, which refines the results of median-cut. This algorithm *indexes* the given original using a trial palette generated by the median-cut method, then makes a new palette based on the *histograms* of the indexed image. If the colors of the trial palette accurately reflect the clustering inherent in the image, the new and trial palettes should be identical. Otherwise, the k-means algorithm tries the new palette in a second round and iterates until differences between two successive palettes fall below a given tolerance.

For students of `gmic`, `-colormap's` implementation contains a number of interesting code bits. The full source is part of the standard G'MIC script library, `gmic_stdlib.gmic`. You may browse a current copy at `gmic.eu/gmic_stdlib.gmic` or fork the project at `github.com` where `gmic_stdlib.gmic` can be found in the `src` directory. Fetch a copy for the following walk throughs.

* See David Tschumperlé's “Visualizing The 3D Point Clouds” at opensource.graphics