一种基于ORB检测的特征点匹配算法

刘 威,赵文杰,李德军,王 骁，叶 怡

(1.空军航空大学航空航天情报系,吉林 长春 130022;2.解放军94891部队，江苏 苏州 215000)



·图像与信号处理·

一种基于ORB检测的特征点匹配算法

刘 威1,赵文杰1,李德军1,王 骁2，叶 怡2

(1.空军航空大学航空航天情报系,吉林 长春 130022;2.解放军94891部队，江苏 苏州 215000)

针对传统的SURF局部特征匹配算法实时性不高的问题,充分利用ORB特征点检测算法简单高效的优势,提出了一种新的特征点匹配算法。首先,针对原始ORB特征匹配算法出现大量误匹配对的问题,采用基于K最近邻的特征点描述后,对前后两帧特征点进行双向匹配,再通过顺序抽样一致性算法进一步提纯。实验结果表明,经过本文算法提纯后匹配对准确度提升到99.9%,平均耗时0.46 s,处理速度约是SURF特征匹配算法的5倍,SIFT特征匹配算法的25倍,能够满足实时运用的需求。

特征点匹配；ORB角点检测；局部特征

1 引 言

特征点匹配算法在运动目标检测与识别、视觉导航等领域有着广泛应用[1]。目前常用的特征点匹配算法主要有：SIFT[2]、SURF[3]和ORB[4]等。其中SIFT算法是David G.Lowe在2004年提出的一种具有里程碑意义的尺度不变特征变换算法,在多尺度空间提取特征点；SURF算法由SIFT算法改进而来,通过积分图像和盒式滤波器来替代SIFT中的尺度空间分解,大大减少了计算量。但在对实时性要求较高的应用中,这两种算法依然无法满足要求。而由Rublee等人在ICCV2011上提出的ORB算法在保证尺度、旋转不变的基础上,速度较前两种算法有了很大的提高。作为一种局部不变特征匹配算法,ORB是建立在FAST特征点检测[5]和BRIEF特征点描述[6]的基础之上,其采用的二进制局部特征描述符的实时性大大优于SIFT、SURF等浮点型局部特征描述符[11]。

本文基于ORB角点检测提出一种特征匹配算法。利用ORB算法快速提取特征点,改进其匹配策略消除误匹配点。与传统的SURF特征匹配算法相比,本文算法在实时性上有了很大提高；与传统的ORB特征匹配算法相比,本文算法能够极大消除噪声点。

2 ORB特征匹配算法

原始的ORB匹配算法主要经过以下几个步骤：首先,利用Oriented FAST检测子在连续两幅图像上检测特征点；再通过Rotated BRIEF描述符生产特征点的二进制描述向量；最后连续两幅图像的特征点的匹配采用汉明距离比值准则得到最终的特征点匹配对。

2.1 Oriented FAST特征点检测

FAST由于其高效性得到了广泛应用,Rosten等人[7]在算法中加入了机器学习和ID3决策树机制提出了一种简单快速的FAST特征点检测算法。在文献[7]中,Rosten等人将FAST特征点定义为：图像中某点的灰度值比周围邻域内大多数像素点的灰度值都大或小时,该点为特征点。检测点p周围的16个点,如果有连续12个点的灰度值与点p的灰度值之差大于一定的阈值,则将点p判定为特征点,为此可以通过一个角点响应函数CRF来判断一个FAST特征点：

(1)

(2)

其中,I(x)是待测点邻域内任一点的灰度值;I(p)是当前待测点的灰度值。所有圆周点与待测点的响应函数值的和为N,ORB算法中N为9,当N大于一定阈值时待测点为特征点。为了使得特征点能适应光照变化,ORB算法首先设置较低的阈值提取多数的特征点,再利用Harris角点[8]的评价函数找到角点响应值较高的前N个FAST特征点；为了使特征点具有尺度不变性,ORB算法使用金字塔算法得到多尺度图像,得到FAST特征点的尺度特征；为了使特征点具有方向不变性,ORB算法使用灰度质心法[9]为特征点提供一个主方向：找到特征点局部区域内的灰度形心,用特征点到形心的矢量方向来确定特征点的主方向,局部区域矩的公式是：

(3)

则这些矩计算特征点区域上的灰度形心为：

(4)

则质心与特征点的夹角即FAST特征点的主方向：

(5)

2.2 Rotated BRIEF特征点描述

ORB算法中采用BRIEF描述子对检测到的特征点进行描述,并解决了BRIEF描述子不具有旋转不变性的问题。

BRIEF描述子是最简单的一种二进制描述子,其生成过程如下：在图像块内随机生成点对(对数可以是128、256和512),每一个点对对应一个二进制位,定义如下：

(6)

其中,p(x)和p(y)是点对的灰度,随机选择n对点(xi,yi)就可以生成一个二进制字符串,则生成的特征描述子可以表示为：

(7)

由于BRIEF描述子比较的是点对的像素值,对噪声非常敏感。为了消除噪声的影响,ORB算法采取如下策略：在特征点邻域的31×31像素区域内随机选取5×5的子窗口,比较窗口的灰度积分来替换点对的像素值的比较。为了解决BRIEF描述子不具有旋转不变性的问题,ORB算法的解决方案是：在特征点上选取n对特征,得到一个2n矩阵：

(8)

利用特征点检测得到的主方向确定的仿射变换矩阵Rθ对进行旋转得到新的描述矩阵：

(9)

结合式(7)这样就可以得到矫正后的BRIEF描述子：

(10)

其中,n可取128、256、512,在ORB算法中作者选取的是相关性较低的256对像素块对进行特征描述。

2.3 ORB特征点匹配

2.1.1 心理护理 术前关注患者的心理状态至关重要［7］。患者为年轻女性，病史2年余，因咳嗽、咳痰、发热就诊于多家医院，口服抗结核药物效果不满意，经多次气管镜检查发现气管下段狭窄。随着病情进展呼吸困难加重，雾化、平喘、对症治疗无效，使患者对治疗信心不足。虽然对手术抱有希望，但又担心手术失败。护士及时了解患者心理变化，随时了解各种检查结果，给予心理疏导。告诉其医护人员及家人正在积极想办法、做准备，并列举成功实施气管手术的病例鼓励患者，讲解大致手术过程，增强患者战胜疾病的信心。在不影响治疗、护理的情况下，尽量让家属陪伴，增加患者安全感，使患者能积极配合检查、治疗。

上节中得到的256维ORB特征描述子,为了建立连续两幅图像上特征点的对应关系,我们计算第二帧图像上每个特征点与第一帧图像上全部特征点描述向量的汉明距离,用D(Vp,Vq)表示,其中Vp是第二帧中某一特征点p的特征向量,Vq是第一帧中最邻近特征点q的特征向量,D(Vp,Vq)越小说明两个特征点越相似,汉明距离最小的即为匹配对。

3 一种匹配对提纯的改进算法

从以上的分析发现ORB算法存在两大缺陷：一是基于穷举搜索得到的匹配对没有考虑两特征点是否属于同一区域；二是当多个特征点较为接近时算法将丧失判断能力,影响了匹配精确度。常见的误匹配去除算法——RANSAC,是一种随机参数估计算法,该算法的缺点是随机抽取匹配对,不考虑匹配对的质量好坏,当误匹配对较多时依然会造成很大偏差。为此本文提出一种新的特征点匹配算法——PROMATCH(progressive match),对去除误匹配对提出如下改进策略。

3.1 基于K最近邻的特征点匹配对描述

3.2 基于汉明距离近邻比值准则的双向匹配

(11)

(12)

Vj≠Vq}

(13)

(14)

3.3 基于PROSAC算法去除误匹配

PROSAC算法[10]是RANSAC算法的改进,不是随机抽取匹配对,而是根据匹配对的质量好坏对匹配对进行排序,在模型参数拟合时优先抽取质量较高的匹配对进行迭代估计。这里我们将上一步中计算得到的最近邻和次近邻的比值R作为匹配质量的定量表示,对经过双向匹配后得到的特征点匹配对进行进一步提纯,本文采用的PROSAC算法步骤如下：

(1)初始设置：迭代次数初值设为0,是否为内点的误差阈值、内点数目的阈值、最大迭代次数。

(2)若迭代次数小于最大迭代次数,选取样本集中前n个具有较高质量的数据,从中随机取出m个,计算模型参数,并计算用此模型参数得到的误差小于内点误差阈值的数据数量,即内点数量。若迭代次数大于最大迭代次数,则返回对应内点数量最大的一组内点。

(3)判定内点数量是否大于设定的内点数目阈值,大于则返回内点,否则迭代次数加1跳转第二步。

4 实验与结果分析

实验平台采用Intel Core(TM)2 Duo CPU主频2.5GHz的PC机,没有任何硬件加速,用C++和OpenCV库在VS2010上进行调试,实验采用一段无人机航拍视频图像,图像大小为1920pixel×1080pixel,首先给出本文算法与原始ORB特征匹配算法的效果对比图,如图1所示,进而再进行算法准确性和实时性的分析。

图1 特征匹配算法效果对比图

4.1 算法匹配准确度比较分析

为了验证本文PROMATCH提纯算法的准确性,本文选用航拍视频帧中的5组数据,对没有提纯匹配对,和使用了RANSAC提纯算法以及本文的PROMATCH提纯算法进行对比试验。如表1和表2所示。

表1 特征点匹配对提纯算法对比

表2 不同算法匹配对数目和耗时对比

