S觟ren Schwertfeger，于天彦

（1.中国科学院 上海微系统与信息技术研究所，上海200050；2.上海科技大学 上海200031）

拓扑地图中的房间检测

（1.中国科学院 上海微系统与信息技术研究所，上海200050；2.上海科技大学 上海200031）

测绘是许多机器人应用的一个重要组成部分。为了评估测绘步骤的表现，需要对其得出的地图的质量进行衡量。地图对定位与路径规划而言都至关重要。本文以先前比较机器人所生成地图与基准地图的拓扑结构的尝试中已经使用的拓扑图匹配法为基础，采用Alpha Shape法对房间等地图开放区域的检测进行了扩展，通过在450幅由不同原始地图添加噪声后形成的地图上进行的充分测试，显示房间检测为匹配算法的稳定性与鲁棒性带来提升。

机器人学；拓扑地图；房间检测；Alpha Shape

在机器人领域，环境地图是其所在环境的模型，该地图通常用二维网格地图的形式表达。而拓扑图则是仅包含地点及其连接的更抽象表达。拓扑地图已在许多方面得到应用，如地图融合[1]、地点检测[2，3]或规划[4]。同时也有不同的二维网格地图生成方法，如基于细化[5]或 Voronoi图[6-7]。

所有的地图都会带有一定程度的由定位错误所带来的误差[8]。之前的拓扑地图质量评估算法通过对拓扑地图进行匹配，并测量其匹配误差，从而决定地图的质量[9，10]。在密闭空间和走廊上，算法的结果良好，但在开放区域内，由于Voronoi图对于墙壁上的噪音极其敏感，导致在同一测试环境的开放区域内不同地图对应的拓扑图无法与基准地图相匹配。

文中通过将房间视为拓扑图中的一个节点，并使此节点与相邻走廊相连。对拓扑图进行了简化，并提升了匹配准确度。

1 定 义

图由一个节点集合V、一个边集合E所组成的有序对G=（V，E）定义。拓扑图为包含节点及节点间可作为行驶路线的边的图。节点是图中边的起始或终止位置。边则用于表示图中节点间的连接关系，而路径由首尾相连且不含其内部连接节点的边构成。其始节点为第一条边的始节点。其终节点是最后一条边的终节点。一条边只可能属于一条路径。单向路径（边）是两个节点间的一条有向路径（边），其对偶路径（边）的始节点是其终节点，其对偶路径（边）的终节点则是其始节点。始节点或终结点仅与路径自身及其对偶路径相连的路径为死路径。

房间定义为边缘上的任意两个障碍物间距离大于某固定阈值的区域。本文中，房间为Alpha Shape算法生成的多边形。边界节点是位于某一路径与某一房间交叉处的节点。房间ID为房间的标识，其默认值为-1。房间中心节点是房间检测完成后，在房间中心位置新生成的节点。

2 拓扑图中的房间检测

房间内部有很少或无障碍物，其内部生成的拓扑图的边与路径对墙壁附近的噪点较敏感。本文中，由Alpha Shape法获取的内部多边形将被视为不同的房间。随后，建立每个房间多边形的中心节点，并在路径与多边形的交点处建立新节点，除边界节点之外的所有房间内部节点及内部边被删除后，需将边界节点与房间中心节点用边相连。

2.1 拓扑图的生成

在此对拓扑图的生成过程进行简要说明，更详细的说明参见文献[9-10]。本文借助Voronoi图由二维网格地图生成拓扑图。Voronoi图是对空间的一种小区域分割方法[11]。在删除死路径，合并相近的节点后，最终得到一个具有节点、边和路径的拓扑地图。

2.2 寻找房间

此处使用Alpha Shape算法来检测房间多边形。Alpha Shape是最初由 Edelsbrunner、Kirkpatrick 与Seidel所定义[12]的欧几里德平面中与一个有限点集的形状相关的一系列线段所构成的简单曲线。其使用的Alpha值可对其内部障碍物之间的最小距离加以限制。

2.3 边界节点的生成

