基于图的语义室内导航模型构建研究

林 雕，宋国民，邓 晨

（郑州测绘学院，河南 郑州450052）

随着城市化进程不断加快，大型建筑物内部构造变得愈加复杂，加重人们的空间认知负担，使得室内寻路变得更加困难，特别是在商场等大型公共场所，室内“迷路”的情况尤为突出［1］，室内导航也因此得到更多的关注。室内空间模型则是实现室内导航的基础和关键所在。目前已提出多种面向室内导航的空间模型，早期常见的符号模型将室内空间对象表示为带有特定ID标识的符号元素［2］，用于表达室内空间元素的相互关系。这类模型符合人的空间认知特性，但缺少对室内的几何描述，且只能给出粗略的路径描述。为实现对室内几何和拓扑的统一描述，Lee等利用对偶图的方法将室内空间抽象表示为节点和边［3］，并通过中轴变换的方式将二维的通道转换为一维的线，构建3维室内拓扑数据模型。这种几何图的建模方式得到广泛的认可，主要用于构建室内道路网络［4－5］。Yuan等则认为“门－门”的建模方式更加符合用户的行为习惯［6］，提出将门抽象表示为节点，门之间的连接表示为边，该模型可以支持非绕行的最优室内寻路并通过增加可视点的方式保证节点之间的通视性。文献［7－8］等也均采用这种室内空间抽象方式。另外，文献［9－10］等则重点考虑用户相关因素（如移动能力、寻路的喜好等）对建模的影响，侧重于室内本体建模，并依据本体之间的推理关系来实现个性化的路径导航。这类模型通常缺少对图模型具体构建方式的描述，且没有将可视性纳入考虑。

在当前已有室内空间模型中，多数模型在建模过程中只考虑部分导航相关的影响因素，适用范围有限。针对该问题，本文基于图论的建模方法，综合考虑用户室内移动特征、几何和语义信息表达以及路径规划效率等多个导航相关的影响因素，提出一种支持多情景应用并符合用户空间认知特性的室内导航空间模型。

1 基于图的语义室内导航模型构建

1．1 思路

传统的室外导航主要是基于交通网络数据模型完成［11］，但对于室内而言则没有同室外一样明确的道路网络，当用户从室外进入室内后，行为习惯也会随之改变［12］，室内外空间认知特性上的差异导致用户行为习惯的不同。因此，需针对室内空间特性构建适合于室内的导航模型。基于图论的建模方法将现实世界抽象表示为节点和边构成的图，可以用于构建室内道路网络模型。对于基于图的室内导航模型构建主要需考虑以下几个问题：

1）用户室内移动特征：不同于室外路网，室内空间没有明确的路径信息，用户在室内移动具有更大的随意性，但同时又具有一定的规律性［7］。一般情况下两个房间之间的移动借助于室内过道且沿着过道中间行走，此时可用中轴线表示过道。房间内部的移动则按照门到门的方式，可将门抽象表示为节点。同时，可视性在室内寻路过程中有很重要的作用，可通过增加可视节点的方式保证通视。例如，对呈L状的房间而言，在构建路网时可将两个门之间的凹点表示为可视点。

2）几何和语义信息表达：模型中节点和边需包含相应的坐标信息以便支持基于长度的最短路计算和路径可视化。语义信息是实现室内导航的关键所在，需将节点所表示的空间类型、通道的方向性、门的开关时间、节点之间的权值等语义信息通过节点和边的属性信息来表示。

3）路径规划效率：室内空间相对狭小，用户移动更加自由，对路径规划的实时性提出了更高要求，特别是在计算能力有限的移动平台环境下，因此要求室内导航模型应尽可能的简单，以便实现高效的路径规划。对于基于图的空间模型而言，主要通过减少图元数的方式来提高路径规划效率。对于有多个出口的过道而言，相对于中轴线法，若采用“门－门”建模方式会大幅增加模型中的图元数，使得路径规划的查询效率有所下降[8]。

1．2 基于图的室内导航概念模型

室内空间中包含有诸多构件，导航模型中则需要重点描述和路径相关的空间对象。综合考虑用户室内移动特征、几何和语义信息表达、路径规划效率等要求，利用图的建模方法提出室内导航概念模型（见图1），该模型中各元素与室内构件之间存在一一对应关系，可用于支持室内的导航推理。下面给出图1中各元素的具体解释：

Exit＿Node：各空间实体的出口节点。

Stair＿Exit：表示楼梯出口节点，每个楼梯对应有两个节点，分别对应于两个不同楼层的出口。

Elevator＿Exit：表示电梯出口节点，电梯所能到达的每一个楼层的出口均需表示为节点。

Escalator＿Exit：表示自动扶梯出口节点，每个自动扶梯对应有两个节点，分别对应于两个不同楼层的出口。

Room＿Exit：表示房间出口节点，包括Room＿Door＿Exit和 Roo m＿Window＿Exit两类，其中Roo m＿Door＿Exit表示房间对应的门节点，Room＿Window＿Exit表示房间对应的靠近室外的窗户节点，在紧急救灾等特殊情况下作为室内的通行路径，正常情况下将其设置为不可通行点。

Buil ding＿Exit：表示建筑物出口节点，用于建立室内外之间的联系，以便实现室内外一体的路径规划。

Corridor＿Node：表示通道上的所有节点。Cross＿Point：表示两个通道的交叉节点。Window＿Point：表示 Roo m＿Window＿Exit在通道上的垂直投影点。

Door＿Point：表示 Roo m＿Door＿Exit在通道上的垂直投影点，以此建立通道和房间之间的连接。

Conner＿Point：表示通道尽头的角落节点。

Inner＿Node：表示房间内部节点，对于凹多边形房间而言，通常需要在凹点处添加节点以便构成室内通视路网。

Horizonal＿Edge：表示水平方向上的连接边，主要用于同一楼层两个位置之间的路径规划。

Inner＿Segment：表示房间内部路径片段，由Roo m＿Exit和Inner两类节点构成，主要用于房间内部寻路。

Joint＿Seg ment：表示房间出口和过道的连接边，由Door＿Point和对应的 Roo m＿Door＿Exit以及Roo m＿Window＿Exit和对应的 Window＿Point节点组成。

Corridor＿Seg ment表示各通道上的路径片段，由通道上的 Cross＿Point、Window＿Point、Door＿Point、Conner＿Point节点构成。

Connect＿Seg ment：表示水平方向和垂直方向的连接边，通常由Corridor节点和Stair＿Exit、Elevator＿Exit、Escalator＿Exit三类节点组成。

Vertical＿Edge表示垂直方向的连接边，主要用于楼层之间的路径规划，包括有楼梯、电梯、扶梯，分别由 Stair＿Exit、Elevator＿Exit、Escalator＿Exit三类节点组成。

Transfer＿Edge：表示室内外之间的连接边，其中有一个节点是Building＿Exit。

图1 室内导航概念模型

1．3 几何图模型构建方法

单纯的只表示空间拓扑关系的图模型不能满足距离量算、路径可视化的要求，需给节点和边附上相应的坐标信息，构建一个三维的室内道路网络，其中主要包括出口节点定位点求取、走廊中轴线求取以及内点求取。

出口节点定位点求取：在几何平面图上，通常将门等出口表示为一维的线，此时选取该线中点作为节点定位点。如图2所示，取门线的中点作为门的定位点，同样的方法可用于处理电梯、楼梯、自动扶梯、建筑物出口等。

图2 门对应定位点

通道中轴线求取：通过中轴变换的方式可将通道从二维的面转换为一维的线，针对通道的一般外形特征，选用基于Delaunay三角剖分的中线法作为室内通道提取算法。主要原理如下：1）提取通道多边形轮廓特征点；2）对多边形边界弧段上的矢量点做加密处理，使得有更多间距接近的点参与构网；3）以多边形边界为约束条件构建约束Delaunay三角网；4）按照三角形所拥有的邻近三角形数量，将三角形分为三种类型：I类三角形的中轴线定义为其重心与非边界边中点的连线；II类三角形的中轴线定义为其两条非边界边各自中点的连线；III类三角形的中轴线定义为其重心分别与三条非边界边中点的连线，最终得到对应的通道中轴线（如图3所示），基于Delaunay三角剖分的中线法的细节可参阅文献［13－15］。

图3 通道中轴线提取示意图

内点求取：凹多边形房间内部两个门之间可能存在不可视的情况，通过增加节点作为路径的中间点确保房间内部的可视性，主要步骤包括：①判定多边形的凹凸性质，如存在内角大于180°的多边形则为凹多边形，否则为凸多边形；②如果是凹多边形，判断两个门之间是否可视，判定方法为连接两个门线中点，若连线在多边形内则表示可视，否则不可视；③若两个门之间不可视则增加凹点作为其中间点，凹点的选取原则为保证两个门之间的路线最短。例如，图4中门d2和门d3之间存在不可视的情况，此时可添加凹点v作为路径中间节点以确保房间内部节点的可视性。

图4 凹多边形内部节点连接

1．4 基于模型的语义信息表达

语义信息是实现个性化室内导航的关键，由于室内空间的语义信息众多，这里重点考虑与导航相关的语义信息表达，常见的有以下几类：

1）门的私有或公有属性，例如某些房间只有特定的用户可以进入，一般不能将其作为普通用户的通行路径。

2）门、电梯等出口开关时间，通常情况下室内中某些场所有其固定的开关时间，例如超过某个时间点，电梯将不可以使用。

3）通道的方向性，与室外类似室内空间中也有部分单向通道，例如上下楼的扶梯只限定于某一个特定的方向。

一般通过给节点和边附加属性信息的方式来实现语义信息表达，由于各节点和边所描述的对象有所不同，对应的语义信息也有所差异，借鉴文献［8］所提的N×ID→SI（其中N表示节点编号、ID表示语义信息类型，SI表示具体的语义信息）语义信息表达方式，通过节点的唯一编号指定各节点所表达的语义信息，同样可将该方法扩展应用于边的语义信息描述。例如，对于一个Room＿Door＿Exit类型的节点n3，可附加一个可进入时间的属性（n3，accessibility）＝“08：00－20：00”，用来表示该门的开关时间在08：00－20：00之间。另外，针对室内单向道路较少的特点，为减少建模工作量，避免构建有向图模型，同样将其作为属性信息描述，如对于边e3而言，（e3，direction）＝1，表示该边的方向是从首节点到尾节点，－1表示反向，0则表示该边是双向通行的。实际应用中可根据需求，给节点和边增加更多的语义信息，如电梯的等待时间、承载人数等。

1．5 图模型数据结构

图模型中主要包括节点和边两类，根据室内导航应用需求，主要考虑几何、拓扑、语义三类相关信息，采用如表1、表2的基本数据结构。其中，节点表中存储的基本信息包括节点编号、类型、是否可用、所在楼层、相连边数、连接边编号以及对应的几何坐标；边表中存储的基本信息包括边编号、类型、首尾节点编号、是否可用、权值、方向以及对应的几何坐标。另外，节点类型（Node＿Type 和边类型（Arc＿Type）分别和图1中各元素类型相对应。Active属性表示对应的节点或边是否可用，若节点不可用则将该点设置为路径规划的绕行点，边不可用则将其对应的权值设置为无穷大。需要指出一点，可根据实际应用需求，利用章节1．4中所提语义信息描述方式来对表1和表2中的基本数据结构作相应扩展。

表1 节点数据结构表

表2 边结构数据表

2 基于模型的路径规划

在室内导航模型基础上主要通过以下两个步骤来实现路径规划。

2．1 根据当前应用情景，更新路网中节点和边的属性信息

主要通过更新节点Active、边Active和Weight 3个属性项的值来建立情景与导航之间的联系。首先判断当前时间下哪些节点和边为不可用，假设当前时间为21：00，且有（n3，accessibility）＝08：00－20：00，则可以推断出n3所表示的门是不可进的，此时应将n3对应的Active属性值设置为“N”，然后将其对应的属性为Joint＿Seg ment的边权值设置为无穷大表示该门与过道之间不可通行；其次根据用户身份信息来排除不适合的路径节点和边，例如，对于一个坐轮椅的用户而言，则不能将楼梯或者是自动扶梯作为其上下楼的通行路径，此时应将类型为Stair和Escalator的边Active属性值设置为“N”，表示该路径不可通行，其他的一些用户相关的语义信息还包括用户年龄、移动能力、感知能力、用户特权等，分别对应于不同的路径选择规则；最后判断用户的喜好对路径的影响，如当用户推着婴儿车上楼时则更加偏向于带电梯的路径，即使有可能导致绕路。实际应用中还存在其他的一些情况需单独考虑，如在发生火灾情况下，应将电梯排除在所选路径之外，同时可将窗户作为特殊的通行路径，另外还需给模型附加上更多的语义信息（如走廊的最大人流量、区域的烟雾浓度等），并建立相应的数学模型来实现对边权值的更新，以便规划出一条合理的撤退路线。

2．2 最优路径计算

在完成路网属性值更新后，则可根据用户的需求选定相应节点作为路径规划的起点和终点。然而，一般情况下的室内寻路通常是将某个特定的房间作为用户的目标位置，此时可分别将该目标区域对应所有可用出口节点作为目标节点，将距离当前用户位置最近的节点作为路径规划起点，选用成熟的路径规划算法（例如Dij kstra算法）计算起点到目标区域不同出口之间的权值，最后选用权值最小的路径作为最优路径。

3 结束语

本文基于图论的方法构建一种语义室内导航模型。该模型综合考虑几何、拓扑、语言三类信息的表达，且通过增加内点的方式保证房间内部的可视性，模型中节点和边与室内实体之间存在一一对应关系，可用于支持室内的导航推理，并可通过更新模型中节点和边属性值的方式建立情景和模型之间的联系以便支持不同情景应用下的室内导航，为构建情景感知的室内导航模型提供借鉴和新的思路。此处没有给出用户相关因素的具体建模，实际应用中可根据需要定义相适应的用户模型，利用本文所提的属性值更新方法实现不同情景下的路径导航。

［1］ SCHOUGAARD，KARI R，KAJ G，et al．Indoor pedestrian navigation based on hybrid route planning and location modeling［J］．Pervasive Co mputing，2012：289－306．

［2］ BRUMITT B，STEVEN SHAFER．Topological world modeling using semantic spaces［C］／／Proceedings of t he Wor kshop on Location Modeling for Ubiquitous Computing，Ubi Comp．Vol．2001：55－61．

［3］ LEE JIYEONG．A Spatial Access－Oriented Implementation of a 3－D GIS Topological Data Model for Urban Entities［J］．Geoinf or matica，2004，8（3）：237－264．

［4］ THILL J C，DAO T H D，ZHOU Y．Traveling in the t hree－di mensional city：applications in route planning，accessibility assess ment，location analysis and beyond［J］．Journal of Transport Geography，2011，19（3）：405－421．

［5］ 穆宣社，游雄．支持突发事件应急反应的建筑物内部交通网络分析［J］．测绘科学技术学报，2007，23（6）：408－410．

［6］ YUAN WENJIE，MARKUS S．Inav：An indoor navigation model supporting length－dependent opti mal routing［J］．Geospatial Thinking，2010：299－313．

［7］ LIU L，ZLATANOVA S．A door－to－door path finding approach for indoor navigation［C］／／Proceedings of GeoInf or mation For Disaster Management Conference．2011：3－8．

［8］ GOETZ M，ZIPF A．For mal definition of a user－adaptive and length－opti mal routing graph f or complex indoor environ ments［J］．Geo－Spatial Infor mation Science，2011，14（2）：119－128．

［9］ ANAGNOSTOPOULOS C，TSETSOS V，KIKIRAS P．Onto Nav：A semantic indoor navigation system［C］／／1ST Workshop on Semantics in Mobile Environments（SME05），AYIA．2005．

［10］DUDAS P M，GHAFOURIAN M，KARI MI H A．ONALIN：Ontology and algorith m for indoor routing［C］／／Mobile Data Management：Systems，Services and Middleware，2009．MDM＇09．Tenth International Conference on．IEEE，2009：720－725．

［11］张晓楠，任志国，曹一冰，等．交通运输最短路径分析系统的设计与实现［J］．测绘工程，2014，23（1）：25－30．

［12］GILLIÉRON P Y，MERMINOD B．Personal navigation system for indoor applications［C］／／11th IAIN World Congress．2003：21－24．

［13］艾廷华，郭仁忠．基于约束Delaunay结构的街道中轴线提取及网络模型建立［J］．测绘学报，2000，29（4）：348－354．

［14］李萌，李伟，钱凌韬．基于文本挖掘的个性化地图服务模型研究［J］．测绘与空间地理信息，2014，37（5）：39－41．

［15］卢伟，魏峰远，张硕，等．基于Zig Bee的室内位置服务应用研究［J］．测绘与空间地理信息，2014，37（10）：75－77．