多媒体技术——哈弗曼编码试验报告

1、一、实验目的1、学习 Matlab 软件的使用和编程；2、进一步深入理解 Huffman 编码算法的原理；3、提高独立进行算法编程的能力。二、实验内容1、用 Matlab 实现 Huffman 编码算法程序；2、要求程序输出显示所有的码字以及编码效率；3、设计简单的输入界面(可以是简单的文字提示信息)，程序运行时提示用户输入代表信源符号概率的向量；要对用户输入的概率向量进行合法性检查。三、实验原理1、二进制 Huffman 编码的基本原理及算法(1) 把信源符号集中的所有符号按概率从大到小排队。(2) 取概率最小的两个符号作为两片叶子合并(缩减)到一个 节点。(3) 视此节点为新符号，其概率等

2、于被合并(缩减)的两个概率之和，参与概率排队。(4) 重复 (2)(3) 两步骤，直至全部符号都被合并(缩减)到根。(5) 从根出发，对各分枝标记0 和 1。从根到叶的路径就给出了各个码字的编码和码长。2、程序设计的原理(1) 程序的输入： 以一维数组的形式输入要进行 huffman 编码的信源符号的概率， 在运行该 程序前， 显示文字提示信息， 提示所要输入的概率矢量； 然后对输入的概率矢量进行合法性 判断，原则为：如果概率矢量中存在小于 0 的项，则输入不合法，提示重新输入；如果概率 矢量的求和大于 1，则输入也不合法，提示重新输入。(2) huffman 编码具体实现原理：1 在输入的概

3、率矩阵 p正确的前提条件下，对p进行排序，并用矩阵L记录p排序之前 各元素的顺序，然后将排序后的概率数组 p的前两项，即概率最小的两个数加和，得到新的 一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵 p以及每次排序之前 概率顺序的矩阵 a。2新生成一个 n-1 行 n 列，并且每个元素含有 n 个字符的空白矩阵， 然后进行 huffman 编码：将 c 矩阵的第 n-1 行的第一和第二个元素分别令为 0和 1(表示在编码时，根节点之下 的概率较小的元素后补 0，概率较大的元素后补 1，后面的编码都遵守这个原则)然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找

4、到值为1所在的 位置，然后在 c 矩阵中第 n-i 行中找到对应位置的编码(该编码即为第 n-i-1 行第一、 二个元素的根节点) ，则矩阵 c 的第 n-i 行的第一、二个元素的 n-1 的字符为以上求得 的编码值，根据之前的规则，第一个元素最后补 0，第二个元素最后补 1 ，则完成该行 的第一二个元素的编码，最后将该行的其他元素按照“矩阵 c中第n-i行第j+1列的值等于对应于 a矩阵中第 n-i+1行中值为j+1的前面一个元素的位置在 c矩阵中的编码值”的原则进行赋值，重 复以上过程即可完成 huffman 编码。3计算信源熵和平均码长，其比值即为编码密码效率。四、 Huffman 编码

