车辆轨迹数据提取道路交叉口特征的决策树模型

doi:10.11947/j.AGCS.2019.20190011

测绘学报 ›› 2019, Vol. 48 ›› Issue (11): 1391-1403.doi: 10.11947/j.AGCS.2019.20190011

车辆轨迹数据提取道路交叉口特征的决策树模型

万子健¹, 李连营¹, 杨敏¹, 周校东²

1. 武汉大学资源与环境科学学院, 湖北武汉 430072;
2. 地理信息工程国家重点实验室, 陕西西安 710054

收稿日期:2019-01-04 修回日期:2019-05-26 出版日期:2019-11-20 发布日期:2019-11-19
通讯作者: 杨敏 E-mail:yangmin2003@whu.edu.cn
作者简介:万子健(1997-),男,研究方向为空间数据匹配集成及更新。E-mail:zijwanim@gmail.com
基金资助:
国家自然科学基金（41871377）；国家重点研发计划（2017YFB0503500）；国家自然科学基金联合基金（U1764262）

Decision tree model for extracting road intersection feature from vehicle trajectory data

WAN Zijian¹, LI Lianying¹, YANG Min¹, ZHOU Xiaodong²

1. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430072, China;
2. State Key Laboratory of Geo-information Engineering, Xi'an 710054, China

Received:2019-01-04 Revised:2019-05-26 Online:2019-11-20 Published:2019-11-19
Supported by:
The National Natural Science Foundation of China (No. 41871377);The National Key Research and Development Program of China (No. 2017YFB0503500);The Joint Funds of the National Natural Science Foundation of China(No. U1764262)

摘要/Abstract

摘要： 众源车辆轨迹数据隐含最新的道路分布信息，研究利用轨迹数据提取道路特征有益于基础路网数据的快速建库与更新。道路网由交叉口和连接交叉口的道路线构成，其中交叉口特征识别是整个道路网生成的关键。由于缺乏精细的交叉口识别模型，轨迹数据生成的道路网容易出现路口遗漏、结构失真等现象。针对这一问题，本文提出一种利用轨迹数据提取道路交叉口的方法。首先，分析车辆在交叉口与非交叉口区域移动轨迹几何形态及隐含动力学特征的变化情形；然后，利用决策树方法构建轨迹片段分类模型，并结合移动开窗式的轨迹线剖分模型建立交叉口区域变道轨迹片段提取方法；最后，依据Hausdorff距离对交叉口区域轨迹片段进行聚类，并提取中心线获得完整的道路交叉口结构。采用真实的车辆轨迹线作为测试数据，验证了本文提出方法的有效性。

关键词: 车辆轨迹数据, 道路网, 交叉口识别, 决策树

Abstract: Crowd sourcing vehicle trajectory data imply the latest road network information. Therefore, studies on the extraction of road features from trajectory data provide the opportunity for efficient construction and renewal of road datasets. Since a road network is composed of road intersections and road segments, the extraction of road intersections plays an important role in road network generation. Due to the lack of accurate mechanisms for intersection extraction, problems such as omission and distortion of road intersections occur frequently. A method is proposed to identify and extract road intersections from vehicle trajectory data. Firstly, it is analyzed that the differences in shape and kinetic features between trajectories from intersection areas and non-intersection areas. Secondly, the decision tree method is employed to construct a trajectory segment classification model, which enables the extraction of lane-changing segments in intersection areas with the support of trajectory division model using a sliding window strategy. Thirdly, a method that based on Hausdorff distance is designed to cluster trajectory segments in intersection areas, and intersection structures are obtained by extracting the central lines of the trajectory segment clusters. Experiments on real-life trajectory datasets were implemented and results showed the effectiveness of the proposed method.

Key words: vehicle trajectory data, road network, road intersection extraction, decision tree

中图分类号:

P208

万子健, 李连营, 杨敏, 周校东. 车辆轨迹数据提取道路交叉口特征的决策树模型[J]. 测绘学报, 2019, 48(11): 1391-1403.

