第三章霍夫曼编码南京林业大学毕业设计（论文）.doc

《第三章霍夫曼编码南京林业大学毕业设计（论文）.doc》由会员分享，可在线阅读，更多相关《第三章霍夫曼编码南京林业大学毕业设计（论文）.doc（47页珍藏版）》请在三一办公上搜索。

1、南京林业大学本科毕业设计（论文）题 目： 霍夫曼编码及其效率的研究 学 院： 南方学院 专 业： 电子信息工程 学 号： N080802124 学生姓名： 徐佳迪 指导教师： 胡洁 职 称： 讲师 二O一二 年 五 月 二十 日摘要Huffman编码是一种无损编码，广泛用于数据文件压缩的十分有效的编码方法，其在电子计算机、电视、遥控和通讯等方面广泛使用。其压缩通常在20%90%之间。哈夫曼编码算法是利用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 本文主要研究Huffman编码在图像压缩方面的应用，介绍了Huffman编码的原理和步骤。通过实践运用Matlab工具验证

2、Huffman算法在图像的压缩和图像复原中可以取得良好的压缩效果。Huffman编码图像压缩算法可以提高图像传输效果和质量，具有较好的应用前景及可扩展性。关键词：Huffman编码 无损压缩 Matlababstract Huffman coding is a lossless coding，which is widely used in data file compression and the computer,TV,remote control and communication.The compression is usually 20% to 90%.Huffman encoding

3、 algorithm is based on character frequency table in the document to create a 0,1 string to get an optimal representation of each character. This paper mainly studies the application of Huffman coding in image compression , the principles and steps of the Huffman coding have been introduce, And Matla

4、b has been utilized to realize the Huffman coding. From the results, it can been concluded that Huffman coding can achieve good compression in image compression and image restoration. .Huffman coding can improve the effectiveness and quality of image transmission, has good application prospects and

5、expansibility.Key word：Huffman coding lossless compression Matlab目录第一章 绪论61.1 图像压缩编码的现状和发展趋势61.2 课题的研究背景71.3 国内外研究状况71.4 课题研究的目的和意义81.5 本文主要内容9第二章 图像压缩和统计编码102.1 图像压缩102.1.1 图像压缩技术概念102.1.2 图像压缩原理102.1.3 图像压缩技术分类112.1.4 图像压缩目前的目标112.1.5 图像压缩目前的标准122.1.6 图像压缩效果的评估122.2统计编码122.1.1 统计编码的概念122.1.2信息量132

6、.1.4 熵编码的概念132.1.5 常见的统计编码14第三章 霍夫曼编码173.1 霍夫曼编码的原理173.2 霍夫曼编码步骤：173.3 霍夫曼图像压缩算法性能评价183.4霍夫曼图像压缩的缺点193.5 Huffman编码在实际情况中的处理193.6 霍夫曼编码的软件设计203. 6.1 对灰度分布均匀图像进行霍夫曼编码的结果及分析203.6.2 对灰度分布不均匀图像进行霍夫曼编码的结果及分析22第四章 压缩编码与其他编码的比较254.1 霍夫曼编码254.2 DCT（离散余弦变换）274.2.1 DCT概念274.2.2 DCT变换原理274.2.3 DCT变换编码的步骤284.2.4

7、 程序运行结果294.2 小波变换编码324.2.1 小波变换概念324.2.2 小波变换原理324.2.3 小波变换的步骤324.2.4序运行结果324.3 三种图像编码的比较34第五章 总结35致谢36参考文献37第一章 绪论1.1 图像压缩编码的现状和发展趋势 1948年提出电视数字化后，就开始对图像压缩编码技术的研究工作，至今已有50多年的历史。图像压缩的基本理论起源于20世纪40年代末香农的信息理论。香农的编码定理告诉我们，在不产生任何失真的前提下，通过合理的编码，对于每一个信源符号分配不等长的码字，平均码长可以任意接近于信源的熵。在五十年代和六十年代，图像压缩技术由于受到电路技术等

