基于ORB特征的误匹配点剔除算法*

赵 辉， 于春梅,2

(1.西南科技大学 信息工程学院，四川 绵阳 621010；2.特殊环境机器人技术四川省重点实验室， 四川 绵阳 621000)

0 引 言

特征点匹配在机器人领域中有着广泛的应用[1,2]，其中,ORB算法的效率，是SIFT和SURF的10倍以上。ORB算法结合了FAST特征点检测与BRIEF特征描述子，并在此基础上作出了改进，具有了旋转与尺度不变的特性[3～6]。但特征点在匹配过程中不可避免地存在着误匹配[7]。对此，人们提出了很多相关的误匹配点剔除算法。文献[8]结合ORB与SURF算法，提取了SURF-ORB特征点，并对图像进行分块处理，然后通过Hamming距离进行初步剔除，再结合顺序采样一致性[9](progressive sample consensus,PROSAC)算法进一步剔除；该算法具有一定的准确性及实时性，但是在Hamming初剔除阶段，没有通过实验设计选取最优阈值，因此后续阶段的处理未能得到最优点对。文献[10]采用K最近邻算法，对前后2帧特征点进行双向匹配，再通过PROSAC算法进一步提纯，该算法具有较高的精度且具有一定的实时性，但是算法未能运用在复杂场景下，对光照变化以及噪声影响下未做相应分析，有一定的不足。文献[11]虽然在算法中融入了特征点周围的灰度信息，但是也仅仅涉及了特征点周围区域的灰度整体信息，如方差、均值等。特征点周围的局部区域相对较为稳定，是可以充分利用的信息。

本文在ORB特征的基础上，针对匹配过程中存在的大量误匹配点对[12]以及上述文献中的不足，提出一种新的特征点误匹配剔除算法并做了补充实验，相较于传统的随机采样一致性[13](random sample consensus,RANSAC)算法，提高了图像特征点匹配的准确性。

1 ORB特征点匹配

1.1 特征点提取

1)在图像中选取像素点p，比较p和以p为圆心半径为3的圆周上16个点的灰度值的大小，若差值足够大的点数超过设定的阈值，则认为p为角点[14]。2)计算FAST角点Harris响应值并进行排序，选取前N个点。3)构建尺度金字塔，在金字塔上的每一层检测角点，对特征点添加尺度的描述。

局部区域矩为

(1)

质心为

C=(m10/m00,m01/m00)

(2)

特征点的方向为

θ=arctan(m01/m10)

(3)

1.2 特征点描述子

ORB算法采用rBRIEF描述子对检测到的特征点进行描述。其基本思想是：根据高斯分布，在特征点周围31像素×31像素的邻域内，选取n对5×5的子窗口，比较2个窗口的灰度积分值[15]，从而对特征点进行描述。表达式为

(4)

式中Ip，Iq为角点邻域内p和q的窗口灰度函数，则n对子窗口比较而形成描述子的计算为

(5)

式中n的取值可以为128,256等。

ORB算法将角点方向作为BRIEF描述子的方向，使其具有了旋转不变性。定义一个2×n的矩阵K为

(6)

对K矩阵进行旋转变换得到新的矩阵

(7)

所得描述子结果为

gn(P,θ)=fn(p)|(pi,qi)∈Kθ

(8)

1.3 特征点匹配

得到待匹配2幅图像中的所有特征点描述子后，分别计算出一幅图像中每一个特征点的描述子到另一幅图像中每一个特征点的描述子的Hamming距离，Hamming距离越小，即两个特征点越相似[16]，当汉明距离小于一定阈值时，即认为两个特征点匹配。

2 匹配点对提纯的算法

2.1 粗剔除

根据汉明距离初步剔除误匹配时，选择阈值过小则剩余的匹配点对数量过少，不利于后续图像处理；阈值过大则剩余的误匹配点对较多，后续工作误差过大。本文通过设计实验选取一个合适的阈值。

根据Hamming距离定义，对于任意一个阈值T，可以得到最大距离dmax与dmin最小距离，定义一个变量s和匹配正确率p

T=s(dmax+dmin)，p=nture/nall

(9)

通过控制变量法，改变s的值，并统计每一次总匹配点对数nall和正确匹配点对数nture，根据所得的结果绘制出折线统计图，分析并确定变量s的最佳值。采用该最佳值对匹配点对进行重新筛选，将所得匹配点对记为粗略匹配点对，进行精剔除。

2.2 精剔除

为更好地利用特征点周围的像素信息，对剩下的匹配点对，以特征点为中心，定义5×5的窗口，计算窗口外层16个像素点与特征点像素值的差值，差值ri=|g(p)-g(xi)|，i=1,2,…,16,其中，g(p)为特征点p的像素值，为了进一步反映p的特征，构造特征点p的16×16邻接矩阵A，其元素

(11)

