基于众源数据的室内外一体化行人路网构建

周宝定，张文香，黄金彩，李清泉

1. 深圳大学城市智慧交通与安全运维研究院，广东 深圳 518060； 2. 滨海城市韧性基础设施教育部重点实验室(深圳大学)，广东 深圳 518060； 3. 深圳大学土木与交通工程学院，广东 深圳 518060； 4. 中南大学大数据研究院，湖南 长沙 410083； 5. 深圳大学广东省城市空间信息工程重点实验室，广东 深圳 518060

2021年全国两会掀起了“碳达峰”与“碳中和”的热烈讨论，绿色发展的理念早已深入人心。步行是一种重要的绿色出行方式，也是城市居民最基本的出行方式之一[1]。随着国家不断倡导绿色出行理念，以及人们对自身健康关注度的提高，越来越多的决策者开始注重城市步行带、骑行带等绿色出行设施的建设，人们亦越来越多地选择步行作为日常出行方式，使得步行导航需求不断增加。行人路网作为步行导航系统中关键的一类基础地理信息数据而逐渐受到关注。然而，目前主流导航应用中提供的道路数据主要基于机动车道路网，如城市快速路、省道、环线等，步行路网如高层建筑物间的步行路径、地下通道、室内通行路径等基础地理信息数据的获取仍存在困难，难以满足当前绿色出行的现实需要[1]。从步行路网的概念上来说，可供绿色出行的步行路网不仅包含传统意义上的室外的步行道路结构(如步行道、骑行绿道等)，还应当包括室内可通行路径(如建筑穿行路径等)，共同构成可步行路网(即室内外一体化步行路网)的关键组成部分[2]，并且室内/外可步行道路结构通过拓扑连接构成室内外一体化步行路网的整体几何拓扑形态。然而，在高层建筑密集的城市环境中，这类路径数据的缺失会导致导航系统在提供路线规划服务时只能从建筑物外围绕过，无法搜索出现实中真实的最优路径。因此，在行人路网中，考虑到室内通行路径，构建室内外一体化行人路网，使整个路网更加完整准确，对于推进绿色低碳出行的发展、完善智能导航服务等方面都具有重要意义。

传统道路数据的采集和获取需要依靠人工实地测量来绘制道路地图[3]，成本高且生产周期长，无法及时更新路网。自动制图[4]是道路网构建的新方法，根据数据来源不同分为两种方向，即基于航空影像的路网构建法和基于众源轨迹的路网构建法。基于航空影像的路网自动构建方法很大程度上取决于图像的分辨率，且难以准确提取地物遮挡处的路段，如隧道、植被覆盖路段等[5]；从众源GNSS轨迹数据中提取路网是一种常用并且有效的路网构建方法[4,6-8]，且对于机动车道路网自动构建的研究已较成熟，并逐渐应用于行人路网构建的研究中[1,3,9]。

行人路网与机动车导航网络不同，是满足行人特定需求的道路拓扑网络[10]，由于专业测量车辆受道路限制，无法驶入步行专用道，因此行人路网与机动车道路网的采集方式也有所不同。根据所采用的数据来源的不同，主要分为基于多源空间数据库集成的方法和基于众源地理数据的方法。基于多源空间数据库集成的方法中，文献[11]获取了政府和相关部门的地理空间数据集，分类并提取出空间数据中的人行道、立交桥、人行天桥等，将该类多边形自动转化为中心点或者交叉点，生成节点连线图作为行人路网；文献[12]则基于可获得的地理空间数据集，创建了一个三步模型来生成人行道、人行横道和人行路径的路网。基于多源地理空间数据集成的方法主要缺陷在于空间数据库的可访问性难以保证，并且各来源数据集间存在差异，需要匹配修改，适用性差。基于众源地理数据[13]的方法则为步行路网数据的获取提供了新思路，其中智能手机中内嵌的各种传感器(如GNSS模块)使得人人都能成为地理数据的采集者，提高了数据获取的便捷性。在采集众源数据的方式上，位置社交网络[14]首先被用于搜集收集用户的真实GNSS轨迹，用于构建行人路网；在道路提取的方法上，文献[15]在特征点滤波的基础上，采用中心点划分聚类法将得到的特征点轨迹进行聚类进而生成路网；文献[16]采用轨迹聚合的方法进行行人路网提取，其主要过程为基于志愿地理信息[17]数据计算轨迹相似度，进而设置邻域阈值进行轨迹聚合并得到提取的道路中心线；文献[18]提出一种多尺度分形维算法，将轨迹数据分为有明确目标的步行和没有明确目标的步行，对没有明确目标的步行数据采用改进的连通域分析算法，得到行人区域，对有明确目标的步行数据采用基于点聚类的核密度估计算法，得到行人路径。基于莫尔斯理论的路网提取则由于具有较好的几何、拓扑保持能力获得了关注[19]；文献[1]对轨迹数据进行核密度分析，提取密度图的山脊线，初步采用莫尔斯理论生成密集且复杂的行人路网。

