李新德 金晓彬 张秀龙 戴先中

(东南大学复杂工程系统测量与控制教育部重点实验室，南京210096)

计算机视觉具有信息丰富、智能化水平高等优点，因此广泛应用于移动机器人的自主导航中.视觉导航中通常采用视觉传感器来检测环境中的一些显著路标，实现快速自定位.通过路标将全局路线分解为片段，不断地探测路标来完成导航［1］.

根据路标的不同可以分为人工路标和自然路标.自然路标是早已在环境中存在并且除了用于导航之外还有一定功能的目标或特征;人工路标是为机器人导航而专门设计的目标或标记，如文献［2-4］中采用了各种具有特殊颜色或者特殊标记的人工路标.人工路标导航不易受到环境干扰而且容易实现，但是破坏了环境的协调性，且每当室内环境发生变化时，就必须调整人工路标的位置，难以适应现代个性化的家庭居住需求.

自然路标不改变工作环境，也不需要额外的设施或额外信息，受遮挡和噪声干扰小，因而受到越来越多的关注.文献［5-7］采用Hough 变换等方法识别门牌、海报、灯饰、室外建筑物等线条状的自然路标，并取得了一定的效果.蔡自兴等［8］提出了一种角点聚类的自然路标局部特征模板，利用模板的不变性特征识别自然路标.该方法对于角点较多的自然路标(如柜子)具有较好的识别效果，但是在复杂环境下角点数量庞大，匹配计算量急剧增长［8］，难以满足实时性要求.文献［9］提出了一种采用SURF 特征的动态环境导航算法.该方法需要提前准备自然路标在真实环境下的多幅图像.然而在未知环境下，提前拍摄自然路标的图像并不可行.

本文模仿人类在未知环境下的导航方式，采用室内常见物体为自然路标，结合BoW 物体识别模型和交互式的手绘地图，指导机器人寻找环境中的关键物体，辅助机器人快速、高效地到达目的地.

1 Bag of Words 模型

Csurka 等［10］首先将“自然语言处理”领域的BoW(bag of words)模型［11］引入图像分类领域，将图像类比为由若干单词组成的文档，每幅图像表示为视觉单词频率直方图，取得较好的分类效果.BoW 模型的关键在于提取图像的视觉单词描述，本文采用SIFT 算法提取图像中的视觉单词［12］.通过SIFT 特征检测后，每幅图像都由一个128 维特征向量集合描述.采用K 均值聚类，得到K 个聚类中心作为视觉单词，视觉单词构成视觉词汇表.由于聚类的不精确性，以及词汇表大小的随意性，视觉单词往往具有一定程度上的冗余.

受文档分类的启发，对每幅图像中的每个特征向量计算N 个最近邻视觉单词，然后采用下式度量第k 个视觉单词的质量:

式中，Mi表示与视觉单词tk第i 接近的特征向量数;s(fj，tk)表示特征向量fj与视觉单词tk之间的相似度，本文中采用欧氏距离.对每个视觉单词计算其质量，如果满足

则保留，否则舍去.式中，h 为视觉单词的质量阈值.为了满足实时性要求，同时保证识别率，本文取N=3，h=0.8.

为了抽象图像的BoW 表示，需要将SIFT 特征向量量化为视觉词汇表中的视觉单词描述.一般采用最近邻归类，将128 维SIFT 特征量化为视觉单词.然后统计每幅图像中视觉单词出现频率，构造视觉单词直方图.

支持向量机具有小样本下推广能力强的优势.针对多分类问题可以对每一类物体构建“一对多”支持向量机.通过离线训练的方式，为室内常见物体建立基于BoW 模型的线性支持向量机，将结果保存为自然路标数据库.

2 手绘地图的表示

本文提出一种与“人类问路”过程中的语义地图比较类似的手绘地图，以指导机器人在局部未知的环境下快速导航.

假设实际环境地图为Mr={L，B，C，T，R}，其中，L 为导航设置的自然路标;B 为不适宜作为自然路标的障碍物;C 为导航环境中的动态障碍;T为导航目的地;R 为机器人的初始位姿.

