G'MIC Color Mapping

Figure 1: New Orleans Fish: July, 2000

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.

  1. Median Cut Algorithm
  2. K-Means Algorithm

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