图像压缩算法论文

1算法论文基于huffman编码的图像压缩技术姓名：康凯学院：计算机学院专业：网络工程1102学号：201126680208摘要随着多媒体技术和通讯技术的不断发展,多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求,也给现有的有限带宽以严峻的考验,特别是具有庞大数据量的数字图像通信,更难以传输和存储,极大地制约了图像通信的发展,因此图像压缩技术受到了越来越多的关注。图像压缩的目的就是把原来较大的图像用尽量少的字节表示和传输,并且要求复原图像有较好的质量。利用图像压缩,可以减轻图像存储和传输的负担,使图像在网络上实现快速传输和实时处理。本文主要介绍数字图像处理的发展概况，图像压缩处理的原理和特点，对多种压缩编码方法进行描述和比较，详细讨论了Huffman编码的图像压缩处理的原理和应用。关键词：图像处理,图像压缩,压缩算法,图像编码,霍夫曼编码AbstractWiththedevelopingofmultimediatechnologyandcommunicationtechnology,multimediaentertainment,information,informationhighwayhavekeptondatastorageandtransmissionputforwardhigherrequirements,butalsotothelimitedbandwidthavailabletoaseveretest,especiallywithlargedataamountofdigitalimagecommunication,moredifficulttotransportandstorage,greatlyrestrictedthedevelopmentofimagecommunication,imagecompressiontechniquesarethereforemoreandmoreattention.Thepurposeofimagecompressionistoexhausttheoriginalimagelessthelargerthebytesandtransmission,andrequiresbetterqualityof2reconstructedimages.Useofimagecompression,imagestorageandtransmissioncanreducetheburdenofmakingthenetworkfastimagetransferandreal-timeprocessing.Thispapermainlyintroducesthedevelopmentsituationofthedigitalimageprocessing,theprincipleandfeatureofimagecompressionprocessing,andthevarietyofcompressioncodingmethodwasdescribedandcompared,detailedlydiscussedtheprincipleandapplicationofcompressionprocessingbasedonHuffmanKeywords:ImageProcessing，ImageCompression，Compressionalgorithm，ImageCoding，Huf.fman1．数字图像处理概述1.1数字图像处理发展概况数字图像处理（DigitalImageProcessing）又称为计算机图像处理，它是指将图像信号转换成数字信号并利用计算机对其进行处理的过程。数字图像处理最早出现于20世纪50年代，当时的电子计算机已经发展到一定水平，人们开始利用计算机来处理图形和图像信息。数字图像处理作为一门学科大约形成于20世纪60年代初期。1在以后的宇航空间技术，如对火星、土星等星球的探测研究中，数字图像处理技术都发挥了巨大的作用。数字图像处理取得的另一个巨大成就是在医学上获得的成果。1972年英国EMI公司工程师Housfield发明了用于头颅诊断的X射线计算机断层摄影装置，也就是我们通常所说的CT（ComputerTomograph）。CT的基本方法是根据人的头部截面的投影，经计算机处理来重建截面图像，称为图像重建。1975年EMI公司又成功研制出全身用的CT装置，获得了人体各个部位鲜明清晰的断层图像。1979年，这项无损伤诊断技术获得了诺贝尔奖，说明它对人类作出了划时代的贡献。与此同时，图像处理技术在许多应用领域受到广泛重视并取得了重大的开拓性成就，属于这些领域的有航空航天、生物医学工程、工业检测、机器人视觉、公安司法、军事制导、文化艺术等，使图像处理成为一门引人注目、前景远大的新型学科.图像理解虽然在理论方法研究上已取得不小的进展，但它本身是一个比较难的研究领域，存在不少困难，因人类本身对自己的视觉过程还了解甚少，因此计算机视觉是一个有待人们进一步探索的新领域。1.2数字图像处理主要研究的内容3数字图像处理主要研究的内容有以下几个方面：1)图像变换由于图像阵列很大，直接在空间域中进行处理，涉及计算量很大。因此，往往采用各种图像变换的方法，如傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术，将空间域的处理转换为变换域处理，不仅可减少计算量，而且可获得更有效的处理（如傅立叶变换可在频域中进行数字滤波处理）。目前新兴研究的小波变换在时域和频域中都具有良好的局部化特性，它在图像处理中也有着广泛而有效的应用。22)图像编码压缩技术可减少描述图像的数据量（即比特数），以便节省图像传输、处理时间和减少所占用的存储器容量。压缩可以在不失真的前提下获得，也可以在允许的失真条件下进行。编码是压缩技术中最重要的方法，它在图像处理技术中是发展最早且比较成熟的技术。3)图像增强和复原的目的是为了提高图像的质量，如去除噪声，提高图像的清晰度等。图像增强不考虑图像降质的原因，突出图像中所感兴趣的部分。如强化图像高频分量，可使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。图像复原要求对图像降质的原因有一定的了解，一般讲应根据降质过程建立降质模型，再采用某种滤波方法，恢复或重建原来的图像。4)图像分割是数字图像处理中的关键技术之一。图像分割是将图像中有意义的特征部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分析和理解的基础。虽然目前已研究出不少边缘提取、区域分割的方法，但还没有一种普遍适用于各种图像的有效方法。因此，对图像分割的研究还在不断深入之中，是目前图像处理中研究的热点之一。5)图像描述是图像识别和理解的必要前提。作为最简单的二值图像可采用其几何特性描述物体的特性，一般图像的描述方法采用二维形状描述，它有边界描述和区域描述两类方法。对于特殊的纹理图像可采用二维纹理特征描述。随着图像处理研究的深入发展，已经开始进行三维物体描述的研究，提出了体积描述、表面描述、广义圆柱体描述等方法。6)图像分类（识别）属于模式识别的范畴，其主要内容是图像经过某些预处理（增强、复原、压缩）后，进行图像分割和特征提取，从而进行判决分类。图像分类常采用经典的模式识别方法，有统计模式分类和句法（结构）模式分类，近年来新发展起来的模糊模式识别和人工神经网络模式分类在图像识别中也越来越受到重视。2．图像压缩2.1图像数据压缩原理4由于图像数据之间存在这一定的冗余，所以使得数据的压缩成为可能。信息论的创始人Shannon提出把数据看作是信息和冗余度（redundancy）的组合。所谓冗余度是由于一副图像的各像素之间存在着很大的相关性，可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。为了去掉数据中的冗余，常常要考虑信号源的统计特性，或建立信号源的统计模型。3图像的冗余包括以下几种：●空间冗余：像素点之间的相关性；●时间冗余：活动图像两个连续帧之间的冗余；●信息熵冗余：单位信息量大于其熵；●结构冗余：区域上存在非常强的纹理结构；●知识冗余：有固定的结构，如人的头像；●视觉冗余：某些图像的失真是人眼不易觉察的。对数字图像进行压缩通常利用两个基本原理:一是数字图像的相关性。在图像的同一行相邻象素之间，相邻象素之间，活动图像的相邻帧的对应象素之间往往存在很强的相关性，去除或减少这些相关性，也即去除或减少图像信息中的冗余度也就实现了对数字图像的压缩。帧内象素的相关称做空域相关性。相邻帧间对应象素之间的相关性称做时域相关性。二是人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。2.2霍夫曼编码Huffman编码在无损压缩的编码方法中，它是一种有效的编码方法。它是霍夫曼博士在1952年根据可变长最佳编码定理提出的。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，它是一种无损编码方法。采用霍夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使5用了一般编码的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、601、0010，可以看到,符号只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径。3哈夫曼编码的图像压缩3.1需求分析设计目标是实现Huffman压缩的编码器。编码器的工作过程呢个如下；首先读入待压缩的源文件，为保证与源文件信息完全一致，对文件的读写操作都用二进制文件的方式进行。与这只偶那个方式对应的是ASCII方式读写。然后建立并分析字母表，对读入内存的源文件我们以字节为单元进行分析，将类型表示，其用C++内建的ＣＨＡＲ，最多将有２５６中可能的字符。我们对每种字符的出现频度进行统计，以频度作为建立Ｈuffman树的权值。频度表建好之后，就可以根据前述算法建立Huffman树，对出现的每种字符进行Huffman编码。此入时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件。可以看出编码的核心是Huffman树，它也是连接编码的纽带。考虑到Huffman树节点的设计。编码时从叶节点逐步构建中间节点，到整颗树。树的节点应该应该包括的信息有：节点表示的字符，子字节的位置，字符出现的频度，父节点的位置等，这些都是构造Huffman所需要的。而