图像程序霍夫曼编码.docx
《图像程序霍夫曼编码.docx》由会员分享，可在线阅读，更多相关《图像程序霍夫曼编码.docx（9页珍藏版）》请在冰点文库上搜索。
图像程序霍夫曼编码
图像程序-霍夫曼编码
赫夫曼编码
设计原理
赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生。
Huffman编码是一种基于统计的无损编码。
设信源X的信源空间为:
X:
xx？
x,12N[X,P]:
PXPxPxPx？
Px（）:
（）（）（）（）123N,
N
其中，，现用二进制对信源X中的每一个符号（i=1,2,„N）进行xP（x）,1,iii,1
编码。
根据变长最佳编码定理，Huffman编码步骤如下:
（1）将信源符号xi按其出现的概率，由大到小顺序排列。
（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终
将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到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编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。
（3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。
（4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原因。
设计程序
clear
loadwoman;%读入图像数据
%X=imread（'girl.bmp','bmp'）;
data=uint8（X）;
[zipped,info]=huffencode（data）;%调用Huffman编码程序进行压缩
unzipped=huffdecode（zipped,info,data）;
%调用Huffman编码程序进行解码
%显示原始图像和经编码后的图像，显示压缩比，并计算均方根误差得erms=0，表示是Huffman是无失真编码
subplot（121）;imshow（data）;subplot（122）;imshow（unzipped）;%erms=compare（data（:
）,unzipped（:
））
cr=info.ratio
whosdataunzippedzipped
%huffencode函数对输入矩阵vector进行Huffman编码，返回%编码后的向量（压缩后数据）及相关信息
function[zipped,info]=huffencode（vector）
%输入和输出都是unit8格式
%info返回解码需要的机构信息
%info.pad是添加的比特数
%info.huffcodes是Huffman码字
%info.rows是原始图像行数
%info.cols是原始图像行数
%info.length是原始图像数据长度
%info.maxcodelen是最长码长
if~isa（vector,'uint8'）
error（'inputargumentmustbeauint8vector'）;end
[m,n]=size（vector）;
vector=vector（:
）';
f=frequency（vector）;%计算各符号出现的概率（调用frequency）symbols=find（f~=0）;
f=f（symbols）;
[f,sortindex]=sort（f）;%将符号按照出现的概率大小排序
symbols=symbols（sortindex）;len=length（symbols）;
symbols_index=num2cell（1:
len）;codeword_tmp=cell（len,1）;whilelength（f）>1%生产Huffman树，得到码字编码表
index1=symbols_index{1};
index2=symbols_index{2};
codeword_tmp（index1）=addnode（codeword_tmp（index1）,uint8（0
））;
codeword_tmp（index2）=addnode（codeword_tmp（index2）,uint8（1
））;
f=[sum（f（1:
2））f（3:
end）];
symbols_index=[{[index1,index2]}symbols_index（3:
end）];
[f,sortindex]=sort（f）;
symbols_index=symbols_index（sortindex）;
end
codeword=cell（256,1）;
codeword（symbols）=codeword_tmp;len=0;
forindex=1:
length（vector）%得到整个图像所有比特数
len=len+length（codeword{double（vector（index））+1}）;
end
string=repmat（uint8（0）,1,len）;pointer=1;
forindex=1:
length（vector）%对输入图像进行编码
code=codeword{double（vector（index））+1};
len=length（code）;
string（pointer+（0:
len-1））=code;
pointer=pointer+len;
end
len=length（string）;
pad=8-mod（len,8）;
%非8整数倍时，最后补pad个0
ifpad>0
string=[stringuint8（zeros（1,pad））];end
codeword=codeword（symbols）;
codelen=zeros（size（codeword））;weights=2.^（0:
23）;
maxcodelen=0;
forindex=1:
length（codeword）
len=length（codeword{index}）;
iflen>maxcodelen
maxcodelen=len;
end
iflen>0
code=sum（weights（codeword{index}==1））;
code=bitset（code,len+1）;
codeword{index}=code;
codelen（index）=len;
end
end
codeword=[codeword{:
}];
%计算压缩后的向量
cols=length（string）/8;
string=reshape（string,8,cols）;weights=2.^（0:
7）;
zipped=uint8（weights*double（string））;%码表存储到一个稀疏矩阵
huffcodes=sparse（1,1）;
forindex=1:
nnz（codeword）
huffcodes（codeword（index）,1）=symbols（index）;
end
%填写解码时所需的结构信息
info.pad=pad;
info.huffcodes=huffcodes;
info.ratio=cols./length（vector）;info.length=length（vector）;info.maxcodelen=maxcodelen;info.rows=m;
info.cols=n;
%huffdecode函数对输入矩阵vector进行Huffman编码，%返回解压后的图像数据
functionvector=huffdecode（zipped,info,image）
if~isa（zipped,'uint8'）
error（'inputargumentmustbeauint8vector'）;end
%产生0，1序列，每位占一个字节
len=length（zipped）;
string=repmat（uint8（0）,1,len.*8）;bitindex=1:
8;
forindex=1:
len
string（bitindex+8.*（index-1））=uint8（bitget（zipped（index）,
bitindex））;
end
string=logical（string（:
）'）;len=length（string）;
%开始解码
weights=2.^（0:
51）;
vector=repmat（uint8（0）,1,info.length）;vectorindex=1;
codeindex=1;
code=0;
forindex=1:
len
code=bitset（code,codeindex,string（index））;
codeindex=codeindex+1;
byte=decode（bitset（code,codeindex）,info）;
ifbyte>0
vector（vectorindex）=byte-1;
codeindex=1;
code=0;
vectorindex=vectorindex+1;
end
end
%vector=reshape（vector,info.rows,info.cols）;
%函数addnode添加节点
functioncodeword_new=addnode（codeword_old,item）codeword_new=cell（size（codeword_old））;forindex=1:
length（codeword_old）
codeword_new{index}=[itemcodeword_old{index}];
end
%函数frequency计算各符号出现的概率
functionf=frequency（vector）
if~isa（vector,'uint8'）
error（'inputargumentmustbeauint8vector'）;
end
f=repmat（0,1,256）;
len=length（vector）;
forindex=0:
255
f（index+1）=sum（vector==uint8（index））;end
f=f./len;
%函数decode返回码字对应的符号
functionbyte=decode（code,info）
byte=info.huffcodes（code）;
（1）对图像woman进行编码
cr=0.6291
NameSizeBytesClassAttributes
data256x25665536uint8
unzipped1x6553765537uint8
zipped1x4122641226uint8
（2）对图像cameraman.tif进行编码
cr=0.8806
NameSizeBytesClassAttributes
data256x25665536uint8
unzipped1x6553765537uint8
zipped1x5771257712uint8
cr=0.8708
NameSizeBytesClassAttributes
data409x541x3663807uint8
unzipped1x663808663808uint8
zipped1x578031578031uint8
心得体会
通过本次课程设计我进一步体会到了数字图像处理的神秘，我们用霍夫曼编码实现了对图像的压缩，本以为把程序输入了就可以正确运行，但是发现书上的程序在matlab中有很多的错误，因此用了很长的时间进行修改，最后终于顺利运行了，这个过程让我明白了不能完全依赖课本，一定要有自己的思考和分析才能攻克难题，而且遇到困难后应该学会互助和自信，希望以后还能得到同样的收获和锻炼。
升级会员 