HOG-FLANN在图像匹配ORB算法中的应用

杨 雷，唐瑞尹，张 怡

（1.华北理工大学电气工程学院，河北 唐山 063210；2.北华航天工业学院电子与控制工程学院，河北 廊坊 065000）

1 引言

图像匹配是机器视觉中重要的研究领域之一，被应用于双目相机三维重构、目标跟踪和机器人识别中。随着机器视觉的发展，对图像的匹配的准确率要求也越来越高。目前成熟的图像特征点检测算法有SIFT算法[1]、SURF算法[2]、和基于一种快速的特征点提取和描述ORB（Oriented FAST and Rotated BRIEF）[3]算法。ORB 算法最大的优点是可以极大的缩短图像匹配的时间，但ORB算法对噪声敏感[4]，容易产生含有不稳定边缘的特征点。

随着研究的不断进步，在图像匹配中经常使用ORB算法和FLANN（Fast Library for Approximate Nearest Neighbors）[5]相结合的匹配方法对图像进行预匹配，并通过使用随机抽样性（RANdom Sample Consensus，RANSAC）[6-7]算法完成图像特征点的匹配。RANSAC算法可以有效提高图像特征点匹配的准确率，但当样本中数据较多且局部内所占比例较低时。RANSAC计算最优模型参数时间呈指数增长，且移除错误匹配后仍然有较多的错误匹配。文献[8]采用在极线约束下通过ORB特征算法进行图像匹配，但该算法只能用于双目相机的图像匹配中；文献[9]采用了图像的彩色信息与SURF-ORB 算法相结合的方式，该算法具有很好的光照不变性，在不同的光照条件下，图像匹配的准确率有所提高。

针对上述情况这里采用了HOG（Histogram of Oriented Gradient，HOG）[10]窗口约束下的FLANN图像匹配方式。在这里算法中通过在HOG 窗口约束下使用FLANN 对ORB 特征点进行预匹配，然后采用RANSAC完成图像特征点的匹配。实验结果表明使用HOG 和FLANN 相互结合可以有效的提高图像预匹配的准确率。

2 特征点检测与匹配

特征点的检测准确率是影响图像匹配准确率的重要因素之一。ORB算法是图像匹配常用的算法其主要作用是对图像特征点进行检测与描述。

2.1 ORB算法

ORB 算法的特征点的选取是通过oFAST 算法进行选取的，而oFAST算法是在FAST算法的基础上改进而来，FAST算法的特征点检测方式如下：

在图像中选取某个像素点p其灰度值为IP，并且以p为圆心，确定一个阈值t让圆上16个连续像素点的灰度值分别与IP做差值运算。若其中有12个以上差值的绝对值大于IP-t或小于IP+t则视p点为特征点，原理图，如图1所示。

图1 FAST角点选取原理图Fig.1 FAST Corner Selection Principle

由于上述方式需要对图像的所有像素点遍历并做差值运算，导致计算速度慢。ORB算法对FAST进行了改进称其为oFAST，该算法选取了其中四个像素点作为判断依据。oFAST在加快运算速度的同时，降低了抗噪声的能力，容易把含有噪声的边缘点选作为特征点。如图1所示在oFAST中分别选取1、5、9和13像素点作为判断依据。如果其中有3个以上差值的绝对值都大于IP+t或都小于IP-t则被视p点为角点，其判别式，如式（1）所示。

ORB算法为了实现旋转不变性，是通过求取一个特征点的方向来实现的。该方法是通过矩来得到特征点在r为半径范围内的质心，并将特征点原点到质心形成的向量作为该特征点的方向。该特征点的领域矩，如式（2）所示。

式中：x，y—坐标值；I（x，y）—灰度值；r—半径。

该特征点窗口的质心坐标，如式（3）所示。

该特征点的主方向角度θ，如式（4）所示。

