基于时空轨迹大数据的城市交叉口车道级结构提取方法

摘要

本发明提供一种基于时空轨迹大数据的城市交叉口车道级结构提取方法，降低了获取城市交叉口结构的成本，且探测方法简单、容易实现。该方法首先根据已有的道路中心线级别路网图，得到城市交叉口位置点，然后设置圆形缓冲区；然后利用轨迹跟踪方法，提取轨迹数据中航向角度变超过45度的轨迹点，记为：转向变化点；其次，利用密度聚类方法对转向变化点进行聚类，通过提取类簇中心及其之间的空间距离构建交叉口范围圆；最后，再一次利用轨迹追踪方法，计算轨迹穿过交叉口范围圆的交点，提取交叉口各转向进出口点，采用空间匹配方法与其相邻路段的车道中心线进行匹配，完成城市交叉口车道级结构提取。本发明得到的交叉口出入口点平面结构图正确率为94.3%。

说明书

技术领域

本发明涉及基于时空轨迹大数据的城市交叉口车道级结构提取方法，属于地 理信息系统与智能交通研究领域。

背景技术

城市道路网络信息是智能交通相关应用的基础。按照城市道路网络信息的精 细度，可以将城市道路网络分为：道路中心线网络、车行道级别网络以及车道级 别网络，其中表达路段的弧段和表达路网拓扑点的节点是道路网络构成的重要组 成部分。目前，获取城市道路网络信息的数据源包括：高分辨率遥感影像、时空 轨迹数据、激光点云数据等，而随着GPS装置的不断普及，时空轨迹数据成为 获取城市道路信息的重要数据源。相较于高精度遥感影像及激光点云数据，记录 移动目标随时间变化的空间位置及其他运动属性的时空轨迹大数据(大数据是指 无法在可承受的时间范围内用常规软件工具进行捕捉、管理和处理的数据集合) 来源广、成本低蕴含大量城市道路静态、动态信息。近几年，从时空轨迹数据中 提取城市道路信息，包括静态路网信息及动态交通流信息成为研究热点。国内学 者唐炉亮等人从2011年到2015年先后对城市车行道级别路网及车道级路网获取 进行了研究，并提出一种基于认知规律的城市车行道级别路网提取以及一种基于 混合高斯混合模型方法的城市道路车道数量获取。交叉口作为城市道路网络拓扑 点类型中的一种，是城市道路系统的重要组成部分，是城市道路上各类交通汇合、 转换、通过的地点，是管理、组织道路各类交通的控制点。国外学者FathiAlireza 和JohnKrumm(2010)采用图形描述器方法从专业采集车和辅助大众运输车辆采 集的高精度时空轨迹数据中探测城市交叉口并确定交叉口位置。此后，LiuJiang 等人(2013)提出基于测量车获取的高精度时空轨迹数据构建城市交叉口范围内 的道路拓扑图。Wang等人(2014)提出一种基于高采样率时空轨迹数据的城市 交叉口位置识别方法流程。该流程首先利用核密度方法，去除时空轨迹数据中的 漂移点；然后利用物理模型方法对时空轨迹进行融合，将没有融合在一起的时空 轨迹作为处于交叉口位置的疑似轨迹点；然后利用局部G统计，对疑似轨迹点 进行密度评估，选择符合评估阈值的轨迹点作为处于交叉口位置的轨迹数据，并 进一步对这些轨迹数据进行聚类，且构建以这些交叉口点为连接点的城市道路网 络图。然而，以上研究并未对交叉口局部范围内的平面结构进行深入解析和识别， 也没有进一步探究车道级路网与交叉口平面结构的空间融合。

发明内容

本发明在以上研究的基础上，提出了一种基于时空轨迹大数据的城市交叉口 车道级结构提取(交叉口范围确定，交叉口各转向点提取，交叉口各转向点与相 邻路段车道级路网空间融合)的新方法。

本发明提供一种基于时空轨迹大数据的城市交叉口车道级结构提取方法，包 括以下步骤，

步骤1、根据已有道路中心级别路网图，得到城市交叉口空间位置点，以各 交叉口空间位置点为中心点，设置圆形缓冲区；

步骤2、利用轨迹跟踪方法，计算位于圆形缓冲区内各轨迹的航向角变化， 提取出航向角度变化值的绝对值大于45度的轨迹点，标记为转向变化点；

步骤3、采用密度聚类方法对转向变化点进行聚类提取各类别中心点，计算 中心点间的空间距离选取最大值作为交叉口范围圆的直径；