在室内路网构建方面，众多学者对室内导航地图的构建进行了广泛研究，这些室内地图制作方法主要依赖特殊的传感器，例如基于激光传感器[20]、深度相机[21]、声呐[22]及多源传感器融合的方法[23]进行室内导航地图构建。这些方法的缺点在于需要使用机器人[23]或者背包[24]数据采集平台，并且需要配套使用专业软硬件进行数据分析处理，制图过程费时费力。为解决这一问题，有学者从当前普遍采用的建筑图纸进行室内制图，例如，文献[25]采用建筑CAD平面图对室内空间进行处理，通过对室内房间、门、走廊等空间对象进行建模识别，生成导航节点与导航边，再与室外路网通过锚点(建筑物出入口)进行连接，完成坐标转换得到室内外一体化导航路网。然而，基于图纸的方法对CAD等建筑平面图的质量要求较高，而且对于大型建筑物室内空间的更新无法及时追踪。随着众包制图技术的兴起，廉价的智能手机搭载的多种环境传感器[26-29]为室内和室外一体化制图提供了新的数据源[9]，由于智能手机普及率高且实时更新，因此为室内道路制图提供了新的解决思路，并且开始广泛应用于室内定位[26-29]、行为识别[30-31]、环境感知等研究中[32]。

分析已有研究可以发现，目前行人路网自动构建方法分别关注于室外路网和室内路网的单独构建，然而，关于室内外一体化行人路网自动构建的研究不足，难以充分满足步行导航等绿色出行导航服务的需求。实际上，人群步行行为的自由度很大，在可步行区域、高层建筑物、地下通道等区域，亦可步行穿过，以上所述室内步行路网的缺失直接影响到步行导航服务的完整性和便利性，因此，如何自动构建室内外一体化行人路网是步行导航服务的关键。

鉴于此，本文提出一种室内外一体化的行人路网构建方法，该方法首先通过室内外检测算法来判断并筛选出室内穿行轨迹，再基于改进的行人航位推算方法(PDR)推算出准确的室内轨迹，用于补充原有缺失的室内步行轨迹数据，最后采用莫尔斯理论的路网构建算法进行路网提取。试验分析采用高精度专业测量设备采集得到真实路网数据，对试验结果进行对比分析，证明了所提方法的有效性。

1 室内外一体化路网构建

1.1 室内外状态检测

在路网自动构建中，原始GNSS数据最接近真实的行人路网[3]，但在建筑物遮挡的室内环境下，GNSS数据会丢失或漂移。因此，首先需要进行室内外检测(I-O detection)，对所有轨迹数据进行室内外判断，将室内轨迹段筛选出来待后续处理。

智能手机中的GNSS模块、相机模块[33]、光强传感器[34]、Wi-Fi模块[35]、蜂窝基站信号[34]及磁强计[36]均可用于室内外检测。其中GNSS信号为检测移动目标室内外状态提供了一种更直接的信息特征[37]，因此，本文基于GNSS信号检测来判断室内外轨迹。令行人轨迹为

T={P1,P2,P3,…PN}

