【C】八叉树算法：BMP颜色降级生成调色板的算法
在一些特殊情况，我们需要将位图从24位真彩色压缩成256色。调色板的选取就变得很重要了，因为调色板决定了这256个颜色是什么样的颜色。如果一个以红色为主的位图用了蓝色较多的调色板，那么它的显示效果就会变得很差。因此，我们需要用一个比较好的算法来取得合适的调色板。
这就是八叉树算法。
八叉树算法的原理是通过建立一个“八叉树”，将图像中的颜色添加进八叉树，当颜色数量超过256色的时候合并八叉树的树叶，从而减少颜色。
最终产生的256个颜色将是最适合这个图片的颜色。
先放上应用了八叉树算法的效果图。
首先是原图：（图片来自pixiv，作者的ID是39656960，详情请看http://www.pixiv.net/member_illust.php?mode=manga&illust_id=39656960）
图片来自pixiv，作者的ID是39656960，详情请看http://www.pixiv.net/member_illust.php?mode=manga&illust_id=39656960
应用了八叉树算法，把图片降级成256色的时候，是如下图的效果：
是不是发现，尽管图片变成了256色，它看起来好像没什么变化呢？没错，这就是八叉树算法的作用了！
八叉树算法给这个图片产生了一个完美的调色板，然后就算图片颜色降级了，看起来也是一样的。
那么现在的重点，是讲讲八叉树算法的实现方法。
八叉树算法要建立一个八叉树，每个节点有8个子节点，共8级，一级一级的延伸下去，最后一级是“树叶”。
当你得到一张图片的时候，你需要把图片的每一个颜色添加进八叉树。怎么添加呢？首先你需要取得颜色的RGB值。
假定图片是24位真彩色，红绿蓝各占8位，也就是一个字节一个颜色值。这里举个例子，假设颜色是淡蓝色（红：240，绿：250，蓝：255），右边括号里的字就是这种颜色（你居然看到了！）
然后，你把红绿蓝的字节按照如下图的方式看：
颜色值的二进制位数 第7位 第6位 第5位 第4位 第3位 第2位 第1位 第0位
红色字节 1 1 1 1 0 0 0 0
绿色字节 1 1 1 1 1 0 1 0
蓝色字节 1 1 1 1 1 1 1 1
现在我们要做的就是把这张表中的数字竖着看，从各个位中间取出3个二进制位，组成一个0到7之间整数，然后这个整数就是这个颜色在八叉树中对应级的位置。看看上面的表，按照这样说的，第7位的三个二进制位组成数字111（十进制的7），那么我们就在八叉树的第0级第7个子节点处添加一个节点，然后第6位的三个二进制位组成数字111（十进制的7），那么我们就在八叉树的第1级第7个子节点处添加一个节点，以此类推。这样八叉树的树叶就在不断增多。当八叉树的树叶数量到达256的时候，我们就需要把一些叶子合并。通常就合并最后添加的颜色所在树枝的树叶。先合并树叶，合并完了再网上合并树枝。
最后，所有颜色采集完了以后，就遍历整个八叉树，取出所有树叶的颜色，这样就得到了调色板。
这里微软也有类似的资料，详情请看：
资料：
http://www.microsoft.com/msj/archive/S3F1.aspx
实例的源码：
http://www.microsoft.com/msj/archive/s3f1a.htm
在这里我贴出经过我修改，可以做成DLL的源码。回复可见。
**** Hidden Message ***** 系统自动沙发 lihai lihailihaihhahahahahhaha LZ你好
我用了你的代码生成了DLL然后写了个测试程序。
测试程序如下：
#pragma comment(lib, "Octree.lib")
#include <iostream>
#include <stdio.h>
#include <math.h>
#include "windows.h"
#include "Octree.h"
#include <math.h>
#include <stdlib.h>
using namespace std;
bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height, int biBitCount, PALETTEITEM *pColorTable)
{
//如果位图数据指针为0，则没有数据传入，函数返回
if(!imgBuf)
return 0;
//颜色表大小，以字节为单位，灰度图像颜色表为1024字节，彩色图像颜色表大小为0
int colorTablesize=0;
if(biBitCount==8)
colorTablesize=1024;
//待存储图像数据每行字节数为4的倍数
int lineByte=(width * biBitCount/8+3)/4*4;
//以二进制写的方式打开文件
FILE *fp=fopen(bmpName,"wb");
if(fp==0)
return 0;
//申请位图文件头结构变量，填写文件头信息
BITMAPFILEHEADER fileHead;
fileHead.bfType = 0x4D42;//bmp类型
//bfSize是图像文件4个组成部分之和
fileHead.bfSize= sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + colorTablesize + lineByte*height;
fileHead.bfReserved1 = 0;
fileHead.bfReserved2 = 0;
//bfOffBits是图像文件前3个部分所需空间之和
fileHead.bfOffBits=54+colorTablesize;
//写文件头进文件
fwrite(&fileHead, sizeof(BITMAPFILEHEADER),1, fp);
//申请位图信息头结构变量，填写信息头信息
BITMAPINFOHEADER head;
head.biBitCount=biBitCount;
head.biClrImportant=0;
head.biClrUsed=0;
head.biCompression=0;
head.biHeight=height;
head.biPlanes=1;
head.biSize=40;
head.biSizeImage=lineByte*height;
head.biWidth=width;
head.biXPelsPerMeter=0;
head.biYPelsPerMeter=0;
//写位图信息头进内存
fwrite(&head, sizeof(BITMAPINFOHEADER),1, fp);
//如果灰度图像，有颜色表，写入文件
if(biBitCount==8)
fwrite(pColorTable, sizeof(PALETTEITEM),256, fp);
//写位图数据进文件
fwrite(imgBuf, height*lineByte, 1, fp);
//关闭文件
fclose(fp);
return 1;
}
int main()
{
//与BMP相关的定义
BITMAPFILEHEADER bf;
BITMAPINFOHEADER bi;
byte bColor;
LONG biWidth=601; /* 以像素为单位说明图像的宽度 */
LONG biHeight=500;/* 以像素为单位说明图像的高度 *///100G的数据为1760
DWORD biSizeImage;
RGBQUAD *RGBquad; //调色板
int RealUsedColor = 0; //说明图像实际用到的颜色数，如果biClrUsed为0则颜色数为2的biBitCount次方
//打开输出的BMP文件
//行方向上像素的字节数必须是4的整数倍
unsigned long biFullWidth;
biFullWidth=ceil(biWidth/4.)*4;//灰度图像
FILE *fpIn;
if (!(fpIn = fopen("test_in.bmp", "rb"))) {
printf("can't create d:\testBMP.bmp");
return 0;
}
FILE *fpout;
if (!(fpout = fopen("test_out.bmp", "wb"))) {
printf("can't create d:\testBMP.bmp");
return 0;
}
fread(&bf, sizeof(BITMAPFILEHEADER), 1, fpIn);
fread(&bi, sizeof(BITMAPINFOHEADER), 1, fpIn);
//此处添加代码
/*
if(bi.biClrUsed == 0){RealUsedColor = 2^bi.biBitCount;}else{RealUsedColor = bi.biClrUsed;} //判断实际颜色数
for(int i = 0; i < RealUsedColor; i++) //读入调色盘
{
fread(&RGBquad.rgbBlue, 1, sizeof(BYTE), fpIn);
fread(&RGBquad.rgbGreen, 1, sizeof(BYTE), fpIn);
fread(&RGBquad.rgbRed, 1, sizeof(BYTE), fpIn);
fread(&RGBquad.rgbReserved, 1, sizeof(BYTE), fpIn);
}
cout<<RGBquad.rgbBlue;
*///真彩色图不用调色盘
if(bi.biBitCount == 8)//256色调色盘
{
RGBquad = new RGBQUAD;
fread(RGBquad, sizeof(RGBQUAD), 256, fpIn);
}
int Datalen = ((bi.biWidth*bi.biBitCount/8)+3)/4*4*bi.biHeight;//读取位图数据
BYTE *Bmpbuf = new BYTE;
fseek(fpIn, bf.bfOffBits,SEEK_SET);
fread(Bmpbuf, 1, Datalen, fpIn);
UINT uPitch = GetBitmapPitch(bi.biBitCount,bi.biWidth);
PALETTEITEM *pPaletteOut = new PALETTEITEM;
// BYTE *Bmpbuf = new BYTE;
CreateOctreePaletteRGB888(Bmpbuf, bi.biWidth, bi.biHeight, uPitch, 256, 8, pPaletteOut);
/*
for(int i=0;i<1024;i = i+3)
{
Bmpbuf = pPaletteOut.R;
Bmpbuf = pPaletteOut.G;
Bmpbuf = pPaletteOut.B;
}
*/
saveBmp("test_out.bmp", Bmpbuf, bi.biWidth, bi.biHeight, 8, pPaletteOut);
return 0;
}
这是我的运行结果：
很显然没有达到预期目的啊，不知是楼主的程序问题还是我的读写问题啊？
附上我的测试图片：
LZ的程序我调试着看过了，没有明显的循环错误之类的
今天有点晚，改天再看看 sx4452 发表于 2014-3-19 17:42
LZ的程序我调试着看过了，没有明显的循环错误之类的
今天有点晚，改天再看看 ...
我的程序我是亲自测试过没问题才放到论坛的，所以估计是你的程序出了问题。。
此外，同时包含stdio.h和iostream是个什么心态…… 0xAA55 发表于 2014-3-20 16:59
我的程序我是亲自测试过没问题才放到论坛的，所以估计是你的程序出了问题。。
此外，同时包含stdio.h和io ...
好吧 受教了 应该是我读写的问题 kankan 学习了。~ 哈哈，看一下:lol 想看看八叉树算法 谢谢分享 啊！才知道自己竟然没有使用Lena图！ 谢谢分享 学习了 来看看... 历害{:soso_e132:} 对应的磁盘空间会减少吗?