Traversable Region Model and Its Automatic Extraction Algorithm for Indoor Navigation
-
摘要: 面向室内位置服务中路径规划与导航的应用需求,提出一种基于栅格空间的通行区域模型及其自动提取算法。首先,在栅格模型基础上引入了相邻栅格和途经栅格,结合具体示例阐述了通行区域模型的基本原理;然后,根据室内地图数据特征,通过室内栅格模型初始化、通行区域初次提取和邻域融合,设计了通行区域的自动提取算法;最后,选取西单大悦城一楼室内地图数据进行了不同栅格尺度的通行区域自动提取和路径规划试验。结果表明,该算法针对走廊内存在障碍等复杂室内环境具有较好的适用性,并且通行区域模型相比网络模型的路径规划结果更加符合复杂室内环境的路径行走特征。Abstract: 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-2]。人类80%~90%时间生活在室内,大型公共建筑的不断出现及其内部结构的日益复杂,促使人们对位置服务的需求从室外延伸至室内环境[3]。路径规划与导航是室内位置服务的重要功能[4],它不仅能够辅助人们在室内空间的行为活动,而且对复杂室内及地下空间的安全管理与应急响应具有重要作用[5]。
多楼层叠加是室内外空间环境的重要区别,室内导航通常采用分楼层路径规划的方式,楼层间通过电梯等跨楼层通行设施实现连通[6]。因此,各楼层路径信息自动提取是实现室内实时导航的关键问题。目前,室内路径模型主要包括语义模型、栅格模型和网络模型等。其中,语义模型原理简单,但是不支持基于最短距离路径规划和规划结果可视化表达[7-8];栅格模型易于创建,但是不适用于大范围室内环境[9-10];网络模型将室内对象的连通关系抽象为具有几何和语义信息的节点及弧段,能够有效支持大范围室内环境路径的规划与导航,是当前应用最广泛的室内路径模型[11-12]之一。
室内路径主要表现为可通行的区域,如走廊、大厅以及房间内部无障碍的空间等。但是,由于网络模型需按照预先构建的几何路网计算最佳路径,从而造成路径规划结果容易存在曲折和迂回等情况[13]。另外,采用Delaunay三角网提取走廊中轴线[14-15]和Door-Door[16]生成房间内部路径的方法,难以处理空间内部存在障碍物等复杂情况[13]。然而,室内导航服务的应用场景多为大型公共建筑,空间结构复杂,现有方法难以实现室内路网的自动提取,需要通过矢量化的方式采集室内路径,从而降低了路径信息的获取效率。
面向室内路径的特征及其自动获取的难点,本文提出一种基于栅格空间描述室内可通行区域边界轮廓及其连通关系的通行区域模型,该模型不仅具备栅格模型易于创建的特点,而且兼具网络模型适用于大范围室内场景的优势。另外,结合室内地图数据特征[17],设计了通行区域自动提取算法。通过具体试验表明,本文算法针对复杂室内环境能够有效实现通行区域的自动提取,相比广泛采用的网络模型,通行区域模型的路径规划结果更加符合人们在室内的路径行走特征。
1 通行区域模型的建模思路和过程
1.1 栅格模型与相邻栅格
栅格模型采用相同间隔对连续室内平面进行二维划分,并根据各栅格所代表实际空间范围内的室内对象特征判断是否可以通行,从而实现连续室内空间的离散化表示。如图 1所示的室内平面环境,图中A、B、C、D分别表示不同的室内空间,d1、d2、d3分别表示出入口,采用某栅格尺度对其进行离散化后结果如图 2所示。由于出入口是连接不同室内空间的重要对象,因此d1、d2、d3所处的栅格作为可以通行的缺口栅格。
本文采用8方向描述相邻栅格邻接关系,按顺时针方向采用整数1~8表示(见图 3)。基于栅格模型采用A*算法可以获取图 2中栅格P至栅格Q之间的最短路径。室内栅格中任意两个目标栅格之间直接通行经过的栅格集合称为途经栅格,具体表现为目标栅格中心点的连线相交的栅格集合(见图 4)。途经栅格是判断栅格之间是否可以直接通行和实现通行区域自动提取的重要基础,仅当两个通行栅格之间的途经栅格均可通行时,它们之间才能够直接通行。
1.2 通行区域模型构建方法
基于栅格模型进行路径规划需要不断遍历当前栅格的相邻栅格,从而判断下一步的行进方向。因此,当室内范围大或栅格尺度小,会导致栅格数目增多,进而增加了路径规划算法的搜索时间,难以满足室内实时路径规划与导航的应用需求。为此,本文在栅格模型基础上构建了通行区域模型,它是对关联相同室内对象的通行栅格进行聚合,从而形成内部任意栅格之间可以无障碍通行的区域,同时建立相邻通行区域之间的连通关系。图 5是图 1中室内平面环境采用通行区域模型表达的路径信息,其中,空白部分表示不可通行的障碍区域,红色虚线分别代表了通行区域R1与R3基于栅格空间的区域范围。
为了实现通行区域的自动提取,本文对传统栅格模型进行了扩展,主要包括关联对象、隶属区域和栅格类型3个方面。关联对象用于表示栅格语义信息,通过关联的室内对象描述,如图 5中栅格a关联对象为室内空间A。隶属区域用于表示栅格所属的通行区域,如果属于多个通行区域,那么所隶属通行区域之间可以通过该栅格实现连通,如图 5中栅格d的隶属区域为R5与R6。本文进一步将通行栅格划分为内部栅格、边界栅格和枢纽栅格3种类型。
1) 内部栅格是唯一隶属于某通行区域R的通行栅格,并且其奇数邻接方向的相邻栅格均为仅隶属于R的通行栅格。如图 5中栅格P与栅格Q分别为通行区域R1和R3的内部栅格。
2) 边界栅格是唯一隶属于某通行区域R,但不属于R内部栅格的通行栅格。边界栅格主要用于描述通行区域的范围,如图 5中栅格k为R5的边界栅格。
3) 枢纽栅格是同时隶属于多个通行区域的通行栅格,它主要用于建立相邻通行区域的连通关系和描述通行区域的范围。如图 5中栅格c、m、l为R4与R5的枢纽栅格。
如图 5所示,R1内栅格P可直接行进至枢纽栅格a,经过D1可以直接行进至枢纽栅格b,再经过R4可直接行进至与R5连通的枢纽栅格c、m、l或与D2连通的枢纽栅格。基于上述原理,采用A*算法得到栅格P至栅格Q的最短路径为P-a-b-c-d-n-p-q-Q。
2 室内通行区域的自动提取
2.1 室内栅格模型初始化
室内栅格模型初始化按照相应栅格尺度生成离散化栅格,同时初始化栅格的类型、关联对象、隶属区域等信息。假设栅格尺度为S,栅格模型初始化的主要流程如下。
1) 划分离散栅格。选取室内地图最小横坐标与纵坐标为原点,沿坐标轴方向采用间隔S将室内平面划分为一系列的离散栅格。栅格尺度越小,反映的室内环境特征越精细,但会导致栅格数目增加,从而影响通行区域的提取效率;栅格尺度较大,反映的室内环境特征越粗略,可能会导致走廊等狭窄室内空间连通性的缺失。
2) 判断栅格属性。如果某室内空间Rs为可通行的区域,那么位于Rs内部的栅格初始化为边界栅格,关联对象为Rs,隶属区域为空;与Rs边界相交的栅格初始化为障碍栅格,关联对象和隶属区域均为空。如果Rs为不可通行的区域,那么与Rs的边界及其内部相交的栅格均初始化为障碍栅格,关联对象和隶属区域均为空。
3) 生成缺口栅格。由于门等缺口依附于墙体等室内空间的边界,从而造成缺口中心点所处栅格在第2)步判断为障碍栅格。因此,如果缺口d中心点位于栅格G内部,那么设置栅格G为缺口栅格,关联对象为d。如图 6所示为图 1中室内平面环境的栅格模型初始化结果,其中缺口栅格G1、G2、G3的关联对象分别为出入口d1、d2、d3。如果初始化之后经过某种方式检验发现存在室内空间连通性缺失的情况,那么需要减小栅格尺度S,并重新进行初始化。
2.2 通行区域初次提取
建立列表RList存储提取到的通行区域,GList[R]存储区域R所有栅格,BGList[R]存储R边界及枢纽栅格。建立待扩展栅格列表SGList和种子栅格SG,通行区域初次提取主要流程如图 7所示,主要包括3个部分。
1) 获取有效种子栅格。通过遍历室内每行栅格或待扩展栅格列表,获取可用于提取通行区域的种子栅格SG,如果某栅格为障碍栅格或已存在隶属区域,则不能作为种子栅格。
2) 提取各个通行区域。以SG为起点新建区域R,通过遍历R边界栅格,不断将满足条件的相邻栅格加入R。其中,BTrav(Gk, R)用于判断Gk是否可以加入R,对于BGList[R]中任意栅格Gi,仅当Gk与Gi之间途经栅格均可通行且不为其他区域的内部及枢纽栅格时,BTrav(G, R)=true。向R添加Gk时,需将R加入Gk隶属区域,同时更新Gk及其相邻栅格的类型。
3) 建立区域连通关系。根据各个缺口区域包含的缺口栅格及其相邻栅格的隶属区域,建立缺口区域与相邻空间区域之间的连通关系。图 6的栅格模型初始化结果经过通行区域初次提取后得到的结果如图 8所示,包含R1~R8共8个空间区域和D1~D3共3个缺口区域。
2.3 通行区域邻域融合
由于室内空间边界不规则等原因,导致初次提取结果通常包含部分栅格数目较少的通行区域,如图 8中R7和R8所示。为降低通行区域复杂度,需要对满足融合阈值和融合条件的区域进行融合。其中,融合阈值是指通行区域的非枢纽栅格小于一定数目;融合条件是指区域融合后不会降低与其连通的通行区域之间的连通性。另外,邻域融合需要按照区域栅格数目由少至多进行。由于出入口是建立相邻室内空间连通性的重要对象,因此缺口区域不可融合。假设某空间区域R满足融合阈值且其连通区域数目为N,若N=0,可直接将R从RList删除;若N=1,仅当R的连通区域不为缺口区域时可以融合,需从其连通区域的枢纽栅格隶属区域中删除R,并将R从RList删除;若N>1,邻域融合的主要流程如图 9所示,主要包括3个部分。
1) 判断R是否满足融合条件。对于R的任意连通区域R1、R2,仅当二者直接连通,或通过某不为R的区域间接连通,或R存在栅格G满足BMerg(G, R, R1)=true且BMerg(G, R, R2)=true,则R满足融合条件。其中,BMerg(G, RA, RB)用于判断区域RA中栅格G至区域RB的可融性,对于BGList[RB]中任意栅格Gi,仅当G与Gi之间途经栅格均可通行且不为除RA与RB外其他区域的内部及枢纽栅格时,BMerg(G, RA, RB) =true。
2) 从R中选取有效扩展栅格。为了将R中栅格尽量融合至相邻区域,需要在R中选取相邻区域共有的栅格进行扩展。首先,从R所有栅格的隶属区域删除R,并更新栅格类型,比如R中内部栅格更新为隶属区域为空的边界栅格;然后,从R中选取隶属区域不为空的边界栅格作为有效扩展栅格,即可以通过该栅格将其相邻栅格加入隶属的通行区域。最后,当R中不存在有效扩展时,邻域融合结束,并将R从RList删除。
3) 将R栅格加入连通区域。通过遍历扩展栅格的相邻栅格,不断地将R中满足隶属区域为空等条件的边界栅格加入扩展栅格隶属的通行区域,同时更新加入边界栅格及其相邻栅格的类型。假设图 8中R7与R8满足融合阈值,R7不满足融合条件不能进行融合,R8存在栅格G(如n、u、x、z)满足BMerg(G, R8, R6)=true且BMerg(G, R8, R7)=true,因此可以进行融合,按照图 9流程进行邻域融合以后得到的结果如图 5所示。
3 试验与分析
选取北京西单大悦城一楼室内地图数据进行通行区域自动提取和路径规划试验,试验数据分为楼层边界、室内空间、出入口和室内路网4层(见图 10)。其中,室内空间包括店铺、天井等类型的面状要素;走廊为楼层边界范围内除去室内空间的部分。
3.1 通行区域提取试验与分析
由于人行走的基本步距约为0.75 m,因此分别采用1.5 m和0.75 m两种栅格尺度进行通行区域的自动提取试验。根据试验区的数据特征,以上两种栅格尺度初始化结果分别如图 11(a)和图 11(b)所示。通过图 11可以看出,采用以上两种栅格尺度进行初始化后均未造成室内空间连通性的缺失。
图 11(a)经过通行区域初次提取得到90个空间区域和35个缺口区域(见图 12(a))。设置图 12(a)融合阈值为9个栅格,经过邻域融合后剩余69个空间区域和35个缺口区域(见图 12(b))。
图 11(b)经过初次提取得到128个空间区域和29个缺口区域(见图 13(a))。根据1.5 m栅格尺度融合阈值对应的实际室内面积,设置图 13(a)融合阈值为36个栅格,经过邻域融合后剩余75个空间区域和35个缺口区域(见图 13(b))。可以看出,栅格尺度越小,初次提取的通行区域数目相对较多,特别是几何特征较为复杂的室内空间需要进行邻域融合的通行区域数目较多;不同栅格尺度最终提取的通行区域数目差别较小,邻域融合后的通行区域能够较好地反映室内主要路径信息。
3.2 室内路径规划试验与分析
选取“APPLE”中心为起点,终点为“NHIZ”,采用相同试验环境和A*算法,分别基于室内路网和通行区域数据进行路径规划,结果如图 14所示。其中,基于图 10中室内路网规划距离为134.51 m,路径规划平均耗时20.94 ms;基于图 12(b)中通行区域规划距离为125.99 m,路径规划平均耗时53.27 ms;基于图 13(b)中通行区域的规划距离为122.51 m,路径规划平均耗时78.04 ms。可以看出,通行区域模型相比网络模型能够有效改善路径规划结果存在较多曲折等情况,更加符合复杂室内环境路径行走特征;路径规划耗时相对较长,但能够满足实时路径规划应用需求。基于北京智慧图公司室内位置服务平台和图 13(b)提取的通行区域,实地进行了路径导航试验(见图 15),验证了通行区域模型对满足大范围室内场景中实时路径规划与导航的适用性。
4 结语
室内路径信息自动获取是实现大规模精准室内导航服务的重要基础,也是当前亟需解决的关键技术之一。本文面向室内路径信息的特点,提出一种适用于室内路径规划与导航的通行区域模型,并设计了通行区域的自动提取算法,有效实现了室内路径信息的自动获取。
本文建立的通行区域模型相比当前广泛采用的网络模型,能够有效改善路径规划结果容易存在曲折等情况,不仅能够满足路径实时规划与导航的应用需求,而且更加符合人们在复杂室内环境的路径行走特征;另外,通行区域自动提取算法能够有效适应大型公共建筑的复杂室内环境。
本文分别选取了两种栅格尺度进行了通行区域自动提取和路径规划试验,并对试验结果进行了对比分析。面向不同室内空间特征的大型公共建筑,还需要对不同栅格尺度的适用性进行更为深入的分析,这将是本文下一步的研究内容。
-
-
[1] 周成虎, 朱欣焰, 王蒙, 等.全息位置地图研究[J].地理科学进展, 2011, 30(11):1331-1335 doi: 10.11820/dlkxjz.2011.11.001 Zhou Chenghu, Zhu Xinyan, Wang Meng, et al. Panoramic Location-based Map[J]. Progress in Geography, 2011, 30(11):1331-1335 doi: 10.11820/dlkxjz.2011.11.001
[2] 朱欣焰, 周成虎, 呙维, 等.全息位置地图概念内涵及其关键技术初探[J].武汉大学学报·信息科学版, 2015, 40(3):285-295 http://ch.whu.edu.cn/CN/abstract/abstract3199.shtml 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 http://ch.whu.edu.cn/CN/abstract/abstract3199.shtml
[3] 游天, 周成虎, 陈曦.室内地图表示方法研究与实践[J].测绘科学技术学报, 2014, 31(6):635-640 doi: 10.3969/j.issn.1673-6338.2014.06.018 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 doi: 10.3969/j.issn.1673-6338.2014.06.018
[4] Gilliéron P Y, Büchel D, Spassov I. Indoor Navigation Performance Analysis[C]. European Navigation Conference GNSS, Rotterdam, Netherlands, 2004
[5] 朱庆, 熊庆, 赵君峤.室内位置信息模型与智能位置服务[J].测绘地理信息, 2014, 39(5):1-7 http://d.old.wanfangdata.com.cn/Periodical/chxxygc201405001 Zhu Qing, Xiong Qing, Zhao Junqiao. Indoor Location Information Model and Intelligent Location Service[J]. Journal of Geomatics, 2014, 39(5):1-7 http://d.old.wanfangdata.com.cn/Periodical/chxxygc201405001
[6] 林浩嘉, 罗文斐.多层建筑空间的分层最优路径算法实现[J].地球信息科学学报, 2016, 18(2):175-181 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201602005 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 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201602005
[7] Brumitt B, Shafer S. Topological Word Modeling Using Semantic Spaces[C]. Ubicomp Workshop on Location Modeling for Ubiquitous Computing, Georgia, USA, 2001
[8] 石朝侠, 洪炳镕, 周彤, 等.大规模环境下的拓扑地图创建与导航[J].机器人, 2007, 29(5):433-438 doi: 10.3321/j.issn:1002-0446.2007.05.004 Shi Chaoxia, Hong Bingrong, Zhou Tong, et al. Topological Map Building and Navigation in Large-scale Environments[J]. Robot, 2007, 29(5):433-438 doi: 10.3321/j.issn:1002-0446.2007.05.004
[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] 董元元, 崔祜涛, 田阳.基于栅格地图的火星车路径规划方法[J].深空探测学报, 2014, 1(4):289-293 http://d.old.wanfangdata.com.cn/Periodical/sktcxb201404007 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 http://d.old.wanfangdata.com.cn/Periodical/sktcxb201404007
[11] 徐战亚, 钟塞尚, 王媛媛.一种易于更新的室内导航路网构建方法[J].计算机仿真, 2015, 32(12):267-275 doi: 10.3969/j.issn.1006-9348.2015.12.057 Xu Zhanya, Zhong Saishang, Wang Yuanyuan. Indoor Navigation Network Construction Method with Ability to Update Conveniently[J]. Computer Simulation, 2015, 32(12):267-275 doi: 10.3969/j.issn.1006-9348.2015.12.057
[12] 穆宣社, 游雄.支持突发事件应急反应的建筑物内部交通网络分析[J].测绘科学技术学报, 2006, 23(6):635-640 http://d.old.wanfangdata.com.cn/Periodical/chxyxb200606006 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 http://d.old.wanfangdata.com.cn/Periodical/chxyxb200606006
[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 http://d.old.wanfangdata.com.cn/Periodical/dqkjxxkxxb-e201102006
[14] 潘鹏, 贺三维, 吴艳兰, 等.曲边多边形中轴提取的新方法[J].测绘学报, 2012, 41(2):278-283 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK201201166467 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 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK201201166467
[15] 艾廷华, 郭仁忠.基于约束Delaunay结构的街道中轴线提取及网络模型建立[J].测绘学报, 2000, 29(4):347-353 http://d.old.wanfangdata.com.cn/Periodical/chxb200004012 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 http://d.old.wanfangdata.com.cn/Periodical/chxb200004012
[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] 孙卫新, 王光霞, 张锦明, 等.源自建筑平面图的室内地图空间数据自动生成方法[J].测绘学报, 2016, 45(6):731-739 http://d.old.wanfangdata.com.cn/Periodical/chxb201606014 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 http://d.old.wanfangdata.com.cn/Periodical/chxb201606014
-
期刊类型引用(7)
1. 朱军,陈佩菁,曾超,郑全红,谢亚坤,游继钢,廉慧洁. 知识引导的森林火灾逃生路网动态生成方法. 测绘学报. 2024(06): 1086-1097 . 百度学术
2. 江帆,刘一凡,朱真才,张超凡,周公博,彭玉兴. 基于多特征融合的煤矿井下辅助运输车辆可通行性评估方法. 煤炭学报. 2024(12): 4986-5001 . 百度学术
3. 韩李涛,周丽娟,龚城,张爱国. 顾及步行习惯的室内导航网络及其生成算法. 测绘学报. 2022(05): 729-738 . 百度学术
4. 朱豫,周京春. 地下建筑物室内疏散引导地图的构建. 导航定位学报. 2022(06): 97-106 . 百度学术
5. 刘明蕾,危双丰,黄帅,汤念. 利用细化空间分隔法的房间细部级室内导航元素提取. 武汉大学学报(信息科学版). 2021(02): 221-229 . 百度学术
6. 李华蓉,彭映雪,李海明. 室内楼层平面导航路网模型的自动生成. 测绘通报. 2021(04): 79-84+104 . 百度学术
7. 邬群勇,曾庆权,张爱国. 一种全球离散格网系统框架下的室内空间网格数据模型. 导航定位学报. 2020(02): 55-62 . 百度学术
其他类型引用(7)