IIVMM:针对低频GPS轨迹的改进交互式投票匹配算法

doi:10.11896/j.issn.1002-137X.2019.09.050

摘要/Abstract

摘要： 地图匹配是根据离散采样的定位数据(GPS坐标)识别移动对象(车辆、行人等)在道路网络中的运动路径的过程。它是许多基于GPS轨迹数据分析和位置分析等相关应用的必要处理步骤。针对现有的算法在应用于低采样轨迹数据时存在的匹配准确率和效率较低的问题,文中提出一种基于交互式投票的改进地图匹配算法。该算法不仅考虑了距离特征、道路的拓扑结构以及路段的限速,还考虑了每个GPS点的实时移动方向和速度,以提高算法的匹配准确率。其次,该算法还加入了基于方向和限速的滤波器,通过约束条件过滤候选噪声路段,以提高算法的匹配效率。为了验证算法的性能,使用了两组真实数据集对所提算法与现有的IVMM算法和AIVMM算法进行比较。实验结果表明,所提算法在匹配性能上优于现有的两种算法。

关键词: 低采样, 地图匹配, 方向, 约束

Abstract: Map matching is the process of recognizing the movement track of moving objects (mainly vehicles,pedes-trians) in the road network according to the discrete sampling location data (GPS coordinates).It is a necessary processing step for many relevant applications such as GPS trajectory data analysis and position analysis.This paper proposed an improved map matching algorithm based on interactive voting to solve the problems that the existing map matching algorithms have low accuracy and efficiency for low sampling trajectory data.The main contributions of the proposed algorithm are as follows.Firstly,the proposed algorithm considers not only the spatial distances between sampling points,road topology and road segment speed limits,but also the real-time moving direction and speed of each GPS point to improve the matching accuracy.Secondly,a filter based on driving direction and speed limits is introduced to filter out noisy candidates,thus improving the efficiency of the algorithm.To evaluate the performance of the proposed algorithm,two real-world datasets were used to compare the proposed algorithm with the existing IVMM algorithm and the AIVMM algorithm.Experimental results show that the proposed algorithm outperforms the existing two algorithms in terms of matching accuracy and efficiency.

Key words: Constraints, Direction, Low sampling rate, Map matching

中图分类号:

TP301

严盛隆, 于娟, 周后盘. IIVMM:针对低频GPS轨迹的改进交互式投票匹配算法[J]. 计算机科学, 2019, 46(9): 325-332. https://doi.org/10.11896/j.issn.1002-137X.2019.09.050

YAN Sheng-long, YU Juan, ZHOU Hou-pan. IIVMM:An Improved Interactive Voting-based Map Matching Algorithm for Low-sampling-rate GPS Trajectories[J]. Computer Science, 2019, 46(9): 325-332. https://doi.org/10.11896/j.issn.1002-137X.2019.09.050

参考文献

