基于中轴变换算法的室内外一体化导航路网自动生成方法

doi:10.12082/dqxxkx.2018.170582

地球信息科学学报 ›› 2018, Vol. 20 ›› Issue (6): 730-737.doi: 10.12082/dqxxkx.2018.170582

• 2017年中国地理信息科学理论与方法学术年会优秀论文专辑 • 上一篇下一篇

基于中轴变换算法的室内外一体化导航路网自动生成方法

武恩超^1,²(), 张恒才^2,³, 吴升^1,^2,^*()

1. 福州大学福建省空间信息工程研究中心,福州大学数据挖掘与信息共享教育部重点实验室,福州 350002
2. 海西政务大数据应用协同创新中心,福州 350002
3. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京 100101

收稿日期:2017-12-03 修回日期:2018-03-03 出版日期:2018-06-20 发布日期:2018-06-20
作者简介:
作者简介：武恩超（1990-）,男,山东德州人,硕士生,研究方向为地理信息服务。E-mail: 153452679@qq.com
基金资助:
国家重点研发计划（2016YFB0502104）;国家自然科学基金面上项目（41771436）;福建省科技创新平台建设项目（2015H2001）

Automatic Generation Method of Indoor and Outdoor Integrated Navigation Network Based on Medial Axis Transform Algorithm

WU Enchao^1,²(), ZHANG Hengcai^2,³, WU Sheng^1,^2,^*()

1. Spatial Information Research Center of Fujian, Fuzhou University, Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education,Fuzhou 350002, China
2. Fujian Collaborative Innovation Center for Big Data Applications in Governments , Fuzhou 350002, China
3. State Key Lab of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China

Received:2017-12-03 Revised:2018-03-03 Online:2018-06-20 Published:2018-06-20
Contact: WU Sheng
Supported by:
National Key Research and Development Program of China, No.2016YFB0502104;National Natural Science Foundation of China, No.41771436;Fujian Provincial Science and Technology Innovation Platform Construction Project, China, No.2015H2001

摘要/Abstract

摘要：

室内外一体化导航路网的快速生成与更新对面向行人的跨场景导航具有重要意义。当前研究主要关注单一场景下的导航路网构建,对于跨室内外场景的导航路网自动生成研究较少。本文基于对偶图思想与二维平面多边形中轴变换（Medial Axis Transform）算法,提出一种室内外一体化导航路网自动生成方法,并以某建筑CAD平面图及周边路网环境为基础数据进行了实例研究。结果表明：该方法能够根据原始数据的几何、拓扑、语义信息自动构建导航路网,并支持室内外跨场景的最短路径查询,在最短路径查询效率上较传统分场景寻路模型整体提升10.18%;相较单一场景下的导航路网,一体化导航路网可结合语义信息将室内及室外导航路网有机统一起来,解决跨场景寻求最优路径的问题,为最优路径规划的相关研究提供了新的思路。

关键词: 室内外一体化, 自动生成, 中轴变换, 语义信息, 导航路网

Abstract:

The rapid generation and updating of indoor and outdoor integrated navigation network are of great significance for pedestrian-oriented cross-scene navigation. The current researches mainly focus on the establishment of the navigation network in a single scene, and few researches on the automatic generation of the navigation network across the indoor and outdoor scenes. In this paper, a method for automatic generation of indoor and outdoor integrated navigation network is proposed based on Dual Graph and Medial Axis Transform algorithm, then a case study was carried out based on the data of a building's CAD plan and it's surrounding road network. The results show that this method can automatically build the navigation network according to the geometry, topology and semantic information of the original data and support the shortest path query of indoor and outdoor cross-scene. Compared with traditional sub-scene, the overall efficiency of the proposed routing algorithm has been improved by 10.18%; the integrated navigation network can combine the indoor navigation network with the outdoor navigation network reasonably through the semantic information. Compared with the navigation network under single scene, this method could solve the problem of finding optimal path across scenes, and provide a new idea for the research of first-best path planning.

Key words: indoor and outdoor integration, automatic generation, Medial Axis Transform, semantic information, navigation network

武恩超, 张恒才, 吴升. 基于中轴变换算法的室内外一体化导航路网自动生成方法[J]. 地球信息科学学报, 2018, 20(6): 730-737.DOI:10.12082/dqxxkx.2018.170582

WU Enchao,ZHANG Hengcai,WU Sheng. Automatic Generation Method of Indoor and Outdoor Integrated Navigation Network Based on Medial Axis Transform Algorithm[J]. Journal of Geo-information Science, 2018, 20(6): 730-737.DOI:10.12082/dqxxkx.2018.170582

图/表 10

图1

表1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 24

[1]	刘涛,张星,李清泉,等.顾及地标可视性的室内导航路径优化算法[J]. 武汉大学学报·信息科学版,2017,42(1):43-48.
	[ Liu T, Zhang X, Li Q Q, et al.Indoor navigation path optimization algorithm considering the visibility of landmarks[J]. Journal of Wuhan University( Information Science ), 2017,42(1):43-48. ]
[2]	刘涛,张星,李清泉,等.一种运动恢复结构和航位推算结合的室内行人视觉定位方法[J].地球信息科学学报,2017,19(6):744-753.
	[ Liu T, Zhang X, Li Q Q, et al.An indoor pedestrian positioning approach based on the integration of SFM and PDR[J]. Journal of Geo-information Science, 2017,19(6):744-753. ]
