基于改进ORB算法的特征点匹配研究

周 涵， 马增强,2， 许丹丹， 钱荣威

(1.石家庄铁道大学 电气与电子工程学院，河北 石家庄 050000；2.石家庄铁道大学 省部共建交通工程结构力学行为与系统安全国家重点实验室，河北 石家庄 050043)

0 引言

特征点匹配是数字图像处理技术中重要的研究内容，是图像拼接、目标定位与检测等技术中的基础。Lowe[1]在2006年提出的SIFT(Scale Invariant Feature Transform)匹配算法具有很高的匹配正确率，但算法本身计算复杂，运行时间较长。之后Bay et al[2]提出了SURF(Speeded Up Robust Feature)算法，虽然SURF算法运行速度比SIFT算法有了很大提升,但仍不能满足某些高实时性需求。因此刘伟等[3]于2018年提出了一种新的特征点匹配算法：ORB算法。它在运算速度上与SIFT和SURF算法相比优势明显且对光照变换、旋转变换以及噪声都具有较好的鲁棒性。但是ORB算法不具有尺度不变性的缺点，当图像尺度变化时，匹配正确率大大降低。文献[4]将SURF算法与ORB算法结合并在特征点匹配阶段使用BBF算法与RANSAC算法进行特征点匹配，提高了ORB算法在图像尺度变化时的特征点匹配正确率；文献[5]采用SIFT-ORB-MRANSAC融合算法，完成特征点的提取、匹配以及去除误匹配，提高了ORB算法在图像尺度变化时的匹配效率和匹配精准度。虽然以上方法有效解决了ORB算法不具有尺度不变性的不足，但是一定程度上也增加了算法的复杂度，增加了运算时间。

现提出使用多尺度Shi-Tomasi特征点检测算法对ORB算法进行改进，将改进算法定义为STORB算法。首先构造多尺度空间，经过特征点预筛选后利用Shi-Tomasi算法检测特征点分布均匀、准确的优点检测出具有尺度信息且特征明显的特征点，然后使用ORB算法生成具有方向信息和尺度信息的特征点描述子后进行特征点初匹配，最后使用RANSAC算法对初匹配结果进行优化,得到准确的匹配特征点对。

1 传统ORB算法原理

传统ORB算法是在FAST算法和BRIEF算法基础上的改进算法，首先使用FAST算法检测特征点并确定特征点方向，然后使用rBRIEF算法生成具有旋转不变性的特征点描述子，最后使用汉明距离完成特征点匹配。ORB算法流程如图1所示。

图1 ORB算法流程

1.1 特征点检测

ORB算法使用增添了方向信息的FAST算法来检测特征点，通过待检测点P和以P为圆心的圆上16个像素点的灰度差来检测特征点。FAST算法的检测原理如图2所示。

图2 FAST算法检测原理图

FAST算法检测速度极快，但容易出现特征点簇集现象，同时FAST特征点也不具有旋转不变性和尺度不变性[6]。FAST算法以特征点为起点构造向量，在特征点的邻域S内计算灰度质心并作为向量终点，向量的方向就作为此特征点的方向，定义特征点邻域S的灰度矩为

(1)

式中，f(x,y)为灰度值，则灰度质心位置C与特征点方向θ为

(2)

(3)

后续生成的特征点描述子通过结合特征点方向使FAST特征点具有旋转不变性。

1.2 特征点描述子

ORB算法首先从特征点周围31×31像素区域Z中按照高斯分布选择n组5×5大小的子窗口测试对记为(xi,yi)，然后计算5×5子窗口的灰度积分值后通过式(4)所示的比较准则τ进行测试对比较。

(4)

式中,z(x)、z(y)分别为测试对x、y的灰度积分值。比较n组测试对后就生成了n位二进制数所构成的特征点描述子，如式(5)所示。

(5)

之后rBRIEF算法结合上文中构造的特征点方向使生成的特征点描述子具有旋转不变性。由生成特征点描述子的n组测试对可定义一个2×n的矩阵

(6)

gn(z,θ)=Hn(z)|(xi,yi)∈Qθ

(7)

1.3 特征点匹配

ORB算法使用汉明距离计算出2个特征点描述子的相似程度从而判断是否为正确匹配点对。设H1，H2为2个由二进制字符串组成的特征点描述子，且H1=x0,x1,…,x255，H2=y0,y1,…,y255，则这2个特征点描述子之间的汉明距离可由式(8)计算。

(8)

D(H1,H2)为2个特征点描述子按位异或运算后的和，D(H1,H2)越小说明2个特征点描述子之间相似程度越高，当D(H1,H2)小于设定阈值时,就判定这2个特征点为正确的匹配点对。

2 STORB算法

STORB算法首先构建多尺度空间,通过预筛选去除大量非特征点后使用Shi-Tomasi算法替换FAST算法进行特征点检测，其特征点包含尺度信息且均匀分布。然后通过ORB算法求出特征点方向生成具有尺度信息和方向信息的特征点描述子，最后进行特征点匹配并优化。STORB算法流程如图3所示。

图3 STORB算法流程

2.1 多尺度特征点检测

2.1.1 构建多尺度空间

使用高斯函数构造多尺度空间得到具有尺度不变性的特征点。图像I(x,y)的多尺度空间表示为

L(x,y，σ)=G(x,y，σ)I(x,y)

(9)

(10)

图4 本文构造的多尺度空间

2.1.2 多尺度Shi-Tomasi特征点检测

Shi-Tomasi算法具有检测特征点分布均匀、稳定性强、特征明显、抗噪性强的优点[7]，因此选用Shi-Tomasi算法在多尺度空间中进行特征点检测。假设某个像素点坐标为(x,y)，检测窗口偏移量为(u,v)，则移动检测窗口前后灰度变化可由式(11)表示

