基于网格对应的双约束特征点匹配算法

林敏　陈姝　袁浩翔

摘   要：常用的特征点匹配算法通常设置严苛的阈值以剔除错误匹配，但这样也会导致过多的正确匹配被删除。针对这一问题，提出了一种采用双约束的特征点匹配方法。首先，在局部上统计特征点匹配数量，运用网格对应的方法过滤部分错误匹配;然后，在全局上运用RANSAC方法计算基础矩阵，通过极线约束对匹配进行再一次筛选。实验表明，相比于传统的匹配算法，该算法能在不增加算法运行时间的前提下，获得更高数量和更高质量的匹配集合。

关键词：特征点匹配;误匹配;网格对应;RANSAC;极线约束

中图分类号：TP391.4                                             文献标识码：A

Feature Point Matching Based on Double Constraints

LIN Min？覮，CHEN Shu，YUAN Hao-xiang

（College of Information Engineering，Xiangtan University，Xiangtan，Hunan 411105，China）

Abstract：Commonly used feature point matching algorithms usually set strict thresholds to eliminate false matches，which may cause many correct matches to be deleted. To overcome this problem，a feature matching algorithm using double constraints isproposed. Firstly，we statistically count the number of feature point matches in local to establish a grid correspondence，which can be used to filter out partial false matches. Then，the RANSAC was globally introduced to calculate the fundamental matrix，and the matching is once again filtered by the epipolar constraint. Experiments show that compared to the traditional matching algorithm，our algorithm can obtain a higher number and higher quality matching set without additional running time.

Key words：feature point matching;false matches;grid correspondence;RANSAC;epipolar constraint

圖像特征点匹配[1]旨在建立同一对象或场景不同视图之间的精确对应关系，其结果一般作为高级计算机视觉算法应用的输入，因此特征点匹配在三维重建[2]，目标跟踪[3]，物体识别[4]，slam[5]等领域都起着至关重要的作用。

目前最常用的特征点匹配策略分为两步。首先，用Flann[6]等匹配器通过比较特征描述子的相似性以删除掉大部分错误匹配，确定基础匹配集合。然后，对于匹配集合采用统计回归[7]，RANSAC[8]等方法对匹配进行验证，最终获得鲁棒的特征点匹配集合。Bay等人通过改变特征点检测方式和降低特征描述维度等方法，提出了众多抗干扰强，速度快的特征点匹配算法[9，10]，但仍是通过相似度来确认特征是否匹配。而Lowe等人对SIFT特征点[11]的研究表明最近邻距离比值法（NNDR，Nearest Neighbor Distance Ratio）可以有效区分匹配是否正确，但是比率阈值难以设计，宽松的阈值会导致误匹配数量激增，严苛的阈值往往将很多正确匹配也排除在外。Bian[12]等人提出采用运动平滑来约束匹配，用网格统计（GMS，grid-based motion statistics）的方法将高数量匹配转换为高质量匹配，但算法需要提取数量巨大的特征点，且误匹配容易“扎堆”出现。文献[13]使用RANSAC方法通过极线约束来提高匹配精度，但算法复杂度高，十分耗时。文献[14]和文献[15]分别针对特征点匹配中难以解决的宽基线和重复结构问题分别提出Code和Repmatch方法，两者都取得了很好的匹配效果，但因为算法复杂，运行较慢。

本算法主要针对特征点匹配进行研究。采用网格对应取代阈值设置对匹配进行首次粗过滤。然后采用RANSAC方法对匹配进行二次筛选。实验证明，网格对应能保留更多的正确匹配，而经过两次过滤后的匹配集合在匹配数量和匹配准确度上都有明显提高。

1   双约束原理与实现

1.1   相关原理

1.1.1   网格对应

网格对应是根据运动相似性原理，通过统计匹配分布，将匹配约束在对应网格中来达到去除误匹配的目的。

图1   网格对应

在一般的网格对应中，图像对{Ia，Ib}各有{N，M}个特征点，X = {x1，x2，…，xi，…，xN}是根据特征点描述子相似度得出的基础匹配集合，取匹配x_i两个特征点周围的小区域{a，b}，它们分别对应有{n，m}个特征点，{a，b}内其它匹配满足Xi■X。由此可以计算匹配xi的邻域支持度Si：

Si = Xi - 1      （1）

如图1所示，用网格对应近似表示匹配xi及其邻域。与（1）类似，对应网格的邻域支持度表示为：

Sab = ■x akbk      （2）

用pt和pf分别表示正确匹配和错误匹配的概率，则可以用一组二项式分布函数近似表示对应网格内正确匹配和错误匹配的邻域支持度：

Si ～ B（Kn，pt），if xi is trueB（Kn，pf），if xi is false      （3）

