随着移动通信等技术的不断发展以及智能移动终端应用的广泛普及，位置服务已经成为构建智慧城市等方面的重要基础支撑^[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分别表示不同的室内空间，d₁、d₂、d₃分别表示出入口，采用某栅格尺度对其进行离散化后结果如图 2所示。由于出入口是连接不同室内空间的重要对象，因此d₁、d₂、d₃所处的栅格作为可以通行的缺口栅格。

图  1  室内平面环境示例

Figure  1.  Example of Indoor Plane Environment

下载: 全尺寸图片 幻灯片

图  2  室内栅格离散化示例

Figure  2.  Example of Indoor Grid Discretization

下载: 全尺寸图片 幻灯片

本文采用8方向描述相邻栅格邻接关系，按顺时针方向采用整数1~8表示(见图 3)。基于栅格模型采用A^*算法可以获取图 2中栅格P至栅格Q之间的最短路径。室内栅格中任意两个目标栅格之间直接通行经过的栅格集合称为途经栅格，具体表现为目标栅格中心点的连线相交的栅格集合(见图 4)。途经栅格是判断栅格之间是否可以直接通行和实现通行区域自动提取的重要基础，仅当两个通行栅格之间的途经栅格均可通行时，它们之间才能够直接通行。

图  3  相邻栅格的邻接方向

Figure  3.  Adjacency Direction of Adjoin Grids

下载: 全尺寸图片 幻灯片

图  4  目标栅格之间的途经栅格

Figure  4.  Traversing Grids of Target Grids

下载: 全尺寸图片 幻灯片

1.2   通行区域模型构建方法

基于栅格模型进行路径规划需要不断遍历当前栅格的相邻栅格，从而判断下一步的行进方向。因此，当室内范围大或栅格尺度小，会导致栅格数目增多，进而增加了路径规划算法的搜索时间，难以满足室内实时路径规划与导航的应用需求。为此，本文在栅格模型基础上构建了通行区域模型，它是对关联相同室内对象的通行栅格进行聚合，从而形成内部任意栅格之间可以无障碍通行的区域，同时建立相邻通行区域之间的连通关系。图 5是图 1中室内平面环境采用通行区域模型表达的路径信息，其中，空白部分表示不可通行的障碍区域，红色虚线分别代表了通行区域R₁与R₃基于栅格空间的区域范围。

图  5  基于栅格空间的通行区域示例

Figure  5.  Example of Traversable Region Based on Grid

下载: 全尺寸图片 幻灯片

为了实现通行区域的自动提取，本文对传统栅格模型进行了扩展，主要包括关联对象、隶属区域和栅格类型3个方面。关联对象用于表示栅格语义信息，通过关联的室内对象描述，如图 5中栅格a关联对象为室内空间A。隶属区域用于表示栅格所属的通行区域，如果属于多个通行区域，那么所隶属通行区域之间可以通过该栅格实现连通，如图 5中栅格d的隶属区域为R₅与R₆。本文进一步将通行栅格划分为内部栅格、边界栅格和枢纽栅格3种类型。

1) 内部栅格是唯一隶属于某通行区域R的通行栅格，并且其奇数邻接方向的相邻栅格均为仅隶属于R的通行栅格。如图 5中栅格P与栅格Q分别为通行区域R₁和R₃的内部栅格。

2) 边界栅格是唯一隶属于某通行区域R，但不属于R内部栅格的通行栅格。边界栅格主要用于描述通行区域的范围，如图 5中栅格k为R₅的边界栅格。

3) 枢纽栅格是同时隶属于多个通行区域的通行栅格，它主要用于建立相邻通行区域的连通关系和描述通行区域的范围。如图 5中栅格c、m、l为R₄与R₅的枢纽栅格。

如图 5所示，R₁内栅格P可直接行进至枢纽栅格a，经过D₁可以直接行进至枢纽栅格b，再经过R₄可直接行进至与R₅连通的枢纽栅格c、m、l或与D₂连通的枢纽栅格。基于上述原理，采用A^*算法得到栅格P至栅格Q的最短路径为P-a-b-c-d-n-p-q-Q。

2 室内通行区域的自动提取

2.1   室内栅格模型初始化

室内栅格模型初始化按照相应栅格尺度生成离散化栅格，同时初始化栅格的类型、关联对象、隶属区域等信息。假设栅格尺度为S，栅格模型初始化的主要流程如下。

1) 划分离散栅格。选取室内地图最小横坐标与纵坐标为原点，沿坐标轴方向采用间隔S将室内平面划分为一系列的离散栅格。栅格尺度越小，反映的室内环境特征越精细，但会导致栅格数目增加，从而影响通行区域的提取效率；栅格尺度较大，反映的室内环境特征越粗略，可能会导致走廊等狭窄室内空间连通性的缺失。

