（计算机应用技术专业论文）基于提升小波的分形图像压缩算法研究.pdf

基于提升小波的分形图像压缩算法研究中文摘要 基于提升小波的分形图像压缩算法研究 中文摘要 随着信息网络化的快速发展，多媒体技术的应用日益广泛，数字图像的存储与传 输在这之中占有重要的位置。然而图像的数据量非常庞大，必须经过有效的压缩，才 能满足实际应用的要求，因而探索高效的图像压缩算法无疑成为当前通信和信号处理 领域里的一个重要研究课题。 分形图像编码是近十几年发展起来的一种新型图像压缩算法，它注重发掘存在于 大多数图像中的自相似性，可以达到其他图像压缩算法无法比拟的高压缩比，因此受 到了研究人员的广泛重视。但分形图像压缩算法在理论及应用上存在许多问题，如编 码时的巨大计算量、解码迭代的收敛性、重构图像的块状效应等。本文在相关文献的 研究基础上，通过引入提升小波变换，结合小波编码与分形编码各自的优点，对两者 结合方法进行了研究，主要工作有以下几方面： 1 提出了一种基于环形结构邻域搜索的分形图像压缩算法。与传统分形图像压缩 算法相比，该算法能够在更短时间找到符合给定误差的定义域块，从而大大提高了编 码速度。 2 对于人眼视觉系统来说，小波变换所分解的各个子带图像重要性是不一样的， 频率越低重要性越高，频率越高则重要性越低。结合这一视觉特性，本文设计了一种 基于提升格式小波的图像压缩算法，采用视觉加权的标量量化技术，该算法加快了编 码的时间，同时重构图像质量也有所提高。 3 结合分形编码与小波编码的各自优点，提出了一种基于提升小波变换的快速分 形图像压缩算法。该算法对不同的分解子图像分别采用s p i h t 算法和本文改进分形 图像压缩算法，实验结果表明，该方法大幅度节约了编码时间，避免了传统分形编码 所固有的方块效应，获得了较高的解码图像质量。 关键词：图像压缩；提升小波；分形编码；环形邻域 作者：余平 指导老师：马小虎 a b s t r a e tr e s e a r c ho nf r a c t a li m a g ec o m p r e s s i o na l g o r i t h mb a s e do nl i f t i n gw a v e l e tt r a n s f o r m r e s e a r c ho nf r a c t a li m a g ec o m p r e s s i o n a l g o r i t h m b a s e do nl i f t i n g”匀v e l e tt r a n s f o r m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nn e t w o r k i n gi nr e c e n ty e a r s ，t h em u l t i m e d i a t e c h n o l o g i e sa p p l i c a t i o n sp l a y sav e r yi m p o r t a n tr o l ei np e o p l e sl i f e t h et r a n s m i s s i o na n d s t o r a g eo ft h ed i g i t a li m a g ep l a y sa l li m p o r t a n tp a r ti ni t o w i n gt od i g i t a li m a g e sd a t ai s v e r yl a r g e ，s oi t c a n n o ts a t i s f yt h er e q u e s to ft h ep r a c t i c a la p p l i c a t i o nb e f o r ee f f e c t i v e c o m p r e s s i o n o nt h i so c c a s i o n ，i ti n e v i t a b l yb e c o m e so n eo ft h em o s ti m p o r t a n td i r e c t i o n s i n t h ef i e l do fc o m m u n i c a t i o na n ds i g n a lp r o c e s s i n gt os e e ka f t e rt h ee f f e c t i v ei m a g e c o d i n ga l g o r i t h m f r a c t a li m a g ec o m p r e s s i o n ( f i c ) t a k e sa d v a n t a g eo fs e l f - s i n i l a r i t i e sw h i c he x i s ti nt h e i m a g e sc o m m o n l y i tu s e st h es e l f - s i m i l a r i t yi nd i f f e r e n ts c a l e so fi m a g et o f i n dt h e c o r r e s p o n d i n gf r a c t a ld e s c r i p t i o na n dr e m o v et h eg e o m e t r yr e d u n d a n c e f i ci so n e o ft h e m o s tc o m p e t i t i v es c h e m e si nr e c e n tr e s e a r c h ，a n di th a st h ec a p a b l eo fa c h i e v i n gg o o d i m a g eq u a l i t ya tav e r yh i g hc o m p r e s s i o nr a t i o t h em a i nd r a w b a c k so ff i ca r et h e e x p e n s i v ec o m p u t a t i o n a lc o s ti nt h ee n c o d i n gp r o c e s s ，t h ec o n v e r g e n c ei nd e c o d i n g p r o c e s s ，t h eb l o c k e f f e c ti nd e c o d i n gi m a g e ，e t c i nt h i st h e s i s ，w ec o m b i n e f i c a n dl i f t i n g w a v e l e tt r a n s f o r m ，w ec a l lg e tm u c hh i g h e rc o m p r e s s i o nr a t ea n ds h o r te n c o d i n gt i m e t h e m 匈o rj o b sa r ed e s c r i b e da sf o l l o w s ： ( 1 ) a ni m p r o v e df r a c t a li m a g ec o m p r e s s i o na l g o r i t h mb a s e do na n n u l a rn e i g h b o u r - s e a r c h i n gi sp r o p o s e d c o m p a r e dw i t ht h et r a d i t i o n a lf i ca l g o r i t h m ，t h ea l g o r i t h mc a nf i n d t h eb e s td o m a i nb l o c kt h a tc o n f o r m st oa s s i g n e de r r o ri nt h es h o r t e s tt i m e ，a n dd e c r e a s et h e e n c d i n gt i m es i g n i f i c a n t l y ( 2 ) t h ei m p o r t a n c eo fe a c hs u b i m a g ea f t e rw a v e l e td e c o m p o s i t i o ni si n e q u a b l i t yi n h u m a nv i s u a ls y s t e m ，t h el o w e rf r e q u e n c yh a sh i g h e ri m p o r t a n c e ，a n dt h eh i g h e rf r e q u e n c y h a sl o w e ri m p o r t a n c e b a s e do nt h i s ，c o m b i n e d 谢t ht h ev i s i b i l i t yp r e a c c e n t u a t i o nb e f o r e t h eq u a n t i z a t i o n ，a ni m a g ec o m p r e s s i o na l g o r i t h mb a s e do nl i f t i n gw a v e l e tt r a n s f o r mi s l l r e s e a r c ho nf r a c t a li m a g ec o m p r e s s i o na l g o r i t h mb a s e do nl i f t i n gw a v e l e tt r a n s f o r m a b s t r a c t d e s i g n e d t h i sa l g o r i t h md e c r e a s e st h ee d c o d i n gt i m e ，a n di m p r o v e st h eq u a l i t yo f d e c o d i n g i m a g e ( 3 ) af a s tf r a c t a li m a g ec o m p r e s s i o na l g o r i t h mb a s e do nt h el i f t i n gw a v e l e tt r a n s f o r m i sp r o p o s e d i tc o m b i n e dt h eg o o dp o i n t sf r o mw a v e l e te n c o d i n ga n df r a c t a le n c o d i n g t h e a l g o r i t h mu s e st h el i f t i n gs c h e m eo fd a u b e c h i e s 9 7 ，a n dc o d e st h ec o e f f i c i e n tb ys p i h to r i m p r o v e d - f r a c t a le n c o d i n gf o rt h ed i f f e r e n ti m a g e s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e p r o p o s e dm e t h o dc a nr e d u c et h ee n c o d i n gt i m e ，a v o i dt h eb l o c k i n ge f f e c t s ，a n dg e tab e t t e r d e c o d i n gi m a g e f i n a l l y , t h er e s e a r c hw o r ki n v o l v e di nt h et h e s i si ss u m m a r i z e d ，a n dt h ef u t u r e d e v e l o p m e n t si nf r a c t a li m a g ec o m p r e s s i o na r ef o r e c a s t k e yw o r d s ：i m a g ec o m p r e s s i o n ；l i f t i n gw a v e l e tt r a n s f o r m ；f r a c t a lc o d i n g ； a n n u l a rn e i g h b o r h o o d i i i w r i t t e nb yy up i n g s u p e r v i s e db ym a x i a o h u 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 日 期： 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名： 灶日 牮日期：掣 基于提升小波的分形图像压缩算法研究第一章绪论 1 1 研究背景 第一章绪论 进入了2 1 世纪以来，网络通信技术、计算机信息处理技术的飞速发展，人类社 会正逐步迈入信息化时代。研究发现，在人们所接受的信息中有7 5 是通过视觉得到 的，这就使图像通信这一技术领域进入了一个革命性的发展时期【l 】。目前人们所得到 的图像主要来源于自然景物，大多通过某些数字产品例如数码相机、数字摄像机等设 备，我们能够将自然景物连续变化的模拟量进行数字量化，从而得到以文件形式存在 的图像数据。图像以数字形式处理和传输，具有质量好、成本低和可靠性高的特点， 因而很适合于网络的传输，但是数字图像的数据量非常巨大，如果不经过压缩，它将 成为数字图像传输和存储的巨大瓶颈，这也是图像压缩编码的原动力。图像信息的处 理、存储和传输在社会生活中的作用已经越来越突出。在很多工程研究中，图像压缩 技术的应用已经相当广泛，如视频传输等，为了节省图像存储量，有效利用传输信道 以及缩短图像处理的时间，就需要对图像数据进行压缩处理。 图像压缩编码技术最早始于2 0 世纪4 0 年代末，自1 9 4 8 年提出的电视信号数字 化，就同时开始了对图像压缩编码的研究工作，至今已有将近6 0 年的历史，相继提 出了诸如d p c m 、d c t 、v q 等压缩算法【2 】，但图像压缩编码技术真正走向实用化、 产业化并得到飞速发展则是最近1 0 年的事，并已经出台了基于d c t 等技术的国际压 缩标准，如j p e g 、m p e g 等均得到了较为广泛的实际应用。2 0 世纪五六十年代的图 像压缩编码技术由于受到电路技术的制约，仅仅停留在预测编码、亚采样以及内插复 原等技术的研究，还很不成熟。1 9 6 9 年在美国召开的第一界“图像编码会议”标志 着图像编码作为一门独立学科的诞生。到了七八十年代，图像压缩技术的主要成果体 现在变换编码技术上，矢量量化编码技术也有较大的发展。8 0 年代末，小波变换理 论、分形理论、人工神经网络理论、视觉仿真理论的建立，人们开始突破传统的信源 编码理论，图像压缩编码向着更高的压缩率和更好的压缩质量的方向发展，进入了一 个崭新的发展时期。 第一章绪论基于提升小波的分形图像压缩算法研究 1 2 研究意义 信息社会充斥着大量的信息，图像作为信息含量最为丰富的信息载体，是构成一 个信息环境所必不可少的要素。它在现代通信技术中所承担的作用已经远远超过其它 载体，这与其在现实生活中所扮演的角色是息息相关的。数字图像作为现代信息社会 的一个重要媒介，在通信、生物学、环境、气象、农林、工业、交通、军事和法律等 各个领域中都发挥越来越大的作用。尤其在当今，计算机技术、通信技术以及其他现 代科学技术的发展，c t 、m r i 、可视电话、低码率视频会议、远程多媒体协同工作、 无线视频、电子商务等成为社会关注的热点，可以说，数字图像对于人们的生产、生 活、经济活动和科学技术研究越来越重要。然而数字化后的图像、音频、视频等媒体 信息具有数据海量性，给信息传输、存储和处理带来了困难，与当前硬件技术所能提 供的计算机存储资源和网络带宽之间有很大差距。 从存储图像的角度来看，图像数据的信息量是非常庞大的，计算机中的数字图像 的灰度级数一般用8 b i t 来量化，而医学图像处理和其他科研应用的图像的灰度量化可 能用到1 2 b i t 以上。例如一幅陆地卫星摄取的图片，其数据量可达2 3 0 0 g b i t ，这无疑 对图像的存储和处理带来巨大的困难。如果在量化的时候，将量化比特数减少，这样 又必然带来图像量化噪声的增大，并且丢失灰度细节的信息。数字图像的庞大数据对 计算机的处理速度、存储容量都提出很高的要求，而图像压缩就可以很好的解决这一 问题。 从传送图像的角度来看，则更要求数据量压缩。首先某些图像采集有时间性，例 如遥感卫星图像采集；其次图像存储体的存储时间也有限制，它取决于存储器件的最 短存取时间，若单位时间内大量图像数据来不及存储就会丢失信息；第三实时性的要 求，在信道带宽、通信链路容量一定的前提下，很显然，采用编码压缩技术，减少传 输数据量是提高通信速度的重要手段。 综上所述，由于图像数据的海量性与存储介质容量和网络带宽的有限性之间的客 观矛盾长期存在，而仅仅靠增大存储设备的容量和拓宽信道来解决这个矛盾又是不现 实的，因此要解决这个矛盾必须依赖高质量的图像压缩技术的支持。 分形图像压缩是一种利用块间自相似性来减少图像数据冗余度的新型压缩技术。 2 基于提升小波的分形图像压缩算法研究第一章绪论 它被公认为第二代图像压缩编码技术的三大方法之一【2 】，通过引入局部和全局相关去 冗余的新颖思想，突破了以熵压缩编码的界限，具有较大潜力，正适时运而生，吸引 了众多的研究者。在分形图像编码过程中，采用了类似描述的方法，而解码是通过迭 代完成的，速度快且具有分辨率无关的解码特性，在图像压缩领域，应用价值很大。 令人遗憾的是，分形编码还未完全实用化，其主要困难在于传统空域的分形压缩有很 多瓶颈【3 】。例如，在压缩时，运算复杂度太大、压缩时间较长、收敛过程较难预测和 控制、高压缩倍率时的块状效应等。因而，在当前图像压缩编码中还不占主导地位。 为了能真正发挥分形图像压缩方法的高压缩比潜力，必须找到编码实现的快速算法。 显而易见，开展分形图像压缩技术的研究具有重大的现实意义。 1 3 研究现状与发展 分形理论是图像压缩的重要数学工具，有着广阔的应用前景。分形图像压缩以迭 代函数系统( i f s ) 为理论基础，基于自然景物的自相似性来进行数据压缩。分形图像压 缩算法具有高压缩比、任意尺度下的重构、快速解码等优越性质。 f r a c t a l 一词是由法国数学家曼德勃罗【4 】创造出来的，用于表达他的分形思想，并 于1 9 7 5 年出版他的专著分形对象：形、机遇与维数，这标志着分形理论的正式诞 生。分形的定义是组成部分与整体以某种方式相似的形。 美国数学家m f b a m s l e y 5 】于1 9 8 7 年首次提出分形图像压缩，通过将迭代函数系 统( i t e r a t e df u n c t i o ns y s t e m ) 理论应用到图像压缩编码中，并获得了极好的压缩性能。 这种压缩方法新颖、有效，突破了以往熵编码的理论界限。但是这种方法具有明显的 缺点，就是在图像分割时需要人机交互，对操作者有较高的要求，无法实用。 1 9 9 0 年，b a r n s l e y 的博士生a e j a c q u i n t 6 】发表了一种基于方块划分的分形图像压 缩方案。在其方案中，首先将原始图像划分为固定大小的方块，然后对每一方块，通 过仿射变换在原始图像的紧缩图像中寻找最相似的部分，这些操作都可以由计算机自 动完成，它为分形图像编码的研究带来了一次质的飞跃。 a e j a c q u i n i7 】方案无疑为分形编码的研究注入了生机与活力，使得分形编码成为 目前图像编码领域研究的热点之一。传统的分形压缩是在空间域完成的，它直接利用 图像内部像素之间的空间相关性对图像的灰度信息进行压缩，而其编解码过程在其系 3 第一章绪论基于提升小波的分形图像压缩算法研究 统结构和实现方法上都比较的简单，但是这种简单也带来了相应的问题，那就是运算 时间太长，复杂度太大。对一幅的5 1 2 5 1 2 的l e n a 灰度图像来说，若分块时值域块 r = 4 ，定义域块d = 8 ，那么值域块就有1 6 3 8 4 块，而定义域块有1 6 1 2 9 块，那么在进 行匹配运算的时候，每一定义域块都要与值域块进行匹配运算，并且还要进行八种变 换，其运算复杂度可想而知，运算时间经常要以小时来记。这样，传统的分形编码过 程中搜索匹配的计算量很大，耗用时间太长，限制了其实际应用。 传统的分形方法直接对原图像进行规则的矩形块划分，并对这些块独立编码，使 得重构图像中相邻的块在边界上产生较为规则的误差分布。由于人类的视觉系统对水 平和垂直方向的规则误差分布具有特殊的敏感性，使得在主观感觉上认为具有规则误 差分布的重构图像质量明显降低，从而产生了“块效应 现象。 近年来人们围绕加快编解码时间、提高编码质量、消除块效应进行了不断改进， 取得了一定的进展，以及在与其它方法结合的编码方法上作了尝试。相关工作可以归 纳一下三个方面【8 】： 1 提高压缩比和编码效果 在提高压缩比和编码效果方面，主要的改进方法有： ( 1 ) 改进分割的方法 常用的分割方法有四叉树分割法和h v 分割法。四叉树分割方法的优势在于定义域 块分类的复用率高，且值域块存储位数较少。h v 分割法使用的变换个数比四叉树少， 但定义域块的分类不能复用。 ( 2 ) 基于视觉特性的处理方法 分形图像压缩对值域块进行独立编码，这不能保证块与块之间的连接是最光滑 的，常有方块效应出现，人的眼睛对此比较敏感。消除方块效应的一个常用方法是后 处理。一般采用2 ：l 加权平均或3 ：2 ：1 加权平均法。 2 提高编解码速度 分形图像编码最大的缺点是其编码时间长，为了要提高编码速度，就必须缩小搜 索范围同时保证最佳匹配在该范围内。目前提出的改进方法有： ( 1 ) 分类法：在进行匹配之前，先将所有的定义域块按灰度和性质分成若干类。 接着对每个值域块，确定它属于哪一类，并只在它所在的类里进行匹配搜索，减少搜 4 基于提升小波的分形图像压缩算法研究第一章绪论 索时间。 ( 2 ) 搜索法：包括提取特征追踪法、最近邻搜索法、采用二叉树和链表结构进 行搜索，这些搜索方法大大提高了编码速度。 ( 3 ) 其他方法：利用定义域块间的相关性来减少总的定义域块数来提高编码速 度，分形与固定矢量结合，基于固定矢量的层次分形图像压缩方法，特征向量方法、 分类法和特征向量方法相结合，将神经网络用于分形图像压缩。 分形解码图像是将编码过程构造的压缩变换迭代应用于某一幅初始图像最后收 敛而得到。由于解码过程没有耗时的搜索操作，所以分形解码速度相对于编码要快得 多，一般它迭代1 0 次左右即可完成解码。 3 与其他方法结合的分形编码 分形与其他方法相结合在不同程度上改变了编码效果，常采用分形与小波变换结 合的编码方法、分形与d c t 变换结合编码、基于预测模型的分形编码。其中，基于小 波变换的分形图像压缩编码是当前此类研究热点方向之一。 运算时间长和“块效应 现象是分形算法的两个主要的缺点【9 1 。因此人们就在试 图寻找其他的分形方法来进行改进，同时保证其高压缩比的性能。近年来，有人提出， 既然传统空间域的分形压缩有这些瓶颈，那就尝试在变换域进行压缩，并取得了优于 传统空间域分形压缩算法的性能。其中，基于小波变换的分形编码最引人注目，它揭 示了传统空间域分形压缩方法事实上可以看作是到h a r r 小波基变换后的小波系数的 量化过程，它提出了从新的角度研究分形压缩收敛问题方法，并使得设计快速的无条 件收敛的分形编码算法成为了可能。 针对传统分形图像压缩算法的缺点，本文正是在分形与小波变换结合的编码方法 做了一些研究。在分形编码中引入了小波变换。 小波变换把图像信号分解为具有不同尺度和空间选择性的一系列子空间信号，并 可以由这些信号重构图像。这是一种空间域与时间域相结合的图像分析手段。而人们 对事物的分析同样遵循由低分辨率到高分辨率的原则，这一原则与分形图像编码中的 总体向局部转化，宏观向微观深化是一致的，他们的这种一致性使其结合具有合理性 和可能性。 小波分解后，我们对图像可以根据研究的目的采取不同的方法进行编码压缩。对 5 第一章绪论基于提升小波的分形图像压缩算法研究 低频部分，我们可以采用小波压缩编码，或者分形编码的方法等等。对高频部分，一 般是采用分形的方法，这是因为利用了图像边缘所具有的局部自相似特点，而图像的 边缘信息又包含在图像的高频部分中，所以采用分形压缩编码方法可极大的利用此特 点，提高压缩比。因为连续小波函数的平滑特性，可以打破“块”的界限，使小波域 上集中分布在块边缘的误差在更大范围内稀释，从而消除“块效应”。 1 4 本文的主要工作及章节安排 在图像压缩领域中，对图像如何进行更好、更快、更高的压缩一直是研究人员所 追求的目标，是人们不懈探索的根源。分形图像压缩方法是近十几年发展起来的一种 新型图像压缩算法，它注重发掘存在于大多数图像中的自相似性，可以达到其他图像 压缩算法不可能达到的高压缩比，因此受到了研究人员的广泛重视。但分形图像压缩 算法在理论及应用上存在许多问题，如编码时的巨大计算量、解码迭代的收敛性、重 构图像的块状效应等。 本文在相关文献的研究基础上，通过引入提升小波变换，利用小波变换所具有人 类视觉特性的多尺度分辨率性质，结合小波编码与分形编码各自的优点，对两者相结 合的方法进行了探讨和研究。 本文主要章节安排如下： 第一章主要叙述了图像压缩的研究背景、意义，并对本论文的主要研究工作和论 文组织结构进行了说明。 第二章对图像压缩的原理及其主要技术进行了整理和总结，回顾了图像压缩技术 的发展历程，介绍了国内外研究中比较典型的图像压缩技术，并讨论了图像质量的评 价方法，为图像压缩编码奠定了理论基础。 第三章首先给出了分形理论的产生背景与发展，然后介绍了分形图像压缩理论基 础，讨论了分形图像编码在图像压缩领域的优势。最后引入邻域这一思想，提出了一 种基于环形结构邻域搜索的分形图像压缩算法。 第四章从小波分析理论入手，首先介绍了基于小波变换图像压缩理论基础，利用 视觉加权的标量量化技术，设计了一种基于提升格式小波的s p i h t 图像压缩算法。 然后结合分形编码与小波编码的优点，提出了一种提升小波变换的快速分形图像编码 6 基于提升小波的分形图像压缩算法研究第一章绪论 方法。实验结果表明，该方法大幅度节约了编码时间，大大避免了传统分形编码所固 有的方块效应，获得了较高的解码图像质量。 第五章总结了本文相关研究工作，同时对未来的工作进行了展望。 7 第二章图像压缩技术概述基于提升小波的分形图像压缩算法研究 第二章图像压缩技术概述 2 。1 图像压缩技术的原理 进入了信息时代，人们越来越依靠计算机获取和利用信息。而数字化后的视频和 音频等媒体信息具有数据海量性，与当前硬件技术所能提供的计算机存储资源和网络 带宽之间有很大差距。这样，就对多媒体信息的存储和传输造成了很大困难，阻碍了 人们有效获取和利用信息，数字化的媒体信息数据以压缩形式存储和传输仍然将是惟 一的选择【l l 】。 2 1 1 图像压缩的必要性与可能性 1 图像压缩的必要性 信息时代的重要特征是信息的数字化，数字化了的信息带来了“信息爆炸 。图 像压缩编码己成为正在建设的数字信息化社会所依赖的主要技术基础之一。 众所周知，原始数字图像在计算机中会占用大量的存储空间。例如，一幅5 1 2 5 1 2 大小的真彩图像，如果每个像素要占3 个字节，其数据量约为1 m b ，这对许多需要 大量存储视频图像信息的应用领域会造成很大困难。因而快速的图像压缩算法，特别 是解压缩算法，对于许多以图像数据为基础的应用场合具有非常重要的意义引。 数字图像传输是图像压缩技术的一个重要应用领域。随着现代社会对通信业务要 求的不断增长，图像通信和通信网容量的矛盾日益突出。特别是具有庞大数据量的数 字图像更是难以传输和存储，极大地制约了图像通信的发展，成为图像通信发展中的 瓶颈。图像压缩技术的应用为传真、视频点播、电视会议、医用图像传输等领域带来 了巨大经济效益。 2 图像压缩的可能性 经研究发现，与音频数据一样，图像数据中存在着大量的冗余，原因在于原始图 像数据是高度相关的。通过去除那些冗余数据可以节约文件所占的码字从而极大地降 低原始图像数据量，解决图像数据量巨大的问题，达到数据压缩的目的。 8 基于提升小波的分形图像压缩算法研究第二章图像压缩技术概述 图像压缩技术就是研究如何去掉信息中的冗余，即保留不确定的信息，去掉确定 的信息，也就是用一种更接近信息本质的描述来代替原有冗余的描述。因此，进行图 像压缩研究的起点是研究图像数据的冗余性【”】。 ( 1 ) 空间冗余：在静态图像中有一块表面颜色均匀的区域，在这个区域中所有 点的光强和色彩以及色饱和度都相同，具有很大的空间冗余。这是由于基于离散像素 采样的方法不能表示物体颜色之间的空间连贯性导致的。 ( 2 ) 时间冗余：电视图像、动画等序列图片，当其中物体有位移时，后一帧的 数据与前一帧的数据有许多共同的地方，如背景等位置不变，只有部分相邻帧改变的 画面，这显然是一种冗余，这种冗余称为时间冗余。 ( 3 ) 结构冗余：有些图像的纹理区，图像的像素值存在着明显的分布模式。例 如，方格状的地板图等。 ( 4 ) 知识冗余：有些图像的理解与其他知识有相当大的相关性。根据已有的知 识，对某些图像中所包含的物体，我们可以构造其基本模型，并创建对应各种特征的 图像库，进而图像的存储只需要保存一些特征参数，从而可以大大减少数据量。 ( 5 ) 视觉冗余：事实表明，人眼视觉系统对图像场的敏感性是非均匀和非线性 的。然而，在记录原始图像数据时，通常假定视觉系统是线性的和均匀的，对视觉敏 感和不敏感的部分同等对待，从而产生了大量的数据冗余。去掉这种冗余信息，并不 会明显降低主观图像质量，但实际上会导致定量信息的损失。 ( 6 ) 图像区域的相同性冗余：在图像中的两个或多个区域所对应的所有像素值 相同或相近，从而产生数据重复性存储。在以上的情况下，记录了一个区域中各像素 的颜色值，则与其相同或相近的其他区域就不再需要记录其中各像素的值。 ( 7 ) 纹理的统计冗余：有些图像纹理尽管不严格服从某一分布规律，但是它在 统计的意义上服从该规律，利用这种性质也可以减少表示图像的数据量。 图像压缩编码技术就是要把上述的种种压缩可能性变为现实。 2 1 2 图像压缩技术的组成 数字图像压缩系统无论采用何种具体结构和技术，其基本过程都是一致的，都包 括编码系统和解码系统两个部分【1 4 】。编码系统包括映射变换、量化和熵编码；解码就 9 第二章图像压缩技术概述 基于提升小波的分形图像压缩算法研究 是编码的逆过程，它包括熵解码、反量化和反映射变换三个步骤。其基本框图如图 2 1 所示。 原始图像变换系数 映射变换卜_ 叫量化 量化数据 恢复数据广_ 反量化数据r 1 熵解码数据 反映射变换卜卜一反量化 图2 1图像压缩系统结构图 熵编码 熵解码 码流 信道 在编码系统中，首先对原始图像进行映射变换，如时域预测、频域变换或其它变 换，作用是将原始图像在一个新的域中用另一种新的形式表述，改变了原始图像数据 的特性，使其更有利于压缩。对变换器的要求是：有效地压缩数据，同时信息保真度 要高，还要求是广义可逆的，方法简单，经济实用；接下来，变换后形成的参数进入 量化过程，用有限的符号集来表示映射后的数据。量化器的引入是图像编码产生失真 的根源。对量化器的要求是：在一定程度的客观或主观误差允许下，总的量化级数要 尽量的少，同时也应便于实现；最后，对量化后的符号进行熵编码，即给量化后输出 的每个符号分配二进制比特流。熵编码器是用来消除符号编码冗余度的，它一般不产 生失真，常用的熵编码方法有分组码、行程码、变长码和算术码等。编码器的编码方 式应与信号或符号流的分布特性相适应以求得较大的压缩比。熵编码后的信息码流将 被送入存储设备或通过信道传输。 以上三个步骤既相互联系又相互制约，对不同的编码技术来说，图像变换的模型、 量化器的设计、熵编码所采取的措施都是不同的。图像压缩的解码系统就是编码的逆 过程，它的三个步骤与编码系统是相互对应，缺一不可的，所以编码系统和解码系统 都应该被看作一个整体。 2 1 3 图像压缩技术的评价准则 在图像压缩编码中，解码图像与原始图像可能会有差异，因此，需要评价压缩后 图像的质量。图像质量的含义包括两个方面：一是重构图像的失真度，即重构图像与 原图像的偏离程度；二是图像的可懂度，即由图像向人和机器提供信息的能力。由于 目前人们对逼真度和可懂度还没有具体的评价标准，所以对图像压缩质量的评价主要 l o 基于提升小波的分形图像压缩算法研究 第二章图像压缩技术概述 还是分为主观评价方法和客观评价方法。 1 图像的主观评价方法 图像的主观评价是以视觉生理为基础，以输入图像为参照点，按照一定规则并根 据自己的经验对图像的优劣作质量判断。在有些情况下，也可以提供一组标准图像作 为参考，帮助观察者对图像质量作适当的评价。人是图像的最终接受者，所以相比客 观评价方法，主观评价方法是最可靠的。一般情况下，对编码重建图像分6 个等级【1 5 】： ( 1 ) 极好：具有极高品质的图像，和希望的一样好； ( 2 ) 良好：高品质的图像，感觉良好，其中的干扰可以接受； ( 3 ) 过得去：具有可接受的品质，其中的干扰不是不可以接受的； ( 4 ) 勉强可以：品质不良的图像，希望能得到改进，干扰在某种程度上难以接受； ( 5 ) 差：非常不好的图像，但还可以看，有明显不能接受的干扰； ( 6 ) 不可用：差到无法观看的图像。 2 图像的客观评价方法 所谓客观评价方法，就是定义一个数学公式，然后对待评价的图像进行运算，得 到一个唯一的数字量作为测度结果，这种方法最常用于对图像的逼真度评价。通常使 用的客观评价方法有输入图像和输出图像的均方根误差，输入图像和输出图像的均方 根信噪比两种【1 6 1 。令厂( x ，y ) 表示输入图像，f ”( x ，j ，) 表示由对输入厂( x ，y ) 先压缩后解 压缩得到的f ( x ，y ) 的估计量或近似量。对任意x 和y ，f ( x ，y ) 和f ( x ，y ) 之间的误差 e ( x ，力可定义为： e ( x ，y ) = f ( x ，y ) - f ( x ，y )( 2 1 ) 若f ( x ，y ) 和f ( x ，y ) 均为m n ，则它们之间均方根误差e 。为： 岛篓黔w m 川 2 ) ， 如果将f ( x ，y ) 看作原图像f ( x ，y ) 和噪声信号e ( x ，y ) 的和，那么输出图像的均方信噪 比s 凇册为： 第二章图像压缩技术概述基于提升小波的分形图像压缩算法研究 snr。=篓孰川2俊郅f(x，y)-f(xy=oix - oy b o川 2 ( 2 3 ) 。= 夕( 训) 2 ，y ) i ( 2 3 ) j 1 0lj 信嗓比的r l 们l s 值舳侬刖通过求取式( 2 3 ) 的平方根得到。买际便用中常将肼限棚归一化 并用分贝( d b ) 表示，令 7 = 面1m 刍- ! 缶n - i ( 五力 ( 2 。4 ) 则有 窆芝y ) 一升沙( x ，y ) 一对 s n r = l o l g 画萧o _ 1 ( 2 5 陟( x ，y ) - f ( x , y ) r 如果令= m a x f ( x ，力，x = 0 , 1 ，m - 1 ，y = 0 , 1 ，n - 1 则可得到峰值信噪比 ( p e a ks i g n a lt on o i s er a t i o ，p s n r ) ，定义如下： 一删g i m 圈- ! n - i 怎赢而 q石mn jr f i ，、，、| 鲁怎y 一。一j 由于图像质量测度的客观方法易于使用，一致性好，所以是最常用的方法，但在 有些情况下评价结果可能与主观方法并不一致。 3 图像的压缩效率评定 图像压缩系统可由冗余度、。编码效率和压缩比来衡量信源特征和编码设备的性 能。设原始图像的平均码长为l ，熵为h ( s ) ，压缩后图像的平均码长为k ，则定义： 冗余度：r = 南一1 编码粹哆= 挈= 丽1 压缩比： c ：= 毒 j l ， 其中日( s ) = 一丑l o g ：最，( 只为像素点灰度概率) 。 ( 2 7 ) ( 2 8 ) ( 2 9 ) 图像的压缩效率通常用压缩比来衡量，压缩比越高，图像压缩越大，反之亦然。 1 2 基于提升小波的分形图像压缩算法研究第二章图像压缩技术概述 此外，还需要考虑算法的复杂度，包括时间复杂度和空间复杂度。 2 2 图像压缩技术分类 常用的图像压缩方法种类繁多，根据解压重建后的图像与原始图像之间是否存在 误差，大致可分为无损压缩和有损压缩两大类【1 3 】。 ( 1 ) 无损压缩( 1 0 s s l e s sd a t ac o m p r e s s i o n ) ，这种方法就是利用数据的统计冗余进 行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到统计冗余度的理论限 制，一般只能是2 ：1 到5 ：l 。它主要是基于统计的编码方案，如游程编码、h u f f m a n 编码、算术编码和l z w 编码等。 ( 2 ) 有损压缩( 1 0 s s yd a t ac o m p r e s s i o n ) ，由于压缩比的限制，仅使用无损压缩方 法就不可能完全解决图像的存储和传输问题。有损压缩方法利用了人类视觉器官对图 像中的某些频率成份不敏感的特性，允许在压缩过程中损失一定的信息；虽然不能完 全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了大得多的 压缩比。常用的有损压缩方法有：p c m ( 脉冲编码调制) 、预测编码、变换编码( 主要是 d c t 变换) 、插值和外推法等。 在图2 2 中，列举了目前常见的几种图像压缩技术。 l 图2 - 2 图像压缩技术分类 1 3 c 嶷 0 h r 莹0陈阢 眦 张换 礅 测 骶 立弦换啦趺换 预 性 傅余变w 蚓变 一 一 燃一一一 线 非 离离m 离k 小 隅r t r|lz；l 一一一一 一 一 一 第二章图像压缩技术概述基于提升小波的分形图像压缩算法研究 按照编码方法提出的时间可以将图像编码分为经典图像压缩技术和现代图像压 缩技术两大类。 2 ，2 1 经典图像压缩技术 经典图像压缩技术出现的时间较早，技术也比较成熟，主要包括预测编码、传统 变换编码和熵编码，也称为三大经典编码方法【1 7 】。 1 预测编码， 预测编码的理论基础是现代统计学和控制论。其基本方法是：首先利用图像相 邻像素间存在一定的相关性，根据数据的统计特性得到预测值，然后传输各像素与其 预测值的差值信号，来达到压缩的目的。由于在进行编码时不是对像素的实际灰度值 进行编码，而是对预测误差进行量化、编码、传输，所以预测编码又称为差分脉冲编 码调制( d p c m ) 。预测编码操作简单，但是在实际应用中预测不总是正确与精确。 与其他编码方法相比，预测编码具有压缩比小、算法不稳定等缺点。 2 传统变换编码 传统变换编码f 1 9 】的基本原理是将原来在空间域上描述的图像等信号通过一种数 学变换，变换到变换域( 如频率域、正交矢量空间) 中进行描述。使图像的大部分能 量集中在较少系数上，如果采用正交变换，则图像在变换后不会丢失任何信息，并且 能量相等。再加上人眼对低频分量采用较细的量化，而对高频分量采用较粗的量化， 因此可以通过只保留幅值较大的系数来达到压缩数据的目的。也可以通过其他组织系 数的方法实现无损压缩。 目前该领域常用的编码方法有离散傅里叶变换( d f d 、离散余弦变换( d c d 、卡 胡南一列夫变换( k - l ) 和沃什一哈达马变换( w t ) 。基于上述传统正交变换的图像编码算 法变换编码的以下几个特性：能量集中特性与保持特性，去相关性和熵不变性。这就 决定了其在图像信号等处理中得到广泛应用。由于通常采用分块变换编码的策略，但 是这会在较低编码率时引入明显的“方块 效应和蚊式噪声。 3 熵编码 熵编码也是一种目前常用的经典编码方式，它主要针对无记忆信源，根据信息码 字出现的概率分布特征通过一些统计学方式来寻找概率与码字长度间的最优匹配。常 1 4 基于提升小波的分形图像压缩算法研究第二章图像压缩技术概述 用的统计编码有游程编码、h u f f m a n 编码和算术编码三种。上述编码的最大缺点是压 缩效率不稳定。例如游程编码对黑白相间的二值图像不仅达不到压缩效果，甚至会使 编码数据量大增。 ( 1 ) r l e ( r u nl e n g t he n c o d i n g ) 编码 在p c x ，b m p 等图像格式，r l e 编码【2 0 1 被广泛使用。它是压缩一个文件最简单 的方法之一。它的做法就是把一系列的重复