基于低精度时空轨迹数据的城市交叉口自动识别的方法

摘要

本发明提供一种基于低精度时空轨迹数据的城市交叉口自动识别的方法，降低了获取城市交叉口的成本，为未来自主驾驶和智能交通提供基础数据和方法参考。该方法首先从轨迹数据的空间密度及时间间隔出发，对数据进行预处理；其次，跟踪并识别轨迹的转弯过程，提取一次转弯过程中航向角度变化值超过转向角阈值且时间间隔小于时间阈值的转弯点对；然后，利用基于距离和空间的生长聚类方法得到转弯点对的聚类类簇及类簇中心；最后基于局部点连通的聚类方法，对转弯点对类簇进行归类，通过分析这些类簇中心点的转向属性及其中心点个数，完成交叉口自动识别。本发明得到的交叉口识别正确率为94.3%。

说明书

技术领域

本发明涉及基于低精度时空轨迹数据的城市交叉口自动识别的方法，属于地 理信息系统与智能交通研究领域。

背景技术

城市道路交叉口是城市道路系统的重要组成部分，是城市道路上各类交通汇 合、转换、通过的地点，是管理、组织道路各类交通的控制点。在整个道路网中， 交叉口成为通行能力与交通安全上的卡口，并且在智能交通导航应用中占有举足 轻重的地位。当前城市交叉口探测的方法数据源不同主要分为两类：从高分辨率 遥感影像数据中识别交叉口和从时空轨迹数据中提取城市交叉口位置。利用时空 轨迹大数据提取城市交叉口结构是目前研究的热点话题。相较于采样率在1s且 定位精度在5m以内的高精度轨迹数据而言，由国内出租车及公共交通运输工具 采集的时空轨迹数据，其定位精度在10-15m左右，采样间隔为10-60s，是一种 低精度GPS数据。FathiAlireza和JohnKrumm(2010)采用图形描述器方法从专 业采集车和辅助大众运输车辆采集的高精度时空轨迹数据中探测城市交叉口并 确定交叉口位置。此后，LiuJiang等人(2013)提出基于测量车获取的高精度时 空轨迹数据构建城市交叉口范围内的道路拓扑图。Wang等人(2014)提出一种 基于高采样率时空轨迹数据的城市交叉口位置识别方法流程。该流程首先利用核 密度方法，去除时空轨迹数据中的漂移点；然后利用物理模型方法对时空轨迹进 行融合，将没有融合在一起的时空轨迹作为处于交叉口位置的疑似轨迹点；然后 利用局部G统计，对疑似轨迹点进行密度评估，选择符合评估阈值的轨迹点作 为处于交叉口位置的轨迹数据，并进一步对这些轨迹数据进行聚类，且构建以这 些交叉口点为连接点的城市道路网络图。然而，以上研究并未对交叉口局部范围 内的平面结构进行深入解析和识别。同时，利用高采样率和高定位精度的时空轨 迹数据获取城市交叉口位置，虽然具有精度可靠的特点，但是也存在数据采集成 本高、周期长且无法反应因为城市建设和车道功能改变等引起的道路交叉口结构 变化的局限性。同高采样率及高定位精度的时空轨迹数据相比，来源于城市出租 车系统或者其他采集设备的低精度时空轨迹数据，虽然定位精度低、采样频率低， 但是其海量信息包含了丰富的道路信息。目前利用低精度时空GPS轨迹数据获 取城市交叉口结构信息是一个难点，而大量的研究仍然停留在道路网络地图提取， 对交叉口的自动识别还处于研究阶段。

发明内容

本发明在以上研究的基础上，提出了一种基于低精度时空轨迹数据的城市交 叉口自动识别的新方法。

本发明提供一种基于低精度时空轨迹数据的城市交叉口自动识别的方法，包 括以下步骤，

步骤1，数据预处理；利用密度聚类方法剔除掉原始低精度轨迹数据中的漂 移点，再选取采样间隔小于15s的轨迹数据；

步骤2，跟踪并识别轨迹的转弯过程，提取一次转弯过程中航向角度变化值 超过转向角阈值且时间间隔小于时间阈值的转弯点对；

步骤3，利用基于距离和空间的生长聚类方法，对所有的转弯点对进行聚类 计算，直到每一个转弯点对找到其归属类别为止；

