（机械电子工程专业论文）基于点模式匹配的图像匹配方法的研究.pdf

华中科技大学硕士学位论文 摘要 视觉自动定位技术是集成电路后封装设备中的一项重要单元技术。视觉自动定位 系统由光学照明系统、光学成像系统、c c d 滠像器件、圈像处理软件等部分组成，其 中高精度的阁像处理算法对视觉自动定位系统的精度超着决定性的作用。本文针对视 觉定位中两戮粒窝像匹配方法、以及与之籀盛瓣蚕像颈箍理方法、箍高遥繇精度豹方 法进行了深入细致的研究。 签豫銎瓣是强豫娃理黪个綦疆惩莲，在工、韭捡溺、交逮管理、遥感测量等领域 中部有广泛的应用。简单地说，它就是找到两幅不同图像之间的空间位置关系。本文 在对臻有夔漤豫疆熬方法懿深入广泛兹研究的基磁主，磅突了裂题点模式殛配进行嬲 像匹配的方法，并在此基础上利用能量最小化方法避一步摁高图像旺配的精度。 零文豹主要蠹嚣包括：( 1 ) 对现有圈像匹配方浚鲍分类鞠概述、以及翁要的分攒； ( 2 ) 对图像预处理方法的研究。篡中，详细地讨论了线性滤波器、中值滤波器的特点 和羯限性，详细地磺究了s u s a n 滤波器的优点，此外，对图像分割方法作了简要的 介绍；( 3 ) 对提取图像中特征点的方法的研究。简疆地介绍了常见的边缘键取方法， 研究了基于小波的强边缘的提取方法和s u s a n 角点提取方法；( 4 ) 对点模式匹配方 法的研究。研究了点模式鼹配的定义以及隧配的遥程；( 5 ) 对进一步援商胬像匹配精 度的方法的研究。研究了豫像素边缘提取方法、能艟最小化方法和光流方法。( 6 ) 对 图像匹配软件的研究。舟鲻了软件的开发平台、禳浃结梅、使嗣方法等。 在本文的最后，对全文进行了总结，并对将来的图像匹酉己方法提出了自己的展黧。 关键词：图像匹聪图像预处理特，征点提取 点模式匹配亚像索边缘提取 能量最小化光流 华中科技大学硕士学位论文 a b s t r a c t v i s i o na n t o m a t i ca l i g n m e n tt e c h n i q u ei so n eo ft h em o s ti m p o r t a n tt e c h n i q u e si ni e e n c a p s u l a t i o n t h ev i s i o na u t o m a t i ca l i g n m e n ts y s t e mc o m p r i s e so p t i c a ll i g h t i n gs y s t e m ， o p t i c a li m a g i n gs y s t e m ，c c dd e v i c e ，a n di m a g ep r o c e s s i n gs o f t w a r ee t c ，i nw h i c ht h eh i g h p r e c i s i o ni m a g ep r o c e s s i n ga l g o r i t h m sf i r et h ed e t e r m i n a n tp a r t 勤rt h ef i n a la c c u r a c yo f a l i g n m e n t 。t h i sp a p e rc o n t a i n st h ei n t e n s i v er e s e a r c ho nt h es u b j e c to fi m a g em a t c h i n g m e t h o d s ，r e l a t e di m a g ep r e p r o c e s s i n gm e t h o d s ，a n dm e t h o d st oe n h a n c et h ea c c u r a c yo f i m a g em a t c h i n g ， i m a g em a t c h i n gi s af u n d a m e n t a lp r o b l e mi n i m a g ep r o c e s s i n g ，a n di th a st o t s o f a p p l i c a t i o n s ，s u c h a s i n d u s t r yi n s p e c t i o n ，t r a f f i cm a n a g e m e n t ，a n dr e m o t es e n s es u r v e y ， s i m p l yp u t ：i t sg o a li st of i n do u tt h es p a t i a lr e l a t i o n s h i pb e t w e e nt w od i f f e r e n ti m a g e s ，t h i s p a p e r f i r s ti n t e n s i v e l ys t u d i e st h ek n o w nm e t h o d so f i m a g em a t c h i n g 。t h e ns t u d i e s t h ep o i n t p a t t e r nm a t c h i n gt om a t c hi m a g e s 。f i n a l l y , t h ep a p e rp r e s e n t ss e v e r a lw a y st oe n h a n c et h e a c c u r a c yo fi m a g em a t c h i n g t h em a i nc o n t e n to ft h ep a p e rc o m p r i s e ：( 1 ) c l a s s i f i c a t i o n ，s u m m a r y , a n dc o n c i s e a n a l y s i so fk n o w ni m a g em a t c h i n gm e t h o d s ( 2 ) s t u d yo ni m a g ep r e p r o c e s s i n gm e t h o d s t h i ss e c t i o nd i s c u s s e si nd e t a i lt h ea d v a n t a g e sa n dd e f e c to fl i n e a rf i l t e ra n dm e d i a nf i t t e r ， a n d p r e s e n t st h ed e t a i lo f s u s a nf i l t e nm o r e o v e r , t h i ss e c t i o na l s o b r i e f l yi n t r o d u c e si m a g e s e g m e n t a t i o n ( 3 ) s t u d yo nm e t h o d s 韬e x t r a c tf e a t u r ep o i n t sf r o mi m a g e s ，t h i ss e c t i o n b r i e f l yi n t r o d u c e ss i m p l ye d g ed e t e c t i n gm e t h o d s ，s t u d i e st h ed e t a i lo f w a v e l e t b a s e ds t r o n g e d g ed e t e c t i n gm e t h o d ，a n ds t u d i e ss u s a n c o r n e rp o i n te x t r a c t i n gm e t h o d 。( s t u d yo n p o i n tp a t t e r nm a t c h i n g ；t h i ss e c t i o ns t u d i e st h ed e t a i l o fd e f i n i t i o no ft h ep o i n tp a t t e r n m a t c h i n gp r o b l e ma n di t sp r o c e s s ( 5 ) s t u d yo nm e t h o d s t oe n h a n c et h ea c c u r a c yo fi m a g e m a t c h i n g t h i ss e c t i o ns t u d i e ss u b p i x e le d g ed e t e c t i n gm e t h o d ，e n e r g y m i n i m i z a t i o nm e t h o d ， a n do p t i c a lf l o wm e t h o d ( 国s t u d yo ni m a g em a t c h i n gs o f t w a r e t h i ss e c t i o ni n c l u d e st h e d e v e l o pp l a t f o r m ，s t m c t u r e ，a n d u s e rg u i d e a tt h ee n d ，as u m m a r yo ft h ep a p e ra n dt h ev i e wo ff u t u r ei m a g em a t c h i n gm e t h o d so r e g i v e n ， k e y w o r d s ：i m a g em a t c h i n g i m a g ep r e p r o c e s s i n g f e a t u r ep o i n te x t r a c t i o n p o i n t p a t t e mm a t c h i n gs u b p i x e le d g e e x t r a c t i o n e n e r g y m i n i m i 。z a t i + o n o p t i c a lf l o w 独创性声明 本人声骥掰呈交的学盘论文是我个a 在导师指导下进牙豹研究二作及取褥 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 令久袋集镩已经发表藏撰写遥稳研究残栗。对本文的研究馓出贡献静个入孝蠡集 体，均己在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承 担。 学位论文作者整名 对 秘赣：五孵了砑曩 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向函家有关部门或枧构送交论文瀚复印俘和电子蔽，允许论文被查阕和 借闻。本人授权华中科技大学砸以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不傈密 ( 请在以上方框内打“”) 学位论文作者签名 同弱：石辑f 胃f 目 琦 指导教薅签名：迢蝴 圜期：衅f 胃 归 华中科技大学硕士学位论文 ；= = = = = = = = = = = = = = = = = 一= = 1 1 课题来源 1 绪论 国家高技术研究发展计划( 8 6 3 计划) “m e m s 动态特性频闪干涉视觉三维测量技术 及系统”( 课题编号2 0 0 2 a a 4 0 4 1 0 0 ) 国家重点基础研究发展计划( 9 7 3 计划) “极限制造中的混合约束数字建模与产品 缺陷诊断机理”( 课题编号：2 0 0 3 c b 7 1 6 2 0 7 ) 1 2 课题背景 微电子制造业是集国家利益和最新科技于一体的战略性产业，是当今世界竞争最 激烈、发展最迅速的领域，其产业规模和技术水平已成为衡量个国家综合国力的重 要标志之。微电子制造装备是“十五”期间8 6 3 计划“先进制造与自动化技术领域” 中的重大专项与重点课题。 后封装技术是微电子制造的关键技术之一，集成电路的制造进行到后封装阶段， 9 0 的成本已经凝聚在芯片上，所以提高此环节的成品率对于提高产量和降低成本有 着举足轻重的影吼因此对此技术的研究也成为了目前微电子制造装备中研究的热点 之。目前广泛使用的后封装技术的有两大类：引线键合( w i r eb o n d i n g ) 和倒装芯片 ( f l i pc h i p ) 。引线键合以单个连接成本最低、制作工艺灵活、适应性强等特点占领了 微电子封装约9 5 的市场。目前，键合机能达到的定位精度约为2 5 微米，相应的空 叫运动精度和生产率分别为4 0 微米和1 5 线秒。随着i c 技术的不断发展，芯片的集 成度越来越高，先进的超大规模集成电路( v l s i ) 和甚大规模集成电路( u l s i ) 对不 断增加输k 输出( i o ) 连接的能力和可靠性提出更严格的要求，芯片接线的删距不 断减小，封装的精密度、速度和可靠性不断提高，例如现在广泛应用于光电器件组装、 i o e n s 、m c m 、m e m s 、三维封装等领域的高精度自动贴片机，它的定位精度已经达到了 l 微米的水平。 机械运动系统的快速精密定位是一项综合技术，其基础是机器视觉系统。机器视 觉系统提供运动目标的位置，由光学照明系统、光学成像系统、c c d 摄像器件、图像 处理软件等部分组成，其中高精度的图像处理算法对机器视觉系统的精度起着决定性 的作用。 华中科技大学硕士学位论文 在芯片上刻有经特殊设计的图形( f i d u c i a l ) ，图形中的某一点将作为参考点( a n c h o r p o i n t ) ，芯片上其它点的绝对坐标都根据已知的相对于参考点哟相对坐标和参考点的绝 对坐标确定，从而达到定位韵目的。爱达到离的测量精度，可以选用满分辨率的c c d 摄像机，提嵩光学成像系统的放大倍数，或采用特殊的光源进行照明。但是这些方法 有禳大的局限性，翔：高分辩率的c c d 摄豫机提高了对图像传输速艘、存储容量韵要 求，过高的放大倍数减小了视炀范围和输出信号的强度。总之，通过提高硬件分辨率 麓方法来提离测量稽寝是不经济静帮有限制豹。因诧，需要瘸软件撼理的方法采解决 图像中目标的高精度定位问题，这是精确定位和运动控制的基础。 1 3 课题的目的和意义 撩于上述考虑，本项目将开展基于实时机器视觉信息的精密定位研究。开展本项 鼙磅究，凑鸯躜子发鼹弱丰嘉褫觉定位懿基磊娄理论帮方法，鸯国内发震县窍鑫主知识 版权的高性能i c 封装设备提供一定的基础理论和单元技术。闷时，由于视觉定位是自 动纯设备的共牲技7 | 乏，除l c 封装夕 ，亦可用于壤寒枫床、枧器人、微机趣系统( m e m s ， m i c r o 。e l e c t r o n i c ，m e c h a n i c a l s y s t e m ) 、微操作f m i c r o m a n i p u l a t i o n ) 和微装配 f m i c r o ，a s s e m b l y ) 等其它毫速离糖设备中，在精密机槭、航天、汽车导航、军纂、医疗 等很多领域都有非常广闶的应用前景。 瞬翦，由于只有少数几家大公司越够生产此类设备，因丽价格极其昂贵，例如离 精度裔动砧片机的价格超过1 0 0 万美元，而高精度手动贴片枫的价格媳高达3 5 万美元。 随着我国i t 行业、特别是光呶子产业的迅速发展，对集成电路封装设备的需求也逐渐 增大，徨强前出于其精贵的价格，国内只有大公司和太弱科磷院所霄能力购买。这极 大地限制了中小企业对集成电路封装设备的使用。而刹用本课题的研究成果，将为集 或电路封装浚备静制造提供关键静挚元技术，往进集成电路潮造装备承平的撬裔，并 极大地降低产品的组装和封装成本，解决光电器件、m c m 、m e m s 等高科技产晶的产业 纯瓶矮滔题。 l 。4 国褒铃发震瑗凝与戆势 传统款税凳定位接术主要果鼹基予蝗一诧获度掇关( n g c ，n o r m a l i z e dg r a y s c a l e 。o r r e i a t i o n ) 理论的模板匹配技术。此方法鲁棒性好、可靠性离，对圈像噪声敏感程度 低，避过对相关表蘑遴行播馕运算还可畈获褥亚象素的定位糖度，联以广泛应用于工 业视觉检测、机器视觉定位等领域中”。在归一化灰液相关方法中，视觉系统获得疑 华中科技大学硕士学位论文 寿实甄摸式爨图爨，与存麓在诗冀槐凌存孛巽有曩襻模式静参考銎像遥牙撩禧跑较， 从而计算出使两幅图像匹配的x y 位置，并找到实际模式的位置。利用灰殿信息甄配 方法豹主要缺鏊是跨篓量太大，嚣为夔矮场合一般郝有一是熬速度要求，赝醴这黧方 法很少被使用；现在已经提出了一些相关的快速算法，如幅度排序相关算法，f f t 相 关冀法翻分罄搜索的序列判疑算法等。 相关匹配存在的另一个问题是匹配后在匹配点产生的顶峰较宽，影响殴配特征的 精确定位，绘后继她理带来不确定豳素 2 j 】。同时它限制了视觉系统在角度、照度、对 比艘变化等模式下的精确定位能力。如果存在光照的非线性变化、物体表面的反射、 标记点的偏移等复杂情况，归一化坎度相关法有可能完全失败。c h e n 等人用付氏变换 的相位来代替幅值进行相位匹配，隧减小顶峰宽度，得到针状峰值。健这种方式对嗓声 非常敏感，适用于无噪声的情况h j 。 基于阐像特征静匹配方法可隧有效克服上文提到的裙关法存在的缺点。由于圈像 的特征点比像素点要少很多，大大减少了匹配过程的计算数；同时，特征点的匹配度 量馕对位霉瓣交佬吃较敏感，可敬大大提怒匹甏麓精确程度；两嚣，特疑点静提取过 程可以减少噪声的影响，对灰度变化，图像形变以及遮挡镣都有较好的适成能力。在 p c b 检测中，萋予穰型瓣方法采爰符号接述p c b 模式，将鬻像霹壤润题转纯为鹜琶醚 问题，其中图匹配取决于图像结构、拓扑和几何特性，所以这种方法的精度依赖予特 短掇敬戆精霾窝簦糁蛙疆l 。警疆势萋名工业辍嚣稷蹩公司，毙裁嚣寸e u r e s y s 公嚣嚣 发的基于点特征的技术的图像分析软件e a s y f i n d ，可以实现线性位移精确到1 3 0 征 象綮，囊转翅度糖确到 4 发，毙剿精确到i 2 。美鞭c o g n e x 提出凡鼹模式莲配技术， 称为p a t m a x ( 包括5 个新的算法：特征提取、训练、仿射搜索、精定位、检测) ，c o g n e x 宣称其算法霹以实现1 4 0 煦象素定位精度，劳将其俸为下一代图像对准工媳，盛用于 工业检测中1 6 】。但魑几何模式匹配的基础鼹图像的几何特征提取，因而此法的定位精 度依赖于图像几何特征的边缘检测精度，在特征提取过程中此方法比n g c 法对随机噪 声爨敏感。 1 5 论文的研究内容 本论文潞第二誊对瑶育鹄一些鬣像匿配方法傲了箍要瓣奔绍，毪摇：赔讫获爱 相关方法、s s d a 方法、亚像素精度的模板妪配方法、f p t 相关匹配方法、艇于傅立叶 变羧兹褶位遥配、维灰度浚影匹聚方法、鞫投影黩配方法、基予轮瘃豹疆嚣方法簿。 第三章研究了图像预处理的方法。其中的图像滤波方法包括：移动平均滤波器、 离戆滤波嚣、中蘧滤波器、匿分比滤波器、s u s a n 滤波器；溷豫分錾部分麓要分绥了 华中科技大学硕士学位论文 图像分割的原理和叠代分割算法。 第四章研究了几种图像特征点的提取方法，包括常见的边缘提取方法：梯度操作 数、拉普拉斯操作数、l o g 操作数、c a n n y 操作数、基于小波的边缘提取方法、s u s a n 角点提取方法，并对这些方法提取得到的特征点对图像匹配的影响做了简要的分析。 第五章研究了利用点模式匹配进行图像匹配的方法，包括点模式匹配的定义、匹 配的过程、试验的结果等。研究了在点模式匹配的基础上进一步提高匹配精度的方法， 包括亚像素边缘检测方法、能量最小化方法、基于光流的方法。 第六章介绍了图像匹配的软件系统，包括开发平台、模块结构、操作界面和操作 方法等。 第七章对全文进行了总结并对将来的图像匹配算法作出了展望。 华中科技大学硕士学位论文 2 1 综述 2 图像匹配方法 图像匹配是图像处理的一个基础问题。简单地说，图像匹配就是找到两幅不同图 像之阃的空间位置关系。对同一物体或场景使用不同的传感器、在不同的光照条件下、 以不同的摄像位置和角度获得的图像一般都会不同，其差异可能表现为：不同的分辨 率、不同的灰度属性、不同的位置( 平移和旋转) 、不同的大小( 缩小和放大) 、以及 其他的非线性变化( 部分物体被遮挡) 等。图像匹配在许多场合都有着重要的应用， 文献【7 把这些应用粗略地分为了四类： 1 ) 由同一场景、不同传感方式获得的图像的配准。 典型应用：多传感器的信息融合。 方法特点：通常需要利用传感器模型，需要对灰度进行预对准，利用物体形状 和定位标志可以简化问题。 应用：医学图像处理，c t 、m r i 、p e t 、s p e c t 图像结构信息融合。遥感图像 领域中的多电磁波段图像信息融合。 2 ) 在图像中寻找参考模板的最佳匹配 典型应用：在图像中识别和定位模板图像，例如：地图、目标物体等。 方法特点：基于模式，预先选定特征，已知物体属性，高级特征匹配。 应用：遥感数据处理，定位和识别己定义或已知特征的场景，如：飞机场、 高速路、车站等。模式识剐，字符识别，标志确认，波形分析等。 3 ) 对不同观察点获得的图像进行配准 典型应用：深度或形状重建。 方法特点：变形多位透视变换；常应用视觉几何和表面属性等假设条件；典型 的方案是特征相关：必须考虑遮挡问题。 应用：计算机视觉，从视觉差异中构建三维深度和形状信息，运动跟踪， 序列图像分析。 4 ) 对同一场景上不同时间或不同条件下获得的图像的匹配 典型应用：检测或监视变化或增长。 方法特点：需要容忍图像中部分内容的差异和形变对配准造成的影响；有时需 要建立传感器噪声喝视点变换的模型。 华中科技大学硕士学位论文 应 用：医学图像处理，数字剪影血管造影( d s a ) ，注射造影剂前后的图像 配准。肿瘤检测，白内障检测。遥感数据处理，自然资源监控，市 区增长检测。 出以的上分类可以看出，图像匹配的方法有很多，且每种方法通常都是针对某一 具体的应用而设计。因此很难对不同应用背景下的匹配方法进行比较，但通常会从精 度、效率、通用性这三个方面来衡量一个图像匹配算法的优劣。其中，定位精度往往 对后续图像处理算法有重要的影响：效率则与算法的实际意义、应用的成本等经济因 素有着直接的关系；此外，匹配算法还应有一定的通用性以适应不同的应用背景。 近年来，出现了许多的图像匹配算法，文献 7 根据特征空间、相似性测度、搜索 空间及搜索策略对这些方法进行了分类： 1 ) 特征空间 决定匹配算法使用的图像特征是图像匹配的第一步。特征可能是图像本身或变换 之后的图像，例如：像素的灰度和图像的傅立叶变换，也可能是边缘、轮廓、表面， 可能是其他一些显著的特征：角点、线段的交点、具有较大曲率的点，还可能是图像 的统计特征：矩不变量、重心，以及上层的结构和句法描述等。图像特征的选择对以 下几个问题有着重要影响：图像中的哪些属性将被匹配，例如：匹配的是结构还是纹 理；匹配算法的计算量：以及传感器的选择，传感器的噪声应该对将要匹配的特征不 敏感。 对输入的图像通常要进行预处理以便提取出图像中物体的结构，这包括：减小和 滤除图像中的噪声，增强图像中待匹配的特征等。特征空间是对图像匹配过程中所用 到的数据的表示。特征决定了被匹配的属性。与特征相应的相似性测度则决定了两幅 图像中对应特征的匹配程度。 2 ) 相似性测度 相似性测度和特征空间紧密相关，它衡量了特征之间的相似程度。典型的相似性 测度包括：互相关豳数、s a d ( s u mo fa b s o l u t ed i f f e r e n c e ) 、傅立叶变换不变量等。 利用结构和句法描述的特征所用到的相似性测度则与特征自身的属性密切相关。 3 ) 搜索空间及搜索策略 搜索空间与两幅图像之间的相对位置变化有紧密关系，例如：如果图像的位置仅 仅只存在平移的变化，那么一个二维的搜索空间就足够了。如果图像之间的变化是更 一般的仿射变换，则搜索空间的维度就会升高。图像的几何变形可以分为三类：全局 的、局部的和位移场形式的。全局变换通常基于矩阵代数理论，用一个参数矩阵来描 述整个图像的变换。典型的全局几何变换包括以下的一种或几种：平移、旋转、各向 同性或异性的缩放等。局部变换有时候又称为弹性映射，它允许图像中不同的位置具 6 华中科技大学硕士学位论文 有不同的变换参数模型，变换参数往往只定义在特定的关键点上，而在区域到区域之 间进行插值。位移场又称光流场，它使用函数优化的方法，为图像中每一点计算出一 个独立的位移向量。 搜索策略的选择对匹配的计算量有着重要影响。常用的搜索策略有：聚类法，松 弛匹配，动态编程、牛顿法、最速下降法、共轭梯度法等。 2 2 基于像素灰度的匹配方法 2 2 1 归一化灰度级相关方法 传统的匹配技术主要采用归一化灰度级相关方法( n g c ) 确定模板在图像中的位置 口引。在计算过程中，模板依次被移动到图像中所有可能的位置，模板中像素的狄度级 乘以图像中被模板覆盖的对应像素的灰度级，得到的总和( n c 值) 存储在二维数组中， 由这个数组可以得到模板在图像中的位置。两个向量对应的元素相乘定义了向量间的 点积。在n g c 中，像素的灰度级相乘同样也是由图像和模板中相应像素的灰度级组成 的向量之间的点积，其结果n c 值衡量了一个向量在另一个向量上投影的大小，也 即两个向量的相似程度，图像中某一区域和参考图像越相似，那么这个区域对应的n c 值就越大。二维数组中n c 值最大的元素的位置就是模板在图像中的位置。 m n c ；yys 。，( m h ) t 。7 ( m ，n ) 【2 1 ) ：l l 篡 但是，点积本身并不能准确地定位，因为二维数组中n c 值中的大小还受到像素灰 度级大小的影响，如果图像中某一区域很亮像素具有较大的灰度级，那么其n c 值自然地也就变大了。我们更加关心的是向量间的夹角，并以此消除图像亮度变化对 定位的影响。 根据以上的分析，我们可以得到如下的计算公式： c o s0 = s 。( m ，n ) ，( m ，h ) ( 2 2 ) 其中，t ( m n 个像素) 为模板， s o 为图像被模板覆盖的区域( 子图) ，i 、j 为 f 图在图像中的坐标。 另外，如果把图像和参考图像都看作随机量，则由相关系数的概念又可以得到下 面的计算公式， 华中科技大学硕士学位论文 f s 一( m ，一) f 】( t 一( n ) 一n 、芝，芝，瑟u ( m ，n ) 一f 、窆兰 ”( ，。，。) 一厂? ￥m = l lvm ( 2 3 ) 其中，s 、t 为子图和模板中豫素欢度缴的平均值，分子是协方差，分母是标准 差的乘积。 2 。2 2 贯淳相禳裣浏算法 如果摸叛甥对予霉像挺慰覆嚣款变化还包括旋转鞍姊缨，郅么可以使瘸多令摸投 来进行定位。然而，当模板数增加时，计算照也随之急剧地上升。b a r n e a 和s i l v e r m a n 提如了一耪效率很糍的贯序相似糗测算法( s s d a ，s e q u e n t i a ls i m i l a r i t y d e t e c t i o n a l g o r i t h m ) 8 1o 该算法从两个方面对计算效率进行r 改进。 首先，簿法使用购相似性度量方法e 计算更为籁单。 m* e = is 7 ( m ，n ) 一t “( ，n ) i ( 2 - 4 ) m = 1 ；：i 嚣嚣避行麴一纯缛至l ， 凹= js 。7 ( m ，h ) 一了一r - 。( 州，”) 一r j ( 2 _ 5 ) * 。i # = i 其中，s 、r 分别是子图和模扳中像素灰度级的平均德。s s d a 实质上是把向量 空阍中嚣患瓣懿距囊作为了嚣令彝繁稷 敦程发瓣度鬟，与 扫彳乏获寝级翊关雾法楣比， 此算法没有乘法运算，减少了计算擞。 英次，簿法豹麓二个改送在于它引入了爨序搜索羡路。此搜索策略基予这样一个 简单的事实：子图与模板的差别越大，该予图处的f 值也越大。因此，在搜索前可以 设豢一个f 的阑毽，每次搜索时只簧s 超过这个阑德就丢夯该子图点，并记录下参与 了计算的像素个数。显然，参与了计算的像素数越多，该予图点就越有可熊是模板在 图像i 事l 的最终位置。当图像中每个子图点的f 值计算完毕，参与计算敦像索最多的位 置就是模板在图像中的最终位置。 s s d a 冀法可以避一步改进。在子图点( i ，j ) 处，对模板覆盏的m 2 个点，可用 与i ，i 无关的随祝方式决定计算e 值的先后顺序。不选用圈定的闽值，而殴用荜调增 长的阁值序列，使得非匹配予图点在更少的计算过程中就达到阈值丽被丢羚。 华中科技大学硕士学位论文 2 2 。3 多羹翔据 幽归一化灰度级相关方法积贯序相似捻测算法的数学意义可以看出，这两科j 方法 都只是从巢一个角度衡量了图像之间的相似性，因此他们都存在一定的不完善性，且 两种方法的结果之间存在茇异。文献【9 】采用两釉或题种以上的基本相关判据网时满足 最大相关条件来确定最终的匹配位鬣，这种方法称为多重剡据相关方法，它可以利用 单判据之间的相互制约达到减少相关错误率、提商相关可靠性的目的，但是其计算 量将明显壤大。多煎蓟据桶关方法可阻有许多种缀合的方式，僵箕原则是箕可靠往要 比任何单一判据相关算法要离。 2 2 4 亚像素精度的模板麟酉己方法 以上的模板匹配方法能确定出模板在输入图像中以像豢为单位的位嚣礁标。为了 达到皿象索的精度，t i a n 和h u h n s 在s s d a 的基础上，利用攒值，提出了具肖亚象素精 度模板西配方法l l 钟，其懋路是：对输入阗像插毽并良更离的分辩率逶彳亍蘧采样，荐 对新得出的图像进 ：s s d a 。假定要达到1 像素的精度，一幅n n 的图像就要被插值 和蓬莱样到l n 1 0 0 n 太，l 、。在穰蔼不溺静捶箧方法、不黼靛系统噪声霸不弱的羹仡 位数的情况下，这种算法的平均误靛为0 o t n o 0 5 像索。回顾此算法，不难发现每一副 输入图豫都要送行攘毽稻黧采样，缀然嚣繇黎疆瘫| l s 攥窭t 一耱更浚弱算法i l ”，毽诗葬 所需的时间仍然是实时处理所不能接受的。 f r i s c h h o l z 窝s p i n n t e r 撼出了一耱实薅鹣翌象紊模援嚣邂箕法”“。魏算法帮文献叫 所提出算法的最大的不同就是插值和重采样的对象不同，谨是对横板而不是输入图像 进行撼毽积重罴群。因此这计算髦巨大静处理过疆可以预先完或，在实射处理中提 高速度。设要求达到的精度为o 1 像素，那么要预先计算1 0 0 个横板，其中每个模板 依次向x 或y 方惫平移o 1 个像素，圜此计算量仍然很大，但有掰个办法珂以减小计 算餐。计算时，先用原模板进行全局的匹配，此后用插值得到的模板进行硒部的区配， 一曼s s d a 值小于全局匹配对的最小值就结束计算。为了进一步掇高精度和减小计算 量，又在s s d a 后进行了谈差鲥正。以一维情况为例，设e j is s d a 计算褥到的坐梅为 h ，那么与h 相邻的两个点h l 和h + l 的s s d a 值显然比h 要大。对h 一1 、h 、 h + i 三个点的s s d a 值迸行抛物线插值，计算所褥的抛匏线的最小值点裁可认为怒萎 精确的坐标。试验袭明，抛物线插值可以把原有的精度再提高5 倍 1 3 1 ：因此要达到1 0 像素的精度就只浠插值计算4 个模板。就算法1 秒睾率髓送行3 0 次测量，最大误麓为 0j 像素。 9 华中科技大学硕士学位论文 2 3 基于傅立叶变换的匹配方法 2 3 1 f f t 相关匹配方法 f f t 相关匹配方法是把图像从空间域变换到频域，模板和待检测图像在空间域上 的互相关运算转换成了频率域上频谱的复数乘法运算。 f s ( u ，v ) = f f t ( s ( x ，y ) )( 2 - 6 ) f r ( u ，v ) = f f t ( t ( x + f ，y + 朋( 2 7 ) c o r r ( u ，v ) = f s 刀( 2 8 ) c ( f ，j ) = ，玎一 c o r r ( u ，v ) ( 2 - 9 ) 其中s ( x ，y ) 和r ( 0 + f ，y + j ) 分别为输入图像和模板图像，f s ( u ，v ) 和f t ( u ，v ) 分别 为s ( x ，y ) 和r ( 0 + f ，y + ，) 的傅立叶变换。f f t 相关匹配方法利用卷积定理和f f t 算法 。叮以提高匹配速度；同时，傅立叶变换可以通过硬件实现，可进一步提高运算效率。 2 3 2 基于傅立叶变换的相位匹配 经过傅立叶变换，图像由空域变换至频率域，两组数据在空间上的相关运算可以 变为在频率域上频谱的复数乘法运算。 信号经过傅立叶变换后分为幅值谱和相位谱，对于模板丁优纠和子图s 化纠，其傅 立叶变换分别为f t ( u ，砂和册m ，w ，当它们之间存在位移：t ( x ，y ) = s ( x x 0y y 。) 时， 其傅立叶变换关系为”： f t ( u ，v ) = f s ( u ，v ) 8 1 2 ”+ “ ( 2 1 0 ) 定义：q ( “，v ) = - f i s i * i ( u j , i v ) j f ：亍t 丽( u , v ) = e x p ( ( 口一( “，v ) 一以( “，v ) ) ) ( 2 - 1 1 ) 其中：眈( “v ) 和眈( “，v ) 分别为f s ( u ，v ) 和f t ( u ，v ) 的相位谱。当信号发生位移时， 其幅度谱不变，由式( 2 - 1 1 ) 得到： q ( u ，v ) = e x p ( 一j 2 e r ( u x 。+ v y o ) ) ( 2 - 1 2 ) 华中科技大学硕士学位论文 上式的傅立叶反变换在( ，y o ) 处为冲激响应，因此在匹配点处可以得到冲激响应 峰值。同样，若信号问存在旋转变换时有： t ( x ，y ) = s ( x c o s o o + y s i n o o x 0 ，- - x s i n 臼o + y c o s o o y o )( 2 - 1 3 ) 其傅立叶变换为： f t ( u ，v ) = p 一。2 ”“1 + f s ( u c o s o o + vs i n o o ，一u s i n o o + v c o s 0 0 )( 2 1 4 ) 定义： q ( u , v , o ) 2 面丽而而f 面t ( u , 磊v ) 石丽面 ( 2 1 5 ) 通过不断旋转f s ( u ，v ) ，当0 = - - o o 时，上式经傅立叶反变换后将有冲激响应峰值。 2 4 基于投影的匹配方法 2 4 1 一维灰度投影匹配方法 投影匹配算法是把二维的图像灰度值投影变换成一维的数据，再在一维数据的基 础上进行匹配运算，通过减少数据的维数来达到提高匹配速度的目的，从而有效地提 高匹配的速度。 假设有m x n 的图像f ( x ，纠( 以向x 轴投影为例) ，现在以左下角的那点为原点， 向x 轴作叠加投影，得到投影后的一维数据为： m 只( f ) = 芝：f ( i ，) ( 2 - 1 6 ) = 1 文献 1 4 1 根据图像灰度的空间特性提出了利用一维投影数据的差分字符串进行图 像匹配的快速算法。考虑到两幅匹配图像，相邻象素的灰度值的相对大小关系应该是 相同的：如果某搜索窗口与模板匹配，那么相应象素之间的灰度大小关系一定与模板 的一致，反之，如果不满足这个条件就可以认为与模板不匹配，而且灰度值之间的大 小关系不随灰度值的线性变换改变而改变，这一特征对灰度的线性变换有“免疫性”。 基于以上考虑，对数据一维投影后，对数据串进行差分处理：在相邻的两个数据中， 用后面的减前面的，结果为正，记为1 ，结果为负，记为o 。这样，一个长度为n 的 一维数据可以得到n 1 维的0 1 字符串，这个字符串就构成了表征模板或者搜索窗口 的特征。这样在模板匹配过程中，只需要将模板的o 一1 字符串和搜索窗口中的字符串 华中科技大学硕士学位论文 = = = = = = = = = = = = = = ；= = = = = = = = = = = = 一 进行匹配运算，就可以获得配准的结果。这种方法在保证匹配结果的前提下，可以提 高匹配的速度。 2 4 2 圆投影匹配方法 吲投影匹配方法是在输入图像中检测目标物体的一种快速有效的方法。它利用小 波变换将输入图像和模板图像分解为各个尺度上的细节图像 ：( x ，力，删( x ，y ) ，船( x ，y ) ，其中j 表示尺度，由此得到尺度j 下的复合图像： ： q ( ) = 懈( w ) h 瑞( ) h 篇( ) f ( 2 - 1 7 ) x , j 。于尺寸为m x n 的图像，尺度，下的复合图像尺, 5 - 蔓j ( m f ) x ( n f ) 。复合图 像中具有较大能量的点般只占总数的2 0 - - 3 0 ，而其他点一般都接近于0 ，因此下 。步的匹配过程可以只考虑具有高能量值的点，即只在这些点处计算模板和子图的相 关系数，从而大幅降低匹配所需的时蚓。 为了能在输入图像中检测出已经旋转了的模板，文献 1 5 】引入了圆投影方法。圆投 影将圆形窗口中的二维图像函数变换为个以一系列同心圆的半径为自变量的维函 数。二维图像的圆投影不仅具有旋转不变性，而且还将匹配的计算复杂度由o ( 酽) 降 低到o ( ，w 表示圆形窗口的半径。其变换公式为： p ( ，) = ( t c o s o k , r s i n o + ) ( 2 1 8 ) 其中怫表示落在以r 为半径的圆周上的像素总数，r 是以窗口中心为圆心的一系 列同心圆的半径，= d ，2 ，w 。图一显示了圆投影的结果，有此可以看到图像旋转后 其圆投影仍然不变。 设模板和子图的圆投影分别为p r = 印删，p r 倒，p rr 叨 和始= 船例p s 川，p s 渺p ，则尸7 - 和p s 之间的归一化相关系数定义为： 矿赢麓摧篙舞陋 其中鸬= i 矿干1i 己。w 所( ，) ，鳓2 i 矿石1 乞，：。w 岛( r ) 华中科技大学硕士学位论文 目国 l 豳豳黧 2 5 基于轮廓的匹配方法 图2 4 1 圆投影 基于图像灰度信息的匹配方法比较直观、容易实现，但在通常情况下，输入图像 巾以模板位置为中心，相似性测度值会形成平缓的峰面；在这种情况下，准确计算匹 配位簧的难度较大。此外，图像的狄度值常会受到光照条件的影响，非线性的不均匀 光照会造成最终结果的较大偏差；同时，图像的比例变化，旋转，部分遮挡等都会显 著地影响匹配结果。基于特征的匹配方法在很大程度上可以避免上述缺点。在2l 节 中已经提到，图像的特征可能是边缘、轮廓、表面，也可能是物体的角点、线段的交 点、具有较大曲率的点。基于特征点的匹目d 方法将在以后的章节里详细论述，这旱只 对基于轮廓的方法作简单介绍。 在基于轮廓的匹配方法0 1 6 , 4 0 1 中，首先就要提取出图像中目标物体的轮廓。文献 1 6 】 为，得到连续、叫靠的轮廓，将轮廓的提取分为两步进行。第一步，将图像与l o g 算 于做卷积得到边缘图像。第二二步检测边缘图像中的零交叉点，并将零交叉点处的边 缘强度与事先设定的两个阂值相比较，判断该点是否属于目标的轮廓，最后计算轮廓 的长度，丢弃长度较短的轮廓。 得戥图像中目标的轮廓后，就要对轮廓进行编码。一条曲线可以由一个整数序列 表示k 0 ，127 1 ，序列中的每一个都表示曲线上的点相对于前一个点的方向，例 如：1 表示4 5 0 ，3 表示1 4 5 0 。文献1 6 1 对以上传统的编码方案做了改进，它对传统的 键吗溉a a 。) 进行移位得到新的链码 岛，6 ：，6 ) ，移位的方法如下： 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一一： 6 】= d l 鳗满足条件：国j q ) m o d 8 = o 剧吼一b ：峰小，i = 2 3 月 一条与z 轴成一2 2 5 。角的直线用传统的编码方法得到链码 7 ，0 ，7 ，0 ，7 ，0 ) ，而由改进 后的编码方法得到 7 ，8 ，7 ，8 ，7 ，8 ) ，显然后者与实际情况更相符。最后再对链码进行高 斯滤波，得到曲线最终的链码表示。 图2 5l 轮廓的链码表示 最后就要对两幅图像的轮廓进行匹配，得出两幅图像之间的相对位置关系，这分 两步进行。第一步，根据轮廓的一些几何、形状特征，例如：轮廓的长度、轮廓点距 轮廓质心的最长和最短距离、轮廓的一阶和二阶不变矩，确定出轮廓之间的匹配关系， 得到匹配轮廓集。第二步，根据匹配轮廓上的点的坐标，由最小二乘法估计出图像的 楣刘位置。 2 6 本章小结 本章首先对图像匹配方法的应用领域做了详细介绍，并对各种方法做了大致的分 类，此后详细地介绍了一些常见的图像匹配方法。总的说来，这些方法有一下特点： 1 ) 基于图像灰度信息的匹配方法直接利用图像的灰度信息，区分不同对象的能力 强、精度高，特别是在十分复杂的图像环境和要求高精度的应用领域能够有效地工作； 它不需要抽取图像的特征，可以避免由此带来的误差；但在通常情况下，输入图像中 翮一网习。网 华中科技大学硕士学位论文 以模板位置为中心，相似性测度值会形成平缓的峰面；在这种情况下，准确计算匹配 位置的难度较大。此外，图像的灰度值常会受到光照条件的影响，非线性的不均匀光 照会造成最终结果的较大偏差：同时，图像的比例变化，旋转，部分遮挡等都会显著 地影响匹配结果。 2 ) 基于图像特征的匹配方法，如点模式匹配