Huffman编码及解码

1、Huffman编码图像解码 */ /读入编码图像 bool readHuffman(char *Name) int i,j; char NameStr100; /读取Huffman编码信息和编码树 strcpy(NameStr,Name); strcat(NameStr,".bpt"); FILE *fin = fopen(NameStr,"r"); if(fin = 0) printf("未找到指定文件！n"); return 0; fscanf(fin,"%d %d %d",&NodeStart,&am

2、p;NodeNum,&InfLen); /printf("%d %d %dn",NodeStart,NodeNum,InfLen); for(i = 0;i < NodeNum;i +) fscanf(fin,"%d %d %d",&nodei.color,&nodei.lson,&nodei.rson); /printf("%d %d %dn",nodei.color,nodei.lson,nodei.rson); /二进制读方式翻开指定的图像文件 strcpy(NameStr,Name); s

3、trcat(NameStr,".bhd"); FILE *fp=fopen(NameStr,"rb"); if(fp=0) printf("未找到指定文件！n"); return 0; /跳过位图文件头结构BITMAPFILEHEADER fseek(fp, sizeof(BITMAPFILEHEADER),0); /定义位图信息头结构变量，读取位图信息头进内存，存放在变量head中 BITMAPINFOHEADER head; fread(&head, sizeof(BITMAPINFOHEADER), 1,fp); /获取

4、图像宽、高、每像素所占位数等信息 bmpWith; bmpHeght; biBitCountCount; /定义变量，计算图像每行像素所占的字节数必须是4的倍数 int lineByte=(bmpWidth * biBitCount/8+3)/4*4; /灰度图像有颜色表，且颜色表表项为256 if(biBitCount=8) /申请颜色表所需要的空间，读颜色表进内存 pColorTable=new RGBQUAD256; fread(pColorTable,sizeof(RGBQUAD),256,fp); /申请位图数据所需要的空间，读位图数据进内存 pBmpBuf=new unsigned

