基于改进HMM模型的3D景区地图匹配算法

doi:10.19678/j.issn.1000-3428.0050584

计算机工程 ›› 2019, Vol. 45 ›› Issue (6): 259-266.doi: 10.19678/j.issn.1000-3428.0050584

基于改进HMM模型的3D景区地图匹配算法

黄娟娟,徐圆,朱群雄

北京化工大学信息科学与技术学院,北京 100029

收稿日期:2018-03-02 出版日期:2019-06-15 发布日期:2019-06-15
作者简介:黄娟娟(1992—),女,硕士研究生,主研方向为虚拟现实、地理信息系统;徐圆(通信作者),副教授、博士;朱群雄,教授。
基金项目:
北京市自然科学基金(4142039)。

3D map matching algorithm for scenic spot based on improved hidden Markov model

HUANG Juanjuan,XU Yuan,ZHU Qunxiong

College of Information Science and Technology,Beijing University of Chemical Technology,Beijing 100029,China

Received:2018-03-02 Online:2019-06-15 Published:2019-06-15

摘要/Abstract

摘要： 针对GPS误差和地图系统误差导致3D地图定位精度较低的问题,提出一种基于改进隐性马尔科夫模型的地图匹配算法。使用面积重叠法获取候选路段,引入距离、道路宽度和历史定位点计算观测概率,利用路网拓扑信息、游客行为特性、景点与道路的相关性计算转移概率,采用Viterbi算法得出最优匹配路段。在Unity3D平台上实现景区场景3D可视化,利用校园地图进行实验验证,结果表明,该算法匹配精度达到95.4%,在3D景区导航中具有良好的实用性和较高的准确性。

关键词: 3D地图, 景区导航, 隐性马尔科夫模型, 地图匹配, Viterbi算法

Abstract: To address the low accuracy of location in 3D map due to GPS error and digital map error,a map matching algorithm based on an improved Hidden Markov Model(HMM) is introduced.This paper proposes the area overlap method to obtain the candidate road segments.The calculation of the observation probability takes the distance,road width and historical positions into account.The transition probability is computed in terms of road network topology data,the tourist’s behavior characteristics and the correlation between scenic spots and roads.Then the algorithm uses the Viterbi algorithm to get the optimal matching road segments.The presented algorithm enables the 3D visualization of the scenic scene on the Unity3D platform,and is verified by using the campus map.Experimental results show that the matching accuracy of the presented algorithm achieves 95.4%.The presented algorithm has a good performance in 3D scenic spot navigation in both practicability and accuracy.

Key words: 3D map, scenic spot navigation, Hidden Markov Model(HMM), map matching, Viterbi algorithm

中图分类号:

TP391

黄娟娟,徐圆,朱群雄. 基于改进HMM模型的3D景区地图匹配算法[J]. 计算机工程, 2019, 45(6): 259-266.

HUANG Juanjuan,XU Yuan,ZHU Qunxiong. 3D map matching algorithm for scenic spot based on improved hidden Markov model[J]. Computer Engineering, 2019, 45(6): 259-266.

参考文献［15］

