基于众包的室内地图自动构建算法*

2022-10-16吴伟施学成姚英彪2

通信技术 2022年9期

吴伟，施学成，姚英彪2,

（1.苏州中科安源信息技术有限公司，江苏苏州 215024；2.杭州电子科技大学探测预警与信息对抗研究院，浙江杭州 310018；3.杭州电子科技大学通信工程学院，浙江杭州 310018）

0 引言

近年来，室内制图领域百花齐放[1-3]，有的延续沿用传统的室外地图制作方法来制作室内地图，即通过专业人员利用专业设备线下实地收集地图绘制数据；有的利用互联网用户激励方式去鼓励用户主动上传地图相关数据；还有的通过获取建筑设计结构图纸来重新绘制室内地图。虽然上述这些方法都可以解决室内地图绘制问题，但各自优缺点也十分明显。比如通过专业人员和设备绘制得到的地图质量无疑是最好的，但是存在人力成本较高的缺陷。此外，人员和设备有限，覆盖面不广，以及室内环境的易变性的问题给室内地图的更新带来很大麻烦。为了解决此类问题，基于众包方式来构建室内地图成为研究热点。

文献[4]提出了CrowdInside 系统，该系统首先基于众包方式收集行人室内行走时的传感器数据；其次利用行人行走过程中的活动点将轨迹进行分割，并通过片段长度、片段密度及片段中每步平均行走时间来区分房间区域和走廊区域内的轨迹；再次利用基于密度的聚类算法聚类房间区域的轨迹和走廊区域的轨迹；最后用α-shape 方法构建房间和走廊地图。文献[5]利用众包采集到的Wi-Fi 指纹和识别出的用户运动信息提取各房间区域形状、房间邻接关系等室内平面图信息，并最终构建室内平面图。上述研究虽然都构建了室内地图，但其地图自动算法构建程度低，且所构建的地图与实际地图贴合度较低。

针对上述问题，本文提出一种基于众包的室内地图自动构建方案。方案的核心包括两点：（1）多条轨迹的自动合并与拓展；（2）基于轨迹点云数据的自动地图构建。现场实验结果表明，相比于基于主成分分析（Principal Component Analysi，PCA）的地图构建方法，本文提出的地图自动构建方法在地图交并比和位置误差这两个指标上都更好。

1 点云数据获取模型

1.1 数据预处理

点云数据是指行人室内行走时的位置坐标集合，可通过行人航迹推算（Pedestrian Dead Reckoning，PDR）算法计算得到。由于行人室内行走时收集的传感器数据包含着大量噪声，因此需对传感器数据进行去噪处理[6]。

文献[7]通过实验分析发现，相比于其他滤波器，巴特沃斯低通滤波器在保留原始数据的相关特征的基础上，能很好地消除传感器数据中的噪声。因此，本文利用截止频率为0.2π 的3 阶低通滤波器来消除原始数据中的噪声。

1.2 PDR 计算点云位置

PDR 是近年来在室内制图领域被广泛采用的算法，也是面向智能手机的算法中使用最多的[8-13]。如图1 所示，PDR 利用行人室内行走过程中收集的加速度计、陀螺仪及磁力计数据来估计行人的步长、航向等信息，进而推算行人的位置坐标。

图1 PDR 航迹推算

PDR 包括步态检测、步长估计和方向角计算3个部分。步态检测是指基于人一步内加速度表现为一个连续正负高峰的特点，判断行人是否在行走。本文采用峰值检测法[14]检测步态。步长估计用于估计行人一步间的距离，本文利用式（1）估计第k步的步长lk。

式中：α，β，γ为参数；ak,max和ak,min分别为第k步合加速度的峰值和谷值；fk为行走频率；vk为加速度方差。fk和vk满足：

式中：和分别为第k步的起始时刻和终止时刻；ak,i为第k步内的第i个加速度值；为第k步的加速度均值；Nk为第k步内加速度采样点的个数。

在方向角计算方面，由于陀螺仪不会受到磁场干扰且具有短距离精度高的特点[15]，因此本文利用陀螺仪来得到一步内方向角的变化量，其计算方式为：

式中：θk为由陀螺仪积分得到的第k步的方向角的变化量；M为第k步的陀螺仪采样点的个数；ρi和Δt分别为陀螺仪Z轴采样点的值和采样间隔。

