文章快速检索  
  高级检索
出租车GPS轨迹集聚和精细化路网提取
邬群勇1,2,3, 吴祖飞1,2,3, 张良盼1,2,3     
1. 福州大学空间数据挖掘与信息共享教育部重点实验室, 福建 福州 350002;
2. 卫星空间信息技术综合应用国家地方联合工程研究中心, 福建 福州 350002;
3. 福建省空间信息工程研究中心, 福建 福州 350002
摘要:针对利用GPS数据提取双向路网和交叉路口转向信息精度低的不足,本文提出一种顾及位置与行驶方向的轨迹集聚和精细化路网提取方法,实现了精细化路网提取。为提高交叉路口路网的提取精度,首先剔除原始轨迹中的离散和异常轨迹点,并按一定的步长对轨迹段进行加密;然后引入行驶方向角来表达车辆在轨迹点处的行驶方向,顾及位置和行驶方向获取每个轨迹点的相似轨迹点集合;接着依次计算每个轨迹点的偏移距离,通过对轨迹点的迭代偏移完成轨迹集聚;最后剔除未成功集聚的轨迹点,将完成集聚的轨迹点连成轨迹线并作缓冲区,运用栅格数据数字化方法提取得到能够反映道路精细转向关系的道路网。以福州市出租车GPS数据进行轨迹集聚和路网提取试验,结果表明:本文方法能有效地将GPS轨迹按车辆行驶方向分别进行集聚,提取的道路网为双向道路并且能反映交叉路口处道路的精细转向关系。
关键词出租车GPS轨迹    轨迹集聚    双向路网    精细路网    路网提取    
GPS trajectory agglomeration and refined road network extraction
WU Qunyong1,2,3, WU Zufei1,2,3, ZHANG Liangpan1,2,3     
1. Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou 350002, China;
2. National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350002, China;
3. Spatial information Research Center of Fujian Province, Fuzhou 350002, China
Abstract: Aiming at the shortcomings of low-accuracy in the use of GPS data to extract bidirection a roads and intersections, this paper proposes a trajectory agglomeration and refined roads extraction method that takes into account the position and travel direction to extracts refined road network. First, we remove the discrete and abnormal trajectory points from the original trajectory and insert the trajectory points into the trajectory segments by a certain step size, in order to improve the extraction accuracy of the intersection network.Second, we introduce the driving direction angle to express the driving direction of the vehicle at the track point, obtain its similar trajectory points set by considering the position and direction of the track point, calculate the offset distance of each track point in turn, and complete the track aggregation by iteratively offsetting the track points.Finally, we eliminate the track points that have not been successfully gathered, and use the Grid digitization method to extract the road network that can reflect the fine steering relationship of the roads from the trajectory data after gather. The trajectory agglomeration and road network extraction experiments were carried out with GPS data of Fuzhou taxis. The experimental results show that this method can effectively gather the GPS trajectories according to the direction of vehicle travel and the extracted road network is bidirectional roads, and can finely reflect the steering relationship of the roads at the intersections.
Key words: GPS trajectory    trajectory agglomeration    bidirectional roads    refined roads    roads extraction    

路网数据作为重要的基础地理信息数据源[1],在地图匹配[2-4]、交通拥堵治理[5]等领域具有重要的应用,如何快速获取现势性强、精细化程度高的路网信息成为当前交通地理信息领域的重要研究方向[6]。伴随移动端定位技术的成熟,携带定位装置的出租车在短时间内便能获取大量城市道路网数据,因此出租车GPS轨迹数据成为挖掘路网信息的重要数据源[7]

利用出租车GPS轨迹数据提取路网信息主要有如下几种方法:

(1) 基于轨迹聚类提取路网,通常利用轨迹点位置和方位角信息,运用聚类算法对轨迹进行聚类提取道路网[8-9]。文献[10]假设每条轨迹段附近存在势能场,通过对轨迹点的移动实现同一条道路上的轨迹汇集,然后运用轨迹增量方法遍历轨迹段提取路网,该方法难以将交叉路口处不同转向关系的轨迹完全分离,尤其在停车场附近的路网提取结果并不理想。文献[11]运用文献[10]提出的轨迹分离方法对轨迹进行预处理,然后通过轨迹点的方位角变化确定交叉路口位置,单独提取交叉路口内部的路网信息。文献[12]根据距离和方向对轨迹段进行聚类,对同一类簇的轨迹点运用B样条曲线进行拟合得到路网,该方法计算复杂,提取结果受路网区域特征影响明显。

(2) 轨迹增量法提取路网,这类方法以轨迹为研究单元,融合位置和形态相似的共同轨迹段,在路段交叉处分割轨迹从而实现路网提取[13-14]。文献[15]基于轨迹点的速度及方向变化特征提出了交叉路口的识别方法。文献[16]通过遍历轨迹段集合,基于轨迹的空间位置关系确定是否将轨迹段添加到待生成的路网集合当中,由于道路交叉处的确定受阈值影响明显,该方法提取得到的路网平滑度不够。

