基于移动用户众包数据的室内平面图感知

Indoor Space Plan Perception Based on Mobile User Crowdsourcing Data

摘要: 针对大型室内环境空间结构和对象实体经常变化进而影响提供实时位置服务的问题，设计了一种利用移动用户众包位置数据感知室内平面图的方法。方法使用来自移动用户的众包数据进行室内平面图的重建，首先应用Voronoi图对室内空间进行空间区域划分，以寻找室内环境下空间的拓扑关系；然后利用拓扑关系约束有向无环图支持向量机(DAG-SVM)生成空间对象的几何特征；最后，联结拓扑关系和几何特征构建室内空间平面图。实验结果表明本文的方法能够感知室内空间平面图。

Abstract: Aiming at the problem that the spatial structure of large indoor environment and object entities change frequently to affect the provision of real-time location service, a method of using the mobile user crowdsourcing location data to sense the indoor floor plan is designed. The method uses crowdsourced data from mobile users to reconstruct the indoor floor plan. Firstly, the Voronoi map is used to divide the indoor space into space to find the topological relationship of the space in the indoor environment, then using the topological relationship to constrain the DAG-SVM algorithm to generate the geometric features of the spatial object; finally, the topological relationship and the geometric features are used to construct the indoor space plan. The experimental results show that the proposed method can sense the indoor space plan.

1. 引言

数字地图服务为户外的基于位置的服务(Location Based Services, LBS)提供了便利，例如兴趣点推荐(Point of Interest, POI)和导航服务。然而，在人们花费大量时间的室内场所中，这种室内平面图是极少的，也是室内LBS服务的一大难点 [1]。随着城市化进程的加快，大型建筑物内部复杂的空间结构加重了人们的认知负担 [2]，特别是商场、会展中心和游乐场等大型公共场所中，交错的空间和复合功能区会让人产生“云深不知处”的错觉，使得研究室内数字地图服务更加有意义。同时，人们在社交网络上以签到的方式分享地理标签或地理位置，与好友分享(餐厅、商场、娱乐场所等)体验和经验 [3]，这种方式极大促进了个性化推荐服务的发展。但室内条件下，全球定位系统(Global Positioning System, GPS)受到高层建筑物的遮挡导致精度下降，无法像户外一样直接利用GPS信息建立位置和地理标签的联系，且大型的室内场所通常集中了很多地理标签和位置，这对室内LBS服务的精度和准确性提出了更高的要求。

近年来，对室内LBS服务的研究不局限于室内导航、基于位置的推荐等服务，在社交营销、基于位置的查询、临近搜索等领域也可以看到室内位置服务的身影。室内LBS服务要求在室内提供基于位置的地理标签和位置要尽可能精细(体现为需要用x品牌店铺来替代x商场)。Basiri A.在文献 [4] 中做出了对室内LBS服务的思考，对比了现有室内定位、室内地图和位置隐私的解决方案，探讨了研究室内LBS服务会面临的技术挑战和机遇，并指出解决这些挑战将会给人们带来更好的室内活动体验。

现在移动众包的概念比较流行，众包方式减少了对专家的过度依赖，且手持智能手机的用户数量较多，为众包方案的实施提供了便利条件。文献 [1] 使用了众包采集的惯性数据来构建和组合用户移动性轨迹，来计算平面图的可访问区域的近似形状。同时，文献 [5] [6] 使用移动用户的众包数据进行室内平面地图重建，他们从视频和图片等数据中提取用户运动轨迹来确定房间形状。这些研究者的工作证明了众包方式的可行性，但他们的工作需要收集用户在一段时间内的行为轨迹数据，长时间的收集用户数据和开启摄像头权限会侵犯用户隐私，不易于应用到实际生活中去。本文使用移动用户众包的方式收集用户在室内签到、发生交易时的快照信息，作为感知室内空间平面图的原始输入数据。

