可导航的室内地图与室内导航算法
李宏利1 李飞2
(1.北京长地万方科技有限公司, 北京 100043；2.广东瑞图万方科技股份有限公司，佛山 528305) 摘要
本文从分析室内地图的需求和现状出发，研究了可导航的室内地图数据模型，给出了室内地图的数据组织方法和表达方式，特别是研究了室内导航系统的构成和使用室内地图进行不同楼层、不同地点间室内导航的基本算法及从室外跨入室内的无缝导航方法。
关键词
室内地图、位置服务、数据模型、室内导航
Indoor Map, LBS(Location Based Service)，Data Model，Indoor Navigation.
引言
随着以智能手机为代表的移动互联网的快速兴起与发展，随着人们生活水平提高、消费能力增强，人们对基于位置的移动生活服务需求与日俱增，人们不再满足于室外出发地到目的地之间的导航，而更需要在大型机场、火车站、百货商店、购物中心，大型室内地下停车场等这类极易迷路的室内场所的导航。
据抽样调查，现代人类有70%—80%的时间是在室内环境下生活与工作的，要提供优质的移动位置服务，不仅面向室外环境，更要能适应复杂的室内环境，这就要求必须有全面准确的可导航室内地图做支撑，实现室内的精确导航。
近年来室内地图的研究逐渐兴起，早在2011年11月Google发布了新版移动地图服务，其中就包括了大型商店和机场的室内地图功能。此后国内不少手机地图厂商相继推出了不少室内地图作品，这些室内地图可以帮助用户清晰辨别每个楼层的建筑物各平面布局，详细搜索兴趣点的位置和深度服务信息，给用户带来全新的地理位置服务体验。据不完全统计，目前可做展示使用的1:500的室内地图覆盖全国300多座城市，拥有超过数万座建筑物，1,00多万个室内POI，涵盖50多个场所类型。由于卫星定位信号无法传播到室内精确解析定位，目前室内定位技术主要还是采用AGPS的基站定位或WIFI 指纹定位，这些定位方式好的也有几十米的误差，无法满足室内精细导航的需要，因此可导航的室内地图制作很少。
基于以上分析，本文的研究，面向未来室内定位技术平面位置可达到米级
精度、垂直精度可分出楼层的条件来研究室内可导航地图的概念模型、数据组织方法和表达方式，室内导航系统的构成和导航算法，以期将来能够依据可导航的室内地图实现高精度的室内导航。
1.室内地图数据模型
可导航的室内地图不但要解决各个楼层平面布局的展示和位置服务信息的搜索，而更重要的是解决一个楼层内的两个不同地点间的路径规划、分处不同楼层两个地点间的路径规划、从楼外的一点到楼内任意一层的任意地点的路径规划。为此需要研究室内地图的数据模型和据此的室内导航算法。
1.1 模型要点
基于上述目的，本文设计给出的室内导航电子地图的数据模型要点是：1）室内导航地图与室外导航地图采用同一坐标系统、同一投影方式，通过设置室外道路连接结点形式连接室外道路，从而达到室内室
外一体化无缝导航。
2）一幢建筑（Building）为一个构图计算单元，由多个楼层（Floor）数据组构成。对具有室内连通关系的多幢建筑群视为一幢建筑。
3）每个楼层由一组平面布局要素、信息点要素和具有点/线拓扑连通关系的通道要素组成。
4）一个楼层内的路径通达关系，用层内通道要素的点、线平面拓扑连通关系表达。
5）楼层间的路径通达关系，由以步行楼梯、垂直电梯、电动扶梯口、坡道为代表的层间转换结点的垂直拓扑连通关系表达。
1.2 单楼层平面图结构模型
一个楼层平面图的组成及相互关系如图1所示：
图1. 楼层平面图组成结构
这个关系图若忽略楼层间垂直连接结点，其实与普通的室外导航电子地图一致。
1.3 多楼层间的垂直拓扑连接关系模型
多个楼层之间的垂直拓扑连接关系如图2所示：
图2. 多楼层间的垂直拓扑关系图
这表达了依靠垂直拓扑连接结点和结点间的关系，可以由任意一层去往其他各层的目的地。
如图3所示，空心圆圈为垂直结点、实心圆为平面连接结点，结点间的实线段为平面连接通道。若由M层的C点，到达N层的目的地F点，只需找出M到N垂直可通达的转换结点Pm和Pn，以及C到Pm和Pn到F的平面最优路径即可完成从C到F的路径规划，图中表达的黑粗线即是从出发地C到目的地F规划处的路径。关键的难点是找到Pm和由Pm找Pn。
图3 不同楼层间路径规划示例图
2.室内地图数据组织
2.1 一幢建筑物的数据文件组织结构
室内地图数据库的组织结构是顶层为室内地图的总文件夹（IndoorMap）, 其下为各个地级以上城市文件夹，以城市字母缩写表达，再其下为城市内各个建筑物文件夹，一幢建筑为一个室内地图文件夹，其下有各个专题数据层。以下是北京市（BJM）领先大厦（LXDS）室内地图数据组织的结构样例：
图4. 室内地图的文件组织样例
一个楼层内的文件主名命名规律是：
字母“F”+“楼层号”+字母下划线“_”+“数据专题类别码”
EG表示此图层为导航弧段；
ND表示此图层为导航结点；
PG表示此图层为设施面；
PT表示此图层为信息点。
楼层号为负值时, 表示该楼层属于地下建筑, 地下一层为“-1”。
如“F2_EG”,表示该图层为第二层楼的导航弧段。
如“F-1_ND”,表示该图层为地下一层楼的导航结点, 包括楼梯口。
若此建筑物内部具有全景观景点，则在建筑物文件夹下设有Pano_Photos 文件夹，存储与观景点相对应的360度全景照片。
2.2 一个楼层平面图的组成与表达
一个楼层平面图由拓扑连接结点、拓扑连接弧段、信息点和设施面四个图层组成，如图1。具体存储结构与表达方式是：
