技术宅的结界

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

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 10249|回复: 47
收起左侧

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

[复制链接]

1044

主题

2345

帖子

5万

积分

用户组: 管理员

一只技术宅

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

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

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

x
在一些特殊情况,我们需要将位图从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

主题

29

帖子

285

积分

用户组: 版主

UID
32
精华
0
威望
6 点
宅币
244 个
贡献
0 次
宅之契约
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然后写了个测试程序。
测试程序如下:
[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;
}









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


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

0

主题

5

帖子

42

积分

用户组: 初·技术宅

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

1044

主题

2345

帖子

5万

积分

用户组: 管理员

一只技术宅

UID
1
精华
218
威望
294 点
宅币
18328 个
贡献
37575 次
宅之契约
0 份
在线时间
1749 小时
注册时间
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 | 显示全部楼层
谢谢分享
回复

使用道具 举报

1044

主题

2345

帖子

5万

积分

用户组: 管理员

一只技术宅

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

0

主题

10

帖子

102

积分

用户组: 小·技术宅

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

17

主题

42

帖子

529

积分

用户组: 大·技术宅

UID
140
精华
5
威望
30 点
宅币
376 个
贡献
26 次
宅之契约
0 份
在线时间
44 小时
注册时间
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 | 显示全部楼层
历害

0

主题

76

帖子

6735

积分

用户组: 真·技术宅

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

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2019-11-17 19:59 , Processed in 0.695810 second(s), 44 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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