EN中文

Journal of Geo-information Science >

2023 , Vol. 25 >Issue 10: 1954 - 1967

DOI: https://doi.org/10.12082/dqxxkx.2023.230070

Turning Information Enhancement of OpenStreetMap Road Network Based on Crowdsourcing Trajectory Data

  • CHEN Xin ,
  • XIANG Longgang , * ,
  • JIAO Fengwei
Expand
  • State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China
* XIANG Longgang, E-mail:

Received date: 2023-02-16

  Revised date: 2023-05-16

  Online published: 2023-09-22

Supported by

National Natural Science Foundation of China(41771474)

National Natural Science Foundation of China(42071432)

Fold

Abstract

OpenStreetMap (OSM) road network is an open-source dataset that is dedicated to providing people with a globe-free digital map resource, and it has been widely used in spatial analysis and applications such as route planning and vehicle navigation services. Meanwhile, in order to regulate traffic order and reduce heavy traffic congestion, the constraints of turning rules are generally implemented at intersections in urban areas. These constraints should be respected in the applications based on OSM road network. However, OSM road network lacks turning relationships at intersections, preventing its services from route planning and vehicle navigation. For this reason, to endow OSM road network structure with turning relationships, this study presents an intersection turning detection method based on map matching and string mapping, which takes advantage of crowdsourcing GNSS trajectory data in terms of its dynamic connection information at traffic intersections. Firstly, a structure detection method for OSM intersections is designed based on a top-down quadtree splitting idea, then the intersections with different sizes and complex and various shapes are reduced to the connection points. On this basis, the improved Hidden Markov Model (HMM) map matching algorithm is introduced to project low-frequency and high-noise trajectories onto OSM road segments. This algorithm considers the direction consistency between roads and trajectories, as well as the effective drift distance between two adjacent trajectory points, can identify trajectory sequences with semantic anomalies during the driving process. Secondly, to simplify turning relationship detection, a character encoding technology facing the intersection-related road segments is presented to map the trajectories crossing through intersections to the directional strings in turning process. The information enhancement method regarding the empty characters based on optimal path analysis is further designed to enhance turning trajectory support for short road segments. This approach helps restore the driving route information for low-frequency trajectories. Finally, the different turn modes of trajectories at the target intersection are mined by directly targeting the trajectory directional strings based on a string matching method, thus this study realizes turning information enhancement for OSM intersections referencing to the "consensus knowledge" of crowdsourcing trajectories. The complicated turning relationship identification for OSM intersections is transformed into the simple string matching. The experiment based on crowdsourcing trajectory data in Shanghai shows that the proposed method can detect turning relationships for OSM intersections with a precision rate of 90%, a recall rate of over 98%, and an F1-score of over 94%.

Key words： turning relationships; map matching; crowdsourcing trajectory; string mapping; string matching; OSM road network; intersection's turning information enhancement; path analysis

Cite this article

CHEN Xin , XIANG Longgang , JIAO Fengwei . Turning Information Enhancement of OpenStreetMap Road Network Based on Crowdsourcing Trajectory Data[J]. Journal of Geo-information Science, 2023 , 25(10) : 1954 -1967 . DOI: 10.12082/dqxxkx.2023.230070

1 引言