(3) 轨迹栅格化提取单线路网,该类方法将轨迹栅格化为二维的数字灰度图,通过骨架线提取方法从图像中识别道路网[17]。文献[18]基于二值化的轨迹数据分别使用Douglas-Pecuker算法和多元自回归适应样条算法获取道路中心线。文献[19]提出了一种改进的核密度方法,该方法能够基于灰度图生成路网骨架,然后采用地图匹配算法完善道路网络的拓扑结构和几何特征。文献[20]运用图像细化算法从栅格化后的轨迹数据提取路网。但大多基于栅格化方法提取的路网数据通常存在明显的锯齿,难以反映交叉路口的细部信息。

(4) 顾及车辆行驶特征的其他路网提取方法。文献[21]根据轨迹点的分布位置,通过计算轨迹点重复的数量来识别可能的路口交叉点,然后以一定的规则将交叉点进行连接得到路网;文献[22]运用轨迹增量的方法提取道路几何特征,结合地址标签信息提取道路属性信息;文献[23]对轨迹构建Delunay三角网得到道路轮廓,然后在道路轮廓基础上二次构建Delunay三角网,通过对不同类型三角形边的中点进行连接提取道路中心线。

上述绝大多数方法的路网提取结果为单线路网数据,更详细的道路网信息需要另做处理;部分算法的路网提取结果在道路中间部分为双线路网,但以节点的方式代表交叉路口,难以反映道路的真实转向关系,或者通过确定交叉路口的范围单独提取内部的路网信息,然而当交叉路口存在复杂转向关系时,交叉路口位置的确定精度受阈值影响明显[11]

本文在上述问题基础上,提出一种轨迹点集聚和路网提取方法。该方法假设道路两侧的轨迹点会受到来自道路中间区域轨迹点的吸引力,而中间区域的轨迹点受到来自道路两侧轨迹点相反方向的吸引力;然后根据轨迹点受到的吸引力大小对轨迹点进行偏移,进而实现同一条道路上相同行驶方向轨迹的集聚;最后剔除未成功集聚的轨迹点,将聚集后的轨迹按车辆ID和时间顺序连成轨迹线,对每条轨迹做缓冲区并融合为面要素,运用栅格数字化的方法提取道路网。本文方法的优势在于能很好地分离不同行驶方向的轨迹分别进行集聚,并完整的提取复杂交叉路口处道路的精细转向关系。

1 精细化路网提取策略

由于受到GPS设备定位误差、城市高层建筑及车辆运营的影响,出租车原始GPS轨迹数据存在以下特点:①包含众多离散轨迹点及远离城市主要道路的停留点;②道路上不同行驶方向的轨迹点交错混杂;③路口转弯处的车辆轨迹无法反映真实的道路几何特征。以上原因导致轨迹数据无法直接用于提取精细化的路网。因此首先对轨迹点进行预处理,剔除离散及异常轨迹点,并对转弯路口稀疏的轨迹点进行一定程度的加密;其次,分离道路上不同行驶方向的轨迹点;最后基于偏移之后的轨迹点提取道路网。

在对原始轨迹数据进行预处理时,引入了轨迹点集合、行驶方向角及相似轨迹点集合3个概念,其中相似轨迹点集合基于行驶方向角而定义。假定位于道路上的轨迹点周围通常也聚集了较多行驶方向角相似的轨迹点,因此对轨迹点集合进行遍历,当轨迹点周围没有行驶方向角相近的轨迹点时,则认为该轨迹点位于支路上或者不位于道路上,视为离散点进行剔除。

定义1:轨迹点集合traj,多个GPS轨迹点Pi组成的序列。其中轨迹点Pi包含移动对象的车辆ID、采样时间、墨卡托平面直角坐标、载客状态等信息。

定义2:行驶方向角θ,从轨迹点Pi-1的指北方向线起依顺时针方向至Pi-1Pi+1连线间的夹角视为轨迹点Pi的行驶方向角,本文定义射线Pi-1-Pi+1方向为车辆在轨迹点Pi处的行驶方向;轨迹的起点和终点的行驶方向角则由后序和前序轨迹点共同确定。如图 1所示,轨迹起点O1和终点O5的行驶方向角分别为θ1θ5。对应的行驶方向分别为射线O1-O2O4-O5方向。

图 1 轨迹点行驶方向角示意 Fig. 1 Schematic diagram of the direction of travel of the track point

定义3:相似轨迹点集Trajs,与轨迹点Pi空间位置邻近、行驶方向角相近的轨迹点集合。

