顾及步行习惯的室内导航网络及其生成算法

韩李涛，周丽娟，龚 城，张爱国

1. 山东科技大学测绘与空间信息学院，山东 青岛 266590； 2. 山东省基础地理信息与数字化技术重点实验室，山东 青岛 266590； 3. 厦门理工学院计算机与信息工程学院，福建 厦门 361024

随着全球城市化进程加快及现代建筑技术飞速发展，城市大型建筑越来越多，室内环境结构越来越复杂，而现代人的学习、工作、生活、娱乐等活动大部分都是在室内进行。因此，室内定位与导航已成为当前导航领域的一个研究热点[1-3]。室内导航涉及室内定位、路径规划、导航地图、导航网络等关键内容，其中室内导航网络作为室内路径规划与导航的基础，其网络结构与几何形态对路径规划效率和结果都具有至关重要的影响。

当前，将室内可通行空间转换成网络模型通常有两种方式：一是栅格化可通行空间，构建栅格网络模型，该模型在机器人导航或人群疏散仿真等领域应用较多[4-5]；二是依据室内空间的连通关系或可见性，构建矢量网络模型，该模型网络结构简单，多应用于个体室内路径规划和导航[6-7]。依据矢量网络生成原理不同，室内矢量网络模型生成方法可分为3类：骨架线法、可视图法和对偶映射法。骨架线法是根据建筑物的几何信息，将可通行区域视为多边形，提取出多边形的骨架线作为室内导航网络。常用的骨架提取方法包括中轴变换[8]、直中轴变换[9]、约束Delaunay三角剖分法[10-11]及基于栅格形式的数学形态学方法。该方法生成路线形态在通道交叉口或转弯处不符合人们的行走习惯[5]。可视图法是将起点和环境中的所有其他顶点进行组合连接，要求起点和各个顶点之间的连线不能穿越障碍物[12]，其优势在于对相互可通视的两个顶点进行直线连接，符合人“抄近路”的习性，但当障碍物数量变多时，路网复杂度将大大增加，且生成的导航路径具有“趋边性”，即过于贴近墙体。基于可视性的改进方法包括利用“门-门”可视性的寻径[13]、基于地标可视性的室内寻径[3]等。文献[13]考虑了室内步行习惯，但对于凹形室内空间或狭窄走廊空间，生成路径的“趋边性”仍然较为明显。文献[14]提出将室内可通行空间网格化，依据网格单元的可视度来提取可通行区域中的关键路径结点，连接后形成室内导航网络。该方法生成的路网形态仅仅取决于可通行空间形状和网格化粒度，且需要先网格化可通行空间。对偶映射法主要根据庞加莱对偶理论来表达室内空间之间的拓扑映射与连通关系。早期模型有NRS模型、扩展NRS的GNM模型[9]。在对室内空间进行建模时，该方法将室内空间实体映射为室内路网中的不同要素，如将房间映射为结点、房门映射为结点之间的连线等，实现了建筑空间到拓扑空间的对偶转换，但路网的几何形态需要改进。除了合理的路网几何形态和拓扑连接关系，室内导航网络的语义支持能力也受到了更多关注[15-17]。另外，利用室内行人轨迹数据来提取室内导航网络[18]是一种新的尝试，但目前海量室内轨迹数据仍不易获取。

总之，现有室内导航网络模型更多考虑了可通行空间几何形态对室内路网的约束，缺乏对人行为习性的考虑，导致路网拓扑连接结构不合理、路径形态不符合人自然行走规律。因此，本文顾及室内可通行空间尺度、人的“抄近路”习性及避碰安全性需求等要素，提出了一种更加符合人室内行走习惯的室内导航网络模型，并基于“空间分割”思想设计了简单高效的网络生成算法。

1 室内导航网络模型

人的行为习性主要指人类普遍存在的一些行为特征或规律，是人类适应环境的本能行为。“抄近路”习性是人的典型行为习性之一[19-20]，即人在选择路径时会选择当前位置与目标位置之间的最短路径。当将室内空间映射为室内导航网络时，房间形状相对简单，可将其几何中心映射为结点，并通过门结点连接到走廊路网上；而走廊空间作为连接室内房间与室外空间的公共空间，其形状往往较为复杂。因此，如何提取走廊空间中的路网是室内导航网络构建的关键。

