（计算机应用技术专业论文）基于遗传算法与视觉特性的分形图像压缩编码.pdf

摘要 随着多媒体技术和计算机通信的曰益发展，具有庞大数据量的数字图像极大 地制约了图像通信。采用有效的压缩编码技术删除冗余，以尽量少的比特数存储 图像，并同时保证图像的质量，己成为研究的热点。分形图像可进行压缩的原因 是其图像具有高度的自相似仿射特性。本论文从理论和实践上介绍了不同于传统 方法的压缩算法一基于遗传算法与视觉特性的分形图像压缩算法。作者采用迭代 函数系统( i f s ) 对图像进行压缩。主要以不动点定理和拼贴定理作为理论基础，对 给定的图像，寻找一组由压缩仿射变换构成的i f s ，使图像通过仿射变换后尽可能 与其相似。图像的解码，不依赖于原始图形，对任意初始图像，用i f s 反复迭代， 就能将原始图像重现。因此，编码文件只需存储i f s 码，从而能得到较高的压缩 比。 分形图像压缩的最终目的是要获得一个较好的i f s ，使它的吸引子与原始图像 尽可能的相似，可以把这个搜索问题看成是一个优化过程。这个优化过程是在大 空间搜索和具有许多复杂约束的知识背景下进行的。传统的经典算法难以解决此 问题，于是作者采用具有人工智能技术的遗传算法来寻找最优解。遗传算法从种 群开始搜索，每个种群所获得的知识都被嵌入了其成员的染色体中。在进化过程 中，它引入了自然进化和适者生存的原理，在复杂和变化的环境中寻找最有利的 生存方式，可以以较大的概率较快速地找到最优解。 论文首先介绍了迭代函数系统和遗传算法的基本定理和原理，它们是该课题 研究的理论基础。然后，介绍了传统的分形算法。最后作者提出了一种改进的用 于求解具有全局最优的自相似分块匹配的遗传算法，详细地一讲述了染色体编码 方法、适应度函数的设计、遗传算子的设计和采样机理。并且利用人眼对灰度变 化的敏感程度与背景有关的特点，在综合考虑图像块的均值与方差的前提下，动 态地改变分形压缩编码时定义域块仿射变换后拼贴到值域块的最小误差，从而提 高了编码速度。通过实验的结果表明，该方法解码质量好、编码速度快，是一种 可行的算法。 关键词：图像压缩；分形图像；迭代函数系统( 1 f 8 ) ；仿射变换；遗传算法( g a ) ； 视觉特性 a b s t r a c t w i t ht h ed e v e l o p i n go fm u l t i m e d i at e c h n o l o g ya n dc o m p u t e rc o m m u n i c a t i o n ， d i g i t a li m a g ew h i c hh a v ee n o r l l q o u sd a t aq u a n t i t yr e s t r i c t si m a g ec o m m u n i c a t i o n e f f e c t i v ee n c o d i n gt e c h n o l o g i e st oo b l i t e r a t er e d u n d a n c ea n dr e t a i nt h ei m a g eq u a l i t y a r et h ef o c u so fr e s e a r c h 。t h e p o s s i b i l i t y o f c o m p r e s s i o ni s b e c a u s eo fh i g h s e l f - s i m i l a r i t ya n ds e l f - t r a n s f o r m a b i l i t yr e d u n d a n c yo fi m a g e s i nt h i sd i s s e r t a t i o n ，f r o m t h e o r e t i c a la n dp r a c t i c ev i e w p o i n t ，w ep r e s e n tan o v e la p p r o a c ht oc o m p r e s sg r a y - s c a l e i m a g e sb a s e do ng e n e t i ca l g o r i t h m sa n dv i s u a lc h a r a c t e r t h ek e r n e lt h e o r yb a s e do n i nt h i sp a p e ri sc a l l e di t e r a t e df u n c t i o ns y s t e m ( i f s ) t h em a i ni d e ai st of i n da ni f s w h i c hc o n s i s t so fas e to fc o n t r a c t i v ea f f i n et r a n s f o r m a t i o n sm a i n l yb a s e do n f i x e d - p o i n tt h e o r e ma n dc o l l a g et h e o r e m ，w h e nt h e ya l ea p p l i e do nt h eo r i g i n a li m a g e ， t h eu n i o no ft h et r a n s f o r m e di m a g e sw i l lc o v e ru pt h eo r i g i n a li m a g e d e c o d i n gp r o c e s s s t a r t sf r o ma n yi m a g e sw h i c hc a nr e c u rt h eo r i g i n a li m a g eb ya p p l y i n gi f s 。t h e r e f o r e ， c o d i n gf i l eo n l ys t o r e si f sc o d e ，w h i c hc a na c h i e v eh i g hc o m p r e s s i o nr a t i o t h ep u r p o s eo ff r a c t a li m a g ec o m p r e s s i o ni s 幻g a i nag o o di f sw h o s ea t t r a c t o ri s s i m i l a rt oo r i g i n a li m a g e s ot h i ss e a r c hp r o b l e mc a nb ev i e w e da sac o m b i n a t i o na n d o p t i m i z a t i o np r o c e s sw i t hc o m p l i c a t e dc o n s t r a i n t sa n dal a m es e a r c h i n gs p a c e b e c a u s e t r a d i t i o n a la l g o r i t h mh a r d l yh a n d l ew i t ht h i sp r o b l e m ，w ea d o i p tg e n e t i ca l g o r i t h mt o s o l v et h i sp r o b l e mw h i c hh a st h ep r o p e r t yo fa r t i f i c i a li n t e l l i g e n c et e c h n o l o g y g e n e t i c a l g o r i t h ms t a r t sf r o mi n i t i a lp o p u l a t i o n t h ei n d i v i d u a l so fe a c hp o p u l a t i o ne m b e ds o m e n e wi n f o r m a t i o nw h i l et h es e a r c h i n gc a i lb ed i r e c t e dt ot h ep r o m i s i n ga r e a t h e e v o h i t i v ep r i n c i p l ea n dt h es u r v i v a lm e c h a n i s ma r ea p p l i e di nt h ea l g o r i t h m a sar e s u l t ， t h eb e s tr e s u l tc a nb ea c h i e v e dw i t hh i 鲈p r o b a b i l i t y t h ed i s s e r t a t i o ns t a r t sb ye x p l a i n i n gt h eb a s i cn o t i o n so fi t e r a t i v ef u n c t i o ns y s t e m a n dg e n e t i ca l g o r i t h m s t h e nw eg ot od e t a i l so ft h ei d e a so fc o m p r e s s i o na l g o r i t h m s b a s e do ni f st h e o r y , l a s t l y , a l lg e n e t i ca l g o r i t h mi sp r o p o s e df o ro b t a i n m e n to f m a t c h i n gd o m a i nb l o c k so ff l a c t a lp a r t i t i o ni ni m a g ec o m p r e s s i o n i tm a k e su s eo ft h e p a r t i t i o n i t e r a t e df u n c t i o ns y s t e ma n df r a c t a li m a g ec o m p r e s s i o n c h r o m o s o m e r e p r e s e n t a t i o n ，i n i t i a l i z a t i o n o fp o p u l a t i o n ，d e s i g no fs p e c i a lg e n e t i co p e r a t o r sa r e i n t r o d u c e de x p l i c i t l y i nt h i sc o d i n ga l g o r i t h m ，b a s e do nt h ec h a r a c t e rt h a tt h ev i s u a l s e n s i t i v i t yo fe y er e l a t e st ot h eb a c k g r o u n d ，w ed y n a m i c a l l ym o d i f yt h em a t c h i n ge r r o r n a f t e rs u f f i c i e n tc o n s i d e r i n gt h ea v e r a g ea n dt h ed i f f e r e n c eo ft h ec o d i n gb l o c k ， c o n s e q u e n t l yr e d u c et h ec o d i n gt i m e t h ea l g o r i t h m i sr o b u s ta n do p t i m a l b o t h t h e o r e t i c a la n a l y s e sa n de x p e r i m e n t ss h o wt h a th i g h e ri m a g eq u a l i t yc a nb ea c h i e v e d p a r a l l e l c o m p u t a t i o n o f g e n e t i ca l g o r i t h m s c o u l dr e d u c et i m ec o s ti nf r a c t a l c o m p r e s s i o n k e y w o r d s ：i m a g ec o m p r e s s i o n ；f r a c t a li m a g e ：i t e r a t i v ef u n c t i o ns y s t e m f l f s ) ； a f f i n et r a n s f o r m a t i o me v o l u t i o n a r ya l g o r i t h m ( e a ) ：v i s u a lc h a r a c t e r i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：互善很 日期：7 0 0 5 年? 月口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：王害侠日期：2 。西年? 月户日 导师签名： 夏羹纪 日期：2 “疵 了月，日 引言 随着现代信息社会对通信业务要求的不断增长，图像通信与通信网容量的矛 盾日益突出，特别是具有庞大数据量的数字图像通信，更难以传输与存储，极大 的制约了图像通信的发展，已成为图像通信发展中的“瓶颈”问题。图像压缩技 术受到了越来越多的关注。图像压缩编码的目的就是要以尽量少的比特数表征图 像，同时保持复原图像的质量，使它符合特定应用场合的要求。图像压缩是图像 存储、处理和传输的基础，它可以减轻图像存储和传输的负担，使图像在网络上 实现快速传输和实时处理。 分形图像压缩以其潜在的高压缩比受到越来越多的学者的重视自从m f b a r n s l e y 和a j a c q u i n 完成了第一个自动编码方案后，分形压缩得到了很多学者 的研究和改进。他们指出：一个精心设计的分形压缩器能产生不亚于j p e g 算法的 压缩比和保真度。最近分形图像压缩的研究主要集中在小波分形、分形定义域的 选择和优化、分形压缩与解压的速度平衡、压缩倍数的提高。其中，分形定义域 的选择与优化直接关系到压缩比和保真度的提高，日益受到重视，一种很有前途 的方法是y f i s h e r 提出的分类搜索法选择匹配对，n c h r i s t o p h e r ，l t h o m a s 等对其作了许多深入的研究，得到了许多有效降低压缩复杂度的优秀算法。1 。但是， 由于分类本身的局限性，无疑会使搜索陷入局部最优；同时，由于搜索方向的不 确定性，也不可能使算法迅速达到最优解，这将造成编码算法难于达到保真度、 压缩比和压缩速度的最优化。 遗传算法( g a ) 是基于模仿自然界的生物进化、遗传机制的一类优化算法一般 应用于控制参数、约束函数等的优化和极值求解。针对传统的分形图像压缩编码 算法的不足之处，提出了一种基于遗传算法与视觉特性的分形压缩算法。该方法 利用人眼对灰度变化的敏感程度与背景有关的特点，在综合考虑图像块的均值与 方差的前提下，动态地改变分形压缩编码时定义域块仿射变换后拼贴到值域块的 最小误差，并且构造了一种分类搜索匹配对的算法，称为遗传搜索法它结合分形 图像压缩的特点，改进了个体的基因编码方法，提出了一种自适应的适应度函数 和杂交位置概率选择方法，从而能有效克服传统搜索方法的缺点，快速找到最优 解，提高压缩比和保真度。 第一章概述 1 1 图像压缩编码基本情况 1 1 1 图像压缩的必要陛与可能性 由于图像包含的信息量大，而且非常直观、确切，相比其它信息形式来说，更容 易被人们所接受，因而具有很高的使用效率和非常广泛的适应性。因此，图像信息对 于人们的生活和工作是非常重要的。特别是在人类社会进入信息化时代的今天，图像 信息在计算机上的处理、存储和网络传输在人们的生活中越来越突出，同时人们对接 受图像信息的要求也越来越高。 从下面表1 i1 中可以看出无论是什么类型的图像信息所含的数据量都是非常巨 大的： 表1 1图像数据类型及未压缩时所需存储空间大小 图像数据大4 , 时间比特像素 未压缩大小 一页文章1 1 0 8 5 随具体情况而定 1 6 - 3 2k b i t s 灰度图像 5 1 2 5 1 28b p p2 im b i t s 彩色图像 5 1 2 5 1 22 4b p p6 2 9m b i t s 医疗图像2 0 4 8 1 6 8 01 2b p p4 1 3m b i t s 虽然目前计算机各项性能指标在不断快速提高，网络传输带宽及传输速度也不断 的得到改善，但图像本身所含数据量的巨大仍然需要对图像数据进行压缩以满足人们 各种不同的需求。 图像数据压缩的可能性是因为图像中相邻像素、行或帧之间存在着较强的相关 性。从统计观点来看，就是某一种像素的灰度值，总是和其周围其他像素灰度值之间 有某种关系，应用某种编码方法提取并减少这些相关特性，便可实现图像信息的数据 压缩。即减少图像信息中无用的冗余信息，保留有效信息，这样既减少了描述信息的 数据量，又保证图像有效信息没有丢失。而且，图像信息的最终接受者是人，而人眼 的视觉系统接受信息的能力是有限的，如灰度和空间分辨率都不能太高等等。以上种 种因素使得对图像数据进行压缩成为可能。 2 1 1 2 图像压缩编码系统 图像编码在通信、介质存储、数据发行等领域有着重要的作用，它一直是信息技 术中最活跃的研究领域之一。图像编码从2 0 世纪4 0 年代末开始进行系统研究以来， 至今已有几十年的历史。特别是到了2 0 世纪8 0 年代末9 0 年代初，随着多媒体技术 和因特网技术的出现，如何有效地组织、存储、传输和恢复图像数据，即探索更有效、 更高压缩比的图像编码技术，成为现代信息处理技术中关键任务之一。在新世纪之初， 人们对图像编码技术和标准提出了更高的要求，图像的处理与分析技术仍然是人们所 关注的重点问题之一。 图像压缩编码基本系统原理框图如图1 1 所示： 图1 1 图像压缩编码系统原理框图 图像压缩编码就是按照图1 1 所示的流程进行的，大体就是先对图像进行压缩编 码，减少图像信息表示数据量，然后经过信道传输到达接收端，在接收端对压缩图像 进行解压缩，恢复图像本来面貌。 1 1 3 图像压缩编码分类 长期以来，人们都是在传统香农信息理论的指导下进行图像压缩编码方法的研 究，即任何一组随机分布的数据信息是由其熵来表征，无失真编码的压缩效率以此熵 为界，失真编码的压缩效率也受此熵约束。然而人们在研究人的视觉特性与图像信息 之间的关系时，发现一个明显或越来越清楚的问题是：人的视觉感知特点与统计意义 上的信息分布并不一致，换句话说，在统计上需要更多信息量才能描述图像信息的特 征对视觉可能并不重要，从感知的角度讲，无需详细表征图像某些局部特征。压缩技 术的研究突破了传统香农信息理论的框架，注重对人的感知特性的利用，利用所谓感 知熵理论，使得压缩效率得以极大提高。 从1 9 4 8 年0 1 i v e r 提出p c m 编码理论开始，迄今已有半个多世纪的历史，人们已 经研究并提出各种各样的压缩方法。根据压缩技术所依据和使用的数学理论和计算方 法进行分类，可将压缩技术分为统计编码、预测编码和变换编码三大类，其中统计编 码包括h u f f m a n 编码、算术编码、跳过白色块编码、游程编码和方块编码，预测编码 包括差分脉冲编码调制和自适应预测编码，而变换编码的方法非常多，有代表性的如 基于d c t 的编码方法和基于d w i 的编码方法“3 ；按照压缩编码过程是否有失真，图像 压缩方法可大致分为无损压缩和有损压缩两种，无损压缩是一种在不引入任何失真的 条件下使比特率为最小的压缩方法，有损压缩是一种在一定比特率下获得最佳保真 度，或在给定的保真度条件下获得最小的比特率的压缩方法“1 。还有一种非常重要的 压缩编码方法是j a c q u i n 于1 9 9 2 年首先提出并实现的自动压缩图像的分形编码，这 是一种基于迭代函数系统理论的图像编码方法，其潜在的图像压缩比是非常高的，因 此得到了有关研究人员的重视图。 1 2 国内外图像压缩编码研究进展 图像压缩技术已经研究了几十年，提出了诸如d p c m ，d c t ，v o 等压缩方法，并已 经形成了基于d c t 等技术的国际压缩标准，如j p e g ，m p e g ，h 2 6 1 等，图像压缩技术 得到了广泛的实际应用。但是人们也逐渐发现这些压缩方法的一些缺点：如高压缩比 时出现严重的方块效应、没有充分利用人眼视觉系统( h u m a nv i s u a ls y s t e m ，简称 i n s ) 等。为此，人们经过不断探索，又陆续提出了一些新的压缩方法，例如分形图像 压缩、小波变换图像压缩、数论变换压缩、人工神经网络压缩等。其中分形图像压缩 和小波变换图像压缩是当前的研究热点。下面对当前最为广泛使用的图像压缩算法进 行综述，讨论了它们的优缺点以及发展前景。 】2 】j p e g 1 9 8 6 年3 月，c c i t ts gv i i i ( 国际电信电话咨询研究委员会研究组v i i i ) 的c c i c ( c o m m o nc o m p o n e n tf o ri m a g e c o m u n i c a t i o n ) 和1 8 0 j t c l s c 2 w g l 0 联合成立了“联 合图片专家组”( j o i n tp h o t o g r a p h i c e x p e r tg r o u p ，简称j p e g ) ，开发静止图像数 据压缩标准，并于1 9 8 9 年一月形成了基于自适应d c r 的j p e g 技术规范的第一个草案， 其后多次修改，至1 9 9 1 年形成i s 0 1 0 9 1 8 国际标准草案，并在一年后成去国际标准。 简称j p e g 标准。 1j p e g 压缩原理及特点 j p e g 以d c t 为基础，压缩过程如下：首先对图像分成互不重叠的块( 一般块的 大小为8 x 8 ) ，对每块进行离散余弦变换( d c t ) ，变换后的系数根据量化表进行量化， 量化后的系数按折线扫描重新组织，然后进行游程编码、算术编码或哈夫曼编码。 j p e g 的特点如下： 优点：形成了国际标准； 缺点：由于对图像进行分块，在高压缩比时产生严重的方块效应；系数进 行量化，损失信息；压缩比不高，小于5 0 ； 2j p e g 压缩的研究状况及其前景 针对j p e g 在高压缩比情况下，产生方块效应，解压图像较差，近年来提出了 不少的改进方法，最有效的是下面的两种方法： ( 1 ) d c t 零树编码 d c t 零树编码( e z d c t ) 是一种类似小波零树编码方法( e z w ) 的压缩方法。它把n xnd c t 块中的系数组成l o g2 n 个子带，然后用零树编码方案进行编码。如用3 2 x 3 2 的d c t 变换，在相同压缩比的情况下，p s n r 的值比e z w 高“3 。但是在实验中发现 e z d c t 在高压缩比的情况下，方块效应仍是致命的弱点。 ( 2 ) 层式d c t 零树编码 采用可以消除方块效应的层式d c t 方法：对图像作n x n 的d c t 变换，将低频 m x m ( m n ) 块集中起来，做m x m 的反o c t 变换；对新得到的图像做相同变换，如此 下去，直到满足要求为止。然后对层式d c t 变换及零树排列过的系数进行零树编 码。解码时，先进行零树的解码操作，然后对得到的系数进行层式d c t 变换的反 变换，得到解码图像。 j p e g 压缩的一个最大问题就是在高压缩比时产生严重的方块效应，因此在今 后的研究中，应重点解决d c t 变换产生的方块效应，同时考虑与人眼视觉特性相 结合进行压缩。 1 2 2 矢量量化编码( v q ) v q 编码方法是近年来图像压缩的一项重要技术，其简单性和有效性已经得到了 证实。它有效地利用了矢量各分量问的四种相关性一线性依赖性、非线性依赖性、概 率密度函数的形状以及矢量维数来进行相关处理。具有压缩比高，解码方法比较简单 的特点，但是编码时运算量庞大，工作时间长，为了减小图像失真，码本的体积自然 增大，使得矢量匹配的搜索时间增长，并且在高压缩比时，由于数据分块技术在矢量 量化中的采用，使得重构的图像会出现明显的块效应和边缘突起。 许多学者对v q 编码方法的不足之处做了大量的改进，如部分失真搜索算法、快 速金字塔式矢量量化算法、双测试算法、超立方体测试算法、平均值差法、不等式判 据法等等。其中，部分失真搜索编码算法是一种比较简单有效的码字搜索算法。 陆哲明和孙圣和提出了一种新颖的快速相关矢量量化图像编码算法口8 3 ，该算法对 图像块的编码采用对角顺序，即在编码过程中根据当前图像块与已编码的邻块之间的 相关性来预测输入矢量的编码标号，从而大大降低了每个输入矢量平均码字的搜索范 围和比特率。测试结果表明，该算法比传统的穷尽搜索算法、部分失真搜索算法和双 测试算法的编码速度快，且比特率低，虽然编码质量有少许下降。 罗强、任庆利等人在找出了适合图像压缩的最优小波基的基础上，提出一种比较 合适的最小距离黄金聚类算法”1 。在此基础上，根据图像分解的小波图像都具有相似 性和人的视觉系统相类似等特性，采用塔式数据矢量法，训练各矢量之间的合成距离 采用加权技术，根据矢量中参数所处层次的信息量决定权值大小，从而形成了基于小 波变换的矢量量化图像编码方法。该方法在高压缩比时具有良好的效果，p s n r 有提 高，编码时间也有减小，没有块效应，在边缘处也无明显突起现象。其他矢量量化编 码方法可以参看文献 4 0 一4 4 。 1 2 3 小波变换图像压缩 1 小波变换 小波变换用于图像压缩开始于1 9 8 9 年，s m a l l a t 提出了小波变换多分辨分 析的概念并给出了用于信号分析和重构的快速小波变换算法一- m a l l a t 算法。 m a l l a t 算法的离散小波分解公式为： h = c j + l ，, h ( n 一2 k ) 1 d j = 芝c j + 1 o 一2 k ) l “ 其重构公式为： c ，一c 卅i ( n 一2 七) + d 卅季( n 一2 t ) 。月。二。卅 婶- 2 七) + 0 “卅g n - z r j ( 1 2 ) ( n ) 和g ( n ) 是综合小 波滤波器组。对于二维数字图像，通过分别进行水平和垂直滤波，离散小波变换 将图像分成四个子带：垂直和水平方向的低频子带l l l ，水平方向的低频和垂直方 向的高频子带l h l ，水平方向的高频和垂直方向的低频子带h l l ，垂直和水平方向 的高频子带h h l 。垂直和水平方向的低频予带信号称为分析信号，其余三个子带信 号称为细节信号。对低频子带l l l 在进一步分解，又可得到更低分辨率的4 个子 带l l 2 ，l h 2 ，h l 2 ，h h 2 。如此反复，可对图像进行多级分解，直到满足我们的要 求。如图1 2 所示为一个小波三级分解的示意图。 l l 2l i t 2 l h l h l 2h h 2 h l lh h l 图1 2 小波变换三级分解示意图 2 小波变换图像压缩 由于小波变换使信号的低频长时特性和高频短时特性同时得到处理，有效地 克服了傅氏变换在处理非平稳的复杂图像信号时所存在的局限性，因而在图像压 缩领域得到了广泛的重视。小波变换图像压缩首先对图像进行多级小波分解，然 后对每层的小波系数进行量化( 一般采用零树编码进行量化) ，再对量化后的系数 进行编码，如算术编码、哈夫曼编码等无失真编码。小波图像压缩是当前图像压 缩的热点之一，已经形成了基于小波变换的国际压缩标准，如m p e g 一4 标准， j p e g 2 0 0 0 标准，足以说明小波压缩在图像压缩技术中的重要性。对于小波变换图 像压缩的研究主要集中在两个方面：一是小波基的选择，一是小波系数的编码。 3 小波基的选择 当前关于小波图像压缩的研究主要集中在研究怎样对小波系数进行有效的编 码。因为小波变换本身并不能压缩图像，只是提供了减少比特率的一种可能，须 与其它编码技术相结合对小波系数编码才能实现压缩目的。目前使用的编码方法 包括： ( 1 ) 标量量化：对小波系数进行一致量化，没有考虑小波系数之间的相关性， 算法简单，但是压缩比不高。 ( 2 ) 矢量量化。“：通过小波变换与l b g 相结合得到较好的编码效果。 ( 3 ) 肖忠提出采用树平面特征进行编码”和分块编码，利用各子带间的纵向相 关性和予带内的横向相关性，来达到数据压缩的目的，并且用实验证明与零树编 7 码相比，具有编解码速度快、压缩比高的特点。 ( 4 ) 李波通过结合基于上下文的算术编码和位平面编码，提出了基于小波包变 换的分层预测图像压缩算法3 。 ( 5 ) 零树编码：s h a p i r o 提出的零树编码利用了小波变换后不同频带中对应 位置系数之间的相关性进行编码，被认为是静态图像变换编码领域迄今为止最好 的算法之一。零树编码的具体内容参见文献 2 7 ，但是其本身存在一些缺点： 对子图进行一致标量量化，该算法中采用的逐次逼近量化( 8 a q ) 不但增加 了计算量，而且也增加了编码的比特数： 对整幅图像都进行统一编码，没有考虑最低频的子带图像能量高的特点：； 没有考虑人眼视觉特性； 为此人们已经提出了一些改进算法：等级树集分割编码方法，郭田德提出先 扫描子节点后扫描父节点以减少扫描次数”1 的改进零树编码方法在一定程度 上可以提高信噪比。 l i a n g r u it a n g 。”将离频信息也进行小波变换，考虑到人眼视觉特性对每一层 采用不同的门限值进行量化，来提高压缩比。对于零树编码以后可在以下方面进 行改进： 考虑人眼视觉特性； 最低频子图单独编码，其余频段的子图采取适当的量化步长。 4 小波变换的前景 小波图像压缩被认为是当前最有发展前途的图像压缩算法之一，具有广泛的 应用前景。小波图像压缩的研究集中在对小波系数的编码问题上。在以后的工作 中，应充分考虑人跟视觉特性，将视觉特性与编码相结合，进一步提高压缩比， 改善图像质量。并且考虑将小波变换与其他压缩方法相结合。例如与分形图像压 缩相结合是当前的一个研究热点。 1 2 4 分形图像压缩 分形图像压缩一词是美国数学家m f b a r n s l e y 于1 9 8 7 年提出的，分形用于 图像压缩开始于1 9 8 8 年，b a r n s l e y 通过实验证明分形图像压缩可以得到比经典图 像编码技术高几个数量级的压缩比，但由于分形压缩计算量大，计算时间长，且 需要专家干预，不能在计算机上自动实现，在当时没有引起太大的注意。1 9 9 0 年， b a r n s l e y 的学生a e 。j a c q u i n 提出局部迭代函数系统理论后，才使分形用于图像 8 压缩在计算机上自动实现成为可能。 1 分形图像压缩的理论基础 分形压缩主要是利用自相似的特点通过迭代函数系统( i f s ) 来实现的，其理论 基础是迭代函数系统定理和拼贴定理。 迭代函数系统i f s 是由一完备度量空间( x ，d ) 和一组有限的压缩变换 w i ：x x ，i = 1 , 2 ，n 组成，并记作 x ：w i ，i ；l 2 ， ，每个迭代函数系统都有 一个吸引子，该吸引子可表示成一幅图像。 拼贴定理的含义是：设( x ，d ) 是一完备度量空间，给定l e l l ( x ) ，e ) 0 ，若一 i v s x ：w i ，i = 1 , 2 ，) 的压缩率为0 s 1 ，且满足： n h ( l ，u 心) ) s s ， n h ( l ，爿) ss 1 一s ，或等价地 ( 工，爿) s ( 1 一s ) 一1 ，l ，0 嵋仁) ) 。 其中a 为该i f s 的吸引子，h 为h a u s d o r f f 度量，h ( x ) 是完备度量空间伍，d ) 的一个子集。 2 分形图像压缩过程 经典的分形图像压缩的一般过程如下： 分块：将图像分成n 个互不重叠的值域块r ，这些值域块正好覆盖整个图 像，同时将图像按一定步长分成m 个尺寸较大可互相重叠的定义域块d i ； 匹配：对每个值域块r ，从定义域块中寻找一个适当的定义域块d ，使得 d ；，通过某种收缩变换w f 作用后近似于r ，即( d ；) 一r ，； 编码：对每个r i ，确定最佳匹配d ；，记录b 和r i 的位置，变换w i 的参数， 对所有的值域块完成这些操作后，整个图像编码成功； 解码：从一幅任意图像开始( 大小与编码图像一样) 进行解码，对选定的n 个定义域块d ，都用相应的w i 进行一次变换，称为一次迭代。通常迭代1 0 次左 右，图像就会稳定下来，趋于迭代函数系统的吸引子，即被编码图像的解码图像。 3 分形图像压缩的研究现状 分形图像编码是目前最有发展前途的图像编码之一，也是目前研究的最为广泛 的编码技术之一。近来人们围绕缩短编码时间、提高压缩比、提高图像质量、消 除块效应等方面进行着不断的改进，取得了一定的进展。归纳如下： ( 1 ) 改进图像分割的方法： 传统的分形压缩算法把图像分割成固定大小的方块，而图像的相似性未必落 在该方块内，限制了分形压缩的效果。为此，人们提出了许多灵活多变的分割方 法，来提高分形压缩的质量。包括四叉树分割法、h v 分割法、基于边界的分割法 及六边形分割法、三角形分割法、菱形分割法、多边形分割法、基于区域的分割 法以及三角形和四边形混合分割法。这些方法都比分成固定大小的块效果好。 ( 2 ) 提高编码速度的方法： 分形图像压缩的最大缺点就是压缩时间长，即主要是编码过程中搜索最佳匹 配的定义域块要花费很长时间，要提高编码速度，就要缩小搜索范围并且保证最 佳匹配在该范围内。常用的改进方法有： 分类法： 在进行匹配之前，先将所有的定义域块按灰度和性质分成若干类。接着对每 个值域块，确定它属于哪一类，并只在它所在的类里进行匹配搜索，减少搜索时 间。f i s h e r 提出了两级分类法，操红武对其进行了改进，提出了三级分类法。1 ， 并且通过实验证明：与两级分类法相比，编码速度提高6 4 7 0 ，信噪比提高近0 5 分贝。此外，还有基于人类视觉的分类等。 搜索法： 包括提取特征追踪法、最近邻搜索法、采用二叉树和链表结构进行搜索，这 些搜索方法大大提高了编码速度。此外，将遗传算法用于分形图像压缩与穷尽搜 索匹配的算法相比，搜索范围在0 ( 1 0 。) 量级，大大降低了压缩编码的复杂性。 其它方法： 提高编码速度的方法还有利用定义域块间的相关性来减少总的定义域块数来 提高编码速度，分形与固定矢量结合，基于固定矢量的层次分形图像压缩方法， 特征向量方法、将分类法和特征向量方法相结合、将神经网络用于分形图像压缩 来提高编码速度。 ( 3 ) 提高解码速度的方法： 分形解码比编码速度快的多，一般迭代1 0 次即可，然而实际应用中，仍希望 解码时间越短越好，即迭代次数越少越好。因此可采用金字塔式解码器、去均值 解码算法和基于最小迭代与分形不动点外插相结合的解码新模式。 ( 4 ) 分形与其它方法结合的图像压缩方法： 较为流行的方法有：分形与小波变换结合的编码方法、分形与d c t 变换结合编 码、基于预测模型的分形编码以及分形与h a d a m a r d 变换相结合等，这些方法都在 不同程度上改变了编码效果。 4 分形图像压缩的特点及其前景 1 0 分形压缩发展了十几年，取得了一些卓有成效的迸展，但是还不够成熟，在 图像压缩领域不占主导地位。作为一种新兴的压缩技术，分形压缩有其独特的优 点和潜力的： ( 1 ) 分形压缩可获得很高的压缩比( 需要人工干预) 1 0 0 0 ：1 和很好的压缩效 果： ( 2 ) 分形压缩利用整体和局部的自相似性压缩，有较广的使用范围； ( 3 ) 解码可以从任意一幅图像开始，解码速度较快； ( 4 ) 将分形压缩用于序列图像。 但是它的缺点也不容忽视： ( 1 ) 在没有人工干预的情况下，压缩比还不够高： ( 2 ) 恢复图像有方块效应； ( 3 ) 压缩时间长，运算量大，不利于实时处理。 针对分形图像压缩存在的问题，可以在以下方面寻找突破口： ( 1 ) 继续寻找提高编码速度、增大压缩比、提高图像质量的改进方法。例如在 图像分割中可考虑将两种或多种分割方法相结合进行分割； ( 2 ) 继续研究分形与其它编码方法结合的新的编码方法； ( 3 ) 将人眼视觉系统引入分形压缩。 1 _ 3 图像压缩编码展望 图像压缩技术研究了几十年，取得了一些成绩，但还有许多的不足，值得我 们进一步探讨。分形图像压缩和小波图像压缩是当前的研究热点，但二者也有各 自的缺点。在今后的工作中，应与人眼视觉特性( 通常人眼对高于一定频率后的高 频信息敏感程度低于相对较低频率的信息，而且对于不同方向上的刺激也不相同， 尤其对于倾斜方向的刺激不敏感，并且在不同背景亮度和不同边缘变化程度的情 况下对误差的敏感程度不同) 相结合。总之，图像压缩领域值得广大研究者去研究、 探索，寻求更好的图像压缩方法。 1 4 本论文研究的主要内容 1 4 1 研究的目标 由于分形图像压缩的最大缺点就是压缩时间长，即主要是编码过程中搜索最 1 1 佳匹配的定义域块要花费很长时间，要提高编码速度，就要缩小搜索范围并且保 证最佳匹配在该范围内。本文希望通过用本文提出的方法能够有效的缩短图像压 缩编码的时间，并在一定程度上改善图像重建的质量，提高信噪比。 1 。4 2 主要工作 1 综合研究国内外关于图像压缩的现状，分析出它们的原理与优缺点。着重 究了分形图像压缩编码的的现状。 2 研究分形的基本理论与遗传算法的基本理论。 3 改进传统的遗传算法。 4 将改进的遗传算法与人眼的视觉特性有机结合起来并应用到分形图像压缩 编码中。 1 4 3 创新点 针对传统的分形图像压缩编码算法的不足之处，提出了一神基于遗传算法与 视觉特性的分形压缩算法。该方法利用人眼对灰度变化的敏感程度与背景有关的 特点，在综合考虑图像块的均值与方差的前提下，动态地改变分形压缩编码时定 义域块仿射变换后拼贴到值域块的最小误差，并且构造了一种分类搜索匹配对的 算法，称为遗传搜索法它结合分形图像压缩的特点，改进了个体的基因编码方法， 提出了一种自适应的适应度函数和杂交位置概率选择方法，从而能有效克服传统 搜索方法的缺点，快速找到最优解，提高压缩比和保真度。 第二章分形的基本理论 2 1 分形的定义及其眭质 分形一词的原文f r a c t a l 是由b b m a n d e l b r o t 用拉丁词根拼造的单词，意 思是细片、破碎、分数、分级等等。大自然中的所有形状和人们考虑的一切图形 可以分为两大类，一类是具有特征尺度的几何体，另一类是没有特征尺度的儿何 体。这些所谓“无标度”的几何体，其实就是分形，它们有一个共同的特征，即 自相似性。m a n d e l b r o t 曾经指出，分形具有三个要素：形状、机遇和维数。首先， 分形的形状是支离破碎、参差不齐和凸凹不平的不规则形状。其次，我们发现大 自然的海岸线与用以描述它的科克分形曲线之间仍有很大不同，而这种差异是由 于海岸线受到自然界随机因素的作用产生的，同时，m f b a r n s l e y 发现，可以对 一组给定的规则通过随机迭代而得到分形，而对象本身并不依赖于随机性，我们 总是以百分之百的概率得到同个分形，因此随机性或者机遇仅仅是工具，而结 果却是确定性的。第三，分形的维数可以是非负整数、分数、无理数。 到目前为止，分形尚无最后的定义。k f a l c o n e r 认为，对分形的定义，可以 用生物学中对“生命”定义的方法。“生命”是很难定义，但却可以给出一系列生 命对象的特征，对分形似乎也宜于给出一系列特征性质，当集合具备这些性质时 就可以认为是分形。按这种观点，称集合f 是分形，是指它具有下面典型的性质： ( 1 ) f 具有精细的结构，也就是说在任意小的尺度之下，它总有复杂的细节； ( 2 ) f 是不规整的，它的整体与局部都不能用传统的几何语言来描述； ( 3 ) f 通常有自相似形式，这种自相似可以是近似的或是统计意义下的： ( 4 ) 一般地，f 的某种定义之下的分形维数大于它的拓扑维数； ( 5 ) 在大多数令人感兴趣的情形下，f 以非常简单的方法确定，可能由迭代过 程产生。 2 2i f s 的起源与发展 m a n d e l b o r t 首先揭示了分形的木质特征，确定了分形儿何的理论框架。现在 在计算机上用各种方法生成的分形结构也越来越多。但到目前为止，用一个数学 的系统去解析地构造、研究一大类存在于人为的或自然的具有“自记忆”( 比例相 似性) 结构的分形，最为成功的就是迭代函数系统，它包含了确定性的过程