手绘地图如图1所示，其中标识了导航过程中可能发现的“自然路标”的位置、名称和参考路径.手绘地图表示为其中，表示自然路标L 在手绘地图中的概略位置.包含路径的起始点S、终点D 以及手绘路径.手绘路径并不是机器人的导航路径，而只是指引移动机器人沿该路径的大致行走趋势.手绘路径具有随意性、灵活性和不精确性.表示机器人的初始概略位姿.手绘地图HM与实际环境地图之间存在“松散”的映射关系.这是因为动态环境的精确大小无法快速获知.另一方面，手绘路径对机器人起到的只是指引作用，因此机器人没有必要完全按照指定路径运行.本文将手绘路径简化为折线，机器人在每段线段间采用直线前进，可以有效地避免频繁旋转所带来的累积误差.

图1 手绘地图

如图2中大圆圈标识，通过计算手绘路径每个点的曲率以及自然路标的位置影响，可以从手绘地图中提取出l +1 个关键引导点，将一条手绘地图路径划分为l 个片段，每一段表示为从节点ni－1到ni的直线，机器人初始位置为r0≈n0，终点为nl.因此全局的导航过程就可以简化为每两个关键引导点间的导航.

图2 关键引导点的提取

3 基于自然路标的视觉导航方法

3.1 自然路标筛选

如图1所示的手绘地图中，关键引导点附近可能有多个候选自然路标.然而每个时刻只需要选择其中一个作为自然路标就足以帮助移动机器人自定位.从候选的自然路标中筛选一个最容易被机器人搜索到的目标，不但减轻了机器人视觉观察的负担，而且提高了机器人的导航速度.

如图3所示，ni－1和ni分别表示当前阶段的起点和终点.假设机器人已经处在ni－1并且朝向的方向，则节点N0.5为向量的中点.Oj(j =1，2，…，m)是与ni比较接近的m 个候选自然路标，dj为候选自然路标Oj与ni的物理距离，αj为的相对夹角.经过分析候选自然路标Oj与节点ni的距离和角度，选Oj作为自然路标Li的权重函数，即

式中，f1(d)为距离约束函数;f2(α)为角度约束函数.由式(6)可以计算出ni附近最容易被发现的自然路标Li.根据经验，若F(Li)＜0.2，则认为ni附近的候选自然路标离ni太远或者角度太偏，机器人可以依据手绘地图和里程计进行惯性导航.若存在多个目标都能使Fi取得最大值，则选择这些目标中最小的αi作为参考目标.

图3 自然路标的筛选

锁定ni附近的自然路标Li后，机器人加载自然路标数据库中的对应分类器.参考手绘地图中路径先快速行驶至N0.5，计算自然路标Li与之间的夹角β.调整摄像机在β 角度附近搜索自然路标Li，一旦确认检测到自然路标Li，则进行视觉粗定位，计算机器人相对Li的位姿.

3.2 视觉导航粗定位

本文采用超声波测距结合视觉信息进行粗定位，从而获得机器人在地图中的相对位姿.

通过关键引导点的提取，可以将一条手绘地图路径划分为l 个片段，每一段表示为从节点ni－1到ni的线段机器人起始位置为r0≈n0.手绘地图的不精确性决定了每一段路程有一个独立的比例尺mi，机器人需要根据间的实际行走路程更新比例尺mi+1.由下式计算路程的初始比例尺m1:

式中，d 为导航环境中2 点之间的物理距离;d′为手绘地图中的像素距离.假设某一时刻机器人沿前进并检测到ni附近的自然路标Li，此刻机器人与Li之间的粗略米制距离为

式中，s(r，Li)表示声纳测得机器人相对路标Li的距离，机器人相对Li的方向即为当前摄像机的旋转角度;r 为机器人在手绘地图中的当前位置;ri－1为机器人到达上一个节点ni－1后经过自定位获得的位置;mi为这段路程的地图比例尺;t 为像素距离阈值，一般取0.6.当机器人检测到路标Li并且d(r，Li)＜mid′(ni，Li)时，由

计算自定位后的位置ri，并更新下一段的比例尺mi+1，即

