留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种路网拓扑约束下的增量型地图匹配算法

朱递 刘瑜

朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
引用本文: 朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
ZHU Di, LIU Yu. An Incremental Map-Matching Method Based on Road Network Topology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
Citation: ZHU Di, LIU Yu. An Incremental Map-Matching Method Based on Road Network Topology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016

一种路网拓扑约束下的增量型地图匹配算法

doi: 10.13203/j.whugis20150016
基金项目: 

国家自然科学基金 41271386

国家自然科学基金 41428102

详细信息
    作者简介:

    朱递, 硕士生, 主要从事地理信息系统、时空大数据和计算机可视化研究。zhudi-001@163.com

  • 中图分类号: P208;P283.1

An Incremental Map-Matching Method Based on Road Network Topology

Funds: 

The National Natural Science Foundation of China 41271386

The National Natural Science Foundation of China 41428102

图(12)
计量
  • 文章访问数:  812
  • HTML全文浏览量:  21
  • PDF下载量:  499
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-04-18
  • 刊出日期:  2017-01-05

一种路网拓扑约束下的增量型地图匹配算法

doi: 10.13203/j.whugis20150016
    基金项目:

    国家自然科学基金 41271386

    国家自然科学基金 41428102

    作者简介:

    朱递, 硕士生, 主要从事地理信息系统、时空大数据和计算机可视化研究。zhudi-001@163.com

  • 中图分类号: P208;P283.1

摘要: 着眼于低频浮动车轨迹数据,对地图匹配问题进行了抽象,并分析了影响匹配结果的几何约束与拓扑约束。针对GPS采样的低频性和城市路网的复杂性,提出了一种路网拓扑约束下的增量型地图匹配算法(topology-constrained incremental matching algorithm,TIM)。选取北京市浮动车的GPS样例轨迹数据进行匹配,结果表明,该匹配算法在不同复杂程度的城市路网下均表现较好。

English Abstract

朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
引用本文: 朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
ZHU Di, LIU Yu. An Incremental Map-Matching Method Based on Road Network Topology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
Citation: ZHU Di, LIU Yu. An Incremental Map-Matching Method Based on Road Network Topology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
  • 在大数据时代,浮动车技术广泛应用,带来了海量的城市车辆轨迹数据。这些数据一方面为研究城市空间结构提供了新的视角,另一方面可以为各类智能交通系统应用提供研究基础[1-3]。其中,智能交通系统为了得到每条路段的交通流量、车速等信息,需要进行GPS轨迹的地图匹配。地图匹配是一种基于软件技术的定位修正手段,其基本思路是将定位装置所获得的车辆定位轨迹与数字地图数据库中的路网数据相联系,从而确定车辆的路网参考位置,或正确识别出车辆在特定时刻所处的路段[4-5]。由于获得的GPS数据质量存在不一致,路网数据精度也存在差异,国内外学者对于地图匹配算法的研究也多种多样。目前,对于高频采样的GPS数据和相对简化的路网数据,已有很多较为成熟的匹配算法[6-7]。然而,针对低频GPS采样数据和高复杂度的城市路网,成熟并实用的地图匹配算法并不多,算法的匹配效率和匹配精度也普遍难以达到研究和应用的要求。

    本文针对低频GPS采样数据在复杂城市路网下的地图匹配问题,综合考虑影响地图匹配的的几何约束与拓扑约束,提出了一种路网拓扑约束下的增量型地图匹配算法(topology-constrained incremental matching algorithm, TIM)。该算法能够较好地解决GPS低频性质带来的匹配不稳定性和复杂城市路网带来的计算复杂性,为相关研究提供思路。

    • 街道系统,即真实的路网,可以表示为N,移动对象的真实轨迹为T,移动对象在t时刻的真实位置为Pt,GPS定位的t时刻位置为Pt。低频GPS采样数据是指Pt的采样时间间隔大于1 min。获得真实街道系统N往往是不可行的,通常研究基于的都是路网的数字表达形式,记作NN由有限数量的弧段组成,每一个弧段AN是由一系列点(A0, A1, A2, …, An)构成,其中A0An是弧段起始点和终止点,而A1A2、…、An-1通常被称作形状点。

      地图匹配问题就是将GPS定位位置Pt匹配到数字路网N中与之对应的弧段A上,从而确定真实街道系统中对应真实位置Pt的道路AN。针对不同的研究目的,有的研究还会进一步确定A弧段上Pt所对应的具体位置,如图 1所示。

      图  1  地图匹配问题抽象化图示

      Figure 1.  Abstraction of Map-Matching

    • 影响地图匹配算法设计和匹配结果的几何约束主要包括距离因素、航向因素与方位因素。国内外已有相关研究构建起相对完善的权重匹配模型来实现地图匹配。

      随着采样点和弧段垂直距离D(>0)的减小,点和弧段的邻近性增加,因此,距离因素对匹配结果的权重WD可以定义为:

      $$ {W_D} = {\lambda _D}/D $$ (1)

      其中,λD(>0)为可调节的权重参数。

      同时,配置有航位推算系统(dead reckoning, DR)的GPS能够提供带有移动个体行驶航向的原始数据,GPS/DR数据的航向参数非常精确,通常能够用于辅助匹配和纠正匹配的结果。

      方位因素对于地图匹配结果也有明显的影响,常见因素有:(1)相邻GPS采样点连线与路段相交程度Wi=λicosθλi为可调节的参数,θ为相邻GPS采样点连线与路段的夹角。(2) GPS采样点相对于路段端点的位置Wr=λrcosαλr为可调节的参数,α为采样点与路段端点连线和交叉口各路段的夹角。

    • 空间拓扑关系能够反映出实体和地理间的相互关系,为了保证地图匹配结果的合理性,构建拓扑约束至关重要。本文主要考虑了两方面的拓扑约束:

      1) GPS误差缓冲区与路网的叠加拓扑约束。GPS定位存在误差,基于概率准则定义误差椭圆,可以有效缩小匹配搜索时的状态空间。从GPS接收机的输出数据中可以直接读出系统正向与北向测量误差的标准差σxσy,设σxyσyx为协方差,定位系统的方差、协方差矩阵M便可以模型化为:

      $$ \mathit{\boldsymbol{M = }}\left[ {\begin{array}{*{20}{c}} {\sigma _x^2}&{{\sigma _{xy}}}\\ {{\sigma _{yx}}}&{\sigma _y^2} \end{array}} \right] $$ (2)

      由此定义的定位误差椭圆半长轴a和半短轴b以及椭圆半长轴取向与正北方向的夹角φ为:

      $$ \begin{array}{l} a = \sigma _0^2 \cdot \\ \sqrt {\frac{1}{2} \cdot \left( {\sigma _x^2 + \sigma _y^2 + \sqrt {\left( {\sigma _x^2 - \sigma _y^2} \right) + 4\sigma _{xy}^2} } \right)} \end{array} $$ (3)
      $$ \begin{array}{l} b = \sigma _0^2 \cdot \\ \sqrt {\frac{1}{2} \cdot \left( {\sigma _x^2 + \sigma _y^2 - \sqrt {\left( {\sigma _x^2 - \sigma _y^2} \right) + 4\sigma _{xy}^2} } \right)} \end{array} $$ (4)
      $$ \varphi = \frac{{\rm{\pi }}}{2} - \frac{1}{2}\arctan \left( {\frac{{2{\sigma _{xy}}}}{{\sigma _x^2 - \sigma _y^2}}} \right) $$ (5)

      在式(3)~(5)中,σ02为单位权值的后验方差,可以通过改变σ0的值来调整误差区域的大小, 从而产生不同的误差椭圆置信度。

      2)路网拓扑连通约束。本文处理的是低频GPS采样数据,而路网又是精度极高的复杂城市路网,在匹配结果中,跳路是很常见的(即相邻两次匹配结果所对应的路段满足拓扑邻接的概率是很低的)。于是,本文提出的路网拓扑连通约束是指相邻两个GPS采样点所匹配到的路段之间,在路网中应当存在一条连通路径,即匹配结果在路网表达上的连通性。

    • 本文旨在解决低频GPS采样数据在复杂城市路网下的地图匹配问题,处理GPS低频性质带来的匹配不稳定性和复杂城市路网带来的计算复杂性显得格外重要。前人也有过将路网拓扑约束和最短路径思想同时考虑并设计算法的相关研究[8]。但是,该研究只是在已知轨迹起始、终止位置的前提下,进行最短路径的检索,忽略了轨迹中段GPS采样点所带来拓扑约束影响以及轨迹之间的差异性。

      本文提出一种拓扑约束下的增量型地图匹配算法。该算法首先结合GPS采样点的几何约束构建误差缓冲区,通过将GPS误差缓冲区与路网缓冲区进行叠加,得到GPS采样点的候选匹配边集。接着,基于候选匹配边集的属性进行轨迹增量化处理,并构建匹配时的拓扑约束。最后,利用拓扑邻接约束下的A*算法实现轨迹增量的地图匹配,将GPS采样点和对应的路段实现匹配。TIM算法流程如图 2所示。

      图  2  TIM算法流程图

      Figure 2.  Flowchart of TIM Algorithm

    • TIM算法在GPS轨迹预处理和路网简单拓扑构建完成之后,首先需要完善并抽象路网拓扑关系,使之成为可用的路网邻接模型。所谓路网拓扑邻接字典(topological adjacency dictionary,TAD),是指利用简单拓扑构建后的边表的Source和Target字段,检索与每一条边相邻的所有边,并将这个巨大的邻接关系存储为字典的形式,其示意图见图 3

      图  3  路网拓扑邻接字典构建示意图

      Figure 3.  Diagram of Topological Adjacency Dictionary

      将TAD转存为JSON文档格式,计算机只需要读取该JSON文档便能够为后续的匹配计算提供路网信息。一个典型的TAD记录在JSON文档中表示为:

      {"Key":1204, "Value":[1205, 1160, 1162, 1206]}

      Key对应当前边的ID,Value对应与该边相邻的边的ID。经测试,读取北京市路网数据的JSON文档并转换为字典格式,用时为1 200~1 500 ms,是完全能够接受的。

    • 地图匹配的关键假设是GPS定位存在误差,且误差是在一定范围之内的。于是,确定误差区域以便提取候选匹配道路便成为了非常重要的一环。TIM算法同样运用构建GPS误差缓冲区的方式来确定GPS的待匹配边集。由于对于误差椭圆的包含和相交运算需要累计执行大量乘积与开方,前人在构建GPS误差缓冲区时常选取误差圆的方法。但是,多数研究在构建误差缓冲区时没有考虑不同GPS采样点之间的差异性。由于随着GPS行驶速度的增大,定位误差会在一定程度上减少[6]。在TIM算法中,通过利用GPS/DR数据中所带有的速度字段,构建一个动态的误差缓冲区,从而进一步提高待匹配边集的有效性和准确性。

      鉴于目前没有成熟的研究将GPS误差圆半径随速度的变化关系量化表示,在GPS轨迹数据预处理之后(包括纠偏、去除飘点和冗余数据等),综合考虑算法效率和匹配结果,TIM算法采用简单的线性关系对其进行刻画,其关系为:

      $$ R = \left\{ \begin{array}{l} 60 - \frac{1}{3}v\Delta t,0 \le v \le 90\\ 30,v \le 90 \end{array} \right. $$ (6)

      式中, R为误差圆半径(m);v为行驶速度(m/s);Δt为单位时间(s)。由于轨迹预处理时已经将纠偏后偏离路网距离过大的采样点去除,根据实验结果,将R范围设置在[30 m, 60 m]能够较好地处理本文的需求。

      生成的GPS误差缓冲区如图 4所示。图 4中紫色的连线为按照时间顺序的GPS采样点连线,考虑到速度因素,GPS误差缓冲区大小不恒定,动态误差缓冲区的思想有非常重要的意义。

      图  4  GPS误差缓冲区动态生成效果图

      Figure 4.  Dynamically Building GPS Error Buffer

    • 在将GPS误差缓冲区与路网进行叠加分析时,利用原始数据中较完善的路段宽度字段,构建路网的双侧缓冲区,再将误差缓冲区与路网缓冲区求交,从而得到每一个GPS采样数据Pi的候选匹配边集EPi,其效果如图 5所示。

      图  5  GPS数据候选匹配边集EPi的建立

      Figure 5.  Generation of EPi

      与建立路网TAD时的思路一样,本文也将GPS数据的EPi存储为JSON文档,以便于匹配时的快速检索与查询。一个典型的EPi记录表示为:

      {"Key":"20121130073700.000000000", "Value":[1452, 1316, 2128, 1317, 1457, 1461, 1458, 2127]}

      Key表示GPS点的采样时间,与GPS数据一一对应,Value对应该GPS可能匹配到的边的集合,集合中的元素对应边的ID,与TAD中的Key相对应。

      EPi在TIM算法中具有非常重要的作用。首先,对于每一个GPS采样点,EPi反应了该点对于轨迹匹配几何约束的贡献,每一个采样点匹配的结果只能够在对应EPi中进行选择。其次,EPi有效地将GPS点和路网拓扑关系连接了起来,通过检索EPi中边集的相邻边,可以在路径搜索中进行有效的拓扑约束。另外,EPi为GPS轨迹提供了一种分类标准,从而使得轨迹能够增量化,EPi的大小会直接影响到算法的效率。

    • 在进行轨迹增量化处理之前,需要对轨迹上的GPS点进行分类,利用分类后GPS点的不同属性,将轨迹划分为一系列增量。这种将轨迹增量化的思想参考了分治思想,能够降低匹配的复杂度,显著提高算法的效率。

      EPi的构建完成后,TIM算法顺序遍历所轨迹T(P1, P2, P3, …, Pi, …, Pt)中的每一个GPS采样点Pi,并对Pi进行分类,分类标准为:

      1)若当前PiEPi为空,从T(P1, P2, P3, …, Pi, …, Pt)中删除Pi

      2)如果当前PiEPi只包含一条边,将Pi标记为停止点。

      3)如果当前PiEPi包含多条边,将Pi标记为中间点。

      通过GPS采样点分类后,轨迹中的点被分成了停止点和中间点两类。停止点在轨迹中的匹配可靠性是非常强的,即轨迹一定会通过该点对应EPi中的那条边,中间点则能够有效地约束轨迹匹配时的抖动幅度。利用停止点的特殊性,原始轨迹的匹配问题便可以进行分治,划分为一个个增量地图匹配子问题,同时很好地保证了匹配的准确性。

      本文定义增量为一个停止点和下一个停止点之间的轨迹片段,抽象为I(Pis, Pi1, Pi2, …, Pij, …, Pit),其中,PisPit为停止点,而Pi1, Pi2, …, Pij, …Pit-1均为中间点。

      在增量匹配阶段,只保留那些起始点和终止点均为停止点的轨迹片段作为增量,若PisPit不能满足均为停止点,则舍弃该轨迹片段。

    • 假设出租车司机是具有经验的路径选择者,在目的地确定的条件下,出租车司机会选择行驶时间最短的路线行驶。由于本文无法获得路网实时速度数据集,假设全路网行驶速度恒定,那么出租车司机会选择距离最短的路线来行驶。

      经过了轨迹增量化后,本文的研究目标转换为一个增量的匹配问题。轨迹增量具有确定的起始路段和确定的终止路段,而中间点的候选匹配边集约束并减小了中间点可能匹配路段的搜索状态空间,TIM算法采用基于轨迹约束的启发式A*算法,能够实现轨迹增量的快速地图匹配。区别于最常见的状态空间搜索,如深度优先搜索和广度优先搜索,启发式A*算法的优点在于它并不是在完整路网所对应的状态空间下进行穷举,而是对每一个搜索的位置进行评估,并对所有评估过的位置进行评估值的排序,将评估值最小的位置作为最优并继续搜索,由此缩小了搜索的状态空间。

      按照传统A*算法,节点n的估价函数f′(n)可以表示为:

      $$ f'\left( n \right) = g'\left( n \right) + h'\left( n \right) $$ (7)
      $$ g'\left( n \right) \le g\left( n \right),h'\left( n \right) \ge h\left( n \right) $$ (8)

      式中,f′(n)为节点n的A*估价函数值;g(n)为状态空间中从初始节点搜索至节点n的实际代价;h(n)为节点n到目标节点的最佳路径的估计代价;要求g′(n)恒小于g(n),而h′(n)恒大于h(n)。计算时取g′(n)为起点到节点n的最短路径,取h′(n)为节点n到目标节点的欧氏直线距离。可以证明,这样的估价函数能够保证找到从起始位置到目标位置的最短路径。

      受到A*算法的启发,本文针对路网的拓扑结构特点提出T-A*算法。T-A*算法的状态空间中处理的对象是轨迹增量的中间点,每一个位置的搜索结果是路段。

      假设当前处理的GPS数据采样点为中间点Pt,其候选匹配边集表示为EPt{E1, E2, E3, …, En},其中,Ei的起始节点为Nis,终止节点为Nit。那么,定义T-A*算法的估价函数为:

      $$ f'\left( {{P^t}} \right) = \mathop {\min }\limits_i \left\{ {g'\left( {{N_{is}}} \right) + l\left( {{E_i}} \right) + h'\left( {{N_{it}}} \right)} \right\} $$ (9)

      式中,g′(Nis)为增量起始采样点对应匹配边的终止节点到Ei起始点Nis的A*最短路径长度;l(Ei)为求候选边Ei的长度的函数;h′(Nit)为Ei终止节点Nit到增量终止采样点对应匹配边的起始节点的欧氏直线距离。

      T-A*算法执行时,首先遍历增量的全部GPS采样点,根据T-A*估价函数确定所有Pt点的匹配边,降低轨迹匹配的抖动性。接着,可以利用传统A*算法得到相邻两GPS采样点之间的路径则。根据上述流程便可以给出一个增量的完整匹配结果,并按照一定格式输出。

    • 从北京市2009年11~12月的6 000余辆出租车行车轨迹中选择了较具有代表性的出租车在2009-11-30T06:32~2009-12-01T00:06的轨迹作为原始样例,经过火星坐标纠偏处理、重采样和去除飘点及冗余数据后,样例轨迹的有效采样点从1 624点减少为853点。另外,选取北京市城区内的路网数据,并将其与编号为该出租车的行驶轨迹进行匹配,城区路网数据如图 6所示,共计边102 575条。

      图  6  北京市城区路网示意图

      Figure 6.  Road Network of Beijing Urban Area

      统计分析发现,样例轨迹平均采样间隔为1.19 min,满足低频数据的特点,采样间隔最大为55 min,绝大部分为1~3 min,少量间隔小于1 min或大于5 min。低频采样的特征且样例数据的速度起伏较大,采样密度的空间差异非常明显(见图 7)。仅从笔者了解到的情况来看,处理如此低频的轨迹数据的相关研究非常少。

      图  7  样例轨迹点密度图

      Figure 7.  Dot Density Map of Sample Trajectory

    • 实验结果表明,TIM算法在处理北京城市复杂路网下的低频采样数据时表现出较好的稳定性,本文选择具有代表性的区域进行匹配结果的展示。

      图 8~10分别显示了TIM算法在带有立交的高速路段、特色明显的北京胡同路段以及采样距离较大的直线路段均能给出相对令人满意的结果,图 8~10中,红色点为增量采样点。这是由于T-A*算法充分考虑了几何约束与拓扑约束,同时加入一些如路网等级、宽度等因素对匹配结果进行了修正。由于TIM对于路网拓扑结构的要求较高,路段拓扑缺失可能会触发T-A*算法在检索时的终止条件,从而对增量片段再分段出现异常,如图 11所示。

      图  8  07:00~07:59机场高速路段匹配结果

      Figure 8.  Match Results for Airport Expressway at 07:00-07:59

      图  9  09:58~11:08北二环胡同

      Figure 9.  Match Results for Beierhuan Alleyway at 09:58-11:08

      图  10  13:33~13:46南二环护城河段

      Figure 10.  Match Results for Nanerhuan Moat at 13:33-13:46

      图  11  15:59~16:08玉渊潭南侧(拓扑异常)

      Figure 11.  Error Match at the South of Yuyuantan at 15:59-16:08

    • 本文对于测试样例轨迹进行匹配的测试环境为Intel (R) Core (TM) i5-3230M CPU @2.60 GHz、4 G RAM、WIN8 x64、VS2012.NET Framework 4.5。在TAD、EPi和轨迹增量的构建完成后,对于72个增量的匹配共计用时116.64 s,平均每个增量用时1.62 s。由于平均每个增量含11.03个采样点,每一个采样点的匹配以及相邻采样点间最短路径的检索需耗时0.147 s,总体效率可以满足普通实时ITS应用的需求。

      另外,本文的样例出租车轨迹真实数据不可知,在进行AN数量准确性分析时无法逐个检查。考虑到GPS采样点的数量并不是很大,本文通过逐个采样点目视观察的方法判断每一个GPS点匹配是否正确(见式(10))。853个GPS采样点得到正确匹配的采样点数量为785, AN=92.03%。

      $$ {A_N} = \frac{{正确匹配的路段}}{{轨迹对应的全部路段}} $$ (10)

      由于目视时有可能忽略路网拓扑因素,直观结果和算法结果可能会出现不一致性,这也有可能导致AN的值不准确。

    • 通过分析TIM算法的流程,可以总结出两个会影响结果准确性的重要因素或参数。

      1)路网现势性问题以及拓扑邻接字典的准确性。如果基础路网边表的Source和Target字段和真实路网情况不一致,或者由于路网导入空间数据库时拓扑容差的阈值过大,则会导致构建的拓扑邻接字典出现拓扑错误或者拓扑缺失,从而导致异常匹配。本文中没有对基础路网的拓扑和准确性进行检查,是有待商榷的。

      2) GPS数据候选匹配边集的大小。候选集平均大小会明显影响T-A*算法的效率,将EPi的平均大小按照合理规则控制在10以内将会有效地保证匹配效率,如图 12所示。本文中,TIM算法在误差圆半径与速度之间建立起简单的线性关系,从而获得候选匹配边集,进一步构建增量进行地图匹配,可以较好地满足算法效率和准确性的要求。

      图  12  候选匹配边集大小与匹配效率的关系

      Figure 12.  Influence of EPi Set on Matching Efficiency

    • 本文提出了一种路网拓扑约束下的增量型地图匹配算法,实现了不同城市路段的低频GPS采样数据地图匹配,分析了拓扑邻接字典、GPS误差缓冲区、候选匹配边集对于算法匹配结果的影响机制,为今后有关地图匹配的研究提供思路和依据。

      本文研究中尚未考虑航向与路段行驶方向的约束,也未论证数据的代表性。后续研究可以从动态缓冲区大小选择的角度来探讨影响误差缓冲区的因素及相应关系。

参考文献 (8)

目录

    /

    返回文章
    返回