图像无损压缩程序设计 霍夫曼编码

1、成绩评定表学生姓名班级学号专业电子信息工程课程设计题目图像的无损压缩程序设计一一霍夫曼编码评语组长签字：成绩日期2015年7月20日课程设计任务书学院信息科学与工程专业电子信息工程学生姓名班级学号1203030119课程设计题目图像的无损压缩程序设计一一霍夫曼编码实践教学要求与任务：本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。工作计划与进度安排：2015年7月8日一11日：熟悉编程环境，查阅相关资料。2015年7月11日

2、12日：图像的霍夫曼编码程序设计。2015年7月12日一13日：编码、调试、实验与分析。2015年7月13日15日：撰写课程设计报告。2015年7月15日一19日：准备答辩。指导教师：2015年7月2日专业负责人：2015年7月2日学院教学副院长：2015年7月2日摘要哈夫曼编码（HuffmanCoding）是一种编码方式，以哈夫曼树一即最优二叉树,带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法）,用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于,它是根据

3、每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的）。本课题通过MATLAB编写适当的函数,对一个随机信源进行哈夫曼编码,得出码字,平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点,并且提高综合运用所学理论知识独立分析和解决问题的能力。关键字：哈夫曼；信源编码；MATLAB目录TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 设计目的及相关知识1设计目的1图像的霍夫曼编码概念

4、11.3Matlab图像处理通用函数1 HYPERLINK l bookmark4 o Current Document 课程设计分析32.1图像的霍夫曼编码概述3图像的霍夫曼编码举例4 HYPERLINK l bookmark6 o Current Document 仿真5结果及分析8 HYPERLINK l bookmark8 o Current Document 附录11 HYPERLINK l bookmark10 o Current Document 结束语14 HYPERLINK l bookmark12 o Current Document 参考文献151设计目的及相关知识1.1

5、设计目的了解霍夫曼编码的原理。理解图像的霍夫曼编码原理，了解其应用，掌握图像的霍夫曼编码的方法。对图像编码程序设计进行较深入的认识，对知识牢固掌握。掌握图像霍夫曼编码的整个过程及其中的注意事项。了解图像无损压缩的目的及好处。1.2图像的霍夫曼编码概念所谓霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码1.3Matlab图像处

6、理通用函数colorbar显示彩色条语法：colorbarcolorbar(vert)colorbar(horiz)colorbar(h)h=colorbar(.)colorbar(.,peer,axes_handle)getimage从坐标轴取得图像数据语法：A=getimage(h)x,y,A=getimage(h).,A,flag=getimage(h).=getimageimshow显示图像语法：imshow(I,n)imshow(I,lowhigh)imshow(BW)imshow(X,map)imshow(RGB)imshow(.,display_option)imshow(x,y

7、,A,.)imshowfilenameh=imshow(.)montage在矩形框中同时显示多幅图像语法：montage(I)montage(BW)montage(X,map)montage(RGB)h=montage(.)immovie创建多帧索引图的电影动画语法：mov=immovie(X,map)mov=immovie(RGB)subimage在一副图中显示多个图像语法：subimage(X,map)subimage(I)subimage(BW)subimage(RGB)subimage(x,y,.)subimage(.)truesize调整图像显示尺寸语法：truesize(fig,m

8、rowsmcols)truesize(fig)warp将图像显示到纹理映射表面语法：warp(X,map)warp(I,n)warp(z,.)warp(x,y,z,.)h=warp(.)zoom缩放图像语法：zoomonzoomoffzoomoutzoomresetzoomzoomxonzoomyonzoom(factor)zoom(fig,option)课程设计分析2.1图像的霍夫曼编码概述赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生。Huffman编码是一种基于统计的无损编码。根据变长最佳编码定理，

9、Huffman编码步骤如下：（1）将信源符号x按其出现的概率，由大到小顺序排列。（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；（3）对每对组合的上边一个指定为1，下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1）；（4）画出由每个信源符号到概率1.0处的路径，记下沿路径的1和0；（5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的Huffman码。Huffman编码的特点是：（1）Huffman编码构造程序是明确的，但编出的码不是唯一的，其原因之一是两个概率分配码字“0”和“1”

10、是任意选择的（大概率为“0”，小概率为“1”，或者反之）。第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。这样编出的码字就不是唯一的。（2）Huffman编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。（3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了霍夫曼编码的应用。（4）Huffman编码只能用近似的整数位来表示单个符号，而不

11、是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原因。2.2图像的霍夫曼编码举例假设一个文件中出现了8种符号SO,SI,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要3比特。假设编码成000,001,010,011,100,101,110,111那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001共用了42比特。我们发现S0,S1,S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0,S1,S2的码字短，其它符号的

12、码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100,那么上述符号序列变成011110001110011101101000000010010010111共用了39比特,尽管有些码字如S3,S4,S5,S6变长了(由3位变成4位),但使用频繁的几个码字如S0,S1变短了，所以实现了压缩。可由下面的步骤得到霍夫曼码的码表首先把信源中的消息出现的频率从小到大排列。每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。重复(2),直到

13、最后得到和为1的根节点。将形成的二叉树的左节点标0,右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。上面的例子用Huffman编码的过程如图下图所示,其中圆圈中的数字是新节点产生的顺序。图2-1Huffman编码的二叉树示意图信源的各个消息从S0到S7的出现概率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。计算编码效率为98.5%，编码的冗余只有1.5%，可见霍夫曼编码效率很高。产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman

14、树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。仿真主程序：%以下为主程序mainp.mclcclearcloseall;%定义HufData/Len为全局变量的结构体globalHufData;globalLendisp(计算机正在准备输出霍夫曼编码结果，请耐心等待);%原始码字的灰度a=imread(kids.tif);%分区画出原始图像和灰度直方图figure;subplot(l,2,l)imshow(a);%取消坐标轴和边框axisoffboxofftitle(MATLAB自带图像,fontsize,13);subpl

15、ot(1,2,2);axisoffboxoffimhist(a);title(图像灰度直方图,fontsize,13);%图像的灰度统计GrayStatistics=imhist(a);GrayStatistics=GrayStatistics;GrayRatioo=GrayStatistics/sum(GrayStatistics);GrayRatioNO=find(GrayRatioo=0);Len=length(GrayRatioNO);%初始化灰度集，防止系统随即赋予其垃圾值GrayRatio=ones(1,Len);fori=1:LenGrayRatio(i)=GrayRatioo(

16、i);endGrayRatio=abs(sort(-GrayRatio);%将图像灰度概率赋予结构体fori=1:LenHufData(i).value=GrayRatio(i);end%霍夫曼编码/霍夫曼编码HuffmanCode(Len);%输出码字zippedHuffman=l;fori=1:LentmpData=HufData(i).code;str=;forj=1:length(tmpData)str=strcat(str,num2str(tmpData(j);zippedHuffman=zippedHuffman+1;enddisp(strcat(a,num2str(i),=,st

17、r)endi;%计算计算机一共输出多少个霍夫曼编码/霍夫曼编码zippedHuffman;%计算在删去0灰度级压缩之前的原始图像字节容量unzipped_delete=i*8;%计算压缩比率ratio_delete=zippedHuffman/unzipped_delete;%计算图像的压缩比率ad=num2str(ratio_delete*100);str2=strcat(ad,%);disp(strcat(霍夫曼编码压缩比率,=,str2)结果及分析结果:图4-1输出原图像与该图像像灰度直方图计算机正在准备输出霍夫曼编码结果，请耐心等待a1=110a2=11110a3=11101a4=01

18、100a5=01010a6=01000a7=00101a8=00011a9=111111a10=111001a11=101111a12=101100a13=101011a14=101010a15=101001a16=100111a17=100110a18=100100a19=100011a20=100010a21=100001a22=100000a23=011111a24=011110a25=011011a26=011010a27=010111a28=010110a29=010011a30=001111a31=001101a32=001100a33=001001a34=001000a35=00

19、0101a36=000011a37=000010a38=000001a39=000000a40=1111101a41=1111100a42=1110001a43=1110000a44=1011101a45=1011100a46=1011011a47=1010001a48=1010000a49=1001011a50=1001010a51=0111011a52=0111010a53=0111001a54=0111000a55=0100101a56=0100100a57=0011101a58=0011100a59=0001001a60=0001000a61=10110101a62=101101001

20、a63=101101000霍夫曼编码压缩比率=78.9683%分析：从输出灰度直方图可得出该图像的量化值主要集中在低灰度级处，通过输出可以看到该灰度级对应的霍夫曼编码，并且输出了该图像的压缩效率。明显可得出霍夫曼编码大大的节省了空间，可以明显的减少发送时间。附录子程序：%子程序：霍夫曼编码/霍夫曼编码函数HuffmanCode.mfunctionHuffmanCode(OriginSize)globalHufData;globalLenfori=l:Len%霍夫曼编码树左边纪录为1HufData(i).left=1;%霍夫曼编码树右边纪录为0HufData(i).right=O;%输出码初始化

21、为0HufData(i).code=;%排序列表初始化SortList(i).symbol=i;SortList(i).value=HufData(i).value;end%初始化原始消息数目newsymbol=OriginSize;forn=OriginSize:-1:2%将N个消息进行排序SortList=sortdata(SortList,n);%将最后两个出现概率最小的消息合成一个消息newsymbol=newsymbol+1;HufData(newsymbol).value=SortList(n-1).value+SortList(n).value;HufData(newsymbol

22、).left=SortList(n-1).symbol;HufData(newsymbol).right=SortList(n).symbol;%将消息添加到列队的最后，为N-1个消息重新排序作好准备SortList(n-1).symbol=newsymbol;SortList(n-1).value=HufData(newsymbol).value;end%遍历霍夫曼树，获得霍夫曼编码/霍夫曼编码visit(newsymbol,Len,);end%子程序：冒泡排序法函数sortdata.mfunctionreData=sortdata(SortList,n)%根据消息概率进行排序fork=n:

23、-l:2forj=1:k-1min=SortList(j).value;sbl=SortList(j).symbol;if(minvSortList(j+1).value)SortList(j).value=SortList(j+1).value;SortList(j+1).value=min;SortList(j).symbol=SortList(j+1).symbol;SortList(j+1).symbol=sbl;endendendreData=SortList;end%子程序：遍历霍夫曼编码/霍夫曼编码树搜索函数visit.mfunctionvisit(node,n,ocode)globalHufDataifnode0)%遍历左分支接点输出1,这里采用子函数嵌套调用ocode1=ocode1;visit(HufData(node).left,n,ocode1);endif(HufData(node).r