基于马氏距离谱特征的图像匹配算法*

鲍文霞 余国芬 胡根生 朱明

(1.安徽大学 计算智能与信号处理教育部重点实验室， 安徽 合肥 230039；2.偏振光成像探测技术安徽省重点实验室， 安徽 合肥 230031)

图像匹配是计算机视觉和模式识别中的基本问题，其中点模式匹配作为图像配准系统中最重要的环节，一直以来都是研究的重心.为了获取精确和有效的匹配点对，近年来谱图理论[1- 6]作为一种高效的数学描述工具被广泛地应用于图像的点模式匹配问题中.例如Leordeanu等[7]结合匹配约束条件和成对集合约束条件构造刻画特征点集全局结构性质的亲近矩阵，通过对亲近矩阵进行谱分解，利用主特征向量的相关性获得特征点的匹配关系；Yuan等[8]在文献[7]的基础上提出权重投票策略，提高了谱匹配算法的速度；Kang等[9]提出一种近似谱匹配算法，对构造的无向图定义亲近矩阵，然后通过对亲近矩阵进行谱分解，将获取的特征向量用来实现匹配；Tang等[10]通过对构造的 Laplace矩阵进行谱分解，将得到的特征向量用作谱匹配代价，利用松弛迭代的方法求得匹配关系.以上基于谱方法的图像匹配算法主要是利用结构图描述图像的全局特征，通过分析图对应亲近矩阵或Laplace矩阵的特征向量来获取节点之间的匹配关系.而当待匹配图像之间存在较大形变或存在出格点时，全局特征稳定性较差；同时当特征点集之间的大小不同时，图结构的差异较大，从而大大降低了特征向量之间的相似性，导致匹配精度下降[11].因此，Tang等[12]利用特征点之间的局部关系构造矩阵，给出了一种局部谱特征描述用于图像的匹配，该算法对特征点位置抖动和出格点具有一定的鲁棒性；朱明等[13]通过构造线图并计算其邻接矩阵，将邻接矩阵进行分解得到的特征值用于描述谱特征，该算法提高了当特征点集大小不一样时的图像匹配精度.Yan等[14]利用有向图上无符号Laplace矩阵的谱特征构造单调亮度不变特征描述子,从理论上证明了谱特征描述子是能够解决图像单调亮度变化和许多图像几何变换的，同时实验也证明了该描述子在图像模糊、视角变化、亮度变化和JPEG压缩等图像变换下优于传统的SIFT描述子.

上述基于谱特征的图像匹配算法在矩阵的构造过程中都采用的是欧式距离进行度量.而欧式距离将输入特征点样本空间看成是各向同性的，然而各向同性假设在众多实际应用中不成立，它不能公平地反映数据样本维度分量之间的潜在关系，因此，Hu等[15]将马氏距离应用到SURF(Speed up Robust Features)算法中来剔除初始误匹配，并将最小二乘法和RANSAC算法(随机抽样一致性算法)相结合得到单应矩阵和位置信息来完成匹配，从而提高匹配精度.为了进一步提高谱匹配算法的精度，文中提出了一种基于马氏距离谱特征的图像匹配算法，该算法利用特征点及其周围子特征点集之间的关系构造局部结构图，代替传统谱特征中的全局结构图；采用马氏距离对其矩阵进行度量，将矩阵谱分解得到的特征值构成的向量代替传统谱特征中的特征向量来构造马氏距离谱特征，然后用贪心算法求解匹配问题；最后为了获取高精度的匹配特征点对，算法给出了利用SVM[16]剔除误匹配对的方法.

1 马氏距离谱特征

1.1 马氏距离

对于由m个样本构成的样本空间X={xz:1≤z≤m}⊂Rn，其内一样本点xz到样本均值uX的马氏距离为

(1)

其中，CX是样本空间X的协方差矩阵，CX、uX的计算公式如下:

(2)

(3)

1.2 马氏距离谱特征