室内LBS服务亟需解决的关键问题是室内空间建模 [7]，即按需求建立位置和环境的联系。文献 [8] [9] 采用基于图模型的方法来表示室内空间的拓扑关系，建立室内空间拓扑模型；Li [10] 等人提出基于格的几何模型；Z. Lei在其文献 [11] 中提出空间距离的概念，使用不同层次表达室内元素、传感器和对象之间的关系，表达室内空间的语义信息。文献 [12] 提出将几何模型、符号模型、语义模型的优势结合起来，建立一种情境相关的双层室内空间数据模型，融合了几何、符号和语义模型的优势，使模型能表达更多的室内环境信息。传统的室内空间建模方法对建筑平面图的依赖程度较高，导致模型不易更新，对结构改变和对象变更不敏感；当空间对象发生变更时不能做出调整，导致对应导航服务和基于位置的服务出错。

室内空间模型不是人们对基于位置服务的最终需求，需要通过对位置的解读去感知和理解室内环境。现在通过人工或同步定位与建图(Simultaneous Localization And Mapping, SLAM)的机器人系统感知室内空间建立室内环境地图的方法已经开始流行 [13]，但这种做法具有时效性，当空间实体对象发生变更时需要重新测量建模，造成了人力、财力资源的浪费。Shu L.介绍了一种检测有毒气体边缘的方法，使用由大量的传感器构成传感器网络对有毒气体覆盖的区域进行检测，将有毒气体覆盖区域的几何轮廓可视化 [14]。这种利用众多传感器检测区域几何形状，并即时更新状态的方法启发了本文的工作。随着学术界和大量研究人员对wifi室内定位技术的探索和研究 [15] [16] [17]，使得室内定位的精度不断提升，这也是本文工作的一个便利条件。

针对上述问题，本文设计了一种感知室内空间布局的方法，通过众包方式获取移动用户在室内签到或者交易快照信息。利用wifi室内定位技术解决GPS系统无法在室内工作的问题；然后利用用户在室内的位置数据重建室内空间平面图。本文方法有以下优点：1) 利用众包的方式获取用户在室内场所的数据进行室内空间平面图感知，与传统人工测绘方法相比，节省了人力和财力；2) 利用现有wifi基础设施进行室内定位，无须额外的定位设施；3) 使用空间拓扑关系约束DAG-SVM算法计算室内空间的几何形态，可以减少计算的复杂程度。

2. 室内空间平面图感知

2.1. 移动用户众包数据获取

获取用户签到、打卡或交易快照等在室内场所活动的数据记录。我们只需要获取一次用户在室内某空间签到或交易快照信息，获取当前用户智能手机的环境RSSI信息作为输入，如表1所示。

Table 1. Environment information of indoor mobile users

表1. 室内移动用户环境信息

在本文中，将地理标签视为室内空间对象，其在二维平面下的几何度量看作子空间区域。通过Wifi室内定位算法计算得到用户的室内位置，得到形如 $L=\langle U_i,R_i,P\rangle$ 的三元组，用来表示用户在室内的一条位置记录。其中 $U_i$ 为用户ID， $R_i$ 为空间对象，P为当前记录在室内的相对位置坐标。

2.2. 室内空间的拓扑关系

Voronoi图是用于空间分割的几何结构，能描述平面空间内实体的临近关系，Voronoi图由离散点(空间对象)和对应的Voronoi区域组成 [18]。使用空间对象作为Voronoi区域的生成点，由于同一个用户在不同子空间区域中可以进行多次签到等数据收集操作，因此把同一子空间对象下所有记录中用户位置的均值作为Voronoi区域的生成点。生成的Voronoi图将室内空间划分为与室内空间对象数目相等的子区域。Voronoi区域生成点 $R_i$ 的计算如公式(1)所示。

$R_i=\frac{1}{n}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{U}_{ij}\left(j=1,2,3,\dots ,n\right)}$ (1)

其中， $R_i$ 表示第i个voronoi区域的生成点(室内空间对象)， $U_{ij}$ 表示第i个空间对象下的第 $j\left(j=1,2,3,\dots ,n\right)$ 条记录。

使用D-三角网生成Voronoi图的步骤如下：

Step1 数据预处理，应用公式(1)计算Voronoi区域生成点 $R_i$ ，建立索引；

