基于手机的室内数字平面图构建方法

赵鹏飙,刘 歌,罗 磊,周 瑞

(1.电子科技大学 信息与软件工程学院,成都 610054; 2.河南漯河职业技术学院,河南 漯河 462000)

0 概述

随着定位导航技术的发展,各种基于位置的服务对地图的需求日益增大。室外地图构建经过多年发展已拥有成熟的方法,通常由专业人员通过专业设备采集数据,再通过专业地理软件处理并绘制地图。此外,借助全球定位系统(Global Positioning System,GPS),也可以自动构建室外数字地图,如OpenStreetMap项目。但是室内地图的构建一直是迄待解决的问题,也是阻碍基于位置的服务在室内获得广泛应用的主要因素之一。目前室内地图的构建主要是由测绘人员测量室内数据并绘制地图或者基于建筑设计结构图绘制平面图。这些方法尽管能够进行部分楼宇的数字地图构建,但是由于高成本及私密性等原因,多数室内环境无法采用专业方法进行地图绘制,而建筑设计结构图也往往由于各种原因无法获得,导致大量室内环境无可用地图,室内定位无法实施。

近年来,随着手机传感技术的发展,加速度计、陀螺仪等传感器已成为智能手机的标配,极大促进了基于智能手机的行人活动识别和行人航位推算(PDR)技术[1]。通过对智能手机传感器数据的采集和处理,可以获得行人当前活动状态和行走轨迹。根据大量普通用户在室内的行走轨迹和活动,采用复杂数据分析算法,就可以获得室内区域的房间和走廊结构,从而自动构建出室内数字平面图。文献[2]率先提出利用智能手机构建室内地图,并实现了环形矩形走廊的构建。即时定位与地图构建(SLAM)[3]的概念由Smith等在1988年提出,主要用于机器人在未知环境下自动构建室内地图。文献[4]实现了SmartSLAM系统,包括实时定位,室内地图创建和指纹地图构建。文献[5]提出CrowdInside系统,通过众包方式采集行人行走轨迹,实现室内平面图的自动构建。文献[6]利用事先已知的WiFi指纹库结合运动信息动态构建室内平面图,并提出判断走廊上房间顺序和走廊邻接关系的算法。文献[7]利用惯性传感器及拍摄图像的数据信息构建平面图。文献[8]提出语法增强算法来帮助室内地图的构建。

为能够在已知信息较少的情况下精确构建包括房间和走廊的室内平面图,本文提出一种简单易行的室内数字平面图自动构建方法。根据手机采集的行人轨迹特征和WiFi信号,结合聚类算法识别出门位置和楼梯位置等标志点,并使用PCA算法来计算走廊的长和宽,从而构建走廊的大小形状,最后采用α-shape算法绘制各房间的形状。

1 室内平面图自动构建方法

本文提出的地图构建方法如图1所示,首先通过PDR对手机采集的传感器数据进行计算得到每一步的位置坐标,并将坐标点连接为行人轨迹,然后通过标志点识别算法确定转弯、门位置和楼梯位置,根据门位置将轨迹划分为房间轨迹和走廊轨迹,最后通过聚类和主成分分析(PCA)算法确定走廊的长和宽,通过聚类和α-shape算法对各房间进行绘制,完成整个室内数字平面图的自动构建。

图1 室内平面图自动构建过程

1.1 行人轨迹获取

室内行人轨迹获取采用基于手机传感器的PDR,主要用到三轴加速度计、三轴磁力计、三轴陀螺仪和气压计。本文采用文献[9]中提出的PDR算法,首先采集原始加速度数据并进行平滑,然后根据平滑后的加速度数据识别行走状态,通过有限状态机识别行走周期并计步,步长根据其和加速度的关系进行估算,采用卡尔曼滤波根据相邻步长之间的关系对步长进行调整,方向计算采用加速度计和磁力计。

