基于粒子滤波的行车轨迹路网匹配方法
摘要：行车轨迹是一种时间序列的地理空间位置采样数据，而传统的轨迹—路网匹配方法主要以全局或局部寻优的方式建立轨迹—路网匹配关系，影响了时空场景中数据的匹配计算过程的相对独立性。针对这个问题，本文基于粒子滤波(ParticleFilter,PF)原理建立行车轨迹与道路网络之间的匹配关系。首先，沿轨迹中车辆运动方向在道路网络中搜索邻近道路节点，在与道路节点拓扑邻接的道路弧段上初始化随机生成粒子，根据轨迹中车辆运动模型将粒子沿所在道路弧段移动;然后，基于PF原理计算各时刻粒子运动状态及与行车轨迹采样点之间的距离误差，根据高斯概率密度函数计算粒子权重并利用随机重采样方法进行粒子重采样，迭代更新粒子运动状态;最后，计算与搜索到的道路节点拓扑邻接的每条道路弧段中累计粒子权重，通过各道路弧段累计权重计算轨迹—路网匹配关系。以行车轨迹进行实验表明，利用本文方法可以通过粒子时空变化反映采样点的移动，行车轨迹—路网匹配结果的正确率大于85%，能够实现行车轨迹和路网的准确匹配。
本文源自地球信息科学学报,2020,22(11):2109-2117.《地球信息科学学报》主要刊登地球系统科学及其相关边缘交叉学科的新研究成果，主要包括前瞻性、创新性强的科学研究论文以及与国民经济、技术研究开发紧密相关，应用价值较高的学术论文。本刊还辟有研究通讯、前沿探索、科技开发、综述、学术动态等相关栏目。热忱欢迎国内外学者踊跃赐稿。
1、引言
装备有GNSS设备的车辆在行驶过程中会得到时间序列上地理位置变化这一轨迹数据。这些行车轨迹尤其是沿城市道路行驶的轨迹数据蕴含了丰富的居民交通出行、道路通行情况等信息，对于移动地理对象建模、地理规律发掘等方面具有重要意义[1,2,3]。通过行车轨迹—路网匹配建立行车轨迹与道路网络之间的语义关联则是进行深入的分析或知识挖掘的基础。因此，有必要寻求高效的行车轨迹—路网匹配方法，准确地建立行车轨迹与道路网络之间的匹配关系，为车辆运动信息快速提取与建模提供基础，进而为智慧城市建设提供有效的决策支持[4,5,6,7,8]。
现有行车轨迹—路网匹配方法可根据匹配过程中采样点的时空分布分为全局匹配和局部/增量匹配2类[2,9]。
(1)轨迹—路网的全局匹配方法[10,11,12,13,14]以完成地理位置采样的轨迹数据为研究对象，通过数据后处理方法，提取轨迹中几何、语义、距离权重、个性偏好等特征，将轨迹数据匹配到道路网络。Yin等[10]将轨迹中采样点到道路弧段的距离作为道路弧段的权重，利用最短路径方法计算加权道路图中的最短路径，将其作为轨迹-道路匹配结果，高需等[11]则以用户历史轨迹中的个性偏好作为权重因子进行路网匹配。Nikolić等[12]对轨迹数据滤波并通过聚类和位置投影的方式建立轨迹采样点与道路节点和道路弧段的关联关系，构建轨迹—路网候选匹配集，然后根据基因遗传算法(GenericAlgorithm,GA)选取最佳路网匹配结果。Lou等[13]与李清泉等[14]根据轨迹中几何和拓扑等特征构建最短路径候选匹配集，然后通过轨迹采样点之间的时间、空间、速度等约束条件，构建轨迹—路网匹配关系。这类方法以事后推定的方式计算轨迹—路网匹配关系，需要顾及整个轨迹数据特征，能够处理长时间间隔的路网匹配问题，但方法计算速度较慢，一般用于离线地图匹配。
(2)轨迹—路网的局部/增量匹配方法[9,15,16,17,18,19]基于轨迹数据的时空采样过程，建立轨迹—路网局部匹配关系。Brakatsoulas等[17]基于自由空间(FreeSpace)理论计算轨迹曲线与道路网络之间的Fréchet距离，根据轨迹和路网的局部相似的几何特征性进行增量式轨迹—路网匹配。针对轨迹采样点之间的时空连续特征，Newson等[18]和Song等[19]根据隐马尔可夫模型(HiddenMarkovModels,HMM)计算轨迹中的采样点与道路网络之间的概率匹配关系，以采样点到相邻道路弧段的距离和道路中不同采样位置之间的最短路径计算HMM的发射概率和转移概率，得到轨迹与道路网络的匹配结果。Liu等[9]针对基于HMM的路网匹配方法中存在的标记偏置问题，提出时空条件随机场(SpatialandTemporalConditionalRandomField,ST-CRF)方法，训练路网匹配特征函数权重参数，通过HMM中类似的解码方法计算轨迹-路网匹配结果。这类方法利用轨迹的局部特征进行路网匹配，计算速度较快，通过已匹配路网局部/增量延伸，最终得到全局最优匹配结果，可用于在线地图匹配，但匹配结果容易受到轨迹噪声的影响，或依赖“贪心算法”策略寻找最优解。
车辆在地理空间运动产生的时空位置记录，是一个动态的地理位置采样过程的结果，而粒子滤波(ParticleFilter,PF)作为一种序贯蒙特卡罗(SequentialMonteCarlo)方法，具有一定的时空模型模拟能力[20,21]，能够根据上一时刻观测值、当前时刻模型模拟值与观测值，通过粒子重采样和权重更新优化当前模型模拟结果，可处理轨迹中的噪声并减少轨迹—路网匹配过程中对已匹配结果准确性的依赖，因此可利用PF方法对行车轨迹中车辆的时空运动过程进行模拟，建立行车轨迹—路网的匹配关系。基于此，本文利用PF原理对行车轨迹中车辆的时空运动过程进行建模，在拓扑关联的道路弧段中生成粒子，构建行车轨迹与道路网络的匹配方法，并通过行车轨迹为研究对象，对方法的可靠性和准确性进行实验和分析。
2、粒子滤波与轨迹—路网匹配
2.1粒子生成
本文以行车轨迹采样点邻近的道路节点拓扑关联的道路弧段为粒子生成区间，所有粒子均位于相邻道路弧段，是一个沿道路线性度量空间分布的二维空间采样点，其中行车轨迹中采样点和相邻道路弧段的关系表示如下：
(1)假定沿着行车轨迹S中车辆运动方向，与轨迹采样点Si(xi,yi)相邻近j个道路节点N{N1,N2,,Nj};
(2)与道路节点Nk∈N相邻的l个道路弧段L{L1,L2,…,Ll}中，存在一条道路弧段Lm∈L，其中每条道路弧段Lm由n个顶点p{p1,p2,…,pn}组成;
在PF过程中，需要在粒子采样空间生成o个随机粒子q{q1,q2,…,qo}。为使得生成粒子具有随机性，粒子的生成需要满足2个条件：(1)粒子q在l个道路弧段L中产生的概率具有随机性;(2)粒子q在道路弧段Lm∈L的几何坐标具有随机性。
因此，可通过随机数生成索引m∈[1,2,…,l]从L中选取道路弧段Lm。然后，根据随机长度比例r∈[0,1]从Lm中生成粒子qkLm，如图1所示。详细步骤如下：
图1粒子的生成
(1)依次计算道路弧段Lm中相邻顶点{pmi,pmi+1}组成的子弧段Lmi的长度SLmi，如式(1)所示，式中Length(·)为长度计算函数。
(2)计算由弧段起点至弧段顶点pmi+1的子弧段ALmi累计长度比例ASLmi，如式(2)所示。
(3)根据随机长度比例r，计算粒子坐标qkLm(r)，如式(3)所示。
(4)最终得到沿道路网络弧段线性度量空间随机分布的初始化随机粒子q，如式(4)所示。其中k为粒子索引，生成的粒子满足条件(1)和条件(2)随机性的要求。
2.2行车轨迹—路网匹配
在传统的PF方法中，粒子随机分布在研究区域中，并随着行车轨迹采样点的状态变化不断更新，从而更新采样点的位置坐标。而在本文行车轨迹—路网匹配方法的计算过程如下：
(1)从车辆运动产生的行车轨迹采样点出发，搜索邻近的道路节点，根据道路节点拓扑邻接的道路弧段初始化产生随机粒子;
(2)通过行车轨迹中车辆运动模型更新粒子在道路弧段中的位置，利用粒子与下一时刻轨迹采样点的地理位置计算粒子权重，并统计每条拓扑邻接道路弧段的粒子权重，进行粒子重采样，根据行车轨迹采样时刻迭代更新轨迹采样位置与粒子状态;
(3)当搜索到新的邻近道路节点时，计算各条道路弧段的累计粒子权重，计算累计粒子权重最大的道路弧段作为匹配道路弧段;
(4)以道路节点为匹配关系分界线，更新行车轨迹与路网的匹配关系，返回步骤(1)并根据新的道路节点及拓扑邻接道路弧段集合自动生成随机粒子采样，不断迭代直至车辆完全停止运动。行车轨迹—路网匹配算法的流程如图2所示。
图2基于粒子滤波的车行轨迹—路网匹配算法流程
基于PF原理的行车轨迹—路网匹配方法，假定输入行车轨迹S，轨迹中车辆匀速运动速度为v，运动模型过程的噪声标准差为ς，同时，利用高斯概率密度函数作为粒子权重函数，其标准差σ表示高斯函数的带宽，将粒子与轨迹采样点之间的距离作为函数输入，计算得到粒子权重w，此外，随机粒子个数为o，道路网络及道路节点和弧段Road(N,L)，行车轨迹采样点与道路节点的搜索距离阈值为d。在这个过程中，在相邻轨迹采样点之间的轨迹中车辆运动模型可以假设为一个匀速运动的过程，因此，可通过计算当前轨迹采样点及其之前时刻轨迹采样点之间的轨迹片段平均速度，将其作为PF方法中车辆运动模型的速度输入，对粒子运动情况进行模拟，此外，如果道路网络中不同等级道路弧段的限速信息已知，可直接将其作为车辆运动模型的速度输入。运动模型如式(5)所示。
式中：St为轨迹采样点在tt时刻坐标;θ为车辆的运动方向(与正北方向顺时针转角);v为运动速度;;S͂t+1为tt+1时刻轨迹采样点的位置预测。粒子生成与更新算法过程如下：
(1)搜索与行车轨迹中采样点Si距离小于d的道路网节点NSi，并根据NSi查找道路网络中拓扑邻接的道路弧段LSi，在LSi上初始化产生o个随机粒子。
(1)如果是首次初始化粒子，则准备开始PF过程模拟;
(2)否则，统计每条邻接道路弧段LSi的累计粒子权重，将权重最大的道路弧段作为对应行车轨迹片段的匹配道路弧段。
(2)根据轨迹中车辆运动方向，根据采样时间先后顺序从行车轨迹中顺序选取采样点Si;
(3)根据PF原理和轨迹中车辆运动模型，在邻接道路弧段LSi中更新粒子状态，其中，粒子在轨迹中的运动存在标准差ς的随机噪声;
(4)计算粒子与行车轨迹采样点的距离D，根据式(6)计算粒子权重w
(5)归一化权重，并对粒子重采样;
(6)重复步骤(1)、(2)(3)，直至采样点Si以距离d搜索到新的道路节点，则返回步骤(1)。
其中，粒子重采样方法为随机重采样，通过不断迭代选择权重较大的粒子作为新的粒子，然后利用车辆运动模型计算下一时刻粒子状态。PF粒子权重的影响因素主要为轨迹采样点在不同时刻的位置以及粒子权重函数式(6)。在该过程中可能会存在粒子退化现象，但是由于本文方法中行车轨迹采样点在每条道路弧段中移动时间较短，并且在道路节点处重新生成粒子，因此，粒子退化现象对本文方法的影响较为有限。
3、行车轨迹—路网匹配实验结果与分析
3.1实验数据
本文采用行车轨迹为实验对象，由两条长时间序列采集的行车轨迹组成。其中，行车轨迹的长度约为102km，轨迹采样点共计1838个;水平采样精度为10m，采样时间间隔为10s。具体情况如表1所示。
表1车行轨迹采样信息
研究区域中道路数据和辅助遥感影像来自于该区域的基础地理数据库，研究区域面积约为55km2，道路中路网分布比较复杂，在部分区域路网密度较高。数据空间分布如图3所示。
3.2实验结果与分析
3.2.1数据预处理与参数选择
行车轨迹—路网匹配过程中，首先需要对数据进行拓扑检查，根据道路数据构建具有弧段和节点结构的道路网络，同时对行车轨迹进行离群值粗差剔除等预处理，然后根据PF原理实现行车轨迹与路网的匹配。其中，相关参数的选取方法如下：
(1)计算每个道路节点及其最邻近道路节点之间的距离，以所有道路节点最邻近道路节点距离平均值的2倍，作为轨迹采样点搜索邻近道路节点的范围d的参考值，在本文实验中d的值为70m;
(2)假定在相邻轨迹采样点之间车辆的运动速度v为匀速，由于本文道路数据中未提供道路限速信息，因此车辆运动速度可通过当前时刻和之前时刻轨迹采样点的距离及其时间间隔计算得到，将行车轨迹中相邻轨迹采样点之间距离平均值的0.5倍作为运动模型的过程噪声标准差ς的参考值，在本文实验中ς为10m;
(3)以道路网络中道路弧段长度的平均值作为高斯概率密度函数标准差σ的参考值，在本文实验中σ的值为1000m;
(4)根据道路网络中每个道路节点的复杂程度作为随机粒子个数o的参考依据，在道路节点复杂程度较高的道路数据中设置较大的粒子数目，反之亦然。在本文实验中与道路节点邻接的道路弧段数目以4条为主，因此可设置随机粒子个数o为100。
3.2.2粒子的随机生成
在行车轨迹中采样点滤波初始时刻，粒子在道路弧段中是随机生成的，如图4所示，假定一条道路弧段由9个顶点组成(绿色小圆点)，从弧段起点到弧段终点，根据式(1)和式(2)计算各个顶点组成的子弧段在道路弧段中的累计长度比例，分别为0%、21%、31%、43%、55%、67%、76%、87%、100%(绿色字体)，初始时刻在道路弧段中随机生成5个粒子，在道路弧段中的长度比例分别为17%、38%、52%、80%、94%(红色字体)，则根据长度比例以式(3)在相应的子弧段中计算粒子在道路弧段中的几何位置(红色大圆点)。由图可见，粒子能够利用随机生成的长度比例，根据粒子坐标计算公式，分别分布在道路弧段的不同子弧段中。
图3研究区域中车行轨迹与道路网络空间分布
图4基于道路弧段的粒子生成
注：绿色数字为各个顶点组成的道路子弧段累计长度比例，红色数字为随机粒子组成的道路子弧段累计长度比例。
3.2.3粒子移动与路网匹配
根据邻近道路节点拓扑关联的道路弧段生成粒子，然后利用PF原理对行车轨迹采样点和粒子每个时刻的状态进行更新，最后根据累计粒子权重匹配道路弧段，过程如图5所示。
由图5可见，在初始时刻1，轨迹采样点(红色大圆点)搜索到道路节点有4条邻接道路弧段，分别在每条道路弧段中生成粒子集(其他颜色小圆点)，在时刻2，车辆位置更新后轨迹采样点移动到下一时刻，道路弧段中粒子的数量和位置得到更新，在时刻3，随着轨迹采样点位置的更新，粒子的空间分布发生较大变化，开始集中在待匹配道路弧段，在时刻4，粒子则集中在了待匹配道路弧段，这条弧段中的粒子数量显著增多，进而可以通过每条道路弧段的累计粒子权重判断出行车轨迹—路网的匹配结果。由图可见，本文方法能够根据PF原理，更新不同行车轨迹位置采样时刻的粒子在道路弧段中的位置，并通过这个过程，计算待匹配道路弧段的累计粒子权重，实现行车轨迹与道路网络的匹配。
图5轨迹采样点不同时刻粒子位置的变化
3.2.4行车轨迹—路网匹配
为了对本文方法路网匹配能力进行实验对比，首先，基于距离判别法将轨迹点与邻近道路网络弧段进行距离投影，根据轨迹点与邻近道路弧段的距离计算其匹配关系，对行车轨迹1和行车轨迹2进行实验，结果如图6所示。
在图6基于距离判别方法的实验结果中，黑色实线为与行车轨迹正确匹配的道路弧段，灰色实线为与行车轨迹错误匹配的道路弧段。由图可见，行车轨迹1和行车轨迹2均匹配到了邻近道路弧段，但匹配结果在道路节点处存在较多错误匹配，导致行车轨迹-路网匹配结果在时间和空间上存在一定的不连续性，与轨迹中车辆运动情况存在不一致。
利用本文基于PF的行车轨迹-路网匹配方法对研究区域中行车轨迹和道路网络进行匹配，实验结果如图7。图中黑色实线为与行车轨迹正确匹配的道路弧段，灰色实线为与行车轨迹错误匹配的道路弧段，灰色虚线为与行车轨迹未匹配的道路弧段。由图可见，行车轨迹-路网匹配结果覆盖了大部分区域，而在局部路网密度较高的复杂通行区域存在一定的错误匹配结果，本文方法能够从行车轨迹中计算出轨迹-路网匹配关系。
本文以用“正确匹配长度/轨迹总长度”计算行车轨迹-路网匹配结果的正确率。对实验结果进行统计，分别从匹配长度、正确匹配、错误匹配、未匹配进行统计，结果如表2所示。
在基于距离判别法的实验结果中，行车轨迹1的正确匹配路网长度为64944m，路网的匹配准确率为84.24%，而行车轨迹2的正确匹配路网长度为21252m，路网的匹配正确率为83.68%，行车轨迹1和行车轨迹2的路网匹配长度均比实际行车轨迹长度大，因此，路网匹配结果中均存在明显的过匹配现象;在本文方法实验结果中，行车轨迹1匹配路网长度为71220m，其中正确匹配路网65921m，未匹配路网长度8882m，路网匹配正确率为85.51%，行车轨迹2匹配路网长度为25057m，其中正确匹配路网23621m，未匹配路网长度2578m，路网匹配的正确率为93.01%。由表可见，本文方法能够在较为复杂的道路网络中建立行车轨迹-路网的正确匹配关系，对85%以上的行车轨迹建立匹配关系，同时能够使匹配结果具有时空连续性。
图6基于距离判别法的车行轨迹—路网匹配结果
图7本文基于PF方法的车行轨迹-路网匹配结果
表2车行轨迹-路网匹配结果统计
通过实验结果可见，本文方法基于PF原理构建行车轨迹-路网匹配方法，使得路网匹配方法在计算过程中不依赖于全局或局部/增量式匹配过程的寻优条件，使得计算过程具有相对独立性，具有较高的匹配准确率并且行车轨迹-路网匹配结果具有路径连续性，与车辆实际运动情况较为一致。
4、结论
行车轨迹—路网匹配方法往往需要顾及行车轨迹中采样点的时空连续特征。现有行车轨迹—路网匹配方法利用采样点的全局或局部时空连续特征，依赖“贪心算法”寻优策略或易受轨迹噪声影响，获得的路网匹配结果准确性和时空连续性存在一定的不足。本文基于PF原理通过3个方面构建行车轨迹—路网匹配关系：(1)利用行车轨迹的采样点邻近道路网络弧段随机生成粒子;(2)通过轨迹中车辆运动模型计算不同轨迹采样时刻下粒子的运动状态，根据粒子与轨迹采样点之间的距离误差计算粒子权重，进行粒子重采样并更新粒子状态;(3)根据每条道路弧段中的累计粒子权重对行车轨迹与道路网络进行匹配。实验表明，本文方法对长度约为102km的较长时间采样序列的行车轨迹进行路网匹配，路网匹配结果的正确率大于85%，能够基于PF原理将行车轨迹与道路网络进行准确地匹配，使得匹配过程具有相对独立性，同时保持匹配结果的时空连续性。本文方法具有一定的实时运算能力，可对较大研究区域中行车轨迹数据通过并行运算方式对本文方法的在线行车轨迹-路网匹配进一步研究。
参考文献：
[1]吴华意,黄蕊,游兰,等.出租车轨迹数据挖掘进展[J].测绘学报,2019,48(11):1341-1356.
[2]高文超,李国良,塔娜.路网匹配算法综述[J].软件学报,2018,29(2):225-250.
[5]高强,张凤荔,王瑞锦,等.轨迹大数据:数据处理关键技术研究综述[J].软件学报,2017,28(4):959-992.
[6]张健钦,李明轩,段颖超,等.一种改进的快速浮动车地图匹配方法[J].测绘通报,2017(1):87-92.
[7]刘张,王心迪,闫小勇.面向复杂城市道路网络的GPS轨迹匹配算法[J].电子科技大学学报,2016,45(6):1008-1013.
[8]吴涛,向隆刚,龚健雅.路网更新的轨迹—地图匹配方法[J].测绘学报,2017,46(4):507-515.
[11]高需,武延军,郭黎敏,等.基于偏好的个性化路网匹配算法[J].软件学报,2018,29(11):3500-3516.
[14]李清泉,胡波,乐阳.一种基于约束的最短路径低频浮动车数据地图匹配算法[J].武汉大学学报·信息科学版,2013,38(7):805-808,885.
[15]朱递,刘瑜.一种路网拓扑约束下的增量型地图匹配算法[J].武汉大学学报·信息科学版,2017,42(1):77-83.