基于多准则粒子滤波算法的车辆轨迹重构

2022-09-23唐进君王凯叶峻青

铁道科学与工程学报 2022年8期

唐进君，王凯，叶峻青

(中南大学交通运输工程学院，湖南长沙 410075)

车辆轨迹数据兼具时空属性，能够为许多研究提供数据支撑，如行程时间估计[1]、车辆排放估计[2]和OD模式估计[3]等。近些年，随着位置跟踪和存储技术的快速发展，人们已经能够获取大量的车辆轨迹数据，但由于设备条件的限制，这些轨迹数据中仍存在一些不完整的轨迹。不完整的车辆轨迹会极大地限制后续研究对轨迹数据的应用[4]。因此，如何重构车辆轨迹数据一直是交通及相关领域学者研究的热点问题。车辆轨迹数据通常由2类传感器采集得到[5]：移动传感器和固定传感器。移动传感器数据包括GPS数据、智能卡数据等；固定传感器数据包括地磁检测数据和自动车牌识别(ALPR)数据。其中ALPR数据相较于其它交通采集源具有易获取、数据格式丰富、采集持续时间长等优点。目前基于ALPR数据进行轨迹重构，国内外学者已经进行了一系列的研究。FENG等[6]采用粒子滤波器作为框架，所有候选轨迹均被视作一个初始粒子，将轨迹时空校正因子作为粒子更新的状态输入粒子滤波器，粒子滤波器的输出即为重构轨迹；YANG等[7]在FENG等[6]研究的基础上，将路径流模型与粒子滤波器模型相结合，融合了宏观角度和微观角度的收益，对车辆轨迹进行了更准确的重构；RAO等[3]在先前研究[6-7]的基础上，通过引入时间地理学中的时空棱镜概念缩小了轨迹搜索的范围，提高了算法运行的效率，使其更加适应大规模网络场景；王龙飞[8]通过把基于限速的拓扑寻优法(topologicaloptim iza‐tion based on speed constraint,SC+TO)与TOPSIS法相结合进行决策完成了车辆出行轨迹的提取及重构。阮树斌等[9]提出了一种k则最短路径(KSP)和灰色关联法(GRA)的组合算法，KSP算法用于搜索前k条最短路径组成候选路径集，GRA算法用于从路径集决策出最优的重构路径。徐建闽等[10]提出了一种基于梯度提升决策树(Gradient Boosting Decision Tree,GBDT)的车辆轨迹重构方法，通过挖掘车牌识别数据中与用户路径选择相关的变量并利用这些变量组成的数据集进行训练还原丢失路径；QI等[11]在已有研究[3,6-9,12]基础上提出了路径长度、道路等级、交叉口个数、转弯次数、行程时间一致性和路径偏好6个决策指标，这些决策指标作为自编码器模型中的多个属性以重构不完整的车辆路径。上述方法确定的决策特征大多带有一定的主观因素，主观因素的存在使得该类决策特征忽略了少数人的出行偏好，降低了重构的稳定性。徐建闽等[10]提出的GBDT算法将车牌识别数据中与用户路径选择相关的变量(如时间窗、进口方向、下一目标交叉口等)作为决策特征，虽然解决了决策特征带有主观因素的问题，但该方法所提出的决策特征存在可解释性差、不同区域之间不统一等缺点。本文针对上述重构方法的局限性，考虑主观因素和客观因素的差异对决策特征进行分类，称含主观因素低的决策特征为基础校正因子，含主观因素高的决策特征为拓展校正因子。为减小拓展校正因子主观因素高对结果稳定性的影响，在拓展校正因子的重采样过程设置了概率参数，提出了一种粒子滤波框架下的多准则城市车辆轨迹重构方法，在保留决策特征可解释性的同时增加了重构的稳定性。首先，对重构算法的结构和功能进行了介绍；然后，详细阐述了重新设计后的决策特征；最后，结合实际路网数据验证了改进算法的有效性。

1 粒子滤波框架下的多准则城市车辆轨迹重构方法

1.1 问题描述

车辆轨迹重构问题可根据图1(a)来进行说明。图1(a)是一个4×4的网络，其中方形节点的路口安装了ALPR设备，圆形节点的路口没有安装，ALPR设备能直接获取车辆牌照、车辆经过路口时间等数据。当车辆在网络中行驶时，局部路径可以通过ALPR设备观测到。假设路口1，5，6，11的设备依次观测了车辆a，车辆a的路径链可表示为{1，5，6，11}。由于ALPR设备在该网络的覆盖率较低，车辆a在节点6和11之间的行驶轨迹没有被观测到。节点6和11之间共存在22种轨迹重构方案。随着网络规模的增大(如图1(b)所示)，轨迹重构方案也会变得更加复杂。因此，如何确定重构方案是解决车辆轨迹重构问题的关键。本文中的轨迹丢失主要针对路口检测设备缺失造成的丢失。

