1、南京林业大学本科毕业设计（论文）题 目： 霍夫曼编码及其效率的研究 学 院： 南方学院 专 业： 电子信息工程 学 号： N080802124 学生姓名： 徐佳迪 指导教师： 胡洁 职 称： 讲师 二 O 一二 年 五 月 二十 日摘要Huffman 编码是一种无损编码，广泛用于数据文件压缩的十分有效的编码方法，其在电子计算机、电视、遥控和通讯等方面广泛使用。其压缩通常在 20%90%之间。哈夫曼编码算法是利用字符在文件中出现的频率表来建立一个用 0，1 串表示各字符的最优表示方式。本文主要研究 Huffman 编码在图像压缩方面的应用，介绍了 Huffman 编码的原理和步骤。通过实践运用
2、Matlab 工具验证 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%.H
3、uffman encoding algorithm be used is based on character frequency table in the document to create a 0,1 string to get that thean 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
4、have been introduce the principles and steps of the Huffman coding, And I used Matlab has been utilized to realize the Huffman coding. through practice to verificationFrom the results, it can been concluded that Huffman coding can achieve good compression in image compression and image restoration.
5、.Huffman coding can improve the effectiveness and quality of image transmission, has good application prospects and expansibility.Key word：Huffman coding lossless compression Matlab目录第一章 绪论 .61.1 图像压缩编码的现状和发展趋势 .61.2 课题的研究背景 .71.3 国内外研究状况 .71.4 课题研究的目的和意义 .81.5 本文主要内容 .9第二章 图像压缩和统计编码 .102.1 图像压缩 .10
6、2.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.1.4 熵编码的概念 .132.1.5 常见的统计编码 .14第三章 霍夫曼编码 .173.1 霍夫曼编码的原理 .173.2 霍夫曼编码步骤： .173.3 霍夫曼图像压缩算法性能评价 .183.4 霍夫曼图像压缩的缺点 .193.5 Huffman 编码在实际情况中的处理 .193.6 霍
7、夫曼编码的软件设计 .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 程序运行结果 .294.2 小波变换编码 .324.2.1 小波变换概念 .324.2.2 小波变换原理 .324.2.3 小波变换的步骤 .324.2.4 序运行结果 .324.3 三种图像编码的比较 .34第五章
8、 总结 .35致谢 .36参考文献 .37第一章 绪论1.1 图像压缩编码的现状和发展趋势1948 年提出电视数字化后，就开始对图像压缩编码技术的研究工作，至今已有 50 多年的历史。图像压缩的基本理论起源于 20 世纪 40 年代末香农的信息理论。香农的编码定理告诉我们，在不产生任何失真的前提下，通过合理的编码，对于每一个信源符号分配不等长的码字，平均码长可以任意接近于信源的熵。在五十年代和六十年代，图像压缩技术由于受到电路技术等的制约，仅仅停留在预测编码、亚采样以及内插复原等技术的研究，还很不成熟。1969 年在美国召开的第一届“图像编码会议” 标志着图像编码作为一门独立的学科诞生了。到了
9、 70 年代和 80 年代，图像压缩技术的主要成果体现在变换编码技术上，矢量量化编码技术也有较大发展，有关于图像编码技术的科技成果和科技论文与日俱增，图像编码技术开始走向繁荣。自 80 年代后期以后，由于小波变换理论，分形理论，人工神经网络理论，视觉仿真理论的建立，人们开始突破传统的信源编码理论，例如不再假设图像是平稳的随机场。图像压缩编码向着更高的压缩比和更好的压缩质量的道路前进，进入了一个崭新的、欣欣向荣的大发展时期。如今图像压缩编码技术广泛地被应用在各个领域。如：电视计算机、多媒体出版物、遥感图像数据库等。它已经为开创新的应用领域提供了良好的技术基础。到目前为止，图像压缩编码技术已经发展
10、到第二代编码技术。1、第一代编码技术包括建立在 shannon 的码率失真理论基础上的预测编码、变换编码、统计编码及 Oliver 提出的 PCM 编码理论。虽然这些编码技术在中等压缩率的情况下，能提供非常好的图像质量，但在码率非常低得情况下，无法提供令人满意的质量。究其原因是由于这些技术没有利用图像的结构特点，同时也没有考虑人类视觉系统的特性，因此它们也就只能以像素或块作为编码的对象。2、第二代编码包括基于分形的编码、基于模型的编码、基于区域分割的编码，以及基于神经网络的编码等。这类编码技术不再局限于信息论的框架，充分利用了人类视觉以及图像信源的各种特征，实现从“波形” 编码到“模型”编码的
11、转变，获得了更高的压缩比。1.2 课题的研究背景1951 年 ， 哈 夫 曼 和 他 在 MIT 信 息 论 的 同 学 需 要 选 择 是 完 成 学 期 报 告 还 是 期 末 考试 。 导 师 Robert M. Fano 给 他 们 的 学 期 报 告 的 题 目 是 ， 寻 找 最 有 效 的 二 进 制 编 码 。 由于 无 法 证 明 哪 个 已 有 编 码 是 最 有 效 的 ， 哈 夫 曼 放 弃 对 已 有 编 码 的 研 究 ， 转 向 新 的 探 索 ，最 终 发 现 了 基 于 有 序 频 率 二 叉 树 编 码 的 想 法 ， 并 很 快 证 明 了 这 个 方 法
12、 是 最 有 效 的 。 由于 这 个 算 法 ， 学 生 终 于 青 出 于 蓝 ， 超 过 了 他 那 曾 经 和 信 息 论 创 立 者 香 农 共 同 研 究 过类 似 编 码 的 导 师 。 哈 夫 曼 使 用 自 底 向 上 的 方 法 构 建 二 叉 树 ， 避 免 了 次 优 算 法Shannon-Fano 编 码 的 最 大 弊 端 自 顶 向 下 构 建 树 。1952 年， David A. Huffman 在麻省理工攻读博士时发表了一种构建极小多余编码的方法 （A Method for the Construction of Minimum-Redundancy Cod
13、es）一文。它是是可变字长编码(VLC) 的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作 Huffman 编码。1.3 国内外研究状况 计 算 机 世 界 月 刊 1994 年 7 月 号 所 登 载 的 动 态 哈 夫 曼 编 码 的 数 据 压 缩 方 法 一 文 给 出 了 一 种 实 时 性 较 强 的 数 据 压 缩 方 法 ， 该 方 法 的 最 大 特 点 是 不 需 预 先 对 原 始 数据 进 行 一 遍 扫 描 以 建 立 哈 夫 曼 树 ， 而 改 为 以 动 态 变 化 的 哈 夫 曼 树 对 数 据 编 码 。 该
14、文 所附 的 动 态 哈 夫 曼 编 码 数 据 压 缩 与 解 压 源 程 序 中 的 UpDate 函 数 是 动 态 修 改 哈 夫 曼 树 的关 键 部 分 ， 该 函 数 对 动 态 哈 夫 曼 树 的 一 种 可 能 情 况 无 法 正 确 修 改 ， 针 对 这 一 点 ， 该 文附 上 对 该 函 数 的 一 个 修 正 定 义 ， 以 使 该 压 缩 与 解 压 程 序 更 加 完 善 。2007 年第24 卷第11 期微电子学与计算机一书中阐述了一种基于浓缩Huffman 表的Huffman 算法的研究与实现。给出两种核心的算法：1.由规范Huffman 树构造浓缩Huff
15、man 表设规范Huffman 树根结点所在层为第1 层, 共有n 层, 从第2 层开始记录每一层的相关信息, 形成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 的右边
16、, 得到二进制串B=b2b3 bn- 1。2.由浓缩Huffman 表得到规范Huffman 树本节介绍如何从二进制位串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 表明该层没有
17、叶结点, 否则b3 为2 位二进制串, 并由定理2 得到R3=2*N2+1。根据定理3, 由b3 逐次加一知道等于R3 为止, 分别得到第3 层所有叶结点的编码。( 3) 按( 2) 中的方法逐次对第i 层( i=4, 5, , n)进行相同处理 , 分别得到Ri, 并通过Ni 求得每一层的叶结点的编码。1.4 课题研究的目的和意义举个例子，将照相机拍摄到的图像数字化之后，其数据量非常庞大。对于一般的彩色图像，以三原色(R，G，B)分别摄入，井分别以 8 位进行数字化，则一个像素是以 24位二进制数据来描述的。如果以电视画面分辨率为 640 X 480 来计算，一帧画面的数据就921.6kby
18、te。如果按每秒 30 帧播放，则需要 221Mbps(bit per second)的通信回路。一张CD(compact disk)大约可以记录 600Mbyte 的信息，所以只能存放大约 20 秒的录像信息，并且需要 221MbPs 速度读出。有线电视台要具备数百个频道的数据传送能力，为了使一张 CD 可以记录 30 分钟的录像，就需要对数据进行大约 1100 的压缩。对于传送黑白二值图像的传真，利用电话线，经调制解调器(modem)，将图像数据转换成编码数据进行传送。这时，因为电话线路只有 14400bPs 左方的传输速度，所以耍在数十秒时间内传送一页 A4 稿纸的内容，就必须进行数据压
19、缩。设设备的分辨率为200bpi(bit per inch)，则 A4 大小的稿纸是 440kbyte 的数据量.如果不压缩，需要 240 秒的传送时间。由此可知，图像数据在传输和存储中，数据的压缩都是必不可少的，图像数据压缩是根据图像的数据冗余和视觉特性进行的。图像压缩编码技术可以追溯到 1948 年提出的电视信号数字化，到今天已经有 60 多年的历史了。在此期间出现了很多种图像压缩编码方法，特别是到了 80 年代后期以后，由于小波变换理论，分形理论，人工神经网络理论，视觉仿真理论的建立，图像压缩技术得到了前所未有的发展，其中，Huffman 编码是由 Huffman1952 年提出的一种编
20、码方法。这种编码方法根据源数据各信号发生的概率进行编码。在源数据中出现概率越大的信号，分配的字码越短；出现概率越小的信号，其码长越长，从而达到尽可能少的码表示源数据。它在编码方法中的最佳的。1.5 本文主要内容本文首先介绍了统计编码的相关内容，其次描述了图像压缩技术以及几种常见的图像压缩方式的机理，后面着详细描述了 Huffman 编码的基本知识，最后基于 Matlab，运用 Huffman 编码对图像进行了压缩处理，并对处理结果作了分析。第 2 章 图像压缩和统计编码2.1 图像压缩2.1.1 图像压缩技术概念所谓的图像压缩编码技术就是对要处理的图像源数据按一定的规则进行变换和组合，从而达到
21、以尽可能少的代码（符号）来表示尽可能多的数据信息。2.1.2 图像压缩原理图像压缩是指以较少的比特有损或无损地表示原来的像素矩阵的技术,也称图像编码.图像数据之所以能被压缩，就是因为数据中存在着冗余。图像数据的冗余主要表现为：图像中相邻像素间的相关性引起的空间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频谱带的相关性引起的频谱冗余。数据压缩的目的就是通过去除这些数据冗余来减少表示数据所需的比特数。由于图像数据量的庞大,在存储、传输、处理时非常困难,因此图像数据的压缩就显得非常重要。信息时代带来了“ 信息爆炸 ”，使数据量大增，因此，无论传输或存储都需要对数据进行有效的压缩
22、。在遥感技术中，各种航天探测器采用压缩编码技术，将获取的巨大信息送回地面。数字图像的冗余主要表现在以下几种形式：A、空间冗余：规则物体和规则背景的表面物理特性都具有相关性，数字化后表现为数字冗余。例如：某图片的画面中有一个规则物体,其表面颜色均匀,各部分的亮度、饱和度相近,把该图片作数字化处理,生成位图后,很大数量的相邻像素的数据是完全一样或十分接近的,完全一样的数据当然可以压缩,而十分接近的数据也可以压缩,因为恢复后人亦分辨不出它与原图有什么区别,这种压缩就是对空间冗余的压缩。B、时间冗余：序列图像(如电视图像和运动图像)和语音数据的前后有着很强的相关性,经常包含着冗余。在播出该序列图像时,
23、时间发生了推移,但若干幅画面的同一部位没有变化,变化的只是其中某些地方,这就形成了时间冗余。C、统计冗余：空间冗余和时间冗余是把图像信号看作概率信号时所反应出的统计特性，因此，这两种冗余也被称为统计冗余。D、编码冗余：同样长度的编码可以表示不同的信息。E、结构冗余：相似的，对称的结构如果都加以记录就出现结构冗余。F、知识冗余：由图像的记录方式与人对图像的知识差异而产生的冗余。人对许多图像的理解与某些基础知识有很大的相关性。许多规律性的结构，人可以由先验知识和背景知识得到。而计算机存储图像时还得把一个个像素信息存入，这就形成冗余。G、视觉冗余：视觉系统对于图像场的注意是非均匀和非线性的，视觉系统
24、不是对图像的任何变化都能感知。2.1.3 图像压缩技术分类图 2.1.1 图像压缩技术分类从图3.3中可以看出,数据压缩技术主要分为无损数据压缩和有损数据压缩两大类,为了保证数据的完整性,对数据的压缩只能采用无损数据压缩技术目前已经开发了很多商品化的数据压缩产品,国际上也制定了很多数据压缩标准(比如JPEG、MPEG等),对这些数据的压缩采用动态的数据流压缩方式。2.1.4 图像压缩目前的目标目标是在给定位速（bit-rate）或者压缩比下实现最好的图像质量。但是，还有一些其它的图像压缩机制的重要特性：可扩展编码 (en:Scalability) 通常表示操作位流和文件产生的质量下降（没有解压缩和再压缩）。可扩展编码的其它一些叫法有 渐进编码（en:progressive coding）或者嵌入式位流（en:embedded bitstreams）。尽管具有不同的特性，在无损编码中也有可扩展编码，