OpenStreetMap（OSM）是一个自发式地理信息项目，于2004年由英国工程师史蒂夫斯科特创建，发展至今拥有庞大的用户群，构建出一个全球性、广泛应用的数据集[1]。与传统制图数据相比，OSM路网数据具有更新快、开放性和范围广等优点，近年来受到了各个领域研究人员的关注，不仅应用于城市活力分析[2]、居民出行可达性分析[3]和区域交通状况分析[4]等，还为基于web端的全球性开源路径计算服务OpenRouteService[5]、智能交通管理和建设[6]等空间应用提供支撑。
在道路矢量地图中，路网的拓扑结构可以利用节点和边的连接关系直观地表达路段间的连通性，而城市区域内路口具有转向规则约束，使得拓扑连通的路段在现实交通中是不可达的[7-8],如禁止左转。因此，有学者在最优路径分析[9]和构建道路交通网络模型[10]的研究中引入路口的转向关系，对提高计算最优路径的真实性和交通出行的效率有重要的现实意义。尽管OSM路网具有转向关系标签描述路口转向，但其路口转向信息和路网规模相比存在大量缺失[11-12]，制约其进一步服务于车辆导航和路径规划。
目前，学者们对路口的转向探测开展了大量的研究工作，按所使用的数据源不同，这类研究主要分为基于视觉图像如地图街景、航拍影像识别静态的转向标志和利用浮动车轨迹数据提取动态的交通转向信息。地图街景和航拍影像通过检测与识别交通标志牌来获取转向信息[13⇓-15]。然而街景更新周期长、成本高和覆盖范围不全面，航拍影像易被树木遮盖，且因天气和光照影响产生同物异谱、同谱异物的现象，给路口转向探测带来困难。随着卫星定位技术的发展和位置感知设备的普及，用户在使用设备时将生成大量具有丰富动态信息的众源GNSS（Global Navigation Satellite System, GNSS）轨迹数据。和从专业测量车采集的高精度高频率轨迹相比[16]，众源轨迹数据路网覆盖度高、采集成本低和现势性强，成为路口的结构提取和转向关系识别研究[11⇓⇓⇓⇓⇓-17]的重要数据源。基于众源轨迹数据提取路口转向规则的研究方法主要分为聚类法和地图匹配法。Wang等[18]基于与转向起终点有关的方向角特征对转向轨迹聚类，获得的每一个聚类簇代表路口的一种转向关系；唐炉亮等 [19]利用随机森林对多种轨迹特征进行重要性评估后，选择转向轨迹的起终点角度特征进行组合聚类，并采用戴维森堡丁指数（Davies-Bouldin Index，DBI）评估聚类结果以识别出路口的转向数目。但是，聚类法所使用的聚类特征均与轨迹点的方向角有关，难以区分方向相近的转向，且聚类结果的准确性依赖于聚类参数的设定，面向大小不一、结构复杂迥异的路口转向探测缺乏适应性。为此，有学者采用轨迹地图匹配方法，将轨迹的动态连接信息映射至路段，直接在基础路网的路口结构之上识别对应的转向规则。Efentakis等[11]基于Fréchet距离曲线匹配法和ST匹配法[20-21]，依据转向的轨迹支持度占从特定路段驶入路口的转向总数的比例识别禁止转向规则；黄敏等[8]基于置信点的地图匹配法[22]，结合转向类型和转向次数以支持向量机的分类方法获取路口的转向关系。但是，现有的地图匹配法忽略了由点漂移引起的轨迹行为语义异常的情况（如逆行）和轨迹低频采样带来的连续点的匹配路段的空间不邻接问题，需过滤低频低质量的轨迹数据或依赖大量训练样本才能实现不同情况的路口转向探测。考虑到大部分众源GNSS轨迹数据具有低频高噪的特点，且城市路口大小各异，结构复杂多样，现有的转向关系信息采集方法适应性不强。
针对OSM路网的路口转向关系缺失问题，本文充分利用众源GNSS轨迹数据的动态连接信息，提出一种基于地图匹配和字符串映射的路口转向探测方法，为OSM路网赋予转向关系。本文主要的贡献点如下：
（1）提出一种基于地图匹配和字符串映射的路口转向探测方法，将复杂的路口转向关系识别转化为简单的字符串匹配问题。基于上海市10 km×10 km区域选取结构多样、大小不一的路口进行试验，其精确率、召回率、F1值分别达到90.29%、98.53%、94.23%，验证了本文方法的可行性。
（2）针对由轨迹漂移引起的匹配中断或匹配错误，引入并改进HMM地图匹配方法，基于轨迹点的有效漂移距离识别逆行轨迹片段，将低质量的众源轨迹投影到OSM路段上。
（3）针对众源轨迹低频和采样不均的特点，引入最优路径分析思想，设计了空字符的信息增强处理方法，以提高转向轨迹支持度，从而准确识别发生在短路段上的转向关系。

2 路口转向识别方法

本文提出的路口转向识别方法技术路线见 图1所示。① 进行数据预处理，对轨迹实施去噪和清洗；② 从OSM路网中识别路口结构并将其简化为一个连接点，使结构迥异的路口结构得以被统一表达；③ 引入并改进基于隐马尔科夫模型（Hidden Markov Model, HMM）的地图匹配算法，将众源GNSS轨迹匹配至OSM路网上；④ 引入局部路段字符编码方法，将轨迹序列映射为字符串；⑤ 进一步考虑到轨迹低频及采样不均的问题，提出基于最优路径分析的空字符信息增强方法，提高短路段上的转向轨迹支持度；⑥ 使用一种快速高效的字符串匹配法，直接在字符串之上实现路口转向关系的识别。
图1 OSM路口转向识别框架

Fig. 1 The workflow of identifying turning relationships at OSM intersections

2.1 数据预处理

2.1.1 轨迹数据预处理

定义1（轨迹）：T= p 1 , … , p i , … , p n ( 0 < i < n )， p i是第i个点。 p i= { x i , y i , t i , v i , a i }， x i , y i为地理坐标系下 p i的经纬度， t i、 v i、 a i分别为 p i的时间戳、瞬时速度、方向角，2个连续点的采样频率为 Δ t，采样距离为 Δ d。
由于设备故障和信号误差，轨迹数据存在噪声与错误，如采样异常和位置漂移等；同时，移动对象因为休息、拥堵等静止或缓慢移动，在小范围内留下大量采样点；此外，众源GNSS轨迹基于用户于多种交通模式下采集，还可能由非机动车产生，如骑行时设备开启定位应用，其轨迹可能在道路上逆向行驶。上述因素带来的轨迹片段不利于路口转向识别，为过滤这类轨迹片段，本文引入4步预处理步骤：
（1）冗余数据剔除。对于轨迹中时间戳、位置的采样重复的点集，保留重复采样的第一个点，删除冗余数据。
（2）轨迹分段。由设备故障引起数据缺失，或由于信号中断无法获取位置信息，使得轨迹相邻点在时空维度上相距较远，呈现非连续行驶状态，而本文关注轨迹连续行驶时的转向行为。为此，设置采样频率 t和采样距离 d， ∃ Δ t > t或 Δ d > d，将轨迹分段。
（3）停留检测。针对轨迹在小区域内留下大量的采样点，本文基于核密度分析，采用文献[23]的方法检测停留片段，停留片段由其几何中心点简化表达。
（4）非机动车轨迹识别。考虑到非机动车的最大速度有限，如《电动自行车安全技术规范》(GB17761-2018)[24]中规定：电动自行车车速不得超过25 km/h，该速度未能达到机动车自由交通流速度。为此，本文检查轨迹在其生命周期内的最大速度，若高于某一阈值，轨迹予以保留，否则视为非机动车轨迹并做删除。

2.1.2 OSM路口识别及简化处理

