基于边缘特征图像配准算法的研究

《基于边缘特征图像配准算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

沈阳理工大学硕士学位论文摘要图像配准是将不同传感器在不同时间或不同成像条件下对同一景物获得的两幅或多幅图像在空间上对准，是图像处理的基本问题之一。配准效果将对图像拼接、图像识别、目标跟踪等后续工作有直接的影响。本文在对基于图像特征的配准方法进行分析的基础上，对基于边缘特征点的图像配准和基于边缘的图像配准进行了研究。基于边缘特征点的图像配准有两个重要的环节：一是图像边缘特征点的提取，二是特征匹配准则。特征点提取的准确性及稳定性将会对后续的配准工作产生影响。特征点在提取过程中对位置变化、灰度变化、噪声、部分遮挡有较好的适应性，本文依据图像的边缘轮廓特征利用动态支持域的改进CSs算法提取边缘角点，然后分别利用奇异值分解和马氏距离的方法对提取的特征点进行配准。奇异值分解利用数据分析法，找出大量数据中所隐含的模式，进而进行匹配，实验证明，奇异值分解具有平移旋转不变性。马氏距离的大小不仅与各个点集相对分布有关，而且与各个点集自身的分布有关，应用马氏距离对不同传感器图像进行配准，实验证明，马氏距离具有一定的实用性，对误匹配的剔除需要进一步改进。基于边缘的图像配准是以图像边缘为特征单元。Hausdorff距离描述两个点集之间的相似性度量，具有很强的抗干扰能力和容错能力，然而单纯的Hausdom距离对噪声和孤立点比较敏感，导致误匹配率较高。本文采用加权平均的方式去除一些出格点实现求取部分均值的Hausdorff距离改进形式。针对配准中全局搜索对配准速度的影响，引入遗传算法作为搜索策略。在遗传操作中，利用改进的MSE．Hausdorff距离作为配准的相似性度量来构造遗传算法的适应度函数，以此确定出最优变换参数，完成基准图和配准图的配准。实验证明，这种改进的部分Hausdorff距离可以很好地克服噪声和部分遮挡对图像配准精度的影响，大大提高了运算的效率。关键词：图像配准：边缘；CSS；Hausdorff距离；遗传算法 AbstractImageregistrationmeans：aligningtwoormoreimagesinspacewhichisobtainedbydia’erentsensorsatdi虢renttimesorunderdi行-erentimagingconditionsbutowethesamescene．Itisoneofbasicproblemsinimageprocessing．Theeffectofregis仃ation埘llhaVeadirectinlpactonthefollow—upwork．Forexanlple，Imagemosaic，imagerecogIlition，仃ac|【ingandothersubsequentwork，etc．Intllisp印er，basedonfeature-baSedanalysisofimageregistration，featurepointsoftheedge-basedimageregistrationandedge-basedimageregistrationhaSbeenstudied．Basedonedgef．eaturepointimageregistrationContainst、Ⅳoimportamaspects：Theflrstistheimageedgef-eaturepointex仃action，thesecondismatchingcrit甜on．TheaCcuracyandstabilit)roff-eaturepointextractionwillimpactontheworkofthefollow。upregistration．FeaturepointshaVebetteradaptabilityonthepositionchaIlge，grayscale，noise，partialocclusionintheextractionprocess．Thispapermatchesthef．eaturepointsextractedaSfollow：first，basedontheimageedgecharacteristics，usingdynamicsupporrtdomainoftheimproVedCSSalgoritlmltoextractedgecomer，andmenusillgtllesingularValuedeconlpositionaJldmeMahalanobisdistaJlcemethodtomatchtllefeaturepointsextracted．SingulaurvaluedecompositionusedataanalysismeⅡlodandfindoutala略equaJltityofdataimpliedbythemodel，andt11enmatclling．neeXperimentsshowthatthesingularvaluedecompositionhasinv撕anceofrotationandtraIlslation．ThesizeofMahalanobisdistancedoesnotonlyrelativetodistributionofeachsetofpo硫s，butalsotothedistributionofitso、)~rn．UsingMallalaIlobisdistallcematchfordi舵rentsensorimage．TheexperimentsshowthattheMahalanobisdistanceispractical，aIldtheexcisionformismatchneedtobefurtherimproved．Edge-baSedimageregis打ationisbaSedonimageedgefeatllreuIlit．TheHausdorfrdistancedescriptthesimilaritymeaSureoftwopoints，aIldhasstronganti．interferenceabil毋aIldfaulttolemce．However’tllesimpleHausdo斌distallceismoresensitiveto 沈阳理：亡大学硕士学位论文noiseaIldoutliers，leadingtoahigherrateoffalsematches．Inmepaper，usingmefomofimprovedHausdorfrdistallcewhichusetheweightedaVerageremoVesomespecialpointsa11dachieVeaponionofmean．Astheinnuenceofglobalsearchtoregistrationspeedintheregistrationprocess，introducinggeneticalgorithmasthesearchstrategy．Ingeneticoperator，usingtheimproVedMSE-Hausdorffdistanceasthesimilaritymeasuretoconstmctthead印tiVe如nctionofgeneticalgoritllIn，thendeteminetheoptimaltrallsf．ompar锄eters，completetheregistrationofthebenclu】[1arkimageandtheregistrationimage．ExperimentsshowthattheimproVedHausdorffdistancecanweUoVercometheimpactofnoiseandpartialocclusiononimageregistrationaccuracyand伊eatlyimproVedtheoperationrate．Keywords：imageregistration；edge；CSS；Hausdorffdistallce；geneticalgorithm 第l章绪论第1章绪论1．1图像配准的发展图像配准长期以来一直都受到非常广泛的应用，其最早开始于二十世纪七十年代的美国，主要运用在飞行器导航辅助系统、武器投射系统的末制导上，其研究一直以来都得到军方的大力支持和赞助。八十年代后，图像配准技术逐渐从纯军事应用扩展到计算机视觉、图像处理、光学图像处理、遥感图像处理和雷达图像目标跟踪与识别和文本设别等其它领域。例如，利用监控技术和图像识别技术结合在一起的智能广告监播系统，它根据节目的图像信号识别出视频图像广告的相关信息，然后生成监播报告，这样就大大减少了人工操作的复杂性和繁琐性。车辆管理、汽车测速中的车牌识别技术，都运用了图像配准。图像配准还应用于气象卫星中，对天气预报、各种自然灾害监控和预防上，起到不可替代的作用。中国的月球探测工程中，嫦娥一号卫星拍摄了月球表面高清晰图像，但这只是月球表面局部的图像，非常具有局限性，不利于对月球表面整体的把握和观察，通过配准实现图像的全景拼接，实现了人们对月球全景的观察。在过去二十多年里，研究者为了寻找到一种既满足精度高又具有实时性的配准方式，对有关图像配准的问题进行了大量的研究工作，也提出了很多实用性强的配准算法。最初使用的配准方法是基于图像的像素灰度信息，直接利用两幅图像的灰度信息，建立两幅图像之间的相似性度量，然后采用某种搜索方法，求取使相似性度量最大变换模型。提出的基于灰度配准方法包括归一化互相关配准方法【l】、基于傅立叶变换的相位配准方法、基于统计矩的配准方法【2】、基于直方图的配准方法嘲等。为了加快配准速度，研究者又提出了各种方法，如B锄ea和Silvenllall提出了序贯排序相关算法(SSDA)嘲，WangR．T提出的SHSM算法，以及由粗到精的金字塔配准方法，并且有部分学者通过硬件实现相似度量计算来加速配准。虽然人们提出的基于灰度的配准方法具有精度高、概念清晰等特点，但其对光照、灰度变化以及旋转、尺寸变换、遮掩极为敏感。为此，人们又提出了点配 沈阳理工大学硕士学位论文准技术、边缘配准技术、闭合轮廓配准技术等基于图像特征的配准方法。其中，孙焘[41等将一般的仿射变换转换为刚体变换，使算法更能符合实际。牛力型s】等人针对图像配准中旋转、平移、缩放变换，推导出了盒距离变换公式，不仅缩小了搜索空间，也大大节省了计算时间，通过实验证明，该算法大大提高了基于Hausdorff距离图像配准的计算速度。彭文[6】等人在应用特征点的基础上结合边缘轮廓进行医学图像配准，并减少轮廓点集的数量来加快计算效率，实验证实算法既能匹配图像中的整体结构信息还能对齐图像中感兴趣的点。随着应用技术的发展，人们提出各种各样的配准算法，并对不同的算法提出改进，在不同场合可以起到很好的效果，为了缩短时间，将不同的搜索算法结合到算法中【7】，如神经网络、模板退火、遗传算法等，起到很好的效果。图像配准技术得到人们越来越多的关注，也在越来越多的领域得到应用。1．2论文选题的理论意义图像配准是计算机视觉及图像处理等领域中的关键步骤，在近几十年来一直是人们研究的热点和难点。图像配准【8】是图像处理的基本任务之一，用于将不同传感器在不同时间或不同成像条件下对同一景物获得的两幅或多幅图像在空间上对准，或是根据已知模式找到另一幅图中相对应的模式。在对图像配准的研究过程中，大量技术被应用于针对不同数据和问题的图像配准工作，产生了多种不同形式的图像配准技术。近年来在对配准技术的研究涵盖了多个应用领域。图像配准技术主要应用于以下领域：(1)医学图像分析，如数字剪影血管造影DSA血管造影术、肿瘤检测、白内障检测、CT、M砌、PET、SPECT图像结构信息融合；(2)模式识别，如特征识别、波形分析、签名证实、目标物运动跟踪、序列图像分析等；(3)计算机视觉，可用于目标定位、自动质量控制等；(4)遥感数据分析，多电磁波段图像信息融合，如多谱段等场景分类、定位和识别定义好的或己知特征的场景、自然资源监控、核生长监控、市区增长检测等⋯7】。由于图像配准已经广泛应用到多个领域，并且它本身具有复杂性，所以它已经成为很多研究课题的重要环节和当前数字图像处理的热点研究问题。 第1章绪论1．3论文的主要工作本文采用基于边缘特征的图像配准方法，在系统研究各种算法中，采用了图像边缘特征点和图像边缘作为特征单元。本文主要工作如下：(1)利用具有动态支持域的改进的CSS角点提取算法从边缘轮廓上提取角点，该方法在低尺度下抑制了噪声的影响，克服出现角点漏检和伪角点的情况，这样保证了角点提取的稳定性和准确性：(2)利用奇异值分解和马氏距离两种方法对用改进的CSS算法提取出角点的两幅图像进行配准，特征点比像素点少很多，大大减少了配准的计算量，特征点对位置变化比较敏感，大大提高了配准的精度：(3)在获取基准图与配准图边缘的基础上，以边缘线作为特征空间，采用改进的部分Hausdom距离作为相似性度量对图像进行配准，有效克服了以灰度为特征对亮度变化、部分遮挡、噪声、图像块缺失比较敏感的缺点；(4)为了加快运算速度，节省计算时间，引入遗传算法作为搜索策略，在遗传算法实现上，结合改进的部分Hausdorfr距离作为评价相似性标准，来判断个体适应值的大小。为了防止遗传漂移现象，使用小生境遗传算法。为了使个体适应值评价强度能够动态改变，在进行运算时，引入了前向距离阈值和后向距离阈值。1．4论文的章节安排本文主要针对基于边缘特征的图像配准问题进行了广泛深入的研究，并针对具体问题提出了具有创新性的图像配准方法，具体内容和安排如下：第1章绪论，主要引入图像配准的定义、研究的意义、应用以及国内外研究的现状：第2章图像配准理论，主要介绍了图像配准所需要的理论知识，如图像配准的数学模型、配准的一般流程和关键要素等，并对基于边缘的图像配准相关概念和技术进行深入研究和归纳总结；第3章边缘特征点的检测与配准，详细研究了基于边缘轮廓提取特征点和利用提取的特征点进行配准。特征点提取是基于边缘特征点图像配准方法的关键，提出了利用改进的基于边缘轮廓曲率的CSS方法提取角点，并将奇异值分解和马氏距离应用到图像配准，并用大量的仿真实验验证该方法的有效性和鲁棒性； 沈阳理工大学硕十学位论文第4章基于改进的部分Hausdorff距离的图像配准，对Hausdorff距离进行研究，并对Hausdorff距离在配准中存在的不足而采取各种改进形式进行了对比分析，提出了本文所采用的改进的部分Hausdorff距离，采取以改进的部分Hausdorff距离作为适应度评价，以遗传算法作为搜索策略进行图像配准，完成了图像的仿真分析；第5章基于边缘特征的图像配准算法分析，对本文所采用的配准算法进行分析总结，进而总结基于边缘特征点和基于边缘图像配准的特点，以便可以更好地应用到各个领域。 第2章图像配准理论2．1图像配准的概述2．1．1图像配准定义在计算机视觉识别过程中，常常需要把不同传感器或同一传感器在不同时间、不同成像条件下对同一景物获取的两幅或多幅图像进行比较，从而找到该组图像中的共有景物，或是根据已知模式到另一幅图中寻找相应的模式，这叫图像配准Ⅲ。2．1．2图像配准主要方法及其比较基于图像配准的不同度量方法，主要分类如下m】：(1)基于图像灰度的配准方法图像的像素灰度值信息包含了图像记录的所有信息。基于图像像素灰度值的配准算法是最基本的配准算法。在这类方法中，以像素的灰度值作为特征，相似性度量建立在配准图像问的灰度信息上，不需要对图像做特征提取，配准精度较高。但由于其要把每个点的信息均考虑进去，计算量很大，速度较慢。常用的相似性度量有归一化互相关系数、相位相关、交互信息法、SSDA等；(2)基于图像特征的配准方法这种方法需要先对图像的特征进行提取，一般提取的特征包括点、线、面特征等。通过提取图像的显著特征，图像的信息量大大被压缩，计算量相比基于灰度配准方法有所减少，加快了配准速度。基于图像特征配准的方法包括特征提取和特征配准两个环节。基于灰度和基于图像特征的配准方法各有其优缺点。基于图像灰度的算法虽然精度高，但对图像的要求也高，其对图像之间的微小差别非常敏感，如因光照的改变而导致的灰度变化对计算结果产生较大的影响，甚至可能导致配准的失败，所以它的抗干扰、抗噪声能力都比较差。对于基于特征的图像算法，由于图像的特征受几何变换和辐射度的影响来说不易变换，并且可以较好地反映图像的形状信息，而且在特征提取后图像灰度上的局部变化可能消失，因此基于图像特征的．S． 沈阳理工大学硕士学位论文算法抗干扰能力比较好，而且其具有平移、旋转、缩放不变性，对存在几何变换的图像配准，其配准效果仍然较好。2．1．3图像配准一般流程对于图像配准的研究，人们提出了各种各样的算法，但各种算法在解决问题时，一般都采用相同的结构【·们，主要流程如图2．1所示：(开始)◆【输入基准图和配准图上图像预处理上图像特征提取V图像配准●结果输出——÷—一(结束)＼／图2．1图像酉己准的一股流程2．1．4图像配准的关键要素传感器噪声、成像过程中视角的改变、目标移动和变形，以及光照环境的改变等因素影响，都会使同一场景在不同条件下投影所得到的二维图像会有很大的差异。图像配准就是为了寻找一个使一幅图像的点映射到另一幅图像上并且使它们之间的差异最小最优的变换，这个任务通常由四个方面组合而成⋯】，分别为：(1)特征空间。特征空间是指从图像中提取出的用于配准的信息。选择特征空间是图像配准的第一步工作，选择合理的特征空间可以有效地提高配准性能、降低搜索空间的时间、减少噪声不确定的因素带来的影响，从而提高算法的鲁棒性和稳定性。图像的特征空间可以是灰度，也可以是物体边缘、轮廓、直线交叉点、角点、虚圆和闭区域的中心；(2)相似性度量。相似性度量是指用哪种方法来确定待配准特征之间的相似性。它是以某种距离函数或代价函数的形式出现的。相似性度量与特征空间是紧密相连的，因为相似性度量是利用特征提取的信息，特征提取的好坏将影响相似性度 第2章图像配准理论量。相似性度量决定了图像配准中参与配准的因素，有利于进一步提高算法性能，常用的相似性度量有相关函数、明考夫斯基距离等。相似性度量和特征空间的选择，可以有效地降低计算量和噪声、遮挡等因素带来的影响，提高配准的精度；(3)搜索空间。搜索是由待估计参数组成、用来校准图像的变换集合。配准的变换模型决定了搜索空间的大小，变换模型中的参数越多，搜索空间的大小越大。例如只考虑平移变换的搜索空间比考虑平移变换、尺寸变化、旋转的变换模型少。在配准过程中，通过图像间的特征来缩小包含最优变换的空间大小，可以加快配准的速度：(4)搜索策略。搜索策略是决定在这个空间选择下一个变换，使经过变换后的相似性得到最大。由于很多配准特征都包含很大的计算量，搜索策略成为一个不容忽视的问题。搜索策略是用合适的搜索方法在搜索空间中选择平移、旋转、缩放等下一个变换参数的最优估计，使得经过变换后两幅图像之间的相似性得到最大。常用的搜索策略有穷尽搜索、遗传算法、金字塔分层搜索、以及生物进化算法等，每种搜索算法都有各自的优缺点，在一定的领域都会起到一定的实效性。在进行配准时，为了找到最优解，就要考虑到变换模型的参数，所以选择搜索策略对搜索空间影响将较大。2．1．5图像配准的相似性测度图像配准的相似性测度有很多种，通常使用的有均方差、绝对差、平均绝对差、互信息、相关系数和标准相关系数等。(1)绝对差(AbsoluteDifference)d(厂，g)=∑∑l厂(f，／)一g0十l，门+_，)l(2-1)，=0J=0(2)平均绝对差(MeanAbsoluteDifference，简称MAD算法)d驴，g)2亩丢荟I厂(f√)一g如+1，胛+／)I(2-2)(3)均方差(MeanSquareDifference，简称MSD算法)d(／，g)2寺荟毛l厂(f，／)一g如+l，疗+／)121肼一lⅣ一l(4)相关系数d(厂，g)2古荟乏厂o，／)g如+咖z+／)1吖一lⅣ一l(2—3)(2-4) 沈阳理工大学硕士学位论文(5)标准相关系数d(厂，g)=嘉篆1篆陟o，／)一7k。+咖+／)一虿](2-5)公式(2-1)到(2-5)中，／(f，／)代表模板图像中位置在第f行第／列的像素的灰度值，g@+f，门+，)代表基准图像中参考点(m，，2)处模板中第f行第／列的像素的灰度值，厂和g分别代表两个图像模板像素灰度值的均值。(6)互信息(MutualInfomlation)两幅图像之问互信息的表示公式如下：s=善pG，y)·。gj专5亏刍{；了(2—6)联合概率pG，y)用归一化的联合直方图表示，pG)、p◇)是pG，y)的边缘概率。2．2图像配准的数学描述2．2．1图像几何变换的基本数学模型描述图像问的几何变换是指用数学建模的方法来描述图像位置、大小、形状等变换方法，是通过数学建模实现对数字图像进行几何变换处理。常见的几何变换有平移、旋转、缩放、投影、错切、扭曲，具体形式如图2．2所示。平移缩放旋转错切匪庐扭曲投影图2．2常用的几何变换形式常用的图像几何变换模型主要包含刚体变换、仿射变换、投影变换和多项式变换。其中仿射变换最为常用，下面着重介绍一下仿射变换。 第2章图像配准理论仿射变换包含平移、旋转、缩放、错切四个几何变换，它是刚体变换的扩展。记基准图像的点(x，y)，变换后得到的点为(x7，y’)，平移向量(f，，f。)，逆时针旋转角度秒，尺寸大小变化为s，变换模型为：阱s瞄誉胁㈦亿7，或者简记为p2=f+脚l(2—8)其中，p。，p：为变换前向的坐标向量，t为平移向量，R为旋转矩阵。2．2．2图像配准的数学表述图像配准的过程就是寻找一个变换，然后将一个图像在此变换下映射到另一图像上，并且与另一图像的相似性度量最大的过程。假若以模板配准为例，要寻找一个固定模板到另一图像的相应位置，记模板图像为B，另一图像为源图像A，变换空间为f，变换丁∈f，在变换T下，模板图像B到源图像A的映射区域为r(B)。选择厂作为相似性度量，厂(B，丁(B))表示模板图像B与映射区域的相似性测度。那么，这个图像配准的过程可以表述为：在变换空间f中，寻找一个变换丁7，使厂(曰，丁’(B))=碑i9厂(E丁(召))。图像配准J‘b就变成一个以f为定义域，以．厂为函数映射的求极值问题。实际中，进行图像处理的并不是连续图像，而是灰度和位置都经过量化生成的离散数值图像，常用像素矩阵来表示。在图像配准中，基准图通常比配准图大，而直接进行配准的图像一般是大小相同的，因此，为了确定配准图在基准图中的位置，基准图必须划分为很多个与配准图大小一样的子图，然后配准图逐个与基准子图进行比对，以便找到最佳的基准子图，确定配准图在基准图中所在的最佳位置。2．3以边缘作为特征空间的图像配准以边缘作为特征空间的图像配准可以分为两类：一种是基于边缘信息进行配准，归根到底还是点，是从点集的角度出发；另一种是基于整个二值边缘的轮廓 沈阳理工大学硕士学位论文形状进行图像配准，但计算复杂度特别高。2．3．1图像边缘的定义图像边缘是一种重要的视觉信息，也是图像最基本的特征，在人的视觉系统和数字图像处理技术中都发挥着越来越重要的作用。目前，对于边缘进行数学的精确定义方法还没有一个具有权威性，被人们广泛接受和认可。图像边缘一般都表现为图像局部特征的不连续性，是图像灰度变化比较剧烈的地方，通常把边缘分为阶跃型边缘和屋顶型边缘，阶跃型边缘即图像强度在不连续处两边的像素灰度变化都比较明显，而屋顶型边缘即位于图像灰度增加与减小的交界处。因此边缘是指周围像素呈现屋顶型或者阶跃型变化的像素集合，主要存在于目标与目标、目标与背景、区域与区域之间【|2】。图像的局部边缘是图像中局部灰度级表现为强度呈突变形式的封闭小区域，这种封闭区域的变换可以用一定窗口的检测算子来进行提取。在数字图像处理技术中，有很多经典的边缘检测算子，它们实质上都是采用某种算法提取出图像与背景间的交界线。常用的边缘检测算子有Roben边缘检测算子、拉普拉斯算子、Sobel边缘检测算子、Prewitt边缘检测算子、CaIllly算子等。2．3．2基于边缘信息的特征配准方法基于边缘信息的特征配准方法是以边缘特征点的形状信息作为两点相似性度量，这样就需要利用一些形状识别方法来获取边缘特征点的形状信息。2．3．2．1常见的基于边缘信息的配准方法常见的方法有：链码描述子m，和矩不变且【141。(1)链码描述子数字图像中，图像中边缘上的像素点都是离散的像素点，除边界上的点外，所有的点在八个方向上都有与之相连接的像素点，若用方向符号来代替将这八个点连接，沿边缘依次记录两个点之间的连接方向，就可以得到边缘轮廓的方向链码。两点间的连接方向如图2．3所示： 第2章图像配准理论0JL厶—产。l0I}∥4|、＼／JDL1』1C／＼E∥lI≮。／R，，7＼图2．3两点I司的连接方向沿着物体的边缘，按图2．3所示的连接方向就可以得到边缘轮廓的链码表示。假设从图像Z(x，y)和六(x，y)中分别提取轮廓口和∥，用链码序列溉)和碱)表示，它们的长度分别为Ⅳ。、Ⅳ口，那么轮廓口上从第尼点开始的门点序列与轮廓∥上从第，点开始的以点序列之间的相关为：巩=吉势缸一∥(2-9)式中：以：圹佩卅删心一去芝佩¨。州㈣<刀以“／2口(“／)mod心一i白a(“J)mod心’Us7<刀邑+，=6。，+，，。删％一丢芸乃。“，，。州％取模考虑到存在闭合轮廓。p“=1意味着完全匹配。为了找到最近配准位置，口上从七开始咒长度一段在∥上滑动，最大相关由下式确定：C叩=ma)({巩)MM为整个滑动范围。(2—10)轮廓口和∥若满足下列两个条件时，它们就是所要得到的最匹配的轮廓对：1)c厶≥％-，∥’包括五(x，y)中与口形状相似的轮廓；2)c筇≥丁，阈值丁是为了提出相关很弱的结果。．11． 沈阳理工大学硕士学位论文(2)矩不变量利用二阶和三阶中心矩构造的七个不变矩可以描述一幅图像的区域形状，且具有平移、旋转、尺寸不变性。算法描述如下：若存在数字图像／(x，y)，则其中(p+g)阶矩定义为：小胛=∑∑xpy9厂(x，y)(2—11)Jy(p+g)阶中心矩为：∥朋=∑∑(x—x)p(y—y)9／(x，y)xV其中，三：鱼，多：堕，聊00moo(2—12)零阶矩聊。。=∑∑厂(x，y)，一阶m。。=∑∑矿(x，y)和垅们=∑∑∥(x，y)分别xyxyxy除以零阶矩m。。后所得的x和J，是物体质量中心的坐标，或者直接表示的是区域灰度重心的坐标。重心矩∥尸。，反映物体区域R中灰度重心分布的度量。(p+口)规范化中心矩即朋，定义为：?1)q=p)q|H‰其中，=(p+g+2)／2利用二阶和三阶规范化中心矩可以导出下面七个不变矩组①l27720+卵02①2=(7720一7702)2+477二①3=(7730一37712)2+(37721+7703)204=(7730+刁12)2+(7721+7703)2①5=(叩30一37712)(刁30一刁12)L(叩30+712)2—3(7721+刁03)2J(2-13)+(3772l一7703)(772l+703)L3(7730+7712)2一(772l+7703)2J①6=(刁20一7702)【(773。+7712)2一(7721+7703)2J+4刁ll(7730+7712)(矽21+刁03)①7=(37712—7730)(刁30+7712)L(7730+叩12)2—3(刁21+刁03)2J+(3772l一7703)(刁2l+刁03)L3(7730+刁12)2一(刁2l+刁03)2J 第2章图像配准理论在实际利用不变矩进行配准时，为了提高准确度，这样就需要计算所有七个不变矩。2．3．2．2基于距离变换的图像配准方法基于距离变换的图像配准方法，则从图像的边缘信息着手(即边缘点集合)，是将二值图像转换为近似距离的图像(即，距离图像)。在距离图像中，图像中一点的灰度值反映了该点到距离它最近边缘点的近似距离。基于边缘信息的配准相似性度量定义为：s胁(么，B)=min(玎甜朋彰7b砌朋，胛“聊6／7b砌膪)(2—14)其中刀甜垅臼，胛甜聊6分别表示集合么和集合B中基本重合点的总数：乃砌以，而砌膪分别表示集合么与集合B中点的总数。下面对上式所定义配准度量的有关性质进行讨论：w，Ⅷ，0≤％≤1醣(彳，刀)=0时，有疗材所日=O或即甜聊6=0，这时集合彳与集合B完全不匹配。既(么，艿)=1时，有玎甜，77d=乃砌阴和门zf所6=乃砌馏，这时集合彳中任意一点与集合B中某一点匹配。反之，集合B中任意一点与集合么中某一点匹配。这时，称彳和B是完全匹配的。既(么，B)=1(咖≠0)，是考虑了成像机理的不同和边缘提取可能出现的偏移时的集合么与曰的配准。根据相似性度量函数，具体步骤为：(1)提取图像边缘，并把图像进行二值化处理；(2)对二值图像进行距离变换，步骤是：对图像进行初始化，将边缘点赋值为O，非边缘点赋值为无穷大；在进行第K次迭代时，对于图像中每一个像素点(f，／)，按公式(2．15)进行计算：蒜器二篇冀嬲∥+3’嘭～’p㈣杉二?+，+3，I：?一，+4，KZ+3，K二?+。+4)r一7其中，形f为点(f，／)的第K次迭代值；根据公式(2—15)重复进行迭代，直到所有的点的灰度值不再发生改变为止。原图像中特征点的灰度值在距离图像中为0，显然，迭代次数取决于图像中非边缘点 沈阳理T大学硕士学位论文到最近边缘点的最大距离：(3)对图像进行配准，在配准图像中，对于每一个可能配准的位置(x，y)，将基准图像看作集合彳，配准图像在基准图像中对应的窗口图像看作集合B(x，少)。对其进行初始化，乃胁从=砌幻旧=0，门“脚口=聆甜m6=O。对于集合彳经过距离变换后灰度值为0的像素点么陋，v]，乃砌阴=乃细幽+1，如果配准图在相应的距离变换后的窗口图像中对应的像素点B(x+甜，少+v)的灰度值小于册(掰由实际距离砌和相应的距离变换公式共同确定)，就认为它和窗口图像中的边缘点重合或者基本重合，玎材聊以=，?“ma+l。用同样的方法，对于集合B经过距离变换后灰度值为0的像素点研f，／】，乃幻膪=乃幻膪+I，如果配准图在相应的距离变换后的窗口图像中对应的像素点么(f—z，／一y)的灰度值小于掰，则胛“m6=胛“川6+1，最后运用公式(2-14)计算它们之间的相似度，相似度最大值所对应的配准位置为所求的正确配准崩15】。2．3．3形状配准2．3．3．1基于边缘形状的图像配准对边缘图像而言，判断两幅图像在几何上是否匹配，就意味着一幅边缘图像所在的像素位置上对应着另一幅边缘图像的边缘最稳定，在数学上表现为它们之间的方差最小。假设两幅边缘图像玳x，少)和，：(x，J，)，它们的大小都为M×Ⅳ，其灰度直方图分别为H，(玎)和H：(玎)。日，(胛)、日：(胛)分别代表了灰度值为f的像素个数，其中灰度等级玎=f(f．1，2)，于是，灰度值f在两幅图像中出现的比率分别为pl(f)=日。(，z)／(M×Ⅳ)和p2(f)=日2(行)／(M×Ⅳ)。对于“x，y)每一个像素级胛，，：(x，y)相对于州x，y)灰度值为，2的对应的像素集合的灰度均值和方差分别用E·，z(门)和仃i：(胛)表示，它们的表达式为：面啦㈣2赤州蚤少y)(2-16) 弟2草图像配准理论————————————————————————————————————————————————一蠢z㈣2南，。酣(w她u∽)2(2．17)同理，对于，z(x，少)的每一个像素级，‘(x，J，)相对于，：(x，y)灰度值为，2对应的像素集合的灰度均值和方差分别为云z，一(门)和仃主。(门)，其表达式为：&’lo卜南以善缈少)(2-18)仃舳2南，愚“w)-_z“砌2(2．19)对仃iz(聆)以灰度值行的出现的比率p。(，?)进行加权平均得到基于，。(x，y)的期望方差为孑i：：盯iz=∑p，(，2)盯i：(，2)(2．20)同理，对仃主·(以)以灰度值的出现比率p：(刀)进行加权平均得到基于，：(x，y)的期望方差孑；．．：仃；，I=∑p：(玎)万乏。(，2)(2．21)仃2，l2乞p2(玎)万乏l(，2)(2．21)由此可以得出两幅边缘图像的交互方差(CI)为a[‘，，：]_(孑iz居；)+(孑；，。居?)(2．22)其中砰和盯；分别为边缘图像‘(x，少)和，2(x，y)的方差，定义为七击舌(似川州¨2击舌似川咖嘉冰∽炉砧2¨2击善驰川交互方差(CI)反映了两幅边缘图像灰度相关对应的稳定程度。为了更容易描述，将用CI的倒数形式AM表示：彳M[，。，，：]=盯?盯；／(孑2，：仃】2+孑：，。盯；)(2。23)AM的值随着两幅边缘图像的配准参数的接近而越来越大，将以此作为图像的 沈阳理工大学硕士学位论文配准标准【16，l71。2．3．3．2基于边缘拟合的无验证的图像配准基于边缘拟合的无验证图像配准算法步骤为：(1)为了使边缘更容易用数学语言表达，对边缘进行可变精度直线拟合，使其转变为直线：(2)对拟合后的直线进行分析和筛选，将边缘直线特征最明显的保留下来，这样可以提高配准的计算效率和稳定性；(3)用加权投票算法作为图像配准策略，计算图像变换参数，越稳定、越显著的边缘直线特征拥有越高的权值，保证配准稳定性。a．在配准图像中任取直线厶，三，组成直线对毛，在基准图像中任取直线厶，三，组成直线对E，，判断组成直线对的两条直线端点间距离是否小于距离阈值，成立则保留，否则，放弃。b．对两组直线之间的夹角差和长度比之差分别设定阈值疋和％，设两直线对之间的夹角差和长度比之差分别为a删和屯埘，满足：％，“<瓦且乇，肼<％，弓和％有权进行投票。c．通过上述两种约束后，直线对厶，三，与厶，三，之间的相似度为：％沪批等H·一等)陪24，式中o≤西，材≤1，西，肼越大则气与凡所构成的直线对匹配程度越高。求得相似度后，根据直线中的点仂，，乃，仇，p，)计算出相应的变换参数缈，口，出，砂)，并在配准参数空间相应位置中进行投票，每次投票的权值△v定义为：△V=R，×R，×R女×Rf×S口，肼(2-25)式中R，，R／，R，R，分别为四条直线的可限度。直线对易，％配准程度越高，组成直线对的四条直线可信度越高，则由特征B，呢确定的变换参数可靠性越高。当两幅图像中全体直线对完成投票后，取变换参数空间中最大得票值所在的网络中心为最后的变换参数【墙]。 一第2草图像配准理论——————————————————————————————————————————_=———一一2．4本章小结本章主要介绍了图像配准的基本理论知识，从配准的定义、主要方法、系统流程、关键要素、相似性度量进行了一下系统描述，着重介绍了一下基于边缘特征图像配准的方法。 沈阳理工大学硕士学位论文第3章边缘特征点的检测与配准3．1基于角点图像配准的概述角点是一种非常重要和直观的局部特征，对于图像整体信息的把握具有决定性的作用。角点具有计算简单、计算量小的特点，在图像配准、目标识别、运动分析、目标跟踪等领域都有相当广泛的应用。角点包括图像绝大多数形状信息，代表了图像特点，并具有旋转不变性，不容易受光照、拍摄角度等外部因素的影响，所以角点特征成为图像特征中的一个重要组成部分。角点可以是兴趣点，也可以是某些属性上强度最大或者最小的孤立点、线段的终点，或者曲线上局部曲率最大的点。对于角点的定义在一定程度上反应了角点检测所采用的方法，同时也反应了所检测出的角点具有的性质特性【191。角点检测方法有很多种，其检测原理也多种多样，大致概括起来可以分为三类：一是基于灰度图像的角点检测算法，二是基于二值图像的角点检测算法，三是基于边缘的角点检测算法。图像角点是属于图像特征点中的一种，因此基于角点特征的图像配准方法其步骤和基于点特征的图像配准方法步骤基本一致。基于角点特征的图像配准方法一般可分为角点提取、角点配准、选取变换模型及求取参数、坐标变换和插值四个环节【20】。在基于角点特征的图像配准算法中角点的提取和配准是整个图像配准过程的关键，这一过程将直接决定图像配准效果的优劣。特征配准技术主要包括松弛配准、聚类技术、寻找最小树等，这些配准技术的最大特点就是它们都是寻找特征点集之间的相互对应关系而不是单个特征点之间的相互对应关系，这样就使得特征点配准结果更加精确，这对于由于存在不清晰、定位不精确的点特征而使虚假特征点增多，从而使得配准结果不可靠的情况具有较大的优越性。3．2经典特征点检测算法介绍3．2．1Ha玎is角点的检测方法1988年，C1lrisHarris和MikeStephens提出了Harris特征点检测算法(也称为Plessey角点检测算法)，它是一种基于信号的局部自相关函数的点特征检测算法。．1R． 第3章基于边缘特征点的检测及其配准它在Moravec算子基础上提出，通过Taylor级数展开法扩展了思路，计算窗口沿任何方向移动后的灰度变化，最后通过数学分析确定特征点【20】。该方法受信号处理中自相关函数的启发，引入了与自相关函数相联系的矩阵肘，M矩阵的特征值为自相关函数的一阶导数，并且特征值的大小反映了局部相关曲率。3．2．1．1Harris角点检测原理H枷s角点检测算法的原理是将所处理的图像窗口w向任意方向移动微小位移(x，)，)，则灰度改变量为：妒∑w"k脚-，V】25孙Vk州+。时)『(3-1)=4x2+2c砂+砂2=G，y弘M(石，少)r式(3—1)中，又和y为一阶灰度梯反，口]通过对图像求卷积得到：x：娑：，Q(-1，o，1)dX】，：芸：，圆(_1，0，1)dV为了减小噪声干扰，提高抗噪能力，对图像窗口进行了高斯平滑，所选高斯窗口如下：w¨一愕2Ⅳ沙2]p2，H枷s算子用Taylor展开去近似任意方向，彳=x2ow，艿=护ow，c=伍y)ow和矩阵M=瞄三]设^和如是矩阵M的特征值，A和如与局部白相关函数的主曲率成正比，构成一个对M的旋转不变数，可以通过丑和五的值来判断平坦区域、边缘和角点，通常有以下三种情况【21】：(1)如果两个曲率值都很小，则表明局部自相关函数比较平妇，榆测|又：域为平 沈阳理工大学硕士学位论文坦区域；(2)如果两个曲率中有一个较大一个较小时，说明E0，y)垂直山脊的变化大，而沿着山脊的变化小，此处为一个边沿，局部自相关函数呈现山脊状；(3)如果两个曲率都很大，说明局部自相关函数有一个尖峰，此处为一个角点。图3．1图像像素点的分类因此，H撕s角点可以定义为局部区域最大值，公式如下：D甜∞)一七乃2似)(3—3)式(3．3)中，n∞)代表矩阵M的迹，det似)是矩阵M的行列式值，七值通常取为0．04。实际计算过程中，有如下两个关系：乃似)=A+如=么+B(3-4)DP《枷=^如=彳B—c2(3—5)角点响应函数鲫F可定义为：R=De“M)一后乃20彳)=4B—c2一尼(4+B)2(3—6)3．2．1．2H厕s角点检测步骤H枷s算法提取图像角点的过程如下：(1)计算图像每个像素点水平方向和垂直方向的梯度，两个方向梯度的乘积，这样就可以得到3幅新图像，每幅新图像中像素值分别为，，，，y和，，‘，肘中四个元素的值为： 第3章基于边缘特征点的检测及其配准M：＼IjL_，，，y(3-7)式(3-7)中，，：=，，木J，，，；=Jy术，，；(2)对矩阵M的四个元素进行高斯平滑，得到新的矩阵M：离散二维零均值高斯函数为：⋯一p(-≮掣)仔8，(3)计算原图像每个像素点的兴趣值，即R值；R：掣B9，I：+I÷j、(4)选取局部极值点，角点是局部范围内极大兴趣值对应的点，实际计算过程中，从每个像素为中心的窗口区域内提取最大值，如果中心点的兴趣值是最大值，则该像素点就是角点；Harris算子对尺度很敏感，在一个尺度下是角点，在另一个尺度下可能就不是了；目回图3．2Harris算于对尺度的敏感性(5)设定阈值，选取角点，局部极值点的数量往往很多，通过设定阈值，选取一定数量的角点。3．2．1．3实验结果及分析对H删s角点检测算法进行验证，实验效果如下：图3．3(a)为原始的H撕s对黑片进行角点提取的结果，图3．3(b)为对Harris中的一阶微分用3×3模板进行改进对黑片进行提取的结果，非极大值抑制的邻域为2。图3．3(c)为用改进的h硼s对house图片进行角点提取，当极大值抑制的邻域为2的情况，(图片是截取的，边界角点属于图片与背景的差距，是错误角点，应该去除，与算法无关)角点个数为66，图3．3(d)邻域为1．5时的情况，角点个数为75。图3．3(e)是用改进H删s提取的角点情况，提取的角点个数为47，图3．3(f)是用改进的H枷s对3．3(e)图缩 沈阳理工大学硕士学位论文小提取角点的情况，个数为29。观察可以得出，H砌s角点提取有误检测和漏检测的情况。(a)(c)(b)(d)(e)(t)图3．3Harris算子对简单图像的响应H附is算子是一种有效的点特征提取算子，根据Harris角点检测算法的原理、步骤和实验结果，对算法的性能分析如下：(1)Ha玎is算子对图像中的每个点都计算其兴趣值，然后在邻域中选择最优点。因此，在纹理信息丰富的区域，Harris算子可以提取出很多有用的特征点，而在纹理信息少的区域，提取的特征点则较少；(2)计算过程中通过图像一阶导数进行判断，灰度变化对特征点提取影响较小。H枷s算子是各向同性的，图像旋转不会影响角点的检测：(3)HaHis特征点提取算法对尺度比较敏感，不具有尺度不变性。因此图像缩放变换对算法影响较大，经常会得出错误的检测结果； 第3章基于边缘特征点的检测及其配准(4)角点提取过程中需要设定闽值，对于不同类型的图像通常需要做大量实验来得到适合该类图像的阈值；(5)提取的特征点是像素级的。3．2．2SIFT特征点的检测方法1999年，D．G．Lowe提出SIFT(Scale．inVariantfea叽e仃ansfom，即尺度不变特征变换)特征的概念，并且在2004年对其进行完善总结。后来Y．Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。SIFT特征算法是一种对局部特征进行提取的算法，在尺度空间寻找极值点。SIFT特征不受旋转、缩放、量度变化的影响，对视角变化、仿射变换、噪声也具有一定的稳定性，广泛应用于图像配准领域。SIFT算法主要包括4个步骤：建立高斯差分(DoG)尺度空间、特征点定位、确定主方向和计算特征描述子。3．2．2．1建立高斯差分(DoG)尺度空间为了模拟图像数据的多尺度特征提出了尺度空间理论。高斯卷积核是实现尺度变换的唯一线性核，二维尺度可变高斯函数为：G(x，y，盯)=i≮P七2+y2m一(3—1o)z冗a一于是一幅二维图像，G，y)的尺度空间三G，y，盯)定义为∞】：三(x，y，仃)=G(x，y，盯)木，(x，y)(3-11)其中，木代表卷积，J表示尺度空间，(x，少)表示图像上像素点的坐标，盯是尺度因子，选择合适的尺度因子是构建尺度空间的关键。为了能够在尺度空间内有效的提取到稳定的特征点，Lowe提出了高斯差分尺度空间(DoGscale．space)。通过利用不同尺度的高斯插值方程与图像卷积生成高斯差分尺度空间。D(x，y，万)=(G(x，y，庇仃)一G(x，y，仃))水，(x，y)=三(x，y，尼仃)一三(x，y，盯)(3-12)其中，D(x，y，盯)代表高斯差分尺度空间，其中后是常数，通常取√j。DoG算子计算简单，是尺度归一化的LoG算子的近似。为了实现多尺度特征点检测，SIFT算法中引入图像金字塔，通过不断卷积和降采样的方法在尺度空间构建金字塔。图像金字塔的构建如图3．4所示： 沈阳理工大学硕士学位论文尺度第二阶尺度第一阶高斯图像高斯差分图像图3．4高斯图像和高斯差分图像构造首先，选用不同尺度因子的高斯核(初始尺度仃，尺度因子忌)对图像进行卷积运算，得到左边的高斯金字塔图像，作为高斯金字塔的第一阶段。然后，对高斯金字塔的第一层以2倍像素距离进行采样，得到第二阶图像的第一层，对该图像采用不同尺度因子的高斯核进行卷积，可以得到一组图像，作为金字塔图像的第二阶，依次采用降采样和卷积，直到图像像素小于16×16为止，得到高斯金字塔图像。最后，将每一阶高斯图像相邻的两幅相减，就可以得到右边的高斯差分图像，即DoG图像。为了寻找尺度空间的极值点，对DoG尺度空问的每个采样点，与其图像域和尺度域的相邻点进行比较，如果全部大于或者小于相邻点，则该点为极值点，如图3．5所示，相邻点包括同一层相邻的8个点以及上下两层相邻的各9个点，共计26个候选点。图3．5高斯差分图像的极值检测 第3章基于边缘特征点的检测及其配准图像的高斯滤波减小了噪声对图像的影响，DoG图像减小了亮度变化对特征点的影响，在DoG尺度空间提取特征点保证了尺度不变性。3．2．2．2特征点过滤并精确定位DoG尺度空间受噪声和边缘影响较大，通过拟合三维二次函数可以较为精确的确定特征点的尺度和位置，达到亚像素精度。将尺度空间方程D(x，少，盯)通过Taylor级数展开，得到。似)=。+等Ⅳ+≯挈x(3-13)其中，x=㈨ay，筹=aDdXaDdyaDd仃a2D’石万一a2D础2a2Dayxa2Da锨a2Doxya2D砂2a2Dd缈a2Da仃a2DayGa2Da仃2式(3．13)中的一阶二阶导数是通过对附近区域的差分近似求得，对该式求导，令其为0，得到极值位置童：．；a2D叫aDX=一二—二·二二一8X1ax把式(3—14)代入式(3．13)中，可得：(3-14)。(膏)=。+争警(3-15)如果l。(龛)I<。．。3，该像素点为特征点，否则舍弃。高斯差分算子的极值在跨越边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。利用一个2x2的HessiaIl矩阵H计算主曲率：H=怯纠p峋D叫D眇IV～7H的特征值与D的主曲率成正比，令口和∥分别为最大和最小的特征值， 沈阳理工大学硕士学位论文，：竺，则B乃∞)=D。+D∥=倪+∥DPf∞)=D。D∥一(D砂)2=筇(3—17)乃∞)2一(口+∥)2一O∥+∥)2一O+1)2丽一了一—矿一_如果满足器<华(Lowe推荐，取哪则保留该特硪否贝U去除o3．2．2．3确定主方向每一个特征点的方向参数由该特征点附近邻域像素的梯度方向分布特性表示，这就使得算子具有旋转不变性。在(3．18)中所(z，少)表示(x，少)处的梯度值，秒(x，y)表示(x，y)处的方向，其中L为特征点各自所在的尺度：jmG，y)=√oG+1，y)一三G一1，y”2+o(x，y+1)一三G，y一1))2(3—18)【秒G，少)=tan。1(亿G，y+1)一三G，y一1))／(三G+l，y)一三G一1，y)))、。在特征点的邻域窗口内进行采样，利用梯度直方图统计邻域像素的梯度方向，梯度直方图的峰值为该特征点邻域梯度的主方向，也就是该特征点的主方向。其中，梯度直方图的取值范围是O～360度，每10度用一个柱表示，共计可以得到36个柱。一个关键点可能会被指定具有多个方向(一个主方向，一个以上辅方向)，在梯度方向直方图中，如果存在相当于主峰值80％能量的另一个峰值，则将该峰值作为该特征点的一个辅方向，这样可以增强配准的鲁棒性∞，。A图3．6由梯度方向直方图确定主梯度方向 第3章基于边缘特征点的检测及其配准3．2．2．4特征描述子生成首先，旋转坐标轴使其和特征点的方向一致，这样做的目的是保证特征描述符的旋转不变性。其次，以特征点为中心取一个8×8的邻域，如图3．7(a)所示，中心点表示当前特征点的位置，一个小格表示特征点邻域所在尺度空间的一个像素，箭头所指的方向表示该像素的梯度方向，箭头的长度表示梯度模值的大小，图中圆圈表示高斯加权的范围(距离特征点越近，其梯度方向信息的贡献就越大)。然后，在每个4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。如图3．7(b)所示，一个特征点由2×2共4个种子点组成，每一个种子点均有8个方向向量信息，产生一个32维SIFT特征向量，即SIFT特征描述符。这种邻域方向性信息联合的思想可以增强算法的抗噪能力，并且对于含有定位误差的特征配准也可以具有较好的容错性。(a)图像梯度(b)特征描述符图3．7图像梯度和特征描述符为了增强配准的稳健性，Lowe建议对每个特征点使用4×4共16个种子点来描述，这样就可以产生128维的SIFT特征描述符。这个128维的SIFT特征向量可以去除缩放、旋转等几何形变的影响；对特征向量的长度进行归一化处理，就可以去除光照变化的影响。3．2．2．5实验结果及分析图3．8为SIFT特征点提取效果图，实验效果如下：图3．8(a)为用SIFT算法对黑片进行检测的结果，发现在边缘上很多点，都被认为是局部的特征点，这样将大大加重了配准时计算的时间，图3．8(b)为用SIFT算法对house图片进行检测的结果。 沈阳理工大学硕士学位论文(a)(b)图3．8SIFT特征提取效果图根据SIFT算法的运算步骤和图像特征提取效果，对SIFT算法分析如下[24】：(1)SIFT特征是图像的局部特征，对图像的旋转、缩放、亮度变化保持不变性，对于视角变化、图像仿射变换和噪声也有较好的稳定性；(2)独特性(DiStinctiveness)好，特征包含的信息量丰富，适合在海量特征数据库中进行快速、准确的配准；(3)多量性，即使图像中存在较少物体也可以产生大量的SIFT特征向量；(4)可扩展性，SIFT特征可以非常方便的与其他形式的特征向量进行结合；(5)高速性，经优化的SIFT配准算法甚至可以达到实时的要求。当两幅图像的SIFT特征向量生成后，下一步采用特征点的SIFT特征描述符之间的欧式距离来作为相似性判定度量。取其中一幅图像中的某个特征点，在另一幅图像中欧式距离最近的点和次近的点，计算这个特征点到最近点和次近点距离的比值，如果比例阈值小于一定的值，则认为这一对点匹配。降低这个比例阈值，SIFT配准点数目会减少，但更加稳定。3．3基于边缘轮廓的角点检测算法实现及性能分析在图像边缘轮廓上有的点边缘曲率足够高，这样的点可以定义是角点。角点一定位于图像边缘上，这样就不需要像原始方法那样搜索整幅图像，只需要沿着轮廓对可能是角点的特征点进行检验，这样不仅大大减少了计算量，还提高了角 第3章基于边缘特征点的检测及其配准点的提取精度。因此可以沿着边缘轮廓对可能是角点的特征点的曲率进行判断来提取角点。基于图像边缘信息方法的最早途径之一为基于边缘轮廓链码的角点检测方法。主要分为三个步骤：首先，对进行预处理的图像进行边缘分割；其次，对分割后的图像中八个方向上寻找相邻的边缘点，并对其进行编码，得到边缘轮廓；最后，沿着边缘轮廓链码对图像中的边缘点进行描述，提取出角点。根据边缘轮廓链码对图像中的角点进行描述和提取，有很多种方法，如通过轮廓链码的特征点的坐标寻找具有最大局部曲率的点；对轮廓链码进行多边形估计，寻找线段的交点或被描述成两条直线的交叉点等。3．3．1基于图像边缘轮廓局部曲率的CSS角点检测Mokht耐all和Suomela[25l在WitkiIl提出的尺度空间的图像分析理论的基础上提出了基于边缘轮廓曲率尺度空间(CuⅣatureScaleSpace，CSS)的角点检测算法。他们首先利用Callny算子对原始图像进行边缘检测，然后把角点定义为局部曲率绝对值最大的特征点，然后根据边缘轮廓链码提取角点。因为图像中存在噪声，在尺度非常小的时候，寻找这些局部绝对值最大的点作为角点候选点，这样提取出的局部绝对值最大的边缘点特别多，所以不断增大尺度，随着曲率尺度的变化，噪声逐渐被平滑，这样使真实的角点保留下来，但这样的做法有一定的局限性，随着尺度的增大，角点位置也在不断发生变化，这样对角点的定位相当差。所以算法首先从高曲率尺度下检测出角点，然后逐渐缩小尺度，在多尺度下跟踪定位角点，这样改变了角点的定位精度。尺度的减小过程中，只需要计算候选角点，大大降低了计算量。CSS角点检测技术适合于多尺度平面曲线的不变几何特征(曲率零交叉点或极值点)。计算经高斯平滑后的曲线轮廓曲率表示为(曲线L用弧长参数u)：坳川=业鬻等舞驴p㈣(x“(“，仃)‘+y。(“，仃)‘)⋯其中：吒(甜，盯)=x(甜)09。(甜，盯)瓦。(甜，仃)=x(甜)Qg。。(甜，盯) 沈阳理工大学硕士学位论文儿(“，仃)=y(甜)og。(甜，盯)y。。@，仃)=y(甜)og。。(甜，仃)o是一个卷积符号，“为弧长参数，提尺度参数g(“，仃，)是高斯函数g(“)在不同尺度q的形式咖州=去e卅鲁"m．．曲率的推导∞，：图3．9弧线的内在定义在曲线上任何点的曲率被定义为瞬时变化率y，瞬时变化率是P的切线和x轴的夹角，关于弧长度s，鉴于c：掣曲率c可以被定义在函数x(s)和y(J)导数的oS黼文=塞小罢乒窘肛窘oSosoS所以罢=姜，窘=学，因此曲率可以用训，夕表示q训卜簖此外，函数x(s)和y(s)一定和下面的函数有关联 第3章基于边缘特征点的检测及其配准C％洲．i2cos∥，÷=sm沙os3．3．2具有动态支持域的改进的CSS角点检测具有动态支持域的CSS算法基本步骤：(1)首先检测灰度图像的边缘获得一个二值边缘图；(2)从边缘图中提取边缘曲线，填充断点，找到轮廓上T型交叉点，标记为T型角点；(3)以高斯函数的参数。为尺度因子，在固定低尺度下计算轮廓曲线上任意一点处的曲率，以保留所有真实的角点；(4)所有局部曲率最大点作为候选角点，同时利用自适应门限控制和角点的角度控制剔除由于边界噪声和琐碎细节引起的伪角点。3．3．2．1Canny边缘检测良好的边缘提取算子应该有三个指标：第一个减少失误概率，尽可能减少边缘点的实际损失，同时尽量避免非边缘点检测为边缘；第二是定位精度高，检测到的边缘应尽可能接近真实边缘：第三对每一个边缘点进行唯一响应，得到单像素宽度的边缘。Callny算子是最好的阶跃型边缘检测算子，它把一阶导数的局部最大值定义为边缘。其基本思路是，首先使用高斯滤波函数对图像进行平滑，然后再由局部最大的一阶导数来确定边缘点。C籼y算子在一般情况下，可以检测几乎所有的图像边缘，并且定位较为准确。通常可以实现单像素边缘。具体步骤如下：(1)利用二维高斯滤波函数对图像厂(z，J，)进行卷积来平滑图像厂木G口(x，y)，其中口为响应的尺度因子；(2)使用微分算子(例如Prewitt算子，Sobel算子)，计算梯度矢量的模和方向。求出了边缘方向，就可以把边缘梯度方向大致分为四种(水平、垂直、45。方向、135。方向)，并且可以找到这个像素梯度方向相邻的像素；计算梯度矢量的模和方向：M。=ll／(x，y)乖VG。(x，y)l|4：丝!丛里g!兰!塑。M， 沈阳理工大学硕士学位论文(3)非极大值抑制梯度幅值，就是便利图像，如果在方向彳。上使M。取得局部极大值的点就是图像边缘的点；(4)使用双阈值算法检测和连接边缘。即使用累计直方图计算两个阈值，任何一个比直方图高阈值高的一定是边缘；所有低于低阈值的一定不是边缘。如果检测大于低阈值，但小于高阈值，它取决于像素的相邻像素，如果有超过高阈值的边缘像素，则该像素是边缘，否则就不是。3．3．2．2自适应局部门限控制在上述确定所有候选角点中，虽然一些点被检测为局部最大值点，但是由于它的曲率同它支持域内临近点之间的曲率差往往很小，这就是产生圆角点的一种情况，这种圆角点也是伪角点，幸运的是，可以通过使用一种自适应局部曲率阈值来删除这种圆角点。原则上，候选角点的自适应局部曲率阈值根据它的邻域的曲率来设定，局部极大值的绝对曲率小于此自适应局部曲率阈值被认为是圆角点，从而删除。这种自适应阈值由下式给出：孔们钉撕。1融再斋。器(f)(3’20)上一十L1十lj⋯上，式中，均值云用来描述邻域的曲率。在这种情况下，支持域(ROS)被定义为从一个邻近的局部曲率最小值到次小值点，曲率从候选点到两端严格递减。在上述公式中，∥是曲线上角点候选点位置，厶和三：是支持域的尺寸，C是一个系数。应该指出，如果C设置为1，没有被删除的角点；为了保留一个曲率函数波形是标准的三角形角点，C边界值为2。通过观察，圆角点的绝对曲率函数是凸的波形，而不是更清晰三角形。因此，从理论上C应大于1，并且小于2，选择了C三1．5，它适用于几乎所有的图像。通过各种测试，发现这个值是稳健的，它的变化不会影响角点检测。3．3．2．3角点的角度控制一般情况下，标准的角点应该是一个相对明显的尖角的顶点。如果知道曲线上各点的角度，就会很容易地识别一个角点是真正的角点还是伪角点。这种方法的关键在于使用适当的支持域，即一个合适的尺度。考虑在图3．10所示的模糊的情况下，在这一条曲线上有5个点可以被视为最大的局部曲率值和候选角点。如 第3章基于边缘特征点的检测及其配准果通过一个小的ROS，所有的5个点都被视为真正的角点；如果选用一个更大的支持域，弯道处角点2，3，4可能会被视为虚假的角点。因为特征尺寸不是先验的，因此找到真实的角点是十分具有挑战性的。图3．10角点的一种模糊情况这启发使用一个动态的支持域，它是由候选角点自己的特征决定的。对于一个候选角点来说，其ROS是根据同它相邻的两个候选角点确定的。在图3．10，如果所有标记5个点都是候选角点，则候选角点3的支持域跨度从2点至4点，然后根据它的形状角度来判断它是一个真正的角点；另一方面，如果经过自适应阈值检测之后只有1，3，5三个点是候选角点，候选点3的支持域跨度就从1点至5点，因为从1点和5点接近是一条直线，它很可能被视为虚假的角点。因此，这个角点检查标准为：如果160。≤么Cf≤200。则e就是伪角点，否则Cf就是真实的角点。么Cf由下式给出：么c』=Itan-1(△誓／△Ⅳ1)一tall-1(△艺／△五)l(3—21)式中：战：手笠硼)叫小△K：÷笠聊)川∥)上1』=∥+l上1，=卢+11∥一J1Ⅳ一l必=古∑x(f)一x(∥)，△E=≠∑】，(f)一y(∥)』吃l=Ⅳ一岛上。2，=∥一L2由于候选角点的序列可能会发生改变，需要进一步的迭代和反复检测，直到它的序列不再变化，收敛到这个标准，这样候选角点的边界噪声和琐碎细节可以被删除，还可以保留多尺度的主要特征。3．3．2．4实验结果与分析Farahnaz及Moht2uriall以角点数量和位置评价角点检测器的稳定性，并提出了相应的角点数一致性(ConsistenceofComerNumbers，CCN)概念，通过旋转、尺度等 沈阳理jI：人学硕士学位论文变换验证检测器的稳定性。设原图中角点的数目为Ⅳ0，变化后检测器检测出的角点数目为Ⅳd，则角点数一致性可以表示为(?(jⅣ：100％×1．1一I～“一～。可见，当CCⅣ的值越大，角点检测器稳定性越好。图3．11大小256×256的house图图3．12原图顺时针旋转10度(3-22) 第3章基于边缘特征点的检测及其配准图3．13原图缩小尺度到200×200表3．1用具有动态支持域的改进的CSS算法提取角点的结果算子—＼方式检测到角点真实角点丢失角点错误角点时间(s)改进正常72569160．4595cSS旋转10。算子缩小1．28Ha玎is算子715411170．5236655510O．45556659670．6952利用CCN算法，对支持动态域的CSS改进算法，对作平移、旋转、缩放的house图片提取角点一致性的检测，把表3．1中检测到的角点数目代入(3．22)中可得，旋转后的CCⅣ值为1．1，缩小后的a叫值为1．95，结合3．1表中真实角点、丢失角点、错误角点的数据，证明具有动态支持域的CSS角点提取算法的稳定性比较好，实验数据证明在时间上改进的CSS角点提取算法优于H州s算法。3．4基于边缘特征点的图像配准3．4．1基于奇异值分解的图像配准3．4．1．1奇异值分解的定义定理：若』4∈尺【”川，则存在正交矩阵，即U=[甜l，甜2，⋯，甜。]∈R“。“y=[V1，V2，⋯，V。]∈R“”使得，Ur彳y=疣昭(仃1，⋯，仃p)(3．23)．15． 沈阳理工大学硕士学位论文其中，p=min(聊，胛)，仃I≥仃2≥⋯≥盯p，仃。(f-1，2，⋯，p)是矩阵彳的奇异值，这些奇异值是矩阵彳Ⅳ彳或矩阵朋H的特征值的平方根。3．4．1．2奇异值分解的特征奇异值分解【27，作为一种特征矢量在图像处理具有广泛的应用，其主要由于奇异值分解的特征，具体如下：(1)SV对图像噪声和光照条件下造成的灰度变化十分不敏感，这一特性决定对图像预处理不需要严格要求，表明SV特征矢量的稳定性；(2)对图像做转置、平移操作，SV特征不发生改变，表明SV特征矢量具有旋转、平移不变性。3．4．1．3待配准图像的奇异值分解和配准，和，为两幅图像，分别包含加个特征点，∥=1，⋯，聊)和n个特征点，，(J=1，⋯，船)，对两幅图像进行奇异值分解，步骤如下：首先，分别取特征点‘(f_1，⋯，聊)和，，(／=1，⋯，，2)的矿×形邻域4和B，于是可以得到这两个区域的互相关系数：∥∑∑(4。，一万)·(B。，一百)c，f=型上兰广_I——忑一(3—24)“形2·盯(4)·仃(B)、7其中，万和百分别为区域彳和B的均值，盯(彳)和仃(B)为标准差。然后，构造相似矩阵G，其中c口是两个特征点Jr，(f=1，⋯，聊)和‘(／=l，⋯，聆)高斯加权的距离表示，即G∥=竿P铂2“，f=1，．一m川，⋯，胛(3-25)其中，勺=怖一10为两个特征点之间的欧式距离。参数盯用来控制两个特征点之间的相互作用，当仃越小时，q越大，一般盯取图像的吉高。最后，对G进行奇异值分解为：G=m叮，其中，丁，U是正交矩阵，D为 第3章基于边缘特征点的检测及其配准对角阵，对D中对角线元素进行降序排列。D中对角线元素值不为O的元素置为1，构造矩阵E，进而可以得到矩阵P，P=兀W。P是与G具有相同形状的矩阵，并且它可以突出相配准的特征点，抑制非对应的特征点。如果己是它所在行和列的最大值，则特征点，，和J，为匹配点，否则，，和~厂，不完全配准【281。使用具有动态支持域的自适应的CSS角点提取算法，利用局部曲率特性从两幅图的二值边缘上提取点特征，然后应用奇异值分解的算法，对提取出来的特征点进行匹配。具体实现过程如下：(1)边缘提取和轮廓编码。用自适应的CallIly算子获取进行滤波后的基准图像和配准图像的边缘二值图像；自适应C锄y算子是基于梯度幅度直方图和类内方差最小化自适应的确定高低阈值的方法，可针对不同的图像，实现双阈值的自适应提取，不需要人为设定任何参数，在边缘连接过程中，采用模糊控制技术提取边缘像素；(2)基于边缘利用具有动态支持域的改进的CSS特征点检测技术提取基准图像和配准图像上的特征点；(3)根据提取的特征点的坐标，用基于奇异值分解算法进行奇异值分解，进而得到配准的特征点对，实现配准；(4)继续深入探讨新的研究方法，删除部分误配准点。3．4．1．4实验结果和分析图3．14用改进的CSS算法对原始图(沈阳理工大学图书馆)提取角点的结果，总共为319个特征点，图3．15用改进的CSS算法对原始图平移后的图片提取角点的结果，总共为298个特征点；图3．16用改进的CSS算法对原始图旋转后的图片提取角点的结果，总共为316个特征点。 沈阳理工大学硕士学位论文图3．14原始图提取角点情况图3．15原始图平移12个像素提取角点情况图3．16原始图顺时针旋转15度提取角点情况图3．17(a)为采用基于奇异值分解算法对原始图与平移后的图像进行配准的结果，图3．17(b)为采用基于奇异值分解的算法对原始图与旋转后的图像进行配准的结果。 第3章基于边缘特征点的检测及其配准(a)(b)图3．17基于奇异值分解对图像进行配准表3．2基于奇异值分解配准结果图3．18为不同模态两幅图像用改进的CSS算法提取角点情况，3．18(a)中角点个数为303个，3．18(b)中角点个数为294个。(a)3．18待配准图像的角点提取情况．39． 沈阳理工大学硕士学位论文果。图3．19为采用基于奇异值分解的算法对图3．18中两幅图像的进行配准的结3．19基于奇异值分解的图像配准从实验可以看出，基于奇异值分解的特征点配准方法，对于一幅图像的不同变换效果明显，因为SV特征向量对平移、旋转特征具有不变性，对配准图找到合适的变换就可以与原图像进行匹配。从图3．19可以看出具有同一特征不同模态的两幅图片进行配准效果不是特别好，还有待改进。3．4．2基于马氏距离的图像配准3．4．2．1马氏距离概念马氏距离(Mahalanobis距离)是由印度科学家马哈拉诺比斯(P．C．Mallalanobis)提出的一种基于统计距离的测度方法。它是一种计算两个未知样本集的相似度的方法。不同于欧式距离，马氏距离考虑到各种特性之间的联系，它的大小不仅与各个点集相对分布有关，而且与各个点集自身的分布有关tz引，并且是尺度无关的。马氏距离必须满足3个基本条件：设x、弘z是总体G的3个样本，则(1)d(x，y)≥O，当且仅当x=y时，d(x，y)=0 第3章基于边缘特征点的检测及其配准(2)d(x，y)=d(y，x)(3)d(x，z)≤d(x，y)+d(y，z)对于由，z个样本z，=(x，，")r构成的样本空间z={(而，M)r，⋯，(以，J，。)r}，两个样本之间的马氏距离为坞=√(z厂zycl(z厂z，)(3—26)任意一个样本点样本均值∥=(段，∥，)的马氏距离定义为A如=√(z，一∥)rCl(z，一∥)(3．27)其中e为协方差矩阵：∥：=c从，∥y，=去[喜砖，喜只]7e=击隧二舡％驴以】]3．4．2．2马氏距离的仿射不变性马氏距离具有仿射不变性，对平移、缩放、旋转都具有不变性，证明如下：(1)平移不变性令[；：]=[；]+[；]，贝u有[笤]=[竺]+[；]e’=击陇二舡砧肛卅=击隧二焉牡唧。坞川w叫=C。得删=厄i砭再；丽：厄i不而：尥因此可以证明马氏距离具有平移不变性。(2)缩放不变性 沈阳理工大学硕士学位论文令[；：]=七[；]，脯阱尼[：：：]e7=击眺二舡一∥锢=击雠嘲砟j他棋Ⅵ]]=尼2C一得删=厄丽丽=忙刊7’·古·c少地。刊=魍证明马氏距离具有缩放不变性。(3)旋转不变性嘲=盛甜荆私蝴锨]由协方差矩阵的性质Var(么丁)=彳var(丁)彳7其中A为一个拥有n列任意行的矩阵，var(丁)表示求n维向量的协方差矩阵。则有星-_雾≤∥，得A倒=√(z；一∥’)rc：一(z；一∥’)=√》(刁一∥)】r．(p卜1c三1p～)．p(互一∥)=√(z，一∥)7’p71·(p71-1cjlp-1)·p(z，一∥)=MDi则证明马氏距离具有旋转不变性。3．4．2．3基于马氏距离的图像配准马氏距离操作的对象不是图像的区块，而是特征点集。通过计算两幅图像每个特征点到各自特征点集中点的马氏距离，确定特征点是否配准。由于马氏距离具有仿射变化不变性，因此在发生仿射变化的情况下配准图像中特征点到特征点 第3章基于边缘特征点的检测及其配准集的马氏距离与标准图像中特征点到所在特征点集的马氏距离依然相等。基于马氏距离对两幅图像进行配准的步骤：(1)利用改进的CSS算法对配准图和基准图提取特征点，得到两个特征点集彳和B：(2)计算特征点集么和B中的点到各自点集的马氏距离d，和d，，选择彳和B中相同的d，和d，，作为候选匹配点对；(3)计算z和以的马氏距离方差仇：竺￡≠』，并计算q的均值∑B仇=L。刀(4)设眈中的最大值朋缸眈，如果肋缸哦K眈，则删除所有大于K砬的特征点，重复(2)_(4)。理论上讲，正确的配准点的马氏距离方差巩应该等于0，在步骤(3)之后删除以≠0的点即可。但是，由于实际的特征点分布并不是完全相同的，所以见往往是一个略大于0的值；同时，由于同名像点中也存在错误的配准点，会对计算马氏距离中的均值、协方差等产生影响；对于不同的图像，会有不同的马氏距离方差值见。正确特征点的玻往往在眈附近均匀分布，可以不采用固定的阈值，采用取和马氏距离方差均值域比较的方式剔除错误的配准点。K是一个系数，当K取得越大时剔除的特征点越多，计算速度也越快；K取得越小时剔除的特征点越少，循环次数越多，计算速度也越慢，这里取K=3。3．4．2．4实验结果与分析图3．20为用改进的CSS算法对原始图提取角点的结果，总共为305个特征点，图3．21为用改进的CSS算法对原始图向上平移后的图像提取角点的结果，总共为289个特征点；图3．22为马氏距离对原始图与向上平移后的图像进行配准的结果。 沈阳理工大学硕士学位论文图3．20原始图图3．21原始图向上平移12个像素图3．22原始图与向上平移12像素后的图像配准结果图3．23为用改进的CSS算法对基准图提取角点的结果，总共为291个特征点，图3．24为用改进的CSS算法对与原始图在不同传感器不同时间存在共同场景的配准图提取角点的结果，总共为219个特征点；图3．25为马氏距离对基准图与配准图进行配准的结果。 第3章基于边缘特征点的检测及其配准图3．25基准图与配准图进行配准的结果表3．3马氏距离配准结果对比配准点对总数正确配准点对错误配准点对正确率——————————————————————————————————————————————一平移变换2242222O．99投影变换249186630．75-45． 沈阳理工大学硕士学位论文实验结果证明，马氏距离不仅对于同一模态下图像的平移、旋转、缩放等仿射变换，配准正确率比较高，而且对不同模态下的图像配准效果明显，由于还存在很多误匹配点，需要进一步对其进行改进。3．5本章小结本章采用基于边缘特征点对图像进行配准，更加利用了边缘的信息，不用从整幅图像找特征点，只要沿着边缘进行搜索就可以实现，这样可以缩短提取边缘点的时间。CSS角点提取算法是利用边缘的局部曲率来提取角点，利用了边缘的形状特征，确保了对旋转、平移、缩放的不变性，保证了提取角点的稳定性。改进的CSS算法具有自适应门限控制和角点的角度控制，避免了原始的CSS为了避免噪声必须不同尺度下提取角点的劣势，增加了算法的鲁棒性。对提取出的特征点分别用基于奇异值分解和马氏距离的方法进行配准，证明这两个方法都具有平移、旋转不变性，对同一模态的图片配准结果很明显，但是奇异值分解对于不同传感器、不同时间获取的具有同一场景的两幅图像配准效果不太明显，利用马氏距离对这种情况作实验，发现正确率挺高，有待于对错误匹配点的剔除作出改进。 第4章基于改进的部分Hausdorfr距离的图像配准第4章基于改进的部分Hausdor圩距离的图像配准把Hausdorff距离进行二值图像的比较最早是由H眦enlocher提出的。使用Hausdorff距离进行图像比较时不需要建立点与点之间的对应关系。通过计算Hausdorff距离并寻找其最小值，为把一个模板配准回源图像相应位置提供了一种快速的计算方法。因为原始的Hausdorff距离计算对图像噪声较为敏感，针对此，人们提出了较多的Hausdom距离改进方法。和其它常用的距离度量相比，具有以下优点：(1)在基准图和配准图之间，无需创建特征点间的对应关系，仅需计算两个特征点集之间的最大距离；(2)可有效屏蔽当图像中存在伪特征点、噪声污染、部分遮挡等引起的配准误差的情况；(3)计算复杂度小，实时性高。4．1Hausdorff距离定义及经典算法Hausdorff距离是描述两组集合之间相似程度的一种量度【30】，是一种定义于两个集合之间最大最小(ma)(．min)距离。假设有两个集合彳={口。，口：，⋯，口，)和B={6l，6：，⋯，％)，则彳和B之间的Hausdor口距离定义如下：日(彳，B)=max(办(4，召)，办(B，彳))(4—1)式中，办(彳，B)2罂骝”讣厅(B，彳)2磴册卜口川⋯为某种定义在两个集合间的距离范式。这里，式(4—1)是Hausdorff距离的标准形式，函数Jiz(么，B)称为从集合么到集合B的有向Hausdorff距离，即办(彳，B)实际上是对点集4中的每个点口，到B集合中点以之间的距离忱一以lf进行排序，再取该距离中的最大值，即为而(彳，曰)的值。如果B为模板，彳为源图像，则一般记乃(B，彳)为前向Hausdorff距离，乃(么，B)为后向Hausdorf．f距离，日(彳，B)为双向Hausdorff距离。双向Hausdorff距离日(彳，B)是单 沈阳理工大学硕士学位论文向距离^(4，B)和办(B，彳)两者中的较大者，它度量了两个点集之间的最大不相似程度。所以，如果日(彳，B)=d，则表示彳中所有点到B中点的距离将不超过d。距离范数ll¨一般包括市区距离、棋盘距离、欧几里得距离。假设记两点为x=(x。，z2)，y=(J，，，y2)，则以上各种距离计算如下：市区距离‰(x，y)=k—y。l+lx。一少：J棋盘距离叱。，(x，y)=max(k—y。I，fx：一y：f)欧几里德距离dE=√(xl—M)2+(戈2一y2)2为了减少计算量，一般采用的距离为市区距离或棋盘距离。(a)(b)(c)(d)图4．1相l司形状的圆形目标的HD距禹图4．1中，(c)图为理想情况下的匹配，(d)图为含有噪声情况下的匹配。理想情况下时，设存在一个圆c。(点集4)，圆心为q；模板为圆c：(点集B)，其圆心为02，且圆C。和圆C2曲线连续，无其它边缘点，半径均为，．。图(c)表示这两个点集的配准过程。图中蝎，M：，M，，M。分别为过两圆圆心与两圆的连线交点，此时，圆C：与待配准的圆C．的Hausdorff距离为：日(彳，B)=ma)【(乃(彳，B)，办(B，么))=ma)【0M。M，I，lM。M：1)=lM。M：I可以看出，如果让C：沿圆心连线向圆Cl靠拢，则日(彳，B)逐渐减小。当模板C：与圆C，完全重合时，H(4，B)=0，此时配准效果最好，反映了点集的配准程度。在圆C1的圆心位置加入一个噪声点Ⅳl，则配准过程如图(d)所示，在模板和圆C1不重合的情况下有H(么，B)=max(1M：Dll，IM。M：1)，而在两个圆完全重合的情况下，由．4R． 第4章基于改进的部分Hausdorfr距离的图像配准于唯一的噪声点Ⅳ．的存在，而使得日(彳，B)=r。显然，由于噪声点出现使配准出现误差，此时不能把Hausdorff距离直接应用于图像配准工作中，因此需要改进HausdorfjF距离到其它形式来进行图像的配准。Dubuison和Jain通过对加入四种噪声的图像来进行配准提出基于平均值的Hausdom距离(modifiedHausdorf!fdistaIlce，MHD)【，t】，它采用统计平均的思想，其中，‰(郇)2玄荟曾¨o(4-2)式中，M为点集A中点的个数。‰彻(彳，B)表示了A点集中的点到B点集中的距离的平均值大小。则双向平均Hausdom距离为：‰(彳，B)=max(‰(彳，B)，‰(B，彳))(4-3)平均Hausdorff距离不需要任何参数，但它用到A中所有的点，如果A图像存在部分遮挡和外部点存在时，配准效果并不好，因为它采用统计平均的概念，以平均距离代替最大Hausdorff距离，而其中一些距离可能是外部点计算得到的。Hausdorff距离是表征两个点集之间的不相似程度。但对干扰十分敏感。为了解决这一问题，DabuekO．H眦enlocher在1993年提出了部分Hausdorff距离(partialHausdorffdistallce，PHD)的概念【32】，以便增强含有噪声或者伪边缘的配准能力。部分Hausdorff有向距离的定义如下：乃，(彳，B)2艺I幽忪一刎(砌表示按从小到大的有序排序)称为点集A到点集B的排序后的有向部分Hausdo姐fI距离。其中，厂代表一个分数厂∈(o，1]。艺I幽忙一刎表示从A点集中所有点到B点集的距离中大小所占比例为厂的距离。￡l必忙一圳求解方法为先求出点集A中所有的点到点集B的距离，然后将这些距离进行大小排序，取序号为厂×M的距离。M表示点集A的点数。当对两幅图像进行配准时，需要计算两幅图像A，B的Hausdorfr距离，引入两个分数，定义其为厶和厶，厶为前向分数(forward1jraction)，厶为后向分数 沈阳理工人学硕士学位论文(reverse丘action)，它们分别用于计算前向部分Hausdorff距离和后向Hausdorff距离。图像A、B的部分Hausdorff距离定义为：日矗厶(彳，B)=max(向厶(彳，B)，力7’(B，彳))(4-4)4．2基于遗传算法的搜索策略遗传算法【331(GeneticAlgorithms简称GA)是由美国MichigaJl大学的HollaJld教授于1975年提出的，它的思想来源于达尔文的进化论和孟德尔的群体遗传学说。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化概率搜索算法，根据优胜劣汰、适者生存的思想，采用基因变异、杂交、繁殖等手段，使种群不断优化来求解问题的最优值。它特别适用于处理传统搜索方法难以解决的复杂的和非线性问题，如旅行商问题、背包问题、调度问题等。经过多年的发展，遗传算法已经取得长足进步，已经可以应用到信息科学、计算机科学、运筹学、应用数学等多个方向。4．2．1遗传算法的基本原理借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，由一群个体组成的种群P(t)，其中每个个体都代表一个潜在解决的问题。通过复制、交叉、突变等操作产生下一代的解，算法中设定一个函数来判断个体的优劣，决定个体在进化中是否被淘汰或者保留。每一代进化过程中，淘汰掉适应度函数值低的解，增加适应度函数值高的解。执行一代代更新，这样进化N代后就很有可能会进化出适应度函数值很高的最优或次优解，即最优个体。遗传算法主要由三个基本算子组成：1)选择(Selection)算子：选择是从种群中选择较好的个体，淘汰劣质个体的过程。选择是建立在适应度评估的基础上，按照一定的规则，从第t代种群P(t)中选择出优胜的个体复制到下一代种弹，钔。适应值越大的个体被选择概率越大。选择方法通常的有排序与比例变换、竞争选择、轮盘赌选择等，其中Hollalld提出的轮盘赌选择最为常见，基本原理是根据个体的适应值计算每个个体在子代中出现的概率，并按照此概率随机选择个体构成子代种群；因为选择是一个随机统计过程，选择不同的方法，其带来的选择压力也有所不同，各种选择方法有其优劣的地方，在执行选择操作时，应该确保能把优良个 第4章基于改进的部分Hausdorff距离的图像配准体选择到下一代中去。对部分高维空间全局优化问题，在选择过程中由于与最优解接近的优秀个体的丢弃，会造成求解问题的失败，针对这种情况，提出了把最优个体直接复制到下一代的方法。运算过程中出现的种群个体聚集现象，人们也提出了适应值共享(fitnesssharing)和族(cluster)的概念；2)交叉(Crossover)算子：交叉算子是根据交叉率将种群中的两个父代个体随机交换某些染色体，产生新的染色体组合而生成新的个体的操作。交叉通常包括两个步骤：在选择的群体中随机选取两个染色体，交换这两个染色体的部分基因产生新的子代。交叉操作在遗传算法中起到关键的作用，是产生新个体的主要方法，一般认为优秀父代的基因会交叉操作后传递给子代，并且有可能生成更优秀的后代。通过交叉，遗传算法搜索能力得以飞跃提高。交叉算子一般有单点杂交、多点杂交与均匀杂交等：3)变异(Mutation)算子：变异算子是指以一定的概率对种群中的某些基因座上的基因值作变动，使其产生新的个体。变异算子操作的基本步骤分为：对种群中所有个体实现设定的变异概率判断是否进行变异，对进行的变异的个体随机选择变异位置进行变异。变异是一种随机搜索，利用变异的这种局部随机搜索能力可以加速向最优解收敛，与选择、交叉算子相互配合又相互竞争操作使其具备全局和局部平衡搜索能力。对种群引入变异操作，是为了减少由选择和交叉操作带来的陷入局部最优的可能性。遗传算法思想：(1)生成初始群体：(2)计算种群中每个个体的适应值：(3)根据适应值所决定的某个规则，选择复制好的个体进入下一代：(4)以一定的概率Pc进行交叉操作；(5)以一定的概率砌进行变异操作；(6)没有满足某种终止条件，则转到第(2)步，否则进入第(7)步；(7)把种群中适应值最优的染色体输出作为问题的最优解。程序的终止条件最简单的有如下两种：种群中的最优个体或平均适应度在连续若干代基本没有改进时终止；执行完预先设定的最大进化代数则立即停止。根据遗传思想设计算法的基本框图，如图4．2所示 沈阳理工大学硕士学位论文初始化种群’汁算适应度的值+选择操作+交叉操作+变异操作否繇素：眇Y变异操作0输出适应度值最优个体幽4．2遗传算法基本框图4．2．2遗传算法的基本结构由于遗传算法的操作简单，所以被广泛应用，通常由几个部分组成。根据不同的问题，修改算法的组成部分便可以得到满足。遗传算法一般组成部分为：(1)编码遗传算法种群中的每个个体的基因表达了具体的问题，一个可能的解决方案，因此在利用遗传算法的首要关键问题是染色体编码。许多应用问题结构很复杂，但可以化为简单的位串形式编码表示，将问题结构变换为位串形式编码表示的过程叫染色体编码，它是基因型空间到解空间的一个映射：染色体编码有以下四个性质组成：非冗余性一染色体和候选解之间的映射是一对一的；合法性一对编码任意排列都会得到相对应的解；完备性一问题空间中的任意解都能作为GA空间中染色体表现；L锄arckian性一某个基因的等位基因的含义不依赖于其他基因；(2)初始种群的生成根据设定的种群大小，随机初始化染色体来生成一个初始种群。种群的初始化是迭代算法的开始，因此初始化种群的好坏将影响后边的收敛性，因此根据不同的问题选择不同的初始化策略。一般来讲，可以选择这样的种群初始化策略：a)依据问题，把握最优解在整个问题空间的分布范围，在此范围．气’． 第4章基于改进的部分Hausdorfr距离的图像配准内设置初始种群；b)从随机生成的个体中挑选最优个体加入到初始种群中，不断迭代，直到个体数目达到预设的规模；(3)适应度函数选取适应度函数也叫评价函数∞】，是判断种群中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。适应度函数用来判断群体中个体或解的优劣，并作为后续遗传操作的依据。在遗传算法中，适应度函数是在比较排序的基础上选择概率来使好的个体有更大的适应度，以使在下代中胜出。在具体应用中，适应度函数的设计结合具体问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能；(4)遗传操作选择：选择操作也叫复制操作，根据个体的适应度函数值来决定它在下一代是被淘汰还是被复制【36，。一般地说，选择算法使适应度较大(优良)个体继续生存的机会较大，而使适应度较小(低劣)的个体生存机会较小；交叉：交叉操作是遗传算法的一个主要操作，体现自然界中基因融合产生子代的思想。交叉操作的执行受交叉率的影响，算法执行过程中，随机产生一个范围在0．1的小数，如果小于交叉率，则选择两条染色体进行交叉操作；变异：变异操作首先在群体中随机选择一个个体，以一定的概率随机改变其结构。遗传算法的一般过程可以表述为：Begint卜0；初始化种群P(t)；对P(t)进行适应值评价；Ⅵ恤le(终止条件不满足)doBegin通过选择算子选出中间代C(t)；对C(t)进行杂交和变异操作生成新一代P(t+1)；t卜什1；EndFnfl 沈阳理工大学硕士学位论文4．2．3遗传算法的搜索策略4．2．3．1变换模型和搜索空间如果通过一幅图像的两个点间直线经过变换后到第二幅图像中仍为直线【37】，并且保持平行，这样的变换叫做仿射变换。模板图像原来的坐标为(_)c，少)，经过仿射变换到基准图像中点的坐标为(x’，y7)，根据公式(2．7)可以知道，变换后的坐标可以表示为：式中，f。表示水平平移变量，f．，表示垂直平移变量，曰为旋转角度，s为尺寸缩放因子。本文实验选取的变换模型是仿射变换模型，包含平移、旋转、缩放，根据式(4．5)分析可知，变换模型可以由f。，f。，s，p四个参数确定，但在本文实验中，有必要对这四个参数进行一定的范围限制，如果记基准图像的宽度为w，高度为向，7那么，平移向量参数f，，f。一定得满足O≤f，≤w，0≤f，≤办。对于尺寸缩放因子s，如果仅从(4．5)考虑，只要是非负数都可以满足条件，但是如果不加限制，搜索空间将非常大，而且模板图像也可能放大到极大或者缩小到极小情况，这样将会给配准任务带来特别大的困难。所以在本文实验中，把尺度缩放因子的范围定为O．5≤J≤2，这就相当于待配准图像最小为参考图像的一半，最大为参考图像的二倍。4．2．3．2染色体编码配准要实现的效果是用待配准图像去基准图像中找到与它相同的部分，并且确定其具体位置。要得到这样的效果就得对待配准图像左上角的坐标作为编码对象。本文研究的配准变换模型为仿射变换，包含平移、尺寸变化、旋转操作，根据4．2．3．1分析可知，变换模型主要由水平方向上的平移坐标x，垂直方向上的平移坐标y，尺寸缩放因子s，旋转因子臼四个参数组成。四个参数结合到一起来表示一个问题的潜在解。本文在进行染色体编码时，为了实现算法快速性，将四个参、I，5-^斗，L‘0+y×9臼．m∞SC×S一+XZX×秒矽∞mCSX×S=Fy 第4章基于改进的部分Hausdor行距离的图像配准数分别编码成相应的格雷码，主要原因是：一是本算法要在基准图像上搜索与待配准图像左上角对应的匹配点的位置，二是二进制编码会使相邻的整数产生很大的距离，这样会加大计算的时间，而格雷码没有这样的缺点。本文实验所用到的基准图像的尺寸大小不超过1024像素×1024像素，而且只在水平和垂直方向上进行搜索，编码时，分别用10位表示图像的行坐标和列坐标，s、口分别用8位表示。本文实验中设定的尺寸缩放因子范围为o．5．2．0，就是说最小缩小到原来的二分之一，最大放大到原来的二倍。旋转角度设定范围为．30。到30。之间，以逆时针为正方向。在编码时，尺寸因子和旋转角度根据设定的范围进行256级量化。一个二进制编码为曰=k％一，⋯如岛，则它对应的格雷码为G=g。g州⋯92蜀，二进制编码转换到格雷码的公式为【38J：g。=九g，=6f+Io包，f=聊一1，聊一2，⋯，1格雷码转换为二进制码公式为：“=g。6l=g，“0gj，f=聊一1，聊一2，⋯，1其中，o表示异或运算符。4．2．3．3选择操作选择算子是按照一种确定的方式进行，主要分为两类：一类是从五个新生成的待选个体中选择出∥(1≤∥≤五)个适应度最高(目标函数值较大的个体)，将它们保留在子代群体中，该法记为(∥，五)一嬲进化策略：另一类是从∥个父代个体和其所产生的五个新个体合并在一起，并从这∥+五个个体中选取∥个适应度最高的个体，将他们保留在子代种群中，该方法记为∽+名)一船进化策略。二者均是基于多点搜索方法，其中(∥+允)一ES是一种保留最优个体的多点搜索算法，比较得知，(∥+五)一嬲较好地继承了父代的优良特性，收敛性好，但易于陷入局部最优，(∥，A)一醪跳出了局部最优，但由于放弃了上一代结果，所以收敛性较慢。这些传 沈阳理工大学硕士学位论文统的遗传算法的选择算子，都分别具有自己的优缺点，对于个体适应值函数的多峰值问题，使用这些传统的选择算子更容易陷入局部最优并且产生遗传漂移现象，因此，本文采用小生境遗传的适应值共享与适应值比例选择结合的选择算子。小生境遗传算法是在对群体进行选择操作前，计算个体之间的海明距离，如小于事先设定值，则对适应值低的个体以处罚函数，降低其适应值。共享机制小生境是通过反映个体之间相似程度的共享函数来调整群体中的各个个体的适应度，以维护群体的多样性，从而在这以后的群体进化过程中，算法能够依据这个新的适应来进行选择运算。共享函数的计算方法如下：记两个体x，，x，，其距离度量(基因型或表现型)为d，，=d(x。，x，)，定义一个小生态半径盯咖。。共享函函数为鼢(引：{1．(丧)，小‰比(4-6)0，D乃fe，1妒括e小生态半径盯加。由用户根据所期望的个体之间的最小分离程度事先估计。在进行实验之前，根据适应值共享的思想，应该先对个体适应值进行调整。随着进化代数对适应值共享半径选取不同的数值。本文实验中，选择进化代数为30代，则适应值共享半径在前10代时为5，然后的10代共享半径为3，最后10代的共享半径为2。在进行选择运算时，为了避免最优解在选择过程中丢失的现象，本文实验中直接把进化中最优的解复制到下一代，这样就可以保证优秀个体的保留。4．2．3．4杂交操作杂交操作只是作为一种辅助性搜索运算操作，设X。={x。，仃。)，％={％，％)为群体中随机配对的两个个体，则对这两个个体交叉操作后，可产生一个新的个体X。。={x。’，仃。)，其中x。‘可按下类方式之一来确定。无交叉，％=％ 第4章基于改进的部分Hausdorfr距离的图像配准直接交叉，艺={≥：嚣竺：掰j三?加权平均求值，％’=x。+臼(％一z。)秒为【0，1]范围均匀分布的随机数。常用的杂交操作包含单点杂交，多点杂交和均匀杂交，本文实验中，对常用的这三种杂交操作进行尝试。单点杂交，这是一个传统的方式，随机产生一个基因位，然后对父代基因中的这个位置的基因进行交换；多点杂交，在本文实验中染色体是有四个参数组成，可以看作基因串是由这四个参数组成的基因子串，多点杂交时候，是把父代中随机产生的基因位后面的全部基因位进行交换；均匀杂交，如果随机生成的基因位是二的倍数，则父代这个基因位才进行交换，否则，保持不变。实验中，发现这三种杂交操作并没有太大的差异。本文实验中，根据适应值大小判断是否把生成的子代复制到下一代种群中，生成的子代与原先的适应值进行比较，如果适应值大于原先的适应值，则将直接将生成的复制到下一代。记父代个体为p口纪玎订、p口rP耐2，它们对应的适应值分别为石、厶，经过杂交操作产生的子代个体为如f橱1、如f掰2，它们对应的适应值分别为Z’、^’，两个被接受的概率定义为∥cc矽r．、叫cc≯r：，分别表示子代如f肠1、c办j搿2被接受的概率。其计算公式如(4．7)所示：f1，Z’一Zp么cc印t={』笪(4—7)IPK，Z’<／：式中，K为一常数，本文中实验中取值为0．1，f=0，1在公式(4．7)中，如果子代个体比父代个体好，则子代以1的概率被接受：反之，子代以一定的概率被接受。引入子代接受概率，实际上是把父代加入到下一代的竞争中，如果父代比子代个体好，即父代生成差的子代，那么，父代将代替子代进入下一代，而予代将会被淘汰。与此同时，就会看到，在杂交的比较过程中，p钾eml与ckldl，parem2与cMld2进行比较，然后pareml与pnrenl2交换信息，如果p甜P刀，J『是好的个体，杂交交换信息后生成的子代个体c办f儿打也是好的个体，而眇P刀口是差的个体，杂交交换信息后生成差的个体c．jzf地，那么在父代与子代的竞争中，p口，．P，z髓将取代c办f耽，进入下一代，则进入下一代的就是幽z掰Z、 沈阳理工大学硕士学位论文p甜e船力，从这个过程可以看出，好的基因段在很大程度上被继续传递进入下一代。本文实验中选取子代接受概率为0．5。4．2．3．5变异操作变异是产生新个体的主要方法，假设群体中某一个个体Ⅳ={x，盯)，则由所生成的新的个体组成元素是：rqexp翌暑焉秽地⋯川洚8，【x；2z，+Ⅳ(u，叫)式中，Ⅳ(O，1)表示均值为0，方差为1的正态分布随机变量，r，f分别表示变异时整体步长和个体步长。本文实验中采用的是单变量变异，是根据变异概率，选择种群中的部分染色体进行变异操作。选择需要变异的基因位的部分基因进行比特翻转。同杂交一样，变异后的个体需要接受一定的概率。定义一个子代接受概率为础cc科，变异前的适应值为厂，变异后的适应值为厂’，叫cc叫计算公式如(4—9)所示．1，厂>厂脚cc印f={盟(4—9)【eK，厂<厂式中，K为一常数，本文中实验中取值为0．1，f_0，1。本文实验中，取变异率为0．1。4．2．3．6个体适应度评价适应度是衡量个体特性优劣的尺度。适应度函数∞，用来反映每一个染色体与问题最优染色体的差距，如果差距很小，则对应的适应度函数差就很小。适应度函数的取值大小与求解问题对象的意义有很大的关系。个体适应度评价的一般过程为：(1)对个体编码串解码处理后，得到个体的表现型；(2)由个体的表现型可以计算对应个体的目标函数值：(3)由目标函数值按一定的规则求出个体的适应度。由于遗传算法的选择运算是按照一种的方式来进行的缘故，每次都是从当前群体中选择出一个或若干个适应度最高的个体遗传到下一代群体中，这里只有个体适应度之间大小关系比较，而无算术运算，所以对个体适应度是取正还是取负，．58． 第4章基于改进的部分Hausdor仃距离的图像配准无特别要求。个体质量的好坏完全由它的适应度值的高低来决定，适应度越高，表明个体的质量越好，遗传到下一代的机会就越大；反之，适应度越低，则表明个体质量越差，遗传到下一代的就会就越小。本文实验采用4．3．1中改进的部分Hausdorff作为适应度的评价函数：1八墨力5雨高@。10)式中，县岘∞(4，召)为待配准图像点集A与基准图像中点集B之间的改进的部分Hausdorff距离。从式中可以看出，只慨∞(彳，B)越小，／(x，y)则越大，表明这一点适应度越高，图像的配准效果就越好，当只啦∞(么，曰)=O时，厂(x，y)取最大值，表明适应值最高。4．3基于改进部分Hausdorff距离的图像配准4．3．1改进的部分Hausdorff距离(MSE皿)通过几个改进的Hausdorff距离比较(如表4．1所示)，可以发现，针对不同的情况，每种改进的Hausdorf!F都有其独特的优势，在某个方面鲁棒性都有一定的提高，但是实际应用中还存在许多问题亟待解决。部分Hausdorff距离和平均Hausdorff都存在自己的优势，如果去粗取精，然后结合起来可以得到好的效果。表4．1Hausdorfr距离与其它改进形式的对比针对以上问题，这里综合出格点、噪声、遮挡等因素，采用均方误差的思想，找到误差最小的均方误差作为限制。例如，可以使用最大的距离和第1／2个最大距离的均值作为误差最小的距离，但这样有一定的单一性，采用广义的Hausdorff距离作为互补，寻找合适的前向(或后向)分数。前向(或后向)分数是为了找到给定一 沈阳理工人学硕士学位论文个适当的误差最小距离的D，进而提供一种高质量的数据集度量。引入聚类的方法，把大于一个固定阈值D的距离点看作出格点，进行剔除，小于阈值的看作是内点，用它进行计算。具体公式如下：HMsEm(爿，B)=max(办MsE皿(彳，B)，向MsE∞(B，么))(4．11)1N。‰删∽2击萎姒m姗m瑚(4。2)N。其中，彳、B是两个点集。M=∑缈D(d(口，B))，d(以，B)是点集彳上特征点口到点集B的距离。f1ztNY未找到正确的结果图4．4遗传算法与改进的部分Hausdorff距离配准算法实现流程4．3．6实验结果与分析输出结果实验选取种群大小为100，杂交率为0．5，变异率为o．01，疗=厶=o．85，以进化代数为算法终止条件，取值30，适应值共享半径前10代取值为5，10～20代取值为3，后十代取值为2。图4．5为改进的部分HD算法在正常情况下的配准效果图，(a)为基准图，(b)为配准图，(c)和(d)分别为基准图和配准图的边缘提取图。(a)基准图(b)配准图 第4章基于改进的部分Hausdorfr距离的图像配准(c)基准图的边缘图(d)配准图的边缘图图4．5正常情况下的配准效果从图4．5看出，改进的部分HD算法不仅正确配准到源图像中的图像，而且配准区域与原来从源图像中截取的区域差别十分小。表4．2为图4．4中基准图像与配准图像进行配准得出的实验结果。表4．2改进的配准算法与PHD算法比较从表4．2看出，改进的部分HD算法运行三次得到的变换参数在数值上比较接近，配准位置坐标在(134，106)附近变动，不存在平移、旋转、缩放，实验数据与实际情况是相符的。与传统的部分Hausdorff距算法比较，在时间和精度上都有很大的改进。图4．6为改进的部分HD算法对存在旋转的图像配准效果图。 (a)(b)图4．6顺时针旋转20度的配准效果从图4．6看出，图像存在一定旋转角度的情况下，用改进的部分HD算法对图像进行配准具有很好的效果。表4．3为改进的部分HD算法对存在旋转的图像进行配准的结果数据。表4．3改进的配准算法对旋转配准结果数据序号配准位置缩放大小旋转角度配准时间／s1(115，30)1．009766—20．165878292(115，31)1．009766—19．93139329_————————————————————————————————————————————————一从表4．3看出，算法运行两次得到的变换参数数值上比较接近，配准位置坐标在(115，30)附近变动，不存在大小缩放，顺时针旋转20。。这与实际情况基本相符。图4．7为改进的部分HD算法对存在部分遮挡的图像配准效果图。图4．7具有一定遮挡的配准效果 第4章基于改进的部分Hausdor仃距离的图像配准从图4．7可以看出，存在部分遮挡的情况下，用改进的部分HD算法对图像进行配准具有良好的效果。表4．4为改进的部分HD算法对存在部分遮挡的图像配准的结果数据。表4．4改进的配准算法对遮挡配准结果数据从表4．4看出，算法运行两次得到变换参数在数值上比较接近，配准位置坐标在(134，106)附近变动，几乎不存在平移、旋转、缩放。表4．4数据与表4．2数据很接近，说明改进的部分HD算法对部分遮挡有很好的效果。图4．8为改进的部分HD算法对存在色调和亮度变化的配准效果图。(a)(b)图4．8亮度增加和蓝色调减小的配准效果图(b)为亮度增加，蓝色调减小的配准图。从图4．8可以看出，存在色调和亮度变化的情况下，用改进的部分HD算法对图像进行配准具有良好的效果。表4．5为改进的部分HD算法对存在色调和亮度变化的图像配准的结果数据。表4．5改进的配准算法对具有色调变化配准结果数据从表4．5看出，算法运行两次得到的变换参数数值上比较接近，配准位置坐标 沈阳理工大学硕士学位论文在(203，67)附近变动，几乎不存在平移、旋转、缩放。实验数据与实际情况是相符，说明改进的部分HD算法对存在色调和亮度变化的图像的配准具有很好的效果。图4．9为改进的部分HD算法对存在噪声的图像配准效果。(a)(b)图4．9加入椒盐噪声的配准效果从图4．9可以看出，在存在椒盐噪声的情况下，用改进的部分HD算法对图像进行配准具有良好的效果。表4．6为改进的部分HD算法对具有噪声的图像配准的结果数据。表4．6改进的配准算法对具有噪声配准结果数据从表4．6看出，算法运行两次得到的变换参数在数值上比较接近滔己准位置坐标在(134，106)附近变动，几乎不存在平移、旋转、缩放。表4．6数据与表4．2数据很接近，说明改进的部分HD算法对存在噪声的图像配准具有很好的效果。4．4本章小结本章在介绍了Hausdorff距离定义和经典Hausdorfr距离算法基础上，提出改进的MSE．Hausdorf!f距离，以改进的Hausdorfr距离作为相似性度量，对基于边缘特征的图像进行配准。在配准策略上采用小生境遗传算法，加快了搜索速度。实验结果证明，该算法不仅对平移、旋转、缩放变换有一定的实用性，而且对噪声、出格点、遮挡、色调变化敏感性小，具有一定的稳定性。 第5章基于边缘特征点图像配准算法分析第5章基于边缘特征的图像配准算法分析基于边缘特征点的图像配准有两个重要的环节：一是图像边缘特征点的提取，二是特征匹配准则。特征点提取的准确性及稳定性将会对后续的配准工作产生影响。对需要配准的两幅待配准图像首先用Canny算子进行边缘检测，然后利用3．3．2节提出的具有动态支持域的改进的CSS角点提取算法提取两幅图像的角点，与传统的角点提取算法相比，CSS角点提取具有边缘约束，更加利用边缘的信息，所以在提取过程中，对噪声、灰度变化、位置变化、部分遮挡都有较好是适应性。3．3．2．4节实验结果和实验数据分析证明，具有动态支持域改进的CSS角点提取算法，对平移、旋转、缩放都具有一定的稳定性，并且在时间上小于在整幅图像上进行检测的H删s算法。然后分别根据3．4．1．3节介绍的基于奇异值分解的步骤和3．4．2．3节介绍的基于马氏距离的图像配准的步骤对已提取角点的两幅待配准图像确定匹配点对。奇异值分解利用数据分析法，找到大量数据中所含的模式，进而进行配准，3．4．1．4节实验结果和数据分析证明，基于奇异值分解的配准方法对于一幅图像的平移、旋转的仿射变换配准效率很高，但是对于不同模态的具有同一场景的两幅图像配准，效果不是特别明显，图3．19证明误配准特别高。马氏距离大小不仅与各个点集相对分布有关，而且还与各个点集自身分布有关，3．4．2．4节实验结果和实验数据分析证明，基于马氏距离的图像配准对一幅图像的平移仿射变换结果明显，配准率特别高，对于不同模态的两幅图像配准率也超过70％，要想做好后续的工作，需要在误匹配剔除上作出改进。这两种的配准方法的实验结果得出以下结论：(1)基于边缘特征点的图像配准的特征点比像素点少的多，大大减少了配准的计算量，提高了计算效率；(2)对图像位置变换比较敏感，大大提高了配准过程中的精度；(3)特征点的提取取决于边缘提取的好坏，所以待配准图像边缘的模糊或边缘连续性差，限制了算法的实用性；(4)匹配过程经常设定阈值，导致伪匹配点存在，最终会导致极大的误匹配率；(5)特征点所含信息量比较少，因而需要较强的约束准则和配准策略，以克服歧义匹配。 沈阳理工大学硕士学位论文第4章介绍的基于改进的Hausdorff距离的图像配准是以图像边缘为特征空间，对待配准图像的边缘点集进行对准。本文改进的MSE．Hausdorff是采用均方误差的思想，用加权求和的方式实现部分出格点的去除，然后求剩余点的Hausdorff距离均值作为最佳匹配距离，这样在一定程度上避免了噪声、孤立点、部分遮挡的影响。全局搜索策略上采用小生境遗传算法作为搜索策略。在遗传操作中，利用改进的MSE．Hausdorff距离作为配准的相似性度量来构造遗传算法的适应度函数，确定最佳的变换参数，完成配准图和基准图的配准。4．3．6节实验结果和实验数据分析证明，基于改进的Hausdorff距离和遗传算法的图像配准不仅对平移、旋转、缩放等仿射变换都有很好的适应性，而且对噪声、出格点、部分遮挡、色调变换敏感性都比较小，稳定性高。同时利用遗传算法搜索策略大大加快了配准的速度。但配准过程中也存在精度降低的情况，原因如下：其一，配准过程中使用搜索策略，搜索空间过大，在很大的搜索范围内每次都找到最优解几乎是不可能的，可以通过加大进化代数来提高匹配的正确性，其代价就是匹配的时间增加；其二，对存在旋转变换和几何失真图像的匹配，进行坐标变换后的图像某些像素点产生失真，这也是导致匹配精度降低的一个重要原因；其三，配准中用到阈值，选择大小合适的阂值很重要，阈值对匹配的实时性和准确性影响很大。实验结果得出以下结论：(1)基于边缘的图像配准不需要建立特征点的对应关系，计算简便：(2)边缘受图像尺度、旋转变换影响较小，保证了假设变化验证的有效性；(3)边缘代表了图像中大部分的本质结构，能较好的剔除传感器的类型和姿态变化导致的几何畸变对成像畸变的影响；(4)待识别图像量度不均匀时，由于边缘提取效果不太好，则不易识别，或识别速度很慢，一旦所选图像子图区域信息比较匮乏，则很难进行后续的特征提取和匹配；(5)基准图中存在多个与待匹配目标有着相似、甚至相同的边缘特征时，会导致误配准率增高。 沈阳理工大学硕士学位论文结论图像配准技术作为一门比较完善的算法体系，已经被广泛应用到各个领域，针对不同的领域，特别在计算机、传感器等技术飞速发展的今天，图像配准的研究更加得到拓展，对图像配准都有大不相同的要求和处理方法，各种不同质量和性质的图像也对图像配准方法提出了挑战。本文在分析了基于特征图像配准理论的基础上，围绕边缘特征对图像进行配准。首先，研究了基于边缘特征点的图像配准算法，对问题的主要部分——特征点提取方法、配准算法进行了讨论、分析，着重研究了改进的css特征点提取算法、基于奇异值分解和马氏距离的图像配准算法，通过理论分析和实验结果对比，证明改进CSS的特征点提取算法具有较好的稳定性和鲁棒性，奇异值分解和马氏距离的配准算法也有较好的性能。其次，研究了基于边缘轮廓特征的图像配准算法，对问题的主要部分——Hausdorff距离、遗传算法进行研究，采用改进的部分Hausdorf：f距离和遗传算法进行图像配准，通过理论分析和实验结果，证明所采用的改进的Hausdorff距离结合遗传算法具有较好的实时性和稳定性。但本文还存在许多不足，在以下几个方面还需要继续改进：(1)边缘提取的方法的改进。本文是基于边缘特征进行图像配准，边缘提取的好坏将直接影响到配准的效果，本来利用C锄y算子对图像进行边缘提取，如果能实现对Calllly算子进行改进，提取更多细节的边缘轮廓，将会有效增强图像配准的精度；(2)误匹配的剔除。本文采用基于边缘特征点的图像配准，以边缘提取的角点为特征空间，应用奇异值分解和马氏距离进行图像配准，虽然效果明显，但当进行投影变换时，错误匹配相当多。如何有效地剔除这些误匹配点对将会为后续的工作提供依靠；(3)阈值的自适应选取。本文提出以改进的部分Hausdorf!f距离作为图像配准的评价标准，其中为了消除噪声、遮挡的影响利用类最小均方误差的方式对一些点进行删除，用到了阈值，而这些阈值的选择将直接影响到图像配准的效果。本文采用经验的方式选取阈值，如果能实现阈值的自适应选取，将会增强图像配准的健壮性：(4)运算速度的提高。本文基于边缘轮廓的图像配准中采用遗传算法作为搜索策略，有效加速了图像配准的速度，但是合理选择和控制参数是影响算法性能的关键，可以采 沈阳理工大学硕士学位论文用其他算法，如梯度下降法、金字塔分层来加快搜索；(5)进一步提高方法的实用性。本文提出的方法主要依赖特征点所在的边缘信息，这样使算法具有一定的依赖性，致使在某些图像上受到限制。如何更有效地利用图像中的各种信息进行图像配准又是一个研究方向。总之，图像配准是一个非常复杂的问题，不同场合、不同图像需要不同的配准方法，几乎不存在对任何场合、任何图像都适用的配准方法。并且，配准精度将直接决定后续工作的成败。因此，对图像配准进行深入研究具有重要的意义。 沈阳理工大学硕士学位论文[2】[3】参考文献BrownLGASurveyofImageRegistrationT'echniques[J】．ACMComputingSuⅣeys，1992，24(4)：325-376Ⅵ7angR．T，SequentialHierarchicalSceneMatclling[C】，IEEETransComputers，1978，27(4)：359-366ShojiMuI．撇atsu，DeVelopmemofTemplateMatchingHardwareandItsHi曲一SpeedProcessingS仃ategy，ElectronicsandCo删叭lIlicationsinJapaIl，2001，84(11)：1667一1675孙焘，王秀坤，等．二维点模式图像的仿射变换配准【J]．计算机辅助设计与图形学学报，2005，17(7)：1497．1503牛力丕，毛士艺，等．基于Hausdorff距离的图像配准[J】．电子与信息学报，2007，29(1)：35-38彭文，董若峰，等．基于轮廓与特征点的医学图像弹性配准方法[J]．中国图像图形学报，2008，13(9)：1777．1782ShojiMu】．撇atsu．StrategyofHigh—Speed1、emplateMatcllingandItsOptimizationbyusingGA[J】．SystemsandComputersinJapan，2003，34(2)：30一36ZitoVaB，FlusserJ．Imageregistrationmemods：asurvey【J】．ImageandvisionComputing．2003．21—100李博．图像的不变特征检测与描述研究．重庆大学硕士学位论文[D】．2007．1．20那彦．基于多分辨分析理论的图像融合方法[M]．西安电子科技大学出版社．2007．4．25吴巾一．基于角点匹配的图像配准算法研究【D】．浙江工业大学硕士学位论文．2009．6．22叶耘恺．基于边缘特征的图像配准方法研究[D】．重庆大学硕士学位论文．2004．43．48H．Freenlan．Ont11eencodingofarbitra巧geometricconfigurations．II≈E．71．川习q刀即铂mn坨B．【[[[rL【l 沈阳理工大学硕士学位论文nans，ElectronCompute，1961，EC·10，250-268【14】M．K．Hu．VisualpattemrecognitionbymomentInVariallts．IRETrallsoninformationtheory，V01．IT-8，pp．179—187，1962【15]陶晓勋．基于特征的快速旋转图像匹配方法研究[D]．河海大学硕士学位论文．2007．19．35[16]葛永新．基于特征的图像配准算法研究[D]．重庆大学硕士学位论文．2006．23．25[17]谌安军，陈炜，毛士艺．一种基于边缘的图像配准方法【J]．电子与信息学报，2004，26(5)：679-684[18】张浩．多信息融合图像边缘特征提取及图像配准研究与应用[D】．浙江大学博士学位论文．2008．75．91[19]杨柳青．基于角点和边缘特征的图像配准方法的研究【D]．南京理工大学硕士学位论文．2009．27．49[20】HarrisC．GStephenM．ACombineComeraJldEdgeDetector[C】．ProceedingsoftheFounhAlVeyVisionConf-erence．1988[2I】贾莹．基于Harris角点检测算法的图像拼接技术研究[D】．长春．吉林大学硕士学位论文．20l0．20．56[22]廖斌．基于特征点的图像配准技术研究[D]．国防科学技术大学博士学位论文．2008．31．67[23]Ma玎D，PoggioT．Acomputationaltheo巧ofhumaJlstereoVision[J】．ProcRoySoc，London：B．1979，204．301-328[24]苏宇．基于特征点的图像拼接技术研究[D]．西安电子科技大学硕士学位论文．2008．43．101[25]X．C．Hea11dN．H．CⅥmg．CurvaturescaleSpacecomerdetectorwithad印tiVethresh01danddynamicregionofsupport【C】，Proceedingsofthe17mIntemationalConferenceonPanemRecognition，August2004，2：791-794[26]AnithaiRatt2urangsi，RolandT．Chin．Scalse—BasedDetectionofComersofPlanarCuⅣes．IEEEtrans肌tionsonpattemaJlalysisa11dmacllineintelligence．1992，Vol14．430—447【27】任仙怡，张桂林，张天序，等．基于奇异值分解的图像匹配方法[J]．红外与激光工 沈阳理工大学硕士学位论文程，2001，30(4)：279．281[28]谢凤英，赵丹培．ⅥsualC++数字图像处理【M】．北京：电子工业出版社，2008．223．400[29】范金城，梅长林．数据分析[M】一匕京：科学出版社．2005．160—161[30】RucklidgeWJ．EmcientlylocatingobjectsusingtheHausdo斌DistaIlce．IntemationalJourIlalofCoⅡlputerⅥsion，1997，24(3)：251—270．[31】DubuissonMP，JainAK．AModmedHausdorfrDistanceforObjectMatching[C】．ProceediIlgsofImem撕onalComrenceonPattemReco嘶tion，Jersalem，Israel，1994：566—568【32】LiTiallK锄ata．Anautomaticimage-mapregistrationalgorithmusingmodifiedpaIrtialHausdor行distance【J]．GeoscienceandRemoteSensingS)，I】叩osi啪，2005，5(4)：9050-9053【33]嘣naD．Russ，M冰W．Koch，CharlesW．Little．A2DRangeHausdomApproachfor3DFaceRecognition[C】．IEEEComputerSocietyConferenceonCoInpmerⅥsiona11dPattemRecognition．2005，3：2372—2373[34】张春美，孙雷，龚志辉．基于鲁棒Hausdo斌距离和遗传搜索的快速匹配方法[J】．海洋测绘，2009，29(1)：42．45[35】贺军．基于边缘特征的匹配算法改进研究[D]．南京：南京理工大学，2009．23．54[36】王开磊．基于Hausdom距离的图像匹配技术研究及应用开发[D】．华东师范大学硕士学位论文．2011．23．70[37】凌志刚，潘泉，等．一种基于边缘测度的加权Hausdorfr景物匹配方法【J】．宇航学报，2009，30(4)：1633．1638【38】李俊山，杨威，张雄美．红外图像处理、分析与融合[M】．北京：科学出版社，2009．56—74【39】孙瑾，顾宏斌，等．一种鲁棒型Hausdom距离图像配准方法[J]．中国图像图形学报，2008，l3(4)：763—767[40】HuiCheng．MatchingofSARImageandOpticalImagesBasedonEdgeFeatureEx仃actedViaSVM【C】．(ICSP’04)，2004[41]沈海滨，赖汝．基于图像中心矩的快速模板配准算法[J】．计算机应用，．75- 沈阳理工大学硕士学位论文2004，24(11)，116_112；[42】范俐捷，王岩飞，高鑫．基于PIU测度和遗传算法的图像匹配方法[J]．数据采集与处理，2008，23(2)：14l一145[43】徐建斌．一种基于Zemike矩和稳态遗传算法的遥感图像匹配方法【J】．电子与信息学报，2005，27(6)：924—927【44]沈海滨，赖汝．基于图像中心矩的快速模板匹配算法[J]．计算机应用，2004，24(11)，116-118【45]杨兵，刘永才，田金文，等．基于新的加权Hausdorfr距离的图像匹配[J】．红外与激光工程，2007，36(5)：0751一0753 沈阳理工大学硕士学位论文—————————————————————————————————————————————————————一攻读硕士学位期间发表的论文和取得的科研成果[1]郝万里，王琰．基于改进Hausdorff距离的图像配准．沈阳理工大学学报．已发表(2011年4月)．