【C】八叉树算法：BMP颜色降级生成调色板的算法

0xAA55

在一些特殊情况，我们需要将位图从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的源码。回复可见。

游客，如果您要查看本帖隐藏内容请回复

系统

系统自动沙发

sx4452

lihai lihailihaihhahahahahhaha

sx4452

LZ你好
我用了你的代码生成了DLL然后写了个测试程序。
测试程序如下：

[C++] 纯文本查看 复制代码

#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[3];
	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[i].rgbBlue, 1, sizeof(BYTE), fpIn);
		fread(&RGBquad[i].rgbGreen, 1, sizeof(BYTE), fpIn);
		fread(&RGBquad[i].rgbRed, 1, sizeof(BYTE), fpIn);
		fread(&RGBquad[i].rgbReserved, 1, sizeof(BYTE), fpIn);
	}
	cout<<RGBquad[0].rgbBlue;
	*///真彩色图不用调色盘

	if(bi.biBitCount == 8)//256色调色盘
	{
		RGBquad = new RGBQUAD[256];
		fread(RGBquad, sizeof(RGBQUAD), 256, fpIn);
	}

	int Datalen = ((bi.biWidth*bi.biBitCount/8)+3)/4*4*bi.biHeight;//读取位图数据
	BYTE *Bmpbuf = new BYTE[Datalen];
	fseek(fpIn, bf.bfOffBits,SEEK_SET);
 	fread(Bmpbuf, 1, Datalen, fpIn);

	UINT uPitch = GetBitmapPitch(bi.biBitCount,bi.biWidth);

	PALETTEITEM *pPaletteOut = new PALETTEITEM[256];
//	BYTE *Bmpbuf = new BYTE[256*4];

	CreateOctreePaletteRGB888(Bmpbuf, bi.biWidth, bi.biHeight, uPitch, 256, 8, pPaletteOut);
	/*
	for(int i=0;i<1024;i = i+3)
	{
		Bmpbuf[i] = pPaletteOut[i/4].R;
		Bmpbuf[i+1] = pPaletteOut[i/4].G;
		Bmpbuf[i+2] = pPaletteOut[i/4].B;
	}
	*/

	saveBmp("test_out.bmp", Bmpbuf, bi.biWidth, bi.biHeight, 8, pPaletteOut);
	


	return 0;
}

这是我的运行结果：
      


很显然没有达到预期目的啊，不知是楼主的程序问题还是我的读写问题啊？
附上我的测试图片： test_in.rar (321.85 KB, 下载次数: 4)

2014-3-20 01:39 上传

点击文件名下载附件

sx4452

LZ的程序我调试着看过了，没有明显的循环错误之类的
今天有点晚，改天再看看

0xAA55

sx4452 发表于 2014-3-19 17:42
LZ的程序我调试着看过了，没有明显的循环错误之类的
今天有点晚，改天再看看 ...

我的程序我是亲自测试过没问题才放到论坛的，所以估计是你的程序出了问题。。
此外，同时包含stdio.h和iostream是个什么心态……

sx4452

0xAA55 发表于 2014-3-20 16:59
我的程序我是亲自测试过没问题才放到论坛的，所以估计是你的程序出了问题。。
此外，同时包含stdio.h和io ...

好吧 受教了 应该是我读写的问题

jssyxzy

kankan                           

我有个梦

学习了。~

fenghuangyuan

哈哈，看一下

因为你

想看看八叉树算法

Lee

谢谢分享

0xAA55

啊！才知道自己竟然没有使用Lena图！

控⑨基

谢谢分享 学习了

mzflz

来看看...

XMStudent

0x01810

对应的磁盘空间会减少吗?