改进人工鱼群的ORB特征匹配算法

李思璇，胡志刚，2，王新征，付东辽，祖向阳

1.河南科技大学医学与技术工程学院，河南 洛阳 471003

2.河南省智能康复医疗机器人工程研究中心，河南 洛阳 471003

在视觉SLAM（simultaneous localization and mapping）[1]中前端（视觉里程计）为后端优化提供了所需的信息，信息精度直接影响后端优化效果与建图轨迹的准确性，精度较高的特征匹配方法有助于准确定位与地图构建。ORB（oriented FAST and rotated BRIEF）[2]是在FAST与BRIEF基础上改进的一种含有方向的二进制描述方法，虽然在匹配精度上略逊于SURF 与SIFT 算法，但在实时性方面有着巨大优势，因此在视觉SLAM中得到广泛应用。近年来众多学者为提升ORB匹配精度进行大量研究。在特征检测方面，文献[3]针对亮度变化明显场景提出一种ORB 局部像素自适应分类方法，对特征点精准提取后结合PROSAC 算法有效降低了不同光强度下的误匹配率。文献[4]使用树状存储结构，对图像节点分割成多个子区域，根据子区域特征点数量进行均匀提取，这种方法有效地解决了特征点聚集冗余的问题，具有优良的图像匹配能力。还有通过将多种算法征检测与ORB结合以改进自身不具备尺度不变性问题并得到了可靠度较高的匹配结果[5-7]。有研究人员进行图像目标分类检测将K-means 聚类算法与ORB 结合[8]解决传统特征匹配不能多目标匹配的问题。文献[9]通过图像语义分割，提取目标图标区域生成词袋模型，使用SVM 提升了图像分类性能。在后端优化方面，文献[10]将人工鱼群应用在粒优子集合优化，重新调整粒子的提议分布，使估测粒子更符合实际状态分布，提高了机器人的位姿估计精度。文献[11]在视觉SLAM路径规划中通过引入聚集因子β与迭代次数共同影响自适应因子改善了人工鱼群收敛精度，同时添加权重评价因子计算了人工鱼当前位置的适应度值，改进算法有效的避免陷入局部解的问题并提高了最佳路径的规划速度。在众多目标分类中K-means 聚类算法在类之间区别较为明显时具有良好的分类性能，但过于依赖随机选取的初始值，容易造成结果不稳定。目前较为成熟的SVM 分类核函及参数基本上都是根据经验值设定，考虑在未知环境中核函数及参数应当按照实际场景来确定，动态满足核函数与参数的设定目前较为复杂。人工鱼群算法作为一种群体智能优化算法[12]，在组合优化问题中得到广泛的应用，它的优点在于对初始值的要求不高，前期快速较快，个体之间独立存在且获得的信息轻便简洁，使得算法在设计改进中上更加灵活，操作性更高。

在总结以上方法后发现现存方法中或多或少存在着特征点检测弹性不足，未考虑实际的情况对特征点数量以及区域检测进行过多控制，虽然部分图分类效果良好但应用在实际环境中实时性尚未达到一定标准。

考虑人工鱼群适合求解精度要求不高的寻优问题与大量特征点之间无需零差别描述匹配相互耦合，且人工鱼群的聚群、追尾、自由行为对特征点选取起到了快速分类的效果，缩小匹配范围，加大了不同区域之间特征点的描述差异，故本文采用改进人工鱼群与ORB 特征匹配算法结合提高特征匹配正确率。改进算法分成两个部分：（1）对于FAST 角点边缘敏感不足的情况，提出FAST-16的角点弹性检测方法，根据不同情况弹性的选择角点圆周位置进行像素值对比；（2）使用自适应的鱼群参数对人工鱼群进行行为分析，在图像中规划聚群区域、追尾区域、自由区域，对人工鱼群（即特征点）更加灵活的分类，最后分别使用汉明距离的筛选方法与RANSAC 算法进行特征匹配并将正确匹配率进行对比。实验结果表明，改进后的ORB 算法匹配精度大幅提升，同时满足室内轮椅定位与建图实时性的需求，为室内轮椅定位与建图的准确性做良好的铺垫工作。

