基于ProjectTango手机的室内导航路网生成方法

丁磊 蔡德成

摘 要：导航路网是实现室内定位与导航服务的关键。现有室内路网生成方法成本较高，且依赖于室内建筑CAD图纸或室内二维平面图等先验知识，数据获取过程繁琐。提出一种服务于室内导航与定位的基础路网模型，利用Project Tango设备采集路网模型所需原始数据，经过细粒度划分得到室内空间适应性导航路网。实验证明，该方法可在面向未知环境时，可更快速、高效地获取较高精度的室内导航路网，且成本更低。

关键词：Project Tango;室内导航;路网模型;运动追踪

DOI：10. 11907/rjdk. 182392

中图分类号：TP301

文献标识码：A文章编号：1672-7800（2019）006-0046-06

Abstract： In the application of indoor space positioning and navigation services， the navigation network is the key to realize indoor positioning and navigation services. At present，the method of generating indoor network is costly and relies on prior knowledge（such as indoor architectural CAD drawings or indoor two-dimensional plan），and the data acquisition process is cumbersome. This paper proposes a basic network model for indoor navigation and positioning，and uses Project Tango equipment to collect the original data needed for the network model，and obtains an adaptive navigation network for indoor space after f*87ine-grained division. The experiment proves that the method can realize the indoor navigation network with higher precision and faster and more efficient，and the cost is lower.

Key Words： Project Tango; indoor navigation; network model; motion tracking

0 引言

随着城镇化进程的加快，办公楼、大型购物场所、地铁站等大型建筑物日益增多。有研究表明，人们绝大部分时间都处在室内空间[1]。另一方面，随着移动互联网、新一代地理信息系统（GIS）、基于位置的服务（LBS）及普适计算、物联网等技术的兴起与快速发展，公众对基于位置的室内移动信息服务需求与日俱增，如室内定位导航、商场移动导购、室内移动社交等[2]。因此室内定位、导航与位置服务技术备受关注。

与开放的室外空间相比，由于室内环境在空间布局、拓扑、环境限制、空间约束等方面更加复杂，使现有基于GNSS的室外导航位置服务技术无法完全适用于室内环境。室内空间路径网络拓扑结构与室外道路网存在较大差异，如室内房间、走廊、大厅等实体之间通過门、楼道等方式连通在一起，并且具有三维特性，使传统欧式距离[3]和道路网路径距离[4]计算方法无法用于计算精细的室内空间路径距离。因此，为提供精准的室内导航服务，路径距离计算大多依赖于底层拓扑网络，与室外道路网不同的是，室内拓扑网络常因为人为因素影响，如大型家具的移动等，导致拓扑网络发生改变，在导航过程中，如果没有及时更新已改变的拓扑网络，会严重影响导航准确性。

对于室内导航服务而言，路径导航问题依赖于精度较高的导航路网。Li等[5]提出一种基于图的网格模型表达二维室内空间，该模型在不同层次结合室内空间结构和拓扑属性，且隐式地集成度量属性，但是模型以室内空间二维平面图作为建模输入，依赖于已有的室内空间二维平面图。Schafer等[6]为在更大范围内提供地图生成解决方案，开发了地图生成工具包，可解析标准CAD图，自动生成室内空间拓扑网络图。Xuan等[7]提出一种从室内行人轨迹众包数据中估算室内拓扑网络图的算法。Johnston等[8]提出利用激光扫描仪估算室内地图的方法。

现有室内拓扑网络图获取方法均依赖于先验知识（如建筑物CAD图、室内平面图），或需要借助激光扫描仪获取数据，其成本高、数据处理复杂，同时室内空间导航路网容易受到人为因素影响发生改变，需及时、快速地更新纠正该区域导航路网。因此本文提出一种基于Project Tango手机的室内导航路网生成方法，阐述其方法流程并进行实验与分析，证明该方法可面向未知室内环境更快速高效地获取较高精度的室内导航路网。

1 Project Tango技术

2014年，谷歌成立Project Tango项目并推出一系列搭载摄像头、各种运动传感器和处理芯片的手机、平板等移动设备（见图1），用于绘制逼真的三维场景，为AR、VR等应用奠定了基础，并为开发者提供面向C、JAVA、UNITY三大语言的API以实现应用开发[9]。

Project Tango平台三大核心技术是运动追踪、深度感知和区域学习，在各种传感器、摄像头、IMU等硬件基础上，利用机器视觉技术和图像处理算法等，整合3个维度的数据，描述Project Tango设备自身运动姿态、趋势和周围环境信息（例如周围环境三维点云数据）。设备参数见表1。

