0 引 言

1 研究方法

1.1 SURF算法的初始匹配

1.2 基于多约束条件的匹配方法

使用NNDR最近邻比率策略以及RANSAC随机采样一致方法，可以对上述获得的SURF特征匹配集进行过滤，得到优质的匹配集合^[21]。NNDR策略的原理^[22]是比较最近邻和次近邻的距离比率，即

${\rm{NNDR}} = \frac{{\left| {{D_A} - {D_B}} \right|}}{{\left| {{D_A} - {D_C}} \right|}} = \frac{{{d_1}}}{{{d_2}}}$

(4)

式中，D_A是一个视角中的目标描述子；D_B和D_C是另一个视角中的与它最近的两个候选匹配点；d₁和d₂是基于描述子间最近邻距离和次近邻距离的两个值。如果测量距离的最优值d₁非常低，而次优值d₂要大许多，即d₁与d₂的比值很小，可以认为D_B是最佳的匹配点。如果两个候选者D_B和D_C很接近，即d₁与d₂的比值接近1.0，由于不确定正确的匹配是哪一个，那么两个匹配都会被拒绝。

接下来使用对称性测试和RANSAC方法来获得最终的匹配集合。1981年由Fischler和Bolles^[23]最先提出RANSAC算法。RANSAC算法的目的是从包含异常值的数据集中估算出给定的数学元素。RANSAC用来过滤错误匹配并估算基础矩阵，其随机地在完整匹配集中挑选7个匹配计算基础矩阵。一旦得到基础矩阵，集合中剩下来的匹配集，用来计算内点数目，该数目越多说明基础矩阵越可靠。这里的内点指的是，在预测对应匹配点位置ε以内的匹配点。随机地对所述过程重复k次，最后含有最多内点的样本集被作为最终的解(正确匹配集合)。

如图 1所示，对于一对待匹配图像(左图和右图)，使用上述约束条件执行特征匹配算法的步骤如下：

1) 检测和描述两幅图像的SURF特征；

2) 根据最近邻匹配策略的原理，对描述子进行双向匹配；

3) NNDR约束，计算最优匹配与次优匹配的距离比值，移除距离比率大于给定阈值的匹配(阈值设为0.5)；

4) 对称性测试，正确的匹配满足一一对称性，剔除不对称的匹配集合；

5) 使用RANSAC算法获得最大匹配支持集合，即为最终的输出匹配集合。

图 1 多约束条件的特征匹配

Fig. 1 Feature matching with multiple constraints

基于多约束条件的方法，通过引入NNDR策略以及对称性策略剔除掉大量错误匹配，再使用RANSAC算法得到质优的特征匹配集合。

1.3 极线约束原理

图 2是极线约束的原理图。观察场景点的两个相机中心C₀和C₁追踪连接空间3维点X到相机中心的直线，可以找到空间点X在一幅图像中的点p(x,y)。相反，通过该点p可以找到在另一幅图像中的对应点q。沿着这条直线在另一个图像面进行搜索，直线在另一个图像面形成了一条虚构的直线l，此直线被称为点p的极线(epipolar)。该极线的一个端点以原始观察线上的无穷远处的投影为界，另一个端点以原摄像机中心在第2个图像面的投影为界，即是极点e(epipole)。基础矩阵F将一个视角中的2维图像点p映射到另一个视角中的极线上，用表达式表示为

$l' = \left[ {\begin{array}{*{20}{c}} {l{'_1}}\\ {l{'_2}}\\ {l{'_3}} \end{array}} \right] = F\left[ {\begin{array}{*{20}{c}} x\\ y\\ 1 \end{array}} \right]$

(5)

因此图像点p(x,y)的匹配点q(x′,y′)在对应图像上应满足方程

