0 引言

随着智能手机的普及和移动互联网的发展，基于位置的服务在生活中的重要性日益凸显。电子地图作为位置服务应用的基础，因其可以使得室内室外服务无缝结合，具有极强的便捷性和实用性，也逐渐发展壮大。目前室外电子地图的相关技术与服务已日趋完善，但室内地图的构建以及基于室内地图的服务还处于探索阶段^[1]。如何高效、准确地构建室内地图^[2]是目前室内位置服务领域的一个研究热点，室内地图构建包括两个部分：结构构建和信息增强。结构构建确定地图基本结构，包括走廊、房间、楼梯等；信息增强完善地图信息，包括商店名称、门牌号等；结构构建是构建室内地图的基础，而如何基于传感器数据进行室内有效距离计算是结构构建的关键技术之一。基于传感器测距的场景有两个基本动作，手持设备行走和转身拍摄地标图像，如何利用传感器数据区分这两种动作并计算有效位移，是本文研究的难点之一。本文提出了一种新的方法，该方法根据人体行走模型，参照支持向量机(Support Vector Machine, SVM)的思想计算计步最优阈值，通过方向扰动剔除无效步数，可以帮助地图构建者获得较为精确的距离测试结果。

目前计算室内距离的方法主要有以下3种：1) 基于专业测距设备，如激光测距仪^[3]、声纳测距仪等；2) 基于图像分析的技术^[4]，利用图像处理的方法，解构图像中各个对象的空间位置^[5]和空间距离关系；3) 基于传感器数据的方法，计算测试者行走速度在时间纬度上的累积量或步数步幅统计的方式^[6]。

基于专业测距设备的方法优点是测量精确，误差较小，但成本较高，并且需要专业的操作人员操作；基于图像分析的方法优点是不需要专业设备，研究主要集中在图像中对象的识别，相对位置的计算，但计算量非常大，图像的质量对结果影响很大；基于传感器数据的方法是目前研究的热点方向，主要是因为其数据获取方便，成本相对较低，数据分析相对于图像处理也并不需要太大的计算量，不过目前的此类方法主要用在测量运动量等场景^[7]，存在较大的误差，因为基于速度的误差很难修正，单纯的步数乘以步幅的计算方式并不能反映真实的位移情况，其结果也无法达到构建地图所需要的精度。

本文基于智能手机多传感器(加速度传感器、磁力传感器和陀螺仪)数据的融合，重新设计了基于步数步幅统计的位移计算方法。使用有时间标记的加速度传感器与方向传感器数据，计算并筛选引起实际位移有效步数，结合步幅估计，计算手机持有者在室内移动的有效距离，并标注这一段路径的方向。融合多种传感器数据，既增加了可用于分析的数据总量，也增加了数据的多样性，从不同的纬度提取有效信息并相互验证，尽可能地接近真实情况，理论上可以达到较高的精度。在实际的模拟测试中，也验证了这一假设的有效性。

1 行走模型

本文通过步数步幅统计的方式计算位移，而步数步幅都与人的行走模型密切相关。从表面上看，人在行走的过程中，人体呈现出周期性运动，如脚步的起落、身体的摆动、重心的升降等；从数据上看，加速度是人体行走行为的数学表达，步数步幅的内在规律蕴含在3个方向的加速度数据里，所以可以从探索数据的周期性变化入手，进而找到加速度与步数步幅的关联关系，下面通过阐述人的行走模型^[8]来说明这其中的规律。

由图 1所示，一个完整的步伐从左(右)脚掌蹬地开始，腰部瞬间上提，左(右)脚落下，腰部下移，接着右(左)脚掌蹬地，腰部再次上提，循环往复，就变成了人的行走行为。在这其中最明显的特征是身体重心的上下移动，当两脚分开时，重心降低；当两脚并拢时，重心上升。这也就给检测步频提供了思路，在手持手机姿势稳定的情况下行走，只要检测重心的变化即重力方向的加速度变化周期，就可以以此统计步数。

人的行走习惯在一定时间内是稳定不变的，根据人体机械原理，步频加大时，出于维持平衡的原因，步幅也将增大，当测试者步频处于常规范围内时，步幅与步频有近似的线性关系。另外，身高与步幅也有类似的关系。利用数据分析的方法可以确定步幅与步频和身高的关系，从而可以通过步频和身高来估计步幅。

2 位移计算算法

基于步数步幅的有效位移计算算法中的步数统计与普通计步算法^[9]的区别在于位移计算算法必须要识别出真正产生有效距离的步数，而不是简单统计所有步数，因为转身、停留拍照、避让行人等动作虽然也产生了真实的步数，但并没有增加有效位移，识别并去除这些与有效位移无关的步数对位移计算结果至关重要。位移计算算法流程如图 2所示。

本文提出的算法对于步数的计算是通过分析一定时间窗内加速度传感器z轴方向数据的波形，设置上下两个阈值作为有效性检查，一步开始时，波形的峰值会大于上阈值，一步结束时，波形的波谷会小于下阈值，重复这一过程，就可以实时检测出步数^[10]。在方法上，首先对原始加速度数据进行采样，在保证不丢失信息的前提下减少计算量，同时也可以过滤掉一些干扰数据；其次是滤波处理，使波形平滑，减少统计波峰波谷时的误差；再次检测极值点和计算阈值，为检测波峰波谷作好铺垫；最后按照一个有效波形周期对应一步的规则检测步数。

本文算法对于步数有效性的检测主要是通过磁力传感器的数据，以陀螺仪的数据作为辅助。在非有效行走时，方向会在一定时间内发生剧烈扰动，而这种扰动在数据层面表现为离散程度的变化，可以据此判断每一步对于位移的有效性。

2.1 原始数据

本文实验采用的数据是通过自制程序在Android手机上采集得来^[11]。三轴加速度传感器可以产生x、y、z三个正交轴上的加速度值，分别对应着人体侧向、前向、纵向的加速度，由于人在行走时重心的变化比较明显且具有一定的稳定性，即z轴上加速度变化具有较强的可识别性，因此在步数检测时只利用z轴方向的加速度数据。

由于加速度传感器z轴方向数据本身叠加了重力加速度，为方便分析，算法使用到的z轴方向数据是去除重力影响后的加速度值。图 3为实验中的一组z轴数据，由图可以看出，虽然噪声较多，波形也不够平滑，但这一组数据在整体上仍然呈现周期性规律，每一个完整的周期对应的就是一个完整的步伐。

2.2 采样与滤波

在实际的数据处理中，为了减小计算量，往往会首先进行采样。根据香农采样定理“为了不失真地恢复模拟信号，采样频率应该不小于模拟信号频谱中最高频率的2倍”。原传感器的采样频率是100Hz，通常人体步行频率为0.2~5Hz，其中最典型的步行频率低于2Hz。不过，为了给后续的数据处理预留足够的操作空间，不能按最低标准采样，本文按照1/4的比例进行均匀重采样，可以保证信息不失真。

实际获得的各种数据总是存在各种各样的噪声。为了得到更好的结果，首先需要对数据进行进一步预处理，在本文涉及到的数据中，其目标是使波形平滑，去除尖刺，减小后续处理的误差。可设计截止频率为5Hz的有限冲激响应(Finite Impulse Response, FIR)低通滤波器^[12]，为简化设计，本文采用4点平均平滑滤波，即

$ D(n) = \sum\limits_{i = 0}^3 {\frac{{d\left( {n - i} \right)}}{4}} $

(1)

其中：d(n)为原始z轴速度信号；D(n)为平滑滤波后信号。图 4为采样并平滑滤波后的数据。与图 3相比，图 4中的数据量更小也更平滑，剔除掉了噪声并且没有破环原数据的结构，处理之后的数据特征更加突出。