由于人在不同室内尺度空间下行走时会表现出不同的特性，因此本文将走廊空间分割为狭窄走廊空间和开阔走廊空间后分别处理。若不考虑障碍物，当人们在狭长楼廊空间行走时，为了保持行走自如和安全，一般会离开墙壁一定距离，选择沿走廊中心线行走；而当人们通过具有多个连接口的开阔走廊空间(如门厅)时，基于抄近路习性人们一般选择当前位置与目标连接口之间的直行路线行走。如图1所示，当行人从door0到door1时，一般会沿图1(c)路径行走，而不会沿图1(a)或(b)路径行走。因此，本文提出的室内导航网络将狭窄走廊中线作为对应空间的路网，将开阔走廊连接的门或通道口连接形成完全图作为对应空间的路网，各部分组合后形成完整导航路网。

图1 不同室内导航网络及生成的最短路径Fig.1 Different indoor navigation networks and generated shortest paths based on them

2 室内导航网络生成方法

目前，室内点云、建筑平面图、BIM数据等都可用来构建室内路网，但建筑平面图仍然使用最广且容易获得。因此，本文以建筑平面图为数据源来生成室内导航网络。基本思路为：①利用建筑平面图丰富的几何信息和语义信息，提取房间、走廊、门窗等室内空间实体，并建立室内空间拓扑模型；②根据走廊多边形顶点的凹凸性和走廊分区空间尺度，将走廊空间分割为较大开阔空间和狭窄走廊空间，提取通道口结点，并构建走廊分区拓扑模型；③将开阔空间以完全图形式连成路网，狭窄走廊空间以中线作为路径，同时将门结点垂直相交于该中线路径，普通房间以房间中心到门结点的连线为路径，最终形成完整室内导航网络。

2.1 室内空间提取

建筑平面图包含了丰富的建筑实体信息(墙体、门窗、电梯、楼梯、注记等)，但缺乏以房间为实体对象的室内空间描述和拓扑信息。因此，首先借鉴文献[21]方法恢复墙线的连通性，然后采用文献[22]提出的方法提取房间和走廊对象并构建室内空间拓扑模型。该模型用于描述门、墙线、房间(含走廊)之间的拓扑关系，主要包括4个表。

(1) 墙角点表V(墙角点ID，坐标值)，用于记录连通性恢复后的室内空间墙角点信息。

(2) 墙线-墙角点表E(墙线ID，起始点ID，终止点ID)，用于描述墙线与墙角点之间的拓扑连接关系。

(3) 房间-墙线表R(房间ID，墙线，房间中心坐标，门数量，房间类型)，用于描述单个房间所包含的墙线、房间几何中心坐标、房间类型。房间类型包括走廊和普通房间。普通房间作为建筑内部相对封闭的私密空间，包含门数一般1～3个；而走廊作为连接建筑内部许多房间单元的公共通行空间，通常会连接着许多门，表现为一个楼层对应一个连通的整体走廊。因此，当多边形包含门数大于设定阈值Nd时，则记录为走廊；否则记录普通房间。Nd可以依据建筑类型自行设定，本文设置Nd=5。

(4) 门-房间表D(门ID，坐标值，墙线，房间ID)。根据提取的门坐标，先建立门与墙线之间的拓扑关系，再根据墙线与房间的关系用于描述门与房间的拓扑关系。

提取多边形时，首先将房间多边形区分为边界多边形、房间多边形和孤岛3种情况，然后通过方位角判断来顺时针或逆时针追踪后续墙线，返回原点即完成一个多边形提取，直到所有墙线被记录两次则完成所有多边形提取[22]。房间多边形提取原理如图2所示，对应的房间-墙线表见表1。

图2 房间多边形拓扑关系模型构建Fig.2 Construction of topological relationship model of room polygon

表1 房间-墙线表