图4 视觉粗定位示意图

3.3 避障导航

避障导航的目的是为了避开静态或动态障碍，同时检测自然路标，避障之后，恢复原始状态.避障步骤如下:

①在机器人的直行过程中利用声纳实时检测前方是否存在障碍物.若存在，则记录当前的前进方向rθ.

②根据滤波后的声纳数据判断机器人旋转方向以避开障碍物.

③机器人旋转一定角度后，根据声纳数据判断此时其前方是否存在障碍物.若不存在，则停止旋转并前行一小段距离，转向④;否则，继续转向③.

④机器人按照避障前的运行模式继续运行(如前行并调整摄像头检测自然路标等)，转向⑤.

⑤判断机器人是否到达下一个关键引导点，若是，则转向⑧;否则，转向⑥.

⑥根据声纳信息检测rθ方向处是否存在障碍物，如果存在障碍，则转向⑦;否则，转向⑨.

⑦根据声纳信息检测机器人前方是否存在障碍物，若是，则转向②;否则，转向④.

⑧退出避障状态，转入无障碍导航状态，并进行下一阶段的运行分析.

⑨机器人转向rθ方向，转入无障碍导航状态，并按照避障前的模式继续运行.

4 实验结果

本文以一台美国Pioneer3-DX 机器人为实验平台.从6 个不同角度进行导航实验.

1)实验1 考察导航方法能否顺利到达不同的目的地.如图5所示环境中，假设任务1 要使机器人从0 到达6 附近，存在一条0－1－2－3－4－5－6的导航路径，每个点附近分别有电风扇、吊兰、垃圾篓、椅子、吉他、雨伞可以作为路标.绘制手绘地图，输入起止距离约9 m.导航结果如图6(a)所示，其中S，D 分别为机器人的起点和终点，改变3 次目标区域D 的位置(分别为任务1～任务3).绘制不同的手绘地图，实验结果如图6所示.由图可见，机器人能够依据手绘地图和自然路标准确地到达不同的目标区域.部分偏差主要因为手绘地图为了便捷性而牺牲了精度.另外机器人的初始位置与手绘地图提供的起点偏差以及实际导航过程中遇到的各种障碍都会改变实际导航路线.

图5 导航任务示意图(单位:cm)

2)实验2 考察路标的绘制偏差对导航的影响.改变路标在地图上的绘制位置，3 次实验结果如图7所示.图中6 个圆限定了自然路标位置变动范围，里面的3 个符号表示每次实验时自然路标在手绘地图中的位置.由图可见，当自然路标的绘制位置在小范围内发生变动时，机器人仍然能够依据视觉识别自然路标在环境中的位置，修正手绘地图中的偏差，指导机器人完成导航.

图6 不同目标区域的导航实验

图7 自然路标的绘制偏差影响

3)实验3 考察自然路标在导航环境中挪动的影响.每次机器人从同一个起点以同样的位姿出发，仅改变真实环境中自然路标的摆放位置和姿态.每次实验路标挪动约1 m，结果如图8(a)所示.由图可见，小范围改变实验环境中的自然路标位置和姿态，会轻微影响机器人的导航路径.但是机器人仍然能够较为准确地到达目的地.说明该导航方法能够适应环境的动态变化，容许手绘地图与真实环境的位置差异.

图8 同类自然路标多次出现的影响

4)实验4 考察手绘地图中部分路标在真实环境中缺失时的影响.第1 次实验时环境中有电风扇、吊兰、垃圾篓、椅子、吉他、雨伞共6 个自然路标;第2 次实验时，有电风扇、吊兰、垃圾篓、吉他、雨伞共5 个自然路标;第3 次实验有电风扇、吊兰、吉他、雨伞共4 个自然路标.结果如图8(b)所示.由图可见，当部分物体被遮挡或者发生较大的位置变化导致部分路标缺失时，导航路径与手绘地图基本一致.因此，只要环境中的大部分自然路标与手绘地图一致，机器人仍然能够到达目的区域.