经过预处理阶段后的轨迹点大多位于道路上,但不同行驶方向的轨迹点仍然难以区分,直接对轨迹点进行处理时无法有效地分离轨迹点的方向,再引入影响权重和轨迹点偏移距离两个概念,提出轨迹点偏移策略分离不同行驶方向的轨迹点,近似认为行驶在道路上的车辆随机分布于道路中心线的两侧,假设每个轨迹点都会受到周围与其具有相近行驶方向轨迹点的吸引力的作用,使其具有向相似轨迹点移动的趋势,综合轨迹点受到的所有吸引力作用,将受到的吸引力作用转化为移动的距离和方向。为了保证基于偏移后的轨迹点所提取的路网仍然与道路中心线吻合,对轨迹点偏移时,区分偏移的方向,使得道路两侧的轨迹点向道路中间移动,而位于道路中间区域的轨迹点同时受到两侧轨迹点的吸引力大致相等并不移动,以此实现不同行驶方向轨迹点的分离。

在经过轨迹集聚之后,轨迹点能够按照行驶方向和空间位置集聚到相应的道路中心线附近,路网的轮廓已经非常的清晰,最后采用栅格化的方法提取道路网。

定义4:影响权重ωs,为模拟相似轨迹点产生的引力作用,用来反映轨迹点Pi受到相似轨迹点集合Trajs中轨迹点Ps影响大小的因子。权重与距离呈负相关,距离越远,影响权重越小,具体计算公式如下

(1)

式中,ωs为相似轨迹点PsPi的影响权重;dsPiPs的欧氏距离;k为常数。

定义5,轨迹点偏移距离Δdi:轨迹点Pi在受到相似轨迹点集合吸引力作用下,垂直行驶方向移动的距离,如图 1所示。

2 轨迹集聚和道路网提取方法

出租车行驶过程中绝大部分轨迹点位于道路上,同一条道路上不同车辆的轨迹具有空间位置临近,行驶方向相近的特点。鉴于此,本文提出的轨迹集聚和精细化路网提取方法,主要分为轨迹预处理、轨迹集聚和路网提取3部分,如图 2所示。

图 2 轨迹集聚和道路网提取方法 Fig. 2 Trajectory agglomeration and road network extraction method

轨迹点预处理:通过判断轨迹点是否存在相似轨迹点集合的方法,识别载客轨迹数据中的异常和离散点;为提高交叉路口区域轨迹集聚的水平,在预处理时对轨迹段按固定步长进行加密处理。

轨迹集聚:首先计算所有轨迹点的行驶方向角,然后顾及位置和行驶方向获取相似轨迹点集合,计算每个相似轨迹点产生的偏移距离,并按偏移方向求和取平均得到待偏移轨迹点的偏移距离,当所有轨迹点的平均偏移距离大于阈值时,以偏移后的坐标重新计算轨迹点的行驶方向角,直至平均偏移距离小于阈值。

精细化路网提取:基于轨迹集聚的结果,剔除未集聚的轨迹点后得到能够反映道路结构的轨迹数据,然后运用栅格数字化的方法提取道路网。

2.1 轨迹数据预处理

(1) 筛选载客轨迹。在出租车实际运营过程中,载客状态下的出租车通常以接近交通流的速度在快速车道上行驶,其轨迹与真实路网重合度较高,而车辆空载时由于受到寻找客源或停车等因素的影响,车辆通常在慢车道以较为缓慢的速度行驶,存在因停车造成的局部区域轨迹点聚集明显和轨迹偏离路网等问题。为提高路网提取精度,本文根据出租车原始轨迹数据中的载客状态信息,筛选载客数据作为路网提取的数据源。

(2) 剔除离散轨迹点。对于周围没有相似轨迹点的离散点,在集聚过程中坐标并不会发生偏移,为提高轨迹点集聚的效率,在预处理阶段剔除离散轨迹点。离散轨迹点的识别通过判断轨迹点是否存在相似轨迹点集来实现,若无则视为离散点进行剔除,相似轨迹点集合的具体获取方法见2.2.1节。

(3) 加密轨迹点。由于出租轨迹的采样频率限制,将轨迹点连接得到的轨迹线与道路真实的几何形态通常存在较大差异,尤其在交叉路口和道路转向区域更为明显。为提高轨迹集聚水平,本文提出对轨迹段进行轨迹点加密处理。加密的具体方法为线性加密,轨迹点加密数量由相邻两轨迹点间的欧氏距离与加密步长确定,当相邻两轨迹点的距离小于加密步长,则加密点数量为零。

2.2 顾及位置和行驶方向的轨迹集聚

轨迹集聚的本质是通过轨迹点的迭代偏移使得同一条道路上相同行驶方向的轨迹汇集在一起。在对轨迹点进行偏移时,首先获取待偏移轨迹点的相似轨迹点集合,然后根据相似轨迹点的空间位置计算待偏移轨迹点的偏移距离,偏移过程中只分析待偏移轨迹点受到相似轨迹点的影响所产生的偏移距离,其余轨迹点的位置保持不变,直至轨迹点集合完成一次遍历;当所有轨迹点平均偏移距离低于设定的阈值时,则认为轨迹已经实现集聚,反之基于轨迹点偏移之后的坐标重新计算每个轨迹点的行驶方向角,重复以上步骤继续对轨迹点进行偏移,直至完成轨迹集聚。轨迹点偏移的具体步骤如下(图 3):