Step2 使用内插法建立Delaunay三角网；

Step3计算目标三角形的外接圆心；

Step4 遍历生成点的索引，重复step3，step4；

Step5连接外接圆心，生成Voronoi图。

图1是商场某层空间例子。室内空间由若干个店铺组成， $R_i$ 表示店铺的标识，不同店铺之间由墙体隔开。图2给出了图1对应的Voronoi图，其中虚线所围成的区域是各子区域初步的边界。每个子区域内仅有一个生成点，子区域之间互不相交。

Figure 1. Indoor space example

图1. 室内空间例子

Figure 2. Voronoi diagram of interior space

图2. 室内空间Voronoi图

使用Voronoi图将室内空划分为多个子区域，可由Voronoi图直接找出与目标区域相邻的其他区域，且当Voronoi区域是n边形时，目标区域与n个区域相邻。下面结合Voronoi图给出室内环境下常用的相邻、相离空间关系的定义。

定义1 (相邻关系)两空间对象之间直接连通，可由空间1直接到达空间2的两空间对象被定义为相邻关系。

定义2 (相离关系)两空间对象不直接连通，需经过中间节点才能到达。如空间1需要通过途经空间2才能到达空间3，则空间1和空间3被定义为相离关系。

通过解读Voronoi图结合给出的室内空间关系定义得到空间拓扑关系。为方便存储和表达，两空间关系映射为图的边，相邻关系在图模型中用连通顶点的边表示，无直接连通的顶点即为相离关系。以图2为例，用图模型存储并表达室内空间拓扑关系如下：

$G=\langle V,E\rangle$

$V\left(G\right)=\left\{R_1,R_2,R_3,R_4,R_5\right\}$

$E\left(G\right)=\left\{\left(R_1,R_2\right),\left(R_1,R_5\right),\left(R_2,R_3\right),\left(R_2,R_4\right),\left(R_3,R_4\right),\left(R_4,R_5\right),\left(R_5,R_2\right)\right\}$

其中， $V\left(G\right)$ 是图的顶点集，由室内子区域对象组成； $E\left(G\right)$ 是图的边集，用来存储室内环境空间拓扑关系。

2.3. 室内空间平面图的生成

现实室内环境中的房间分隔会使用一面公共墙壁作为分离相邻空间的界线，且一个房间拥有墙壁的数目由其相邻的空间数目决定，使用SVM分类器训练两个相邻空间的位置数据得到的分离超平面作为相邻空间的间隔边界，使用这些边界组成室内空间的平面图。使用SVM分类器训练数据生成室内空间平面图，这种方法依据拓扑关系保留了空间对象的几何形态，还可以还原客观世界存在的墙壁隔断。

用户的签到数据映射在二维平面上是具有明显类别界限的散点，随着用户数据的不断丰富，这些用户的散点位置所形成的形状会逐渐接近真实世界的轮廓。对室内空间平面图的感知关键是依托空间拓扑关系计算子空间的几何属性，进而感知室内空间的布局。

空间的几何形态采用由SVM分类器训练生成的分离超平面表达。在求解目标空间的几何形态的过程中，只考虑与邻接的空间分离超平面，因为具有相离空间关系的空间与目标空间是不存在公共墙等隔断的。基于空间拓扑关系感知室内空间平面图的计算框图如图3所示。

Figure 3. Calculation block diagram of indoor space plan

图3. 室内空间平面图计算框图

使用DAG-SVM方法进行目标空间几何形态的求解，计算过程中加入空间拓扑关系 $G=\langle V,E\rangle$ 这个限制条件，确保在正确分类时构造节点路径只与相邻空间有关，而不会经过相离空间，使得分类节点可以代表室内环境下的隔断。

使用空间拓扑关系做约束条件构造DAG-SVM的节点数小于传统方法，数目小于 $N*\left(N-1\right)$ 个。室内空间平面图感知过程如下：

输入：空间对象索引列表Object_index，室内位置记录三元组 $L=\langle U_i,R_i,P\rangle$ ，室内空间拓扑关系 $G=\langle V,E\rangle$ ，