［1］	MARTINEZ-GRAA A M,GOY J L,CIMARRA C.2D to 3D geologic mapping transformation using virtual globes and flight simulators and their applications in the analysis of geodiversity in natural areas［J］.Environmental Earth Sciences,2015,73(12):8023-8034.
［2］	KIM D H,ATHIKULWONGSE K,HEALY M B.Design and analysis of 3D-MAPS(3D massively parallel processor with stacked memory)［J］.IEEE Transactions on Computers,2014,64(1):112-125.
［3］	袁寒寒.基于多模型交互算法在三维定位导航中的应用与研究［D］.南京:南京邮电大学,2017.
［4］	QUDDUS M A,NOLAND R B,OCHIENG W Y.The effects of navigation sensors and spatial road network data quality on the performance of map matching algorithms［J］.Geoinformatica,2009,13(1):85-108.
［5］	OULASVIRTA A,ESTLANDER S,NUMINEN A.Embodied interaction with a 3D versus 2D mobile map［J］.Personal and Ubiquitous Computing,2009,13(4):303-320.
［6］	HASHEMI M,KARIMI H A.A critical review of real-time map-matching algorithms:current issues and future directions［J］.Computers Environment and Urban Systems,2014,48(8):153-165.
［7］	WHITE C E,BERNSTEIN D,KORNHAUSER A L.Some map matching algorithms for personal navigation assistants［J］.Transportation Research Part C:Emerging Technologies,2000,8(1):91-108.
［8］	MOHAMED R,ALY H,YOUSSEF M.Accurate and efficient map matching for challenging environments［C］//Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2014:401-404.
［9］	FAHED A,GHALIA N,THIERRY D.A multiple-hypothesis map-matching method suitable for weighted and box-shaped state estimation for location［J］.IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1495-1510.
［10］	蒋佳维,张勇.车辆定位数据实时匹配地图解决策略［J］.电子设计工程,2017,25(24):88-91.
［11］	GOH C Y,DAUWELS J,MITROVIC N.Online map-matching based on hidden Markov model for real-time traffic sensing applications［C］//Proceedings of International IEEE Conference on Intelligent Transportation Systems.Washington D.C.,USA:IEEE Press,2012:776-781.
［12］	MALEKIAN R,KAVISHE A F,MAHARAJ B T.Smart vehicle navigation system using hidden Markov model and RFID Technology［J］.Wireless Personal Communications,2016,90(4):1717-1742.
［13］	向长风,徐圆,朱群雄.一种面向景区导航的动态地图匹配算法［J］.计算机工程,2016,42(10):32-37.
［14］	张小平,王保保,范克利.GPS 与数字地图的匹配研究［J］.计算机仿真,2005,22(6):148-151.
［15］	REN Ming,KARIMI H A.A hidden Markov model-based map-matching algorithm for wheelchair navigation［J］.Journal of Navigation,2009,62(3):383-395.

[1]	白玲玲, 宁振虎, 薛菲, 杨永丽. 隐马尔可夫模型在恶意域名检测中的应用[J]. 计算机工程, 2019, 45(9): 161-168.
[2]	滕志军,曲兆强,侯学艳,贾韬正,赵才博,夏滨. 基于曲线拟合与拓扑结构的地图匹配算法[J]. 计算机工程, 2018, 44(8): 291-295.
[3]	王科,李鹏,金瑜,刘宇. 基于三证据DS理论的双模式地图匹配算法[J]. 计算机工程, 2018, 44(5): 316-321.
[4]	向长风,徐圆,朱群雄. 一种面向景区导航的动态地图匹配算法[J]. 计算机工程, 2016, 42(10): 32-37,44.
[5]	翟东海,崔静静,聂洪玉,于磊,杜佳. 基于条件随机场的敏感话题检测模型研究[J]. 计算机工程, 2014, 40(8): 158-162,167.
[6]	陈金龙,夏莹杰. 一种基于位置服务的动态虚拟交通诱导系统[J]. 计算机工程, 2014, 40(10): 296-303.
[7]	乐娟, 赵玺. 基于HMM的京剧机构命名实体识别算法[J]. 计算机工程, 2013, 39(6): 266-271,286.
[8]	许建国, 张志利, 周召发. 基于DR/GIS组合导航的误差补偿研究[J]. 计算机工程, 2013, 39(5): 314-317.
[9]	王敏, 魏衡华, 鲍远律. GPS导航系统中的地图匹配算法[J]. 计算机工程, 2012, 38(14): 259-261.
[10]	蒋艳荣, 刘习文, 陈耿涛. 基于Viterbi改进算法的高棉语分词研究[J]. 计算机工程, 2011, 37(15): 174-176.
[11]	刘洁彬, 宋茂强, 赵方, 杨志宇. 基于上下文的二阶隐马尔可夫模型[J]. 计算机工程, 2010, 36(10): 231-232.
[12]	刘丹;方卫国;周泓. 基于贝叶斯网络的二元语法中文分词模型[J]. 计算机工程, 2010, 36(1): 12-14.
[13]	赵喜玲;李其申;卢致天;李俊峰. 一种改进的步态识别方法[J]. 计算机工程, 2009, 35(2): 177-179.
[14]	马瑞;杨静宇. 一种利用灰度信息和二值信息的手写字符分割[J]. 计算机工程, 2007, 33(15): 175-177.
[15]	史建红;郑浩然;蒋鸿. 一种基于纠错码的快速相关攻击算法[J]. 计算机工程, 2006, 32(18): 144-146,.

基于改进HMM模型的3D景区地图匹配算法

3D map matching algorithm for scenic spot based on improved hidden Markov model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［15］

相关文章 15

Metrics

本文评价

推荐阅读 10

基于改进HMM模型的3D景区地图匹配算法

3D map matching algorithm for scenic spot based on improved hidden Markov model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［15］

相关文章 15

Metrics

本文评价

推荐阅读 10

参考文献［15］