图像压缩算法论文.doc

算法论文基于huffman编码的图像压缩技术姓名：康凯学院：计算机学院专业：网络工程1102学号：201126680208摘 要随着多媒体技术和通讯技术的不断发展, 多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求, 也给现有的有限带宽以严峻的考验, 特别是具有庞大数据量的数字图像通信, 更难以传输和存储, 极大地制约了图像通信的发展, 因此图像压缩技术受到了越来越多的关注。图像压缩的目的就是把原来较大的图像用尽量少的字节表示和传输,并且要求复原图像有较好的质量。利用图像压缩, 可以减轻图像存储和传输的负担, 使图像在网络上实现快速传输和实时处理。本文主要介绍数字图像处理的发展概况，图像压缩处理的原理和特点，对多种压缩编码方法进行描述和比较，详细讨论了Huffman编码的图像压缩处理的原理和应用。关键词：图像处理,图像压缩,压缩算法,图像编码,霍夫曼编码AbstractWith the developing of multimedia technology and communication technology, multimedia entertainment, information, information highway have kept on data storage and transmission put forward higher requirements, but also to the limited bandwidth available to a severe test, especially with large data amount of digital image communication, more difficult to transport and storage, greatly restricted the development of image communication, image compression techniques are therefore more and more attention. The purpose of image compression is to exhaust the original image less the larger the bytes and transmission, and requires better quality of reconstructed images. Use of image compression, image storage and transmission can reduce the burden of making the network fast image transfer and real-time processing.This paper mainly introduces the development situation of the digital image processing, the principle and feature of image compression processing , and the variety of compression coding method was described and compared, detailedly discussed the principle and application of compression processing based on HuffmanKeywords: Image Processing，Image Compression，Compression algorithm，Image Coding，Huf.fman1数字图像处理概述1.1数字图像处理发展概况 19 数字图像处理（Digital Image Processing）又称为计算机图像处理，它是指将图像信号转换成数字信号并利用计算机对其进行处理的过程。数字图像处理最早出现于20世纪50年代，当时的电子计算机已经发展到一定水平，人们开始利用计算机来处理图形和图像信息。数字图像处理作为一门学科大约形成于20世纪60年代初期。赵杰,王海松.数字图像压缩技术的现状及前景分析. 2010（3）在以后的宇航空间技术，如对火星、土星等星球的探测研究中，数字图像处理技术都发挥了巨大的作用。数字图像处理取得的另一个巨大成就是在医学上获得的成果。1972年英国EMI公司工程师Housfield发明了用于头颅诊断的X射线计算机断层摄影装置，也就是我们通常所说的CT（Computer Tomograph）。CT的基本方法是根据人的头部截面的投影，经计算机处理来重建截面图像，称为图像重建。1975年EMI公司又成功研制出全身用的CT装置，获得了人体各个部位鲜明清晰的断层图像。1979年，这项无损伤诊断技术获得了诺贝尔奖，说明它对人类作出了划时代的贡献。与此同时，图像处理技术在许多应用领域受到广泛重视并取得了重大的开拓性成就，属于这些领域的有航空航天、生物医学工程、工业检测、机器人视觉、公安司法、军事制导、文化艺术等，使图像处理成为一门引人注目、前景远大的新型学科.图像理解虽然在理论方法研究上已取得不小的进展，但它本身是一个比较难的研究领域，存在不少困难，因人类本身对自己的视觉过程还了解甚少，因此计算机视觉是一个有待人们进一步探索的新领域。1.2数字图像处理主要研究的内容数字图像处理主要研究的内容有以下几个方面：1) 图像变换由于图像阵列很大，直接在空间域中进行处理，涉及计算量很大。因此，往往采用各种图像变换的方法，如傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术，将空间域的处理转换为变换域处理，不仅可减少计算量，而且可获得更有效的处理（如傅立叶变换可在频域中进行数字滤波处理）。目前新兴研究的小波变换在时域和频域中都具有良好的局部化特性，它在图像处理中也有着广泛而有效的应用。Peter Syme.Digital Video Compresion.New York.McGraw-Hill.2004.2)图像编码压缩技术可减少描述图像的数据量（即比特数），以便节省图像传输、处理时间和减少所占用的存储器容量。压缩可以在不失真的前提下获得，也可以在允许的失真条件下进行。编码是压缩技术中最重要的方法，它在图像处理技术中是发展最早且比较成熟的技术。3)图像增强和复原的目的是为了提高图像的质量，如去除噪声，提高图像的清晰度等。图像增强不考虑图像降质的原因，突出图像中所感兴趣的部分。如强化图像高频分量，可使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。图像复原要求对图像降质的原因有一定的了解，一般讲应根据降质过程建立降质模型，再采用某种滤波方法，恢复或重建原来的图像。4)图像分割是数字图像处理中的关键技术之一。图像分割是将图像中有意义的特征部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分析和理解的基础。虽然目前已研究出不少边缘提取、区域分割的方法，但还没有一种普遍适用于各种图像的有效方法。因此，对图像分割的研究还在不断深入之中，是目前图像处理中研究的热点之一。5)图像描述是图像识别和理解的必要前提。作为最简单的二值图像可采用其几何特性描述物体的特性，一般图像的描述方法采用二维形状描述，它有边界描述和区域描述两类方法。对于特殊的纹理图像可采用二维纹理特征描述。随着图像处理研究的深入发展，已经开始进行三维物体描述的研究，提出了体积描述、表面描述、广义圆柱体描述等方法。6)图像分类（识别）属于模式识别的范畴，其主要内容是图像经过某些预处理（增强、复原、压缩）后，进行图像分割和特征提取，从而进行判决分类。图像分类常采用经典的模式识别方法，有统计模式分类和句法（结构）模式分类，近年来新发展起来的模糊模式识别和人工神经网络模式分类在图像识别中也越来越受到重视。2图像压缩2.1图像数据压缩原理由于图像数据之间存在这一定的冗余，所以使得数据的压缩成为可能。信息论的创始人Shannon 提出把数据看作是信息和冗余度（redundancy）的组合。所谓冗余度是由于一副图像的各像素之间存在着很大的相关性，可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。为了去掉数据中的冗余，常常要考虑信号源的统计特性，或建立信号源的统计模型。李昌坤.JPEG2000标准算法研究及改进D.四川大学.2005.图像的冗余包括以下几种：空间冗余：像素点之间的相关性；时间冗余：活动图像两个连续帧之间的冗余；信息熵冗余：单位信息量大于其熵；结构冗余：区域上存在非常强的纹理结构；知识冗余：有固定的结构，如人的头像；视觉冗余：某些图像的失真是人眼不易觉察的。对数字图像进行压缩通常利用两个基本原理:一是数字图像的相关性。在图像的同一行相邻象素之间，相邻象素之间，活动图像的相邻帧的对应象素之间往往存在很强的相关性，去除或减少这些相关性，也即去除或减少图像信息中的冗余度也就实现了对数字图像的压缩。帧内象素的相关称做空域相关性。相邻帧间对应象素之间的相关性称做时域相关性。二是人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。2.2霍夫曼编码Huffman编码在无损压缩的编码方法中，它是一种有效的编码方法。它是霍夫曼博士在1952 年根据可变长最佳编码定理提出的。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，它是一种无损编码方法。采用霍夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。例如：假设信源符号为【a、b、c、d、e、f、g】，其出现的概率相应的为【0.25、0.025、0.025、0.05、0.35、0.25、0.05】，一共7个字符，对其进行huffman 编码，算法如下：首先按照每个字符出现的频率大小从左到右排列：0.35、0.25、0.25、0.05、0.05、0.025、0.025；选出最小的两个值作为叶子节点构成一棵二叉树，值较大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行2），直到最后得到值为1 的根节点。得到一棵huffman 树，如下图所示： 图 2.1在得到的huffman 树上左分支标记1，右分支标记0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的0、1 字符串即为对应叶子节点所在字符的编码。a、b、c、d、e、f、g七个字符的huffman 编码分别是：10、0001、0000、0011、11、01、0010，可以看到,符号只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径。3 哈夫曼编码的图像压缩3.1 需求分析设计目标是实现Huffman压缩的编码器。编码器的工作过程呢个如下；首先读入待压缩的源文件，为保证与源文件信息完全一致，对文件的读写操作都用二进制文件的方式进行。与这只偶那个方式对应的是ASCII方式读写。然后建立并分析字母表，对读入内存的源文件我们以字节为单元进行分析，将类型表示，其用C+内建的，最多将有中可能的字符。我们对每种字符的出现频度进行统计，以频度作为建立uffman树的权值。频度表建好之后，就可以根据前述算法建立Huffman树，对出现的每种字符进行Huffman编码。此入时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件。 可以看出编码的核心是Huffman树，它也是连接编码的纽带。考虑到Huffman树节点的设计。编码时从叶节点逐步构建中间节点，到整颗树。树的节点应该应该包括的信息有：节点表示的字符，子字节的位置，字符出现的频度，父节点的位置等，这些都是构造Huffman所需要的。而解码时，我们只需要能够根据位序列从树的根节点循次遍历到叶节点，叶节点保留其表示的字符，这就足够了。3.2 设计流程图 本设计目的是为了实现图像压缩，霍夫曼算法是实现此目的关键步骤。因此本设计流程图是以霍夫曼为中心展开叙述的。流程图如图3-1所示。需求分析构建Huffman树设计 Huffman压缩类结果显示测试及分析 图3-1流程图3.3 Huffman树的构造基类设计如下：/ NIL 表示一个空子树const short NIL = -1;/ 压缩文件中Huffman树的节点对象class DiskHuffNodepublic:/ 存储的字符unsigned char ch;/ 子节点的指针（索引）short left;short right;DiskHuffNode (unsigned char c = 0, short lptr = NIL, short rptr = NIL):ch(c), left(lptr), right(rptr);/ 单个字符的最大位码大小const int MAXBITSIZE = 255;typedef bitset BitCode;/ 构建Huffman树的节点/ 压缩算法使用这些属性以及基类DiskHuffNode建立节点/ 此类中的属性在解压缩算法中并不需要class HuffNode: public DiskHuffNodepublic:int freq;/ f字符ch的出现频度int index;/ 自身节点在树中的索引int parent;/ 自身节点的父节点int numberOfBits;/ ch的Huffman编码的bit数目BitCode bits;/ 放置Huffman码的bitset容器HuffNode (unsigned char c = 0, short lptr = NIL, short rptr = NIL, int f = 0, int indx = NIL, int p = 0, int numBits = 0, int maxSizeOfBits = MAXBITSIZE):DiskHuffNode(c, lptr, rptr), freq(f), index(indx),parent(p), numberOfBits(numBits), bits(0)/ “”运算符是构建最大优先级队列和最小优先级队列必须的friend bool operator (const HuffNode& lhs, const HuffNode& rhs)return lhs.freq (const HuffNode& lhs, const HuffNode& rhs)return lhs.freq rhs.freq;3.4 图像压缩的具体实现3.4.1 压缩类的实现1.Compress()成员函数是控制文件压缩的关键模块，Huffman树的构造是算法的核心功能所在。本设计就从这两点出发考虑Huffman压缩类得实现。Compress()成员函数的定义如下：void HCompress:compress()int i;DiskHuffNode tmp;if (verbose)cout 源文件字符集频度分析中 . endl;/ 执行频度分析freqAnalysis();if (verbose)cout 构造Huffman树中 . endl;/ 构建Huffman树buildTree();if (verbose)cout 生成Huffman码中 . endl endl;/ 为每个字符生成Huffman码，并计算压缩字符中的总字符数目generateCodes();/ 如果选择verbose，此时树已生成，可以输出树数据if (verbose)treeData();if (verbose)cout 生成压缩文件中 . endl endl;/ 输出树大小dest.write(char *)&treeSize, sizeof(short);/ 输出树：注意我们只输出HuffNode对象的基类部分，/ 解压缩Huffman所需要的仅是字符和子节点指针for (i=0; i treeSize; i+)tmp = (DiskHuffNode)treei;dest.write(char *) &tmp, sizeof(DiskHuffNode);/ 对于仅含有单个字符的源文件，/ 删除由于附加叶节点所添加到总体代价的多余位if (oneChar)totalBits-;/ 输出Huffman压缩文件的比特总数目dest.write(char *)&totalBits, sizeof(unsigned long);/ 完整读入源文件，在Huffman树中查找对应每个字符的Huffman码/ 写入到dest文件中writeCompressedData();/ 关闭源文件和目的文件source.close();dest.close();filesOpen = false;它的执行过程如下：(1) 调用freeAnalysis()读取源文件，列出文件中每个字符出现的个数。当首次读到一个字符时，将叶节点计数数目numberLeaves加1。算法利用叶节点数目来分配Huffman树。另外函数也计算文件的大小，以支持下面计算压缩比的需要。（2）调用bulidTree () 为文件构造Huffman树。为了将Huffman树写入到压缩文件，如前面的需求分析中所描述那样，我们采用基于vector实现的数。这时指针是整数索引，可任意把它理解为相对地址，而不是基于链表的数结构的动 态生成的内存地址。动态的内存地址指向程序特定的一次运行中的内存，写它到文件将毫无意义。基于vector的树使用相对地址作为指针，就回避了动态内存地址的问题。（3）调用generateCode() 对于每个叶节点，顺着到根节点的路径，可以判断每个字符的bit码。在此过程中，确定树的代价，它是生成的位码的总位数。（4）完成所有数据收集Huffman树的最大节点数目为2*256-1=511。将此数值以16位整数写入到压缩文件中。（5）将Huffman树的基类以字符流的形式写入到压缩文件中。（6）将位码总数写入到压缩文件中（7）调用writeCompressData()再次读取源文件。对每个字符，将它对应的位码写入到压缩文件中。2.构造Huffman树前面部分已经设计好了树节点的集成层次类，并详述了构造Huffman树的原理，现在我们从freeAnalysis（）的分析结果出发，构造Huffman树。void HCompress:buildTree()/ 顺序遍历Huffman树节点int i, nodeIndex;/ 捕捉从优先级队列中出来的节点HuffNode x, y;/ 最小优先级队列，用于构建Huffman树priority_queueHuffNode, vector, greater pq;/ 处理文件仅有一个独特字符的特殊情形if (numberLeaves = 1)/ 设置叶节点数目为2，/ 并在索引0或1位置添加1个叶节点/ 因为在这些位置的字符不出现在文件中numberLeaves = 2;if (charFreq0 != 0)charFreq1 = 1;elsecharFreq0 = 1;/ 记录我们已经添加了填充节点oneChar = true;elseoneChar = false;/ 树的大小为2*numberLeaves-1treeSize = 2*numberLeaves - 1;tree.resize(treeSize);/ 检索我们构造中的树nodeIndex = 0;/ 开始构造各个叶节点/ value = char(i)/ left/right = NIL,/ frequency = charFreqi/ index = nodeIndex/ parent, numberOfBits, maxSizeOfBits 为默认值/ 在charLoc中记录叶节点的位置，将节点插入到最小优先级队列中for (i=0; i MAXCHARS; i+)if (charFreqi != 0)treenodeIndex = HuffNode(unsigned char)(i), NIL, NIL, charFreqi, nodeIndex);pq.push(treenodeIndex);/ 记录该叶节点的索引，用于/ writeCompressedData()函数charLoci = nodeIndex;/ 准备构造下一个节点nodeIndex+;/ 对于 numberLeaves-1 次迭代, 移除节点对,/ 生成父节点, 并将父节点插入树中for (i=1; i = numberLeaves-1; i+)/ 移除频率最低的两个节点。它们在向量树中对应节点的副本/ 位置为x.index和y.indexx = pq.top();pq.pop();y = pq.top();pq.pop();/ 生成父节点（内部节点），它的子节点/ 在数组树中的索引位置为x.index和y.index，/ 它的频度为x和y的频度和/ 这个节点的索引为nodeIndex，/ 其父节点暂时设为0treenodeIndex = HuffNode(char(0), x.index, y.index,x.freq + y.freq,nodeIndex, 0, 0, 0);/ 使用x.index和y.index，/ 将nodeIndex分配为x和y的父节点成员变量的值treex.index.parent = nodeIndex;treey.index.parent = nodeIndex;/ 将新的父节点插入到优先级队列pq.push(treenodeIndex);nodeIndex+;if (verbose)cout Huffman树的节点数目: treeSize endl endl;在算法中需要注意这样一个细节问题，即包括这样的特殊情况：树只包含有一个唯一的字符。在这种情两况下，为了满足扩展二叉树的内部节点必须有两个子节点的要求，此函数还须生成另外一 叶节点个节点作为填充的辅助节点。函数首先生成叶节点，索引范围为0number-1，每个叶节点都含有字符值，它出现的频率和节点自身的索引值，然后再生成内部节点。此步需要执行一个number-1次的循环。来自优先队列中的每个节点都包含自己在向量树中的索引值，这便利了节点关系的建立，可以将索引值赋值给父节点的左指针或右指针，也能够通过索引快速设置对应子节点的父节点属性。3生成位码 函数generateCode()从每个叶节点开始，沿着父节点路径往上直到发现根节点，就能够确定每个叶节点位码。每向上一步，如果此节点是其父节点的左子节点，就把位码相应位设为0，如果是右子节点，则设为1。这样发现的位码是逆序的，当将它赋值给叶节点的位码数据成员时，需要将位码再次逆转。4写位码 成员函数writeCompressData()参考上面已经生成的Huffman 编码方案，实现将源文件转换为压缩文件的过程。它首先以二进制方式再次读入源文件，将其诸字节解释为字符，并产生对应的压缩编码，此时压缩编码时在内存中，再将整个压缩码由内存转移到磁盘文件。其代码如下：void HCompress:writeCompressedData() / 用于容纳压缩文件Huffman码的位向量bit_vector compressedData(totalBits,false);int bitPos, i, j;unsigned char ch;/ 为源文件清除end-of-file状态标记/ 并将文件指针设为文件的开始位置source.clear();source.seekg(0, ios:beg);/ bitPos用于将bits位码放入compressedData中bitPos = 0;/ 再次读取源文件/ 并在compressedData中生成Huffman码 while (true)/ 获取下一个字符ch = source.get();if (!source)break;/ 含有ch的树节点的indexi = charLocch;/ 将treei.ch的位码放入位向量中for (j=0;j treei.numberOfBits; j+)/ 当treei.bitsj为1时，/ 对compressedData相应位置位if (treei.bits.test(j)compressedDatabitPos = true;/ 一直将bitPos向前推进bitPos+;/ 将位码由内存compressedData中写入到磁盘文件mem_to_file(compressedData,dest);men_to_file()的实现如下：void HCompress:mem_to_file(bit_vector& bv,fstream& ostr)/ 我们无法直接将二进制bit序列vector传递到文件/ 借助字符串流ostringstream将位流转换，并传递到文件中ostringstream os;/ 位向量中包含的字节单元个数，如果尾部不足整字节，/ 则补齐为整字节int bytecnt = (bv.size()+7) 3;/ bitset对象具有转换为unsigned long的方法bitset btemp;for (int i = 0; i bytecnt; i+)/ 将向量每8位转换为bitset对象/ 再进一步转换为unsigned longfor(int j=0; j8; j+)btempj= bv8*i+j;char ch=btemp.to_ulong();ostr.put(ch);/ 将二进制bit序列从内存传递到文件中4 运行结果显示及其分析4.1 结果显示：1 .对文件mspaint.exe进行压缩，结果如图4-1所示。图4-1压缩结果2 对文件demo.dat压缩：结果如图4-2所示。图4-2压缩结果3.对文件films.dat 压缩，结果如图4-3所示。图4-3压缩结果4对文件webster.dict进行压缩，结果如图4-4所示。图4-4压缩结果4.2 结果分析：我们对不同的文件类型进行压缩，测试对象除了demo.dat，还包括webster.dict以及mspaint.exe文件。Webster.dict有234，946个词，2，251，959个字符，53个不同的字符（26 个大写字母，26个小写字母，以及一个换行符）。对这个文件应用Huffman算法的压缩比为1.83.mspaint.exe是较大的二进制文件，共包含有255种不同字符，而压缩比