基于步行轨迹的复杂道路中心线提取方法

李俊杰， 刘鹏程， 顿玉多吉

(1.武汉大学遥感信息工程学院， 武汉 430079；2.华中师范大学城市与环境科学学院 地理过程分析与模拟湖北省重点实验室， 武汉 430079；3.西藏自治区气象局， 拉萨 850000)

数字地图作为国家重要的基础地理信息，也是智能交通系统构建的基础，在交通管理、车辆导航、城市规划以及网络地图服务等方面发挥着巨大作用[1].相较于传统的使用测绘和遥感影像判读获取数字地图路网数据，基于GPS轨迹的路网提取具有精度高、采集成本低、数据来源广、实时性强等特点.随着物联网技术和众源地理信息技术的发展，如何从海量的GPS时空轨迹数据中有效地挖掘丰富的道路信息，成为地理信息领域研究的热点[2].

目前，使用GPS轨迹数据提取路网主要分为4类方法：1)基于轨迹聚类，例如文献[3]采用K-Means算法对轨迹点进行聚类，并引入了样条曲线拟合道路转弯区域；文献[4]采用数学模型中的直线和弧来描述GPS轨迹，根据定位点和行驶方向将大量GPS轨迹点聚类后连接成轨迹链，采用非线性最小二乘法拟合出了道路中心线.2)基于增量化的方法，如文献[5]对轨迹点进行分类，判断空间和语义关系，将轨迹点合并到候选路网中；文献[6]基于轨迹合并提出了一种通用地图生成方法，使用人工智能算法推断道路的几何特征，采用聚类算法增量生成路网.3)基于Delaunay三角网，如文献[7]基于约束Delaunay三角网提取道路中轴线从而建立街道路网；文献[8]引入约束Delaunay三角网及其对偶Voronoi图几何模型，从车辆轨迹线中提取出了道路边界.4)基于栅格图像细化，如文献[9]对车辆GPS轨迹数据栅格化，基于数学形态学合并离散数据点，最后使用SPTA算法细化得到道路网；文献[10]对车辆轨迹数据创建缓冲区，然后采用交叉数细化算法细化出租车轨迹数据，构建路网.相较于前3种方法，栅格细化方法将大量矢量轨迹数据点转化为图像运算，提高了计算效率.

当前现有研究多基于车载GPS轨迹数据(出租车、公交车、专业采集车)提取城市车道级路网，忽略了校园、社区、公园、旅游景区等小范围区域内的复杂道路信息.其主要原因在于车道级道路级别高、路面宽阔，而类似于校园、景区等小范围区域往往包含复杂的道路信息，不仅具有行车道，还有纵横交错、形态多样的小路，交通方式以步行为主，不适用于GPS采集车进行轨迹采集.步行GPS轨迹相较于车载GPS轨迹具有如下特点：1) 自由度高，不受现有路网约束，能够达到车载GPS不能到达的地方；2) 方向多变，下一时刻的方向存在任意性；3) 速度较慢，变化幅度小，一般在0.5～6 km/h之间[11]；4) 受采集人员的经验、采集过程、采集设备等因素影响，数据质量具有不确定性.为此，本文在顾及区域中存在人车混行、小路交错的情况下，设计了一种基于步行GPS轨迹数据的复杂区域道路中心线提取方法.

1 复杂道路中心线提取原理和方法

使用步行GPS轨迹数据提取复杂道路中心线技术路线如图1所示，首先对大量步行GPS数据进行清洗，根据GPS轨迹点分布密度进行栅格化，然后基于栅格细化思想构建小范围内的矢量路网.栅格细化能够在保证拓扑结构和道路连通性不变的情况下，保留道路特征点并提取出栅格路网的道路中心线.

1.1 GPS轨迹数据清洗

步行GPS轨迹点由于定位精度误差、多路径效应、网络状态不稳定、长时间驻留在某区域会产生大量冗余的甚至错误的定位数据，数据清洗能够避免给道路提取算法带来额外开销，还有利于提高精度.轨迹数据清洗主要包括去除漂移点和停留点，如图2所示，漂移点是由于GPS定位误差产生的明显偏离实际道路的异常点，停留点是GPS采集设备在小范围内长时间停留和聚集的区域，也被称为停滞点和感兴趣区域.

图1 复杂道路中心线提取技术路线图Fig.1 Technical roadmap of complex road centerline extraction

