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

Trajectory Simplification and Adaptive Map Matching Algorithm for Electric Bicycle

近年来,随着全球定位系统(global positioning system,GPS)的大范围应用,越来越多的电动自行车装配了GPS传感器,由此产生的海量轨迹数据是深入了解用户出行规律、为城市规划者提供科学决策支持等诸多应用的重要基础.但是,电动自行车上普遍使用的价格低廉的GPS传感器无法提供高精度的定位,同时,电动自行车轨迹地图匹配过程因以下原因更具有挑战性:(1)存在大量停留点;(2)高采样频率导致相邻轨迹点的距离较短;(3)电动自行车可行驶的路段更多,存在大量无效轨迹.针对上述问题,提出一种可自适应路网精度的电动自行车轨迹地图匹配方法KFTS-AMM.该方法融合基于分段卡尔曼滤波算法的轨迹简化算法(KFTS),和分段隐马尔可夫模型的地图匹配算法(AMM).首先,利用卡尔曼滤波算法可用于最优状态估计的特性,KFTS能够在轨迹简化过程中对轨迹点进行自动修正,使轨迹曲线变得平滑并减少了异常点对于地图匹配准确率的影响.同时,使用基于分段隐马尔可夫模型的地图匹配算法AMM,避免部分无效轨迹对整条轨迹匹配的影响.此外,在轨迹数据的处理过程加入了停留点的识别与合并,进一步提升匹配准确率.在郑州市真实电动自行车轨迹数据的实验结果表明,KFTS-AMM在准确率上相对于已有的对比算法有较大的提升,并可通过使用简化后的轨迹数据显著提升匹配速度.

With the wide application of global positioning system(GPS),more and more electric bicycles are equipped with GPS sensors.Massive trajectory data recorded by those sensors are of great value in many fields,such as users’travel patterns analysis,decision support for urban planners,and so on.However,the low-cost GPS sensors widely used on electric bicycles cannot provide high-precision positioning.Besides,the map matching for the electric bicycles’track data is more complex and challenging due to:(1)many stay points on electric bicycles’trajectories;(2)higher sampling frequency and shorter distance between adjacent track points on electric bicycle’s track data;(3)some roads only open for electric bicycles,and the accuracy of matching is sensitive to the quality of the road network.To solve those issues mentioned above,an adaptive and accurate road network map matching algorithm is proposed named KFTS-AMM,which consists of two main components:the segmented Kalman filtering based trajectory simplification(KFTS)algorithm and segmented hidden Markov model based adaptive map matching(AMM)algorithm.Since Kalman filtering algorithm can be used for optimal state estimation,the trajectory simplification algorithm KFTS can make the trajectory curve smoother and reduce the impact of abnormal points on the accuracy of map matching by fixing the trajectory points automatically in the process of trajectory simplification.Besides,the matching algorithm AMM is used to reduce the impact of invalid trajectory segments on the map matching accuracy.Moreover,stay points identification and merging step are added into the processing of track data,and the accuracy is further improved.Extensive experiments conducted on the real-world track dataset of electric bicycles in Zhengzhou city show that the proposed approach KFTS-AMM outperforms baselines in terms of accuracy and can speed up the matching process by using the simplified track data significantly.