$l{'_1}x' + l{'_2}y' + l{'_3} = 0$

(6)

图 2 极线约束的原理图

Fig. 2 Schematic draw of epipolar constraint

1.4 引入极线约束条件获得优质匹配

基于多约束策略过滤错误匹配的过程，获得的正确匹配数很少，且比率阈值很难设置。阈值设置的太低会导致较多的错误匹配被保留，而阈值设置太高会导致很多正确的匹配被过滤掉。同时锁紧NNDR和RANSAC算法的参数，可以得到优质的特征匹配集，但是匹配数量极少。在此基础上，为了得到数目多而又优质的匹配，利用极线几何原理，引入极线约束条件，从而获得特征匹配的方法。

基于极线约束条件的特征匹配算法流程图如图 3所示，实现的具体步骤如下：

1) 读取待匹配两幅图像，获得计算F的RANSAC算法的输入匹配集合。

(1) SURF检测和描述两幅图像上的特征点；

(2) 检查每幅图像上的特征点数，限制特征点数在1 200个以内；

(3) 使用匹配器对所有特征点的描述子进行双向匹配，得到两个匹配集合；

(4) 分别对匹配集合进行NNDR距离比率测试，剔除一些匹配对，比率阈值设为0.50；

(5) 利用特征点匹配对的唯一性原则，对两个匹配集合进行对称性测试，返回对称的匹配集合。

图 3 基于极线约束的特征匹配

Fig. 3 Feature matching based on epipolar constraint

2) 使用RANSAC算法计算基础矩阵，计算出具有最大匹配支持集合的基础矩阵，返回此基础矩阵F。

文献[24]中指出RANSAC方法被实践证明是计算基础矩阵F的一种非常有效的鲁棒性方法，因此使用RANSAC方法自动估计F。其步骤如下：

(1) 当前抽样7个点对应，计算F和支持它的一致点集S(F)；

(2) 如果当前的一致点集大于原先一致集，则保持当前的S(F)和相应的基础矩阵F，并删除原始一致集和基础矩阵；

(3) 自适应算法终止抽样，获得最大一致集S(F)，即内点；

(4) 用最大一致集重新计算出基础矩阵F。

3) 对于待匹配的两幅图像，根据SURF描述子内容进行双向最佳匹配，得到两个匹配集合。

4) 对称性测试，根据图像特征点匹配的唯一性原则，两个匹配集合中的索引值相互对称时保留此匹配集合，不对称时剔除此匹配集合，返回对称性的匹配集合。

5) 使用基础矩阵F，分别计算两幅图像上的每一个特征点在对应图像上的极线。

6) 对匹配集合进行极线约束测试，返回通过极线约束测试的匹配集合。

极线方程(式6)变换得到的极线函数为