在得到每步步长、方向角后，则可得到行人位置的表达式为：

最终所有步坐标的集合即为PDR轨迹点云数据。

2 PDR 轨迹点云数据处理模型

2.1 轨迹简化

轨迹简化指的是将PDR 得到的行人轨迹表示为只包括关键点（起点、转弯点、开门点、终点）的有序集合。本文规定所有轨迹的起点相同，将轨迹最后一步定义为终点，开门点通过特定动作识别。转弯点需满足两个条件：（1）转弯点所在步的航向角变化量的绝对值为局部最大值，且大于阈值Thrθlow；（2）以转弯点所在步为中心、窗口长度为len的窗口内，方向角变化量总和的绝对值大于阈值Thrθhigh，即：

则认为第k步为转弯点所在步，由此，一条轨迹可简化为：

Trani为第i条简化轨迹，in为当前轨迹第n个关键点，满足：

式中：Type(·)代表关键点种类，起始点、转弯点、开门点、终点赋值分别为0，1，2，3。

本文利用信息矩阵Mesi记录编号为i的简化轨迹的关键点编号、种类、方向角、位置等信息，如图2 所示。

图2 轨迹简化

图2 中，i1为轨迹起始点，i5为轨迹终点，其余为轨迹转弯点，矩阵Mesi为对应的轨迹信息矩阵。在简化所有轨迹后，得到了所有简化轨迹对应的轨迹信息矩阵集合Mes。

2.2 轨迹合并

在得到所有简化轨迹后，下一步是合并所有简化轨迹。本文用方阵Mop来记录所有轨迹中关键点之间的连通关系，方阵维度等于识别出的不同关键点数量。具体来说，当第j个和第k个关键点连通时（即存在直线轨迹），Mj,kop赋值为1，否则为0。轨迹合并的具体步骤如下：

（1）利用第1 条轨迹Tran1的信息初始化方阵Mop。

（2）从集合Mes中取出一个轨迹信息矩阵Mesot，将Mop与Mesot进行合并。具体来说，先检测关键点的相似性，若相似则更新Mop对应关键点信息（方向角、空间位置及相似点集合LS）；若不相似，则拓展Mop方阵来记录Mesot中的不相似的关键点（即更新轨迹连通信息）。

轨迹合并的伪代码如下：

代码第1 行确定循环次数为Mesot包含的关键点数目，代码第3 行初始化Mop当前处理点集合Pop1，代码第4 行遍历Mesot中关键点。代码第6行SD(·)用于判断Pop1中是否存在和Pot相似的点，SD(Pot,Pop1)会依次遍历Pop1中的关键点，若Pop1中存在关键点满足以下条件，则返回为True:

式中：Pot为对应Mesot中的关键点；Type(·)，Angle(·)，PosX(·)，PosY(·)分别用于获取关键点在Mes中的种类、方向角以及X和Y的坐标信息。

关键点相似需满足关键点的种类相同、方向角差值的绝对值小于或大于（相同转弯点转向不同的情况）、空间距离小于的条件。本文设定为20，为150，为2.5。

代码第7 行RP(·)函数用于更新轨迹信息矩阵Mesop中对应相似点的值和更新相似点集合LS，相似点集合指的是每一关键点及与其相似的点的并集，用于后续点云数据的提取。图3、图4 为轨迹合并和更新后的Mop及相似点序列示意图。

图3中A1与B1判断为相似，A2与B2判断为相似，因此更新A1与A2的相似点集合和，如图4所示。

图3 轨迹合并

图4 更新后的M op 及相似点序列

代码第9 行FN(·)用于更新Pop1，获取下一个连通区域。代码第11 行EM(·)通过拓展Mop记录连通信息，EM(·)伪代码如下：

图4 为更新后的Mop及相似点序列。SD(·)函数判断A3与B3不相似，因此进行矩阵拓展，首先拓展行（对应代码第3 行），其次拓展列（对应代码第5 和12 行），最后记录连通信息（对应代码第6 和10 行）。由此通过拓展Mop维度记录了Mesot中的连通信息。合并所有简化轨迹后得到记录了室内所有关键点连通信息的方阵Mopa，下一步将进行地图构建。

3 地图构建模型

3.1 点云数据提取

构建室内地图首先需要提取所有PDR 轨迹中位于相同区域的点云数据，本文提出一种基于广度优先思想的点云数据提取方法，具体步骤为：

