（信号与信息处理专业论文）分形图像快速编码技术的算法研究.pdf

硕士学位论文 摘要 在各种多媒体服务和数字通信等应用领域，图像压缩( 编码) 是至关重要的 技术。现有的大多数图像编码算法是借助相邻像素间的相关性来进行压缩的，因 而压缩比不高。实际上，图像中不仅区域内相邻像素间存在相关，而且一些相距 甚远的区域之间，或区域与整体之间也可能存在相当大的相关性，这是一种全局 相关性。分形图像编码就是利用了自然图像中不同区域间存在的跨尺度自相似性， 把现实图像建模为分形体来实现图像压缩的，它打开了图像压缩的一个全新的编 码思路。 分形图像编码是由b a r s l e y 于2 0 世纪8 0 年代末首先提出来的，它源于迭代函 数系统理论。在分形编码中，一幅图像由一个使它近似不变的压缩仿射交换表示， 重构图像是压缩交换的不动点，压缩仿射变换的参数组成原始图像的分形码。因 此，一幅图像的分形码就是寻找一个合适的压缩仿射变换，它的不动点就是原始 图像尽可能好的近似。但是，b a r s l e y 的分形压缩方法因编码时间太长，且需要人 机交互，对操作者要求较高，所以不太实用。1 9 9 0 年b a r s l e y 的学生j a c q u i n 提出 一种基于分块划分的分形图像压缩编码方案，将b a r s l e y 方案中根据图像景物内容 的人机交互分割变成为固定大小的图像块分割，将只能与整幅图像进行相似性比 较变为可以在图像的任意部分之间进行比较，从而使图像编码可以自动进行，有 力地促进了分形图像压缩的迅速发展。 然而，j a c q u i n 的编码方案也有其局限性，主要是计算量大、编码时间过长。 这是因为对于每一个值域块为了寻找一个与其最匹配的定义域块，需要对所有可 能的定义域块在所有可能的仿射变换下进行一遍穷搜索，而对每一个定义域块在 每变换下的结果，都要与值域块进行比较，计算均方误差。本文针对j a c q u i n 编 码方案计算量过大这一不足，从两个方面提出了分形编码算法的改进方案一一基 于缩减子块池算法和基于相关系数算法。基于缩减子块池算法是预先从子块池中 排除那些不太可能满足对比度因子约束的码块，从而可在图像质量降质极小或甚 至不降质的情况下显著地减少计算量和减少编码时间。在基于相关系数算法中， 用极大化子块的相关系数代替极小化子块的均方误差，避免了每次计算均方误差 前需要计算对比度因子和亮度因子的缺点，因此减少了计算量，并结合基于缩减 子块池算法，在图像质量甚至略有上升的情况下，显著地提高了编码性能。最后， 本文在基本分形解码方案的基础上，提出了基于对比度因子调节的快速分形解码 算法，通过对搜寻码本设置阙值的方法来调节对比度因子，获得了质量较高( p s n r 度量) 的第一次迭代后图像，从而在解码图像质量降质较小的情况下较基本分形解 分形图像快速编码技术的算法研究 码加快了收敛速度。 关键词：分形；图像压缩编码；快速编码；快速解码；子块；相关系数；对比度 因子 n 硕士学位论文 a b s t r a c t i m a g ec o m p r e s s i o na n dc o d i n ga r ee s s e n t i a l l yi m p o r t a n tf o rt h ed e v e l o p m e n to f v a r i o u sm u l t i m e d i as e r v i c e sa n dt e l e c o m m u n i c a t i o na p p l i c a t i o n s n o w l yt h em o s t a l g o r i t h m sf o ri m a g ec o m p r e s s i o na n dc o d i n ga r ep r o p o s e db a s e do nt h ec o r r e l a t i o no f t h en e a ri m a g ep i x e l sa n ds ot h e i rc o m p r e s s i o nr a t i o e sa r en o tb i g i nf a c t ，n o to n l yt h e n e a rp i x e l sa r ec o r r e l a t e db u ta l s ot h ed i s t a n tp i x e l sa r ec o m m o n l yc o r r e l a t e di na l l i m a g e t h ef r a c t a li m a g ec o d i n gr e g a r d st h ei m a g ea saf r a c t a a n dg a i n st h eg o a lo f c o m p r e s s i o nb yt h es e l f - c o r r e l a t i o ni nt h ev a r i o u sd i m e n t i o ni nan a t u r a li m g ea n dt h e n i n i t i a t e san e wi d e ai nt h er a n g eo fi m a g ec o d i n g f r a c t a ti m a g ec o m p r e s s i o nw a sf i r s tp r o p o s e db yb a m s l e yi nt h el a t t e ro f 】9 8 0 s a n dw a sd e v e l o p e df r o mt h em a t h e m a t i c a lt h e o r yc a l l e di t e r a t e df u n c t i o ns y s t e m s i n t h i st e c h n i q u e ，a ni m a g ei su s u a l l yr e p r e s e n t e db yac 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 ， f o rw h i c ht h er e c o n s t r u c t e di m a g ei s i t sf i x e dp o i n ta n da p p r o x i m a t et ot h eo r i g i n a l i m a g e t h ef r a c t a lc o d eo ft h ei m a g ec o n s i s t so ft h ep a r a m e t e r so ft h ec o n t r a c t i v e t r a n s f o r m a t i o n t h u s ，e n c o d i n ga l li m a g eb yf r a c t a lt e c h n i q u e sc o n s i s t so ff i n d i n ga l l a p p r o p r i a t e c o n t r a c t i v et r a n s f o r m a t i o nw h o s ef i x e d p o i n t i st h eb e s t p o s s i b l e a p p r o x i m a t i o no ft h eo r i g i n a li m a g e ，b u t ，b a r s l e y sf r a c t a lc o m p r e s s i o nm e t h o ds u f f e r s f r o mt o ol o n gc o d i n gt i m ea n dn e e dm a n u a lo p e r a t i o nw i t hh i g ht e c h n i q u e sf o rt h e o p e r a t o r s s oi t h a sn op r a c t i c a l i t y ，b a r s l e y ss t u d e n tn a m e dj a c q u i np r o p o s e da m e t h o do ff r a c t a lc o m p r e s s i o nb a s e do ni m a g et i l e s p a r t i t i o ni n19 9 0 t h em e t h o d m a k e sa l li m a g ei n t os o m ef i x e dt i l e si n s t e a do fb a r s l e y sm e t h o db a s e do nt h ei m a g e c o n t e n t a n dt h e nt h em e t h o dg a i n sa u t o - c o d i n gb yc o m p m e r sa n db o o s t st h ep r o c e s s o f t h ef r a c t a li m a g ec o d i n g b u t ，j a c q u i n sc o d i n gm e t h o dh a ss o m es h o r tb e c a u s ei t h a sm u c hc o m p u t a t i o n a n dc o d i n gt i m e t h em e t h o dt r i e st ol o o kf o rt h eb e s tm a t h e dd o m a i nb l o c kf o re v e r y r a n g eb l o c ki na l li m a g e n a m e l y ，t h em e t h o dn e e dt os e a r c hi nt h ec o d e p o o lf o re v e r y c 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 na n da l ld o m a i nb l o c k sn e e dt oc o m p a r ew i t ha n yr a n g b l o c ka n dc o m p u t e rt h em e a ns q u a r ee r r o r t h ep a p e rp r o p o s e ss o m ei m p r o v e d a l g o r i t h mf r o mt w of a c t o r sb ya i m i n ga tt h el a c ko fj a c q u i n sa l g o r i t h m - - t h ea l g o r i t h m b a s e do nc o d e b o o kr e d u c t i o na n dt h ea l g o r i t n mb a s e do nc o r r e l a t i o nt o e 伍c i e n t s t h e a l g o r i t h mb a s e do nc o d e b o o kr e d u c t i o ni s a c h i e v e db yap r i o r ie x c l u s i o no ft h e c o d e b o o kb l o c k sw h i c ha r eu n l i k e l yt om e e tt h ec o n s t r a i n to nc o n t r a s ts c a l i n gf a c t o r s m 坌丝塑丝堡壅丝至垫奎墼丝鎏丝圣 a n dt h e nm a r k e d l yr e d u c et h en u m b e ro fc o m p u t a t i o na n dt h ec o d i n gt i m ew h i l et h e d e c o d i n gi m a g eh a sh a r d l yb e e nd e g r a d e d f o rt h ea l g o r i t h mb a s e do nc o r r e l a t i o n c o e f f i c i e n t s ，w er e p l a c em a k i n gt h em s em i n i m u mb ym a k i n gt h ec o r r e l a t i o n c o e f f i c i e n tm a x i m u ma w o r d i n go f fc o m p u t e r i n gt h ec o n s t r a c t s c a l i n gf a c t o r sa n d i n t e n s i t yf a c t o r sb e f o r ec o m p u t e r i n gm s e a n dc o m b i n i n gt h ea l g o r i t h mb a s e do n c o d e b o o kr e d u c t i o n ，w eo b v i o u s l yi m p r o v et h ep e r f o r m a n c eo fc o d i n gw h i l et h e d e c o d i n gi m a g e sp s n re v e nh a si n c r e a s e dal i t t l e a tl a s t ，an e wa l g o r i t h mf o rf a s t f r a c t a li m a g ed e c o d i n gb a s e do na d j u s t e dc o n t r a s tf a c t o r sw h i c ha r ea d j u s t e dt h r o u g h s e t t i n gs o m et h r e s h o l d sf o rt h ec o d e b o o ki sp r o p o s e db a s e do nt h eb a s e l i n ea l g o r i t h m t h e e x p e r i m e n tr e s u l t ss h o w t h ea l g o r i t h mc a l lg a i nah i g h e rq u a l i t yo f d e c o d i n gi m a g e a f t e rt h ef i r s ti t e r a t i o nd e c o d i n gt h a nt h eb a s e l i n ef r a c t a ld e c o d i n ga n da c c e l e r a t e o b v i o u s l yt h ep r o c e s so fc o n v e r g i n gi nc o n t r a s tt ot h eb a s e l i n ef r a c t a ld e c o d i n gw i t ha i e s sd e g r a d a t i o no fd e c o d e di m a g e k e y w o r d s ：f r a c t a l ；i m a g ec o m p r e s s i o n c o d i n g ；f a s te n c o d i n g ；f a s td e c o d i n g ；b l o c k ； c o r r e l a t i o nc o e f f i c i e n t ；c o n t r a s tf a c t o r 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：_ 凇 日期：勿谣占月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囱。 ( 请在以上相应方框内打“”) 作者签名：丧象& 刷磴轹了莎旗 i t l t ：而年6 冠 f t 日期：加年z ；月日 硕士学位论文 1 1 课题研究的背景 第1 章绪论 自2 0 世纪8 0 年代以来，计算机在各行各业和社会生活的各个方面得到了广 泛的应用，并已广泛应用于数据处理与数据通信。尽管大容量设备和宽带网络技 术的不断发展，但是仍然难以适用快速发展的现代多媒体技术。多媒体技术就是 指用计算机综合处理文字、声音、图形、图像等多种媒体上承载的信息，图像是 其中最主要的信息载体。而图像数据的传输常常要占用很大的带宽，需要很大的 存储空间，因而怎样对图像数据进行行之有效地传输和存储是一个极具挑战性的 课题【i 儿2 1 。所以面对如何降低传输成本，增加数据传输的可靠性，不断满足人们对 信息传输的需求，图像压缩就显得具有十分重要的作用。为了解决好这个问题， 我们就必须对图像进行编码压缩，在保证一定图像质量的前提下，有效地减少存 储和传输时所需的数据量和占用的频带。 2 0 世纪8 0 年代后期和9 0 年代初，人们结合人类的视觉生理特性和心理特性、 模式识别、计算机视觉、神经网络、小波分析和分形几何学等理论，开始探索图 像压缩的新途径，称为第二代图像编码技术。其中，分形图像编码技术以其新颖 的思想、高压缩比、分辨率无关性和快速解码等优点受到技术界的广泛关注。然 而，分形编码技术是不对称的，尽管分形解码已经足够快了，分形编码也有着很 高的压缩比，但因其编码非常耗时，导致其一直难以实际应用。为此，技术界在 如何加快分形编码速度方面进行了广泛深入的研究。纵观大量分形图像编码文献， 在提高编码质量和加快分形编码速度等方面，许多新观点和大量改进算法被提出， 对它们进行准确的分类是困难的。但总的来说，大多数现有分形编码文献都是围 绕下面的基本问题展开的，或者说大多数分形编码方案的区别主要反映在这些方 面：( 1 ) 图像分割；( 2 ) 虚拟码本构成；( 3 ) 变换参数的量化、比特分配与熵编 码；( 4 ) 基础理论研究；( 5 ) 加快编码过程；( 6 ) 混合分形编码。分形编码与其 它编码方法( 如v q 、小波、神经网络等) 结合的混合编码方法已经显示出巨大 的发展潜力。分形编码技术已进入与其它编码技术结合的新时代，国外许多学者 都在积极寻找新的突破口。目前与分形编码技术结合最为成功的，应该是v q 技 术与小波技术p j 。 分形图像快速编码技术的算法研究 1 2 图像压缩编码 1 2 1 图像压缩编码的基本概念 图像压缩编码的目的是以尽量少的比特数表征图像，同时保持复原图像的质 量，使它符合预定应用场合的要求。通常把图像压缩编码简称为图像编码。 图像数据压缩的可能性在于：( 1 ) 图像中的像素之间，行之间和帧之间都存在 着较强的相关性。即某一个像素的灰度值总和其周围其他像素灰度值有某种关系， 应用某种编码方法提取并减少这些相关性，就是减少图像信息中无用的冗余信息， 达到数据量压缩，实现保持编码。( 2 ) 图像信息的信宿( 接收器) 往往是人的视 觉系统，它的灰度和空间分辨率是有限的。( 3 ) 一般的记录和显示设备接受信息 量的程度也受本身的限制。( 4 ) 许多应用方面，可以只对图像中的某些有用的特 征信息进行特征抽取编码【1 1 。 1 2 2 图像压缩编码的基本方法 图像压缩编码的方法很多，其基本技术的发展可分为两个阶段，即第一代图像 编码技术和第二代图像编码技术【l 】【2 】【4 】。 第一代图像编码技术是以香农的信息论为基础，并充分考虑了图像信源的统计 特性，根据其核心技术的不同又分为：预测编码、变换编码和统计编码。 预测编码：指只对新的信息进行编码，从而去掉相邻像素之间的相关性和 冗余性。常用的方法有：增量调制( d e l t a m 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 ) 变换编码：指将给定的图像变换到另一个数据域( 如频域) 上，使得大量 的信息能有较少的数据来表示。常用的方法有：离散傅立叶变换( d f t ) 、离散余 弦变换( d c t ) 、离散哈达玛变换( d h t ) 统计编码：指根据信息码字出现概率的分布特征进行压缩编码，寻找出现 概率与码字长度间的最优匹配。常见的霍夫曼( 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 d i n g ) 都属于统计编码。 第二代图像编码技术不再局限于香农的信息论框架，它充分地利用人眼的视觉 生理特性和图像信源的各种特征，以获得更高的压缩比和主观满意度。第二代图 像编码技术主要分为两类。 考虑人眼视觉特性的方法：基于方向滤波的图像编码方法、基于图像轮廓 一纹理的编码方法。 考虑图像景物特征的方法：分形编码方法、基于模型的编码方法等。 2 硕士学位论文 1 3 分形编码 1 。3 1 概论 分形图像编码是一个相对较新的图像压缩技术，它利用自然图像中不同区域 间存在的跨尺度自相似性、把现实图像建模为分形体来实现图像压缩的。它源于 b a m s l e y 及其研究小组对迭代函数系统的研究( 5 】和j a c q u i n 提出的分形块编码1 6 j 。 目前，分形图像编码以其新颖的思想、高压缩比、分辨率无关性等优点受到技术 界广泛关注【7 1 ，是目前公认的三种最有前途的新一代图像编码技术之一。 2 0 世纪8 0 年代末期，b a m s l e y 及其研究小组公布了使用分形压缩图像数据 的思想 s 】【9 1 。这是一种图像编码的全新思想：自然图像都包含有许多复杂的类似于 分形的物体，一种编码图形图像的有效方式是设法把这些物体描述为分形，而不 是以“光滑”的方式近似它们。其数学原理是，一幅图像用使图像近似不变的压 缩仿射变换( 由一组刻画局部自相似性的压缩仿射变换组成，即迭代函数系统) 的量化参数来表达，只需储存压缩变换的量化参数而不是整幅图像，而存储仿射 变换量化参数的比特数大大低于储存原始图像的比特数，因此实现了图像数据的 高倍压缩。解码是新颖的快速迭代过程，表达图像的交换是压缩的，b a n a c h 不动 点定理保证变换的不动图像是存在唯一的，且可以从任何初始图像迭代生成。 然而，如何寻求一个不动点图像是原始图像较好逼近的压缩仿射变换? 这是 分形图像编码技术最基本的问题。b a n a e h 不动点定理并没有提供现成的解法，一 个次优的解决途径是借助于拼贴定理【5 】：只要压缩变换使图像。近似不变 即 耳a ) ，变换不动点就是图像的一个近似图像。于是，原始图像近似 等于t ”( ) ，n 是迭代次数( 一般n 1 0 ) 。除此之外，在具体寻求压缩变换的方 式上，目前有两种方法，一种b a m s l e y 方法1 8 ，另一种是j a e q u i n 方法坤j 。b a r n s l e y 方法的编码时间太长，需要人机交互，对操作者有较高要求。因此，j a c q u i n 方法 受到更多的关注。 分形编码是一种和用块间自相似性来减少图像数据冗余度的新型编码技术， 它具有以下特点： 思想新颖。分形编码是利用自然图像中不同区域间存在的跨尺度冗余( 即 不同尺度下的自相似冗余) 来实现图像压缩的。自然图像是大自然某个部分的真 实再现，而自然界的景物图像都或多或少存在着确定的或统计的自相似性，分形 编码算法恰好利用了这一点。 压缩比很高。尽管分形编码能够实现1 0 0 0 0 ：1 压缩比的流行说法有一些夸 张，但是研究表明，对于一般图像，当压缩比在2 0 倍以上时仍能得到较好的图 像质量。对某些自相似性强的图像，压缩比可达上百倍。此外，与基于d c t 的 j p e g 编码相比，当压缩比在4 0 倍以上时，分形编码能取得更好的图像质量；但 在较低的压缩比下，j p e g 编码的效果更好。因此，分形图像编码可以作为j p e g 编码的有益补充。 一解码图像的分辨率无关性。可按任意高于或低于原编码图像的分辨率来进 行解码，当要解码成较高分辨率图像时，引入的细节会与整个图像大致和谐一致， 从而比像素复制或插值方法得到的图像看起来更自然。这种缩放能力也可以用作 图像增强工具。 一解码速度快。分形压缩是一非对称过程，虽然基本分形编码很耗时，但解 码速度快( 且是新颖的迭代解码方式) ，因此，分形编码为图像存储与恢复等一次 编码多次解码的应用场合提供了一个优秀的候选方法一一编码可由专用硬件设备 完成，解码则可按用户的需要用软件方法多次重复进行。一个成功的应用是微软 的c d r o m 百科全书l l o j ( “m i c r o s o f te n e a r t a ”) 。 一编码时闯过长，实时性差。但这仅仅是对b a m s l e y 算法和基本分形块算 法而言的，目前已提出的大量快速分形算法使得编码时间大大缩短( 几秒内完成) 。 1 3 2 分形编码的主要内容 纵观大量分形图像编码文献，在提高编码质量和加快分形编码等方面，许多 新观点和大量改进算法被提出，对它们进行准确的分类是困难的。但总的来说， 大多数现有分形编码文献都是围绕下面的基本问题展开的，或者说大多数分形编 码方案的区别主要反映在下列几方面： 图像分割。对图像的分割目前主要有以下几种：1 固定块分割，2 四叉树 分割，3 水平垂直分割，4 不规则分块。尽管固定方块分割方案实现简单，也有分 割方案占有零信息量的优点( 即无需存储或传输分割信息) ，但编码质量不理想， 不能自适应于不同的图像，也不能自适应于同一图像的不同细节。四叉树分割方 案虽然有一定的图像适应性，且描述四叉树分割的成本也很小，但它对图像的适 应性仍然是有限的。水平垂直分割和不规则分割对图像重建较好，但复杂度较高。 因此，研究一种更强的自适应分割方案是一个重要的问题。 虚拟码本构成。合适的虚拟码本对编码时间和编码质量都有很大影响，码 本越大，搜索时的耗时就越严重，但信噪比就越高；反之则信噪比越低。还有， 码本越大，记录最佳匹配块的位置所需的比特数也就越多。因此，如何构建码本 也是一个很重要的问题。 一变换参数的量化、比特分配与熵编码。在分形编码中，一幅图像是用使图 像近似不变的压缩变换来表达的，而变换又是由表达它的参数确定的。为了进一 步实现图像数据的压缩，表达变换的亮度调整参数和亮度偏移参数必须进行量化 处理，并对量化参数进行合理的比特分配。此外，熵编码可进一步改进分形编码 4 硕士学位论文 的效率。 基础理论研究。迭代函数系统逆问题的研究是其核心问题，尽管人们己尝 试各种方法解决这个问题，但目前仍然不甚理想。我们知道，压缩图像的分形文 件就是一个压缩变换的描述，对于如何寻求这样的压缩变换，拼贴定理是目前依 据的理论基础。但是，拼贴定理只是给重构误差提供一个上界( 体现为所谓的拼 贴误差) ，这个上界极小化并不意味着重构误差的极小化。因此，目前的分形编码 方案远不是最优的。当然，相关的基础理论问题并不止这个逆问题，例如，更好 的数学框架、解码收敛性、解码误差控制以及分形编码机理等的研究。 加快编码过程。这主要涉及匹配搜索问题，因为在分形编码阶段，匹配搜 索占据了主要的编码时间。全搜索固然能够得到最好的编码质量，但全搜索的运 算量大是不争的事实。加快分形编码速度的关键是设计好的搜索方案( 与虚拟码 本的构成密切相关) ，这是分形图像编码实用化的核心问题。 混合分形编码。分形编码与其它编码方法( 如v q 、小波、神经网络等) 结合的混合编码方法已经显示出巨大的发展潜力【4 儿“】。分形编码技术已进入与其 它编码技术结合的新时代，国外许多学者都在积极寻找新的突破口。目前与分形 编码技术结合最为成功的，应该是v q 技术与小波技术。 应该指出，上述所列并没有涵盖分形图像编码的全部内容，例如另一类全新 的分形编码方法w f a t l 2 】( w e g i h t e df i n i t ea u t o m a t a ) 就没有提及。 1 4 本文的组织结构 第一章简要地介绍课题的研究背景，图像压缩的必要性和可能性，叙述了一些 经典的图像压缩方法，接着介绍了分形图像编码的概念及主要内容。 第二章介绍分形图像编码的数学基础，主要包括迭代函数系统、b a n a c h 不动 点定理和拼贴定理。 第三章介绍利用迭代函数系统理论来进行图像压缩编码的具体实现方法。 第四章分别介绍作者的两种加快分形图像编码的算法。 第五章介绍作者的一种加快分形解码的算法。 最后是总结与展望。 5 分形图像快速编码技术的算法研究 2 1引言 第2 章分形图像编码的数学基础 分形编码的数学基础 b j 【m 】主要包括迭代函数系统、压缩映射原理和拼贴定 理。迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 【5 】1 1 5 1 是b a m 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 df u n c t i o nt h e o r y ) 的基础上发 展起来的，它是分形几何的一个重要组成部分。压缩映射原理是泛函分析 1 6 j 中的 一个著名结果，是著名数学家b a n a e h 在总结前人结果的基础上于1 9 2 2 年提炼出 来的。拼贴定理是b a m s l e y 于2 0 世纪8 0 年代后期提出的，它是压缩映射原理的 一个简单推论，并成功地用于集合、函数( 包括信号、图像) 等的逼近。基于i f s 的分形图像编码可以获得极好的压缩性能，能够实现很高的压缩比，其实质是假 设现实图像具有自相似性( 分形的典型特征) 来实现图像数据压缩。从数学上看， 分形编码的原理是简单的，待编码图像由不动点定理保证可用接近它的压缩仿射 交换表示，压缩映射原理保证解码图像由压缩变换迭代作用于任意初始图像来生 成，拼贴定理则保证解码图像是待编码图像的近似图像。 尽管分形编码的原理从概念的观点上看是容易理解的，但是为了叙述严谨、 清晰，坚实可靠而明确的数学描述是绝对必要的。此外，要了解分形图像压缩技 术的起源，以及理解该技术的数学原理，分形的概念、度量空间及其压缩映射原 理和拼贴定理是必不可少的。分形理论( 核心是分形几何) 是非线性科学研究中 十分活跃的一个分支，特别是十余年来在计算机图像处理和分析中显示出越来越 重要的作用。 分形图像压缩编码是分形几何、泛函分析等现代数学分支最成功的应用之一。 这充分说明，一些复杂的数学理论，尽管难于理解，但往往能为图像处理等技术 提供意想不到的合理方法。 2 2 分形及分形空间 2 2 1 分形的定义 1 9 7 5 年，法国数学家m a n d e l b r o t 发表了几本分形专著，标志着“分形”作 为一门科学正式成立。分形及其理论涉及的领域非常广泛，其应用已经深入到许 多应用领域。分形理论的基础和主要内容是分形几何。分形几何的研究对象是理 论和现实中不规则的几何图形。例如：曲折的海岸线、多变的云彩图案、参差不 齐的金属表面乃至涨落无常的股价曲线等等这些经典几何对之束手无策的现象和 6 硕士学位论文 状态。这些均可用分形几何的加以描述、解释和研究。分形几何的核心的概念之 一就是分数维和局部与整体的对称性( 自相似性) 。分形集还为研究混沌动力系统 的“奇怪吸引子”提供了直观的几何语言。近十几年来，分形几何学已成为探讨 复杂和无序现象的强有力的数学工具，被各个学科分支中的学者们广泛地应用着， 它同孤立子理论、混沌理论一起被誉为二十世纪后期的非线性科学的三大理论突 破【1 7 】【l s 】【19 1 。 经典的欧式几何处理的都是相当规则和光滑的图形，并具有整数维数。但现 在，人们对以前认为是病态和例外的不规则图形产生了越来越浓厚的兴趣，分形 理论的兴起，恰好为研究这类问题提供了可能。一般说来，分形集具有以下的特 征【1 2 】： ( i ) 分形集都具有任意小尺度下的比例细节，或者说它具有精细的结构。 ( i i ) 分形集不能用传统的几何语言来描述，它既不是满足某些条件的点的轨 迹，也不是某些简单方程的解集。 ( ) 分形集具有某种自相似的形式，可能是近似的自相似或统计的自相似。 ( i v ) 一般情况下，分形维数大于它相应的拓扑维数。 ( v ) 在大多数令人感兴趣的情况下，分形集由非常简单的方法定义，可能以 变换的迭代产生。 对于各种不同的分形，有的可能同时具有上述的全部性质，有的可能只有( i ) - - ( v ) 中的大部分性质，而对某个性质有例外，但这并不影响我们把这个集合称为 分形。分数维是分形集的基本要素之，维数是分形图形最基本的不变量，是度 量分形集“不规则”程度的数量尺度。 2 2 2 分形空间 分形理论及其应用问题的研究，总是在一个假定的理想空间中进行的，一个 完备的度量空间常常能够满足我们的要求。 定义2 1一个度量空间( x ，d ) 是由一个空间或一个非空集合x ，以及其上的 一个实值函数d ：x x 寸r 组成，d 是定义在此空间上的度量，且具有如下性质： 1 ) d ( x ，y ) 0 , v x , y x 2 ) d ( x ，y ) = 0 ，当且仅当x = y ，v x ，y x 3 ) d ( x ，y ) = d ( y ，x ) ，v x ，y x 4 ) d ( x ，y ) + d ( y ，z ) d ( x ，z ) ，v x ，y ，z x 定义2 2 如果度量空间( x ，d ) 中所有的柯西序列都是收敛序列，则称( x ，d ) 为 完备度量空间。 定义2 3 设( ) ( ，d ) 为一完备度量空间，记为h ( x ) = s is 是x 的紧子集且s 妒。 给定b h ( x ) 及x x ，记d ( x ，b ) 为点x 到集合b 的距离，其定义为： 7 分形图像快速编码技术的算法研究 d ( x ，b ) = m i n d ( x ，y ) ly b ( 2 1 ) 定义2 4 设a ，b h ( x ) ，记d ( a ，b ) 是从集合a 到集合b 的距离： d ( a ，b ) = m a x d ( x ，b ) ix a ) ( 2 2 ) 由上面定义的距离，我们可以得到d ( a ，b ) d ( b ，a ) ，即不满足交换率。因此， 如上定义的距离不是h ( x ) 上的一个度量。我们定义h a u s d o r f f 距离如下。 定义2 5 设( x ，d ) 为一完备度量空间，a ，b s ( x ) ，记d h ( a ，b ) 为a 和b 的 h a u s d o r f f 距离，定义如下： “( a ，b ) = m a x d ( a ，b ) ，d ( b ，a ) ( 2 3 ) 根据这个定义，显然有 d h ( a ，b ) = d 。( b ，a )( 2 4 ) 定理2 ih a u s d o r f f 距离d 。是h ( x ) 上的一个度量，称为h a u s d o r f f 度量。因 此称( h ( x ) ，d h ) 为h a u s d o r f f 度量空间。 定理2 2 设( ) ( ，d ) 为一完备度量空间，则h a u s d o r f f 度量空间( h ( x ) ，d h ) 也是一 个完备度量空间。 分形空间就是由( h ( 均，d 。) 空间构成，对分形的讨论均在这个空间下进行。 综上所述，在实平面上r 2 定义了度量d 的完备度量空间( r 2 ，d ) 上的集合族组 成的定义了h a u s d o r f f 距离的空间( h ( r 2 ) ，d 。) 也是一个完备的度量空间。 在本文中，我们研究的图像就是定义在实平面上的点集，即是h ( r 2 ) 的一个元 素。因此，( h ( r 2 ) ，d 。) 就是图像存在的空间，并且是完备的。 2 3 仿射变换 定义2 6 设t 为n 维空间r 4 上的线性变换，o r 。，称变换w w ( x ) = t ( x ) + o ，v x r 。 ( 2 5 ) 为仿射变换。 一副图像是在实平面上的点集，所以我们研究仿射变换时主要研究实平面上 的仿射变换，即二维的( n = 2 时) 仿射变换。在二维的仿射变换中，设t 和o 具 有如下的形式： t = ， 则仿射变换写成如下形式： w ( 黛期+ ( 弘2 采用极坐标形式，进一步可表示为： w 陆妒r c o 髫s - s s i n 堋q y x ，1 + ( 匀 8 ( 2 6 ) ( 2 7 ) ( 2 8 ) 硕士学位论文 其中：r 、s 表示x ：b - 向、y ：y 向的缩放比例。 口、妒表示x 方向、y 方向的旋转角度。 e 、f 表示x 方向、y 方向的位置偏移量。 当r = s ，0 = 舻时，则为一相似变换。由此可见，仿射变换就是把原图进行缩放、 扭曲、平移和旋转。 2 。4 压缩映射及其不动点 定义2 7 设( ) 【，d ) 为一完备度量空间，m 为定义在其上的一个映射( 仿射变 换) ，如果有0 s 收敛到x 。 定理2 4 设c o ：x 斗x 是度量空间( ) 【，d ) 上的一个压缩映射，压缩因子为s ； ( h ( x ) ，d h ) 是由x 的非空紧集构成的h a u s d o r f f 空间，d h 为h a u s d o r f f 度量。则下面 定义的映射：h ( x ) 专h ( x ) 是( h ( x ) ，d h ) 上的压缩映射，压缩因子也为s ： c o ( b ) = 国( x ) ：x e b ) ，v b h ( ) ( ) ( 2 1 0 ) 定理2 5 设 c o n ：n = 1 , 2 ，n ，是( h ( ) ( ) d h ) 上的一组压缩映射，对每个n ，瓯的 压缩因子为s 。，定义w ：h ( x ) 寸h ( x ) ， w ( b ) = q ( b ) u 彩2 ( b ) u u m n ( b ) ，峙，b h ( x ) ( 2 1 1 ) 则w ：n ( x ) = - 9 h ( x ) 是一个压缩映射，压缩因子s = m a x s 。：n = 1 , 2 ，n ) 。 2 5 迭代函数系统( i f s ) 、吸引子、拼贴定理 定义2 8迭代函数系是完备度量空间( ) ( ，d ) 上的一组有限的压缩映射 吼：x 寸x ，n = 1 ，2 ，n ，每个压缩映射铭的压缩因子是s 。，常用i f s 来表示迭代 函数系( i t e r a t e d f u n c t i o ns y s t e m ) ，记为 x ；o 。，n = 1 , 2 ，n ) 。 定理2 6 设 x ；c o n ，1 1 = 1 , 2 ，n ) 是一个迭代函数系，压缩因子为s 。则由下式 定义的变换w ：h ( x ) 斗h ( x ) 是完备度量空间h ( x ) 上的一个压缩映射，压缩因子是 s ： w ( b ) = c o l ( b ) u 国2 ( b ) u u n ( b ) ，v b h ( x ) ( 2 1 2 ) 即对所有的b ，c h ( x ) ，有 d h ( w ( b ) ，w ( c ) ) s d h ( b ，c ) ( 2 1 3 ) 且w 有不变集，记为a h ( ) ( ) ，使下式 9 分形图像快速编码技术的算法研究 a = w ( a ) = v 。( a ) ( 2 1 4 ) 成立。并且对于任意一个b h ( x ) ，有 a = l i m w “( b )( 2 1 5 ) 成立。 定义2 9 定理2 6 中的不变集a 称为迭代函数系 x ；c o 。，n = 1 ，2 ，n ) 的吸引 子。迭代函数系的吸引子常常被看作“确定性分形”。 定理2 7 ( 拼贴定理) 设( x ，d ) 为一完备度量空间，给定l h ( x ) 与占0 。 选取一个具有压缩因子s ：0 s 1 的迭代函数系 x ；o n ，n = 1 , 2 ，n ) ，使得 d h ( l ，蓦珊n ( l ) ) 占 ( 2 1 6 ) 则 d h ( l ，a ) 击 ( 2 1 7 ) 其中a 是迭代函数系 x ；o ) n ，1 1 = 1 , 2 ，n ) 的吸引子。 证明：根据度量的连续性，我们有 d h ( l ，a ) = d h ( l ，熙w 4 ( l ) ) _ 。l i + m 。d n ( l ，w “( l ) ) l i n l d h ( l ，w ( l ) ) + d