图 3 轨迹点偏移流程 Fig. 3 Track point offset flowchart

(1) 计算所有轨迹点的行驶方向角。

(2) 遍历轨迹点集合,获取待偏移轨迹点Pi的相似轨迹点集合。

(3) 遍历相似轨迹点集合中的所有轨迹点,计算待偏移轨迹点Pi的偏移距离Δdi和偏移后的坐标。

(4) 直至轨迹点集合完成遍历,更新偏移后的坐标为当前坐标,计算所有轨迹点的平均偏移距离Δd

(5) 若Δd大于设定的阈值,则重复步骤(1)-(4),反之完成轨迹点的集聚。

2.2.1 相似轨迹点集获取

本文顾及行驶方向角和空间位置获取相似轨迹点集,目的在于筛选出与待偏移轨迹点位于同一条道路上具有相同行驶方向的轨迹点,用于轨迹点偏移计算。获取相似轨迹点集合时,引入行驶方向角替代轨迹点方位角作为筛选条件,是由于基于行驶方向角筛选得到的相似轨迹点集合能更好地提高轨迹点集聚的精度。一方面降低轨迹点因定位不准导致该点方位角与实际方位角存在偏差所造成的误差;另一方面能提升不同道路车流并入时的轨迹集聚效果,如图 4所示,图 4(a)为采用轨迹点的方位角进行集聚的效果,在道路交汇处轨迹集聚效果差,图 4(b)为本文引入行驶方向角集聚的效果,能很好地将轨迹点按道路行驶方向分别进行集聚。

图 4 引入行驶方向角进行轨迹点偏移 Fig. 4 Introduce the direction of travel angle to offset the track point

为提高获取相似轨迹点集的效率,本文首先将研究区域划分为ρ×ρ m的网格单元,ρ为获取相似轨迹点时定义的距离阈值,根据网格的顶点坐标为网格进行唯一编号,将同一个网格内的轨迹点集中存储并与其所在网格的编号进行关联。遍历轨迹点集合中的轨迹点时,根据坐标确定待偏移轨迹点所在的网格编号,遍历以该网格为中心的九宫格所包含的所有轨迹点,依次计算与待偏移轨迹点行驶方向角差值和距离,筛选出符合限制条件的相似轨迹点集。若轨迹点所在网格位于研究区域最外层,则遍历研究区域内与该网格相邻网格内的轨迹点,其余步骤相同。

2.2.2 轨迹点偏移计算

由于同一条道路上的轨迹通常近乎平行分布,轨迹点偏移时限制轨迹点仅垂直行驶方向偏移能够缩短轨迹集聚的时间;同时轨迹点并非均匀分布,即使是同一条轨迹的前后相邻轨迹点,其相似轨迹点集合也可能存在很大差异,如果允许轨迹点沿着行驶方向偏移,可能改变相邻轨迹点在道路上的位置顺序,影响轨迹点集合下一次迭代偏移,反复迭代容易造成误差累积。因此在对轨迹点进行偏移计算时,本文提出轨迹点仅垂直车辆行驶方向偏移。

为便于分析待偏移轨迹点受到周围相似轨迹点的引力作用,每次都以待偏移轨迹点为原点建立平面直角坐标系,如图 5所示,以轨迹点O3为原点,平行于O3的行驶方向(射线O2O4方向)作为y轴的正方向,与行驶方向顺时针成90°的方向作为x轴正方向建立平面直角坐标系Oxy,轨迹起始点O1O5Oxy坐标系建立方式同理,以轨迹点为原点,行驶方向为y轴正方向,如图 5所示。基于以待偏移轨迹点为原点的Oxy坐标系,计算出相似轨迹点在Oxy坐标系下的xy轴坐标

(3)
图 5 轨迹点偏移计算 Fig. 5 Schematic diagram of track point offset calculation

式中,θx0y0为待偏移轨迹点O3的行驶方向角以及在投影坐标系下的坐标;xaya为相似轨迹点在投影坐标系下的坐标;xaya为相似轨迹点在Oxy直角坐标系下的坐标。

根据相似轨迹点与待偏移轨迹点的距离、影响权重以及在Oxy坐标系下的x轴坐标,求解待偏移轨迹点的偏移距离Δdi

(3)

式中,mωjdj为相似轨迹点集合中x轴坐标大于0的轨迹点数量、影响权重和x轴坐标值;nωkdk为相似轨迹点集合中x轴坐标小于0的轨迹点数量、影响权重和x轴坐标值。以待偏移轨迹点O3为例,R为相似轨迹点集合搜索半径,范围内与O3的行驶方向角差值的绝对值小于阈值的轨迹点为O3的相似轨迹点;根据轨迹点与O3的欧氏距离计算每个相似轨迹点的影响权重,距离越远影响越小;影响权重与对应的x轴坐标值乘积得到该相似轨迹点对O3所产生的偏移距离,然后分方向累加所有相似轨迹点对待偏移轨迹点在x轴正负方向上产生的偏移距离并取平均值,最后对两个方向的平均值求和得到待偏移轨迹点O3最终的偏移距离Δdi,若Δdi>0,则轨迹点O3沿着x轴正方向偏移,反之沿着x轴负方向偏移,若Δdi=0则不偏移。