2.2 走廊空间分割

对于简单凸多边形房间，依据上述房间-墙线表和门-房间表，可直接连接房间中心点和门形成房间内部网络。然而，走廊空间(包括复杂形状房间)一般呈非凸多边形，采用“door to door”的思想直接将房门连接会导致路径穿墙。因此，需要先将走廊空间分割为狭窄走廊空间和开阔走廊空间，然后依据其大小、形状以及人的行走习惯来生成该空间路网。

2.2.1 判断顶点凹凸性

顶点凹凸性是多边形重要的形状特征[23]。设α为多边形某顶点的对应内角，当α为优角(180°<α<360°)时，该顶点称为多边形的凹点；当α为劣角(0°<α<180°)时，该顶点称为多边形的凸点。当α=180时，对应顶点对于多边形的形状影响不大(如图2中C4)，所以只需保留走廊的凹凸顶点用于反映走廊的形状特征。在可通行多边形内，凹点可能会影响人的可视范围和路径选择，所以需要同时标识凹点。

具体过程为：将构成走廊封闭面点集合Corridor进行筛选，仅保留构成走廊的凸点和凹点，形成新的走廊列表NCorridor,NCorridor={C1,C3,C5,C9,C8,C12,C11,C7,C6,C0}，如图2(b)所示。此时走廊的构成依旧是逆时针，不改变其顺序。同时，更新走廊自身的墙线表，墙线表包含墙线ID、起点点号、终点点号。

2.2.2 走廊空间分割

图3 走廊空间分割原理Fig.3 The principle of corridor space division

特殊情况下，若某凹点对应的两条分割线L1、L2均小于τ，则两条均要保留，并提取对应的通道口结点；若L1、L2均大于τ，则标记该凹点，以便于后续判断该凹点是否遮挡该走廊分区内的路径。

为便于后续计算，需要记录交点和通道口结点的拓扑关系，生成交点表。除记录交点坐标、所在墙线ID以及对应凹点外，还需标记该交点是否为新增角点(因走廊分割时生成的交点可能会与走廊原有角点重合)，见表2。同时，构建通道口结点表P记录(通道口结点ID，坐标)。

表2 交点表

2.2.3 构建走廊分区拓扑模型

完整描述走廊空间分割后，各实体要素之间的拓扑连接关系及几何特征对于走廊内路网的构建非常关键[24-25]。走廊分区拓扑模型需要描述分区-墙线、分区-门结点、分区-通道口结点等对象之间的拓扑关系，主要由分区角点表V′、墙线-分区角点表E′以及走廊分区表R′实现。各自构建过程如下。

(1) 分区角点表V′(角点ID，坐标)，将新增交点集合加入到原墙角点V集合即可。

图4 走廊分区拓扑模型Fig.4 Topological model of corridor partition

(3) 走廊分区表(分区ID，墙线，门结点ID，通道口结点ID)。根据更新后的分区角点表和墙线-分区角点表，采用2.1节中的房间多边形提取方法重构走廊分区与墙线、分区与对应通道口结点以及分区与门结点之间的拓扑连接关系，并存储在走廊分区表中，见表3。该表完整记录了分区与对应的墙线、 通道口结点以及门结点之间的连接包含关系。

表3 走廊分区表

2.3 室内导航网络生成

图5 室内导航网络生成原理Fig.5 Indoor road network based on corridor topological model

当相邻分割空间都属于狭窄区域时，本文方法也能够得到较为符合室内行走习惯的路网结构。在狭窄通道区域行走时，人们通常会沿通行区域中线行走，而在转弯路口、“T”路口或“十字”形路口，人们会直接沿着两相邻通行区域的通道口结点连线方向前进。图6展示了这些特殊情况下的网络提取结果。弧形可以认为是直线段组合的逼近，所以弧形走廊网络提取可以看作图6(c)情况的连续组合，执行算法前需要对光滑弧线按一定逼近精度离散为直线段组合。

图6 狭窄走廊分区连接处的路网形态Fig.6 The shape of the network at the junction of narrow corridors

2.4 算法描述