[1]JOSHIR R.A new approach to map matching for in-vehicle navi-gation systems:the rotational variation metric[C]//2001 IEEE Intelligent Transportation Systems.Oakland,CA,USA,2001:33-38.
[2]YUAN J,ZHENG Y,XIE X,et al.T-Drive:Enhancing DrivingDirections with Taxi Drivers’Intelligence[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(1):220-232.
[3]PANG L X,CHAWLA S,LIU W,et al.On detection of emerging anomalous traffic patterns using GPS data[J].Data & Know-ledge Engineering,2013,87(9):357-373.
[4]WHITEC E,BERNSTEIN D,KORNHAUSERA L.Some map matching algorithms for personal navigation assistants[J].Transportation Research Part C:Emerging Technologies,2000,8(1):91-108.
[5]BRAKATSOULAS S,PFOSER D,SALAS R,et al.On map-matching vehicle tracking data[C]//Proceedings of the 31st International Conference on Very Large Data Bases.Trondheim,Norway,2005:853-864.
[6]QUDDUSM A,OCHIENGW Y,ZHAO L,et al.A general map matching algorithm for transport telematics applications[J].GPS Solutions,2003,7(3):157-167.
[7]VELAGAN R,QUDDUSM A,BRISTOWA L.Developing anenhanced weight-based topological map-matching algorithm for intelligent transport systems[J].Transportation Research Part C,2009,17(6):672-683.
[8]QUDDUSM A,NOLANDR B,OCHIENG W Y.A High Accuracy Fuzzy Logic Based Map Matching Algorithm for Road Transport[J].Journal of Intelligent Transportation Systems,2006,10(3):103-115.
[9]OBRADOVIC D,LE NZ H,SCHUPFNER M.Fusion of Sensor Data in Siemens Car Navigation System[J].IEEE Transactions on Vehicular Technology,2007,56(1):43-50.
[10]NEWSON P,KRUMM J.Hidden Markov Map MatchingThrough Noise and Sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Seattle,Washington,USA,2009:336-343.
[11]HSUEHY L,CHENH C,HUANG W J.A Hidden MarkovModel-Based Map-Matching Approach for Low-Sampling-Rate GPS Trajectories[C]//IEEE 7th International Symposium on Cloud and Service Computing (SC2).Kanazawa,Japan,2017:271-274.
[12]HUNTER T,ABBEEL P,BAYENA M.The Path Inference Filter:Model-Based Low-Latency Map Matching of Probe Vehicle Data[J].IEEE Transactions on Intelligent Transportation Systems,2013,15(2):507-529.
[13]LIU X,LIU K,LI M,et al.A ST-CRF Map-Matching Method for Low-Frequency Floating Car Data[J].IEEE Transactions on Intelligent Transportation Systems,2017,18(5):1241-1254.
[14]SU H B,WANG G Z,WANG J D.Map matching algorithmbased on fuzzy neural network [J].Journal of Beijing University of Science and Technology,2012,34(1):43-47.(in Chinese)苏海滨,王光政,王继东.基于模糊神经网络的地图匹配算法[J].北京科技大学学报,2012,34(1):43-47.
[15]NIKOLIC＇ M,JOVIC＇ J.Implementation of generic algorithm in map-matching model[J].Expert Systems with Applications,2017,72:283-292.
[16]GONG Y J,CHEN E,ZHANG X,et al.AntMapper:An Ant Colony-Based Map Matching Approach for Trajectory-Based Applications[J].IEEE Transactions on Intelligent Transportation Systems,2018,19(2):390-401.
[17]HASHEMI M.Reusability of the Output of Map-Matching Algorithms Across Space and Time Through Machine Learning[J].IEEE Transactions on Intelligent Transportation Systems,2017,18(11):3017-3026.
[18]LOU Y,ZHANG C,ZHENG Y,et al.Map-matching for Low-sampling-rate GPS Trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Seattle,Washington,USA,2009:352-361.
[19]YUAN J,ZHENG Y,ZHANG C,et al.An Interactive-VotingBased Map Matching Algorithm[C]//2010 Eleventh International Conference on Mobile Data Management.Kanas City,Missouri,USA,2010:43-52.
[20]LI C,SHEN D R,ZHU M D,et al.KNN query processing me-thod for spatio-temporal information [J].Journal of Software,2016,27(9):2278-2289.(in Chinese)李晨,申德荣,朱命冬,等.一种对时空信息的kNN查询处理方法[J].软件学报,2016,27(9):2278-2289.
[21]DONG J,HUANG C H.Research on improving Dijkstra algorithm in GIS navigation application shortest path search [J].Computer Science,2012,39(10):245-247,257.(in Chinese)董俊,黄传河.改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J].计算机科学,2012,39(10):245-247,257.
[22]ZHANG Y,HE Y.An advanced interactive-voting based map matching algorithm for low-sampling-rate GPS data[C]//IEEE 15th International Conference on Networking,Sensing and Control (ICNSC).2018:1-7.

相关文章 15

