哈夫曼编码的实现及应用毕业设计.doc

哈夫曼编码的实现及应用毕业设计 目录 摘要 I Abstract II 第一章 绪论 1 1.1 研究目的及意义 1 1.2 图像压缩编码技术概述 2 1.2.1 图像压缩编码技术分类 2 1.2.2 图像压缩编码评价 2 1.3 哈夫曼编码简介 3 1.4 本设计所做的主要工作 4 第二章 利用静态哈夫曼编码实现图像压缩 5 2.1 静态哈夫曼编码介绍 5 2.2 静态哈夫曼编码树的构造 6 2.3 静态哈夫曼编码的具体编码过程 6 2.4 静态哈夫曼编码的算法实例 7 2.3 利用静态哈夫曼编码压缩与还原图像的C语言实现 9 2.3.1 压缩的实现 9 2.3.2 解压缩的实现 11 2.4 图象压缩实例 12 第三章 利用动态哈夫曼编码实现图像压缩 15 3.1 动态哈夫曼编码的提出 15 3.2 动态哈夫曼编码的原理 15 3.3 动态哈夫曼编码的算法思想 16 3.4 动态哈夫曼编码的编码实例 18 3.5 利用动态哈夫曼编码压缩与还原图像的C语言实现 25 3.5.1 数据结构 25 3.5.2 压缩的实现 26 3.5.3 解压缩的实现 27 3.6 图像压缩实例 28 3.7 静态哈夫曼编码与动态哈夫曼编码的比较 29 第四章 对哈夫曼编码的改进 31 4.1 在哈夫曼编码中引入堆排序 31 4.2 模拟哈夫曼树的创建 32 第五章 总结 34 5.1 总结 34 参考文献 35 附录 36  第一章 绪论 1.1 研究目的及意义 从信息论角度看，信源编码的一个最主要的目的，就是要解决数据的压缩问题。 数据压缩是指以最少的代码表示信源所发出的信号，减少容纳给定信息集合或数据采样集合的信号空间。图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合，从而达到以尽可能少的代码表示尽可能多的图像信息。 图像数字化之后，其数据量非常庞大，例如，一副640×480 的彩色图像（24bit/ 像素），其数据量约为921.6KB。如果以30 帧/s 的速度播放，则每秒的数据量为640×480×24×30bit=221.12Mbit，需要221 Mbit/s 的通信回路。在多媒体中，海量图像数据的存储和处理是一个难题。如不进行编码压缩处理，一张存650MB 字节的光盘仅能存放24s 左右的640 像素×480 像素的图像画面[1][5]。总之，大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计算机的处理速度增加极大的压力。仅靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的。另一方面，图像本身包含着大量的冗余成分。统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相关性。一般情况下，画面中亮度变化相对平坦的地方，相邻像素就有相同的值，而且对相邻帧的图像来说，画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变。如果能对这些冗余成分加以有效削减，就能够大大节减图像的存储空间，减少图像传输时所占信道容量，使得现有的PC 和网络在指标和性能方面能够达到处理图像信息的要求。没有压缩技术的发展，大容量图像信息的存储与传输难以适应应用的要求，多媒体通信技术也难以推广。因此，图像数据在传输和存储中，数据的压缩是必不可少的 1.2 图像压缩编码技术概述 1.2.1 图像压缩编码技术分类 图像压缩编码的方法很多，其分类视出发点不同而有差异。从图像压缩技术发展过程来看，可将图像压缩编码分为两代，第一代是指20世纪80年代以前的编码方法，它主要研究有关信息熵、编码方法以及数据压缩比等内容。第二代是指20 世纪80 年代以后的编码方法，它突破了信源编码理论，结合分形、模型基、神经网络、小波变换等数学工具，充分利用了人类视觉系统生理特性和图像信源的各种特性。但由于“第二代”编码技术增加了分析的难度，所以大大增加了实现的复杂性。从当前发展情况来看，它仍处于深入研究的阶段。 根据解压重建后的图像与原始图像之间是否有误差，图像压缩编码分为无损 （也成为无失真、无误差、信息保持、可逆压缩）编码和有损（有误差、有失真、 不可逆）编码两大类。无损压缩中去掉的仅仅是图像数据中冗余的数据，经解码重建的图像和原始图像没有任何失真，如哈夫曼编码、行程编码、算术编码；有损压缩是指解码重建的图像与原始图像相比有失真，不能精确地复原，但视觉效果基本上相同，是实现高压缩比的编码方法，如预测编码、变换编码。 1.2.2 图像压缩编码评价 图像信号在编码和传输中会产生误差，尤其是在熵压缩编码中，产生的误差应 在允许的范围内。压缩方法的优劣主要由压缩比和所恢复的图像的质量两个方面来衡量。 (1)图像熵 设数字图像像素灰度级集合为{d1,d2,……,dn}，其对应的概率分别为p(d1)， p(