(11)

式中，I(x+u,y+v)、I(x,y)分别为点(x+u,y+v)、(x,y)处的灰度值；ω(x,y)为加权函数[8]。将I(x+u,y+v)进行泰勒级数展开后带入式(11)可得

(12)

式中，Ix、Iy、IxIy分别为点(x,y)在X轴方向、Y轴方向的一阶梯度以及二阶梯度。M为自相关矩阵

(13)

通过式(14)比较自相关矩阵M中较小特征值与设定阈值T的大小来判断检测点是否为特征点。

(14)

由于Shi-Tomasi算法在多尺度空间中检测特征点时需考虑尺度信息[9]，因此多尺度Shi-Tomasi算法的自相关矩阵M改为式(15)，通过式(14)进行特征点检测。

(15)

2.1.3 特征点预筛选

使用如图5所示的8邻域环形模板对图像进行特征点预筛选，即在检测特征点之前通过预筛选快速排除大部分非特征点。

图5 8邻域环形模板

以待检测点P(x,y)为中心，按式(16)计算其周围8个相邻点与待检测点灰度值差的绝对值和N(x,y)，当N(x,y)大于设定筛选阈值T时,选择待检测点为候选特征点。

(16)

式中，T(x+u,y+v)=|I(x+u,y+v)-I(x,y)|。筛选出候选特征点后选择其周围3×3邻域内绝对值和N(x,y)最大的点作为待检测特征点，然后多尺度Shi-Tomasi算法只对待检测特征点进行检测，这将大幅度缩短算法时间，提高检测效率。

2.2 特征点匹配优化

RANSAC算法是一种特征点匹配提纯算法[10]，使用其对经过汉明距离匹配后误匹配点对的问题进行优化，主要步骤如下：

(1)设汉明距离匹配得到s对匹配点对，从中随机抽取4对匹配点对计算变换模型H中的8个参数。

(2)使用求出的变换模型H对s对匹配点对进行映射匹配，计算映射后特征点与匹配特征点之间的欧氏距离，记录欧式距离小于阈值的特征点匹配点对个数为i。

(3)重复k次步骤(1)至(2)，选取i最多的变换模型作为最终变换模型，此时i中包含点对即为最终的特征点匹配点对。

3 实验与结果分析

为了验证提出算法的各项性能，使用Visual Studio 2015开发工具集与OpenCV开源视觉库作为实验平台。硬件系统CPU为Intel(R) Core(TM)i5-3230M，4 GB内存，操作系统为64位。使用匹配正确率、运行时间作为算法性能评价指标对实验结果进行全面分析。其中匹配正确率定义为

(17)

3.1 尺度不变性实验

使用传统ORB算法、文献[4]算法、文献[5]算法及STORB算法对2组尺度变化的图像分别进行匹配实验，实验结果如图6和图7所示。可以看出当图像尺度发生变化时文献[4]、文献[5]和STORB算法的匹配正确率均远超ORB算法，而STORB算法与文献[4]和文献[5]算法相比误匹配点对明显减少。为了进一步说明STORB算法在尺度变化时的匹配性能，对图6和图7中2组图像6组不同的尺度变化进行匹配实验并统计实验结果如表1所示。由表1可知，当图像发生尺度变化时，STORB算法平均匹配正确率为95.8%，比ORB算法提高65.2%，比文献[4]和文献[5]算法也有部分提升,主要原因为STORB算法检测的特征点信息丰富更利于特征点对的匹配，同时经过匹配点对优化后进一步提高了匹配正确率。实验结果表明，提出的STOR法具有良好的尺度不变性。

图6 尺度变化实验(1)

图7 尺度变化实验(2)

表1 尺度变化实验匹配正确率 %

3.2 旋转不变性实验

STORB算法与ORB算法生成特征点方向信息的方式相同，为了验证STORB算法保留了ORB算法优良的旋转不变性，使用STORB算法与ORB算法对发生旋转变化的2组图像进行匹配实验，匹配结果如图8所示。由图8可以看出，STORB算法比ORB算法匹配点对分布更均匀，误匹配点对更少。

图8 旋转变化匹配实验

表2统计了2组实验的匹配结果，ORB算法在图像发生旋转变化时的平均匹配正确率为86.7%，而STORB算法平均匹配正确率为91.1%，比ORB算法提升了4.4%，这是由于STORB算法检测的特征点信息充足，为后续生成特征点描述子提供了准确的特征信息，有利于特征点的正确匹配。实验结果表明，STORB算法不仅保留了传统ORB算法优良的旋转不变性，还进一步提高了匹配准确性。

表2 旋转变化匹配实验匹配结果

3.3 算法运行时间对比实验

为了验证STORB算法在运行速度方面的性能，随机统计6组实验中各算法运行时间进行对比试验，结果如表3所示。从表3可以看出，STORB算法的平均运行时间比文献[4]算法快了68.1 ms，比文献[5]算法快了65.2 ms，只比ORB算法慢了7 ms，主要原因是STORB算法相比于文献[4]和文献[5]算法构建的多尺度空间更简洁，同时通过快速预筛选过滤了大量非特征点，节省了特征点检测时间，特征点的特征信息更准确节省了特征点描述子的生成时间。实验结果表明了STORB算法在实时性方面同样具有良好性能。

表3 运行时间对比 ms

4 结论

针对ORB算法不具有尺度不变性的不足，结合多尺度Shi-Tomasi算法对传统ORB算法进行改进，实验结果表明，所提出的STORB算法有效弥补了ORB算法不具有尺度不变性的缺陷，显著提高了匹配正确率。在拥有优良的尺度不变性与匹配正确率的同时还保留了传统ORB算法的旋转不变性和实时性，具有一定的实用性。