地图匹配算法及软件系统研究
|
摘要
近来,车载导航系统的发展方兴未艾,在物流、智能交通等领域得到了广泛地应用,而GPS/MM(全球定位系统/地图匹配)组合导航系统则是一种性价比比较高的车载组合导航方案。在GPS定位信息和电子地图精度一定的条件下,地图匹配算法的优劣就成为了决定导航及定位精度的关键因素,因此对其进行研究是十分必要的。
首先本文阐述了GPS和GIS的基本原理,为利用GPS定位信息和电子地图信息进行地图匹配算法的研究提供了相关理论。在已有的点到线的地图匹配算法和模糊综合评判地图匹配算法的基础上,根据模式识别的有关理论,针对各种不同的路况建立了初始匹配模式、跟踪匹配模式和交叉口匹配模式等三种地图匹配模式,并结合模糊综合评判法设计了一种基于模式匹配的模糊综合评判地图匹配算法。本算法首先根据当前的地图匹配模式来确定侯选路段集,然后通过模糊综合评判法在候选路段集中寻找最优匹配路段,最后通过正交投影法在最优匹配路段上寻找一点作为定位结果。
然后运用Visual Studio C++ 6.0和MapX开发了地图匹配可视化软件,实现了本文设计的基于模式匹配的模糊综合评判地图匹配算法的同时,还为GPS信息的采集和离线分析、地图匹配过程的建模以及不同的地图匹配算法之间的测试比较提供了一个功能完善的软件平台,也为今后进一步深入研究地图匹配算法打下了良好的基础。
最后通过实地跑车实验,将本文设计的基于模式匹配的模糊综合评判地图匹配算法分别与点到线的地图匹配算法、模糊综合评判地图匹配算法进行比较,证明了在一些复杂的道路拓扑结构下,基于模式匹配的模糊综合评判地图匹配算法能够做出更合理、更准确的匹配,从而验证了该算法的有效性。
Nowadays the development of navigation system for land vehicles is just in the ascendant. It has been widely used in many fields such as physical distribution and intelligent transportation system. The GPS/MM system is one of the preferable projects in the integrated vehicle navigation system. On condition that the accuracy of GPS positioning information and digital map data are both fixed, the map matching algorithm become the key factor in the precision of the navigation and positioning. Hence, it’s necessary for us to keep focusing on the map matching algorithm.
Firstly, the thesis researches the basic theory of the GPS and GIS, which provide corresponding concepts for researching map matching algorithms with GPS positioning information and digital map data. Based on the point to curve map matching algorithm and fuzzy synthetic evaluation map matching algorithm, three matching modes which are named initial matching mode, tracking matching mode and junction matching mode are founded according to different road topologies by using the Pattern Recognition theory. Combining fuzzy synthetic evaluation and the three matching modes, a novel map matching algorithm named fuzzy synthetic evaluation map matching algorithm based on mode matching is proposed in this thesis. The first step in this algorithm is to form a candidate road set according to the mode of current matching process. The second step is to choose an optimized matching road among the candidate road set by fuzzy synthetic evaluation. In the end, the current position of the vehicle on the selected optimized matching road is determined by perpendicular projection.
Secondly, a visualized software is designed by using VC++ 6.0 and MapX control, as well as the map matching algorithm proposed by this paper. Further more, this software provides a software platform with comprehensive functions of sampling and analyzing GPS positioning information out of line, modeling the map matching process and testing different map matching algorithms. Also, it is a well foundation for future research.
In the end, the paper compares the new map matching algorithm with the point to curve map matching algorithm and fuzzy synthetic evaluation map matching algorithm by the real road experiments. The result of these experiments testify that the new map matching algorithm can make better matching under some complex road topologies. Meanwhile, this conclusion verifies the validity of the new algorithm.
首先本文阐述了GPS和GIS的基本原理,为利用GPS定位信息和电子地图信息进行地图匹配算法的研究提供了相关理论。在已有的点到线的地图匹配算法和模糊综合评判地图匹配算法的基础上,根据模式识别的有关理论,针对各种不同的路况建立了初始匹配模式、跟踪匹配模式和交叉口匹配模式等三种地图匹配模式,并结合模糊综合评判法设计了一种基于模式匹配的模糊综合评判地图匹配算法。本算法首先根据当前的地图匹配模式来确定侯选路段集,然后通过模糊综合评判法在候选路段集中寻找最优匹配路段,最后通过正交投影法在最优匹配路段上寻找一点作为定位结果。
然后运用Visual Studio C++ 6.0和MapX开发了地图匹配可视化软件,实现了本文设计的基于模式匹配的模糊综合评判地图匹配算法的同时,还为GPS信息的采集和离线分析、地图匹配过程的建模以及不同的地图匹配算法之间的测试比较提供了一个功能完善的软件平台,也为今后进一步深入研究地图匹配算法打下了良好的基础。
最后通过实地跑车实验,将本文设计的基于模式匹配的模糊综合评判地图匹配算法分别与点到线的地图匹配算法、模糊综合评判地图匹配算法进行比较,证明了在一些复杂的道路拓扑结构下,基于模式匹配的模糊综合评判地图匹配算法能够做出更合理、更准确的匹配,从而验证了该算法的有效性。
Nowadays the development of navigation system for land vehicles is just in the ascendant. It has been widely used in many fields such as physical distribution and intelligent transportation system. The GPS/MM system is one of the preferable projects in the integrated vehicle navigation system. On condition that the accuracy of GPS positioning information and digital map data are both fixed, the map matching algorithm become the key factor in the precision of the navigation and positioning. Hence, it’s necessary for us to keep focusing on the map matching algorithm.
Firstly, the thesis researches the basic theory of the GPS and GIS, which provide corresponding concepts for researching map matching algorithms with GPS positioning information and digital map data. Based on the point to curve map matching algorithm and fuzzy synthetic evaluation map matching algorithm, three matching modes which are named initial matching mode, tracking matching mode and junction matching mode are founded according to different road topologies by using the Pattern Recognition theory. Combining fuzzy synthetic evaluation and the three matching modes, a novel map matching algorithm named fuzzy synthetic evaluation map matching algorithm based on mode matching is proposed in this thesis. The first step in this algorithm is to form a candidate road set according to the mode of current matching process. The second step is to choose an optimized matching road among the candidate road set by fuzzy synthetic evaluation. In the end, the current position of the vehicle on the selected optimized matching road is determined by perpendicular projection.
Secondly, a visualized software is designed by using VC++ 6.0 and MapX control, as well as the map matching algorithm proposed by this paper. Further more, this software provides a software platform with comprehensive functions of sampling and analyzing GPS positioning information out of line, modeling the map matching process and testing different map matching algorithms. Also, it is a well foundation for future research.
In the end, the paper compares the new map matching algorithm with the point to curve map matching algorithm and fuzzy synthetic evaluation map matching algorithm by the real road experiments. The result of these experiments testify that the new map matching algorithm can make better matching under some complex road topologies. Meanwhile, this conclusion verifies the validity of the new algorithm.
引文
[1] 苏洁、周东方,GPS 车辆导航系统中的实时地图匹配算法,测绘学报,2001(3):252~256
[2] Van Diggelen, F., Indoor GPS theory & implementation, Position Location and Navigation Symposium, 2002:240~247
[3] Morisue F., Ikeda K.,Evaluation of map-matching techniques,Vehicle Navigation and Information Systems Conference,1989 :23~28
[4] Carpenter, R.N.,Medeiros, M.R,Concurrent mapping and localization and map matching on autonomous underwater vehicles, MTS/IEEE Conference and Exhibition on OCEANS,2001,1:380~389
[5] 王冬晖,城市车辆定位的地图匹配算法的设计与实现,硕士学位论文,沈阳工业大学,2003
[6] 万德均、房建成, GPS 动态滤波的理论、方法及其应用,江苏:江苏科技出版社,2000
[7] QUDDUS, MOHAMMED A., WASHINGTON Y. OCHIENG, LIN ZHAO, ROBERT B. NOLAND, A General Map Matching Algorithm for Transport Telematics Applications,GPS Solutions Journal,2003,7(3),157~167
[8] Dakai Yang, Baigen Cai, Yifang Yuan,An improved map-matching algorithm used in vehicle navigation system, Proceedings on Intelligent Transportation Systems, 2003(2) :1246 ~1250
[9] 彭飞、柳重堪,基于模糊逻辑的 GPS/DR 组合导航系统地图匹配算法,遥测遥控,2000,22(1):32~36
[10] Mengyin Fu, Jie Li, Meiling Wang, A hybrid map matching algorithm based on fuzzy comprehensive, Proceedings of The 7th International IEEE Conference on Intelligent Transportation Systems, 2004:613 ~ 617
[11] Winter M., Taylor G.., Modular neural networks for map-matched GPS positioning,Proceedings of Fourth International Conference on Web Information Systems Engineering Workshops, 2003:106 ~111
[12] 周颖、程荫杭,基于曲线拟合的地图匹配算法,交通运输系统工程与信息,2004(4):68~70
[13] Wuk Kim, Gyu-In Jee, JangGyu Lee,Efficient use of digital road map in various positioning for ITS,Position Location and Navigation Symposium, 2000:170~176
[14] Li Jie, Fu Meng-yin, Research on route planning and map-matching in vehicle GPS/dead-reckoning/electronic map integrated navigation system, Proceedings on Intelligent Transportation Systems, 2003(2):1639~1643
[15] 王惠南,GPS 导航原理与应用,北京:科学出版社,2003,11~12
[16] 朱华统,杨元喜,吕志平,GPS 坐标系统的转换,北京:测绘出版社,1994,11~37
[17] 刘基余,GPS 卫星导航定位原理与方法,北京:科学出版社,2003
[18] 徐绍铨,GPS 测量原理及应用,武汉:武汉大学出版社,2003
[19] 张勇,平面四参数法 GPS 坐标转换技术的应用分析,城市勘测,2005,2:28~30
[20] 李拥军,GPS 定位系统中数据读取和坐标的转换,铁路计算机应用, 2005,4:43~45
[21] 詹舒波,张其善,GPS/电子地图的坐标转换算法和实现,北京航空航天大学学报,1998,22(5):530~534
[22] 杨生辉、柴炜,基于 GPS 和 GIS 的车辆定位与导航系统,公路与汽运,2003(6):3~5
[23] Brady, D., Designing GIS for high availability and high performance, Proceedings of The Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, 2000,1:423~431
[24] Min Han, Xue Tian, Design and realization of GPS and GIS integration technology in wetland study, Proceedings of IGARSS '04 on Geoscience and Remote Sensing Symposium, 2004,5:2857~2860
[25] 王仁礼、陈天泽,计算机辅助设计与图形学报,智能型地图匹配综合算法的研究,2003,15(11):1443~1447,1451
[26] 李天文,GPS 原理及应用,北京:科学出版社,2003
[27] 张守信,GPS 技术与应用,北京:国防工业出版社,2004
[28] Huabei Yin, Wolfson, O., A weight-based map matching method in moving objects databases, Proceedings of 16th International Conference on Scientific and Statistical Database Management, 2004:437~438
[29] Sinn Kim, Jong-Hwan Kim, Q-factor map matching method using adaptive fuzzy network,Fuzzy Systems Conference Proceedings, 1999(2):628~633
[30] Sinn Kim, Jong-Hwan Kim, Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system,Industrial Electronics, IEEE Transactions,2001,48(2):432~441
[31] 诸静,模糊控制原理与应用,北京:机械工业出版社,1998
[32] 陈佳瑜,肖桂荣,基于权重的地图匹配算法,计算机工程与应用,2005(4):168~170
[33] Enescu, V., Sahli, H., Multiple model estimation scheme for map-matching, Proceedings of The IEEE 5th International Conference on Intelligent Transportation Systems, 2002:576~581
[34] Yamada H., Yamamoto K., Hosokawa,K.,Directional mathematical morphology and reformalized Hough transformation for the analysis of topographic maps,Pattern Analysis and Machine Intelligence, 1993,15:380
[35] Bullock J B, Krakiwsky E J., Analysis of the Use of Digital Road Maps in Vehicle Navigation[C].In:Proc IEEE Position Location and Navigation Symposium, 1994:494～501
[36] 刘光,地理信息系统二次开发教程——组件篇, 北京:清华大学出版社2003
[37] 冯永玉、时三帅,基于 MapX 控件的 GIS 应用软件开发研究,矿山测量, 2004(1):32~34
[38] 史剑珺、李军,基于 MapX 的空间查询应用,计算机工程与科学, 2004,26(9):75~78
[39] 任一峰、薛笑芳,GPS/电子地图车辆导航系统研究,华北工学院学报,2004,25(3):204~208
[40] 袁林、曹杰,利用 VC++实现 GPS 全球定位系统定位数据的提取,现代电子技术, 2004 ,27(24):105~107
[41] White C E, Bernstein D, Kornhauser A L., Some Map Matching Algorithms for Personal Navigation Assistants[J].Transportation Research Part C,2000(8) :91~108
[42] Bernstein D, Kornhauser A., An Introduction to Map Matching for Personal Navigation Assistants.http://www.njtude.org/reports/mapmatchintro.pdf
[2] Van Diggelen, F., Indoor GPS theory & implementation, Position Location and Navigation Symposium, 2002:240~247
[3] Morisue F., Ikeda K.,Evaluation of map-matching techniques,Vehicle Navigation and Information Systems Conference,1989 :23~28
[4] Carpenter, R.N.,Medeiros, M.R,Concurrent mapping and localization and map matching on autonomous underwater vehicles, MTS/IEEE Conference and Exhibition on OCEANS,2001,1:380~389
[5] 王冬晖,城市车辆定位的地图匹配算法的设计与实现,硕士学位论文,沈阳工业大学,2003
[6] 万德均、房建成, GPS 动态滤波的理论、方法及其应用,江苏:江苏科技出版社,2000
[7] QUDDUS, MOHAMMED A., WASHINGTON Y. OCHIENG, LIN ZHAO, ROBERT B. NOLAND, A General Map Matching Algorithm for Transport Telematics Applications,GPS Solutions Journal,2003,7(3),157~167
[8] Dakai Yang, Baigen Cai, Yifang Yuan,An improved map-matching algorithm used in vehicle navigation system, Proceedings on Intelligent Transportation Systems, 2003(2) :1246 ~1250
[9] 彭飞、柳重堪,基于模糊逻辑的 GPS/DR 组合导航系统地图匹配算法,遥测遥控,2000,22(1):32~36
[10] Mengyin Fu, Jie Li, Meiling Wang, A hybrid map matching algorithm based on fuzzy comprehensive, Proceedings of The 7th International IEEE Conference on Intelligent Transportation Systems, 2004:613 ~ 617
[11] Winter M., Taylor G.., Modular neural networks for map-matched GPS positioning,Proceedings of Fourth International Conference on Web Information Systems Engineering Workshops, 2003:106 ~111
[12] 周颖、程荫杭,基于曲线拟合的地图匹配算法,交通运输系统工程与信息,2004(4):68~70
[13] Wuk Kim, Gyu-In Jee, JangGyu Lee,Efficient use of digital road map in various positioning for ITS,Position Location and Navigation Symposium, 2000:170~176
[14] Li Jie, Fu Meng-yin, Research on route planning and map-matching in vehicle GPS/dead-reckoning/electronic map integrated navigation system, Proceedings on Intelligent Transportation Systems, 2003(2):1639~1643
[15] 王惠南,GPS 导航原理与应用,北京:科学出版社,2003,11~12
[16] 朱华统,杨元喜,吕志平,GPS 坐标系统的转换,北京:测绘出版社,1994,11~37
[17] 刘基余,GPS 卫星导航定位原理与方法,北京:科学出版社,2003
[18] 徐绍铨,GPS 测量原理及应用,武汉:武汉大学出版社,2003
[19] 张勇,平面四参数法 GPS 坐标转换技术的应用分析,城市勘测,2005,2:28~30
[20] 李拥军,GPS 定位系统中数据读取和坐标的转换,铁路计算机应用, 2005,4:43~45
[21] 詹舒波,张其善,GPS/电子地图的坐标转换算法和实现,北京航空航天大学学报,1998,22(5):530~534
[22] 杨生辉、柴炜,基于 GPS 和 GIS 的车辆定位与导航系统,公路与汽运,2003(6):3~5
[23] Brady, D., Designing GIS for high availability and high performance, Proceedings of The Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, 2000,1:423~431
[24] Min Han, Xue Tian, Design and realization of GPS and GIS integration technology in wetland study, Proceedings of IGARSS '04 on Geoscience and Remote Sensing Symposium, 2004,5:2857~2860
[25] 王仁礼、陈天泽,计算机辅助设计与图形学报,智能型地图匹配综合算法的研究,2003,15(11):1443~1447,1451
[26] 李天文,GPS 原理及应用,北京:科学出版社,2003
[27] 张守信,GPS 技术与应用,北京:国防工业出版社,2004
[28] Huabei Yin, Wolfson, O., A weight-based map matching method in moving objects databases, Proceedings of 16th International Conference on Scientific and Statistical Database Management, 2004:437~438
[29] Sinn Kim, Jong-Hwan Kim, Q-factor map matching method using adaptive fuzzy network,Fuzzy Systems Conference Proceedings, 1999(2):628~633
[30] Sinn Kim, Jong-Hwan Kim, Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system,Industrial Electronics, IEEE Transactions,2001,48(2):432~441
[31] 诸静,模糊控制原理与应用,北京:机械工业出版社,1998
[32] 陈佳瑜,肖桂荣,基于权重的地图匹配算法,计算机工程与应用,2005(4):168~170
[33] Enescu, V., Sahli, H., Multiple model estimation scheme for map-matching, Proceedings of The IEEE 5th International Conference on Intelligent Transportation Systems, 2002:576~581
[34] Yamada H., Yamamoto K., Hosokawa,K.,Directional mathematical morphology and reformalized Hough transformation for the analysis of topographic maps,Pattern Analysis and Machine Intelligence, 1993,15:380
[35] Bullock J B, Krakiwsky E J., Analysis of the Use of Digital Road Maps in Vehicle Navigation[C].In:Proc IEEE Position Location and Navigation Symposium, 1994:494～501
[36] 刘光,地理信息系统二次开发教程——组件篇, 北京:清华大学出版社2003
[37] 冯永玉、时三帅,基于 MapX 控件的 GIS 应用软件开发研究,矿山测量, 2004(1):32~34
[38] 史剑珺、李军,基于 MapX 的空间查询应用,计算机工程与科学, 2004,26(9):75~78
[39] 任一峰、薛笑芳,GPS/电子地图车辆导航系统研究,华北工学院学报,2004,25(3):204~208
[40] 袁林、曹杰,利用 VC++实现 GPS 全球定位系统定位数据的提取,现代电子技术, 2004 ,27(24):105~107
[41] White C E, Bernstein D, Kornhauser A L., Some Map Matching Algorithms for Personal Navigation Assistants[J].Transportation Research Part C,2000(8) :91~108
[42] Bernstein D, Kornhauser A., An Introduction to Map Matching for Personal Navigation Assistants.http://www.njtude.org/reports/mapmatchintro.pdf