Click here to Skip to main content
12,747,207 members (35,019 online)
Click here to Skip to main content
Add your own
alternative version


52 bookmarked
Posted 5 Oct 2001


, 3 Sep 2003 CPOL
Rate this:
Please Sign up or sign in to vote.
Color quantization using the octree algorithm


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, to graphic tools, to file format conversion utilities.

For this purpose, I will use the CQuantizer class, developed in 1996-97 by Jeff Prosise, and described with two 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.

What's new

In this update, there are only two minor changes. The first is a small bug-fix in CQuantizer::ProcessImage which causes strange results in small images (let's say icons) with 8 bits 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 inCQuantizer::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 chromatic contents are not very complex, but don't pretend the same quality for all the kinds of images.

Class Members & Operations

CQuantizer (UINT nMaxColors, UINT nColorBits)Construction and initialization. nMaxColors = maximum number of colors permitted in the palette. nColorBits = number of significant bits in each 8-bit color component. For example, nColorBits = 6 tells the algorithm to ignore the lower two bits of each color component. A setting of 5 or 6 generally produces a palette that is pleasing to the eye while keeping the octree's memory requirements to a reasonable minimum. nColorBits = 8 is required for reduction to 16 colors or less, when the precision is very important.
ProcessImage (HANDLE hImage)Processes the image to find the optimal palette. hImage = DIB image handle.
SetColorTable (RGBQUAD* prgb)Transfers the optimized palette to a RGBQUAD structure. The size of the structure must be at least nMaxColors.
GetColorCount ()Returns the number of colors found in the optimized palette.


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

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

CQuantizer q(16,8);
RGBQUAD* ppal=(RGBQUAD*)malloc(16*sizeof(RGBQUAD));


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

No Biography provided

You may also be interested in...

Comments and Discussions

QuestionIs there any way to quantize without dithering? Pin
JohnnyLightwave7-Feb-11 2:19
memberJohnnyLightwave7-Feb-11 2:19 
AnswerRe: Is there any way to quantize without dithering? Pin
Davide Pizzolato7-Feb-11 7:51
memberDavide Pizzolato7-Feb-11 7:51 
QuestionBetter than CxImage::Decrease? Pin
are_all_nicks_taken_or_what30-Nov-09 4:03
memberare_all_nicks_taken_or_what30-Nov-09 4:03 
AnswerRe: Better than CxImage::Decrease? Pin
Davide Pizzolato30-Nov-09 7:35
memberDavide Pizzolato30-Nov-09 7:35 
GeneralRe: Better than CxImage::Decrease? Pin
are_all_nicks_taken_or_what2-Dec-09 6:39
memberare_all_nicks_taken_or_what2-Dec-09 6:39 
Generalreally needs help .. can u provide Dll Pin
pravat_sagun8-Mar-07 0:46
memberpravat_sagun8-Mar-07 0:46 
Questionocttree-color-quantization in .net? Pin
benhold16-Nov-04 0:29
memberbenhold16-Nov-04 0:29 
GeneralImprovements Pin
baze`5-Sep-03 0:17
memberbaze`5-Sep-03 0:17 
GeneralRe: Improvements Pin
Davide Pizzolato5-Sep-03 13:12
memberDavide Pizzolato5-Sep-03 13:12 
GeneralCool Pin
Normski4-Sep-03 22:01
memberNormski4-Sep-03 22:01 
GeneralNice Pin
Chris Maunder4-Sep-03 17:49
adminChris Maunder4-Sep-03 17:49 
Generalnumber of colors Pin
Anonymous2-Jun-02 20:03
memberAnonymous2-Jun-02 20:03 
Generalhelp Pin
Jordancode1-Feb-02 23:22
memberJordancode1-Feb-02 23:22 
Questionhelp? Pin
Jordancode31-Jan-02 18:45
memberJordancode31-Jan-02 18:45 
AnswerRe: help? Pin
Davide Pizzolato31-Jan-02 20:57
memberDavide Pizzolato31-Jan-02 20:57 
GeneralOctree Pin
jodon17-Jan-02 15:34
memberjodon17-Jan-02 15:34 
GeneralRe: Octree Pin
Davide Pizzolato17-Jan-02 21:24
memberDavide Pizzolato17-Jan-02 21:24 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170215.1 | Last Updated 4 Sep 2003
Article Copyright 2001 by Davide Pizzolato
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid