﻿ 运用约束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 结 论

﻿

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