图1 车辆轨迹重构问题示意图Fig.1 Schematic diagram of vehicle trajectory reconstruction

1.2 算法结构

为实现对不完整轨迹的重构，本文的重构方法主要包含3个模块，分别是：断点识别、轨迹搜索和改进后的粒子滤波模型，如图2所示。以下对3个模块的功能进行逐一介绍。

图2 车辆轨迹重构算法结构Fig.2 Structure of vehicle trajectory reconstruction algorithm

1.2.1 断点识别

“断点”指的是车辆轨迹序列中非连续路口之间的部分，一旦轨迹序列中存在断点，那么该轨迹就是不完整轨迹。如图1(a)所示，假设提取到车辆a的路径链为{1，5，6，11}，通过遍历其中的路口能发现路口6与11非连续形成断点。因此，断点识别的主要功能在于找到不完整轨迹中需要重构部分的起终点，当一条轨迹存在多个断点时，以断点出现的顺序进行重构。

1.2.2 轨迹搜索

为了搜索断点部分的可能轨迹并提高搜索的效率，本文在该部分采用Yen算法[13]。Yen算法由Yen在1971年提出，又名k则最短路算法，在轨迹搜索领域一直被广泛运用[14]。与DFS算法不同的是，Yen算法仅能求出2点间的前k条最短路径而非全部路径。然而，通过实验发现选用Yen算法进行轨迹搜索在保证重构准确率的同时还提高了重构算法的运行效率。

1.2.3 改进的粒子滤波器

本文在原有粒子滤波器[6]的基础上进行了校正因子的修正。首先将上一模块搜索到的候选轨迹作为初始粒子，利用车辆轨迹的5个时空校正因子，对这些粒子的真实状态空间概率进行更新。这些校正因子分别是行程时间一致性因子、可测性准则因子、路径尺寸因子、转弯次数因子和取的，定义为基础校正因子；后面的3个校正因子是考虑驾驶行为特征，包含了主观因素，定义为拓展校正因子。粒子滤波器的步骤如下。

步骤1：初始化粒子集(x1,x2,…,xI)

将搜索到的候选轨迹x1,x2,…,xI作为初始粒子集，P(x1),P(x2),…,P(xI)表示粒子的先验概率。在没有历史轨迹数据的情况下，各粒子的先验概率被设置为1/I，其中I表示粒子的数量。

步骤2：重要性采样

对于i=1,2,…,I，假定粒子的先验分布服从由上一个的重要性采样得到的密度函数。5个重要采样过程基于5个校正因子。拓展校正因子的重采样过程在开始前需要进行一次轮盘赌法，轮盘赌法的概率α是事先设定好的，3个拓展校正因子的概率分别设为α，β和γ。若轮盘赌法的结果在所选择的概率区间内，那么所有粒子将执行该拓展校正因子的重采样过程；否则，不执行。基础校正因子的重采样过程在开始前则不需要进行轮盘赌法，直接执行后面的内容。

在第1个重要性采样(行程时间一致性)中，初始粒子质量服从均匀分布，可以表示为表示行程时间一致性概率密度函数，后验概率分布服从

行程时间一致性的权值更新方程为：

其中，表示行程时间一致性更新后可能轨迹i的非标准化权值；表示可能轨迹i的初始先验权值，开始时均为1；yt:t+Δt代表从时间t到时间t+Δt收集的客观数据或经验标准，其中t是开始收集数据的时间，Δt是仅取决于车辆轨迹重构计算区间的变量；表示行程时间一致性下可能轨迹i的状态空间；表示初始情况可能轨迹i的状态空间；表示基于行程时间一致性的可能轨迹i的概率；表示从先验数据到行程时间一致性状态空间的转换概率，对于静态计算过程，可能的轨迹不存在空间或时间的过渡关系，故状态转移概率可以视为常数；表示先验概率密度函数，该函数可以看作是一个常数概率密度函数。

为了简化计算过程，同原粒子滤波模型，没有考虑粒子权重的归一化计算；相应地，使用粒子聚集方程计算，其中的粒子权重为更新后的粒子权重。粒子聚集方程表示为：

其中，表示行程时间一致性计算后可能轨迹i的粒子聚集数；N表示粒子总数目。

在第1次重要性采样后，还需要进行基础校正因子的重采样和若干拓展校正因子的重采样。第一个重要性采样过程称为步骤2.1，计算过程如下：步骤1-步骤2.1-步骤2.2-步骤2.3-步骤2.4-步骤2.5-步骤3，具体流程如图2所示。