[3]	Stanney K M.Handbook of virtual environments:Design, implementation, and applications[M]. ClevelandC: RC Publisher, 2014:135-137.
[4]	张得群,谢传节,裴韬.基于HBase的面向语义单元的室内移动对象索引[J].地球信息科学学报,2017,19(3):307-316. doi: 10.3724/SP.J.1047.2017.00307
	[ Zhang D Q, Xie C J, Pei T.Semantic cell oriented indoor moving objects index based on HBase[J]. Journal of Geo-information Science, 2017,19(3):307-316. ] doi: 10.3724/SP.J.1047.2017.00307
[5]	Li K J.Indoor space: A new notion of space[M]. Berlin: Springer Berlin Heidelberg Press, 2008.
[6]	Walton L, Worboys M.An algebraic approach to image schemas for geographic space[C]. International Conference on Spatial Information Theory. Springer-Verlag, 2009:357-370.
[7]	Giudice N A, Walton L A, Worboys M.The informatics of indoor and outdoor space: A research agenda[C]. Indoor Spatial Awareness-Isa 2010, International Workshop, San Jose, Ca, Usa, November 2, 2010. Proceedings. DBLP, 2010:47-53.
[8]	Worboys M.Modeling indoor space[C]. ACM Sigspatial International Workshop on Indoor Spatial Awareness. ACM, 2011:1-6.
[9]	Stoffel E P, Lorenz B, Ohlbach H J.Towards a Semantic Spatial Model for Pedestrian Indoor Navigation[M]. Berlin: Springer Heidelberg Press, 2007:328-337.
[10]	Stoffel E P, Schoder K.Applying hierarchical graphs to pedestrian indoor navigation[C]. ACM Sigspatial International Conference on Advances in Geographic Information Systems. ACM, 2008:54.
[11]	Lee J.A Spatial Access-Oriented Implementation of a 3-D GIS Topological Data Model for Urban Entities[J]. Geoinformatica, 2004,8(3):237-264. doi: 10.1023/B:GEIN.0000034820.93914.d0
[12]	Lee J, M P Kwan. A combinatorial data model for representing topological relations among 3D geographical features in micro-spatial environments[J]. International Journal of Geographical Information Science, 2005,19(10):1039-1056. doi: 10.1080/13658810500399043
[13]	Becker T, Nagel C, Kolbe T H.A multilayered space-event model for navigation in indoor spaces[M]. Berlin: Springer, Heidelberg Press, 2009:61-77.
[14]	Borovikov I, 2011. Navigation graph generation.,2014-06-02.
[15]	Needell D, Nelson S.Biquasiles and dual graph diagrams[J]. Journal of Knot Theory and Its Ramifications, 2017,26(8):64-76. doi: 10.1142/S0218216517500481
[16]	Lee J.A Three-Dimensional Navigable Data Model to Support Emergency Response in Microspatial Built-Environments[J]. Annals of the Association of American Geographers, 2007,97(3):512-529. doi: 10.1111/j.1467-8306.2007.00561.x
[17]	Choset H M.Principles of robot motion: Theory, algorithms, and implementation[M]. Cambridge: MIT Press, 2005.
[18]	Kneidl A, Hartmann D.Generation and use of sparse navigation graphs for microscopic pedestrian simulation models[M]. Amsterdam: Elsevier Science Publishers, 2012.
[19]	朱欣焰,周成虎,呙维,等.全息位置地图概念内涵及其关键技术初探[J].武汉大学学报·信息科学版,2015,40(3):285-295. doi: 10.13203/j.whugis20140462
	[ Zhu X Y, Zhou C H, Guo W, et al.Holographic location map discussion on the connotation and key technologies[J]. Journal of Wuhan University( Information Science ), 2015,40(3):285-295. ] doi: 10.13203/j.whugis20140462
[20]	Edmonds J.A combinatorial representation of polyhedral surfaces[J]. Notices of the American Mathematical Society, 1960,7:646.
[21]	Tutte W T.What is a map. In: New directions in the theory of graphs[M]. New York: Academic Press, 1973:309-325.
[22]	胡炎,王萍.优化的离散λ-中轴骨架提取算法[J].计算机辅助设计与图形学学报,2017,29(8):1505-1514.
	[ Hu Y, Wang P.Skeleton extraction algorithm for discrete optimization of Lambda-axis[J]. Journal of Computer-Aided Design & Computer Graphics, 2017,29(8):1505-1514. ]
[23]	Birbrair L, Denkowski M P.Medial axis and singularities[J]. Journal of Geometric Analysis, 2017,27(3):2339-2380. doi: 10.1007/s12220-017-9763-x
[24]	Lee D T. Medial axis transformation of a planar shape[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1982, PAMI-4(4):363-369. doi: 10.1109/TPAMI.1982.4767267 pmid: 21869050

导航节点类型	图标	属性
房间门		{坐标,门号,方向,时空限制,备注}
建筑物出入口		{坐标,方向,时空限制,备注}
电梯出入口		{坐标,楼层号,电梯号}
楼梯出入口		{坐标,楼层号,楼梯号}
房间节点		{坐标,房间号,功能,说明}
转向点		{坐标}

基于中轴变换算法的室内外一体化导航路网自动生成方法

Automatic Generation Method of Indoor and Outdoor Integrated Navigation Network Based on Medial Axis Transform Algorithm

RichHTML

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 24

相关文章 2

Metrics

本文评价

推荐阅读 0

[1]	赵明伟, 金永林, 江岭, 王春, 杨灿灿, 徐燕. 多模型协同下的城郊地区DEM构建方法研究[J]. 地球信息科学学报, 2020, 22(3): 389-398.
[2]	杨灿灿, 江岭, 陈昕, 王春, 赵明伟. 面向城市DEM构建的地形要素分类及表达[J]. 地球信息科学学报, 2017, 19(3): 317-325.