输出： 室内空间平面图，

Step1：选取目标空间对象，

Step2：广度优先遍历图 $G=\langle V,E\rangle$ ，找出目标空间的相邻空间，

Step3：以step2的输出作为DAG-SVM方法组织分类节点的限制条件，

Stpe3：训练目标节点的SVM分类器，

Step4：遍历整个空间对象索引列表，重复step1，step2，step3，

Step5：分类节点可视化，得到室内空间布局地图。

下面给出了基于空间拓扑关系的DAG-SVM方法组织分类节点的关键函数的伪代码如下：

1) Object_Space #目标空间

2) Object_list #候选空间列表

3) Neighbor_list #目标相邻空间合集

4) DefNeighborSpace (目标空间)：

5) BFS ( $G=\langle V,E\rangle$ )

6) ReturnNeighbor_list

#广度优先的方法遍历图 $G=\langle V,E\rangle$ ，返回目标空间的相邻空间集合

7) DefIs_NeighborSpace (候选空间，相邻空间)

8) If 候选空间isin(Neighbor_list)：

9) Return true

#若候选空间在相邻空间列表，返回true

10) Else：

11) Return false

#若候选空间不在相邻空间列表，返回false

12) DefCreate_Node (目标空间，候选空间)

13) IfIs_NeighborSpce：

#对候选节点进行空间关系判定

14) 构造SVM分类节点

#若判定结果为true，则构造二分类节点

15) Else：

16) Create_Node (目标空间，更换候选空间)

#判定结果为false，则更换候选空间重新执行。

3. 实验

3.1. 实验设置

本文通过模拟室内定位得到的位置数据进行实验，首先设置一个具有5个空间的室内环境，然后在每个空间内随机生成数据(为保证实验的合理性，每个空间下生成数量不同的记录)模拟众包方式获得的数据，来模拟一个具有5个子空间的室内环境进行仿真实验。使用文章提出方法进行室内平面图感知，设置的室内空间环境的平面图和数据如图4所示。

Figure 4. Experimental data distribution map

图4. 实验数据分布

使用本文方法对数据进行室内空间平面图的感知，首先使用voronoi图对室内空间进行划分子区域，找到室内空间拓扑关系，用图模型来存储拓扑关系；然后根据空间拓扑关系来组织分类器节点，以拓扑关系约束空间对象的几何形状；最后将分类节点的分离超平面可视化建立室内空间的布局。

3.2. 实验结果

将数据输入进行室内空间平面图感知，通过细粒度的室内空间划分将室内空间划分为5个子区域，如图5所示，从Voronoi图中得到当前室内环境的空间拓扑关系 $G=\langle V,E\rangle$ 如图6所示。

实验中基于空间拓扑关系的DAG-SVM方法组织的分类器节点树状图如图7所示，以空间拓扑关系作为限制条件组织的分类节点数目少于传统DAG-SVM方法。在分类正确的前提下，缩减了计算资源的开支。将训练SVM得到的分离超平面可视化后得到室内空间平面地图如图8所示，从实验结果可以看出与设置的室内空间平面图近似，表明本文方法可以感知室内空间平面图，且随着数据不断丰富，感知到的室内平面图会更加精确。

Figure 5. Voronoi diagram divides indoor space

图5. Voronoi图划分室内空间

Figure 6. Topological relationship of indoor space

图6. 室内空间拓扑关系图

Figure 7. Construction of nodes based on DAG-SVM method based on spatial topology

图7. 基于空间拓扑关系的DAG-SVM方法构造分类节点

Figure 8. Indoor space layout map

图8. 室内环境空间布局地图

4. 总结与展望

本文设计了一种利用移动用户众包数据感知室内空间平面图的方法，使用室内定位得到的位置数据作为输入，进行室内空间平面图的感知。实验结果表明，本文的方法是可行的，并随着用户数据的不断丰富，构建的室内空间平面地图会更加精确。此外，室内元素不够丰富，缺少一些公共设施的描述，这也是未来要解决的问题。

基金项目

本文得到国家自然科学基金项目(No.61572144)的资助。