运动追踪是基于单目摄像头技术，在IMU、加速度计和陀螺仪的基础上添加广角摄像头视觉特征识别[10]，计算特征点在帧与帧之间的相对位置变化，识别相机移动距离及运动姿态。但此时并没有获得深度数据，且单目摄像头技术无法辨别大面积无特征点的环境，如全黑或全白区域。

深度感知可检测物体或障碍物表面及形状，目前常见的解决方案主要包括结构光和TOF，根据激光从发射到返回的时间长短计算物体或障碍物距离摄像头的真实距离，将所有点的距离信息生成三维点云图，在Project Tango Core的优化下，结合运动追踪中获得的特征点即可动态获得室内空间单元模型[11]。

区域学习是将运动追踪获得的特征点数据与深度感知获得的深度数据融合匹配成场景信息，当检测到新场景时，会与已有或预设场景进行匹配，并且同步修正运动追踪的数据，即区域学习是运动追踪和深度感知的结合，通过数据库不断扩充和匹配，实现场景学习的目的，模拟人类感知世界[11]。

本文提出的方法充分利用Project Tango深度感知和运动追踪技术，经实验证明该方法采集获取室内导航路网的过程简单、快速且获得的室内导航路网精度较高。

2 室内导航路网模型

在室内空间导航中，导航路径非常重要，然而室内导航路径不同于室外导航路径，因受房间、门、墙等室内实体要素限制，在空间布局、拓扑网络、空间约束等方面具有特殊性，传统欧式距离和道路网路径距离在室内空间导航中存在较大缺陷，因此需构建室内导航网络以规划导航路径及计算路径距离。室内导航路网属于2.5维结构，本部分从空间几何、拓扑等方面描述室内环境[12]。

2.1 室内基础导航路网

拓扑关系是导航网络主要表达内容，如包含、邻接、连通、覆盖等。在室内空间中，各实体要素之间的拓扑关系主要是邻接及连通关系。本文首先通过结合图模型[13]、节点关系模型[14-15]和地标导航数据模型[16]构建室内基础导航网络，表达室内空间基本轮廓。

节点关系模型是由Lee等[14-15]提出的一种可简化表达室内空间实体要素间复杂拓扑关系的数据模型，如建筑物中房间之间的连接或连通关系。地标导航数据模型是由汤欣怡[16]提出的一种利用地标辅助室内导航的路网模型，该模型在导航路网决策点处选择一个显著性最强的空间实体要素作为该决策点的地标。在节点关系模型和地标导航数据模型的基础上，本文提出一种表达室内空间关键节点间连接关系的数据模型——室内基础导航路网。

室内基础导航路网根据室内空间单元基本结构生成，表达室内空间单元基本形状、单元间连通拓扑关系、连通距离及角度，该结构是实现室内导航与路径规划的基础。

室内基础路网节点包括空间内节点、转弯点和终止点。其中，空间内节点定义为室内开阔区域（如大厅，房间等）的边界节点，处理走廊时建立中轴[17]对空间结构进行抽象，中轴上产生的中间节点即为转弯节点，中轴端点即为终止节点。

如图2所示，空间内节点为空间结构中空间实体（大厅、房间等）的边界节点，障碍物空间实体没有边界节点。

对于常规建筑来说，走廊形状一般是狭长的。当处理走廊时，建立该区域中轴对其连通路径进行表达，并在相应位置插入转弯节点，如图3所示。该空间为长方形ABCD，由于AC边连接3个空间实体，BD边也连接3个空间实体，即会出现边AB被分解为4段、BD边被分为3段的情况，在这种情况下，网络模型使用中轴抽象走廊ABCD，产生5个转弯节点。另外，终止节点用于封闭中轴线，终止节点的位置根据中轴生成的算法确定。

在垂直通道的处理上，倾斜空间使用中轴[17]及两个终止节点表示，转换空间由于连接了两个倾斜空间，也处理为中轴表示，并插入转弯节点，连接到相邻倾斜空间上的终止节点，如图4所示。

2.2 室内适应性导航路网

与室内基础路网相比，室内适应性路网对开阔空间进行了进一步细化，如图5所示。在室内基础路网的基础上，适应性路网首先根据语义信息确定室内开阔的自由空间，如大厅、房间等（狭长区域为宽度小于阈值的走廊、楼梯等），对开阔空间对应的面进行格网剖分，将格网中心点作为新的节点，根据四方向或八方向邻接关系建立格网中心点的边，并通过与连接空间内节点之间的连通边，将开阔的空间形成的格网-图模型连接到室内基础路网中 ，形成在狭长区域使用中轴表达、在开阔区域使用格网—图表达的适应性室内路网。格网—图模型是对空间细粒度离散化表达，以格网单元中心点作为节点，以格网八方向连通关系作为边，连接相邻节点构成的网络模型。格网—图模型的粒度根据格网单元的边长确定，格网单元越小，中心点越密集，格网—图模型的分辨率越高。格网—图模型可进行精度更高的路径规划。

