（计算机应用技术专业论文）图像特征点匹配算法研究.pdf

硕士论文翌像特征占昨配算往研究 摘要 特征点匹配是计算机视觉和模式识别领域中一个基本而重要的问题。有着广阔的 应用背景，如图像配准、物体识别、运动目标的检测与跟踪、手写体识别等。同时它 也是计算机视觉的一个难题，这不仅是因为在图像获取和特征提取阶段阈值选取不当 等过程中会产生不同程度的噪声，使得本来精确的特征点之间的对应关系变得难以确 定，而且点集中往往有出格点和非刚性形变的存在，使得点匹配变得艰难和复杂起来。 特征点匹配是要找到两点集之间的对应关系和空问映射关系。以点的位置表示点 特征是一种最简单的特征。在多数实际应用中，都是存在非刚性形变的情况下对特征 点进行匹配，因此本文针对非刚性特征点匹配给出了两种实用的匹配算法： ( 1 1 提出基于寻找不变量的特征点匹配算法。它是对c h a n g 等的点匹配算法p l 进行 了改进，即利用原始算法的寻找匹配点对支持度方法来得到可靠的几何不变量，然后 给出了根据两点间距离不变量自上而下的推导出最大匹配点对集和仿射变换参数。理 论分析和实验结果表明本算法推理严密，在精确性和稳定性都有显著的改善，是一种 理想的特征点匹配算法。 ( 2 ) 第二种特征点匹配算法是对基于确定性退火的点匹配算法进行改进，给出了适 合确定性退火算法求解的新的目标函数形式，提出采用相似性度量值来约束匹配矩 阵，加快了匹配矩阵收敛的速度从而减少计算量，在退火率较高时也能得到比较好的 解。实验也验证了在相同退火率的情况下能够得到比改进前算法好的匹配结果，并且 适当提高退火率时仍然能够得到比较理想的匹配结果 关键词：匹配点对最大支持度匹配集确定性退火匹配矩阵相 似性度量值 硕士论文图像特莅点匹配算法研究 a b s t r a c t f e a t u r ep o i n t sm a t c h i n gp l a y sa nb a s i ca n di m p o r t a n tr o l ei nc o m p u t e rv i s i o na n d p a t t e r nr e c o g n i t i o n i tc a l lb ew i d e l yu s e di nm a n ya r e a ss u c ha si m a g er e g i s t r t i o n ，o b j e c t r e c o g n i t i o n , m o t i o nt a r g e td e t e c t i o na n dt r a c k i n g ，h a n d w r i t t e nc h a r a c t e r sr e c o g n i t i o na n ds o o n a tt h es a m et i m e ，i ti sa l s oa nd i f f i c u l tp r o b l e mi nc o m p u t e rv i s i o n b e c a u s et h et o w p o i n ts e t sn o to n l yh a v ed i f f e r e n td e g r e eo fn o i s eb u ta l s oe x i s ti no u t l i e r sa n dn o n 。r i g i d l r a n s f o r m a t i o n , w h i c hm a k et h ei s s u eo f p o i n t sm a t c h i n g s o m e w h a td i f f i c u l ta n d c o m p l i c a t e d f e a t u r ep o i n t sm a t c h i n gi n t e n t st od e t e r m i n ec o r r e s p o n d e n c ea n dt r a n s f o r m a t i o n b e t w e e nt w os e t so fp o i n t si ns p a c e i ti st h es i m p l e s tf o r mo ff e a t u r e st h a tp o i n tf e a t u r e s r e p r e s e n t e db yt h ep o i n tc o o r d i n a t e i nag r e a tn u m b e ro fp r a t i c a la p p l i c a t i o n s ，t h e r ei s n o n - r i g i dt r a n s f o r m a t i o nf o rp o i n t sm a t c h i n g s oi nt h i st h e s i s ，t w oa p p l i e df e a t u r ep o i n t s m a t c h i n ga l g o r i t h m sa r ep r e s e n t e di na l l u s i o nt on o n - r i g i df e a t u r ep o i n t sm a t c h i n g ： ( 1 ) ab a s e do nf i n d i n gi n v a r i a b l ea p p r o a c hf o rf e a t u r ep o i n t sm a t c h i n gi sp r o p o s e d w h i c hi m p r o v e sc h a n g sp o i n t sm a t c h i n ga l g o r i t h m s t h en e wa p p r o a c hu s e sf i n d i n g m a t c h i n gp a i r ss u p p o r tm e t h o do fo r i g i n a la l g o r i t h m s ，a n dt h e na c c o r d i n ga sd i s t a n c e i n v a r i a b l eo ft w op o i n t sb e t w e e no n es e ta n da n o t h e rs e tf r o mt o pt ob o t t o mg a i n e d m a x i m u mm a t c h i n gp a i r ss e ta n da f f i n et r a n s f o r m a t i np a r a m e t e r s t h e o r e t i c a la n a l y s i sa n d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mh a sr i g o r o u sc o n s e q u e n c ea n d b e n e r a c c u r a c ya n ds t a b i l i t yw h i c hi sap e r f e c tf e a t u r ep o i n t sm a t c h i n ga l g o r i t h m ( 2 ) t h es e c o n dm e a n so fa l g o r i t h mi m p r o v eb a s e do nd e t e r m i n i s t i ca n n e a l i n gp o i n t m a t c h i n ga p p r o a c h t h ei m p r o v e da l g o r i t h mp r e s e n tt h en e w f o r mo f t a r g e tf u n c t i o nw h i c h f i t sf o rc a l c u l a t i o no fd e t e r m i n i s t i ca n n e a l i n gm e t h o d ，a n da d o p tt h ec o m p a r a b i l i t y m e a s u r i n gv a l u ea sr e s t r i c t i o no fm a t c h i n gm a t r i xi no r d e rt oa c c e l e r a t ec o n v e r g e n c eo f m a t c h i n gm a t r i xa n dr e d u c eq u a n t i t y o fc a l c u l a t e w h e na n n e a lr a t i oi sr e l a t i v e 1 1 i g h e r , i m p r o v e da l g o r i t h mc a na l s or e c e i v ep e r f e c tr e s u l t s e x p e r i m e n t a lo u t c o m e sv a l i d a t e t h a ti m p r o v e dm e t h o d sr e a s u l t sa r eb e t t e rt h a no r i g i n a la l g o r i t h m su n d e rt h e $ a l t l ea n n e a l r a t i oa n dc a na t t a i np e r f e c tm a t c h i n gr e a s u l t sa l lt h es a m ew h e na n n e a lr a t i o ni sr e d u c e d b e f i t t i n g l y k e yw o r d s ：m a t c h i n gp a i r s m a x i m u ms u p p o r td e g r e e m a t c h i n gs e t d e t e r m i n i s t i c a n n e a h n gm a t c h i n gm a t r i xc o m p a r a b i l i t y - m e a s u r i n gv a l u e i i v1 0 0 1 2 6 0 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：麴垫播加g 年5 月2 7 日 学位论文使用授权声明 南京理卫大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名 麴蛰塑i。彻孝万月) 7 日 硕士论文 图像特征点匹配算法研究 1 绪论 1 1 引言 特征匹配问题一直是计算机视觉和模式识别领域中的一个非常基本而又重要的 工作。特征匹配是要找出对准两组或多组特征的空间变换。图像的特征反映了图像重 要信息，以这些特征作为模型进行匹配。局部特征有点、边缘、线条、较小的区域， 全局特征包括多边形和成为结构的复杂的图像内容描述。基于特征的匹配绝大多数都 是指基于点、线、和边缘的局部特征匹配。 特征点是图像内容最抽象的描述，与图像灰度相比，特征点相对于几何图像和辐 射度影响来说更不易变化，因此基于特征点的匹配方法可以克服利用图像灰度信息进 行匹配的缺点，由于图像的特征点比较象素点要少很多，大大减少了匹配过程的计算 量；同时，特征点匹配的度量值对位置的变化比较敏感，可以大大提高匹配的精度程 度；而且，特征点对图像噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的 适应能力。所以基于图像特征点匹配在实际中的应用越来越广泛。 1 1 1 气象图像配准 到目前为止，我国成功地发射的风云系列( f y ) 的气象卫星，为气象部门提供了 大量的气象云图，对于天气预报、各种灾害的监控和预防上，有着不可替代的作用， 而这些作用与气象卫星所提供的云图有着密切的关系。 本教研室的c c d 成像仪多光谱图像配准项目是关于气象图像配准的研究，c c d 成像 仪是气象卫星的主要载荷。经过调研在国内关于在不周谱段下成像获得的多幅气象图 像的配准问题的研究很少。正在研制中风云4 号卫星，其核心的f y 一4c c d 遥感器或称 为f y 一4c c d 成像仪正在设计阶段。该卫星对同一个地区分时成像，得到一组多光谱的 图像和一组全色图像，由于更换滤光镜、转换压缩数据、传送数据给地面需要一定时 日j ，所以每次成像有大约2 0 秒的间隔。因为是分时成像，在这个时j 、日j i 甘j 隔内，相机处 于一个非常复杂的运行状态。一方面卫星在轨道上向前飞行；另一方面，卫星又带有 随机的姿态变化，这个随机的姿惫变化可以分解为微小的方位旋转和微小的平移。以 上的因素将导致所得到的图像之甘j 有像差。由于像差的存在，在运用中会导致多光谱 和全色图像的信息融合不能很好地进行，进行像素级的数据融合则有很大的像差。所 以需要在具有2 0 个像素的像差范围内，用3 0 秒钟的时间，进行多光谱图像与全色图像 的配准，消除像差对多光谱和全色图像的信息融合所产生的影响，较好的将同一目标 1 颂士论文 图像特征点旺配算法研究 或区域的多个传感器的不同图像进行融合，从而提供信息更丰富、更真实、更清晰的 遥感图像，为进一步的分析处理做准备。 ， 在研究中发现因为在多源图像融合时，由于多光谱图像灰度特征和图像的纹理信 息有差别，因此很难运用基于图像灰度的方法进行配准。而基于特征点的配准方法较 基于灰度信息的配准方法计算量小，抗噪能力强，不宜陷入局部最小值。特征点提取 后就需要特征点匹配，基于图像之间是刚性变换则可采用简化的仿射变换。由于待配 准的气象图像是r 、g 、b - - 通道在同一地区的分时成像，图像数据量大并且配准的实 时性要求高，试验中可知影响实时和准确性的关键是特征点的匹配算法，因此就需要 研究特征点匹配鲁棒性强，速度快，精度高的算法。 i 1 2 医学图像配准 医学图像配准是医学图像融合的前提，是目前医学图像处理中的热点之一，具 有重要的临床诊断和治疗价值。医学影像学为临床诊断提供了多种模态的医学图像， 如x 线断层成像、m r i 、f m r i 、s p e t 、p e t 、d s a 、超声成像、脑磁图等。不同的医学 影像可以提供人体相关脏器和组织的不同信息。如c t 具有较高的空间分辨率，有利于 定位病灶，m r i 对软组织成像清晰，有利于确定病灶范围。而p e t 和s p e t 虽然空间分 辨率较差，但却提供了脏器的功能和代谢信息。所以临床医生迫切希望对不同图像信 息进行适当的集成。然而不同模态的医学图像成像原理不同，分辨率不同，成像参数等 不同，因此在图像融合i i 必须先进行图像配准。配准结果应使两幅图像上所有的解 剖点，或至少是所有具有诊断意义的点都达到匹配。 医学图像特征点匹配的方法从变换角度来分，可以分为用刚性的和用非刚性的 ( 包括仿射、投影，弹性变换) 两种方法。由于刚性变换不考虑坐标轴的尺度缩放，仅 存在坐标轴的平移和旋转在用于同一模式和不同模式的医学配准中已经发展成熟并 且在临床中得到了应用。然而，刚性的特征匹配只适用于不存在变形或刚性体的配准， 如：由于大脑的变形基本上被颅骨限制，所以同一患者的大脑图像可以通过刚性变换 来联系。对于患者和图谱之自j 的匹配，不同患者之b j 的配准以及存在变形的配准( 肿 瘤，开颅手术等) 刚性的特征点匹配都是不适用的。然而，医学图像配准中刚性体的 匹配只是很小的一部分，许多重要的临床应用需要非刚性变换柬描述图像之间的空间 关系。比如： ( 1 ) 在图像引导的神经外科和立体定向放射治疗中，为了提高定位的准确性和 自动化程度，需要将患者的图像和杯准图谱进行配准。在比较不同个体或人群大脑的 形状和功能的研究中，以及建立大脑的统计模型和图谱时，需要将不同患者的图像进 行配准。此时就需要非刚性特征点匹配来保证良好的配准效果。 2 硕士论文图像特征点匹配算法研究 ( 2 ) 在研究腹部以及胸部脏器的图像配准中，由于不自主的生理运动或患者移 动等使其内部的器官和组织的位置、尺寸和形状发生改变，以及在图像引导手术中由 于干涉引起的组织变形，需要非刚性变换的特征点匹配来补偿图像变形。 1 1 3 运动目标的检测和跟踪 运动目标的检测和跟踪是计算机视觉和图像序列分析中重要的研究课题，它可以 应用于交通监视、导航控制、运动估计等领域。运动的目标根据相机的运动情况主要 分为两类：一类是相机不动，目标运动：另一类是相机和目标都在运动。这两类情况势 必会引起| ；i 后两幅序列图像的非刚性空间变换。对运动物体的跟踪分为二维运动和三 维运动的跟踪，主要是确定物体的二维或三维平移、旋转参数，并籍此求出物体的运 动轨迹及规律。特征匹配法是的二维运动物体跟踪的离散方法中常用的一种。它是利 用特征匹配的方法找出两幅图像的对应部分及坐标，从而得出运动参数。文献 3 1 就是采用抽取两个特征点即运动物体的形心点的然后作匹配的两点匹配算法来求出 运动物体的运动参数。由于点特征不仅特征明显，而且稳定性好，所以基于特征点匹配 技术估计全局运动矢量的应用也比较多【3 2 】这就需要有计算快捷、精度高、适应性强 的特征点匹配算法。 1 1 4 手写体识别 手写体识别是字符高速、自动输入计算机的重要手段，是智能计算机接口的一个 重要组成部分，在文献检索、办公自动化、邮政系统、银行票据处理等方面有着广阔 的应用前景。目前印刷体汉字识别系统已经走出实验室，加入到办公自动化产品的行 列，得到了广泛应用。手写体识别从字体的形式来分有数字字符识别和汉字及其它字 符识别，从识别的手段来分又可分为联机手写体识别和脱机手写体识别。其中手写体 汉字识别一直是模式识别研究领域中的难点。正是手写体汉字的自身特点给手写体汉 字的识别带来诸多不利的影响。这些特点包括：汉字的样本集类别多而且样本数量 巨大；样本类别间的差距不平均，有些类别日j 的差别很大，而有些类别日j 的差别极 其细微；不同的书写者书写的汉字样本风格于差月别，下笔轻重不同，笔划粗细不 同，样本的大小、旋转方向、倾斜角度不统一，有些字写得偏左、偏右、偏上或偏下 等。而脱机手写体识别由于缺少笔划和笔顺信息。识别难度远远大于联机手写体识别。 现有的脱机手写体识别方法有许多种，包括模糊的方法，网络神经元的方法和基于组 合特征的方法等。其中有一种识别方法先将手写体配准，再进行分类，根据不同的类 别确定字体所代表的含义，两特征点集之日j 的距离可以作为分类的杯准。 3 硕士论文图像特征点匹配算法研究 1 2 课题的目的和意义 特征点匹配是计算机视觉和模式识别领域中的一个基本且重要的问题，特征点匹 配的主要任务是，要找到两点集之间的对应关系和空间映射关系。它适用于解决计算 机视觉应用中的许多问题，如图像配准、物体识别、运动目标的检测与跟踪、手写体 识别、飞行器导航和姿态测定等。因此这种点模式匹配问题在图像匹配和图像配准中 有广泛的应用背景。传统的模板匹配算法精度较高，但它难以处理图像伸缩、旋转、 目标物体被部分遮挡等复杂情况下的位置测量，此外它的效率较低，特别是当搜索空 间的维数增加时其效率将急剧下降。点模式匹配在输入图像伸缩、旋转、平移、目标 物体被部分遮挡、存在非刚性形变等情况下，能快速有效地完成两个图像中特征点集 的匹配，具有很高的鲁棒性。 特征点匹配是模板点集和目标点集之间的匹配，图1 2 1 显示了利用特征点匹配 进行图像匹配的流程： 提取特征点集 蕊砑户 图1 2 1 图像匹配中的特征点匹配 同时，特征点匹配在图像配准中是基于特征的图像配准中必要和重要的一步。图 1 2 2 显示了利用特征点匹配进行图像配准的流程；其中特征点匹配的正确性和速度 直接影响了图像融合后的效果和整个配准的实时性。 图1 2 2 图像配准中的特征点匹配 从特征点匹配在图像匹配中的地位束分析。图像匹配可分成三大类：基于灰度相 关的方法，基于特征的匹配方法和基于解释的特征匹配方法。基于灰度相关的方法是 一种对图像以一定大小的狄度阵列按某种或几种相似性度量顺序进行搜索匹配的办 法。这种匹配一旦进入信息贫乏，或图像有较大的比例尺差异或扭曲的区域，匹配难 免失败，而基于解释的图像匹配技术需要建立在图片自动判读的专家系统上，目前尚 未取得突破性进展，所以基于特征的方法在图像匹配中就显得特别重要。基于特征的 匹配绝大多数都是指基于点、线、和边缘的局部特征匹配。而特征点是所有特征中对 图像噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的适应能力。这使得特 4 硕士论文图像特征点匹配算法研究 征点匹配在实际中的应用越来越广泛。 从实际应用的实时性和准确性要求角度来分析。在早期的图像匹配的算法研究中 主要是对两幅图像空间域上的灰度进行相关运算。常用的方法有：归一化互相关、统 计相关、平均绝对差、平均平方差；基于f f t 频率域的频域相关，包括相位相关和功 率谱相关；不变矩；这些基于图像灰度相似性的匹配方法主要缺陷是计算量太大，因 为使用场合一般都有一定的速度要求，所以这些方法很少被使用。现在已经提出了一 些相关的快速算法，如幅度排序相关算法，f f t 相关算法和分层搜索的序列判断算法 等。但是上述算法还存在如下缺陷：影像( 即图像) 的灰度因获取的时间、季节， 天气等变化及不同传感器拍摄而产生的差异很大，甚至在局部有反转的情况。而且由 于基准图像的更新时间较长还会出现地形地物等内容发生变化，导致影像局部不相 似；计算复杂度高；对目标的旋转，形变以及遮挡比较敏感。所以采用基于图像 灰度相似性的匹配方法就显得不能满足匹配的要求。而点模式匹配方法可以克服利用 灰度信息进行匹配的缺点，因图像的特征点比像素点要少很多，大大减少了匹配的计 算量；同时特征点的匹配度量值对位置的变化比较敏感，可以大大提高匹配的精确程 度。 从硬件发展的水平来分析。利用机器视觉进行各种精密测量，主要有三个环节对 测量精度起到关键性的影响：摄像系统的物面分辨率，摄像系统的标定和误差修正精 度，图像中目标的定位精度。要提高测量精度，可以选用高分辨率的c c d 摄像机， 提高光学成像系统的放大倍数，或采用特殊的光源进行照明。但是这些方法有很大的 局限性，如：高分辨率的c c d 摄像机提高了对图像传输速度、存储容量的要求，过 高的放大倍数减小了视场范围和输出信号的强度。总之，通过提高硬件分辨率的方法 来提高测量精度是不经济的和有限制的。因此，需要用软件处理的方法来解决图像中 目标的高精度定位问题。 因此，从以上几个方面来看对特征点匹配算法的实际应用需求较多，对精度和时 间以及鲁棒性的不断提高从而适应不同的应用需求。同时，特征匹配基于点特征、线 特征、面特征三种方式，但是大多数情况下无论是线特征还是面特征最终也要归结为 点特征，如线特征的拐点、面特征的重心等。所以本课题就是从这方面的需求来出发， 基于现有的特征点匹配算法提出了两种改进的特征点匹配算法。 i 3 本文的主要工作 1 3 i 课题内容 本课题从特征点匹配算法的发展和现有有算法的讨论结合特征点匹配算法的应 5 硕士论文图像特征卓匹配算法研究 用出发，首先讨论特征点匹配在气象图象医学图像等配准、运动目标检测和跟踪、手 写体识别等具体应用的角度分析t i e 在对特征点匹配算法的需求，阐明了点匹配算法 的研究方向是根据应用向更精确，更快，更具有鲁棒性的趋势发展。 基于灰度相关的特征点匹配算法是以往常用的方法，但是算法要求特征点应该位 于灰度变化的区域的中心，例如孤立点、拐角点。且要求以特征点为中心，在其周边 方向上灰度差应当较大。这样，在特征点匹配时比较容易搜寻。如果在一条直线上， 选择了若干特征点，因为直线上特征点的灰度差为零，在另一幅图像的特征点匹配就 会发生混淆，以至于找不到对应得特征点【l 】。同时这类算法对两幅图像灰度信息变化 较大、有部分遮挡、存在图像噪声的情况适应性不强，且通常都只针对刚性变换的匹 配，对于非刚性点和局部扭曲此类算法无法解决匹配问题。 不幸的是在多数实际应用中，都是存在非刚性形变的两幅图像特征点进行匹配， 因此本文以点的位置表示点特征，在非刚性形变的情况下，根据现有的两个特征点匹 配算法进行改进。 首先本文第三章的算法对c h a n g 等的快速点模式匹配算法哪进行改进，即利用 c h a n g 等的算法中寻找匹配点对支持度方法束得到本算法所需的可靠的几何不变量。 主要对c h a n g 等的算法中确定匹配点对( m p d - - m a t c h i n gp a i r sd e t e r m i n a t i o n ) 方法 进行改进，包括给出了两点间数量不变量，然后自上而下的推导出最大匹配点对集和 仿射变换参数。在算法描述中进行理论分析对原算法改进的原因和改进的措施。最后 针对仿真和真实图像的在抗噪能力和出格点的处理能力以及抗形变能力分别进行了 试验与分析，预期结果是在精确性和稳定性都有显著的提高。 其次本文第四章的算法对基于确定性退火的点匹配算法进行改进，给出了适合确 定性退火算法求解的新的目标函数形式。本算法提出采用相似性度量值来约束匹配矩 阵，加快了匹配矩阵收敛的速度从而减少计算星，在退火率较大时也能得到比较好的 解。预期在相同退火率的情况下能够得到比改进前算法好的匹配结果，并且适当提高 退火率时仍然能够得到比较理想的匹配结果， 1 3 2 课题难点 由于国内对特征点匹配算法的研究还不系统，同时国内关于特征点匹配相关的资 料也较少，很多都只是将某种特征点匹配算法在一个具体问题中的应用，而且并没有 对其比较和研究，因此在本课题_ 丌= 展的前期需要收集和阅读大量的外文文献，同时对 特征点匹配算法在实际应用中归纳总结，并且对典型的算法进行分析试验。 在前面已经介绍了点匹配技术所获得很大的进展，但它仍然存在不少困难，首先 在图像获取和特征提取阶段的阂值选取不当等过程中都会产生不同程度的噪声，使得 6 硕士论文图像特征点匹配算往研究 1 5 本文各章内容安排 本文分五章展开，其中第三章和第四章是本文的重点。 第一章首先概述了特征点匹配算法在图像配准、运动目标检测和跟踪、手写体识 别等领域的应用需求，然后说明本文研究的特征点匹配算法的目的和意义，接着将本 文的主要工作在课题内容里做了阐述。最后对本文采用的丌发工具简要介绍。 第二章对点匹配算法的研究现状做简要介绍，首先分析特征点及特征点对解决匹 配问题有利的一些特性，然后对现有的点匹配算法回顾分析与分类。最后给出本文中 要用到的相关知识，以便于的理解本文后面给出的两个算法。 第三章提出了基于寻找不变量的特征点匹配算法。这是对快速点匹配算法的改 进，首先对快速点模式匹配算法进行分析并说明对快速算法的改进方案，然后对改进 后算法进行详细的描述，给出了最大匹配集求解算法。通过仿真和真实图像的实验比 较原快速匹配算法，来说明本章改进后算法的在抗形变、抗噪声和抗出格点三方面性 能的提高。 第四章提出基于确定性退火的非刚性点匹配的算法。首先在给出新的点匹配目标 函数前，说明点匹配矩阵表达形式和满足的约束。紧接着本算法给出了适合确定性退 火求解的新的目标函数一股形式，并分别给出在仿射变换和薄板样条两种映射条件下 的目标函数。然后详细介绍相似性度量值及其计算，还有匹配矩阵的求解。最后推出 基于确定性退火的特征点匹配算法的整体框架，并进行实验比较与分析。 第五章，总结全文并指出本文算法的可行性以及需要进一步研究和解决的问题。 顿卜论文 图像特征点匹配算法研究 定的闽值。但该算法当有丢失点特征，或出现虚假点特征的等不利情况时，容易导致 错误匹配，从而得到错误的空间变换参数。j e z c h i n g 和a n i l 也采用了松弛算法的匹 配策略i ，并引入了匹配矩阵的概念，他们采用了双向匹配的思想。双向匹配的概 念是两个图像中的特征点均可以在另一个图像中选择匹配点。这种双向匹配的改进更 能够产生更多一致的匹配点对。但是他们的这个算法必须保证两个点集中能够存在一 半以上的有效点。z z h a n g 和r d e r i c h e 给出了一个较好的基于互相关函数得点特征 匹配算法i 。该算法首先利用互相关获得点集之间得初始匹配；接着利用对极几何 约束改进精匹配。以上算法采用了不同的相关准则来度量特征点的相似度，通过初始 匹配和进一步加上一定约束条件来筛选匹配点对的模式来得到精确的特征点匹配点 对。 以上一些特征点匹配算法利用特征点附近某一个窗口内象素的灰度信息，根据不 同的获度统计特性的匹配准则( 最常用的交叉相关准则) 来判断特征点的相关性。但 是图像存在的遮挡和图像灰度变化较大的情况往往将影响算法的效果。还有一些算法 是利用特征点的位置信息及两个点集之间的不变量来确定特征点的对应关系。l i h u a z h a n g 的仿射变换下基于遗传算法搜索策略的特征点匹配算法1 ”】，通过构造点集的特 征椭圆和遗传算法( g a ) 的并行机制来减少遗传算法的解空间，因此这种方法计算效 率较高匹配结果较理想，但是如果存在一个3 一元组合错误的封闭于一个特征椭圆内 这将在另一个点集中找不到对应的3 一元组合。c h a n g 等人的快速点模式匹配算法p 1 用 聚类的方法确定匹配两个点集的旋转量0 ，然后根据旋转量0 找出所有的匹配点对， 最后由最4 , - 乘法精确地确定出匹配参数仿射变换参数。这个算法在效率上有出色的 表现，但是由于算法中引入五个阂值使得算法的精确度和稳定性较差。s t e v e ng o l d 等人提出一种点匹配的新算法【9 】，采用确定性退火算法的搜索策略和软分配过程，该 算法对于噪声和高比例的丢失点及虚假点体现了较强的鲁棒性，但是该算法要求初始 温度足够高退火率足够低才能保证找到全局最优，这使得匹配时间消耗较大。t o r u w a k a h a r a 提出了一种类似于迭代匹配最近点( i c p ) 方法的算法i ”】，它的思想是在迭 代每一步根据最近的一对点确定对应关系，再由对应关系找到空日j 变换。它同时提出 局部仿射变换( l o c a la f f i n et a n s f o r m a t i o n ) 的概念，使整体的空日j 映射具有更好 的自由度。国内对于解决特征点匹配问题的算法不是很多，但近几年也引起了许多学 者的关注，p a nj u n j u n 和z h a n gy a n n i n g 提出了一种基于点位置相似性的点匹配 算法| 8 1 ，它采用了最小化欧几垦德距离总和的规则来匹配对应得点，使错误匹配减 少。该方法仅基于特征点的位霄特征以较少的时间消耗达到了最多的正确匹配点对。 x i a n g y uy u 等人的点匹配算法l l 卵中引入了点集的凸核顶配对的思想。通过凸核顶配 对来减少特征点的数目，变换参数和点集间的匹配在迭代的每一步都被更新，然后由 点之间的顶和距离共同判断是否两个点是匹配的。变换参数的求解是当所有的点部被 颟十论文图像特征点匹配算j 杰研究 变换后仍然是直线，则这种变换成为刚体变换如图2 2 1 1 。刚体变换可分解为平移、 旋转和反转( 镜像) 。在二维空间中，点( x ，y ) 经刚体变换到点( x ，y ) 的变 换公式为： ；- = 。c 。o n s 妒9 千_ + d , i - 缈1 。r y q + 乏 其中伊为旋角，瞳 为平移向量。 原始图像 变换后图像 图2 ，2 1 1 刚体变换 仿射变换 经过变换后第一幅图像上的直线映射到第二幅图像仍为直线，并且保持平行关 系，这样的变换称为仿射变换如图2 2 1 2 。仿射变换可以分解为线性( 矩阵) 变换和 平移变换。在2 d 空间中，变换公式为： ；t = 。口a 甜l lo 口篮q 。y q + 仿射变换重要性质是“保直线”，仿射变换包括刚体变换。 原始图像 变换后图像 幽2 2 i 2 仿射变换 投影变换 经过变换后第一幅图像上的直线映射到第二幅图像上仍为直线，但平行关系基本 不保持，这样的变换称为投影变换。投影变换具有更一般的形式，它适用于景物平面 1 3 硕 论文 图像特符点匹配算j 杰研究 2 2 2 最小二乘法求仿射变换参数 这一节将介绍最小二乘法估计两个特征点集的仿射变换参数，前提是已知两点集 的一对一的匹配关系。同时这一节的知识将在第三章的算法中用到。 如果在两点集p 和q 中有k 对匹配点对 ( p ，q 。) fi = l ，k 且k 2 2 。我们需要 计算的仿射变换参数g ( 驭，t y ，s ，护) 就是使一个点集中的点经过此变换后的坐标 与另一个点集中对应的点的坐标欧式距离的平方和s ( t x ，t y , s ，口) 最小的变换。令e 为 p ，的坐标与q 。变换后的坐标g ( q ) 的差。 = 旺 - y q , l l - - y q 斟 = ( ：囊。斟 k p s 证盯，巳= 囊 e = c 叽 c 口2 ： c 口r 一 至 。：2 ， ctp 其中p r = ( p iz ) ，c r = ( c ：c 妇r c ：) 。 所以可以将s ( t x ，吼s ，p ) 表达为： t s ( t ) = z e r e , = ( i ) j 。l 弓 岛 ： 气 5 、 以 n x y ，。l 一 、， k ，。l 、 口口 n s幽 一 s口口口 c s s j ，l + 、，j ，p p 一 一 厶厶 厶 ，。l = 、j q 色；气 硕士论文凰像特征苣匹配算法研究 2 2 3 搜索策略 由于形变、出格点和噪声等多个因素的影响，使得特征点匹配过程本质上是一个 多参数的最优化问题，在给定目标函数的条件下，可能会出现多个局部极值，这就使 得求取一般单极值的算法无法完成此工作。而必需通过将目标函数嵌入到各种搜索策 略中求出匹配目标函数的全局极值，从而得到最优的匹配。所常用的搜索策略有：模 拟退火法、确定性退火法还有遗传算法等。本文的第四章算法用到确定性退火法，这 里将对点匹配算法中常用的搜索策略做简单介绍。 模拟退火法 模拟退火算法是一种能使优化问题获得全局最优解得方法。该算法是由 m e t r o p o l i s 等人在1 9 5 3 年提出的，它代表了一类鲁棒的优化方法【”j 。模拟退火算法 对表示复杂系统好坏的目标函数( 代价函数) 进行最小值搜索。它适用于n p 完全的优 化问题；它并不保证找到全局最优解，但通常可以得到近似最优解。 c e r n y l 2 8 】经常用下面的例子来说明模拟退火的原理。想象一个盛方糖的糖罐，通 常会有一些方糖与糖罐的形状不吻合，使得无法合上盖子。根据日常经验，每个人都 知道将糖罐摇一摇可以使方糖自动移到更合适的位置，于是就可以合上盖子了。换句 话说，将罐子中所装的方糖块数视为评价函数，摇动罐子可以得到近似最小解( 对于 方糖所占的空间来说) 。摇动罐子的程度时这个优化过程的一个参数，对应与下面要 说的加热和冷却过程。 模拟退火综合了两个基本的优化原理：分而治之和迭代改进。这样的结合使用可 以避免停止在局部最优上。模拟退火算法的思想，是基于固体物质的退火处理过程。 在对固体物质进行退火处理时，通常先将它高温加热，使其中的颗粒可以自由运动， 然后随着温度的逐渐下降，颗粒也逐渐形成了低能太的晶格。如果在凝结点附近的温 度下降速率( 退火率) 足够慢，则固体物质一定会形成最低能量的基态。 对于优化问题也存在着与固体物质退火处理相似的过程。在优化问题的解空间中 的每个点都代表了一个解，不同的解对应着不同的函数值，优化过程就是在解的空间 中寻找目标函数最小的解。在模拟退火算法中，如果系统的变量变化后，能量函数有 更低的值，那么就接收这种有益的变化；如果在系统的变量变化后，能量函数没有更 低的值，那么就按预先确定的概率分布接收这种变化。这就是说系统不但能接收能量 函数减小( 性能改善) 的变化，而且还以某种概率分布接收能量函数增大( 性能变差) 的变化。这实际上给系统得变量引入一些“噪声”。使系统更有可能跳出能量函数的 局部最优区域面向全局最优区域搜索。 传统的启发式搜索算法，如快速下降法，都是向能量函数减小的方向搜索。这种 算法往往会导致搜索过程停留在系统得局部最优而不是全局最优的区域，因而是一种 1 7 硕士论文图像特符点匹配算法研究 “贪心”算法，该算法的搜索过程如图2 2 2 1 所示，模拟退火算法搜索过程如图2 2 2 2 所示。 e - 、 o v 文 、。 o v 文 图2 2 3 1 “贪心”算法搜索示意图 图2 2 3 2 模拟退火算法搜索示意图 结合以上基本思想，模拟退火算法的框架为： 1 令x 为优化参数的向量，计算目标还书j ( x ) 的值，t = t 。 2 将第3 步和第4 步重复n ( t ) 次： 3 对参数向量x 做轻微扰动，得到新向量x 一，计算新的优化函数值j ( x 。) a 4 生成一个随机数r e ( o ，1 ) ，满足区n ( o ，1 ) 上的平均分布。若： ， t m ，则回到第2 步，否则算法结束。 6 这时参数向量x 表示优化问题的解。 注意，事先并不知道需要多少次迭代步骤，怎样的参数扰动( 状态改变) ，选择 什么温度t 、采用多快的冷却速度才能得到最好的结果，虽然有一些一般性原则可供 参考，但对于特定的问题有特定的合适参数。目前只知道对任一温度来说，退火过程 都应该足够长的时间来达到稳定状态。如糖罐的例子：开始时摇动会比较剧烈，然后 逐渐变缓已达到最好结果。 退火率和每个温度达到热平衡所需的迭代步数n 称为退火进度。较大的迭代步数 n 和较小的温度t 变化步长可以产生的最终优化函数值也更低( 解更接近于全局最 小) ，但需要较长的计算时日j 。较小的迭代步数n 和较大的温度t 的变化步长可以更 快结束，但结果也可能离全局最小比较远。因此需要仔细设置t 和n 的值，使得在可 以接受的时日】内得到比较接近全局最小的解。然而目前还没有设计出退火进度的实用 方法。 确定性退火法 确定性退火技术是由美国加州理工学院的k r o s e 博士于1 9 9 0 年首先提出的陋1 。 硕士论文 图像特征卢匹配算法研究 它类似于模拟退火算法，同样采用了物理学中通过缓慢降温可以将材料的能态降到最 低的理想热平很状态。不同的是这里的算法在每一个温度下，对最为变量的优化参数 施加的是确定性，而不是随机的值。它通过控制作为变量的优化参数的熵，使熵值由 最大值变到最小，在熵值变化的每一步对目标函数进行优化而逐渐求解出一个全局的 比较好的解。这样就把原来的可能存在多个极值点的非线性问题凸化。 与模拟退火法相比，它只需要较少的迭代次数便可在每一个温度下达到热平衡状 态。它在性能和计算复杂度两者之间作了一个很好的折衷。在实践中，确定性退火和 模拟退火给出相似的解。对于大规模的现实问题，确定性退火要快很多，有时可以快 2 - - 3 个数量级m 1 。因此确定性退火算法在特征点匹配尤其是对于非刚性点匹配的复杂 问题有较多的应用，如文献【5 、7 、8 、9 、4 0 】。 将确定性退火法应用于特征点匹配具体实现方法为：定义点对应关系的匹配矩阵 h ，然后在目标函数中加入一项表示h 的熵的阻尼项：t 气0 0 9 k 1 ) 。通过调整 退火温度t 实现对h 的熵的控制，迭代的求解空间映射和灯应关系，最终实现点匹 配。 确定性退火技术的求解框架： 1 取足够大的t 。，令k - - - o ，求解目标函数m i n f ( x ，t k ) ，设最优解为：x 。( tk ) 。 2 t k + i - - a tk ，a 为退火率且o a l ，以x 。( tk ) 为初始解，求解m i n f ( x ，t k + 1 ) ； 设最优解为x 。( t 。) 。 3 判断收敛性准则是否满足，若满足，则停，x 。( tk + 1 ) 为最优解；否则转步 骤4 。 4 k = k + 1 ，转步骤2 。 遗传算法 遗传算法是一种模拟自然选择和遗传得随机搜索算法。它由密执安大学j o h n h o l l a n d 提出，最初用于研究自然系统得适应过程和设计具有自适应性能的软件。近 来，遗传算法作为问题求解和最优化的有效工具，引起越来越多的注意，在特征点匹 配问题也有应用，如文献 1 5 、1 7 。 遗传算法是一种迭代算法。它在每一次迭代时都拥有一组解答。这组解答最初是 随机生成的。在每次迭代时又有一组新的解答由模拟进化和继承的遗传操作生成。每 个解答都由一个目标函数给予评价，而且这一过程不断重复，直至达到某种形式上的 收敛。新的组解答不但可以有选择地保留一些目标函数值高的旧的解答，而且可以 包括一些经由其它解答结合而得的新的解答。 遗传算法的术语借鉴与自然遗传学。一个解称为一个符号串或染色体。染色体由 决定其特性的基因构成，而基因又可以有称为等位基因的不同取值。目标函数称为适 硕士论文酗像特征皂匹配算法研究 3 基于寻找不变量的特征点匹配