2) 判断栅格属性。如果某室内空间R_s为可通行的区域，那么位于R_s内部的栅格初始化为边界栅格，关联对象为R_s，隶属区域为空；与R_s边界相交的栅格初始化为障碍栅格，关联对象和隶属区域均为空。如果R_s为不可通行的区域，那么与R_s的边界及其内部相交的栅格均初始化为障碍栅格，关联对象和隶属区域均为空。

3) 生成缺口栅格。由于门等缺口依附于墙体等室内空间的边界，从而造成缺口中心点所处栅格在第2)步判断为障碍栅格。因此，如果缺口d中心点位于栅格G内部，那么设置栅格G为缺口栅格，关联对象为d。如图 6所示为图 1中室内平面环境的栅格模型初始化结果，其中缺口栅格G₁、G₂、G₃的关联对象分别为出入口d₁、d₂、d₃。如果初始化之后经过某种方式检验发现存在室内空间连通性缺失的情况，那么需要减小栅格尺度S，并重新进行初始化。

图  6  室内栅格模型初始化示例

Figure  6.  Example of Indoor Grid Model Initialization

下载: 全尺寸图片 幻灯片

2.2   通行区域初次提取

建立列表RList存储提取到的通行区域，GList[R]存储区域R所有栅格，BGList[R]存储R边界及枢纽栅格。建立待扩展栅格列表SGList和种子栅格SG，通行区域初次提取主要流程如图 7所示，主要包括3个部分。

图  7  通行区域初次提取的主要流程

Figure  7.  Flow Chart of Traversable Region Preliminary Extraction

下载: 全尺寸图片 幻灯片

1) 获取有效种子栅格。通过遍历室内每行栅格或待扩展栅格列表，获取可用于提取通行区域的种子栅格SG，如果某栅格为障碍栅格或已存在隶属区域，则不能作为种子栅格。

2) 提取各个通行区域。以SG为起点新建区域R，通过遍历R边界栅格，不断将满足条件的相邻栅格加入R。其中，BTrav(G_k, R)用于判断G_k是否可以加入R，对于BGList[R]中任意栅格G_i，仅当G_k与G_i之间途经栅格均可通行且不为其他区域的内部及枢纽栅格时，BTrav(G, R)=true。向R添加G_k时，需将R加入G_k隶属区域，同时更新G_k及其相邻栅格的类型。

3) 建立区域连通关系。根据各个缺口区域包含的缺口栅格及其相邻栅格的隶属区域，建立缺口区域与相邻空间区域之间的连通关系。图 6的栅格模型初始化结果经过通行区域初次提取后得到的结果如图 8所示，包含R₁~R₈共8个空间区域和D₁~D₃共3个缺口区域。

图  8  通行区域初次提取示例

Figure  8.  Example of Traversable Region Preliminary Extraction

下载: 全尺寸图片 幻灯片

2.3   通行区域邻域融合

由于室内空间边界不规则等原因，导致初次提取结果通常包含部分栅格数目较少的通行区域，如图 8中R₇和R₈所示。为降低通行区域复杂度，需要对满足融合阈值和融合条件的区域进行融合。其中，融合阈值是指通行区域的非枢纽栅格小于一定数目；融合条件是指区域融合后不会降低与其连通的通行区域之间的连通性。另外，邻域融合需要按照区域栅格数目由少至多进行。由于出入口是建立相邻室内空间连通性的重要对象，因此缺口区域不可融合。假设某空间区域R满足融合阈值且其连通区域数目为N，若N=0，可直接将R从RList删除；若N=1，仅当R的连通区域不为缺口区域时可以融合，需从其连通区域的枢纽栅格隶属区域中删除R，并将R从RList删除；若N>1，邻域融合的主要流程如图 9所示，主要包括3个部分。

图  9  通行区域邻域融合的主要流程

Figure  9.  Flow Chart of Adjoin Traversable Region Merge

下载: 全尺寸图片 幻灯片

1) 判断R是否满足融合条件。对于R的任意连通区域R₁、R₂，仅当二者直接连通，或通过某不为R的区域间接连通，或R存在栅格G满足BMerg(G, R, R₁)=true且BMerg(G, R, R₂)=true，则R满足融合条件。其中，BMerg(G, R_A, R_B)用于判断区域R_A中栅格G至区域R_B的可融性，对于BGList[R_B]中任意栅格G_i，仅当G与G_i之间途经栅格均可通行且不为除R_A与R_B外其他区域的内部及枢纽栅格时，BMerg(G, R_A, R_B) =true。

