（应用数学专业论文）基于kpca的图像匹配算法研究.pdf

武汉理工大学硕士学位论文 捅要 图像匹配是根据已知模式的图像在一幅陌生图像中寻找对应该模式的子图 像的过程，它是图像理解和机器视觉的基础，其应用领域十分广泛。图像匹配 研究涉及到了许多相关知识领域，如图像采样、变换、预处理、分割、特征提 取等，并且与计算机视觉、多维信号处理和数值计算方法等紧密结合。 本文首先系统分析了国内外近年来关于图像匹配问题的研究状况，总结了 图像匹配这一研究领域的进展，分析讨论了图像匹配的研究方法，比较了它们 优点和不足，并阐明了有待进一步研究的几个问题。 基于灰度信息的匹配方法和基于图像内容特征的匹配方法虽有其自身的不 足，但由于这两种方法，尤其是二者相结合，已取得了比较好的匹配效果，引 起了许多学者的研究兴趣。本文着重研究了基于灰度信息的匹配和基于图像内 容特征的匹配方法。 其次，主成分分析( p c a ) 是最为常用的特征提取方法，被广泛应用到各 领域。本文详细论述了主成分分析的基本思想、数学模型、几何解释及推导、 算法执行步骤等内容，然后将主成分分析引入图像匹配处理中，提出基于主成 分分析的图像匹配算法，并对其进行了一定的改进，通过实验，证明了基于主 成分分析的图像匹配方法比传统的归化互相关匹配方法具有更好的鲁棒性， 能较好地克服由于图像尺寸、方向、部分场景内容变化以及噪声干扰等的影响。 再次，由于p c a 只考虑了图像数据中的二阶统计信息，未能利用数据中的 高阶统计信息，忽略了多个像素间的非线性相关性。研究表明，一幅图像的高 阶统计往往包含了图像边缘或曲线的多个像素间的非线性关系。针对这一问题， 本文引入了核方法，并通过最d x - 乘回归的例子，分析研究了核方法的所有主 要的成分：然后将核方法与p c a 方法结合，提出基于核主成分分析( k p c a ) 的图像匹配方法。 最后，针对目前图像匹配中的一个研究热点人脸匹配，运用p c a 和 k p c a 方法进行了对比实验，验证了本文方法的有效性。 关键词：图像匹配，互相关，主成分分析，核函数 武汉理工大学硕士学位论文 a b s t r a c t i m a g em a t c h i n gi sap r o c e s so fs e e k i n gt h ec o r r e s p o n d i n gs u bi m a g ei nas t r a n g eo n eb a s e d 0 1 1t h ei m a g ew i t hk n o w nm o d e i ti st h eb a s i c so fi m a g eu n d e r s t a n d i n ga n dm a c h i n ev i s i o n i t s a p p l i c a b l ef i e l di sv e r ye x t e n s i v e t h er e s e a r c h e sr e f e rt om a n yi n t e r r e l a t e dk e ns u c ha si m a g e s a m p l i n g ，t r a n s f o r m a t i o n ，p r e t r e a t m e n t ，s e g m e n t a t i o n ，f e a m r ee x t r a c t i o na n ds oo n i ta l s ol i n k e d t i g h t l yt oc o m p u t e rv i s i o n ，m u l t i d i m e n s i o n a ls i g n a lp r o c e s s i n g a n dn u m e r i c a lc o m p u t a t i o n m e t h o d t h i sp a p e rf i r s t l ya n a l y z e st h er e s e a r c ha c t u a l i t yo fi m a g em a t c h i n gi nr e c e n ty e a r sa th o m e a n d 曲r o a ds y s t e m a t i c a l l ya n ds u m m a r i z e st h ed e v e l o p m e n to ft h i sf i e l do fr e s e a r c h t h e nw e d i s c u s si t sr e s e a r c hm e t h o d sa n dd r a wac o m p a r i s o nw i t he a c ho t h e r f u r t h e r m o r e ，w ep r o p o s e s o m ep r o b l e m sf o rd i s c u s s i o n t h o u g ht h em a t c h i n ga p p r o a c h e sb a s e do ng r a ys c a l ei n f o r m a t i o na n dc h a r a c t e r so fi m a g e h a dd i s a d v a n t a g e s ，t h ec o m b i n a t i o n so ft w om e t h o d sh a v ea c h i e v e db e t t e rm a t c h i n ge f f e c ta n di t h a sm a d ea na p p e a lt om a n yr e s e a r c h e r s t h i sp a p e re m p h a s i z e st h em a t c h i n ga p p r o a c h e sb a s e d o ng r a ys c a l ei n f o r m a t i o na n dc h a r a c t e r so fi m a g e s e c o n d l y ，p r i n c i p a lc o m p o n e n ta n a l y s i si st h ec o m m o n e s ta p p r o a c ho ff e a t u r ee x t r a c t i o n a n di sa p p l i e dt ov a r i o u sf i e l d s t h i sp a p e rs p e c i f i e si t sb a s i cp r i n c i p l e ，m a t h e m a t i c a lm o d e l ， g e o m e t r i cs i g n i f i c a n c e ，d e d u c i n g a n dt h ep l o c e o fa l g o r i t h m ，t h e ni n t r o d u c e sp r i n c i p a l c o m p o n e n ta n a l y s i st oi m a g em a t c h i n gp r o c e s sa n dp r o v e si t so p t i m a l i t yi nt h ee x p e r i m e n t s t h e i m a g em a t c h i n gb a s e do np r i n c i p a lc o m p o n e n ta n a l y s i sh a sp r e f e r a b l er o b u s t n e s st h e nt r a d i t i o n a l n o r m a l i z a t i o nc r o s s - c o r r e l a t i o nm a t c h i n ga n dc a na v o i dt h ei n f l u e n c eo fi m a g es i z e ，d i r e c t i o n ， p a r t i a ls o g n ea n dn o i s ej a m m i n g t h i r d l y ，p r i n c i p a lc o m p o n e n ta n a l y s i so n l yr e f e r st os e c o n d - o r d e rs t a t i s t i ci n f o r m a t i o no f i m a g ed a t aa n dd o e sn o tu t i l i z et h ch i g h - o r d e ro n e s i ti g n o r e si t sn o n l i n e a rr e l a t i v i t ya m o n ga l a r g en u m b e ro fp i x e l s ，r e s e a r c h i n d i c a t e st h a th i g h - o r d e rs t a t i s t i ci n f o r m a t i o ns o m e t i m e s c o n t a i n si m a g ee d g eo rn o n l i n e a rr e l a t i o n sa m o n gm u l t i p i x e l s a i m i n ga tt h i sp r o b l e m ，t h i s p a p e rp r o p o s e sk e r n e lm e t h o da n ds t u d i e sa l l i t sp r i m a r yc o m p o n e n t sa c c o r d i n gt ot h ee x a m p l e s o fl e a s ts q u a r er e g r e s s i o n t h e n ，w ec o m b i n ek e r n e lm e t h o da n dp r i n c i p a lc o m p o n e n ta n a l y s i st o p r e s e n tt h ei m a g em a t c h i n gm e t h o db a s e do nk e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s f i n a l l y ，w ed r a wac o m p a r i s o nb e t w e e np r i n c i p a lc o m p o n e n ta n a l y s i sa n dk e r n e lp r i n c i p a l c o m p o n e n ta n a l y s i sa i m i n ga to n eo ft h eh o tr e s e a r c h e so ni m a g em a t c h i n g - a c em a t c h i n g a n dv a l i d a t ei t se f f e c t i v e n e s s k e y w o r d s ：i m a g em a t c h i n g ，c r o s s - c o r r e l a t i o n ，p r i n c i p a lc o m p o n e n ta n a l y s i s ，k e r n e lf u n c t i o n 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中明确的说明并表示了谢意。 研究生签名：避日期卫越 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部内容， 可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 研究生签名：李摊导师签名：雌毒_ 日期五心 武汉理工大学硕士学位论文 第1 章绪论 1 1引言 随着科学技术的迅猛发展，图像匹配技术己成为近代信息处理，特别是图 像信息处理领域中的一项非常重要的技术，1 9 9 8 年自动化图像协会关于机器视 觉的报告中指出，大约有4 0 的机器视觉应用中需要用到图像匹配技术。图像 匹配技术所涉及的应用领域很广泛，从工业检测推广到导弹的地形和地图匹配、 飞机导航、武器投射系统的制导、光学和雷达的图像模板跟踪、工业流水线的 自动监控、工业仪表的自动监控、资源分析、气象预报、医疗诊断、交通管理、 文字识别、图像数据库检索以及景物分析中的变化检测等等。因此，开展图像 匹配技术的研究具有重要的理论意义和实用价值。 在机器识别事物的过程中，经常需要根据已知模式( 通常是人们感兴趣的 对象) 的图像在一幅陌生图像中寻找对应该模式的子图像，这个过程就是图像 匹配( 见图1 1 ) 。我们将已知的图像或已知模式的图像称为模板图，将待检测 的陌生图像称为匹配图，在陌生图像中町能与它对应的子图称作该模板的潜在 匹配子图像1 1 j 吐 模板图 图1 1 匹配图 模板图和匹配图 由于各种各样的原因，如：成像条件的差异、图像预处理引入的误差等， 参与图像匹配的模板与潜在的匹配子图像间通常存在着程度不同的不一致，因 此，根据模板在一幅陌生图像中检测出潜在的匹配对象并得出它在图像中的位 置是一件复杂的工作。图像模板匹配是计算机图像分析中最基本和最常用的方 法，在有些情况下，图像模板匹配过程只是针对两幅图像在空间上的相对平移 武汉理工大学硕士学位论文 过程；但是在相当多的实际应用中，由于以下的一些主要因素，使得匹配变得 十分复杂： ( 1 ) 传感器噪声； ( 2 ) 传感器位置变化或者载物平台抖动； ( 3 ) 目标对象的平移、旋转、变形或者膨胀等； ( 4 ) 成像光照条件的变化以及阴影遮挡等； ( 5 ) 不同传感器成像造成的匹配困难； ( 6 ) 具体应用场合的匹配速度要求。 图像匹配技术研究涉及到了许多相关知识领域，如图像预处理、图像采样、 图像分割、特征提取等，并且将计算机视觉、多维信号处理和数值计算方法等 紧密结合在一起( 图1 2 ) 。 图1 2图像匹配系统 1 2 图像匹配算法的分类和比较 由于匹配图与模板图拍摄时间与条件的变化，同时由于成像设备的限制， 使得模板图与匹配图之间不仅存在严重的灰度差异，而且存在相当的几何变形。 通过对模板图进行灰度校正和几何校正可以很大程度上改善这种情况，但在模 板图和匹配图之间仍存在着一定的灰度失真和几何变形。另外，匹配图本身也 存在着一定的噪声干扰。因此匹配算法不仅应该具有计算量少，便于硬件或并 行实现，还必须具有良好的抗噪能力和抗几何变形的能力。 迄今为止，人们已经提出了各种各样的图像匹配算法，但从总体上讲，这些 匹配算法可以分成关系结构匹配方法、结合特定理论工具的匹配方法、基于灰 度信息的匹配方法、基于亚像元匹配方法、基于内容特征的匹配方法五大类型。 武汉理工大学硕士学位论文 1 2 1基于关系结构i 匹r i p _ 方法 所谓关系结构主要是指语义网络。这种方法是把计算机中的模型同外部世 界中的物体或现象建立起对应关系，即利用图像的结构特征或关系特征之问的 关系，把物体和物体问的关系表示成结构，通过沿图中的弧作关联搜索，建立 图中结点之间的关系，借助语义网络、框架理论和图论方法寻求匹配问题的解 决。进一步讲，这种方法是人工智能技术在图像匹配领域的应用，在这个意义 上，景物可用知识和规则来描述，利用知识和规则实质上是给景物赋予了一种 解释，故这种方法也称为基于解释的匹配。这种方法在实现时，为了减少计算 量而使结构与点之间关系的描述常常是不完全的，并且它们缺乏一种有效的衡 量点集之问是否相同的手段，所以这种方法的研究至今尚未取得突破性进展。 1 2 2 结合特定理论工具的匹配方法 近年来，随着各学科许多新理论和方法的提出，人们也提出了许多与特定 理论、方法和工具相结合的匹配技术，比如基于神经网络的匹配技术【3 j f 4 j 、基于 小波分析和变换的匹配技术1 5 1 1 6 1 1 7 1 等等。 由于神经网络的并行分布处理等特点，神经网络匹配方法理所当然地引起 了人们的重视，利用神经网络进行图像匹配的基本方法是：首先利用某种特征 提取算法( 也可以是神经网络算法) 对图像进行预处理，并按要求提取一定数量的 特征点；接着根据构造的某种神经网络算法的要求，选取并输入网络需要的一 些初始状态，同时也将选取的特征点作为基本输入参数：然后启动神经网络算 法的迭代过程，可能还要有学习过程；最后给出迭代结果，并对其进行分析评 价。神经网络匹配方法的这种匹配过程有以下缺陷：( 1 1 特征点的选取还无法自 动实现，目前的研究仅限于一些边缘棱角突出的匹配识别实验等；( 2 ) 网络需要 的初始状态的选择对网络迭代过程影响较大，选择不当还会造成不收敛或陷于 某一极值而不能自拔；( 3 ) 特征提取的预处理，神经网络的学习和迭代过程都是 计算代价比较昂贵的过程。 由此可见，虽然神经网络匹配方法取得了一些初步进展，但由于收敛性、 通用性不够理想，还无法用于灰度变化平缓、特征不突出的图像匹配，与实用 性和实时性要求相差甚远。 小波变换作为一种新的数学工具，由于其良好的时频局部化和多分辨分析 特点，因而能有效地从信号中提取信息，通过伸缩和平移等运算功能对函数或 武汉理工大学硕士学位论文 信号进行多尺度分析，解决了傅立叶变换不能解决的许多问题。基于小波变换 的匹配技术首先对匹配图和模板图同时进行小波变换：然后分别在不同尺度上， 将匹配图和模板图的低频图像利用前面叙述的匹配算法进行匹配运算，通过设 置门限等选择一些位置点作为最终可信点；最后对匹配图和模板图的原始图像 进行匹配。不足之处是小波基的选取给匹配带来了一定的困难。总之，基于小 波变换的匹配技术利用它多分辨分析的思想，构造图像的塔式分解，可由粗到 精的分析图像数据，在图像匹配中，先在低分辨率下对图像进行全局匹配，然 后在高分辨率下对图像的细部进行匹配，其结果减少了迭代时落入局部最优点 的可能性，又提高了匹配运算速度和精度，因此成为目前的前沿课题之一。 1 2 3 基于灰度信息的匹配方法 基于灰度的匹配就是逐像素地把一个以一定大小的匹配图像窗口的灰度矩 阵与模板图像的所有可能的窗口灰度阵列按某种相似性度量方法进行搜索比较 的匹配方法，从理论上说就是采用图像相关技术。图像相关技术近二十年来得 到了迅猛发展，并形成了一门新的学科。由于它与其它方法帽比具有计算量小， 易于硬件实现等优点，围绕减少搜索空间和减少匹配时间的问题，人们相继提 出了序贯相似性检测算法、两级模板匹配算法、分层序贯匹配算法、多子区域 相关匹配算法等各种快速匹配算法；围绕抗噪声干扰和抗几何失真问题，人们 相继提出了随机符号变化准则、不变矩等算法：同时，人们对与提高匹配精度 和匹配速度有关的各种问题，比如定位精度、噪声、灰度电平偏差、量化误差 等误差因素对匹配性能的影响，各种预处理技术等都进行了比较系统的研究1 8 1 。 在早期的图像匹配算法研究中，主要是对两幅图像空间域一l 的灰度值进行 相关运算，根据相关系数的峰值，求出匹配位置。其中，常用的方法有：规 化互相关、统计相关、平均绝对差、平均平方差、基于f f r 频率域的频域相关， 包括相位相关和功率谱相关、不变矩。利用灰度信息匹配方法的主要缺陷是计 算量太大，由于实际工作中一般都有一定的速度要求，所以这些方法很少被使 用。现在已经提出了一些相关的快速算法，如幅度排序相关算法，f f r 相关算法 和分层搜索的序列判断算法等。 同时，上述方法还存在如下几个缺陷：( 1 ) 对图像的灰度变化比较敏感，尤 其是非线性的光照变化，将大大降低算法的性能：( 2 ) 计算复杂度高；( 3 ) 对目标 的旋转，形变以及遮挡比较敏感。 武汉理工大学硕士学位论文 1 2 4 基于亚像元匹配方法嘲 模式识别中的目标匹配和定位是一个传统问题，已经提出许多经典算法，但 是大多数定位精度都是象素级。由于大规模集成电路制造、摄影测量、工业检 测和目标检测等应用对精度要求不断提高，象素级的精度已经不能满足要求了， 而亚像元匹配可以突破物理分辨率的限制，提高匹配和定位精度，从而产生了 距像元匹配的算法研究，即：在已知待匹配图像信息、粗匹配点坐标、匹配模 板信息的情况下，计算图像匹配的亚像元级偏移。 亚像元定位一般有4 种方法：( 1 ) 基于图像高分辨率重采样的方法；( 2 ) 基 于曲面拟合的方法；( 3 ) 微分法；( 4 ) 基于f o u r i e r 分析的相位法等。在实际应用 中，经常使用重采样和拟合方法。由于重采样方法在实现插值时需花费大量的 时间，而曲面拟合方法所能达到的精度是有限的，但所需时间极少，因此将这 两种方法相结合，既能达到所要求的精度，又减少所需时日j ，是图像模板亚像 元定位的一种新方法。 1 2 5 基于内容特征的匹配方法 基于内容特征的匹配首先提取反映图像重要信息的特征，而后以这些特征 为模型进行匹配。局部特征有点、边缘、线条和小的区域，全局特征包括多边 形和称为结构的复杂的图像内容描述。特征提取的结果是一个含有特征的表和 对图像的描述，每一个特征由一组属性表示，对属性的进一步描述包括边缘的 定向和弧度，边与线的长度和曲率，区域的大小等。除了局部特征的属性外， 还用这些局部特征之问的关系描述全局特征，这些关系可以是几何关系，例如 两个相邻的三角形之闻的边，或两个边之问的距离：可以是辐射度量关系，例 如灰度值差别，或两个相邻区域之问的厌度值方差；或拓扑关系，例如一个特 征受限于另一个特征。人们一般提到的基于特征的匹配绝大多数都是指基于点、 线和边缘的局部特征匹配，而具有全局特征的匹配实质上是我们上面提到的关 系结构匹配方法。 特征是图像内容最抽象的描述，与基于灰度的匹配方法相比，特征相对于 几何图像和辐射影响来说更不易变化，但特征提取方法的计算代价通常较大， 并且需要一些自由参数和事先按照经验选取的阈值，因而不便于实时应用：同 时，在纹理较少的图像区域提取的特征的密度通常比较稀少，使局部特征的提 取比较困难。另外，基于特征的匹配方法的相似性度量也比较复杂，往往要以 武汉理工大学硕士学位论文 特征属性、启发式方法及阈方法的结合来确定度量方法。 基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于 图像的特征点比象素点要少很多，因而可以大大减少匹配过程的计算量：同时， 特征点的匹配度量值对位置的变化比较敏感，可以大大提高匹配的精确程度； 而且，特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以及遮 挡等都有较好的适应能力。所以基于图像特征的匹配在实际中的应用越来越广 泛。所使用的特征基元有点特征( 明显点、角点、边缘点等) 、边缘线段等。 尽管基于灰度信息的匹配方法和基于特征的匹配方法有其自身的不足，但 由于这两种方法，尤其是二者相结合，业已取得了比较好的匹配效果，所以许 多学者正在从事这方面的研究工作。本文在基于主成分分析( p c a ) 的图像匹配 算法的基础上，将基于核函数的主成分分析方法( k p c a ) 引入图像的特征匹配 之中，进一步提高了图像的匹配性能。 1 3 有待进一步研究的几个问题 图像匹配算法经过几十年的发展已经取得了很大的进展，各种算法相继提 出，但是由于拍摄环境复杂多变，现有算法在某些方面都有不尽人意的缺陷， 目前尚没有一种算法能解决所有的图像匹配问题，我们认为在以下几个方面值 得更深入的研究： ( 1 ) 复合匹配算法。上一节提到的五类匹配方法都有各自的优缺点，如果 能综合利用它们的优点将会取得更好的匹配结果，文献【1 0 】就采用了复合匹配方 法，实验结果表明多种匹配方法的结合能获得比单一匹配方法要好的结果； ( 2 ) 目前大多数算法是利用图像的全局特征，基于图像之间存在剐性变换 的前提下提出的，但是物体的全局特征一般不容易获取，而且当物体之日j 存在 遮挡时提取的全局特征是不可靠的，局部特征能较好地解决这一问题，因此很 有必要研究基于图像的局部特征以及图像之问存在非线性变换时的匹配算法； ( 3 ) 人们对灰度图像的匹配算法已经进行了比较广泛和深入的研究，对彩 色图像的研究却相对较少。图像匹配在图像检索、三维重建、目标识别和跟踪 以及人脸识别等领域都有非常广泛的应用，通过对大量文献的阅读发现对于彩 色图像的匹配研究最多的是基于颜色特征的图像检索，而对其在其它应用中的 研究甚少，因此这也是一个值得注意的问题： ( 4 ) 实时性在飞行器巡航制导等应用中非常重要，现有算法大多不能满足 武汉理工大学硕士学位论文 这一要求，笔者认为这主要是因为算法过于复杂以及采用串行方式执行，所以 应该尝试对算法进行改进，使其并行实现，并结合并行计算机和特定理论工具 进一步提高图像匹配的速度： ( 5 ) 在计算机视觉领域中，传统的边缘检测和图像匹配算法等都采用自主 的自底向上的过程，这一过程不依赖于高层知识，所以低层处理结果的误差将 传播到高层而没有修正的机会；另外，在很多基于特征的图像匹配中，都是假 设图像分割问题已经解决或者是不存在图像分割的问题，但这些假设是不合理 的。基于模型的方法为边缘检测、图像分割以及图像匹配等问题的研究提供一 个新的思路，现有结果也展现出了该方法的优越性，但是对它的研究还不够深 入，比如变形模型对于噪声比较敏感，初始轮廓及模板的选取困难，最优化过 程易陷入局部最小以及计算量大等都是需要进一步研究和克服的问题。 1 4 本文研究的目的和主要内容 本文主要包括以下几个方面的内容： 在第一章绪论部分，系统分析了国内外近年来关于图像匹配问题的研究状 况，总结了图像匹配这一研究领域的进展，从结构匹配方法、神经网络匹配方 法、基于灰度的匹配方法、基于亚像元匹配方法、基于特征的匹配方法五个方 面分析讨论了图像匹配的研究方法，比较了它们在进行图像匹配时的优点和不 足，并阐明了有待进一步研究的几个问题。 基于灰度信息的匹配方法和基于图像内容特征的匹配方法虽有其自身的不 足，但由于这两种方法，尤其是二者相结合，已取得了比较好的匹配效果，引 起了许多学者的研究兴趣。本文第二章进一步讨论了基于灰度信息的匹配和基 于图像内容特征的匹配方法。 主成分分析( p c a ) 是最为常用的特征提取方法，被广泛应用到各领域。本 文第三章详细论述了主成分分析的基本思想、数学模型、几何解释及推导、算 法执行步骤等内容，然后将主成分分析引入图像匹配处理中，并通过对比实验， 证明基于主成分分析的图像匹配方法比传统的归一化互相关匹配方法具有更好 的鲁棒性，能较好地克服由于图像尺寸、方向、部分场景内容变化以及噪声干 扰等的影响。 p c a 只考虑了图像数据中的二阶统计信息，未能利用数据中的高阶统计信 息，忽略了多个像素问的非线性相关性。研究表明，一幅图像的高阶统计往往 武汉理工大学硕士学位论文 包含了图像边缘或曲线的多个像素间的非线性关系。针对这一问题，本文第四 章引入了核方法，并将核方法与p c a 方法结合，提出基于核主成分分析( k p c a ) 的图像匹配方法。核主成分分析( k p c a ) 是基于数据的高阶统计，它描述了多 个像素间的相关性，所以运用k p c a 能够捕捉这些重要的信息，从而可以取得 更好的匹配效果。 第五章，针对目前图像区配中的一个研究热点人脸匹配，运用本文的 匹配算法进行了匹配实验，验证了本文方法的有效性。 第六章，总结了本文的工作，并讨论了今后努力的方向。 武汉理工大学硕士学位论文 第2 章图像匹配方法 2 1 引言 近几年在很多领域都有大量匹配技术的研究，如遥感、模式识别、自动导 航、医学诊断、计算机视觉等，各个领域的匹配技术都是对各自具体的应用背 景结合实际情况，度身定制的特定技术，但是不同领域的匹配技术之间在理论 方法上又具有很大的相似性，在某一领域中的匹配技术，很容易移植到其它相 关领域。本文主要以人脸匹配为背景，但在某种意义上同样适用于医学等其它 领域的相关图像。本文以下假定在图像匹配前，已进行了图像的精确几何校正， 匹配过程中不再考虑几何变形影响，只考虑辐射变形和随机噪声的影响。 2 2 图像匹配原理 2 2 1 数学描述 图像匹配可以定义为两幅图像在位置空间和狄度的配准。定义j 。，：是两个 二维数组，其中，扛，y ) 和，：o ，y ) 分别表示对应空白j 位置处的狄度值，此时可以 把两幅图像的匹配表示成如下表达式： ，： ，y ) = ，“( 9 0 ，_ ，) ) )( 2 1 ) 其中，g 是二维空间的一个坐标变换，即： 7 ，y7 ) 一g ( x ，y )( 2 2 ) ，是一维灰度的变换函数。 从而，图像匹配问题便转化为寻找最优的空闻和灰度变换，使季导在图像噪声 存在的情况下，可以进行正确的图像配准。一般情况下，灰度变换是不需要的， 除非在一些特殊情形下，傍j 如存在传感器类型的改变( 从光学传感器到雷达) 。寻 找空间或者几何变换是解决匹配问题的关键，这种变换经常用如下的两个单值 函数来表示丘，： ，z 0 ，) ，) = i ，( l ，y ) ，o ，y ) )( 2 3 ) 如果这些几何变换可以表示成若干独立的函数，例如可以用两个一维的变换 函数来表示这个二维的空间变换， ，o ，y ) = 丘 ) ，( ) ，)( 2 - 4 ) 则可以节省存储空间并且提高计算效率，具体来说，丘对应所有的x ，厂。对应 武汉理工大学硕士学位论文 所有的y 。 以上是图像匹配的一般定义，模板匹配作为图像匹配的一类重要方法，它主 要通过待匹配图像和模板之间的相似性度量来确定它们的相对位置。模板匹配 根据所使用的匹配特征可以大致分为两类：( 1 ) 直接利用图像灰度信息进行匹 配，例如规一化互相关匹配、统计相关匹配、平均绝对差匹配、频率域的频域 相关匹配，包括相位相关和功率谱相关匹配、图像不变矩匹配；( 2 ) 使用图像 特征进行匹配，例如点集匹配技术使用明显的角点或者边缘点进行匹配，这种 方法的关键是找到图像中易于识别的特征点，基于该特征空间的相似性度量来 确定模板在匹配图中的位置。 2 2 2 变换空间 各种配准技术都要建立自己的变换空间模型，变换空间的选取与图像的变 形特性有关。图像的几何变换可分成全局、局部两类。全局变换对整幅图像都 有效，通常涉及矩阵代数。典型的变换运算有平移、旋转、缩放；局部变换有 时又称为弹性映射( e l a s t i cm a p p i n g ) ，它允许变换参数存在对空日j 的依赖性。对 于局部变换，由于局部变换随图像像素位置变化而变化，变换规则不完全一致， 需要进行分段小区域处理。 经常用到的主要变换有刚体变换( r i 西dt r a n s f o r m a t i o n ) t 1 ”、仿射变换( a f f i n e t r a n s f o r m a t i o n ) 旧、透视变换( p e r s p e c t i v et r a n s f o r m a t i o n ) 、投影变换( p r o j e c t i v e t r a n s f o r m a t i o n1 、多项式变换( p o l y n o m i a lt r a n s f o r m a t i o n ) 等。 2 3 基于图像灰度信息的匹配方法 图像灰度信息般分为灰度信息和灰度统计信息。在两幅图像灰度信息相 似的情况下，常用的匹配方法有：互相关方法，基于n 叮的频域相位匹配方法， 以及图像矩匹配方法。 2 3 1 互相关匹配 互相关匹配方法是一种最基本的统计匹配方法【1 3 l 。互相关匹配要求模板图像 和待匹配图像具有相似的尺度和灰度信息。模板窗口在匹配图上进行遍历，计 算每个位置处模板图像和匹配图对应部分的互相关值，互相关信息最大的位置 便是模板在匹配图中对应的位置。 现在考虑将一个尺寸为j k 的模板图像w ( x ，y ) 与一个mx n 的大图像 武汉理工大学硕士学位论文 ，0 ，y ) 进行位置匹配，设js m 和k s n 。尽管借助矢量形式进行相关计算， 但直接使用图像形式更为直观。在最简单的情况下， ，y ) 和w ( x ，y ) 之间的相 关函数可写为： c ( 蹦) = ，o ，y ) w ( x 吨y f ) ( 2 - 5 ) 其中s 一0 , 1 , 2 ，m 一1 ；t o 工2 ，：一，n 一1 。式( 2 5 ) 中的求和是对f ( x ，y ) 和吣，y ) 相重叠的图像区域进行的。图2 1 给出相关计算的示意图，其中假设f ( x ，y ) 中给 定的原点在左上角，w ( x ，y ) 的原点在其中心。对任何在，o ，_ ) ，) 中给定的位置 o ，f ) ，根据式( 2 5 ) 可以算得c ( s ，t ) 的特定值。当s 和f 变化时，w ( x ，y ) 在图像 区域中移动并给出函数c ( s ，t ) 的所有值。c ( s ，f ) 的最大值指示与w ( x ，y ) 最佳匹配 位置。注意，对接近，o ，y ) 边缘的s 和t 值，匹配精度受图像边界的影响，其误 差正比于w ( x ，y ) 的尺寸。 图2 1 模板匹配示意 式( 2 5 ) 所定义的相关函数有一个缺点，即对，o ，y ) 和圳旺，y ) 幅度值的 变化比较敏感，例如当i ( x ，y ) 的值加倍时，c o ，f ) 的值也会加倍。为了克服这 个问题，可定义如下相关系数： ，o ，f ) - c r o ，y ) 一7 ，y ) h o s y r ) 一讯一，) ，一，) ) ( 2 - 6 ) 其中s - 0 , 1 , 2 ，m 一1 ；f - 0 ，1 ，2 ，n 一1 ，虿是w 的均值( 只需算一次) ， 7 ( x ，y ) 是i ( x ，y ) 中与w 当前位置相对应区域的均值。式( 2 6 ) 中的求和是对i ( x ，) ) 和 w ( x ，y ) 的共同坐标进行的。因为相关系数已尺度开区间【1 ，1 】，所以其值与 武汉理工大学硕士学位论文 ，0 ，_ ) ，) 和w ( x ，) ) 的幅度变化无关。 利用相关系数的计算，可将相关函数归一化，克服幅度变化带来的问题。 但要对尺寸和旋转进行归一化是比较低困难的。对尺寸的归一化需要进行空间 尺度变换。这个过程需要大量的计算。对旋转进行归一化更困难，如果对，0 ，y ) 的旋转角度可知的话，则只要将缸，y ) 也旋转相同的角度使这与，o ，y ) 对齐就 可以了。但在不知道旋转角度的情况下，要寻找最佳匹配需要将w ( x ，y ) 以所有 可能的角度旋转。实际中这种方法是行不通的，因而在任意旋转或对旋转没有 约束的情况下很少使用相关的方法。 为减少模板匹配的计算量，一方面可利用一些先验知识( 如立体匹配时的 极线约束) 减少需匹配的位置；另一方面可利用在相邻匹配位置上，模板覆盖 范围有相当大重合的特点来减少重新计算相关值的次数1 1 4 j 。 ( 1 ) f f i 相关匹配方法 f f t 相关匹配方法是把图像从空间域变换到频域，模板和匹配图在空间域 上的互相关运算转换成了频率域上频谱的复数乘法运算。 f m ，v ) = 肝r ( 厂o ，y ) )( 2 7 ) f i ( u ，v ) - f f t ( w ( x s ，y f ) ) ( 2 - 8 ) c o r r ，v ) 一f m f i( 2 9 ) c ( s ，f ) = 盯r 一 c o r r ( u ，y ) ( 2 一l o ) 其中，f m ( u ， ，) 和f t ( u ，v ) 分别为f ( x ，) ，) 和w ( x s ，y t ) 的f o u r i e r 变换。 如果，和w 的尺寸相同，则在频域计算有可能比直接空域计算效率更高。 实际上，w 一般远小于，有人曾估计过，如果w 中的非零项少于1 3 2 ( 约相当 于一个1 3 x 1 3 的子图像) ，则直接使用式( 2 5 ) 在空域中计算比用f f t 在频域中 计算的效率更耐1 5 l 。当然这个数字与所作的计算机和算法编程都有关系。图像 在空日j 域中的平移，旋转，尺寸变化都有对应的表达部分；而且可以排除频率 相关的噪声，从而获得鲁棒的匹配方法；同时，f o u r i e r 变换可以通过硬件实现， 大大提高了运算效率。 ( 2 ) 模板与匹配图差的绝对值 由于计算互相关时需要很多的乘积运算，为节省运算时间，通常选用模板 武汉理工大学硕士学位论文 与待匹配图像之间差的绝对值来衡量图像中是否存在模板。 形式： m d ( s ，t ) = m a x l f ( x ，) ，) 一计协一j ，y f ) | s a d ( s ，f ) = i ，o ，y ) 一w o 喵y 一叫 jy 一般采用如下三种 佗1 1 ) ( 2 1 2 ) s s d ( s ，f ) = e e i i ( x ，_ ) ，) 一h 取- s 7 y f ) 2 ( 2 - 1 3 ) j y ( 3 ) 基于多分辨的匹配方法 图像的金字塔模型在实际中已经得到了广泛的应用，它可以由粗到精地分析 图像数据。在图像匹配中，粗分辨率上所获得的模板位置可以传递到精细分辨 率上，指导在精细分辨率上模板可能存在位覆的搜索过程。d y e r l l 6 l 采用的方法 是自上而下的：对粗分辨率上的峰值点，在精细分辨率上检测其邻域窗口中是 否存在匹配测度的峰值点。但是上述方法对峰值的相关能量p c e ( p e a kt o c o r r e l a t i o ne n e r g y ) 度景却很少考虑，b o n m a s s a r l l 7 1 等提出了一种新的分层匹配 算法：基于l a p l a c i a n 多分辨率模型，累加所有层上的互相关值作为新的相似性 度量，通过这种方法不仅可以正确地检测到模板的位置，而且能够增强p c e 。 2 3 2 投影匹配 投影匹配算法是把二维的图像灰度值投影变换成一维的数据，再在一维数据 的基础上进行匹配运算，通过减少数据的维数来达到提高匹配速度的目的。投 影的示意图如图2 3 所示，其中厂o ，y ) 为图像函数，s 为投影方向，t 为其垂直 方向，则f ( x ，y ) 沿着s 的投影定义为： p ( t ，0 ) 一r ，o c o s o - s s i n o s i n 0 + s c o s o ) d s ( 2 - 1 4 ) 当0 固定时，p ( f ，口) 为t 的函数，是一个一维波形。不断在0 一幼间变换口， 可以得到在不同方向上的投影，特别地在x ，y 轴上的投影为： p ，一n c x , y ) d y ，p ，一r ，0 ) 出 ( 2 一1 5 ) 武汉理工大学硕士学位论文 j ky ) ，t ，j 0 ，。? 、 粤 ，弋e 。 x - 图2 3 投影坐标( f ，s ) 与原坐标0 ，y ) 间的对应关系 孙远等1 8 1 根据图像灰度的空间特性提出了利用一维投影数据的差分字符串 进行图像匹配的快速算法。考虑到两幅匹配图像，相邻象素的灰度值的相对大 小关系应该是相同的；如果某搜索窗口与模板匹配，那么相应象素之问的灰度 大小关系一定与模扳的一致，反之，如果不满足这个条件就可以认为与模板不 匹配，而且灰度值之问的大小关系不随灰度值的线性变换改变而改变，这特 征对灰度的线性变换有“免疫性”。 基于以上考虑，对数据一维投影后，对数据串进行差分处理：在相邻的两个 数据中，用后面的减前面的，结果为正，记为1 ，结果为负，记为o 。这样，一 个长度为n 的一维数据可以得到n 1 维的0 1 字符串，这个字符串就构成了表 征模板或者搜索窗口的特征，匹配运算将在两个0 - 1 字符串之问进行。过程如图 2 4 所示： d 】 d “】一d 1 ：n 】d 【r i 】 图2 4 投影示意图 在图2 4 中，d i 】为第f 列的象素灰度值的累加，o = 0 ，1 ，月一1 ) m a r g i n d i 】1d i 卜d i 一1 】 ( 2 1 6 ) 时 矗 m r r 武汉理工大学硕士学位论文 l i n e s t r i n g i 】- 1 , i f m a r g i n d i p0 ( 2 1 7 ) l i n e s t r i n g i 】一0 ，i f m a r g i n d i 1 o 。了解这一点也就可以明白为什么主成分的名 次是按特征根取值大小的顺序排列的。 在解决实际问题时，一般不是取p 个主成分，而是根据累计贡献率的大小取 前七个称第一主成分的贡献率为 ，由于妇r ( ) t ，所以 缗4 嚣舭一粉部 方差 中的比值。这个值越大，表明第一主成分综合x t ，z ，信息的力越 前两个主成分的累计贡献率定义为( + a 2 ) 善 ，前七个主成分的累计 贡献率定义为i 。1 艺i m l 。如果前七个主成分的贡献率达到8 5 ，即： 武汉理工大学硕士学位论文 善 倭 8 5 ( 3 - 1 4 ) 表明取前七个主成分包含了全部测量指标所具有的信息，这样既减少了变量 的个数又便于对实际问题的分析和研究。 值得指出的是：当协差阵未知时，可用其估计值s ( 样本协差阵) 来代替。 设原始资料阵为： x =