图像中任意一个特征点u的特征属性可以由该特征点及其周围的特征点之间的局部关系来进行描述.假设I和J是两幅待匹配的图像，图像I中有S个特征点，记为点集P={u1,u2,…，uS}，图像J中有S′个特征点，记为点集Q={v1,v2,…，vS′}.

点集P内任一特征点ui到其余特征点ui′的平均最小马氏距离du为

(4)

(5)

其中，i≠i′,CP是点集P的协方差矩阵.

定义半径集Ru={rα|rα=αdu,α=1,2,…，5}，对于任一个rα∈Ru，在点集P上选择到特征点ui的马氏距离小于rα的点构成子点集Ωiα，即Ωiα={uk:uk∈P且dM(ui,uk)

(6)

其中:uk,ul∈Ωiα；βP是常数因子，用来控制特征点之间的角度或相互之间的作用.

Hiα是一个对称的、半正定的矩阵，因此对Hiα进行谱分解得到：

Hiα=UiαΔiαUiαT

(7)

其中:Δiα=diag(|λiα1|,|λiα2|,…，|λiα|Ωiα||),其对角元素是Hiα特征值绝对值的降序排列；Uiα={Uiα1,Uiα2,…，Uiα|Ωiα|}是|Ωiα|×|Ωiα|的正交矩阵.

将Δiα的对角元素排列成一个向量Aiα=(|λiα1|,|λiα2|,…，|λiα|Ωiα||)，于是特征向量组Aiα(α=1,2,…，5)定义为特征点ui的马氏距离谱特征，构建过程如图1所示.

1.3 马氏距离谱特征的不变性

马氏距离谱特征的性质主要有：

(1)平移不变性.由于马氏距离谱特征在构造过程中采用的是特征点之间的相对距离，而平移并不会改变特征点之间的相对距离，所以马氏距离谱特征具有平移不变性.

(2)尺度不变性.构造马氏距离谱特征时用每个点集的平均最小距离作为距离度量，因此所选择的子点集是尺度不变的，此时可通过设置βQ=βPdv/du使马氏距离谱特征对尺度具有不变性.其中βP、βQ分别为点集P、Q中的对应子点集构造关联邻接矩阵时的常数因子，du、dv分别为点集P、Q中最小平均马氏距离.

(3)旋转不变性.马氏距离谱特征是在半径集中选取子点集来构造的，当发生旋转时，每次所选的子点集保持不变，只是在构造邻接矩阵时的访问顺序改变了，因此可以通过证明马氏距离谱特征的置换不变性来证明其旋转不变性.假设H′=VHVT是点集中特征点排列顺序变化后的邻接矩阵，将H=UΔUT用来替换H′=VHVT中的H得到:

Hiα=0h1,2h1,3…h1,Ωiα-1h1,Ωiαh2,10h2,3…h2,Ωiα-1h2,Ωiαh3,1h3,20…h3,Ωiα-1h3,Ωiα︙︙︙︙︙hΩiα-1,1hΩiα-1,2hΩiα-1,3…0hΩiα-1,ΩiαhΩiα,1hΩiα,2hΩiα,3…hΩiα,Ωiα-10éëêêêêêêêêùûúúúúúúúúSVD分解Ai1=(λ1Hi1,…,λΩi1Hi1)︙ Ai5=(λ1Hi5,…,λΩi5Hi5)将特征值对角元素排列成向量Hi1=Ui1λ1Hi1⋱λΩi1Hi1)éëêêêùûúúúUTi1︙ Hi5=Ui5λ1Hi5⋱λΩi5Hi5)éëêêêùûúúúUTi5

图1 马氏距离谱特征构建过程
Fig.1 Mahalanobis distance spectral construction process

H′=VUΔUTVT=(VU)Δ(VU)T

(8)

其中,V为H′的置换矩阵，Δ的对角元素是H′的特征值降序排列,U为H矩阵特征值向量对应的特征向量矩阵.由于H′是实对称矩阵，所以其奇异值分解是唯一的，而矩阵的谱分解具有置换不变性，所以马氏距离谱特征对旋转具有不变性.