2.3 计算阈值

由于在行走时每个人重心移动的幅度不同，这就导致了阈值是因人而异的，而确定阈值是检测步数的前提条件，本文实验中使用了带标记的数据。因为可用的阈值有很多个选择，因此找到最优的阈值是增强算法泛化能力的关键。

在分类问题中，同样存在以上的问题，如何在众多的分类面中找到最优的分类面是决定一个分类算法优劣的关键。在机器学习方法中，支持向量机^[13]在此类问题下表现出了极强的泛化能力，它通过确定两类样本之间的最大间隔寻找边界分类面，确定两个边界分类面中间的平面为最终分类面。如图 5所示，该分类面可以尽可能地将两类样本分开，从而使得该平面对训练样本局部扰动“容忍”性更好。

在样本空间中，分类面可通过如下线性方程来描述：

$ {\mathit{\boldsymbol{\omega }}^{\rm{T}}}\mathit{\boldsymbol{x}} + b = 0 $

(2)

其中：ω=(ω₁; ω₂; …; ω_d)为法向量，决定了分类面的方向；b为位移项，决定了分类面与原点之间的距离。显然，分类面可被法向量ω和位移b确定，将其记为(ω, b)。样本空间中任意点x到分类面(ω, b)的距离可写为：

$ r = |{\mathit{\boldsymbol{\omega }}^{\rm{T}}}\mathit{\boldsymbol{x}} + b|/\parallel \mathit{\boldsymbol{\omega }}\parallel $

(3)

假设分类面(ω, b)能将训练样本正确分类，即对于(x_i, y_i)∈D，若y_i=+1，则有ω^Tx_i+b > 0；若y_i=－1，则有ω^Tx_i+b < 0。令：

