﻿ 运用约束Delaunay三角网从众源轨迹线提取道路边界
 文章快速检索 高级检索

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
Foundation support: The National Natural Science Foundation of China (No.41531180),The National High Technology Research and Development Program of China(863 Program) (No.2015AA1239012)
First author: YANG Wei(1987—), male, PhD candidate, majors in spatial-temporal trajectory data modeling and mining.E-mail： ywgismap@whu.edu.cn
Corresponding author: AI Tinghua. E-mail:tinghua_ai@tom.com
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

1 众源轨迹线几何特征分析

2 Delaunay三角网支持下的轨迹数据提取道路边界

2.1 道路边界识别指标计算

(1) 密度变化率指数。道路边界作为道路面内外的分界线，两边的轨迹点密度差异显著，密度变化率成为道路边界识别的重要指标。文献[23]认为每个点目标的存在都要获取其生存空间，相邻点目标对分布空间的竞争结果相当于对空间做等分式划分(不考虑点性质差异)，并用点的Voronoi图面积的倒数表示该点的密度。在由轨迹线生成的Voronoi图中(图 1(a))，道路内部Voronoi图面积小，非道路区域Voronoi图面积大，道路边界两侧的轨迹点密度差异大。由于Delaunay三角网与Voronoi图互为对偶，故将轨迹密度变化差异融入Delaunay三角形边中。三角形边将空间分为左右区域，如果三角形边的左右两侧轨迹点密度差异大，则为道路边界区域。因此，三角形边相对左右两点的密度之比即是该边的密度变化率，该比值称为密度变化率指数(density change rate index，DCRI)，计算公式为

(1)

 图 1 道路边界识别指标及特征 Fig. 1 The characteristics of identification index of road boundary

(2) 边长距离。Delaunay三角网中边的长度表达了点目标间在空间分布上的远近关系，边越长轨迹稀疏，密度低；反之轨迹密集，密度高(图 1(b))。由于车辆轨迹沿道路网聚集分布，在由轨迹线构建的Delaunay三角网中(图 1(b))，道路内部区域三角形边长度小，非道路区域边长度大。设定边长阈值，将三角形边分为两级(图 1(b))，即可区分道路与非道路区域，识别道路边界。根据Delaunay三角网中边长的统计特征[22]，计算公式如下

(2)

2.2 基于Delaunay三角网的道路边界提取

2.2.1 轨迹数据预处理

2.2.2 道路边界提取方法

 图 2 道路边界提取算法及决策模型 Fig. 2 The algorithm of the road boundary extraction and decision model

(1) 孤立障碍边与障碍区。由于道路内部、不同等级道路连接处的轨迹密度差异，在搜索扩展中出现零散分布的孤立障碍边、障碍区(图 3(a)中C)。障碍区由少量Ⅱ类三角形、Ⅲ类三角形组成，形成了道路多边形区域内的障碍区“空洞”。这些孤立障碍边、障碍区的邻接区域都已扩展搜索，处于活跃状态。对于该情形，把障碍边当作非障碍边继续扩展。对于障碍区还需要设定面积阈值与环形道路中的非道路区域区分开。

 图 3 复杂情形下的道路边界提取决策 Fig. 3 The decision model of road boundary extraction

(2) 扩展“瓶颈”与边界平滑。在搜索过程中出现单一障碍边(图 3(b)中A)、单一Ⅲ类三角形(图 3(b)中B)阻断扩展路径，无法完成搜索。对于单一障碍边，如果障碍边左右邻接的三角形都处于扩展活跃状态，需跨越该障碍边继续扩展。对于Ⅲ类三角形，如果该Ⅲ类三角形的3个邻接三角形中有两个以上三角形处于扩展活跃状态，将与活跃状态三角形邻接的边作为非障碍边继续扩展。另外，城市支路上出现障碍边与非障碍边间隔分布(图 3(c))情形。针对该情形，判断每个Ⅱ类三角形障碍边的邻接三角形类型。如果是Ⅱ类、Ⅰ类、Ⅳ类，则跨越障碍边继续扩展；如果是Ⅲ类三角形，则以障碍边为边界终止扩展。扩展完成后的道路边界凹凸不平(图 3(b))，需对道路边界平滑化简，最后完成道路多边形提取。

2.3 指标参数取值及探讨

 图 4 参数取值范围及敏感度分析 Fig. 4 Range of parameter values and sensitivity analysis

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

 图 5 道路数据结果及定性评价 Fig. 5 The results of experiment and qualitative evaluation of road data

3.2 试验结果分析

 (%) 方法 道路面数据(叠置) 线数据(缓冲区) P R P(2 m) R(2 m) P(5 m) R(5 m) P(8 m) R(8 m) 本文方法 86.4 83.6 64.2 58.7 82.4 77.8 86.7 82.1 栅格化方法 76.7 71.2 28.6 23.1 63.7 60.2 74.1 72.9

 图 6 两种方法试验结果对比评价 Fig. 6 Comparative evaluation of experimental results of two methods

(1) 不同道路等级。城市区域不同等级道路具有不同交通流量、不同行车频率，导致轨迹密度悬殊。如图 7(a)所示，本文方法相比栅格化方法对于空间上邻近的双干道(图 7(a)中A)、低等级道路(图 7(a)中C)识别更完整。栅格化方法对密度低值区域无法提取或提取不完整(图 7(a)中C)，导致边界不平滑或拓扑断开，对高密度区域如双干道边界、环形匝道区域(图 7(a)中A、B)识别不如本文方法。

 图 7 特殊情形下的道路边界提取结果对比分析 Fig. 7 Comparison and analysis of road boundary extraction results under special circumstances

(2) 复杂道路结构。道路交叉口区域轨迹密集、数据量大，环形匝道、主干道等不同等级道路在空间上邻近，导致栅格化方法难以完整提取环形匝道内空白区域边界(图 7(b)中A、B处)。本文方法在边界提取中顾及了轨迹密度差异性，对于环形闸道与空白区域的区分较好(图 7(b)中边界)、边界提取更完整。

(3) 不同时间长度。分别选取1小时、1天、1周不同时间长度的轨迹线进行试验分析(图 7(c))。当处理1周轨迹数据量时(图 7(c)中D)，栅格化方法已经无法区分出环形道路中的空白区域，将空间上邻近的多条道路识别为一条道路。本方法对于1周数据量不进行轨迹线加密、选取约束性严格的参数值(DCRI=0.58，α=0.4)，提取的边界精度可达到73.1%，道路中的环形空白区也能较好识别(图 7(c)中D)。对于一条道路，轨迹量太少或太大(时间跨度过长)，即使通过调节参数也难以达到理想结果。

4 结 论

﻿

 [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. DOI:10.1007/s10707-014-0222-6 [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. DOI:10.1080/13658816.2014.944527 [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. DOI:10.1016/j.jag.2012.05.013 [9] 唐炉亮, 刘章, 杨雪, 等. 符合认知规律的时空轨迹融合与路网生成方法[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 [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. DOI:10.3390/ijgi4042446 [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. DOI:10.3724/SP.J.1047.2012.00165 [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. DOI:10.1080/13658816.2015.1092151 [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. DOI:10.1016/j.patcog.2008.03.023 [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. DOI:10.1111/tgis.2015.19.issue-1 [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. DOI:10.1080/136588197242419
http://dx.doi.org/10.11947/j.AGCS.2017.20160233

0

#### 文章信息

YANG Wei, AI Tinghua

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

Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 237-245
http://dx.doi.org/10.11947/j.AGCS.2017.20160233