Jeff Prosise
Sometimes the code you write is only as good as the tools you have to help you. A case in point is Windows®-based code that displays static bitmaps. On 256-color display devices, a bitmap containing a wide range of colors looks good only if you create a palette to go with it. But that raises a question that’s as old as computer graphics itself: how do you know what colors to put in the palette?
One solution to the problem of picking palette colors is to use a color quantization algorithm like the one I presented in this column a year ago (August, 1996). Color quantization is the process of finding the optimal n colors with which to display an image that contains m colors, where m is greater than n. The August 1996 column introduced a Win32® implementation of the ultracool Gervautz-Purgathofer octree color quantization algorithm that, given a bitmap handle, quantizes the bitmap’s colors and returns a handle to a GDI palette representing the best combination of colors for displaying the image.
The CreateOctreePalette function presented in that column is great for generating palettes for arbitrary bitmapped images at runtime, but it leaves a little to be desired when you know ahead of time what images you’ll be displaying. Suppose you write an application that displays a colorful splash screen as it’s starting up. Furthermore, suppose that the splash screen is a bitmap and that the bitmap contains more than just the 20 static colors in the Windows system palette. Unless your application will run only on adapters that support 16 or 24-bit color, you need a palette to display the splash screen’s full range of colors. You could use CreateOctreePalette to generate a palette on-the-fly, but since color quantization is a time-consuming operation, doing it this way could delay the startup of your application by several seconds.
The better solution is to pick the palette colors at design time and write them into your code. Then there’s no delay waiting for the image to be quantized. The only question is how—I’ve yet to see a programming tool that will take an arbitrary bitmap and create an optimized color table formatted so that it can be plugged right into a C or C++ program. For lack of tools, many a developer has been reduced to using a graphics editor to compute palette colors and manually transposing the resulting RGB color values into source code.
Maybe you like to do it the hard way, but I don’t. That’s why I wrote PalGen, a handy palette-generating utility that takes as input one or more BMP files and outputs a text file containing a table of RGB color values. The table is a two-dimensional array of BYTEs that can be pasted into a C or C++ program. PalGen makes it trivial to compute static color palettes for the bitmaps your applications display. And because the input to the program can consist of multiple BMP files, you can easily create composite palettes suitable for displaying two or more images.
Figure 1: PalGen
When PalGen starts, you’ll see the window pictured in Figure 1. From there, you can generate a set of RGB color values in four easy steps:
PalGen’s text output file contains a color table formatted in the following manner:
// 236 entries
BYTE byVals[236][3] = {
255, 240, 36,
180, 64, 192,
[...]
};
Each row in the table identifies one palette color. The first number in the row is the color’s red component, the second number is the color’s green component, and the third number is the color’s blue component. Note that the actual number of colors in the table may be less than the maximum number you specified. If it’s substantially less—for example, if you set the maximum to 236 and PalGen outputs only 128 colors—that probably means the bitmap contains fewer colors than you realized.
How do you convert PalGen’s text output into a GDI palette? Easy. Suppose the output file contains the following statements:
// 8 entries
BYTE byVals[8][3] = {
255, 240, 36,
180, 64, 192,
4, 32, 200,
224, 85, 80,
224, 128, 0,
16, 0, 244,
122, 7, 114,
78, 255, 225
};
First, paste these statements into a source code file. Then create a LOGPALETTE structure containing one PALETTEENTRY structure for each color in the palette, copy the color values from the byVals array to the corresponding PALETTEENTRYs, and call CreatePalette with a pointer to the initialized LOGPALETTE structure. In MFC, that’s CPalette::CreatePalette. Figure 2 shows how it looks in code. Note that the number of PALETTEENTRY structures declared in the pal structure is one fewer than the number of colors in the palette. That’s because LOGPALETTE contains one PALETTEENTRY structure already.
Figure 2: Creating a GDI Palette
//
// Color table created by PalGen.
//
BYTE byVals[8][3] = {
255, 240, 36,
180, 64, 192,
4, 32, 200,
224, 85, 80,
224, 128, 0,
16, 0, 244,
122, 7, 114,
78, 255, 225
};
//
// Code to create a logical palette from the color table.
//
struct {
LOGPALETTE lp;
PALETTEENTRY ape[7]; // Number of palette entries minus 1
} pal;
LOGPALETTE* pLP = (LOGPALETTE*) &pal;
pLP->palVersion = 0x300;
pLP->palNumEntries = 8; // Number of palette entries
for (int i=0; i<pLP->palNumEntries; i++) {
pLP->palPalEntry[i].peRed = byVals[i][0];
pLP->palPalEntry[i].peGreen = byVals[i][1];
pLP->palPalEntry[i].peBlue = byVals[i][2];
pLP->palPalEntry[i].peFlags = 0;
}
HPALETTE hPalette = CreatePalette (pLP);
PalGen uses the same octree color quantization algorithm I described in Wicked Code a year ago. I reused much of my original code, but I also made two enhancements. First, I added code to handle 1, 4, and 8-bit DIBs. The code I presented last year worked only with 16, 24, and 32-bit formats. Second, I wrapped the palette generation algorithm in a handy C++ class named CQuantizer and generalized the code so that color values are returned as RGB triples. (The original implementation, which was written in C rather than C++, returned a palette handle. If you wanted RGB color values, you had to extract them from the palette.)
CQuantizer is an extremely useful class to have around if you do much graphics programming, because it understands all the Windows DIB section formats and also knows how to quantize colors. You can see how PalGen uses CQuantizer by peeking at PalGen’s source code, which you can download along with PalGen.exe from the MSJ Web site at http://www.microsoft.com/msj/. The remainder of this column describes how to use CQuantizer in your own applications.
CQuantizer makes generating custom color palettes a snap. The following statements create a CQuantizer object named q and a custom palette containing up to 128 colors from the image whose handle is stored in hImage:
CQuantizer q (128, 6);
q.ProcessImage (hImage);
The first value passed to CQuantizer’s constructor is the maximum number of colors permitted in the palette. The second specifies the number of significant bits in each 8-bit color component. Setting this value to 6 tells the octree algorithm to ignore the lower two bits of each red, green, or blue color value. 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.
You can call ProcessImage as many times as you’d like. To create a composite palette that will serve three different images, for example, call ProcessImage three times, each time with a different image handle. Handles passed to the ProcessImage function should refer to DIB sections, not device-dependent bitmaps (DDBs). For BMP files, this means that you should use the Win32 LoadImage function rather than LoadBitmap to load images from disk. Be sure to include a LR_CREATEDIBSECTION flag so LoadImage will know that you want to create a DIB section, as illustrated here:
HANDLE hImage = ::LoadImage (NULL,
"C:\\Images\\Fish.bmp",
IMAGE_BITMAP, 0, 0,
LR_LOADFROMFILE | LR_CREATEDIBSECTION);
In certain cases—specifically, when it’s called upon to process 1, 4, or 8-bit per pixel images on systems with palettized display adapters—ProcessImage can produce incorrect results if it’s passed a handle to a DDB.
After the final call to ProcessImage, use the CQuantizer::GetColorCount function to find out how many colors are in the palette, and use CQuantizer::GetColorTable to retrieve the colors. Given a pointer to an array of RGBQUAD structures, GetColorTable copies the palette colors to the array, as shown here:
UINT nNumColors = q.GetColorCount ();
RGBQUAD* prgb = new RGBQUAD[nNumColors];
q.GetColorTable (prgb);
Once the colors are retrieved, it’s a simple matter to convert them into a GDI palette, or to do as PalGen does and output the RGB color values to a file.
CQuantizer’s source code is reproduced in Figure 3. If you read the August 1996 column, much of the source code will look familiar to you. The most notable change (other than the fact that all the code is now part of a C++ class) is the code added to ProcessImage to support 1, 4, and 8-bit DIBs. Rather than reading the raw bitmap bits, ProcessImage uses the Win32 GetDIBits function to convert the DIB’s pixels to 24-bit RGB format one scan line at a time. Then it reads individual pixels by scanning the line from left to right using the same logic it uses to read 24-bit DIBs. The chief advantage to this technique is that CQuantizer doesn’t have to understand run-length encoded (RLE) bitmap formats. GetDIBits handles the unencoding, and ProcessImage neither knows nor cares whether the original bitmap data was stored in a compressed format.
There you have it: two new tools to add to your toolbox. Use PalGen to pick palette colors for images whose identities are known at design time, and CQuantizer to build palettes at runtime. With only a few extra lines of code, your bitmaps can look as good on 256-color screens as they do on true-color output devices.
Figure 3: The CQuantizer Class
Quantize.h
typedef struct _NODE {
BOOL bIsLeaf; // TRUE if node has no children
UINT nPixelCount; // Number of pixels represented by this leaf
UINT nRedSum; // Sum of red components
UINT nGreenSum; // Sum of green components
UINT nBlueSum; // Sum of blue components
struct _NODE* pChild[8]; // Pointers to child nodes
struct _NODE* pNext; // Pointer to next reducible node
} NODE;
class CQuantizer
{
protected:
NODE* m_pTree;
UINT m_nLeafCount;
NODE* m_pReducibleNodes[9];
UINT m_nMaxColors;
UINT m_nColorBits;
public:
CQuantizer (UINT nMaxColors, UINT nColorBits);
virtual ~CQuantizer ();
ProcessImage (HANDLE hImage);
UINT GetColorCount ();
void GetColorTable (RGBQUAD* prgb);
protected:
int GetLeftShiftCount (DWORD dwVal);
int GetRightShiftCount (DWORD dwVal);
void AddColor (NODE** ppNode, BYTE r, BYTE g, BYTE b, UINT nColorBits,
UINT nLevel, UINT* pLeafCount, NODE** pReducibleNodes);
NODE* CreateNode (UINT nLevel, UINT nColorBits, UINT* pLeafCount,
NODE** pReducibleNodes);
void ReduceTree (UINT nColorBits, UINT* pLeafCount,
NODE** pReducibleNodes);
void DeleteTree (NODE** ppNode);
void GetPaletteColors (NODE* pTree, RGBQUAD* prgb, UINT* pIndex);
};
Quantize.cpp
#include "stdafx.h"
#include "Quantize.h"
CQuantizer::CQuantizer (UINT nMaxColors, UINT nColorBits)
{
ASSERT (nColorBits <= 8);
m_pTree = NULL;
m_nLeafCount = 0;
for (int i=0; i<=(int) nColorBits; i++)
m_pReducibleNodes[i] = NULL;
m_nMaxColors = nMaxColors;
m_nColorBits = nColorBits;
}
CQuantizer::~CQuantizer ()
{
if (m_pTree != NULL)
DeleteTree (&m_pTree);
}
BOOL CQuantizer::ProcessImage (HANDLE hImage)
{
DWORD rmask, gmask, bmask;
int rright, gright, bright;
int rleft, gleft, bleft;
BYTE* pbBits;
WORD* pwBits;
DWORD* pdwBits;
BYTE r, g, b;
WORD wColor;
DWORD dwColor;
int i, j;
HDC hdc;
BYTE* pBuffer;
BITMAPINFO bmi;
DIBSECTION ds;
::GetObject (hImage, sizeof (ds), &ds);
int nPad = ds.dsBm.bmWidthBytes - (((ds.dsBmih.biWidth *
ds.dsBmih.biBitCount) + 7) / 8);
switch (ds.dsBmih.biBitCount) {
case 1: // 1-bit DIB
case 4: // 4-bit DIB
case 8: // 8-bit DIB
//
// The strategy here is to use ::GetDIBits to convert the
// image into a 24-bit DIB one scan line at a time. A pleasant
// side effect of using ::GetDIBits in this manner is that RLE-
// encoded 4-bit and 8-bit DIBs will be uncompressed.
//
hdc = ::GetDC (NULL);
pBuffer = new BYTE[ds.dsBmih.biWidth * 3];
::ZeroMemory (&bmi, sizeof (bmi));
bmi.bmiHeader.biSize = sizeof (BITMAPINFOHEADER);
bmi.bmiHeader.biWidth = ds.dsBmih.biWidth;
bmi.bmiHeader.biHeight = ds.dsBmih.biHeight;
bmi.bmiHeader.biPlanes = 1;
bmi.bmiHeader.biBitCount = 24;
bmi.bmiHeader.biCompression = BI_RGB;
for (i=0; i<ds.dsBmih.biHeight; i++) {
::GetDIBits (hdc, (HBITMAP) hImage, i, 1, pBuffer, &bmi,
DIB_RGB_COLORS);
pbBits = pBuffer;
for (j=0; j<ds.dsBmih.biWidth; j++) {
b = *pbBits++;
g = *pbBits++;
r = *pbBits++;
AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
m_pReducibleNodes);
while (m_nLeafCount > m_nMaxColors)
ReduceTree (m_nColorBits, &m_nLeafCount,
m_pReducibleNodes);
}
}
delete pBuffer;
::ReleaseDC (NULL, hdc);
break;
case 16: // 16-bit DIB
if (ds.dsBmih.biCompression == BI_BITFIELDS) {
rmask = ds.dsBitfields[0];
gmask = ds.dsBitfields[1];
bmask = ds.dsBitfields[2];
}
else {
rmask = 0x7C00;
gmask = 0x03E0;
bmask = 0x001F;
}
rright = GetRightShiftCount (rmask);
gright = GetRightShiftCount (gmask);
bright = GetRightShiftCount (bmask);
rleft = GetLeftShiftCount (rmask);
gleft = GetLeftShiftCount (gmask);
bleft = GetLeftShiftCount (bmask);
pwBits = (WORD*) ds.dsBm.bmBits;
for (i=0; i<ds.dsBmih.biHeight; i++) {
for (j=0; j<ds.dsBmih.biWidth; j++) {
wColor = *pwBits++;
b = (BYTE) (((wColor & (WORD) bmask) >> bright) << bleft);
g = (BYTE) (((wColor & (WORD) gmask) >> gright) << gleft);
r = (BYTE) (((wColor & (WORD) rmask) >> rright) << rleft);
AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
m_pReducibleNodes);
while (m_nLeafCount > m_nMaxColors)
ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
}
pwBits = (WORD*) (((BYTE*) pwBits) + nPad);
}
break;
case 24: // 24-bit DIB
pbBits = (BYTE*) ds.dsBm.bmBits;
for (i=0; i<ds.dsBmih.biHeight; i++) {
for (j=0; j<ds.dsBmih.biWidth; j++) {
b = *pbBits++;
g = *pbBits++;
r = *pbBits++;
AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
m_pReducibleNodes);
while (m_nLeafCount > m_nMaxColors)
ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
}
pbBits += nPad;
}
break;
case 32: // 32-bit DIB
if (ds.dsBmih.biCompression == BI_BITFIELDS) {
rmask = ds.dsBitfields[0];
gmask = ds.dsBitfields[1];
bmask = ds.dsBitfields[2];
}
else {
rmask = 0x00FF0000;
gmask = 0x0000FF00;
bmask = 0x000000FF;
}
rright = GetRightShiftCount (rmask);
gright = GetRightShiftCount (gmask);
bright = GetRightShiftCount (bmask);
pdwBits = (DWORD*) ds.dsBm.bmBits;
for (i=0; i<ds.dsBmih.biHeight; i++) {
for (j=0; j<ds.dsBmih.biWidth; j++) {
dwColor = *pdwBits++;
b = (BYTE) ((dwColor & bmask) >> bright);
g = (BYTE) ((dwColor & gmask) >> gright);
r = (BYTE) ((dwColor & rmask) >> rright);
AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
m_pReducibleNodes);
while (m_nLeafCount > m_nMaxColors)
ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
}
pdwBits = (DWORD*) (((BYTE*) pdwBits) + nPad);
}
break;
default: // Unrecognized color format
return FALSE;
}
return TRUE;
}
int CQuantizer::GetLeftShiftCount (DWORD dwVal)
{
int nCount = 0;
for (int i=0; i<sizeof (DWORD) * 8; i++) {
if (dwVal & 1)
nCount++;
dwVal >>= 1;
}
return (8 - nCount);
}
int CQuantizer::GetRightShiftCount (DWORD dwVal)
{
for (int i=0; i<sizeof (DWORD) * 8; i++) {
if (dwVal & 1)
return i;
dwVal >>= 1;
}
return -1;
}
void CQuantizer::AddColor (NODE** ppNode, BYTE r, BYTE g, BYTE b,
UINT nColorBits, UINT nLevel, UINT* pLeafCount, NODE** pReducibleNodes)
{
static BYTE mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
//
// If the node doesn't exist, create it.
//
if (*ppNode == NULL)
*ppNode = CreateNode (nLevel, nColorBits, pLeafCount,
pReducibleNodes);
//
// Update color information if it's a leaf node.
//
if ((*ppNode)->bIsLeaf) {
(*ppNode)->nPixelCount++;
(*ppNode)->nRedSum += r;
(*ppNode)->nGreenSum += g;
(*ppNode)->nBlueSum += b;
}
//
// Recurse a level deeper if the node is not a leaf.
//
else {
int shift = 7 - nLevel;
int nIndex = (((r & mask[nLevel]) >> shift) << 2) |
(((g & mask[nLevel]) >> shift) << 1) |
((b & mask[nLevel]) >> shift);
AddColor (&((*ppNode)->pChild[nIndex]), r, g, b, nColorBits,
nLevel + 1, pLeafCount, pReducibleNodes);
}
}
NODE* CQuantizer::CreateNode (UINT nLevel, UINT nColorBits, UINT* pLeafCount,
NODE** pReducibleNodes)
{
NODE* pNode;
if ((pNode = (NODE*) HeapAlloc (GetProcessHeap (), HEAP_ZERO_MEMORY,
sizeof (NODE))) == NULL)
return NULL;
pNode->bIsLeaf = (nLevel == nColorBits) ? TRUE : FALSE;
if (pNode->bIsLeaf)
(*pLeafCount)++;
else {
pNode->pNext = pReducibleNodes[nLevel];
pReducibleNodes[nLevel] = pNode;
}
return pNode;
}
void CQuantizer::ReduceTree (UINT nColorBits, UINT* pLeafCount,
NODE** pReducibleNodes)
{
//
// Find the deepest level containing at least one reducible node.
//
for (int i=nColorBits - 1; (i>0) && (pReducibleNodes[i] == NULL); i--);
//
// Reduce the node most recently added to the list at level i.
//
NODE* pNode = pReducibleNodes[i];
pReducibleNodes[i] = pNode->pNext;
UINT nRedSum = 0;
UINT nGreenSum = 0;
UINT nBlueSum = 0;
UINT nChildren = 0;
for (i=0; i<8; i++) {
if (pNode->pChild[i] != NULL) {
nRedSum += pNode->pChild[i]->nRedSum;
nGreenSum += pNode->pChild[i]->nGreenSum;
nBlueSum += pNode->pChild[i]->nBlueSum;
pNode->nPixelCount += pNode->pChild[i]->nPixelCount;
HeapFree (GetProcessHeap (), 0, pNode->pChild[i]);
pNode->pChild[i] = NULL;
nChildren++;
}
}
pNode->bIsLeaf = TRUE;
pNode->nRedSum = nRedSum;
pNode->nGreenSum = nGreenSum;
pNode->nBlueSum = nBlueSum;
*pLeafCount -= (nChildren - 1);
}
void CQuantizer::DeleteTree (NODE** ppNode)
{
for (int i=0; i<8; i++) {
if ((*ppNode)->pChild[i] != NULL)
DeleteTree (&((*ppNode)->pChild[i]));
}
HeapFree (GetProcessHeap (), 0, *ppNode);
*ppNode = NULL;
}
void CQuantizer::GetPaletteColors (NODE* pTree, RGBQUAD* prgb, UINT* pIndex)
{
if (pTree->bIsLeaf) {
prgb[*pIndex].rgbRed =
(BYTE) ((pTree->nRedSum) / (pTree->nPixelCount));
prgb[*pIndex].rgbGreen =
(BYTE) ((pTree->nGreenSum) / (pTree->nPixelCount));
prgb[*pIndex].rgbBlue =
(BYTE) ((pTree->nBlueSum) / (pTree->nPixelCount));
prgb[*pIndex].rgbReserved = 0;
(*pIndex)++;
}
else {
for (int i=0; i<8; i++) {
if (pTree->pChild[i] != NULL)
GetPaletteColors (pTree->pChild[i], prgb, pIndex);
}
}
}
UINT CQuantizer::GetColorCount ()
{
return m_nLeafCount;
}
void CQuantizer::GetColorTable (RGBQUAD* prgb)
{
UINT nIndex = 0;
GetPaletteColors (m_pTree, prgb, &nIndex);
}Are there tough Win32 programming questions you’d like to see answered in this column, or tools you’d like to see developed? If so, send me email at the address listed below. I regret that time doesn’t permit me to respond individually to all questions, but rest assured that I’ll read each and every one and consider all for inclusion in a future installment of Wicked Code.
To obtain complete source code listings, see the MSJ Web site at
http://www.microsoft.com/msj/.
Have a tricky issue dealing with Windows? Send your questions via email to Jeff Prosise: Jeffpro@msn.com