oFAST算法选取的特征点窗口是通过rBRIEF描述子进行描述的。该描述子是通过对BRIEF描述子的改进，进而使其具有了旋转不转性以及减少了描述子之间相关性。BRIEF算法的思想是在oFAST检测的特征点窗口处通过高斯分布随机的选取点对。然后将这些随机点对的灰度值进行大小比较，进而得到一组二进制数。该组二进制数τ的计算方式，如式（5）所示。

式中：P（x）—点x处的灰度值。表达式，如式（6）所示。

由于点对的选取是通过高斯分布随机选取的，导致生成的描述子对噪声十分的敏感。因此在oFAST特征点选取之前需要对图像进行高斯平滑滤波，这在一定的程度上降低了噪声的干扰，但显然不能解决ORB算法对噪声敏感的问题。

为了解决BRIEF 不具备旋转不变性的问题，提出了一个含有方向角的Steered BRIEF算法。在任意特征点位置定义了一个2×n维的点对矩阵，如式（7）所示。

根据特征点的主方向角度θ定义一个旋转矩阵Rθ，则点对矩阵与Rθ的关系，如式（8）所示。

其中，Rθ的表达式，如式（9）所示。

则Steered BRIEF描述符，如式（10）所示。

ORB 为了增加描述子的区分度对Steered BRIEF 进行了改进。描述子表达了不同特征点之间的区别，因此每个描述子应该具有其独特性。如果描述子之间的可区分度比较差，就容易引起误匹配。为了降低描述子之间的相关性，在ORB算法中采用了统计学习的方式，其具备步骤如下：

（1）首先建立一个300k个测试集，对于测试集考虑其31×31的领域；

（2）在此领域中使用（5×5）的平均灰度值取代某个点对的灰度值，共得到M中点对；

（3）通过选取较小的点对，进而得到300k×M个矩阵Q；

（4）按照矩阵Q中的列向量之间的相关性使用贪婪搜索对列向量重新排序，最终得到相关性最低的描述符，该描述符为rBRIEF；

2.2 HOG算法

方向梯度直方图（Histogram of Oriented Gradient，HOG）是一种图像特征的描述符。HOG算法经常用于行人检测中，在本文中通过HOG窗口平移的方式将目标图中的局部窗口与背景图的局部窗口进行描述子匹配，最终得到HOG 窗口的局部匹配图。本文算法中HOG窗口特征描述方式如下：

（1）将被检测图转换为灰度图；

（2）将输入图像进行Gamma校正，其的目的是提高改算法的可靠性；

（3）通过卷积的方式遍历整个输入图像，主要是获取每个像素的梯度；

（4）将输入图像方式划分成小局部窗口，这里为（128*128像素/窗口）；

（5）将局部窗口划分成cell，本文中为（8*8像素/cell）；

（6）将多个cell 组成一个block 描述子，这里为（16*16 像素/block）；

（7）通过将block在局部窗口中的滑动，这里block滑动的增量为（8*8像素），得到局部窗口的HOG描述子；

（8）按照一定的步调滑动图像中的HOG窗口，得到整个输入图像不同区域的描述子；

（9）将目标图中每个HOG 窗口与背景的HOG 窗口进行对比，通过相关性大小判断两个局部窗口是否匹配，如式（11）其中R值越小表示目标局部窗口与背景局部窗口的相关性越高；

相关性大小比较，如式（11）所示。

式中：R—相关性系数；n—描述子个数；Ti和Ii—目标图和背景图中HOG描述子值；

局部HOG窗口匹配，如图2所示。

图2 HOG局部窗口匹配图Fig.2 HOG Local Window Matching Graph

2.3 FLANN匹配器

图像特征点匹配是通过计算特征点之间相关性完成的，常用的图像匹配方式有BFMatcher（Brute Force Matcher）和FLANN两种匹配方式。BFMatcher是通过对图像所有特征点进行匹配，寻找最佳的图像匹配点。

FLANN是一种近似匹配方式，其具有计算速度快的特点，并且通过改变FLANN的参数可以调整图像匹配的准确度和改变该算法的计算速度。FLANN匹配是对大数据集和高维向量进行最近邻搜索算法的集合，且该算法不受局部敏感哈希的影响。