因A是一个实对称矩阵，故对A进行奇异值分解，可获得16个实特征值

λ1(p)≥λ2(p)≥…≥λ16(p)

(12)

定义P=[λ1(p)/‖λ‖,λ2(p)/‖λ‖,…,λ16(p)/‖λ‖]为特征点p的描述向量，同理，与p相匹配的点q的描述向量为Q=[λ1(q)/‖λ‖,λ2(q)/‖λ‖,…,λ16(q)/‖λ‖]。其中，‖·‖为L—2范数。

由空间矢量的余弦定理可知

r=cosθ=P·Q/‖P‖‖Q‖

(13)

式中 cosθ的取值范围为[-1 1]，也即当值越接近1，则两个向量越相关。设定一个阈值ST，当r>ST时，保留该匹配点对，否则剔除。将所有点对计算对比后，得到最优点对集。

算法流程如下：

1)采用ORB算法分别对待匹配图像A、B进行特征提取，根据Hamming距离采用暴力匹配算法对2幅图片进行匹配。

2)构造阈值函数T=s(dmax+dmin))和匹配正确率函数p=nture/nall，随机选取9组图片，改变系数s的值，统计并分析变化曲线图，选择最优s值。

3)若Hamming距离小于阈值T，保留匹配点对，反之则剔除。保留的特征点对进入下一阶段计算。

4)根据特征点及邻域点像素值，构造差值矩阵，对差值矩阵进行奇异值分解，重新描述特征点。

5)根据空间矢量余弦定理，当r值大于一定阈值时，判别是正确匹配点对，反之,则剔除。最终得到正确匹配点对。

2.3 算法性能分析

1)旋转不变性:文中的特征向量主要是利用特征点的邻域点像素值构造差值矩阵，通过对该矩阵进行奇异值分解获得由奇异值组成的描述向量，而该矩阵的奇异值分解具有置换不变性，因此该特征描述具有旋转不变性。

(14)

3 实验结果分析

本文实验的编程环境为Microsoft Visual Studio 2013，操作系统采用的是Windows7 64位[Intel(R)Core i5—2430M CPU 2.4 GHz，4 G内存]。

实验1：s的最优值选取。将18张不同角度的图片随机分成9组进行试验，s值取0.1～0.9，改变s值并统计匹配正确率。实验的最终目标是确定一个s值使匹配在获得较多匹配点对的同时最大化正确匹配率。图1为s值的变化曲线。

图1 不同s值与p值的变化

从图1可以看出，当s在0.1～0.4之间不断增大时，p值变化较慢且值普遍在0.9以上。当s在0.4～0.5之间时，变化幅度较大，在0.5之后又开始趋于平缓，因此，取s=0.45作为最优值。用测试组10进行阈值测试，结果表明,当s取0.45时，正确率p为94.6 %，满足要求。

实验2：改进算法与RANSAC算法效果对比。为了验证改进算法可以有效剔除误匹配点对，对2张位于不同位置角度的图片作对比试验，如图2。

图2 不同算法剔除效果比对

对比各组图像可以看出，新算法下的粗剔除可以有效地剔除大部分错误的匹配，为精匹配减少了计算量。而对比精匹配与RANSAC的效果发现，两者的剔除效果都比较好，但新算法剩余的点对较RANSAC算法剩余的点对具有多样性与灵活性。

为了更加精确地比较两种算法的准确度，随机选取5组不同环境下的图像对，并对其进行编号。对比各组采用RANSAC与新算法下的剔除结果，结果如表1。可以看出，RANSAC算法的精确度为90.99 %，而新算法的精确度高达98.97 %。

实验3：窗口大小对剔除精度的影响。若仅仅利用特征点及其周围16个领域点来构造差值矩阵，则对特征点的描述也不完全充分。因此，可取以特征点为中心(2n+1)×(2n+1)的窗口构造差值矩阵，则对应的矩阵阶数为8n，n=1,2,…,k，但当n的取值较大时，则矩阵的奇异值分解需要很高的计算代价。随机选取5组图像进行匹配，改变窗口的大小，统计每一次的正确数，表2反映的是随着窗口的变化，剔除的精度的变化。

从表2可以看出，随着窗口的变大，匹配点对的精度也在增加，当窗口大小为15×15时，匹配精度达到99.12 %，因此，本算法在误匹配点对的剔除应用中具较好的效果。

表2 窗口大小与匹配精度的变化对比

4 结 论

通过选取合适的Hamming阈值，再构造并求解像素差值矩阵用以重新描述特征点，消除了直接用二进制方法难以剔除的误匹配点对，同时该算法对光照、旋转以及噪声具有一定的鲁棒性。但由于该算法是利用特征点的邻域点构造描述向量，因此,当图片发生尺度变化时，剔除效果会受到一定的影响，今后拟寻找更好的描述方法，以确保算法在尺度变化上的效果有所改进。