Environment: VC++ 6.0/7.0, Windows 98 and later, GDI+.

Original JPG picture	Default GIF picture	GIF picture after octree color quantization

QColorQuantizer Gets the Most out of Your Picture

GDI+, the new graphics API that was introduced with Windows XP, lets you save GIF files quite easily. That's a good thing, of course. However, the default GIF files GDI+ produces are not the most perfect ones. With a bit of extra work, we can do better.

Look at my portrait above. Left is the original bitmap picture in JPG format. The second picture shows how GDI+ transforms it to GIF format. At the right is another GIF picture, but this time the bitmap has been put through octree color quantization.

The problem

As most of you will know, GIF files contain only 256 colors at the most, far fewer than the average picture. What's needed is a way to find 256 or fewer colors that can be used to represent the original colors as genuinely as possible. These colors will fill the palette of the GIF file. This process is called 'color quantization.'

When GDI+ saves a bitmap in GIF format, it performs a very crude form of color quantization. It always uses the same color palette, mostly filled with the 216 'Web-safe colors.' In the early years of the Internet, these colors were the only ones to be displayed consistently by most browsers; hence the name. However, a fixed set of colors will almost never be the optimum palette for any given picture. On top of that, the 216 Web-safe colors were chosen purely on the basis of their technical merits (they uniformly divide the RGB color space), and not because of their visual qualities. As a consequence, the Web-safe palette (also called the 'halftone palette') contains many almost indiscernible purples and a lot of muddy greenish and brownish colors, whereas some more useable parts of the spectrum are seriously underpopulated.

Because it always uses a fixed palette, GDI+ doesn't even save bitmaps with fewer than 256 colors correctly in GIF format. Every color is changed into one of the Web-safe colors, deteriorating the picture.

Adaptive color quantization

Far better is 'adaptive' or 'optimized' color quantization. This helps in both cases. Bitmaps with 256 or fewer colors are saved as perfect GIFs. And it's remarkable to see that a photographic picture with the right color palette often displays almost as well as GDI+'s native 24 bits bitmap, with its 16,777,216 colors.

Adaptive color quantization is no trivial task, however. Quite a few algorithms have been invented, varying from complicated to very complicated. Color quantization is still the subject of intensive research; it is also important for computer vision and related areas.

For this project, I chose a very elegant method with the impressive name of the 'Gervautz-Purgathofer octree algorithm.' Michael Gervautz and Werner Purgathofer invented it, fifteen years ago, at the Technische Universität Wien in Austria. The 'octree' is the data structure that plays a key role in the algorithm.

I also investigated another algorithm, called the 'Heckbert median cut.' This yields different results which, according to some, are superior to those of the octree method. I found the difference to be extremely small, however, while 'median cut' was up to eight times slower, mainly because data often has to be sorted.

So, octree it is. The algorithm first collects all the colors used in the bitmap. Each new color is put in a tree structure. The big trick is that the tree structure is not allowed to grow more than 256 'leaves' (ending nodes). As soon as this is imminent, the tree is pruned. A number of leaves representing relatively few pixels with closely related colors are replaced with one leaf. Because the tree never grows beyond 256 leaves, there is never much data to handle. Therefore, the algorithm is quite efficient.

The tree structure used is the octree, in effect a three-dimensional tree in RGB color space. Every node can have up to eight child nodes. The leaves are points in the color space, and the higher nodes define paths to the leaves. The bits of the RGB color value are used to navigate in the octree. The highest bits of R, G, and B determine the first branch from the root, the next highest bits the second step, and so on. It's all very clever.

After all the color information is condensed in the octree, a color palette is created by iterating through the octree leaves. Notice that it may contain fewer than 256 colors, even if the source bitmap is very rich in color. Finally, the bitmap is scanned again. The 24-bit color information is replaced by an 8-bit index in the palette.

QColorQuantizer

I encapsulated my version of the octree in a single MFC class, QColorQuantizer. Using it is extremely simple. Just call one function:

  Bitmap * GetQuantized(Image * pSource, Mode mode);

The parameter pSource is a pointer to a bitmap of any GDI+ format. If all goes well, the function returns a pointer to a new color quantized bitmap of the same size, ready to be saved as a GIF file. If mode has the value WebSafe, the returned bitmap sports the rigid, Web-safe color palette. If mode has the value Octree, octree color quantization has been performed. If anything goes wrong (presumably because of a lack of memory), GetQuantized() returns NULL.

Because octree color quantization is a somewhat lengthy operation, there is an option to perform it in a separate worker thread. To do so, call the function:

  void MakeQuantized(Image * pSource, Mode mode, CWnd * pMsgWnd);

The parameters pSource and mode are identical to those of GetQuantized(). This function, however, returns immediately. When the quantization algorithm is finished, the window pointed to by pMsgWnd receives the special Windows message QM_COLORQUANTIZER. The LPARAM parameter of this message contains a pointer to a new quantized bitmap, or NULL in case of failure (the WPARAM parameter is not used).

In both cases, the calling function or the receiving window gets the ownership of the quantized bitmap and is responsible for deleting it. Actually, both functions have a few extra default parameters. See the source for details.

Tinter 1.3