一种面向室内导航的通行区域模型及其自动提取算法
|
摘要
面向室内位置服务中路径规划与导航的应用需求,提出一种基于栅格空间的通行区域模型及其自动提取算法。首先,在栅格模型基础上引入了相邻栅格和途经栅格,结合具体示例阐述了通行区域模型的基本原理;然后,根据室内地图数据特征,通过室内栅格模型初始化、通行区域初次提取和邻域融合,设计了通行区域的自动提取算法;最后,选取西单大悦城一楼室内地图数据进行了不同栅格尺度的通行区域自动提取和路径规划试验。结果表明,该算法针对走廊内存在障碍等复杂室内环境具有较好的适用性,并且通行区域模型相比网络模型的路径规划结果更加符合复杂室内环境的路径行走特征。
For the application requirement of route planning and navigation in indoor Location-based-service, we propose a traversable region model based on grid space and its automatic extraction algorithm. Firstly, this paper introduces adjoin grid and traversing grids based on grid model, expounds the basic principle of traversable region model through specific example. Then, according to the characteristics of indoor map data, through indoor grid model initialization, traversable region preliminary extraction and adjoin region merge, it designs traversable region automatic extraction algorithm. Finally, taking Xidan Joy City first floor indoor map data as an example, we perform different grid scale traversable region automatic extraction and route planning experiment. Results show that the automatic extraction algorithm has preferable applicability to deal with complex indoor environment which has barrier in the corridor and so on. Compared with network model, the route planning results of traversable region model are more conformed to the route walking feature of complex indoor environment.
For the application requirement of route planning and navigation in indoor Location-based-service, we propose a traversable region model based on grid space and its automatic extraction algorithm. Firstly, this paper introduces adjoin grid and traversing grids based on grid model, expounds the basic principle of traversable region model through specific example. Then, according to the characteristics of indoor map data, through indoor grid model initialization, traversable region preliminary extraction and adjoin region merge, it designs traversable region automatic extraction algorithm. Finally, taking Xidan Joy City first floor indoor map data as an example, we perform different grid scale traversable region automatic extraction and route planning experiment. Results show that the automatic extraction algorithm has preferable applicability to deal with complex indoor environment which has barrier in the corridor and so on. Compared with network model, the route planning results of traversable region model are more conformed to the route walking feature of complex indoor environment.
引文
[1] Zhou Chenghu, Zhu Xinyan, Wang Meng, et al. Panoramic Location-based Map[J]. Progress in Geography, 2011, 30(11): 1 331-1 335 (周成虎, 朱欣焰, 王蒙, 等. 全息位置地图研究[J]. 地理科学进展, 2011, 30(11): 1 331-1 335)
[2] Zhu Xinyan, Zhou Chenghu, Guo Wei, et al. Preliminary Study on Conception and Key Technologies of the Location-based Pan-Information Map[J]. Geomatics and Information Science of Wuhan University, 2015, 40(3): 285-295 (朱欣焰, 周成虎, 呙维, 等. 全息位置地图概念内涵及其关键技术初探[J]. 武汉大学学报·信息科学版, 2015, 40(3): 285-295)
[3] You Tian, Zhou Chenghu, Chen Xi. The Research and Practice of Indoor Map Representation[J]. Journal of Geomatics Science and Technology, 2014, 31(6): 635-640 (游天, 周成虎, 陈曦. 室内地图表示方法研究与实践[J]. 测绘科学技术学报, 2014, 31(6): 635-640)
[4] Gilliéron P Y, Büchel D, Spassov I. Indoor Navigation Performance Analysis[C]. European Navigation Conference GNSS,Rotterdam,Netherlands,2004
[5] Zhu Qing, Xiong Qing, Zhao Junqiao. Indoor Location Information Model and Intelligent Location Service[J]. Journal of Geomatics, 2014, 39(5): 1-7 (朱庆, 熊庆, 赵君峤. 室内位置信息模型与智能位置服务[J]. 测绘地理信息, 2014, 39(5): 1-7)
[6] Lin Haojia, Luo Wenfei. Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space[J]. Journal of Geo-Information Science, 2016, 18(2):175-181 (林浩嘉, 罗文斐. 多层建筑空间的分层最优路径算法实现[J].地球信息科学学报, 2016, 18(2):175-181)
[7] Brumitt B, Shafer S. Topological Word Modeling Using Semantic Spaces[C]. Ubicomp Workshop on Location Modeling for Ubiquitous Computing,Georgia,USA,2001
[8] Shi Chaoxia, Hong Bingrong, Zhou Tong, et al. Topological Map Building and Navigation in Large-scale Environments[J]. Robot, 2007, 29(5): 433-438 (石朝侠, 洪炳镕, 周彤, 等. 大规模环境下的拓扑地图创建与导航[J].机器人, 2007, 29(5): 433-438)
[9] Li X, Claramunt C, Ray C. A Grid Graph-based Model for the Analysis of 2D Indoor Spaces [J]. Computer Environment & Urban Systems, 2010, 34(6):532-540
[10] Dong Yuanyuan, Cui Hutao, Tian Yang. A Path-Planning Method for Mars Rovers Based on Grid Map[J]. Journal of Deep Space Exploration, 2014, 1(4):289-293 (董元元, 崔祜涛, 田阳. 基于栅格地图的火星车路径规划方法[J]. 深空探测学报, 2014, 1(4): 289-293)
[11] Xu Zhanya, Zhong Saishang, Wang Yuanyuan. Indoor Navigation Network Construction Method with Ability to Update Conveniently[J]. Computer Simulation, 2015, 32(12):267-275 (徐战亚, 钟塞尚, 王媛媛. 一种易于更新的室内导航路网构建方法[J].计算机仿真, 2015, 32(12): 267-275)
[12] Mu Xuanshe, You Xiong. Connectivity in Built Environments Interior for Quick Emergency Response[J]. Journal of Geomatics Science and Technology, 2006, 23(6): 635-640 (穆宣社, 游雄. 支持突发事件应急反应的建筑物内部交通网络分析[J]. 测绘科学技术学报, 2006, 23(6): 635-640)
[13] Goetz M, Zipf A. Formal Definition of a User-Adaptive and Length-Optimal Routing Graph for Complex Indoor Environments[J]. Geo-spatial Information Science, 2013, 14(2): 119-128
[14] Pan Peng, He Sanwei, Wu Yanlan, et al. A New Method for Extracting Curved-Polygon Medial Axis[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 278-283 (潘鹏, 贺三维, 吴艳兰, 等. 曲边多边形中轴提取的新方法[J]. 测绘学报, 2012, 41(2): 278-283)
[15] Ai Tinghua, Guo Renzhong. Extracting Center-lines and Building Street Network Based Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(4): 347-353 (艾廷华, 郭仁忠. 基于约束Delaunay结构的街道中轴线提取及网络模型建立[J].测绘学报, 2000, 29(4): 347-353)
[16] Liu L, Zlatanova S. A “Door-to-Door” Path-Finding Approach for Indoor Navigation[C]. International Society for Photogrammetry and Remote Sensing (ISPRS), Georgia, USA, 2011
[17] Sun Weixin, Wang Guangxia, Zhang Jinming, et al. A Method of Generating Indoor Map Spatial Data Automatically from Architectural Plans[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(6):731-739 (孙卫新, 王光霞, 张锦明, 等. 源自建筑平面图的室内地图空间数据自动生成方法[J].测绘学报, 2016, 45(6):731-739)
[2] Zhu Xinyan, Zhou Chenghu, Guo Wei, et al. Preliminary Study on Conception and Key Technologies of the Location-based Pan-Information Map[J]. Geomatics and Information Science of Wuhan University, 2015, 40(3): 285-295 (朱欣焰, 周成虎, 呙维, 等. 全息位置地图概念内涵及其关键技术初探[J]. 武汉大学学报·信息科学版, 2015, 40(3): 285-295)
[3] You Tian, Zhou Chenghu, Chen Xi. The Research and Practice of Indoor Map Representation[J]. Journal of Geomatics Science and Technology, 2014, 31(6): 635-640 (游天, 周成虎, 陈曦. 室内地图表示方法研究与实践[J]. 测绘科学技术学报, 2014, 31(6): 635-640)
[4] Gilliéron P Y, Büchel D, Spassov I. Indoor Navigation Performance Analysis[C]. European Navigation Conference GNSS,Rotterdam,Netherlands,2004
[5] Zhu Qing, Xiong Qing, Zhao Junqiao. Indoor Location Information Model and Intelligent Location Service[J]. Journal of Geomatics, 2014, 39(5): 1-7 (朱庆, 熊庆, 赵君峤. 室内位置信息模型与智能位置服务[J]. 测绘地理信息, 2014, 39(5): 1-7)
[6] Lin Haojia, Luo Wenfei. Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space[J]. Journal of Geo-Information Science, 2016, 18(2):175-181 (林浩嘉, 罗文斐. 多层建筑空间的分层最优路径算法实现[J].地球信息科学学报, 2016, 18(2):175-181)
[7] Brumitt B, Shafer S. Topological Word Modeling Using Semantic Spaces[C]. Ubicomp Workshop on Location Modeling for Ubiquitous Computing,Georgia,USA,2001
[8] Shi Chaoxia, Hong Bingrong, Zhou Tong, et al. Topological Map Building and Navigation in Large-scale Environments[J]. Robot, 2007, 29(5): 433-438 (石朝侠, 洪炳镕, 周彤, 等. 大规模环境下的拓扑地图创建与导航[J].机器人, 2007, 29(5): 433-438)
[9] Li X, Claramunt C, Ray C. A Grid Graph-based Model for the Analysis of 2D Indoor Spaces [J]. Computer Environment & Urban Systems, 2010, 34(6):532-540
[10] Dong Yuanyuan, Cui Hutao, Tian Yang. A Path-Planning Method for Mars Rovers Based on Grid Map[J]. Journal of Deep Space Exploration, 2014, 1(4):289-293 (董元元, 崔祜涛, 田阳. 基于栅格地图的火星车路径规划方法[J]. 深空探测学报, 2014, 1(4): 289-293)
[11] Xu Zhanya, Zhong Saishang, Wang Yuanyuan. Indoor Navigation Network Construction Method with Ability to Update Conveniently[J]. Computer Simulation, 2015, 32(12):267-275 (徐战亚, 钟塞尚, 王媛媛. 一种易于更新的室内导航路网构建方法[J].计算机仿真, 2015, 32(12): 267-275)
[12] Mu Xuanshe, You Xiong. Connectivity in Built Environments Interior for Quick Emergency Response[J]. Journal of Geomatics Science and Technology, 2006, 23(6): 635-640 (穆宣社, 游雄. 支持突发事件应急反应的建筑物内部交通网络分析[J]. 测绘科学技术学报, 2006, 23(6): 635-640)
[13] Goetz M, Zipf A. Formal Definition of a User-Adaptive and Length-Optimal Routing Graph for Complex Indoor Environments[J]. Geo-spatial Information Science, 2013, 14(2): 119-128
[14] Pan Peng, He Sanwei, Wu Yanlan, et al. A New Method for Extracting Curved-Polygon Medial Axis[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 278-283 (潘鹏, 贺三维, 吴艳兰, 等. 曲边多边形中轴提取的新方法[J]. 测绘学报, 2012, 41(2): 278-283)
[15] Ai Tinghua, Guo Renzhong. Extracting Center-lines and Building Street Network Based Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(4): 347-353 (艾廷华, 郭仁忠. 基于约束Delaunay结构的街道中轴线提取及网络模型建立[J].测绘学报, 2000, 29(4): 347-353)
[16] Liu L, Zlatanova S. A “Door-to-Door” Path-Finding Approach for Indoor Navigation[C]. International Society for Photogrammetry and Remote Sensing (ISPRS), Georgia, USA, 2011
[17] Sun Weixin, Wang Guangxia, Zhang Jinming, et al. A Method of Generating Indoor Map Spatial Data Automatically from Architectural Plans[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(6):731-739 (孙卫新, 王光霞, 张锦明, 等. 源自建筑平面图的室内地图空间数据自动生成方法[J].测绘学报, 2016, 45(6):731-739)