步骤4、再一次利用轨迹跟踪方法，计算轨迹穿过交叉口范围圆后留下入口 交点与出口交点的航向角变化，并按照两个交点将轨迹分为位于交叉口范围内的 轨迹与位于交叉口相邻路段的轨迹；

步骤5、根据航向角变化值与转向属性之间的关系，对各条轨迹的入口交点 和出口交点的转向属性进行标示，并分别计算属于同一个转向属性的出口点集与 入口点集的中心点，提取交叉口出入口点平面图；

步骤6、对交叉口相邻路段的车道中心线进行提取，采用基于几何 匹配和语义匹配方法将交叉口平面结构与其响铃路段的车道级结构 进行空间匹配，完成交叉口车道级结构的提取。

所述步骤1，根据已有道路中心线级别的道路地图中已知交叉口空间位置点 (道路中心线级别的道路地图是由拓扑点和线条表示，其中拓扑点表示为道路交 叉口空间位置点，而连接两个拓扑点之间的线条即为道路路段)，以其作为中心 点设置圆形缓冲区，圆形缓冲区的半径推荐设置为50米(可按照所在城市地区 具体的交叉口设计面积自行设定缓冲区阈值)；

所述步骤2，根据步骤1获取的每一个交叉口的圆形缓冲区，采用轨迹跟踪 方法，跟踪经过每一个圆形缓冲区的所有时空轨迹数据，并计算每一条轨迹在该 圆形范围内航向角的变化情况，如果经过圆形缓冲区内轨迹的前一个轨迹点的航 向角与后一个航向角的角度差值的绝对值超过45°，那么就将这两个轨迹点标记 为转向变化点对；

所述步骤3，以步骤2中获取转向标记点对为对象，采用密度聚类方法对位 于同一个交叉口圆形缓冲区内的所有转向标记点进行聚类处理，并计算每一个聚 类类别的中心点，如何实现聚类并求解聚类类别中心点目前已经有很多方法，具 体实施时本领域技术人员可自行选择，此处不再赘述，然后计算各聚类中心点之 间的空间距离，构建聚类中心点空间距离矩阵，并从该矩阵中选取最大的空间距 离值，作为描述该交叉口空间区域的范围圆的直径，绘制交叉口范围圆，实现每 一个交叉口空间区域的重新分配；

所述步骤4，根据步骤3中获取的每一个交叉口范围圆，再一次利用轨迹跟 踪方法，记录轨迹穿过该范围圆的入口点和出口点(入口点与出口点也即为轨迹 与范围圆的两个交点，按照轨迹的行驶方向，与范围圆的第一个交点为入口点， 第二个交点为出口点)，然后按照轨迹与范围圆的两个交点，将该轨迹切割为“位 于交叉口范围内的轨迹”与“位于交叉口相邻路段的轨迹”，也即一条轨迹中位 于两个交点之间的那段轨迹为“位于交叉口范围内的轨迹”，其余剩下的轨迹为 “位于交叉口相邻路段的轨迹”，并将与入口点相邻的前一个轨迹点的航向值作 为该入口点的航向角度值，与出口点相邻的后一个轨迹点的航向值作为该出口点 的航向角度值；

所述步骤5，以步骤4获取的出入口交点及其航向角，计算两个交点的航向 值变化并提取交点的转向属性，其中具体计算如下所示：

1)如果入口点与出口点的航向角度值的差值大于-45°，那么将改入口点标 记为左转入口点，该出口点标记为左转出口点；

2)如果入口点与出口点的航向角度值的差值大于45°，那么将改入口点标 记为右转入口点，该出口点标记为右转出口点；

3)如果入口点与出口点的航向角度值的差值在0°左右，也即其差值在-10° 与10°之间，那么将改入口点标记为直行入口点，该出口点标记为直行出口点；

4)如果入口点与出口点的航向角度值的差值在180°左右，也即其差值在 170°与190°之间，那么将改入口点标记为掉头入口点，该出口点标记为掉头出 口点；

分别计算左转入口点集的中心点，左转出口点集的中心点，右转入口点集的 中心点，右转出口点集的中心点，直行入口点集的中心点，直行出口点集的中心 点，掉头入口点集的中心点，掉头出口点集的中心点，连接各类转向的入口点与 出口点，获取城市交叉口的出入口点平面结构；

