运用约束Delaunay三角网从众源轨迹线提取道路边界

doi:10.11947/j.AGCS.2017.20160233

测绘学报 ›› 2017, Vol. 46 ›› Issue (2): 237-245.doi: 10.11947/j.AGCS.2017.20160233

运用约束Delaunay三角网从众源轨迹线提取道路边界

杨伟, 艾廷华

武汉大学资源与环境科学学院, 湖北武汉 430079

收稿日期:2016-05-11 修回日期:2016-12-22 出版日期:2017-02-20 发布日期:2017-03-07
作者简介:杨伟(1987-),男,博士生,研究方向为时空轨迹数据建模与挖掘。E-mail:ywgismap@whu.edu.cn
基金资助:
国家自然科学基金重点项目（41531180）；国家863计划（2015AA1239012）

The Extraction of Road Boundary from Crowdsourcing Trajectory Using Constrained Delaunay Triangulation

YANG Wei, AI Tinghua

School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China

Received:2016-05-11 Revised:2016-12-22 Online:2017-02-20 Published:2017-03-07
Contact: 艾廷华 E-mail:tinghua_ai@tom.com
Supported by:
The National Natural Science Foundation of China (No.41531180),The National High Technology Research and Development Program of China(863 Program) (No.2015AA1239012)

摘要/Abstract

摘要： 运用众源车辆轨迹数据提取道路信息需要解决轨迹点采样稀疏、高噪音、密度差异大等问题。为此，本文提出一种运用约束Delaunay三角网从车辆轨迹线集中提取道路边界的方法。首先，通过三角形边长度和Voronoi面积等几何特征表达轨迹点分布的聚集性差异，并将这两种不同几何维数的控制条件集成建立道路边界识别模型，运用“种子点”区域扩展方法实现道路边界的精确提取。最后，运用北京市出租车GPS轨迹进行试验，结果表明该方法适于车辆分布频率悬殊、时间跨度不同、道路网结构复杂的轨迹线数据处理。

关键词: 众源轨迹, 道路更新, 约束Delaunay三角网, 空间聚类

Abstract: Extraction of road boundary accurately from crowdsourcing trajectory lines is still a hard work.Therefore,this study presented a new approach to use vehicle trajectory lines to extract road boundary.Firstly, constructing constrained Delaunay triangulation within interpolated track lines to calculate road boundary descriptors using triangle edge length and Voronoi cell.Road boundary recognition model was established by integrating the two boundary descriptors.Then,based on seed polygons,a regional growing method was proposed to extract road boundary. Finally, taxi GPS traces in Beijing were used to verify the validity of the novel method, and the results also showed that our method was suitable for GPS traces with disparity density,complex road structure and different time interval.

Key words: crowdsourcing trajectory, road updating, Delaunay triangulation, spatial clustering

中图分类号:

P208

杨伟, 艾廷华. 运用约束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.

参考文献

