-
道路网络信息是位置服务(LBS)及智能交通系统的关键，然而随着经济的不断发展，城市路网每天都在变化，因此如何实现路网快速更新成为目前的研究热点[1-2]。本文按照道路变化检测的数据源不同，将当前道路网络更新方法分为影像与影像比较的变化检测、影像与矢量比较的变化检测、矢量与矢量比较的变化检测[3]。影像与影像比较的变化检测是通过比较变化前后道路遥感影像实现变化检测；影像与矢量比较的变化检测是将旧道路矢量与新遥感影像直接比较，或从遥感影像中提取矢量后与旧道路矢量进行比较；矢量与矢量比较的变化检测是通过对新旧矢量数据进行比较提取出变化量。这些通过比较变化前后两份道路数据的路网更新方法，往往具有数据获取周期长、成本高，检测算法复杂、计算难度大等缺点。
安装GPS的出租车每天24 h行驶在城市大街小巷，GPS时空轨迹遍布城市任何道路和路段，是一种采集成本低、时效性强且蕴含丰富道路信息的数据源。国内外学者已经提出从GPS轨迹中获取道路级别与车道级别的路网图形线、路网交叉点位置、交通灯与停车标识牌位置等路网信息的方法[4-8]；张淑玲等通过GPS轨迹数据与空间网格结合的方法实现新增道路检测[9]，但无法对道路改建与废弃检测；Tang[10]等提出将出租车GPS轨迹数据与路网匹配方法实现道路变化检测，但没有考虑路网拓扑关系，只实现于道路图形的变化检测；Boucher[11]等基于概率地图匹配方法检测路网中的拓扑变化，但计算过程复杂，变化检测效率低。此外还有学者通过GPS轨迹点密度计算[12]、神经网络聚类[13]等方法提高轨迹点与道路拓扑匹配精度，从而实现路网变化检测。
本文充分利用出租车GPS每天24 h的时空轨迹采集成本低、时效性强等优势，从道路拓扑变化检测出发，通过度量出租车GPS运动轨迹向量与路网局部拓扑向量之间的相似性，检测道路拓扑的变化，构建一定范围内新的道路拓扑关系，形成一种路网数据采集快、成本低、检测算法计算量小的实时路网数据获取与变化检测新方法。
-
基于出租车GPS时空轨迹的路网拓扑变化检测方法分为两步：
1) 从当前轨迹点分布出发，构建GPS时空轨迹向量和出租车当前所在位置的局部道路拓扑向量，时空轨迹向量体现一段时间内车辆通行趋势，局部道路拓扑向量体现道路通行方向，计算两向量间的相似性，根据设定的相似性阈值得到疑似拓扑变化轨迹点数据；
2) 从时空轨迹所体现出的车辆运动趋势出发，通过轨迹拓扑边界点提取及拓扑连通性分析，去除所检测出的错误变化轨迹点，构建路段交叉处新的路网拓扑关系，实现路网拓扑的自动变化检测，基于GPS时空轨迹的路网拓扑变化检测方法流程图如图 1所示。
图 1 路网变化检测方法流程图
Figure 1. Process of Road Network Change Detection
-
疑似轨迹变化点是指与旧有路网局部拓扑无法匹配的轨迹点，为了检测这些疑似轨迹点，本文提出采用向量相似性度量算法实现疑似轨迹变化点的检测，轨迹向量与路网局部拓扑向量之间存在的空间关系主要分为距离关系和角度关系。本文提出以角度和距离为差异因子的向量相似性度量算法，实现GPS轨迹向量与局部道路拓扑向量相似性度量。
1) GPS轨迹向量构建
建立GPS时空轨迹向量时，以GPS轨迹点作为向量起点，方向取当前点所记录的车辆运行方向。这种方法构建的轨迹向量在保证较高计算效率的同时，构建的轨迹向量方向更符合实际的车辆运行方向。
2) 局部道路拓扑向量构建
构建局部道路拓扑向量时，先构建当前轨迹点与前后轨迹点三点最小包围矩形的面状缓冲区，再根据落入缓冲区内的道路动态构建局部道路拓扑向量。构建过程如图 2所示，图中的向量即为构建的局部道路拓扑向量。当缓冲区内有多条拓扑路段时，则需要构建多条局部道路拓扑向量作为候选向量。本文为保证构建的矩形缓冲区内有图形路段落入，将城市内一个街区的宽度作为矩形缓冲区的大小。
图 2 局部道路拓扑向量的构建
Figure 2. Partial Topological Road Vector Creating
3) 向量相似性度量
借鉴浮动车地图匹配中基于权重定位点匹配算法[14]与基于拓扑的全局地图匹配[15]思想，本文度量GPS轨迹与道路之间的相似性，实质为度量GPS轨迹向量与道路局部拓扑向量之间的相似性。度量向量相似性过程中分别计算轨迹向量与局部道路拓扑向量之间的距离相似性SDis、方向相似性SAng，并将两相似性赋权相加得到空间位置和运动方向双重约束下的向量相似性，综合相似度表示为：
$$S = \lambda \cdot{S_{{\rm{Dis}}}} + \left( {1 - \lambda } \right)\cdot{S_{{\rm{Ang}}}}$$ (1) 式中，S为双重约束下的综合相似度；SDis和SAng分别为距离相似度和运动方向相似度; λ和(1-λ)分别为距离相似度与方向相似度在计算中所占的权值。
其中距离相似度表示为：
$${S_{{\rm{Dis}}}} = \frac{{{D_{{\rm{TH}}}} - {D_i}}}{{{D_{{\rm{TH}}}}}}$$ (2) 距离相似度SDis用来描述轨迹向量与局部道路拓扑向量距离的接近程度，式(2) 中Di表示轨迹向量的起点到图形路段的距离，DTH为距离阈值。本文阈值大小为轨迹点到矩形缓冲区的边界位置的最远距离，当轨迹向量起点到候选图形路段的垂足不在候选路段上时，分别计算轨迹向量起点到图形路段起始点和终点的距离，并选择较小值。距离相似度SDis的取值范围为[0, 1]，且当轨迹点到图形路段的距离为0时，SDis取值为1；当轨迹点到图形路段的距离为阈值DTH时，SDis取值为0；随着轨迹点到路段的距离不断增大，相似度SDis逐渐变小。
方向相似度表示为：
$${S_{{\rm{Ang}}}} = {\rm{cos}}({\theta _{i,{\rm{ }}j}})$$ (3) 方向相似度SAng用来描述轨迹向量与局部道路拓扑向量方向相似程度，式(3) 中θi, j为轨迹向量与局部道路拓扑向量之间的夹角，当θi, j大于π时取θi, j的补角。
-
轨迹向量与局部道路拓扑向量的相似度S值越大，说明轨迹向量与道路拓扑向量越相似，路网变化的可能性越小；向量相似度S值越小，说明轨迹向量与道路拓扑向量越不相似，路网变化的可能性越大。因此，小于相似性阈值T的轨迹点即可能为路网变化点，称作疑似变化轨迹点，通过对疑似变化轨迹点进一步跟踪，在道路交叉口处对道路拓扑边界点进行提取，进行拓扑连通性分析，基于变化轨迹点构建一定范围内新的路网拓扑关系，比较新旧路网拓扑确定道路变化类型。
-
疑似变化轨迹点的提取结果依赖于距离相似性权值λ和相似性阈值T两个参数。为得到最佳权值与阈值，本文通过调整不同权值和阈值，对其相应的变化轨迹点提取结果正确率进行分析，其中变化轨迹点提取结果正确率的计算方法为：
$${P_i} = \frac{{\{ {A_n}\} n\{ {R_n}\} }}{{\{ {A_n}\} }}$$ (4) 式中，{An}为实验区内提取的变化轨迹点集合；{Rn}为{An}中实际从路网中获取的变化轨迹点的集合。
-
轨迹变化点所具有的拓扑变化性主要体现在以下几个方面：(1) 相邻的两个轨迹点匹配到不同路段，并且两路段直接连通，如图 3(a)所示；(2) 相邻两个轨迹点分别匹配到不同拓扑路段，但两路段不直接连通，如图 3(b)所示；(3) 相邻两个轨迹点一个匹配到拓扑路段，而另一个不能成功匹配，如图 3(c)所示。
图 3 轨迹拓扑点的存在情况
Figure 3. Certain Circumstances of the Topological Points
一般情况下，轨迹在经过路口时如果提取出变化轨迹点，则该轨迹在交叉路口附近一定范围内有且仅有一对拓扑点。
当在交叉路口一定范围内，同一条轨迹上出现一对以上的拓扑点时，表明车辆转向一条道路短暂行驶后又迅速撤回，是一种非常态行为。因此，本文将交叉路口一定范围内同一条轨迹上出现一对以上拓扑点的情况认定为变化轨迹点的提取错误。
综上所述，本文以获取的变化轨迹拓扑点为中心，相邻拓扑路段的平均长度为线缓冲区半径，沿着轨迹线在缓冲区内搜索。如果找到一对及以上的轨迹拓扑点，则说明缓冲区范围内的变化轨迹点提取结果存在错误，然后对缓冲区内所有提取出的变化点进行修正。具体修正方法为：统计缓冲区内的变化轨迹点与非变化轨迹点数量，若两类轨迹点数量相差较大，则将数目较少类别的轨迹点修正为另一类别；若出现两类轨迹点数量相当，缓冲区范围内的变化轨迹点无法修正，需要借助在相同缓冲区内搜索同一时间段内的其他车辆轨迹来判断所提取变化轨迹是否正确。
-
路网拓扑关系变化类型有拓扑的增加、删除、修改，与其相对应的道路变化类型是道路新增、道路废弃、道路交通管控3种。拓扑检测结果与道路变化类型的对应关系如下。
1) 道路新增：主要表现为拓扑点增加与拓扑路段新增，在此情形下，通过变化轨迹点中的非变化轨迹边界点分布寻找新增的路网拓扑点，根据轨迹点分布拟合新增路段图形，并在路网拓扑表中新增拓扑路段记录；
2) 道路废弃：道路属性中设置一个“Tag”字段，每当有轨迹点经过时给该字段+1，当一周后“Tag”字段仍未0，认为在一周内没有车辆经过该路段，则该路段为道路删除；
3) 道路交通管控：包括路段单双通行变化和转向连通性变化两种，此情形下道路图形没有变化，只有道路拓扑连通关系的增加和删除，在此情形下，通过变化轨迹点非变化轨迹边界点分布寻找变化的路网拓扑点，在路网拓扑表中增加删除相对应的拓扑路段记录。
变化轨迹点可以体现出路网拓扑的新增。路网拓扑的新增包括道路新增引起的拓扑新增和道路通行性改变引起的拓扑新增。
-
本文采用2015年武汉市GPS轨迹数据，以及2013年的武汉市路网数据。图 4为实验中所使用的路网数据和原始轨迹数据，总共使用2015年7月某一周内武汉市内200辆出租车轨迹数据进行实验，总共有20万个GPS轨迹点，轨迹点的采样间隔在5~40 s或几分钟不等，为了提高运算效率，本文通过建立路网数据网格索引进行变化检测。
图 4 原始GPS轨迹与路网数据图
Figure 4. Original GPS Trajectories and Road Network Map
在实验过程中，为得到最佳权值与阈值，本文采用实验片区抽样的方法，针对不同阈值下疑似变化轨迹点的提取正确率进行统计，实验表明，当距离相似性权值λ为0.87，最佳相似性阈值T为0.85时可以得到最佳的变化检测结果，因此后续实验中均将距离相似性权值λ设为0.87，将相似性阈值T设为0.85。
-
图 5为使用本文提出的基于拓扑检测的路网变化检测方法所得到的局部范围内道路新增结果。通过Google Earth影像图验证实验结果的正确性。
图 5 基于路网拓扑的路网变化检测新增道路结果
Figure 5. Road Addition Detection Results Based on Road Topology Change Detection
最终得出，本文方法检测出新增路段20条，废弃路段3条，修改路段2条。经过影像比较与实地考察对比，新增路段中存在一些新增路段的检测错误，如图 5(a)中的R5，由于本文实验过程中采用出租车GPS轨迹，所以出租车可能驶入小区内或者广场等开放空间区域进行载客，在这种情形下不可避免会存在新增道路的检测错误。同样的数据，采用基于地图匹配的变化检测和与网格结合的道路自动检测方法进行实验，实验的检测结果与本文方法检测结果对比如表 1所示。
表 1 不同路网变化检测方法对比表
Table 1. Comparison of Different Change Detection Methods
方法 检测新增路段/条 检测错误的道路/条 检测废弃路段/条 检测修改路段/条 是否能检测道路的拓扑变化 每点算法处理时间/ms 基于道路拓扑变化检测(本文) 20 3 3 2 是 20 基于地图匹配的变化检测 15 2 3 未检测 否 30 浮动车与空间网格结合的新增道路自动检测 20 3 未能检测 未检测 否 70 表 1表明，基于地图匹配的变化检测的方法虽然能检测出新增与废弃路段，但该方法在变化检测时检测结果受缓冲区大小的影响较大，当缓冲区较大时，几乎没有变化轨迹点，当缓冲区较小时，会检测出大量错误的变化轨迹点。经过反复实验选取最佳的缓冲区大小进行实验，在路网环境较为复杂的区域内，由于GPS轨迹点无法正确匹配影像变化检测结果，最终只能检测出新增路段15条。结合空间网格的新增道路自动检测只能检测出道路的新增，而无法检测出道路废弃与道路修改等情形。同时，这两种方法都只是路网的图形检测，本文方法可以检测出路网的拓扑的变化。在算法效率方面，本文方法达到每点20 ms，可以满足实时检测的条件。相对于基于地图匹配方法的30 ms/点、网格结合的路网新增方法的70 ms/点，本文方法在时间效率上具有一定的优势。因此，本文提出的基于GPS轨迹拓扑的路网变化检测方法优于现有基于浮动车数据路网变化检测方法。
-
本文在现有变化检测研究的基础上，提出了一种基于道路拓扑变化检测的路网更新方法。该方法从道路拓扑变化检测出发，通过度量车辆运动轨迹向量与路网局部拓扑向量之间的相似性，构建一定范围内新的道路拓扑关系，实现了道路的自动更新。实验结果表明，在路网变化检测的计算效率和检测结果方面，该方法可以有效的检测道路新增及道路废弃，并实现了路网的拓扑信息更新。同时，通过对比现有路网检测方法，本文方法在路网变化检测的计算效率较高，检测结果正确率较好。下一步将深入研究众包模式下城市道路网络精细信息的自动变化检测，包括人行道路网变化检测及车道级路网变化检测等。
Road Network Topology Automatic Change Detection Based on GPS Spatio-Temporal Trajectories
-
摘要: 充分利用出租车GPS时空轨迹数据分布广和时效性强的特点，提出一种基于车载GPS轨迹数据的路网拓扑自动变化检测新方法。该方法首先利用向量相似性度量模型，度量GPS轨迹向量与路网局部拓扑向量之间的相似性，检测疑似道路拓扑变化点，然后通过比较疑似道路拓扑变化点与路网拓扑关系，完成新增、废弃、改建等道路变化，实现基于车载GPS轨迹的路网拓扑自动变化检测。实验结果表明，该方法不仅有效地检测出道路新增、道路废弃与道路改扩建等变化，而且能利用出租车实时和大范围分布特点来实现城市路网大范围实时变化检测。Abstract: The conventional methods of road change detection have disadvantages in terms of the data acquisition period, data cost, algorithmic complexity, calculation difficulty, and periodic updating. In this paper, by making full use of taxi GPS trajectory data distribution and timeliness, a new road network topology change detection method based on vehicle GPS spatio-temporal trajectories is proposed. In this method, the similarity between the GPS trajectory vector and the partial topological vector is measured using the vector similarity measure model, and the topological change of the road network is detected by comparing the path changes of the new, the waste and the reconstruction. Experimental results show that this method can not only detect the changes of new, wasted, and reconstructed parts of road network, but also can realize real-time change detection in urban road networks.
-
图 5 基于路网拓扑的路网变化检测新增道路结果
Figure 5. Road Addition Detection Results Based on Road Topology Change Detection
表 1 不同路网变化检测方法对比表
Table 1. Comparison of Different Change Detection Methods
方法 检测新增路段/条 检测错误的道路/条 检测废弃路段/条 检测修改路段/条 是否能检测道路的拓扑变化 每点算法处理时间/ms 基于道路拓扑变化检测(本文) 20 3 3 2 是 20 基于地图匹配的变化检测 15 2 3 未检测 否 30 浮动车与空间网格结合的新增道路自动检测 20 3 未能检测 未检测 否 70 
下载: 导出CSV
-
[1] 李德仁, 李清泉, 杨必胜, 余建伟. 3S技术与智能交通[J]. 武汉大学学报·信息科学版, 2008, 33(4): 331-336 http://ch.whu.edu.cn/CN/abstract/abstract1500.shtml Li Deren, Li Qingquan, Yang Bisheng, et al. Techniques of GIS, GPS and RS for the Development of Intelligent Transportation [J]. Geomatics and Information Science of Wuhan University, 2008, 33(4):331-336 http://ch.whu.edu.cn/CN/abstract/abstract1500.shtml [2] 陆峰, 张恒才.大数据与广义GIS [J].武汉大学学报·信息科学版, 2014, 39(6):645-654 http://ch.whu.edu.cn/CN/abstract/abstract3009.shtml Lu Feng, Zhang Hengcai. Big Data and Generalized GIS [J]. Geomatics and Information Science of Wuhan University, 2014, 39(6):645-654 http://ch.whu.edu.cn/CN/abstract/abstract3009.shtml [3] 刘虎林, 闫浩文, 刘涛.空间数据变化检测研究进展[J].测绘空间地理信息, 2014, 37(9):25-38 http://www.cnki.com.cn/Article/CJFDTOTAL-DBCH201409009.htm Liu Hulin, Yan Haowen, Liu Tao. Research on Spatial Data Change Detection [J]. Geomatics & Spatial Information Technology, 2014, 37(9):25-28 http://www.cnki.com.cn/Article/CJFDTOTAL-DBCH201409009.htm [4] Tu Wei, Li Qingquan, Fang Zhixiang, et al. Optimizing the Locations of Electric Taxi Charging Stations: A Spatial-temporal Demand Coverage Approach[J]. Transportation Research Part C: Emerging Technologies. 2015, 65, 172-189 doi: 10.1007/978-3-319-50230-4_7 [5] Tang Luliang, Yang Xue, Kan Zihan, et al. Lane-Level Road Information Mining from Vehicle GPS Trajectories Based on Naive Bayesian Classification [J]. ISPRS Int. J. Geo-Inf. 2015, 4(4): 2660-2680 doi: 10.3390/ijgi4042660 [6] 唐炉亮, 阚子涵, 黄方贞, 等.利用低频时空GPS轨迹进行交叉口通行时间探测[J].武汉大学学报·信息科学版, 2016, 41(1):136-142 http://ch.whu.edu.cn/CN/abstract/abstract3446.shtml Tang Luliang, Kan Zihan, Huang Fangzhen, et al. Travel Time Detection at Intersection from Taxis'Trace Data [J]. Geomatics and Information Science of Wuhan University, 2016, 41(1):136-142 http://ch.whu.edu.cn/CN/abstract/abstract3446.shtml [7] 姜桂艳, 常安德, 张玮.基于GPS浮动车采集交通信息的路段划分方法[J].武汉大学学报·信息科学版, 2010, 35(1):42-50 http://ch.whu.edu.cn/CN/abstract/abstract828.shtml Jiang Guiyan, Chang Ande, Zhang Wei. Link Dividing Method for Traffic Information Collecting Based on GPS Equipped Floating Car [J]. Geomatics and Information Science of Wuhan University, 2010, 35(1):42-50 http://ch.whu.edu.cn/CN/abstract/abstract828.shtml [8] 李德仁, 姚远, 邵振峰.智慧城市中的大数据[J].武汉大学学报·信息科学版, 2014, 39(6):631-640 http://ch.whu.edu.cn/CN/abstract/abstract2999.shtml Li Deren, Yao Yuan, Shao Zhenfeng. Big Data in Smart City [J]. Geomatics and Information Science of Wuhan University, 2014, 39(6):631-640 http://ch.whu.edu.cn/CN/abstract/abstract2999.shtml [9] 张淑玲, 管刚宇, 邹复民, 等.浮动车与空间网格结合的新增道路自动检测[J].科学技术与工程, 2012, 12(22):5496-5501 doi: 10.3969/j.issn.1671-1815.2012.22.017 Zhang Shuling, Guan Gangyu, Zou Fumin, et al. Combine the Floating Cars with Space Grid for Automatic Detection of the New Road [J]. Science Technology and Engineering, 2012, 12(22):5499-5501 doi: 10.3969/j.issn.1671-1815.2012.22.017 [10] Tang Luliang, Huang Fangzhen. Road Network Change Detection Based on Floating Car Data [J]. Journal of Networks, 2012, 7(7):1063-1070 doi: 10.1007/s11235-016-0155-5 [11] Boucher C, Noyer J C. Automatic Detection of Topological Changes for Digital Road Map Updating [J]. IEEE Transaction on Instrumentation & Measurement, 2012, 6(11): 3094-3102 [12] Zhao Yue, Liu Jian, Chen Runqiang, et al. A New Method of Road Network Updating Based on Floating Car Data [J]. IEEE International Geoscience & Remote Sensing Symposium, 2011, 24(8):1878-1881 [13] Frang E, Allan B, Dominic P B. Updating Road Network Databases: Road Segment Grouping Using Snap-Drift Network [C]. Proceedings of Geographical Information Science Research Conference, Maynooth, Ireland, 2007 [14] 王美玲, 程林.浮动车地图匹配算法研究[J].测绘学报, 2012, 41(1):133-138 http://cdmd.cnki.com.cn/Article/CDMD-10183-1013195549.htm Wang Meiling, Cheng Lin. Study on Map-matching Algorithm for Floating Car [J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1):133-138. http://cdmd.cnki.com.cn/Article/CDMD-10183-1013195549.htm [15] 李清泉, 胡波, 乐阳.一种基于约束的最短路径低频浮动车数据地图匹配算法[J].武汉大学学报·信息科学版, 2013, 38(7):805-808 http://ch.whu.edu.cn/CN/abstract/abstract2697.shtml Li Qingquan, Hu Bo, Yue Yang. Flowing Car Data Map-Matching Based on Constrained Shortest Path Algorithm [J]. Geomatics and Information Science of Wuhan University, 2013, 38(7):805-808 http://ch.whu.edu.cn/CN/abstract/abstract2697.shtml -
点击查看大图
图(5) / 表(1)
计量
- 文章访问数: 1386
- HTML全文浏览量: 121
- PDF下载量: 663
- 被引次数: 0
