ImageCompressionAndRestroation

利用霍夫曼树实现8位256色灰度图像的压缩与复原

一、实验语言与环境

Windows
C++
Visual Studio Code或code::blocks
MinGW-gcc.exe

二、代码解析

图像压缩

详见ImageCompress.cpp

获取256种颜色的权值

int wid = bitMapInfoHeader.biWidth, hei = bitMapInfoHeader.biHeight;
int md = wid%4;
int base = (md==0)? wid:4-md+wid;
for (int j=0;j<hei;j++){
    for (int i=0;i<wid;i++){
        v[pData[j*base+i]] +=1; //颜色 i 的权值 v[i]
    }
}

建立霍夫曼树并获取每种颜色的霍夫曼编码（具体代码实现详见：ImageCompress.cpp）
```
HuffmanTree(256);
getCode(true, tree[2 * 256 - 2].l,-1);
getCode(false, tree[2 * 256 - 2].r,-1);
```
将图像的文件头、信息头、调色板写入后，将每个颜色的权值写入，权值用unsigned int型写入二进制文件，存入权值目的是方便在解压时重建霍夫曼树。这里不用写入颜色序号，因为这本就是颜色i对应v[i]，按照顺序排列好了，无需再写入颜色i，只需写入v[i]即可。
```
//写入每种颜色的权重
    for (int i=0;i<256;i++){
        unsigned int weight_to_write = v[i];
        ot.write((char*)&weight_to_write,sizeof(unsigned int));
    }
```

写入霍夫曼编码后的位图数据

这里我将所有位图数据的霍夫曼编码长度加了起来，计算出总长度hufSize,并将其以unsigned int型写入文件，这样方便我在解压时读入位图数据

unsigned int hufSize = 0;
    for (int j=0;j<hei;j++){
        for (int i=0;i<wid;i++){
            int color = pData[j*base+i];
            // cd[color]：该颜色对应的霍夫曼编码，string类型
            int leng = cd[color].length(); 
            hufSize+=leng;
        }
    }
//写入huffman编码
ot.write((char*)&hufSize,sizeof(unsigned int));

利用一个32位，即unsigned int型的缓冲区buf来存储即将要写入文件的霍夫曼编码（之前是用string保存，需要转换成unsigned int），利用变量buflen记录长度，每当buflen达到32时，就将buf写入文件，将buf和buflen归零，循环往复，直到将所有的位图数据霍夫曼编码写入，注意，最后一个位图数据的霍夫曼编码可能无法用完buf的32bits的空间，所以需要将buf右移相应的位数，保证写入的位图数据是相连的。更多细节请参考代码。

	for (int j=0;j<hei;j++){
        for (int i=0;i<wid;i++){
            int color = pData[j*base+i];
            int leng = cd[color].length();
            for (int k=0;k<leng;k++){
                if (cd[color][k]=='0'){
                    buf *= 2;
                }else buf = buf*2+1;
                buflen++;
                if (buflen==32){
                    ot.write((char*)&buf,sizeof(unsigned int));
                    // cnt++;
                    buf = 0;
                    buflen = 0;
                }
            }
        }
    }
//最后一次写入，不足则右移
    if (buflen>0){
        buf = (buf<<(32-buflen));
        ot.write((char*)&buf,sizeof(unsigned int));
    }

压缩算法的复杂度分析

主要影响复杂度的是图像的大小，即width和height，以下用w和h表示

建立霍夫曼树的时间复杂度：

$$ 获取权值：w*h $$

$$ 建树：(n+2n-2)*(n-1)/2,n = 256 $$

$$ (n+2n-2)*(n-1)/2=97655 $$

计算hufSize：

$$ w*h $$

写入位图数据：

$$ {\sum_{i=0}^{w*h-1}}length_i,length为每个位图数据的霍夫曼编码长度 $$

总结，这里为了方便，用8表示length，所以总的复杂度为：

$$ O(max(97655,w*h)) $$

图像复原

详见ImageExtract.cpp

读入无关紧要的东西，以及权值，重建霍夫曼树

for (int i=0;i<256;i++){
        unsigned int weightRead;
        bmpfile.read((char*)& weightRead,sizeof(unsigned int));
        v[i] = weightRead; 
    }
HuffmanTree(256);

读入hufSize，根据hufSize确定要读入多少个32位的buf

bmpfile.read((char*)&hufSize,sizeof(unsigned int));
    if (hufSize%32==0){
        T = hufSize/32;
    }else {
        T = hufSize/32 + 1;
    }

读入霍夫曼编码位图数据并将其复原，方法是根据霍夫曼编码dfs重建的霍夫曼树即可，需要注意一些细节，详情见代码。

while(T--){
        unsigned int buf = 0;
        bmpfile.read((char*)&buf,sizeof(unsigned int));
        string cdc = "",cd="";
        while(buf>0){
            if (buf%2==1) cdc = cdc + "1";
            else cdc = cdc + "0";
            buf/=2;
        }
    	//不足32位要补全
        if (cdc.length()!=32) {
            int chajia = 32 - cdc.length();
            for (int i=0;i<chajia;i++) cdc = cdc + "0";
        }
        // if (cdc.length()!=32) cout<<"fucdfsdfsk"<<endl;
        for (int i=31;i>=0;i--){
            cd = cd + cdc[i];
        }
        if (T==0){
            int leng = cd.length();
            for (int i=0;i<hufSize;i++){
                if (cd[i]=='1') nv = tree[nv].l;
                else nv = tree[nv].r;
                if (nv<256){
                    pData[cnt] = nv;
                    if (base != wid){
                        // cnt从0开始
                        if ((cnt+1)%base == wid){
                            cnt = cnt-wid+base+1;
                        }else cnt++;
                    }else cnt++;
                    nv = 256*2-2;
                }
            }
        }else {
            hufSize-=32;
            int leng = cd.length();
            for (int i=0;i<leng;i++){
                if (cd[i]=='1') nv = tree[nv].l;
                else nv = tree[nv].r;
                if (nv<256){
                    pData[cnt] = nv;
                    if (base != wid){
                        if ((cnt+1)%base == wid){
                            cnt = cnt-wid+base+1;
                        }else cnt++;
                    }else cnt++;
                    nv = 256*2-2;
                }
            }
        }
    }

复原算法的复杂度分析

重新建立霍夫曼树

$$ (n+2n-2)*(n-1)/2=97655 $$

复原位图数据

$$ T*32 = hufSize $$

$$ hufSize=8wh $$

总的时间复杂度

$$ O(max(97655,w*h)) $$

三、样例测试

输入lena1.bmp（8位）

压缩后结果为，lena1.bmp.hfm，二进制文件，用一个喜欢的名字吧。

复原后结果：

结果一模一样。

实际压缩率：

$$ 239/258 = 92.6% $$

四、实验总结

部分代码可以做算法复杂度优化
一开始我的想法是，将颜色和颜色对应的霍夫曼编码写入，再把位图数据对应的霍夫曼编码的长度和霍夫曼编码写入，很明显这是会让图像变大一倍；改正后的算法是写入权值和霍夫曼编码后的位图数据，不写入每个霍夫曼编码的长度，于是图像“扩张”就变回了图像压缩。

chuiyukong/ImageCompressionAndRestroation