找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 43332|回复: 68

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

  [复制链接]

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2014-3-1 19:03:41 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
在一些特殊情况,我们需要将位图从24位真彩色压缩成256色。调色板的选取就变得很重要了,因为调色板决定了这256个颜色是什么样的颜色。
如果一个以红色为主的位图用了蓝色较多的调色板,那么它的显示效果就会变得很差。因此,我们需要用一个比较好的算法来取得合适的调色板。
这就是八叉树算法。
八叉树算法的原理是通过建立一个“八叉树”,将图像中的颜色添加进八叉树,当颜色数量超过256色的时候合并八叉树的树叶,从而减少颜色。
最终产生的256个颜色将是最适合这个图片的颜色。
先放上应用了八叉树算法的效果图。
首先是原图:(图片来自pixiv,作者的ID是39656960,详情请看http://www.pixiv.net/member_illust.php?mode=manga&illust_id=39656960
狛枝.jpg
图片来自pixiv,作者的ID是39656960,详情请看http://www.pixiv.net/member_illust.php?mode=manga&illust_id=39656960
应用了八叉树算法,把图片降级成256色的时候,是如下图的效果:

Octree.gif
是不是发现,尽管图片变成了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的源码。回复可见。
游客,如果您要查看本帖隐藏内容请回复

本帖被以下淘专辑推荐:

回复

使用道具 举报

4

主题

24

回帖

286

积分

用户组: 中·技术宅

UID
32
精华
0
威望
6 点
宅币
245 个
贡献
1 次
宅之契约
0 份
在线时间
45 小时
注册时间
2014-2-7
发表于 2014-3-15 00:19:09 | 显示全部楼层
系统自动沙发
回复 赞! 靠!

使用道具 举报

0

主题

5

回帖

42

积分

用户组: 初·技术宅

UID
132
精华
0
威望
1 点
宅币
35 个
贡献
0 次
宅之契约
0 份
在线时间
2 小时
注册时间
2014-3-19
发表于 2014-3-19 19:35:04 | 显示全部楼层
lihai lihailihaihhahahahahhaha
回复 赞! 靠!

使用道具 举报

0

主题

5

回帖

42

积分

用户组: 初·技术宅

UID
132
精华
0
威望
1 点
宅币
35 个
贡献
0 次
宅之契约
0 份
在线时间
2 小时
注册时间
2014-3-19
发表于 2014-3-20 01:39:59 | 显示全部楼层
LZ你好
我用了你的代码生成了DLL然后写了个测试程序。
测试程序如下:
  1. #pragma comment(lib, "Octree.lib")

  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <math.h>
  5. #include "windows.h"
  6. #include "Octree.h"
  7. #include <math.h>
  8. #include <stdlib.h>


  9. using namespace std;

  10. bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height, int biBitCount, PALETTEITEM *pColorTable)
  11. {

  12.     //如果位图数据指针为0,则没有数据传入,函数返回

  13.     if(!imgBuf)
  14.         return 0;

  15.     //颜色表大小,以字节为单位,灰度图像颜色表为1024字节,彩色图像颜色表大小为0

  16.     int colorTablesize=0;

  17.     if(biBitCount==8)
  18.         colorTablesize=1024;

  19.     //待存储图像数据每行字节数为4的倍数

  20.     int lineByte=(width * biBitCount/8+3)/4*4;

  21.     //以二进制写的方式打开文件

  22.     FILE *fp=fopen(bmpName,"wb");

  23.     if(fp==0)
  24.         return 0;

  25.     //申请位图文件头结构变量,填写文件头信息

  26.     BITMAPFILEHEADER fileHead;

  27.     fileHead.bfType = 0x4D42;//bmp类型

  28.     //bfSize是图像文件4个组成部分之和

  29.     fileHead.bfSize= sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + colorTablesize + lineByte*height;

  30.     fileHead.bfReserved1 = 0;

  31.     fileHead.bfReserved2 = 0;

  32.     //bfOffBits是图像文件前3个部分所需空间之和

  33.     fileHead.bfOffBits=54+colorTablesize;

  34.     //写文件头进文件

  35.     fwrite(&fileHead, sizeof(BITMAPFILEHEADER),1, fp);

  36.     //申请位图信息头结构变量,填写信息头信息

  37.     BITMAPINFOHEADER head;

  38.     head.biBitCount=biBitCount;

  39.     head.biClrImportant=0;

  40.     head.biClrUsed=0;

  41.     head.biCompression=0;

  42.     head.biHeight=height;

  43.     head.biPlanes=1;

  44.     head.biSize=40;

  45.     head.biSizeImage=lineByte*height;

  46.     head.biWidth=width;

  47.     head.biXPelsPerMeter=0;

  48.     head.biYPelsPerMeter=0;

  49.     //写位图信息头进内存

  50.     fwrite(&head, sizeof(BITMAPINFOHEADER),1, fp);

  51.     //如果灰度图像,有颜色表,写入文件

  52.     if(biBitCount==8)
  53.                 fwrite(pColorTable, sizeof(PALETTEITEM),256, fp);

  54.     //写位图数据进文件

  55.     fwrite(imgBuf, height*lineByte, 1, fp);

  56.     //关闭文件

  57.     fclose(fp);

  58.     return 1;

  59. }




  60. int main()
  61. {
  62.         //与BMP相关的定义
  63.         BITMAPFILEHEADER   bf;
  64.         BITMAPINFOHEADER   bi;
  65.         byte bColor[3];
  66.         LONG        biWidth=601;   /* 以像素为单位说明图像的宽度 */
  67.     LONG        biHeight=500;  /* 以像素为单位说明图像的高度 *///100G的数据为1760
  68.         DWORD                biSizeImage;
  69.         RGBQUAD                *RGBquad;                //调色板
  70.         int RealUsedColor = 0;     //说明图像实际用到的颜色数,如果biClrUsed为0则颜色数为2的biBitCount次方

  71.         //打开输出的BMP文件

  72.         //行方向上像素的字节数必须是4的整数倍
  73.         unsigned long biFullWidth;
  74.         biFullWidth=ceil(biWidth/4.)*4;//灰度图像

  75.         FILE *fpIn;
  76.         if (!(fpIn = fopen("test_in.bmp", "rb"))) {
  77.                 printf("can't create d:\testBMP.bmp");
  78.                 return 0;
  79.         }
  80.         FILE *fpout;
  81.         if (!(fpout = fopen("test_out.bmp", "wb"))) {
  82.                 printf("can't create d:\testBMP.bmp");
  83.                 return 0;
  84.         }
  85.         fread(&bf, sizeof(BITMAPFILEHEADER), 1, fpIn);
  86.         fread(&bi, sizeof(BITMAPINFOHEADER), 1, fpIn);

  87.        

  88.         //此处添加代码
  89.         /*
  90.         if(bi.biClrUsed == 0){RealUsedColor = 2^bi.biBitCount;}else{RealUsedColor = bi.biClrUsed;} //判断实际颜色数
  91.         for(int i = 0; i < RealUsedColor; i++)                    //读入调色盘
  92.         {
  93.                 fread(&RGBquad[i].rgbBlue, 1, sizeof(BYTE), fpIn);
  94.                 fread(&RGBquad[i].rgbGreen, 1, sizeof(BYTE), fpIn);
  95.                 fread(&RGBquad[i].rgbRed, 1, sizeof(BYTE), fpIn);
  96.                 fread(&RGBquad[i].rgbReserved, 1, sizeof(BYTE), fpIn);
  97.         }
  98.         cout<<RGBquad[0].rgbBlue;
  99.         *///真彩色图不用调色盘

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

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

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

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

  112.         CreateOctreePaletteRGB888(Bmpbuf, bi.biWidth, bi.biHeight, uPitch, 256, 8, pPaletteOut);
  113.         /*
  114.         for(int i=0;i<1024;i = i+3)
  115.         {
  116.                 Bmpbuf[i] = pPaletteOut[i/4].R;
  117.                 Bmpbuf[i+1] = pPaletteOut[i/4].G;
  118.                 Bmpbuf[i+2] = pPaletteOut[i/4].B;
  119.         }
  120.         */

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


  123.         return 0;
  124. }