8、的制约，仅仅停留在预测编码、亚采样以及内插复原等技术的研究，还很不成熟。1969年在美国召开的第一届“图像编码会议”标志着图像编码作为一门独立的学科诞生了。到了70年代和80年代，图像压缩技术的主要成果体现在变换编码技术上，矢量量化编码技术也有较大发展，有关于图像编码技术的科技成果和科技论文与日俱增，图像编码技术开始走向繁荣。自80年代后期以后，由于小波变换理论，分形理论，人工神经网络理论，视觉仿真理论的建立，人们开始突破传统的信源编码理论，例如不再假设图像是平稳的随机场。图像压缩编码向着更高的压缩比和更好的压缩质量的道路前进，进入了一个崭新的、欣欣向荣的大发展时期。如今图像压缩编码技术广泛地

9、被应用在各个领域。如：电视计算机、多媒体出版物、遥感图像数据库等。它已经为开创新的应用领域提供了良好的技术基础。到目前为止，图像压缩编码技术已经发展到第二代编码技术。1、 第一代编码技术包括建立在shannon的码率失真理论基础上的预测编码、变换编码、统计编码及Oliver提出的PCM编码理论。虽然这些编码技术在中等压缩率的情况下，能提供非常好的图像质量，但在码率非常低得情况下，无法提供令人满意的质量。究其原因是由于这些技术没有利用图像的结构特点，同时也没有考虑人类视觉系统的特性，因此它们也就只能以像素或块作为编码的对象。2、 第二代编码包括基于分形的编码、基于模型的编码、基于区域分割的编码，

10、以及基于神经网络的编码等。这类编码技术不再局限于信息论的框架，充分利用了人类视觉以及图像信源的各种特征，实现从“波形”编码到“模型”编码的转变，获得了更高的压缩比。1.2 课题的研究背景1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底

11、向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端自顶向下构建树。1952年，David A. Huffman在麻省理工攻读博士时发表了一种构建极小多余编码的方法（A Method for the Construction of Minimum-Redundancy Codes）一文。它是是可变字长编码(VLC)的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。1.3 国内外研究状况计算机世界月刊1994年7月号所登载的动态哈夫曼编码的数据压缩方法一文给出了一种实时性较强的数据压缩方法，该方法的最大特点

12、是不需预先对原始数据进行一遍扫描以建立哈夫曼树，而改为以动态变化的哈夫曼树对数据编码。该文所附的动态哈夫曼编码数据压缩与解压源程序中的UpDate函数是动态修改哈夫曼树的关键部分，该函数对动态哈夫曼树的一种可能情况无法正确修改，针对这一点，该文附上对该函数的一个修正定义，以使该压缩与解压程序更加完善。2007 年第24 卷第11 期微电子学与计算机一书中阐述了一种基于浓缩Huffman 表的Huffman 算法的研究与实现。给出两种核心的算法：1.由规范Huffman 树构造浓缩Huffman 表设规范Huffman 树根结点所在层为第1 层, 共有n 层, 从第2 层开始记录每一层的相关信息

13、, 形成Huffman 表, 具体做法是:( 1) 第2 层, 记录最右边的非叶结点的编码b2。显然, 若b2=1, 表明第2 层没有叶结点; 若b2=0, 表明第2 层有一个叶结点且编码为1, 并令二进制串B=b2。( 2) 逐次对第i 层( i=3, 4, , n- 1) 进行相同处理, 若第i 层没有叶结点, 且I 层之前记录的编码中第1 位出现过0, 则记录一位二进制位bi=1 作为标记, 否则记录第i 层最右边非叶结点的编码bi, 并依次把bi 存放在bi- 1 的右边, 得到二进制串B=b2b3bn- 1。2.由浓缩Huffman 表得到规范Huffman 树本节介绍如何从二进制位

14、串B 得到规范Huffman树的编码25。设树的第i 层( i=2, 3, , n)上最右边非叶结点编号为Ni, 最右边的结点编号为Ri。( 1) 取B 中第一个字串b2, 因为层数为2, 所以码长为1。若b2=1, 则N2=R2=1, 该层无叶结点; 若b2=0, 则N2=0, R2=1, 由定理3 得到该层叶结点编码为N2+1=1。( 2) 对第3 层取B 中第2 个字串b3, 具体做法是: 若b2=0, 且b2 后的第一位是1, 由定理5, b3=1 表明该层没有叶结点, 否则b3 为2 位二进制串, 并由定理2 得到R3=2*N2+1。根据定理3, 由b3 逐次加一知道等于R3 为止,