$f\left( x \right) = l{'_1}x' + l{'_2}y' + l{'_3}$

(7)

式中，l₁′、l₂′、l₃′通过基础矩阵F(式(5))计算得到。将匹配点代入f(x)，得到的函数值可以用来判断匹配的准确性。具体步骤为：

(1) 取出匹配集合中参考索引对应的左图上的匹配点，取出匹配集合中训练索引对应的右图上的匹配点；

(2) 使用极线函数(式(7))，将左图上的匹配点带入右图特征点的极线函数，计算其函数值。将右图上的匹配点带入左图特征点的极线函数，计算其函数值；

(3) 比较左图和右图上的极线函数值，函数值取正后同时为0的匹配保留，即，匹配点在对应各自的极线上的匹配才能保留，否则剔除。

7) 对于通过极线约束的匹配集合，剔除不满足式(8)而在同一条极线上匹配点交叉的匹配点对，返回最终的优质匹配集合。

同一条极线上的匹配点出现交叉现象时，就表示其匹配错误，如图 4所示。存在两对匹配(k₁,k′₁)和(k₂,k′₂)，其中k₁、k₂在左图的一条极线上，k′₁和k′₂在右图的一条极线上。它们在图像上的坐标用(x,y)表示，多数情况下，如果同一条极线上的点k₁在k₂上方，那么对应图像上的匹配点k′₁也应在k′₂的上方。用公式判断同一条极线上的匹配点交叉的情况可以表示为

${\mathop{\rm sgn}} \left( {{k_1} - {k_2}} \right) \equiv {\mathop{\rm sgn}} \left( {k{'_1} - k{'_2}} \right)$

(8)

至此，完成了利用极线约束条件获取图像优质特征匹配的处理过程。

图 4 同一条极线上的交叉匹配对

Fig. 4 A pair of crossed matches with a pole epipolar

2 算法测试及结果分析

2.1 匹配结果比较

为了验证本文算法的普适性，结合上述的3个阈值输入参数，使用不同种类的图像对多约束条件的特征匹配方法(旧方法)和本文提出的基于极线约束条件的特征匹配算法(新方法)进行验证和比较。

图 5是选择其中5组图像数据的特征匹配结果图。每一条白色的线表示一对优秀匹配。图 5(a)(b)分别表示旧方法和新方法得到的特征匹配结果图。从匹配的结果图能够看出，图 5(a)中的特征匹配数明显少于图 5(b)的特征匹配数。并且通过算法验证，新方法完全包含了旧方法得到的特征匹配对，是正确的匹配。新方法保证质量的同时，获得了比旧方法更多的匹配数。

图 5 不同算法的特征匹配结果

Fig. 5 Feature matching results of different algorithms ((a) the old algorithm; (b) the new algorithm)

9组匹配结果数据用表 1列出。由表 1可知，Church图像的匹配结果中，旧方法获得的优质匹配数量为15个，新方法为98个，新方法获得的优质匹配数量是原方法的6.6倍。新方法包含旧方法的优质匹配数的为15个，说明新方法完全包含旧方法的优质匹配。新方法中，极线上存在的互交叉的错误匹配在parliament数据中有4个，剔除之后得到的优质匹配数为189个，是原方法的2.1倍。Circlebuild图像匹配结果中，新方法获得的优质匹配数量是旧方法的8.1倍。9组数据中新方法的优质匹配数目比旧方法增加28倍。

表 1 新算法与旧算法匹配数量的比较
Table 1 Comparison of matches’ number on old and new algorithm

下载CSV

/对
图像	旧方法	新方法
	优质匹配数目	优质匹配数目	包含旧算法的匹配数目	极线上存在交叉的错误匹配数目
Flower	7	19	7	0
Canal	7	43	7	0
Circlebuild	7	57	7	0
Monument	14	30	14	0
Church	15	98	15	0
Office	23	66	23	0
Parliament	88	189	88	4
Art	90	176	90	13
Teddy	197	308	197	29

为了进一步表明新方法的优越效果，画出了新方法和旧方法得到的特征点匹配集数目的柱状图，如图 6所示。由柱状图可以更加直观的看出，对于任意一组图像数据，新方法的匹配数都要比旧方法多出2倍以上。选择的图像包括：个体对象、室内场景、室外场景，它们都获得了大幅度改进，足以说明新方法的普适性。

图 6 新方法和旧方法匹配数目的柱状图比较

Fig. 6 Histogram comparison on the number of matches by using old and new algorithm

2.2 运行时间比较

算法运行时间不仅受计算机的硬件性能所限，更重要的是算法的影响。因此，比较和讨论了在加入极线约束算法前后的时间消耗。由于程序每次执行时间都有所偏差，这里对每组图像数据的其中一次运行时间作为比较。表 2列出了新算法运行时间。其T_F、T_add和T_sum分别表示计算基础矩阵的时间、得到基础矩阵之后再使用极线约束的时间、总的时间。由表 2可知，本文的总时间消耗几乎都在计算基础矩阵中，而使用的极线约束阶段消耗很小。总时间消耗基本控制在毫秒范围内。因此可以认为，本文的基于极线约束的SURF特征匹配算法运算简单、处理速度快。

表 2 基于极限约束的算法执行时间
Table 2 The time of epipolar constraint algorithm

下载CSV

/ms
图像	TF	Tadd	Tsum
Flower	0.038	0.006	0.044
Canal	0.063	0.006	0.069
Circlebuild	0.158	0.019	0.177
Monument	0.063	0.006	0.069
Church	0.133	0.032	0.165
Office	0.152	0.006	0.158
Parliament	0.057	0.006	0.063
Art	0.353	0.025	0.378
Teddy	0.069	0.006	0.075

实验结果表明，提出的新型基于极线约束条件的图像特征匹配方法具有与如下优点：

1) 准确度高、数量更多；

2) 完全包含原有方法的优质匹配集合；

3) 运算简单，处理速度快。