式中，Pi代表某用户GNSS轨迹点，Pi={ti,li,ni,hi,ai,ri}；ti为该轨迹点的时间戳；li=(xi,yi)为该点的位置坐标，xi表示经度，yi表示纬度；ni为该轨迹点接收的有效卫星数量；hi为该点的GNSS水平精度；ai为该轨迹点加速度计的信息，ai=(axi,ayi,azi)，分别表示该点分别在X轴、Y轴、Z轴方向的加速度值；ri为该轨迹点的陀螺仪记录信息，ri=(rxi,ryi,rzi)，分别表示陀螺仪绕着X轴、Y轴和Z轴的旋转速率。

在进行室内外检测(I-O detection)时，由于GNSS设备启动时需要一段时间(约1 min)用于搜索卫星，导致该时间段内数据精度差、噪音大。因此，在进行室内外检测前需要对原始数据进行预处理，删除搜星阶段的噪音数据，即删除每条GNSS轨迹数据前1 min的轨迹数据。令indi表示GNSS点Pi的室内外状态，indi=1则表示Pi所处状态为室内，indi=0则表示Pi所处状态为室外。为筛选室内GNSS点，本文根据式(1)对所有GNSS点逐一进行室内外状态筛查

(1)

式中，n表示有效卫星数，指的是某GNSS轨迹点的所处位置上，卫星信噪比低于30 dB的有效卫星数量，有效卫星数越多，则GNSS位置点可靠性越高；h表示水平精度，其值越小表明GNSS位置信息越准确；Δl=‖Pi,Pi+1‖，表示相邻GNSS点Pi和Pi+1之间的欧氏距离。

式(1)设置3个阈值σn、σh和σl来进行Pi的室内外状态检测，若有效卫星数n小于给定阈值σn，或水平精度h大于给定阈值σh，或Δl大于给定阈值σl，则indi=1，即Pi为室内点。与室内轨迹点相邻的室外轨迹点可分为两种：由室外进入室内的衔接轨迹点称为“丢失点”，由室内到室外的衔接轨迹点称为“找回点”，截取“丢失点”与“找回点”之间的轨迹段标记为室内穿行轨迹。

1.2 行人航位推算(PDR)

行人航位推算(PDR)基于行人步态的运动生理学特征，计算步频和步长，结合陀螺仪等传感器估计航向，从而实现位置推算，这种算法在短距离中取得了较好的效果[38]，常用于行人定位系统中。行人航位推算(PDR)的原理如图1所示，其中E为正东方向，N为正北方向，θ为航向角，L为步长。

图1 行人航位推算(PDR)的过程和原理Fig.1 The process and principle of PDR

(1) 步数检测：行人的行走步态呈明显周期性，从抬脚到落地，重心抬升至下降，垂直方向加速度数据表现呈波峰与波谷曲线[39]。利用智能手机内置的加速度计采集到的ai=(axi,ayi,azi)三轴加速度值计算合成加速度，剔除重力g的影响，通过巴特沃滋滤波进行平滑处理，消除伪波峰。采用加速度波峰—波谷探测的步态检测模型[34]来计算行走步数

(2)

(2) 步长估计：采用常数模型对步长进行估算。用室外轨迹段行走距离除以步数得到一个常量作为估计步长Lk。

(3) 方向推算：对陀螺仪数据进行积分计算，计算出每走一步相对初始位置的角度变化θk。

最后进行PDR推算，得到室内轨迹的相对位置

(3)

行人航位推算(PDR)存在着累积误差，可以通过活动序列[30]进行匹配以修正误差。本文以GNSS丢失点为原点，将墨卡托坐标系转换至WGS-84坐标系，完成平面坐标到经纬度坐标的转换，以GNSS找回点为标准，计算PDR推算终点与GNSS找回点之间的角度及位置的差值，通过坐标旋转与位置平差以消除行人航位推算(PDR)的累计误差，得到推算的室内轨迹数据，保留时间戳以便进行室内外轨迹拼接。最终得到的室内数据形式为Pi=(ti,xi,yi)。提取原始数据的时间戳与经纬度，根据时间戳的先后顺序将PDR推算得到的室内轨迹段补充至原始数据相对应的位置，得到完整准确的行人室内轨迹数据。

1.3 室内外一体化路网构建

本文基于莫尔斯理论进行室内外一体化路网的构建。室内外路网由于等级不同、用途差异，会造成不同道路上行人步行的频率差异，进而导致上传的众源步行轨迹呈现空间密度分布不均的特点，为路网的提取增加困难。本文方法可以兼顾数据的空间密度差异，提取几何完整、拓扑正确的室内外一体化路网。本文方法在行人航位推断的基础上，首先采用核密度估计方法生成轨迹密度图；其次将轨迹密度图抽象化地形图，将各个点的高程对应该点的轨迹密度值；进而基于莫尔斯理论检索地形图中的特征点，如鞍点、极值点，按照一定的规则连接特征点并提取山脊线作为最终路网，具体过程如下。

1.3.1 核密度分析

核密度分析主要计算轨迹段在邻域内的单位密度，从而生成密度图。令E={e1,e2,…,em}，表示以经纬度为节点的所有轨迹段的集合，L为所有轨迹的矩形边界框，顶点集合为V={v1,v2,…,vn}。首先需要确定搜索半径，即带宽R，带宽值越小，生成栅格的显示信息越详细

(4)

式中，Ds是标准距离，即所有轨迹与其轨迹质心之间距离的标准差

(5)

(6)

式中，Dm为中值距离；n是轨迹段的数量总和。

进而，采用式(6)进行轨迹点的核密度估计可知每个顶点vi与每条轨迹ei均覆盖着一个平滑曲面。以其所在位置为中心向四周发散，所在位置处密度最大，随着与轨迹间距增大，密度值逐渐减小，输出的栅格像元密度各轨迹为在栅格像元中心叠加的所有密度值的总和。

1.3.2 基于莫尔斯理论的路网重构

本文采用莫尔斯理论进行室内外一体化路网重建，其基本思想是将轨迹密度图抽象化为地形图，通过流形学习方法，提取地形图中能够形成稳定流形的山脊线作为最终路网拓扑结构图，如图2所示。首先构建平滑函数f:S2→S，表示核密度值的二维函数，其中S2表示密度函数的定义域，(x,y)∈S2表示密度图中各点坐标，轨迹点的核密度图则可以表示为Q=(x,y,f(x,y))。函数f的梯度值Δf(v)表示函数f在点v处的梯度向量，将密度图Q视为地形图，假设某水滴从任意点滑落，其滑落方向是v点处坡度最陡的方向，即该点沿着该梯度向量的方向以最大速率减小，水滴沿梯度方向的曲线称为积分线。当Δf(v)=0表示v点是函数f的关键点，否则为正则点[40]，关键点则分为峰点、鞍点和谷点，令点v与它邻域点的集合为St(v)，各关键点定义如下。

(1) 峰点，当点v的切平面与集合St(v)有且仅有一个交点，且集合St(v)中各点的各密度值小于点v的密度值时，点v称为峰点。

(2) 谷点，当点v的切平面与集合St(v)有且仅有一个交点，且集合St(v)中各点的各密度值大于点v的密度值时，则点v为谷点。

(3) 鞍点，当点v的切平面将St(v)分割成k部分，且k≥4时，则点v为鞍点[41]；若平面将St(v)分割为两部分，点v为正则点。

核密度图中各关键点的积分线为室内外一体化路网构建提供关键基础。积分线上流入某关键点的所有点的集合称为稳定流形，稳定流形具有几何、拓扑完整性，保证了提取道路网的几何和拓扑正确性。两个关键点的积分线为关键线，可以发现，关键线是两个关键点的稳定流形。通过上述分析可知：①峰点的稳定流形为峰点本身；②鞍点的稳定流形是沿着峰点到鞍点的“山脊线”；③谷点的稳定流形则是从峰点至谷点的所有关键线的集合。其中，鞍点的稳定流形为道路网的提取提供了关键基础：在原始轨迹数据中，由于道路的等级和用途差异会导致轨迹密度空间分布的不均匀性，行人步行行为受路网约束，因此导致密度较高的区域总是位于道路面上，且轨迹密度函数中极大值总是沿道路面中心附近分布，而密度较低的区域位于不可步行区域。通过上述分析可以发现，道路网几何形状可以用地形图中所有山脊线来进行几何表示。试验分析中，计算试验区域所有鞍点的稳定流形，可得到几何和拓扑完整的室内外一体化道路网络。莫尔斯方法中持续值是衡量特征点重要性的方法[42]，给定不同阈值δ可得到不同简化程度的路网，该阈值可将持续值小于阈值δ的稳定流形过滤，试验中对阈值δ的最佳取值进行对比分析。