步骤4，计算各转弯点对类簇中心，采用基于局部点连通性的聚类方法，若 两个类簇中心是直接可达的，则将这两个类簇中心划分为同一类，直到所有的类 簇中心得到划分；

步骤5，将属于同一个类别的类簇中心点作为对象，通过分析这些类簇中心 点的转向属性及其中心点个数，完成交叉口自动识别。

所述步骤1，数据预处理。低精度时空轨迹数据一般有两个特征，一是，数 据定位精度较低，二是，数据采样间隔不一致，范围从5s浮动到60s之间，因 此需要对数据进行预处理操作。预处理操作包括两个方面：首先，采用现有的密 度聚类方法，剔除原始浮动车数据中低密度漂移点，目前密度聚类方法非常成熟， 具体实施时可以自行选择，不在赘述，然后，选取原始数据中采样间隔小于15s 的轨迹数据；

所述步骤2，根据步骤1预处理后的数据，利用车辆在交叉口区域的行驶特 点：车辆在交叉口处存在左转、右转、直行、掉头这几种类型的组合，例如：(左 转，右转，掉头)，(左转，右转，掉头，直行)，(左转，右转，直行)几种，计 算轨迹点中前一个轨迹点与后一个轨迹点之间的航向角度变化值，并按照航向角 度变化值与转向属性之间的关系，标示状态变化点对的转向属性；

所述步骤3，对步骤2获取的具有左转、右转、掉头转弯点对，分别进行基 于角度和距离的空间聚类。转弯点对的空间相似性从距离和角度两方面度量，首 先将转弯点对用坐标向量表示；然后，考虑到轨迹转弯点对之间的角度和距离的 量纲和量级不同，会对最终的空间相似性造成很大影响，为了消除该影响对它们 做标准化处理；最后对两者加权求和得到转弯点对的空间相似性，用公式1表示。 在聚类过程中，首先选取一个转弯点对作为初始类别，按照公式1计算转弯点对 两两之间的相似度，将满足聚类相似度阈值的归属到同一类，不断迭代，直至所 有转弯点对都归属到对应的类别，且聚类类别不再发生变化为止：

所述步骤4，根据步骤3获取的各转向状态变化点对聚类类簇，利用现有的 类簇中心点方法首先计算每个转弯点对类簇的中心点，位于同一交叉口的转弯点 对类簇，其中心点必然集中在相应的交叉口区域。利用DBSCAN区域连通性的 思想，采用基于局部点连通性分析的聚类方法，给定搜索半径阈值R，如果两个 中心点的距离小于R，认为这两个点是可达的；对每一个中心点搜索其邻域内的 其他中心点，得到初始类簇，然后将每个簇内的点直接可达的点吸收进来，不断 迭代，直到已有的簇不再增长或者没有新簇出现为止。将属于同一空间范围的转 弯点对类簇的中心归为一类；

所述步骤5，分析步骤4获取的归属于同一空间范围的转弯点对类簇中心， 对交叉口进行自动识别，具体方法：

1)如果属于同一空间范围的转弯点对类簇中心点的属性仅有左转和右转两 种，且中心点的数量也仅有两个，那么将其表示为非交叉口，也即属于道路转弯 点；

2)如果属于同一空间范围的转弯点对类簇中心点的属性仅有掉头一种类型， 那么就将其标示为非交叉口，也即属于道路转弯路段；

3)如果属于同一空间范围的转弯点对类簇中心点的属性不属于前两种情况， 那么就将其标示为交叉口；

完成最终的交叉口自动识别。

本发明构筑了一种基于低精度时空轨迹数据的城市交叉口自动识别的方法， 降低了获取城市交叉口的成本，为未来基于交叉口探测城市交通流信息、城市道 路路网更新、城市道路路网拓扑点提取提供基础数据和方法参考。本发明所提供 方法首先，利用密度聚类方法剔除掉原始低精度轨迹数据中的漂移点，再选取采 样间隔小于15s的轨迹数据；其次，跟踪并识别轨迹的转弯过程，提取一次转弯 过程中航向角度变化值超过转向角阈值且时间间隔小于时间阈值的转弯点对；然 后，利用基于距离和空间的生长聚类方法，对所有的转弯点对进行聚类计算直到 每一个转弯点对找到其归属类别为止；再进一步，计算各转弯点对类簇中心，采 用基于局部点连通性的聚类方法，如果两个类簇中心是直接可达的，那么将这两 个类簇中心划分为同一类，直到所有的类簇中心得到划分；最后，将属于同一个 类别的类簇中心点作为对象，通过分析这些类簇中心点的转向属性及其中心点个 数，完成交叉口自动识别。