15、 分别得到第3 层所有叶结点的编码。( 3) 按( 2) 中的方法逐次对第i 层( i=4, 5, , n)进行相同处理, 分别得到Ri, 并通过Ni 求得每一层的叶结点的编码。1.4 课题研究的目的和意义 举个例子，将照相机拍摄到的图像数字化之后，其数据量非常庞大。对于一般的彩色图像，以三原色(R，G，B)分别摄入，井分别以8位进行数字化，则一个像素是以24位二进制数据来描述的。如果以电视画面分辨率为640 X 480来计算，一帧画面的数据就921.6kbyte。如果按每秒30帧播放，则需要221Mbps(bit per second)的通信回路。一张CD(compact disk)大约可以

16、记录600Mbyte的信息，所以只能存放大约20秒的录像信息，并且需要221MbPs速度读出。有线电视台要具备数百个频道的数据传送能力，为了使一张CD可以记录30分钟的录像，就需要对数据进行大约1100的压缩。 对于传送黑白二值图像的传真，利用电话线，经调制解调器(modem)，将图像数据转换成编码数据进行传送。这时，因为电话线路只有14400bPs左方的传输速度，所以耍在数十秒时间内传送一页A4稿纸的内容，就必须进行数据压缩。设设备的分辨率为200bpi(bit per inch)，则A4大小的稿纸是440kbyte的数据量.如果不压缩，需要240秒的传送时间。 由此可知，图像数据在传输和存

17、储中，数据的压缩都是必不可少的，图像数据压缩是根据图像的数据冗余和视觉特性进行的。 图像压缩编码技术可以追溯到1948年提出的电视信号数字化，到今天已经有60多年的历史了。在此期间出现了很多种图像压缩编码方法，特别是到了80年代后期以后，由于小波变换理论，分形理论，人工神经网络理论，视觉仿真理论的建立，图像压缩技术得到了前所未有的发展，其中，Huffman编码是由Huffman1952年提出的一种编码方法。这种编码方法根据源数据各信号发生的概率进行编码。在源数据中出现概率越大的信号，分配的字码越短；出现概率越小的信号，其码长越长，从而达到尽可能少的码表示源数据。它在编码方法中的最佳的。1.5

18、本文主要内容 本文首先介绍了统计编码的相关内容，其次描述了图像压缩技术以及几种常见的图像压缩方式的机理，后面着详细描述了Huffman编码的基本知识，最后基于Matlab，运用Huffman编码对图像进行了压缩处理，并对处理结果作了分析。第二章 图像压缩和统计编码2.1 图像压缩2.1.1 图像压缩技术概念 所谓的图像压缩编码技术就是对要处理的图像源数据按一定的规则进行变换和组合，从而达到以尽可能少的代码（符号）来表示尽可能多的数据信息。2.1.2 图像压缩原理图像压缩是指以较少的比特有损或无损地表示原来的像素矩阵的技术,也称图像编码.图像数据之所以能被压缩，就是因为数据中存在着冗余。图像数据

19、的冗余主要表现为：图像中相邻像素间的相关性引起的空间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频谱带的相关性引起的频谱冗余。数据压缩的目的就是通过去除这些数据冗余来减少表示数据所需的比特数。由于图像数据量的庞大,在存储、传输、处理时非常困难,因此图像数据的压缩就显得非常重要。信息时代带来了“信息爆炸”，使数据量大增，因此，无论传输或存储都需要对数据进行有效的压缩。在遥感技术中，各种航天探测器采用压缩编码技术，将获取的巨大信息送回地面。数字图像的冗余主要表现在以下几种形式：A、空间冗余：规则物体和规则背景的表面物理特性都具有相关性，数字化后表现为数字冗余。例如：某图片的画

20、面中有一个规则物体,其表面颜色均匀,各部分的亮度、饱和度相近,把该图片作数字化处理,生成位图后,很大数量的相邻像素的数据是完全一样或十分接近的,完全一样的数据当然可以压缩,而十分接近的数据也可以压缩,因为恢复后人亦分辨不出它与原图有什么区别,这种压缩就是对空间冗余的压缩。B、时间冗余：序列图像(如电视图像和运动图像)和语音数据的前后有着很强的相关性,经常包含着冗余。在播出该序列图像时,时间发生了推移,但若干幅画面的同一部位没有变化,变化的只是其中某些地方,这就形成了时间冗余。C、统计冗余：空间冗余和时间冗余是把图像信号看作概率信号时所反应出的统计特性，因此，这两种冗余也被称为统计冗余。D、编码