图2 GPS定位漂移点和停留点Fig.2 GPS positioning drift point and stay point

在图2(a)中，把GPS轨迹看作连续时间序列，计算定位点A到P的平均速率v.

(1)

若v大于给定的速度阈值T，则判断P为漂移点，进行去除.其中，Δt为GPS采样周期，|AP|表示轨迹点AP之间的球面距离，计算表达式如下：

(2)

其中，λ1，λ2是以孤度制表示的两点经度，φ1，φ2是以弧度制表示的两点的纬度，R为地球半径，取R=6378137 m.

本文设计的基于空间聚类去除停留点的主要原理是通过聚类中心替代类簇中的所有点达到轨迹抽稀的目的.考虑到轨迹的方向性，本文在DBSCAN聚类算法基础上进行改进，算法流程图如图3所示，设置扫描半径r和最小包含点数min Pts，从未被访问的点开始，扫描该点半径范围内包含的轨迹点个数N，当N>min Pts时聚类并计算聚类中心，但不对类簇进行扩展，而是直接以聚类中心点代替本簇中包含的种子点，直到访问完所有轨迹点.

1.2 基于分布密度的轨迹点栅格化

GPS轨迹点是包含定位信息的点状要素，而道路是在空间上连续分布的地理实体，GPS轨迹栅格化就是将离散的地理定位点坐标变成连通的数字图像坐标，旨在实现道路空间上的连通.本文设计了一种基于分布密度的轨迹点栅格化方法，如图4所示，在GPS轨迹空间定义外包矩形T，对任意轨迹点P，满足P∈T.以Res×Res方形网格对区域T进行划分，将GPS轨迹空间划分为m×n个单元，Res变量确定了最终栅格化的分辨率，既要考虑到空间中大部分轨迹能够相互连通，又要避免将两条距离很近的小路归为一条道路.统计GPS轨迹点在基本单元中的分布密度ρ，设置给定的阈值α.当ρ>α时，认为该区域为道路候选区域.基于轨迹点的分布密度不仅实现了栅格化，同时进一步过滤掉了稀疏的误差轨迹点.轨迹点栅格化后可能出现空洞点和断裂，采用数学形态学的闭运算进行填补和修复，如公式(3)所示：

AB=(A⊕B)⊖B，

(3)

其中，⊕为数学形态学膨胀运算，⊖为腐蚀运算.

图3 去除停留点算法流程图Fig.3 Algorithm flow chart of removal of stay point

图4 轨迹点栅格化Fig.4 Rasterization of trajectory points

1.3 栅格细化提取道路中心线

路网栅格细化前，需要将栅格图像进行二值化处理变成黑白二值图像，如公式(4)所示，二值图像能够减小存储、方便判别，提高图像处理效率.其中，G(i，j)表示单一像素灰度值，B(i，j)表示二值化结果.

(4)

路网栅格图像细化，就是不断去除边缘像素，生成连通的单位像素宽度的中心线骨架[12]，使用结构元素序列B对二值化栅格图像A进行细化运算如公式(5)所示：

AB=A-(AB)，

(5)

1.4 道路中心线矢量化

矢量化是将道路中心线的栅格数据结构转为矢量线状数据结构的过程，传统的追踪法在矢量化过程中容易将细化后产生的边缘毛刺也进行矢量化，从而影响实际效果.本文在此基础上进行改进，其中心线矢量化原理如图5所示，追踪法需要先搜寻出弧段交点，然后沿弧段追踪进行矢量化.图5(a)为细化后的中心线，二值化指定存在道路像素为1，否则为0，遍历每个像素P(x，y)的八邻域σP(x，y)={(x-1，y-1)，(x-1，y)，(x-1，y+1)，(x，y-1)，(x，y+1)，(x+1，y-1)，(x+1，y)，(x+1，y+1)}，定义道路的交点节点(Intersection Node，IN)为P(x，y)∈{sum≥3|sum=∑P(xi，yi)，P(xi，yi)∈σP(x，y)}，定义道路的悬挂节点(Dangling Node，DN)为

P(x，y)∈{sum=1|sum=∑P(xi，yi)，

P(xi，yi)∈σP(x，y)}，

如图5(b)所示.选定其中任意一个交点节点，沿“1”出发，直到到达下一交点或者悬挂节点，计算IN→DN的路径长度L，若L小于最小悬挂长度阈值，则此路径不存入结果集合中.对所有交点执行上述操作，最终矢量化结果如图5(c)，矢量化后对于道路弯曲的情况采用道格拉斯-普克算法[18]进行化简处理.