[1] 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.
[2] 杨伟, 艾廷华. 基于车辆轨迹大数据的道路网更新方法研究[J]. 计算机研究与发展, 2016, 53(12):2681-2693. YANG Wei, AI Tinghua. A Method for Road Network Updating Based on Vehicle Trajectory Big Data[J]. Journal of Computer Research and Development, 2016, 53(12):2681-2693.
[3] 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.
[4] ZHANG Lijuan,THIEMANN F,SESTER M. Integration of GPS Traces with Road Map[C]//Proceedings of the Third International Workshop on Computational Transportation Science. New York:ACM, 2010:17-22.
[5] GUO Tao, IWAMURA K, KOGA M. Towards High Accuracy Road Maps Generation from Massive GPS Traces Data[C]//Proceedings of the 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona:IEEE, 2007:667-670.
[6] 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. New York:ACM, 2012:669-677.
[7] CAO Lili, KRUMM J. From GPS Traces to a Routable Road Map[C]//Proceedings of the 17th ACM SIGSP-ATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2009:3-12.
[8] 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:238-247.
[9] 唐炉亮, 刘章, 杨雪, 等. 符合认知规律的时空轨迹融合与路网生成方法[J]. 测绘学报, 2015, 44(11):1271-1276. DOI:10.11947/j.AGCS.2015.20140591. 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.
[10] WU Junwei, ZHU Yunlong, KU Tao, et al. Detecting Road Intersections from Coarse-gained GPS Traces Based on Clustering[J]. Journal of Computers, 2013, 8(11):2959-2965.
[11] XIE Xingzhe,BING-YUNGWONG K,AGHAJAN H,et al. Inferring Directed Road Networks from GPS Traces by Track Alignment[J]. ISPRS International Journal of Geo-Information, 2015, 4(4):2446-2471.
[12] SHI Wenhuan, SHEN Shuhan, LIU Yuncai. Automatic Generation of Road Network Map from Massive GPS, Vehicle Trajectories[C]//Proceedings of the 12th International IEEE Conference on Intelligent Transportation Systems. St. Louis, MO:IEEE, 2009:1-6.
[13] 蒋益娟, 李响, 李小杰, 等. 利用车辆轨迹数据提取道路网络的几何特征与精度分析[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.
[14] KUNTZSCH C, SESTER M, BRENNER C. Generative Models for Road Network Reconstruction[J]. International Journal of Geographical Information Science, 2016, 30(5):1012-1039.
[15] WANG Yin,LIU Xuemei,WEI Hong, et al. Crowd Atlas:Self-updating Maps for Cloud and Personal Use[C]//Proceedings of the 11th Annual International Conference on Mobile Systems, Applications, and Services. New York:ACM, 2013:27-40.
[16] 李怡静, 胡翔云, 张剑清, 等. 影像与LiDAR数据信息融合复杂场景下的道路自动提取[J]. 测绘学报, 2012, 41(6):870-876. LI Yijing,HU Xiangyun,ZHANG Jianqing,et al. Automatic Road Extraction in Complex Scenes Based on Information Fusion from LiDAR Data and Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6):870-876.
[17] 方莉娜, 杨必胜. 车载激光扫描数据的结构化道路自动提取方法[J]. 测绘学报, 2013, 42(2):260-267. FANG Lina, YANG Bisheng. Automated Extracting Structural Roads from Mobile Laser Scanning Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2):260-267.
[18] 杨伟, 艾廷华. 基于众源轨迹数据的道路中心线提取[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.
[19] 李清泉, 李德仁. 大数据GIS[J]. 武汉大学学报(信息科学版), 2014, 39(6):641-644. LI Qingquan, LI Deren. Big Data GIS[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6):641-644.
[20] DUCKHAM M,KULIK L,WORBOYS M, et al. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane[J]. Pattern Recognition, 2008, 41(10):3224-3236.
[21] LIU Qiliang, TANG Jianbo, DENG Min, et al. An Iterative Detection and Removal Method for Detecting Spatial Clusters of Different Densities[J]. Transactions in GIS, 2015, 19(1):82-106.
[22] 艾廷华, 郭仁忠. 基于约束Delaunay结构的街道中轴线提取及网络模型建立[J]. 测绘学报, 2000, 29(4):348-354. AI Tinghua, GUO Renzhong. Extracting Center-lines and Building Street Network Based on Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(4):348-354.
[23] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2):175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2):175-181.
[24] ZHENG Yu, LI Quannan, CHEN Yukun, et al. Understanding Mobility based on GPS Data[C]//Proceedings of the 10th International Conference on Ubiquitous Computing. New York:ACM, 2008:312-321.
[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.

运用约束Delaunay三角网从众源轨迹线提取道路边界

The Extraction of Road Boundary from Crowdsourcing Trajectory Using Constrained Delaunay Triangulation

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	刘呈熠, 武芳, 巩现勇, 行瑞星, 杜佳威. 空间知识挖掘的自然面群聚集度聚类方法[J]. 测绘学报, 2021, 50(4): 544-555.
[2]	杨伟, 艾廷华. 轨迹分割与图层融合的车辆轨迹线构建道路地图方法[J]. 测绘学报, 2018, 47(12): 1650-1659.
[3]	郭庆胜, 魏智威, 王勇, 王琳. 特征分类与邻近图相结合的建筑物群空间分布特征提取方法[J]. 测绘学报, 2017, 46(5): 631-638.
[4]	刘萌, 邬群勇, 邱端昇, 孙梅, 张强. 签到位置数据的密度峰值快速搜索与聚类方法[J]. 测绘学报, 2017, 46(4): 516-525.
[5]	李志林, 刘启亮, 唐建波. 尺度驱动的空间聚类理论[J]. 测绘学报, 2017, 46(10): 1534-1548.
[6]	郭沛沛, 李成名, 殷勇. 建筑物合并的Delaunay三角网分类过滤法[J]. 测绘学报, 2016, 45(8): 1001-1007.
[7]	唐炉亮, 杨雪, 牛乐, 常乐, 李清泉. 一种众源车载GPS轨迹大数据自适应滤选方法[J]. 测绘学报, 2016, 45(12): 1455-1463.
[8]	余莉, 甘淑, 袁希平, 杨明龙. 综合线面特征分布的点目标多尺度聚类方法[J]. 测绘学报, 2015, 44(10): 1152-1159.
[9]	李佳田, 康顺, 罗富丽. 利用层次Voronoi图进行点群综合[J]. 测绘学报, 2014, 43(12): 1300-1306.
[10]	刘启亮,邓敏,石岩,彭东亮. 一种基于多约束的空间聚类方法[J]. 测绘学报, 2011, 40(4): 0-441.
[11]	耿协鹏杜晓初胡鹏. 基于栅格距离变换的扩展对象空间聚类方法[J]. 测绘学报, 2009, 38(2): 0-174.