步骤3：输出真实轨迹

经过若干次重采样过程后，粒子聚集数最大的可能轨迹作为最优轨迹输出。

2 粒子滤波器中的时空校正因子

2.1 校正因子1：行程时间一致性

区别于之前的研究[6]，本文采用行程时间分布作为一致性评价准则，该准则需要拟合所有可能轨迹在断点时间区间内的行程时间分布函数(本文采用高斯混合模型)，再将真实行程时间代入各分布函数中得到结果，如式(3)所示。

其中，表示基于行程时间一致性，可能轨迹i的后验概率；表示2个ALPR设备间可能轨迹i的平均行程时间；t'(AVI1,AVI2)表示2个ALPR设备间的真实行程时间；Fi(t)表示基于高斯混合模型，可能轨迹i的行程时间分布函数；

所有轨迹的初始权重相等，视作1/N，N为粒子总数。遵循式(3)的概率密度函数。可以看作是一个常数概率密度函数。

2.2 校正因子2：可测性准则

可测性准则是基于ALPR设备检测误差的逆向推理过程[5]。有2种原因可能导致ALPR设备没有检测到车辆：第1种原因是车辆通过了设置ALPR设备的路口，但由于设备检测错误而没有检测到车辆；另一种原因是车辆没有通过设置ALPR设备的路口。基于这2种原因，当2个ALPR设备间的可能轨迹i包含其他设置ALPR设备的路口或链路时，可以认为这些路口或链路上的ALPR设备在检测时出现了错误。

其中，表示基于可测性准则，可能轨迹i的后验概率；ε表示ALPR设备检测出错的概率；n表示可能轨迹i中包含其他设置ALPR设备的路口或链路的个数。

2.3 校正因子3：路径尺寸Path-Size

Path-Size这一概念在Path-Size Logit模型中提出[15]，主要用于解决路径选择行为中的路径重叠问题，尽管该模型有较多的拓展[16-17]，但这些拓展都是在式(5)的基础上进行的。在这个模型中，效用函数添加了一个称为路径尺寸(PS)的确定性修正项，PS定义为：

其中，PSin表示可能轨迹i的路径尺寸的大小；Γi表示所有组成可能轨迹i路段的集合；lk表示路段k的长度；Li表示可能轨迹i的长度；当路段k在轨迹j上时，δkj的值为1；当路段k不在轨迹j上时，δkj的值为0。若轨迹i与轨迹集Cn中的其他路径不重叠，则其PSin值为1。否则，与其他路径共享的路段越多，其PSin值越低。

当可能轨迹i的PSin值越低，该轨迹中的路段重叠指数越高，重叠指数高表示这些路段会被更多车辆驶过，该轨迹也越有可能成为真实轨迹。令服从式(6)中的概率密度函数。可以视作一个常数概率密度函数。

转弯次数校正因子、行驶距离校正因子[8]与路径尺寸校正因子具有相似的描述，即可能轨迹i的转弯次数/行驶距离值越小，该轨迹更可能被驾驶人选择，越有可能成为真实轨迹。故和服从的概率密度函数与式(6)形式一致，不同之处仅在于式(6)中的路径尺寸被替换成了转弯次数和行驶距离，和均可视作常数概率密度函数。

3 方法验证与结果评价

3.1 数据预处理

本文所做工作的数据来源于长沙市天心区五一广场附近ALPR设备所拍摄到的数据，数据的时间区间为2019年3月11日00:00至2019年3月17日24:00。本文在研究过程中选取了五一广场附近的22个安装了ALPR设备的路口，如图1(b)所示。

本文使用SQL Server和Matlab对数据进行预处理，数据集属性包含：车辆牌照(“湘AMXXXX”)、车辆类型(01或02；01是大车，02是小车)、车辆通过路口时ALPR设备记录的时间(“2019/3/14 10:33:52”)、车辆通过路口的编号、车辆所在车道的编号、车辆驶入路口的方向(1-4分别代表着：由东往西、由西往东、由南往北，由北往南)。由于图像识别技术的局限性，一些车辆的车牌号码无法被清晰地捕捉到，因此需要将这些未识别的记录从数据集中删除。另外，由于路口的红灯使得车辆在路口停留，某些设施识别的数据也可能是重复的。故需要从数据集中删除这些重复记录，重复记录具体指相邻的2条记录包括时间字段在内完全相同。