复制代码



这是我的运行结果:
8cb1cb13495409234a475ec09058d109b3de4965.jpg        a044ad345982b2b7b50f047a33adcbef77099bff.jpg


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

使用道具 举报

0

主题

5

回帖

42

积分

用户组: 初·技术宅

UID
132
精华
0
威望
1 点
宅币
35 个
贡献
0 次
宅之契约
0 份
在线时间
2 小时
注册时间
2014-3-19
发表于 2014-3-20 01:42:06 | 显示全部楼层
LZ的程序我调试着看过了,没有明显的循环错误之类的
今天有点晚,改天再看看
回复 赞! 靠!

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
 楼主| 发表于 2014-3-20 16:59:49 | 显示全部楼层
sx4452 发表于 2014-3-19 17:42
LZ的程序我调试着看过了,没有明显的循环错误之类的
今天有点晚,改天再看看 ...

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

使用道具 举报

0

主题

5

回帖

42

积分

用户组: 初·技术宅

UID
132
精华
0
威望
1 点
宅币
35 个
贡献
0 次
宅之契约
0 份
在线时间
2 小时
注册时间
2014-3-19
发表于 2014-3-21 14:58:32 | 显示全部楼层
0xAA55 发表于 2014-3-20 16:59
我的程序我是亲自测试过没问题才放到论坛的,所以估计是你的程序出了问题。。
此外,同时包含stdio.h和io ...