室内空间提取详见文献[22]，走廊空间分割及导航路网生成的详细算法步骤如下。

输入：走廊凹凸点集合NCorridor、分割阈值τ、墙角点表V。

输出：路网集合Road。

(1) 遍历NCorridor，若当前点P是凹点，计算该边延长线与走廊弧段的交点以及当前交点集合中与P最近交点的距离Ln，执行步骤(2)；否则，继续遍历。

(2) 若Ln<τ，记录交点坐标、凹点坐标以及对应点所在边，同时记录凹点和交点连线的中点，即通道口结点；否则，执行步骤(1)。

(3) 遍历交点表中的点，若该点不与走廊角点重复，则将该点与墙角点表V合并，生成分区角点表V′，并记录该点的ID和对应凹点到墙线-分区角点表E′；否则，记录对应的走廊角点ID和对应的凹点到E′。

(4) 按顺序依次记录走廊边，若当前边有新增交点，则对交点和该边的首尾墙点进行排序，然后记录到E′；否则，直接记录边到E′。

(5) 根据V′以及E′，判断是否所有边都记录两次，若不是，将记录次数最小且ID最小的边设为edgeC，将该边ID小的点设为初始角点，该边的另一个点设为当前点，执行步骤(6)；否则，输出分区的边界边的集合divFace，执行步骤(8)。

(6) 若当前点回到初始角点，则输出当前小分区的边界边集合faceI，并添加到集合divFace；否则，执行步骤(7)。

(7) 搜索当前点除edgeC边外且记录次数少于2的边集合，计算集合里edgeC顺时针旋转遇到的第1条边Eq，记录Eq到faceI，Eq边的另一个点置为当前点，执行步骤(6)。

(8) 将所有通道口结点与门结点匹配到对应走廊分区，建立走廊分区表R′。

(9) 对走廊各个分区依次作如下处理：构建分区最小外接矩形，获取较短边长度Ls。若Ls<τ，则判定该区域为狭窄走廊，计算其中线并生成门点到中心线的辅助结点，添加到路网集合Road；否则，判定该区域为开阔空间，将该区域的门结点和通道口结点以完全图方式连接，执行步骤(10)。

(10) 若该区域多边形存在凹点Pt，则判断Pt对应两边是否与完全图的边相交。若不相交，则直接将完全图添加到路网集合Road；否则，将完全图中的相交边更新，即把边的两个端点分别与Pt相连，删除原边。

(11) 直到所有分区处理完毕，算法结束。

3 试验与讨论

为了验证上述方法，采用Visual Lisp语言基于AutoCAD进行了算法实现，该方式便于对建筑平面图的图形数据进行操作和处理结果可视化。试验数据分别选择内部结构较规则的教学楼和较为复杂的商场两组典型测试数据。

3.1 规则室内环境

为增加对比性，选择文献[14]采用的南京师范大学行远楼四楼和大礼堂数据进行测试。行远楼建筑内部结构较为规则，房间基本为矩形，走廊也相对规则，包含了两个相对开阔的区域。设置走廊空间分割阈值τ为3.5 m，图7(a)显示了行远楼走廊分割效果以及提取的走廊路网，图7(b)为文献[14]提取的走廊路网。由图7可以看出，本文方法能够依据走廊分区尺度生成不同形态的路网，在开阔分区没有障碍遮挡时，行人会沿直线路径从当前门或通道口结点到达目标结点。

图7 走廊分割及路网形态对比Fig.7 Corridor segmentation and comparison of road networks

在将门结点连接到走廊路网时，本文与文献[14]不同的是在开阔空间门结点和通道口结点两两直线连接形成完全图；而在狭窄空间，则直接垂直连接到走廊路网。图8为两种方法生成的完整室内导航路网和基于对应路网生成的S到T的最短路径。显然，在走廊开阔空间和走廊拐弯处本文方法的路径形态更符合人的“抄近路”习性，路径长度也更短。

图8 室内导航路网及最短路径形态对比Fig.8 Comparison of indoor navigation road networks and that of shortest paths

