I spent a couple hours tonight toying with some adaptive algorithms, applying them to the problem of color reduction. I am often disappointed by the methods many programs used to reduce the number of colors in an image, such as octree methods. They are simply too harsh, and never seem to take into consideration how "important" a color is to the continuity of the image itself.

I applied an algorithm used for topology mapping of a set of points to the color space of an image (left).

I limited the algorithm to a maximum of 256 nodes, so there would be one node per output color. These nodes 'communicate' with each other, spreading across the color space so as to accumulate the least amount of error in their total approximation. Once the summed error of the network falls below a certain point, the nodes' coordinates are dumped as colors to an Adobe Color Table (.ACT) file, which is then loaded as a custom color table for indexed color conversion.

The algorithm is very sensitive to the density of colors in the color space. At first, I thought this might be bad, so I wrote some code to even the density out. Then, I realized this caused the algorithm to allocate more nodes to colors which are more common in the image. This really balanced the color usage out in a very nice way.

None of these images use any sort of dithering. There is a luminance histogram at the bottom of each image, and error statistics showing the total error between the pixels of that image and the original 24-bit version. These stats are NOT related to the histogram.

First test: twilight snow in Owatonna, MN (with some tail lights . . .)

Original 24-Bit image (16,777,216 colors)