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

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

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

3、某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。关键字：哈夫曼；信源编码；MATLAB目 录1设计目的及相关知识11.1设计目的11.2图像的霍夫曼编码概念11.3Matlab图像处理通

4、用函数12课程设计分析32.1 图像的霍夫曼编码概述32.2 图像的霍夫曼编码举例43仿真64结果及分析95附录12结束语15参考文献161设计目的及相关知识1.1设计目的1）了解霍夫曼编码的原理。2）理解图像的霍夫曼编码原理，了解其应用，掌握图像的霍夫曼编码的方法。3）对图像编码程序设计进行较深入的认识，对知识牢固掌握。4）掌握图像霍夫曼编码的整个过程及其中的注意事项。5）了解图像无损压缩的目的及好处。1.2图像的霍夫曼编码概念所谓霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加

5、时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码1.3 Matlab图像处理通用函数colorbar  显示彩色条语法：colorbar colorbar('vert') colorbar('horiz') colorbar(h) h=colorbar(.) colorbar(.,'peer',axes_handle)getimage从坐标轴取得图像数据语法：A=getimage(h) x,y,A=getimage(h) .,

6、A,flag=getimage(h) .=getimageimshow显示图像语法：imshow(I,n) imshow(I,low high) imshow(BW) imshow(X,map) imshow(RGB) imshow(.,display_option) imshow(x,y,A,.) imshow filename h=imshow(.)montage 在矩形框中同时显示多幅图像语法：montage(I) montage(BW) montage(X,map) montage(RGB) h=montage(.)immovie创建多帧索引图的电影动画语法：mov=immovie(X

7、,map) mov=immovie(RGB)subimage在一副图中显示多个图像语法：subimage(X,map) subimage(I) subimage(BW)   subimage(RGB) subimage(x,y,.) subimage(.)truesize调整图像显示尺寸语法：truesize(fig,mrowsmcols) truesize(fig)warp 将图像显示到纹理映射表面语法：warp(X,map) warp(I ,n) warp(z,.) warp(x,y,z,.)   h=warp(.)zoom 缩放图像语法：zoom on zoom of

8、f zoom out zoom reset zoom zoom xon zoom yon zoom(factor) zoom(fig,option)2课程设计分析2.1 图像的霍夫曼编码概述赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生。Huffman编码是一种基于统计的无损编码。根据变长最佳编码定理，Huffman编码步骤如下：（1）将信源符号xi按其出现的概率，由大到小顺序排列。（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到

9、1.0为止；（3）对每对组合的上边一个指定为1，下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1）；（4）画出由每个信源符号到概率1.0处的路径，记下沿路径的1和0；（5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的Huffman码。Huffman编码的特点是：（1）Huffman编码构造程序是明确的，但编出的码不是唯一的，其原因之一是两个概率分配码字“0”和“1”是任意选择的（大概率为“0”，小概率为“1”，或者反之）。第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。这样编出的码字就不是唯一的。（2）Huffman编码结果，码字不等长，平均码字最短，效率最

10、高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。（3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了霍夫曼编码的应用。（4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原因。2.2 图像的霍夫曼编码举例假设一个文件中出现了8种符号S0，S1，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3

11、比特。假设编码成000，001，010，011，100，101，110，111那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01，11，101，0000，0001，0010，0011，100，那么上述符号序列变成0111100011100

12、11101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。可由下面的步骤得到霍夫曼码的码表(1) 首先把信源中的消息出现的频率从小到大排列。(2) 每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。(3) 重复(2)，直到最后得到和为1的根节点。(4) 将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。上面的例子用H

13、uffman编码的过程如图下图所示，其中圆圈中的数字是新节点产生的顺序。图2-1    Huffman编码的二叉树示意图信源的各个消息从S0到S7的出现概率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。计算编码效率为98.5%，编码的冗余只有1.5%，可见霍夫曼编码效率很高。产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。3仿真主程序