拥有各房间所对应的多边形后，还要在路径与各房间的交点处添加新的“边界节点”。此处通过对路径进行逐一检查，以寻找该路径是否与房间有交点，若有，需确定交点的具体位置，并返回一个存有交点位置与其所在路径始节点间路径长度的列表，列表中的长度将用于随后的路径切割。

2.4 在边界节点处切割路径

对于所有生成的边界节点，切割长度lvoric是其所在路径始节点与该节点间的路径长度，该长度介于0和路径全长之间。当切割长度接近0或接近路径全长lvori时，由于浮点数表达不精确，需使用阈值ε确定接近程度（ε设为0.000 000 01）。在始节点或终节点切割时只返回含有Evori的列表，否则返回含有切割后的两条新路径的列表。

在对某单向路径Evorik（1≤k≤M）进行切割时，通过对其中首尾相连的单向边 （Etopo1、Etopo2、...、EtopoN）长度（ltopo1、ltopo2、...、ltopoN）进行累加，并与 lvoric 进行比较，以确定切割位置。若切割后返回的单向路径列表的大小为1时，只需将其切割位置的始节点或终节点标记为边界节点，否则需采用相同参数切割其对偶路径，添加新的边界节点，并在其边连接列表中加入新建立的边及其对偶边。该边界节点的房间ID与该位置与此路径相交的多边形的房间ID相同。

2.5 设置房间ID

边界节点的房间ID已在切割时设置，而其他节点的房间ID为默认值-1。这些节点中，有的在房间多边形内，有的不在任何房间多边形内。多边形内节点的房间ID被设为Alpha Shape所生成的多边形列表中该多边形所对应的ID，而其他节点的房间ID则保持不变。全部节点设置完成后，房间ID为默认值-1的节点将可被视为不在任何房间多边形内。

其后，比较每条路径的始节点和终节点的房间ID相等与否，若两者相同，则判断该值是否为默认值，若为默认值则忽略，否则将该路径及其对偶路径的房间ID设为该值。若两者不同，当该路径为死路径且长度不大于阈值minLenThreshold（设为20个像素）时，将其末节点（只有两条路径相连的始节点或终节点）房间ID设为两者中的非默认值，这会为之后移除短死路径带来便利。

2.6 移除短死路径

仅与两条互为对偶的路径相连的节点被称为死节点，这两条路径则为死路径。若一个边界节点与一条长度小于minLenThreshold的死路径相连，则需将死路径及其对应的死节点、边界节点及与之相连的房间内路径从拓扑图中删除。

因为Alpha Shape无法伸入房间角落部位，故时常会有虽然不在房间多边形内，但实际上在房间内的节点（如图2中节点10）。由于之后需要由单一节点表达房间，故需将这些节点删除。

2.7 建立包含房间的拓扑图

将所有房间内路径和除边界节点之外的房间内节点移除后，还需逐一建立代表房间的新节点。这些节点位于多边形中心位置，并与所有该房间的边界节点相连，同时拥有该多边形（图中的有色区域）的相关信息。

一个非自交叉的封闭多边形的中心可由其边界上的N个点计算得到。设这些点为：

则多边形的中心为（Cx，Cy），其中

上述公式[13]中，边界上的点沿多边形的边界依次出现，且被逐一按其出现顺序编号。其中，点（xN，yN）与（x0，y0）相同。

图1 含Voronoi图和Alpha Shape的地图

图2 采用房间检测由图1生成的拓扑图

图3 不采用房间检测由图1生成的拓扑图

3 实 验

本章将展示算法的有效性，并通过广泛的实验证明房间检测为拓扑图匹配所带来的提升。

图4 含Voronoi图和Alpha Shape的地图

图5 采用房间检测由图4生成的拓扑图

图6 不采用房间检测由图4生成的拓扑图

3.1 机器人世界杯救援比赛地图

测试中使用的拓扑地图由2010新加坡救援机器人世界杯的原始地图[14，15]生成。这些地图已被用于一些基于拓扑地图的测试中，其对应的三维地图也被用于三维地图评估测试[16]。