由于正确匹配和错误匹配各自的邻域支持度遵循不同的分布，所以Si整体上呈双峰分布，这使得邻域支持度Si可以成为区分网格是否正确对应的一个重要指标。

本文算法根据不同的特征点分布情况设置不同的邻域支持度阈值来确立网格对应。当特征点分布稀疏时，意味着匹配分布也是稀疏的，此时网格邻域支持度会很小，设置阈值τ′ = 2，剔除网格邻域支持度小于2的对应网格。而针对特征点聚集区域，设置阈值τ′′ = ■，sum是9个网格内的匹配数，剔除网格邻域支持度在9个网格内占比不足1/8的对应网格。由此得到的匹配都约束在一定条件下的对应网格内，虽然这样的网格对应并不能完全将误匹配去除，但这也为后续的极线约束奠定了良好的基础。

图2   极线约束

1.1.2   极线约束

极线约束源于对极几何[16]，它描述了两幅视图之间内在的射影关系。一幅视图中的点定义了另一幅视图中对应点所在的极线。图2是极线约束的基本介绍。P是空间中一三维点，C0和C1表示相机中心，空间点在两摄像机成像平面的投影分别为p0和p1，P和两个相机中心构成的平面称为极平面，点p0和p1均在此平面上。该平面和两个成像平面的交线即为极线。点p0在第二幅视图上的对应点必在极线l1上，同理p1点的对应点必在l0上。可以用基本矩阵F表示这种从点到直线的射影映射关系，即：

l = ABC = Fp = Fxy1    （4）

1.2   双约束特征点匹配

基于网格对应的双约束特征点匹配算法实现的具体步骤如下：

1）读取待匹配的图像对，经过暴力匹配和对称性检测获得一个基础的匹配集合。

2）采用网格对应的方法对匹配进行第一次筛

选。分两种情况设置不同的网格对应阈值以确立网格对应，步骤如下：

a）将图像对{Ia，Ib}各自划分成G个网格;

b）图像Ia的每个网格根据匹配数最大的原则

找Ib中对应网格;

c）计算对应网格的邻域支持度Sab;

d）如果Sab大于τ′和τ′′中相对较大的那个，则认为网格对应;

e）剔除掉不满足网格对应的匹配。

3）将网格对应后的匹配集合作为RANSAC算法的输入，计算出具有最大匹配支持集合的基本矩阵F，并获得第二次约束后的匹配集合。RANSAC算法采用迭代的方式自动估计F，步骤如下：

a）从匹配集合中随机选取一个匹配子集Ti，假设Ti的所有匹配满足极线约束;

b）由Ti内的匹配点对计算基本矩阵F;

c）用得到的F去测试其他其它所有匹配，将满足约束的匹配归入子集Ti中;

d）如果Ti内匹配数量足够多，则认为计算出来的F足够合理;

e）以上过程重复执行固定次数，比较每次Ti内匹配数量，找出Ti的最大集合;

f）用更新后的Ti重新计算F，而Ti集合内的匹配即为满足极线约束的匹配。

至此，完成了利用网格对应获得优质匹配的整个过程。

2   实验结果分析

实验采用Intel■CoreTM i5-8265U CPU @ 1.60GHz，8GB内存的计算机，在vs2017上采用OpenCV开源图像库作为实验平台，选取公开数据集[17][18]的图像作为实验数据。实验中所有参数都采用图像库默认参数设置。

2.1   匹配结果对比

为了能验证算法的有效性，采SIFT特征点作为匹配对象，对比本文算法和不同阈值设置下NNDR算法的匹配结果。如图3所示，括号内给出了正确匹配数和匹配数，r表示比率阈值。实验发现，当r设置为0.8时NNDR算法的匹配结果最优，但本文算法仍比它多了19对正确匹配，这说明本文算法在剔除误匹配的同时将更多正确匹配保留了下来。同时，如图4所示，选取6组复杂度不同的图像，包含简单和复杂个体对象以及室内、外场景。将NNDR阈值设置为0.8，表1列出了两种方法得到的匹配数据。从表1可以看出，本文算法在6组图像中都取得了更多的匹配数和更高的匹配精度，说明本文算法针对不同种类的图像都能取得不错的匹配效果。

（a）NNDR+RANSAC（106/106）r = 0.8

（b）本文方法（125/125）

图3   比例阈值法匹配与本文算法匹配对比

图4   部分实验图像