本文首先从OSM路网中提取路口信息，进而通过地图匹配探测车辆轨迹在路口的转向行为。考虑到路口结构复杂多样，且OSM本身为众源地图，由不同志愿者绘制而来，导致OSM在路口结构表达上有多种不同的表达方法，另一方面本文仅关注在路口范围内，直接连接该路口的所有路段之间的转向关系，路口的内部表达结构并不需要予以关注，为此，本文提取OSM路口结构并将其简化为一个连接点，以便基于轨迹的地图匹配和路口转向探测。
在矢量道路地图中，称地面上3条及以上路段的公共节点为交叉点，而路口处多个路段相交会产生多个交叉点。为此，本文识别路口的交叉点并将其整合为一个连接点，实现路口结构的简化处理。首先，考虑到OSM路网中路段相交但可能无公共节点，将同层路段在交点处打断以获取所有的交叉点；然后，本文利用一种自上而下的空间四叉树分裂思想[25]，将路网范围逐级分裂至最小单元；最后，将空间四邻域最小单元内的交叉点划分至同路口。为有效区分相近路口的交叉点，参考道路宽度和路口最小间距[26]，单元的边长小于50 m时停止分裂。图2示意了一个路口结构的简化过程：3次分裂后（由图2（a）至图2（b）），十字路口的连接点（图2（d））由4个绿色交叉点（图2（c））的坐标平均值计算得来，近似表征路口位置。本文从OSM路网中识别路口结构，并将其统一表达为一个连接点，使得路口的路段基于连接点实现相互连通，从而简化轨迹地图匹配，以及基于匹配结果的路口转向关系识别。
图2 路口结构简化处理流程

Fig. 2 Simplification of road intersection structures

2.2 轨迹-地图匹配

本文引入地图匹配算法将轨迹点匹配至路段，使得偏离的轨迹数据与路网结合并具有空间上的行驶路线信息，进而利用轨迹的行驶路线信息实现路口转向探测。HMM是一种概率统计模型，由初始概率分布、转移概率分布和发射概率分布确定[27]，在路径推断中对点定位误差、行驶上下文距离和行驶方向等因素集成性较好[28-29]。基于HMM的地图匹配方法充分考虑了轨迹和路段的相关性、相邻轨迹点的连续性等特征，能有效提高低频高噪的众源轨迹的匹配精度。为此，本文采用HMM地图匹配方法计算轨迹的行车路线。
定义2（轨迹匹配序列）：Tr={ C 1 , … , C i , … , C n}， i ∈ [ 1 , n ]， C i为 p i垂直投影至路段 e i的匹配点， C i= { X i , Y i , e i }， X i , Y i为 C i的地理坐标。
部分轨迹在连续时空状态下发生交通模式转变，如用户由骑行转为乘坐汽车，可能在道路上逆行；此外，受高楼、树木及高架遮盖等影响，点定位形成多径效应[30]，轨迹点可能漂移至其前一点的后方，造成伪逆行。这2种逆行均难以在预处理中被检测，易导致地图匹配出错。为此，本文引入轨迹-路段方向一致性约束检测逆行，进而使用有效漂移距离 d v识别伪逆行轨迹片段，最后借助于一个惩罚因子 p f计算伪逆行的真实路线。
在OSM路网中，低等级道路通常由一条双向路段表示，因此，本文使用2条方向相反的单向路表征一条双向路，以构建有向路网结构。当相邻点匹配至同一单向路段上，排除掉头，当前点在路段上行驶的距离应大于前一点，否则为逆行。以分析 图3（a）中 T 1轨迹的行驶为例， λ i< λ i - 1，即 d i < 0， p i逆行；进一步判断若 d i < d v，表示点在有效漂移距离 d v内，属于伪逆行。为不影响双向或平行路段上非伪逆行点的匹配，在计算伪逆行点的转移概率 P s i | s i - 1 r时引入惩罚因子 p f（式（3））。
图3 改进后的地图匹配过程示意图

Fig. 3 Improved map matching process