基于轨迹点在Oxy坐标系下沿x轴的偏移距离Δdi,转换得到轨迹点偏移后在投影坐标系下的坐标,计算公式如下

(4)

式中,xOyO分别为轨迹点偏移后在投影坐标系下的坐标;θ为待偏移轨迹点的行驶方向角;Δdx、Δdy分别为待偏移轨迹点在Oxy直角坐标系下沿x/y坐标轴的偏移量,即Δdxdi,由于本文中轨迹点只沿x轴方向偏移,因此Δdy=0;xOyO为待偏移轨迹点在投影坐标系下的原始坐标。

当所有轨迹点完成一次偏移计算后,将偏移后的坐标更新为轨迹点当前坐标,并计算所有轨迹点偏移距离的平均值Δd。若Δd大于预先设定的阈值δ,则以偏移后的坐标重新计算轨迹点的行驶方向角θ,继续迭代偏移;反之认为轨迹点集聚完成,结束偏移。

2.3 精细化路网提取

(1) 剔除未集聚的轨迹点。经过轨迹点偏移后,绝大多数位于同一条道路上的轨迹能完成集聚,但部分轨迹点的相似轨迹点集合数量较少,使得反复迭代过程中轨迹点的偏移距离很小,导致部分轨迹点无法完全集聚。为提高交叉路口路网信息的提取精度,需要识别出未完全集聚的轨迹点并进行剔除。考虑到轨迹集聚之后位于同一条道路上的轨迹点间隔非常近,本文通过遍历轨迹点集合,判断轨迹点周围是否存在相似轨迹点来识别未集聚的轨迹点,将识别出的未集聚轨迹点进行剔除。判断是否存在相似轨迹点集的方法见2.2.1节,与预处理阶段的区别在于距离和角度阈值的不同。

(2) 栅格化提取道路网。将剔除未集聚轨迹点之后的轨迹点集合按车辆ID和采样的时间顺序连成轨迹线,接着对每条轨迹线作距离为γ的缓冲区,并融合为单部件的面要素。由于局部道路轨迹稀疏,当轨迹间的最大距离超过缓冲区半径γ的2倍时,道路缓冲区融合后的面要素容易在道路内部形成孔洞,进行二值化之前需要根据孔洞的面积设定阈值填充孔洞。最后利用ArcScan工具提取道路中心线,剔除距离过短的线段和悬挂线,提取得到精细化的双线路网信息。

3 试验与分析 3.1 数据与试验环境

本文以福州市鼓山高架桥附近的道路作为试验路段(图 6),该区域道路网交错,包含较多的转弯路口,能很好地验证方法的有效性。试验数据选用福州市2015年5月22日至5月30日的出租车轨迹数据,采样频率在10~30 s之间,轨迹数据包括车辆ID、采样时间、投影坐标系下的XY坐标及载客状态信息,共计39 087个轨迹点,1959条轨迹。本试验在普通PC(Intel Core i5/CPU 3.20 GHz/8 G/Win10)环境下,基于ArcGIS 10.3平台、JAVA编程语言进行轨迹集聚和路网提取试验。

图 6 轨迹点预处理、轨迹集聚和路网提取结果 Fig. 6 Trajectory point preprocessing, trajectory agglomeration and network extraction results

3.2 试验参数选取

3.2.1 数据预处理参数的确定

预处理阶段,需要确定获取相似轨迹点的距离、行驶方向角阈值及加密步长。具体思路是首先分析轨迹数据,结合试验区域内的道路几何特征确定阈值范围,而后选取不同参数进行试验,综合路网提取效果和算法运行效率确定具体的阈值。

考虑到选取的试验区域存在快速路和高架桥道路重叠,道路宽度从4~20 m不等,本文分别选取5 m、10 m、15 m、20 m作为相似轨迹点筛选的距离阈值进行轨迹集聚试验,结果表明过小的距离阈值容易剔除道路边缘的轨迹点,距离阈值过大则无法有效剔除离散点,当距离阈值为15 m时,能很好地分离不同道路上的轨迹;轨迹集聚后道路交汇处的位置精度则与行驶方向角阈值的选取密切相关,行驶方向角阈值过小造成道路交汇的位置提前,过大导致道路交汇的位置延后。由于试验区域涉及不同类型、不同级别的道路交汇,本文分别以2.5°、5°、7.5°、10°作为行驶方向角阈值进行轨迹集聚试验,结果表明,行驶方向角阈值设置为5°时,轨迹集聚得到的道路交叉口与真实位置较为接近。因此预处理时获取相似轨迹点集合的距离阈值设为15 m,行驶方向角阈值设为5°。