另外，将本文算法运用到包含重复結构图像的匹配中。如表2所示，实验统计了5组匹配数据，本文算法同样做到了在匹配数量和匹配质量上都优于另外两种算法。图5是其中一组数据的匹配效果图。图5（a）是用最邻近距离比值法（NNDR）过滤部分匹配后再采用RANSAC方法得到的匹配结果，从图中可以看出，虽然经过RANSAC极线约束，但仍存在较多误匹配。图5（b）为GMS算法的匹配结果图，可以看出GMS算法的误匹配数虽然有所减少，但也存在误匹配聚集出现的问题。图5（c）是本文算法得到的匹配结果。相较GMS算法，由于本文算法在网格对应的基础上增加了一次极线约束的几何验证，所以获得了更高质量的匹配结果。

（a）NNDR+RANSAC（446/510）

（b）GMS（460/480）

（c）本文方法（472/475）

图5   包含重复结构图像的匹配结果

2.2   时间复杂度对比

在图像特征点匹配算法评价标准中，算法耗时同样是一项重要指标。故如表3所示，列出上述总共11组数据NNDR方法RANSAC用时和本文算法RANSAC用時。由于RANSAC算法随机采样的机制，每组数据运行5次，取平均运行时间。从表中可以看出，本文算法虽然增加了正确匹配数量，但并未增加算法运行时间，相比之下本文算法有几组数据的运行时间甚至更短，这也说明本文算法的网格对应部分能有效地筛除错误匹配，减少了RANSAC算法迭代运行时间。

表3   时间复杂度对比

3   结  论

特征点匹配技术在众多高级计算机视觉应用领域都具有相当重要的意义。对比采用阈值设置方式进行匹配选择的算法，针对其难以设置理想阈值保留足够多正确匹配的问题，本文引入网格对应和极线约束来对基础匹配集合进行两次筛选，匹配实验结果表明，经过局部和全局上的两次误匹配剔除，本算法实现了在不增加算法运行时间和减少误匹配的同时，极大地提高了正确匹配数量。

参考文献

[1]    肖明，鲍永亮，颜仲新. 基于点特征的图像配准方法综述[J]. 兵工学报，2015，2.

[2]    AGARWAL S，SNAVELY N，SIMON I，et al. Building Rome in aday[C]//IEEE International Conference on Computer Vision， 2009.

[3]    CHEN S，LIANG L，LIANG W，et al. 3D pose tracking with multi-template warping and SIFT correspondences[J]. IEEE Transactions on Circuits and Systems for Video Technology，2015，26（99）：1—1.

[4]    GUO Y，SOHEL F，BENNAMOUN M，et al. A novel local surface feature for 3D object recognition under clutter and occlusion[J]. Information Sciences，2015，293：196—213.

[5]    MUR-ARTAL R，MONTIEL J M M，TARDOS J D. ORB-SLAM：a versatile and accurate monocular SLAM system[J]. IEEE Transactions on Robotics，2015，31（5）：1147—1163.

[6]    MUJA M，LOWE D. Flann-fast library for approximate nearest neighbors user manual[J]. Computer Science Department，University of British Columbia，Vancouver，BC，Canada，2009.

[7]    LIU Y，DEDOMINICIS L，WEI B，et al. Regularization based iterative point match weighting for accurate rigid transformation estimation[J]. IEEE Transactions on Visualization and Computer Graphics，2015，21（9）：1058—1071.

[8]    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.

[9]    BAY H，TUYTELAARS T，VAN GOOL L. Surf：Speeded up robust features[C]//European Conference on Computer Vision. Springer，Berlin，Heidelberg，2006：404—417.

[10]  RUBLEE E，RABAUD V，KONOLIGE K，et al. ORB： an efficient alternative to SIFT or SURF[C]//2011 International conference on computer vision. Ieee，2011： 2564—2571.

[11]  LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision，2004，60（2）： 91—110.

[12]  BIAN J W，LIN W Y，MATSUSHITA Y，et al. GMS：grid-based motion statistics for fast，ultra-robust feature correspondence[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017：4181—4190.

[13]  陳洁，高志强，密保秀，等. 引入极线约束的SURF特征匹配算法[J]. 中国图象图形学报，2018，21（8）：1048—1056.

[14]  LIN W Y，WANG F，CHENG M M，et al. CODE：coherence based decision boundaries for feature correspondence[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2017：1—1.

[15]  LIN W Y，LIU S，JIANG N，et al. RepMatch：robust feature matching and pose for reconstructing modern cities[C]// European Conference on Computer Vision. Springer，Cham，2016.

[16]  HARTLEY R，ZISSERMAN A. Multiple view geometry in computer vision[M]. Cambridge University Press，2003.

[17]  SHAO H，SVOBODA T，VAN GOOL L. Zubud-zurich buildings database for image based recognition[J]. Computer Vision Lab，Swiss Federal Institute of Technology，Switzerland，Tech. Rep，2003，260（20）：6—8.

[18]  JRGEN S，ENGELHARD N，ENDRES F，et al. A benchmark for the evaluation of RGB-D SLAM systems[C]//2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE，2012.