WAN Zijian, LI Lianying, YANG Min, ZHOU Xiaodong. Decision tree model for extracting road intersection feature from vehicle trajectory data[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1391-1403.

参考文献 28

[1]	ANDRIENKO G, ANDRIENKO N. Spatio-temporal aggregation for visual analysis of movements[C]//Proceedings of2008 IEEE Symposium on Visual Analytics Science and Technology. Columbus, OH:IEEE, 2008:51-58.
[2]	龙瀛, 张宇, 崔承印. 利用公交刷卡数据分析北京职住关系和通勤出行[J]. 地理学报, 2012, 67(10):1339-1352. LONG Ying, ZHANG Yu, CUI Chengyin. Identifying commuting pattern of Beijing using bus smart card data[J]. Acta Geographica Sinica, 2012, 67(10):1339-1352.
[3]	LIU Yaqiong, SEAH H S. Points of interest recommendation from GPS trajectories[J]. International Journal of Geographical Information Science, 2015, 29(6):953-979.
[4]	DAVIES J J, BERESFORD A R, HOPPER A. Scalable, distributed, real-time map generation[J]. IEEE Pervasive Computing, 2006, 5(4):47-54.
[5]	LIU Xuemei, BIAGIONI J, ERIKSSON J, et al. Mining large-scale, sparse GPS traces for map inference:comparison of approaches[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China:ACM, 2012:669-677.
[6]	BIAGIONI J, ERIKSSON J. Inferring road maps from global positioning system traces:survey and comparative evaluation[J]. Transportation Research Record:Journal of the Transportation Research Board, 2012, 2291(1):61-71.
[7]	KUNTZSCH C, SESTER M, BRENNER C. Generative models for road network reconstruction[J]. International Journal of Geographical Information Science, 2016, 30(5):1012-1039.
[8]	EDELKAMP S, SCHRÖDL S. Route planning and map inference with global positioning traces[M]//KLEIN R, SIX H W, WEGNER L. Computer Science in Perspective:Essays Dedicated to Thomas Ottmann.Berlin, Heidelberg:Springer, 2003:128-151.
[9]	SCHROEDL S, WAGSTAFF K, ROGERS S, et al. Mining GPS traces for map refinement[J]. Data Mining andKnowledge Discovery, 2004, 9(1):59-87.
[10]	GUO Tao, IWAMURA K, KOGA M. Towards high accuracy road maps generation from massive GPS Traces data[C]//Proceedings of 2007 IEEE International Geoscience and Remote Sensing Symposium.Barcelona, Spain:IEEE, 2007.
[11]	AGAMENNONI G, NIETO J I, NEBOT E M. Robust inference of principal road paths for intelligent transportation systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(1):298-308.
[12]	EZZAT M, SAKR M, ELGOHARY R, et al. Building road segments and detecting turns from GPS tracks[J]. Journal of Computational Science,2018, 29(11):81-93.
[13]	PEUCKER T. A theory of the cartographic line[J]. International Yearbook of Cartography,1976, 16(1):134-143.
[14]	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.
[15]	CAO Lili, KRUMM J. From GPS traces to a routable road map[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington:ACM, 2009:3-12.
[16]	唐炉亮, 牛乐, 杨雪, 等. 利用轨迹大数据进行城市道路交叉口识别及结构提取[J]. 测绘学报, 2017, 46(6):770-779. DOI:10.11947/j.AGCS.2017.20160614. TANG Luliang, NIU Le, YANG Xue, et al. Urban intersection recognition and construction based on big trace data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(6):770-779. DOI:10.11947/j.AGCS.2017.20160614.
[17]	杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2):237-245. DOI:10.11947/j.AGCS.2017.20160233. YANG Wei, AI Tinghua. The extraction of road boundary from crowdsourcing trajectory using constrained delaunaytriangulation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):237-245. DOI:10.11947/j.AGCS.2017.20160233.
[18]	LI Jun, QIN Qiming, XIE Chao, et al. Integrated use of spatial and semantic relationships for extracting road networks from floating car data[J]. International Journal of Applied Earth Observation and Geoinformation, 2012, 19(10):238-247.
[19]	唐炉亮, 刘章, 杨雪, 等. 符合认知规律的时空轨迹融合与路网生成方法[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.
[20]	RUTKOWSKI L, JAWORSKI M, PIETRUCZUK L, et al. The CART decision tree for mining data streams[J]. Information Sciences, 2014, 266(5):1-15.
[21]	田晶, 艾廷华, 丁绍军. 基于C4.5算法的道路网网格模式识别[J]. 测绘学报, 2012, 41(1):121-126. TIAN Jing, AI Tinghua, DING Shaojun. Grid pattern recognition in road networks based on C4.5 algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1):121-126.
[22]	陈利燕, 张新长, 林鸿, 等. 跨比例尺新旧居民地目标变化分析与决策树识别[J]. 测绘学报, 2018, 47(3):403-412. DOI:10.11947/j.AGCS.2018.20170373. CHEN Liyan, ZHANG Xinchang, LIN Hong, et al. Change analysis and decision tree based detection model for residential objects across multiple scales[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(3):403-412. DOI:10.11947/j.AGCS.2018.20170373.
[23]	KIM I H, FENG C C, WANG Yichen. A simplified linear feature matching method using decision tree analysis, weighted linear directional mean, and topological relationships[J]. International Journal of Geographical Information Science, 2017, 31(5):1042-1060.
[24]	李春鑫, 李天伟. 基于决策树改进CART算法的决策支持与分析技术[J]. 计算机科学, 2004, 31(9A):44-46. LI Chunxin, LI Tianwei. Decision support and analysis technique based on improved CART arithmetic of decision trees[J]. Computer Science, 2004, 31(9A):44-46.
[25]	陈锦阳, 宋加涛, 刘良旭, 等. 基于改进Hausdorff距离的轨迹聚类算法[J]. 计算机工程, 2012, 38(17):157-161. CHEN Jinyang, SONG Jiatao, LIU Liangxu, et al. Trajectory clustering algorithm based on improved Hausdorffdistance[J]. Computer Engineering, 2012, 38(17):157-161.
[26]	ETIENNE L, DEVOGELE T, BUCHIN M, et al. Trajectory box plot:a new pattern to summarize movements[J]. International Journal of Geographical Information Science, 2016, 30(5):835-853.
[27]	UDUWARAGODA ERIAC M, PERERA AS, DIAS SAD. Generating lane level road data from vehicle trajectories using kernel density estimation[C]//Proceedings of the 16th International IEEE Conference on Intelligent Transportation Systems. ZThe Hague, Netherlands:IEEE, 2014:384-391.
[28]	DENG Min, HUANG Jincai, ZHANG Yunfei, et al. Generating urban road intersection models from low-frequency GPS trajectory data[J]. International Journal of Geographical Information Science, 2018, 32(12):2337-2361.

车辆轨迹数据提取道路交叉口特征的决策树模型

Decision tree model for extracting road intersection feature from vehicle trajectory data

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 28

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张彩丽, 向隆刚, 李雅丽, 王文龙. 基于出租车轨迹的可导航路网构建[J]. 测绘学报, 2021, 50(12): 1650-1662.
[2]	郭漩, 钱海忠, 王骁, 刘俊楠, 钟吉. 道路网选取的案例与本体推理方法[J]. 测绘学报, 2021, 50(12): 1717-1727.
[3]	郭庆胜, 刘洋, 李萌, 程晓茜, 何捷, 王慧慧, 魏智威. 基于网格模型的导航道路图渐进式化简方法[J]. 测绘学报, 2019, 48(11): 1357-1368.
[4]	张志然, 刘纪平, 仇阿根, 钱新林, 张福浩. 面向大规模道路网的最短路径近似算法[J]. 测绘学报, 2019, 48(1): 86-94.
[5]	陈利燕, 张新长, 林鸿, 杨敏. 跨比例尺新旧居民地目标变化分析与决策树识别[J]. 测绘学报, 2018, 47(3): 403-412.
[6]	崔晓杰, 王家耀, 巩现勇, 武芳. 基于改进霍夫变换的环形交叉口识别方法[J]. 测绘学报, 2018, 47(12): 1670-1679.
[7]	黄博华, 钟巍, 翟仁健, 周青. 城市道路网匹配的层次化面域剖分模型[J]. 测绘学报, 2018, 47(11): 1526-1536.
[8]	裴洪星, 翟仁健, 武芳, 李靖涵, 巩现勇, 吴铮. 小比例尺道路网眼约束下的多尺度道路网自动匹配[J]. 测绘学报, 2017, 46(6): 760-769.
[9]	郭庆胜, 谢育武, 刘纪平, 王琳, 周林. 顾及尺度变化和数据更新的道路网匹配算法[J]. 测绘学报, 2017, 46(3): 381-388.
[10]	付仲良, 杨元维, 高贤君, 赵星源, 范亮. 道路网多特征匹配优化算法[J]. 测绘学报, 2016, 45(5): 608-615.
[11]	王骁, 钱海忠, 何海威, 陈竞男, 胡慧明. 顾及邻域居民地群组相似性的道路网匹配方法[J]. 测绘学报, 2016, 45(1): 103-111.
[12]	蒋波涛, 王艳东, 叶信岳. 使用点评数据探测城市商业服务设施的发展规律[J]. 测绘学报, 2015, 44(9): 1022-1028.
[13]	郭敏钱海忠黄智深何海威刘海龙. 采用案例类比推理进行道路网智能选取[J]. 测绘学报, 2014, 43(7): 761-770.
[14]	胡荣明黄小兵黄远程. 增强形态学建筑物指数应用于高分辨率影像中建筑物提取[J]. 测绘学报, 2014, 43(5): 514-520.
[15]	栾学晨杨必胜李秋萍. 保持城市道路格网模式的街区合并混合整数规划模型[J]. 测绘学报, 2014, 43(4): 426-434.