图像编码——霍夫曼编码

编号：题目名称图像编码——霍夫曼编码学生姓名学号学院信息科学与工程学院专业年级2009级通信一班指导教师职称老师填写时间2012年10月27日2摘要进入21世纪，人类已步入信息社会，新信息技术革命使人类被日益增多的多媒体信息所包围，这也正好迎合了人类对要示提高视觉信息的需求。多媒体信息主要有三种形式：文本、声音和图像。从信息传输的发展史（电报、电话、传真、收音机、电视机直至现在的网络）可以看出，人们逐渐将信息传输的重点从声音转向图像，然而图像是三种信息形式中数据量最大的，这给图像的传输和存储带来了极大的困难。对于巨大的数字图像数据量，如果不经过压缩，不仅超出了计算机的存储和处理能力，而且在现有的通信信道的传输速率下，是无法完成大量多媒体信息实时传输的，数字图像高速传输和存贮所需要的巨大容量已成为推广数字图像通信和最大障碍。因此，为了存储、处理和传输这些数据，必须进行压缩。图像压缩之所以能够进行压缩是因为原始图像数据是高度相关的，存在很大的数据冗余。数字图像包含的冗余信息一般有以下几种：空间冗余、时间冗余、信息熵冗余、统计冗余、结构冗余、视觉冗余以及知识冗余等。图像压缩算法就是要在保证图像一定的重建质量的同时，尽可能多的去除这些冗余信息，以达到对图像压缩的目的。关键词：图像处理,图像压缩,压缩算法,图像编码,霍夫曼编码1.图像数据压缩原理对数字图像进行压缩通常利用两个基本原理:一是数字图像的相关性。在图像的同一行相邻象素之间，相邻象素之间，活动图像的相邻帧的对应象素之间往往存在很强的相关性，去除或减少这些相关性，也即去除或减少图像信息中的冗余度也就实现了对数字图像的压缩。帧内象素的相关称做空域相关性。相邻帧间对应象素之间的相关性称做时域相关性。二是人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。图像数据压缩的目的是在满足一定图像质量的条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量，在信息论中称为信源编码。图像压缩是通过删除图像数据中冗余的或者不必要的部分来减小图像数据量的技术，压缩过程就是编码过程，解压缩过程就是解码过程。压缩技术分为无损压缩和有损压缩两大类，前者在解码时可以精确地恢复原图像，没有任何损失；后者在解码时只能近似原3图像，不能无失真地恢复原图像。假设有一个无记忆的信源,它产生的消息为{ai},1≤i≤N,其出现的概率是已知的,记为P(ai)。则其信息量定义为:由此可见一个消息出现的可能性越小，其信息量就越多，其出现对信息的贡献量越大，反之亦然。信源的平均信息量称为“熵”（entropy），可以表示为：对上式取以2为底的对数时，单位为比特（bits）：根据香农（Shannon）无噪声编码定理，对于熵为H的信号源，对其进行无失真编码所可能达到的最低比特数为，这里为一任意小的正数，因此可能达到的最大压缩比：其中B是原始图像的平均比特率。在图像压缩中，压缩比是一个重要的衡量指标。可以定义压缩比为：2.霍夫曼编码Huffman编码在无损压缩的编码方法中，它是一种有效的编码方法。它是霍夫曼博士在1952年根据可变长最佳编码定理提出的。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，4它是一种无损编码方法。采用霍夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。例如：假设信源符号为【a、b、c、d、e、f、g】，其出现的概率相应的为【0.25、0.025、0.025、0.05、0.35、0.25、0.05】，一共7个字符，对其进行huffman编码，算法如下：首先按照每个字符出现的频率大小从左到右排列：0.35、0.25、0.25、0.05、0.05、0.025、0.025；选出最小的两个值作为叶子节点构成一棵二叉树，值较大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行2），直到最后得到值为1的根节点。得到一棵huffman树，如下图所示：5图2.1在得到的huffman树上左分支标记1，右分支标记0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的0、1字符串即为对应叶子节点所在字符的编码。a、b、c、d、e、f、g七个字符的huffman编码分别是：10、0001、0000、0011、11、01、0010，可以看到,符号只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径。3.哈夫曼编码的图像压缩设计目标是实现Huffman压缩的编码器。编码器的工作过程呢个如下；首先读入待压缩的源文件，为保证与源文件信息完全一致，对文件的读写操作都用二进制文件的方式进行。与这只偶那个方式对应的是ASCII方式读写。然后建立并分析字母表，对读入6内存的源文件我们以字节为单元进行分析，将类型表示，其用C++内建的ＣＨＡＲ，最多将有２５６中可能的字符。我们对每种字符的出现频度进行统计，以频度作为建立Ｈuffman树的权值。频度表建好之后，就可以根据前述算法建立Huffman树，对出现的每种字符进行Huffman编码。此入时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件。编码的核心是Huffman树，它也是连接编码的纽带。考虑到Huffman树节点的设计。编码时从叶节点逐步构建中间节点，到整颗树。树的节点应该应该包括的信息有：节点表示的字符，子字节的位置，字符出现的频度，父节点的位置等，这些都是构造Huffman所需要的。而解码时，我们只需要能够根据位序列从树的根节点循次遍历到叶节点，叶节点保留其表示的字符，这就足够了。4.设计程序;clearloadwoman;%读入图像数据%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.ratiowhosdataunzippedzipped%huffencode函数对输入矩阵vector进行Huffman编码，返回%编码后的向量（压缩后数据）及相关信息function[zipped,info]=huffencode(vector)%输入和输出都是unit8格式%info返回解码需要的机构信息%info.pad是添加的比特数7%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);%计算各符号出现的概率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);endcodeword=cell(256,1);codeword(symbols)=codeword_tmp;len=0;forindex=1:length(vector)%得到整个图像所有比特数len=len+length(codeword{double(vector(index))+1});end8string=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;endlen=length(string);pad=8-mod(len,8);%非8整数倍时，最后补pad个0ifpad0string=[stringuint8(zeros(1,pad))];endcodeword=codeword(symbols);codelen=zeros(size(codeword));weights=2.^(0:23);maxcodelen=0;forindex=1:length(codeword)len=length(codeword{index});iflenmaxcodelenmaxcodelen=len;endiflen0code=sum(weights(codeword{index}==1));code=bitset(code,len+1);codeword{index}=code;codelen(index)=len;endendcodeword=[codeword{:}];%计算压缩后的向量cols=length(string)/8;string=reshape(string,8,cols);weights=2.^(0:7);9zipped=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.