本发明得到的交叉口识别正确率为94.3％。

附图说明：

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

图2是本发明定义的转弯点对示意图；

图3是本发明实施例转弯点对提取结构；

图4是本发明实施例转弯点对相似度评价示意图；

图5是本发明实施例交叉口区域的转弯点对聚类结果示意图，5a为左转的 转弯点对聚类结果，图5b为右转的转弯点对聚类结果，

图6是本发明实施例交叉口自动识别结果；

具体实施方式

本发明设计了基于低精度时空轨迹数据的城市交叉口自动识别的方法，降低 了获取城市交叉口结构的成本，且探测方法简单、容易实现。本发明所提供的方 法如下：首先，利用密度聚类方法剔除掉原始低精度轨迹数据中的漂移点，再选 取采样间隔小于15s的轨迹数据；其次，跟踪并识别轨迹的转弯过程，提取一次 转弯过程中航向角度变化值超过转向角阈值且时间间隔小于时间阈值的转弯点 对；然后，利用基于距离和空间的生长聚类方法，对所有的转弯点对进行聚类计 算直到每一个转弯点对找到其归属类别为止；再进一步，计算各转弯点对类簇中 心，采用基于局部点连通性的聚类方法，如果两个类簇中心是直接可达的，那么 将这两个类簇中心划分为同一类，直到所有的类簇中心得到划分；最后，将属于 同一个类别的类簇中心点作为对象，通过分析这些类簇中心点的转向属性及其中 心点个数，完成交叉口自动识别。

本发明提出基于低精度时空轨迹数据的城市交叉口自动识别的方法，从大量 GPS轨迹数据中自动识别交叉口，为未来基于交叉口探测城市交通流信息、城市 道路路网更新、城市道路路网拓扑点提取提供基础数据和方法参考。本发明技术 方案可采用计算机软件方式支持自动运行流程。以下结合实施例和附图详细说明 本发明技术方案。

参见图1，本发明实施例提供了一种基于低精度时空轨迹数据的城市交叉口 自动识别的方法，具体操作步步骤如下：

步骤1，数据预处理。低精度时空轨迹数据一般有两个特征，一是，数据定 位精度较低，二是，数据采样间隔不一致，范围从5s浮动到60s之间，因此需 要对数据进行预处理操作。预处理操作包括两个方面：首先，采用现有的密度聚 类方法，剔除原始浮动车数据中低密度漂移点，目前密度聚类方法非常成熟，具 体实施时可以自行选择，不在赘述，然后，选取原始数据中采样间隔小于15s的 轨迹数据；

步骤2，根据步骤1预处理后的数据，利用车辆在交叉口区域的行驶特点： 车辆在交叉口处存在左转、右转、直行、掉头这几种类型的组合，例如：(左转， 右转，掉头)，(左转，右转，掉头，直行)，(左转，右转，直行)几种，计算轨 迹点中前一个轨迹点与后一个轨迹点之间的航向角度变化值，并按照航向角度变 化值与转向属性之间的关系，标示状态变化点对的转向属性，具体实施方法如下 所示：

车辆在道路行驶时，通常不会突兀的改变行驶方向，只有在经过弯道或者交 叉口时，航向角才会发生比较明显的变化。在弯道处，车辆的转弯类型比较单一， 而在交叉口区域，由于交叉口结构复杂，车辆的转弯类型也比较多样，因此可以 利用轨迹的转弯特征来识别交叉口。