好吧 受教了 应该是我读写的问题
回复 赞! 靠!

使用道具 举报

0

主题

1

回帖

16

积分

用户组: 初·技术宅

UID
156
精华
0
威望
1 点
宅币
13 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2014-3-26
发表于 2014-3-26 11:25:28 | 显示全部楼层
kankan                           
回复 赞! 靠!

使用道具 举报

0

主题

19

回帖

51

积分

用户组: 小·技术宅

UID
158
精华
0
威望
1 点
宅币
30 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2014-3-26
发表于 2014-3-26 16:26:28 | 显示全部楼层
学习了。~
回复

使用道具 举报

0

主题

2

回帖

26

积分

用户组: 初·技术宅

UID
169
精华
0
威望
1 点
宅币
22 个
贡献
0 次
宅之契约
0 份
在线时间
1 小时
注册时间
2014-3-30
发表于 2014-3-30 20:03:17 | 显示全部楼层
哈哈,看一下
回复 赞! 靠!

使用道具 举报

KxIX 该用户已被删除
发表于 2014-8-6 13:33:20 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 赞! 靠!

使用道具 举报

忧郁 该用户已被删除
发表于 2014-9-16 00:57:25 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

0

主题

1

回帖

22

积分

用户组: 初·技术宅

UID
559
精华
0
威望
2 点
宅币
17 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2014-11-17
发表于 2014-11-17 14:36:11 | 显示全部楼层
想看看八叉树算法
回复 赞! 靠!

使用道具 举报

0

主题

1

回帖

9

积分

用户组: 初·技术宅

UID
703
精华
0
威望
0 点
宅币
8 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2015-3-2
发表于 2015-3-2 10:00:44 | 显示全部楼层
谢谢分享
回复

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
 楼主| 发表于 2015-3-2 12:51:22 | 显示全部楼层
啊!才知道自己竟然没有使用Lena图!
回复 赞! 靠!

使用道具 举报

0

主题

9

回帖

101

积分

用户组: 小·技术宅

UID
681
精华
0
威望
0 点
宅币
92 个
贡献
0 次
宅之契约
0 份
在线时间
12 小时
注册时间
2015-2-13
发表于 2015-3-4 19:43:05 | 显示全部楼层
谢谢分享 学习了
回复 赞! 靠!

使用道具 举报

17

主题

28

回帖

590

积分

用户组: 大·技术宅

UID
140
精华
5
威望
30 点
宅币
440 个
贡献
26 次
宅之契约
0 份
在线时间
54 小时
注册时间
2014-3-22
发表于 2015-6-30 12:13:19 | 显示全部楼层
来看看...
回复

使用道具 举报

zoand 该用户已被删除
发表于 2015-9-15 03:15:17 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 赞! 靠!

使用道具 举报

0

主题

8

回帖

51

积分

用户组: 小·技术宅

UID
1125
精华
0
威望
1 点
宅币
41 个
贡献
0 次
宅之契约
0 份
在线时间
4 小时
注册时间
2015-9-13
发表于 2015-9-19 08:39:03 | 显示全部楼层
历害{:soso_e132:}
回复 赞! 靠!

使用道具 举报

0

主题

76

回帖

6758

积分

用户组: 真·技术宅

UID
604
精华
0
威望
2 点
宅币
825 个
贡献
5853 次
宅之契约
0 份
在线时间
101 小时
注册时间
2014-12-20
发表于 2015-10-20 21:10:00 | 显示全部楼层
对应的磁盘空间会减少吗?
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 15:25 , Processed in 0.049638 second(s), 38 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表