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

doi:10.11947/j.AGCS.2019.20190011

Abstract

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

CLC Number:

P208

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.

References 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.