【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然后写了个测试程序。
测试程序如下：

1. #pragma comment(lib, "Octree.lib")
   
2. 
   
3. #include <iostream>
   
4. #include <stdio.h>
   
5. #include <math.h>
   
6. #include "windows.h"
   
7. #include "Octree.h"
   
8. #include <math.h>
   
9. #include <stdlib.h>
   
10. 
    
11. 
    
12. using namespace std;
    
13. 
    
14. bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height, int biBitCount, PALETTEITEM *pColorTable)
    
15. {
    
16. 
    
17.     //如果位图数据指针为0，则没有数据传入，函数返回
    
18. 
    
19.     if(!imgBuf)
    
20.         return 0;
    
21. 
    
22.     //颜色表大小，以字节为单位，灰度图像颜色表为1024字节，彩色图像颜色表大小为0
    
23. 
    
24.     int colorTablesize=0;
    
25. 
    
26.     if(biBitCount==8)
    
27.         colorTablesize=1024;
    
28. 
    
29.     //待存储图像数据每行字节数为4的倍数
    
30. 
    
31.     int lineByte=(width * biBitCount/8+3)/4*4;
    
32. 
    
33.     //以二进制写的方式打开文件
    
34. 
    
35.     FILE *fp=fopen(bmpName,"wb");
    
36. 
    
37.     if(fp==0)
    
38.         return 0;
    
39. 
    
40.     //申请位图文件头结构变量，填写文件头信息
    
41. 
    
42.     BITMAPFILEHEADER fileHead;
    
43. 
    
44.     fileHead.bfType = 0x4D42;//bmp类型
    
45. 
    
46.     //bfSize是图像文件4个组成部分之和
    
47. 
    
48.     fileHead.bfSize= sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + colorTablesize + lineByte*height;
    
49. 
    
50.     fileHead.bfReserved1 = 0;
    
51. 
    
52.     fileHead.bfReserved2 = 0;
    
53. 
    
54.     //bfOffBits是图像文件前3个部分所需空间之和
    
55. 
    
56.     fileHead.bfOffBits=54+colorTablesize;
    
57. 
    
58.     //写文件头进文件
    
59. 
    
60.     fwrite(&fileHead, sizeof(BITMAPFILEHEADER),1, fp);
    
61. 
    
62.     //申请位图信息头结构变量，填写信息头信息
    
63. 
    
64.     BITMAPINFOHEADER head;
    
65. 
    
66.     head.biBitCount=biBitCount;
    
67. 
    
68.     head.biClrImportant=0;
    
69. 
    
70.     head.biClrUsed=0;
    
71. 
    
72.     head.biCompression=0;
    
73. 
    
74.     head.biHeight=height;
    
75. 
    
76.     head.biPlanes=1;
    
77. 
    
78.     head.biSize=40;
    
79. 
    
80.     head.biSizeImage=lineByte*height;
    
81. 
    
82.     head.biWidth=width;
    
83. 
    
84.     head.biXPelsPerMeter=0;
    
85. 
    
86.     head.biYPelsPerMeter=0;
    
87. 
    
88.     //写位图信息头进内存
    
89. 
    
90.     fwrite(&head, sizeof(BITMAPINFOHEADER),1, fp);
    
91. 
    
92.     //如果灰度图像，有颜色表，写入文件
    
93. 
    
94.     if(biBitCount==8)
    
95.                 fwrite(pColorTable, sizeof(PALETTEITEM),256, fp);
    
96. 
    
97.     //写位图数据进文件
    
98. 
    
99.     fwrite(imgBuf, height*lineByte, 1, fp);
    
100. 
     
101.     //关闭文件
     
102. 
     
103.     fclose(fp);
     
104. 
     
105.     return 1;
     
106. 
     
107. }
     
108. 
     
109. 
     
110. 
     
111. 
     
112. int main()
     
