《图像的霍夫曼编码教材》由会员分享，可在线阅读，更多相关《图像的霍夫曼编码教材（14页珍藏版）》请在金锄头文库上搜索。
1、 序号： 图像的霍夫曼编码姓 名： 班 级： 学 号： 专 业： 指导老师： 完成时间： 湖南理工学院物理与电子学院 目 录摘要：1一、引言1二、霍夫曼编码简介1三、 霍夫曼编码21、霍夫曼编码规则22、霍夫曼树3（1）霍夫曼树的相关概念3（2）霍夫曼算法3（3）霍夫曼树的构建43. 霍夫曼的局限性5四、霍夫曼编码分类61、 截断霍夫曼编码62、 自适应霍夫曼编码6五、 仿真8六、 结论12参考文献12摘要：霍夫曼编码是一种常用的无损编码，他基于不同符号的概率分布，在信息源中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码越长，从而达到用尽可能少的码符号表示源数据。本文介绍了霍夫曼编
2、码的原理、方法、特点、应用、霍夫曼树的生成过程，霍夫曼编码的产生，霍夫曼表的构建，霍夫曼编码的结果以及怎样用MATLAB实现霍夫曼编码。关键字：无损编码 霍夫曼编码 霍夫曼树 MATLAB一、引言随着科学技术的发展和需求，人们广泛致力于对各种文本、图片、图形、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术研究，使信源的数据压缩技术得以蓬勃发展和逐渐走向成熟。在信息化高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息在传递的过程中，能够保持节省性和保密性和无损性，而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压是相当有必要的。二、霍
3、夫曼编码简介1952年，DavidA.Huffman在麻省理工攻读博士时，根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的编码思想提出了一种不定长编码的方法霍夫曼编码，并发表于一种构建极小多余编码的方法一文。霍夫曼编码是常用的无损编码方法，广泛应用于图像压缩技术。JPEG标准中的基准模式采用的就是霍夫曼编码。霍夫曼编码是不定长编码，即代表各元素的码字长度不等。该编码是基于不同符号的概率分布，在信息源中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码越长，从而达到用尽可能少的码符号表示源数据。它在变长编码中是最佳的。在计算机信息处理中，“霍夫曼编码”是一种一致
4、性编码法（又称熵编码法）霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。3、 霍夫曼编码1、霍夫曼编码规则设信源X的信源空间为： 其中，现用二进制对信源中的每一个符号进行编码a. 将信源符号xi按其出现的概率，由大到小顺序排列。b. 将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；c. 对每对组合的上边一个指定为1，下边一个指定为0（或相反：对
5、上边一个指定为0，下边一个指定为1）；d. 画出由每个信源符号到概率1处的路径，记下沿路径的1和0，所得的就是该符号的霍夫曼码字。2、霍夫曼树（1）霍夫曼树的相关概念霍夫曼树：指所有叶子结点的二叉树中带权路径长度最小的二叉树。节点的带权路径长度：从树的根节点到该节点的路径长度与该节点权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。（2）霍夫曼算法a. 根据给定的n个权值w1,w2,.,wn构造n棵二叉树的集合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。b. 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二
6、叉树的根结点的权值为其左、右子树上根结点的权值之和。c. 在F中删除这两棵树，同时将新得到的二叉树加入F中。d. 重复（2)和（3)，直到F中只含一棵树为止。这棵树便是最优二叉树。（3）霍夫曼树的构建假设对由a1、a2、a3、a4、a5、a6、a7、a8八个信源符号组成的源信息字符串:“a1 a1 a2 a2 a3 a3 a3 a4 a4 a4 a4 a5 a5 a5 a6 a6 a6 a7 a7 a8”进行霍夫曼编码。首先应对信息中各数字出现的次数进行统计，得出各数字出现的相对概率。假设各数字出现的次数及概率如表1所示。 表一码值a1a2a3a4a5a6a7a8次数22343331概率0.1
7、0.10.150.20.150.150.10.05 具体过程是这样的，先将所有符号排成一行构成8个最底层节点。首先将这些节点中最小两个概率值相加：0.05+0.1=0.15, 得到新的节点，这时拥有的概率值为0.2, 0.1, 0.1, 0.15, 0.15, 0.15, 0.15。再将两个最小的概率值相加得到新的节点. . 直到得到根节点概率为1.0为止。相加时，对于概率值相等的多个节点，可以任意选取。除根节点外，设节点左边分支为0，右边分支为1（也可以反过来）。根据表一生成的霍夫曼树如图1所示。 图1对于各值（码值）的代码（码字）就是从根节点出发到底层节点所经历的分支序列。如a4的代码（码
8、字）为00，a6的码字为111. .通常a4和a6等称为码值，00和111等称为码字。所有码值和码字对应关系如表2所示。3. 霍夫曼的局限性a. 利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。b. 输入符号数受限于可实现的码表尺寸c. 译码复杂d. 需要实现知道输入符号集的概率分布e. 没有错误保护功能四、霍夫曼编码分类1、 截断霍夫曼编码霍夫曼编码不仅适用于压缩文本文件，经过符号合并后也可用于二进制文件。但在实用中，霍夫曼编码的输入符号数常受限于可实现的码表大小。JEPEG采用将码字截断为“前缀码（SSSS）+尾码”的方法，对
9、码表进行了简化，这种编码方法称为截断霍夫曼编码。前缀码用来指明尾码的有效位数（设为B位），用标准的霍夫曼编码；尾码则直接采用B位自然二进码（对于给定的前缀码它为定长码，高位在前）。对于8位量化的图像，SSSS值的范围为011，故其码表只有12项。根据DIFF的幅度范围由表4.2查出前缀码字和尾码的位数后，则可按以下规则直接写出尾码的码字,即 按此规则，当DIFF0时，尾码的最高位是“1”；而当DIFF0时则为“0”。解码时则可借此来判断DIFF的正负。2、 自适应霍夫曼编码（1） 自适应霍夫曼编码提出的目的和意义在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中的符号出现概率，因此必须对
10、输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。其次，在存储和传送霍夫曼编码时，必须先存储和传送霍夫曼编码树。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。为了解决静态Huffman编码的缺点，人们提出了自适应Huffman编码这种方案不需要事先扫描输入符号流，而是随着编码的进行同时构造Huffman树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量
11、的图像和视频流传输中中获得了广泛的应用。（2）自适应霍夫曼编码的原理这种方案在不需要事先构Huffman树，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。由于自适应Huffman编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的NYT节点的编码树作为初始状态，然后根据Huffman编码数据流，对符号进行还原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号之前，Huffman树都处于与进行编码时使用的的Huffman树完全相同
12、的状态，保证了解码的正确性。自适应霍夫曼编码是一种扩展的熵编码方法，相比于先前的静态霍夫曼编码，自适应霍夫曼编码具有仅需单遍扫描、无需传送编码树、能够对输入符号流的局部统计规律变化做出反应等一系列优点，具有更高的压缩效率。这些优点使得它在一些实时性、可靠性要求比较高的场合得到了广泛的应用，被称为近代压缩算法的灵魂。5、 仿真用MATLAB实现图像的霍夫曼编码和解码，代码如下：close all; clear all; clc; I=imread(lena.bmp);I=im2double(I)*255;height,width=size(I); %求图像的大小HWmatrix=zeros(he
13、ight,width);Mat=zeros(height,width); HWmatrix(1,1)=I(1,1); for i=2:height%以下将图像像素值传递给矩阵Mat Mat(i,1)=I(i-1,1);endfor j=2:width Mat(1,j)=I(1,j-1);endfor i=2:height%以下建立待编码的数组symbols和每个像素出现的概率矩阵p for j=2:width Mat(i,j)=I(i,j-1)/2+I(i-1,j)/2; endendMat=floor(Mat);HWmatrix=I-Mat;SymPro=zeros(2,1); SymNum
14、=1; SymPro(1,1)=HWmatrix(1,1); SymExist=0;for i=1:height for j=1:width SymExist=0; for k=1:SymNum if SymPro(1,k)=HWmatrix(i,j) SymPro(2,k)=SymPro(2,k)+1; SymExist=1; break; end end if SymExist=0 SymNum=SymNum+1; SymPro(1,SymNum)=HWmatrix(i,j); SymPro(2,SymNum)=1; end endendfor i=1:SymNum SymPro(3,i)=SymPro(2,