1 人工鱼群与ORB算法的基本原理

1.1 人工鱼群的行为描述

人工鱼群算法[13]是对鱼类不同行为归纳总结得出的一种优化方法，将鱼群行为描述分为如下四种并概述一些基本定义，其中X=(x1,x2,…,xn)表示当前人工鱼的位置，Y=f(x)表示寻求的目标函数，di,j=||Xi-Yj||表示个体与个体之间的相互距离，Visual表示以人工鱼为中心的感知半径，W表示聚集程度。

（1）觅食行为：Xi在Visual圆周内选择任意一点新状态Xj，若Yi

（4）随机行为：作为其他情况的补充，人工鱼在不满足任何行为的时候在Visual圆周任意更新位置。

全局性公示板用于保存人工鱼的最佳状态，每次行为迭代后都会检索其自身状态，若优于最佳状态，则将全局公示板更正为当前状态。

1.2 ORB特征匹配原理

1.2.1 FAST特征点检测

图像中任意两点像素P1、P2，构建灰度差值函数M=|IP1-IP2|。设强差异的阙值为T，若M>T，则认为这2个点具有强差异。考虑圆心像素点周围以3为半径的16 个像素点，如果这16 个像素点中有连续的n个强差异像素点，那么它就是一个特征点，如图1所示。

图1 FAST检测原理图Fig.1 Detection schematic of FAST

为了使特征点带有方向描述[4]，首先定义图像块的矩函数Mpq如式（1）所示：

式（2）表示的是以r为半径的邻域S内质心位置C：

连接图像块的几何中心O与质新C，得到式（3）中θ为特征点的方向：

1.2.2 特征点描述

普通BRIEF不具有方向旋转的性质，通过上文计算出方向向量使BRIEF 具有良好的旋转不变性。通过选取角点周围随机选取n个点对进行比较，并用0 与1 组合成描述子。每个BRIEF 描述子是一个长度为n的二进制数值码串，并构成点对集合S，使用邻域方向θ和对应的旋转矩阵Rθ，构建S的一个校正版本Sθ，如式（4）所示：

其中θ为主方向，在求得的新点对中使用相互关联性最低的一组点对集合，得到含有方向的描述子。

1.2.3 特征点匹配

特征匹配作为视觉里程计中极为关键的部分，匹配的好坏程度将决定后续优化模型的工作量大小，目前常用的有暴力匹配法（brute-force matcher），它使用的方法是在原始图像中选取一个包含描述子的特征点，然后按照一定的顺序与目标图像中的特征点进行描述距离的比较，最后与距离描述最近的点进行匹配，同时本文参考了文献中工程上的筛选方法，通过筛选将描述距离小于最小距离特定倍数的特征点进行匹配。RANSAC 算法[14]是在两幅图像中找到最佳单应性矩阵H（homography matrix），它表示的是同一物体，在不同视角下的矩阵转换关系。此种算法具有良好的剔除误匹配能力，抗噪能力强，适用于大部分场景的特征匹配。

2 改进人工鱼群的ORB特征匹配算法

使用改进人工鱼群算法与ORB特征匹配结合需要大量丰富的图像特征点以便于通过鱼群行为更好的对特征信息分类，减小匹配范围，提高正确匹配率。为了得到更多的特征点，需要对图像明显分界处更加合理灵活的检测，改进FAST 算法并未通过增加或减小圆周半径r来提高灵敏度，而是对特征点达到一定条件后，对圆周不同方向上弹性选取像素位置进行像素值对比，然后根据检测结果结合改进人工鱼群具有并行计算、收敛速度快的特点，通过对特征点3 种鱼群行为分析，将其分类成多个类间描述差异较大的特征区域，最后利用RANSAC算法进行特征匹配。

2.1 改进FAST特征点检测