2 图像匹配

2.1 特征匹配

设特征点ui和vj的马氏距离谱特征分别为Aiα和Bjα，则匹配关系矩阵M的对角元素定义为Aiα和Bjα之间的相似性约束：

(9)

其中,γ是常数因子，Aiα和Bjα在计算过程中可能由于所选子点集的点数不同，会导致向量长度不一致.当遇到这种情况时，在长度较短的向量后面直接补零使其长度一致.

匹配矩阵M的非对角元素Mij,i′j′由如下的公式计算得到：

Mij,i′j′=exp(-‖pii′-qjj′‖2/(2γ2))

(10)

pii′和qjj′分别表示点集P和点集Q中特征点两两之间的马氏距离,计算公式如下所示：

(11)

(12)

因此，特征点集P和Q之间的匹配问题可以用匹配的通用数学模型来描述[17- 18]，即

(13)

其中,x是二进制分配矩阵X∈{0,1}S×S′的列向量表达形式，当图像I中特征点ui和图像J中特征点vj匹配时，二进制分配矩阵X中的第i行第j列元素为1，否则为0.求解匹配问题转换为求解分配向量x*使式(13)中目标函数最大化.

文中采用贪心算法[8]求解该匹配的数学模型，从而得到匹配结果.

2.2 误匹配的剔除

为了进一步提高基于马氏距离谱特征匹配的精度，在文中提出的马氏距离谱特征匹配算法的基础上，利用SVM剔除误匹配点对.首先，利用马氏距离谱特征匹配结果建立训练集，而训练样本集由样本点的特征向量和样本点所属的分类标签来表示，因此，样本点采用匹配后的匹配对(ui,vj)表示，其对应的马氏距离谱特征分别为Aiα和Bjα，样本点的特征向量用马氏距离谱特征向量组的差值之和表示：

(14)

分类标签由是否为正确匹配来判断:当匹配对(ui,vj)是正确匹配时，分类标签为1;反之为错误匹配时，分类标签为-1.即

接着，将建立的训练样本集输入到SVM分类器中，通过学习得到一个二分类模型.

最后，将匹配对(ui′,vj′)输入到分类模型中，根据分类结果得到精确匹配结果，从而剔除误匹配点对.

2.3 算法流程

综上所述，基于马氏距离谱特征的图像匹配算法首先是在待匹配图像中提取特征点，计算马氏距离谱特征描述；接着，根据马氏距离谱特征之间的相似性构造匹配矩阵，利用匹配的通用数学模型并采用贪心算法求解得到匹配结果；最后，借助SVM剔除误匹配对，从而获得精确匹配.

3 实验结果与分析

3.1 基于马氏距离谱特征匹配的实验结果与分析

首先，为了验证文中给出的马氏距离谱特征描述的性能，采用CMU/VASC图像数据库中的序列图像做了大量实验，下面给出部分实验结果.以house图像序列的第0、20、25、30、35、40、50、60、70、80帧为例，为了便于验证匹配的精度，在每帧图像上分别提取40个特征点，分别用SPCM[12]和文中提出的算法(MDSM算法)对特征点进行描述，采用相同的匹配数学模型以及贪心算法将其余帧分别与第0帧进行匹配.实验结果如图2和表1所示.其中图2(a)、2(b)、2(c)分别表示两种算法第0帧与第25、35、40帧图像匹配结果，表1给出了具体的匹配数据.从实验数据可以看出，文中的马氏距离谱特征描述具有更高的匹配精度，在帧差数不大于35帧的情况下一直保持100%.

图2 图像匹配实验结果Fig.2 Experimental results of image matching

图像MDSM算法SPCM算法正确点个数正确率/%正确点个数正确率/%第0、20帧40100.03690.0第0、25帧40100.03485.0第0、30帧40100.03485.0第0、35帧40100.03177.5第0、40帧3587.52050.0第0、50帧2870.01947.5第0、60帧2255.01640.0第0、70帧1742.51332.5第0、80帧1332.5820.0