低精度时空轨迹数据定位精度在10-15m左右，采样频率为5-60s，在完成一 次转弯过程中，车辆轨迹通常在交叉口或弯道附近区域保留2-4个轨迹点。为了 提取轨迹的转弯特征，本发明提出转弯点对的概念。转弯点对是指车辆在完成一 次转弯过程中留下的前后两个轨迹点，这两个轨迹点的航向角变化值大于给定的 阈值θ。如图2所示，某一车辆完成一次转弯过程中留下P₁和P₂两个轨迹点， 轨迹点P₁的航向角为θ₁，相邻的下一个轨迹点P₂的航向角为θ₂，两个轨迹点航 向角度变化值为△θ。给定转向角阈值θ，如果△θ若大于给定的阈值θ，则认为 轨迹点P₁和P₂是一个转弯点对，具体计算步骤如下：

第一步：初始化所有轨迹数据，将所有的轨迹数据按照车辆编号和时间排序；

第二步：按照车辆编号顺序和时间顺序逐个跟踪轨迹，计算同一辆车相邻两 个轨迹点P₁、P₂的航向角度变化值△θ₁，进入第三步；

第三步：如果第二步中航向角度变化值△θ₁的绝对值大于给定的转向角阈值 θ(如a，b，c三种判断条件所示)，则将P₁，P₂保存为一个转弯点对，记录航 向角度变化值△θ₁，并重复第二步继续跟踪轨迹，否则进入步骤第四步，具体转 向属性判断包括：a.△θ₁大于-45°，那么将该变化点对标示为左转变化点对；b. △θ₁大于45°，那么将该变化点对标示为右转变化点对；c.△θ₁在180°左右，也 即△θ₁在170°与190°之间，那么将该变化点对标示为调头变化点对；

第四步：如果航向角度变化值△θ₁的绝对值小于给定的转向角阈值θ，则继 续跟踪与P₂相邻的轨迹点P₃，计算轨迹点P₁、P₃的航向角度变化值△θ₂；

第五步：重复上述步骤，遍历所有的轨迹点；

步骤3，对步骤2获取的转弯点对及其转向属性，如图3所示，按照属性对 各转弯点对分别进行基于角度和距离的空间聚类。本发明中对转弯点对聚类的目 的是为了区分同一交叉口中不同转向类型的轨迹，因此对转弯点对的相似性度量 只需要考虑空间相似性，而不需要考虑时间相似性。转弯点对的空间相似性从距 离和角度两方面度量。首先将转弯点对用坐标向量表示，按照时间顺序，从前一 个轨迹点指向后一个轨迹点，如图4所示，用向量P和向量Q分别表示转弯点 对P_i(x_pi，y_pi)、P_j(x_pj，y_pj)和Q_i(x_qi，y_qi)、Q_j(x_qj，y_qj)，其中x_pi，y_pi，x_pj，y_pj，x_qi， y_qi，x_qj，y_qj分别为点P_i，P_j，Q_i，Q_j的平面横坐标及纵坐标，P_i和Q_i的距离为 d_i，P_j和Q_j的距离为d_j，向量P和向量Q的夹角为△θ。轨迹转弯点对之间的角 度和距离的量纲和量级不同，会对最终的空间相似性造成很大影响。为了消除该 影响对它们做标准化处理，最后对两者加权求和得到转弯点对的空间相似性。转 弯点对相似度计算公式如下：

ω₁，ω₂分别表示距离和角度的权重值，且ω₁>0，ω₂>0，ω₁+ω₂＝1；diff_d表 示转弯点对之间的距离，按照时间顺序分别计算前后两个时刻点上转弯点对上对 应的两点的欧式距离，将两个距离求平均值作为转弯点对之间的距离，并对距离 标准化。计算公式如下：

diff_△θ表示转弯点对之间的角度，即转弯点对向量之间的夹角，并对角度标 准化。计算公式如下：

diff_△θ＝1-cos(Δθ)(公式3)

本实施例在聚类过程中，首先选取一个转弯点对作为初始类别，按照公式1 计算转弯点对两两之间的相似度，将满足聚类相似度阈值的归属到同一类，不断 迭代，直至所有转弯点对都归属到对应的类别，且聚类类别不再发生变化为止， 具体聚类步骤如下所示：

第一步，对转弯点对分类，令顺时针方向为正，步骤1中转弯的阈值设为 45°，记转弯点对的角度变化值为△θ。若+45°<△θ<+135°，转弯点对为右转， 如果-45°>△θ>-135°，转弯点对为左转，如果135°<|△θ|<180°，转弯点对为掉 头(在步骤5处理掉头情况)，对左转和右转的转弯点对分别执行步骤2.1-2.5；