所述步骤6，按照现有方法提取交叉口相邻路段的车道中心线(如何从轨迹 数据中提取车道中心线目前已经有很多方法，具体实施时本领域技术人员可自行 选择，此处不再赘述)，采用几何匹配方法寻找出与交叉口范围圆上的出入口点 相匹配的相邻路段，几何匹配方法推荐使用ICP算法(ICP算法具体算法原理目 前已经非常成熟，本发明不再赘述)，并采用语义匹配方法完成出入口点与其相 邻路段车道中心线端点的匹配(语义匹配目前已经有很多方法，具体实施时本领 域技术人员可自行选择)，将交叉口所有的出入口点集中心点与其相邻路段的车 道中心线进行空间匹配，完成交叉口车道级结构最终获取。

本发明构筑了一种基于时空轨迹大数据的城市交叉口车道级结构提取的方 法，降低了获取城市交叉口结构的成本，且探测方法简单、容易实现。

本发明所提供方法包括：首先通过已有的道路中心级别的路网图，获取交叉 口空间位置点，并以其为中心点，构建半径为50米的圆形缓冲区；其次采用轨 迹跟踪方法，跟踪经过该圆形缓冲区内的轨迹点的航向变化值，将航向变化值的 绝对值大于45°的轨迹点对标记为转向变化点对；然后采用密度聚类方法对这些 变化点进行聚类提取各聚类类别的中心点，通过计算聚类类别中心点的空间距离， 构建空间聚类矩阵，并选取矩阵中最大的距离值作为描述该交叉口空间范围的范 围圆直径，完成对各交叉口空间范围的重新划定；再进一步利用轨迹跟踪方法， 计算轨迹经过交叉口范围圆后与其相交的交点，按照两个交点的位置，将属于交 点之间的轨迹段标记为“位于交叉口范围内的轨迹”，其余轨迹段则标记为“位 于交叉口相邻路段的轨迹”，并为两个交点的航行值赋值；再进一步计算经过交 叉口范围圆的两个交点的角度变化值，并按照角度变化规律与转向之间的关系， 提取交点的转向属性，计算属于同一个转向属性的交点集的中心点，得到交叉口 出入点的平面结构；最后利用现有方法提取交叉口相邻路段的车道中心线，采用 几何匹配和语义匹配方法将交叉口相邻路段与交叉口出入口点进行空间匹配，完 成交叉口车道级结构的提取。本发明得到的交叉口出入口点平面结构图正确率为 94.3％。

附图说明

图1是本发明实施例的方法流程图；

图2是本发明实施例的交叉口圆形缓冲区；

图3是本发明实施例的轨迹转向变化点对提取结果；

图4是本发明实施例的轨迹转向点聚类结果及其中心点；

图5是本发明实施例的交叉口范围圆；

图6是本发明实施例的位于交叉口范围内的轨迹段与位于相邻路段的轨迹 段分割示意图；

图7是本发明实施例的交叉口出入口点集及出入口点平面结构；

图8是本发明实施例的交叉口出入口点与相邻路段车道级路网空间匹配示 意图；

图9是本发明实施例的交叉口车道级结构提取最终结果示意图。

具体实施方式

以下结合实施例和附图详细说明本发明技术方案。

本发明技术方案可采用计算机软件方式支持自动运行流程。参见图1，本发 明实施例提供的一种基于时空轨迹数据的城市交叉口车道级结构提取的方法，包 括如下步骤：

1)根据已有道路中心级别路网图，得到城市交叉口空间位置点，以各交叉 口空间位置点为中心点，绘制半径为50米的圆形缓冲区；然后进入2)利用轨 迹跟踪方法，计算位于圆形缓冲区内各轨迹的航向角变化，提取出航向角度变化 值的绝对值大于45度的轨迹点，标记为转向变化点；然后进入3)采用密度聚 类方法对转向变化点进行聚类提取各类别中心点，计算中心点间的空间距离选取 最大值作为交叉口范围圆的直径；然后进入4)再一次利用轨迹跟踪方法，计算轨 迹穿过交叉口范围圆后留下入口交点与出口交点的航向角变化，并按照两个交点 将轨迹分为位于交叉口范围内的轨迹与位于交叉口相邻路段的轨迹；进入5)根 据航向角变化值与转向属性之间的关系，对各条轨迹的入口交点和出口交点的转 向属性进行标示，并分别计算属于同一个转向属性的出口点集与入口点集的中心 点，提取交叉口出入口点平面图；最后进入6)利用现有车道中心线提取方法， 对交叉口相邻路段的车道中心线进行提取，采用基于几何匹配和语义匹配方法将 交叉口平面结构与其响铃路段的车道级结构进行空间匹配，完成交叉口车道级结 构的提取。