其次，用graffiti6图像集存在较大形变的两幅图像进行匹配算法的对比实验，在每幅图像中提取40个特征点，分别用文中提出的MDSM算法和SPCM算法、SMT算法[5]、SM算法[7]进行匹配，实验结果如图3所示，匹配的具体数据如表2所示.由表2可见，文中提出的MDSM算法的匹配精度最高，SPCM算法的匹配精度次之，SM算法和SMT的匹配精度较低.

3.2 剔除误匹配实验结果与分析

随着帧差的增加误匹配点对增加，因此，文中利用SVM方法剔除帧差较大时的误匹配点对，从而获取精确匹配.下面给出部分实验结果，取CMU/VASC图像数据库中house图像序列的第0、40、50、60、70、80帧图像，先利用文中的MDSM算法进行匹配，然后分别用SVM方法和RANSAC[19]算法剔除误匹配点对.实验结果如图4所示，其中图4(a)、4(b)、4(c)分别表示第0帧与第40、60、80帧的误匹配剔除实验结果，表3给出了具体的误匹配剔除实验数据.结合表1 和表3的数据分析得到，文中提出的基于SVM学习的误匹配剔除算法进一步提高了MDSM算法的匹配精度；从表3的实验数据可以得到，RANSAC误匹配剔除算法的正确率有时高于SVM误匹配剔除算法，但其正确匹配的点数较少，并且将大多数的正确匹配对当成错误匹配对剔除，误剔除率较高；而文中提出的SVM误匹配剔除算法将大多数的误匹配剔除且误剔除率较低.其中，正确率=正确匹配点个数/总匹配点个数；误剔除率=剔除的正确匹个配点数/总剔除点个数.

3.3 鲁棒性实验结果与分析

为了验证文中基于马氏距离谱特征的图像匹配算法在存在出格点的情况下的鲁棒性，取第0、40帧图像进行实验.首先在每帧图像上提取40个特征点并进行匹配实验；然后，在第40帧图像上依次添加10、20、30、40、50、60、70、80个出格点后与第0帧进行匹配，并将MDSM算法与SPCM算法、SMT算法、SM算法进行比较，实验结果如图5所示.分析图5可以得到，文中提出的MDSM算法在含有较多出格点的情况下仍然能够保持较高的匹配精度，鲁棒性较高；SPCM算法、SMT算法和SM算法在含有出格点的情况下匹配精度明显下降，并且在出格点数达到80个时，正确匹配率低于20%.

图3 graffiti6图像的匹配实验结果Fig.3 Results of graffiti6 image matching experiment

指标MDSM算法SPCM算法SMT算法SM算法正确点个数38342525正确率/%95.085.062.562.5

图4 图像误匹配剔除实验结果Fig.4 Experimental results of eliminate the false match

图像SVM误匹配剔除算法RANSAC误匹配剔除算法正确匹配点个数总匹配点个数正确率/%误剔除率/%正确匹配点个数总匹配点个数正确率/%误剔除率/%第0、40帧343694.425.01111100.082.8第0、50帧222781.546.281080.066.7第0、60帧182281.822.281080.046.7第0、70帧152462.512.56966.736.7第0、80帧101566.712.06875.021.9

图5 出格点对匹配结果的影响Fig.5 Effect of outliers on matching

4 结语

文中提出了一种基于马氏距离谱特征的图像匹配算法.该算法利用特征点之间的局部信息以及马氏距离度量构造结构图，并将对应矩阵的特征值用于描述特征点的属性；对匹配结果利用SVM方法进行误匹配剔除，从而进一步提高匹配精度.实验结果验证了算法的有效性和鲁棒性.然而，采用马氏度量的谱匹配算法虽然提高了匹配精度，但马氏度量线性变换的局限性导致它不能描述样本潜在的非线性关系，限制了其实际应用的范围.今后的工作是寻找一种能够描述样本非线性关系的距离度量，进而拓宽基于谱特征的图像匹配算法的应用.