14、：%以下为主程序mainp.mclcclearclose all;%定义HufData/Len为全局变量的结构体global HufData;global Lendisp('计算机正在准备输出霍夫曼编码结果,请耐心等待');%原始码字的灰度a=imread('kids.tif');%分区画出原始图像和灰度直方图figure;subplot(1,2,1)imshow(a);%取消坐标轴和边框axis offbox offtitle('MATLAB自带图像','fontsize',13);subplot(1,2,2);axis off

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

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

17、trcat('a',num2str(i),'= ',str)endi;%计算计算机一共输出多少个霍夫曼编码/霍夫曼编码zippedHuffman;%计算在删去0灰度级压缩之前的原始图像字节容量unzipped_delete=i*8;%计算压缩比率ratio_delete=zippedHuffman/unzipped_delete;%计算图像的压缩比率ad=num2str(ratio_delete*100);str2=strcat(ad,'%');disp(strcat('霍夫曼编码压缩比率','= ',str2)4

18、结果及分析结果:图4-1 输出原图像与该图像像灰度直方图计算机正在准备输出霍夫曼编码结果,请耐心等待a1=110a2=11110a3=11101a4=01100a5=01010a6=01000a7=00101a8=00011a9=111111a10=111001a11=101111a12=101100a13=101011a14=101010a15=101001a16=100111a17=100110a18=100100a19=100011a20=100010a21=100001a22=100000a23=011111a24=011110a25=011011a26=011010a27=01011

19、1a28=010110a29=010011a30=001111a31=001101a32=001100a33=001001a34=001000a35=000101a36=000011a37=000010a38=000001a39=000000a40=1111101a41=1111100a42=1110001a43=1110000a44=1011101a45=1011100a46=1011011a47=1010001a48=1010000a49=1001011a50=1001010a51=0111011a52=0111010a53=0111001a54=0111000a55=0100101a56

20、=0100100a57=0011101a58=0011100a59=0001001a60=0001000a61=10110101a62=101101001a63=101101000霍夫曼编码压缩比率=78.9683%分析：从输出灰度直方图可得出该图像的量化值主要集中在低灰度级处，通过输出可以看到该灰度级对应的霍夫曼编码，并且输出了该图像的压缩效率。明显可得出霍夫曼编码大大的节省了空间，可以明显的减少发送时间。5附录子程序：%子程序：霍夫曼编码/霍夫曼编码函数HuffmanCode.mfunction HuffmanCode(OriginSize)global HufData;global Le

21、nfor i=1:Len%霍夫曼编码树左边纪录为1HufData(i).left=1;%霍夫曼编码树右边纪录为0HufData(i).right=0;%输出码初始化为0HufData(i).code=;%排序列表初始化SortList(i).symbol=i;SortList(i).value=HufData(i).value;end%初始化原始消息数目newsymbol=OriginSize;for n=OriginSize:-1:2%将N个消息进行排序SortList=sortdata(SortList,n);%将最后两个出现概率最小的消息合成一个消息newsymbol=newsymbol

22、+1;HufData(newsymbol).value=SortList(n-1).value+SortList(n).value;HufData(newsymbol).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,L

23、en,);end%子程序：冒泡排序法函数sortdata.mfunction reData=sortdata(SortList,n)%根据消息概率进行排序for k=n:-1:2for j=1:k-1min=SortList(j).value;sbl=SortList(j).symbol;if(min<SortList(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=sb

24、l;endendendreData=SortList;end%子程序：遍历霍夫曼编码/霍夫曼编码树搜索函数visit.mfunction visit(node,n,ocode)global HufDataif node<=n%如果没有霍夫曼编码/霍夫曼编码树的子接点直接输出原始码，这里为空码（）HufData(node).code=ocode;elseif(HufData(node).left>0)%遍历左分支接点输出1，这里采用子函数嵌套调用ocode1=ocode 1;visit(HufData(node).left,n,ocode1);endif(HufData(node).right