一种基于时空轨迹数据的城市交叉口车道级结构提取的方法，包括以下步骤，

步骤1，根据已有道路中心线级别的道路地图中已知交叉口空间位置点(道 路中心线级别的道路地图是由拓扑点和线条表示，其中拓扑点表示为道路交叉口 空间位置点，而连接两个拓扑点之间的线条即为道路路段)，以其作为中心点设 置圆形缓冲区，圆形缓冲区的半径推荐设置为50米(可按照所在城市地区具体 的交叉口设计面积自行设定缓冲区阈值)。

实施例具体实现如下，

已有的道路中心级别路网图，由表示交叉口的拓扑点与表示非交叉口的路段 组成，其中拓扑点在路网图中为节点，路段则为连接两个节点之间的线段。提取 道路中心级别路网图中的所有拓扑点，作为城市交叉口的空间位置点，然后以这 些空间位置点为中心，构建半径为50米的圆形缓冲区，如图2所示。

其中，圆形缓冲区的半径可以根据具体城市的交叉口的平面范围来定，例如: 国内小型城市的交叉口范围一般在直径为50米的圆以内；大中型城市的交叉口 范围一般在直径为100米的圆以内。

步骤2，根据步骤1获取的每一个交叉口的圆形缓冲区，采用轨迹跟踪方法， 跟踪经过每一个圆形缓冲区的所有时空轨迹数据，并计算每一条轨迹在该圆形范 围内航向角的变化情况，如果一条轨迹的在圆形缓冲区内，前一个轨迹点的航向 角与后一个航向角的角度差值的绝对值超过45°，那么就将这两个轨迹点标记为 转向变化点，如图3所示，具体实施步骤如下所示；

假设一条轨迹为T＝(p₁,p₂,…,p_n),其中p_i是该轨迹中的任意一个点，i＝1,2,…,n， 其中轨迹T经过交叉口缓冲区后，轨迹T的一段子轨迹p_k到p_k+t位于缓冲区内， 然后依次计算p_k+j与p_k+j+1的航向角度值差值，其中k＝1,2,…,n-1；j＝1,2,…,t；其中 k<t≤n,计算公式如下：

其中，θp_k+j是轨迹点p_k+j的航向值,θp_k+j+1是轨迹点p_k+j+1的航向值，如果 Δθ>45°,那么p_k+j与p_k+j+1就被标记为转向变化点对。

步骤3，以步骤2中获取转向标记点为对象，采用密度聚类方法对位于同一 个交叉口圆形缓冲区内的所有转向标记点进行聚类处理，并计算每一个聚类类别 的中心点，如图4所示，如何实现聚类并求解聚类类别中心点目前已经有很多方 法，具体实施时本领域技术人员可自行选择，此处不再赘述，然后计算各聚类中 心点之间的空间距离，构建聚类中心点空间距离矩阵，并从该矩阵中选取最大的 空间距离值，作为描述该交叉口空间区域的范围圆的直径并绘制交叉口范围圆， 实现每一个交叉口空间区域的重新分配，具体实施过程如下所述：

假设位于交叉口I的转向变化点对数据集为P，根据密度聚类算法得到多个 个聚类类别(聚类类别数量由交叉口的设计类型相关)C_a,a＝1,2,…,l；

其中每一个聚类类别C_a的类簇中心点为CP_a，然后计算CP_a之间的空间距 离，a＝1,2,…,l；具体计算公式如下：

其中和分别表示类簇中心点CP_h的x坐标和y坐标，和分 别表示类簇中心点CP_d的x坐标和y坐标，点CP_h与点CP_d分别为CP_a内任意两 个点，h＝1,2,…l；d＝1,2,…,l。

经过计算后，即可构建空间中心点的空间距离矩阵，选取max(Dis)作为描述 该交叉口的空间范围圆的直径，如图5所示。

步骤4，根据步骤3中获取的每一个交叉口范围圆，再一次利用轨迹跟踪方 法，记录轨迹穿过该范围圆的入口点和出口点(入口点与出口点也即为轨迹与范 围圆的两个交点，按照轨迹的行驶方向，与范围圆的第一个交点为入口点，第二 个交点为出口点)，然后按照轨迹与范围圆的两个交点，将该轨迹切割为“位于 交叉口范围内的轨迹”与“位于交叉口相邻路段的轨迹”，如图6所示。