从表1中我们可以发现,基于穷尽搜索得到的特征匹配对中存在着大量的误匹配,使用了RANSAC提纯算法后将匹配准确度从68.4%提升到了91.8%,但依然存在着大量误匹配,势必对特征匹配的应用带来很大影响,而经过本文的PROMATCH算法提纯后,误匹配对基本接近于零,为特征匹配的后续应用提供了可靠数据。

为了验证算法的实时性,下面将本文的特征匹配算法和传统的SIFT、SURF特征匹配算法进行对比试验,表1是在航拍视频帧中的5组数据上得到的试验结果,我们可以发现：本文算法得到的匹配对数目最多且耗时最低,虽然在特征匹配阶段算法复杂度有所增加,但在处理速度约是SURF的5倍,SIFT的25倍,能够满足实时处理的需求。

5 结 论

针对传统SURF算法实时性不高、ORB算法准确度不够的两难问题,本文提出了一种新的特征匹配算法。首先利用ORB算法快速提取特征点,提出一种新的特征点匹配算法(PROMATCH)消除误匹配点,该方法利用了ORB算法的实时性,并对影响配准准确性的关键步骤——特征点匹配进行了改进,有效滤除了误匹配对,最后通过一段航拍视频图像验证了本文算法的匹配精确度和实时性,下一步拟打算将本文算法运用到复杂场景下的目标检测和跟踪中去。

[1] YAO Siyuan,WANG Xiaoming,WANG Shuai.Fast feature points matching based on SURF[J].Laser & Infrared,2014,44(3):347-350.(in chinese)

尧思远,王晓明,王帅.基于SURF的特征点快速匹配算法[J].激光与红外,2014,44(3):347-350.

[2] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[3] Bay H,Tuytelaars T,Gool L V.SURF:Speeded up robust features[C].Proceedings of European Conference on Computer Vision,2006,1:404-417.

[4] Rublee E,Rabaud V,Konolige K,et al.ORB:An efficient alternative to SIFT or SURF[C].Proceedings of IEEE International Conference on Computer Vision,Washington,USA,2011:2564-2571.

[5] Mair E,Hager G D,Burschka D,et al.Adaptive and generic corner detection based on the accelerated segment test[C].Proceedings of European Conference on Computer Vision,Greece,2010,63(12):183-196.

[6] Calonder M,Lepetit V,Fua P.BRIEF:Binary Robust Independent Elementary Features[C].Proceedings of European Conference on Computer Vision,Greece,2010,63(14):778-792.

[7] Rosten E,Drummond T.Machine learning for high-speed corner detection[M].New York:Springer,2006:25-36.

[8] Harris C,Stephens M.A combined corner and edge detector[C].Proceedings of Alvey Vision Conference,1988:147-151.

[9] P L Rosin.Measuring corner properties[C].Computer Vision and Image Understanding,1999,73(2)：291-307.

[10]Chum O,Matas J.Matching with PROSAC-Progressive Sample Consensus[C]Proceedings of IEEE Computer Society Conference on Computer Vision and Patten Recognition,2005,2:220-226.

[11]LI Junshan,ZHU Yinghong,ZHU Xiaojuan,et.al.Description and matching of self-similarities for IR and visual images[J].Laser & Infrared,2013,43(3):339-343.(in chinese)

李俊山,朱英宏,朱晓娟,等.红外与可见光图像自相似性特征的描述与匹配[J].激光与红外,2013,43(3):339-343.

Feature points matching algorithm based on ORB detection

LIU Wei1,ZHAO Wen-jie1,LI De-jun1，WANG Xiao2,YE Yi2

(1.Department of Aerospace Intelligence,Aviation Univ.of Air Force.,Changchun 130022,China;2.PLA 94891 Troop,Suzhou 215000,China)

As traditional SURF local feature points matching algorithm has low real-time,a new feature points matching algorithm is proposed by using the advantage of ORB feature points detection.First of all,there are a large number of false matching pairs in the original ORB,and these false matching pairs are described by feature points based on K nearest neighbor,and then the feature points in two consecutive frames are bilaterally matched.At last,the consistency is further refined by sequential sampling algorithm.Experimental results show that the match accuracy is up to 99.9% after purification,and the average running time is 0.46 s.Processing speed is about 5 times faster than SURF feature matching algorithm and 25 times faster than SIFT feature matching algorithm,and it can meet the requirements of real-time processing.

feature matching；ORB Detection；local feature

1001-5078(2015)11-1380-05

国家自然科学基金项目(No.61301233);全军军事学研究生课题(No.213JY512)资助。

刘 威(1991-)，男，硕士研究生，主要研究方向为目标检测与跟踪。E-mail：1224337250@qq.com

2015-03-18;

2015-05-28

TP39

A

10.3969/j.issn.1001-5078.2015.11.019