This article shows an implementation of the octree algorithm used to reduce the number of colors, finding the optimal palette of the image. The applications of the algorithm range from optimized drawing routines, graphic tools, file format conversion utilities.

For this purpose, I will use the CQuantizer class, developed in 1996-97 by Jeff Prosise, and described with 2 articles in the MSDN. The original code has been written to display images on 256-color display devices in the end of the 16-bit era; but nowadays some functions can be replaced, so I changed the memory allocation functions and removed the need of a device context, to make the class a bit more portable.

In this update there are only 2 minor changes. The first is a small bugfix in CQuantizer::ProcessImage, which causes strange results in small images (let's say icons) with 8 bit per pixel or less, when you try to reduce the number of colors down to 16 or less.

The second change is an improvement to avoid a limit of the octree algorithm: the reduction comes on the leafs of the tree, each of them hold 8 colors, and for less than 16 colors there are only 2 leafs; so the reduction for a really small number of colors needs a different process. This has been implemented in CQuantizer::SetColorTable, with the help of some additional information gathered by CQuantizer::GetPaletteColors.

original true-color image	reduction to 16 colors
reduction to 8 colors	reduction to 4 colors
all images are © Jairo Boudewyn [^]

The images above show some good results, achievable when the cromatic contents are not very complex, but don't pretend the same quality for all the kinds of images.

This example shows an application of CQuantizer with the CxImage class:

CxImage image("test.bmp",CXIMAGE_FORMAT_BMP);

CQuantizer q(16,8);
q.ProcessImage(image.GetDIB());
RGBQUAD* ppal=(RGBQUAD*)malloc(16*sizeof(RGBQUAD));
q.SetColorTable(ppal);
image.DecreaseBpp(4,ppal);
free(ppal);