电动自行车轨迹简化与自适应地图匹配算法.pdf

近年来,随着全球定位系统(globalpositioningsystem,GPS)的大范围应用,越来越多的电动自行车装配了GPS 传感器,由此产生的海量轨迹数据是深入了解用户出行规律、为城市规划者提供科学决策支持等诸多应用的重要基础.但是,电动自行车上普遍使用的价格低廉的 GPS 传感器无法提供高精度的定位,同时,电动自行车轨迹地图匹配过程因以下原因更具有挑战性:(1)存在大量停留点;(2)高采样频率导致相邻轨迹点的距离较短;(3)电动自行车可行驶的路段更多,存在大量无效轨迹.针对上述问题,提出一种可自适应路网精度的电动自行车轨迹地图匹配方法 KFTS-AMM.该方法融合基于分段卡尔曼滤波算法的轨迹简化算法(KFTS),和分段隐马尔可夫模型的地图匹配算法(AMM).首先,利用卡尔曼滤波算法可用于最优状态估计的特性,KFTS 能够在轨迹简化过程中对轨迹点进行自动修正,使轨迹曲线变得平滑并减少了异常点对于地图匹配准确率的影响.同时,使用基于分段隐马尔可夫模型的地图匹配算法 AMM,避免部分无效轨迹对整条轨迹匹配的影响.此外,在轨迹数据的处理过程加入了停留点的识别与合并,进一步提升匹配准确率.在郑州市真实电动自行车轨迹数据的实验结果表明,KFTS-AMM在准确率上相对于已有的对比算法有较大的提升,并可通过使用简化后的轨迹数据显著提升匹配速度.关键词:地图匹配;轨迹简化;卡尔曼滤波;轨迹数据分析;隐马尔可夫模型;停留点中图法分类号:TP18中文引用格式:王东京,刘继涛,俞东进.电动自行车轨迹简化与自适应地图匹配算法.软件学报,2023,34(8):37933820.http:/ Simplification and Adaptive Map Matching Algorithm for Electric BicycleWANGDong-Jing,LIUJi-Tao,YUDong-Jin(SchoolofComputerScienceandTechnology,HangzhouDianziUniversity,Hangzhou310018,China)Abstract:Withthewideapplicationofglobalpositioningsystem(GPS),moreandmoreelectricbicyclesareequippedwithGPSsensors.Massive trajectory data recorded by those sensors are of great value in many fields,such as users travel patterns analysis,decisionsupportforurbanplanners,andsoon.However,thelow-costGPSsensorswidelyusedonelectricbicyclescannotprovidehigh-precisionpositioning.Besides,themapmatchingfortheelectricbicyclestrackdataismorecomplexandchallengingdueto:(1)manystaypointson electric bicycles trajectories;(2)higher sampling frequency and shorter distance between adjacent track points on electric bicyclestrackdata;(3)someroadsonlyopenforelectricbicycles,andtheaccuracyofmatchingissensitivetothequalityoftheroadnetwork.Tosolve those issues mentioned above,an adaptive and accurate road network map matching algorithm is proposed named KFTS-AMM,whichconsistsoftwomaincomponents:thesegmentedKalmanfilteringbasedtrajectorysimplification(KFTS)algorithmandsegmentedhidden Markov model based adaptive map matching(AMM)algorithm.Since Kalman filtering algorithm can be used for optimal stateestimation,thetrajectorysimplificationalgorithmKFTScanmakethetrajectorycurvesmootherandreducetheimpactofabnormalpoints*基金项目:工信部工业互联网创新发展工程(TC200802C,TC200802G);浙江省自然科学基金(LQ20F020015)收稿时间:2021-01-07;修改时间:2021-08-04,2021-10-08;采用时间:2021-11-17;jos 在线出版时间:2023-01-13CNKI 网络首发时间:2023-01-19软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(8):37933820doi:10.13328/ki.jos.006542http:/中国科学院软件研究所版权所有.Tel:[phone]on the accuracy of map matching by fixing the trajectory points automatically in the process of trajectory simplification.Besides,thematching algorithm AMM is used to reduce the impact of invalid trajectory segments on the map matching accuracy.Moreover,staypoints identification and merging step are added into the processing of track data,and the accuracy is further improved.Extensiveexperimentsconductedonthereal-worldtrackdatasetofelectricbicyclesinZhengzhoucityshowthattheproposedapproachKFTS-AMMoutperformsbaselinesintermsofaccuracyandcanspeedupthematchingprocessbyusingthesimplifiedtrackdatasignificantly.Key words:mapmatching;trajectorysimplification;Kalmanfiltering;trackdataanalysis;hiddenMarkovmodel(HMM);staypoints近年来,我国已经成为全球电动自行车生产和销售第一大国,同时,电动自行车也已经成为人们出行的主要交通工具之一.据统计,2018 年我国电动自行车的保有量已经达到了 2.5 亿1,随着 GPS 定位技术的不断成熟,越来越多的电动自行车被安装了 GPS 设备,由此获取到的海量轨迹数据为分析城市交通状况和用户出行规律提供了很好的基础2,3.地图匹配算法的任务是将 GPS 记录的轨迹匹配到交通工具实际经过的道路上,这是对轨迹数据进行深度分析和有效利用的必要步骤.但是,电动自行车上普遍使用的成本低廉的 GPS 传感器无法提供高精度的定位,因此往往无法从原始的轨迹数据中直接得知实际经过的准确路线.目前,学者对于地图匹配的研究已经有 20 多年的历史,专注于解决地图匹配问题的文献也有上百篇之多4.然而,现有的各类算法大多是研究机动车轨迹数据的匹配问题.对于电动自行车轨迹的地图匹配算法的相关研究还比较少.相比于机动车的轨迹数据,电动自行车轨迹数据具有以下 3 个特点.特点 1:电动自行车轨迹上存在大量停留点.特点 2:电动自行车轨迹采样频率高,行驶速度较慢,导致采样点距离较小,轨迹点密度相应增大.特点 3:电动自行车行驶路段更多,由于路网精度的限制,部分轨迹可能无法匹配到对应的路网上.p2p3p2p3p2 p3具体而言,特点 1 会导致地图匹配准确率的下降.停留点指轨迹上一组连续且相距较近的轨迹点,其产生原因分为两类:(1)由于停止或运动速度极慢;(2)由于车辆反复行驶过某区域3.这两类原因均会导致文献 4 中提到的不必要迂回的出现,从而降低匹配的准确率.例如,在图 1 中,当车辆在轨迹点与处行驶速度极慢,为两个停留点,由于 GPS 的测量误差5,与在道路 A 上的投影点前后顺序与道路 A 的方向相反,导致地图匹配算法计算出的路线为道路 A道路 B道路 C道路 D道路 A,与事实情况不符.p1p2p3p4道路 D道路 A道路 B道路 C道路段匹配路线轨迹点轨迹点到道路段的投影图1因停留点导致的轨迹上不必要的迂回文献 6 对 GeoLife7,8轨迹数据集中不同出行方式的轨迹进行了分析,认为自行车与步行出行方式的轨迹数据有更高的方向变化概率与停止概率.在真实场景中,机动车只有当等待红绿灯或处于交通拥堵路段时才会导致轨迹上出现停留点,但是电动自行车用户拥有更大的行驶自由,例如可以随意在路边停车、在某较小区域内反复行驶,从而产生更多的停留点.因此对电动自行车轨迹上的停留点进行预先识别与处理十分必要.特点 2 会显著地降低地图匹配算法的效率.电动自行车车速较慢,因此轨迹点更加密集,高峰时段下轨迹点密度会进一步提高.文献 9 将采样时间间隔在 1s 至 10s 之间的采样方式定义为高频采样,而时间间隔高于 2min的采样方式定义为低频采样.然而,这种定义方式只考虑了时间间隔,忽略了采样点在空间上的距离.当交通工具速度不同时,即使采样频率相同,也可能导致采样点空间距离相差很大.图 2(a)显示了一段郑州电动自行车轨迹,相邻轨迹点平均间距约为 60m、采样时间间隔约为 12s,图 2(b)显示了一段 CRAWDAD 数据集中旧金山出租车的轨迹10,相邻轨迹点平均间距约为 600m、采样时间间隔约为 30s.尽管电动自行车的采样频率约为机动车的3 倍,但是轨迹点密度却达到了机动车的 10 倍.在许多开源轨迹数据集中,机动车轨迹上的轨迹点密度相对较低.3794软件学报2023 年第 34 卷第 8 期例如,开源数据集 T-Drive11,12采集了北京市的一万余辆出租车一周内的轨迹数据,平均采样时间间隔 177s,轨迹点间隔 623m,文献 13 中使用了 20102011 年间采集的北京市 6 万余辆出租车轨迹数据,平均采样时间间隔 70s,轨迹点间隔 560m.(a)电动自行车轨迹,轨迹点间平均距离约为 60 m(b)出租车轨迹,轨迹点间的平均距离约为 600 m图2电动自行车与汽车轨迹点间距示例,地图来源于谷歌地图(https:/ DP 算法15的轨迹简化方法应用最为广泛,其基于下述假设:轨迹点的位置记录是交通工具在该时刻位置的真实记录.由于 GPS 测量存在误差,当交通工具位于高层建筑旁、桥梁旁时,误差会急剧增大5.基于 DP 的轨迹简化算法会计算出与原始轨迹形状差异最小的简化轨迹,因此倾向于保留 GPS 误差较大的轨迹点4,进而可能导致匹配准确率下降.例如,图 3 中高层建筑旁的轨迹点 GPS 误差很大,若使用简化后的轨迹进行地图匹配,将会得到错误匹配结果.由于卡尔曼滤波算法能够用于最优状态估计,因此使用卡尔曼滤波算法与轨迹简化算法相结合,能够在简化过程中不断修正轨迹点.同时,现有基于 DP 算法15的轨迹简化算法1620依赖于人为设置的距离阈值,只有简化过程结束后才能计算出轨迹的简化比例.轨迹点停留点无效轨迹点异常点高层建筑图3电动自行车轨迹数据特点对于电动自行车轨迹数据的特点 3,我们使用无效轨迹片段来表示轨迹上不存在于给定路网的部分.当路网精度降低时,电动自行车的无效轨迹片段会相应增加.在实际的路网中,电动自行车能够在一些机动车不能驶入的路段行驶.例如,在图 3 中,星形轨迹点不存在于图中的路网上,这些轨迹点组成了一个无效轨迹片段.一些全局匹配算法使用折线间距离度量方法如弗雷歇距离来计算路网上的各条可能路线与待匹配轨迹的相似度21.当轨迹上存在无效轨迹片段时,这些算法仍会将相似度最大的路线作为匹配结果.基于状态转移模型的地图匹配算法14,2225则会因无效轨迹片段的存在导致匹配过程中断4,无法对轨迹的有效部分计算出匹配路线.上述两类算法都会因无效轨迹片段的存在而使匹配准确率降低.为解决现有地图匹配算法因电动自行车轨迹数据的上述特点导致的匹配准确率下降、匹配效率不高的问题,本文提出了一种可自适应路网精度的电动自行车轨迹地图匹配方法 KFTS-AMM.该方法融合了基于卡尔曼滤波王东京等:电动自行车轨迹简化与自适应地图匹配算法3795算法的轨迹简化算法(KFTS),以及分段的隐马尔可夫模型(hiddenMarkovmodel,HMM)的地图匹配算法(AMM).本文的贡献主要集中在以下 3 个方面.(1)提出了基于时空聚类的停留点处理算法,能够准确地识别与合并停留点,减少轨迹上的迂回,从而提高地图匹配算法的准确率.(2)提出了基于卡尔曼滤波算法的轨迹简化算法 KFTS,改进了 DPhull 算法,使其不依赖人为设置的距离阈值,仅使用轨迹简化比例作为简化过程参数.由于轨迹简化算法倾向于保留误差较大的轨迹点4,因此在轨迹简化过程中加入滤波操作对轨迹点加以修正,能够提升后续地图匹配过程的准确率.(3)使用分段的 HMM 的自适应地图匹配算法 AMM,能够在匹配的过程中不断检测出无效的轨迹片段,同时将有效的轨迹片段匹配到给定精度的路网图上,在不同精度的路网上均能取得良好的准确率.本文第 1 节回顾了地图匹配算法、轨迹简化算法与轨迹停留点识别的相关研究工作.第 2 节介绍相关的定义以及问题描述.第 3 节详细介绍了本文提出的算法.第 4 节展示了在真实数据集上的对比实验结果.第 5 节总结了现有工作以及未来工作的重点.1 相关工作在本节中,我们回顾了地图匹配、轨迹简化以及轨迹停留点识别的相关研究工作.1.1 地图匹配文献 26 提出根据轨迹匹配过程中的采样点范围将地图匹配算法分为局部/增量算法2729与全局算法21,30.局部/增量算法使用轨迹的局部特征进行匹配,计算速度快,适用于高频率采样的轨迹,但当路网密集度较高时,准确率普遍较低.全局算法使用整条轨迹进行匹配,为轨迹寻找一条相似度最高的路线,计算复杂度较高.Quddus 等人根据地图匹配算法所使用的技术将地图匹配算法分为以下 4 类26:基于几何关系的匹配算法31、基于拓扑关系的匹配算法32、基于概率统计的匹配算法33和其他匹配算法(例如:使用了诸如扩展卡尔曼滤波器34、模糊逻辑35、证据理论36和贝叶斯推理37等技术).但是,随着近年来又有许多新的方法被提出,这一分类标准已经不再适用.Chao 等人在文献 4 中提出根据核心匹配模型将地图匹配算法分为 4 个类别:相似度模型21,27、状态转移模型9,14,23,24,38、候选进化模型39和评分模型40.同时,Chao 等人还列举了 3 种给地图匹配带来挑战的数据质量问题,包括不必要的迂回、异常点和路网中道路的密度,这 3 种问题均会降低地图匹配算法的准确率.在基于状态转移模型的地图匹配算法中,基于隐马尔可夫模型的地图匹配算法14,2225,38,41是最流行的,同时也被证实具有较高的准确率42.一些研究人员致力于提高地图匹配效率.地图匹配效率的提升可以通过以下 4 种方式14:使用空间索引技术43,44以加快对某个轨迹点的近邻点与近邻边的查找速度、避免路网图中最短路径的重复计算14,45、使用分布式与并行计算技术22,4648、压缩轨迹以减少参与计算的轨迹点.上述地图匹配算法设计的实验所使用的数据集多为机动车轨迹数据集,由于电动自行车轨迹上存在大量停留点、采样频率高、轨迹点密集且存在大量无效轨迹片段的特点,已有算法不适宜直接应用在电动自行车轨迹数据上.1.2 轨迹简化轨迹简化算法是目前最主流的轨迹数据压缩处理方法49,将轨迹数据视为一条连续的折线,通过删除部分对折线形状影响较小的轨迹点,实现简化后折线与原始折线的近似拟合,从而完成轨迹数据的压缩.根据轨迹简化算法是否适用于实时计算,可以将现有轨迹简化算法划分为在线轨迹简化算法与离线轨迹简化算法2.O(n3)O(n2)O(nlogn)离线轨迹简化算法没有输入轨迹规模的限制,能够得到全局最优的简化结果.Bellman 算法50是最早用于解决轨迹简化问题的算法,利用了动态规划技术,但是计算复杂度较高,达到了.DP 算法15是另一种经典的轨迹简化算法,在最坏情况下的时间复杂度为.许多研究人员为了提升 DP 算法的效率提出了改进方法,如 DPhull算法16引入了凸包技术,使算法在最坏情况下的时间复杂度下降到了.现有基于 DP 算法的轨迹简化算法大多依赖于人为设置的距离阈值,无法直接确定最终的简化比例.文献 51 提出了不使用距离阈值作为参数的3796软件学报2023 年第 34 卷第 8 期简化方法,使用递归的方式,动态调整距离阈值以控制简化比例,但是易造成轨迹上不同片段简化比例的不平衡.文献 52 提出的简化算法首先依据速度对轨迹分段,再结合 DP 算法对轨迹简化,以保留轨迹时空特征.在线场景中,需要实时对轨迹数据进行简化,因此必须根据计算设备的存储与计算性能限制轨迹的输入规模.Slidingwindow(SW)算法17和 openingwindow(OW)算法18都使用了能够动态调整大小的滑动窗口作为轨迹点缓冲区,利用两个轨迹点作为起止点标记一个滑动窗口,当窗口内某轨迹点与窗口首尾轨迹点连线的欧式距离超过设定阈值时,将窗口的起始轨迹点向前移动.这两种算法不同之处在于,SW 算法将起始轨迹点移动到终止轨迹点的前一个轨迹点处,而 OW 算法则将其移动到距离首尾连线距离最大的轨迹点处.STTrace 算法19与 SQUISH算法20设置了固定大小的缓冲区,同样根据窗口内各轨迹点距首尾轨迹点连线的距离大小来决定是否将窗口向前滑动.1.3 停留点识别停留点是指在某一段连续的时间内,位置变化小于一定距离的一组轨迹点.当车辆运动速度过于缓慢(例如用户推行电动自行车)、暂时停止行驶,或在较小区域内反复行驶时,就会产生停留点.停留点识别方法有 3 类:基于差异的方法8,53、基于历史数据与额外位置信息的方法8和基于聚类的方法54,55.其中,基于差异的方法需要通过设置速度、距离或者时间阈值来识别停留点,这种方法在拥有足够先验知识的情况下才能够有较高的准确率;基于历史数据与额外位置信息的方法通过用户历史出行数据挖掘用户的出行模式,进而结合关键位置信息推测停留点;基于聚类的方法使用聚类算法寻找轨迹点聚类,但是这种方法同样依赖输入的参数,如距离和时间阈值.当距离阈值与时间阈值设置合理时,基于聚类的方法在没有历史数据和位置信息的情况下仍能达到较高的准确率.文献 8 设置了时间与距离阈值,线性扫描轨迹以识别停留点,然后以求均值的方式合并停留点.然而这种识别方法只考虑了相邻位置的时空关系,当轨迹在一段区域内反复迂回,则无法有效识别出停留点.DBSCAN 算法56是一种基于密度的聚类算法,能够识别任意形状的聚类,且不需要预先确定聚类个数.但是由于时空数据的时间属性和空间属性尺度不同,因此该算法不能很好地解决时空数据的聚类问题.为此,Birant 等人提出了 ST-DBSCAN 算法57,该算法使用了空间邻域半径和时间邻域半径作为聚类内轨迹点的距离阈值,能够很好地解决时空数据的聚类问题.本文 StayPointsProcess 算法即使用 ST-DBSCAN 算法完成停留点的识别.1.4 卡尔曼滤波卡尔曼滤波算法58是一种利用线性系统状态方程,迭代地对系统每一时刻状态做出最优估计的算法.许多研究人员对其进行了创新,使卡尔曼滤波算法也可应用于非线性系统,例如使用泰勒级数展开将非线性系统线性化的扩展卡尔曼滤波算法(extendedKalmanfiltering,EKF)59,60和结合了无迹变换(unscentedtransform,UT)的无迹卡尔曼滤波算法(unscentedKalmanfiltering,UKF)61.卡尔曼滤波算法在许多领域都有巨大的应用价值,例如车辆状态预测62、动态目标跟踪63、传感器信息融合64等.卡尔曼滤波算法能够融合多种传感器数据,减小仅使用 GPS 传感器对车辆定位时的误差.文献 34 使用车内里程表、陀螺仪与 GPS 传感器数据,通过卡尔曼滤波算法构建车体的运动模型,然后结合地图匹配算法对车辆精确定位.文献 65 提出了将卡尔曼滤波算法与地图匹配算法融合入动态的贝叶斯网络中,同样使用了多种传感器数据对车辆运动模型建模以达到对车辆的精确定位.2 基本概念和问题描述在本节中,我们给出了本文中出现的一些关键变量和符号的说明,如表 1 所示.同时,我们给出了本文相关概念的定义以及所要解决的问题的描述.p:lonlat定义 1.轨迹点.轨迹点 p 为 GPS 传感器的一条记录,代表了电动自行车的时空状态,可以由一个三元组表示,其中,和分别表示电动自行车所处位置的经度和纬度,t 表示这条记录的时间戳.由于传感器存在测量误差,因此轨迹点 p 的位置测量值并不完全等于真实位置.王东京等:电动自行车轨迹简化与自适应地图匹配算法3797表1关键变量说明变量名说明p Tr轨迹Tr上的轨迹点pG(V,E)路网图,且为有向图V,E路网图中的顶点集合和有向边集合,分别表示道路端点和路段e.start,e.end,e E路段的起点和终点R路线Tr:p1 p2.pnp1 p2.p14定义 2.轨迹.轨迹是由一组按照时间顺序排列的轨迹点组成的序列.图 4 中展示了一段轨迹的示例.v2v1v3v4v5v6p1p2p3p4p5p6p7p8p9p10p11p12p13p14e1e3e2e2.ende3.start道路端点轨迹点道路段匹配的路线图4电动自行车轨迹示例G(V,E)v Ve Ee:,e.start,e.end Vv1,v2,.,v6定义 3.路网图.路网图是一个有向图,其中,(1)V 是路网图中的顶点集合,顶点,表示道路的端点;(2)E 是路网图中有向边的集合,有向边,在路网中表示道路段,可表示为一个二元组.在图 4 中,顶点为路网图上的道路端点,顶点间的有向边为路网图中的道路段.顶点与顶点间的有向边共同组成了路网图.R:e1 e2.enei E,ei+1.start=ei.end,i 1,n1e1 e2 e3p1 p2.p14定义 4.路线.路线是由一组路网图中的相连道路段组成的序列,.在图 4 中,为图中轨迹实际经过的路线.Tr:p1 p2.pnTrsub:pa pa+1.pb,1 a b na i j b,dist(pi,pj)thresholddist(pi,pj)pipjthresholdTrsubp9 p10.p14定义 5.停留点.轨迹上,存在一条子轨迹,且,其中为轨迹点和的距离,为停留点距离阈值,则称上的轨迹点为停留点.在图 4 中,虚线框中的轨迹点为一组停留点的示例.Tr:p1 p2.pnTr:p1 p2.pmm nratio=m/n,ratio (0,1ratio轨迹简化问题描述:对于给定的原始轨迹,使用轨迹简化算法将计算出一条新的轨迹,是原始轨迹 Tr 的子序列,即轨迹 Tr上的轨迹点也存在于原始轨迹 Tr 上,称 Tr上的轨迹点为特征点.轨迹简化比例是指简化后的轨迹 Tr与原始轨迹 Tr 的轨迹点数量之比,越大,轨迹简化过程保留的轨迹点越多.Tr:p1 p2.pnG(V,E)R:e1 e2.eme1 e2.emp1 p2.p14地图匹配问题描述:给定一条轨迹和路网图,地图匹配算法将计算出轨迹 Tr实际经过的路线.在图 4 中,路线是轨迹真实经过的3798软件学报2023 年第 34 卷第 8 期路线.3 基于卡尔曼滤波的轨迹简化与自适应地图匹配算法(KFTS-AMM)在本节中,我们详细地描述了本文提出的可自适应路网精度的电动自行车轨迹地图匹配方法 KFTS-AMM.其整体的架构图如图 5 所示,主要由 4 个部分组成,分别是轨迹提取、停留点识别与合并、轨迹简化与地图匹配,(1)轨迹提取:删除 GPS 日志中存在属性缺失、冗余和存在明显错误的记录.对 GPS 日志按照电动自行车设备ID 与记录时间进行排序,通过设置时间阈值分割提取出轨迹数据;(2)停留点处理:使用时空聚类算法识别停留点,结合旋转卡壳算法(rotatingcalipersalgorithm)66对停留点进行合并;(3)轨迹简化:使用分段的卡尔曼滤波算法对轨迹进行修正,然后使用基于 DPhull 算法16改进的 DPhull-ratio 算法进行轨迹简化;(4)地图匹配:使用分段的隐马尔可夫模型(HMM)地图匹配算法进行地图匹配.数据清洗轨迹分割轨迹提取基于分段的 HMM 的地图匹配算法 AMM地图匹配停留点处理算法StayPointsProcess停留点识别与合并基于卡尔曼滤波的轨迹简化算法 KFTS轨迹简化轨迹日志路网图图5KFTS-AMM 算法架构图本文提出的算法涵盖了电动自行车轨迹数据的清洗、轨迹提取、停留点处理、轨迹压缩简化以及地图匹配过程.在实际应用场景中,能够兼顾地图匹配的效率和准确率.同时,简化后的轨迹可以有效降低数据的存储空间.3.1 轨迹提取3.1.1轨迹数据清洗本文使用的是郑州市采集的真实电动自行车行驶数据.数据传输过程中存在部分数据丢失和部分数据传输错误的情况,因此需要对初始采集数据进行清洗.原始日志字段包括电动自行车 ID、数据采集时间、数据产生时间、经度与纬度.其中,电动自行车设备 ID 和数据产生时间可以唯一确定一条数据.轨迹数据清洗的过程包括以下 3个步骤:(1)删除存在属性缺失的记录;(2)对电动自行车设备 ID 和时间戳属性均相同的重复记录,只保留其中一条;(3)由于已知郑州市的经纬度范围为东经 112.42至东经 114.14,北纬 34.16至北纬 34.58,因此将经度或纬度超出这一范围的异常记录删除.3.1.2轨迹数据的分割交通部门使用安装在电动自行车上的边缘设备采集轨迹数据.首先按照电动自行车设备 ID 对日志数据进行分割,然后再按照数据产生时间进行排序,通过这种方式可获取每辆电动自行车按照时间顺序排列的 GPS 日志序列.为了从排序后的 GPS 日志中提取电动自行车的轨迹数据,还需要按照时间间隔对其进行分割.当电动自行车长时间静止后,GPS 传感器会停止采集数据.因此,我们使用了固定的时间阈值来分割不同的轨迹,我们将时间阈值设置为 3min.若排序后的 GPS 日志中相邻记录的数据采集时间超过 3min 时,可以认为其属于不同轨迹.3.2 停留点识别与合并本节详细分析了电动自行车轨迹的停留点分布特点,并据此特点提出了电动自行车轨迹上对停留点的处理算王东京等:电动自行车轨迹简化与自适应地图匹配算法3799法 StayPointsProcess.停留点是指在某一段连续的时间内,位置变化小于一定距离的一组轨迹点.当车辆运动速度过于缓慢(例如用户推行电动自行车)、暂时停止行驶或者在某一较小区域内反复行驶时,就会产生停留点.在实际场景中,用户会在骑行电动自行车的途中停车或下车推行并保持一定时间,此时会随之产生停留点.图 6 显示了一段真实轨迹与其 GPS 测量记录.当电动自行车速度接近于零时,出现了一组停留点,由于 GPS 测量值在真实位置附近呈混合高斯分布,因此停留点的 GPS 记录分布在图中椭圆形虚线框范围内.图 7 展示了 StayPointsProcess 算法的过程,图中左侧椭圆形虚线框内为一组停留点,右侧多边形框为停留点的凸包,凸包直径上的点为停留点合并得到的新轨迹点,该点位于凸包的直径上.在图 7 中,使用均值计算得到的轨迹合并点,受停留点密度影响,未分布在这一区域的中心位置,若以此点作为合并点,则可能导致合并后的轨迹不平滑.pO(plogp)qq pO(q)O(plogp)n,n pO(nlogn)O(nlogn)StayPointsProcess 算法首先使用 ST-DBSCAN 算法57完成停留点的识别,然后通过旋转卡壳算法66求出停留点的凸包并计算凸包直径,最后使用电动自行车的平均速度在直径上取出若干点代替停留点,从而形成新的轨迹.若轨迹中停留点的个数为,则构造凸包的时间复杂度为,设凸包上点个数为,使用旋转卡壳算法计算此凸包直径的时间复杂度为,则停留点的合并过程时间复杂度为.若轨迹上的轨迹点个数为,则 ST-DBSCAN 的平均时间复杂度为.综上,StayPointsProcess 算法的整体时间复杂度为.eps1eps2metricTrDiameterstayRCmerge(Diameterstay,vavg)vavg算法 1StayPointsProcess 描述了停留点的处理过程,其输入包括原始轨迹 Tr、空间邻域半径、时间邻域半径、停留点最小邻居数 minPts 以及距离计算指标,默认的距离计算指标为曼哈顿距离(Manhattandistance).算法输出为新轨迹.算法1 第 11 行为使用旋转卡壳算法计算出的停留点凸包直径,第 12 行为停留点的合并过程,其中为轨迹的平均速度.算法 1StayPointsProcess 的具体步骤如下.第 1 步(第 14 行):初始化当前停留点集合、输出轨迹为空.构造聚类模型并拟合数据,标记每个轨迹点是否为噪声点.计算整个轨迹的全局平均速度.第 2 步(第 6 行):判断当前点是否为噪声点,即该点是否不属于任何聚类,若该点为噪声点,则执行步骤 3;若不为噪声点,则执行步骤 4.第 3 步(第 714 行):获取当前聚类的标签,向后遍历轨迹点,将属于同一聚类的轨迹点加入当前停留点集合.然后使用旋转卡壳算法计算停留点凸包直径,在直径上取若干个点作为合并后的轨迹点,加入输出轨迹.清空停留点集合.第 4 步(第 16 行):将非噪声轨迹点加入输出轨迹.算法 1.停留点处理算法 StayPointsProcess.Tr:p1 p2.pneps1eps2minPtsmetric输入:原始轨迹,空间邻域半径,时间邻域半径,停留点最小邻居数,距离计算方法;输出:停留点识别合并后的轨迹 Tr.v0真实轨迹GPS 记录轨迹停留点的高斯分布图6停留点分布示例停留点凸包直径停留点凸包均值合并点图7停留点处理算法 StayPointsProcess 说明3800软件学报2023 年第 34 卷第 8 期sstay,Tr;sstay1./停留点集合初始化为空集合model ST-DBSCAN(eps1,eps2,minPts,metric Manhattan);2./构建聚类模型labels model.fit(Tr);3./使用聚类模型拟合数据vavgn1i=1dis(pi,pi+1)/(pn.t p1.t)4.;/计算轨迹的全局平均速度i=1n5.fortodolabelsi,16.ifdo/判断该点是否属于某个簇类labelcur labelsi;7.labelsi=labelcur8.while dosstay.add(Tri);9.i i+1;10.11.endwhileDiameterstay RC(sstay);12./使用旋转卡壳算法计算停留点凸包的直径Tr.add(merge(Diameterstay,vavg);13./在凸包直径上取若干轨迹点,加入新轨迹sstay.clear()14.;/清空当前停留点集合15.elseTr.add(Tri);16.17.endif18.endfor 3.3 轨迹简化本节详细介绍了本文所提出的基于分段的卡尔曼滤波的轨迹简化算法 KFTS.该算法首先使用分段的卡尔曼滤波算法修正轨迹曲线,然后使用基于 DPhull 算法改进的 DPhull-ratio 算法进行轨迹简化,得到简化后的轨迹.3.3.1基于轨迹简化比例的轨迹简化算法 DPhull-ratio现有的离线与在线轨迹简化算法大多使用距离阈值作为轨迹简化过程的参数49,只有当简化过程终止时,才能计算出轨迹简化比例.但是,距离阈值的设置依赖于先验知识和对轨迹数据的初步统计结果,若设置不够合理,则无法得到期望的简化比例.文献 51 使用递归的方式,动态调整距离阈值以控制简化比例,易造成轨迹上不同片段简化比例的不平衡.本文在 DPhull 算法的基础上,提出了基于轨迹简化比例的轨迹简化算法 DPhull-ratio,能够仅使用轨迹简化比例作为参数,得到简化结果.利用优先队列存储轨迹上的子轨迹段,以达到不同片段简化比例的平衡.Tr:p1 p2.p6Dthresholdp1p6p4Dthresholdp4p4Trp1 p2 p3 p4p4 p5 p6p1p2p4p6Tr:p1 p2 p4 p6O(nlogn)DP 算法的计算过程如图 8 所示,设待简化的轨迹为,距离阈值为.首先,将轨迹起点与终点设置为特征点,并做连线,由于与首尾连线垂直距离最远,且超过了距离阈值,因此被作为轨迹的特征点.然后,在处分割原轨迹,得到子轨迹段与.对这两段子轨迹分别递归执行上述过程,最终确定特征点为、与,简化后轨迹为.文献 51 在 DP 算法的基础上,实时计算当前简化比例,若达到输入简化比例,则简化过程结束.这种方式易造成轨迹不同片段简化比例的不平衡.DPhull 算法引入了凸包的结构,能够快速查找距离首尾连线距离最大的轨迹点,使算法的最坏时间复杂度下降到了.p1Dthresholdp4p3p2p4p5p6p1p3p2p5p6Dthreshold图8DP 算法示意图王东京等:电动自行车轨迹简化与自适应地图匹配算法3801当需要获得某一设定简化比例的简化结果,使用 DP 算法(包括 DPhull)需要对距离阈值参数多次尝试,导致计算资源的浪费.为了解决此问题,本文提出了 DPhull-ratio 算法,一次运行即可得到期望的简化比例.DPhull-ratio算法基于贪心的思想,维护了一个优先队列,队列中每个节点记录了一段子轨迹和距离子轨迹首尾连线垂直距离最大的轨迹点,称其为分割点,节点的优先级即为分割点距离首尾连线的距离.这样设置优先级的原因在于,轨迹段上距离首尾连线垂直距离更大的轨迹点更能代表轨迹段的轮廓.DPhull-ratio 算法每次取出一个队头节点,在分割点处对子轨迹二分,并计算分割后两个子轨迹的分割点、优先级用于构建新的队列节点,最后将新节点加入优先队列.DPhull 算法在递归过程中,每次选出距子轨迹段首尾连线距离最大,且超过距离阈值的轨迹点作为特征点,这一选择依据与 DPhull-ratio 算法的优先级设置方式相似.因此,对于同一条轨迹,当 DPhull-ratio 算法与 DPhull 算法得到同一简化比例的结果时,所选取的特征点集合应具有较大相似度,与原始未简化轨迹的误差也应该较为接近.Tr:p1 p2.p10p1 p10p6p6在图 9 中,待简化轨迹为,设轨迹简化比例为 50%.优先队