一种面向室内导航的通行区域模型及其自动提取算法

面向室内位置服务中路径规划与导航的应用需求，提出一种基于栅格空间的通行区域模型及其自动提取算法。首先，在栅格模型基础上引入了相邻栅格和途经栅格，结合具体示例阐述了通行区域模型的基本原理；然后，根据室内地图数据特征，通过室内栅格模型初始化、通行区域初次提取和邻域融合，设计了通行区域的自动提取算法；最后，选取西单大悦城一楼室内地图数据进行了不同栅格尺度的通行区域自动提取和路径规划试验。结果表明，该算法针对走廊内存在障碍等复杂室内环境具有较好的适用性，并且通行区域模型相比网络模型的路径规划结果更加符合复杂室内环境的路径行走特征。     

顾及地标可视性的室内导航路径优化算法

提出了一种构建室内行人通行网络的方法,利用矢量建筑图自动构建室内建筑、地标的可视关系,建立行人导航通行规则,支持室内导航路径规划。实验结果表明,此方法能够有效描述室内行人通行规则,并满足拓扑网络构建的实时性需求,减少大规模存储与维护室内路网的压力。在此基础上提出了一种多目标导航路径优化算法,该算法时间开销较低,能够实时地进行路径规划,得到的最优路径与最短路径相比具有更高的地标可见性和覆盖率。     

利用点云检测室内导航元素的方法综述

随着大型公共设施的普及和人们室内活动的增多,人们对构建室内精细化导航模型的需求日渐迫切。近年来飞速发展的三维激光扫描、摄影测量、计算机视觉等技术,能够快速高效地获取高精度室内点云数据,为室内精细化导航提供丰富的数据源。如何从海量杂乱的点云中提取出可用于室内导航路径规划的室内导航元素如房间、门窗、楼梯、走廊等,成为了研究的热点和难点。因此,从基于点云的室内导航元素提取所面临的问题出发,综述和评价了近年来各种导航元素提取的相关理论和算法,并针对其各自优缺点,提出利用几何方法与统计方法相结合实现室内导航元素检测和导航网络构建的新思路。     

基于建筑平面图的室内空间拓扑模型自动生成算法

针对以建筑平面图为数据源构建室内导航模型时,建筑平面图缺少拓扑信息,尤其是缺少对房间、走廊等多边形对象拓扑描述的问题,本文提出了一种自动化构建室内空间拓扑模型的算法。该算法首先根据CAD建筑平面图的基本特征,将墙线抽象为弧段,门窗抽象为点,房间抽象为多边形;然后从起始墙线出发,将该墙线顺时针或逆时针遇到的第一条墙线作为目标房间或走廊的第一条边,依次类推,直至回到起始墙线,则完成一个房间或走廊的提取;重复上述过程,直到所有墙线均被标记两次,说明所有房间或走廊提取成功,完成墙线与房间、走廊之间的拓扑连接关系自动建立。门窗与房间之间的拓扑关系则是根据门窗与墙线的拓扑关系,推导出门窗与房间之间的拓扑关系。以某大学教学楼的建筑平面图为例进行试验,试验结果表明本文算法能够有效实现室内空间拓扑模型的自动生成。     

室内楼层平面导航路网模型的自动生成

室内路网模型作为室内导航研究的基础,如何自动生成室内路网模型成为近年的研究热点。对于目前自动路网模型研究中出现的复杂环境适应度不够的问题,本文提出了一种室内楼层平面路网模型的自动提取方法。它将室内空间分为公共空间和专属空间两类,从而形成公共空间路径和专属空间路径,并用转换点将两类路径进行衔接;最终利用提取的公共空间路径、专属空间路径和连接路径构成楼层平面导航路网模型。基于此方法,将某学校教学楼一层建筑平面图生成平面自动路网模型,并从路径完整度、准确度及寻路情况3个方面与手动路网模型进行了对比分析,其表现良好。     

利用细化空间分隔法的房间细部级室内导航元素提取

