一种基于低速特征和聚类算法的交叉口提取方法与流程

1.本发明涉及交通大数据应用领域，特别是指一种基于低速特征和聚类算法的交叉口提取方法。


背景技术：

2.随着gps(global position system)设备的普及和在日常生活中的大规模应用，由定位设备所采集的轨迹数据无处不在。由gps定位设备所产生的轨迹数据具有低成本、信息丰富、采集方便等优点，已经广泛应用到我们日常生活中的各个领域。随着城市建设的高速发展，路网信息也是不断地在进行变化。传统的测绘等路网信息提取技术又需要大量人力物力，且路网信息的提取周期过长。车辆gps轨迹数据覆盖范围广且成本低、周期短，基于车辆gps轨迹数据的路网信息提取具有现实意义。
3.交叉口是路网结构中的重要组成部分，城市交叉口的空间位置、范围及详细的内部结构是构成城市各级交通路网信息的关键。目前大部分交叉口提取的算法主要包括三类，基于gps轨迹数据的、数字图像的和多传感器组合的交叉口提取。其中，基于gps轨迹数据的交叉口提取方法主要有以下已有方案：基于局部连通性聚类算法的交叉口识别，利用交叉口与非交叉口处车辆转向大小不同、转向数量不用、转向类型不同筛选转向对及转向对，通过局部连通性聚类算法计算得到交叉口；基于多密度区划分的dbscan聚类算法的交叉路口提取，利用交叉口与非交叉口处车辆转向大小不同、转向数量不用、转向类型不同筛选转向对及转弯点，通过多密度区域划分的dbscan聚类算法进行交叉口的提取；这些算法的效果普遍一般，且仍有部分特征未被考虑。


技术实现要素：

