ORB特征匹配(精选五篇)
ORB特征匹配 篇1
运动目标检测在军事制导、航空侦察、视觉导航等领域有着广泛的应用[1]。航拍视频中,背景是动态变化的,且相对背景而言运动目标较小。因此在进行目标检测之前,都需要根据一定的方法进行背景运动补偿,转化到静态场景下的运动目标检测问题,再通过前后帧的差分图像分离出运动目标。
常见的背景运动补偿方法有块匹配法[2]、基于变换域的匹配法[3]和特征点匹配法,而特征点匹配法处理影像的旋转、伸缩等变换更具优势。目前常用的特征点匹配算法主要有:SIFT[4]、SURF[5]和ORB[6]等。 其中SIFT算法是David G.Lowe在2004年提出的一种具有里程碑意义的尺度不变特征变换算法,在多尺度空间提取特征点;SURF算法由SIFT算法改进而来,通过积分图像和盒式滤波器来替代SIFT中的尺度空间分解,大大减少了计算量。但在对实时性要求较高的应用中,这两种算法依然无法满足要求。而由Rublee等人在ICCV2011上提出的ORB算法在保证尺度、旋转不变的基础上,速度较前两种算法有了很大的提高。 作为一种局部不变特征匹配算法,ORB是建立在FAST特征点检测[7]和BRIEF特征点描述[8]的基础之上, 其采用的二进制局部特征描述符的实时性大大优于SIFT、SURF等浮点型局部特征描述符。因此本文将用其解决前后帧图像之间精确匹配的问题。
本文基于ORB特征匹配算法,提出了一种基于改进的ORB特征匹配和差分相乘算法融合的运动目标检测方法。利用ORB算法快速提取特征点,改进其匹配策略消除误匹配点,精确补偿背景运动量,然后用连续四帧图像差分相乘技术和形态学处理技术完整检测出运动目标。与传统的SURF特征匹配算法相比, 本文算法在实时性上有了很大提高;与简单的帧差法和累加帧差法相比,本文算法能够极大消除噪声点。
1改进的ORB特征匹配算法
本文基于ORB匹配的背景运动补偿主要经过以下几个步骤:首先,利用Oriented FAST检测子在相邻帧图像上检测特征点,再通过Rotated BRIEF描述符生产特征点的二进制描述向量。相邻帧图像的特征点的匹配采用汉明距离比值准则,通过最近邻阈值、双向匹配、PROSAC提纯三步消除误匹配,得到相邻帧图像的最佳匹配对进行背景运动模型参数解算。
1.1 Oriented FAST特征点检测
FAST由于其高效性得到了广泛应用,Rosten等人[9]在算法中加入了机器学习和ID3决策树机制提出了一种简单快速的FAST特征点检测算法。文献[9]中,Rosten等人将FAST特征点定义为:图像中某点的灰度值比周围邻域内大多数像素点的灰度值都大或小时,该点为特征点。检测点p周围的16个点,如果有连续12个点的灰度值与点p的灰度值之差大于一定的阈值,则将点p判定为特征点。
我们可以通过一个角点响应函数CRF来判断一个FAST特征点:
其中:εd为阈值,I (x )是待测点邻域内任一点的灰度值,I (p )是当前待测点的灰度值。所有圆周点与待测点的响应函数值的和为N ,ORB算法中N为9,当N大于一定阈值时待测点为特征点。为了使得特征点能适应光照变化,ORB算法首先设置较低的阈值提取多数的特征点,再利用Harris角点[10]的评价函数找到角点响应值较高的前N个FAST特征点;为了使特征点具有尺度不变性,ORB算法使用金字塔算法得到多尺度图像和FAST特征点的尺度特征;为了使特征点具有方向不变性,ORB算法使用灰度质心法[11]为特征点提供一个主方向:找到特征点局部区域内的灰度形心,用特征点到形心的矢量方向来确定特征点的主方向,局部区域矩的公式是:
则这些矩计算特征点区域上的灰度形心为
则质心与特征点的夹角也即FAST特征点的主方向为
有了特征点主方向之后,就可以依据此主方向提取ORB描述子。
1.2 Rotated BRIEF特征点描述
ORB算法中采用BRIEF描述子对检测到的特征点进行描述,并解决了BRIEF描述子不具有旋转不变性的问题。
BRIEF描述子是最简单的一种二进制描述子,其生成过程如下:在图像块内随机生成点对(对数可以是128、256和512),每一个点对对应一个二进制位,定义如下:
其中:p (x)和p(y)是点对的灰度,随机选择n对点就可以生成一个二进制字符串,则生成的特征描述子可以表示为
由于BRIEF描述子比较的是点对的像素值,对噪声非常敏感。为了消除噪声的影响,ORB算法采取如下策略:在特征点邻域的31×31像素区域内随机选取5×5的子窗口,比较窗口的灰度积分来替换点对的像素值。为了解决BRIEF描述子不具有旋转不变性的问题。ORB算法的解决方案是:在特征点上选取n对特征,得到一个2n矩阵:
利用特征点检测得到的主方向确定的仿射变换矩阵Rθ,对其旋转得到新的描述矩阵:
这样就可以得到矫正后的BRIEF描述子:
最后ORB算法通过贪婪搜索的方法选取了相关性较低的256对像素块对进行特征描述。
1.3 ORB特征点匹配
上节中得到的256维ORB特征描述子,为了建立相邻帧图像上特征点的对应关系,我们计算第二帧图像上每个特征点与第一帧图像上全部特征点描述向量的汉明距离,用D(Vp,Vq)表示。
其中Vp是第二帧中某一特征点p的特征向量,Vq是第一帧中最邻近特征点q的特征向量,D(Vp,Vq)越小说明两个特征点越相似,汉明距离最小的即为匹配对。图1给出连续两帧图像基于ORB特征匹配后效果。
1.4一种匹配对提纯的改进算法
从图1中可以发现,图中出现了大量误匹配对,这是因为基于穷举搜索得到的匹配对没有考虑两特征点是否属于同一区域,或者当多个特征点较为接近时也会出现误匹配,如果在背景运动估计中引入了误匹配点,势必会带来很大的误差从而影响动目标检测的正确性。因此需要对算法进行改进,常见的误匹配去除算法——RANSAC,是一种随机参数估计算法,该算法的缺点是随机抽取匹配对,不考虑匹配对的质量好坏,当误匹配对较多时就会对背景运动估计造成很大偏差。为此本文提出一种新的特征点匹配算法—— PROMATCH(Progressive Match),该算法对去除误匹配对提出如下改进策略:
1) 基于K最近邻的特征点匹配对描述
虽然二进制特征描述子采用汉明距离减少了计算量,但采用穷举搜索方法建立匹配对仍然带来了大量重复的计算量,本文基于K最近邻(K—Nearest Neighbour,KNN)算法的思路,对训练样本集进行组织和整理分类,尽可能将计算压缩在接近测试样本邻域的小范围内,避免盲目地与训练样本集中的每一个样本进行计算,在这里K取2,最终为每一个特征点找到汉明距离最小和次小的特征点,假设Vp是某一特征点p的特征向量,Vp是第一帧中最邻近特征点q的特征向量,Vq是第一帧中次邻近特征点q的特征向量,则最终的特征点匹配对可以描述成pi(Vq,Vq)(i=1,2,...,n), n为第二帧中检测到的特征点个数。
2) 基于汉明距离近邻比值准则的双向匹配
第一步:对每一个第二帧中的特征点在第一帧中同时寻找最近邻和次近邻的特征点,将最近邻和次近邻距离的比值作为匹配对质量好坏的定量表示,假设Vp和Vq的距离为D(Vp,V),D(Vp,V)与D(Vp,V)的比值为R ,当R小于某个阈值TR时则接受p与q为正确的匹配对,记作p ←→ q,否则记为p←→q,则基于汉明距离近邻比值准则定义为
本节通过实验确定式(12)中的阈值TR取0.65时在匹配对数量和正确率之间取得最好的平衡。最终得到的特征点匹配对用集合A来表示:A={pi(Vq,V)i=1,2,...,m1},其中m1为从第二帧到第一帧的特征点匹配对的个数。
第二步:对每一个第一帧中的特征点在第二帧中同时寻找最近邻和次近邻的特征点,按照同上的步骤去除R小于阈值TR的误匹配对,最终得到的特征点匹配对用集合B表示:B={qi(Vp,Vp)i=1,2,...,m2},其中m2为从第二帧到第一帧的特征点匹配对的个数。
第三步:遍历集合A中的每一个元素,对于集合A某一匹配对(pi,qj),在集合B中能够找到一个匹配对(qj,pi)与之相对应,则接受该元素,我们将经过双向匹配后得到的特征点匹配对存入到集合C中:,m3为经过双向匹配后特征点匹配对的个数。
3) 基于PROSAC算法去除误匹配
PROSAC算法[12]是RANSAC算法的改进,不是随机抽取匹配对,而是根据匹配对的质量好坏对匹配对进行排序,在模型参数拟合时优先抽取质量较高的匹配对进行迭代估计。这里我们将上一步中计算得到的最近邻和次近邻的比值R作为匹配质量的定量表示,对经过双向匹配后得到的特征点匹配对进行进一步提纯,本文采用的PROSAC算法步骤如下:
1初始设置:迭代次数初值设为0,是否为内点的误差阈值、内点数目的阈值、最大迭代次数。
2若迭代次数小于最大迭代次数,选取样本集中前n个具有较高质量的数据,从中随机取出m个, 计算模型参数,并计算用此模型参数得到的误差小于内点误差阈值的数据数量,即内点数量。若迭代次数大于最大迭代次数,则返回对应内点数量最大的一组内点。
3判定内点数量是否大于设定的内点数目阈值,大于则返回内点,否则迭代次数加1跳转第2步。
经本文算法去除误匹配后得到的效果如图2所示。
2运动小目标提取
2.1背景运动估计模型参数计算
将上节提纯后得到的匹配对代入背景运动估计模型进行解算就可以得到背景的运动信息。
由于运动平台导致图像产生平移、旋转、缩放等变换,综合运算量和描述精度的考虑,本文选用仿射变换模型:
(xk-1,yk-1)T是第一帧图像中特征点的坐标,(xk,yk)T是第二帧中对应的匹配点的坐标,(a,b,c,d,e,f)T参数确定了图像之间的变换关系,6参数模型只需要3组匹配对就可以解算,当得到的匹配对大于3时可以利用最小二乘法模型的最优解。用参数模型对第二幅图像进行变换,得到运动补偿后的图像。
2.2连续四帧差分相乘
理论上对运动补偿后的图像与前一帧进行帧间差分就可以提取出运动目标,但在实际运用中,图像中存在的噪声、光照等影响因素使得帧差后的二值图像中存在噪声点,为此本文采取连续四帧差分相乘的方法[13],隔帧选取连续的四帧图像,以第一帧Ik(x ,y)为参考帧,对后三帧图像进行运动补偿得到补偿后的图像Ik +1(x ,y)、Ik +2(x ,y)和Ik +3(x ,y),给定阈值T可以得到帧差后的二值图像:
则差分相乘后的二值图像可以表示为
经过连续四帧差分相乘处理后,得到的运动目标依然不规则且目标存在小的空洞,且仍有可能存在一些孤立的噪声点,本文利用形态学处理技术[15],对差分相乘后的二值图像进行腐蚀、膨胀处理,最终得到准确的运动目标区域。
3实验结果与分析
实验平台采用Intel Core(TM)2 Duo CPU主频2.5 GHz的PC机,没有任何硬件加速,用C++和Open CV库在VS2010上进行调试,算法准确性和实时性的分析。实验采用一段无人机航拍视频,图像大小为1 920pixels×1 080 pixels,采样频率25 f/s。
3.1算法匹配准确度比较分析
为了验证本文PROMATCH提纯算法的准确性,选用航拍视频帧中的5组数据,对没有提纯匹配对, 和使用了RANSAC提纯算法以及本文的PROMATCH提纯算法进行对比试验,实验结果如表1所示。
从表1中我们可以发现,基于穷尽搜索得到的特征匹配对中存在着大量的误匹配,使用了RANSAC提纯算法后将匹配准确度从68.4%提升到了91.8%,但依然存在着大量误匹配,势必对后续的背景运动估计带来很大影响,而经过本文的PROMATCH算法提纯后,误匹配对基本接近于零,为后续的背景运动估计模型参数解算提供了可靠数据。
3.2算法匹配对数目及实时性分析
为了验证算法的实时性,将本文改进后的ORB特征匹配算法和传统的SIFT、SURF特征匹配算法进行对比试验,表2是在航拍视频帧中的5组数据上得到的试验结果,可以发现:本文的ORB特征匹配算法得到的匹配对数目最多且耗时最低,平均耗时在毫秒级(0.46 s),虽然在特征匹配阶段算法复杂度有所增加,但在处理速度约是SURF的5倍,SIFT的25倍,能够满足航拍视频实时处理的需求。
在ORB特征提取特征点并完成配准后,经过差分相乘和形态学处理后便能完整提取出目标,表3给出了算法各个阶段的平均耗时对比。
从表3可以看出,本文提出的运动小目标检测算法耗时主要体现在改进的ORB特征点匹配阶段和背景补偿阶段,分别占总耗时的79.54%和17.47%,也是影响算法实时性的关键因素,且特征点匹配阶段匹配上的特征点对的准确度将严重影响背景补偿的质量。而从表2可以发现,本文算法正是通过对特征点匹配阶段进行改进,在提高算法实时性的同时提高了匹配对的准确度。
3.3差分相乘目标提取
在配准的基础上,根据前文的连续四帧差分相乘算法,实验数据选用航拍视频中的第1,2,3,4帧图像。
首先进行图像配准,以第1帧作为参考帧图像,分别对后续三帧图像进行运动补偿,第4帧补偿后的图像如图3(b)所示;然后分别对第3帧与第1帧、第4帧与第2帧进行帧间差分,差分结果如图4所示; 最后将两幅差分图像相乘并作形态学处理(如图5所示),得到的二值图像中运动小目标用矩形框表示。从图5中可以发现复杂场景下的运动小目标被准确提取了出来并排除了大量的噪声干扰。
结束语
ORB特征匹配 篇2
摘要:文章主要在限定的特征点提取区域,用改进的SIFT特征匹配算法进行帧图像的并行双向搜索匹配,缩短视频帧图像的匹配时间达到视频拼接的目的。
关键词:SIFT;帧图像匹配;视频拼接
中图分类号:TP391.41文献标识码:A文章编号:1006-8937(2011)22-0070-02
1视频帧图像拼接
1.1SIFT算法
SIFT算法由D.G.Lowe 1999年提出,后来Y.Ke进行完善。主要有四个步骤:第一,建立尺度空间。尺度空间理论的主要思想是利用高斯对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列。为了得到在不同尺度空间下的稳定特征点,主要是构建高斯金字塔和DOG金字塔,然后在DOG金字塔里面进行极值检测。第二,精确定位极值点。由于DOG值对噪声和边缘较敏感,通过上面的方法所检测到的局部极值点还要经过进一步的检验才能精确定位为特征点。通过三维二次函数拟合来精确确定极值点的位置和尺度。第三,特征点指定方向参数。用直方图统计邻域像素的梯度方向,梯度直方图的范围是0~360°,其中每10°一个柱,总共36个柱。直方图的峰值则代表了该特征点处邻域梯度的主方向,作为该特征点的方向。第四,特征向量的生成。在窗口中用箭头方向来代表该像素的梯度方向,箭头长度来代表梯度模值,在窗口上用一个圆圈代表高斯加权的范围。然后在每4×4的小块上计算8个方向的梯度方向直方图,绘制每个梯度方向的累加值,即可形成一个种子点。
1.2SIFT特征向量的匹配
本文采用欧氏距离作为两幅图像间的相似性度量。获取SIFT特征向量后,采用K-D树进行优先搜索来查找每个特征点的2近似最近邻特征点。在这两个特征点中,如果最近的距离除以次近的距离少于某个比例阈值,则接受这一对匹配点。
1.3图像的配准与融合
在上述的SIFT算法过程中获得的特征点和有效匹配对的基础上,进行图像间变换参数估计。以视频图像V1为参照系,将视频图像V2变换到V1所在的坐标系,记变换后的图像为V2',其对应关系如公式(1)所示:
x2'y2'1=t11 t12 t13t21 t22 t23t31 t32 1x2y21=Tx2y21 (1)
式(1)中有8个参数,仅需要四对匹配点即可计算变换图像V2',即V2'=TV2
图像配准后,图像间的变换关系就得到了唯一确定。本文采用加权平均的融合方法进行图像平滑过渡,从而达到图像的无缝拼接。
2实际问题框架
本文主要工作是将倒车时所拍摄的实时视频进行拼接,具体步骤如下:
①获取两组视频同一时刻的帧图像。在汽车尾部对称的两侧安装视角范围大小为60°的摄像头,并在同一时刻分别抓取视频帧图像。
②对同一时刻的帧图像进行拼接。摄像头的位置和角度固定以后,抓取图片的相对位置也就固定,重叠区域也相对固定了,如图 1所示。其中l是车身后面两摄像头之间的距离,L是摄像头与车身后面场景的距离,O点是摄像头视线交叉点,OO1是O点到摄像头的距离,OO3是O点到驾驶员视线范围的距离。重叠区域即A与B之间的部分,其宽度为H,通过公式(2)得到。
(3)
③对拼接好的帧图像按时序进行视频格式的播放。把同一时刻的两张帧图像拼接成的一幅图像,进行校正后按照时序用视频格式输出。此时驾驶员根据视频所反映的车身后面的场景来进行倒车。
3算法优化
3.1特征点提取区域的限定
本文中视频帧图像的拼接是基于特征点的拼接,提取特征点是拼接的关键,为了达到视频拼接的实时要求本文提出选取特征点时只在限定的区域进行,如图2所示。即右边摄像头所获取的视频帧图像其特征点提取区域即为图1中CO2之间的部分,它们之间的距离为l/2,左边摄像头所获取的视频帧图像其特征点提取区域即为图1中O2C'之间的部分,它们之间的距离为l/2。
3.2K-D树优先搜素算法
在SIFT算法中,特征向量的匹配先采用欧氏距离进行了相似性度量,再采用K-D树进行优先搜索来查找每个特征点的2近似最近邻特征点。树的顶层结点按一维进行划分,下一层结点按另一维进行划分,以此类推,各个维循环往复。划分要使得存储在子树中大约一半的结点落入一侧,而另一半落入另一侧。当一个结点中的点数少于给定的最大点数时,划分结束。在SIFT算法中实际运用中是采用的一种K-D树搜索算法基础上改进的搜索算法,即BBF(best-bin-first)算法来搜索样本特征点的最近邻和次近邻特征点,其中BBF搜索算法是在四维空间,即k=4的K-D树基础上用一个优先级队列实现以结点和被查询结点距离递增的顺序来搜索结点,结点和被查询结点的距离是指他们之间的最短距离。
3.3改进的K-D树优先搜素算法
本文提出双向并行搜索的策略,即以特征集A中所有的特征点基准点在特征集B中采用K-D树进行优先搜索,找到与特征点最近邻和次近邻的两点bi1、bi2,如果bi1、bi2之间的距离比值小于某一个设定的比例阈值,则接受这一对匹配点;同时又以特征集B中的所有特征点为基准点在特征集A中采用K-D树进行优先搜索,找到与特征点最近邻和次近邻的两点aj1、aj2,如果aj1、aj2之间的距离比值小于某一个设定的比例阈值,则接受这一对匹配点。如图 3所示。
如果以A中的点ai为基准点搜索时,在B中找到了点bj与其匹配,并且在B中以bj点为基准点,在A中进行搜索时,恰好又与A中的点ai匹配的话,则从A中去除点ai,从B中去除点bj;
算法步骤如下:第一,同时输入特征点集A和B以及集合总数m和n,使i=0,j=0。第二,若i<m或j<n,或n<0,则ai去B中找匹配点,bj去A中找匹配点。第三,若ai找到匹配点bp,bj找到匹配点aq则保存这样的匹配对。第四,从集合A和B中减去已经配对的点,然后进入步骤2。
通过本文改进算法的分析,对两个2×2的特征点矩阵进行匹配,如图 4所示。用改进的K-D搜索策略,A集合与B集合中的特征点是同时进行,即第一步,a1用4次找到b3匹配,同时b1用4次找到a4匹配;第二步,a2用4次找到b2匹配,同时b2用4次找到a2匹配,此时a2与b2双向都匹配上了,所以在A中去除a2,在B中去除b2;第三步,a3用3次没有找到匹配点,同时b3用3次找到a1匹配,此时a1与b3构成了双向匹配上了,所以同时去除a1,b3;第四步,a4用2次找到b1,同时b4用2次找到a3匹配。至此所有的点搜索完毕,K-D树搜索方法共用了16次,而改进的K-D树搜索方法共用了13次。
4实验结果与分析
本实验采用两个设置相同焦距、色度等参数的摄像头,以某场景进行实验。根据上述的理论,通过VC++和Opencv编程实现视频拼接。
参考文献:
基于ORB特征匹配的电子稳像算法 篇3
1 ORB特征匹配算法
1.1 特征检测算子
FAST算法本身不能描述方向信息, 对噪声影响敏感。ORB算法引入了图像矩的方式弥补这一缺陷, 定义公式如下所示:
其中, I (x, y) 表示位于 (x, y) 位置处的图像灰度值, p, q代表图像矩的阶数。为了保证检测特征的旋转不变性, 算法选择一定尺寸的圆形区域作为特征领域, 并计算邻域内所有像素的图像矩, 根据对应矩值得到质心位置C, 将特征点O到质心C的向量方向定义为该位置的特征方向, 计算公式如下所示:
1.2 特征描述算子
ORB算法选用BRIEF算子作为特征描述子, 运算速度非常快。选取图像的一块平滑区域S, 则二进制灰度测试算子的定义如下所示:
其中, S (X) , S (Y) 分别表示位于坐标X (x1, y1) 和Y (x2, y2) 两处的图像灰度值, 对应的BRIEF特征描述子的计算形式如下所示:
其中, n为构成描述子的测试算子数量, 通过选取邻域内n个随机点对即可构造特征描述子。
选用FAST算法中的质心方向作为主方向, 克服BRIEF算子对方向的敏感性, 并依据主方向提取旋转不变描述子。同时, 为了增加算法对噪声的抵抗能力, 将像素到像素的匹配运算改为子块间的运算。
2 电子稳像算法实现过程
电子算法中的运动估计指的是全局运动估计, 即符合图像中大部分背景特征运动趋势的全局一致性参数, 根据这一特点, 对初步匹配结果进行分类优化, 将匹配结果分为全局匹配和局部匹配, 只利用全局匹配坐标求解参数。
2.1 全局运动估计
实拍序列图像匹配结果可能存在部分与全局运动趋势不一致的匹配结果;同时ORB描述子是局部特征的表现形式, 匹配结果中也会包含误匹配特征;这些均不可避免的会影响全局运动参数的求解精度。为了避免集合中初次误匹配特征对参数结果造成的不良影响, 采用两步操作优化初始匹配集合:
(1) 按照匹配距离升序的顺序对初始匹配点对进行排列, 根据需要保留的匹配数量设置距离阈值, 剔除集合中匹配距离较大的点对;
(2) ORB特征的主方向代表了该位置的方向信息, 因此如果两个特征点对是正确的匹配关系, 则对应主方向的差值应该相同, 可以根据这一特点对匹配集合进行再次优化。图1给出了序列Tree加入二次优化前后的图像特征匹配结果。
对比图1 (a) 和 (b) 可以看出, 原ORB特征匹配结果包含了较多的误匹配特征, 而优化后的匹配集合去除了大部分位于局部运动区域的特征点对, 提高了匹配集合精度, 同时减少了匹配过程运算量。
2.2 运动补偿 (表1)
本文仅考虑摄像机静止的情况, 直接采用全局运动参数反向补偿当前图像即可得到的视频序列。以四类序列为实验对象, 分别采用SIFT、SURF和ORB三种特征匹配, 结合迭代最小二乘法求解运动参数。采用图像中心区域的峰值信噪比PSNR评价补偿前后图像的性能。
3 结语
ORB特征匹配算法能有效改善运动估计性能, 同时引入优化算法, 筛选初始匹配集合, 只保留稳定的全局匹配进行参数估计, 降低运算负担的同时降低了局部匹配的不良影响, 提高了全局参数求解精度。对多类抖动序列仿真发现, 算法能有效去除抖动成分, 能提高原始图像的PSNR平均2d B以上。
参考文献
[1]E.Rublee, V.Rabaud, K.Konolige, and G.Bradski.ORB:an efficient alternative to SIFT or SURF.IEEE International Conference on Computer Vision, 2011, .2564-25711.
ORB特征匹配 篇4
同时定位与地图创建是指机器人在未知环境中通过传感器信息确定自身空间位置,并建立所处空间的环境模型,是实现机器人任务规划、导航、控制等自主运动的前提之一。SLAM本质上是一个状态估计问题,可分为两类求解方法[1],一类是基于滤波器的方法,另一类则是基于图优化的方法。基于滤波器的方法采用递归贝叶斯估计,假定从初始时刻t0到时刻t的观测信息以及控制信息均为已知的条件下,对系统状态( 包括机器人当前位姿以及所有地图特征位置)的后验概率进行估计,常用扩展卡尔曼滤波( EKF) 法和粒子滤波( PF) 法[2]。基于图优化的方法则是通过所观测信息估计机器人完整的运动轨迹并构建环境地图。该类方法以位姿图( pose graph) 的形式表达地图特征间的约束关系。图中的节点( node) 对应于机器人在不同时刻的位姿,节点连线构成的图边( edge) 描述了位姿间的约束关系[3],约束关系可通过里程计或观测信息配准得到。通过优化节点位姿,可对位姿漂移以及匹配错误进行修正,最终得到优化后机器人的运动轨迹。肖雄等[4]提出了一种增广扩展卡尔曼滤波( AEKF) SLAM方法,提高了二维地图得以执行与精确度,但该方法只能建立环境的二维地图,缺乏直观的三维描述。文献[5]提出了一种室内环境下的三维环境建模方法,基于GPU-SIFT的算法大幅提高了系统的运行效率,实现了三维环境的建立,但地图效果欠佳且无法实现位姿估计。文献[6-7]中提出的Kinect Fusion使用分层ICP算法将Kinect传感器的深度信息投影到三维空间,实现了立体环境建模,但该算法对硬件要求较高,并不完全适用于移动机器人。Henry等人[8]提出了一种基于Kinect的交互式三维建模重建系统,但由于该系统依赖于关键帧选取,计算量大、时间复杂度高,因此,移动机器人难以实时创建三维地图。
针对上述问题,本研究通过研究特征点提取、帧间配准、闭环检测等算法对传统图优化SLAM方法的影响[9],并提出一种适用于移动机器人的改进RGB-D SLAM框架。为提高图优化过程中的特征点提取匹配实时性,研究并改进ORB ( oriented fast and rotated brief) 特征提取与匹配算法[10]。帧间配准过程,由于初始配准估计不确定的问题导致数据关联错误与配准效率低下,可通过随机采样一致性( random sample consensus,RANSAC ) 与迭代最近点( iterative closest point,ICP) 结合的改进RANSAC-ICP算法防止位姿估计陷入局部收敛。本研究采用基于keyframe的词袋闭环检测算法,可提高闭环检测速度,有效减少冗余地图结构,可生成具有一致性的地图,提高了系统鲁棒性。本研究通过标准数据集测试,验证该SLAM框架可建立具有全局一致性的环境模型与全局行估计,并证实本研究提出的改进算法和系统框架的实时性与鲁棒性。
1ORB特征点检测与匹配
1. 1 FAST算法及其改进
ORB算法通过FAST角点检测提取特征点,其原理描述如下: 检测以图像任意点p为圆心、3. 4 个像素为半径的圆上16 个像素点( 称为M16 模板) 的灰度值,若M16 中有连续n个点的灰度值均大于Ip+ t,或均小于Ip- t( 其中: Ip—p点灰度值,t—阈值) ,则判定p为特征点。为提高特征点检测速率与准确性,笔者采用一种分割测试准,令n为12,只需先检测点1、5、9、13 的灰度值,只有至少3 个点满足上述阈值条件后,才继续检测剩余12 个点。
M16 测试模板如图1 所示。
上述分割准则仅适用于n = 12 的情况,为增强算法普适性,FAST算法引入了机器学习方法,其步骤为:针对指定像素值n与阈值t,使用分割测试准则从图像集中检测出所有特征点,该过程需要检测每个点的M16,将检测过的图像作为训练样本; 随后根据信息增益最大原则使用ID3 算法,训练得到特征点的分类决策树。通过决策树将图像中的点分类为特征点和非特征点。
使用机器学习的FAST角点检测仅比较像素点的灰度值,其匹配效率优于SIFT算法,使用机器学习可增强算法的普适性。指定强度质心( intensity centroid)为旋转方向可得到具有旋转不变性的o FAST( oriented FAST) 描述符。该过程为: 建立以特征点O为坐标系原点,在邻域S内计算质心位置C,以特征点为起点,质心为终点构造向量
邻域S的矩可表示为:
式中: I( x,y) — 图像的灰度值,x,y ∈ [- r,r],r— 邻域S的半径。则该邻域的质心位置为:
到FAST特征点的方向为:
1. 2 r BRIEF算法及其改进
BRIEF是一种以二进制编码为表现形式的局部图像特征描述符[11]。通过BRIEF检测随机响应,可提高描述符的建立速度。BRIEF算法以任意特征点为中心,在像素点面积为s × s的邻域p内定义二进制测试准则:
式中: I( x) — 平滑处理后的图像邻域p在x = ( u,v)T处的灰度值。
对于n个( x,y) 测试点对,可定义唯一的二进制准则,所生成的BRIEF描述子即为n维的二进制码串:
式中: n— 可为128,256 或512,对应描述符的大小分别为16 字节,32 字节和64 字节,根据算法的实时性、存储空间以及识别率进行选择。
BRIEF描述子本身是无向的,不具有旋转不变性。通过对BRIEF描述符施加特征点质心方向 θ,可在一定程度上解决旋转不变性的问题。在点对( xi,yi) 处,对于任意n个二进制准则特征集,可定义2 × n阶矩阵:
式中: ( xi,yi) — 测试点对,Rθ— 以 θ 特征点方向所对应的旋转矩阵。构造出矩阵S的旋转版本Sθ= RθS。通过该方法可得到具有旋转不变性的r BRIEF( rotated BRIEF) 描述符:
r BRIEF描述符向量中点对之间的相关性会增加匹配难度,需要通过贪婪式搜索来减小相关性并对其约束。r BRIEF的图像邻域准仅考虑单个像素点,具有噪声敏感性。为降低噪声影响,本研究对每个测试点均采用像素总值为31 × 31 的邻域中的5 × 5 子窗口内像素点的灰度平均值来代替某点对的点灰度值。具体步骤如下:
( 1) 在某一特征点邻域内计算以子窗口为基础的点对测试 τ;
( 2) 将步骤( 1) 中所有的测试值 τ 根据其与0. 5的差值排序,形成向量T;
( 3) 进行贪婪式搜索:
( a) 将第一个测试点 τ 放入结果向量R中,并将其从向量T中移除;
( b) 从向量T中取一个测试 τ,并将其与向量R中的所有测试值进行比较,如果相关程度大于某一阈值,则将其丢弃,否则将其加入向量R中作为生成描述子的一个坐标;
( c) 重复上述步骤,直到向量R中有256 个坐标为止,形成最终描述子。然后将相关度的阈值增加,再一次检测所选的这些测试值 τ 的相关度,保证最终结果有较小的相关度。
Hamming距离可用于判定r BRIEF特征点是否匹配。生成的r BRIEF特征点描述子为二进制码串,而Hamming距离是通过二进制串的异或运算建立的,因此特征匹配过程简单且运行速度快。采用基于k -树( best-bin-first算法) 的最邻近法可实现r BRIEF特征描述的匹配。通常认为当前特征点与最邻近点的Hamming距离越小,与次邻近点的Hamming距离越大,则当前的r BRIEF匹配质量越好。
1. 3 ORB旋转不变性与实时性验证
本研究使用同样配置的计算机,通过人工旋转并增加高斯噪声,对同一组的测试图像进行比较,比较几种常见特征点提取与匹配算法,其匹配结果可验证改进ORB算法的旋转不变性。各种算法旋转不变性比较如图2 所示,本研究提出的改进r BRIEF算法具有较好的抗旋转性能。
算法的执行时间是评价算法实时性的重要指标。相同硬件条件下,使用Mikolajczyk和Schmid数据集中的ubc图集可验证ORB算子具有较好的实时性,其结果如表1 所示.
2基于改进ORB的SLAM框架研究
2. 1 改进SLAM系统框架
本研究提出的RGB-D SLAM框架是基于图优化的改进方法,其总体框架如图3 所示。该框架分为前端构建、后端优化以及地图表示3 部分。系统前端根据观测和约束信息,通过特征点配准和位姿变换估计可构建位姿图和环境三维点云。
系统后端负责位姿图优化,使输出的地图模型具有全局一致性。传感器噪声、深度值量化的累计误差以及配准错误等因素将导致系统具有不确定性,进而出现位姿和三维地图的漂移。通过闭环检测、随机闭环检测、轨迹优化3 部分共同组成的优化后端,在地图构建过程中对整个地图进行实时更新,加强所生成地图模型的全局一致性。
2. 2 SLAM系统前端
RGB-D传感器通过联合标定后,可得到彩色相机与深度相机的内参数以及两者之间的刚体变换,通过视差补偿模型可校正深度相机的畸变。RGB-D相机可同时获得环境的彩色信息与深度信息,对两组相机的视角进行调整可获得信息一致的图像,从而得到在同一视角下的彩色图像序列IRGB和深度图像序列ID。
RBG图像与深度图像联合标定前、后比较情况如图4 所示。
从联合标定的IRGB和深度图像ID中可获得坐标为( u,v) ,深度值为d的像素点p( p = [u,v,d]T) ,通过如图5 所示的相机投影模型,可建立与图像点p对应的空间点P的坐标:
式中: fx,fy— 相机在x、y轴的焦距,cx,cy— 相机的光圈中心,可通过相机的内参矩阵得到; s— 深度图的缩放因子,通常设置为1 000。通过上述方法,可得到单帧的三维彩色点云图。
RGB-D相机模型如图5 所示。
本研究通过ORB算法从IRGB中提取匹配特征点,特征点描述子d ∈ R64以y ∈ R3的形式存储,可得观察位置( x ∈ R6) 与观测信息之间的几何关系。
本研究通过ORB特征点图像的帧间变换可实现帧间配准,将不同观测坐标系下的特征数据转换到全局坐标系中,从而实现机器人的位姿变换估计。
帧间配准常采用ICP数据关联方法,在迭代过程中,通过不断修正图像间的对应关系与相对变换矩阵,直到收敛至局部最优。因此,初始值的选取决定了优化结果过程是否会陷入局部最小值。为防止陷入局部最优,本研究采用RANSAC与ICP相结合的改进RANSAC-ICP配准算法。视觉特征和与之相关的深度值进行初始化配准,可增强收敛性能。随后通过优化对齐稀疏特征点匹配和密集点云,其流程图如图6所示:
本研究通过RANSAC粗配准可得到相对变换T( p) 将作为RANSAC-ICP的输入。T( p) 函数表示对点p进行刚性变换,则T ( p ) = Rp + T。RANSAC-ICP最终输出为最优相对变换T*( p) 。
Extract_RGB _ Point _ Featrures函数分别可从待配准帧与参考帧中提取稀疏的ORB特征点云Ps、Pt。随后使用RANSAC算法从两组特征点云中找到初始的刚性变换T( p) ,通过在两帧之间找到匹配的特征完成刚性变换初始化。随后,通过重复采样,可以确定特征点的内点数,变换后内点数最大的变换即为最优变换,使最终转换结果更加准确、有效。
步骤( 4 - 6) 为基于最小二乘法的ICP配准算法。该算法选择对应点对进行迭代计算,计算最优刚体变换估计,直到满足配准的收敛精度。其具体步骤描述如下:
( 1) 计算Ps中的每一个点在Pt点集的最近对应点;
( 2) 求得使上述对应点对的平均距离最小的刚体变换T*:
( 3) 对Pt使用上一步求得的平移和旋转参数,得到新的变换点集;
( 4) 如果新的变换点集与参考点集满足平均距离小于阈值时,则停止迭代计算; 否则新的变换点集作为新的Pt继续迭代,直到满足目标函数的要求为止。
2. 3 SLAM系统后端
闭环检测是图优化方法中至关重要的一部分[12],是指根据传感器信息判断机器人是否处在已访问过的场景。正确的闭环检测能够修正由传感器的累计误差带来的地图非一致性问题; 错误的闭环检测则会对后续图优化造成影响,甚至在更新过程中损坏已构建的地图模型,导致地图创建失败。闭环检测与地图创建关系图如图7 所示。
关键帧选取为闭环检测中基础的问题之一,合适的关键帧( keyframe) 能够提高算法的实时性与计算效率,其选取过程为: 当前帧与上一关键帧通过RANSAC进行配准,如果配准内点值小于规定阈值,则认定其为关键帧,数学描述为:
式中:Fkj—离j时刻最近的关键帧,Fj—当前帧。
闭环检测算法通过视觉词袋模型( Bag-of-Words,Bo W) 将关键帧的ORB视觉特征聚类,采用视觉词典( Visual vocabulary) 将特征描述子映射为视觉单词,通过对比关键帧中的“单词”,可判断关键帧间是否形成闭环。闭环检测中大闭环与随机闭环在位姿图中的示意如图8 所示。
图优化是SLAM后端中的核心部分,通过减少轨迹估计中的漂移减少轨迹扭曲。通过位姿图的进一步优化可增强鲁棒性。通过最小化误差函数F( x) 可得到优化位姿图,该误差函数为:
式中: x = ( x1T,…. ,xnT) ,T— 机器人的位姿信息集合; zij— 位姿xi和位姿xj之间的约束即从xi到xj的变换矩阵; Ωij— 位姿xi和位姿xj之间的信息矩阵;e( xi,xj,zij) — 由位姿xi和位姿xj组成的边所产生的误差函数,它代表了xi和xj满足约束条件zij的程度。当xi和xj完全满足约束条件zij的时候,则e( xi,xj,zij)=0。
3实验结果与分析
为了验证本研究中所提出的keyframe的词袋闭环检测算法的后端优化机制能否有效减少了冗余地图结,生成具有一致性的地图,提高了系统鲁棒性,笔者采用了部分NYUv2 中的数据集作为测试数据[13]。NYUv2 测试集优化前后对比图如图9 所示。未采用Key Frame词袋闭环检测算法的环境地图如图9 ( a) 所示,与经过处理的图9( b) 相比,其生成的点云信息模糊且全局一致性较差。
该数据集包含有动态物体( 人) ,对所生成的环境地图影响较大,采用优化算法的SLAM可从连续帧中分辨出动态物体,并加以处理,所生成的点云图具有清晰的运动物体轮廓,为今后研究中的动态物体识别处理提供了先决条件。其对比如图10所示。
本研究改进的SLAM框架运行在配置为Inte( R) Core i5-3210M 2. 5GHz和4GB RAM的Ubuntu12 . 04 平台上。 为验证本研究提出的基于改进ORB算法的SLAM系统框架的实时性与鲁棒性,笔者使用基于Computer Vision Group的数据集进行验证实验[14]。该数据集由Microsoft Kinect传感器以30 fps,分辨率为640 × 480 的图像采集室内的彩色信息与深度信息,具有8 台高速跟踪相机( 100 fps)的高精度运动捕获系统获取传感器运动的真实路径。最终,本研究通过绝对轨迹误差( ATE) 的均方根误差( RSME) 以系统可靠性。测试传感器、手持传感器及机器人自带传感器3 种典型应用场景下的共9 组数据集如表2 所示,本研究分别对SLAM框架进行了可靠性与实时性验证。
从不同角度观测到的复杂室内环境地图与运动位姿图如图11 所示。
由不同数据集得到的系统可靠性与实时性的测试结果如表3 所示。
在复杂的室内环境下,本研究在传统RBG-D SLAM框架的基础上[15],实现了接近实时的构建出环境模型并完成定位。在复杂室内环境下,由于RGB-D摄像头深度值的有效范围仅为3. 5 m,且不能精确较远的深度对象,导致三维点云建立过程中出现匹配错误。上述5 个典型数据集,其深度误差值与环境结构复杂度依次增大,结果表现为绝对轨迹误差的均方根误差递增。通过处理时间可知,本研究提出的改进SLAM框架能够在传感器有效范围内,其三维构建模型的绝对轨迹误差为厘米级别,建立速度均在20 帧左右。通过keyframe词袋闭环检测算法的后端优化算法能够有效降低动态模型的影响,建立轮廓清晰的环境模型。上述实验结果表明,使用改进ORB算子与RANSAC-ICP配准算法可减小绝对轨迹误差,提高匹配速度。闭环检测算法能够弥补ORB算子特征匹配对较少的缺陷,在保证建立速度的同时,可增强建模稳定性,对将来的导航与多传感器信息融合SLAM有很高的研究价值。
4结束语
机器人环境模型构建与自定位是实现机器人自主导航的前提,针对室内复杂环境,本研究在基于图优化方法的基础上,提出了一种改进的SLAM框架。该框架采用RGB-D相机作为传感器,使用改进ORB算子能够在较短时间内完成彩色图像的特征点提取与匹配,降低了计算复杂度; 借助相机投影模型与深度值信息,能够快速建立单帧立体图像。通过改进RANSACICP结合算法避免了由初始配准不准确导致的陷入局部最优问题,提高了机器人在运行过程中构建模型的鲁棒性; 通过Key Frame词袋闭环检测算法的后端优化算法,能够有效减少冗余地图结构,降低轨迹漂移扭曲,提高地图模型一致性; 基于标准数据集的实验结果验证了该框架的系统鲁棒性与实时性。
下一步计划通过以下几个方面对系统进行改进:
( 1) 采用动态物体识别滤波技术,将环境中的动态物体进行滤波,使生成的地图进包含环境静态信息;
( 2) 通过多线程并行技术与GPU并行技术,将图像处理与数据处理分离,提高建模的速度;
( 3) 引进多传感器融合技术,将二维激光传感器与IMU相融合,进一步提高深度值的范围与精度,增强SLAM系统的鲁棒性。
摘要:针对复杂环境下机器人的同时定位与地图构建(SLAM)存在实时性与鲁棒性下降等问题,将一种基于ORB特征点的关键帧闭环检测匹配算法应用到定位与地图构建中。研究并分析了特征点提取与描述符建立、帧间配准、位姿变换估计以及闭环检测对SLAM系统的影响,建立了关键帧闭环匹配算法和SLAM实时性与鲁棒性之间的关系,提出了一种基于ORB关键帧匹配算法的SLAM方法。运用改进ORB算法加快了图像特征点提取与描述符建立速度;结合相机模型与深度信息,可将二维特征图像转换为三维彩色点云;通过随机采样一致性(RANSAC)与最近迭代点(ICP)相结合的改进RANSAC-ICP算法,实现了机器人在初始配准不确定条件下的位姿估计;使用Key Frame的词袋闭环检测算法,减少了地图的冗余结构,生成了具有一致性的地图;通过特征点匹配速度与绝对轨迹误差的均方根值对SLAM系统的实时性与鲁棒性进行了评价。基于标准测试集数据集的实验结果表明,ORB关键帧匹配算法能够有效提高SLAM系统建图速度与稳定性。
ORB特征匹配 篇5
进入21世纪以来, 伴随着科学技术尤其是信息技术的发展, 集信息技术、计算机科学技术、数据通信技术、多传感器信息融合等技术于一体并结合了人工智能方面理论的智能交通运输系统已经成为了海内外研究的热点问题。通过计算机视觉系统来采集交通场景的环境信息是智能交通系统中获取外在信息的重要渠道, 而交通场景中的道路标志包含着重要的交通信息[1,2]。如何快速准确并且鲁棒性地识别交通标志是智能交通系统中的关键技术, 对无人驾驶汽车和智能辅助驾驶系统的设计也有非常重要的现实指导意义。
交通标志识别一般分为交通标志检测与交通标志识别2个部分:交通标志检测阶段一般是利用交通标志特殊的形状和色彩特征检测出可能包含有交通标志的区域并对其定位, 然后将检测出来的交通标志区域进行大小归一化, 以方便交通标志识别的处理;识别阶段是准确理解图像所包含的语义信息[3,4]。目前在识别技术领域中常用的方法为:①最近邻方法[5]。曲仕茹, 张超提出了一种基于双向二维的主成分分析的交通标志识别算法。首先, 对交通标志图像进行去噪归一化等预处理。然后, 进行水平和垂直方向的投影, 通过特征空间降维提高匹配速度。最后, 利用最近邻法进行分类。②径向基函数方法[6,7]。径向基函数是取值仅仅依赖于离原点距离的实值函数, 这种方法的本质是降维映射, 因而在交通标志的识别分类中获得应用。③神经网络方法[8,9]和支持向量机 (SVM) 分类[10]。黎群辉, 张航提出采用改进概率神经网络进行交通标志图像识别的新方法, 整个算法分两步实现:首先对交通标志图像提取它的不变距并作为图像的特征;然后采用改进的概率神经网络进行识别。支持向量机SVM与神经网络类似, 都属于学习型的机制, 但是与神经网络不同的是SVM使用的是数学方法和优化技术。④基于模版匹配方法[11]。这是一种比较常用的交通标志识别方法。做法通常是根据有交通标志的图像区域与模板图像之间匹配成功的特征点对来识别交通标志和模板之间的信息, 匹配方法操作较简单, 但是识别的结果会受图像的扭曲、部分遮挡等的影响比较大。以神经网络或SVM为代表的分类方法识别交通标志效果很好, 但是需要在训练阶段 (即离线阶段) 收集大量的交通标志图像样本, 学习不同类别交通标志之间的差异性来取得最佳的分类识别效果。同时如果需要识别新的交通标志, 必须收集相应的新样本图像重新进行学习, 所以, 前期处理过程的工作量巨大。
近些年来, 基于局部特征匹配的方法逐渐受到关注, 这类方法主要思想是提取图像中的SIFT[12,13]或SURF[14,15]等特征点的描述符, 通过加上一定的鲁棒算法选取正确匹配的SIFT或SURF特征向量集来识别交通标志。 不论是SIFT还是SURF算法在提取描述符进行特征点匹配时都存在耗时非常严重的现象, 在此基础上, 笔者用实时性很高的ORB[16]特征描述向量进行交通标志的匹配识别, 创造性地将ORB局部描述算子应用成全局描述算子, 将图像预处理成一个Patch (63*63像素) , 生成中心点的二进制描述符, 以此生成特征点的训练数据库, 利用KNN最近邻匹配算法检测出交通标志。成功检测出来的交通标志加入训练数据库以扩大训练器容量, 为下一次的交通标志识别提供更多的信息保证。
1 笔者算法
针对SIFT和SURF算法在实时处理上的不足, Ethan Rublee, 等人在ICCV2011基础上提出了ORB (oriented Fast and rotated BRIEF) 特征检测算子。在运行效率上有了极大提升。ORB算法是建立在著名的FAST特征检测和2010年由Calonder等人提出的BRIEF特征描述子基础上。FAST和BRIEF运行速度都非常快, 这使得ORB在速度上具有极大的优势。根据文献[16], ORB的处理速度是SIFT算法的100 倍左右, SURF算法的10倍左右。
基于ORB全局特征的交通标志识别算法主要分为3个步骤:特征点检测, 生成中心点的二进制描述符, KNN最近邻分类匹配。
1.1 ORB算法
ORB算法采用的是FAST算子检测图像中的特征点[17], 该算法检测的角点定义为:在像素点的周围邻域内有足够多的像素点与该点处于不同的区域。应用到灰度图像中, 即有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值。这种检测方法的明显优势在于其检测的速度非常快, 然后利用图像矩给检测到的特征点加上方向信息, 构成oFAST, 解决了FAST算子不带有方向性的不足。
一般选择以任意1个像素点为圆心的圆形区域作为该像素点的邻域。如图1所示, 图1中为待判断P点和以P为中心的一个半径等于3的离散化的圆。对P点的判断过程如下:将P点的灰度值和它邻域内16个像素点的灰度值进行比较, 若圆圈上存在n个连续的像素点的灰度值大于P点的灰度值+t (t是阈值) 或者小于P点的灰度值-t, 则我们称P点为被检测到的角点特征。
这里n通常取9、10、11、12等值, 实验证明, 当n取9 时效果最理想, ORB算法中采用的是FAST-9。特征点的主方向是通过矩 (moment) 计算而来, 公式如下:
质心为:, 特征点方向为:θ =arctan (m01, m10)
ORB中采用BRIEF描述子对oFAST检测到的特征点进行描述, 并给BRIEF添加1个方向构成rBRIEF[18], 解决了其本身不具有旋转不变性的首要不足。BRIEF描述子计算简单, 快速, 它的基本思想是:图像邻域 (patch) 能够用相对少量的强度对比来表达。定义S×S大小的图像邻域P的τ 准则:
式中:p (x) 为平滑后的图像邻域P在x = (u, v) T处的像素灰度值。
选择nd个 (x, y) 位置对, 唯一的定义了二进制准则, BRIEF描述子就为nd维的二进制比特串:
nd可以定义为128、256、512等。选用不同的数值需要在速度存储效率和识别准确率之间作出权衡。BRIEF本身是无向的, ORB解决的办法是在位置 (xi, yi) 处, 对任意n个二进制τ准则, 定义一个2n矩阵:, 使用邻域方向θ和对应的旋转矩阵Rθ, 构建S的校正版本Sθ=RθS, 于是Steered BRIEF描述子就为:
得到Steered BRIEF后, 执行暴力贪婪搜索, 从所有可能的Patch中找到256相关性最低的像素块对, 即得到最终的rBRIEF。
1.2 基于ORB算法的全局特征提取
ORB是一种局部描述算子, 通常用于图片局部特征的匹配, 笔者创造性将其应用成全局描述符。其核心思想是把输入的交通标志图像首先通过归一化处理, 变成统一大小。笔者设置标准的图像大小为63×63 (像素) 。取图像中心点坐标 (31, 31) 作为特征点, 以生成的标准图像作为ORB的1个图像块, 从而生成ORB中心点特征描述符。因为ORB作为局部特征算子具有非常好的特征表征性能, 因此利用ORB作为全局特征亦具有非常好的表征能力用以描述交通标志的全局特征。
图2显示了对一个典型的交通标志进行归一化处理, 然后利用ORB算法提取的全局描述符, 全局描述符为256位二进制数字, 即为8个字节, 每个字节为8位二进制数字。缩放后的交通标志图像大小虽然有一部分信息丢失, 但是包含了整个原图像的基本内容。对这样处理后的交通标志图像提取它的ORB特征点与生成相应的描述符, 这样的特征点与其描述符包含了原图像的整体信息, 即称之为ORB全局特征点 (Holistic Feature) 与全局描述符 (Holistic Descriptor) 。这样做的优点在于:
1) 把握了整体图像特征, 有利于在匹配阶段排除局部特征匹配不上的情况;
2) 由于每幅图像生成1个全局的特征, 在匹配识别时只需要每幅图像匹配1次, 极大的提高了识别效率。
1.3 基于最近邻 (KNN) 的交通标志识别
在提取的ORB全局特征的基础上, 笔者提出利用最近邻法 (KNN) 的交通标志识别算法, 整个算法过程可以分为训练与识别2个阶段。
1) 生成训练数据库。 对20 组交通标志共200张图像进行图像的ORB全局特征提取与生成ORB全局描述符, 描述符即为256位的二进制数字, 将这些描述符依次储存起来, 以生成交通标志匹配的训练数据库, 通过查询训练数据库可以看到每一类交通标志中每一张训练图像的全局描述子。
2) 描述子之间的匹配用海明距离来表征。对所计算的两串256 位的二进制数字取异或 (XOR) 操作即来计算海明距离, 海明距离通过位运算即可完成计算, 因此ORB算法在匹配过程中具有非常高效的计算速度。
3) 用KNN最近邻算法进行交通标志的匹配。对用来测试的交通标志图像提取其ORB全局描述符, 通过暴力贪婪的方式在训练数据库中找出与其海明距离最近的K个ORB全局描述符 (通过实验笔者确定K取5较为合适) , K个样本中大多数ORB描述符属于数据库中的某一交通标志分类, 则该测试的交通标志也属于这个分类, 如图3。青色的圆圈代表测试用的交通标志图像, 三角形和正方形代表与青色圆圈距离最近的ORB全局描述符对应的训练数据库中的某2类, 由于5个样本中三角形所占的比率最大, 即该圆圈属于三角形的类中。
2 实验结果与分析
2.1 实验数据及其预处理
笔者实验数据全部来自著名的交通标志公开图像库GTSRB[19]。在GTSRB中, 选出了20组生活中最常见的不同类型的交通标志作为分类对象 (见图4所示) 。这些交通标志包括限速标志、禁止停车标志、车辆让行标志等等, 按照1-20组顺序排列如图4, 每一组中随机选取10张来自不同场景下的同一种交通标志图片, 共200张图片作为训练数据库;在GTSRB同一组数据中随机选出另外5张, 同样是20组作为后续测试数据。
为提高笔者算法的有效性, 排除一些无关的错误干扰, 要求实验图片中交通标志占图形整个面积的80%以上, 事实上, 这在交通标志检测中很容易实现。其次, ORB特征提取是在图片中不同的图像块中进行的, 笔者拟将图片整体作为ORB算法提取的一个图像块, 构造图片全局特征, 将图片大小归一化处理, 统一缩放为63×63 (像素) 大小, 如图5, 其中上面的原图是缩放标准相同的, 可以看到其图像像素大小是不同的, 下面5张图片是与之对应的统一缩放后的63×63 (像素) , 为方便观察, 将其放大显示。
2.2 实验方法
笔者算法流程图如图6, 具体计算过程概括如下:
1) 对训练图片进行预处理, 灰度图方式载入, 并将图片大小归一化生成一个图像块;
2) 提取图像块中心点的ORB特征点, 并生成256位的ORB全局描述符;
3) KNN聚类分析生成训练数据库;
4) 载入检测图片重复 (1) 、 (2) 步骤;
5) 将检测图片和训练数据库中的图片进行匹配, 暴力贪婪地找出匹配距离最小的5个匹配点, 并分析5个匹配中所占比率最大的一类, 所检测的图片即属于那一类交通标志;
6) 若成功检测将检测到的图片储存至训练数据库中, 从而扩大数据库容量, 提高检测准确率
2.3 实验结果与分析
实验中所用训练数据总共为200张图片, 分为20组不同类别;测试图片为100张, 同样是20组不同类别。根据KNN最近邻判定交通标志识别准则, 在图7中左边的图像中, 测试图片类13在所检测出的5张训练类图片中, 占有大多数的训练图片属于类13, 即测试图片识别结果为类13, 正确识别出来;对于图7右边的图像中, 测试图片类15在检测出来的训练类中为类13居多, 错误地将类15识别为类13。
为了对交通识别结果进行详细分析, 将不同类别交通标志的识别结果用混淆矩阵 (con-fusion matrix) 来表征, 其结果见表1所示。混淆矩阵在图像精度评价中, 主要用于比较分类结果和实际测得值, 混淆矩阵是通过将每个实测像元的位置和分类与分类图像中的相应位置和分类像比较计算的。混淆矩阵的每一列代表了测试图片的信息, 每一列中的数值等于测试图片在训练数据库对应于相应类别的数量;混淆矩阵的每一行代表了测试图片的分类信息, 每一行中的总数量等于测试图片相应类别中的总数量。
即如果测试图片某一组图像在对角线上的像元数目占该组类别总数的比率越大, 识别越准确。此外, 我们还针对算法的综合性能进行了测试, 包括算法总体识别率, 算法计算时间。同时我们用BOW (bag-of-words) 算法[14]进行对比实验验证。BOW模型在图像训练阶段主要是用Kmeans方法将图像的ORB局部描述子进行聚类, 形成一系列的频率分布的码书 (codebook) , 然后将每幅训练图像向码书进行投影, 得到不同图像块在不同码字的词频分布, 即词袋 (bag of words) ;在测试阶段, 用KNN算法提取出测试图像词袋和训练图像词袋间的欧式最小距离, 距离最小的类别即为交通标志所属的类别。笔者算法和BOW方法2种算法的性能对比如表2所示。
由实验结果可知:
1) 在表1中, 绝大部分测试图片分类显示在对角线上, 即能够正确识别相应的交通标志, 表2显示交通标志识别准确率在91%, 算法具有较好的识别能力;
2) 从表1中可知, 类2, 类3, 类10, 类12, 类15的识别准确率分别为60%, 80%, 80%, 80%和20%;其余的识别准确率均为100%。对类15来说, 类15被错误识别成了类17 和类13, 我们将两类图片拿出来对比一下, 如图8:中间为类15中的测试图片, 左边为训练图像类17中的图像, 右边为训练图像类13中的图像。可以发现, 中间的图片从纹理上比较接近于右边的图片, 而从形状上比较接近于左边的图片。从而造成了类15在识别上被误认为是其他的交通标志。
3) 算法具有非常高效的计算性能, 在低配置的普通计算机上, 从ORB特征提取到交通标志识别等过程全部运算时间小于2ms, 明显高于同类交通标志识别算法。其主要原因是ORB在匹配过程中全部用位运算, 计算效率得到极大提升。
3 结束语