2.3 极线约束条件探讨

采用新方法进行特征匹配时，有一个判断匹配保留的条件，即：匹配点必须在极线上的匹配才能得到保留。为了验证这一条件，在算法中添加了一个参数ε设置，用于极线约束过程中判断当前的匹配保留要满足的条件，即当前特征点p的匹配点q在其极线位置的ε(0,1,2)个像素范围内找到。对得到的特征匹配数进行比较，数据结果显示如表 3。表 3中ε=0表示新方法要求的条件，即只有极线上的匹配点得到保留。ε=1表示允许极线边缘一个像素范围内的匹配点得到保留，ε=2和ε=3同理。同时，对匹配结果中同一条极线上出现交叉的错误匹配进行比较，如表 4。

表 3 新方法中在极线位置ε个像素内找到匹配数目的比较
Table 3 Comparison on the number of matches found in ε pixels round of epipolar by using new algorithm

下载CSV

/对
图像	极线约束前输入的匹配数	极线约束后的匹配数
		ε=0	ε=1	ε=2
Church	424	99	121	137
Canal	214	23	57	62
Circlebuild	403	57	82	105
Monument	199	30	40	49
Parliament	331	189	225	235

表 4 极线位置ε个像素内出现交叉错误匹配数目的比较
Table 4 Comparison on the number of error cross-matches found in ε pixels round of epipolar

下载CSV

/对
图像	ε=0	ε=1	ε=2
Church	0	2	6
Canal	0	2	4
Circlebuild	0	3	4
Monument	0	2	2
Parliament	4	6	6

由表 3和表 4可知，随着ε的增加，新方法得到的特征匹配数是不断增加的，但是同时，极线上出现的错误匹配也开始增加。剔除这样的交叉错误匹配后，得出了Circlebuild图像的特征匹配结果图，当允许匹配点在极线边缘的12个像素范围内时，即使剔除了同一极线上相互交叉的错误匹配，匹配的结果还是出现了明显的错误。本文给出了ε=2时，错误匹配的情形，如图 7所示，错配部分以圆圈显示。

图 7 极线处2个像素范围内对Circlebuild的匹配

Fig. 7 Feature matching for Circlebuild in two pixels round of epipolar

因此，极线约束中，判断当前匹配对是否正确的条件是匹配点必须在极线上，即ε=0。

3 结 论

参考文献

