[非原创] 用于将真彩色图像降级为索引图像的八叉树算法

时间：2010-10-27 来源：hoodlum1980

　　　　索引图像的尺寸比真彩色图像可以大幅降低，保存为256色索引图像只有真彩色图像的1/3 （bpp = 24）或 1/4 （bpp = 32），因为表示每个像素的数据从3或4个字节减少到 1 个字节。如果保存为16色索引图像则还能减小一半尺寸，不过16色图像的质量相比真彩图像实在过低，一般除非硬件限制（比如TC那样的图形模式下），在现在的条件下是很少再会用到的。

　　　　【原创性声明】：本文提到的算法和原始范例的源码来自参考文献。对八叉树的绘制，以及不需要修改显示器模式的条件下，展示八叉树算法生成的索引图像（原范例需要先把显示器调整为256色模式才能看到效果），把真彩色位图通过八叉树算法保存为BMP索引位图文件，属于我增加的代码。

　　　　对该算法的介绍请参考 Jeff Prosise 的文档，是英文的，那篇文章中讲解了该算法的核心思想，我在这里不做重复介绍。根据文档的内容，八叉树算法最早是在1988, M. Gervautz 和 W. Purgathofer 发表的论文《A Simple Method for Color Quantization: Octree Quantization.》中首次介绍的。这个算法非常简洁优美，其优美之处在于从一副具有很多色彩的图像中，提取出最能完美表达该图像颜色的调色板的过程。这个过程就是一个八叉树的生长和节点合并的过程。该算法的最大优点是效率高，占用内存少（仅需要不超过颜色数量+1 个节点，加上一些中间节点所占用的内存），比流行方法（扫描图像然后取最多像素数量的颜色组成调色板）好很多。下图就是从我修改后的范例的展示出来的结果而来，我重新排列了一下图像：

　　　　为了我想要的展示，我调整了原来范例的代码，提供了一个根据真彩色位图，创建出八叉树的代码，该代码主要来源于原来的范例，该算法的核心是用RGB通道的相应的位组成子结点的索引（从高位开始提取RGB分量中的位），来让树生长，每当叶子节点数量（代表一种颜色）超出最大颜色数量时，就选出一个最深的非叶子节点，将其收缩为叶子节点，最终的颜色值是用RGB分量的总和除以该节点代表的像素数量来得到的（代码中引用到的某些辅助方法在此省略）：

Code_CreateOcTree

//根据一个图像，创建一个八叉树，hoodlum1980 add;
NODE* BuildOctree(HANDLE hImage, UINT nMaxColors, UINT nColorBits)
{
    DIBSECTION ds;
    int i, j, nPad;
    BYTE* pbBits;
    WORD* pwBits;
    DWORD* pdwBits;
    DWORD rmask, gmask, bmask;
    int rright, gright, bright;
    int rleft, gleft, bleft;
    BYTE r, g, b;
    WORD wColor;
    DWORD dwColor;
    NODE* pTree;
    UINT nLeafCount, nIndex;
    NODE* pReducibleNodes[9];

    // Initialize octree variables
    g_nMaxPixelCount = 0;

    pTree = NULL;
    nLeafCount = 0;
    if (nColorBits > 8) // Just in case
        return NULL;
    for (i=0; i<=(int) nColorBits; i++)
        pReducibleNodes[i] = NULL;

    // Scan the DIB and build the octree
    GetObject (hImage, sizeof (ds), &ds);
    nPad = ds.dsBm.bmWidthBytes - (((ds.dsBmih.biWidth *
        ds.dsBmih.biBitCount) + 7) / 8);

    switch (ds.dsBmih.biBitCount) {

    case 16: // One case for 16-bit DIBs
        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 (&pTree, r, g, b, nColorBits, 0, &nLeafCount,
                          pReducibleNodes);
                while (nLeafCount > nMaxColors)
                    ReduceTree (nColorBits, &nLeafCount, pReducibleNodes);
            }
            pwBits = (WORD*) (((BYTE*) pwBits) + nPad);
        }
        break;

    case 24: // Another for 24-bit DIBs
        pbBits = (BYTE*) ds.dsBm.bmBits;
        for (i=0; i<ds.dsBmih.biHeight; i++) {
            for (j=0; j<ds.dsBmih.biWidth; j++) {
                //*pbBits = 0xff;
                b = *pbBits++;
                g = *pbBits++;
                r = *pbBits++;
                AddColor (&pTree, r, g, b, nColorBits, 0, &nLeafCount,
                          pReducibleNodes);
                while (nLeafCount > nMaxColors)
                    ReduceTree (nColorBits, &nLeafCount, pReducibleNodes);
            }
            pbBits += nPad;
        }
        break;

    case 32: // And another for 32-bit DIBs
        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 (&pTree, r, g, b, nColorBits, 0, &nLeafCount,
                          pReducibleNodes);
                while (nLeafCount > nMaxColors)
                    ReduceTree (nColorBits, &nLeafCount, pReducibleNodes);
            }
            pdwBits = (DWORD*) (((BYTE*) pdwBits) + nPad);
        }
        break;

    default: // DIB must be 16, 24, or 32-bit!
        return NULL;
    }

    // 现在第二次遍历像素，把它复成调色板的值~
    //得到调色板
    nIndex = 0;
    GetRGBQUADs (pTree, g_pColors, &nIndex);
    g_nColorCount_Real = nIndex; //实际调色板数量（小于等于最大颜色数量）

    return pTree;
}

