（电路与系统专业论文）图模型在点模式匹配中的应用.pdf

安徽大学博士学位论文摘要 摘要 i i i ii ii iii iiif ii ll li il 19 7 5 0 9 6 点模式匹配是模式识别与计算机视觉领域的一个重要的基础性问题，研究 成果可以广泛地应用于图像处理、目标识别与跟踪、计算化学、天文学等众多领 域。由于待匹配点集间常常存在着较大的差异，使得点模式匹配存在着较高的复 杂性，目前仍然是一个尚未完全得到解决的问题，多年来一直是诸多学者研究的 热点。 图模型是一种有效的结构信息表示方式，利用图模型来表示待匹配点集的 结构特征，通过研究图模型的匹配来实现点模式匹配得到了越来越多的关注，也 是目前点模式匹配问题的主要研究方向。本文通过构造不同的图模型，采用不同 的图模型表示方式对不同情形下的点模式匹配问题进行了研究，主要内容与创新 如下： l 、提出了一种基于线图q 谱的点模式匹配算法。首先，分别利用待匹配 点集构造赋权完全图；其次，对每个点，利用与其相关联的前k 条最短边来构造 线图；然后，根据线图构造无符号l a p l a c i a n 矩阵，并进行谱分解，应用无符号 l a p l a c i a n 矩阵的特征值( q 谱) 来表示点的特征，通过这些特征计算点之间的 匹配概率；最后，通过k m 算法来寻找点集之间的最优匹配，并将该最优匹配作 为最终的匹配结果。该算法可以在平移、缩放、旋转等变换下获得较好的匹配效 果，并且还能够处理不同大小点集的匹配问题。实验结果表明了该算法的有效性。 2 、提出了一种基于局部相对形状上下文与q _ 谱的点模式匹配算法。首先， 对每个点构造相应的线图，并对线图的无符号l a p l a c i a n 矩阵进行谱分解；其次， 利用分解所获得的特征值计算点的初始匹配概率：然后，通过定义局部相对形状 上下文计算点的相似性距离；最后，将q 谱方法与局部相对形状上下文结合进 行概率松弛迭代获得最终的匹配结果。实验结果表明该算法具有较高的匹配精 度，提高了q 谱方法的性能。 3 、提出了一种基于q r 分解的点模式匹配算法。首先，利用待匹配点集构 造赋权完全图，并根据赋权完全图构造赋权邻接矩阵；然后，对所构造的赋权邻 接矩阵进行q r 分解，利用分解所得的正交矩阵进行点集匹配；为了进一步提高 匹配的精度，提出了一种简单的通过比较点的前k 个最相似邻点的对应关系进 行误匹配检测的方法；最后，通过循环检测与匹配获得最终匹配结果。大量的实 安徽大学博士学位论文 图模型在点模式匹配中的应用 验结果表明该算法具有较高的匹配精度，并能够在较大仿射变换下获得较好的匹 配效果。 4 、提出了一种基于有向图谱的点模式匹配算法。根据两幅图像所提取的特 征点构造赋权完全图，在赋权完全图的基础上，提出一种边定向方法对其进行定 向，从而获得有向图；根据有向图，构造反对称矩阵，并对其进行谱分解，利用 获得的部分特征向量来表示点的特征，通过比较特征间的距离来实现匹配。从理 论上证明了该算法能够处理仿射变换下的点模式匹配问题，模拟实验与真实图像 实验证实了该算法的有效性。另外，作为有向图谱算法的一个应用，进行了遥感 图像配准，获得了较好的效果。 关键词：点模式匹配；图模型；线图；q r 分解；有向图；反对称矩阵；概率松 弛；图像配准 n 安徽大学博士学位论文a b s t r a c t a b s t r a c t p o i n tp a t t e r nm a t c h i n g ( p p m ) i sa l li m p o r t a n ta n df o u n d a t i o n a li s s u ei np a t t e r n r e c o g n i t i o na n dc o m p u t e rv i s i o n i t sr e s e a r c hr e s u l ti sw i d e l y u s e di nm a n ya r e a s ，s u c h a s i i 】1 9 ep r o c e s s i n g , o b j e c tr e c o g n i t i o na n dt r a c k i n g , c o m p u t a t i o n a lc h e m i s t r y , a s t r o n o m y , e t c h o w e v e r , h i g hc o m l e x i t ye x i s t s i np p md u et o l a r g ed i f f e r e n c e b e t w e e nt h et w op o i n ts e t st ob em a t c h e d b yn o w , p p mi ss t i l la l lo p e np r o b l e m , w h i c hi sah o tt o p i cm a n yr e s e a r c h e r sf o c u so n g r a p h i c a lm o d e li sa ne f f e c t i v ef a s h i o nt oe x p r e s ss t r u c t u r a li n f o r m a t i o n m a n y a t t e n t i o n sa r ef o c u s e do nt h ew a yt op r o c e s st h ep p m p r o b l e m 、) l ，i t l lg r a p h i c a lm o d e l s ， w h i c hi sa l s ot h em a i nd i r e c t i o nt od e a l 谢t l lt h ep p mp r o b l e m w eu t i l i z es e v e r a l d i f f e r e n tg r a p h i c a lm o d e l sa n dd i f f e r e n tg r a p h i c a l - m o d e l d e n o t e dw a y st od e a l 、衍t h t h ep p m p r o b l e m t h em a i nc o n t e n t sa n di n n o v a t i o n sa l ea sf o l l o w s ： 1 ap o i n tp a t t e r nm a t c h i n ga l g o r i t h mb a s e do nq - s p e c t r ao fl i n eg r a p hi s p r o p o s e d f i r s t l y , aw e i g h t e dc o m p l e t e dg r a p hi sc o n s t r u c t e d f o re a c hp o i n ts e t ； s e c o n d l y , al i n eg r a p hi sc o n s t r u c t e df o re a c hp o i n tw i t ht h ef i r s tks h o r t e s te d g e s ，a n d t h e ns p e c t r a ld e c o m p o s i t i o ni sp e r f o r m e do nt h es i g n l e s sl a p l a c i a nm a t r i xa s s o c i a t e d w i t ht h el i n e g r a p h t h ee i g e n v a l u e s ( q - s p e c t r a ) o b t a i n e df o r mt h es p e c t r a l d e c o m p o s i t i o na r eu s e dt or e p r e s e n tt h ep o i n t sf e a t u r e , a n dt h em a t c h i n gp r o b a b i l i t y i s c a l c u l a t e d ；f i n a l l y , t h eo p t i m a lm a t c h i n gi sf o u n db yk ma l g o r i t h ma st h ef i n a l m a t c h i n gr e s u l t t h ep r o p o s e da l g o r i t h mo a l lo b t a i nab e t t e rm a t c h i n gr e s u l tu n d e r t r a n s l a t i o n , z o o ma n dr o t a t i o ne t c ，a n da l s og a l ld e a lw i t ht h em a t c h i n gp r o b l e mo f t h e t w op o i n ts e t si nd i f f e r e n ts i z e 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 ee f f e c t i v e n e s so ft h e p r o p o s e da l g o r i t h m 2 a na l g o r i t h mf o rp o i n tp a t t e r nm a t c h i n gi sp r o p o s e d , w h i c hc o m b i n e sl o c a l r e l a t i v es h a p ec o n t e x ta n dq s p e c t r a f i r s t l y , al i n eg r a p hi sc o n s t r u c t e df o re a c hp o i n t , a n dt h es p e c t r a ld e c o m p o s i t i o ni sp e r f o r m e do nt h es i g n l e s sl a p l a c i a nm a t r i xo fl i n e g r a p h ；s e c o n d l y , t h ee i g e n v a l u e so b t a i n e df r o m t h es p e c t r a ld e c o m p o s i t i o na r eu s e dt o r e p r e s e n tt h ep o i l l t sf e a t u r e , a n dt h ei n i t i a lm a t c h i n gp r o b a b i l i t yi sc a l c u l a t e d ；t h i r d l y , ad e s c r i p t o rn a m e dl o c a lr e l a t i v es h a p ec o n t e x ti sd e f i n e dt oc o m p u t et h es i m i l a r i t y d i a t a n c eb e t w e e na n yt w op o i n t s ；f i n a l l y , q s p e c t r am e t h o di sc o m b i n e d 、析t t ll o c a l r e l a t i v es h a p ec o n t e x tv i aap r o b a b i l i s t i cr e l a x a t i o na p p r o a c ht o g e tt h em a t c h i n g r e s u l t e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mh a s ah i g h e r a c c u r a c y i i i 安徽大学博士学位论文 图模型在点模式匹配中的应用 3 a na l g o r i t h mb a s e d o n q rd e c o m p o s i t i o n ( o r t h o g o n a l - t r i a n g u l a r d e c o m p o s i t i o n ) i sd e s c r i b e d f i r s t l y , aw e i g h t e dc o m p l e t eg r a p hi sc o n s t r u c t e df o r e a c hp o i l l ts e t ；s e c o n d l y , q rd e c o m p o s i t i o ni sp e r f o r m e do nt h ew e i g h t e da d j a c e n t m a t r i c e sa s s o c i a t e d 谢t ht h et w ow e i g h t e dc o m p l e t eg r a p h s ，t h e nt h eo r t h o g o n a l m a t r i c e so b t a i n e df r o mq rd e c o m p o s i t i o na r eu s e dt om a t c ht h et w op o i n ts e t s t h i r d l y , i no r d e rt oi m p r o v et h em a t c h i n ga c c u r a c y , w ep r o p o s eas i m p l em e t h o df o r i n c o r r e c tm a t c h e sd e t e c t i n gr e l i e do nt h ec o r r e s p o n d e n c eo ft h ef i r s tks i m i l a r n e i g h b o r so ft h em a t c h e dp a i r s f i n a l l y , t h ef l a m ew o r ko fi t e r a t i v ed e t e c t i n ga n d m a t c h i n gi s e s t a b l i s h e dt 0g e tt h em a t c h i n gr e s u l t t h ep r o p o s e da l g o r i t h m ，w h e n a p p l i e dt 0a 、) l ，i d ec x p c d m e n t a ld a t a , h a ss h o w nh i g h e ra c c u r a c ya n dc a na c h i e v ea b e t t e rm a t c h i n gr e s u l tu n d e rl a r g ea f f m et r a n s f o r m a t i o n 4 ap o i n tp a t t e r nm a t c h i n ga l g o r i t h mb a s e do nt h es p e c t r ao fd i r e c t e dg r a p h si s p r e s e n t e d f i r s t l y , t w ow e i g h t e dc o m p l e t eg r a p h sa r ec o n s t r u c t e dw i t hf e a t u r ep o i n t s e x t r a c t e df r o mt h et w oi m a g e s ；s e c o n d l y , am e t h o df o re d g eo r i e n t i n gi sp r o p o s e dt 0 t r a n s f o r me a c hw e i g h t e d c o m p l e t eg r a p h t oad i r e c t e dg r a p h ；t h i r d l y , t w o s k e w - s y m m e t r i cm a t r i c e sa s s o c i a t e dw i t hr e s p e c t i v ed i r e c t e dg r a p h sa r ee s t a b l i s h e d ； f o u r t h l y , s p e c t r a ld e c o m p o s i t i o ni sp e r f o r m e do nt h et w os k e w - s y m m e t r i cm a t r i c e st 0 g e tas p e c t r a lr e p r e s e n t a t i o no ft h ef e a t u r ep o i n t sw i t hh a l fo ft h ee i g e n v e c t o r s ；t h e f i n a lm a t c h i n gr e s u l ti so b t a i n e db yc o m p a r i n gt h es p e c t r a lr e p r e s e n t a t i o no fe a c h p o i n t w et h e o r e t i c a l l ya n a l y z et h a to u t a l g o r i t h r nc a nw e l ld e a l 、析mt h em a t c h i n g p r o b l e mu n d e ra f f m et r a n s f o r m a t i o n t h ee x p r e i m e n t sa p p l i e dt 0s y n t h e t i cd a t aa n d r e a l - w o r l di m a g e ss h o wt h ee f f e c t i v e n e s so fo u rm e t h o d m o r e o v e r , a sa na p p l i c a t i o n o ft h i sa l g o r i t h m , w ea p p l yi tt or e m o t es e n s i n gi m a g er e g i s t r a t i o n , t h er e s u l ti s s a t i s f y i n g k e y w o r d s ：p o i n tp a t t e r nm a t c h i n g ；g r a p h i c a lm o d e l ；l i n eg r a p h ；q rd e c o m p o s i t i o n ； d i r e c t e dg r a p h ；s k e w s y m m e t r i cm a t r i x ；p r o b a b i l i s t i cr e l a x t i o n ；i m a g er e g i s t r a t i o n i v 安徽大学博士学位论文图模型在点模式匹配中的应用 插图清单 图2 1 几种图的示例1 4 图2 2 三个同构的图1 4 图3 1 线图的构造。2 6 图3 2 本章算法流程图2 9 图3 3 各种方法在两个模拟数据的大小一致的情况下的匹配结果。3 0 图3 4 各种方法在两个模拟数据的大小不一致的情况下的匹配结果3 l 图3 5 各种方法在图像帧数相差3 0 帧情况下的实验结果3 2 图3 6 各种方法在图像帧数相差4 0 帧与5 0 帧情况下的实验结果3 3 图3 7 各种算法在两个点集相差一定比例情况下的性能比较。3 4 图4 1 局部相对形状上下文示意图3 7 图4 2 岛的统计直方图3 7 图4 3 墨的统计直方图3 8 图4 4 汉字“福一4 1 图4 5 平移、旋转、缩放、翻转变换后的汉字“福 4 l 图4 6q l s c 算法匹配结果( 正确率1 0 0 ) 4 2 图4 7 文献 t a n g2 0 0 9 算法的匹配结果( 正确率2 7 6 ) 4 2 图4 8 不同方法对于位置噪声的匹配性能比较。4 3 图4 92 0 帧与3 0 帧在不同方法下的匹配结果4 5 图4 1 03 0 帧与5 0 帧在不同方法下的匹配结果4 6 图4 1 12 0 帧与5 0 帧在不同方法下的匹配结果4 7 图5 1 匹配过程示例( k = 2 ) 5 2 图5 2 不同变换下的匹配结果。5 3 图5 3 不同算法随机点抖动下的匹配效果5 4 图5 4 不同算法受仿射变换的影响。5 5 图5 5 不同算法受点数差的影响5 6 图5 6 匹配结果比较5 7 图6 1 边定向6 0 图6 2 算法流程图6 2 v i u 安徽大学博士学位论文插图清单 图6 3 汉字“福 6 6 图6 4 仿射变换后的“福。6 6 图6 5 匹配结果6 6 图6 6 不同算法受仿射变换的影响6 7 图6 7 不同算法的匹配结果6 9 图6 8 遥感图像配准算法的流程7 1 图6 9 原始图像。左边为参考图像、右边为待配准图像7 2 图6 1 0 特征点匹配结果7 2 图6 1 1 配准结果7 3 i x 室塑盔堂竖主堂垡堡塞 一一 图模型在点模式匹配中的应用 _ - - 一- ：= 二= ：= = ：= ：= = ：= ：= ：= ： l i s to fi u u s t r a t i o n s f i g 2 1e x a m p l e so f s e v e r a lg r a p h s 1 4 f i g 2 2t h r e ei s o m o r p h i cg r a p h s 1 4 f i g 3 1c o n s t r u c t i o no f l i n eg r a p h 2 6 f i g 3 2t h ef l o wo f t h ep r o p o s e da l g o r i t h m 2 9 f i g 3 3m a t c h i n gr e s u l t so fd i f f e r e n ta l g o r i t h m so nt w os a m e - s i z es i l i l u l a t ed a t e s 3 0 f i g 3 4m a t c h i n gr e s u l t so fd i f f e r e n ta l g o r i t h m so i lt w od i f f e r e n t s i z es i i n u l a t e d a t e s 31 f i g 3 5m a t c h i n gr e s u l t so fd i f f e r e n ta l g o r i t h m sw h e nt h ed i f f e r e n c 圮b e t w e e nt w o i m a g e sa l e3 0f r a m e s 3 2 f i g 3 6m a t c h i n gr e s u l t so fd i f f e r e n ta l g o r i t h m sw h e nt h ed i f f e r e n c eb e t w e e nt w o i m a g e sa g o4 0o r5 0f r a m e s 3 3 f i g 3 7p e r f o r m a n c ec o m p a r i n gw h e nt h et w op o 衄s e t sa td i f i t e r e n ts i z e s 。3 4 f i g 4 1d e m o n s t r a t i o no f l o c a lr e l a t i v es h a p ec o n t e x t 3 7 f i g 4 2s t a t i s t i c a lh i s t o g r a mo f2 5 l f 3 7 f i g 4 3s t a t i s t i c a lh i s t o g r a mo f 墨。3 8 f i g 4 4t h ec h i n e s ec h a r a c t e r 福”。4 l f i g 4 5t h ec h i n e s ec h a r a c t e r “福”a f t e rt r a n s l a t i o n , r o t a t i o n , z o o ma n df l i p p i n g t r a n s f o r m a t i o n s 二4 l f i g 4 6m a t c h i n gr e s u l t so f q l s cm e t h o dw i t hp r e c i s i o n1 0 0 4 2 f i g 4 7m a t c h i n gr e s u l t so ft h em e t h o dp r o p o s e di n t a n g2 0 0 9 w i t hp r e c i s i o n 2 7 6 4 2 f i g 4 8d i f f e r e n tm e t h o d s m a t c h i n gp e r f o r m a n c e sc o m p a r i n gu n d e rp o s i t i o n a l n o i s e 4 3 f i g 4 9m a t c h i n gr e s u l t sf o rt h e2 0 t hf l a m ea n dt h e3 0 t hf l a m eb yd i f f e r e n t m e t h o d s 4 5 f i g 4 10m a t c h i n gr e s u l t s 细廿l e3 0 t hf r a l t l ea n dt h e5 0 t hf r a m eb yd i f f e r e n t m e t h o d s 4 6 f i g 4 1lm a t c h i n gr e s u l t sf o rt h e2 0 t hf r a m ea n dt h e5 0 t hf r a m eb yd i f f e r e n t m e t h o d s 4 7 f i g 5 1g e n e r a lm a t c h i n gs t e p sw i t hk = 2 5 2 x 安徽大学博士学位论文l i s to fi l l u s t r a t i o n s f i g 5 2m a t c h i n gr e s u l tu n d e rd i f f f e r e n tt r a n s f o r m a t i o n s 5 3 f i g 5 3m a t c h i n gr e s u l t so f d i f f e r e n tm e t h o d su n d e rp o i n tp o s i t i o n a lj i t t e r 5 4 f i g 5 4e f f e c to f s k e wa n g l eo nd i f f e r e n tm e t h o d s 5 5 f i g 5 5e f f e c to fs i z ed i f f e r e n c eo nd i f f e r e n tm e t h o d s 5 6 f i g 5 6m a t c h i n gr e s u l t sc o p m p a r i n g 5 7 f i g , 6 1a ni l l u s t r a t i o no fe d g eo r i e n t i n g 6 0 f i g 6 2t h ef l o wo f t h ep r o p o s e dm e t h o d 6 2 f i g 6 3t h ec h i n e s ec h a r a c t e r “福”6 6 f i g 6 4 “福”t r a n s f o r m e x ib ya f f i n et r a n s f o r m a t i o n 6 6 f i g 6 5m a t c h i n gr e s u l tu s i n g o u rm e t h o d 6 6 f i g 6 6e f f e c to fs k e wa n g l eo nd i f f e r e n tm e t h o d s 6 7 f i g 6 7m a t c h i n gr e s u l t so f d i f f e r e n tm e t h o d s 6 9 f i g 6 8t h ef l o wo f r e m o t es e n s i n gi m a g er e g i s t r a t i o na l g o r i t h m 7 1 f i g 6 9t h ei n i t i a lr e m o t es e n s i n gi m a g e sf o rr e g i s t r a t i o n 7 2 f i g 6 1 0m a t c h i n gr e s u l tf o rf e a t u r ep o i n t s 7 2 f i g 6 iir e g i s t r a t i o nr e s u l t 7 3 “ x i 安徽大学博士学位论文第一章绪论 第一章绪论 1 1 研究背景与选题意义 图像匹配是指通过一定的匹配算法寻找两幅或多幅图像中像素点之间的 匹配关系，是计算机视觉、图像处理、模式识别等领域研究的热点问题，也 是众多相关理论研究的基础。根据匹配基元的不同，可以将图像匹配分为三 类 c a i1 9 9 7 ：区域匹配、相位匹配和特征匹配。其中特征匹配相对于另两类 方法，具有计算量小、速度快、鲁棒性高等优点，是应用较多的一种方法。 特征匹配首先对图像进行预处理来提取其高层次的特征，然后建立两幅图像 之间特征的匹配关系，通常使用的特征基元有点特征、边缘特征和区域特征， 其中点特征是另外两种特征的基础，应用最为广泛。 点模式匹配是点特征匹配中抽象出来的一种更为基本的问题，主要任务是将 满足一定几何变换关系的点集中的点匹配成对，是计算机视觉和模式识别领域中 重要的基础性问题，也是目前各相关领域关注和研究的热点。 点模式匹配的研究成果可以广泛地应用于计算机视觉、图像处理、计算化学、 天文学等众多领域，例如： 在计算机视觉方面，基于模板的目标识别是一个热点问题，在处理该问题的 过程中，视觉目标常常被视为一个空间分布的离散点集，在视觉场景中寻找目标 实际上就是处理一个点模式匹配问题； 在图像处理方面，经常需要对同一场景在不同情形下获取的两幅图像进行配 准，为了较好地对准两幅图像，配准的过程中必须寻找出两幅图像中相关点之间 的对应关系，然后根据对应关系估算两幅图像之间的变换参数，从而完成图像的 配准工作； 在计算化学方面，特别是药效团的检测的工作，可以认为是一种点集的匹配， 即利用已知药效团作为模板，在分子结构中检测是否存在与模板相匹配的子结 构； 在天文学方面，常常通过将每颗星的质心或中心作为一个点来研究两个星系 之间的匹配关系，该过程主要是通过点模式匹配来判断两个星系之间的相似性。 除了所述的以上几个方面，点模式匹配还在其它方面也有着广泛的应用，如 安徽大学博士学位论文 图模型在点模式匹配中的应用 数据融合、语音识别、机器人视觉的自动控制、运动检测、飞行器导航、姿态测 定等。 由于数据可能在不同光照强度、不同分辨率、不同尺度、不同光谱、不同时 相、不同角度等条件下采集的，同时也可能受到传感器在成像的过程中的畸变因 素的影响，待匹配点集间常存在着较大的差异，这使得点模式匹配成为了一个难 点问题，例如 c h a n g1 9 9 7 - l 、同一场景的两幅图像可能通过不同的传感器从不同的视角，或者通过同 一传感器在不同的时间采集所得。因此，两个点集之间可能存在着平移、旋转以 及缩放变换，甚至可能存在着复杂的非线性变换。大部分情况下，这些变换的几 何参数是不知道的，只有寻找到点之间的对应关系，才可能利用一些技术方法( 如 最小二乘法、t p s 变形模型等) 来估算出这些变换参数； 2 、点在获取的过程中可能会存在着位置上的局部微小扰动或噪声。两个点 集中相对应的点有可能并不是严格意义上的对应点，这就增加了匹配关系的搜索 难度，需要一种近似的点模式匹配技术在进行匹配关系的搜索时考虑到噪声的区 域范围； 3 、两个点集中的点的数目可能不同。在对两幅图像进行特征提取的时，可 能会出现一些出格点，导致了点集中的点并不是严格的二一对应，在很大程度上 增加了匹配关系的求解难度，使得问题的可能解的数量大大增加； 4 、点集间的变换参数的估计往往需要求解复杂的高维模型，这给算法的设 计带来了极大的难度，而且算法本身的复杂度也很难降低。 综上所述，点模式匹配具有非常广泛的应用范围，是众多相关理论研究的 基础，但点模式匹配问题自身的复杂性给算法的设计带来了巨大的困难，使 得现有算法都具有一定的局限。因此，对点模式匹配问题展开研究，寻找具有 高精度、高鲁棒性、低运算量的算法具有一定的理论意义和实际应用价值。 1 2 点模式匹配的研究现状 近年来，国内外学者对点模式匹配问题进行了大量的研究，提出了许多种方 法，但各种方法所依据的技术思想不尽相同【谭2 0 0 8 ，主要可以分为以下几类： 2 安徽大学博士学位论文 第一章绪论 1 2 1 基于不变特征描述的匹配方法 采用不变特征描述来实现匹配主要是利用点集在某些变换下的保持不变的 性质来对点进行描述，特征描述不仅需要有较强的辨别能力，还需要有较强的稳 定性。强辨别能力使得不同点的特征描述能够被很好地区分，而高稳定性使得同 一点在不同变换下均能够进行可靠地匹配，但通常情况下很难满足这样的要求， 学者们也从不同的角度进行了尝试，如h o p c o r 等 h o p c o f t1 9 9 2 利用了仿射变换 中面积比这一仿射不变量进行点模式匹配：t a u b i n 等 t a u b i n1 9 9 2 使用了二阶矩 不变量来实现点模式匹配；t u y t e l a a r s 等 t u y t e l a a r s2 0 0 4 通过寻找仿射不变区域 ( a f f m ci n v a r i a n tr e g i o n ) 来处理匹配问题；s h i n 等 s h i n2 0 1 0 贝l j 使用局部仿射不 变区域的几何性质来提高匹配算法的鲁棒性；h u 矩 r o s s2 0 0 1 ；孙2 0 0 5 】在处理 点模式匹配问题方面也是一个常用的仿射不变量；p 2 不变量则可以用于求解透 视变换下，点数不等的两个平面点模式匹配问题【张2 0 0 0 i 张立华等 张2 0 0 2 雪i i j 利用计算几何的理论，通过寻找两个待匹配点集的凸壳，分别进行凸壳匹配和内 点匹配，从而实现在透视变换下的点集匹配问题；徐斌等 徐2 0 0 2 利用由多个曲 面微分不变量组成的灰度差分不变量( g r a y - v a l u ed i f f e r e n t i a li n v a r i a n t s ) 来进行 特征点匹配。 由于点模式匹配问题的难度与复杂性，单纯依靠不变量特征并不能够在所有 情形( 如噪声、位置扰动以及各种线性与非线性的变换) 下都有很好的表现，因 此，学者们通常采用限制匹配问题的条件或将不变量特征描述方法与其它方法相 结合的方式来提高算法的性能，如文献 张2 0 0 0 需要在待匹配的两个点模式中有 三对点整体对应已知的前提下进行匹配；邵泽明等【邵2 0 0 8 利用r s t c 不变特 征量来作为匹配相似度的衡量尺度，再结合r a n s a c 鲁棒估计以及外极线约束 进行引导匹配，获得了较好的匹配结果等。 1 2 2 基于图模型的匹配方法 点模式匹配问题在计算机视觉领域中经常被作为一个图匹配问题来处理 【c a e t a n o2 0 0 4 。通过以点集中点作为顶点，顶点之间按照一定的规则条件设定 边来构造图( g r a p h ) ，可以反映点之间的相互关系，是一种非常重要而有效的结 构特征信息的表示方式。图匹配( g r a p hm a t c h i n g ) 的任务是寻找满足一定约束 3 安徽大学博士学位论文图模型在点模式匹配中的应用 条件下的两个图的顶点之间以及边之间的对应关系，确保将一个图或图中的子结 构映射到另一个图或图中的与其相似的子结构。在过去的3 0 多年的时间里，学 者们对图匹配问题做了大量的研究 c o m e2 0 0 4 ，按照匹配的要求与效果，可以 将以图模型为基础的点模式匹配算法分为2 类 c o m e2 0 0 4 ：精确图匹配( e x a c t g r a p hm a t c h i n g ) 和非精确图匹配( i n e x a c tg r a p hm a t c h i n g ) 。 ( 1 ) 精确图匹配 精确的图匹配要求：在待匹配的两个图a 和b 中，若图a 的两个顶点由一 条边连接，则图b 中与其匹配的两个顶点也必须由一条边相连。若反过来也成 立，则对两个图的结构要求最高，此时精确匹配就是图同构，