图1、4展示了地图及其生成的复杂的Voronoi图和Alpha Shape，图2、5则展示了修剪后的拓扑图及检测出的房间，与不采用房间检测直接生成的拓扑图（图3、6）相比，可见拓扑图复杂度有了明显降低。

3.2 对匹配的影响

测试过程选用了5幅地图，一幅来自文献[3]（命名为“Beeson”），一幅来自数据库[17]（命名为“Belgioioso”），其它三幅（“EdmontonConvention Center”、“Longwood”、“SDR Site B”）则来自另一数据库[18]。为了保证一致的测试条件，首先对参与测试的地图进行了灰度化和细化，随后，从原地图中删除一定比例的黑色像素点（设为白色），再以随机方式选择同样数量的黑色像素点，并将距离每个选中的黑色像素点一个固定距离内的某个像素点（具体距离与位置随机确定）设为黑色，由此为地图添加随机噪点。

图7 Belgioioso地图

图8 Edmonton Convention Center

图9 Longwood地图

图10 SDR Site B

测试中，比例（p）为{2%，8%，14%}，距离 dr为{1，2，3}。 图 11 中展示了当 dr为 1，p=2 时，对 Beeson地图使用房间检测算法的结果。为使结果更明显，房间区域用不同深度的颜色表示。

图11 Beeson地图

对于每个不同的{dr，p}值对，需由每个原始地图生成10个随机化后的地图用于测试，其中第一个地图为基准地图，用于与其它地图进行匹配。匹配过程中，对每个由随机化地图所生成的拓扑图中的每个节点进行遍历，同时在由基准地图生成的拓扑图中找到与之距离最近的节点（视为匹配），并累计该距离。遍历后累计值（视为匹配误差和）的均值可作为房间检测算法稳定度的度量。在由同一地图以不同随机化程度生成的地图上，该值见表1～5。

表1 Beeson地图距离比较（alpha值：200）

表2 Belgioioso地图距离比较（alpha值：250）

表3 Edmonton地图距离比较（alpha值：500）

表4 Longwood地图距离比较（alpha值：250）

从结果中可见，使用房间检测后的拓扑图有明显的优势。这一结果当然也与具体地图有关，若其中障碍物间距与Alpha Shape算法的Alpha值接近，则房间自身很容易受噪点影响（如图9的Longwood地图，表4）。这时，房间检测所带来的优势就变得很有限。而其他包含大房间的地图则从房间检测中获益良多。这在图 11（Beeson地图，表 1）与图 7（Belgioioso地图，表2）中都有一定体现。

总的来说，噪点与墙壁间距离越远，房间检测所带来的正面效应就越少，因为它们会越来越多地影响房间的整体拓扑结构，但p值对比率的整体影响较小。效率方面，用于比较的两幅地图的拓扑图生成过程（含房间检测与匹配）的速度很快，单地图耗时还不到一秒。

表5 SDR地图距离比较（alpha值：422）

4 结 论

文中展示了基于Alpha Shape算法，对二维网格地图的房间检测过程，并使用提取出的房间多边形对拓扑图进行修改。由此产生的拓扑图仅使用单一节点表示一个房间，通过在通向房间的边与房间的交点处增加新节点的方式，很好地保持了原拓扑图中房间与其周围节点间的连接关系。算法在机器人世界杯救援比赛地图上表现良好。测试中，基于上述方法生成的450幅随机化地图，对算法稳定度和可重复性进行了客观评估。

由于算法生成的地图具有一定的稳定性，可将本文中算法与文献[7]中的拓扑图匹配相结合。今后，还可将其与另一文献[19]中的路径匹配相整合。未来，这一算法将有助于生成适用于多样化应用场景的极为鲁棒的地图。

[1]Saeedi S， Paull L， Trentini M， et al.Group mapping:A topological approach to map merging for multiple robots[J].Robotics&Automation Magazine，IEEE，2014，21（2）:60-72.