图2 山脊说明Fig.2 Illustration of ridge

2 试验结果分析

试验以深圳大学沧海校区为研究区域，图3(a)所示为试验区域的开放街道地图(open street map,OSM)，试验区域路网包含机动车道、人行道、人行横道、小径、室内穿行路径等复杂密集类型的室内外道路，该区域较适合验证本文所提方法。试验采用在深圳大学沧海校区收集到的260条众源步行轨迹数据，如图3(b)所示，原始轨迹包括室内穿行轨迹和室外轨迹，室内穿行路径既有简单的直穿通道如图3(c)，又有拐弯通道如图3(d)。轨迹数据包括编号ID、时间戳、经纬度、有效卫星数量、GNSS水平精度、三轴加速度、三轴陀螺仪数据、室内外轨迹标记，数据采集频率为100 Hz。

图3 试验区域、数据和环境Fig.3 Experiment area, data and environment

2.1 试验结果

试验分析中首先对室内外检测的阈值进行设置，首先删除每段轨迹前1 min数据，以减少GNSS搜星阶段信号不稳定的影响；由于GNSS准确定位至少需要4颗或以上的有效卫星，因此有效卫星数n取阈值σn=4颗；当GNSS水平精度h大于20 m时，文献[36]表明设备处于室内状态，因此取阈值σh=20 m；文献[1]表明，青少年人群平均步行速度为1.51 m/s，老年人平均步行速度为1.25 m/s，根据智能手机采集GNSS模块的采样间隔可知，当相邻点间距离大于3 m[16]，则间接反映两点间的数据缺失，此时为室内状态，因此取阈值σl=3 m。

室内外状态检测最终试验结果发现，在260条原始轨迹数据中共检测发现121条轨迹中包含室内轨迹点，因此将室内轨迹进行分段，共获得192段室内轨迹，如图4(a)所示为室内外轨迹检测结果，红色部分为室内穿行轨迹。可以发现，检测结果基本符合目视解读结果，检测得到的室内轨迹大多位于建筑物范围内，且检测得到的室内轨迹的主要呈现杂乱无序状态。为了更进一步对本文方法的有效性进行分析，对室内外检测结果的精度进行统计分析，以单个轨迹点为统计对象，通过现场实际勘查获取原始数据中真实的室内轨迹，最终统计得到室内外检测结果的混淆矩阵见表1。根据表1计算得到本文方法检测结果的精度为81.74%、精准度为82.42%，召回率为83.95%，表明了本文方法的有效性。

表1 室内外检测结果的混淆矩阵

对室内轨迹进行行人航位推算，得到准确的室内轨迹，如图4(b)所示为室内轨迹推断结果，经行人航位推算后的室内轨迹更规整，更符合行人室内穿行通道的路径形状。对所有轨迹段进行核密度分析，通过公式计算得到带宽R=0.196，生成核密度栅格图，采用莫尔斯理论进行室内外一体化路网提取，最终结果如图4(c)所示。通过叠加卫星影像，可以发现最终提取的路网与实际影像有着较好的重合度，在室外，所构建的道路主要分布于道路中央；在建筑区域，所提取的室内道路基本刻画出室内通行路线的几何形状，较贴合真实的室内道路。

2.2 试验结果评价

众源开放街道地图(OSM)是由大众创建的开放式地理空间数据，可用于行人路网的效果评价。但由于当前现有的OSM路网数据不包含室内轨迹且室外轨迹也未及时更新，因此本文采用高精度测图背包设备实地采集得到真实的室内外路网数据，高精度测图背包集成惯导、相机、激光雷达、GNSS等传感器，测图精度为厘米级。结合OSM路网数据与构建结果叠加对比，对试验中路网构建的结果进行定性评价。使用该测图背包对深圳大学整个沧海校区的室内外路径进行实地测图，测图过程如图5所示，结合OSM现有的路网数据，得到完整精确的室内外路网数据，与构建结果进行叠加对比如图6所示。所构建的路网结果与真值路网形状一致，路网位置基本吻合。