d i = λ i - λ i - 1 ( i ∈ [ 1 , n ]）
P s i | s i - 1 ~ γ e x p { γ ( p i - p i - 1 - | d i | ) }
P s i | s i - 1 r = p f · P s i | s i - 1 ( p f ∈ ( 0,1 ) )
式中： λ i和 λ i - 1分别为 p i和 p i - 1在同一匹配路段上行驶的距离； d i表示两点行驶距离差； P s i | s i - 1为 p i - 1至 p i的转移概率； p i - p i - 1表示两点的欧式距离，其中需参考轨迹采样序列的观测位置确定最佳参数 γ[28]， γ越小表示转移概率受两点行驶距离和欧式距离的差异影响越小；式（3）中，惩罚因子 p f值越小，惩罚力度越大。
以图3（a） T 2中 p 4伪逆行为例，基于传统匹配算法， p 3到 p 4需完成2个掉头后才能从 C 3行驶至红色匹配点 C 4，而本文识别出 p 4伪逆行后，将匹配点 C 4投射至 C 3位置，使其匹配合理。图3（b）和图3（c）示意了2条局部伪逆行轨迹，其匹配结果准确还原了轨迹的行车路线。

2.3 基于方向字符的路口转向关系识别

在OSM路网中，一条道路实体可能被标绘成多个路段对象，使得一个转向关系涉及到多个路段，导致城市路口转向分析需要关注转向路段之间的复杂组合关系。此外，有研究表明，在低速或静止状态下点定位结果在一定区域内移动，误差较大[30]，而在路口附近，车辆趋于减速或静止、道路密集且相距较近，导致车辆轨迹的地图匹配存在不确定性。上述现象将给直接基于轨迹匹配序列的路口转向识别带来严峻挑战。为有效从中探测交通路口的转向关系，本文首先基于目标路口的路段字符编码，将轨迹映射为具有方向语义信息的字符串；接着考虑到轨迹低频及采样不均会导致一些短路段上的采样点较少，实施空字符信息增强处理以提高短路段的转向轨迹支持度；最后，基于简单的字符串匹配法，依托海量的众源GNSS轨迹识别路口转向，为OSM路网赋予转向关系。

2.3.1 路段字符编码及轨迹字符映射

本文基于路口路段的方向字符编码及其映射规则，将轨迹映射为具有方向语义信息的字符串，从而可以在字符串之上实现基于字符匹配的转向关系探测。以图4（a）中十字路口的路段编码为方向字符为例，首先，参考路口范围[26]基于路口连接点生成50 m的缓冲区与路段产生交点，设交点与原点连线的方向为 θ i ( i ∈ [ 1,8 ] )；然后，在目标路口与其邻近路口之间，沿交点所在路段的方向扩展同向路段集合；最后，按照 θ i的大小顺时针将路段集合编码为字符 l j。图4（b）中，使用 l 2编码的路段有{ e 5 , e 6 ,}。
图4 路段字符编码与轨迹字符串映射

Fig. 4 Road character encoding and trajectory-string mapping

依据路段字符编码将轨迹映射为字符串后，鉴于路口范围内的轨迹点匹配存在不确定性，本文分析转向时避开这类轨迹点，并将其映射为“ ?”以便快速索引轨迹驶入路口前、后的轨迹点；此外，轨迹点行驶至与目标路口无关的路段上无法被映射为方向字符，则映射为空字符“E”。根据映射规则，图4（b）轨迹 T映射为“ l 4 ? l 3 l 3 E E E l 2 l 2 ? l 1”。
目标路口的路段编码为方向字符后，转向关系可由一对方向字符表达。表1记录了一个十字路口的转向关系，( l r , l t)表示一组从 l r转到 l t的转向，转向频率为转向轨迹的数量，转向属性为1时转向关系被识别出。
表1 路口的转向关系

Tab.1 Turning relationships at intersections

路口 路段字符表示 转向频率 转向属性
I N l 1 , l 2 , l 3 , l 4 , l 5, l 6 , l 7 , l 8 ( l 1 , l 2):0|…|( l 6 , l 7):88|… ( l 1 , l 2)=0|…|( l 6 , l 7)=1|…

注：( l 1 , l 2)表示路口 I N中从路段 l 1方向驶入路段 l 2方向的一组转向关系。

2.3.2 空字符信息增强处理

轨迹映射为方向字符串后可以显现其在路口的转向过程，具体包括驶入路口、位于路口和驶离路口，如字符串中“ l r ? l t”表示轨迹在目标路口从 l r转至 l t。然而，轨迹由于低频或采样不均，在一些短的路段上没有留下采样点，使得转向对应的方向字符缺失，如“ l r ? E”缺少驶离路口的方向，导致分析发生在这类路段上的转向关系存在一定困难。为此，本文采用最优路径分析对空字符做信息增强处理，以提升短路段的转向轨迹支持度。
两点间最优路径的选择通常需考虑路段等级、长度和弯曲度等多种因素，显然，排除路段封闭等特殊情况，相邻两路口的最优路径通常为连接二者的公共路段。为此，本文假设轨迹中连续两点驶过2个相邻路口，则也应经过相邻路口的公共路段，以此获取轨迹于“?”与“E”字符之间隐藏的行驶路段信息。以分析图5中 I N 1的转向为例， T 1和 T 2分别映射为字符串“EEE l 1 l 1? l 2 l 2”和“ l 4 l 4?EE”， T 1转向过程完整，而 T 2缺少驶离路口的方向字符。因此，进一步对 T 2做空字符信息增强，分析出 T 2经过 l 2， T 2最终映射的字符串为“ l 4 l 4? l 2 E E”。其中，空字符信息增强算法的时间复杂度和空间复杂度均为O(n)。
图5 2种轨迹行驶示意

Fig. 5 Two kinds of track driving diagram

综上，以图5中 T 2字符串缺少驶离路口的方向字符为例，空字符信息增强伪代码如算法1所示。
算法1 空字符信息增强算法
输入: T 2: 原始轨迹; I N 1: 路口;
输出: T s t r n e w: 信息增强后的字符串;
1 //轨迹地图匹配，输出匹配序列 T r
2 T r ← M a p M a t c h ( T 2 ) ;
3 //轨迹字符映射，输出字符串 T s t r
4 T s t r ← S t r i n g M a p ( T r ) ;
5 //该字符串属于缺少驶离路口字符的类型
6 if T s t r contains “?” and “?” 右侧相邻为 “E” then
7 推测 T r 路口 I N 1驶向路口 I N 2;
8 if T s t r连续经过的2个路口 I N 1和 I N 2 相邻 then
9 //将方向字符 l j 插入 “?” 和 “E” 之间，输出 T s t r n e w
10 T s t r n e w ← I s e r t S t r ( l j , T s t r ) ;
11 end if
12 end if

2.3.3 基于字符串匹配的转向关系识别

识别轨迹转向行为的本质在于探测其通过路口前和后的方向路段信息。为此，本文基于一种简单高效的字符串匹配法探测轨迹的转向。见图6，字符串匹配可分为3步：定位、匹配、输出。定位，遍历字符串根据“?”索引轨迹位于路口内的位置；匹配，基于“?”匹配左右邻近的方向字符对；输出，根据匹配结果输出一对方向字符，即为轨迹在目标路口发生的转向类型。
图6 基于字符串匹配的转向关系识别流程

Fig. 6 The flowchart of identifying turning relationships based on string matching

在现实中车辆可能行驶错误，路口有转向轨迹不能作为识别此转向关系的充分条件。为此，参考“共识知识”理念，本文依托海量的众源GNSS轨迹数据，依据转向发生的频繁程度，选取合适的经验值SUP来识别路口转向关系。考虑到轨迹在不同区域的分布具有空间异质性，难以确定SUP值，本文基于大范围OSM路网和海量的轨迹数据进行多次实验探索SUP的取值。由SUP值识别转向具体公式见下：
( l r , l t ) = 0 N u m < S U P 1 N u m ≥ S U P ( r , t ∈ ( 0 , g ) )
式中： N u m为转向轨迹支持度；g为路口处方向路段的数量，若 N u m ≥ S U P，则转向关系（ l r , l t）被识别出。

3 试验与结果分析

3.1 试验数据及精度评估方法

实验区域选取上海市黄浦区、虹口区附近 10 km×10 km区域，该区域的OSM路网数据（https://www.openstreetmap.org/）包含8 098条路段、2 159个路口。众源GNSS轨迹数据由用户开启定位应用时进行采集，出租车、网约车众源轨迹数据的采集人群局限于司机群体，而一般性手机众源轨迹由手机用户采集，其设备数量规模更大、泛在性更强、路网覆盖度更高。为此，本文选择经过匿名化等隐私处理后的一般性手机众源轨迹数据作为试验数据。本文选取试验区域内于2019年8月1日—31日一个月采集的共计约70万条轨迹、850万个轨迹采样点，其行驶总长度超100万km，每一个采样点包括编号id、时间戳、定位精度、地理坐标、方向角、速度等属性信息（图7），轨迹数据预处理后作为机动车数据源（图8）。图9（a）和图9（b）分别展示了预处理后轨迹数据的定位精度及采样频率分布，其中，定位精度大于50 m占比约10%，采样频率大于50 s占比约15%。
图7 原始轨迹数据属性信息

Fig. 7 Attribute information of raw trajectory data

图8 试验区域的OSM路网及GNSS轨迹数据集示意

Fig. 8 OSM road network and GNSS trajectories in the test area

图9 轨迹数据定位精度和采样频率统计结果

Fig. 9 Statistics of trajectory positioning accuracy and sampling frequency

考虑到不同道路等级的路段轨迹覆盖度有差异，为分析轨迹覆盖度对提取路口转向信息的影响，本文将OSM多个道路等级分为高、低两个等级，高等级包括“Motorway（高速公路）、Trunk（重要道路）、Primary（主干道）、Secondary（二级公路）、Tertiary（三级公路）”；考虑到机动车可在“Residential（住宅区道路）”的路段上行驶，因此低等级包括“Unknown（规模更小的本地道路）、Residential (可人行的道路) ”等其他级别道路。
本文随机抽样465个路口，共包括5 308组待检测的转向关系。结合实际交通进行人工标注检查，其中4 637组转向允许通行、671组转向禁止通行，分别标记为正、负样本。本文采用精确率（Precision）、召回率（Recall）、F1值（F1-score）3种指标评估方法的有效性（式（5）—式（7）)，TP、FN分别为正样本识别成正样本和负样本的数量，FP为负样本识别成正样本的数量。F1值介于0和1之间，值越大表明精确度和召回率指标越好。
P r e c i s i o n = T P / ( T P + F P )
R e c a l l = T P / ( T P + F N )
F 1 - s c o r e = 2 × P r e c i s i o n × R e c a l l / ( P r e c i s i o n + R e c a l l )
考虑到伪逆行点的前进方向与实际位置移动方向具有矛盾性，表现在伪逆行点相对其前后两点有折返移动现象，本文利用3个变化方向角 a n g l e 1、 a n g l e 2、 a n g l e 3（式（8）—式（10)）分析伪逆行识别结果。假设轨迹中 p i伪逆行， a n g l e 1和 a n g l e 2分别表示 p i和 p i + 1前进方向的变化， a n g l e 3为 p i与其前后轨迹点的相对位移所发生的方向变化。
a n g l e 1 = a r c c o s a i - a i - 1 · 180 π ( i ∈ [ 0 , N ) )
a n g l e 2 = a r c c o s a i + 1 - a i · 180 π ( i ∈ [ 0 , N ) )
a n g l e 3 = a r c c o s → p i - 1 p i , → p i p i + 1 · 180 π ( i ∈ [ 0 , N ) )
式中：N为一条轨迹的点数量，当 a n g l e 1、 a n g l e 2的值接近0°时，表示 p i - 1、 p i、 p i + 1的方向趋于一致，即当 a n g l e 3的值接近180°时，表示 p i相对于其前后两点位移有折返现象。

