多媒体技术之哈弗曼编码实验报告.docx

一、实验目的
1、学习Matlab软件的使用和编程；
2、进一步深入理解Huffman编码算法的原理；
3、提高独立进行算法编程的能力。
二、实验内容
1、用Matlab实现Huffman编码算法程序；
2、要求程序输出显示所有的码字以及编码效率；
3、设计简单的输入界面（可以是简单的文字提示信息），程序运行时提示用户输入代表信源符号概率的向量；要对用户输入的概率向量进行合法性检查。
三、实验原理
1、二进制Huffman编码的基本原理及算法
(1) 把信源符号集中的所有符号按概率从大到小排队。
(2) 取概率最小的两个符号作为两片叶子合并（缩减）到一个 节点。
(3) 视此节点为新符号，其概率等于被合并（缩减）的两个概率之和，参与概率排队。
(4) 重复(2)(3)两步骤，直至全部符号都被合并（缩减）到根。
(5) 从根出发，对各分枝标记0和1。从根到叶的路径就给出了各个码字的编码和码长。
2、程序设计的原理
(1)程序的输入：以一维数组的形式输入要进行huffman编码的信源符号的概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。
（2）huffman编码具体实现原理：
1>在输入的概率矩阵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行找到值为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编码的Matlab源程序
clc
clear
close all; %定义HufData/Len为全局变量的结构体
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=GrayStatistics';
GrayRatioo=GrayStatistics/sum(GrayStatistics);
GrayRatioNO=find(GrayRatioo~=0);
Len=length(GrayRatioNO); %初始化灰度集，防止系统随即赋予其垃圾值
GrayRatio=ones(1,Len);
for i=1:Len
GrayRatio(i)=GrayRatioo(i);
end
GrayRatio=abs(sort(-GrayRatio));%将图像灰度概率赋予结构体
for i=1:Len
HufData(i).value=GrayRatio(i);
End % 哈夫曼编码/霍夫曼编码
HuffmanCode(Len); %输出码字

zippedHuffman=1;
for i=1:Len
tmpData=HufData(i).code;
str='';
for j=1:length(tmpData)
str=strcat(str,num2str(tmpData(j)));
zippedHuffman=zippedHuffman+1;
end
disp(strcat('a',num2str(i),'= ',str))
end
i; %计算计算机一共输出多少个哈夫曼编码/霍夫曼编码
zippedHuffman; %计算在删去0灰度级压缩之前的原始图像字节容量
unzipped_delete=i*8; %计算压缩比率
ratio_delete=zippedHuffman/unzipped_delete; %计算图像的压缩比率
ad=num2str(ratio_delete*100);
str2=strcat(ad,'%');
disp(strcat('哈夫曼编码压缩比率','= ',str2))
子程序：哈夫曼编码/霍夫曼编码函数HuffmanCode.m
function HuffmanCode(OriginSize)
global HufData;
global Len
for i=1:Len %%霍夫曼编码树左边纪录为1
HufData(i).left=1; %%霍夫曼编码树右边纪录为0
HufData(i).right=0; %%输出码初始化为0
HufData(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+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,Len,[]);
End
子程序：冒泡排序法函数sortdata.m
function reData=sortdata(SortList,n) %根据消息概率进行排序
for k=n:-1:2
for j=1:k-1
min=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=sbl;
end
end
end
reData=SortList;
End %子程序：遍历哈夫曼编码/霍夫曼编码树搜索函数visit.m
function visit(node,n,ocode)
global HufData
if node<=n %如果没有哈夫曼编码/霍夫曼编码树的子接点直接输出原始码，这里为空码（[]）
HufData(node).code=ocode;
else
if(HufData(node).left>0) %遍历左分支接点输出1，这里采用子函数嵌套调用
ocode1=[ocode 1];
visit(HufData(node).left,n,ocode1);
end
if(HufData(node).right>0)
%遍历右分支接点输出0，这里采用子函数嵌套调用
ocode2=[ocode 0];
visit(HufData(node).right,n,ocode2);
end
end
end
五、程序运行结果
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
a24=011110
a25=011011
a26=011010
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=101101001
a63=101101000
哈夫曼编码压缩比率=78.9683%

六、实验总结
在该实验的过程中，利用一个矩阵记录每次排序前概率的所在位置，是该实验的关键，在编码的过程中利用该矩阵就能比较容易进行huffman编码。通过这个实验，对huffman编码的具体实现原理了解的更加深刻，加深了对课程的理解，结合课本上的知识，在老师的帮助下，解决了在实验的过程中也遇到了一些问题，最终完成了这次试验，同时这次试验巩固了我对matlab的掌握。收获良多。