2) 从R中选取有效扩展栅格。为了将R中栅格尽量融合至相邻区域，需要在R中选取相邻区域共有的栅格进行扩展。首先，从R所有栅格的隶属区域删除R，并更新栅格类型，比如R中内部栅格更新为隶属区域为空的边界栅格；然后，从R中选取隶属区域不为空的边界栅格作为有效扩展栅格，即可以通过该栅格将其相邻栅格加入隶属的通行区域。最后，当R中不存在有效扩展时，邻域融合结束，并将R从RList删除。

3) 将R栅格加入连通区域。通过遍历扩展栅格的相邻栅格，不断地将R中满足隶属区域为空等条件的边界栅格加入扩展栅格隶属的通行区域，同时更新加入边界栅格及其相邻栅格的类型。假设图 8中R₇与R₈满足融合阈值，R₇不满足融合条件不能进行融合，R₈存在栅格G(如n、u、x、z)满足BMerg(G, R₈, R₆)=true且BMerg(G, R₈, R₇)=true，因此可以进行融合，按照图 9流程进行邻域融合以后得到的结果如图 5所示。

3 试验与分析

选取北京西单大悦城一楼室内地图数据进行通行区域自动提取和路径规划试验，试验数据分为楼层边界、室内空间、出入口和室内路网4层(见图 10)。其中，室内空间包括店铺、天井等类型的面状要素；走廊为楼层边界范围内除去室内空间的部分。

图  10  西单大悦城一楼室内地图数据

Figure  10.  Indoor Map Data of Xidan Joy City First Floor

下载: 全尺寸图片 幻灯片

3.1   通行区域提取试验与分析

由于人行走的基本步距约为0.75 m，因此分别采用1.5 m和0.75 m两种栅格尺度进行通行区域的自动提取试验。根据试验区的数据特征，以上两种栅格尺度初始化结果分别如图 11(a)和图 11(b)所示。通过图 11可以看出，采用以上两种栅格尺度进行初始化后均未造成室内空间连通性的缺失。

图  11  试验楼层栅格模型初始化结果

Figure  11.  Result of Experiment Floor Grid Model Initialization

下载: 全尺寸图片 幻灯片

图 11(a)经过通行区域初次提取得到90个空间区域和35个缺口区域(见图 12(a))。设置图 12(a)融合阈值为9个栅格，经过邻域融合后剩余69个空间区域和35个缺口区域(见图 12(b))。

图  12  试验楼层1.5 m栅格尺度通行区域提取结果

Figure  12.  Result of Experiment Floor Traversable Region Extraction Based on 1.5 m Grid Scale

下载: 全尺寸图片 幻灯片

图 11(b)经过初次提取得到128个空间区域和29个缺口区域(见图 13(a))。根据1.5 m栅格尺度融合阈值对应的实际室内面积，设置图 13(a)融合阈值为36个栅格，经过邻域融合后剩余75个空间区域和35个缺口区域(见图 13(b))。可以看出，栅格尺度越小，初次提取的通行区域数目相对较多，特别是几何特征较为复杂的室内空间需要进行邻域融合的通行区域数目较多；不同栅格尺度最终提取的通行区域数目差别较小，邻域融合后的通行区域能够较好地反映室内主要路径信息。

图  13  试验楼层0.75 m栅格尺度通行区域提取结果

Figure  13.  Result of Experiment Floor Traversable Region Extraction Based on 0.75 m Grid Scale

下载: 全尺寸图片 幻灯片

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)，验证了通行区域模型对满足大范围室内场景中实时路径规划与导航的适用性。

图  14  试验楼层路径规划结果对比

Figure  14.  Contrast of Experiment Floor Route Planning Result

下载: 全尺寸图片 幻灯片

图  15  基于通行区域模型的室内路径实时规划及表达

Figure  15.  Indoor Route Real-Time Planning and Presentation Based on Traversable Region Model

下载: 全尺寸图片 幻灯片

4 结语

室内路径信息自动获取是实现大规模精准室内导航服务的重要基础，也是当前亟需解决的关键技术之一。本文面向室内路径信息的特点，提出一种适用于室内路径规划与导航的通行区域模型，并设计了通行区域的自动提取算法，有效实现了室内路径信息的自动获取。

本文建立的通行区域模型相比当前广泛采用的网络模型，能够有效改善路径规划结果容易存在曲折等情况，不仅能够满足路径实时规划与导航的应用需求，而且更加符合人们在复杂室内环境的路径行走特征；另外，通行区域自动提取算法能够有效适应大型公共建筑的复杂室内环境。

本文分别选取了两种栅格尺度进行了通行区域自动提取和路径规划试验，并对试验结果进行了对比分析。面向不同室内空间特征的大型公共建筑，还需要对不同栅格尺度的适用性进行更为深入的分析，这将是本文下一步的研究内容。