在数据预处理完成后，通过车牌号分类来提取车辆出行轨迹，最终得到的车辆轨迹形式为一个按车辆通过时间排序的路口编号列表。这样的轨迹可能是由车辆在一段时间内的多次出行组成的。在此基础上，还需要使用出行时间阈值B来分割该轨迹，这样才能保证每个列表中存储的都是车辆的单次出行。本文将单次出行定义为车辆连续通过2个路口的时间间隔不超过时间阈值B。如果时间间隔大于B，将较长的出行划分为2个较短的出行。阈值B可以通过式(7)确定：

其中，T是研究区域各路口间行程时间集合，T={t1,t2,t3,…,tn}，该集合通过统计车辆经过2个路口的差值来得到；t为可变时间阈值，本文将t设置为5m in。

3.2 轨迹重构与结果分析

首先从ALPR数据提取出车辆初始轨迹，由于所选取的研究区域的ALPR设备基本上覆盖了各主要路口，因此提取到的初始轨迹大多是完整的，验证集由这些完整轨迹组成。为测试所提出的轨迹重构算法的效果，假定部分路口未设置ALPR设备，例如，当覆盖率为70%时，会有30%的路口未设置ALPR设备，即7个路口；当覆盖率为50%时，会有50%的的路口未设置ALPR设备，即11个路口，以此类推。这些未设置ALPR设备的路口将从完整轨迹中剔除，从而生成丢失样本集。将丢失样本集代入算法中进行重构，重构结果与原轨迹一致则视作成功，准确率根据重构成功的轨迹数量与总重构的轨迹数量之比得到。为确定拓展校正因子最合适的概率参数，对概率α，β和γ：(0.1，0.1，0.1)、(0.1，0.1，0.2)、(0.1，0.1，0.3)、……、(1.0，1.0，1.0)，共1 000种参数组合进行实验。根据实验结果，将概率参数α，β和γ设置为准确率最高的参数组合(1.0，0.1，0.5)。

由于算法的稳定性需要多组实验结果来进行验证，因此选取一周7天7个早高峰6个晚高峰共13个时段的数据，每个时段的数据进行10次实验，算法可以得到130组结果。如图3所示，横轴表示实验序号，纵轴表示轨迹重构的准确率。路网ALPR覆盖率设置为40%～90%之间。

图3 车辆轨迹重构结果Fig.3 Vehicle trajectory reconstruction results

为了突出算法的有效性，进行如下几组对比实验。

1)将本文方法与TOPSIS算法及候选图算法进行比对。将每次实验设定为相同的条件用3种算法进行计算，得到图4的结果。

图4 70%覆盖率3种算法准确率对比Fig.4 Accuracy comparison of three algorithmsw ith 70%coverage

通过以上结果可以看出粒子滤波算法的结果最稳定，在70%ALPR覆盖率的路网中，平均准确率能达到94.8%，TOPSIS决策法次之，最短路径法结果波动最大。该结果说明对于重构车辆轨迹，本文提出的算法相较于TOPSIS决策法和最短路径法具有更高的准确率和稳定性，在实际应用中的效果更好。

2)探究3种算法在无检测数据路口个数、断点间距离、断点间行程时间递增的情况下，轨迹重构的准确率变化，结果如图5所示。

图5(a)是轨迹重构准确率与断点间距离的关系，随着断点间距离的增加，重构准确率有略微下降的趋势，当断点间距离为0m时(断点的起终点相同)，3种算法的重构准确率最低。这是因为当断点起终点相同时，可搜索到的轨迹数量会大大增加，从中确定重构方案将会变得十分困难。

图5(b)是轨迹重构准确率与断点间行程时间的关系，横坐标是断点间真实行程时间与最小行程时间之比，该比例能客观反映真实行程时间的相对长度，行程时间越长，重构的难度越大，准确率越低。主要原因在于：行程时间是轨迹重构的重要决策特征，随着行程时间的增大，与其匹配的轨迹重构方案的距离及包含路口个数都会增加，轨迹重构方案的数量会增大，重构真实的车辆轨迹会变得更加困难。与另外2种算法相比，本文提出的算法对于行程时间较长的断点仍能得到更准确的重构方案。

图5 不同影响因素对算法准确率的影响Fig.5 Influence of different factorson the accuracy of the algorithm

图5(c)是轨迹重构准确率与断点间无检测数据路口个数的关系，无检测数据路口数量越多，重构的难度越大，准确率越低。该现象出现的原因与图5(b)相似，主要是断点间无检测数据路口个数增多导致轨迹重构方案的数量增大，使得轨迹重构的难度增加。另外，从图中可以发现3种算法对于无检测数据路口个数较多的断点，其重构结果都较差，这将是算法改进的一个方向。

3)为了表示算法相较于原先粒子滤波算法做出的改进，将使用高斯混合模型与传统行程时间一致性准则的算法进行对比实验，得到图6的结果。