Better GIFs with Octrees

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.


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

I incorporated QColorQuantizer in the latest version of Tinter, my work in progress with a plethora of bitmap tools. The first version demonstrated color matrices. Version 1.1 added sharpening and blurring tools. Version 1.2 had zooming capabilities and scanning support, and displayed image properties. This latest version has a new 'GIF Preview' command in the 'View' menu, and an option to create Web-safe or octree GIF files. In the preview window, you can switch between the two modes to study the difference. I didn't use a worker thread for color quantization. As an extra, I also added a command to change the size of the bitmap.


Note: for this project, your system must support GDI+, which currently only XP does natively. However, other Windows versions can be upgraded. Also, VC++ 6.0 comes without the GDI+ headers. You may obtain them by downloading the Windows Platform SDK. The GDI+ headers are included with VC++ 7.0.


Download demo project and source - 191 Kb
Download demo project executable only - 62 Kb


Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • U.S. companies are desperately trying to recruit and hire skilled software engineers and developers, but there's simply not enough quality talent to go around. In response, companies often resort to inferior solutions -- hiring substandard developers and engineers, recruiting talent on a part-time or temporary basis, poaching people from competitors, or burdening an already stressed IT staff for more of their labor. Fortunately, there's a better solution. Read this white paper to learn the business value of …

  • Lenovo recommends Windows 8 Pro. "I dropped my laptop getting out of the taxi." This probably sounds familiar to most IT professionals. If your employees are traveling, you know their devices are in for a rough go. Whether it's a trip to the conference room or a convention out of town, any time equipment leaves a user's desk it is at risk of being put into harm's way. Stay connected at all times, whether at the office or on the go, with agile, durable, and flexible devices like the Lenovo® …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date