3.2 转向识别结果与分析

3.2.1 转向识别结果评估

针对本文的试验数据，轨迹预处理停留半径和持续时间分别设为30 m、60 s，最大采样频率和采样距离分别设为120 s、1.5 km；考虑到非机动车的速度通常低于25 km/h，小于机动车自由交通流速度，因此保留机动车的速度阈值设25 km/h。然后，基于Yang所实现的HMM地图匹配框架[29]进行改进，根据经验将 d v 、 p f 、 γ分别设为25 m、0.1、0.8。为进一步验证本文方法的有效性，采用Efentakis[11]的方法作为基准方法和本文方法进行比较，结果见 表2。Efentakis方法中常规经验值取为5%，表示转向的轨迹支持度占从特定路段驶入路口的转向总数的比例小于经验值时，该转向被识别为禁止通行，因此本文假设转向比例大于经验值则该转向被识别为允许通行。而本文方法中SUP值初始设为10，相较于Efentakis方法，本文方法精确率、查全率和F1值分别提升0.68%、22.36%和12.21%，可见本文方法能全面而有效地探测路口转向关系。
表2 不同方法的实验结果对比

Tab. 2 Comparison of experimental results of different methods (%)

方法 Precision Recall F1-score
Efentakis 89.75 73.86 81.03
本文方法 90.43 96.22 93.24
图10（a）和图10（b）分别对转向识别结果的完整度和精确率逐个路口进行可视化，可见绝大部分路口的转向关系被完整识别，且精确率较高。图11给出了几个典型路口的转向关系识别结果，图11（a）中T型路口共有9组转向关系；图11（b）中常见的十字型路口有16组转向关系；图11（c）中复杂多方向的路口共有20组转向关系。这类路口流量大、转向信息丰富，其转向关系能被完整、准确地探测到。图11（d）为小流量的单向小路汇入弯曲主路的路口，该处受路段方向和交通规则约束仅有3组转向关系，也能被准确识别出。
图10 试验区域内路口转向识别结果