现有的室内三维模型重建中,通常将墙等承担空间分隔作用的室内导航元素看作一个整体,通过对墙的提取来实现房间子空间的分割。然而,一面墙的两个墙面形态上的差异会造成室内三维重建过程中房间细节的损失,并且引起门窗提取的困难。针对这一现象,提出了一种细化空间分隔的思想,通过将一面墙细化为两个墙面,利用区域生长算法获取墙面角点,从而获得室内的精细化表达;同时利用对应墙面上对应区域的点云密度比对方法,规避门窗提取中遮挡墙面的障碍物对提取结果的影响。结果表明,该方法可以对室内门窗进行有效地提取,从而为导航网络的生成提供了重要依据。     

一种自动提取室内通行网络的方法

针对当前从建筑物设计图中提取通行结点网络的方式存在人工干预过多和效率较低等问题,该文提出了一种自动化构建室内通行网络的方案。在总结当前以CityGML LOD4格式存储的建筑物通行数据存在的各类典型问题之后,进行对应性的数据错误修正和补全;然后结合室内可通行空间特点,引入正交多边形分割算法和邻近关系分析算法,完成室内通行网络提取。实验结果证明,该方法所提取的基于CityGML LOD4文件的基本通行结点网络,能够在保持空间定性连通关系的基础上融合空间定量属性,满足人员室内路径规划应用的多重需求。     

一种基于体素的室内三维连通图自动生成算法

为了能快速计算室内导航路径,必须使用简单的数据结构表达室内复杂的路径导航信息,室内三维连通图就是一种较好的手段。但是传统的室内精细建模重在几何模型的构建和纹理数据采集,缺乏室内三维连通图的构建。针对广泛存在室内几何模型提出一种基于体素的室内三维连通图自动生成算法,对建筑物内部进行分割和填充,将室内空间划分为离散的导航空间,通过自动语义关联提取连通关系,最终生成室内空间三维连通图。     

一种室内导航网络众包构建方法

室内导航网络是室内位置服务的基础,传统人工测绘或基于CAD半自动提取等方法时效性较差。室内移动对象众包轨迹数据的出现为室内导航网络构建提供了一种新的解决方案。提出一种室内导航网络众包构建方法。首先提取出用于构建室内导航网络的廊道区域轨迹点;其次通过轨迹点生长融合聚类算法将廊道轨迹点转化为聚类点;最后通过聚类点连接生成室内导航网络。以某商城一楼2 d的移动对象轨迹数据进行了实验。结果表明,本文方法提取的室内导航网络准确度较高,能够为室内空间结构快速变化检测和更新提供支持。     

引入导航网格的室内路径规划算法

随着社会、经济的不断发展进步,室内导航定位越来越重要,其导航定位精度、准确性倍受业界关注,而路径规划是该研究方向的重要组成部分。针对传统的基于节点的拓扑模型无法较好解决室内空间"路网"的模糊性问题,该文分析了室内外导航定位的差异,并对传统路径规划算法的局限性进行了分析,提出将基于Delaunay三角剖分导航网格的A*算法应用于室内导航路径规划中。通过算例验证了该方法的有效性,具有较好的实用价值。     

Finding outdoor boundaries for 3D space‐based navigation

Outdoor navigation is widely used in daily life, but faces various issues related to the fidelity of outdoor navigation networks. For instance, agents (pedestrians) are often guided via unrealistic detours around places without clear paths (e.g., squares) or if there are vertical constraints such as overpasses/bridges. This is partly explained by the fact that the main sources of navigation networks in current outdoor navigation are two‐dimensional road/street networks. Utilizing a three‐dimensional space‐based navigation model, compatible with some indoor approaches, is a popular way to address the above‐mentioned issues. A 3D space‐based navigation model is generated by treating 3D spaces as nodes and the shared faces as edges. Inputs of this model are enclosed 3D spaces (volumes). However, outdoor spaces are generally open and unbounded. This article puts forward an approach to enclose outdoor spaces and mimic the indoor environments to derive a network based on connectivity and accessibility of spaces. The approach uses 2.5D maps and consists of three major steps: object footprint determination, footprint classification and space creation. Two use cases demonstrate the proposed approach. Enclosing outdoor spaces opens a new research direction toward providing seamless indoor/outdoor navigation for a range of agents.     

A generic space definition framework to support seamless indoor/outdoor navigation systems