5、的 Matlab 源程序clc clear close all; global HufData; global Len disp(计算机正在准备输出哈夫曼编码结果 a=imread(kids.tif); figure; subplot(1,2,1) imshow(a); axis off box off title(MATLAB 自带图像 ,fontsize,13); subplot(1,2,2); axis off box off imhist(a); title( 图像灰度直方图 ,fontsize,13); GrayStatistics=imhist(a); GrayStatistics

6、=GrayStatistics; GrayRatioo=GrayStatistics/sum(GrayStatistics); GrayRatioNO=find(GrayRatioo=0); Len=length(GrayRatioNO); GrayRatio=ones(1,Len);for i=1:Len GrayRatio(i)=GrayRatioo(i);% 定义 HufData/Len 为全局变量的结构体，请耐心等待);%原始码字的灰度%分区画出原始图像和灰度直方图%取消坐标轴和边框%图像的灰度统计%初始化灰度集，防止系统随即赋予其垃圾值endGrayRatio=abs(sort(-G

7、rayRatio);% 将图像灰度概率赋予结构体 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;endendi;disp(strcat(a，num2str(i)，= ，str)%计算计算机一共输出

8、多少个哈夫曼编码/霍夫曼编码zippedHuffman;%计算在删去 0 灰度级压缩之前的原始图像字节容量unzipped_delete=i*8;%计算压缩比率ratio_delete=zippedHuffman/unzipped_delete; %计算图像的压缩比率 ad=num2str(ratio_delete*100);str2=strcat(ad,%);disp(strcat( 哈夫曼编码压缩比率 ,= ,str2) 子程序：哈夫曼编码 /霍夫曼编码函数 HuffmanCode.m newsymbol=newsymbol+1; HufData(newsymbol).value=Sort

9、List(n-1).value+SortList(n).value; HufData(newsymbol).left=SortList(n-1).symbol;function HuffmanCode(OriginSize) global HufData;global Lenfor i=1:LenHufData(i).left=1;HufData(i).right=0;HufData(i).code=;SortList(i).symbol=i;SortList(i).value=HufData(i).value;End newsymbol=OriginSize;for n=OriginSize

10、:-1:2SortList=sortdata(SortList,n);% 霍夫曼编码树左边纪录为 1% 霍夫曼编码树右边纪录为 0% 输出码初始化为 0%排序列表初始化%初始化原始消息数目%将 N 个消息进行排序%将最后两个出现概率最小的消息合成一个消息HufData(newsymbol).right=SortList(n).symbol; %将消息添加到列队的最后，为 N-1 个消息重 新排序作好准备SortList(n-1).symbol=newsymbol; SortList(n-1).value=HufData(newsymbol).value;End%遍历霍夫曼树，获得霍夫曼编码 /

11、哈夫曼编码visit(newsymbol,Len,);End子程序：冒泡排序法函数 sortdata.mfunction reData=sortdata(SortList,n) %根据消息概率进行排序 for k=n:-1:2for j=1:k-1min=SortList(j).value;sbl=SortList(j).symbol;if(minSortList(j+1).value) SortList(j).value=SortList(j+1).value; SortList(j+1).value=min;SortList(j).symbol=SortList(j+1).symbol;

12、SortList(j+1).symbol=sbl;endend end reData=SortList;End% 子程序：遍历哈夫曼编码 /霍夫曼编码树搜索函数visit.mfunction visit(node,n,ocode)global HufDataif node0)%遍历左分支接点输出 1，这里采用子函数嵌套调用ocode1=ocode 1;visit(HufData(node).left,n,ocode1);endif(HufData(node).right0)%遍历右分支接点输出 0，这里采用子函数嵌套调用ocode2=ocode 0;visit(HufData(node).ri

13、ght,n,ocode2);endendend五、程序运行结果a1=110 a2=11110 a3=11101 a4=01100 a5=01010 a6=01000 a7=00101 a8=00011 a9=111111 a10=111001 a11=101111 a12=101100 a13=101011 a14=101010 a15=101001 a16=100111 a17=100110 a18=100100 a19=100011 a20=100010 a21=100001 a22=100000 a23=011111=78.9683%a24=011110 a25=011011 a26=0

14、11010 a27=010111 a28=010110 a29=010011 a30=001111 a31=001101 a32=001100 a33=001001 a34=001000 a35=000101 a36=000011 a37=000010 a38=000001 a39=000000 a40=1111101 a41=1111100 a42=1110001 a43=1110000 a44=1011101 a45=1011100 a46=1011011 a47=1010001 a48=1010000 a49=1001011 a50=1001010 a51=0111011 a52=0111010 a53=0111001 a54=0111000 a55=0100101 a56=0100100 a57=0011101 a58=0011100 a59=0001001 a60=0001000 a61=10110101 a62=