在实际特征点检测中，FAST为了加快计算速度，在像素点以r为半径的圆周上，全部像素点并未按照顺时针方向比较，而是每间隔3个像素点取一个像素点与之进行对比（以3为半径间隔3个位置，如位置1、5、7、9的像素点），若大于等于3 个同时属于强差异的像素点则继续检测中间需要相连接的像素点。当至少连续9 个同时为强差异像素点则认为该点是特征点，虽然这种方法计算速度较快但同时由于用于依赖开始选择固定的4个像素点，导致边缘敏感不足，抗锯齿能力不强。针对这种情况，改进后的FAST在选择间隔为3的4个像素点中，若只存在2个同时属于强差异的像素点则先考虑其他2 个非强差异像素点的边缘与中心像素点是否存在强差异。如图2（a）所示：若位置1 为非强差异像素点，则考虑位置1 的上下边缘，若位置13 为非强差异像素点，则考虑位置13左右边缘与中心像素强度差异关系，在这两对边缘中只要存在1 个强差异点即可认为满足选择的4个像素点中同时存在3个强差异像素点的初始要求，在边缘检测条件满足后进行像素点的连续性检测，到达至少9个像素点连续为强差异像素则认为它是一个特征点进行保留，反之则去除。图2（b）为经过改进后的圆周检测位置示例。

图2 改进FAST检测原理图Fig.2 Detection schematic of improved FAST

确定角点后通过灰度质量心法计算出质心C与主方向θ，得到带有方向的rBEIEF。改进FAST特征点检测流程图如图3所示。

图3 改进FAST特征点检测流程图Fig.3 Feature point detection flowchart of improved FAST

2.2 改进人工鱼群的特征点选取

通常鱼群聚集的地方往往是营养较为丰富的地方，基于此思想在特征点检测中特征点较多的区域同样图像特征较为丰富，考虑K-means聚类方法[15]需要多次迭代并照顾全局每一个点，直到计算出一个或多个聚类中心，过于依赖初始点的位置，如图4（a）所示，经过聚类算法的计算将图像中的点分为上下两类，距离聚类中心较远的点同样被考虑在计算范围之内。本文通过上文改进的FAST提取，将当前特征点作为已收敛后的人工鱼群，即图像特征信息最优提取，通过改进人工鱼群思想计算出一个或多个聚群区域，根据特征点相应的位置判断其当前的状态，对于未在聚群区域的特征点通过状态判断策略选择保留或去除。每一个特征点位置对图像整体计算影响较小，通过减小图像特征区域外的相似描述提高匹配精度。图4（b）为改进人工鱼群的特征点分类原理图。

图4 分类类型示意图Fig.4 Schematic diagram of classification types

下面是改进算法中包含的一些基本定义：SR（satisfactional research）代表区域认可度，FI（follow intensity）代表人工鱼的追随强度，Nmax为图像中检测到特征点的数量。

（3）自由状态行为分析：如图4（b）绿色点所示，不在聚群与追尾区域的人工鱼将被认定为自由状态Fd，考虑其不影响其他人工鱼的条件下，将其去除。自由状态的行为分析将图像中某一局部区域单独出现的特征点在不影响其他特征点聚类、描述图像信息的情况下视为环境干扰产生的噪声，故通过不同的行为分析后将其在图像特征点中过滤消除。

2.3 特征点匹配

随机一致性（random sample consensus，RANSAC）通过拟合参数模型高效的去除了大量误匹配，该方法[16]可以在包含大量误差超过阈值的数据集中分离出误差在一定范围内的优质参数。在实际情况中，RANSAC算法对于优质的模型会很快跳出迭代，节省大量计算时间。它的计算过程如下：

（1）从数据集合中，任意的抓取一定的参数生成拟合函数，并计算出最佳单应性矩阵H。

（2）设置一个误差阈值T，计算其他未被选择的点与模型的投影距离L，若L

（3）计算每个模型含有局内点的数量，通过迭代随机生成的模型，直到局内点数目不再变化，并达到最大数量时停止采样。

2.4 改进算法的总流程

改进算法的具体流程如图5所示。

图5 改进人工鱼群的ORB特征匹配流程图Fig.5 ORB feature matching flowchart of improved AFSA

首先针对特征点检测能力不足的的情况，对FAST特征点圆周弹性位置的像素值进行对比然后提取特征点；接着通过改进人工鱼，结合其速度快、输入信息简洁，算法设计方便等优点划分特征区域，追尾区域，对特征点赋予不同状态优化选取；最后使用RANSAC 算法计算出最佳拟合函数去除图像中的误匹配。