[1] FAN R K C.Spectral graph theory [M].Washington D C:American Mathematical Society,1997:212.

[2] SHAPIRO L S,BRADY J M.Feature-based correspondence:an eigenvector approach [J].Image Vision Computing,1992,10(5):283- 288.

[3] CARCASSONI M,HANCOCK E R.Spectral correspondence for point pattern matching [J].Pattern Recognition,2003,36(1):193- 204.

[4] SILLETTI A,ABATE A,AXELROD J D,et al.Versatile spectral methods for point set matching [J].Pattern Re-cognition Letters,2011,32(5):731- 739.

[5] FENG Wei,LIU Zhi-qiang,WAN Liang,et al.A spectral-multiplicity-tolerant approach to robust graph matching [J].Pattern Recognition,2013,46(10):2819- 2829.

[6] YANG Xu,QIAO Hong,LIU Zhi-yong.Feature correspondence based on directed structural model matching [J].Image and Visio Computing,2015,33(C):57- 67.

[7] LEORDEANU M,HEBERT M.A spectral technique for correspondence problems using pairwise constraints [C]∥Proceedings of International Conference on Computer Vision.Beijing:IEEE,2005:1482- 1489.

[8] YUAN Yuan,PANG Yan-wei,WANG Kong-qiao,et al.Efficient image matching using weighted voting [J].Pattern Recognition Letters,2012,33(4):471- 475.

[9] KANG U,HEBERT M,PARK S.Fast and scalable approximate spectral graph matching for correspondence problems [J].Information Sciences,2013,220(1):306- 318.

[10] 唐俊,黄煌,梁栋,等.一种结合几何相容性分析的谱匹配算法 [J].光学学报,2012,32(7):0715001.

TANG Jun,HUANG Huang,LIANG Dong,et al.Spectral correspondence for point pattern matching combined with analysis of geometric consistency [J].Acta Optica Sinica,2012,32(7):0715001.

[11] ABREU N M M,CARDOSO D M,MARTINS E A,et al.On the Laplacian and signless Laplacian spectrum of a graph with k pairwise co-neighbor vertices [J].Linear Algebra and Its Applications,2012,437(9):2308- 2316.

[12] TANG Jun,SHAO Ling,ZHEN Xian-tong.Robust point pattern matching based on spectral context [J].Pattern Recognition,2014,47(3):1469- 1484.

[13] 朱明,梁栋,范益政,等.基于谱特征的图像匹配算法 [J].华南理工大学学报(自然科学版),2015,43(9):60- 66.

ZHU Ming,LIANG Dong,FAN Yi-zheng,et al.Image matching algorithm based on spectral feature [J].Journal of South China University of Technology(Natural Science Edition),2015,43(9):60- 66.

[14] YAN Pu,LIANG Dong,TANG Jun,et al.Local feature descriptor invariant to monotonic illumination changes [J].Journal of Electronic Imaging,2016,25(1):013023.

[15] HU Yong-hao,LI Bang-jun,SHI Li-ping.The remote sensing image matching based on SURF algorithm [C]∥Proceedings of the Photoelectronic Technology Committee Conferences.Tianjin:International Society for Optics and Photonics,2014:91421T.

[16] CORTES C,VAPNIK V.Support-vector networks [J].Machine Learning,1995,20(3):273- 297.

[17] ZHOU F,TORRE F D L.Deformable graph matching [C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Portland:IEEE,2013:2922- 2929.

[18] MINSU C,JIAN S,OLIVIER D,et al.Finding matches in a haystack:a max-pooling strategy for graph matching in the presence of outliers [C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Columbus:IEEE,2014:2091- 2098.

[19] FISCHLER M A,BOLLES R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography [J].Communications of the ACM,1981,24(6):381- 395.