4.本发明的主要目的在于克服现有技术中的上述缺陷，提出一种基于低速特征和聚类算法的交叉口提取方法，本方法考虑到车辆在平峰期经过交叉口的低速特征，根据车辆的航向变化提取出转弯点，根据低速点数目对转弯点进行剔除，聚类后得到交叉口信息，精确率高。
5.本发明采用如下技术方案：
6.一种基于低速特征和聚类算法的交叉口提取方法，包括以下步骤：
7.步骤1:读入轨迹数据；
8.步骤2:提取轨迹中的转向对，定义两个连续的gps定位点为转向对，并提取对应的转弯点，得到转弯点集合；
9.步骤3:筛选出平峰时段所有车辆轨迹的低速点；
10.步骤4:根据每一转弯点周围的低速点数量，剔除或保留该转弯点，得到筛选后的转弯点数据集；
11.步骤5:采用基于局部连通性的聚类算法，对筛选后的转弯点数据集进行分类提取类簇中心，得到交叉口。
12.具体地，所述的提取转弯点的方法为：
13.遍历所有的轨迹，当两个轨迹点p1(x1,y1,k1)和p2(x2,y2,k2)的航向角之差小于转向角阈值α
turn
，且两个轨迹点的时间之差小于时间阈值t
turn
，则两个轨迹点被判定为转向对，其中x，y，k分别为其坐标和其航向对应平面直角坐标系的斜率；并采用
[0014][0015]
计算转向对对应的转弯点tp(x,y)，最终得到转弯点集合tp＝{tp1,tp2,...,tpn}。
[0016]
具体地，所述剔除或保留该转弯点的判断方法为：
[0017]
给定一个阈值η∈[0,1]和一个半径阈值r
turn
，对得到的转弯点集合tp＝{tp1,tp2,...,tpn}，遍历集合tp，当tpi的半径范围r
turn
内低速点的个数tpi.clp和tpi的半径范围内所有点的个数tpi.cp满足tpi.clp＞tpi.cp
×
η时，则对当前的转弯点进行保留，否则认为其不满足转弯点的条件，舍去。
[0018]
由上述对本发明的描述可知，与现有技术相比，本发明具有如下有益效果：
[0019]
本发明提供了一种基于低速特征和聚类算法的交叉口提取方法，包括以下步骤：读入轨迹数据；提取轨迹中的转向对，定义两个连续的gps定位点为转向对，并提取对应的转弯点，得到转弯点集合；筛选出平峰时段所有车辆轨迹的低速点；根据每一转弯点周围的低速点数量，剔除或保留该转弯点，得到筛选后的转弯点数据集；采用基于局部连通性的聚类算法，对筛选后的转弯点数据集进行分类提取类簇中心，得到交叉口；本发明提出的方法考虑了车辆在经过交叉口时的低速特征，根据车辆的航向变化提取出转弯点，根据低速点数目对转弯点进行剔除，聚类后得到交叉口信息，精确率高。
附图说明
[0020]
图1为本发明实施例提供的一种基于低速特征和聚类算法的交叉口提取方法的流程图；
[0021]
图2为本发明实施例中基于低速特征和局部连通性聚类的交叉口提取算法的转弯点分布区域；
[0022]
图3为本发明实施例中基于低速特征和局部连通性聚类的交叉口提取算法的转弯点和低速点的分布图；其中图(a)为转弯点的提取分布，图(b)转弯点和低速点分布；
[0023]
图4为本发明实施例中基于低速特征和局部连通性聚类的交叉口提取算法的提取结果。
具体实施方式
[0024]
为使本发明实施方式的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施方式中的技术方案进行清楚、完整地描述。
[0025]
实施例：
[0026]
请参阅图1，本发明提供了一种基于低速特征和聚类算法的交叉口提取方法，该交叉口提取方法包括以下步骤：
[0027]
步骤1:读入轨迹数据。
[0028]
步骤2:提取轨迹中的转向对，并提取对应的转弯点。
[0029]
步骤3:筛选出平峰时段所有车辆轨迹的低速点。
[0030]
步骤4:根据转弯点周围的低速点数量，剔除或保留转弯点。
[0031]
步骤5:采用基于局部连通性的聚类算法，对不同交叉口进行分类提取类簇中心。
[0032]
本实施例采用厦门市大数据安全开放平台某比赛提供的厦门市巡游车和网约车gps轨迹数据集，时间段为2019年和2020年端午期间(2019年6月6日-6月9日、2020年6月24日-27日)的轨迹数据，其数据字典如表1所示。
[0033]
表1数据字典
[0034][0035]
实验区域采用厦门市湖里区，经度在[118.121926,118.180926]之间且纬度在[24.498138,24.548138]之间的区域，如图2所示，交叉口总数为126个，对轨迹数据也进行经纬度区间的筛选。
[0036]
在步骤1中，读入的数据定义如下：
[0037]
轨迹数据的定义为：轨迹集合traj＝＜s1,s2,...,sn＞，表示n条轨迹的集合。其中一条gps轨迹si＝{p1,p2,...,pm,cidi}，为一趟连续的轨迹点，其中p表示一个gps点，cidi表示第i趟轨迹的车辆编号。一趟连续的轨迹点为相邻时间间隔在10分钟以内的定位点的集合。
[0038]
gps点p描述为pi(lgt,ltt,drc,v)，其中lgt表示经度，ltt表示维度，drc表示航向角，即当前行驶方向与正北方向顺时针的夹角，v表示当前车辆的行驶速度。
[0039]
在步骤2中，转向对的定义如下，车辆在经过一个交叉口并完成转弯动作时，会留下至少两个连续相邻的轨迹点p1和p2，其中p1的航向角为p1.drc，p2的航向角为p2.drc，而δα为两点p1和p2航向的夹角。给定一个转向角阈值α
turn
和一个时间阈值t
turn
。当δα大于阈值α
turn
且前后两点的时间差小于阈值t
turn
时，我们称p1和p2为一对转向对，而轨迹点p1的航向和p2的航向的延伸线交点为这对转弯对的转弯点，记为tp
1,2
。
[0040]
p1(x1,y1,k1)和p2(x2,y2,k2)为一对转向对，其中x，y，k分别为其坐标和其航向对应平面直角坐标系的斜率。则转向对对应的转弯点tp(x,y)计算方法如下
[0041][0042]
遍历所有的轨迹，当两个轨迹点的航向角之差小于转向角阈值α
turn
，且两个轨迹
点的时间之差小于时间阈值t
turn
，则两个轨迹点被判定为转向对，最终得到转向对集合tp＝{tp1,tp2,...,tpn}。
[0043]
在步骤3中，对于每一个轨迹点，计算其速度，若轨迹点的速度v小于设定阈值，则标记其为低速点。
[0044]
在步骤4中，给定一个阈值η∈[0,1]和一个半径阈值r
turn
，使用在步骤2中得到的转弯点集合tp＝{tp1,tp2,...,tpn}，遍历集合tp，当tpi的半径范围r
turn
内低速点的个数tpi.clp和tpi的半径范围内所有点的个数tpi.cp满足tpi.clp＞tpi.cp
×
η时，我们对当前的转弯点进行保留，否则我们认为其不满足转弯点的条件，舍去。
[0045]
在步骤5中，对于转弯点集合tp中的任意两点tpi(ltti,lati)和tpj(lttj,latj)，使用
[0046]
c＝sin(lati)
×
sin(latj)
×
cos(ltt
i-lttj)+cos(lati)
×
cos(latj)
[0047]
geodistance(tpi,tpj)＝r
×
arccos(c)
×
π/180
[0048]
计算出它们的欧氏距离geodistance(tpi,tpj)，接着使用图2的算法1提取交叉口。
[0049]
评价方法和指标
[0050]
为了定量的对比不同方法之间的性能，本章使用精确率和召回率两个指标来评价地图匹配算法的有效性，其公式如下，其中，n
tp
、n
fp
、n
np
的值分别表示匹配算法正确提取交叉口的个数、错误提取交叉口的个数、未提取的交叉口个数。
[0051][0052][0053]
参数设置
[0054]
根据反复实验验证，转向对的前后角度差阈值在45、50、55和60
°
中选择60作为最佳取值。转向对的时间差阈值在15、20、25中选择20s作为最终取值。经过实验结果的可视化分析判断，将转弯点的统计低速点范围半径取30m且转弯点半径范围内低速点占比取值55％时，实验效果最佳。具体参数设置如表2所示：
[0055]
表2参数配置表
[0056][0057]
为了分析和验证本文算的有效性，将本文算法与以下算法进行对比实验，比较实验结果。
[0058]
算法1：基于局部连通性聚类算法的交叉口识别(2017)利用交叉口与非交叉口处车辆转向大小不同、转向数量不用、转向类型不同筛选转向对及转向对，通过局部连通性聚类算法计算得到交叉口；
[0059]
算法2：基于多密度区划分的dbscan聚类算法的交叉路口提取(2019)利用交叉口与非交叉口处车辆转向大小不同、转向数量不用、转向类型不同筛选转向对及转弯点，通过多密度区域划分的dbscan聚类算法进行交叉口的提取；
[0060]
我们的实验数据选取的均为城市平峰时段，早上10点至下午16点之间的时间范围内巡游车和网约车的gps轨迹数据。如图3所示，分别为转弯点的提取结果和低速点的在转弯点上的分布结果，其中，图(a)为转弯点的提取分布，图(b)转弯点和低速点分布。城市平峰期的低速点几乎包含于算法提取的转弯点范围内。可以明显看出在城市平峰期车辆轨迹的低速点比通过转向对提取的转弯点更集中于交叉路口处，通过两种方式的结合我们能更准确的提取城市交叉路口的空间位置。如图4所示，为基于低速特征和聚类算法最终聚类中心的结果图。
[0061]
分别将本文提出的城市平峰时段低速特征应用于基于局部连通性聚类算法的交叉口提取和基于多密度区域划分的dbscan聚类算法的交叉口提取。由于考虑到城市平峰期低速gps点的特征分布对转向对进行筛选，通过对传统提取转向对的方法进行改进，考虑到每一个转向对附近一定范围内在平峰时段低速gps点的占大小，若占比达到一定的阈值则保留，否则舍去，因此大大提高了交叉口提取算法的精确度。基于低速特征和局部连通性聚类的交叉口提取算法的伪代码如表3所示；
[0062]
表3：基于低速特征和局部连通性聚类的交叉口提取算法的伪代码
[0063][0064]
算法对比结果如表4所示，实验结果表明，引入了低速特征的交叉口提取算法后，算法的精确率和召回率都得到了明显的提高，其中基于低速特征的多密度划分的dbscan聚类算法的精确率最高，达到了97.54％。
[0065]
表4算法对比实验结果
[0066]
[0067][0068]
本发明提供了一种基于低速特征和聚类算法的交叉口提取方法，包括以下步骤：读入轨迹数据；提取轨迹中的转向对，定义两个连续的gps定位点为转向对，并提取对应的转弯点，得到转弯点集合；筛选出平峰时段所有车辆轨迹的低速点；根据每一转弯点周围的低速点数量，剔除或保留该转弯点，得到筛选后的转弯点数据集；采用基于局部连通性的聚类算法，对筛选后的转弯点数据集进行分类提取类簇中心，得到交叉口；本发明提出的方法考虑了车辆在经过交叉口时的低速特征，根据车辆的航向变化提取出转弯点，根据低速点数目对转弯点进行剔除，聚类后得到交叉口信息，精确率高。
[0069]
上述仅为本发明的具体实施方式，但本发明的设计构思并不局限于此，凡利用此构思对本发明进行非实质性的改动，均应属于侵犯本发明保护范围的行为。

