（计算机软件与理论专业论文）几种图像编码算法的研究与改进.pdf

大连理工大学硕士学位论文 摘要 分形图像压缩方法是近十几年发展起来的一种新型图像压缩算法，其思想主要来源 于分形图像可以用迭代函数系( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 生成。现实生活中的图像 都存在某种自相似性，只要能够找到表示编码图像的一组仿射变换，原始图像用仿射变 换得到的不动点来表示，便实现了原始图像的压缩。分形图像压缩文件中存储的是仿射 变换参数的量化值而不是图像本身的像素值，从而实现图像数据的高倍压缩。 本文针对分形图像压缩算法压缩比较低、编码时间过长等问题，做了以下几方面的 工作： 首先，提出了一种基于匹配误差阈值的分形图像编码算法。该算法设置了两个剔除 条件，用来减少码书容量；然后在搜索最佳匹配块时设置一个匹配阂值来加快编码的速 度，同时取消了大多数文献所提到的等距变换；因为等距变换的引入徒增了计算的复杂 性，相同甚至更好的图像质量可以通过减小生成定义域块( d 块) 的步长来达到。实验结 果表明，该算法能够大大缩短编码时间，同时实现和全搜索分形编码算法相同甚至更好 的解码图像质量。 其次，以传统的四叉树分割和固定块分割为基础，提出了一种基于四叉树分割和方 差排序的有效的编码算法。初始时，用四叉树分割方案将原始图像分割为一系列大小为 3 2 x 3 2 的值域块。对于每一个大于4 x 4 的值域块，我们用无搜索方案来计算它的拼贴误 差；如果拼贴误差不满足条件，也就是e ( r ，d ) t ，那么我们需要用四叉树分割方案将 该值域块分割为4 个相同的子块并分别处理，如果子块大小大于4 x 4 ，我们仍然用无搜 索算法计算它的拼贴误差，否则，我们就在事先定义的定义域块池中搜索最佳匹配块。 实验结果证明了方法的有效性。 最后，介绍了当前流行的基于小波的图像编码算法，详细的描述了基于小波的 s p i - i t 编码算法。同时，提出了一种改进的s p i h t 算法，与s p i t t t 不同的是，该算法 初始化时总是以固定的点填充l i p 和l i s 链表，保证了系数扫描的准确性与完整性。实 验结果表明该算法的性能较传统s p i h t 相比有一定的提高。 关键词：分形；图像压缩；迭代函数系统；仿射变换；小波变换 大连理工大学硕士学位论文 r e s e a r c ha n di m p r o v e m e n to fs e v e r a li m a g ee n c o d i n gm e t h o d s a b s t r a c t f r a c t a li m a g ec o m p r e s s i o n ( f i c ) i sd e v e l o p e di nt h el a s t1 0y e a r sa n dt a k e sa d v a n t a g eo f s e l f - s i m i l a r i t i e sw h i c he x i s ti nt h ei m a g e sc o m m o n l y t h e r ei sac e r t a i nk i n do f s e l f - s i m i l a r i t y i nn a t u r a li m a g e s f r a c t a li m a g ec o m p r e s s i o nc a nb ea c h i e v e ds ol o n ga sag r o u po fa f f m e t r a n s f o r m a t i o nw h o s ef i x e dp o i n ti st h ea 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 ei sf o u n d f i c r e a l i z eh i 【g hc o m p r e s s i o nr a t i ob e c a u s et h ec o d ec o n s i s t so fp a r a m e t e r so ft h ei t e r a t e df u n c t i o n s y s t e m si n s t e a do ft h ep i x e l so ft h ei m a g e f i eb e c a m eah o tr e s e a r c hi nt h ef i e l do fi m a g e c o m p r e s s i o ne n c o d i n g b a s e do nf r a c t a la n dw a v e l e tt h e o r y , t h ef o l l o w i n gw o r k sa r ed o n ei no r d e rt oi m p r o v e t h ec o m p r e s s i o nr a t i oa n dr e d u c et h eh u g ee n c o d i n gt i m eo ff r a c t a li m a g ec o m p r e s s i o na n d i m p r o v e dt h ei m a g eq u a l i t yo fw a v e l e ti m a g ec o m p r e s s i o n ： f i r s t l y , t h i sp a p e rp r o p o s e saf r a c t a li m a g ee n c o d i n ga l g o r i t h mb a s e do nm a t c h i n ge r r o r t h r e s h o l d f i r s tt h ea u t h o r ss e tu pt w ok i c k - o u tc o n d i t i o n st or e d u c et h ec a p a c i t yo ft h e c o d c b o o k ，a n dt h e ns e tu pam a t c h i n gt h r e s h o l dw h e ns e a r c h i n gt h eb e s tm a t c h i n gb l o c k s ， w h i c hc a l ls h o r t e ni t sr u n t i m eg r e a t l y m e a n w h i l e ，t h ea u t h o r sd i s c a r dt h ei s o m e t r i c t r a n s f o r m a t i o n st h a tm e n t i o n e di nm o s tl i t e r a t u r e s ，b e c a u s et h eu s a g eo ft h ei s o m e t r i c t r a n s f o r m a t i o n so n l yi n c r e a s et h ec o m p u t a t i o n a lc o m p l e x i t y , t h es a m eo re v e nb e t t e r r e c o n s t r u c t e di m a g ec a l la c h i e v et h r o u g hr e d u c i n gt h es l i d i n gs t e po fp r o d u c i n gd o m a i n b l o c k s e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mc a nb o t hs h o r t e nt h e e n c o d i n g t i m eg r e a t l ya n da c h i e v et h es a m eo rb e t t e rr e c o n s t r u c t e di m a g eq u a l i t ya sc o m p a r e d w i t ht h eb a s i cf r a c t a le n c o d i n ga l g o r i t h mw i t hf u l ls e a r c h s e c o n d l y , w eh a v ep r e s e n t e daf r a c t a li m a g ec o d i n ga l g o r i t h mb a s e dq u a d t r e ep a r t i t i o n a n dv a r i a n c es o r t i n g i n i t i a l l yt h eo r i g i n a li m a g ei sp a r t i t i o n e di n t oas e to fr a n g eb l o c k sw i t h s i z eo f3 2 x 3 2u s i n gq u a d t r e es c h e m e f o re a c hr a n g eb l o c kw i t hs i z el a r g e rt h a n4 x 4 ，w eu s e n os e a r c hs c h e m et oc o m p u t ei t sc o l l a g ee i t o r i ft h ec o l l a g ee r r o ri su n a c c e p t a b l e ，le e ( r ，d ) t ，t h e nw ep a r t i t i o nt h i sr a n g eb l o c ki n t of o u ri d e n t i c a ls q u a r es u b b l o c k s i ft h e s i z eo ft h es u b b l o c k si sl a r g e rt h a n4 x 4 ，t h e nw ea l s ou s en os e a r c hs c h e m et oc o m p u t ei t s c o l l a g ee r r o r ，e l s ew es e a r c ht h eb e s tm a t c h e dd o m a i nb l o c kf r o mt h ed o m a i np 0 0 1 e x p e r i m e n t a lr e s u l t ss h o wt h ep r o p o s e da l g o r i t h mi s ab e t t e rc h o i c et h a ns o m eo t h e r a l g o r i t h m s f i n a l l y , w ei n t r o d u c eap o p u l a ri m a g ec o d i n gm e t h o db a s e dw a v e l e tt r a n s f o r m ，a n d d e p i c tt h es p i h t ( s e tp a r t i t i o n i n gi nh i e r a c h i c a lt r e e ) a l g o r i t h mi nd e t a i l a tt h es a m et i m e ， 几种图像编码算法的研究与改进 w ep r o p o s eai m p r o v e ds p i h t a l g o r i t h m b ed i f f e r e n tw i t hs p i h ta l g o r i t h m ，t h ep r o p o s e d s c h e m ea l w a y ss e tl i pa n dl i sw i t ht h ef i x e dp i x e l s ，w h i c hm a k ea l lt h ec o e f f i c i e n t sb e s c a n n e d e x p e r m e n t a lr e s u l t ss h o wt h a t t h ei m p r o v e ds p i h tc a ne x c e e dt h et r a d i t i o n a l s p i h tw h e nt h eb i tr a t ei sl e s st h a n1 k e yw 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 ；i t e r a t e df u n c t i o ns y s t e m ；a f f i n et r a n s f o r m ： w a v e l e tt r a n s f o l 加 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： ! 型敛因鱼编塑薹i 幺鱼堑歪盘刍丝丝 作者签名：纽童受。日期：迎堡年一上乙月上丘日 大连理下大学顾卜研究生学位论文 大连理工大学学位论文版权使用授权书 本入完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理工大学硕七学位论文 引言 人们所获得的外界知识中约有7 5 以上的信息来自于视觉，很多情况下图像所承载 的信息比任何其他形式的信息都更真切、更丰富，获取也更便捷。然而，数字化图像具 有极大的数据量，这对图像存储和传输很不利，阻碍了人们对图像的有效获取和使用。 因此，面对数据量巨大的数字化图像的传输、存储、处理和交换等问题，图像压缩编码 成为当今的一个重要研究课题1 1 3 1 。 2 0 世纪末期，分形理论的迅速发展，为图像编码注入了新的活力。目前，分形图像 编码以其新颖的思想、高压缩比、分辨率无关性等优点受到技术界广泛关注，是公认的 三种最有前途的新一代图像压缩编码技术之一1 2 1 。但是，基本分形图像压缩算法走向实 用化的巨大障碍是复杂的匹配搜索和解码图像存在的方块效应。国内外的许多学者针对 算法的缺陷提出了一些改进方法，改进方向主要包括加快编解码速度、提高解码图像质 量和压缩比。加快编解码速度的改进方法主要是缩小值域块的搜索范围，主要包括分类 法【删、邻域法【弘1 、无搜索方法1 1 2 1 5 l 等；提高解码图像质量的改进方法主要有寻找更合 理的值域块分割方法i 搏1 9 l 、与其他编码方法结合的混合编码1 2 0 - 2 4 j 等；提高压缩比的改进 方法主要是选择更有效的参数量化和熵编码算法 1 7 , 1 9 。 然而，分形编码技术是不对称的，尽管分形解码已经足够快了，分形编码也有着很 高的压缩比，但因其编码非常耗时，导致其一直难以实际应用。为此，技术界在如何加 快分形编码速度方面进行了广泛深入的研究。 本文在前人的基础上，以非线性理论中的分形理论和数学中的离散小波变换为基 础，采用阈值剔除、方差排序等方法对分形图像压缩过程中降低搜索时问、提高图像压 缩比等方面进行了研究。 几种图像编码算法的研究与改进 1 绪论 1 1 课题研究的背景 自2 0 世纪8 0 年代以来，计算机在各行各业和社会生活的各个方面得到了广泛的应 用，并己广泛应用于数据处理与数据通信，尽管大容量设备和宽带网络技术的不断发展， 但是仍然难以适用快速发展的现代多媒体技术。多媒体技术就是指用计算机综合处理文 字、声音、图形、图像等多种媒体上承载的信息，图像是其中最主要的信息载体。而图 像数据的传输常常要占用很大的带宽，需要很大的存储空间，因而怎样对图像数据进行 行之有效地传输和存储是一个极具挑战性的课题。所以面对如何降低传输成本，增加数 据传输的可靠性，不断满足人们对信息传输的需求，图像压缩就显得具有十分重要的作 用。为了解决好这个问题，我们就必须对图像进行编码压缩，在保证一定图像质量的前 提下，有效地减少存储和传输时所需的数据量和占用的频带。 2 0 世纪8 0 年代后期和9 0 年代初，结合人类的视觉生理特性和心理特性、模式识别、 计算机视觉、神经网络、小波分析和分形几何学等理论，人们开始探索图像压缩的新途 径，被称为第二代图像编码技术。其中，分形图像编码技术以其新颖的思想、高压缩比、 分辨率无关性和快速解码等优点受到技术界的广泛关注。然而，分形编码技术是不对称 的，尽管分形解码己经足够快了，分形编码也有着很高的压缩比，但因其编码非常耗时， 导致其一直难以实际应用。为此，技术界在如何加快分形编码速度方面进行了广泛深入 的研究。纵观大量分形图像编码文献，在提高编码质量和加快分形编码速度等方面，许 多新观点和大量改进算法被提出，对它们进行准确的分类是困难的。但总的来说，大多 数现有分形编码文献都是围绕下面的基本问题展丌的，或者说大多数分形编码方案的区 别主要反映在这些方面图像分割虚拟码本构成变换参数的量化、比特分配与熵编码基础 理论研究加快编码过程混合分形编码。分形编码与其它编码方法如：小波、神经网络等 结合的混合编码方法已经显示出巨大的发展潜力。分形编码技术已进入与其它编码技术 结合的新时代，国外许多学者都在积极寻找新的突破口。目前与分形编码技术结合最为 成功的，应该是矢量量化技术( v q ) 与小波技术( w a v e l e t ) 。 1 2 图像压缩编码 1 2 1图像压缩编码的基本概念 图像压缩编码的目的是以尽量少的比特数表征图像，同时尽量保持复原图像的质 量，使它符合预定应用场合的要求，通常把图像压缩编码简称为图像编码。 大连理工大学硕士学位论文 图像数据压缩的可能性在于图像中的像素之间，行之间和帧之间都存在着较强的相 关性，即某一个像素的灰度值总和其周围其他像素灰度值有某种关系，应用某种编码方 法提取并减少这些相关性，就是减少图像信息中无用的冗余信息，达到数据量压缩，实 现保持编码。图像信息的信宿接收器往往是人的视觉系统，它的灰度和空间分辨率是有 限的。一般的记录和显示设备接受信息量的程度也受本身的限制。许多应用方面，可以 只对图像中的某些有用的特征信息进行特征抽取编码。 1 2 2 图像压缩编码的分类 图像压缩编码的目的在于用尽量少的数据表示原始数据，因此，在压缩当中或多或 少的会损失一些数据，基于此，我们将其分为可逆的压缩与不可逆压缩。可逆压缩又叫 无损压缩，不可逆压缩又叫做有损压缩，本文介绍的分形图像压缩算法是不可逆的，属 于有损压缩。 1 2 3 图像压缩编码的基本方法 图像压缩编码的方法很多，其基本技术的发展可分为两个阶段，即第一代图像编码 技术和第二代图像编码技术。 第一代图像编码技术是以香农的信息论为基础，并充分考虑了图像信源的统计特 性，根据其核心技术的不同又分为预测编码、变换编码和统计编码。 预测编码：指只对新的信息进行编码，从而去掉相邻像素之间的相关性和冗余性。 常用的方法有增量调制( 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 l p 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 ) 都属于统计编码。 第二代图像编码技术不再局限于香农的信息论框架，它充分地利用人眼的视觉生理 特性和图像信源的各种特征，以获得更高的压缩比和主观满意度。第二代图像编码技术 主要分为两类。 考虑人眼视觉特性的方法：基于方向滤波的图像编码方法、基于图像轮廓一纹理的 编码方法。 考虑图像景物特征的方法：分形编码方法、基于模型的编码方法等。 几种图像编码算法的研究与改进 1 3 分形图像压缩编码 1 3 1概论 分形图像编码是一个相对较新的图像压缩技术，它利用自然图像中不同区域间存在 的跨尺度自相似性、把现实图像建模为分形体来实现图像压缩的。它源于b a m s l e y 及其 研究小组对迭代函数系统的研究和提出的分形块编码。目前，分形图像编码以其新颖的 思想、高压缩比、分辨率无关性等优点受到技术界广泛关注，是目前公认的三种最有前 途的新一代图像编码技术之一。 2 0 世纪8 0 年代末期，b a m s l e y 及其研究小组公布了使用分形压缩图像数据的思想。 这是一种图像编码的全新思想：自然图像都包含有许多复杂的类似于分形的物体，一种 编码图形图像的有效方式是设法把这些物体描述为分形，而不是以“光滑”的方式近似 它们。其数学原理是，一幅图像用使图像近似不变的压缩仿射变换( 由一组刻画局部自 相似性的压缩仿射变换组成，即迭代函数系统) 的量化参数来表达，只需储存压缩变换 的量化参数而不是整幅图像，而存储仿射变换量化参数的比特数大大低于储存原始图像 的比特数，因此实现了图像数据的高倍压缩”解码是新颖的快速迭代过程，表达图像的 变换是压缩的，不动点定理保证变换的不动图像是存在唯一的，且可以从任何初始图像 迭代生成。 然而，如何寻求一个不动点图像是原始图像较好逼近的压缩仿射变换? 这是分形图 像编码技术最基本的问题。b a n a c h 不动点定理并没有提供现成的解法，一个次优的解决 途径是借助于拼贴定理：只要压缩变换使图像从近似不变( 即砟) ，变换不 动点就是图像心，2 的一个近似图像。于是，原始图像心喈近似等于t ( ) ，n 是迭代次 数一般n 1 0 。除此之外，在具体寻求压缩变换的方式上，目前有两种方法，一种b a m s l e y 方法，另一种是j a c q u i n 方法。b a m s l e y 方法的编码时间太长，需要人机交互，对操作 者有较高要求。因此，j a c q u i n 方法受到更多的关注。 1 3 2 分形编码的主要内容 纵观大量分形图像编码文献，在提高编码质量和加快分形编码等方面，许多新观点 和大量改进算法被提出，对它们进行准确的分类是困难的。但总的来说，大多数现有分 形编码文献都是围绕下面的基本问题展开的，或者说大多数分形编码方案的区别主要反 应在下列几方面： ( 1 ) 图像分割。对图像的分割目前主要有以下几种固定块分割，四叉树分割，水平 垂直分割，不规则分块。尽管固定方块分割方案实现简单，也有分割方案占有零信息量 大连理丁大学硕士学何论文 的优点即无需存储或传输分割信息，但编码质量不理想，不能自适应于不同的图像，也 不能自适应于同一图像的不同细节。四叉树分割方案虽然有一定的图像适应性，且描述 四叉树分割的成本也很小，但它对图像的适应性仍然是有限的。水平垂直分割和不规则 分割对图像重建较好，但复杂度较高。因此，研究一种更强的自适应分割方案是一个重 要的问题。 ( 2 ) 虚拟码本构成。合适的虚拟码本对编码时间和编码质量都有很大影响，码本越 大，搜索时的耗时就越严重，但信噪比就越高反之则信噪比越低。还有，码本越大，记 录最佳匹配块的位置所需的比特数也就越多。因此，如何构建码本也是一个很重要的问 题。 ( 3 ) 变换参数的量化、比特分配与熵编码。在分形编码中，一幅图像是用使图像近 似不变的压缩变换来表达的，而变换又是由表达它的参数确定的。为了进一步实现图像 数据的压缩，表达变换的亮度调整参数和亮度偏移参数必须进行量化处理，并对量化参 数进行合理的比特分配。此外，熵编码可进一步改进分形编码的效率。 ( 4 ) 基础理论研究。迭代函数系统逆问题的研究是其核心问题，尽管人们已尝试各 种方法解决这个问题，但目前仍然不甚理想。我们知道，压缩图像的分形文件就是一个 压缩变换的描述，对于如何寻求这样的压缩变换，拼贴定理是目前依据的理论基础。但 是，拼贴定理只是给重构误差提供一个上界体现为所谓的拼贴误差，这个上界极小化并 不意味着重构误差的极小化。因此，目前的分形编码方案远不是最优的。当然，相关的 基础理论问题并不止这个逆问题，例如，更好的数学框架、解码收敛性、解码误差控制 以及分形编码机理等的研究。 ( 5 ) 加快编码过程。这主要涉及匹配搜索问题，因为在分形编码阶段，匹配搜索占 据了主要的编码时间。全搜索固然能够得到最好的编码质量，但全搜索的运算量大是不 争的事实。加快分形编码速度的关键是设计好的搜索方案与虚拟码本的构成密切相关， 这是分形图像编码实用化的核心问题。 ( 6 ) 混合分形编码。分形编码与其它编码方法( 如v q 、小波、神经网络等) 结合的 混合编码方法己经显示出巨大的发展潜力。分形编码技术已进入与其它编码技术结合的 新时代，国外许多学者都在积极寻找新的突破口。目前与分形编码技术结合最为成功的， 应该是v q 技术与小波技术。 1 4 本文的组织与结构 第一章简要地介绍课题的研究背景，图像压缩的必要性和可能性以及叙述了图像压 缩类型，接着介绍了分形图像编码的概念及主要内容。 几种图像编码算法的研究与改进 第二章介绍分形图像编码的数学基础，主要包括迭代函数系统、b a n a c h 不动点定理 和拼贴定理，以及介绍利用迭代函数系统理论构造分形集的具体实现方法 第三章介绍了传统的j a c q u i n 的分形图像压缩方法的编解码流程。 第四章，第五章分别介绍作者利用分类的思想进行分形图像压缩，其中第四章是基 于匹配误差阈值的分形图像编码算法，第五章是采用四叉树分割和方差排序的思想来进 行图像压缩。 第六章介绍了一种基于小波变换的改进的s p i h t 算法。 最后是总结与展望。 一6 一 大连理丁人学硕十学位论文 分形编码的数学基础 2 1 引言 迭代函数系统、不动点理论以及拼贴定理是分形编码的主要数学基础。迭代函数系 统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 2 5 】是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 df u n c t i o nt h e o r y ) 1 2 6 】的基础上发展起来的，它是分形几何的重 要组成部分。不动点理论是泛函分析的重要分支阢2 8 1 。拼贴定理【2 5 】是b a n a c h 不动点定 理的简单推论，并成功地用于集合、函数( 包括信号、图像) 等的逼近。 基于i f s 的分形图像编码可以获得极好的压缩性能1 2 9 , 3 0 】，能够实现很高的压缩比， 其实质是假设现实图像具有自相似性( 分形的典型特征) 来实现图像数据压缩的。尽管从 概念的观点上看，分形编码原理是容易理解的，但是为了叙述严谨、清晰，坚实可靠而 明确的数学描述是绝对必要的【3 l 】。此外，要了解分形编码技术的起源，以及理解该技术 的工作原理，分形的概念、度量空间、不动点理论和拼贴定理是必不可少的。 总之，分形图像编码是分形几何、泛函分析等现代数学分支最成功的应用之一。这 充分说明，一些复杂的数学理论，尽管难于理解，但往往能为图像处理等技术提供意想 不到的合理方法。 2 2度量空间 对于分形图像编码来说，度量空间的概念是必不可少的，还要涉及一些集合论、拓 扑学、动力系统等数学分支的基本概念。此外，在分形图像编码框架内，图像被看成是 h i l b e r t 空间的向量 3 2 , 3 3 】，其度量由内积通过范数诱导出来。不过，在短短的篇幅里面面 俱到是不可能的，也是不必要的。因此，我们对这些数学概念作个简短介绍，许多细节 可以参考有关的数学书籍。 2 2 1 度量 极限是分析数学中基本概念之一。序列( 数列、函数列等) 的许多收敛概念，都可以 统一在度量空间中按度量收敛的概念之中。这样的处理，使我们有可能更容易认识那些 乍看似乎毫无关系的极限过程的本质联系。此外，度量概念也可以使不确切的“接近”、 “逼近”等说法精确化。 定义2 1设x 是一个非空集合。函数d ：x x r 称为x 上的一个度量( 亦称距 离，如果它满足下面的三条叟量公理： 正定性：d ( x 川20 ，且d ( x y ) = 0 铮z = 少，v x ，x ； 几种图像编码算法的研究与改进 对称性：d ( x ，y ) = d ( y ，x ) ，v x j y x ； 三角不等式：d ( x ，y ) d ( x ，z ) + d ( z ，y ) ，v x ，y ，z x 。 引进了度量d 的非空集合x ，称为度量空间，记为( x ，d ) 。 定义2 2 点列 矗) cx 称为在度量空间( x ，d ) 中收敛于x x ，如果对于任意 占 0 ，存在自然数，使得对所有的力 n ，有 d ( x 。，x ) 0 ，3 n 0 ，甩，m njd ( 矗，靠) 0 ，x x ，我们称 b ( x ，) = yd ( x ，y ) ，y x 为以x 为心、，为半径的开球。 定义2 7( x ，d ) 为度量空间，4 是x 的点集。 设x a ，如果存在一个丌球b ( x ，) ca ，刃f z , 称点z 是点集爿的内点。 若点集4 的所有点都是内点，则称么为歼集。空集规定为开集。 若点集爿的补集x 一4 为开集，则称a 是闭集。 定理2 1度量空间中的点集4 为闭集的充分必要条件是4 中任意收敛点列必收敛 于4 中的点。即闭集关于极限运算是封闭的，这也许是“闭集的由来。有了开集的概 念，现在我们就可以定义度量空间中点的邻域概念了。 定义2 8如果x 是度量空间，x 是x 一个任意的点，则任意一个包含有x 的开集 称为x 的邻域。 下面引入映射连续性的这一重要概念它是通常函数连续性的自然推广。 定义2 9 设x 和l ，是两个度量空间，f ：x l ，是任意映射。称厂在x x 是连续 大连理下大学硕十学位论文 定义2 9 设x 和y 是两个度量空间，厂：x 呻y 是任意映射。称厂在x ex 是连续 的，如果对f ( x ) 的任何邻域y ，存在z 的邻域u ，使得对所有的z e u ，都有f ( z ) e v 。 若映射f ( x 1 在a cx 中的每个点连续，则称它在a 上是连续的。当l ，是实数直线 或复数平面时，称，o ) 为连续函数。 定理2 2 设x 和y 是两个度量空间，映射f ：x y 在x e x 连续的充分必要条件 是对任何收敛于x 的序列瓴 cx ，序y u f 瓴) ) 收敛于厂g ) 。 最后定义点到点集的距离。在分形图像编码理论中，这是一个重要的概念。 定义2 1 0 设度量空间( x ，d ) ，x e x ，acx ，我们把x 到彳的距离定义为 d i s t ( x ，4 ) 1i n f d o ，) ，) iye a 。 ( 2 ) 紧性 “紧性一是拓扑空间的一个重要概念，是化“无限为“有限”的极为有用的性质。 定义2 1 l 设( x ，d ) 是度量空间，4 是x 的子集称为紧的，如果4 包含在任何开集 族似) 目的并集之中，则族中存在有限个开集4 ，4 ，氏，使得4 c u ，以。 简言之，称4 是紧集，如果4 的每个开覆盖具有有限子覆盖。紧性还有另外的等价 刻画，这里不加证明地给出其中的一个。 定理2 3 完备度量空间( x ，d ) 中的子集4 是紧集，当且仅当下列条件成立：j a 是闭的； a 中每个点列都有收敛子点列收敛于a 中的一点。 由这个定理立即得出下面结论，它在后面要用到。 定理2 4 设x 和l ，是两个度量空间，厂：x y 是连续映射，则对x 中的任意紧 集a ，似) = f ( x ) l x a 是y 中的紧集。简言之，连续映射保持紧性不变。 2 2 4 不动点定理 一些方程的求解问题常常可以化为求映射的不动点，并用迭代法求不动点，这是计 算数学等数学分支中一个很重要的方法，在不同领域中都有重要应用。1 9 2 2 年，b a n a c h 把这个方法的基本点提炼出来，用度量空间以及其中的压缩映射的一些基本概念更一般 地描述了这个方法。目前，不动点原理的应用远不止求方程的近似解，已经有了许多意 想不到的应用。分形编码就是其应用最成功的例子之一。 定义2 1 2 度量空间( x ，d ) 上的映射丁称为压缩的，如果存在a 【0 ，1 ) ，使得 a ( r x ，7 ) ，) s a d ( x ，y ) ，协，y x 几种图像编码算法的研究与改进 其中，1 2 称为映射丁的压缩因子( c o n t r a c t i v i t yf a c t o r ) 。 一个压缩映射总是缩短任意两点的映像之间的距离。映射z 的不动点x 是指满足 t x 一工的点，即在r 作用下“不动一的点。 定理2 5 ( b a n a c h 不动点定理或压缩映象原理) 1 2 7 1 设( x ，d ) 是一个完备度量空间， r ：x 呻x 是压缩因子为口e o ，1 ) 的压缩映射，则z 存在唯一不动点k ，且 l i l i m t 。z = l i r a t ( t ”k ) ，v x e x 。 ( 2 1 ) - _ 换言之，完备度量空间中压缩映射r 的不动点存在唯一，且可以由映射对任意初始 点的反复迭代逼近到任意精度。 我们知道，分形图像解码基于压缩映象原理，为了保证解码迭代收敛，表达图像的 分形变换一般被要求是压缩的。但是，实验结果表咧蚓，压缩因子可以增大到1 5 ，可 见在分形图像编码中压缩性也仅仅是充分条件。分形编码文献常常用“最终压缩修 ( e v e n t u a lc o n t r a c t i v i t y ) 的概念来解释这个现象。映射r 是最终压缩的，是指对某个正整 数肌，映射t m 是压缩的。这个术语常出现在分形编码文献中。 最终压缩映射有下面的熟知性质。 推论设( x ，d ) 是一个完备度量空间，映射t ：x x 。如果存在一个正整数所， 使z 。是压缩的，则r 存在唯一不动点k ，并成立式( 2 1 ) 。 2 2 5 拼贴定理 b a n a c h 不动点定理表明，完备度量空问中的映射，只要是压缩的，它的不动点就存 在且唯一，并可以由映射对任意仞始点的反复迭代逼近到任意精度。然而，在分形图像 编码中，必须解决其逆问题：给定一个点，寻求一个压缩变换，使它的不动点就是给定 点。这是一个非常困难但极具挑战性的问题，至今尚未得到理想的解决。下面介绍的拼 贴定理是对这个问题的部分回答。考虑到在泛函分析书中找不到拼贴定理，我们给出其 详细证明。 引理2 1 设( x ，d ) 是度量空间。对于固定的a x ，函数e 0 ) 一d o ，a ) 是连续的。 证明由三角不等式及对称性得到。 定理2 6 ( 拼贴定理)设( x ，d ) 是一个完备度量空间，t ：x _ x 是压缩因子为 a 【o ，1 ) 的压缩映射，则r 的不动点瓦满足 d o ，屯) s 击m 吼坛x 。 火连理t 大学硕十学位论文 证明：根据度量的连续性( 引理2 1 ) ，我们有 d 忱，z 。j d 何，l l m = f ”j 【) = l i m d ( x ，t ”工) n 一 n + s ! i m d ( x ，r x ) + d ( r x ，t 2 彳) + + d ( 丁”工，t ”工) 。- - 1 1 c i o 一 ， s l i m d o ，r x ) + a d o ，r x ) - i - - i - 口”1 a ( x ，r x ) = ! 璁1 1 - - 一o 口5 # d o ，a ) 一击d o ，a ) 拼贴定理告诉我们，在完备度量空间( x ，d ) 中，要找一个压缩变换使其不动点与某 个给定点相近或相似，即d ，瓦) 很小，只需在度量空间x 中找到一个压缩变换， 该变换使给定点近似不变，即d ，玩) 很小。于是定理2 6 把上述问题转换为“寻找 给定点与其映像接近的压缩映射的问题。因此，编码时只需极小化所谓的拼贴误差 d ，砜) 。解码则