3 实验结果与分析

3.1 改进FAST算法的实验结果

本文实验环境为Ubuntu 16.04，CPU 为i7-4510U，Opencv2.4.13，为了验证改进算法的有效性，选择公开数据集中bikes场景、light场景、graffiti场景，公开数据集的地址为http：//www.robots.ox.ac.uk/～vgg/research/affine/，同时选取了实际场景，对改进FAST 算法前后进行了效果图的比较。在实际测试中过高的阈值使判断条件过于严格，导致少量的特征点无法准确描述图像信息，过低的阈值会导致特征点聚集在图像某一处，大量重叠。本文在实验中将阈值设置为（Threshold=50），在提取阶段阶段进行了非极大值抑制，实验结果如图6所示。

图6 改进FAST效果对比图Fig.6 Effect comparison diagram of improved FAST

通过观察，图6（a）左二摩托车车头与车尾有大量重叠的特征点，每辆摩托车车胎、遮阳棚、门框均少量特征点。从图6（b）可以发现，经过改进后的算法使得车胎处、门框处存在较多的特征点符合实际图像的轮廓边界，并无聚集重叠的特征点。根据图6（c）所示，图像树叶、建筑物入口上方处，特征点过于密集，楼梯边缘处也没有有效检测到特征点。如图6（d）所示，在树叶与楼体中检测到了较多且均匀分布的特征点，对楼梯边缘、白色汽车车体边界处进行了高质量的特征点提取，对图6（c）中存在的问题进行了有效的改善。从图6（e）中可以很明显的看到，在整个图像中明显分界处并没有符合理想的特征点，而经过改进后的算法在图6（f）中精准的对图像中存在边界的地方进行了特征提取，对图像轮廓进一步详细的描述。在实际环境中，从图6（g）与6（h）可以发现改进算法更加精准的将暖气片之间缝隙作为特征点提取出来符合理论的设计原理，对右下角办工桌的边缘使用特征点勾绘出来满足物品实际的边缘形状，并对桌面物品的外形又有着进一步的精准描绘。从图6（i）与6（j）对比中可以看出，改进算法对图像下方的办公椅提取出较多的特征点，并且对图像上方的灯管处提取出与实际情况一致的特征点。这是由于传统FAST严格要求对比像素的圆周位置导致特征提取并不理想，通过算法改进前后效果表明改进ORB的FAST算法，可以灵活有效地对不同情况的像素位置及时调整，更加均匀精准的突出图像中存在的特征点，对于特征点圆周位置弹性范围的灰度值对比检测，可以有效地克服特征点对边缘检测的不敏感。

3.2 改进ORB特征匹配算法的实验结果

在3.1 节中对ORB 的FAST 算法进行了改进，并在公开数据集中验证了改进算法的有效性。本实验模拟室内环境共采集了80 组室内图片进行特征点匹配，选择其中40 组匹配效果较为良好图片作为样本，计算了不同特征匹配算法的平均正确匹配率并测试了算法的稳定性即标准差，结果如表1所示。

根据表1 可知，传统ORB 平均正确匹配率较低，并且标准差达到3.1%，匹配结果极不稳定。通过使用筛选匹配或RANSAC 匹配策略与传统ORB 结合，不需要额外消耗更多的匹配时间便可以将平均正确匹配率小幅度提升15.4%～29.5%，将标准差降低0.4%～0.8%，虽然改善了匹配效果与稳定性但并未达到理想正确匹配率。优化ORB算法与筛选匹配结合在匹配精度方面较传统ORB 提高了39.2%，经过优化后的ORB 算法明显比传统ORB 匹配效果提升一个数量级并且降低了正确匹配率标准差至2.0%，但依然不满足理想的正确匹配率。最后，通过改进人工鱼群的ORB 优化算法与RANSAC匹配结合，在平均消耗时间上比优化ORB+筛选匹配多2.32 ms，在满足实时检测的要求下平均正确匹配率与标准差分别达到92.7%、1.3%，结果相对稳定，与传统ORB 相比匹配精度提升了117%，标准差降低1.8%，符合理想的正确匹配率与稳定性。

