室内环境仿人机器人快速视觉定位算法*

吴俊君，胡国生

(1.广东食品药品职业学院软件学院，广东广州 510520;2.华南理工大学机械与汽车工程学院，广东广州 510641）

机器人技术是当今自然科学研究领域最活跃的分支之一。经过几十年的研究，机器人在功能、构型及性能等方面都取得了长足的发展，并在社会生产中产生了巨大的经济效益。机器人的应用领域正在从标准化的工业生产线逐步渗透至社会生活的各个服务领域，这一发展趋势对机器人的自主移动能力提出较高的要求。视觉传感器能够获取丰富的场景特征 (颜色、纹理等)，其对环境的刻画能力优于其他传感器，因此移动机器人视觉导航成为当前研究的热点。视觉导航是从仿生学的角度，给机器人配备一双能感知自身周边环境的眼睛，帮助机器人完成避障，路径规划和环境地图构建等任务。场景图像中存在的一些具有局部不变性特征的特征点对旋转、平移、尺度均保持不变性，这有利于帮助机器人解决自然环境下视觉导航中各个重要环节的问题，比如:闭环探测和视觉返巢等问题［1－2］。视觉定位是机器人视觉导航中的关键问题之一，通过计算机器人观测到的场景相似度完成机器人所在位置的空间相关性估计。视觉定位的效果与闭环探测密切相关，它将直接影响到:视觉SLAM(simultaneous localization and mapping)的成败［3］，视觉返巢中移动方向的判断以及转角的实时计算和环境地图节点中关键帧的选取［4］等方面。与GPS定位和基于内部传感器的航迹推演定位等精确定位方法相比，视觉定位更关注机器人当前所处的区域范围而非具体的坐标值。因为对于大范围环境下的视觉拓扑地图而言，区域定位比精确定位更有意义。

1 相关工作

目前视觉定位主要分为概率计算方法［5－6］和图像匹配方法［7－9］。概率计算方法将视觉定位归结为递归贝叶斯估计问题。首先采用图像建模方法描述机器人每一位置的场景图像，估计已获取图像与对应位置的先验概率A，在当前时刻计算新场景图像与已访问位置匹配的后验概率B，若概率B大于预设阈值确定定位结果。图像匹配方法将视觉定位归结于序列图像匹配问题，将当前时刻的图像与已获取的图像序列进行相似性匹配，若相似度高于预设阈值，则匹配图像被认为是对应了机器人所处的场景位置。

机器人在视觉导航过程中，需要连续不断地定位，即:计算当前观测到的视觉信息与拓扑地图节点对应的关键帧的相似度，但是较大的视觉信息量和不确定的环境因素制约了机器人视觉定位的实时性与鲁棒性。比如:在视觉返巢中，机器人依赖于高密集的关键帧图像;大范围内基于视觉的同时定位与地图构建aVSLAM(Appearance Based Visual SLAM)过程中，机器人会生成信息量巨大的视觉地图节点。如何在保证定位效果的同时提高定位的实时性，对移动机器人视觉导航的实际应用具有重要意义。

场景图像的相似度测量决定着视觉定位的效果。目前被用于视觉定位的场景相似度测量方法主要分为两类:①采用图像整体特征的方法，例如:基于信息理论计算图像的信息熵确定图像之间的共有信息量［10］;②采用局部不变性特征点的方法，例如:采用局部不变性特征点 (如:SIFT，PCASIFT，SURF 等)作为图像中的稳定点［11－13］，然后基于BOW(Bag of Words)模型对场景进行刻画，再通过余弦距离计算模型的相似度［14］。以上方法在有效性上的确取得了不错的效果，但是计算过程繁琐 (比如:BOW模型需要聚类过程和不断地更新视觉词汇字典)，实时性不佳，实用性有待进一步提升。

本文研究工作在保证视觉定位有效性前提下，提升定位的速度，增强方法的实用性。方法创新点如下:①采用BRISK局部特征作为视觉定位的特征点，提高了场景相似度测量的实时性。②受物种群落相似性度量的启发，将场景图像表征为由若干特征点组成的种群集合，简化了图像场景模型，提高了计算效率。③采用种群的索雷申相似系数，度量场景图像的相似性，计算过程简洁快速有效。

2 仿人机器人视觉定位算法设计

2.1 BRISK特征点探测与描述

本文算法采用BRISK特征［15］作为局部不变性特征点，与SIFT，PCA-SIFT，SURF局部特征点相比，BRISK采用二进制特征向量描述特征点，利用汉明距离度量特征点的相似性，匹配速度远高于其他特征点。

算法首先探测并描述BRISK特征，具体过程主要包括3个步骤:①基于尺度空间理论构建图像金字塔;②特征点探测。在尺度空间探测局部极值点作为特征点，如图1所示。探测结果如图2所示:极值点所处的尺度k，位置 (x，y)。③ 采用二进制向量描述特征点。

图1 图像金字塔:探测特征点Fig.1 Image pyramid:point detection

图2 探测结果Fig.2 Detection result

特征点描述:用特征点p{(x，y)，k}邻域的60个特征点之间的灰度大小关系来表征，生成二进制的特征向量［15］。特征向量的相似性采用汉明距离来度量，如图3所示。

图3 二进制描述符匹配Fig.3 Binary descriptor match

2.2 场景建模与相似性测量

由于不同的图像自匹配峰值差别较大，因此两幅场景图像的相似性无法直接通过两者包含的特征点匹配数目来度量 (如图6所示:峰值为图像之间的特征点匹配数)。因此，需要利用这些离散的特征点来合理地描述一幅场景，即:场景建模。具体描述如下:

假设一幅图像I包含若干个BRISK特征点，任意一个特征点Pl及其描述符Pd如公式 (1)，公式(2)所示

其中x，y，k，φ分别表示特征点的坐标，尺度和主方向。

其中bi是当前特征点描述符的二进制比特位。

则该场景图像I的描述，如公式 (3)所示

其中n是BRISK特征点数目。

假设图像I里的BRISK特征点被看成若干类不同的物种，则一幅场景图像可等价为一个物种群落，如公式 (4)所示

其中m是群落Q的物种种类数量。

生物群落的相似性计算本质上是基于集合理论。无论是一个群落Q还是一幅包含若干特征点的图像I，能否被视为一个集合，必须满足“逻辑性”这个充分必要条件，即:每一个对象都能确定是不是某一个集合的元素。将图像的BRISK特征点进行自匹配可知 (如图4所示):不仅可以确定一个特征点是否属于某幅图像，而且图像特征点之间也满足互异性 (即:特征点一一对应)属性条件，因此图像被简化为一个特征点集合是合理的。如图5所示:图像的相似性度量转化为求两个种群集合的相似性。

在生物学领域，为了研究生物种群群落的生长状况受环境因素的影响，需要计算两个种群的相似度。种群里的物种总数和共有种数的综合性指标(即:群落相似性系数)被用来表征种群组成的相似度，相似系数包括:索雷申系数，杰卡特系数和芒福德系数。本文通过计算两个种群的相似度来度量两幅场景图像的相似性，实验采用的相似系数为索雷申系数SC，如公式 (5)，两幅图像的相似距离DSC，如公式 (6)所示

其中 Qi，Qj为群落，且 SC(Qi，Qj)∈ ［0，1］和DSC(Qi，Qj)∈［0，1］。

图6 图像匹配结果Fig.6 Match result

视觉定位算法设计，如图7所示。算法的时间复杂性分析如下:整个算法的执行主要包括四个方面:BRISK特征点的探测，BRISK二进制描述符的生成，描述符的匹配和图像相似度计算。其中特征点描述符的匹配环节是影响算法时间复杂度的关键因素。假设当前待比较的两幅图像包括的特征点数分别为:N，M(N＜M)，那么匹配环节的双重循环次数为N*M，则算法的时间复杂度为O(N*M)。

3 仿真实验

3.1 场景相似阈值

实验采用室内随机捕获的一组场景图像作为数据集F，数据集F包含1002幅640*480大小介于60～200 K之间的图像。数据集F被分为四类场景图像:同一场景集合A，相似场景集合B，非相似场景集合C，完全不同的场景集合D。采用本文的算法对数据集里的图像做成对的相似性计算:以10幅图像为例，部分测量结果分别如图8和图9所示，每条曲线反映了当前某个场景与其他场景的相似度。

由仿真实验可知:相同或相似场景的SC系数均处于0.15以上，故算法将相似阈值设为0.15。为了便于计算，在实际的验证实验中将SC系数放大100倍，相似阈值设为15。

3.2 算法验证

本小节对算法的有效性、鲁棒性和实时性，与现有方法进行对比验证。

有效性:在数据集F包含的场景区域范围内，随机拍摄一组图像C作为机器人当前的位置。根据设定的阈值15，从实验数据集估算场景位置，成功率为99%。各个场景集合图像的相似性测量结果如表1。

表1 算法的有效性Table 1 The effectiveness of algorithm

此外，实验将本文方法FVL(Fast Visual Location)与其他场景相似性测量方法 (SIFT-BoW［14］，SIFT-BoRF［16］)的定位效果进行了对比。实验的具体方法如下:将机器人连续观测到的40幅场景图像作为测试数据集T，随后任意选取一幅场景图像n作为机器人在当前位置的观测值，然后分别采用FVL，SIFT-BoW和SIFT-BoRF方法对机器人的实际位置概率分布进行估计。以图像n=15为例:三种方法分别计算了图像15与数据集T中其他图像的空间相似度，然后进一步将三组相似系数分别归一化到 ［0.4，0.6］，［0.6，0.8］，［0.8，1.0］三个区间，三条曲线分别反映了机器人当前所处位置的概率分布，曲线的顶点峰值对应的场景作为视觉定位结果。如图10所示:三条曲线中，在图像15附近的场景被估算为实际位置的概率明显高于其他位置。这表明:在视觉定位效果上，三种方法均准确有效地完成视觉定位，而且本文方法FVL和SIFT-BoRF的效果相当，SIFT-BoW方法次之。

鲁棒性:为了验证方法的鲁棒性，实验进一步将相似场景细分为在不同角度、不同距离、不同光照三种情况。算法分别对其进行了相似性测量。如表2:同一场景在左右平移2 m，前后直行1.5 m，白天室内环境开灯和关灯情况下，计算得到的相似系数均在阈值15以上，算法具有良好的适应性。

图10 三种方法定位效果对比Fig.10 The locating efficiency of three methods

表2 算法的鲁棒性Table 2 The robustness of algorithm

实时性:从数据集F随机取一个样本依次与场景图像序列 (500幅)进行相似计算，记录下该样本与图像序列相似性测量所耗费的时间。反复取若干样本重复这个计算过程，取时间的平均值。如图11所示:每次计算的时间基本处于0.05 s以下，平均耗时约为0.03 s。计算时间主要受制于两个因素:特征提取的时间耗费，场景模型的复杂度。实验将本文的方法 FVL与 SIFT-BoW［14］，SIFT-BoRF［16］在计算时间上做了对比分析，结果发现:SIFT-BoW方法提取SIFT特征后，需要进一步聚类分析构建单词本，故相似计算的总耗费时间远大于SIFT特征提取的时间;SIFT-BoRF方法测量时间与SIFT特征提取时间相近，如表3所示。该方法在计算速度上要明显高于另外两种方法，耗费时间仅为前两种方法的1%。

表3 计算时间对比Table 3 The comparison of computing time

图11 时间耗费Fig.11 Time cost

4 实验验证

本实验采用法国Aldebaran Robotics公司研发的小型仿人机器人NAO作为研究平台，该机器人具有典型的双足机器人行走特点。机器人配有两个上下排列的针孔摄像机，上方的摄像机视野向前观测周围环境，下方的摄像机视野向斜下方观测地面。

机器人NAO利用前向摄像机在办公室环境中构建拓扑地图:机器人的移动轨迹由直线速度v、转角α和转角速度ω决定。实验中机器人的直线速度设为固定，转角α=0.3。每隔2 s取一幅关键帧，在室内构建56个拓扑节点，如图12和图13所示。每个地图节点用一幅场景图像进行刻画。机器人在室内漫游，实时进行视觉定位:机器人首先计算出所有与自己位置场景相似系数大于阈值15的地图节点，然后选出最大的相似节点 MN(Max－similar node)，此节点MN被认为是机器人当前所处的位置，定位结果如图14所示。若相似系数均小于15则认为机器人处在一个新位置，此场景被作为一个新的节点加入到环境地图中。

图12 视觉定位场景Fig.12 Visual location scene

视觉定位分析:机器人在室内漫游，利用本文算法进行视觉定位，对于同一场景从不同视觉角度的观测值，均被有效地测量出来，如图14所示。整个定位过程中对于已经到过的拓扑地图节点位置识别率达到99%，每对图像的相似系数平均计算时间:0.03 s，每秒可处理33帧图像。此外，实验过程也发现如下现象:个别死角或非常昏暗的位置由于无法提取到有效的特征点而导致相似度测量失败，如图15所示。此类“迷失问题”需要进一步研究有效的视觉地图节点生成方法，比如:对无效的关键帧进行剔除，或将模糊的图像清晰化。该问题将在下一步研究工作中展开。

5 结论

仿人机器人主要以室内工作环境为主，视觉定位方法能快速确定机器人所处的场景区域，对机器人进行视觉导航及完成后续任务具有重要的现实意义。非结构化室内环境存在较多的不确定因素影响着视觉定位效果，尤其是定位的实时性这一重要指标有待提升。本文受生物群落相似度测量的启发，提出一种快速的视觉定位算法，并利用仿真实验和仿人机器人平台对算法的实时性、有效性和鲁棒性进行了验证，结果表明:和现有的方法相比，本文方法FVL不仅取得了良好定位效果，而且实时性具有较大的提升。一次场景相似性计算平均耗时0.03 s(33 fps)，定位有效性为99%，对具有一定差异的相似场景，相似度计算具有良好的鲁棒性。算法的整个计算过程比较简洁实用，对提升视觉导航性能，尤其是实时性方面具有积极意义。

后期的研究工作将继续致力于提高室内环境下仿人机器人视觉导航的性能，并专注细节问题的研究:例如考虑如何选取有效的拓扑地图节点，研究动态环境下视觉定位的鲁棒性和大范围环境中移动机器人视觉闭环探测的实时性等问题。

［1］JAUREGI E，IRIGOIEN I，SIERRA B，et al.Loop-closing:a typicality approach［J］.Robotics and Autonomous Systems，2010，59(3):218 －227.

［2］MOLLER R，KRZYKAWSKI M，GERSTMAYR L.Three 2D-warping schemes for visual robot navigation［J］.Autonomous Robot，2010，29(11):253 －291.

［3］MORIOKA H，HASEGAWA O.Vision-based mobile robot's SLAM and navigation in crowded environments［C］//IEEE International Conference on Intelligent Robots and Systems，San Francisco，CA，2011:3998 －4005.

［4］ZHANG H，LI B，YANG D.Key frame detection for appearance-based visual slam ［C］//IEEE International Conference on Intelligent Robots and Systems，Taipei，2010:2071－2076.

［5］RANGANATHAN A，DELLAERT F.Online probabilistic topological mapping［J］.International Journal of Robotics Research，2011，30(6):755－771.

［6］CUMMINS M，NEWMAN P.Probabilistic appearance based navigation and loop closing［C］//IEEE International Conference on Robotics and Automation，Rome，2007:2042－2048.

［7］HO K L，NEWMAN P.Loop closure detection in SLAM by combining visual and spatial appearance［J］.Robotics and Autonomous Systems，2006，54(9):740 －749.

［8］CALLMER J，GRANSTROM K，NIETO J，et al.Tree of words for visual loop closure detection in Urban SLAM［C］//the Australasian Conference on Robotics and Automation，2008:1－8.

［9］HO K L，NEWMAN P.Detecting Loop closure with scene sequences［J］.International Journal of Computer Vision，2007，74(3):261－286.

［10］DAME A，MARCHAND E.A new information theoretic approach for appearance-based navigation of non-holonomic vehicle［C］//IEEE International Conference on Robotics and Automation，Shanghai，2011:2459 －2464.

［11］LOWE D G.Distinctive image features from scale-invariant key points［J］.International Journal of Computer Vision，2004，60(2):91－119.

［12］BAY H，ESS A，TUYTELAARS T，et al.Surf:speeded up robust features［C］//Europe Conference on Computer Vision，2006:404－417.

［13］KE Y，SUKTHANKAR R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2004:II－506.

［14］FILLIAT D.A visual bag of words method for interactive qualitative localization and mapping［C］//IEEE InternationalConference on Robotics and Automation，Rome，2007:3921 － 3926.

［15］LEUTE NEGGER S，CHLI M，SIEGWART R Y.BRISK:binary robust invariant scalable key points［C］//IEEE International Conference on Computer Vision，Barcelona，2011:2548 － 2555.

［16］HONG Z.BoRF:loop-closure detection with scale invariant visual features［C］//IEEE International Conference on Robotics and Automation，Shanghai，China，2011:3125－3130.