5)实验5 考察环境中有多个同类别的自然路标对机器人导航的影响.在8 个自然路标中，有3 个自然路标都是椅子，通过椅子位置变化，检测导航算法在不同方位对相同类别的自然路标的识别能力.实验结果如图8(c)所示.由图可见，若环境中有多个同类别的自然路标，利用本导航方法中的路标筛选方法，能够有效预测出当前状态下机器人最可能识别的自然路标，因此其导航结果基本不受影响.进一步证明了，本文提出的导航方法能够适应动态环境.

6)实验6 将实验1 中的自然路标替换为同一类别、不同外观的物体，考察本导航方法在环境改变下的导航情况，实验结果如图9所示.由图可见，以同一类别不同外观的物体作为自然路标，只要结构不发生太大的变化，BoW 物体识别模型仍然能够准确识别.以上实验表明本文提出的自然路标识别方法具有一定的通用性，在一定程度上能够克服同类物体的差异.

图9 自然路标外观变化的影响

5 结语

本文提出了一种基于BoW 物体识别模型的视觉导航方法，机器人以显著物体作为路标，依据手绘地图高效地完成导航任务.实验结果表明，即使自然路标的外观、位置和数量、环境发生改变，在手绘地图的粗略指导下，本导航方法仍然能够快速适应这些变化.该方法能容忍手绘地图的部分偏差，表现出很好的人机互动性，方便用户操作.目前自然路标数据库中的物体种类相对偏少，今后将会进一步扩充，实现更大范围的导航.

References)

［1］Bonin-Font B，Ortiz A，Oliver G.Visual navigation for mobile robots:a survey［J］.Journal of Intelligent and Robotic Systems，2008，53(3):263-296.

［2］许俊勇，王景川，陈卫东.基于全景视觉的移动机器人同步定位与地图创建研究［J］.机器人，2008，30(4):289-297.

Xu Junyong，Wang Jingchuan，Chen Weidong.Omnivision-based simultaneous localization and mapping of mobile robots［J］.Robot，2008，30(4):289-297.(in Chinese)

［3］Guo Yang，Xu Xinhe.Color landmark design for mobile robot localization［C］//IMACS Multi Conference on Computational Engineering in Systems Applications.Beijing，China，2006:1868-1874.

［4］Hu Huosheng，Gu Dongbing.Landmark-based navigation of industrial mobile robots［J］.International Journal of Industry Robot，2000，27(6):458-467.

［5］Hayet J B，Lerasle F，Devy M.A visual landmark framework for indoor mobile robot navigation［C］//Proceedings of ICRA′02 Robotics and Automation.Washington DC，USA，2002，4:3942-3947.

［6］Blanc G，Mezouar Y，Martinet P.Indoor navigation of a wheeled mobile robot along visual routes［C］//IEEE International Conference on Robotics and Automation.Barcelona，Spanish，2005:3354-3359.

［7］Madhavan R，Durrant-Whyte H F.Natural landmarkbased autonomous vehicle navigation［J］.Robotics and Autonomous Systems，2004，46(2):79-95.

［8］蔡自兴，王勇，王璐.基于角点聚类的移动机器人自然路标检测与识别［J］.智能系统学报，2006，1(1):52-56.

Cai Zixing，Wang Yong，Wang Lu.Corner clustering based detection and recognition of natural landmark for mobile robot［J］.CAAI Transactions on Intelligent Systems，2006，1(1):52-56.(in Chinese)

［9］李新德，吴雪建，朱博，等.一种基于手绘地图的动态环境视觉导航方法［J］.机器人，2011，33(4):490-501.

Li Xinde，Wu Xuejian，Zhu Bo，et al.A visual navigation method using a hand-drawn-route-map in dynamic environments［J］.Robot，2011，33(4):490-501.(in Chinese)

［10］Csurka G，Dance C，Fan L，et al.Visual categorization with bags of keypoints［C］//ECCV’04 Workshop on Statistical Learning in Computer Vision.Prague，Czech，2004:59-74.

［11］Zhao R，Grosky W I.Narrowing the semantic gap-improved text-based web document retrieval using visual features［J］.IEEE Transactions on Multimedia，2002，4(2):15-42.

［12］David G L.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.