[2]KaraoguzH，BozmaH I.Reliabletopological place detection in bubble space[C]//Robotics andAutomation (ICRA),2014 IEEE International Conference on,2014:697-702.

[3]Beeson P， Jong N K， KuipersB.Towards autonomous topological place detection using the extended voronoi graph [C]//Robotics and Automation,2005.ICRA 2005.Proceedings of the 2005 IEEE International Conference on,2005:4373-4379.

[4]Konolige K， Marder-eppstein E， Marthi B.Navigation in hybrid metric-topological maps[C]//Robotics and Automation （ICRA），2011 IEEE International Conference on,2011:3041-3047.

[5]Portugal D，Rocha R P.Extracting topological information from grid MAPS for robot navigation[C]//ICAART （1）， 2012:137-143.

[6]Gadre A S， Du S，Stilwell D J.A topological map based approach to long range operation of an unmanned surface vehicle[C]//ACC，2012:5401-5407.

[7]Lau B，Sprunk C，Burgard W.Improved updating of Euclidean distance maps and Voronoi diagrams[C]//Intelligent Robots and Systems （IROS）,2010 IEEE/RSJ International Conference on,2010:281-286.

[8]Schwertfeger S， Jacoff A， Pellenz J，et al.Using a fiducial map metric for assessing map quality in the context of robocup rescue[C]//Safety,Security,and Rescue Robotics (SSRR),2011 IEEE International Symposium on,2011:208-214.

[9]Schwertfeger S，Birk A.Evaluation of map quality by matching and scoring high-level,topological map structures [C]//Robotics and Automation（ICRA）,2013 IEEE International Conference on,2013:2221-2226.

[10]Schwertfeger S，Birk A.Map evaluation using matched topology graphs[J].Autonomous Robots,2016，40（5）:761-787.

[11]Klein R.Abstract voronoi diagrams and their applications[G].Computational Geometry and its Applications.Würzburg,FRG:Springer,1988:148-157.

[12]Edelsbrunner H，Kirkpatrick D G，Raimund S.On the shape of a set of points in the plane[J].Information Theory， IEEE Transactions on，1983，29（4）:551-559.

[13]Bourke P.Calculating the area and centroid of a polygon[Z]，1988.

[14]Sheh R，Kimura T，Ehsan M，et al.The robo cup rescue robot league:guiding robots towards fieldable capabilities[C]//Advanced Robotics and its Social Impacts （ARSO）,2011 IEEE Workshop on,2011:31-34.

[15]Sheh R，Jacoff A，Ann-Marie V，et al.Advancing the state of urban search and rescue robotics through the robocuprescue robot league competition[C]//Field and service robotics,2014:127-142.

[16]Birk A， Others.Using fiducialsin 3D map evaluation[C]//2015 IEEE International Symposium on Safety,Security,and Rescue Robotics（SSRR），2015:1-7.

[17]University of Freiburg. Robotics datasets:Belgioioso castle[Z].2002.

[18]HOWARD A,ROY N.The robotics data set repository(radish)[Z].2003.

[19]Schwertfeger S，YU Tian-yan.Matching paths in topological maps[C]//会议/论文集缺失，2016.

Room detection for topological maps

Mapping is an important part of many robotic applications.In order to measure the performance of the mappingprocess we have to measure the quality of its result:the map.The map is essential for robotic algorithms like localizationand path planning.In this paper，based on the Topology Graph matching method which has been used in comparingthe topology of the robot generated map to the topology of a ground truth map，a novel algorithm with Alpha Shapeis applied to open areas'detection as an extension of the previous approach.On 450 maps which are generated by adding noise to different original maps，the experiments show the algorithm makes the matching method more stable and robust.

Robotics； topological map； room detection； alpha shape

TP242

A

1674－6236（2017）12-0027-06

2016-06-01稿件编号：201606004

S觟ren Schwertfeger（1979—），男，德国人，博士，博士后研究员，助理教授。研究方向：搜救机器人的智能化功能及其性能评估。