用哈夫曼树实现图像压缩.doc

———用哈弗曼算法实现图像压缩 姓名：黄函 学号：2011221104210146 班级：11计科3班 算法设计课程论文 1.数字图像的冗余表现为以下几种形式：空间冗余、时间冗余、视 觉 冗余、信息熵冗余、结构冗余和知识冗余。(1)空间冗余：图像内部相邻像素之间存在较强的相关性所造成的冗余。 (2)时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。(3)视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 (4)信息熵冗余：也称编码冗余，如果图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。(5)结构冗余：是指图像中存在很强的纹理结构或自相似性。(6)知识冗余：是指有些图像还包含与某些先验知识有关的信息。 2.无损压缩很常见的例子是磁盘文件的压缩。有损压缩的实例是图像和声音的压缩。 3.图像压缩的目的就是在给定位速或者压缩比下实现最好的图像质量。但是，还有一些其它的图像压缩机制的重要特性： 可扩展编码 ：又称渐进编码、嵌入式位流，通常表示操作位流和文件产生的质量下降（没有解压缩和再压缩）。尽管具有不同的特性，在无损编码中也有可扩展编码，它通常是使用粗糙到精细像素扫描的格式。尤其是在下载时预览图像（如浏览器中）或者提供不同的图像质量访问时（如在数据库中）可扩展编码非常有用，有几种不同类型的可扩展性： 质量渐进：又称层渐进，位流渐进更新重建的图像。 分辨率渐进：首先在低分辨率编码图像，然后编码与高分辨率之间的差别。 成分渐进：首先编码灰度数据，然后编码彩色数据。 感兴趣区域编码：图像某些部分的编码质量要高于其它部分，这种方法可以与可扩展编码组合在一起（首先编码这些部分，然后编码其它部分）。 元数据信息：压缩数据可以包含关于图像的信息用来分类、查询或者浏览图像。这些信息可以包括颜色、纹理统计信息、小预览图像以及作者和版权信息。 压缩方法的质量经常使用峰值信噪比来衡量，峰值信噪比用来表示图象有损压缩带来的噪声。但是，观察者的主观判断也认为是一个重要的、或许是最重要的衡量标准。 4.以哈弗曼算法为实例了解图像压缩算法　　Huffman码是一种变长码，其基本思想是：先统计图像（已经数字化）中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。我们可以用下面的框图来表示Huffman编码的过程： 在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。 Huffman树的构造可以按照下面图2的流程图来完成。首先对统计出来的概率从小到大进行排序，然后将最小的两个概率相加；到这儿的时候，先把已经加过的两个概率作为树的两个节点，并把他们从概率队列中删除；然后把相加所得的新概率加入到队列中，对这个新队列进行排序。如此反复，直到最后两个概率相加为1的时候停止。这样，Huffman树就建立起来了。 5.哈夫曼图像压缩算法性能评价 我们主要从三方面[ 2 ]来评价Huffman的性能： （1）压缩比的大小； （2）恢复效果的好坏，也就是能否尽可能的恢复原始数据； （3）算法的简单易用性以及编、解码的速度。 6.我设计的哈弗曼树达到以下要求： （1）软件设计支持灰度图像和彩色图像的压缩（2）图像文件格式为bmp或者gif（3）软件压缩率至少达到30% 7.软件源代码：代码分为5个文件，compress.h , pg.h, compress.c , pg.c , main.c compress.h /* * File: compress.h * Purpose: To compress file using the Haffman algorithm * Author: puresky * Date: 2011/05/01 */ #ifndef _FILE_COMPRESSION_H #define _FILE_COMPRESSION_H //Haffuman Tree Node typedef struct HaffumanTreeNode HTN; st