PDR算法对行人步数、步长和行走方向进行估算,结合初始位置,就能实现对室内行人的实时位置追踪。本文将行人的位置点表示为:{t,(x,y),o,r,a},其中,t表示行人在该位置点的时间,(x,y)为当前位置坐标,o表示当前方向,r表示在该位置点采集的WiFi指纹,即AP列表及信号强度,a表示该位置点属性,如转弯、门位置或楼梯。

1.1.1 行走周期识别及步数统计

一个行走周期从静止状态开始,经过波峰状态和波谷状态后,便完成了一个完整的行走周期,计步一次。通过设定状态阈值,可以判断并识别行走状态,包括静止状态阈值、波峰状态阈值和波谷状态阈值。由于存在传感器噪声,同时人的行走动作存在不规律性,有限状态机中的状态转换可能会出现错误转换情况。因此,算法根据加速度数据的变化动态设定状态阈值。假设Td表示动态设定的状态阀值,T表示固定的状态阈值:

Td=R0+T

(1)

其中,R0为动态设定的零参考值,其值根据加速度数据的实时变化动态设置。这样状态阈值就随零参考值和实时加速度数据动态变化,从而准确识别状态,减少错误的状态转换。状态的准确识别也保证了每个行走周期的起止时间的精确确定,从而提高步长计算的精度。零参考值R0的取值为本周期内所有状态的状态分界值的平均:

(2)

其中,n为本周期的状态数,bi为状态i的状态分界值。波峰状态的状态分界值为本状态加速度峰值和前一状态加速度谷值的平均;波谷状态的状态分界值为本状态加速度谷值和前一状态加速度峰值的平均;静止状态的状态分界值为本状态中所有加速度的均值。

1.1.2 基于卡尔曼滤波的步长计算

研究人体行走模型可以建立步长和行走中躯干的垂直位移之间的关系,进而获得行走周期中步长和z轴加速度之间的关系,从而根据z轴加速度计算步长。假设l代表步长,h为常数,N为一个周期内加速度样本数,ai、amax和amin分别为该周期中第i个加速度样本、加速度峰值和谷值,文献[10]提出的步长计算公式为:

(3)

人行走中速度的变化是一个渐变的过程,导致人行走中相邻2步的步长可能不同但差异不大。因此,可以在式(3)计算当前步长的基础上,结合上一步步长对该计算结果进行微调。本文采用卡尔曼滤波[11]结合基础算法进行步长计算。将步长作为系统状态Xk,将基础算法得到的步长作为量测值Zk。假设第k步步长Xk和第k-1步的步长Xk-1相等,步长的逐渐变化使用系统噪声Wk来表示。由于量测值代表的也是步长,因此量测矩阵为1,量测噪声用来表示基础步长算法的计算误差。系统状态方程式和量测方程式为:

Xk=Xk-1+Wk

(4)

Zk=Xk+Vk

(5)

1.1.3 方向确定

(6)

1.2 轨迹中标志点检测

1.2.1 转向点检测

行人在室内行走过程中,如果在某个位置发生左转或右转,则称该位置为转向点。在室内环境中,行人一般会在门口、走廊拐角、室内拐角等位置发生转向动作,因此可以将轨迹中的转向点作为一种室内标志点,并在后续处理中作为轨迹分割点。每当检测到行人步数发生变化时,也就是新轨迹点产生时,转向点检测算法进行转向点检测。首先判断当前一步和前一步方向的变化值是否大于阈值Δ,如果大于Δ,则判定当前位置为转向点,否则将当前方向变化值临时存储起来;如果出现连续n步转向,且n步转向累积值大于Δ,也将最后一个位置点判定为转向点,否则判定为没有发生转向。

1.2.2 门位置检测

门位置检测不仅关系到房间类型和走廊类型轨迹的区分,同时也是室内地图的重要标志点。由于人在进门和出门时通常会有转向动作,同时由于墙体影响室内外的WiFi信号不同,因此首先根据转向点检测算法检测出行人轨迹中的转向点位置,然后再根据WiFi信号进一步判断是否是门位置,包括2步:

1)一次识别。由于WiFi信号在穿墙后会有较大衰减,导致手机接收到的WiFi信号强度在房间内部和走廊上通常会不同。假设ri表示一个WiFi信号指纹:

ri=(si1,si2,…,sin)

(7)

其中,n表示接收到信号的AP个数,sik表示接收到的第k个AP的信号强度。2个WiFi指纹ri和rj之间的平均曼哈顿距离可以由下式计算得到:

(8)

如果相邻2步的d(ri,rj)大于阈值Wd,则初步判断当前位置为门口,否则不是。通过该方法能够得到如图2(a)所示结果,小圆圈为轨迹中识别出的门位置,三角形为真实门位置。从中可以看出,有一些转向点被误检测为门位置,同时还存在一些门位置没有被检测出来,因此需要二次识别。

2)二次识别。对一次识别得到的所有门位置采用基于密度的聚类(DBSCAN)算法进行聚类。DBSCAN算法[13]可以自动识别出远离聚类中心的噪声数据,即上面提到的误识别的门位置。n个聚类簇对应n个聚类中心,将每个聚类中心的半径为R的圆范围内的门位置点标记为该轨迹上的门位置点,从而完成门位置点的二次识别,如图2(b)所示。

图2 门位置识别

1.2.3 楼梯位置检测

室内环境往往是多楼层,楼梯位置是重要室内标志点。上下楼方式包括楼梯、扶梯和直梯。通过手机内置的气压计可以获得海拔高度,通过海拔高度的变化可以判断出行人是否进行上下楼,但要区分上下楼方式,则需要加入三轴加速度数据。识别过程包括2步:

1)识别直梯上下楼。首先采用移动平均算法对海拔高度数据进行平滑,平滑后的海拔高度序列H={h1,h2,…,hn}通过下式做线性拟合[14]:

(9)

其中,p(x)=a0+a1x为拟合得到的表达式,a1为斜率。

假设Hu为直梯上楼的经验阈值,Hd为直梯下楼的经验阈值,H0为上下楼的经验阈值。若a1>Hu,则为直梯上楼;若H0≤a1

2)识别楼梯和扶梯。首先求出加速度量级:

(10)

其中,(ax,ay,az)为三轴加速度数据。假设Au和Ad分别为楼梯上楼和楼梯下楼的加速度量级阈值。根据上一级识别的结果,如果是扶梯或楼梯上楼,若am

1.3 平面图自动构建

1.3.1 轨迹分段和聚类

根据门位置,系统将行人轨迹划分成房间类型和走廊类型,如图3所示,然后使用DBSCAN算法分别对房间类型轨迹点和走廊类型轨迹点进行聚类,同时去除噪声数据。聚类后的房间或走廊轨迹点如图4所示,其中圆点和方点是聚类簇中的点,而星形表示噪声点。

图3 轨迹类型

图4 轨迹点聚类结果

1.3.2 房间构建

房间构建就是解决从聚类后的二维点集构建平面形状的问题。通过二维点集构建平面形状最简单快捷的方法是找出点集的凸包作为平面形状,即包含点集中所有点的最小凸多边形。但实际的房间形状往往不会刚好就是点集的凸包,为了更加准确地构建出房间形状,本文采用α-shape算法来构建房间形状[5]。α-shape算法[15]是一种在欧几里得平面中通过简单线性曲线表示有限点集平面的算法。通过该算法,可以得到由聚类后的房间点集确定的一个集合平面,即房间形状,如图5所示。由于房间内部通常有家具等物品,因此通过该方法实际上获得的是房间可达区域的形状和大小。

图5 基于α-shape算法的房间形状构建

1.3.3 走廊构建

走廊通常为矩形,具有长度和宽度,构建走廊就是通过走廊轨迹点坐标计算走廊的长和宽。通过PCA[15]可以获得走廊轨迹点数据集的主方向和次方向,将数据集向主方向压缩可以得到走廊的长度,而将数据集向次方向压缩可以得到走廊的宽度。假设走廊轨迹点数据集为X={(xi,yi)|i=1,2,…,m},m为轨迹点个数。首先计算点集X的协方差矩阵:

P=XXT/m

(11)

图6 基于PCA算法的走廊的长和宽计算