Contemporary public buildings are becoming conglomerates of open, semi‐open and closed spaces, with indoor, outdoor and underground sections. For humans and robots to navigate seamlessly through such environments, new flexible approaches need to be developed. Navigation systems generally rely on a network (nodes and edges) as an abstraction of underlying space availability. However, indoor and outdoor networks have different origins. While indoor systems rely on indoor space subdivision approaches, current outdoor systems utilize road‐based network approaches. Linking such networks via particular nodes is possible but restrictive. Many spaces in the built environment are not strictly indoor or outdoor spaces and are thus often omitted from navigation networks, further limiting navigation options. To overcome these shortcomings, we introduce a new space definition framework in which the entire built environment is categorized into indoor, outdoor, semi‐indoor and semi‐outdoor spaces. We provide strict definitions for the four space categories. Our framework allows the same navigation network extraction approaches to be used and therefore enables seamless indoor/outdoor path computation for single or combinations of locomotion modes. The notions of semi‐indoor and semi‐outdoor spaces offer new options for further tailoring of the navigation path with respect to environmental factors, which we demonstrate with two use cases.     

A comparison of network model creation algorithms based on the quality of wayfinding results

Various network model creation algorithms have been introduced to demonstrate a better approximation of the actual walking pattern and to provide a better wayfinding guide. However, it is under‐investigated which algorithm creates the most appropriate indoor navigation network model in the context of wayfinding applications. Due to the lack of discussion, some studies unconsciously extended an algorithm designed for creating an outdoor navigation network model to indoor space applications. This is problematic because indoor space has different spatial contexts from outdoor space, such as non‐linear space and no‐designated walking space. Our solution is to select five well‐known algorithms that have been introduced, to reproduce the algorithm for the automated construction of the indoor navigation network model, and to evaluate the applicability of algorithms for indoor wayfinding applications. This article compares the quality of wayfinding results from the output of the indoor navigation network model against two criteria: route efficiency (i.e., length) and route simplicity (i.e., number of directions). Our statistical analysis illustrates that the visibility graph algorithm is the most appropriate for indoor wayfinding applications.     

Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments

Car routing solutions are omnipresent and solutions for pedestrians also exist. Furthermore, public or commercial buildings are getting bigger and the complexity of their internal structure has increased. Consequently, the need for indoor routing solutions has emerged. Some prototypes are available, but they still lack semantically-enriched modelling (e.g., access constraints, labels, etc.) and are not suitable for providing user-adaptive length-optimal routing in complex buildings. Previous approaches consider simple rooms, concave rooms, and corridors, but important characteristics such as distinct areas in huge rooms and solid obstacles inside rooms are not considered at all, although such details can increase navigation accuracy. By formally defining a weighted indoor routing graph, it is possible to create a detailed and user-adaptive model for route computation. The defined graph also contains semantic information such as room labels, door accessibility constraints, etc. Furthermore, one-way paths inside buildings are considered, as well as three-dimensional building parts, e.g., elevators or stairways. A hierarchical structure is also possible with the presented graph model.     

Semantic enrichment of octree structured point clouds for multi‐story 3D pathfinding

3D indoor navigation in multi‐story buildings and under changing environments is still difficult to perform. 3D models of buildings are commonly not available or outdated. 3D point clouds turned out to be a very practical way to capture 3D interior spaces and provide a notion of an empty space. Therefore, pathfinding in point clouds is rapidly emerging. However, processing of raw point clouds can be very expensive, as these are semantically poor and unstructured data. In this article we present an innovative octree‐based approach for processing of 3D indoor point clouds for the purpose of multi‐story pathfinding. We semantically identify the construction elements, which are of importance for the indoor navigation of humans (i.e., floors, walls, stairs, and obstacles), and use these to delineate the available navigable space. To illustrate the usability of this approach, we applied it to real‐world data sets and computed paths considering user constraints. The structuring of the point cloud into an octree approximation improves the point cloud processing and provides a structure for the empty space of the point cloud. It is also helpful to compute paths sufficiently accurate in their consideration of the spatial complexity. The entire process is automatic and able to deal with a large number of multi‐story indoor environments.