图5 高精度测图背包图Fig.5 The results of high-precision backpacked mapping system

图6 路网真值与构建结果对比Fig.6 Comparison of road network truth value and construction results

(7)

完整度就是真实路网上能被匹配的所有长度与真实路网的总长度的比值。令l为能被匹配到的真实路网长度，L为真实路网的总长度，完整度C的计算公式为

C=l/L

(8)

完整度的取值范围为0～1，其值越接近1则表示评价的路网构建得越完整。

精确度反映的是构建路网与匹配到的真实路网的准确程度。用最短距离的平均值μ和标准差σ来表示。平均值和标准差值越小，构建路网与真实路网各支路越接近，意味着精确度越高。其计算公式如下

(9)

(10)

拓扑正确性主要通过计算F值来反映，F的取值范围为0～1，其值越接近1则表示构建路网的拓扑正确性越高

(11)

(12)

(13)

式中，sb表示在构建路网上未匹配的点数；mb表示构建路网上得到匹配的点数；eh表示在真实路网中没有匹配的点数；mh表示得到匹配的真实路网上的点数。

从真值路网任意样本点开始，随意在构建的路网上放置某个点，向外遍历最大半径来探索图的拓扑结构，计算在构建网络中随机放置的点与真实路网的样本点相匹配的点的数量。

2.3 参数分析

阈值δ决定了构建路网的简化程度，在保持其他条件相同的情况下，设置不同的阈值δ，将构建结果与真值路网进行叠加对比，如图7所示。试验结果表明，阈值δ越大，构建路网的支路越少，随着阈值δ的减小，支路增多，且逐渐出现原本不存在的错误路径。

图7 不同阈值δ下室内外一体化路网构建结果Fig.7 Indoor and outdoor integrated road network construction results under different threshold δ

使用完整度、精确度和拓扑正确性3个指标对结果进行定量评价。通过试验发现，简化阈值为0.045时构建路网的完整度与精度达到最佳平衡状态。试验结果见表2。

表2 不同阈值的路网构建评价结果

图8为不同阈值δ下，室内外一体化路网构建的完整度与精确度均值的变化趋势分析。可见在达到最佳阈值前，阈值越大，精确度越小，表明试验结果与真值路网差异越小，这是由于过小的阈值会给路网构建增加不必要的错支路；在达到最佳阈值后，阈值越大，完整度越低，这是因为阈值越大，过滤的支路会更多。

众源数据的数据量N也会对结果有所影响。比较不同数据量下的路网构建效果，将构建路网与真值路网叠加比较，如图9所示，可以发现，数据量越大，构建结果越完整。

对不同数据量的试验结果进行定量评价，结果见表3。可以发现，随着数据量的增多，构建路网的完整度越高，其精确度越来越小，即构建结果与真值间距相差越小，表明路网构建结果越精确。

图8 不同阈值δ下的试验结果评价Fig.8 Evaluation of experimental results under different threshold δ

图9 不同数据量对路网构建的影响Fig.9 Influence of different data volume on road network construction

表3 不同数据量的路网构建结果

3 结 论

构建室内外一体化行人路网，是对现有行人路网的有力补充，为缺失的室内路径提供生成方法，提高了行人路网的完整性，对行人导航的路径规划具有重要意义。本文提出的室内外一体化行人路网构建方法，主要包括室内外轨迹检测、行人航位推算、室内外一体化路网构建等步骤。试验结果表明，本文提出的室内外一体化行人路网构建方法可以准确筛选出室内轨迹，改进的PDR算法可以有效推断室内路径，最终得到的行人路网包括室外路网与室内穿行路径，成功构建出室内外一体化路网，且完整度可达82.89%，平均误差约为4.87 m，验证了所提方法的有效性。

室内外一体化是行人路网的发展趋势。本文方法在行人路网构建中加入室内穿行路径，对行人路网中室内路径的缺失做了补充。该方法目前只构建了二维行人路网，存在一定的局限性，未来可进一步研究包括人行天桥在内的三维人行路网，为行人导航提供更为丰富的行人路网数据支撑。