第二步，将所有的转弯点对标记为未被聚类，从未被聚类的状态点对集中随 机选取一个转弯点对，将其作为初始类别，在对转弯点对进行空间相似性度量时 距离和角度同样重要，因此令权重ω1＝ω2＝0.5，然后利用公式1计算该转弯点 对与其他未被聚类的转弯点对之间的相似度值。

第三步，如果当前转弯点对与某一个其他转弯点对的相似度值满足聚类相似 度阈值(以角度差异45°、距离差异为15m时所对应的相似度值作为相似度阈值 进行聚类，本实例中将阈值设为0.8)，将该转弯点对与当前转弯点对聚为一类， 并标记类别；

第四步，找出与当前转弯点对不能聚为一类的转弯点对，对所有未被标记的 转弯点对重复第二步和第三步，直到所有转弯点对都归属到与其对应的聚类类别。

第五步，通常情况下，在非交叉口区域浮动车可能存在少数非法掉头，随机 转弯等情况，因此非交叉口区域的转弯点对数量非常少，而且这些转弯点对之间 相似性较低；在交叉口区域，则分布有较多数量且相似度较高的转弯点对，统计 所有聚类结果包含的转弯点对数量分布近似服从泊松分布，设置置信度为0.95 的置信区间，小于置信区间下限的聚类类簇在交叉口路口的可能性很小，因此选 择大于置信区间下限的聚类结果，将可能在交叉口区域的转弯点对提取出来。

如图5所示：图5a为左转的转弯点对聚类结果，图5b为右转的转弯点对聚 类结果。可以看出该聚类算法能够较准确的区分不同转向的转弯点对。

步骤4，基于局部点连通性的聚类方法识别交叉口，并剔除弯道。首先计算 每个转弯点对类簇的中心点，位于同一交叉口的转弯点对类簇，其中心点必然集 中在相对应的交叉口区域。交叉口范围大小不一，同一交叉口最远的两个转弯点 对类簇中心点的距离可能会超过两个相邻交叉口的距离，为了识别步骤3中获取 的转弯点对类簇分别属于哪一个交叉口，利用DBSCAN区域连通性的思想，采 用基于局部连通性分析的聚类方法，假设搜索圆的半径为R，以P1为核心对象， 检测到Q1在其搜索邻域内，建立类别C，然后检测Q1的搜索邻域，将在Q1 搜索邻域的点也归属到类别C中，不断迭代，将属于同一交叉口的转弯点对类 簇的中心归为一类，并根据同一类中转弯点对簇中心的数量判断是否为弯道，如 果是弯道，则剔除。

具体的识别方法如下：

第一步，计算步骤3中获取的转弯点对类簇的中心点；

第二步，初始化第一步中的类簇中心点集U；检测U中未被标记过的点P， 如果点P未被标记则检查以P为中心，以R为半径的邻域，如果邻域内存在其 他点，认为这些点是与点P直接相连的，建立新类别C，并将这些与点P直接相 连的点加入候选集N；

第三步，检测候选集N中未被标记的点Q，检查以Q为中心，以R为半径 的邻域，如果存在与其直接相连的点，则将点Q加入候选集N；如果Q未标记 为任何一个类别，则将Q加入类别C；

第四步，重复第二步，继续检测候选集N中未标记的点；

第五步，重复第二步到第四步，直至检测过所有的点。

第六步，对交叉口进行识别，识别条件如下所示：a.如果属于同一空间范围 的转弯点对类簇中心点的属性仅有左转和右转两种，且中心点的数量也仅有两个， 那么将其表示为非交叉口，也即属于道路转弯点；b.如果属于同一空间范围的转 弯点对类簇中心点的属性仅有掉头一种类型，那么就将其标示为非交叉口，也即 属于道路转弯路段；c.如果属于同一空间范围的转弯点对类簇中心点的属性不属 于前两种情况，那么就将其标示为交叉口；完成交叉口自动识别。

基于本发明，可以方便地从低精度时空轨迹数据中对城市交叉口进行自动识 别，为未来基于交叉口探测城市交通流信息、城市道路路网更新、城市道路路网 拓扑点提取提供基础数据和方法参考。

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