21、冗余：同样长度的编码可以表示不同的信息。E、结构冗余：相似的，对称的结构如果都加以记录就出现结构冗余。F、知识冗余：由图像的记录方式与人对图像的知识差异而产生的冗余。人对许多图像的理解与某些基础知识有很大的相关性。许多规律性的结构，人可以由先验知识和背景知识得到。而计算机存储图像时还得把一个个像素信息存入，这就形成冗余。G、视觉冗余：视觉系统对于图像场的注意是非均匀和非线性的，视觉系统不是对图像的任何变化都能感知。2.1.3 图像压缩技术分类 图2.1.1 图像压缩技术分类从图3.3中可以看出,数据压缩技术主要分为无损数据压缩和有损数据压缩两大类,为了保证数据的完整性,对数据的压缩只能采用无损

22、数据压缩技术目前已经开发了很多商品化的数据压缩产品,国际上也制定了很多数据压缩标准(比如JPEG、MPEG等),对这些数据的压缩采用动态的数据流压缩方式。2.1.4 图像压缩目前的目标目标是在给定位速（bit-rate）或者压缩比下实现最好的图像质量。但是，还有一些其它的图像压缩机制的重要特性：可扩展编码 (en:Scalability) 通常表示操作位流和文件产生的质量下降（没有解压缩和再压缩）。可扩展编码的其它一些叫法有 渐进编码（en:progressive coding）或者嵌入式位流（en:embedded bitstreams）。尽管具有不同的特性，在无损编码中也有可扩展编码，它通

23、常是使用粗糙到精细像素扫描的格式。尤其是在下载时预览图像（如浏览器中）或者提供不同的图像质量访问时（如在数据库中）可扩展编码非常有用 有几种不同类型的可扩展性：质量渐进（en:Quality progressive）或者层渐进（en:layer progressive）：位流渐进更新重建的图像。 分辨率渐进（en:Resolution progressive）：首先在低分辨率编码图像，然后编码与高分辨率之间的差别。 成分渐进（en:Component progressive）：首先编码灰度数据，然后编码彩色数据。 感兴趣区域编码，图像某些部分的编码质量要高于其它部分，这种方法可以与可扩展编码组

24、合在一起（首先编码这些部分，然后编码其它部分）。元数据信息，压缩数据可以包含关于图像的信息用来分类、查询或者浏览图像。这些信息可以包括颜色、纹理统计信息、小预览图像以及作者和版权信息。2.1.5 图像压缩目前的标准经典的视频压缩算法已渐形成一系列的国际标准体系，如H.26x系列建议，H.320系列建议以及MPEG系列建议等。2.1.6 图像压缩效果的评估压缩方法的质量经常使用峰值信噪比来衡量，峰值信噪比用来表示图象有损压缩带来的噪声。但是，观察者的主观判断也认为是一个重要的、或许是最重要的衡量标准。下面我们就介绍一下图像压缩中的无损压缩。2.2统计编码2.1.1 统计编码的概念 高效编码的主要

25、方法是尽可能地除去信源中的成分，从而减少码率传递最大的信息量。对于有记忆信源来说，首先要去除像素间的相关性，从而达到压缩编码的效率。对于无记忆信源来说，像素间没有相关性，可以利用像素灰度值出现概率的不均等性，采用某种编码方式，从而达到压缩冗余信息的目的。这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫做统计编码。主要的统计编码包括香农-范诺(Shannon-Fano)编码、哈夫曼(Huffman)编码、算术编码(arithmetic coding)和LZW编码等。2.1.2信息量所谓信息量是指从N个相等可能事件中选出一个事件所需要的信息度量或含量,也就是在辩识N个事件中特定的一个事件的过

26、程中所需要提问是或否的最少次数. 2.1.3 信息熵 信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。信息论之父克劳德艾尔伍德香农第一次用数学语言阐明了概率与信息冗余度的关系，用来度量信息中所含的信息量：（为自信息量的均值/数学期望）其中，H为信息熵（单位为bit），S为信源，pi为符号si在S中出现的概率。最大离散熵定理：所有概率分布P（Xj）所构成的熵，以等概率时为最大。 此最大值与熵之间的差值，就是信源X所含的冗余度（redundanc

