基于局部一致性的特征匹配算法

第37卷 第07期数字技术与应用第 37 卷 数字技术与应用 www.szjsyyy.com2019年 7月Digital Technology &ApplicationVol.37 No.7July 2019算法分析DOI:10.19695/j.cnki.cn12-1369.2019.07.65基于局部一致性的特征匹配算法*姚晋晋1,2 张鹏超2 王永鑫1,2 王彦1,2(1.陕西理工大学 机械工程学院,陕西汉中 723000;2.陕西省工业自动化重点实验室,陕西汉中 723000)摘要:针对特征匹配对尺度、光照变化敏感的问题,提出一种改进ORB特征提取方法,并采用基于局部一致性的方法进行匹配。首先采用改进ORB算法提取鲁棒性更强的特征点,并计算特征点的方向与描述子,接着采用暴力匹配进行粗匹配,最后根据运动平滑性的条件使用基于网格运动统计的方法剔除误匹配。实验结果表明所研究算法在尺度、光照等条件变化时匹配平均精度仍然大于95%,具有较好的匹配准确率和鲁棒性。关键词:ORB；特征匹配；局部一致性；运动统计中图分类号:TP391.4文献标识码:A文章编号:1007-9416(2019)07-0128-030 引言图像匹配是计算机视觉领域一个基本问题,目的是为了寻找图片对应的运动关系,目前常用的匹配方法是基于特征点的匹配,然而该方法由于特征点的固有问题,容易受到光照、尺度、视角等影响,匹配准确率有待提高。随机采样一致性(RANSAC)方法是常用的特征匹配算法,但是算法复杂度较高,无法满足实时性要求较高的系统。Zhang Songtao[1]等人提出了基于双向交叉匹配和距离阈值的匹配方法,提高了匹配的准确率,然而正确匹配数量却随之减少了;Yong An[2]等人提出了一种基于k近邻的用于SIFT特征的匹配算法,根据特征点周围的附属点判断匹配是否准确,从而实现误匹配的筛选,具有良好的去误匹配的能力;Jiawang Bian[3]提出一种基于网格运动统计(GMS)的特征匹配方法,该方法在运动平滑的假设上,通过计数邻域的匹配点个数判断匹配是否正确,提高了匹配准取率,但是为了保证效果,需要提取大量的特征点。为此,本文提出了改进的ORB方法进行特征提取,采用Hessian矩阵计算关键点,并计算关键点的方向,使其具有尺度和旋转不变性,并采用BRIEF描述子对关键点邻域内随机生成的点对进行灰度值的比较,通过Hamming距离进行暴力匹配得到粗匹配结果,最后采用基于局部一致性的方法进行误匹配的去除,从而提高特征匹配的准确率。 Lxyx,σ、 Lyyx,σ分别是在点(x,y)处高斯其中, Lxxx,σ、二阶微分与图像间的卷积,并根据其行列式的值将关键点分类。接着构建四层金字塔,第一层为原始图像,然后在此基础上二倍采样得到二到四层,每层中有一系列不同模糊度的图片,对每层图像上的每个像素与空间邻域内和尺度邻域内的三维空间中26个像素点的响应值比较,若为极大值或者极小值,则将其作为关键点。为了使特征点具有旋转不变性,使用灰度质心法为上述特征点添加方向信息[8]。首先定义图像的矩为: mpqx,yBxpyqIx,yp,q0,1 (2)其中B为图像区域, Ix,y为图像灰度。然后通过矩找到图像质心: mmC=10,01 (3)m00m00得到特征点的主方向为: θ=arctanm01m10 (4)在得到特征点后,采用BRIEF作为其描述子,通过0和1编码关键点附近随机两个像素灰度值的大小关系,从而组合成二进制的描述子。1 算法描述1.1 改进ORB特征提取传统ORB算法不具备尺度不变性,为此在OpenCV中的ORB算法构建了金字塔,在多尺度上提取特征点,但对于模糊的图片仍然难以达到较高的匹配效果,本文采用Hessian矩阵[4]为核心的方法提取特征点,具有更强的鲁棒性。每个像素点都可以求出一个Hessian矩阵,但是为了使特征点具备尺度不变性,在构造Hessian矩阵前,需要对其进行滤波,滤波后的图像中像素点(x,y)的Hessian矩阵计算如下:1.2 基于运动统计的匹配算法目前常用的匹配算法有k近邻匹配、双向匹配和采用RANSAC的匹配,其中RANSAC方法由于其对准确率的提升得到了广泛使用,但是该方法计算复杂度高,迭代次数较多,耗时较长。而基于运动统计的GMS方法根据局部一致性,以运动的平滑性为前提作为约束去除误匹配,并用基于网格的分数估计方法,使得特征匹配算法能达到实时性[3]。图像 Ia,Ib中分别有 N,M个特征点, χx1,x2,……,xN是从 Ia到 Ib的所有最近邻匹配,通过计算匹配点的局部匹配点数可以判断匹配是否正确。记匹配对在 Ia,Ib中分别对应领域 a,b, χiχ, χi是邻域 a,b的匹配子集, Si为匹配点的邻域支Lxxx,σHx,σLxyx,σLxyx,σ (1)Lyyx,σ收稿日期:2019-06-12*基金项目:陕南秦巴山区生物资源综合开发协同创新项目(QBXT-17-7)作者简介:姚晋晋(1993-),男,山西运城人,硕士研究生,研究方向:视觉SLAM。通信作者:张鹏超(1977—),男,陕西咸阳人,教授,博士,研究方向:机器人控制。128姚晋晋 张鹏超 王永鑫等:基于局部一致性的特征匹配算法持度,则有: Siχi1 (5)其中-1是将待检验的匹配对移除。文献[3]中利用二项分布近似 Si在 χi邻域内的分布:2019年第 07 期最后得到概率评估公式:KnptKnpf PmtmfstsfKnpt1ptKnpf1pf (8)从公式(8)分析可知, P与 n成正比,即特征点的数量越多,评分越高,匹配准确率将越高,GMS方法将匹配数量上的优势转化为匹配质量的提升。BKn,pt,xitrueSi: (6)BKn,pf,xifalse其中 pt, pf分别为正确和错误匹配概率,K为不连接邻域数 Si整体呈双峰分布,其均值和标准差分量,n为图像中的特征数量。别为: 2 实验分析为验证本文算法的图像匹配效果,本实验主要采用OpenCV视觉库在牛津大学图像匹配数据集中进行。实验在Ubuntu16.04系统下进行,CPU为i5-4258,2.4GHz,8G内存。为了验证匹配算法在不 mtKnpt,stKnpt1pt,xitrue同环境下的效果,分别在模糊程度不同,光照不同,以及视角不同的 (7)mKnpf,sfKnpf1pf,xifalse条件下,对暴力匹配、基于RANSAC的方法的匹配和本文算法进行f对比实验。在模糊处理的图片上匹配结果如图1所示,a、b、c分别是暴力匹配、RANSAC匹配和本算算法在模糊处理后的匹配结果,由实验分析可知,暴力匹配的效果最差,包含有大量的误匹配,而后两种算法的效果较好,但是本文算法的匹配准确率和正确匹配 a b c数量均优于基于RANSAC匹配,准确率达96.62%。图1 模糊变化匹配结果图2和图3分别为光照变化、视角变化条件下三种匹配算法的实验结果。由图2分析可知,在光照条件变化下,本文算法仍然保持较多的匹配数量,具体如表一所示,并且仍然保持较高的匹配准确率,而基于RANSAC的方法,则由于其算法的严格性删除了大量的正确匹配。 a b c而在视角变化下,如图3所示,本文算法所得到的匹图2 光照变化匹配结果配数量少于基于RANSAC的方法,原因是因为本文算法在视角变化较大时,运动平滑性的假设条件被破坏,导致匹配数量下降,但是匹配准确率依然维持在较高水平。匹配结果的具体数据如表1所示,分别对匹配数量、匹配准确率及匹配时间进行检测,为不失一般 a b c性,每组实验数据均为10次结果的平均值,其中暴力图3 大视角变化下的测试结果匹配(BF)算法的匹配时间为特征点匹配所用时间,表1 三种算法匹配结果而为了直接对比基于RANSAC方法的匹配和本文匹配算法 环境变化 匹配数量 正确匹配数量 准确率/% 匹配时间/s 算法的匹配时间,后两者的匹配时间指的是得到粗匹配后再处理的时间,例如BF+RANSAC算法匹配模糊 500 285 57.00% 0.0034 时间为对粗匹配结果使用RANSAC方法进一步提BF匹配 光照 500 298 59.60% 0.0039 纯所用的时间。视角 500 281 56.20% 0.0036 由表1分析可知直接使用暴力匹配得到的匹配模糊 337 331 98.21% 1.1x10-3 BF+ -3 准确率不到60%,远未达到可以进行位姿估计的要光照 248 238 95.97% 1.2x10RANSAC 求,而BF+RANSAC和本文算法的匹配准确率均在视角 271 257 94.83% 8.9x10-4 并且本文算法在模糊处理模糊 385 372 96.62% 8.35x10-5 90%以上,匹配效果良好。本文算法 光照 399 374 93.37% 7.64x10-5 和光照条件变化的条件下的正确匹配数量远高于视角 195 188 96.41% 7.91x10-5 BF+RANSAC算法,其中在模糊条件下高出BF+RANSAC方法12.39%,在光照条件变化下高出表2 提取2000个特征点的匹配结果前者57.14%。但是在视角变化较大的情况下,本文匹配算法 环境变化 匹配数量 正确匹配数量 准确率/% 算法的正确匹配数量下降,是因为本文匹配算法建模糊 1333 1290 96.77 立在平滑运动的假设上,当视角变化较大时,匹配数ORB+RANSAC 光照 1129 1068 94.80 量下降。由匹配时间分析可知,本文算法在匹配对的视角 948 887 93.57 提纯上比RANSAC方法快1～2个数量级,大幅减少模糊 1294 1273 98.38 了特征匹配的时间。ORB+本文算法 光照 1430 1386 96.92 为了进一步验证本文算法在大数量特征点匹视角 1546 1532 99.09 配上的优势,实验对不同图像均提取2000个ORB特129第 37 卷 数字技术与应用 www.szjsyyy.com征点,再对其分别用RANSAC和本文算法进行提纯,匹配结果如表2所示。从表2分析可知,在环境变化时,本文算法相对于传统RANSAC算法可以保持较高的准确率,平均提升3.08%,同时保留的较多的正确匹配,尤其是在光照条件和视角变化时,所得正确匹配数量大幅提升,对三维重构具有重要意义。[2] Yong A,Hong Z.SIFT matching method based on K nearestneighbor support feature points[C]// IEEE International Con-ference on Signal & Image Processing. IEEE,2017.[3] Bian J,Lin W Y,Matsushita Y,et al.GMS: Grid-Based MotionStatistics for Fast,Ultra-Robust Feature Correspondence[C]//2017IEEE Conference on Computer Vision and Pattern Recognition(CVPR). IEEE,2017.[4] Bay H,Tuytelaars T,Gool L V.SURF:Speeded up robust features[J].Computer Vision & Image Understanding,2006,110(3):404-417.[5] Gao X,Zhang T.Robust RGB-D simultaneous localization andmapping using planar point features[J].Robotics& AutonomousSystems,2015,72:1-14.[6] 王瑜,禹秋民.基于曲率特征与改进的RANSAC策略的图像匹配算法[J].计算机工程与设计,2018,39(12):3791-3796.[7] 孙莹.图像特征点提取与描述算法研究[J].网络空间安全,2016,7(2):18-21.3 结论实验结果表明,本文所提出的算法在图像亮度变化和模糊情况下,具有较好匹配效果,在保证一定准确率的同时,可以得到更多的正确匹配,有利于位姿估计和三维重建,并且相对于RANSAC方法,本文算法的提纯时间减少了1～2个数量级,大大减小了去除误匹配的时间,但是在视角变化变大时,匹配数量有所下降,仍需进行改进。参考文献[1] Songtao Z,Chao L, Liqing L.An improved method for elimi-nating false matches[C]// International Conference on Image.IEEE,2017.Feature matching algorithm based on local consistencyYAO Jin-jin1,2, ZHANG Peng-chao2, WANG Yong-xin1,2, WANG Yan1,2(1. School of Mechanical Engineering, Shaanxi University of Technology, Hanzhong Shaanxi 723000;2.Shaanxi Key Laboratory of Industrial Automation, Hanzhong Shaanxi 723000)Abstract:Aiming at the problem that feature matching is sensitive to scale and illumination changes, an improved ORB feature extraction methodis proposed, and the method based on local consistency. Firstly, the improved ORB algorithm is used to extract the more robust feature points, and thedirection and descriptor of the feature points are calculated. Then the brute force matching is used for rough matching. Finally, the method based on gridmotion statistics is used to eliminate errors according to the condition of motion smoothness. The experimental results show that the matching accuracyof the proposed algorithm is still greater than 95% when the scale, illumination and other conditions change, which has better matching accuracy androbustness.Key words:OR; feature matching; local consistency; motion statistic······上接第127页况时,首先用博弈论方法分析了游客逃生时因心理变化产生的行为,个体利益与群体利益的关系。接着用迪杰斯特拉算法计算出建筑内各区域到各出口的最短逃生路线,这里借用了“光程”的概念,不止是考虑实际疏散路程长短,也根据人群密度对疏散速度的影响,对人群分布概率的不对等做出了弥补。分析结果显示该模型具有很好的可行性,这在我们为大型复杂建筑设计室内逃生路线时提供了新方法,具有很好的现实意义。参考文献[1] 刘根旺,周颖,张磊,康增信.基于博弈论的人员疏散演化研究[J/OL].计算机工程与应用:1-8[2019-07-23].[2] Dirk Helbing,Illes Farkas,Tamas Vicsek.Simulating dynamicalfeatures of escape panic[J].Nature,2000(03):487-490.[3] 李苹.基于博弈论方法的人员运动规律研究[D].华北水利水电大学,2017.[4] 付婷.城市轨道交通车站集散能力瓶颈识别[D].北京交通大学,2014.Research on Large Building Escape Scheme Based on Game Theory and DijkstraAlgorithmCHEN Hong-lv, DENG Yi-ran(School of Software, Sichuan University, Chengdu Sichuan 610000)Abstract:With the development of society, public safety has received widespread attention. This article is aimed at large and complex buildingswith a visit nature, Take the Louvre as an example, A comprehensive analysis of the distribution and flow characteristics of the people in the building isgiven, the game behavior analysis based on the game theory and the MSTS model based on the Dijkstra algorithm are given to formulate the evacuationroute. Finally, the model is applied to the Louvre to calculate the escape time of tourists and verify the feasibility of the model.Key words:game theory; herding effect; fast is slow; optical path; Dijkstra algorithm130