2. 邵阳学院城乡建设学院, 湖南 邵阳 422000;
3. 国网思极神往位置服务(北京)有限公司, 北京 100000
2. Urban and Rural Construction College, Shaoyang University, Shaoyang 422000, China;
3. State Grid Siji Shenwang Location Service(Beijing) Co., Ltd., Beijing 100000, China
道路网络作为智慧城市发展的重要基础条件，不仅需要交叉口与路段来表达几何与拓扑信息，而且需要导航信息来承载道路连接语义，从而支撑大规模车辆在道路网络中的有序流动。传统路网信息获取主要依靠野外测量及遥感影像处理[1]，不仅时间长、成本高、现势性差，还难以获得道路的转向、单双向等导航信息。随着便携式定位设备的普及，利用成本低、覆盖广，易于获取，现势性强，蕴含丰富道路语义信息[2]的出租车轨迹数据开展可导航路网构建成为可能。然而，一方面，出租车轨迹数据噪声大，采样频率低，采样间隔不固定，另一方面，城市道路网具有非常复杂的空间结构，且在转向关系上有多种约束。从出租车轨迹中提取城市道路信息，形成可导航路网模型是一件相当有挑战性的工作。
目前，业界基于GPS轨迹数据开展了大量路网构建方面的研究工作，主要集中于路网骨架结构的提取，包括增量法、聚类法、栅格法，以及交叉口连接法。增量法通过逐步插入轨迹来不断完善初始路网，先后提出了引力斥力模型[3]、加权Delaunay三角网[4]、信息熵[5]等方法；聚类法针对大规模轨迹点或轨迹段进行聚类，然后通过拟合聚类簇或表征点形成路网，代表性方法有k-means[6-7]、DBSCAN[8-9]、OPTICS[10]等；栅格法对轨迹数据进行栅格化处理，然后利用Voronoi分割[11]、形态学处理[12]、LDA推导[13]等方法进行道路中心线提取；交叉口连接法首先利用轨迹点密度等隐含语义特征[14-15]，轨迹点方向等隐含动力学特征[16-17]，以及道路几何特征[18-20]等识别道路交叉口，然后提取连接交叉口[21-22]的路段信息。在路网导航信息挖掘方面，文献[23]引入置信点概念，而文献[16-17, 24]考虑交叉口影响范围内子轨迹，通过聚类等方法分析交叉口转向规则。上述工作大多要求高频率、高精度的轨迹数据输入，不能满足低频高噪出租车轨迹数据的路网构建。
在文献[2, 14, 20]中，基于交叉口连接特征及出租车轨迹密度特征，设计了一种交叉口优先的城市路网生成方法。首先通过结合数学形态学处理与密度峰值聚类(CFDP)[25-26]，开展矢栅融合的交叉口识别；然后据此对形态学方法生成骨架线进行位置调整及断裂修复，在一定程度上解决了从低质量出租车轨迹提取交叉口及其关联路段的问题。由于城市路网的复杂性，仍然有大量未识别和错提取的现象。为此，本文一方面致力于交叉口及其路段的全面精确识别；另一方面着眼于转向等导航信息的提取，从而构建出面向城市的可导航路网结构。具体而言，考虑到交叉口的连接本质，采用“交叉口位置-路段几何-导航属性”的研究思路(图 1)。首先，在已有工作基础上设计顾及多模特征的交叉口集成识别方法及零样本监督式去伪策略；然后，考虑Delaunay三角网邻接特征，轨迹分布特征及道路几何特征，识别交叉口之间的拓扑关系，并融合形态学结果生成路段几何；最后，分析出租车轨迹在交叉口处的方向与连接信息，推导交叉口转向规则及路段单双向属性，从而实现城市可导航路网的构建。
|
| 图 1 可导航路网构建流程 Fig. 1 Navigable road network construction |
1 交叉口位置探测
作为路网结构提取及导航属性分析的首要环节，交叉口识别的全面性与准确度直接影响可导航路网的生成质量。为此，本文分析与挖掘出租车轨迹在矢栅空间关于交叉口的多模特征，设计道路交叉口的集成识别技术，提出基于随机森林方法的零标注监督式分类，实现待定交叉口的去伪留真。具体技术流程如图 2所示。
|
| 图 2 交叉口识别流程 Fig. 2 Road intersection recognition |
1.1 交叉口多模特征分析
由于交叉口处红绿灯限制、两条以上道路实体交汇衔接以及行驶车道变更转换，出租车经过时往往发生停留、转向等行为，不仅形成不同于其他区域的轨迹点密度、行进方向及速度等低阶特征，还呈现出交叉口拓扑连接、方向多样性、反向交汇点密度、主成分比[14]、转向聚类个数等高阶特征。这些多模多阶特征形成了关于交叉口的高判别性互补特征集，可作为识别交叉口的基础与依据。考虑到不同特征在矢量空间和栅格空间计算互补优势，本文选择轨迹点密度、拓扑连接、反向交汇点密度等栅格空间特征进行交叉口集成提取与融合，其他矢量空间特征用于零标注监督式去伪。具体特征设计如下。
1.1.1 轨迹点密度特征fP为消除噪声轨迹点影响，本文将轨迹数据进行格网化，以核密度代替单位面积内轨迹点个数来表征轨迹分布情况。给定搜索半径h，栅格单元的核密度估计可基于K函数[16]进行计算，可以看到高密度区域总是分布在交叉口周围，如图 3(a)所示。
|
| 图 3 交叉口多模特征示例 Fig. 3 The illustration of multi-mode features for road intersection |
1.1.2 拓扑连接特征fN
设置合适阈值k，从上述轨迹核密度分布图中提取高密度区域，对其进行形态学细化，8邻域内像素点个数刻画了道路不同区域的连接特征，如图 3(b)所示。
1.1.3 反向交汇点密度fT基于文献[26]提出的反向交汇点(图 3(c))，进一步进行核密度分析(图 3(d))可加强交叉口表征特性。考虑到弯道段上距离较远转向点对反向交汇点会落在道路外，本文基于转向点对距离统计直方图(图 3(e))，对转向点对距离d进行限制，限制后转向点对基本分布于交叉口周边(图 3(g))。
1.1.4 方向多样性fH与路段相比，交叉口的车辆行驶方向更加多样化。给定搜索半径h，每隔30°对0°~360°进行划分，计算每个方向间隔内轨迹点数Ni占落入搜索半径h内总轨迹点数N的比例，利用辛普森多样性指数(式(1))即可统计路网不同区域轨迹点方向多样性
(1)
由于路段的通行特性，一般不会像交叉口处一样发生大量转向，因此以某点为中心，搜索h范围内反向交汇点(图 3(f)中的红色五角星)，进而反推转向点对TP(如(P1, P2)(P3, P4))，基于转向点对起始与终止方向进行层次聚类，并统计转向点方向聚类个数，即可有效区分交叉口与其他区域。
1.1.6 主成分比fΔ由于交叉口连接多个路段，轨迹点在交叉口分布时一般呈现非线性特性，如图 3(h)所示。以某点为中心，截取一定范围h内轨迹点，以轨迹点集合的x和y坐标为变量，构造协方差矩阵，计算特征值λ1和λ2，基于式(2)即可判断轨迹点分布特征，值越小非线性特征越强，越有可能为交叉口
(2)
车辆经过交叉口一般需要减速，因此，轨迹点速度平均值fSa及速度标准差fSd也可作为区分交叉口与其他区域的有效指标。
1.2 交叉口提取与融合基于轨迹点密度特征fP或反向交汇点密度特征fT获取的密度信息ρ，对高密度区域进行局部距离δ计算，即可采用CFDP算法进行类簇中心(道路交叉口)识别。为保证提取更多交叉口，本文仅对局部距离进行限制[14]，基于决策图将局部距离大于D的栅格单元识别为交叉口。特征fP、fT虽可有效识别候选交叉口，但却无法保证交叉口的准确性，因此，为获取更高置信交叉口，本文进一步引入交叉口连接特征fN，将8邻域内像素点个数大于2的单元识别为候选交叉口。基于特征fP、fT、fN识别的候选交叉口结果设计了相应融合机制，见表 1，可有效区分真交叉口、伪交叉口及待定交叉口如图 4所示。
| 基于fT提取结果(R1) | 基于fN提取结果(R2) | 基于fP提取结果(R3) | 融合规则 | 输出结果 |
| √ | √ | √ | 真 | R1 |
| √ | √ | - | 真 | R1 |
| √ | - | √ | 待定 | R1 |
| √ | - | - | 待定 | R1 |
| - | √ | √ | 真 | R2 |
| - | √ | - | 假 | R2 |
| - | - | √ | 假 | R3 |
|
| 图 4 交叉口融合结果 Fig. 4 The fusion results of road intersections |
1.3 零标注监督式去伪
由于出租车轨迹数据噪声大，直接由单一特征取经验阈值对待定交叉口进行去伪效果较差。为此，本文将待定交叉口去伪看成真伪分类问题，选择主成分比fΔ[14]、速度标准差fSd、速度平均值fSa、方向多样性fH及转向点方向聚类数fC等特征，从而利用随机森林方法，实现多模特征的待定交叉口分类。
考虑到基于融合规则判别的真伪交叉口(图 4(a))分布均匀且代表性强，本文随机将真伪交叉口60%作为训练样本，40%作为验证样本。首先利用训练样本，基于随机森林分类器对上述特征进行重要性度量，如图 5(a)所示，优先选择重要性分值最高的3个特征fΔ、fH和fC；然后对fΔ、fH和fC随机组合进行训练，得到各组合训练的模型；利用验证样本，基于各组合训练的模型，得到各特征子集识别准确率，最终选择识别率最高组合(fΔ、fH、fC)训练的模型对待定交叉口进行零样本监督式去伪。与仅考虑交叉口非线性特征的主成分分析去伪方法相比，该方法既较大程度保留了真交叉口(图 5(b))，又剔除了大量伪交叉口，有效解决了监督分类需要标注及单特征识别精度不高等问题。为保证分类模型计算速度及精度，所有特征均进行了min-max标准化处理。
|
| 图 5 待定交叉口去伪 Fig. 5 False intersection removal from undetermined results |
2 路段几何提取
任意两交叉口之间可能有路段连接，但相距较近的交叉口之间存在路段的可能性更大。考虑Delaunay三角网边在一定程度上反映交叉口之间的邻接信息，本文综合轨迹点分布特征及道路几何特征，融合形态学细化结果，提出一种基于Delaunay三角网的多阶段路段生成方法，不仅有效避免了扫描所有组合而引发的计算风暴实现大规模路段的高效探测，还解决了间隔较小交叉口附近路段的扭曲问题，识别了密集区域及稀疏区域路段信息，具体流程如图 6所示。
|
| 图 6 可导航路网生成流程 Fig. 6 Navigable road network generation |
2.1 路段识别
由于Delaunay三角网边缘存在许多狭长三角形，直接进行路段提取会引入伪结果，因此本文首先迭代剔除两公共边角度大于135°的狭长三角形并将剩余三角形边作为候选路段集S进行后续多阶段路段识别：
(1) 真路段轨迹点分布一般较为密集，因此本文首先将轨迹点高密度区域矢量化与候选路段集S叠加，如图 7(a)所示，保留重叠长度与其长度比值大于γ的路段，记入集合T1，可得到图 7(c)中的红色路段。
|
| 图 7 基于Delaunay三角网的路段提取 Fig. 7 The extraction of road segment based on Delaunay triangulation network |
(2) 考虑到Delaunay三角网的最大空圆准则及上述策略无法识别弯曲路段和研究区边缘路段，如图 7(a)中A、B、C区域，本文将形态学骨架线矢量化并化简，与路段集T1 50 m缓冲区进行匹配，保留长度大于l的未匹配路段，如图 7(b)所示，并基于方向与距离将其延伸到相应交叉点及缺失路段端点。完成以上3种状况路段的补充，记为T2，如图 7(c)中的绿色路段。
(3) 以上得到路段集T={T1，T2}皆位于高密度区域。考虑城市相邻道路夹角通常不会小于60°[22]，最后本文进一步从S集中识别与路段集T具有公共结点，夹角大于60°，且不与其他无公共结点路段相交的路段，记入T3集合，结果如图 7(c)中的黄色路段。
2.2 路段拟合T1集合与T2集合识别的路段可直接表达为该路段的几何中心线。T3集合仍包含伪路段，且直线段不足以表达路段的几何形状，需进一步判断连接路段两交叉口间是否存在子轨迹进行伪路段剔除，并对识别真路段进行分段拟合。
如果某条轨迹中一点Pi落在交叉口Ii影响范围ri内，存在另一点Pj落在交叉口Ij影响范围rj内，则表明轨迹段[Pi, Pj]为交叉口Ii和Ij之间的子轨迹段。由于道路交叉点影响距离不会超过以该交叉点为公共顶点的最短边直线距离d，顾及轨迹采样频率及道路宽度影响，本文将ri、rj设置为β×d，如图 8(a)所示。为剔除伪子轨迹，本文还进行了如下的范围及方向限制。
|
| 图 8 子轨迹提取及路段拟合 Fig. 8 Sub-trajectory extraction and road segment fitting |
(1) 范围限制。以Ii与Ij之间的中点Pcenter为原点，Ii Ij为X轴，Ii Ij的垂线为Y轴，如图 8(b)所示。则子轨迹点到原点的距离在X轴方向投影disx(Pi, Pcenter)及在Y轴方向投影disy(Pi, Pcenter)满足以下条件
(3)
(2) 方向限制。车辆在道路上行驶时，除非在十字路口转弯，否则行驶方向不会发生太大变化，因此子轨迹点方向限制如下
(4)
式中，Pi、Pj为子轨迹点(0≤i < j≤n-1)；dir(Ii, Ij)为Ii Ij路段方位角；heading(Pi)为子轨迹点Pi头方向。
基于Ii Ij两方向子轨迹即可对路段进行拟合，首先将路段的直连线段划分为M等份，然后提取每一段局部密度极大点，最后将起点、局部密度极大点及终点依次连接，利用道格拉斯算法对形成的折线段进行简化，完成分段拟合，如图 8(c)所示。
需要说明的是，如果T1集合中存在三角形3条边都被识别，并且至少一个非斜边不是其他三角形斜边，则该三角形斜边为伪路段，需要从T1集合剔除。如果T1集合中存在悬挂边，且该边与其他T1集合具有公共结点路段之间夹角小于60°，则为伪路段，也需从T1集合中剔除。基于提取路网T=[T1, T2, T3]，进一步剔除一些少于3条道路与之相连，违反交叉口定义的伪交叉点，并对路网进行拓扑检查，合并伪节点连接的两条路段，完成道路网拓扑纠错。
3 导航属性分析转向关系的有效性直接决定了城市路网导航信息的质量，是导航信息计算的重中之重。本文顾及出租车轨迹采样频率及城市路段的短连接特性，以“路段-交叉点-路段”[23]的形式进行交叉口与路段的关联分析，研究路段到路段的转向模式，进一步分析路段的单双向信息，实现可导航路网构建的有效探索。
3.1 路段转向关系识别考虑到出租车轨迹采样频率较低，难以探测交叉口转向片段，本文将转向与直行关系区分对待，基于相似性评价指标分别对交叉口转向点对(图 3(f))及直行片段进行层次聚类，然后计算交叉口关联路段，分析路段之间转向关系进行路网转弯信息识别。对于任意的两个转向点对/直行片段(t1, t2)，其空间相似性主要体现在起始点方向差异和终止点方向差异[16, 24]，设立如下指标进行转向点对/直行片段的相似性评价
(5)
式中，dis(θs1, θs2)、dis(θe1, θe2)为起始点及终止点头方向欧氏距离。为了更好地度量角度之间的距离，本文将方向进行了极坐标转换[27]。w1和w2与起始点之间、终止点之间相似度有关，如果e-dis(θs1, θs2)和e-dis(θe1, θe2)的值都大于0.5，则w1、w2均设置为0.5；否则，如果e-dis(θs1, θs2)>e-dis(θe1, θe2)，设置w1=0.01、w2=0.99，如果e-dis(θs1, θs2) < e-dis(θe1, θe2)，设置w1=0.99、w2=0.01。
基于路段几何提取信息，可进一步根据转弯/直行聚类簇起止方向确定交叉口的关联路段。为消除少数非法掉头与随机转弯情况，根据经验将转向点对数量小于3的聚类簇剔除。以图 9中交叉口I为例，对于每类聚类簇(如0类簇)，计算起始、终止方向中位数作为该簇起始方向及终止方向，如果存在I2-I路段结点P到I方向与该簇起始方向差异最小，存在I到I-I3路段结点Q方向与终止方向差异最小，则交叉口I转弯规则即可映射到交叉口关联路段I2-I与I-I3之间的关系。考虑到弯曲道路对结果的影响，P、Q取路段中离交叉点I最近的路段结点。以P-I为前进方向，表示为向量a，I-Q表示为向量b，则转向规则可基于向量b与向量a的夹角θ进行判断。如果两向量叉积(a×b)的坐标Z>0，则向量b逆时针偏离向量a，表示从I2-I路段，转到I-I3路段的转角α=θ，如果Z < 0，则表示α=-θ。路段转弯规则与转角关系如下。
|
| 图 9 交叉口关联关系 Fig. 9 The association relationship for road intersection |
(1) 如果45°≤α≤135°，则路段转弯规则为左转。
(2) 如果-135°≤α≤-45°，则路段转弯规则为右转。
(3) 如果-45° < α < 45°，则路段转弯规则为直行。
(4) 如果135° < α≤180°/-180° < α≤-135°，则路段转弯规则为掉头。
3.2 路段单双向判断路网中路段的单双向信息也是导航属性的重要组成部分，可由交叉口识别的关联路段间转弯信息进一步推导获得。以图 9交叉口I为例，I2-I路段右转向I-I3路段，即存在轨迹由路段I2-I途径交叉口I至I-I3。进一步而言，如果存在路段途经交叉口I至I-I2，则路段I2-I为双向通行路段，否则为单向通行路段。
4 试验分析 4.1 研究区域与数据集本文试验数据包括汉口出租车轨迹数据、武汉大学出租车轨迹数据及芝加哥校园巴士轨迹数据(图 10)。文献[28]认为当采集周期超过7 d后，武汉市路段上出租车数据覆盖宽度逐渐趋于稳定，因此，武汉两个研究区域选取2014-05-29-06-04的1周内出租车轨迹数据进行试验。汉口区为武汉市中心城区，新旧建筑交错，道路间距不一；武汉大学研究区道路曲折多样，无一定几何形状，都对低频轨迹应用于道路信息提取的分析与挖掘有一定代表性。由于武汉大学数据集噪声较大，连续点间的时间间隔及空间间隔不一致，本文对武汉大学数据进行了如下预处理：①删除原始轨迹数中位置重复记录、航向为0、速度为0及速度超过100 km/h的轨迹点；②当相邻轨迹点时间间隔大于60 s、两轨迹点之间距离大于100(km/h)×60 s≈1.3 km或两轨迹点之间距离大于(v1+v2)×(t2-t1)/2时，对轨迹进行打断，删除轨迹点个数小于1的轨迹。芝加哥数据集为公共数据集，其采样频率(2~3 s)及定位精度较高，为验证本文方法处理低频轨迹效果，将其进行了30 s抽稀。表 2为预处理后轨迹数据情况。
|
| 图 10 研究区轨迹数据集 Fig. 10 The trajectory datasets of study area |
| 数据集 | 轨迹点数 | 采样频率/s | 平均采样频率/s | 定位误差/m | 面积/km2 |
| 汉口数据集 | 253 319 | 1~59 | 37.10 | >15 | 4.2×2.8 |
| 武汉大学数据集 | 202 877 | 1~59 | 37.59 | >15 | 2.8×3.43 |
| 芝加哥数据集 | 13 282 | 30~58 | 33.26 | 10~15 | 3.88×2.4 |
4.2 参数设置
多模特征交叉口提取与融合中参数主要涉及搜索半径h、像元大小C、高密度阈值k、转向点对距离限制阈值d、局部距离阈值D及交叉口融合半径R。为区分距离较近交叉口，综合考虑道路宽度及道路交叉口最小间距，搜索半径h一般设置为50 m。像元大小C可通过研究范围的宽度或高度中的较小值除以250来计算。局部距离阈值D基于密度-距离决策图一般设置为20 m，转向点对距离限制阈值d则基于转向点对距离统计直方图设定为最大频率对应距离。由于抽稀前芝加哥数据采样频率较高，不需要设置转向点对距离限制阈值。阈值k的设定较为困难，本文基于经验设定为平均密度的α倍。交叉口融合半径R，可基于交叉口最小间距设置为75 m。路段提取主要涉及路段重叠率阈值γ及范围限制阈值β。根据经验，γ一般设置为0.9。β可根据不同采样频率进行设置，对于高频数据，β值可相应减小为1/2。未匹配路段长度l保留可根据经验进行设置为50 m，不同数据集参数设置见表 3。
| 数据集 | 基于密度提交叉口 | 基于转向提交叉口 | 交叉口融合 | 路段提取 | ||||||||
| α | D | d | α | D | R | γ | β | l | ||||
| 汉口 | 1/10 | 20 | 200 | 1/4 | 20 | 75 | 0.9 | 3/4 | 50 | |||
| 武汉大学 | 1/10 | 20 | 300 | 1/2 | 20 | 75 | 0.9 | 3/4 | 50 | |||
| 芝加哥(抽稀后) | 1/5 | 20 | 200 | 1 | 20 | 75 | 0.9 | 3/4 | 50 | |||
| 芝加哥(抽稀前) | 1/10 | 20 | 1 | 20 | 75 | 0.9 | 1/2 | 50 | ||||
4.3 试验结果与精度评价
汉口区域、武汉大学区域及芝加哥区域识别交叉口及路段结果如图 11所示。汉口和武汉大学数据集为出租车轨迹数据，采样频率较低且包含大量噪声，在这种情况下，本文方法均取得了较好的道路提取效果，表明本文方法可有效规避低频及噪声对识别结果带来的不利影响。芝加哥数据在抽稀前后识别结果变化不大，进一步验证本文方法适用于低频轨迹数据。可以看出，本文方法不仅可以有效识别老城区等道路密集区域的路网(图 11(a))，而且适合于轨迹分布不均区域的道路提取(图 11(b))。
|
| 图 11 本文方法提取结果 Fig. 11 The extraction results of our method |
图 11(e)-图 11(i)进一步展示了本文方法和3个经典算法(Davies方法[11]、Ahmed方法[12]和Karagiorgou方法[21])在交叉口位置与道路中心线的局部提取效果。显然，本文方法所提取中心线的扭曲很小，且其拓扑连通性也得到了正确构建。通过与OpenStreetMap道路数据比较，本文方法所提取的交叉口位置精度更高，所提取中心线的几何形态偏差更小。
为进一步验证本文方法完备性与准确率，使用精确率(precision)、召回率(recall)和F1分数(F1-score)对本文方法、Davies方法、Ahmed方法和Karagiorgou方法提取结果进一步进行精度评定，见表 4。其中交叉口基于邻域半径r内匹配的交叉口个数进行精度评定，而路网则基于像元大小r进行栅格化后匹配的单元格数[19]进行精度评定。
| 数据集 | 提取方法 | 交叉口 | 道路网 | |||||
| 精确率 | 召回率 | F1分数 | 精确率 | 召回率 | F1分数 | |||
| 汉口数据集 | 本文方法 | 95.96 | 76.61 | 85.20 | 86.53 | 79.06 | 82.63 | |
| Karagiorgou | 44.00 | 62.60 | 51.68 | 63.10 | 65.36 | 64.21 | ||
| Ahmed | 46 | 18.70 | 26.59 | 72.18 | 57.34 | 63.91 | ||
| Davies | 60.49 | 39.84 | 48.04 | 77.64 | 59.59 | 67.43 | ||
| 武汉大学数据集 | 本文方法 | 76.09 | 55.56 | 64.22 | 76.42 | 61.30 | 68.03 | |
| Karagiorgou | 27.62 | 46.03 | 34.52 | 64.78 | 53.11 | 58.37 | ||
| Ahmed | 18.18 | 19.05 | 18.60 | 47.81 | 56.85 | 51.94 | ||
| Davies | 9.91 | 66.67 | 17.25 | 32.30 | 48.53 | 38.78 | ||
| 芝加哥数据集(抽稀后) | 本文方法 | 100 | 53.70 | 69.88 | 77.00 | 55.56 | 64.53 | |
| Karagiorgou | 37.27 | 75.93 | 50 | 69.40 | 57.73 | 63.03 | ||
| Ahmed | 43.14 | 40.74 | 41.90 | 73.17 | 77.27 | 75.17 | ||
| Davies | 40 | 44.44 | 42.11 | 67.37 | 36.94 | 47.72 | ||
| 芝加哥数据集(抽稀前) | 本文方法 | 86.84 | 61.11 | 71.74 | 81.71 | 61.90 | 70.44 | |
| Karagiorgou | 65.88 | 100 | 79.43 | 72.96 | 59.70 | 65.67 | ||
| Ahmed | 71.62 | 98.15 | 82.81 | 65.45 | 70.91 | 68.07 | ||
| Davies | 100 | 37.04 | 54.05 | 81.27 | 38.82 | 52.54 | ||
面对低频高噪的武汉出租车轨迹数据，本文所识别交叉口及道路网较之其他方法，具有更高的精确率与召回率。基于交叉口间最小距离将r设置为50 m时，汉口区域交叉口精确率超过90%，具有不规则路网的武汉大学区域也达到70%以上。考虑到本文基于交叉口对提取路段中心线，较高的交叉口识别精度有利于道路网的全面与精确识别，以汉口数据集为例，相应的道路网在精确率和召回率两个指标上分别达到86.53%和79.06%。对于芝加哥数据集，本文方法的交叉口召回率不如Ahmed和Karagiorgou，主要原因在于高置信交叉口判定除方向特征外，其他特征均与密度相关，导致在仅有少数几条轨迹通过的区域中，交叉口难以被有效识别。但是在该数据集上，本文方法取得了比其他方法更高的精确率，且所提取路网的视觉表现更接近实际情况。
本文方法充分利用道路多模特征的互补优势，在高置信交叉口基础上实施多阶段路段识别，可以较为全面与精确地从低频高噪且分布不均的出租车轨迹数据中识别出道路交叉口与道路网。针对3个数据集的试验表明，本文方法无论从视觉效果还是在定量评价上，均取得了比其他方法更优的提取结果，不仅可以有效识别方格式路网，而且适用于非规则路网的提取。由于加油站与停车场等POI的出入口与道路交叉口呈现出类似特征，本文方法有可能将其识别为伪交叉口。此外，对于轨迹非常稀疏的区域，本文方法将因其密度过小而发生交叉口漏提，进而导致路网识别效果下降。
针对本文方法在转向关系与单双向信息识别方面的有效性，选取试验区域内最为复杂的沿河大道与晴川街交叉口(图 12(a))开展试验，并与OpenStreetMap导航信息进行比对(图 12(b))。该交叉口关联路段的转向关系提取结果见表 5，路段单双向信息见表 6。在总共25个转向关系中，有19个被正确提取出来，而单双向信息被全部正确识别。错误转向关系主要发生在长度较短的路段上(图 12(a)中80、81号路段)。由于武汉出租轨迹数据的采样频率普遍较低，落在该路段与其一阶相邻路段的转向子轨迹非常少，使得转向关系的判定较为困难。
|
| 图 12 沿河大道与晴川街交叉口 Fig. 12 The road intersection of Yanhe avenue and Qingchuan street |
| 节点 | 起始路段 | 转向路段 | 转向判定 | 实际是否允许转向 | 是否正确提取 | 编号 |
| 0 | 0 | 0 | 禁止 | 禁止 | true | 1 |
| 0 | 0 | 80 | 禁止 | 允许 | false | 2 |
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
| 0 | 81 | 164 | 禁止 | 禁止 | true | 9 |
| 0 | 81 | 168 | 禁止 | 允许 | false | 10 |
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
| 0 | 80 | 164 | 禁止 | 允许 | false | 14 |
| 0 | 80 | 168 | 右转 | 禁止 | false | 15 |
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
| 0 | 164 | 168 | 左转 | 禁止 | false | 20 |
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
| 0 | 168 | 164 | 右转 | 允许 | true | 24 |
| 0 | 168 | 168 | 禁止 | 禁止 | true | 25 |
| 路段 | L0 | L80 | L81 | L164 | L168 |
| I0→Ii/Ii→I0(Ii为路段另一端点) | 存在/存在 | 存在/存在 | 不存在/存在 | 存在/不存在 | 存在/存在 |
| 单双向判定 | 双向 | 双向 | 单向 | 双向 | 双向 |
| 是否正确提取 | true | true | true | true | true |
5 结论
目前，关于城市路网提取的研究较多，但大多需要高质量轨迹数据的支持，难以适用低频率、低精度、时空异质的出租车轨迹数据。由于交叉口识别精确度不高及路段生成时缺乏有效的提前判别，大部分方法中交叉口周围路段扭曲严重，相邻路段区分困难，极大影响转向关系识别。为此，本文通过挖掘出租车轨迹关于道路网络的多模特征，采用“交叉口位置-路段几何-导航属性”的研究思路，分别提出了一种顾及多模特征的道路交叉口集成识别技术、一种基于Delaunay三角网的多阶段路段生成方法及一种路段到路段的转向关系识别模式，在交叉口信息的引导下，逐步生成路网的“骨架”与“血肉”，实现城市可导航路网的分而治之构建，大大降低了可导航路网构建的复杂度。
为了构建更为全面的可导航路网结构支撑精细导航需求，未来将在复杂交叉口精细构建和多类型导航属性挖掘两方面继续开展研究。
| [1] |
HE Hao, WANG Shuyang, WANG Shicheng, et al. A road extraction method for remote sensing image based on encoder-decoder network[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2): 16-25. |
| [2] |
李思宇, 向隆刚, 张彩丽, 等. 基于低频出租车轨迹的城市路网交叉口提取研究[J]. 地球信息科学学报, 2019, 21(12): 1845-1854. LI Siyu, XIANG Longgang, ZHANG Caili, et al. Extraction of urban road network intersections based on low-frequency taxi trajectory data[J]. Journal of Geo-Information Science, 2019, 21(12): 1845-1854. DOI:10.12082/dqxxkx.2019.190187 |
| [3] |
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, WA: Association for Computing Machinery, 2009: 3-12.
|
| [4] |
TANG Luliang, REN Chang, LIU Zhang, et al. A road map refinement method using Delaunay triangulation for big trace data[J]. ISPRS International Journal of Geo-Information, 2017, 6(2): 45. DOI:10.3390/ijgi6020045 |
| [5] |
刘纪平, 张用川, 徐胜华, 等. 一种顾及道路复杂度的增量路网构建方法[J]. 测绘学报, 2019, 48(4): 480-488. LIU Jiping, ZHANG Yongchuan, XU Shenghua, et al. An incremental construction method of road network considering road complexity[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 480-488. DOI:10.11947/j.AGCS.2019.20180419 |
| [6] |
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. DOI:10.1109/TITS.2010.2069097 |
| [7] |
EDELKAMP S, SCHRÖDL S. Route planning and map inference with global positioning traces[M]. Berlin: Springer, 2003: 128-151.
|
| [8] |
LI Hengfeng, KULIK L, RAMAMOHANARAO K. Automatic generation and validation of road maps from GPS trajectory data sets[C]//Proceedings of the 25th ACM International Conference on Information and Knowledge Management. Indianapolis: ACM, 2016: 1523-1532.
|
| [9] |
QIU Jia, WANG Ruisheng. Automatic extraction of road networks from GPS traces[J]. Photogrammetric Engineering & Remote Sensing, 2016, 82(8): 593-604. |
| [10] |
廖律超, 蒋新华, 邹复民, 等. 浮动车轨迹数据聚类的有向密度方法[J]. 地球信息科学学报, 2015, 17(10): 1152-1161. LIAO Lüchao, JIANG Xinhua, ZOU Fumin, et al. A fast method of FCD trajectory data clustering based on the directed density[J]. Journal of Geo-Information Science, 2015, 17(10): 1152-1161. |
| [11] |
DAVIES J J, BERESFORD A R, HOPPER A. Scalable, distributed, real-time map generation[J]. IEEE Pervasive Computing, 2006, 5(4): 47-54. DOI:10.1109/MPRV.2006.83 |
| [12] |
AHMED M, FASY B T, GIBSON M, et al. Choosing thresholds for density-based map construction algorithms[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, WA: Association for Computing Machinery, 2015: 1-10.
|
| [13] |
ZHENG Renjie, LIU Qin, RAO Weixiong, et al. Topic model-based road network inference from massive trajectories[C]//Proceedings of the 18th IEEE International Conference on Mobile Data Management (MDM). Daejeon, Korea (South): IEEE, 2017: 246-255.
|
| [14] |
ZHANG Caili, XIANG Longgang, LI Siyu, et al. An intersection-first approach for road network generation from crowd-sourced vehicle trajectories[J]. ISPRS International Journal of Geo-Information, 2019, 8(11): 473. DOI:10.3390/ijgi8110473 |
| [15] |
ZOURLIDOU S, SESTER M. Intersection detection based on qualitative spatial reasoning on stopping point clusters[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2016, XLI-B2: 269-276. DOI:10.5194/isprs-archives-XLI-B2-269-2016 |
| [16] |
WANG Jing, WANG Chaoliang, SONG Xianfeng, et al. Automatic intersection and traffic rule detection by mining motor-vehicle GPS trajectories[J]. Computers, Environment and Urban Systems, 2017, 64: 19-29. DOI:10.1016/j.compenvurbsys.2016.12.006 |
| [17] |
HUANG Jincai, DENG Min, ZHANG Yunfei, et al. Complex road intersection modelling based on low-frequency GPS track data[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2017, XLII-2/W7: 23-28. DOI:10.5194/isprs-archives-XLII-2-W7-23-2017 |
| [18] |
FATHI A, KRUMM J. Detecting road intersections from GPS traces[C]//Proceedings of the 6th International Conference on Geographic Information Science. Berlin: Springer, 2010: 56-69.
|
| [19] |
MARIESCU-ISTODOR R, FRÄNTI P. CellNet: inferring road networks from GPS trajectories[J]. ACM Transactions on Spatial Algorithms and Systems, 2018, 4(3): 8. |
| [20] |
王德浩. 基于低频出租车GPS轨迹数据的路网信息提取[D]. 武汉: 武汉大学, 2017. WANG Dehao. Generation of road network information from massive less frequent GPS vehicle trajectories[D]. Wuhan: Wuhan University, 2017. |
| [21] |
KARAGIORGOU S, PFOSER D. On vehicle tracking data-based road network generation[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, CA: Association for Computing Machinery, 2012: 89-98.
|
| [22] |
YANG Xue, TANG Luliang, NIU Le, et al. Generating lane-based intersection maps from crowdsourcing big trace data[J]. Transportation Research Part C: Emerging Technologies, 2018, 89: 168-187. DOI:10.1016/j.trc.2018.02.007 |
| [23] |
庄立坚, 何兆成, 杨文臣, 等. 基于大规模浮动车数据的交叉口转向规则自动提取算法[J]. 武汉理工大学学报(交通科学与工程版), 2013, 37(5): 1084-1088. ZHUANG Lijian, HE Zhaocheng, YANG Wenchen, et al. A large-scale floating car data-based algorithm of turning rule extraction at intersections[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2013, 37(5): 1084-1088. DOI:10.3963/j.issn.2095-3844.2013.05.042 |
| [24] |
唐炉亮, 于智伟, 任畅, 等. 基于车载GPS轨迹的立体交叉口空间结构信息获取方法[J]. 交通运输工程学报, 2019, 19(5): 170-179. TANG Luliang, YU Zhiwei, REN Chang, et al. Information acquisition method of three-dimensional intersection spatial structure based on vehicle GPS trajectory[J]. Journal of Traffic and Transportation Engineering, 2019, 19(5): 170-179. DOI:10.3969/j.issn.1671-1637.2019.05.018 |
| [25] |
RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496. DOI:10.1126/science.1242072 |
| [26] |
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. |
| [27] |
ZHAO Lisheng, MAO Jiali, PU Min, et al. Automatic calibration of road intersection topology using trajectories[C]//Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE). Dallas, TX: IEEE, 2020: 1633-1644.
|
| [28] |
唐炉亮, 杨雪, 阚子涵, 等. 一种基于朴素贝叶斯分类的车道数量探测[J]. 中国公路学报, 2016, 29(3): 116-123. TANG Luliang, YANG Xue, KAN Zihan, et al. Traffic lane numbers detection based on the naive Bayesian classification[J]. China Journal of Highway and Transport, 2016, 29(3): 116-123. DOI:10.3969/j.issn.1001-7372.2016.03.015 |