（信号与信息处理专业论文）基于分形方法的图像匹配研究.pdf

基于分形方法的图像匹配研究摘要分形理论是现代数学与非线性科学研究中的一个十分活跃的分支。近年来，它在图像处理方面已获得了一系列的成功应用。特别是分形编码，它以简洁的迭代函数系统来表征图像，所以在图像压缩方面取得了很好的效果，同时，它也能应用到图像匹配中，本文在分析传统的灰度图像匹配的基础上提出几种基于分形方法的图像匹配。方法1 ：基于值域块参数对p ，l m s e ) 的图像匹配分形编码理论基于同一图像或不同图像之间的局部相似性。一个值域块的分形编码，一定会有一个定义域块( d ) 和最小均方误差( 脚一) 与之一一对应，从而得到描述此值域块的一组参数( d ，l m s e ) ，将此参数对作为图像匹配的参数特征进行匹配。待匹配图像分割为相同大小的值域块，然后将每一值域块按给定的定义域块进行分形编码，得到一组参数( b ，l m s e j ) ，进而求得整个图像的l m s e ，计算该l m s e 与此待匹配图像通过自身的分形编码求得的脚孵的欧氏距离，从而求得最佳的匹配图像。方法2 ：基于分形邻距( f l v d ) 的图像匹配分形邻距是针对经过分形编码的图像而定义的一种图像间相似性的测度方法。它具有分形编码的吸引子唯一不变性特点，因而对旋转、缩放、平移和光照都有不变性。在图像匹配中，把它作为图像相似性的度量标准。分别将匹配图像通过分形编码求得分形码，在解码的过程中，以待匹配图像作为解码的输入图像进行一次迭代，求得用以，从而得到最佳的匹配图像。关键词：分形编码；图像匹配；分形邻距；最小均方误差as t u d yo ni m a g em a t c h i n gb a s e do nf r a c t a lm e t h o da b s t r a c tf r a c t a lt h e o r yi sav e r ya c t i v eb r a n c hi nm o d e r nm a t h e m a t i c sa n dn o n - l i n e a ls c i e n c e i nt h el a s td e c a d e ，i th a sa c h i e v e dag r e a ts u c c e s si ni m a g ep r o c e s s i n g e s p e c i a l l yf r a c t a lc o d i n g ，w h i c hu s e sc o m p a c ti t e r a t i v ef u n c t i o ns y s t e m ( 傩) t od e n o t et h ei m a g e ，h a sag o o de f f e c to ni m a g ec o m p r e s s i o na sw e l la si m a g em a t c h i n g a f t e ra n a l y z i n ga n dc o m p a r i n gs e v e r a lt r a d i t i o n a lg r a y - m a t c h i n ga l g o r i t h m s ，t h i st h e s i sp r o p o s e ss e v e r a li m a g em a t c h i n gm e t h o d sb a s e do nf r a c t a lc o d i n g t h ef i r s tm e t h o d ：i m a g em a t c h i n gm e t h o db a s e do nap a i ro fp a r a m e t e r s( d ，l m s e ) o far a n g eb l o c k f r a c t a lc o d i n gt h e o r yi sb a s e do ns e l f s i m i l a r i t yo rm u t u a ls i m i l a r i t yo fi m a g e a sar a n g eb l o c k ，i tc a nb ed e s c r i b e db yag r o u po fp a r a m e t e r s ( ad o m a i nb l o c ka n d l m s e ) b yu s i n gt h ep a i ro fp a r a m e t e r sc o r r e s p o n d e n tt oar a n g eb l o c ka st h ei m a g em a t c h i n gc h a r a c t e r i s t i c ，an e wi m a g em a t c h i n gi si m p r o v e d t h em a t c h i n gi m a g ei sd i v i d e di n t or a n g eb l o c k sw i t ht h es a m es i z e ，t h e nt h er a n g eb l o c k sa r ec o d e di nt e r m so ft h ep r e s e td o m a i nb l o c k s ，w h i c hr e s u l t si nal m s e ta n dt h el m s eo ft h em a t c h i n gi m a g e a no p t i m a lm a t c h i n gi m a g ei so b t a i n e db yt h ee u c l i dd is t a n c eb e t w e e nt h ea b o v el m s ea n dt h el m s e gt h a tt h ed o m a i nb l o c k sf o u n db yi t s e l f t h es e c o n dm e t h o d ：i m a g em a t c h i n gm e t h o db a s e do nf r a c t a ln e i g h b o rd i s t a n c e ( f n d ) g i v e saq u a n t i t a t i v em e a s u r eo ft h ei n p u t l 。o u t p u tc h a r a c t e r is tic so ft h ef r a c t a lc o d eo ft h ee n c o d e di m a g e t h ef u n d a m e n t a lm e c h a n i s mb e h i n dt h i sm a t c h i n gl i e si nt h eu n i q u e n e s so ft h ea t t r a c t o ro faf r a c t a lc o d e ，t h ea t t r a c t o rh a st h ei n v a r i a n c et oi m a g et r a n s i a t i o n ，i i ir o t a t i o n ，s c a l i n ga n di l l u m i n a t i o n i t sp r o v e dt ob eas t a n d a r dt om e a s u r ei m a g es i m i l a r i t yi ni m a g em a t c h i n g w i t ht h eo b j e c ti m a g ea st h ei n p u ti m a g ew h il ed e c o d i n g ，w eg e tt h eo u t p u ti m a g ea f t e rt h ef i r s ti t e r a t i o no ft h ei f s t h e nc o m p a r et h i so u t p u ti m a g ew i t ht h ei n p u ti m a g eb yf n d i ，t h u sf i n dt h em o s to p t i m a lm a t c h i n gb l o c k k e yw o r d s ：f r a c t a lc o d i n g ：i m a g em a t c h i n g ：f n d ：l m s ei v独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含未获得( 洼! 垫遗直墓丝霞墨挂别直明煎：奎拦亘窒2 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：函f 坨彩签字日期：加g 年彳月多日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。( 保密的学位论文在解密后适用本授权书)学位论文作者签名：函化磊导师签字：签字日期：为0 8 年月日律毖签字e t 期：5 年占月日基于分形方法的图像匹配研究0 前言0 1 课题背景本论文以国家自然科学基金项目“中国海常见浮游植物细胞图像识别 作为支撑，从分形编码的角度对中国海常见浮游植物的几种细胞图像特征参数进行了研究，并将其应用到图像的匹配中，为进一步的图像识别奠定了基础。浮游植物是一个生态学概念，通常浮游植物就是指浮游藻类。海洋浮游植物指生活在海水中的浮游藻类。海洋浮游植物主要包括蓝藻门、硅藻门、金藻门、黄藻门、甲藻门、隐藻门和绿藻门等。通过历年来海洋物种生态分布调查【1 - 5 】，可以比较全面地了解我国海域浮游植物的分布情况，从而确定本文研究对象中国海常见浮游植物的具体范围。特别是近年来，海洋赤潮频繁爆发，对渔业生产及海洋生态环境产生了巨大的灾害性影响。在海洋赤潮监测及其发生发展规律的研究中，浮游植物种类的识别和数量调查是赤潮监测的基础，也是海洋生态环境研究和海洋调查的重要内容，对海洋环境保护、海洋渔业生产等多方面具有重要的科学研究和现实意义。0 2 分形的发展及应用长期以来，人们用以描述客观世界的几何学有欧几里德几何、解析几何、射影几何、微分几何等。它们能有效地对人为设计的规则形体进行描述。但随着人类的发展，人们逐渐感觉到用传统几何并不能包罗万象地描述大自然中所有的对象，如果仔细地观察周围的世界，可以随时随地的看到许多有趣的现象，例如生长的枝枝岔岔的树木，高低不平的山脉，弯弯曲曲的河流与海岸线，云烟，雪花等等，这些不规则体是难以用欧几里德几何学【6 】来描述的。直到2 0 世纪7 0 年代这一困惑多年的问题终于被美国数学家b e n o i tb m a n d e l b r o t 彻底解决 蝎】。以( c h a n c ea n dd i m e n s i o n 1 3 】为标志的分形理论诞生了。分形理论经历了三个阶段【7 1 。第一阶段是从1 8 2 7 年到1 9 2 5 年。在这一阶段，数学家们构造并且研究了种种奇异或病态的集合及其图像，而且试图对这类图像集合与经典几何的差别进基于分形方法的图像匹配研究行描述、分类和刻画，其中的一些后来被认为是典型的分形。如w e i e r s t r a s s 函数、k o c h 函数、c a n t o r 三分集、p e a n o 曲线。第二阶段大致从1 9 2 6 年到1 9 7 6 年。在这半个世纪里，人们对分形几何的性质作了深入地研究，p o n t r y a g i n 、b e s i c o v i c h 等研究了曲线的维数、分形集的局部性质、分形集的结构以及在几何测度论中的应用，他们的研究成果极大地丰富了分形几何理论。在这一阶段，l e v y 在这两方面的工作极其重要：第一，研究了自相似集；第二，建立了分数布朗运动理论，成为随机分形理论系统的重要先驱者之一。第三阶段为1 9 7 6 年至今，这是分形在各个领域的应用取得全面发展并形成独立学科的阶段。由于分形几何极强的应用性，它在物理的相位理论、材料的结构与控制、力学中的断裂、高分子链的聚合、自然图形的模拟、酶的生长等领域取得了令人瞩目的成果，于是有了后来的分形几何学。随着分形的发展，它的概念和思想被抽象成一种科学方法论，通过分析分形客体的部分和整体之间的自相似性，利用分形理论的思想和方法，从无序中发现有序，揭示杂乱、破碎、混沌等极不规则的复杂现象内部所蕴含的规律，使人们对它们之间关系的认识思维方式由线性进展到非线性阶段。分形，作为新兴科学，已被应用到自然科学与社会科学的许多领域，如数学、物理【8 】、化学、材料科学、医学、生物、地质、地理学、地震、天文学、力学、计算机科学乃至经济、社会、艺术等领域都有重要的应用价值。特别是在信息技术发展的今天它已成为计算机智能和非线性科学的研究热点之一。分形中可以用简单的迭代方法来描述复杂的自然景物，分数维能够有效度量物体的复杂性，因此分形与图像之间存在着一种自然联系，正是这种联系奠定了分形理论应用于图像处理的基础。分形理论在图像处理方面的应用主要集中在两方面【9 】：分形编码和分数维。1 9 8 7 年，美国g e o r g i a 理工学院的m f b a r n s l e y 提出了分形图像压缩【埘，为图像编码领域注入了新的活力。次年，他和a d s l o a n 将迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，简称i f s ) 应用到图像编码中，并获得了极好的压缩性斛1 1 】。这种编码方法突破以往熵编码的理论界限，新颖、有效，但这种方法在图像分割时需要人机交互，对操作者有较高的要求，无法实用，此方案在当时2基于分形方法的图像匹配研究并未引起太多的注意。1 9 9 0 年，m f b a r n s l e y 的博士生a e j a c q u i n 提出了一种基于方块划分的分形编码方法【1 2 1 ，即分块迭代函数系统( p a r t i t i o n e di t e r a t e df u n c t i o ns y s t e m ，p i f s ) 。分块迭代函数系统也是一个寻找仿射变换的过程，它利用图像分割成块之后的局部与局部的关系，去除图像d o m a i n 块与r a n g e 块之间的相关性进行压缩。这些操作都可以由计算机自动完成，它为分形图像编码的研究带来了一次质的飞跃。分形维数作为图像表面不规则程度的度量，不仅能度量复杂程度而且具有多尺度多分辨率变化的不变性，它与人类视觉对图像表面纹理粗糙度的感知是一致的，即分形维数越大，对应的图像表面越粗糙；反之，图像表面越光滑，因此，分形维数被用来作为纹理的一个重要特征而被用于纹理分割、纹理边缘检测等。分形，形之分也，物体形状、结构与形态的分割、分裂与分解o _ 分形是一个过程，是事物从整体向局部转化，认识从宏观向微观深化的过程。一旦人们把分形视为认识复杂事物的方法，分形及其度量定义的问题便可迎刃而解；自从人们把分形作为图像处理的重要工具之日起，就意味着图像处理领域变得更加广阔。0 3 论文的主要工作本文研究的对象主要是中国海常见浮游植物细胞图像【5 5 1 。这些细胞是利用“东方红 2 号调查船进行海上现场采样得到的，细胞图像是取样后通过实验室内n i k o ne 8 0 0 显微照相设备拍摄所得。灰度、形状、纹理等特征是进行图像匹配时通常使用的视觉特征。通过对大量的细胞图像观察发现，由于采集时细胞可能处于不同的生长期，则反映在图像上也是不同的；有的细胞以壳面观的形式展现，有时以侧面观的形式展现；可能在同一属或同一科下的两种不同的细胞非常相似。如图0 1 所示，细胞不同拍摄角度下的形状、纹理分布、角毛的排列等才是浮游植物细胞匹配的重要特征。因此，寻找一种合适的参数对这些复杂的特征进行有效的分析提取成为细胞图像分类的关键问题。传统的基于灰度、边缘特征等图像匹配方法存在一定的局限性，通过分形理论的产生，特别是分形编码在图像领域的广泛应用，基于分形编码原理，自然界中物体之间所存在的整体与局部的自相似性，局部与局部之间的相似性，对于任意的细胞图像，都可以用一组迭代函数系( m s ) 1 1 6 , 2 0 】来表示，利用这3基于分形方法的图像匹配研究一迭代参数作为图像匹配的特征成为本文尝试使用的方法。因此，本文尝试采用分形编码中的参数特征对浮游植物细胞图像进行匹配。围绕这个问题，主要进行了以下几个方面的工作：通过参数调整，对基于固定块和四叉树的分形编码算法进行了研究比较，为利用参数特征进行细胞图像匹配打下了理论基础。通过迭代函数系的参数特征进行了细胞图像匹配实验。在相似( a ) 粗根管藻壳面观( c ) 虹彩圆筛藻壳面观( c ) 中肋骨条藻利用分形邻距【5 6 】进行了细胞图像的匹配实验。( b ) 粗根管藻侧面观( d ) 弓束圆筛藻壳面观中肋骨条藻( g ) 豪猪棘冠藻细胞环面观( h ) 豪猪棘冠藻细胞分裂图0 1 几种藻类细胞图像4基于分形方法的图像匹配研究0 4 本论文的结构本文通过对国内外分形理论及其在图像处理领域相关应用问题的研究成果和最新进展的搜索、整理和总结，对分形编码参数特征以及在图像匹配上的应用进行了较为系统的研究和探讨。提出了基于分形编码的图像匹配算法。第一章主要介绍分形及分形编码理论基础，为后续章节的研究工作提供了基本的理论依据。第二章主要介绍分形编码算法。对于分割方法不同，编码过程中是否进行四叉树分解等进行了实验，以确定不同应用条件下对参数的选取问题。第三章是本论文的主要工作。主要介绍了图像匹配的定义和一些常用的基于t ，灰度、特征的图像匹配方法，然后介绍了将分形编码应用到图像匹配中，并针对此算法的不足提出基于分形编码参数的图像匹配方法和基于分形邻距的图像匹配算法。通过藻类细胞实验和o r l 人脸图像库的标准人脸模型实验验证了其有效性。第四章总结了本论文的要点和主要工作，并对本课题的进一步研究方向和分形理论的未来发展进行了展望。5基于分形方法的图像匹配研究1 分形编码基础分形理论是二十世纪七十年代中期由美国科学家m a n d e l b r o t 创立的【1 3 , 1 8 】。它是现代非线性科学研究中十分活跃的一个分支。特别是随着计算机科学技术的迅速发展和广泛应用，它在模式识别、自然图像模拟、信息信号处理以及艺术制作等领域都取得了巨大的成功。它同孤立子理论、混沌理论一起被誉为二十世纪后期的非线性科学的三大理论突破。作为一门新兴学科，分形理论已在图像处理方面得到广泛应用，特别是随着分形编码的出现。1 9 8 7 年，b a r n s l e y 首次提出利用分形技术进行图像压缩的方法【1 0 , 1 4 ，后来，j a c q u i n 又提出了j 种分形图像压缩的方法 1 2 , z s , l o q ，此后相继出现了各种类型的分形图压缩方法，它已成为图像领域的热点，为人们所关注。1 1 分形长期以来，对某一个数学集合，人们总是 - q 惯于在e u c l i d 空i 日- j ( r “，e u c l i d e a n )对其研究和度量，其中字母n 表示该空间的维数，通常它是一个整数，对有限个点，一取刀一0 ，对一条线段或一块有限平面图形或一块有限的空间几何体，则分别取n 为1 ，2 和3 ，同时也可分别得到它们的定常度量。习惯上我们分别称它们为点的个数、线段的长度、平面图形的面积和立体的体积。但在一个世纪前，相继出现了一些被称之为“数学怪物”( m a t h e m a t i c a lm o n s t e r s ) 的东西，人们无法用传统的e u c l i d 几何语言去描述它们的局部和整体性质。典型的数学怪物有如下几种【1 1 】。 康托( c a n t o r ) 集如图1 - 1 所示，可以这样来构造c a n t o r 集：记c o 一 o ，1 】，第一步( 万- 1 ) ，去掉中间三分之一，得且z 0 ，詈】u 曙，1 】，第二步( 刀l2 ) ，重复刚才步骤，得e 2 。 o ，吾 u 匿专】u 匮：吾】u 曙，1 ，如此重复刚才一系列步骤，得e ，当托_ 6基于分形方法的图像匹配研究= 二i = = = =时，即得到c a n t o r 集，显然，c a n t o r 集由无穷个点组成，在零维空间，其度量为无穷大，在一维空间，当其在第刀步时，共有2 厅个小区间，每个区间长度为( 三) 4 ，所以咖晓但) 一。l i m 弋 3 2 - - 1 4 = 。要么为无穷大，要么为零，c a n t 。r 集在e u c l i d 几何领域不可度量。图1 - 1 原托c a n t o r 集 科克( h v k o c h ) l 描线设置是单位长度的线段，把最三等分，以其中间三分之一为底边作向外凸出的正三角形，然后去掉该底边即得易；再把同样的过程应用到e 的每个线段( 包含四个线段) ，就得出岛；以此类推，直至无穷，如图1 - 2 所示，其极限曲线e 就是科克曲线，又称为雪花曲线。科克曲线在职- ，e u c l i d e a n ) 中的长度为切鼬假) 1 1 ，砌鼬皈) 。詈，l e n g t h ( e s ) 。萼，l e n g t h ( e ) 一舰e 一l i m i ( 4 3 j 1 i “一，由于它是一条闭区间的曲线，在职2 ，e u c l i d e a n ) 中，其面积为零，可见，科克曲线在传统e u c l i d 几何领域是不可度量的。图1 - 2 科克( k o c h ) i t 丑线7基于分形方法的图像匹配研究 谢尔宾斯基( w s i e 印i n s l 【i ) 垫片设e o 是r 2 上的一个边长为1 的等边三角形，把它的三边中点相连，就成为四个小三角形，去掉中间一个倒三角形，就得到e 1 ；再把同样的过程应用到e 。的每个小三角形，就得到e ，；以此类推，直至无穷，如图1 - 3 所示，就得到极限集f ，它像是打有许许多多大大小小三角形孔的垫片，简直是“体无完肤 ( 没有整块面积) ，又称为谢尔宾斯基三角形。我们来看看集合e 在( 尺1 , e u c l i d e a n )中的长度是多少，由于在忍_ 0 0 时，原先的黑色三角形变成了无穷个小点，所以每个小点的边缘长度之和砌g 肪但) l i m n , - - p 。3 ( 兰) 4 - ，在僻2 ，勖c 施嬲厅) 中，玩t ，面积为鱼4 ，以后每一步都是分4 留3 ，所以谢尔宾斯基垫片的面积为口踟但) 一! 现等( 三) 4 一。，可见，在传统的凰c 磁几何领域谢尔宾斯基垫片是不可度量的：图1 3 谢尔宾斯基( w s i e r p i n s k i ) 垫片上述的三个“怪物都是数学家的创造物，然而在自然界，同样有不可思议的现象存在，气象学家r i c h a r d s o n 在测量英国西海岸长度时，发现了一个规律：绘制地图的比例尺度由大变小时，如由l e n a 代表l o o k m 减小到l e m 代表l k m 时，海岸线长度却变得越来越长了，令口为比例尺度( 为1 0 0 0 ，1 0 0 0 0 0 0 等) ，s 为海岸线长度，墨为a = 1 0 0 0 时的s 长度，则英国西海岸长度s 的对数l o g s ；l o g s l 0 2 2 1 0 9 a( 1 1 )8基于分形方法的图像匹配研究或s ( 圹m 幻这意味着，当口减小到其去时，s 将增大一倍。按这个公式，海岸线长度实际上是不确定的。这就是说，自然界的某些现象是不可能用欧氏几何来描述的。这些困惑数学家许多年的怪现象终于在2 0 世纪7 0 年代被美国数学家b c n o i tb m a n d c l b r o t 彻底解决【1 8 】，在上面的叙述中，始终在励c 磁几何的整数维空间中讨论，那么为什么不允许有非整数维的几何存在呢? 实际上，若对长度为1的线段咒等分，每段长为，则t 。，一1 ，( 1 3 )对面积为1 的正方形作万等分，每个小正方形的边长为r ，则t ，2 1 ，( 1 - 4 )对体积为1 的正立方体作t 等分，每个小正立方体的边长为厂，则拧r 3 1 ，( 1 - 5 )上面三个等式中，厂的幂次实际上就是该几何体能得到定常度量的空间维数，于是有如下公式万，d 一1 ，( 1 - 6 )两边取对数，得到空间维数d 的表达式：d 一罂( 1 7 )i n ，对于康托集，在第以步时，原先的单位线段被分成了等长的2 ”段，每段长度为( 孝) “，故其维数d ，l n 2 0 6 3 0 9 3l n 3对于科克曲线，在第刀步时，其等长折线段总数为4 厅，于是科克曲线的维数d 应为9名，ql1 3，i-i为度长段每基于分形方法的图像匹配研究d 。一旦一l n 4 1 2 6 1 8 6k m( 1 - 9 )对于谢尔宾斯基垫片，在第阼步时，所有全等三角形的边长数为3 一个，每边长度为f 吾丫，所以谢尔宾斯基垫片的维数为d ；l n 3 1 5 8 4 9 6( 1 1 0 )l i l2康托集、科克曲线、谢尔宾斯基垫片等的维数都是分数维，它是分形理论的最主要的概念之一，维数的定义也体现了分形理论的重要特色，它突破了拓扑学中集合维数都是整数的局限，从整数维到分数维，是数学理论的重大变革与发展。维数有许多不同的定义方法，直观地说，维数是各种分形集充满空间的程度以及复杂程度的描述。人们对维数的概念进行了更深入研究与理解，提出了许多关于维数的新概念。常见的有相似性维数、容量维数、豪斯道夫( h a u s d r o f f ) 维数、信息维数、李亚普诺夫维数、谱维数、拓扑维数、广延函数、盒维数等。两种最常用的分形维数是( h a u s d o r f f ) 维数【2 1 】和盒维数( 又称m i n k o w s k i 维数，容量维数和度量维数) 【捌。m a n d c l b r o t 在对这些数学怪物及许多物理现象进行研究后，终于创立了这门重要学科分形。那么究竟什么是分形? m a n d e l b r o t 指出，豪斯道夫一贝西科维奇( h a u s d r o f f - b e s i c o v i t c h ) 维数严格大于拓扑维数的集合称为分形。这是实验性的定义，很不严格，也无可操作性，而后他修改了这个尝试性的定义，指出“其组成部分以某种方式与整体相似的形体叫分形”。但到目前为止，分形尚无最后的定义。k f a l c o n e r 认为，对分形的定义可以用生物学中对“生命定义的方法。“生命”很难定义，但却可以给出一系列生命对象的特征，对分形似乎也易于给出一系列特征性质，当集合具备这些性质时就可以认为是分形。按这种观点，称集合f 是分形，是指它具有下面典型的性质【2 3 】：( 1 ) f 具有精细的结构，即它包含有任意小比例的细节；( 2 ) f 具有某种自相似的结构，它可能是精确的，或是近似的，也可能是统计意1 0基于分形方法的图像匹配研究义下的自相似；( 3 ) f 的分维( 以某种方式定义) 严格大于它的拓扑维；( 4 ) 存在对f 的简单算法( 低信息量) 描述，例如迭代函数系统等。在上面的定义中，自相似性是分形中最重要的一个特征。所谓自相似性，是指系统的整体和局部之间，局部和局部之间具有的相似性，将其局部放大后会发现与原图是相似的，只不过存在一些比例放大和缩小，图形旋转和平移等，也就是说，局部是整体的一个小复制品。例如一棵苍天大树与它自身的树枝及树枝上的枝岔，在形状上没什么大的区别，大树与树枝这种关系在几何形状上称之为自相似关系；一片树叶的叶脉也具备这种性质；高山的表面，无论怎样放大其局部，它都如此粗糙不平等等。1 过去，数学主要是讨论集合和函数，对此可应用经典的微积分方法加以研究，一而那些不够光滑和不够规则的集合和函数都被认为是病态的，不值得研究的而被忽视。现在人们已认识到对不光滑集合可以而且必须进行详细的数学描述。表1 - 1 中总结了分形几何与欧几里德几何之间的某些主要区别【1 羽。表1 - 1e u c l i d 几何与分形几何的欧氏几何分形几何1 | 无曼。2 0 0 0 多年最近数1 0 年间对象人造物体适于自然形态尺度可用特定的比例及尺寸度量没有特定的比例和尺寸，有无限细节性方法公式，基本元素算法( 递归，迭代)1 2 分形编码的数学基础为了描述一幅图像及其编码、解码后的图像，需要为其建立数学模型。压缩映射、不动点定理、迭代函数系统及拼贴定理【1 8 】是分形图像编码主要的数学理论。迭代函数系统( 椰) 【2 9 】是b a r n s l c y 研究小组在h u t c h i n s o n 冽于1 9 8 1 年提出的迭代函数理论的基础上发展起来的，它是分形几何的重要组成部分。基于i f s 的分形图像压缩编码可以获得极好的压缩性能，能够实现很高的压缩比。不基于分形方法的图像匹配研究动点理论是泛函分析的重要分支【3 0 , 3 1 】，它保证了任何一个迭代函数系统都存在唯一的吸引子，并且该迭代函数系统的吸引子与初始值无关。拼贴定理 2 7 】是不动点定理的简单推论，并成功地用于集合、函数( 包括信号、图像) 等的逼近。1 2 1 度量空间分形理论及其应用问题的研究，总是在一个假定的理想空间中进行的，一个完备的度量空间常常能够满足我们的要求。定义1 1 度量空间，d ) 就是空间x 伴随实数函数，d ：x x r 。令x ，y x ，函数d 是x 和y 的距离。d 满足如下性质：w d 0 ，j ，) 一d ( y ，力，磁x - , y x ；( 2 ) 0 cd 0 ，y ) ，v x ，ye x ，x y ；( 3 ) d ，z ) 一0 ，v x e x ；( 4 ) d 0 ，) ，) 墨d ，z ) + d q ，y ) ，v x ，y ，z x 。在集合z 中定义了某个度量矗( 距离) ，则僻，矗) 称为度量空间。如果集合x中定义了某个拓扑结构f ，则僻，f ) 称为拓扑空间。度量空间是拓扑空间的特殊。所以度量空间是一种拓扑空间，其上的拓扑由指定的距离决定。典型的度量有：1 ) d ( x ，) ，) ii x - y l ，比，ye r 为e u c l i d e a n 度量2 ) d ( x ，) ，) - 【( 黾一z 2 ) 2 + ( ) ，l 一) ，2 ) 2 】1 胆，v l ，y 1 ) ， 2 ，y 2 ) e r 2 ，为e u c l i d e a n度量3 ) d o ，) ，) - k - - x 2 i , l y 。- y ：i ，v 。，y 。) ，0 2 ，y ：) e r 2 ，为m a n h a t t a n 度量4 ) 在码空间z ，定义讹小d ( x l x 2 x 3 - - - , y l y 2 y 3 ) 一砉搿5 ) 若x 。( x 1 ，工2 ，) ，) ，i ( y l , ) ，2 ，y 用) e r m ，贝i j1 2基于分形方法的图像匹配研究d 。，) ，) s 【荟mk 一) ，t | 2 】1 7 2 为e u c l i d 度量6 ) h a u s d o r f f 测度h a u s d o r f f 测度是分形理论及应用中的一种基本测度，它是l e b e s g u e 测度在维数不一定是整数时的推广。设fcr “是一个非空集合，6 是一个非负函数， 阢) 是r “中的一个可数或有限的集合。如果fcu 阢，并对每个，o 0 ，定义jh j ( f ) = i n f 善l u , i ：戤) 是f 的6 覆盖) ( i - i i )对于给定的f 和s ，鹾仃) 是6 的一个减函数，当6 _ o 时，日；但) 趋近于一个极限，这个极限可能是0 和，也可能是一个非0 的实数，记作日；( f ) 一l 。i r a 。珥但)( 1 1 2 )o u称日；( f ) 是f 的s 维的h a u s d o r f f 测度。度量空l 司中有三个非常重要的概念：完备的、紧集和b o r e l 集。完备的定义1 2x 上的两个度l d 。和d 2 是等价的，则存在常数0 c ， c 2 0 ，存在一个正整数n 0 ，使得d 0 。，) n 。( 1 1 5 )则度量空间中僻，d ) 的点序列也】二称为收敛于x e x ，如果对任意给定的1 3基于分形方法的图像匹配研究 0 ，存在一个正整数n 0 ，使得d o 。，x ) n 。记为x l i m 。丸( 1 - 1 6 )定理1 1 如果度量空间僻，d ) 中的一个点序列缸。】二收敛= y x e x ，则缸。】- 二是柯西序列【2 5 1 。如果度量空间，d ) 中所有的柯西序列都是收敛序列，则称( x ，d ) 为完备度量空间。紧集一个集合s 是紧集，则覆盖s 任何一族开集都有一个覆盖s 的有限子覆盖。b o r c l 集凡属可以从开集出发，通过有限次运算，用取余集，取有限个或可数个集合的并集或交集得到的集合，统称为b o r c l 集或b o r c l 可测集。h a u s d o r f f 距离吃是h ( x ) 上的一个h a u s d o r f f 度量，( 日僻) ，) 为h a u s d o r f f 度量空间。设( x ，d ) 为一完备度量空间，则h a u s d o r f f 度量空间( 日) ，九) 也是一个完备度量空间，( 日) ，) 也构成了分形空间，对分形的讨论均在这个空间下进行。1 2 2 灰度图像分形编码的数学模型为了讨论灰度图像编码，首先建立图像的基本数学模型。其中，常用的灰度图像数学模型有3 种：测度空间、像素数据和函数。1 ：测度空间模型。以测度空间作为图像模型，就是把图像表示为平面上的一种测度z ，这时，图像明暗度就能由平面子集4 上的度量来表示，即肛c a ) 。f d l z( 1 - 1 7 )例如利用迭代函数系统构造分形图形的随机迭代算法，就是采用的这种模型。2 ：像素数据模型。在像素数据模型中，把图像表示为离散像素的集合，每个像素具有的离散值( 通常范围为o 到2 5 5 ) 代表一个灰阶。每个像素的比特数( 用来存储像素值) 确定了灰度的分辨率，而总的像素数目就确定了图像的分辨率。1 4基于分形方法的图像匹配研究一幅包含有mx n 个像素的图像，可以想象为，l mx n 维空间中的一个向量，当略去像素值的离散特性时，这个空间就是尺“，把r “上的普遍范数( 即p 一范数) 定义为一帆i ，+ 蚓，+ + k f p ) 珈，( 1 1 8 )因此可以定义两个向量间的度量为d p ，y ) 一怯一y l l ，坛，y e r 4( 1 - 1 9 )特别的，当p = 2 时，2 范数又称为z 2 范数，由它导出的度量称为均方根度量，简称栅。于是，两幅图像x 一( x 1 ，x 2 ，毛) 和y 一( y 。，y 2 ，y ) 的均方根度量为厂一d 栅吣) _ h 卜1 善 一y t ) 2 ( 1 - 2 0 )3 ：函数模型。在函数模型中，把函数，：r 2 _ r 看作是一幅具有无限分辨率的灰度图像。考虑到实际图像总是在有限范围内，取，的定义域为单位正方形，2 一缸，y ) ：osx ，ys 蚺，而厂的值域为，一仁：os 工墨1 ，厂的值代表灰度级。则函数空间中的酽度量为d p ( 厂，g ) 一，一矶一旺：l 厂一矿出) 妇，( 1 - 2 1 )于是，均方根度量就相当于厶2 度量。给定一个函数厂：尺2 _ 尺，厂的图像就是指全体三元点 ，y ，0 ，y ”所组成的尺3 中的一个子集。函数模型是分形图像编码中将采用的模型。1 2 3 迭代函数系统由于研究的对象不同，迭代函数系统( 孵) 可以分成决定性i f $ 和随机性i f s ，决定性i f s 在二值图像时可以得到较大的压缩比，而随机的i f s 对灰度图像的压缩效果较好。1 ：二值图像的迭代系统1 5基于分形方法的图像匹配研究如下欧氏空间中的三个仿射变换：m 州铡圈吲一降l册降显然，这三个变换都是压缩变换，压缩因子均为去。因此， x ：w l ，w 2 ，w 3 ) 就二是一个迭代函数系统i f s 。把该i f s 对不同的初始图像( 一个正方形和一个圆) 进行反复迭代，如图1 4 所示。由于三个变换都是仿射压缩的，每次迭代后的新图形都是缩小的，初始图形的迭代极限将成为一个点，所以无论x 是怎样的初始图形，反复迭代后将逼近于同样的极限图形。图1 - 4 的极限图形如图1 5 所示的s i c r p i n s l d 三角形 3 2 1 。& 融k k图1 _ 4图1 - 5s i e r p i n s k i 三角形这个例子是由给定的迭代函数系统i f s 求得其分形图像s i c r p i n s k i 三角形，1 6oo-lpl+1j1jxyxy，i-l-j_lp_l-t-ll11，joo基于分形方法的图像匹配研究每个变换是由一个含有6 个实值系数的仿射变换构成，由此生成图1 5 所示的s i e r p i n s k i 三角形所需的全部信息，包含在6 3 - - 1 8 个实值系数中，这样这1 8个系数就可以作为图1 5 的编码，如果要记录s i e r p i n s k i 三角形这个图形，只需记录其椰，即 x ：m ，屹，w 3 ) 。2 ：灰度图像的迭代系统在前面讨论的图像是二值图像，并且在全局上是自相似的。然而现实生活中的图像往往都是灰度图像，那么对于任意灰度图像是否可以用一个迭代函数系统i f s 来表示呢? 答案是肯定的。b a m s l e y 提出，迭代函数系统i f s 并不仅仅用于描述分形图形，事实上任何图形都可以表示为其自身的一些仿射复制品，都可以通过一系列仿射变换来表示，关键在于仿射变换的选择，另外，并不是任意仿射变换都可以用于迭代函数系统，它必须是收缩的，即任何点集内元素之间的距离经过仿射变换后要缩小。这种仿射变换被称为压缩仿射变换，它的收缩性决定了迭代函数系统的保形性，使迭代函数系统最终是收敛的。灰度图像的仿射变换假设西0 ，y ) 是，2 ：一，2 上的仿射变换，其中，2 是单位正方形讹加4 睁仇( 1 - 2 2 )其中4 为2 2 矩阵，b i 为2 x1 向量。假设b ，2 是单位正方形的定义域块，令西；) 一r ，仿射变换e 建立了值域块r 与定义域块d ；之间的对应关系，定义图像厂 ，y ) 上的映射：f 呻f 为q ( ，) ，y ) 一s i ，簖1 ，) ，) ) + d j ，o ，y ) r( 1 2 3 )在变换中，常数墨控制灰度图像的对比度，o ，控制图像的亮度，厩是q 的空间变换部分。空间仿射变换以及其逆变换见图1 - 6 。图1 - 6 空间仿射变换以及其逆变换1 7基于分形方法的图像匹配研究灰度图像压缩映射【3 3 】如果映射峨：f 啼f 是压缩的，存在s ，0 s 1 ，使d z ( q ( ，) ，q ( g ) ) ss 。d e ( f ，g )其中度量d ( ，) 是函数空间己2 度量。在积分中改变变量，从而有d ；( 皑( n q ( g ) ) = ( d 1 ) 纵，) o ，y ) 一；( g ) o ，y ) 1 2 蛐一盯| d e t ) 眩f 厂o ，) ，) 一g o ，y ) 1 2 蚴sm 2d e t ( a ；矽；( ，g )( 1 2 4 )其中d e t ( a ；) 表示矩阵4 的行列式，墨表示对比度调节系数，因为q 是压缩的，于是盯i d e t ( a , ) l 1( 1 - 2 5 )从式( 1 2 5 ) p - f f j 氟i ，只要映射妣是压缩的并且其压缩因子较小，对比度系数可以大于1 。将单位正方形，2 划分成立不相交的值域块集俄 ，即j 2 - l 峨及足n 墨一爹( f j )假是j 5 c 2 中的定义域块，对于定义域块，并不要求u b 覆盖，2 ，也不要求d j 互不相交。假设 面】是p i f s ：缸：q _ r ，如图1 - 7 。图1 - 7 定义域块与子块的匹配对于每一个厩在函数空间f 上定义相应的映射1 8基于分形方法的图像匹配研究，( ，) ，y ) ；墨f ( m 7 1 0 ，) ，) ) + d ，( 1 - 2 6 )选择适当的邑使得q 是压缩的。定义w ：f 呻f形( 厂) o ，y ) = c o 。( ，) o ，) ，) ， ，y ) e r i( 1 2 7 )由于r 是，2 的分割，对于，2 上所有的点0 ，y ) ，形都有定义，因此矽( 厂) 是图像。因为每一个妣是压缩的，从而在f 上形也是压缩的，根据压缩映射定理，存在唯一的不动点，埘e f 满足矽( 九) 一九( 1 - 2 8 )对于任何初始图像厂o ，反复作用于映射形，最终收敛于不动点厂越。压缩映射定理是分形图像压缩的基础，任意给定灰度图像厂，寻找压缩映射形，使得形的不动点非常接近厂，则包含了恢复厶的所有信息。如果存储映射所需要的空间少于存储图像，所需的空间，就达到了图像压缩的目的。灰度图像的拼贴定型3 3 】任意给定灰度图像厂，要求对它进行编码压缩，也就是如何能找到压缩映射彤，使它的吸引子厶等于厂。如果能够找到图像厂f ，使得d ( ，厂) 达到最小，而厂与九非常接近，拼贴定理保证了这一点。而图像的解码只需要将压缩映射形反复作用于任意初始图像g 就可以。灰度图像的拼贴定理为：任意给定灰度图像厂，能够找到一个压缩映射形，使得d ( f ，形( ，”ss则有a ( f ，厶) se 1 一s( 1 2 9 )其中s 是映射形的压缩因子，厶是映射的不动点。这就意味着对于任何初始图像g ，反复作用映射矽所获得的图像非常接近厂。w “ ) 一凡一厂( 1 3 0 )1 0基于分形方法的图像匹配研究迭代函数系统设q ，吐，是( 日( x ) ， ) 上的胆个压缩映射，压缩因子为墨，s 2 ，。q ，0 s ， 。如果口) ；彳，则称彳为日僻) 的吸引子w s 的不变子集或不动点。若w s x ：，j = l 2 , - - - , 以】的压缩因子s 满足o s 是收敛的，拼贴定