2.3 室内导航路网数据模型

本文提出室内基础导航路网数据模型IBNNDM（Indoor Basic Navigation Network Data Model）的形式化定义为：

IBNNDM=（Node，Edge，LandMark，Room，Storey，Building）。

其中，Node是节点集合，代表基础路网中的节点;Edge是边集合，代表两节点间的连接关系;LandMark是地标集合，代表节点附近的地标;Room是室内房间集合，代表室内所有房间（包括大厅）;Storey是楼层集合，代表节点所在楼层;Building是建筑物集合，代表节点及边所在建筑物。

建筑对象（Building）是人们日常活动的室内空间，每栋建筑均包含多个楼层（Storey），每个楼层包含多个房间（Room），每个房间又包含若干个节点（Node）和路网的边（Edge）。一个路网节点可能分布着多个候选地标，路网的边代表该两节点间具有連通关系。该数据模型的关键在于如何组织Project Tango设备采集到原始室内空间数据，最后生成室内导航路网。

IBNNDM模型中每个对象类的实现及属性见表2-表7。构建室内导航路网仅需获得表2-表7中的数据即可。

3 室内导航路网模型构建

3.1 坐标系转换

Tango设备采用参照定位的方法，即相对于初始位置的一种定位方式，不涉及到卫星定位。它根据硬件设备传感器，比如重力传感器、IMU陀螺仪等，获取移动设备相对于初始位置的位移和旋转角度，从而构建一个局部参照坐标系——起始点为坐标原点，将Z轴设置为与重力对齐，Z +指向上方，并且XY平面平行于与重力垂直的方向，且X轴指向设备屏幕右边，Y轴垂直于X轴、Z轴构建的平面指向X正方向逆时针旋转90°的反向，如图6所示。由于不能保证每次采集开始时设备构建的局部参照坐标系X、Y轴方向和大地坐标系统一致，所以需将局部参照坐标系转换到大地坐标系（仅统一坐标轴方向，不统一坐标原点）。

3.2 原始数据采集

调用 Project Tango API，通过重写onPoseAvailable 的方法，可以获取相机当前姿态与初始位置的相对位置关系，返回一个三元组表示位置信息。遇到上文定义的3类节点时便记录下该位置坐标值、节点类型及所属对偶空间编号，并与上一个采集节点连接，构成连接边，同时检测该节点是否与已记录节点重合。如果重合，则将该节点与之前采集的节点进行连接，继续进行直到采集工作结束。

原始数据采集流程如图7所示。

3.3 适应性导航路网生成

通过以上流程采集的只是室内基础导航路网，对其开阔区域进一步细化得到室内适应性导航路网。根据室内基础路网标记的节点类型，对全部节点是空间内节点且在同一个对偶空间里构成封闭多边形对应的面进行格网划分，然后将其连接到基础路网上，形成格网—图表达的室内适应性导航路网。

格网划分步骤包括：首先获取每个开阔区域的外包络矩形（见图8（a）），然后根据导航与定位精度的需要对开阔区域进行不同尺寸的规则格网划分，本文以1m为划分尺寸标准。对外包络矩形进行格网劃分后得到格网图（见图8（b）），再计算出格网中心点作为新节点，根据四方向邻接关系建立格网中心点的边（见图8（c）），然后在开阔区域剔除对应多边形之外的节点，将起始和结束节点均保留在该多边形内连接边上，其余连接边剔除（见图8（d）），最后将其连接到基础路网上。

4 实验与分析

为验证模型与方法的可行性，选取中国地质大学（武汉）地理信息系统研究中心（见图9）作为实验场地，其单层面积为3 300m2。该场景中总共有4个实验室、1个学术报告厅、1个研究室，这5个场所经常有相关办公人员和学生出入，每个房间均有多个门可以通过。环境复杂多样，可满足测试要求。

4.1 路网生成效率分析

本文主要从两个方面分析所提方法的效率，一是该方法消耗的物资成本，二是该方法生成室内路网消耗的时间成本。由于不需要任何先验知识（如室内平面图），减少了室内平面图生成需消耗的人力和物力，且使用的设备是一个价值仅3 000元左右的Tango智能移动设备，相比于激光扫描仪，本文方法设备成本低。同时本文设计了一个时间成本对比实验，将利用ArcGIS从室内平面图获取导航路网（记为实验A）与本文提出的方法（记为实验B）进行结果对比。实验地点依然选择中国地质大学（武汉）地理信息系统研究中心，实验结果如表8所示。