图9是以大礼堂走廊为测试数据对弧形走廊分割和构建路网的结果。由于预处理时已将弧形墙线(凹向走廊的弧)等分为若干段，因此可类似图6(c)情况生成许多通道口结点，然后依次连接通道口结点。由于在凹点P1、P2进行空间分割时，分割线长度大于阈值，因此走廊上部空间没有被分割而成为开阔空间。该空间内包含T1、T2两个通道口结点，为避免直接连接T1、T2与墙线相交，需要将P1、P2作为T1、T2路线的中转点，如图9(a)。为了避免“趋边性”，可以在P1、P2处对路线做适当处理，如适当向开阔空间内部偏移P1、P2。若从S行至E，显然本文路网生成的路线形态更为自然。

3.2 复杂室内环境

复杂室内环境选择文献[4]使用的北京西单大悦城一楼室内地图，数据从该文截图矢量化，因此为无单位仿真数据。该数据不仅具有9个孤岛，而且有的孤岛含有弧形边(图10)。空间分割阈值τ分别取3.5和4.5对走廊空间进行分割，并生成走廊分区拓扑图、室内导航路网和测试最短路径(图10—图12)。

图9 弧形走廊分割结果及生成路网对比Fig.9 Comparison of arc corridor segmentation results and that of generated road networks

测试分析发现：

(1) 本文算法对复杂室内环境仍然有效，能够将复杂走廊进行合理空间分割，并生成适合分区空间尺度的相应路网。在开阔空间表现为门结点和通道口结点的直线连接，在狭窄走廊区域表现为走廊中线，规划的路线符合“抄近路”和安全避碰习性(图12)。当然，在一些形状复杂且空间尺度较小的分割区域生成的路网形态还需要进一步优化，如区域R6包含3个通道口结点和1个扶梯结点，生成路网时因为空间尺度小没有生成完全图，从而使得该区域路网形态不自然。

图10 走廊分割结果对比Fig.10 Comparison of corridor segmentation results

图11 走廊分区拓扑对比Fig.11 Comparison of corridor partition topology

图12 室内路网形态及路径形态对比Fig.12 Comparison of indoor road network forms and that of path forms

(2) 复杂室内环境下走廊空间尺度变化较大，导致分割阈值大小对生成路网形态影响较大。阈值越大空间分割数越多，τ由3.5变成4.5后，分区R1到R5被分割为更多子分区(图11)，此时生成的室内导航路网将包含更少的完全图，如图12(b)；而阈值越小，有些空间就界定为开阔空间，在这些空间内生成路网会更自然，如τ=3.5时R2分区的路网。当τ=0时，走廊空间将不进行分割，本文生成路网将类似于“door to door”生成效果。

(3) 分割阈值越小，走廊中更多区域被构建为完全图，使得规划的最短长度越短。如图12所示，测试路径为起始S1到T1，当τ=3.5时，路径长度为45.00；当τ=4.5时，路径长度为45.56。关键原因在于分区R1和R3内的路线形态发生了改变。

4 结 论

针对现有室内导航网络结构和几何形态不太符合人行走习惯的问题，本文依据人的行为习性，提出了一种顾及室内空间尺度和行走习惯的室内导航网络模型，并引入“空间分割”思想来构建模型。试验结果表明，依据该网络生成的最短路径的几何形态更符合人的室内行走习惯。通过楼层之间的连接元素(电梯、楼梯)很容易将本文方法扩展到所有楼层，从而构建室内三维路径网络。另外，在构建室内导航网络过程中存储了门、房间、走廊等导航要素之间拓扑关系，为后续的室内位置服务实现提供了支持。当然，真实室内场景中会存在大量的障碍物(如家具、廊柱等)，增加了室内导航网络的构建难度，复杂室内环境下顾及障碍物的精细室内导航网络还需要进一步研究。同时，由于走廊分割线阈值的大小对网络的连通结构和几何形态影响较大，当室内结构和布局比较复杂时，如何确定合适的阈值也需要进一步研究。

致谢：特别感谢南京师范大学庞月勇博士提供试验对比数据和宝贵建议。