113. {
     
114.         //与BMP相关的定义
     
115.         BITMAPFILEHEADER   bf;
     
116.         BITMAPINFOHEADER   bi;
     
117.         byte bColor[3];
     
118.         LONG        biWidth=601;   /* 以像素为单位说明图像的宽度 */
     
119.     LONG        biHeight=500;  /* 以像素为单位说明图像的高度 *///100G的数据为1760
     
120.         DWORD                biSizeImage;
     
121.         RGBQUAD                *RGBquad;                //调色板
     
122.         int RealUsedColor = 0;     //说明图像实际用到的颜色数，如果biClrUsed为0则颜色数为2的biBitCount次方
     
123. 
     
124.         //打开输出的BMP文件
     
125. 
     
126.         //行方向上像素的字节数必须是4的整数倍
     
127.         unsigned long biFullWidth;
     
128.         biFullWidth=ceil(biWidth/4.)*4;//灰度图像
     
129. 
     
130.         FILE *fpIn;
     
131.         if (!(fpIn = fopen("test_in.bmp", "rb"))) {
     
132.                 printf("can't create d:\testBMP.bmp");
     
133.                 return 0;
     
134.         }
     
135.         FILE *fpout;
     
136.         if (!(fpout = fopen("test_out.bmp", "wb"))) {
     
137.                 printf("can't create d:\testBMP.bmp");
     
138.                 return 0;
     
139.         }
     
140.         fread(&bf, sizeof(BITMAPFILEHEADER), 1, fpIn);
     
141.         fread(&bi, sizeof(BITMAPINFOHEADER), 1, fpIn);
     
142. 
     
143.        
     
144. 
     
145.         //此处添加代码
     
146.         /*
     
147.         if(bi.biClrUsed == 0){RealUsedColor = 2^bi.biBitCount;}else{RealUsedColor = bi.biClrUsed;} //判断实际颜色数
     
148.         for(int i = 0; i < RealUsedColor; i++)                    //读入调色盘
     
149.         {
     
150.                 fread(&RGBquad[i].rgbBlue, 1, sizeof(BYTE), fpIn);
     
151.                 fread(&RGBquad[i].rgbGreen, 1, sizeof(BYTE), fpIn);
     
152.                 fread(&RGBquad[i].rgbRed, 1, sizeof(BYTE), fpIn);
     
153.                 fread(&RGBquad[i].rgbReserved, 1, sizeof(BYTE), fpIn);
     
154.         }
     
155.         cout<<RGBquad[0].rgbBlue;
     
156.         *///真彩色图不用调色盘
     
157. 
     
158.         if(bi.biBitCount == 8)//256色调色盘
     
159.         {
     
160.                 RGBquad = new RGBQUAD[256];
     
161.                 fread(RGBquad, sizeof(RGBQUAD), 256, fpIn);
     
162.         }
     
163. 
     
164.         int Datalen = ((bi.biWidth*bi.biBitCount/8)+3)/4*4*bi.biHeight;//读取位图数据
     
165.         BYTE *Bmpbuf = new BYTE[Datalen];
     
166.         fseek(fpIn, bf.bfOffBits,SEEK_SET);
     
167.         fread(Bmpbuf, 1, Datalen, fpIn);
     
168. 
     
169.         UINT uPitch = GetBitmapPitch(bi.biBitCount,bi.biWidth);
     
170. 
     
171.         PALETTEITEM *pPaletteOut = new PALETTEITEM[256];
     
172. //        BYTE *Bmpbuf = new BYTE[256*4];
     
173. 
     
174.         CreateOctreePaletteRGB888(Bmpbuf, bi.biWidth, bi.biHeight, uPitch, 256, 8, pPaletteOut);
     
175.         /*
     
176.         for(int i=0;i<1024;i = i+3)
     
177.         {
     
178.                 Bmpbuf[i] = pPaletteOut[i/4].R;
     
179.                 Bmpbuf[i+1] = pPaletteOut[i/4].G;
     
180.                 Bmpbuf[i+2] = pPaletteOut[i/4].B;
     
181.         }
     
182.         */
     
183. 
     
184.         saveBmp("test_out.bmp", Bmpbuf, bi.biWidth, bi.biHeight, 8, pPaletteOut);
     
185.        
     
186. 
     
187. 
     
188.         return 0;
     
189. }
     
190. 
     
191. 
     
192. 
     
193. 
     
194. 
     
195. 
     

复制代码

这是我的运行结果：
      


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

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

历害{:soso_e132:}

0x01810

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