4.2 路网精度分析

为避免实验偶然性，一共进行4次原始数据采集，随机选取3个节点计算测量值与真实值真误差和方差。为保证实验有效性，此处作3点约束：①实验场地光照良好，无光线昏暗之处;②每次实验人员手持Tango设备采集数据时尽量做到每次速度匀速且大致相等;③实验场地无大片全白或者全黑区域。

经过实验得到结果如表9、表10所示。

由以上两表可知随机选取的3个节点测量值方差均很小，所以可以判断测量数据较为精确。

5 结语

本文针对室内空间导航与定位服务对室内适应性路网的需求，提出一种基于Project Tango手机的室内导航路网生成方法。与现有路网生成方法相比，该方法可面向未知的复杂室内环境，形成快速、低成本、高精度的室内适应性导航路网。目前智能设备室内导航系统缺乏大量已绘制好的路网，无法有效导航、定位，本文方法可弥补该项不足，且与文献[8]的方法相比，本文使用的Project Tango设备成本更低。实验结果表明，该方法能生成满足室内导航与定位要求的路网。

但目前该方法还存在一些不足之处：首先作为一个半自动方法，时耗不小;另外一个楼层的采集工作必须一次性完成，若中途停止，会导致两次采集工作坐标系原点不同，需后期人工进行数据合并。后续将进行路网实际应用，将本文方法应用于实际导航与定位应用，并进行方法完善，以期实现室内导航路网完全自动化生成。

参考文献：

[1] WORBOVS M. Modeling indoor space[C]. Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness， 2011： 1-6.

[2] 刘兆宏，王科，丰江帆，等. 矢量室内地图建模与制作方法[J]. 数字通信， 2012（4）：77-80.

[3] HJALTASON G R，SAMET H. Distance browsing in spatial databases[J]. ACM Transactions on Database Systems （TODS）， 1999， 24（2）： 265-318.

[4] ZHANG J，PAPADIAS D，MOURATIDIS K， et al. Query processing in spatial network databases[C]. the 29th International Conference On Very Large Data Bases ，2003：802-813.

[5] LI X，CLARAMUNT C，RAY C. A grid graph-based model for the analysis of 2D indoor spaces[J]. Computers， Environment and Urban Systems， 2010， 34： 532-540.

[6] SCHAFER M，KNAPP C，SAMARJIT C. Automatic generation of topological indoor maps for real-time map-based localization and tracking[C]. 2011 International Conference on Indoor Positioning and Indoor Navigation， 2011： 1-8.

[7] XUAN Y G，SENGUPTA R，FALLAH Y. Crowd souring indoor maps with mobile sensors[M]. Berlin： Springer Berlin Heidelberg， 2012.

[8] JOHNSTON M，ZAKHOR A. Estimating building floor-plans from exterior using laser scanners[C]. SPIE，2008：68050.

[9] 千尋. Project Tango：3D影像触手可及[J]. 计算机应用文摘， 2014（11）：72.

[10] HESCH J A，KOTTAS D G，BOWMAN S L，et al. Camera-IMU- based localization：observability analysis and consistency improvement[J].  The International Journal of Robotics Research， 2014， 33（1）： 182-201.

[11] 洪程. 基于Project Tango的SLAM技术研究[D].  武汉：武汉大学， 2017.

[12] 徐战亚，钟赛尚，王媛湲. 一种易于更新的室内导航路网构建方法[J]. 计算机仿真， 2015（12）： 267-271，275.

[13] BECKER C，DüRR F. On location models for ubiquitous computing[J].  Personal and Ubiquitous Computing， 2005， 9（1）： 20-31.

[14] LEE J. 3D GIS for geo-coding human activity in micro-scale urban environments[M]. Berlin： Springer Berlin Heidelberg， 2004.

[15] LEE J， ZLATANOVA S. A 3D data model and topological analyses for emergency response in urban areas[J]. Geospatial Information Technology for Emergency Response，2008，143： C168.

[16] 汤欣怡. 面向室内行人的地标导航方法研究——以大型室内商场为例[D]. 武汉：中国地质大学（武汉）， 2017.

[17] TANEJA S，AKINCI B，GARRETT J H，et al. Algorithms for automated generation of navigation models from building information models to support indoor map-matching[J]. Automation in Construction， 2016， 61： 24-41.

（责任编辑：江 艳）