　　　　上面的方法返回一个八叉树的根节点指针，然后我们就可以根据这棵树，生成索引图像和调色板，方法是重新遍历图像，根据RGB的值，在树之间向更深的方向导航，直到遇到叶子节点，那么叶子节点上可以计算出该像素在索引图像的中的RGB值。在另存为 BMP 时，这个RGB值被放到索引图像的调色板中。下面的方法，我用一个24BPP的像素数据去模拟出索引图像的显示效果，因此 g_lpBits 是一块24bpp的图像处理，但是我将它设置成降级后的颜色，并在窗口中展示出来：

Code_CreateOctreeBitmap

//生成八叉树降级后的位图
void CreateOctreeBitmap (NODE* pTree, UINT nMaxColors, UINT nColorBits)
{
    int bpp = g_BmInfo.bmiHeader.biBitCount;
    static BYTE mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
    
    // 现在第二次遍历像素，把它复成调色板的值~
    int i, j;
    UINT nIndex, nLevel, shift;
    NODE* pNode = NULL;
    BYTE *pbBits, r, g, b;
    int stride = (g_BmInfo.bmiHeader.biWidth * bpp + 31)/32 *4;
    int nPad = stride - (g_BmInfo.bmiHeader.biWidth *bpp + 7) / 8;
    
    if(bpp == 24 || bpp == 32)
    {
        pbBits = (BYTE*) g_lpBits;
        for (i=0; i<g_BmInfo.bmiHeader.biHeight; i++) 
        {
            for (j=0; j<g_BmInfo.bmiHeader.biWidth; j++) 
            {
                //*pbBits = 0xff;
                b = *pbBits;
                g = *(pbBits+1);
                r = *(pbBits+2);
                
                pNode = pTree;
                nLevel = 0;
                while(!pNode->bIsLeaf)
                {
                    shift = 7 - nLevel;
                    nIndex = (((r & mask[nLevel]) >> shift) << 2) |
                        (((g & mask[nLevel]) >> shift) << 1) |
                        ((b & mask[nLevel]) >> shift);
                    pNode = pNode->pChild[nIndex];
                    nLevel++;
                }
                //取颜色
                *pbBits = (BYTE)(pNode->nBlueSum/pNode->nPixelCount);
                *(pbBits+1)= (BYTE)(pNode->nGreenSum/pNode->nPixelCount);
                *(pbBits+2)= (BYTE)(pNode->nRedSum/pNode->nPixelCount);

                pbBits += (bpp/8);
            }
            pbBits += nPad;
        }
    }
    return;
}

　　　　最后是用我的代码绘制出的八叉树效果，绘制是通过递归函数来完成的，这个代码并不复杂，这里我就不贴了。在这里假设每个节点具有一个面向的方向，例如根节点是面向下方生长，其角度就是PI/2。然后向八个角度方向生长出子结点，通过递归调用绘制出整个树，中间节点是空白的圆形，叶子节点代表调色板中的一个颜色，并且用该调色板颜色填充。

　　　　通过调整参数（树枝长短，节点占据的角度等）可以绘制出各种形态的八叉树，在源码中我把代表像素数量较多的节点绘制的更大一些，代表像素数量少的绘制小一些。下面是一些早期绘制出来的八叉树，有些因为角度关系，不能看出根节点在何处。我还想制作出八叉树的生成和合并过程的动画，不过展示还没有写这部分代码。

　　　　最后是我修改后的范例的源码下载连接：

　　　　http://files.cnblogs.com/hoodlum1980/Colors_src.rar

　　　　这里简单介绍该范例的使用方法，用菜单打开，打开一个真彩色的BMP位图，然后点击Optimized Palette 菜单可以弹出一个对话框，在该对话框中，设置的第一项 SignicantColorBits 表示八叉树的深度可以最大达到多大（1~8，默认值为6），在颜色被降级以后，由于树的深度会减小，所以该值设置的太大的话也没有什么意义。MaxColorCount 表示索引图像最多的颜色数量（1~256）。其他两个为显示值，一个是实际调色板数量，在保存为BMP索引图像时，我将使用八叉树代表的实际的调色板数量（而不是固定为16或者256）。另一个是表示八叉树中的所有叶子节点中，每个叶子节点都有一个属性：所代表的像素数量，g_nMaxPixelCount 表示的它们中的最大值。在生成索引图像以后，即可看到下方显示出索引图像的视觉效果，右侧是其调色板。在View菜单中点击“重新绘制八叉树图”，即可看到我绘制的八叉树的图像。通过View下面的其他两个菜单切换显示位图或者八叉树图。

　　　　这里是原始范例的代码：

　　　　http://www.microsoft.com/msj/archive/s3f1a.htm

　　　　注意，如果要使用这个程序之前，必须先把显示器调整到256色模式（XP中隐藏了低级别模式，需要点击监视器的高级按钮），然后点击Option下面的菜单可以看到不同调色板对应的索引图像效果。

　　　　参考资料：

　　　　（1）http://www.microsoft.com/msj/archive/S3F1.aspx；

　　　　　　<<wicked code>> -- Jeff Prosise