BMP位图缩位压缩

BMP位图压缩

说明：本文主要分为两个部分：压缩和解压

压缩部分：

注：本文所讲的压缩方法仅仅对BMP灰度图有用。

1.对于BMP格式图片的认识:

　　一张BMP图片一共有四个部分：文件头、位图信息头、调色板和像素数据组成。

　　文件头：

　　typedef struct tagBITMAPFILEHEADER {
　　　　WORD bfType;
　　　　DWORD bfSize;
　　　　WORD bfReserved1;
　　　　WORD bfReserved2;
　　　　DWORD bfOffBits;
　　} BITMAPFILEHEADER;
　　bfType（2byte）
　　　　文件类型，具体值为0x4D42 = “BM”
　　bfSize（4byte）
　　　　文件大小，此图片大小为0x00000206 = 518（十进制）byte。
　　bfReserved1和bfReserved2（每个2byte）
　　　　保留项，必须设置为0。
　　bfOffBits（4byte）
　　　　从文件开头到具体图像数据的字节偏移量，0x00000076 = 118（十进制），具体文件头（14byte）+位图信息头（40byte）+调色板（64byte） = 118byte。

　　位图信息头：

　　typedef struct tagBITMAPINFOHEADER{
　　　　DWORD biSize;
　　　　LONG biWidth;
　　　　LONG biHeight;
　　　　WORD biPlanes;
　　　　WORD biBitCount;
　　　　DWORD biCompression;
　　　　DWORD biSizeImage;
　　　　LONG biXPelsPerMeter;
　　　　LONG biYPelsPerMeter;
　　　　DWORD biClrUsed;
　　　　DWORD biClrImportant;
　　} BITMAPINFOHEADER；

    biSize（4byte）
    　　位图信息头的大小，所有图片均为0x00000028 = 40（十进制）byte。
    biWidth（4byte）
    　　位图宽度，单位为像素，0x00000019 = 25（十进制）。
    biHeight;（4byte）
   　　 位图高度，单位为像素，0x00000019 = 25（十进制）。
    biPlanes（2byte）
   　　 位图的平面数，设置为1，0x0001。
    biBitCount（2byte）
   　　 颜色深度（位数），又称位深度、位分辨率，单位为bpp（bit/像素点），意为存储每个像素点需要的bit数，值有1,4,8,16,24,32等。此图片为0x0004 = 4位。
    biCompression（4byte）
    　　是否压缩，0（不压缩），1（RLE 8，8位RLE压缩），2（RLE 4，4位RLE压缩，3（Bitfields，位域存放）。0x00000000为不压缩。
    biSizeImage（4byte）
   　　 图像数据部分大小，单位字节，数值上等于位图宽度大小（单位字节，必须是离宽度字节数最近而且是4的倍数值）×位图高度，上图位图宽度是16byte*25的高度=400byte，0x00000190 = 400，图片分析　　　与计算一致。
    biXPelsPerMeter（4byte）
    　　用像素/米表示的水平分辨率，0x00001EC2 = 7874（十进制）。
    biYPelsPerMeter（4byte）
    　　用像素/米表示的水平分辨率，0x00001EC2 = 7874（十进制）。
    biClrUsed（4byte）
    　　调色板中的颜色索引数，0为图片有调色板。
    biClrImportant（4byte）
    　　重要影响的颜色索引数，0表示都重要。
　　调色板：

　　结构为蓝，绿，红的顺序排列，最后一位为保留项。
　　typedef struct tagRGBQUAD {
　　　　BYTE rgbBlue;
　　　　BYTE rgbGreen;
　　　　BYTE rgbRed;
　　　　BYTE rgbReserved;
　　} RGBQUAD;

　　调色板中的数据每4字节一组，分别表示蓝、绿、红和保留值（十六进制），该图片的颜色数为2^4=16种，占用的字节数为16 * 4=64byte。而在8位的BMP图片中，图片的　　颜色就有2^8=256种，占用的字节数为256*4=1024byte。

　　像素数据：

　　在八位的BMP图像中，每个像素点用8位表示，那么每个像素的取值就位于0~255之间，由白到黑。

2、缩位压缩方法的原理

　　由上面的讲解我们就可以得知，对于一个8位的BMP图片，存储其一个像素数据就需要八位的空间，即一个字节。如果一个像素数据的值位255，转化为二进制就是11111111，那么不得不用八位来存储，但是如果一个像素数据的值为1呢，转化为二进制就是1，但是计算机存储的时候却是00000001。那么问题就来了，我只需要一位，你却给我八位，这不是赤裸裸的浪费吗？计算机存储设备表示抗议（此处为玩笑话）。所以对于图片的压缩就显得很有必要了。压缩的原理也就是如此，将不需要八位存储空间的像素数据进行缩位。他需要几位就给他几位。做到减少存储空间的目的。但是这时候问题就出来了，好家伙，我们这么一搞，图片的大小立马下来了，搞压缩的人爽坏了，但是当你把压缩后的像素数据给别人的时候，别人怎么解压呢？比如说由三个像素数据：2、42、170，转化为二进制按照我们的压缩方法压缩之后就是：10，101010，10101010。但是计算机不存储逗号呀，结果就是1010101010101010。基本上没办法把他正确的解读。有人说把逗号也存储了不就好了？但是存储一个逗号需要八位，这不是白搭了吗？这里可能会出现的问题先不说，就压缩后的空间也许比不压缩还要大这一点来说，这个压缩还有什么意义呢？所以这个时候就出现了一个好的方法兼顾了存储位数和压缩后解读的可能性：动态规划。至于动态规划如何搞这个图片压缩？请自行百度学习这个算法。（网上教程一抓一大把）