Fig. 10 Visualization of identified turning relationships in the test area

图11 路口转向识别示例

Fig. 11 Examples of identified turning relationships at intersection

除了人为标注转向真值的误差，转向识别错误较多的路口在不同等级路段上均有分布（图10（b）），由于非机动车轨迹未能完全被过滤，对转向识别造成干扰。此外，路口的平行同向路段也会造成转向识别错误，如图11（e）中被识别出的4组转向，其中转向1、2分别从平行方向 l 4、 l 1驶向 l 3方向，转向1存在而转向2不存在。经观察，此地受高架影响，轨迹点定位误差较大，地图匹配易混淆行驶于平行且同向路段上的轨迹，造成转向2和4被误识别。
图10（a）展示了各路口转向识别的完整度，转向漏识别较多的路口多分布于低等级道路上，这类路段极少或没有轨迹经过，由于支持度不够，难以推测路口的转向信息。另外，较高等级路段上的路口的掉头转向容易被漏识别，由于部分路段上存在非路口位置的掉头转向点，使得路口处的掉头转向频率较低（图11（f））。
本文随机选择10个路口分析不同转向类型（左转、右转、直行和掉头）的实验结果，其评价指标见表3。直行的精确率和召回率最高，左转和右转次之，掉头最低。在一个允许任意转向的路口中，直行的车流量和其他转向流量相比通常最高，直行的转向关系更容易被识别，而掉头流量最低，识别有一定困难。左转和右转交通流量变化较大，部分路口的转向支持度较低，且受定位点在平行邻近路段上的匹配错误的影响，精确率和召回率有所下降。
表3 不同转向的实验结果对比

Tab. 3 Comparison of experimental results of different turning relationship classes (%)

转向 Precision Recall F1-score
左转 94.12 91.43 92.76
右转 89.74 92.10 90.90
直行 100.00 100.00 100.00
掉头 80.00 77.41 75.73

3.2.2 轨迹伪逆行评估

为评估轨迹点的伪逆行，本文依据地图匹配结果选取2 500条伪逆行轨迹。图12示意了3个变化方向角 a n g l e 1、 a n g l e 2、 a n g l e 3的分布情况。 a n g l e 1和 a n g l e 2集中分布于接近0°的区域，表明多数伪逆行点和其前后两点的方向趋于一致；而 a n g l e 3多分布于数值较大的区域，表示多数伪逆行点位移有折返现象。上述结论证实了伪逆行点的前进方向与实际位置移动方向的矛盾性，可见本文基于改进的地图匹配算法能有效识别伪逆行。
图12 a n g l e 1、 a n g l e 2、 a n g l e 3取值分布

Fig. 12 Distributions of a n g l e 1, a n g l e 2 and a n g l e 3

3.2.3 空字符信息增强评估

图13展示了有无空字符信息增强处理的2种转向识别结果。图13（a）中，轨迹低频或采样不均使得转向支持度不够，多数路口的转向关系存在漏识别；而图13（b）中，经空字符信息增强处理后，路口转向关系的识别完整度有显著提升。
图13 SUP=10，路口转向关系识别结果可视化

Fig. 13 SUP=10, visualization of the identified turning relationships at intersections

3.2.4 SUP取值与精度评估

为选取合适的SUP值以便路口转向识别结果最佳，本文设置SUP=[1,5,10,20,30,40]进行对比试验，结果见表4。图14（a）和图14（b）分别绘制有无空字符信息增强处理的3种评价指标折线图，其中，Precision、Recall分别与SUP值呈正相关和负相关，表明随着SUP值变大，转向识别的判断条件提高，使得精确率提升、召回率降低。图14（b）中F值在SUP=5时最高，达到94.23%。因此，基于本文试验区域和试验数据，SUP=5时召回率和精确率指标达到平衡，转向关系识别结果最佳。
表4 不同参数的实验结果对比

Tab. 4 Comparison of experimental results based on different parameters (%)

方法 评价指标 支持度阈值SUP
1 5 10 20 30 40
无信息
增强处理		 Precision 88.51 91.64 94.01 96.11 96.68 96.83
Recall 94.91 80.64 70.48 57.57 49.05 42.86
F1-score 91.60 85.79 80.56 72.01 65.08 59.42
有信息
增强处理		 Precision 89.02 90.29 90.43 90.90 91.73 92.43
Recall 99.91 98.53 96.22 89.64 83.51 77.69
F1-score 94.15 94.23 93.24 90.27 87.43 84.42
图14 评价指标

