本文内容来源于《测绘通报》2024年第6期，审图号：GS京（2024）1024号
钟青岑1, 吴晨昊2, 向隆刚1,3, 姚鹏4
1. 武汉大学测绘遥感信息工程国家重点实验室, 湖北 武汉 430079;2. 福建省高速公路科技创新研究院有限公司, 福建 福州 350001;3. 湖北珞珈实验室, 湖北 武汉 430079;4. 广西泰绘信息科技有限公司, 广西 桂林 541100基金项目：湖北省珞珈试验室专项基金(220100010);广西JMRH发展专项项目(202203)
关键词：地图匹配, 深度学习, 序列到序列模型, GRU, 多任务学习, 注意力机制
引文格式：钟青岑, 吴晨昊, 向隆刚, 等. 顾及路网约束的深度地图匹配方法. 测绘通报，2024(6)：96-102. DOI: 10.13474/j.cnki.11-2246.2024.0617.摘要 ：在低频或非均匀采样条件下,已有的地图匹配算法存在匹配精度不高或效率较低的问题。本文提出了一种顾及路网约束的深度地图匹配方法(RNCMM)。该方法首先利用Seq2Seq框架将低频轨迹点序列端到端地映射为高频路段序列;其次根据道路与轨迹点间的距离、方位差构建细粒度约束掩模层,有利于缓解轨迹网格表示的局限性,提高匹配精度;然后引入注意力机制和多任务学习机制,挖掘轨迹点间的时空关联性,并进行路段与方向的联合预测;最后在Porto出租车轨迹数据集和OSM路网上进行试验。结果表明,相较于传统的隐马尔可夫模型(HMM)算法,本文方法可以有效地提高低频浮动车轨迹的匹配精确度和效率。
随着位置感知技术的发展，基于轨迹数据分析的应用越来越广泛。然而，受恶劣天气及复杂路况的影响，采集的GPS轨迹会偏离移动对象真实的运动路径。地图匹配算法可将采集的轨迹点匹配到正确的行驶路段上，有效减少了定位误差，为路径规划[1]、车载定位[2]和自动驾驶[3]等应用提供重要支持。
地图匹配算法主要分为基于几何信息[4]、拓扑关系[5-7]、概率统计[8-9]及先进技术的算法。几何匹配易于实现且效率高，但难以保障相邻采样点匹配路段的连通性。利用路网拓扑关系可限制轨迹点的候选匹配路段，却需在匹配过程中进行大量的路径分析。概率统计方法能较好地减弱定位噪声的干扰，然而算法实现复杂且计算开销大。基于轨迹与路段的关联性及相邻轨迹点的上下文关系，目前广泛应用的隐马尔可夫(hidden Markov model，HMM)地图匹配模型[10]可显著提高轨迹的匹配精度，随后不断结合速率[11]、路段宽度[12]和路径选择偏好[13]改进算法。为了降低采集成本和传输能耗，在实际应用中通常采集低频的浮动车轨迹。然而稀疏轨迹采样点间的不确定性较大，HMM算法在匹配时需要大量搜索最短路径，导致其在处理海量低频轨迹数据时匹配精度受到限制且匹配效率低。
为克服传统匹配方法的局限性，研究人员尝试利用深度学习技术解决地图匹配问题。如文献[14]利用RNN模型和强化学习快速识别用户最可能的运动路径。借助数据增强技术和Seq2Seq框架，文献[15]可将具有较大定位误差的稀疏轨迹高效地映射到路网中。RNN模型利用隐藏向量表示轨迹序列，在匹配过程中可根据当前轨迹采样点与隐藏向量直接推断最大概率的候选路段，避免在相邻采样点的多个候选路段集间大规模搜索最短路径，显著提高匹配效率。然而现有的深度地图匹配模型仍面临挑战，将轨迹点的经纬度坐标转换为离散单元有效降低模型的计算量，但粗粒度的输入增加了匹配的不确定性。此外，具有短期记忆能力的RNN难以有效利用较早时间步的信息，轨迹较长时匹配效果不佳。
为此，本文提出一种顾及路网约束的深度地图匹配方法(road network constrained map matching based on deep learning，RNCMM)。主要有以下改进：基于Seq2Seq架构实现从低频轨迹点序列到高频路段序列的端到端映射；基于路段和轨迹采样点间的距离和方向差异构建具有精细特征的掩膜层，为神经网络提供更多的约束信息，有效地提高模型的匹配准确率；引入注意力机制便于捕捉轨迹序列的长程依赖关系；引入多任务学习机制联合预测路段标识号(ID)和方向，有助于抵消部分噪声，减少过拟合。
顾及路网约束的深度地图匹配方法的技术路线如图 1所示。首先对原始轨迹数据进行预处理，剔除冗余、异常和超出试验范围的轨迹数据；计算轨迹点的行驶方向，将其设定为前后两轨迹点所构成的射线方向。其次对路网数据进行预处理，调用OSMnx[16]工具包自动简化和纠正OSM路网的拓扑结构；并利用RTree存储路段的标识号和最小外接矩形MBR，这种空间索引结构便于查找轨迹点一定距离范围内的路段；将路网建模为属性有向图。然后将低频轨迹点序列和路网有向图输入RNCMM模型训练，输出高频轨迹匹配序列。最后删除轨迹匹配序列中的连续重复项并将其投影至路网空间。
图 1 顾及路网约束的深度地图匹配方法框架
定义1(轨迹)：轨迹是按时间顺序排列的轨迹点序列T={P1，P2，…，Pi，…，Pn}，轨迹点Pi={xi，yi，ti}记录了移动对象的运动状态，xi、yi和ti分别为地理坐标系下采样点Pi的经度、纬度和采样时间，相邻轨迹点的采样频率为ε=ti+1-ti。定义2(道路网)：定义道路网为有向图G={V，E}，顶点v∈V，表示路段的交叉口或端点；路段e∈E，表示有向边，由起始点、终点、路段标号和其他属性表示，一条可双向通行的道路被认作两条单向路段。定义3(轨迹匹配序列)：序列Tr={e1，e2，…，ej，…，em}, 代表移动对象在道路网中的真实运动路径，ej是轨迹点的匹配路段。如图 2所示，给定高频采样率εr和低频轨迹点序列T，RNCMM模型首先将T转换为时空嵌入向量序列，然后利用编码器捕捉向量序列的依赖关系并将其映射为上下文向量h0′，解码器基于h0′逐步生成采样率为εr的轨迹匹配序列Tr，即模型可生成低频轨迹中的缺失点并同时将其映射到对应的路段上。图 2 RNCMM模型
对离散向量序列进行建模比连续数值序列更可靠容易，因此本文将轨迹点Pi表示为时空嵌入向量Gi=〈MDi，pidi〉。将研究区域划分为一系列网格单元，MDi是点Pi所在网格的Geohash编码值，其由网格行列号的二进制数交叉排列，每5位分为一组，每组的二进制序列转换为一个十进制整数。在二维地理空间中坐标相近的轨迹点具有相近的Geohash编码值。pidi是点Pi的时序索引，计算公式为式中，tP1和tPi分别为低频轨迹T中首个和第i个轨迹点的采样时间；εr为轨迹匹配序列Tr的采样间隔。pidi可帮助解码器学习应在轨迹T的相邻采样点间生成多少个缺失点。如某条低频轨迹L=〈P1，P2，P3〉的时序索引为pid=〈1，3，7〉，解码器需要在采样点P1和P2间生成1个缺失点，而在点P2和P3间生成3个缺失点。GRU创新地引入更新门z和重置门r控制历史信息的流动，有助于捕获序列的长程依赖关系，防止梯度消失或爆炸。在编码过程中，将当前时间步的时空嵌入向量Gi和前时间步的隐藏状态hi-1一起输入GRU，便可计算出编码器当前时间步的隐藏状态hi。计算公式为式中，σ为Sigmoid函数；Wz和Wr分别更新门和权重门的权重矩阵；bz和br为门的偏置项；为候选隐藏状态。当前时间步隐藏状态hi的计算公式可简化为为了提取轨迹时间的潜在特征，首先把一整日划分为24个离散的时间段并将其转换为相应的独热编码，然后利用嵌入层提取时间特征向量At, 最后将At与编码器末时间步的隐藏状态hn的融合结果作为解码器的初始隐藏状态h0′，其计算公式为式中，tanh()为激活函数；Wt、bt分别为全连接层的权重矩阵和偏置项。引入多任务学习机制同时预测轨迹点匹配路段的方向及标识号，可确保重建的轨迹映射到道路网络而非整个研究区域，且联合训练有助于抵消部分噪声，提升模型的泛化能力。图 2展示了多任务块(multi-task block，MB)的详细结构，首先将解码器在第j-1时间步生成的输出向量依次送入全连接层和softmax层预测路段方向dj-1。路段ID和方向不能直接输入神经网络的分类值，利用嵌入层降低输入向量的维度并挖掘其语义信息。其次将方向预测值与GRU层的输出向量拼接，并通过全连接层挖掘拼接向量的特征。然后通过约束掩膜层输出每条路段的概率值。最后利用预测的路段方向dj-1和标识号ej-1更新解码器当前时间步的隐藏状态hj′，其计算公式为将轨迹点经纬度坐标网格化可有效减少模型的计算量，但可能会损失部分运动细节，增加匹配的不确定性。对此，文献[17]构建掩膜层对神经网络进行细粒度约束，本文则进一步根据距离与行驶方向差异构建约束掩膜层。使用约束掩膜层可将轨迹采样点投影到有限路段而非整个路网空间，有利于提高匹配的准确率。约束掩膜层的核心思想是构造权函数fw衡量轨迹点与候选路段上投影点的相似程度，相似程度越高的候选路段成为匹配结果的概率越大。如图 3所示，以低频轨迹的采样点Pi为中心构建方形缓冲区，搜索缓冲区内的所有候选路段(即候选路段的最小外接矩形与缓冲区相交)，点C1、C2和C3分别为点Pi在候选路段e1、e2和e3上的投影点。将fw定义为距离权函数fd与方向权函数fh的乘积，fd(i，l)表示采样点Pi对候选匹配点Cl的影响，fh衡量点Pi行驶方向与候选路段el方向的相似程度，计算公式为图 3 候选路段示意
式中，di，l为点Pi与点Cl的Haversine距离；R为地球半径；λ和φ分别为经度和纬度；θi，l为点Pi与路段el的方向差；θi和θl分别为点Pi的方位角和路段el的方位角；超参数σ和γ分别设置为5.8与100。本文只计算低频轨迹中采样点Pi的候选路段集权重，将点Pi缓冲区外的路段权重设置为极小值10-10。对于解码器在低频轨迹采样点间生成的缺失点Pj，将研究区域内所有路段的权重设置为1，即点Pj可能匹配到任意路段。最后将权函数fw与softmax函数结合为约束掩膜层，其定义为式中，Rl为路段el的最小外接矩形；Rj为采样点Pj的缓冲区，边长设置为50 m；wu为可学习的网络参数矩阵WU的第u列向量。Seq2Seq的编码器将输入序列压缩为固定大小的上下文向量，但这种有损压缩会遗忘长序列中的细节信息。因此，本文引入注意力机制提高解码器捕捉信息的能力，通过动态调整模型对输入序列的关注度，即可从编码器的所有隐藏状态中选出与生成目标最相关的信息，并将其表示为上下文向量α。首先计算解码器在第j-1时间步生成的隐藏状态hj-1′和编码器的每个隐藏状态hi的相似度，再利用softmax函数对相似度权重进行归一化。然后将编码器所有的隐藏状态加权求和得到上下文向量αj-1，计算公式为式中，v、W和U为可学习的网络参数；n为编码器输入序列的长度；αj-1包含不同采样点对预测路段的影响，权重值越大表示采样点的影响越大。最后解码器根据向量αj-1生成下一时间步的隐藏状态hj′，其计算公式由式(8)更新为路段ID和方向的预测任务都可视作多分类问题：轨迹点可能匹配到研究区域内的任意路段，其预测方向角可能为360°中的任意整数角度。引入交叉熵优化多分类问题，最终将RNCMM模型的优化函数L定义为路段方向损失函数Ld和路段ID损失函数Le的加权和，计算公式为式中，B为批量大小；m为解码端重建匹配序列Tr的长度；K为方向角度；L为路段数量；yj，k与yj，l为符号函数，当时间步j的方向角真实值等于k时yj，k取1，否则取0；当时间步j的路段真实值等于l时yj，l取1，否则取0；pj，k为时间步j的方向角预测值等于k的概率；pj，l为时间步j的路段预测值等于l的概率；δ为先验的超参数，可线性协调模型中两项任务的重要性。基于Porto出租车轨迹数据集[18]和OSM路网数据进行试验。在研究区域内随机选取10万条预处理后的轨迹作为试验数据集，利用HMM匹配算法[10]标注车辆真实的行驶路径。轨迹的平均长度为2.91 km，相邻轨迹点的采样间隔均为15 s，路网经度、纬度范围分别为[-8.653 7°，-8.585 6°]和[41.144 8°，41.175 4°]，构建的Geohash网格区域为6.4 km×6.4 km，覆盖整个路网空间。构建的路网有向图中包含4837条路段和2402个节点。为验证RNCMM模型对低频轨迹的匹配效果，本文分别以6.25%、12.5%、25%和50%的重采样率对原始轨迹数据进行抽稀，对应的低频轨迹平均采样间隔分别为240、120、60和30 s。每条重采样轨迹与原始轨迹进行一一配对，用于后续的模型训练和验证。将试验数据集以7∶2∶1的比例随机拆分为训练集、验证集和测试集。训练时设置网格边长默认值为50 m，隐藏状态维度默认值为512，路段ID和方向的嵌入向量维度分别为128和32，teaching force的阈值为0.75，并使用随机梯度下降法不断调整神经网络的参数。模型利用PyTorch深度学习框架，在搭载Intel? CoreTM i7-6900K @ 3.20 GHz中央处理器和NVIDIA GeForce RTX 3080图形处理器的计算机上训练。参考文献[19]，本文利用精确率(precision，P)和召回率(recall, R)评估地图匹配算法的准确性，用每条轨迹的平均匹配时间(average matching time，AMT)评估算法的执行效率，计算公式为式中，|D|为测试集D中轨迹的数量；Trk和Tgk分别为轨迹k的匹配路径和真实路径；Trk∩Tgk为正确匹配的路径；time()用于计算轨迹k的匹配时间；Precision为匹配路径中正确匹配路段的占比；Recall为真实路径中正确匹配路段的占比。精确率和召回率越高，表明算法的匹配准确性越高。选取两种地图匹配算法和两种RNCMM变体进行对比试验。(1) Linear[20]+HMM[10]：为了减少低频轨迹的不确定性，假设车辆在做匀速直线运动。即给定目标采样率，先采用线性插值的方式将低频轨迹恢复为高频轨迹，然后用HMM算法对高频轨迹进行地图匹配。(2) Seq2Seq[15]：一个用于轨迹恢复与匹配的模型，可将轨迹点序列映射为路段序列。(3) RNCMM-noConst：移除多任务块中的约束掩膜层验证该组件的重要性。(4) RNCMM-noAttn：移除模型的注意力机制验证其重要性。
图 4展示了不同的采样间隔下3种匹配方法的准确率差异，RNCMM模型的匹配准确率比Seq2Seq模型和Linear+HMM算法更高。随着采样间隔增大，3种匹配方法的精确率和召回率都有所下降，但与Linear+HMM算法相比，RNCMM模型和Seq2Seq模型总体变化较为平稳，RNCMM模型比HMM算法更具稳健性。由表 1可知，当采样间隔从30 s增加到240 s，Linear+HMM算法精确率急剧下降了48.61%，而RNCMM模型和Seq2Seq模型的精确率仅分别下降了11.77%和7.77%。注意，当采样间隔为30 s时，Linear+HMM的召回率略优于RNCMM，而明显优于Seq2Seq。这是因为HMM算法是当前高频轨迹匹配技术中最成熟的一种，且本文利用HMM算法[10]标注原始轨迹数据(15 s采样间隔)的真实行驶路径。但随着采样间隔增大，RNCMM在匹配精度上表现出更大的优势。图 5展示了不同的采样间隔下RNCMM模型与两种变体的准确率差异，RNCMM模型的匹配精确率和召回率均最高，而RNCMM-noConst模型的匹配准确性最差。如，当采样间隔为240 s时，RNCMM的精确率和召回率比RNCMM-noAttn的分别增加了1.71%和2.91%，对比RNCMM-noConst模型，分别增加了4.13%和7.66%。这是因为注意机制可有效捕捉轨迹序列的长程依赖关系。约束掩模层引入低频轨迹中采样点的先验知识，其基于距离和方向指标来为每个路段赋予一定的权重值，轨迹采样点更有可能匹配到有限的候选路段而非整个路网空间，有效提高匹配准确率。图 5 RNCMM模型不同变体的准确性
不同的重采样率下不同算法的匹配效率见表 2。可知RNCMM模型和Seq2Seq模型的匹配速度明显优于Linear+HMM算法。因为RNCMM模型和Seq2Seq模型将轨迹编码为潜在表示向量，计算机对向量的计算效率比坐标数值更高。此外，RNCMM模型和Seq2Seq模型都只需要对神经网络进行前向计算，而HMM算法需要进行大量的动态规划计算。
随着重采样率的增加，Seq2Seq模型的执行时间略微减少，RNCMM模型的执行时间小幅度增加，Linear+HMM算法的执行时间急剧增加。因为Seq2Seq模型需要预测的缺失点减少，而HMM需要匹配的点增多。RNCMM的约束掩膜层需要搜索低频采样点的候选路段并计算其权重值。重采样率较高意味着需要在构建约束掩膜层时计算更多采样点候选路段的权重值。将重采样率设置为25%，研究关键超参数对模型匹配精度的影响。如图 6所示，当隐藏状态维度、多任务权重值δ和网格边长分别设置为512、0.5和50 m时，RNCMM模型的匹配精确率最高。隐藏状态维数过高会导致模型待训练参数过多，计算复杂度高，而维数过低又会导致模型欠拟合。图 6(b)显示多任务权重值δ设置为0.5时，模型的性能最佳，此时模型可从路段ID和方向的预测任务中取得良好的平衡。图 6(c)显示网格边长为50 m时，模型的精确率最高，损失值最小。网格变小，大量的网格单元会增加模型训练的复杂性，性能也会变差；而网格变大，粗糙的表示可能会损失轨迹的部分运动细节，降低匹配准确率。本文提出了一种顾及路网约束的深度地图匹配模型，将低频轨迹映射为高频的匹配路径。与HMM算法相比，基于Seq2Seq架构的RNCMM模型只需要对神经网络进行前向计算，无须在相邻采样点间大量搜索最短路径，显著提升了匹配效率。此外，基于距离和方向差异构建的约束掩膜层，为研究区域内所有路段赋予相应的权重值，有助于将采样点匹配到有限的候选路段而非整个路网空间，从而提高模型的匹配准确率。本文在真实的轨迹数据集上进行试验，与Seq2Seq模型和Linear+HMM算法相比，RNCMM模型的匹配准确率和效率均较高。尤其当轨迹的采样间隔较长时，RNCMM模型的匹配准确率显著提升。解决低频轨迹数据的地图匹配问题，对许多应用具有重要的意义。但不足的是，RNCMM模型的匹配效率介于两种对比算法之间。未来计划利用路网的拓扑关系和用户偏好提高匹配性能。
作者简介：钟青岑(1998—),女,硕士,主要研究方向为轨迹数据分析与挖掘。E-mail:qingcen＿zhong@whu.edu.cn通信作者：向隆刚。E-mail:geoxlg@whu.edu.cn
本文暂时没有评论，来添加一个吧(●'◡'●)