$ \left\{ \begin{array}{l} {\mathit{\boldsymbol{\omega }}^{\rm{T}}}{\mathit{\boldsymbol{x}}_i} + b \ge + 1, {y_i} = + 1\\ {\mathit{\boldsymbol{\omega }}^{\rm{T}}}{\mathit{\boldsymbol{x}}_i} + b \le - 1, {y_i} = - 1 \end{array} \right. $

(4)

如图 5所示，距离分类面最近的这几个训练样本点使得式(4) 中的等号成立，它们被称为“支持向量”，两个异类支持向量到分类面的距离之和(被称为间隔)为：

$ \gamma = 2/\parallel \mathit{\boldsymbol{\omega }}\parallel $

(5)

欲找到具有“最大间隔”的分类面，也就是要找能满足式中约束的参数ω和b，使得γ最大，即：

$ \begin{array}{l} \mathop {\min }\limits_{{\bf{ \pmb{\mathsf{ ω}} }},b} {\left\| {\bf{ \pmb{\mathsf{ ω}} }} \right\|^2}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;{y_i}({\mathit{\boldsymbol{\omega }}^{\rm{T}}}{\mathit{\boldsymbol{x}}_i} + b) \ge 1;\;i = 1,2, \cdots ,m \end{array} $

(6)

这就是支持向量机(SVM)的基本型。

由于要解决的问题高度相似，本文参照了支持向量机的思想来学习最优阈值。使用用户提前标记的步数为N的行走z轴加速度D(n)作为输入，算法首先找到可用阈值的上下边界，因为最优阈值就是离上下边界最远的值，所以可以确定上下边界的中间值即为最优阈值。以图 6寻找最优上阈值为例，从上下边界分别向中间移动，直到穿过当前阈值的波峰个数满足要求，则可以得到p₁、p₂两个上阈值，取p₁、p₂中间的值作为上阈值p。

算法描述如下。

输入：加速度值D(n)，步数N。

输出：下阈值q，上阈值p。

参数：Nq表示峰值小于q的波谷个数，Np表示峰值大于p的波峰个数，Δ为一个很小的正数，max(D(n))表示取最大的D(n)值，min(D(n))表示取最小的D(n)值。

令q₁=p₁=(max(D(n))+min(D(n)))/2

while(Nq!=N && q > min(D(n))){

  q₁=q₁-Δ

}

while(Np!=N && p < max(D(n))){

  p₁=p₁+Δ

}

令q₂=min(D(n)), p₂=max(D(n)),

c=(max(D(n))+min(D(n))/2

while(Nq!=N && q < c){

  q₁=q₁+Δ

}

while(Np!=N && p > c){

  p₁=p₁-Δ

}

q=(q₁+q₂)/2

p=(p₁+p₂)/2

2.4 步数检测

步数检测主要是通过检测极值点，筛选有效完整的波形，利用一个完整的波形周期对应一个步伐的原则完成的。

2.4.1 极值检测

在微积分中，极值定理说明如果实函数f在闭区间[v, w]上是连续函数，则它一定取得最大值和最小值，至少一次。也就是说，存在[v, w]内的c和d，使得：

$ f(c) \ge f(x) \ge f(d);\;x \in [v{\rm{, }}w] $

(7)

令所有z轴加速度数据为D(n)，按照时间轴的方向，依次检测极值点，设置一个长度为3的滑动数组Z，存储当前的三个连续值，Z[0]=D(n-2), Z[1]=D(n-1), Z[2]=D(n)，根据极值判断理论：

如果Z[1] < Z[0]且Z[2] > Z[1]，那么Z[1]为最小值；

如果Z[1] > Z[0]且Z[2] < Z[1]，那么Z[1]为最大值。

2.4.2 步伐检测

令所有的极值点数据J(n)，按照时间轴的方向，依次检测波峰波谷，设置一个长度为2的滑动数组d，存储当前两个连续的极值Z[0]=J(n-1), Z[1]=J(n)，根据一个完整的波形周期对应一步的原则：

如果Z[0] > p且Z[1] < q，则累计一步；

否则，向后滑动数组。

另外需要注意的是，时间窗口的平移并不是直接从新的数据开始，而是要包含上一个时间窗口中判断无效的尾部数据，这样才能防止半步的数据被舍弃，避免因为数据截断所造成的误差^[14]。如图 7所示，长虚线表示第1个时间窗口，短虚线表示第2个时间窗口，第2个时间窗口开始的时间是第1个时间窗口最后一个波谷结束的时间。

2.5 步伐有效性检测

在这一阶段，本文将筛选出产生实际位移的步数。在非正常行走时，如拍照、转身等都会产生步数，但这类步数对距离没有贡献，需要剔除掉。在实际测试中观察到，在非正常行走时，测试者的方向一直在大范围内变动，在数据层面看，方向数据的离散度很大，由此可以通过每一步时间附近的方向离散程度来检测此步的有效性。同理，陀螺仪的旋转加速度数据也可以进行辅助判断。本文以方向数据为例。

图 8(a)是正常行走时的方向数据，数据只在小范围内波动，波形平稳；图 8(b)是转弯时方向数据，可以看出中间有个明显的跃阶，那个时刻就是发生转向的时间；图 8(c)是非正常行走时的方向数据，波动很大。从图 8上可以直观地看出，方向数据可以明显地区分有效步伐和无效步伐，利用一定时间方向数据的方差：

$ D = \sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {{{({x_i} - x)}^2}} } $

(8)

其中：x= $\frac{1}{n}\sum\limits_{i = 1}^n {{x_i}} $为样本值的平均数，x_i为每个采样点的方向值，当方差大于正常水平时，判断此步伐无效，使用阈值可以很容易识别出转弯的动作，这样就确定了所有有效步数的数据。

2.6 步幅估计

位移是有效步数与步幅的乘积，准确地估计步幅对位移的计算非常关键。一般来说，加速时，步频会加大，为维持身体平衡，步幅也将加大，但步频不可能无限增大，步幅的范围也是有上下限的，当测试者步频处于常规范围时，步幅与步频有近似的线性关系。同理，身高与步幅也存在着类似的关系。通过对多个测试者的行走数据进行分析，得到步频F与身高和步幅的关系对照表^[15]，具体关系如表 1所示。

2.7 位移计算

经过以上步骤的处理，此时的数据如图 9所示，图中的每个点代表一步，可以看到，图 9中的点明显分为两部分，断点处表示转向的位置，从图 9的数据可知，在15s时转了一个90°的弯。

在室内地图结构构建中，平面线段特征的构建与位移和方向均相关，而位移是有效步数与步幅的乘积，方向则跟每一步的方向相关。由于每一步的方向与实际方向都有小范围内的偏离，所以需要融合多步的方向推算真实的路径方向。在此阶段把步数按大致方向分段，每段内的方向偏差不大于20°，每段采用步数乘以步幅的方式计算距离，再结合每步的方向采用简单取平均的方式可计算出此段的方向，即可得到位移和方向。

3 实验测试结果与分析

测试设备为一部型号为Nexus 4操作系统为Android 5.1的智能手机，测试地点为某大学的一栋封闭教学楼内。本实验共有10名测试者，每名测试者测试10次，最终结果取平均。

3.1 不同场景下的实验分析

实验通过模拟多种构建室内地图时的场景，使用实验设备进行实际测试，采集并分析实验数据。本文通过避让次数来反映人流情况。测试者每次在室内行走距离为50m。实验结果如图 10所示。

由图 10(a)可以看出行为越复杂，则测距误差就越大；人流量对测试结果有很大的影响，但是正常的偶尔的避让行为并不会引起误差的迅速增加，在测试过程中干扰因素越少，则测试的精准度越高。最常见的场景下，测距误差率在4%左右。图 10(b)中显示行为越复杂，则方向误差就越大；人流量并没有对方向数据造成较大的影响，这是因为方向的获取主要来自于磁场数据，而人流量并不会造成磁场的变化。

3.2 不同方法下的实验分析

在相同的实验环境下，并且不考虑人流量的影响，测试了其他两种测距算法的误差率，图像测距和基于速度的传感器测距(速度测距)，前者通过识别图像中的标的物实现空间测距，后者通过速度在时间上的积分实现测距。本实验中使用手机应用Smart Distance进行图像测距，利用罗印^[6]提出的方法进行速度测距。实验结果如表 2所示。

由表 2可知，图像无法识别复杂的结构，但走廊的测距精度较高；速度测距在简单场景中，其精度要高于本文中的方法，但在室内地图构建最常见的场景中，其精度要低于本文中的方法，因此，相比图像测距和速度测距等方法，本文方法在室内地图构建时的测距问题中表现得更好。

4 结语

传统测距方法在室内地图构建中因成本、精度等无法达到预期效果，针对此问题，本文重新设计了基于步数步幅统计的室内位移算法。通过参照机器学习方法支持向量机的优点设定最优阈值增强了算法泛化能力，通过评估方向的离散程度筛选有效步数，利用步频、身高等与步幅的相关关系估计步幅克服了现有方法的缺陷与不足，通过融合多种传感数据提高了感知能力与精度。本文在低成本低可靠数据的基础上，在室内地图构建的各种场景下，均获得了较高的精度。

在实际应用中，利用工程方法，结合多人多数据多方法综合评估的方式，如地图同比例缩放、线段之间相互校正、角度之间相互校正等，可以把距离误差率控制在2%以内，方向误差控制在1.5%左右，能够满足实际要求。

但本文研究也有一些不足：1) 数据采集的过程中需要测试者以稳定的姿势手持设备；2) 步幅的估计并没有考虑到个人习惯的影响，这在大规模的数据分析中可能会造成一些误差。在以后的研究中，可以放开这些限制，融合更多传感器数据，从数据分析的角度深度挖掘内在规律，提高数据的纯度，进而提高位移计算的精确度。