附上我自己的代码：

　 //vector<int> Pixel = {0,10,12,15,255,1,2,124,127,3,255,55,66};//像素数据
    //int len = Pixel.size(); //像素个数
    //vector<int> length(len); //记录当前像素点所在组的元素个数
    //vector<int> bit(len);  //记录当前像素点所在组的元素的位数
    //vector<int> s(len);  //记录最优解(最少位数)

int length(int i)   //得到一个数的二进制位数
{
    int k = 1;
    i = i / 2;
    while (i > 0)
    {
        ++k;
        i /= 2;
    }
    return k;
}

int PictureCompressBest(vector<int>& Pixel, vector<int>& s, vector<int>& l, vector<int>&bit, int len)
{
    //初始化
    int  Lmax = 255;  //每组中的像素个数不超过255
    int header = 11;   //每个组有3位记录该组元素的位数，8位用例记录组内像素个数
    s[0] = 0;
    int bmax = 0;
    for (int i = 1; i < len; ++i)
    {
        bit[i] = length(Pixel[i]);  //得到当前元素位数
        bmax = bit[i];   //记录当前组内的元素的最大位数
        s[i] = s[i - 1] + bmax;  //状态转移方程
        l[i] = 1;

        for (int j = 2; j <= i && j < Lmax; ++j)
        {
            if (bmax < bit[i - j + 1])
            {
                bmax = bit[i - j + 1];  //寻找最大位数，因为当前组内每个元素的位数有当前组内位数最大的元素决定
            }
            if (s[i] > s[i - j] + j * bmax)
            {
                s[i] = s[i - j] + j * bmax;
                l[i] = j;
            }
        }
        s[i] += header; //加上头
    }
    return s[len - 1];
}

　　最后这个函数返回的是存储当前这些像素数据所需要的最少位数。

3、压缩的操作步骤　

　　第一步：先读取一个图片的文件头：然后读取其中的bfType，看看他是不是等于0x4D42，如果不等于就说明他不是.bmp格式的图片。那就不要压这张图片了，压了也解不开。

　　第二步：读取位图信息头

　　第三步：读取调色板

　　stop：有人会问我这么知道以上三个部分各有多少位呢？在c++中sizeof（BITMAPFILEHEADER）就是文件头的位数，sizeof（BITMAPINFOHEADER）就是位图信息头的位数。然后请留意文件头中的一个数据bfOffBits，这个数据代表的是像素数据开始的位置。所以bfOffBits -  sizeof（BITMAPFILEHEADER）- sizeof（BITMAPINFOHEADER）就是调色板数据开始的位数。以上的读取都是以位（bit）为单位的，具体的读取操作不同的语言不同，请自行百度。

　　第三步：新建一个文件，将以上的三个部分原封不动的写入新的文件中，这个文件就是以后的图片压缩包，等后面再将压缩处理后的像素数据写入之后就算是压缩完成了。

　　第四步：（搞了这么久，终于开始读取像素数据了）将像素数据全部读入一个二维矩阵。注意Windows规定一个扫描行所占的字节数必须是4的倍数(即以long为单位),不足的以0填充。 
一个扫描行所占的字节数计算方法:DataSizePerLine=(biWidth* biBitCount+31)/8；

　　第五步：再将像素数据按蛇形读入一个一位数组，至于为什么？因为上下相邻两个像素数据的值相差不大，有利于减少压缩后文件的大小。

　　第六步：利用动态规划对于这些像素数据进行最优（位数最少）分段。

　　第六步：整合：将上面代码中的lenght数组，bit数组整合。具体的格式就单个段：段标题（占八位，记录当前段有几个像素数据，最多255个所以是八位）+ 位数（占三位，存储当前段内元素的存储位数）+ 本段内压缩后的像素数据。

　　第七步：将以上出后的像素数据写入文件之后，压缩就算完成了。写文件操作主要利用的是位操作 “<<” ">>",实现几个位的拼接，然后满八个位就写入文件。

解压部分

　　说明：解压其实就是压缩的逆过程。

　　第一步：其实和压缩一样，前面的三步没有任何的变化，读取文件头，信息头，调色板然后将其写入新的文件作为解压后的文件。

　　第二步：读取压缩数据

　　第三步：有了以上的铺垫，你就可以很容易的知道该如何去解读压缩数据，最开始的八位是本段内的像素个数，后面的三位就是本段内的像素数据存储的位数，在后面就是本段的像素数据了。然后将每个像素数据恢复至八位，存入一个一位数组当中。直到恢复完所有的像素数据。

　　第四步：按照文件信息头中的位图的长和宽将像素数据按蛇形恢复至二维矩阵中。

　　第五步：将这些数据写入刚刚写入相关头的文件中，解压也就完成了。

总结

　　其实在写这个程序的过程中最难的部分不是动态规划部分，而是文件的读写，和像素数据的整合，对于压缩数据的解读，稍有不慎，解压过后的文件就会打不开。