27、y）。可见：只要信源不是等概率分布，就存在着数据压缩的可能性。这就是统计编码的理论基础。此最大值与熵之间的差值，就是信源X所含的冗余度（redundancy）。可见：只要信源不是等概率分布，就存在着数据压缩的可能性。这就是统计编码的理论基础。2.1.4 熵编码的概念如果要求在编码过程中不丢失信息量，即要求保存信息熵，这种信息保持编码又叫做熵保存编码，或者叫熵编码。特性：熵编码是无失真数据压缩，用这种编码结果经解码后可无失真地恢复出原图像。2.1.5 常见的统计编码1.算术编码算术编码（ Arithmetic Coding ）跳出了分组编码的范畴，从全序列出发，采用递推形式的连续编码。它不是将单

28、个的信源符号映射成一个码字，而是将整个输入符号序列映射为实数轴上 0 ， 1 区间内的一个小区间，其长度等于该序列的概率；再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出，从而达到了高效编码的目的。不论是否二元信源，也不论数据的概率分布如何，其平均码长均能逼近信源的熵。算术编码基本原理 算术编码方法是将被编码的信息表示成实数 0 和 1 之间的一个间隔。信息越长编码表示它的间隙就越小，表示这一间隙所须二进位就越多，大概率符号出现的概率越大对应于区间愈宽，可用长度较短的码字表示；小概率符号出现概率越小层间愈窄，需要较长码字表示。算术编码实现步骤 设数据序列有两种符号组成，其概率各不相

29、同（一大一小），称概率大的为大概率符号，以 MPS(Most Probable Symbol) 表示大概率符号，其概率用 Pe 代表；称概率小的为小概率符号，用 LPS(Least Probable Symbol) 表示小概率符号，其概率用 Qe 代表；算术编码的实现相应地比Huffman编码复杂，但当与信号源符号的出现概率接近时，算术编码的效率高于Huffman编码。在图像测试中表明，算术编码效率比Huffman效率高5%左右。在算数编码中需要注意的几个问题1.由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位，32位或者64位的精度，因此这个问题可使用

30、比例缩放方法解决。2.算术编码器对整个消息只产生一个码字，这个码字实在间隔【0，1）中的一个实数因此译码器在接受到表示这个实数的所有位之前不能进行译码。3.算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。2 Huffman编码Huffman编码(Huffman Coding)是一种熵编码编码压缩方式，Huffman编码是可变字长编码(VLC)的一种。Huffman压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列

31、，而那些很少出现的符号，则用较长的位序列3 Shannon-Fano编码按照Shannon所提出的信息理论，1948年和1949年分别由Shannon和MIT的数学教授Robert Fano描述和实现了一种被称之为香农-范诺(Shannon-Fano)算法的编码方法，它是一种变码长的符号编码。 Shannon-Fano算法采用从上到下的方法进行编码：首先按照符号出现的概率排序，然后从上到下使用递归方法将符号组分成两个部分，使每一部分具有近似相同的频率，在两边分别标记0和1，最后每个符号从顶至底的0/1序列就是它的二进制编码。香农-范诺编码和哈夫曼编码都属于不对称、无损、变码长的熵编码。它们的码

32、长虽然都是可变的，但却都不需要另外附加同步代码（即在译码时分割符号的特殊代码）。如上例中，若哈夫曼编码的码串中的头两位为01，那末肯定是符号A，因为表示其他符号的代码没有一个是以01开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“000”，那么它就代表符号C。如果事先编写出一本解释各种代码意义的“词典”，即码簿（H表），那么就可以根据码簿一个码一个码地依次进行译码。采用香农-范诺编码和哈夫曼编码时有两个问题值得注意：没有错误保护功能，在译码时，如果码串中有哪怕仅仅是1位出现错误，则不但这个码本身译错，而且后面的码都会跟着错。称这种现象为错误传播(error propagatio

33、n)，计算机对这种错误也无能为力，不能知道错误出在哪里，更谈不上去纠正它。是可变长度码，因此很难在压缩文件中直接对指定音频或图像位置的内容进行译码，这就需要在存储代码之前加以考虑。与香农-范诺编码相比，哈夫曼编码方法的编码效率一般会更高一些。尽管存在上面这些问题，但哈夫曼编码还是得到了广泛应用。4 LZW编码 LZW算法是一种基于字典的编码将变长的输入符号串映射成定长的码字形成一本短语词典索引（串表），利用字符出现的频率冗余度及串模式高使用率冗余度达到压缩的目的。该算法只需一遍扫描，且具有自适应的特点（从空表开始逐步生成串表，码字长从像素位数n+1逐步增加到12），不需保存和传送串表。串表具有