[1] Guo Y, Bennamoun M, Sohel F, et al. 3D object recognition in cluttered scenes with local surface features: a survey[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(11): 2270–2287. [DOI:10.1109/TPAMI.2014.2316828]
[2] Abiantun R, Prabhu U, Savvides M. Sparse feature extraction for pose-tolerant face recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(10): 2061–2073. [DOI:10.1109/TPAMI.2014.2313124]
[3] Nebehay G, Pflugfelder R. TLM: Tracking-learning-matching of keypoints[C]//Proceedings of the 2013 Seventh International Conference on Distributed Smart Cameras. Palm Springs, CA: IEEE, 2013: 1-6. [DOI: 10.1109/ICDSC.2013.6778201]
[4] Guo Y, Sohel F, Bennamoun M, et al. An accurate and robust range image registration algorithm for 3D object modeling[J].IEEE Transactions on Multimedia,2014,16(5): 1377–1390. [DOI:10.1109/TMM.2014.2316145]
[5] Furukawa Y, Ponce J. Accurate, dense, and robust multiview stereopsis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(8): 1362–1376. [DOI:10.1109/TPAMI.2009.161]
[6] Brown M, Lowe D G. Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision,2007,74(1): 59–73. [DOI:10.1007/s11263-006-0002-3]
[7] Dai X L, Khorram S. The effects of image misregistration on the accuracy of remotely sensed change detection[J].IEEE Transactions on Geoscience and Remote Sensing,1998,36(5): 1566–1577. [DOI:10.1109/36.718860]
[8] Wang K P, Gui Y, Zhang X H, et al. Robust tracking method with drift correction[C]//Proceedings of 2010 International Conference on Image Analysis and Signal Processing. Zhejiang, China: IEEE, 2010: 403-406. [DOI: 10.1109/IASP.2010.5476089]
[9] Shen H, Li S M, Bo F C, et al. On road vehicles real-time detection and tracking using vision based approach[J].Acta Optica Sinica,2010,30(4): 1076–1083. [ 沈峘, 李舜酩, 柏方超, 等. 路面车辆实时检测与跟踪的视觉方法[J].光学学报,2010,30(4): 1076–1083.] [DOI:10.3788/aos20103004.1076]
[10] Richard S. Computer Vision Algorithm and Application[M]. Ai H Z, Xing J L, trans. Beijing: Tsinghua University Press, 2012: 157-179. [塞利斯基. 计算机视觉-算法与应用[M]. 艾海舟, 兴军亮, 译. 北京: 清华大学出版社, 2012: 157-179.]
[11] Lowe D G. Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2): 91–110. [DOI:10.1023/B:VISI.0000029664.99615.94]
[12] Bay H, Ess A, Tuytelaars T, et al. Speeded-up robust features (SURF)[J].Computer Vision and Image Understanding,2008,110(3): 346–359. [DOI:10.1016/j.cviu.2007.09.014]
[13] Hao Z C, Zhu M. Serial image registration based on multiple restriction matching algorithm[J].Acta Optica Sinica,2010,30(3): 702–707. [ 郝志成, 朱明. 基于多约束准则匹配算法的序列图像配准[J].光学学报,2010,30(3): 702–707.] [DOI:10.3788/aos20103003.0702]
[14] Park H, Mitsumine H, Fujii M. Automatic adjustment of the distance ratio threshold in nearest neighbor distance ratio matching for robust camera tracking[J].IEICE Transactions on Information and Systems,2011,E94-D(4): 938–940. [DOI:10.1587/transinf.E94.D.938]
[15] Wu Y, Ma W P, Gong M G, et al. A novel point-matching algorithm based on fast sample consensus for image registration[J].IEEE Geoscience and Remote Sensing Letters,2015,12(1): 43–47. [DOI:10.1109/LGRS.2014.2325970]
[16] Xu W, Zhang M J, Xiong Z J, et al. Feature point matching based on bidirectional maximal correlation and parallactic restriction[J].Computer Engineering and Applications,2008,44(28): 155–157. [ 徐玮, 张茂军, 熊志辉, 等. 基于双向最大相关与视差约束的特征点匹配[J].计算机工程与应用,2008,44(28): 155–157.] [DOI:10.3778/j.issn.1002-8331.2008.28.052]
[17] Wang Z F, Wang H. Target location of Loitering Munitions based on image matching[C]//Proceedings of the 6th IEEE Conference on Industrial Electronics and Applications. Beijing, China: IEEE, 2011: 606-609. [DOI: 10.1109/ICIEA.2011.5975657]
[18] Liu G X, Liu D M, Liu F P, et al. A robust image registration algorithm based on feature points matching[J].Acta Optica Sinica,2008,28(3): 454–461. [ 刘贵喜, 刘冬梅, 刘凤鹏, 等. 一种稳健的特征点配准算法[J].光学学报,2008,28(3): 454–461.] [DOI:10.3321/j.issn:0253-2239.2008.03.009]
[19] Jiang Z T, Wang Q, Cui Y R. A fast method for feature matching based on SURF[C]//Proceedings of the 2nd Sino-foreign-interchange Workshop. Berlin Heidelberg: Springer, 2012: 374-381. [DOI: 10.1007/978-3-642-31919-8_48]
[20] Maresca M E, Petrosino A. The Matrioska tracking algorithm on LTDT2014 dataset[C]//Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition Workshops. Columbus, OH: IEEE, 2014: 720-725. [DOI: 10.1109/CVPRW.2014.128]
[21] Laganiere R. OpenCV2 Computer Vision Application Programming Cookbook[M]. Zhang J, trans. Beijing: Science Press, 2013: 180-185. [Laganiere R. OpenCV2计算机视觉编程手册[M]. 张静, 译. 北京: 科学出版社, 2013: 180-185.]
[22] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(10): 1615–1630. [DOI:10.1109/TPAMI.2005.188]
[23] 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. [DOI:10.1145/358669.358692]