图5 基于追踪法的中心线矢量化Fig.5 Center line vectorization based on tracking method

2 实验结果及分析

2.1 数据来源

实验数据来源于19名采集人员3周时间内使用GPS轨迹采集软件在华中师范大学校园(不包括南湖校区)采集的1 022 026个轨迹点，覆盖了校园教学楼、办公楼、食堂、运动场和学生宿舍等日常活动区域，轨迹点信息如表1所示，采集的GPS轨迹点分布如图6所示.

表1 轨迹点信息表

图6 GPS轨迹点分布图Fig.6 GPS Trajectory points distribution diagram

2.2 道路中心线提取实验

实验在普通PC机上进行，处理器为Intel Core i7-6700 3.40 GHz，内存RAM为32 GB，编程语言采用python.设置速度阈值为2 m/s去除漂移点，设置扫描半径eps为1 m，最小包含点数min Pts为5，去除停留点.为提高路网提取的效率和精度，对不同细化算法进行比较，效果如图7所示，并统计细化时间，如表2所示.

图7 不同细化算法结果Fig.7 Results of different thinning algorithms

表2 不同细化算法处理时间

细化效果上，Hilditch经典算法产生的边缘毛刺较多，Pavlidis算法边缘毛刺最少，但细化后容易出现断裂，基于数学形态学的细化算法则断裂更为严重.Zhang-Suen快速细化算法和Rosenfeld 细化算法效果类似，但处理时间上，Zhang-Suen快速细化更有优势，因此，采用Zhang-Suen快速细化算法作为路网栅格细化算法.最终提取的矢量道路中心线如图8所示.

图8 校园矢量路网Fig.8 Campus vector network

2.3 精度评价

采用Goodchild等提出的基于缓冲区的道路中心线几何精度评价方法[19]定量评价提取精度，以百度地图为参考路网，建立半径为d的缓冲区，实际提取的道路中心线落入到缓冲区中的长度占总长度的比值即为提取精度.这里，分别设置缓冲区半径2 m、5 m和7 m，同时将本研究实验结果与文献[10]中的方法进行对比，结果如图9所示.

图9 道路提取精度评价Fig.9 Evaluation of road extraction accuracy

由图9分析可知，当以2 m、5 m和7 m容错范围建立缓冲区时，本文方法提取的路网精度分别为29.2 %、68.8 %和78.6 %，相较于文献[10]中的方法有明显提高.因为传统的GPS轨迹点栅格化以固定缓冲区半径实现路网的连通，本文采用基于轨迹点密度的栅格化方法，能够较好的自动适应不同宽度的道路.实验结果验证了本研究设计的基于步行GPS轨迹数据的道路中心线提取方法能够实现复杂道路的提取，且提取效果较好.

在7 m缓冲区范围内仍有部分道路未被提取出来，考虑到本文提出的方法依赖于大量的GPS轨迹，当此路段未采集到GPS轨迹点或者GPS轨迹点数量较少时，在数据清洗和栅格化过程中会被过滤，出现道路缺失的情况.但同时，本文的方法提取出了复杂的小路信息，极大丰富了路网密度，相较于GPS采集车具有明显的优势.

3 结论

1) 针对包含复杂道路的校园景区等区域的道路提取，提出了一种基于步行GPS轨迹数据的道路中心线提取方法，且提取效果较好，为复杂路况区域的道路提取提供了新的思路.

2) 与传统的栅格细化提取路网方法相比，本文在数据清洗的基础上，根据人车混行的复杂道路特点，以GPS轨迹点分布密度作为栅格化标准，这样在保证道路连通性的基础上最大限度适应不同道路宽度，提高了细化提取中心线的精细程度，同时进一步过滤了定位误差数据.

3) 校园、景区和社区是人流量较密集的区域，互联网时代，人人都是传感器[20]，人人能够自发分享日常出行、活动、娱乐等路途中步行GPS轨迹，将志愿者地理信息(Volunteered Geographic Information， VGI)[20]作为路网更新的数据源，能够节省人力物力，在较短时间内有效地整合大量轨迹数据资源.因此，今后需要建立和完善VGI数据采集平台，基于道路提取算法自动化完成路网的及时提取和更新，为导航定位、出行安全、区域规划、应急救援等提供高效的基础地理服务.