技术特征：
1.一种基于低速特征和聚类算法的交叉口提取方法，其特征在于，包括以下步骤：步骤1:读入轨迹数据；步骤2:提取轨迹中的转向对，定义两个连续的gps定位点为转向对，并提取对应的转弯点，得到转弯点集合；步骤3:筛选出平峰时段所有车辆轨迹的低速点；步骤4:根据每一转弯点周围的低速点数量，剔除或保留该转弯点，得到筛选后的转弯点数据集；步骤5:采用基于局部连通性的聚类算法，对筛选后的转弯点数据集进行分类提取类簇中心，得到交叉口。2.根据权利要求1所述.一种基于低速特征和聚类算法的交叉口提取方法，其特征在于，所述的提取转弯点的方法为：遍历所有的轨迹，当两个轨迹点p1(x1,y1,k1)和p2(x2,y2,k2)的航向角之差小于转向角阈值α
turn
，且两个轨迹点的时间之差小于时间阈值t
turn
，则两个轨迹点被判定为转向对，其中x，y，k分别为其坐标和其航向对应平面直角坐标系的斜率；并采用计算转向对对应的转弯点tp(x,y)，最终得到转弯点集合tp＝{tp1,tp2,...,tp
n
}。3.根据权利要求1所述一种基于低速特征和聚类算法的交叉口提取方法，其特征在于，所述剔除或保留该转弯点的判断方法为：给定一个阈值η∈[0,1]和一个半径阈值r
turn
，对得到的转弯点集合tp＝{tp1,tp2,...,tp
n
}，遍历集合tp，当tp
i
的半径范围r
turn
内低速点的个数tp
i
.clp和tp
i
的半径范围内所有点的个数tp
i
.cp满足tp
i
.clp＞tp
i
.cp
×
η时，则对当前的转弯点进行保留，否则认为其不满足转弯点的条件，舍去。

技术总结
本发明提供了一种基于低速特征和聚类算法的交叉口提取方法，包括以下步骤：读入轨迹数据；提取轨迹中的转向对，定义两个连续的GPS定位点为转向对，并提取对应的转弯点，得到转弯点集合；筛选出平峰时段所有车辆轨迹的低速点；根据每一转弯点周围的低速点数量，剔除或保留该转弯点，得到筛选后的转弯点数据集；采用基于局部连通性的聚类算法，对筛选后的转弯点数据集进行分类提取类簇中心，得到交叉口；本发明提出的方法考虑了车辆在经过交叉口时的低速特征，根据车辆的航向变化提取出转弯点，根据低速点数目对转弯点进行剔除，聚类后得到交叉口信息，精确率高。精确率高。精确率高。


技术研发人员：王成 张明杰 丁成 苏敏咸 江培舟 李文锋
受保护的技术使用者：厦门卫星定位应用股份有限公司
技术研发日：2023.03.17
技术公布日：2023/7/11