试验数据的轨迹段间隔通常在80~120 m之间,为使得轨迹集聚后道路转弯处尽可能的平滑,本文分选取5 m、10 m、15 m、20 m作为加密步长进行试验,其中步长为5 m和10 m时,交叉路口处的轨迹集聚效果良好,但步长为5 m时,加密后的轨迹点数量过大导致轨迹集聚时间延长,步长大于15 m时在局部转弯角度较小区域轨迹集聚并不理想。因此本文选取10 m作为步长对轨迹段进行加密。

3.2.2 轨迹集聚参数的选取

轨迹集聚过程中相似轨迹点获取参数同预处理时剔除离散轨迹点的参数,以下分别讨论影响权重常数k和偏移距离阈值的选取。

最佳的影响权重常数k应当使轨迹点的偏移符合由外向内逐渐集聚的趋势。本文分别对影响权重常数0.25、0.5、0.75进行了轨迹集聚试验,限定迭代次数为100次,结果显示影响权重常数过大将导致轨迹点偏移过远,无法完成轨迹集聚;过小使得轨迹点每次偏移距离过小,迭代终止时尚未完成轨迹集聚;k为0.5时,轨迹集聚效果良好,因此本文选取影响权重常数为0.5。

在轨迹点的迭代偏移过程中,随着轨迹集聚水平的提高,轨迹点的平均偏移距离将越来越小。若设置的偏移距离阈值过低会导致偏移的迭代时间过长,但集聚水平无明显提升;过高容易造成迭代循环过早结束,影响轨迹集聚效果。经试验,偏移距离阈值小于0.005 m时,轨迹集聚速度下降,效果无明显提升,因此设定偏移距离阈值为0.005 m时,在迭代时间与集聚效果之间能取得较好的平衡。

3.2.3 路网提取参数的确定

路网提取过程中,需要确定获取相似轨迹点的阈值参数以及缓冲区半径:

(1) 剔除未集聚的轨迹点时,道路上相同行驶方向的轨迹线在集聚后宽度通常在10 cm以内,因此本文选取筛选相似轨迹点集合的距离阈值为1 m,行驶方向角度阈值为5°,确保轨迹稀疏路段上的轨迹点不被视为未完成集聚的轨迹点。

(2) 在运用栅格化方法提取路网时,为保证道路交叉路口的路网提取质量,要求缓冲区半径尽量的小,使得交叉路口的缓冲区面积不会过大。

经试验,半径选取为0.1 m时,能很好地减少同一条道路上轨迹间因轨迹线稀疏融合缓冲区时形成的孔洞。

3.3 结果分析

采用上述选取的参数,利用福州市轨迹数据进行轨迹集聚和道路网提取试验。试验结果如图 6所示。

经轨迹集聚后,将轨迹点按车辆ID和时间连成轨迹线,得到的轨迹线已基本能够反映道路网结构,但仍存在部分轨迹点未完全集聚,在剔除这部分轨迹点之后,结果如图 7所示,图 7(b)(c)中不同类型道路交叉口的转向关系完成提取,能清晰反映道路间的连通情况;图 7(d)(e)中局部区域的轨迹未完全集聚到一起,这是轨迹采样频率不高,车辆在转向时轨迹点过少所导致的。

图 7 轨迹集聚后部分交叉路口细节 Fig. 7 After trajectory agglomeration partial intersection details

为定性评价本文方法提取的路网,首先与试验区域的谷歌卫星影像叠加对比,如图 8所示,道路上相同行驶方向的轨迹已完成集聚,与谷歌卫星影像上的道路重合良好,基本完全落在卫星影像的道路范围内,交叉路口区域轨迹集聚后能够反映真实的车辆行驶路径。

图 8 集聚后的轨迹与Google卫星影像叠加结果(红色实线为本文提取路网) Fig. 8 Accumulated trails and Google satellite image overlay results(red solid line extracts for this article)

本文提取的路网结果与OSM路网叠加如图 9所示,红色实线为本文方法提取的路网,黑色为OSM矢量路网,两者整体上基本重合。OSM路网在交叉路口通过人为干预处理,以道路相交代表复杂的转向,难以反映道路间的真实连接关系。与OSM路网相比,本文提取的路网在交叉路口信息更为精细,能反映道路的具体转向关系,如图 9(b)-(c)所示。同时本文提取得到的路网数据要比OSM路网数据更详细,由于OSM路网未及时更新路网变化信息,在局部区域缺少新增道路以及部分无效路段未及时删除,而本文提取的路网具有更为合理的路段连通关系,不存在孤立的路段以及较少的悬挂线,如图 9(d)-(e)所示。

图 9 本文提取的路网与OSM路网叠加结果(红色实线为本文提取路网,黑色为OSM矢量路网) Fig. 9 Road network extraction results and OSM road network overlay results(red solid line extracts for this article, black means OSM vector road network)

3.4 精度评价

