The problem: You want to display an image that has n colors in it. You can only get m colors, where m<n. What colors do you use?
As explained in "Color Allocation in xv" , colors on a non- TrueColor X display are a scarce resource. You can't guarantee that you'll get as many colors as you might like. You can't even know ahead of time how many colors you will succeed in getting. As such, the first step of all of the color allocation algorithms is to sort the colors in order of decreasing 'importance'. The colors are then allocated in this order, so that if the color allocation fails after m colors, then at least we allocated the m most 'important' colors.
This sorting algorithm is called the Diversity Algorithm, and is described in detail here. While the algorithms described in "Color Allocation in xv" are probably only of use to other X programmers (or programmers using other windowing systems with shared colormap resources), the Diversity Algorithm should be of use to anyone who has to display an image using fewer colors than they'd like to have. As far as I know, the Diversity Algorithm is an original algorithm designed for this program.
There are many different criteria that one could use to define which colors in an image are 'important'.
The most naive approach would be to simply ignore the question, and just use the first m colors from the colormap. This is clearly unacceptable. The entries in a colormap are generally not sorted in any order whatsoever. Even when the colors are sorted in some order, it's not likely that it will be a useful order.
For example, in a normal greyscale picture, there is an implied colormap consisting of a continuous collection of greys, with black at the beginning, and white at the end. If a program were to only use the first few colors from this colormap, it would have several shades of black, but no whites, or even middle greys.
A method of determining a color's importance to the overall picture quality is needed.
A color's 'importance' can be determined intuitively by asking the question "If we can only use one of these two colors, which one would make the picture look better?". The goal is to have the picture be recognizable with very few colors. Additional colors should smooth out color gradation, but should not add significant detail, nor change the color balance of the overall picture.
Picking colors in this order is not a trivial task, and is open to some degree of subjectivity. One method might involve calculating a histogram of the data to find out which colors are used the most often (i.e., which colors have the greatest number of pixels associated with them), and using those colors first. This is certainly a valid approach, but it places too much emphasis on large, uniformly colored regions, such as backgrounds. This is not generally where the 'interesting' portion of the picture is found.
For example, assume a picture that consists of a blue background, with a relatively small red square on it. Furthermore, suppose that the background isn't just one solid shade of blue, but is actually made up of three shades of blue ( light blue, dark blue, and medium blue, to give them names). Finally, assume that a histogram has been computed, and light blue has been found to be the most prevalent color, followed by medium blue, dark blue, and red, in that order.
Now, attempt to display this picture using only two colors. Which two should be used? If the selection criteria is simply 'in order of decreasing usage', light blue and medium blue would be picked. However, if this is done the red square will disappear completely (as red will wind up being 'approximated' by one of the two blues). Clearly the solution is to use red and one of the blues. Which blue, though? It could be argued that since there are three blues and only one of them can be used, middle blue should be selected, since it is the 'average' blue. This is where it gets somewhat subjective. The Diversity Algorithm would pick light blue, since it is used more than the others. When possible, the algorithm will try to maximize the number of pixels that are 'correct' (i.e. exactly what was asked for), rather than trying to minimize the total error of the picture. This way, additional colors smooth out gradations, rather than changing the overall color balance of the picture.
Suppose that a small yellow circle is added to the picture described above. If the problem is still 'display this picture using only two colors', then it cannot be resolved in any satisfactory method. There are no two colors that will adequately display red, yellow, and blue simultaneously . No matter what colors are used, one of the three major colors will be lost. As this is now a no-win scenario, it is no longer very interesting. It doesn't matter what colors are picked, since it will look bad regardless. However, if the problem is changed, and three colors can now be selected, it is intuitively obvious that yellow, red, and one of the blues should be selected.
So, the question is, "what is being maximized when colors are selected in this manner?" Certainly, since the blue regions are so much larger than the red and yellow regions, any rule based on the number of pixels satisfied by the color choice is irrelevant. What is being maximized is the diversity of the colors. By picking colors that are as unlike each other as possible, we wind up covering the 'inhabited' portion of the RGB color space as quickly as possible.
As a general rule, this tends to bring out the major details (such as objects) in the picture first, since the details are likely to involve contrasting colors. As more colors are picked, gaps in the RGB space are filled in. This smoothes out the color gradations, and brings out lesser detail (such as texture).
The algorithm operates as follows:
d = [ (r1 - r2)^2 + (g1 - g2)^2 + (b1 - b2)^2 ]^1/2
where r1,g1,b1 are the RGB components of one color, and r2,g2,b2 are the RGB components of another color. d is the computed distance between the two colors.
Tom Lane of the Independent JPEG Group came up with a couple of improvements to the Diversity Algorithm, resulting in the Modified Diversity Algorithm, which is what xv currently uses. He rightly pointed out that, on displays with an intermediate number of colors (~64), too much emphasis was being placed on getting 'different' colors, and not enough emphasis was placed on getting the 'correct' colors. His idea was to modify the sorting criteria slightly, to better balance the allocation between diverse colors and 'popular' colors (colors with high 'pixel counts'). His solution to the problem was to alternate between picking colors based on diversity and based on popularity.
In the Modified Diversity Algorithm, as implemented in xv, the first color picked is the most-popular color. The second color picked is the color furthest away from the first color. The third through tenth colors picked are all picked using the normal Diversity Algorithm. The eleventh color picked is picked on popularity, (the un-picked color with the highest 'pixel count' is chosen). The twelfth color is once again picked on diversity. The thirteenth color is chosen on popularity, and so on, alternating, until all the colors have been picked.
It should be pointed out that there's a fair amount of subjectivity here, and certainly different fine-tunings of the color picking order will make some pictures look better, and other pictures look worse. Tom originally had the algorithm pick colors alternately based on diversity and popularity right from the first color. (The first color picked on popularity, the second on diversity, the third on popularity, etc.) I felt that this broke the algorithm for displays with very few colors (<16), and proposed the strategy described above. (First color picked on popularity, the next ten colors picked on diversity, remaining colors alternately picked on popularity and diversity.)
Tom's other major modification to the Diversity Algorithm was to rewrite it so that 'diverse' colors are picked in O(n^2) time, instead of O(n^3) time. Applied cleverness is a useful thing!
For further information, consult the source code. (The function 'SortColors()' in the file 'xvcolor.c'.)
