（计算机应用技术专业论文）几种快速分形图像编码方法的研究.pdf

大连理工大学硕士学位论文 摘要 本文以非线性理论中分形理论为基础，研究了几种快速分形图像压缩方法，具体研 究内容如下： ( 1 ) 基于分形的图像压缩编码是一种不对称的编码方法，编码时间长，而解码时间 却很短。传统算法进行全局搜索，编码时间长，大量的时间花费在寻找最佳匹配块。针 对传统算法的不足之处，本文利用邻近搜索法，减少了搜索定义域块的数日，从而减少 了查找最佳匹配块的时间。实验结果表明本方法在压缩编码的速度方面，比t r u o n g 等 人提出的搜索方法相比，提高了编码速度，并且重建图像的效果基本上相差不多。 ( 2 ) 利用离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ，简称d c t ) 的简单分类的快速分 形编码方法，在编码的过程中，首先根据图像的边缘属性将图像按照二叉树的形式进行 分割，并根据所给图像的两个d c t 最小的垂直和水平系数将图像块分成三类，即平坦 块，边沿块和对角块。然后，每一个值域块可以在对应类型的定义域块中查找最佳匹配 块。该方法缩小了查找空间，并且分类计算简单而有效，提高了编码速度，保证了重建 图像的质量。同时自适应产生分类的门限值，能够保证稳定的压缩比。实验结果表明本 文方法能够保证稳定的压缩比，且解码图像质量与全搜索方法的差不多。 ( 3 ) 图像纹理是图像分析与处理的一个重要内容，而分形编码理论中的分形维数可 以刻画物体表面不规则程度，并且它与入类视觉系统对图像纹理租糙度的感知是一致 的。分形维数越大，对应的图像表面越粗糙，分形维数越小，对应的图像表面越光滑。 因此本文正是利用分形维数的简单分类进行分形图像编码。首先从分形维数的角度出 发，利用图像的分形对图像进行分类预处理，然后，每一个值域块可以在对应类型的定 义域块中查找最佳匹配块。该方法基于图像块的差分盒维数特征，能够在较小的搜索范 围内完成值域子块的最佳匹配，在保证重建图像的质量的前提下，提高编码速度，同时 能够准确描述图像块的纹理特征，基于该分类的图像压缩编码方法，在信噪比较高的条 件下，能够提高编码速度，而且压缩比有所提高。实验结果表明本方法与全搜索方法相 比，能够在保证具有稳定的压缩比的前提下，提高编码速度且得到比较理想的解码图像。 关键词：分形；图像压缩；迭代函数系；分形维数 大连理工大学硕士学位论文 r e s e a r c ho ns o m ef a s tf r a c t a li m a g ee n c o d i n gm e t h o d a b s tr a c t i nt l u sp a p e r , b a s e do nt h ef r a c t a lt h e o r yw h i c hi st h ek e r n e lo ft h en o n - l i n e a rt h e o r y , s o m ef a s tf r a c t a li m a g e e n c o d i n gm e t h o dh a sb e e ns t u d i e da sf o l l o w s ： ( 1 ) f r a c t a ii m a g ec o m p r e s s i o ni san o n s y m m e t r i c a lc o d i n gm e t h o d , w h i l ee n c o d i n gi s t h em o s tc o n s u m i n gp a r tw h i l ed e c o d i n gt i m ei sq u i t es h o r t t h el o n gt i m eo ft h eb a s e l i n e m e t h o di se s s e n t i a l l ys p e n t0 1 1t h es e a r c hf o rt h eb e s t - m a t c hb l o c ki nal a r g ed o m a i np o o la n d s u c hd r a w b a c kr e n d e r si ti m p r a c t i c a lf o rr e a lt i m ea p p l i c a t i o n i nt h i sp a p e r , a d j a c e n ts e a r c h m e t h o di su t i l i z e dt or e d u c ot h es e a r c h i n gs p a c e ，a n ds p e e du pt h ef r a c t a li m a g ec o m p r e s s i o n w i t ht h et e c h n i q u e ，t h ee n c o d i n gs p e e di s3 0 0t i m e sf a s t e rt h a nt h a to fc o n v e n t i o n a lf u l l s e a r c hm e t h o d ，a n do u t p e r f o r m sp r e c e d e st ot h er e c e n t l yp u b l i s h e ds p a t i a lc o r r e l a t i o n a l g o r i t h mb yt r u o n ge ta 1 i nt e r m so fe n c o d i n gt i m ew h i l e t h eq u a l i t yo ft h er e t r i e v e di m a g e i sa l m o s tt h es a m e ( 2 ) i nt h i sp a p e r , s p 矗g l - u pf r a e t a li m a g ec o m p r e s s i o nw i t hd c t ( d i s c r e t ec o s i n e t r a n s f o r m ) c l a s s i f i e ri sp r o p o s e d d u r i n gt h ee n c o d i n gp r o c e s s ，u s i n gt h ee d g ep r o p e r t i e so f i m a g e , t h eg i v e ni m a g ei sf i r s tp a r t i t i o n e d i n t os o m e b l o c k s b a s ，e d o nt h eb i n a r yt r e ea ts ametimea l lb l o c k so ft h e i m a g e a r ed e f i n e dt h r e ec l a s s e sw h i c ha r es m o o t h c l a s s ， d i a g o n a l s u b d i a g o n a le d g ea n dh o r i z o n t a l v e r t i c a le d g ec l a s s ，o n l ya c c o r d i n gt ot h el o w e s t h o r i z o n t a la n dv e r t i c a ld c tc o e f f i c i e n t so ft h eg i v e nb l o c k t h e ne a c hr a n g eb l o c ks e a r c h e s t h eb e s tm a t c hi nt h ec o r r e s p o n d i n gd o m a i nc l a s s s i n c et h es e a r c h i n gs p a c ei sr e d u c e da n d t h ec l a s s i f i c a t i o no p e r a t i o ni ss i m p l ea n dc o m p u t a t i o n a l l ye f f i c i e n t ，t h ee n c o d i n gs p e e di s i m p r o v e da n dt h eq u a l i t yo ft h ed e c o d e di m a g ei sp r e s e r v e d t h et h r e s h o l d so ft h ec l a s s i f i e r a t ea d a p t i v e l yd e t e r m i n e ds oa st og u a r a n t e et h es t a b l es p e e d u p e x p e r i m e n t ss h o wt h a t c o m p a r i n gw i t hf u l ls e a r c hm e t h o d ，t h ep r o p o s e dm e t h o dr e d u c e dt h ee n c o d i n gt i m e 酬y ， a n do b t a i n e dr a t h e rg o o dr e t r i e v e di m a g e , m e a n w h i l e ，a c h i e v e dt h es t a b l es p e e d u pr a t i o ( 3 ) i m a g et e x t u r ei sa ni m p o r t a n tc o n t e n ti ni m a g ea n a l y s i sa n dp r o c e s s i n gw h i c hc a nb e u s e dt od e s c r i b et h ee x t e n to f i r r e g u l a rs u r f a c e t h ef i a c t a ld i m e n s i o ni nf r a c t a lt h e o r yc a nb e u s e dt od e s c r i b et h ei m a g et e x t t l r e , a n di ti st h es a m ew i t ht h eh u m a nv i s u a ls y s t e m ，t h e l l i g h e l t h ef r a c t a ld i m e n s i o ni s ，t h em u t e rt h es u r f a c eo f t h ec o r r e s p o n d i n gg r a p hi s a n dv i c e v c i 戬1 t h e r e f o r ei n t h i sp a p e raf a s tf i a c t a le n c o d i n gm e t h o db a s e d0 1 1f r a c t a ld i m e n s i o ni s p r o p o s e d d u r i n g t h e e n c o d i n g p r o c e s s ，u s i n g t h e f r a c t a l d i m e n s i o n o f t h e i m a g e , a l l b l o c k s o f t h eg i y e l li m a g ef i r s ta r ed e f i n e di n t ot h r e ec l a s s e s t h e ne a c hr a n g eb l o c ks e a r c h e st h eb e s t m a t c hi nt h ec o r r e s p o n d i n gc l a s s t h em e t h o di sb a s e d0 1 1d i f f e r e n t i a lb o xc o u n t i n gw h i c hi s i l l - 几种快速分形图像编码方法的研究 c h o s e nf o rt e x t u r ea n a l y s i se x a c t l y s i n c et h es e a r c h i n gs p a t i sr e d u c e da n dt h ec l a s s i f i c a t i o n o p e r a t i o ni ss i m p l ea n dc o m p u t a t i o n a l l ye f f i c i e n t ，t h ee n c o d i n gs p e e di si m p r o v e da n dt h e q u a l i t yo ft h ed e c o d e di m a g ei sp r e s e r v e d e x p e r i m e n t ss h o wt h a tc o m p a r i n gw i t hf u l ls e a r c h m e t h o d ，t h ep r o p o s e dm e t h o dr e d u c e dt h ee n c o d i n gt i m eg r e a t l y , a n do b “n e dr a t h e rg o o d r e t r i e v e di m a g e ，m e a n w h i l e , a c h i e v e dt h es t a b l es p e e d u pr a t i o k e yw o r d s ：f m c t a l ；i m a g ec o m p r e s s i o n ；i t e r a t e df u n c t i o ns y s t e m ；f r a c t a id i m e n s i o n i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名； 逾翌缘日期：苎翠兰兰 人连理l 人学硕+ 研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作一：豇堡氅 铷虢 习。釜之 塑丑年卫月旦同 大连理工大学硕士学位论文 引言 9 0 年代蓬勃发展起来的多媒体技术是当代科技发展的主导领域之一，而图像是其中 最为重要和复杂的媒体。多媒体数据有效传输、存储的一个关键问题是数据压缩技术， 尤其是图像数据压缩。它己成为计算机、通信、数字消费电子三大信息支柱产业得共性 核心技术，也是电话网、计算机网和广播电视网三网逐步融合最终走向合一的技术基础 之一。因而怎样对图像数据进行行之有效地传输和存储是个极具挑战性的课题【i 弓】。 2 0 世纪8 0 年代末，b a m s l e y 及其研究小组公布了使用分形压缩图像数据的思想卜”。 1 9 9 0 年，j a c q u i n 提出了基于局部迭代函数系统( t 成a l i t e r a t e d f u n c t i o ns y s t e m ，简称l 腰s ) 的分形块编码方法【8 】，这是首次利用计算机进行数字图像的分形压缩的自动算法，对分 形图像压缩方法的实用化起了奠基的作用。这是一种图像编码的全新思想：它利用自然 图像中不同区域闯存在的跨尺度自相似性、把现实图像建模为分形体来实现图像压缩 的。一幅图像用使图像近似不变的压缩仿射变换( 由一组刻画局部自相似性的压缩仿射 变换组成，即迭代函数系统) 的量化参数来表达，只需储存压缩变换的量化参数而不是 整幅图像，而存储仿射变换量化参数的比特数大大低于储存原始图像的比特数，因此实 现了图像数据的高倍压缩。解码是新颖的快速迭代过程，表达图像的变换是压缩的， b a n a c h 不动点定理保证变换的不动图像是存在唯一的，且可以从任何初始图像迭代生 成。 分形图像编码技术以其新颖的思想、高压缩比、分辨率无关性和快速解码等优点受 到技术界的广泛关注。然而，分形编码技术是不对称的，尽管分形解码已经足够快了， 分形编码也有着很高的压缩比，但因其编码非常耗时，导致其一直难以实际应用。为此， 技术界在如何加快分形编码速度方面进行了广泛深入的研究。 本文在前人工作的基础上，以非线性理论中的分形知识为基础，在提高分形图像压 缩的编码速度方面，对邻近搜索、分类方法以及与其他方法相结合的混合图像压缩方法 进行了重点研究。 几种快速分形图像编码方法的研究 1 数字图像压缩概述 1 1 图像压缩的必要性 9 0 年代蓬勃发展起来的多媒体技术是当代科技发展的主导领域之一，而图像信息是 其中最为重要和复杂的媒体。尽管图像存在诸多优点，但有一个潜在的问题，就是要表 示或传输它们则需要大量比特数。此时图像压缩则显得非常重要。例如低分辨率，t 、， 质量，彩色电视图像：5 1 2 x 5 1 2 像素色，8 比特像素，3 色z6 x 1 0 6 b i t ，假如电话线上 传输分辨率为5 1 2 x 5 1 2 x 8 比特像素3 色的电视图像，当利用9 6 0 0 波特( b i t s ) 的调制解 调器是，对于单幅图像的传输占用大约1 1 分钟，对于大多数应用来说，这是不可接受 的【9 l 。 1 2 图像压缩编码的可能性 图像的压缩不仅是必要的，而且是可能的。通常把图像压缩编码简称为图像编码。 图像数据压缩的可能性在于： ( 1 ) 图像中的像素之间，行之间和帧之间都存在着较强的相关性。即某一个像素的 灰度值总和其周围其他像素灰度值有某种关系，应用某种编码方法提取并减少这些相关 性，就是减少图像信息中无用的冗余信息，达到数据量压缩，实现保持编码。 ( 2 ) 图像信息的信宿( 接收器) 往往是人的视觉系统，它的灰度和空间分辨率是有限 的。 ( 3 ) 一般的记录和显示设备接受信息量的程度也受本身的限制。 “) 许多应用方面，可以只对图像中的某些有用的特征信息进行特征抽取编码【1 1 。 1 3 图像压缩编码的分类 利用不同的编码方法删除冗余，就形成了不同类型的压缩编码方法。数据压缩编码 技术的分类方法众多，至今尚无统一分类方法。多数学者比较统一的分类方法是将数据 压缩分为某种程度上可逆的和实际上不可逆的两大类 1 - 1o 】：可逆压缩和不可逆压缩。 ( 1 ) 可逆压缩冗余度压缩 可逆压缩常称为冗余度压缩，该方法没有信息的丢失，可以根据压缩后的数据完全 恢复原来的数据。它始终是一个可逆的过程。包括统计编码等方法： 统计编码：指根据信息码字出现概率的分布特征进行压缩编码，寻找出现概率与码 字长度问的最优匹配。常见的霍夫曼( h u f f m a n ) 编码、香农一费诺( s h a n n o n f a n o ) 编码以 及算术编码( a r i t h m e t i cc o a i n g ) 都属于统计编码。 一2 大连理工大学硕士学位论文 ( 2 ) 不可逆压缩j 商压缩 不可逆压缩是一类有失真的编码方法，信息论中叫做熵压缩。该方法导致信息的减 少，有信息丢失。丢失了的信息是根本无法恢复的，所以是一个不可逆的过程。常用的 方法有： 变换编码：指将给定的图像变换到另一个数据域( 如频域) 上，使得大量的信息 能有较少的数据来表示。常用的方法有：离散傅立叶变换( d i s c r e t ef o u r i e rt r a n s f o r m ， 简称d f t ) 、离散余弦变换( d c t ) 、离散哈达玛变换( d i s c r e t eh a d a m a r dt r a a s f o r i l l ，简 称d h t ) 。 预测编码：指只对新的信息进行编码，从而去掉相邻像素之间的相关性和冗余 性。常用的方法有：增量调制( d e l t am o d u l a t i o n ，简称d m ) 、差分脉冲编码调制 ( d i f f e r e n t i a lp u l s ec o d em o d u l a t i o n ，简称d p c m ) 。 直接映射：常用方法有向量量化、神经网络和方块截尾等。以向量量化为例， 它把图像分块，每一块中的元素组成一个向量，对向量进行新的编码。注意到图像中的 很多块可能比较相近，因而只要用一个向量就可以代表这些块。通过聚类算法，可用比 较少的码把图像恢复出来。 分析综合编码：包括子带、模型基和小波等。 冗余度压缩与不可逆压缩的结合形成了一类称为混合编码技术，它体现了不同类型 技术的交叉和综合，实际上许多国际标准都是采用混合编码技术。 1 4 图像质量的评价标准 对于图像不可逆压缩，原始图像与重建图像之间存在着差异，这些差异的大小意味 着恢复图像的质量的不同，存在着如下两种评价标准【”】： ( 1 ) 客观评价标准 设原始的m x n 个像素点的灰度图像a = f ( i ，) ，经压缩还原后的图像数据为 a = f ( f ，- ，) ，其中i = 0 , 1 9 - 9 m ，- ，= 0 , 1 ，n 。可用下列几种指标评价： 均方误差：朋晒2 赤善丢( 厂( d f u - ，) ) 2 规范化均方误差：舢= 等笋，其中巧= = 1 缶m 丢n m y 厂2 g 力 盯； 。 面= 厅2 对数信燥比：髓傻= 1 0 l o g 盖2 1 0 l o g n m s e ( d b ) 几种快速分形图像编码方法的研究 峰值信燥比：p s n r = 1 0 l o g 羔( d b ) m ) c 实际上，p s n r 为常用标准，当p s n r 超过3 0 d b 时，我们的主观视觉很难找出其差 异。 ( 2 ) 主观评价 主观评价是通过一组实验人员对图像进行观察打分，来评价图像的质量。主观评价 与客观评价之间有一定的联系，但又不能完全等同。客观评价更具有说服力，所以论文 中采用此种评价标准。 1 5 分形图像压缩 分形理论是7 0 年代产生的- - f 新兴学科。分形图像压缩是分形理论在图像压缩领 域的应用。分形图像可以看作一种具有复杂几何形状，其内部存在无穷多个自相似的图 像。可以用一组表示仿射变换的迭代函数方程来描述这些相似性。并且分型图像也可以 通过迭代函数系统多次迭代产生。任意图像都可以近似为分形图像，那么只要找到其图 像内部存在的自相似性，得到其迭代函数系统，就可以通过该迭代函数系统的多次迭代 而产生图像。如果我们用代表白相似迭代函数系统得参数来表达图像，就可以大大减少 原始图像的数据量，从而达到数据压缩的目的。分形图像编码方法也应运而生了。 实际上，按照分类，分形图像编码的方法介于直接映射和分析综合编码之间，但 又有其独特的风格。大致讲，它把任意一幅图像看作一个分形，只要找到分形变换的参 数，就可以用迭代的方法把原来的图像恢复出来。图像既是被近似为分形，因而它是不 可逆压缩。它是一个相对较新的图像压缩技术，它的基础是分形变换，实际上是局部迭 代函数系统。1 9 8 8 年，b a m s l e y 对几幅图像进行编码，达到了高达1 0 0 0 0 ：1 的压缩比。 目前，分形图像编码以其新颖的思想、高压缩比、分辨率无关性等优点受到技术界广泛 关注，是目前最有前途的新一代图像编码技术之一1 0 1 2 】。 分形编码是一种利用自然图像不同区域间存在的跨尺度块间自相似性来减少图像 数据冗余度的新型编码技术，它具有以下特点： ( 1 ) 思想新颖。分形编码是利用自然图像中不同区域间存在的跨尺度冗余( 即不同 尺度下的自相似冗余) 来实现图像压缩的。自然图像是大自然某个部分的真实再现，而 自然界的景物图像都或多或少存在着确定的或统计的自相似性，分形编码算法恰好利用 了这一点。 ( 2 ) 压缩比很高。尽管分形编码能够实现1 0 0 0 0 ：1 压缩比的流行说法有一些夸张， 但是研究表明，对于一般图像，当压缩比在2 0 倍以上时仍能得到较好的图像质量。对 - 4 - 大连理工大学硕士学位论文 某些自相似性强的图像，压缩比可达上百倍。此外，与基于d c t 的j p e g 编码相比，当 压缩比在4 0 倍以上时，分形编码能取得更好的图像质量：但在较低的压缩比下，j p e g 编码的效果更好。因此，分形图像编码可以作为j p e g 编码的有益补充。 ( 3 ) 解码图像的分辨率无关性。可按任意高于或低于原编码图像的分辨率来进行解 码，当要解码成较高分辨率图像时，引入的细节会与整个图像大致和谐一致，从而比像 素复制或插值方法得到的图像看起来更自然。这种缩放能力也可以用作图像增强工具。 ( 4 ) 解码速度快。分形压缩是一非对称过程，虽然基本分形编码很耗时，但解码速 度快( 且是新颖的迭代解码方式) ，因此，分形编码为图像存储与恢复等一次编码多次解 码的应用场合提供了一个优秀的候选方法一编码可由专用硬件设备完成，解码则可按 用户的需要用软件方法多次重复进行。一个成功的应用是微软的c d - r o m 百科全书 ( “m i c r o s o f te n c a r t a ”) i l o 。 ( 5 ) 编码时间过长，实时性差。但这仅仅是对b a r n s l c y 算法和j a c q u i n 的基本分形 块算法而言的，目前已提出的大量快速分形算法使得编码时间大大缩短( 几秒内完成) 。 1 6 本文研究内容和章节安排 第一章简要地介绍课题的研究背景，图像压缩的必要性和可能性以及叙述了图像压 缩类型，接着介绍了分形图像编码的概念及主要内容。 第二章介绍分形图像编码的数学基础，主要包括迭代函数系统、b a n a c h 不动点定理 和拼贴定理，以及介绍利用迭代函数系统理论构造分形集的具体实现方法 第三章介绍了传统的j a c q u i n 的分形图像压缩方法以及基于改进的邻近搜索法分形 图像压缩方法。 第四章，第五章分别介绍作者利用分类的思想进行分形图像压缩，其中第四章结合 离散余弦的方法进行分形图像压缩，第五章是采用分形理论中的分形维数的思想来进行 图像压缩。 最后是总结与展望。 几种快速分形图像编码方法的研究 2 分形理论与分形图像压缩 分形编码的数学基础【b ，1 4 】主要包括迭代函数系统、压缩映射原理和拼贴定理。迭代 函数系统( i t e r a t e df u n c t i o ns y s t e m ，简称i f s ) 【6 ，”】是b a r n s l e y 及其研究小组h u t c h i n s o n 在1 9 8 1 年提出的迭代函数理论( i t e r a t e d f u n c t i o n t h e o r y ) 的基础上发展起来的，它是分形 几何的一个重要组成部分。压缩映射原理是泛函分析【1 6 】中的一个著名结果，是著名数学 家b a n a c h 在总结前人结果的基础上于1 9 2 2 年提炼出来的。拼贴定理是b a r n s l e y 于2 0 世纪8 0 年代后期提出的，它是压缩映射原理的一个简单推论，并成功地用于集合、函 数( 包括信号、图像) 等的逼近。基于i f s 的分形图像编码可以获得极好的压缩性能，能 够实现很高的压缩比，其实质是假设现实图像具有自相似性( 分形的典型特征) 来实现图 像数据压缩。从数学上看，分形编码的原理是简单的，待编码图像由不动点定理保证可 用接近它的压缩仿射变换表示，压缩映射原理保证解码图像由压缩变换迭代作用于任意 初始图像来生成，拼贴定理则保证解码图像是待编码图像的近似图像。 尽管分形编码的原理从概念的观点上看是容易理解的，但是为了叙述严谨、清晰， 坚实可靠而明确的数学描述是绝对必要的。此外，要了解分形图像压缩技术的起源，以 及理解该技术的数学原理，分形的概念、度量空间及其压缩映射原理和拼贴定理是必不 可少的。分形理论( 核心是分形几何) 是非线性科学研究中十分活跃的一个分支，特别是 十余年来在计算机图像处理和分析中显示出越来越重要的作用。 分形图像压缩编码是分形几何、泛函分析等现代数学分支最成功的应用之一。这充 分说明，一些复杂的数学理论，尽管难于理解，但往往能为图像处理等技术提供意想不 到的合理方法。 2 1 分形与分形空间 2 1 1 分形的定义 分形( f r a c t a l ) 这个新的术语是美籍法国数学家m a n d e l b r o t 于1 9 7 5 年创造的。目前 对分形还没有严格的数学定义，只能给出描述性的定义。粗略的说，分形是对没有特征 长度( 所谓特征长度，是指所考虑的集合对象所包含的各种长度的代表者，例如一个球， 可用它的半径作为它的特征长度) ，但具有一定意义下的自相似图形和结构的总称。大 多数分形在一定的标度范围内不断放大其任何部分，其不规则程度都是一样的，这个性 质称为比例自相似性；而按照统计的观点，其任一局部经移位、旋转、缩放变换后与其 他任意部分相似。这两个性质揭示了自然界中一切形状及现象都能以较小或部分的细节 反映出整体的不规则性。m a n d e l b r o t 最先引入分形一词，意为破碎的，不规则的，并且 6 一 大连理工大学硕士学位论文 曾建议将分形定义为整体与局部在某种意义下的对称性的集合，或者具有某种意义下的 自相似集合。为此，m a n d e l b r o t 曾经为分形下过两个定义 1 9 1 ： ( 1 ) 满r = o z m ，( 彳) d i m ，) 的集合，称为分形集。其中，d i m 。( 一) 为集合a 的 h a u s d o f f 维数( 或分维数) ，d i m ，( _ ) 为其拓扑维数。一般说来，d i m 。( 爿) 不是整数，而 是分数。 ( 2 ) 组成部分以某种方式与整体相似的形体，称为分形。 然而，经过理论和应用的检验，人们发现这两个定义很难包括分形如此丰富的内容。 实际上，对于什么是分形，到目前为止还不能给出一个确切的定义，正如生物学中对“生 命”也没有严格明确的定义一样，人们通常是列出生命体的一系列特性来加以说明。对 分形的定义也可同样的处理。 ( 1 ) 分形集都具有任意小尺度下的比例细节，或者说它具有精细的结构。 ( 2 ) 分形集不能用传统的几何语言来描述，它既不是满足某些条件的点的轨迹，也 不是某些简单方程的解集。 。 ( 3 ) 分形集具有某种自相似形式，可能是近似的自相似或者统计的自相似。 ( 4 ) 一般，分形集的“分形维数”严格大于它相应的拓扑维数。 ( 5 ) 在大多数令人感兴趣的情形下，分形集由非常简单的方法定义，可能以变换的 迭代产生。 对于各种不同的分形，有的可能同时具有上述的全部性质，有的可能只有( 1 ) 一( 5 ) 中的大部分性质，而对某个性质有例外，但这并不影响我们把这个集合称为分形：。 2 1 2 分形空间 定义2 1 一个度量空间，d ) 就是空间x 伴随实函数d ：x x r 。令x , y x ， 函数d 就是度量x 和y 的距离。d 必须满足如下公理： ( 1 ) d “y ) = d 砷，v x , y x ； ( 2 ) 0 d “y ) 0 0 ，帆，y x ，石j ，； ( 3 ) d ( 五工) = o ，v x x ； ( 4 ) d ( y ) 茎d z ) + d ( 五z ) ，v x , y , z x 。 定义2 2 如果度量空间，d ) 中每个c a u e h y 序列都有极限工x ，则度量空间 ，d ) 称为完备度量空间。 分形几何的研究对象是分形几何，所以必须引入点与集合，集合与集合的度量关系。 几种快速分形图像编码方法的研究 定义2 3 设，d ) 为完备度量空间，工x ，集合b e h ( x ) ，定义 d ( x ，曰) = n f m 埘( 工，y ) i y b ) ， 称d ( x ，b ) 为点x 到集合口的距离。 定义2 4 设彳，b h ( x ) ，j 已d ( a ，曰) 是从集合一到集合b 的距离： a ( a ，口) = n l a x d ( 工，b ) i 工4 ) 。 由上面定义的距离，我们可以得到a ( a ，功d ( 且一) ，即不满足交换率。因此，如 上定义的距离并不是h ( x ) 上的一个度量。我们定义h a u s d o r f f 离如下。 定义2 5设，d ) 为一完备度量空间，a ，b h ( x ) ，记h ( a ，b ) 为a 和曰的 h a u s d o r f f 距离，定义如下： h ( a ，口) = m a x d ( a ，b ) ，a ( b ，彳) ) ， 根据这个定义，显然有 h ( a ，曰) = h ( b ，彳) 。 定理2 1h a u s d o r f f 离h 是空间r t ( x ) 中的一个度量，称为h a u s d o r f f 度量。因此 称( 日( ) ，h ) 为h a u s d o r f f 度量空间。 定理2 2 设，d ) 为一完备度量空间，则h a u s d o r f f 度量空间( 日( j ) ，h ) 也是一个完 备度量空间。 我们称( 日( 加，功为分形空间，今后对分形的讨论均在此空间中进行。 2 2 分形图像压缩的数学基础 2 2 1 仿射变换 定义2 6设厂：x 寸x 是度量空间上的一个变换，厂的向前迭代就是变换 广：石寸j ，其定义为f 0 ( j ) = x , f 1 ( 工) = ( 工) ，f ( x ) = f o ，4 ( 善) = f ( f 4 ( 砷) ，开= 0 , 1 ，2 ， 定义2 7 变换w ：r 2 呻r 2 具有形式 岈升 其中口，b ，c , d ，e ，f 为实数，则称矿为一个( 二维) 仿射变换。 当工r 2 时。式( 2 1 ) 常写成 一8 一 ( 2 1 ) 大连理工大学硕士学位论文 = m + f ， 撕= 一计 有四种平面仿射变换具有明显的几何意义，记 4 ： 4 书o 件一瞄= ， 其中4 为缩放变换，4 为伸长变换，4 为剪切变换，4 为旋转变换。 由此可见，仿射变换就是把原图进行缩放、扭曲、平移和旋转。 2 2 2 压缩映射与不动点 定义2 8 度量空间，d ) 上的变换，：x 寸z 称作压缩或压缩映射，如果存在一个 常数0 茎s 1 ，使得 d ( 厂( ，( _ ) ) ) 妇( 五_ ) ，) ，v x ，) ，r ， 则称厂为空间x 上的一个压缩映射，j 为压缩因子，且此压缩映射是连续的。 定理2 3 ( 压缩映射原理) 设，d ) 为一完备度量空间，厂：工寸x 是x 上的一个压 缩映射。则，存在唯一的不动点矗，即( k ) = 矗。且对任意的x e x ，序列 扩( ，以= 0 , i ，2 ，) 收敛到k 。 。 压缩映射原理是泛函分析的一个著名结果，在泛函分析专著中都可以找到证明( 参 看文献1 1 6 ) 这里略去证明细节。 定理2 4 设f ：x 一工是度量空间，d ) 上的一个压缩映射，压缩因子为s ； ( 日( j 0 ，| 1 1 ) 是由x 的非空紧集构成的h a u s d o r f f 空间，h 为h a u s d o r f f 度量。则下面定义 的映射f ：日( x ) - - 4 日( x ) 是( 日( x ) ，h ) 上的压缩映射，压缩因子也为s ： ，( 口) = ( 砷：工哪，垤h ( n 。 定理2 5 设 q ，开- - 1 ，2 ，) 是( 圩( x ) ，j j l ) 上的一组压缩映射，对每个一，q 的压 缩因子为，定义w ：h ( x ) 斗汀( 石) ， w ( b ) = q ( b ) u 哆( b ) u u c o # ( b ) ，v b ( d ， 则：日( 柳一日( j ) 是一个压缩映射，压缩因子j = m 缸p 。，疗= l 2 ，明。 一9 几种快速分形图像编码方法的研究 2 2 3 迭代函数系统、吸引子和拼贴定理 迭代函数系统是分形理论的重要分支，最早来源于h u t c h i n s o n 于1 9 8 1 年对自相似 集的研究。美国科学家b a r n s l e y 于1 9 8 5 年发展了这一分形构型系统，并命名为迭代函 数系统( s ) 【1 5 ， 1 。 定义2 9 ( 迭代函数系统)一个迭代函数系统是由一个完备度量空间，d ) 和一组 有限的压缩映射q ：x x 及其相应的压缩因子是j 。，n = l ，2 ，n ，所组成。常用i f s 来表示迭代函数系( i t e r a t e df u n c t i o ns y s t e m ，简称w s ) ，记为弘；q ，h = l ，2 ，) 且其 压缩因子便是5 = m a x 瓴，一= l ，2 ，) 。 定理2 6 【6 1 设 x ；q ，n = 1 , 2 9 oo9 n ) 是拥有压缩因子j 的一个迭代函数系，则变换 形：h ( x ) 斗h ( x ) 定义如 w ( b ) = q ( 口) u 哆( 口) u u 吐，( b ) ，v b e 日( 。d 是完备空间( 日( j ) ， ) 上具有压缩因子s 的压缩映射，即 即对所有的b ，c h ( x ) ，有 j l l ( 形( 曰) ，( c ) ) j h ( b ，c ) ， 且它的唯一不动点a eh ( x 1 ，满足 j 4 = 形( 4 ) = u q ( 一) ， n - i 并且对于任意一个b 日( 彳) ，有 a = l i m w 4 ( 丑) 。 日蛐 定义2 1 0 定理2 6 中的不动点彳称为迭代函数系 x ；吃，n - l ，2 ，】的吸引子 迭代函数系的吸引子常常被看作“确定性分形”。 定理2 7 ( 拼贴定理) 嘲设，d ) 为一完备度量空问，给定日( x ) 与f 0 ，选定 一个迭代函数系；q ，n = l ，2 ，) ，其压缩因子为s ：o ss 1 ，使得 h ( l ，u q ( 工) ) f ， 肛l 其中h ( d ) 是h a u s d o r f f 度量，则 大连理工大学硕士学位论文 ( 厶a ) # 一， 其中a 是迭代函数系t x ；q ，n = l ，2 ，) 的吸引子，等价地 h ( l ，4 ) - 兰 ( 工，u q ( 工) ) 。 1 一j = 证明：根据度量的连续性，我们有 h ( l ，彳) = h ( l ，l i m w “( 工) ) = f t r n h ( l ，形“( l ) ) l i m ( 厶形( ) ) + ( 形( 三) ，形2 ( 上) ) + + ( 矿“1 ( 工) 矿4 犯) ) ) s t t m h ( l ，矿) ) + 曲仁，矿( ) ) + + j ”1 h ( l ，矿( 三) ) ) =lim普h(l川动=击h(l17-i00朋助茎击1l jl j j 拼贴定理的意义告诉我们如何去寻找一个迭代函数系统( z ；嚷，打= 1 ，2 ，) ，使得 其吸引子a 近似于或相似于一个给定的集合。找到一组压缩变换舰，9 - * * 9 ) ，当满 足上不等式时，给定集合三即可近似地用这组压缩变换的吸引子代替。因此，拼贴定理 提供了构造i f s 吸引子的计算机逼近理论依据。 2 2 4 用迭代函数系构造分形集 迭代函数系统时构造分形集的一种有效方法。下面用两个例子来说明用迭代函数系 统构造分形集的方法。 例1枫叶的绘制【j 8 ，2 0 1 ， 给出的四个仿射变换如下表2 1 ： 、 表2 1 确定性算法的仿射变换 t a b 2 1a r l e n et r a n s f o r m a t i o nu s i n gd e t e r m i n i s t i ca l g o r i t h m 则可通过i f s 迭代生成如下的枫叶： 几种快速分形图像编码方法的研究 图2 1 枫叶图 f i g 2 1g r a p ho f m a p l el e a f 以上绘制分形图形的做法叫做确定性算法，原理简单明了，易于掌握。但这种方法 不考虑吃的区别，而在迭代中使它们处于平等的地位，这就会造成了不必要的机时浪费， 所以执行起来比较费机时。为此介绍这种方法的改进形式，称之为随机迭代算法。 在r 2 上的由式( 2 1 ) 定义的仿射变换，如果用如饵表示4 的行列式，设集b 有二维 面积，则由初等几何的一个性质知： i d e a l = 絮鬻。 由于q 是压缩的，所以i 如码i o ( f - l ，2 ，忉， 其中概率只对应于变换q 。把带概率的i f s 表示成f r ；q ，哆，a ，p 2 ，p ) a 通常可取 大连理工大学硕士学位论文 乃。乒盟“- 1 ，2 ，忉， l 删。l 式中4 = 心纷- 1 ，2 ，