34、前缀性若串wc（c为字符）在表中，则串w也在串表中（所以，可初始化串表为含所有单个字符的串）。匹配采用贪婪算法每次只识别与匹配串表中最长的已有串w（输出对应的码字）、并可与下一输入字符c拼成一个新的码字wc。对串表的改进：用w的码字来代替wc中的w，则串表中的串等长；当串表已满时（一般表长为212），可清表重来（输出清表码字）。清表码字=2n，结束码字=1+2n。所以，第一个可用的多字符串的码字=2+2n。5 RLE行程长度编码 行程编码RLE（Run Length Encoding游程长度编码）是一种使用广泛的简单熵编码。它被用于BMP、JPEG/MPEG、TIFF和PDF等编码之中，还被用

35、于传真机。RLE的编码方法RLE视数字信息为无语义的字符序列（字节流），对相邻重复的字符，用一个数字表示连续相同字符的数目（称为行程长度），可达到压缩信息的目的。如未压缩的数据：ABCCCCCCCCDEFFGGGRLE编码：AB8CDEFF3G 对比该RLE编码例前后的代码数可以发现，在编码前要用17个代码表示的数据，而编码后只要用10个代码，压缩比为1.7 : 1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于数据本身的特点。如果图像数据（如人工图形）中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之（如自

36、然照片），压缩比就越小。RLE译码采用与编码相同的规则，还原后得到的数据与压缩前的数据完全相同。因此，RLE是一种无损压缩技术。 RLE压缩编码特别适用于计算机生成的图形，对减少这类图像文件的存储空间非常有效。然而，RLE对颜色丰富多变的自然图像就显得力不从心，这时在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。但是，这并不意味着RLE编码方法在自然图像的压缩中毫无用处，恰恰相反，在各种自然图像的压缩方法中（如JPEG），仍然不可缺少RLE。只不过，不是单独使用RLE一种编

37、码方法，而是和其他压缩技术联合应用。第三章 霍夫曼编码3.1 霍夫曼编码的原理哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman 编码。以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来

38、的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman 发展起来的。哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码（最优前缀码就是平均码长最小的前缀码）。3.2 霍夫曼编码步骤：1.建立最优的二叉树过程：1）如下图所示，在每个结点上标出信源字母的概率， 图3.2.1 信源的哈夫曼编码图（2） 找出两个具有最小概率的节点，在本例中是0.01和0.04，把它们放在同一个父节点的两个字节点上。（3） 在其父结点上标出子节点的概率之

39、和，如图所示，应是0.01+0.04=0.05。进行下一轮找最小概率节点，由于这个父节点代表了原来的两个节点，因此现在只考虑7个节点。（4） 在这7个节点中还没有产生父节点，在其中找两个最小概率的，这里是0.05和0.05，把它们放在同一个父节点的两个子节点上，并在其父节点上标上子节点的概率之和0.05+0.05=0.1。（5） 继续这样的合并，每一步都将两个节点合并到一个父节点之下，对于两个概率相同的可以任意挑选一个，直到形成的父节点为1为止，此节点即为根节点。2. 编码过程分别给建成的最优二叉树中每个节点的左右分支分别标0和1，作为权值，这样，从根节点到每一个叶子节点有一条唯一的路径，读出

40、每条路径上的权值就会产生一个对应节点的唯一码字。如图2.1所示，二叉树左右分支的0、1标号并不是确定的，本例中左分支是1，右分支是0，也可以相反，如图3.2.2所示。 图3.2.2 另一种编码上面这两种Huffman编码方式的平均码长分别为：可见，尽管这两种编码设定不同，但它们都有相同的平均码长，要真正实现压缩还得对新的编码进行按位存储。3.3 霍夫曼图像压缩算法性能评价我们主要从三方面来评价Huffman的性能：（1）压缩比的大小；（2）恢复效果的好坏，也就是能否尽可能的恢复原始数据；（3）算法的简单易用性以及编、解码的速度。首先分析一下对压缩比的影响因素。对于Huffman编码来说，我们因