Fig. 14 Evaluation index chart

总体来说，本文方法基于低成本、更新快、覆盖率高的众源GNSS轨迹数据，在SUP=5时路口转向关系识别结果最佳，其精度、召回率、F值分别达到90.29%、98.53%、94.23%。误差主要源于3点：① 轨迹可能包含骑行交通模式，带来干扰；② 点的漂移距离较大，引起轨迹地图匹配出错；③ 发生转向的轨迹极少、甚至没有，导致支持度不够。

4 结论与展望

针对OSM路网的路口转向关系缺失问题，本文充分利用众源GNSS轨迹的动态连接信息，提出一种基于地图匹配和字符串映射的路口转向探测方法，为OSM路网结构赋予转向关系。本文方法的核心思想有：① 提取并以连接点的形式统一表达OSM中结构复杂迥异的路口结构，据此引入并优化HMM地图匹配算法，将低频高噪的众源轨迹更准确的匹配到OSM路网上；② 将复杂的路口转向探测问题转化为简单的字符匹配。引入局部路段字符编码方法，将已匹配的轨迹序列映射为字符串，然后直接面向轨迹字符串，基于字符模式匹配实现路口转向关系地高效识别；③针对低频采样可能带来的匹配“跳跃”问题，提出基于最优路径分析的缺失路段补全方法，从而提高短路段的轨迹支持度。
基于上海市数据的试验结果表明：①本文方法可以有效识别结构多样、大小不一的路口转向关系，精确率、召回率、F1值分别达到90.29%、98.53%、94.23%，相较于Efentakis方法，均有不同程度提高；② 改进后的HMM地图匹配算法可以有效识别轨迹逆行异常，缓解了轨迹匹配错误对转向探测的不利影响；③ 实施空字符信息增强处理后，召回率有明显提升，SUP=5时提升了17.89%。上述实验结果验证了该方法的有效性和实用性，能够为OSM路网赋予转向关系。
考虑到城市路网中路口转向可能存在限时通行的情况，未来将进一步挖掘路口转向关系的时间限制信息。此外，鉴于非机动车轨迹对路口转向关系识别的干扰，后续将进一步引入轨迹的速度、加速度、停留等特征，开展众源轨迹交通模式的分类研究。

感谢武汉大学-华为空间信息技术创新实验室对本文提供资助。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Zhang Y J, Li X M, Wang A M, et al. Density and diversity of OpenStreetMap Road networks in China[J]. Journal of Urban Management, 2015, 4(2):135-146. DOI:10.1016/j.jum.2015.10.001

[2]
Botta F, Gutiérrez-Roig M. Modelling urban vibrancy with mobile phone and OpenStreetMap data[J]. PLoS One, 2021, 16(6):e0252015. DOI:10.1371/journal.pone.0252015

[3]
陈舒燕. 基于OpenStreetMap的出行可达性分析与实现[D]. 上海: 上海师范大学, 2010.

[Chen S Y. A web-based accessibility analysis service using OpenStreetMap data[D]. Shanghai: Shanghai Normal University, 2010.] DOI:10.7666/d.y1667221

[4]
寇培颖, 牛铮, 刘正佳, 等. 基于自发地理信息的“一带一路”区域陆路交通状况分析[J]. 地球信息科学学报, 2018, 20(8):1074-1082.

DOI

[Kou P Y, Niu Z, Liu Z J, et al. Analyzing the Land Transportation Conditions in the Belt and Road Area Based on Volunteered Geographic Information[J]. Journal of Geo-information Science, 2018, 20(8):1074-1082.] DOI:10.12082/dqxxkx.2018.180090

[5]
Mobasheri A, Zipf A, Francis L. OpenStreetMap data quality enrichment through awareness raising and collective action tools—Experiences from a European project[J]. Geo-Spatial Information Science, 2018, 21(3):234-246. DOI:10.1080/10095020.2018.1493817

[6]
张绛丽, 张笑非, 徐丹, 等. 基于OpenStreetMap的智能交通路网数据的构建[J]. 道路交通与安全, 2014, 14(1):41-47.

[Zhang J L, Zhang X F, Xu D, et al. Road_net data construction for intelligent transportation based on the open street map[J]. Road Traffic & Safety, 2014, 14(1):41-47.] DOI:10.13986/j.cnki.jote.2014.01.005

[7]
庄立坚, 何兆成, 杨文臣, 等. 基于大规模浮动车数据的交叉口转向规则自动提取算法[J]. 武汉理工大学学报(交通科学与工程版), 2013, 37(5):1084-1088.

