基于地标的点云拓扑地图构建方法研究

申紫铭，郭鹏，李敏



基于地标的点云拓扑地图构建方法研究

申紫铭，郭鹏，李敏

（河北工业大学机械工程学院，天津 300130）

为了提高构建复杂空间点云拓扑地图的效率与准确性，提出了一种基于地标的拓扑地图构建方法。对目标空间进行点云数据采集，对采集的点云根据位置信息进行区域划分，并对每个划分好的区域进行点云特征提取，将提取的特征作为地标信息。对每个地标做拓扑处理，构建出拓扑地图。实验表明，该方法可以有效地构建出点云拓扑地图，为机器人的高效导航奠定基础。

地标；拓扑地图；特征提取；云数据

1 引言

目前，环境的空间表示方法主要分为两大类，分别是几何地图和拓扑地图。对复杂空间进行紧凑的表达时常通过拓扑地图的表达方法来完成[1]。拓扑地图是由Kuipers在1978年首先提出的，以点线面的结构组合形式来表现一个具有连通性的环境空间[2]，属于简洁、直观的环境表示方法。拓扑地图可将目标空间表示为带有节点与节点间的相关连接线的拓扑关系结构图，其中用节点表示目标空间中的某些重要位置点，例如拐角、桌子等，拓扑地图中的边用来表示不同的节点间的连接方式[3]。拓扑地图在路径规划中可以起到重要作用，为机器人提供简洁、高效的规划策略[4]，而且对存储空间大小与计算速度并无特别要求，所以在相同条件下拓扑地图的效率较高[5]。

但拓扑地图的劣势在于其重在描述目标空间的拓扑结构，而对目标空间无精确的位置关系要求，在节点的定义与选择方面也存在着难点，容易出现因环境的相似性造成的节点混淆等问题[6]。针对以上问题，本文提出了一种基于地标的拓扑地图构建方法：对目标空间进行点云数据采集，对采集的点云根据其位置信息进行区域划分，对每个划分好的区域进行点云特征提取，将提取的特征作为地标信息，对每个地标做拓扑处理，构建出拓扑地图。

2 目标空间的区域划分与地标选取

2.1 目标空间的区域划分

对目标空间进行区域划分时需要机器人在空间中不断行走，设置其行走步长，当走到步长值时，将经过的区域设为局部空间1，然后重复对局部空间1进行点云离散化处理，分析环境的结构特点，实现点云的权重信息精简，以满足实时性的要求，并对其轮廓进行分析提取特征，利用不变矩原理计算质心位置获得其局部质心坐标1，直到划分完整个目标空间，获得局部空间n与局部质心坐标n.最终形成局部空间{1，2，…，n}及其局部质心坐标{1，2，…，n}。机器人的行走过程如图1所示。

图1 机器人的行走过程

2.2 地标的选取

目标空间的区域划分完后，进行地标的提取，对局部空间中的点云数据进行特征提取与分割。本文中采用基于LCCP（局部凸连接聚类）的方法对局部空间中的典型物体进行提取。该算法分为两大部分，分别是基于超体聚类的过分割与基于超体聚类的再聚类。LCCP依赖于点云数据的空间形状信息和法线方向信息，用这些信息完成超体类聚过程。在完成超体类聚后，对过分割的点云计算不同块之间的凹凸关系，其凹凸关系是通过CC（Extended Convexity）和SC（Sanity Criterion）判据来判断的。判据方法如图2所示。

图2 凹凸关系判断图

以相邻两片法向量与中心线向量的夹角来判断凹凸性，如图2所示，当1＞2时，判断为凹；当1＜2时，判断为凸。因为所处理的数据会存在噪声问题，所以在判断时加入阈值，当1与2差值的绝对值大于时，为了避免误判，采用下列公式进行判断：

将每个块都做完凹凸关系判断之后，采用区域增长算法将块的小区域进行聚类形成较大的物体，然后对此提取的物体进行去噪，最后提取结果如图3所示。

图3 物体提取结果

最后，对每个区域都进行物体提取，将提取出的物体作为地标进行拓扑地图的构建，每个提取出的物体的质心坐标为地标的坐标，质心到物体最远点的距离作为地标的大小。

3 基于地标的拓扑地图构建

实验所用电脑配置Win10系统，4 G内存，3.3 GHz的台式电脑，所用软件为Matlab2017a，所用的实验数据为实验室的整体空间。实验时，使机器人在房间中漫游行走采集数据，按照1 m的步长划分区域，采集完信息后对其进行特征提取，然后进行拓扑地图的构建。

拓扑地图是用一张图来表示环境的畅通性。地图由两个基本要素节点和边组成，其顶点用来表示环境中的某些物体或者区域，在本文中使用提取的地标作为结点进行构建。边用来表示每个节点的连通情况，用机器人行走时所获取的点云信息中的墙壁表示。在本文中，对简单的房间进行了实验，选取其中的桌子作为地标，墙壁作为路径连通，实验结果如图4所示，为拓扑地图的构建结果，其中包含6个顶点和6条路径，顶点分别为v1、v2、v3、v4、v5、v6，边为e1、e2、e3、e4、e5、e6。

每个顶点的坐标值已知，路径长度已知，并且在导航时对机器人提供了专门针对环境的简洁说明，则其可以作为导航地图使用。在匹配拓扑地图的节点时，使用坐标变换公式将局部作为转换为全局坐标。导航时，只需输入要到达的目标地点，机器人则自动沿路径行走到达目标位置。

图4 拓扑地图

4 结论

本文提出了一种基于地标识别的拓扑地图构建方法，实验结果表明，该方法可以提高对复杂空间的点云拓扑地图在构建时的效率与准确性，解决了拓扑地图构建中的节点选择问题，为机器人的高效导航奠定了基础。

［1］王璐.未知环境中移动机器人视觉环境建模与定位研究［D］.湖南：中南大学，2007.

［2］王卫华，陈卫东，席裕庚.基于不确定信息的移动机器人地图创建研究进展［J］.机器人，2001，23（6）：563-568.

［3］Ghia U，Ghia K N，Shin C T.High-Re solutions for incompressible flow using the Navier-Stokes equations and a multigrid method［J］.Journal of Computational Physics，1985，48（3）：387-411.

［4］罗荣华，洪炳镕.基于信息融合的同时定位与地图创建研究［J］.哈尔滨工业大学学报，2004，36（5）：566-569.

［5］赵翊捷，陈卫东.基于地图的移动机器人定位技术新进展［J］.上海交通大学学报，2002，36（10）：1435-1438.

［6］樊征，曹其新，杨扬，等.面向移动机器人的拓扑地图自动生成［J］.华中科技大学学报（自然科学版）， 2008（Suppl 1）：172-175.

2095－6835（2019）03－0086－02

TP391.4

A

10.15913/j.cnki.kjycx.2019.03.086

申紫铭（1994—），男，河北廊坊人，硕士研究生，研究方向为特种机器人。

〔编辑：王霞〕