图像程序霍夫曼编码.docx
- 文档编号:1769747
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:9
- 大小:32.54KB
图像程序霍夫曼编码.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中有很多的错误,因此用了很长的时间进行修改,最后终于顺利运行了,这个过程让我明白了不能完全依赖课本,一定要有自己的思考和分析才能攻克难题,而且遇到困难后应该学会互助和自信,希望以后还能得到同样的收获和锻炼。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图像 程序 霍夫曼 编码