简单的BMCP位图图片压缩算法

此算法并不高深,各位专业人士可以飘过了Orz.并且如果各位知道一些图片格式与压缩算法的话,从中应该可以看到一些相似的"影子".

PS:本人非专业人士,以下有说错的敬请各位谅解:)

什么是位图?
位图也称像素图像或点阵图像,是由多个点组成的,这些点被称为像素。位图可以模仿照片的真实效果,具有表现力强、细腻、层次多和细节多等优点。 

图片的压缩格式：
在Windows系统中,我们常见的bmp图片文件(bitmap file)就是位图图片。位图图片的文件大小一般都是最大的（这个可以从上上面的定义可知），不便于存储和传输，所以后来才出现了一些"压缩"格式图片，比如:gif,tiff,jpeg,png等等图片文件。

图片"压缩"又分为" 有损压缩"和" 无损压缩"：

有损压缩 ： 顾名思意就是还原出来的图片有失真现象，或者简单的说就是此还原图片不再是原来的图片。（如jpeg图片）
无损压缩 ： 也即是不会有失真现象，还原出来的图片和原有图片是一模一样的。（如tiff图片）

根据不同的压缩格式与算法，最终的压缩图片文件大小也不尽相同，但一般都比位图文件小！！（如果不小还有意义吗？ ）

PS: jpeg也可以是无损压缩


好了，上面简单的说了几个概念，现在回归正传，说一下下面的图片压缩算法，为了方便，我在这里简称为“ BMCP”压缩格式。

BMCP 是采用 无损压缩方法对图片进行压缩的，其处理流程大概如下：

对一幅位图的所有象素点进行扫描，取出所有象素点的颜色构造颜色表，并且记录这些象素点的颜色在颜色表中的索引位置，然后再对这些索引位置记录进行压缩后再存储数据，也就是存储的时候象素点位置只存储索引而不存储颜色！！（看到这里大家想到哪种格式图片没有？）

我们都知道一张图按行/列扫描时某个点的颜色在它后面连续同时出现的机率是很大的，所以我们的压缩就在这里了。简单的压缩原理用伪代码表示如下：
color = 图片的第一点象素点颜色；
while(图片的象素点没有扫描完)
    newColor = 获取当前象素点的颜色;
    if(newColor == color)
    {
        color的出现次数+1;
    }else{
        存储color;
        color = newColor;
    }
}

这样压缩后，我们就可以将一些连续出现的颜色点压缩为一个颜色点了。例如有下面的字符数据：
abceefaccccch
经我们压缩后就可以变为如下数据了：
a1b1c1e2f1a1c5h1
(注：字符后面的数字表示其连续出现的次数）
嗯？也许你会说这个看起来怎么字符反而多了？别急，在图片世界里，这样压缩还是有不错效果的，除非那个图片是很变态的，不会有两个以上相同颜色点出现！！！

BMCP的颜色索引值的存储：
我们大家都知道在bmcp里是存储颜色索引值的，而大家也知道在C#里的int/uint是占用4个字节空间的，所以我们存储象素颜色索引时肯定尽量避免存储为int/uint值！
在bmcp里颜色索引值的存储大小是根据颜色表的数量来决定的。当颜色表的颜色数量小于255个时索引占用的空间就只占用1个字节；而颜色表的数量小于ushort值范围时索引占用的空间就是2个字节；而如果颜色表数量小于ushort.MaxValue*255时就索引就占用3个字节（前2个字节存储的是“值/255”的整数部分，而后1个字节则存储的是“值%255”）；否则就只能使用4个字节存储索引。
在上面的压缩计解中，我们还要存储一个“颜色连接出现的次数”值，这个值的大小在bmcp里是占用1个字节的，也就是说计算某颜色重复出现的次数时只最多只能记录到255次，如果还继续出现同一个颜色，则重新记录颜色！为什么要这样做呢？这是为了减少占用空间所做的，在很多图片中，不连续出现相同颜色的位置所占的比率也是很大的，而连续出现同一种颜色超出255次的地方则是少之又少。

BMCP的文件格式：
讲解完上面后，我们就可以整理出BMCP的文件存储格式了，如下表：

地址	大小	说明
0x000000	4个字节	bmcp标识字符
0x000004	1个字节	扩展位，暂时不使用，本来打算是用来存储扫描方式的，也就是区别行扫描还是列扫描（在图片高大于宽时列扫描有可能压缩率更高）
0x000005	4字节	图片的宽度
0x000009	4字节	图片的高度
0x00000d	4字节	颜色表的颜色总数
0x0000011	n*4字节	颜色表数据，n代表颜色表的总数，每个颜色占用4个字节
0x000????	n*m字节	图片各象素点的颜色索引。 n代表象素点的总数（压缩后），m代表颜色索引值+1字节的连续出现的次数的总占用的空间（如颜色表的总数小于255则占用2字节）

好了，到此讲解完成，大概也知道BMCP是如何做到压缩位图文件的吧？
1。只存储每个象素点颜色索引值
2。将连续出现相同颜色的多个象素点压缩为一个“象素点”

经测试用BMCP压缩的位图文件大小基本和TIFF压缩的大小相差不多，但在颜色表数量较少时压缩出来的图片文件大小则小于TIFF格式图片。

此压缩算法免费，你可以自由使用而不用通知作者本人。  

源码下载： http://files.cnblogs.com/kingthy/Bmcp.rar

使用示例：