表1 匹配结果对比Table 1 Comparison of matching results

下面给出在实际环境中与公开数据集中配精度效果较好的四组图片加以说明，第一组如图7所示。其中图（a）为初始图像，图（b）、（c）、（d）、（e）、（f）分别对应传统ORB 特征匹配、传统ORB+筛选特征匹配、传统ORB+RANSAC匹配、优化ORB+筛选匹配、优化ORB+RANSAC匹配5种实验的结果。

图7 改进ORB特征匹配效果图Fig.7 Feature matching effect diagram of improved ORB

从图7（b）中可以观察到由于传统ORB使用暴力匹配法，图像中存在大量误匹配，使得匹配精度极低。在图7（c）与7（d）中可以观测到虽然使用了两种不同的特征匹配策略，虽然在匹配精度上小幅度的改善了误匹配率，但由于图像特征点在提取的过程中并未提取出质量较高的特征点，并且是对全局相似特征点进行对比匹配，导致原始图像左侧的特征点在目标图像上发生了误匹配，产生并不理想的匹配效果。观察图7（e）与7（f）中可以发现，优化ORB 与RANSAC 匹配算法的结合正确匹配率高于ORB 与筛选匹配的结合，同时对于目标图像缺少初始图像左侧的部分，并在该部分产生大量特征点，目的是检测两张图像经过改进人工鱼群划分特征区域后，区域内的特征点是否会像去除的特征点一样干扰匹配。通过实验表明，RANSAC 匹配算法虽然会带来迭代计算，由于优化ORB 算法通过划分特征区域大大缩小了匹配范围，弥补了RANSAC计算量大的劣势，并且在特征区域内特征点之间不会产生强烈干扰，降低特征点由于随机相似的特征描述引起的误匹配。

如图8所示，为样本中两组不同场景的传统ORB特征匹配与改进算法的效果对比图。图（a）、（b）、（c）、（d）两组实际效果对比图选择的场景分别是正常光线的室内、与光线较暗的走廊，通过效果对比图可以看出经过改进人工鱼群的ORB特征匹配算法在较亮或较暗的环境中都具有较好匹配效，图（e）、（f）是选用公开数据集中的graffiti场景通过偏转一定角度来进行特征匹配，从图8（e）中可以看出偏转后的图像特征匹配较为混乱，具有较高的误匹配率，使用改进的特征匹配算法通过对图像的位置信息分类，缩小匹配范围，有效地降低了误匹配率，即使在图片偏转一定角度的情况下仍然具有一定的鲁棒性，改进算法具有较高的稳定性与正确匹配率。

图8 不同场景改进算法对比图Fig.8 Comparison diagram of improved algorithms for different scenes

3.3 改进算法总结

根据实验结果得出改进人工鱼群的图像信息分类扩大了不同特征区域特征点之间的描述差异，使得室内物品杂乱较多的情况下具有较好的分类匹配效果，同时针对室内环境光照强度的不同，具备较好稳定性以及良好特征匹配性能，降低了实际环境中误匹配率。改进算法为室内环境中的轮椅导航与建图提供了良好的前端信息，为后续工作关键帧的确定做好准备。

4 结论

本文针对室内轮椅定位与地图构建中提高视觉里程计ORB特征匹配正确率的要求。首先根据不同条件对ORB中FAST弹性选取边缘位置后进行像素值对比，经过检测后提取出特征点并计算方向与描述子，然后通过改进人工鱼群的ORB特征选取策略对特征点划分特征区域并根据其位置赋予不同状态，最后结合RANSAC匹配算法，对传统ORB 算法进行了优化。通过改进前后的ORB 算法对公开数据集与实际场景实验效果对比，结果表明改进FAST 算法可以在图像边缘处检测到更多的特征点，基于人工鱼群的ORB 算法平均正确匹配率可以达到92.7%，稳定性较高。该算法对于室内环境具较高的正确匹配率，环境适应能力强，为后续工作室内轮椅定位与地图构建做好了充分准备。