（1）根据Mopa得到与Cur相连的关键点集合为ConsCur；

（2）从ConsCur中取出一个点ConCur(ConCur∈ConsCur)；

（3）根据点Cur和ConCur的相似点集合获取在Cur与ConCur间的PDR 轨迹编号；

（4）从对应编号的PDR 轨迹中取出位于这两个点之间的每一步的坐标；

（5）重复步骤（1）到步骤（4），直到遍历完ConsCur。

图5 为点云数据提取示意图。

图5 点云数据提取

假设A1-A2-A3-A4，A1-A2-B3-B4，A1-A2-C3-C4和A1-A2-D3为Mopa记录的室内连通信息，以提取A1-A2段子地图为例，假设A1，A2的相似点集合分别为：

由可知，有4 条轨迹（A，B，C，D）经过A1。由可知，有编号为A，B，C的3 条轨迹经过A2，则编号为A，B，C的3 条轨迹包含了A1-A2段子地图所需的点云数据。在得到经过该子地图内的行人轨迹编号后，利用关键点的步数信息即可提取对应轨迹中的点云数据。

上述A1段子地图获取到的点云数据可表示为：

3.2 地图构建

本文地图构建是利用栅格将每一段子地图进行覆盖，然后统计有效栅格，最后对得到的有效栅格进行规则化处理，从而完成子地图的构建。

同一子地图内的点云数据表示为：

式中：m为该段子地图内点云数目。

本文采用边长为l的正方形作为基本栅格将子地图覆盖（栅格区域用Sq表示），假设第i行第j列的栅格中心点坐标为：

则栅格4 个顶点（Q，R，S，T）的坐标为：

若存在Pv满足：

则认为Pv点云落入当前栅格中。若当前栅格落入的点云数目超过阈值Thrnum，则认为该栅格是有效的，由此可以得到所有有效栅格区域，如图6 所示。

图6 栅格规则化

由图6 可以看出，有效栅格区域存在“空洞”情况，为了使构建的地图贴近实际地图，本文对其规则化处理。首先定义Averow为Sq有效行的平均有效栅格数（有效行指的是有效栅格数不为0的行），Avecol为Sq有效列的平均有效栅格数，则有：

式中：Count(Sq)为Sq中有效栅格的数目；NumR，NumC分别为Sq中有效行数和有效列数。本文将有效栅格数目超过Averow的有效行的最小、最大行下标区间视为有效行范围，将有效栅格数目超过Avecol的有效列的最小、最大列下标区间视为有效列范围，并将位于有效范围内的栅格视为有效栅格，由此完成了有效栅格规则化处理。

最终基于广度优先思想分别构建子地图，并重复上述步骤，得到完整的室内地图。

4 实验结果与分析

本文将从地图构造、地图精度等方面评估基于本文所提算法构建的地图与基于α-shape[16]、基于主成分分析法[17]构建的室内地图的优劣，并评估所提算法的性能。

4.1 实验设置

本次实验选取了4 位志愿者，分别让其水平持Oneplus 8、荣耀20S、小米5 及Google Nexus 5 手机采集数据，这4 部手机均内置加速度计、磁力计、陀螺仪等惯性传感器，采样频率为50 Hz。实验场地如图7 所示。

图7 实验场地

实验场地主要由一条走廊及两种大小不一的共计6 个房间组成，走廊由若干个规格为0.6 m×0.6 m的地砖块铺设而成，长约52 m，宽约3 m；大房间（房间1 和房间2）长约13.2 m，宽约8.4 m；小房间（房间3～6）长约9 m，宽约6.6 m。志愿者水平持智能手机沿着室内区域不构成封闭轨迹正常行走，并以50 Hz 的采样频率采集三轴加速度、陀螺仪及磁力计数据。所有轨迹起点保持一致，志愿者点击“开始采集”按钮则开始采集数据，在到达尽头时点击“结束采集”按钮结束采集。本文共采集了80 条志愿者室内行走的轨迹数据，将得到的数据文本文件利用MATLAB 处理并进行实验仿真。

4.2 地图构造分析

基于PDR 算法计算得到的80 条行人室内轨迹点云数据如图8 所示。

图8 采集的80 条轨迹点云数据

图9 为利用边长为0.6 m 的正方形栅格覆盖房间1 所得到的有效区域图，其中，圆圈为各栅格中心点，栅格区域为构建出的房间有效区域，判定阈值Thrnum设置为2。构建的房间1 地图的有效区域长宽为22×13 个栅格长度。