步骤5，以步骤4获取的轨迹与交叉口范围圆的进出口点，计算两个交点的 航向值变化并提取交点的转向属性，具体实施步骤如下：

假设轨迹T＝(p₁,p₂,…,p_n),其中p_i是该轨迹中的任意一个点，i＝1,2,…,n，根据 轨迹T与交叉口范围圆的两个交点为TI₁与TI₂，其中TI₁是入口交点，是TI₂出 口交点；

p_c是与TI₁相邻的前一个轨迹点，p_e是TI₂相邻的后一个轨迹点，其中Ang_c是p_c的航向角度值，Ang_e是p_e的航向角度值，那么TI₁航向角度值θ₁与TI₂的航 向角度值θ₂分别为：

θ₁＝Ang_c公式3

θ₂＝Ang_e公式4

然后根据公式1，参考转向属性与航行角度值变化范围，提取出入口交点的 转向属性，具体计算如下所示：

1)如果入口点与出口点的航向角度值的差值大于-45°，那么将改入口点标 记为左转入口点，该出口点标记为左转出口点；

2)如果入口点与出口点的航向角度值的差值大于45°，那么将改入口点标 记为右转入口点，该出口点标记为右转出口点；

3)如果入口点与出口点的航向角度值的差值在0°左右，也即其差值在-10° 与10°之间，那么将改入口点标记为直行入口点，该出口点标记为直行出口点；

4)如果入口点与出口点的航向角度值的差值在180°左右，也即其差值在170° 与190°之间，那么将改入口点标记为掉头入口点，该出口点标记为掉头出口点；

分别计算左转入口点集的中心点，左转出口点集的中心点，右转入口点集的 中心点，右转出口点集的中心点，直行入口点集的中心点，直行出口点集的中心 点，掉头入口点集的中心点，掉头出口点集的中心点，连接各类转向的入口点与 出口点，获取城市交叉口的出入口点平面结构，如图7所示。

步骤6，按照现有方法提取交叉口相邻路段的车道中心线(如何从轨迹数据 中提取车道中心线目前已经有很多方法，具体实施时本领域技术人员可自行选择， 此处不再赘述)，采用几何匹配方法寻找出与交叉口范围圆上的出入口点相匹配 的相邻路段，几何匹配方法推荐使用ICP算法(ICP算法具体算法原理目前已经 非常成熟，本发明不再赘述)，并采用语义匹配方法完成出入口点与其相邻路段 车道中心线端点的匹配(语义匹配目前已经有很多方法，具体实施时本领域技术 人员可自行选择)，将交叉口所有的出入口点集中心点与其相邻路段的车道中心 线进行空间匹配，完成交叉口车道级结构最终获取，具体实施步骤如下：

首先，根据步骤4获取的位于相邻路段的轨迹段，利用现有方法提取这些轨 迹段中包含的道路车道中心线，将接近交叉口的车道中心线端点作为与交叉口出 入口点相匹配的空间点，并利用已有方法获取每一个车道中心线的转向信息，将 转向信息作为车道中心线端点的属性信息，存储到车道中心线端点的属性表中， 目前从时空轨迹数据中提取车道中心线及获取车道转向信息的方法有很多，具体 实施方法自行选取；

其次，以相邻交叉口的各路段的车道中心线端点为匹配基准，交叉口出入口 点作为待匹配对象，按照几何匹配方法ICP算法，实现车道中心端点与交叉口出 入口点的几何匹配，ICP算法原理目前已经非常成熟，具体步骤就不再赘述；

然后，利用语义匹配方法，对交叉口出入口点带有的转向属性与车道中心线 端点的转向属性进行匹配，实现多对多的属性匹配，如图8所示，因为该语义匹 配只需要对比字段相似度，且字段语义复杂度极低，同时具体匹配方法目前有很 多，具体实施方法可以自行选取，不再赘述；

最后，根据各路段车道中心线与交叉口出入口点的匹配结果，构建交叉口车 道级结构图，也即获得车道中心线端点与其他位于同一个交叉口的车道中心线端 点之间的相连关系及专项属性，如图9所示。

基于本发明，可以方便地从GPS轨迹数据中获取待城市交叉口车道级信息， 为未来智能导航及无人驾驶提供基础路网数据。

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技 术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用 类似的方式替代，但并不会偏离本发明的精神或超越所附权利要求书所定义的范 围。