41、为要用额外的位保存和传输Huffman树而“浪费”掉一些存储位，也就是说，为了编、解码的方便，我们把本已减少的数据量又增加了一些。如果文件比较大的话，这一点多余的数据根本算不了什么，所占比例很小。但是，如果压缩的文件本来就很小的话，那么这笔数据就很可观了。一般来说，经典的Huffman算法的压缩比不是很高，这是无损压缩的“通病”。第二点就不用说了，由于它是无损压缩，能够完全恢复压缩之前图像的本来面貌。最后，让我们来分析一下Huffman压缩方法的速度问题。在压缩的过程中，我们进行了两次扫描，第一次是为了统计各个灰度出现的频数而扫描整幅图像，第二次则是为了分配码字而扫描整个Huffman树。这样

42、一来，对较大的文件进行编码时，频繁的磁盘读写访问必然会降低数据编码的速度，如果用于网络的话，还会因此带来一些延时，不利于实时压缩和传输。3.4霍夫曼图像压缩的缺点1.霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。2.霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。硬件实现有难度。3

43、. 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。4.压缩与还原相当费时。5. 对不同信号源的编码效率不同3.5 Huffman编码在实际情况中的处理Huffman算法目前已经得到了广泛的应用，软件和硬件都已经实现。基于Huffman经典算法的缺陷，不少人提出了一些自适应算法前面的算法中，Huffman树是整个图像全部输入扫描完成后构造出来的，而自适应算法（或称动态算法）则不必等到全部图像输入完成才开始树的构造，并且可以根据后面输入的数据动态的对Huffman树进行调整。实际上，实用的Huffman树都是经过某种优化后的动态

44、算法。3.6 霍夫曼编码的软件设计3. 6.1 对灰度分布均匀图像进行霍夫曼编码的结果及分析 实验用Matla软件，程序为附录程序（一），下图为原始图像，格式为jpg 。 图3.6.1 灰度分布均匀原始图像图3.6.2 灰度分布均匀原始图像数据图 由原始图像数据可看出，图片大小为4243字节，尺寸为128*128，灰度范围0-255整个程序运行时间为6.536秒图3.6.3 灰度分布均匀压缩图像数据图 由压缩图像数据可看出，图片大小为4131字节，尺寸为128*128，灰度范围为0-255，压缩率为0.9736，压缩率较低。3.6.4 灰度分布均匀图实验结果图 认真观察原始图像、解码后的图像以

45、及它们的大小，容易看出，两幅位图一模一样，它们尺寸的大小也一样，这是因为哈夫曼编码是一种无损压缩编码， 它不会造成信息损失， 解压缩时能够从压缩数据精确地恢复原始图像。3.6.2 对灰度分布不均匀图像进行霍夫曼编码的结果及分析 实验原图 图3.6.5 原始图像 图3.6.6 灰度分布不均匀图像原始图像数据图 由原始图像数据可看出原图大小为5526字节，尺寸为128*128，灰度范围0-255，整个程序运行时间为4.7秒 图3.6.7 灰度分布不均匀图像压缩图像数据图 由压缩图像数据可看出解码后图像大小为4947字节 尺寸为128*128 压缩比为0.89522压缩率和上实验相比较高。 图3.6

46、.8 实验结果图 比较两个实验可以发现，霍夫曼编码表现出的图像压缩和恢复效果都比较好，可以准确。对不同信号源的编码效率不同，对于灰度分布比较均匀的图压缩率较低，对灰度分布不均匀的图压缩率有所提升，但是整体看来，压缩率还是偏低。因此我们要采用改进的霍夫曼编码和一些其他图像编码方式来提高图像的压缩率。第四章 压缩编码与其他编码的比较4.1 霍夫曼编码 实验原图，程序为附录（一）图4.1.1 实验原图 图4.1.2 霍夫曼编码原始图像数据图 由原始图像数据图可看出图像大小为10586字节，尺寸为256*256，灰度范围为0-255，整个程序用时105.8975秒4.1.3 霍夫曼编码压缩图像数据图 由压缩图像数据图可看出，图像大小为9750字节，尺寸为256*256，灰度范围为0-255，压缩率为0.9210图4.1.4 霍夫曼编码实验结果图4.2 DCT（离散余弦变换）4.2.1 DCT概念