[Zhuang L J, He Z C, Yang W C, 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

[8]
黄敏, 潘嘉杰, 刘芳. 基于SVM的交叉口连通关系建模[J]. 计算机工程与设计, 2017, 38(5):1319-1323.

[Huang M, Pan J J, Liu F. Modeling for logical connectivity of intersection based on SVM[J]. Computer Engineering and Design, 2017, 38(5):1319-1323.] DOI:10.16208/j.issn1000-7024.2017.05.037

[9]
段莉琼, 雷大伟. 车辆自导航系统中加入道路转向限制的最短路径算法[J]. 海洋测绘, 2003, 23(5):12-15.

[Duan L Q, Lei D W. The algorithm of the shortest path for turning restriction in vehicle navigation system[J]. Hydrographic Surveying and Charting, 2003, 23(5):12-15.] DOI:10.3969/j.issn.1671-3044.2003.05.004

[10]
隋东, 任刚, 邵进达. 基于GIS的城市交通网络数据模型研究[J]. 公路交通科技, 2006, 23(9):94-97.

[Sui D, Ren G, Shao J D. Study on GIS-based data model for urban transport networks[J]. Journal of Highway and Transportation Research and Development, 2006, 23(9):94-97.] DOI:10.3969/j.issn.1002-0268.2006.09.022

[11]
Efentakis A, Grivas N, Pfoser D, et al. Crowdsourcing turning-restrictions from map-matched trajectories[J]. Information Systems, 2017, 64:221-236. DOI:10.1016/j.is.2016.04.004

[12]
Efentakis A, Brakatsoulas S, Grivas N, et al. Crowdsourcing turning restrictions for OpenStreetMap[C]// Proceedings of the EDBT/ICDT Workshops. Athens, Greece, 2014:355-362.

[13]
孙智文. 基于航拍影像的道路附属设施检测技术研究[D]. 西安: 西安电子科技大学, 2018.

[Sun Z W. Research on detection technology of road accessory facilities based on aerial image[D]. Xi'an: Xidian University, 2018.]

[14]
陈兴华, 万幼川, 王晓华. 基于街景影像的交通标志识别[J]. 地理空间信息, 2014, 12(5):75-77,10.

[Chen X H, Wan Y C, Wang X H. Traffic sign recognition based on street view image[J]. Geospatial Information, 2014, 12(5):75-77,10.] DOI:10.3969/j.issn.1672-4623.2014.05.027

[15]
Naseer M, Supriadi I, Supangkat S H. Feature detection of curve traffic sign image on the bandung - jakarta highway[J]. Journal of Physics: Conference Series, 2018, 978:012083. DOI:10.1088/1742-6596/978/1/012083

[16]
Fathi A, Krumm J. Detecting road intersections from GPS traces[C]// Proceedings of the 6th International Conference on Geographic Information Science. New York: ACM, 2010:56-69. DOI:10.10.5555/1887961.1887966

[17]
唐炉亮, 牛乐, 杨雪, 等. 利用轨迹大数据进行城市道路交叉口识别及结构提取[J]. 测绘学报, 2017, 46(6):770-779.

DOI

[Tang L L, Niu L, Yang X, 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

[18]
Wang J, Wang C L, Song X F, 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

[19]
唐炉亮, 于智伟, 任畅, 等. 基于车载GPS轨迹的立体交叉口空间结构信息获取方法[J]. 交通运输工程学报, 2019, 19(5):170-179.

[Tang L L, Yu Z W, Ren C, 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.19818/j.cnki.1671-1637.2019.05.017

[20]
Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C]//Proceedings of the 31st International Conference on Very Large Data Bases. New York: ACM, 2005:853-864. DOI:10.5555/1083592.1083691

[21]
Lou Y, Zhang C Y, Zheng Y, et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY, USA: ACM, 2009: 10.1145/1653771.1653820. DOI: 10.1145/1653771.1653820.

[22]
He Z C, She X W, Zhuang L J, et al. On-line map-matching framework for floating car data with low sampling rate in urban road networks[J]. IET Intelligent Transport Systems, 2013, 7(4):404-414. DOI:10.1049/iet-its.2011.0226

[23]
向隆刚, 邵晓天. 载体轨迹停留信息提取的核密度法及其可视化[J]. 测绘学报, 2016, 45(9):1122-1131.

DOI

[Xiang L G, Shao X T. Visualization and extraction of trajectory stops based on kernel-density[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(9):1122-1131.] DOI:10.11947/j.AGCS.2016.20150347

[24]
徐倩. GB 17761-2018《电动自行车安全技术规范》解读[J]. 中国质量技术监督, 2019(3):61-63.

[Xu Q. Interpretation of GB 17761-2018 safety technical specification for electric bicycles[J]. China Quality Supervision, 2019(3):61-63.]

[25]
Zhao L S, Mao J L, Pu M, et al. Automatic calibration of road intersection topology using trajectories[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020:1633-1644. DOI:10.1109/ICDE48307.2020.00145.

[26]
张彩丽, 向隆刚, 李雅丽, 等. 基于出租车轨迹的可导航路网构建[J]. 测绘学报, 2021, 50(12):1650-1662.

DOI

[Zhang C L, Xiang L G, Li Y L, et al. Construction of navigable road network based on taxi trajectories[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12):1650-1662.] DOI:10.11947/j.AGCS.2021.20200470

[27]
李航. 统计学习方法[M]. 北京: 清华大学出版社, 2012.

[Li H. Statistical learning method[M]. Beijing: Tsinghua University Press, 2012.]

[28]
Mattheis S, Al-Zahid K K, Engelmann B, et al. Putting the car on the map: a scalable map matching system for the Open Source Community[C]// Proceedings of the Informatik, 2014:2109-2119.

[29]
Yang C, Gidófalvi G. Fast map matching, an algorithm integrating hidden Markov model with precomputation[J]. International Journal of Geographical Information Science, 2018, 32(3):547-570. DOI:10.1080/13658816.2017.1400548

[30]
李军, 游弋, 邓红平. 城市浮动车数据定位误差分布规律研究[J]. 科学技术与工程, 2016, 16(1):244-249.

[Li J, You Y, Deng H P. Distribution characteristics of FCD positioning error in urban areas[J]. Science Technology and Engineering, 2016, 16(1):244-249.] DOI:10.3969/j.issn.1671-1815.2016.01.047

Options
Outlines

/

〈 〉