2.4 HOG-FLANN匹配算法

这里提出了HOG与FLANN相结合的检测算法。该算法是通过在HOG的局部窗口的约束下通过FLANN对ORB的特征点进行匹配，该方法可以有效提高ORB算法特征点匹配的准确率。采用ORB算法中rBRIEF作为特征点的描述子，通过使用HOG的局部窗口的约束下的FLANN 进行图像预匹配，最后利用RANSAC完成图像特征点的匹配。

该算法的流程，如图3所示。

图3 文中算法流程图Fig.3 Algorithm Flow Chart in this Paper

这里算法中的计算步骤主要如下：

（1）通过使用HOG局部窗口按照平移的方式对目标图和背景图进行遍历，然后采用式（11）获取R值。R值越小表示两个窗口的相关性越高，通过选取R的最小值，获得两个图像中局部窗口的匹配结果。

（2）通过ORB算法提取图像特征点，得到一个含有256位的二进制描述符。

（3）在HOG局部窗口的约束下对ORB算法提取图像特征点进行查询，选取HOG局部窗口内的特征点。

（4）采用FLANN对目标图和背景图的相互匹配的局部窗口中的特征点进行匹配，最后利用RANSAC完成图像特征点匹配。

经过上述特征点匹配后可以有效的提高ORB算法特征点的匹配精度，使其具有很好的鲁棒性。

在HOG局部窗口约束下的FLANN匹配结果，如图4所示。

图4 局部窗口的特征点预匹配Fig.4 Feature Point Pre-Matching for Local Windows

2.5 RANSAC算法

由于FLANN 预匹配的精度不够高仍然存在大量的匹配错误，所以需要移除错误的匹配点。

这里采用了RANSAC 对错误的匹配点进行处理，该算法可以有效去除错误率超50%的匹配点，所以具有较好的稳定性。并且这里是通过RANSAC 去除错误点的大小去衡量预匹配的准确率。

3 实验结果分析

为了验证这里算法的合理性进行了对照实验，主要是通过这里算法和FLANN算法的对照实验。通过该实验验证这里算法在不同像素、噪声和对比度下的匹配准确率。

该对比实验的仿真环境为CPU Intel（R）Core（TM）i5-4200M 2.50GHZ、RAM 4GB、开发环境为VS2015与OpenCv 3.1。

3.1 实验结果

这里采用了桌面照片作为测试图，通过使用该测试图对这里算法与原有算法进行了对比，并且验证了在含有噪声和改变亮度时本算法的稳定性，这里的算法的准确率明显高于原有算法，如图5～图7所示。这里算法与原有算法的匹配结果的数据对比，由表（1）可以看出在不同条件下这里算法剔除误匹配的数目要小于原有算法，说明这里算法具有更好的预匹配效果。

图5 原有算法与文中算法预匹配的对比Fig.5 Comparison Between the Original Algorithm and the Present Algorithm

图6 不同亮度下原有算法与文中算法预匹配对比Fig.6 Comparison Between the Original Algorithm and the Present Algorithm under Different Luminance

图7 含有噪声下原有算法与文中算法预匹配对比Fig.7 Comparison Between the Original Algorithm and the Present Algorithm Under Noise

表1 文中算法与原有算法的数据对比Tab.1 Data Comparison between the Present Algorithm and the Original Algorithm

4 结束语

针对传统ORB 特征点一般采用FLANN 进行图像特征点预匹配，这里采用HOG窗口与FLANN的相结合的算法。首先通过移动的HOG 窗口对图像进行局部窗口进行匹配，再通过使用FLANN对局部窗口中的特征点进行预匹配，通过该算法可以有效的提高图像匹配的准确率。经实验测得这里算法的预匹配准确率由原来的89%提高到了94%，但是由于为了提高HOG局部窗口匹配的准确性，需要对图像进行HOG窗口遍历，所以将降低时效性，这将是今后的研究方向之一。