为定量评价本文方法、文献[14]及文献[24]3种提取路网方法的精度,本文采取文献[25]提出的基于线要素缓冲区的相似度计算方法进行评价。该方法以标准矢量数据为基准作不同距离的缓冲区,通过计算待评价线要素与缓冲区相交的长度占总长度的百分比来评价不同缓冲区半径下的精度。本文以试验区域内的OSM矢量路网为标准数据,分别做2 m、5 m、7 m的缓冲区,比较3种方法提取得到路网的精度,评价结果如图 10所示。文献[14]通过构建轨迹点Delunay三角网提取得到的路网为单线形式,本文方法提取结果为双线路网,交叉路口信息完整,能够更加真实地反映道路转向关系;随着缓冲区半径的增大,本文方法所提路网的精度有明显提高,缓冲区距离为7 m时本文方法优于文献[14]结果,在不同缓冲区半径下,本文提取的路网精度与文献[24]结果相比都有明显的提高;试验区域内OSM矢量路网总长度为33 666.2 m,本文方法提取得到的路网总长度为33 727.5 m,整体上与OSM路网几乎完全重叠。OSM矢量路网在复杂交叉路口进行了概要处理,而本文提取的交叉路口转向关系基于车辆行驶轨迹,反映的是车辆转向时的真实行驶路径。

图 10 精度评价 Fig. 10 Accuracy evaluation

4 结论

本文提出一种通过偏移轨迹点实现轨迹集聚和路网提取方法,以福州市出租车轨迹数据进行了轨迹集聚和路网提取试验,结果表明该方法能对道路网及交叉路口转向信息实现精细化的提取,为精细化路网信息提取提供了新的方法。本文方法与已有的路网提取算法相比,具有以下3个特点:

(1) 本文方法受研究区域内路网几何特征形态影响小,能够完成路网精细几何特征和道路中心线级别交叉口结构的同时提取;

(2) 方法同时顾及轨迹点的空间位置和行驶方向,能够实现复杂立交区域的道路提取,严格区分空间位置临近但行驶方向存在差异的路段;

(3) 基于轨迹集聚后的结果,运用栅格化方法提取得到的道路网能够反映复杂交叉路口区域道路的精细转向关系,可及时发现道路变化情况,为路网信息更新提供帮助。

由于原始轨迹中缺乏高程数据,笔者并没有精细化识别上下层道路重叠的路段,后续将继续完善精细化路网提取方法,尝试利用出租车GPS数据识别道路网中的上下层路段,进一步提高精细化路网提取的精度。