5、 charlineByte * bmpHeight; fread(pBmpBuf,1,InfLen / 8,fp); /关闭文件 fclose(fp); return 1; void HuffmanDecode() /获取编码信息 int i,j,tmp; int lineByte=(bmpWidth * biBitCount/8+3)/4*4; for(i = 0;i < InfLen / 8;i +) j = i * 8 + 7; tmp = *(pBmpBuf + i); while(tmp > 0) ImgInfj = tmp % 2; tmp /= 2; j -; /*f

6、or(i = 0;i < InfLen;i +) printf("%d",ImgInfi); printf("n");*/ /解码 int p = NodeStart; /遍历指针位置 j = 0; i = 0; do if(nodep.color >= 0) *(pBmpBuf + j) = nodep.color; /printf("%d ",*(pBmpBuf + j); j +; p = NodeStart; if(ImgInfi = 1) p = nodep.lson; else if(ImgInfi = 0)

7、p = nodep.rson; i +; while(i <= InfLen); /printf("nj: %dn",j); /* Huffman编码 */ /Huffman编码初始化 void HuffmanCodeInit() int i; for(i = 0;i <256;i +)/灰度值记录清零 Numi = 0; /初始化哈夫曼树 for(i = 0;i < 600;i +) nodei.color = -1; nodei.lson = nodei.rson = -1; nodei.num = -1; nodei.mark = 0; NodeNu

8、m = 0; /深搜遍历Huffman树获取编码值 char CodeTmp300; void dfs(int pos,int len) /遍历左儿子 if(nodepos.lson != -1) CodeTmplen = '1' dfs(nodepos.lson,len + 1); else if(nodepos.color != -1) CodeLennodepos.color = len; CodeTmplen = '0' strcpy(CodeStrnodepos.color,CodeTmp); /遍历右儿子 if(nodepos.lson != -1)

9、 CodeTmplen = '0' dfs(nodepos.rson,len + 1); else if(nodepos.color != -1) CodeLennodepos.color = len; CodeTmplen = '0' strcpy(CodeStrnodepos.color,CodeTmp); /寻找值最小的节点 int MinNode() int i,j = -1; for(i = 0;i < NodeNum;i +) if(!nodei.mark) if(j = -1 | nodei.num < nodej.num) j = i

10、; if(j != -1) NodeStart = j; nodej.mark = 1; return j; /编码主函数 void HuffmanCode() int i,j,k,a,b; for(i = 0;i < 256;i +) /创立初始节点 Feqi = (float)Numi / (float)(bmpHeight * bmpWidth);/计算灰度值频率 if(Numi > 0) nodeNodeNum.color = i; nodeNodeNum.num = Numi; nodeNodeNum.lson = nodeNodeNum.rson = -1; /叶子节点

11、无左右儿子 NodeNum +; while(1) /找到两个值最小的节点，合并成为新的节点 a = MinNode(); if(a = -1) break; b = MinNode(); if(b = -1) break; /构建新节点 nodeNodeNum.color = -1; nodeNodeNum.num = nodea.num + nodeb.num; nodeNodeNum.lson = a; nodeNodeNum.rson = b; NodeNum +; /nodea.mark = nodeb.mark = 1; /根据建好的Huffman树编码(深搜实现) dfs(Nod

12、eStart,0); /屏幕输出编码 int sum = 0; printf("Huffman编码信息如下：n"); for(i = 0;i < 256;i +) if(Numi > 0) sum += CodeLeni * Numi; printf("灰度值：%3d 频率: %f 码长: %2d 编码: %sn",i,Feqi,CodeLeni,CodeStri); / printf("原始总码长：%dn",bmpWidth * bmpHeight * 8); / printf("Huffman编码总码长：%d

13、n",sum); / printf("压缩比：%.3f : 1n",(float)(bmpWidth * bmpHeight * 8) / (float)sum); /记录图像信息 InfLen = 0; int lineByte=(bmpWidth * biBitCount/8+3)/4*4; for(i = 0;i < bmpHeight;i +) for(j = 0;j < bmpWidth;j +) lpBuf = (unsigned char *)pBmpBuf + lineByte * i + j; for(k = 0;k < Cod

14、eLen*(lpBuf);k +) ImgInfInfLen + = (int)(CodeStr*(lpBuf)k - '0'); /再编码数据 j = 0; for(i = 0;i < InfLen;) *(pBmpBuf + j) = Change2to10(i); i += 8; j +; /* 主函数 */ int main(int argc, char* argv) int ord;/命令 char c; int i,j; clock_t start,finish; int total_time; / CString str; while(1) printf(&

15、quot;本程序提供度BMP图像Huffman编码an编码BMP文件解码nt3.退出nn请选择需要执行的命令:"); scanf("%d%c",&ord,&c); if(ord = 1) printf("n-256色灰度BMP图像Huffman编码-n"); printf("n请输入要编码图像名称："); scanf("%s",str); /读入指定BMP文件进内存 char readPath100; strcpy(readPath,str); strcat(readPath,"

16、.bmp"); if(readBmp(readPath) /输出图像的信息 /printf("n图像信息：nwidth=%d,height=%d,biBitCount=%dn",bmpWidth,bmpHeight,biBitCount); int lineByte=(bmpWidth * biBitCount/8+3)/4*4; if(biBitCount=8) /编码初始化 HuffmanCodeInit(); /计算每个灰度值出现的次数 for(i = 0;i < bmpHeight;i +) for(j = 0;j < bmpWidth;j +

17、) lpBuf = (unsigned char *)pBmpBuf + lineByte * i + j; Num*(lpBuf) += 1; /调用编码 start=clock(); HuffmanCode(); finish=clock(); total_time=(finish-start); printf("识别一张耗时：%d毫秒",total_time); /将图像数据存盘 char writePath100; /保存编码后的bmp strcpy(writePath,str); strcat(writePath,"_Huffman.bhd")

18、; saveBmp(writePath, pBmpBuf, bmpWidth, bmpHeight, biBitCount, pColorTable); /保存Huffman编码信息和编码树 strcpy(writePath,str); strcat(writePath,"_Huffman.bpt"); saveInfo(writePath,lineByte); printf("n编码完成!编码信息保存在 %s_Huffman 文件中nn",str); else printf("本程序只支持256色BMP编码！n"); /去除缓冲区，

19、pBmpBuf和pColorTable是全局变量，在文件读入时申请的空间 delete pBmpBuf; if(biBitCount=8) delete pColorTable; printf("n-nnn"); else if(ord = 2) printf("n-Huffman编码BMP文件解码-n"); printf("n请输入要解码文件名称："); scanf("%s",str); /编码解码初始化 HuffmanCodeInit(); if(readHuffman(str) /读取文件 HuffmanDe

20、code(); /Huffman解码 /将图像数据存盘 char writePath100; /保存解码后的bmp strcpy(writePath,str); strcat(writePath,"_Decode.bmp"); InfLen = bmpWidth * bmpHeight * 8; saveBmp(writePath, pBmpBuf, bmpWidth, bmpHeight, biBitCount, pColorTable); system(writePath); printf("n解码完成!保存为 %s_Decode.bmpnn",st

21、r); printf("n-nnn"); else if(ord = 3) break; return 0; /* ANSI C requires main to return int. */ /* 编码：#include <stdlib.h> #include <stdio.h> #include <string.h> #include "Windows.h" #include "math.h" #include <time.h> /几个全局变量，存放读入图像的位图数据、宽、高、颜色表

22、及每像素所占位数(比特) /此处定义全局变量主要为了后面的图像数据访问及图像存储作准备 unsigned char *pBmpBuf;/读入图像数据的指针 int bmpWidth;/图像的宽 int bmpHeight;/图像的高 int imgSpace;/图像所需空间 RGBQUAD *pColorTable;/颜色表指针 int biBitCount;/图像类型 char str100;/文件名称 int Num300;/各灰度值出现的次数 float Feq300;/各灰度值出现的频率 unsigned char *lpBuf;/指向图像像素的指针 unsigned char *m_

23、pDib;/存放翻开文件的DIB int NodeNum; /Huffman树总节点个数 int NodeStart; /Huffman树起始节点 struct Node /Huffman树节点 int color; /记录叶子节点的灰度值非叶子节点为 -1 int lson,rson; /节点的左右儿子假设没有那么为 -1 int num; /节点的数值编码依据 int mark; /记录节点是否被用过(用过为1，没用过为0) node600; char CodeStr300300; /记录编码值 int CodeLen300; /编码长度 bool ImgInf8000000; /图像信息

24、 int InfLen; /图像信息长度 /* * 函数名称： * readBmp() * *函数参数： * char *bmpName -文件名字及路径 * *返回值： * 0为失败,1为成功 * *说明：给定一个图像文件名及其路径，读图像的位图数据、宽、高、颜色表及每像素 * 位数等数据进内存,存放在相应的全局变量中 */ bool readBmp(char *bmpName) /二进制读方式翻开指定的图像文件 /FILE *fp=fopen("E:Program FilesprogramHuffman1.bmp","rb");FILE *fp=fo

25、pen(bmpName,"rb"); if(fp=0) printf("未找到指定文件！n"); return 0; /跳过位图文件头结构BITMAPFILEHEADER fseek(fp, sizeof(BITMAPFILEHEADER),0); /定义位图信息头结构变量，读取位图信息头进内存，存放在变量head中 BITMAPINFOHEADER head; fread(&head, sizeof(BITMAPINFOHEADER), 1,fp); /获取图像宽、高、每像素所占位数等信息 bmpWith; bmpHeght; biBitCou

26、ntCount; /定义变量，计算图像每行像素所占的字节数必须是4的倍数 int lineByte=(bmpWidth * biBitCount/8+3)/4*4; /灰度图像有颜色表，且颜色表表项为256 if(biBitCount=8) /申请颜色表所需要的空间，读颜色表进内存 pColorTable=new RGBQUAD256; fread(pColorTable,sizeof(RGBQUAD),256,fp); /申请位图数据所需要的空间，读位图数据进内存 pBmpBuf=new unsigned charlineByte * bmpHeight; fread(pBmpBuf,1,l

27、ineByte * bmpHeight,fp); /关闭文件 fclose(fp); return 1; /* 保存信息 */ /二进制转十进制 int Change2to10(int pos) int i,j,two = 1; j = 0; for(i = pos + 7;i >= pos;i -) j += two * ImgInfi; two *= 2; return j; /保存Huffman编码树 int saveInfo(char *writePath,int lineByte) int i,j,k; FILE *fout; fout = fopen(writePath,&q

28、uot;w"); fprintf(fout,"%d %d %dn",NodeStart,NodeNum,InfLen);/输出起始节点、节点总数、图像所占空间 for(i = 0;i < NodeNum;i +) /输出Huffman树 fprintf(fout,"%d %d %dn",nodei.color,nodei.lson,nodei.rson); /*for(i = 0;i < InfLen;i +) fprintf(fout,"%d",ImgInfi); fprintf(fout,"n");*/ fclose(fout); return 0; /保存文件 bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height, int biBitCount, RGBQUAD *pColorTable) /如果位图数据指针为0,那么没有数据传入,函数返回 if(!imgBuf) return 0; /颜色表大小,以字节为单位,灰度图像颜色表为1024字节,彩色图像颜色表大小为0 int colorTables