图9 栅格边长为0.6 m 时构建的房间1 区域图

图10 为基于α-shape 方法构建的房间1 区域示意图，由图10 和图11 可以看出，栅格法相较于α-shape 方法，其所构建的室内地图更贴近于实际地图，且能消除部分异常轨迹点的干扰，但基于栅格法构建的室内地图精度会受栅格边长l影响。

图10 基于α-shape 法构建的房间1 区域图

图11 为利用边长为0.8 m 的正方形栅格覆盖房间1 所得到的有效区域图。

图11 栅格边长为0.8 m 时构建的房间1 区域图

用边长为0.8 m 的栅格构建的房间1 有效区域长宽为19×10 个栅格长度。为探究在本文实验环境下的最佳栅格边长l，本文固定有效栅格判定阈值Thrnum为2，调整栅格边长长度l，并将所得到的房间长宽结果汇总于表1。

表1 栅格边长结果

本文主要考虑了栅格边长在1 m 范围内的情况。由表1 可知，栅格边长为0.6 m 时构建的房间长宽与实际长宽更相符，因此后续地图构建时皆用边长为0.6 m 的栅格l 来构建，最终构建的平面图见图12。

图12 基于栅格法构建的室内地图

图12 中，栅格覆盖区域为所构建的房间地图，无栅格覆盖的区域为所构建的走廊地图。基于栅格法构建的室内地图精度依赖有效栅格的分布，在轨迹较少的情形下，表现为有效栅格分布较稀疏，会导致构建出的地图精度较低（房间6）。为进一步分析本文所提算法所构建的室内地图的优越性，本文基于文献[17]利用PCA 构建室内地图，并将其作为对比算法来评估所构建地图的精确性。

图13 为一段PCA 压缩室内走廊区域点云数据得到的区域长宽示意图，两段实线分别为PCA 投影得到的区域长宽，图14 为利用PCA 构建的室内地图。

图13 基于PCA 构建的子地图

图14 基于PCA 构建的室内地图

由图14 可看出，基于PCA 构建的室内地图存在两个缺陷：（1）投影长度依赖数据点的空间位置，数据点若分布较离散，即聚拢性较低，则投影长宽误差会变大，表现为在房间地图构建时，两相邻房间区域已出现重合现象（房间3、4，房间5、6）；（2）基于PCA 构建的地图的区域中心位置难以确认，若依赖点云数据中心位置去确认区域位置，会受点云数据分布密度影响，即点云中心位置并不代表实际区域中心位置。基于栅格法构建的室内地图则通过有效栅格阈值Thrnum和规则化有效栅格的方式筛除了部分异常点云数据，进而解决了相邻房间重叠问题。

4.3 地图精度分析

本文将从两个指标评测所提出的地图构建算法的优劣性，一是利用交并比（Intersection Over Union，IOU）去衡量本文所提出的室内地图构建方案与实际地图的吻合度，二是基于房间位置误差及走廊位置误差去评估关键点位置精度。IOU 定义为：

式中：Areap和Areat分别代表所构建的地图区域和实际真实区域；IOU为两者的交并比。IOU在理想状态下为1，但由于实际传感器精度和地图构建算法影响，IOU值往往达不到理想值。表2 给出了本文所提算法构建的房间及走廊的位置误差及交并比等性能指标。

表2 本文所提算法构建的地图精度

表2 中房间和走廊的位置误差分别为房间顶点位置、走廊顶点位置与实际位置的欧氏距离均值。表2 中房间1 和2 的轨迹数量最多且位置误差相对较小，因而交并比较大。房间4、房间5 及房间6一方面由于行走距离较远而导致位置误差较大，另一方面则因为轨迹数量相对较少且并未完全覆盖房间区域，导致交并比下降。本文提出的算法构建的地图的平均位置误差在1.94 m 左右，平均交并比在0.63 左右。

表3 为基于PCA 构建的室内各区域的精度表。由PCA 构建的地图的位置误差在2.87 m 左右，交并比在0.49 左右。可以看出，本文所提算法无论在区域交并比，还是在位置误差上均优于基于PCA的地图构建算法，且位置误差降低了32.4%，交并比提高了28.6%，由此可知基于本文方法构建的地图精度较高。