[1]	傅彦铭, 朱杰夫, 蒋侃, 黄保华, 孟庆文, 周兴. 移动众包中基于多约束工人择优的激励机制研究 Incentive Mechanism Based on Multi-constrained Worker Selection in Mobile Crowdsourcing 计算机科学, 2022, 49(9): 275-282. https://doi.org/10.11896/jsjkx.210700129
[2]	黄璞, 沈阳阳, 杜旭然, 杨章静. 基于局部约束特征线表示的人脸识别 Face Recognition Based on Locality Constrained Feature Line Representation 计算机科学, 2022, 49(6A): 429-433. https://doi.org/10.11896/jsjkx.210300169
[3]	杨辉, 陶力宏, 朱建勇, 聂飞平. 基于锚点的快速无监督图嵌入 Fast Unsupervised Graph Embedding Based on Anchors 计算机科学, 2022, 49(4): 116-123. https://doi.org/10.11896/jsjkx.210200098
[4]	官铮, 邓扬琳, 聂仁灿. 光谱重建约束非负矩阵分解的高光谱与全色图像融合 Non-negative Matrix Factorization Based on Spectral Reconstruction Constraint for Hyperspectral and Panchromatic Image Fusion 计算机科学, 2021, 48(9): 153-159. https://doi.org/10.11896/jsjkx.200900054
[5]	张帆, 宫傲宇, 邓磊, 刘芳, 林艳, 张一晋. 面向实际信道观测环境的时限约束无线下行调度策略 Wireless Downlink Scheduling with Deadline Constraint for Realistic Channel Observation Environment 计算机科学, 2021, 48(9): 264-270. https://doi.org/10.11896/jsjkx.210100143
[6]	王中元, 刘惊雷. 基于二阶近邻的核子空间聚类 Kernel Subspace Clustering Based on Second-order Neighbors 计算机科学, 2021, 48(6): 86-95. https://doi.org/10.11896/jsjkx.200800180
[7]	徐艺菲, 熊淑华, 孙伟恒, 何小海, 陈洪刚. 基于非局部低秩和自适应量化约束先验的HEVC后处理算法 HEVC Post-processing Algorithm Based on Non-local Low-rank and Adaptive Quantization Constraint Prior 计算机科学, 2021, 48(5): 155-162. https://doi.org/10.11896/jsjkx.200800079
[8]	李笠, 李广鹏, 常亮, 古天龙. 约束进化算法及其应用研究综述 Survey of Constrained Evolutionary Algorithms and Their Applications 计算机科学, 2021, 48(4): 1-13. https://doi.org/10.11896/jsjkx.200600151
[9]	周秋艳, 肖满生, 张龙信, 张晓丽, 杨文理. 多约束条件下生产排程智能优化技术 Intelligent Optimization Technology of Production Scheduling Under Multiple Constraints 计算机科学, 2021, 48(3): 239-245. https://doi.org/10.11896/jsjkx.200300105
[10]	郑建云, 庞建民, 周鑫, 王军. 基于约束推导式的增强型二进制漏洞挖掘 Enhanced Binary Vulnerability Mining Based on Constraint Derivation 计算机科学, 2021, 48(3): 320-326. https://doi.org/10.11896/jsjkx.200700047
[11]	王文博, 罗恒利. 基于图卷积神经网络的完全图人脸聚类 Complete Graph Face Clustering Based on Graph Convolution Network 计算机科学, 2021, 48(11A): 275-277. https://doi.org/10.11896/jsjkx.201200102
[12]	曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193
[13]	叶亚男, 迟静, 于志平, 战玉丽, 张彩明. 基于改进CycleGan模型和区域分割的表情动画合成 Expression Animation Synthesis Based on Improved CycleGan Model and Region Segmentation 计算机科学, 2020, 47(9): 142-149. https://doi.org/10.11896/jsjkx.190900203
[14]	杨帆, 王俊斌, 白亮. 基于安全性的成对约束扩充算法 Extended Algorithm of Pairwise Constraints Based on Security 计算机科学, 2020, 47(9): 324-329. https://doi.org/10.11896/jsjkx.200700092
[15]	张龙信, 周立前, 文鸿, 肖满生, 邓晓军. 基于异构云计算的成本约束下的工作流能量高效调度算法 Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems 计算机科学, 2020, 47(8): 112-118. https://doi.org/10.11896/jsjkx.200300038

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed