多粒度栅格地图的创建与拓扑地图的自动生成

肖克来提+邓志东

摘 要：环境建模是无人驾驶汽车的关键技术之一，而栅格几何地图则是无人驾驶汽车进行环境建模、环境感知与自主导航的基础。为此，提出的多粒度多属性栅格地图不仅能表达具有不同粒度大小的数据级、特征级与决策级栅格地图，而且可以较全面地描述护栏、城市道路边缘、树干与电线杆、交通标志牌、车道线、斑马线、路口等多种属性。与此同时，自动提取的拓扑地图的精度可达到车道级水平。目前我们正在利用所提出的多粒度多属性栅格地图，进行基于地图匹配的精准自主导航新方法研究，并进一步基于此混合地图开展高可靠环境感知系统的研究与实践。第一部分是引言。第二部分介绍多粒度多属性栅格地图的创建。第三部分介绍基于栅格地图自动生成拓扑地图的方法。最后给出实验结果与分析。

关键词：多粒度栅格地图；拓扑地图；自动生成

中图分类号：TB

文献标识码：A

doi：10.19311/j.cnki.1672-3198.2016.23.133

1 一种多粒度栅格地图的创建

1.1 多属性地图的定义

创建栅格地图之前，必须首先给出栅格的定义，即单个栅格的表示或数据存储结构。本文用三个字节来表达栅格中的状态与属性信息。

一个占用栅格通过栅格状态及道路属性、栅格标志位属性和栅格交通标识属性等三个字节进行表达。栅格状态及道路属性字节，是指栅格状态值（即表示栅格是否被占用）、障碍物及其类型、车道线及其类型以及停止线等。栅格标志位属性字节，是指标志位，即该栅格是否为马路牙子、护栏、匝道、非结构化区域和地面箭头等。栅格交通标识字节，是指交通灯的类型和交通标志牌的类型。

1.2 栅格地图的多粒度表达

作为模糊粒度计算的起步，张钹等人提出了模糊商空间理论。所得到的主要结果有：证明了利用模糊等价关系可以将原来的商空间理论推广成模糊商空间理论，并给出了几个基本的定理。在这里我们将模糊粒度计算的概念应用到栅格地图当中。我们创建出来的基本占用栅格地图是细粒度地图，但是无人驾驶汽车的自主决策，通常需要多层次、多粒度的环境信息。此时需要生成一个具有不同分辨率的粗粒度地图。

算法1.1：

（1）基于激光雷达点云数据生成一个M×N二维细粒度栅格地图。

（2）确定粒度大小n，即一个粗粒度栅格由多少个细粒度栅格组成。

（3）定义Ai，j=fun（X）为从细粒度地图到粗粒度地图的映射函数。其中X为n×n的小栅格的状态属性矩阵，Ai，j是处在第i行，第j列的粗粒度栅格的状态属性值。映射函数可以根据所需要提取的宏观信息进行调整。在本文的实现中，映射函数是通过统计大栅格里被占用栅格的个数来确定大栅格是否被占用。

（4）基于映射函数返回的状态属性矩阵A生成粗粒度地图。

2 基于栅格地图的拓扑地图自动生成方法

拓扑地图是由多个顺序连接的点边组成。创建拓扑地图，首先是要确定组成拓扑地图的拓扑点集，其次要确定这些拓扑点集的顺序。有了拓扑点集和顺序之后，只要将各点按照原先的顺序以边的形式连接起来就可以生成拓扑地图了。

本文的拓扑点都是选自汽车行驶的实际轨迹。拓扑点取自轨迹点集有两个好处：一个是该点的定位非常精确，肯定是道路上可行驶的点，不会出现严重偏离车道的情况，因此该点实际就是定义车道的路点。其次轨迹点本身就有顺序，我们就不需要考虑怎么确定各点之间的连接顺序。

由于拓扑地图的提取目标是给出行驶环境的宏观信息，因此这些拓扑点必须具有代表性。对于一个直道，只需要在直道的两端各返回一个路点即可。而对于弯道，路口，U型掉头和环岛等情况，则需要加入多个路点才能表示出其复杂的结构信息，如图1所示。

算法2.1：

（1）将行驶轨迹经过的栅格标记到多属性栅格地图中，作为提取路点的候选拓扑点集。

（2）对栅格地图进行粗粒度化处理，并在粗粒度地图中保留斑马线属性以及标记为轨迹的栅格。

（3）取处在有斑马线属性的轨迹栅格中间的栅格为该斑马线的路点。

（4）计算每个轨迹栅格的航向角变化率Ψ，若Ψ大于阈值α且小于某阈值β，则认为该点是弯道上的路点。

（5）若航向角变化率Ψ大于β，则认为该点是U型调头上的路点。

（6）顺序连接以上提取到的路点，进而生成拓扑地图。

在实际操作过程中，有时我们需要在拓扑地图里面人为地插入一些路点，并确保这些路点在车道范围之内。这就应该先识别车道，再在车道水平上编辑路点。

在城市道路中，车道是由车道线划分的。一般地，一个车道可能在两个车道线的中间，也可能是处在车道线和城市道路边缘之间。我们恰好可以利用车道的这一特点提取车道特征。具体的提取方法如下：

算法2.2：

（1）我们由车体行驶方向的那条直线垂直的往两边用光栅跟踪算法扫描，直到碰撞道路边缘为止。

（2）再从道路边缘点往车体中行驶方向线垂直扫描，直道碰撞车道线为止。

（3）如果是双车道，则扫描结束，取所有扫描线的中心点的连线为车道的中心线，如图2（a）所示。

（4）如果是三车道或者是四车道，则在原来扫到的车道线的基础上再往车道行驶方向线垂直扫描，直道碰撞车道线为止。

（5）取所有扫描线的中心线的连线为车道的中心线，扫描结束。

3 实验结果

实验中采用了Velodyne公司生产的HDL-64E S2 64线激光雷达作为环境建模的测量设备，该设备提供了混合地图创建所需的关键数据-三维激光点云。图1（a）为基于细粒度地图生成的粗粒度地图，图1（b）为基于多属性地图生成的拓扑地图。

参考文献

[1]肖克来提，邓志东.基于激光雷达的多属性栅格地图的创建[J].信息与电脑：理论版，2016，（8）.

[2]张铃，张钹.基于商空间的问题求解（粒度计算的理论基础）[M].北京：清华大学出版社，2014.