参考文献
[1] WANG Yin, LIU Xuemei, WEI Hong, et al. Crowdatlas: self-updating maps for cloud and personal use[C]//Proceedings of the 11th Annual International Conference on Mobile Systems, Applications, and Services. New York, NY: ACM, 2013: 27-40.
[2] 吴涛, 向隆刚, 龚健雅. 路网更新的轨迹-地图匹配方法[J]. 测绘学报, 2017, 46(4): 507–515.
WU Tao, XIANG Longgang, GONG Jianya. Renewal of road networks using map-matching technique of trajectories[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4): 507–515. DOI:10.11947/j.AGCS.2017.20150479
[3] 曾喆, 李清泉, 邹海翔, 等. 曲率积分约束的GPS浮动车地图匹配方法[J]. 测绘学报, 2015, 44(10): 1167–1176.
ZENG Zhe, LI Qingquan, ZOU Haixiang, et al. Curvature integration constrained map matching method for GPS floating car data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1167–1176. DOI:10.11947/j.AGCS.2015.20140352
[4] 高悦尔, 陈舒婷, 郑承于, 等. 基于浮动车数据的旅游景点周边路网容量研究--以厦门岛为例[J]. 地理科学进展, 2016, 35(12): 1529–1537.
GAO Yueer, CHEN Shuting, ZHENG Chengyu, et al. Road network capacity of tourist site's periphery based on FCD:taking Xiamen island as an example[J]. Progress in Geography, 2016, 35(12): 1529–1537.
[5] 李清泉, 李秋萍, 方志祥. 一种基于时空拥挤度的应急疏散路径优化方法[J]. 测绘学报, 2011, 40(4): 517–523.
LI Qingquan, LI Qiuping, FANG Zhixiang. An emergency evacuation routing optimization method based on space-time congestion concept[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 517–523.
[6] 杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2): 237–245.
YANG Wei, AI Tinghua. The extraction of road boundary from crowdsourcing trajectory using constrained delaunay triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 237–245. DOI:10.11947/j.AGCS.2017.20160233
[7] 刘经南, 高柯夫. 智能时代测绘与位置服务领域的挑战与机遇[J]. 武汉大学学报(信息科学版), 2017, 42(11): 1506–1517.
LIU Jingnan, GAO Kefu. Challenges and opportunities for mapping and surveying and location based service in the age of intelligence[J]. Geomatics and Information Science of Wuhan University, 2017, 42(11): 1506–1517.
[8] AHMED M, KARAGIORGOU S, PFOSER D, et al. A comparison and evaluation of map construction algorithms using vehicle tracking data[J]. GeoInformatica, 2015, 19(3): 601–632. DOI:10.1007/s10707-014-0222-6
[9] QIU Jia, WANG Ruisheng. Road map inference:a segmentation and grouping framework[J]. ISPRS International Journal of Geo-Information, 2016, 5(8): 130. DOI:10.3390/ijgi5080130
[10] CAO Lili, KRUMM J. From GPS traces to a routable road map[C]//Proceedings of the 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems. Washington D C: ACM, 2009: 3-12.
[11] WANG Jing, RUI Xiaoping, SONG Xianfeng, et al. A novel approach for generating routable road maps from vehicle GPS traces[J]. International Journal of Geographical Information Science, 2015, 29(1): 69–91.
[12] LIU Xuemei, ZHU Yanmi, WANG Yin, et al. Road recognition using coarse-grained vehicular traces[R]. Tech. rep. HPL-2012-26.[S.l.]: HP Laboratories, 2012.
[13] AHMED M, WENK C. Constructing street networks from GPS trajectories[C]//European Symposium on Algorithms. Berlin: Springer, 2012: 60-71.
[14] 唐炉亮, 刘章, 杨雪, 等. 符合认知规律的时空轨迹融合与路网生成方法[J]. 测绘学报, 2015, 44(11): 1271–1276.
TANG Luliang, LIU Zhang, YANG Xue, et al. A method of spatio-temporal trajectory fusion and road network generation based on cognitive law[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11): 1271–1276. DOI:10.11947/j.AGCS.2015.20140591
[15] KARAGIORGOU S, PFOSER D. On vehicle tracking data-based road network generation[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York, NY: ACM, 2012: 89-98.
[16] ZHANG Yongchuan, LIU Jiping, QIAN Xinlin, et al. An automatic road network construction method using massive GPS trajectory data[J]. ISPRS International Journal of Geo-Information, 2017, 6(12): 400. DOI:10.3390/ijgi6120400
[17] SHI Wenhuan, SHEN Shuhan, LIU Yuncai. Automatic generation of road network map from massive GPS, vehicle trajectories[C]//Proceedings of 12th International IEEE Conference on Intelligent Transportation Systems. St. Louis, MO: IEEE, 2009: 1-6.
[18] 王德浩.基于低频出租车GPS轨迹数据的路网信息提取[D].武汉: 武汉大学, 2017.
WANG Dehao. Generation of road network information from massive less frequent GPS vehicle trajectories[D]. Wuhan: Wuhan University, 2017.
[19] BIAGIONI J, ERIKSSON J. Map inference in the face of noise and disparity[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York, NY: ACM, 2012: 79-88.
[20] 蒋益娟, 李响, 李小杰, 等. 利用车辆轨迹数据提取道路网络的几何特征与精度分析[J]. 地球信息科学学报, 2012, 14(2): 165–170.
JIANG Yijuan, LI Xiang, LI Xiaojie, et al. Geometrical characteristics extraction and accuracy analysis of road network based on vehicle trajectory data[J]. Journal of Geo-Information Science, 2012, 14(2): 165–170.
[21] ZHANG Jindong, MENG Weibin, LIU Qiangqiang, et al. Efficient vehicles path planning algorithm based on taxi GPS big data[J]. Optik, 2016, 127(5): 2579–2585. DOI:10.1016/j.ijleo.2015.12.006
[22] LI Jun, QIN Qiming, HAN Jiawei, et al. Mining trajectory data and geotagged data in social media for road map inference[J]. Transactions in GIS, 2015, 19(1): 1–18.
[23] 杨伟, 艾廷华. 基于众源轨迹数据的道路中心线提取[J]. 地理与地理信息科学, 2016, 32(3): 1–7.
YANG Wei, AI Tinghua. Road centerline extraction from crowdsourcing trajectory data[J]. Geography and Geo-Information Science, 2016, 32(3): 1–7. DOI:10.3969/j.issn.1672-0504.2016.03.001
[24] ZHANG Lijuan, THIEMANN F, SESTER M. Integration of GPS traces with road map[C]//Proceedings of the 3th International Workshop on Computational Transportation Science. New York, NY: ACM, 2010: 17-22.
[25] GOODCHILD M F, HUNTER G J. A simple positional accuracy measure for linear features[J]. International Journal of Geographical Information Science, 1997, 11(3): 299–306.
http://dx.doi.org/10.11947/j.AGCS.2019.20180256
中国科学技术协会主管、中国测绘地理信息学会主办。
0

文章信息

邬群勇,吴祖飞,张良盼
WU Qunyong, WU Zufei, ZHANG Liangpan
出租车GPS轨迹集聚和精细化路网提取
GPS trajectory agglomeration and refined road network extraction
测绘学报,2019,48(4):502-511
Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 502-511
http://dx.doi.org/10.11947/j.AGCS.2019.20180256

文章历史

收稿日期:2018-06-07
修回日期:2018-11-21

相关文章

工作空间