1.3.4 室内地图绘制

通过走廊构建和房间构建,可以得到各条走廊的长宽以及各个房间的位置和形状,然后根据轨迹点的坐标将各个房间和走廊连接起来构成完整的室内平面图。通过这种方法构建的室内平面图可以正确反映房间和走廊的相对位置,房间的排列顺序以及走廊和房间的形状大小。房间的形状和大小由房间中的行人轨迹决定,反映的是可访问的房间区域,和房间的真实大小及形状可能不完全相同。对于走廊来说,因为走廊通常不会被障碍物占用,所以构建出的走廊通常能够代表真实走廊。

2 实验与结果分析

本文选择学校主楼4楼区域作为地图构建的实验环境。多名不同实验者分别手持三星Galaxy S3、三星Galaxy Note2以及红米Note3手机在不同时间进行传感器数据采集,包括加速度、角速度、磁场强度、海拔高度以及每检测到新的一步时的WiFi指纹。实验者的行走路线如图7中的直线所示,起始位置是412房间斜对面的楼梯位置,行走过程中没有对实验员的速度和行走方式进行约束,每条行走轨迹也不需要将所有路径走一遍,最终收集89条轨迹路径,包括在走廊两端的上下楼动作。采用PDR获得的行走轨迹如图8所示。

图7 行走路线

图8 行走轨迹

对收集到的轨迹数据首先通过标志点检测算法识别出轨迹中的转弯、门位置和楼梯位置,然后划分出房间类型的轨迹数据和走廊类型的轨迹数据。对房间类型轨迹使用DBSCAN算法聚类后得到7个聚类簇,对应该区域中的8个房间,其中416和418-1由于门位置较近和误差原因被聚类为一个簇。对每个聚类簇使用α-shape算法得到每个房间的边界轨迹点,即房间形状,如图9所示。对走廊类型的轨迹数据采用PCA算法进行数据降维处理获取主方向和次方向。图10展示了对图7中长走廊的处理过程,对短走廊的处理过程与此类似。图10(a)首先获得走廊上行人轨迹数据变化的主方向和次方向,图10(b)是将轨迹点数据集向变化主方向投影的结果,而图10(c)是将轨迹点数据集向变化次方向投影的结果。由于数据变化的主方向和次方向分别对应的是走廊的长和宽,所以对投影降维后的数据进行排序就可以分别找出长和宽的2个端点坐标,从而确定走廊的长和宽。

图9 房间形状

图10 走廊长和宽

根据房间和走廊的构建结果,可以得到构建完成的室内平面图,如图11所示,同时楼梯的位置也根据上下楼动作的识别标在图中。如果事先知道该实验环境中的房间是长方形的,那么可以对构建出来的室内平面图作进一步调整。首先通过围成每一个房间的轨迹点求得房间的中心位置坐标,本文定义与走廊平行的边为房间的长边,与走廊垂直的边为房间的宽边,通过围成每个房间的点计算得到房间长宽,结合房间中心即可将房间形状调整为长方形。经过调整,使平面图更加规整,符合实际,如图12所示。

图11 构建完成的室内平面图

图12 调整后的室内平面图

3 结束语

为方便快捷地绘制室内地图,本文提出一种室内平面图自动构建方法。该方法首先通过智能手机采集传感器数据,通过PDR确定行人行走轨迹,然后通过标志点检测算法识别出轨迹中的转弯、门位置和楼梯位置,并对轨迹进行走廊类型和房间类型的划分。房间构建采用聚类和α-shape算法,而走廊构建采用聚类和PCA算法,最后根据各房间和各走廊的坐标完成整个室内平面图的构建。当室内由于重新装修或布置导致室内环境发生变化时,该方法能够迅速反映出这种变化并自动创建新的平面图。

该方法依赖于较精确的PDR系统来获得行人轨迹。如果航位推算精度过低,系统则无法构建地图。另外,由于采用的是行人的行走轨迹,该方法构建出的实际上是室内可通达区域的平面图,对于无法通达的区域则无法构建相关平面图,因此,下一步将针对上述问题进行研究。