EN中文

Journal of Geo-information Science >

2025 , Vol. 27 >Issue 1: 151 - 166

DOI: https://doi.org/10.12082/dqxxkx.2025.240479

Outdoor Hiking Navigation Road Network Map Construction Using Crowd-Source Trajectory Data

  • TANG Jianbo , 1, 2, * ,
  • XIA Heyan 1 ,
  • PENG Ju 1 ,
  • HU Zhiyuan 1 ,
  • DING Junjie 1 ,
  • ZHANG Yuyu 1
Expand
  • 1. School of Geosciences and Info-physics, Central South University, Changsha 410083, China
  • 2. Hunan Geospatial Information Engineering and Technology Research Center, Changsha 410007, China
*TANG Jianbo, E-mail:

Received date: 2024-08-29

  Revised date: 2024-11-25

  Online published: 2025-01-23

Supported by

National Natural Science Foundation of China(42271462)

National Natural Science Foundation of China(42171441)

National Key Research and Development Program of China(2022YFB3904203)

Hunan Provincial Natural Science Foundation of China(2022JJ30703)

Fold

Abstract

[Objectives] The outdoor pedestrian navigation road network is a vital component of maps and a crucial basis for outdoor activity route planning and navigation. It plays a significant role in promoting outdoor travel development and ensuring safety management. However, existing research on road network generation mainly focuses on the construction of urban vehicular navigation networks, with relatively less emphasis on hiking navigation road networks in complex outdoor environments. Moreover, existing methods primarily emphasize the extraction of two-dimensional geometric information of roads, while the reconstruction of real three-dimensional geometric and topological structures remains underdeveloped. [Methods] To address these limitations, this study proposes a method for constructing the three-dimensional outdoor pedestrian navigation road network maps using crowdsourced trajectory data. This approach leverages a road network generation layer and an elevation extraction layer to extract the two-dimensional structure and three-dimensional elevation information of the road network. In the road network generation layer, a trajectory density stratification strategy is adopted to construct the two-dimensional vector road network. In the elevation extraction layer, elevation estimation and optimization are performed to generate an elevation grid raster map, which is then matched with the two-dimensional road network to produce the three-dimensional hiking navigation road network. [Results] To demonstrate the effectiveness of the proposed approach, experiments were conducted using 1 170 outdoor trajectories collected in 2021 from Yuelu Mountain Scenic Area in Changsha through an online outdoor website. The constructed outdoor three-dimensional hiking road network map achieved an average positional offset of 4.201 meters in two-dimensional space and an average elevation estimation error of 7.656 meters. The results demonstrate that the proposed method effectively handles outdoor trajectory data with high noise and varied trajectory density distribution differences, generating high-quality three-dimensional hiking road network maps. [Conclusions] Compared to traditional outdoor two-dimensional road networks, the three-dimensional navigation road networks constructed this study provide more comprehensive and accurate map information, facilitating improved pedestrian path planning and navigation services in complex outdoor environments.

Key words： three-dimensional pedestrian road network; crowdsourcing trajectory data; road network generation; outdoor pedestrian navigation; travel map; three-dimensional navigation services; trajectory data mining; elevation matching

Cite this article

TANG Jianbo , XIA Heyan , PENG Ju , HU Zhiyuan , DING Junjie , ZHANG Yuyu . Outdoor Hiking Navigation Road Network Map Construction Using Crowd-Source Trajectory Data[J]. Journal of Geo-information Science, 2025 , 27(1) : 151 -166 . DOI: 10.12082/dqxxkx.2025.240479

1 引言

随着全球城市化的快速发展，城市交通拥堵和环境污染问题日益突出，可持续的城市规划已成为当务之急，绿色出行和可持续发展已经成为城市规划和交通领域的核心议题[1]。步行作为一种环保、健康的出行方式，有助于减少交通污染和交通拥堵，提升居民的生活质量，促进城市的可持续发展，受到了越来越多居民的欢迎，这也使得人们对步行导航系统的需求不断增加。然而，当前社会高度依赖汽车，城市规划和街道资源多向机动车倾斜，这种导向使得目前的主流导航应用主要侧重于机动车道路网数据，而对行人路网的研究和数据标准化不足[2⇓⇓-5]。机动车道路网通常不包括步行者所需的详细步行路径，且会忽略仅适用于步行者的路径，在步行导航过程中可能导致对重要信息的忽略，难以满足当前社会绿色出行的实际需求[1]。步行导航路网的应用场景主要包括城市街道的非机动车道、室外校园、旅游景点、公园、其他野外活动区域等。其中，户外徒步旅行导航路网主要用于在野外场景活动，如登山中。为用户提供准确的导航信息与合理的路线规划，对于户外导航与旅游安全管理等具有重要意义。此外，户外环境复杂的地形起伏对徒步旅行导航提出了更高的要求，目前车行导航路网大多是从浮动车或出租车的平面轨迹数据中挖掘城市主干道路网，难以满足对三维导航路网的需求[5⇓-7]。例如，缺乏及时更新与三维信息的户外导航路网难以提供完善的户外导航服务，步行者无法获得准确的路线指引，在复杂地形和地势条件下，可能会导致其忽略地形因素选择较长的路线，浪费时间和精力，甚至可能危及其生命安全；相反，完善的户外三维徒步旅行路网导航系统能够准确反映复杂地形信息，为步行者提供考虑高差、坡度的精细化导航路径选择，可以有效引导步行者避开复杂地形，选择体力消耗较小的路线，从而提升步行者户外活动体验，保障户外活动安全。因此，户外三维徒步导航路网提取与生成日益成为户外导航的新趋势[8]。
传统路网生成方法主要借助测绘手段[9]或遥感卫星数据，前者生产成本高、生产周期长，难以满足路网及时更新需求；后者受限于高分辨率卫星或航空图像[10]，并且在户外环境中，植被遮盖问题突出，户外步行路网提取困难，路网生成的质量和准确性有待提升。随着物联网、传感器技术的发展和智能穿戴设备的流行和普及，积累了多种类型大量实时更新的众源轨迹数据[11-12]，可以反映用户或者车辆的当前位置和移动路径，为三维户外徒步旅行导航路网的构建提供了新的数据源和生成思路，能够提高三维步行导航路网生成的效率、准确性和实时性，从而满足户外环境下对高质量、精细化、实时导航数据的需求。
目前路网生成研究主要关注于城市路网地图二维空间结构的构建，众多学者基于众源轨迹数据对路网二维结构生成方法进行了广泛探索，主要可以分为： ① 基于聚类的路网生成：该类方法通常对GPS轨迹数据进行聚类，识别和提取道路网络的结构和特征[13⇓⇓⇓-17]。例如，Zhang等[13]提出根据GPS轨迹与现有车行道路信息之间的距离、方向以及轨迹与道路之间的角度进行匹配，使用聚类方法对轨迹进行划分，从而识别出道路网络的结构和特征，进而提取出道路中心线。Zhou等[17]使用了改进的DBSCAN聚类算法和逐步拟合算法，提高了车道识别的准确性； ② 基于密度的路网生成：根据轨迹点的密度分布，利用密度峰值和低谷区域提取道路骨架信息。例如，Gao[18]考虑到轨迹点会在空间中表现出各向异性，利用基于各向异性密度的噪声聚类（ADCN）算法识别道路沿线的轨迹点，结合核密度估计（KDE）生成连续表面，细化和矢量化道路中心线来构建路网； ③ 基于增量合并的路网生成：该方法通过遍历车辆的轨迹数据，将已匹配到路网的部分保持不变，未匹配到路网的部分则生成新的路径并插入到路网中[19]。Chao[20]提出迭代轨迹协同优化算法，对新更新的道路进行评估，提升了轨迹匹配和更新路网的质量，这类方法主要应用于地图匹配和地图更新方面； ④ 基于交叉点连接的路网生成：该类方法首先识别道路交叉口的出入口，再通过连接这些交叉点生成路网拓扑结构[21-22]。例如，Yuan通过检测道路交叉口和车道结构变化来划分轨迹数据，在车道结构一致的区域，使用主曲线拟合算法提取车道中心线，基于构建的车道交叉口图剪枝由车道变换行为产生的错误车道，在车道合并和分流的区域，设计了车道组拟合算法，结合高斯混合模型和车道宽度先验知识估计车道位置，推断车道级拓扑结构[22]。
上述研究主要针对城市车行路网的二维空间结构进行提取并且已经取得了显著进展[23-24]。除了城市车行路网的构建，众源轨迹数据也逐渐被应用于行人道路网的二维空间结构生成研究[1,25⇓⇓⇓⇓⇓⇓-32]。例如，Kasemsuppakorn等[25]尝试利用步行GPS轨迹数据提取大学校园内的行人路网，其首先对GPS轨迹点进行滤波，提取起点、终点和转折点等特征点，然后采用中心点划分聚类方法对特征点进行聚类，最后通过一种轨迹增量的方法提取大学校园内的行人路网。Yang等[26]则将行人轨迹分为有明确目的地和无明确目的地的步行数据。针对有明确目的地的轨迹，使用核密度估计提取骨架线得到行人路径；对无明确目的地的轨迹采用改进的连通域分析算法得到行人区域，生成武汉市和北京市内包含行人区域和路径的详细步行网络。2021年，Yang等[27]进一步提出了一种空间分层策略，以提取步行路网的倾斜度和路径类别等语义信息，增强了步行路网数据的表达能力，更准确地反映真实的步行环境。Zhou等[1]将行人的运动理解为受到道路约束的密度场，将基于核密度分析生成的密度图视为地形表面，真实道路上的轨迹点通常具有更高的密度值，可以理解为地形中的山脊，并首次借助莫尔斯理论进行检索，将提取的山脊线视为路网，可以有效提取出校园环境内行人运动的步行路网的二维信息。
上述分析可以发现，目前基于众源数据的路网生成主要侧重于城市区域内车行导航路网的构建，对行人路网的研究也多集中于城市内部或校园环境，对于复杂野外环境下的徒步旅行地图构建还相对缺乏；并且现有的路网生成研究主要构建道路的二维几何形态和拓扑连接关系，而大多忽略了地形高程等三维信息对步行活动中路径选择的关键影响，从而导致了户外环境中（例如山区、林地、自然保护区等）路网数据的不完整。缺乏准确的户外路网数据，将会影响户外徒步导航服务的准确性。此外，不同于受到城市路网和交通规则约束的车辆轨迹数据，户外步行轨迹数据受到行人主观行为和活动兴趣点分布等因素的影响，更加具有随机性和不规律性，从而导致户外步行轨迹分布更加散乱、轨迹密度分布差异更加显著。部分热点区域轨迹密度更高，而其他区域轨迹密度较低，户外轨迹数据存在明显的噪声和密度差异。这些问题会降低户外徒步导航路网生成的准确性和质量。因此，为了满足户外环境中的精确的徒步导航服务需求，本文提出了一种基于步行轨迹数据的户外徒步旅行导航步行路网构建方法。该方法首先基于轨迹密度分层策略提取户外步行路网的二维几何结构信息，在此基础上结合轨迹数据中的高程信息，估计路网的高程值，结合二维几何结构信息构建包含经纬度和高程的户外三维徒步导航路网，能够反映户外环境中的地形信息。相比于传统户外二维路网，户外三维徒步导航路网数据信息更加丰富和精确，可支持在复杂山地等户外环境中实现更好的步行路径规划和导航服务。

2 户外三维徒步旅行导航路网构建

本文旨在研究户外环境下的三维徒步旅行导航路网构建方法，通过融合户外徒步轨迹中的高程信息，在户外二维步行路网生成的基础上实现户外三维徒步旅行路网的构建。本文提出的方法主要包括路网生成层和高程提取层，具体流程如图1所示。在二维路网生成层，采取轨迹密度分层策略构建户外矢量二维路网[33]，并针对本文所选择的研究区域数据进行参数修正；在高程提取层，对轨迹覆盖的区域进行高程估计与优化，生成高程格网栅格图，再将二维路网与高程格网进行高程匹配，生成户外三维徒步旅行导航路网。
图1 户外三维步行导航路网构建方法

Fig.1 The framework of the proposed outdoor three-dimensional pedestrian navigation network construction method

2.1 轨迹数据预处理

在轨迹数据处理过程中，预处理是确保轨迹数据准确性和连贯性的重要步骤。给定包含M条轨迹的数据集T= {T1, T2, …, TM}，每条轨迹Tj (1≤ j≤ M) 由多个连续轨迹点pi = {xi, yi, zi, ti}组成，其中，xi、 yi、 zi、 ti分别表示轨迹点pi的经度、纬度、高程和采样时间。为了保证后续户外步行路网二维几何结构信息和三维高程信息提取的准确性，本文结合实际情况对轨迹数据进行如下预处理。
（1）范围裁剪：基于研究区域的边界对轨迹数据进行裁剪，剔除目标范围外的无关数据。
（2）噪声点剔除：检查并删除因设备误差或信号丢失等原因导致的异常跳跃点，如突兀的大范围位移情况，以保证轨迹数据的空间连续性。
（3）基于引力模型的轨迹点集中调整[19,34]：由于定位误差和外部干扰因素，户外步行轨迹数据点通常不会集中分布在道路中心线上，而是呈现出围绕道路中心线两侧分散分布的特点。该模型能够模拟轨迹点之间的相互作用，有效调整轨迹点的空间分布，使原本分散的轨迹数据更加集中、连贯，从而更好地呈现出道路的特征。

2.2 户外徒步旅行路网二维几何结构信息提取

2.2.1 核密度图像生成

在上述预处理的基础上，使用核密度估计方法对轨迹数据进行映射，生成轨迹数据的密度栅格图像。相较于原始的分散户外步行轨迹数据，经过引力模型调整后的轨迹数据更能够反映出实际的道路结构，所得到的轨迹密度栅格图像也会更为可靠和准确。
其中，核密度估计（Kernel Density Estimation，KDE）是一种用于估计点数据概率分布的非参数统计方法[35-36]，其基本思想是将每一个数据点视为一个核函数的中心，然后将这些核函数叠加在一起来估计整个数据集的概率密度分布，如式（1）所示。
f n ( x ) = 1 n h ∑ i - 1 n k x - x i h
式中： n为数据点的个数； h为带宽，通常大于0； (x-xi)表示估计点x到样本点xi之间的距离； k(·)表示核函数，本文选取高斯核函数（又称正态核函数或径向基函数），其数学表达式为：
k ( x ,   x ' ) = e - ( x - x ' ) / 2 σ 2
式中： x和x'表示2个不同的样本点； σ为带宽参数，决定了核函数的局部作用范围。σ越大，核函数的影响范围越大；反之，当σ较小时，高斯核函数的影响范围则更加局部，主要关注于邻近的样本。因此，带宽σ的选择对于核密度估计的效果至关重要。
在核密度估计过程中，将研究区域划分为给定大小的规则格网，统计每个格网中包含的轨迹点数量，作为该格网的密度。根据式（1）和式（2）对每个格网进行核密度估计，生成核密度图像，并将核密度图像转为灰度图像。在本文中，格网大小设置为1 m×1 m，以提供足够精细的分辨率来捕捉道路的详细结构，根据GPS轨迹数据的平均定位误差与户外道路的平均宽度设置高斯核函数的带宽参数σ为8.5 m[33]。

2.2.2 基于多阈值细化的道路二维几何结构信息提取

基于核密度估计生成的KDE图像能够反映轨迹点的空间分布密度，呈现出多级灰度特征。其中，深色区域代表轨迹点密集，覆盖率较高，可能对应于主要道路；而浅色区域则表明轨迹密度较低，轨迹分布相对稀疏，可能对应于次要道路或者噪声轨迹的重叠区域。如何区分主次道路并减少噪声干扰，精准提取道路的中心骨架线是一项复杂的任务。
目前，骨架线细化被认为是从KDE图像中提取道路中心线的最常用方法之一[37]。其关键在于选择合理的二值化阈值对图像进行分割。较高的阈值可能导致低密度轨迹分布的道路被过滤，而较低的阈值则可能引入过多噪声，使得道路骨架线提取结果存在大量毛刺和杂散。为解决该问题，本文采用了Biagioni等[33]提出的多阈值骨架线细化算法从KDE图像中提取道路骨架线。该算法从高阈值到低阈值逐级迭代提取道路骨架线，在每次迭代中仅添加新发现的道路而不改变已提取的道路。这种渐进式的方法能够同时保留高密度和低密度区域的道路信息。然而，连续多阈值迭代方式可能会带来大量的计算开销。该研究表明，将迭代阈值限制为2的幂指数次（如256、128、64，…， 次）可以产生与连续迭代方式基本相同的道路骨架线提取效果，执行时间也会呈指数级改善[33]。
因此，为了降低计算复杂性，将密度阈值设置为2的幂指数次，并进行迭代提取道路骨架线[33]。虽然该方法的迭代间隔较大，但由于轨迹密度分布的渐变性，每次迭代都会在不同灰度级别下捕捉到不同层次的道路结构，并不会导致道路的突然丢失。并且，该方法采用了增量式提取方式，每次迭代中只提取高于当前阈值的新道路信息，而保留之前已提取的道路不变，提取的道路骨架线会在不同密度区域之间逐步累加，不仅可以减少不必要的计算，同时也确保了道路结构的完整性。图2展示了对同一数据集进行处理，采用2种迭代方式得到的道路中心线提取结果与原始KDE图像的对比。可以发现，基于连续迭代的方式能够提取出具有不同密度分布区域的道路骨架线，但是其存在较多的毛刺。相比之下，基于2的幂指数次迭代的方式在提取出与连续迭代方式基本相同的道路骨架线结果的情况下，明显减少了道路毛刺的产生。进一步，采用Combustion算法将道路骨架图像转化为矢量式的道路网络数据[38]。同时，结合Douglas-Peucker算法[39]对提取的道路边进行平滑与简化处理，得到包含节点和边数据的初始道路网络结构。
图2 道路骨架线提取结果对比

Fig. 2 Comparison of road skeleton extraction results

2.2.3 道路结构优化

基于密度的道路提取算法通常面临着2个问题：一是容易产生大量假边；二是对道路交叉口的拟合效果差。在骨架线细化提取的过程中，为保留轨迹分布较稀疏区域的道路，不可避免地同时会保留部分密度较高的噪声轨迹。因此，本文采用轨迹数据与路网数据多次匹配[33,40]的策略对路网结构进行优化。具体来说，首先采用地图匹配算法将原始轨迹与初始路网结构进行轨迹点的地图匹配[41]，删除少于2次被轨迹点匹配到的节点和边，完成假边和伪节点的修剪[33]；重复该步骤，将轨迹点数据与修剪后的路网数据再次进行地图匹配，处理残余的碎屑边，去除与主要道路网络不相连的悬浮边和节点，实现路网结构的进一步拓扑优化。图3展示了公开的芝加哥轨迹数据集[42]中部分区域在路网修剪过程中的演变结果。通过对比修剪前后的道路结构可以发现，经过多次迭代匹配修剪后的路网质量得到显著提升：假边明显减少，路网整体性更强，主要道路结构更加清晰。
图3 路网修剪前后对比

Fig. 3 Comparison of road network before and after pruning

拓扑优化后的路网在整体性方面表现良好，但在道路交叉口处仍可能存在问题，这源于KDE算法无法很好地处理交叉口结构。因此，本文在路网修剪优化的基础上对交叉口进行路径细化。具体来说，将修剪后的路网数据再次与原始轨迹数据进行匹配，获得与路网高度吻合的轨迹点，对轨迹点数据进行小尺度的密度聚类，根据聚类结果以及轨迹点的转向信息确定道路交叉口的出入口位置，同时通过分析轨迹数据的转向特征确定不同方向道路之间的拓扑连接关系，以实现路网细节部分的优化，改善道路交叉口的表现效果，最终生成具有良好道路拓扑结构的二维路网，如图4所示。
图4 道路交叉口细化前后对比

Fig. 4 Comparison of road intersection before and after refinement

2.3 户外三维徒步旅行导航路网构建

在道路二维结构信息提取的基础上，本文进一步利用户外徒步轨迹数据中包含的高程信息，丰富道路的三维属性，构建面向户外环境的三维徒步旅行导航路网。该过程包括2个关键步骤：高程估计与高程匹配。
在高程估计阶段，首先统计核密度估计过程中获得的格网内轨迹点的高程信息。考虑到定位系统接收器的误差，相同经纬度位置的轨迹点高程值可能存在一定波动，因此需要推算每个轨迹点的真实高程，以尽量减少系统误差的影响。为此，首先通过先验知识或检验模板识别并剔除明显异常的高程值，并采用卡尔曼滤波对轨迹数据的高程值进行修正，确保数据的可靠性。其次，在高密度区域，采用格网内轨迹点的高程中值作为该格网点的高程估计值，以降低个别差异值的影响和噪声干扰。在估算高程值时，考虑到同一格网可能对应多个高程值的情况，即同一二维位置上可能存在多条高度不同的道路，如多层建筑、立交桥、隧道等场景。户外环境中也存在类似情况，如图5所示的山地地形。同一平面位置上可能分布着不同海拔高度的道路，既有底层公路，也有凿穿山体的高架路或隧道。为了全面反映复杂地形对高程的影响，本文在高程估计过程中引入了高程聚类分析。具体而言，对同一格网内轨迹点高程数据进行聚类，根据不同区域的地形复杂程度动态调整聚类的邻域半径参数，识别出不同的高程簇。其中，每个簇代表可能存在的一条道路的高度水平。在对高程簇进行判别时，加入轨迹点的局部空间密度、坡度变化等要素来辅助高程值聚类的过程，细化不同高度道路分布的判别，更好的区分邻近平面内不同高度的 道路。
图5 邻近平面位置出现高程值不同的多条道路的情况

Fig. 5 The case of multiple roads with different elevation values at adjacent plane locations

对于低密度区域，轨迹点数量较少，难以直接确定高程估计值，在这种情况下实施搜索策略。查找距离该格网最近的已知高程估计值，为了避免邻近格网的高程估计值引入过多误差，设定一个动态误差阈值，若搜索到的数值与该格网中落入轨迹点的高程数据相差不超过该特定阈值，那么将落入点的平均高程值设为该格网点的高程估计值，否则，将采用搜索到的值作为该格网点的高程估计值。匹配完成后，检查高密度区域与低密度区域之间的过渡是否平滑，若发现较大的高程跳跃，进一步调整阈值重新估计低密度区域的高程值。此外，由于行人使用智能手机作为定位系统接收器，手机与地面之间存在一定距离，因此，本文将格网点的高程估计值减去1 m确定为修正后的最终高程估计值。
在高程匹配阶段，将生成的户外二维步行路网所在的格网信息与相应的高程估计值进行关联，实现高程值与户外二维步行路网节点的匹配，从而构建包含经纬度和高程属性的三维路网。这一过程丰富了户外步行路网的三维空间信息，实现了从平面到三维的转化，能够提供更加全面的三维空间视角。在三维视角的支撑下，可以有效避免二维路径规划中仅基于平面距离的局限性，在考虑横向距离的同时考虑高度差异的影响，动态权衡距离和高程差，在复杂地形中找出更具可行性和效率的路线，根据实际地形选择最合适的路径。通过这种方式，三维路网的构建将为户外徒步旅行导航提供更加精准和可靠的支持，提升整体路径规划的有效性。

3 试验与分析

3.1 模拟实验与分析

为验证本文选取的基于密度分层的二维路网生成算法对存在噪声和显著密度差异的户外步行轨迹数据的适用性，首先将本文方法与以下4种方法在柏林和芝加哥2个公开轨迹数据集上的路网二维结构提取效果分别进行了对比实验[42]。这3种方法分别为：① Karagiorgou等[43]提出的根据参数探测交叉口提取道路的方法：该方法通过检测运动模式的变化来识别交叉口，基于交叉口节点进行聚类构建路网；② Davics等[44]提出的路网生成算法：将轨迹点栅格化后运用图像处理技术来提取道路中心线；③ Ahmed等[45]提出的增量化提取道路的方法：该方法使用轨迹匹配算法将轨迹数据与现有的道路网络进行匹配，识别其中的节点和连接，通过轨迹流跟踪生成道路网络；④ Lyu等[21]提出的MAMC方法：该方法通过聚类转弯点进行节点推断，然后聚合轨迹段来构建道路网络图，同时考虑采样过程的特点和轨迹几何特征。对比方法相关实验参数根据相应参考论文进行设置。柏林和芝加哥轨迹数据集如图6所示。
图6 柏林和芝加哥轨迹数据集

Fig. 6 Visualization of the Berlin and Chicago trajectory datasets

本文根据Biagioni等[33]提出的评价方法选取F1分数评价指标对二维路网提取结果进行量化分析，结果如图7所示。实验结果表明，在处理大规模、复杂的柏林轨迹数据集时，基于密度分层的方法（即本文方法）展现出较强的适应性，其提取效果优于其他对比方法；而在处理数据量较小、噪声水平较低的芝加哥轨迹数据集时，Ahmed等[45]提出的方法对路网二维结构的提取效果更佳（图8）。轨迹数据的质量直接影响了MAMC算法地图构建结果的好坏，在噪声较大的情况下，受异常值的影响，该算法性能下降而基于密度分层的方法表现更好。这一发现揭示了不同方法在处理具有不同特性数据集时的适应性差异，也凸显了在实际应用中需要根据数据集特性选择适当方法的重要性。基于此，本文进一步将2种情况下表现最好的Ahmed方法与基于密度分层的方法分别应用于后续研究区域内步行路网二维结构的提取与分析。
图7 柏林和芝加哥路网提取F1分数评价结果

Fig. 7 The evaluation of the road network extraction results on the Berlin and Chicago datasets using F1-score

图8 本文方法与对比方法在芝加哥数据集上的路网二维结构提取结果

Fig. 8 The two-dimensional structure of the extracted road network on the Chicago trajectory dataset using the proposed method and three baselines

3.2 实际应用与分析

3.2.1 研究区域概况与数据来源

本文选取岳麓山风景区为研究区域，该区域位于湖南省中部、湘江西岸，地形多变，高程起伏明显，地貌特征丰富，以其秀美的自然风光和悠久的历史文化而闻名，融合了自然景观和人文历史，是一个具有浓厚文化底蕴的旅游胜地，吸引了大量的游客，留下了丰富的步行轨迹记录。本文所使用的轨迹数据集从户外轨迹共享网站六只脚（http://foooooot.com）下载获得[46]。六只脚是是国内著名的户外网站，记录了百万条以上的户外活动轨迹数据。用户可以通过智能手机的软件客户端记录和上传数据，同时，该平台提供数据下载服务，下载的原始轨迹为WGS84坐标系下的轨迹数据，每个轨迹点包含经度、纬度和高程值等信息。实验研究区域和获取的1 170条用户共享的户外轨迹数据如图9所示。
图9 研究区域与实验轨迹数据

Fig. 9 Study area and the experimental data

3.2.2 户外三维徒步旅行路网生成结果与对比分析

将本文方法（即密度分层的方法）和Ahmed的方法应用于岳麓山研究区域内的户外步行轨迹数据，提取的步行路网二维结构如图10所示。虽然在前文3.1节中芝加哥数据集（数据量小、噪声水平低）的对比实验中，Ahmed的方法表现出较好的路网二维结构提取效果，但在处理岳麓山研究区域内包含大量噪声和不规则的户外步行轨迹数据中，Ahmed的方法抗干扰能力不足，导致其路网二维结构提取效果不佳。相比之下，本文方法在面对复杂多样的岳麓山户外轨迹数据集时展现出显著优势（图10（b）），其能够有效处理高噪声数据，适应轨迹密度分布不均匀的情况，可以更好地提取不同层级的道路，从而实现对研究区域内步行路网二维结构的有效提取。
图10 岳麓山二维步行路网提取结果对比

Fig. 10 Comparison of two-dimensional pedestrian navigation network extraction results in Yuelu Mountain

为了进一步验证所构建路网的准确性，分别从二维空间定位和三维高程信息两个方面对其进行定量评价。由于缺乏该研究区域的真实二维路网数据以及对应的真实三维信息，本文选取所构建路网上的20个具有明显特征的位置点，如拐点或路段端点，如图11(b)所示，并采用手持定位设备实地采集这些特征点对应的地理坐标信息作为基准数据来进行定量评价。首先，对本文方法构建的户外步行路网的二维空间位置进行定量评价，通过计算特征点与实际位置的偏移距离，得到平均偏移距离为4.201 m，这一结果表明了该路网结果在二维空间定位上的较高准确性。随后，采用相同的评价方法对Ahmed方法生成的路网进行二维空间定位精度分析，在Ahmed结果路网中选取与在本文结果路网中选取的特征点位置对应的特征点，即位于相同或相近位置的拐点、路段端点等，如图11(a)所示，计算得到其平均偏移距离为11.318 m。该结果进一步表明，本文方法在二维空间定位准确性上优于Ahmed方法。鉴于Ahmed方法生成的路网中不包含三维高程信息，对三维高程信息的准确性评估仅针对本文方法构建的路网结果。具体来说，我们将选取的特征点的高程数据与数字高程模型（DEM）数据进行了对比，对比结果显示，平均高程误差为7.656 m，考虑到轨迹数据本身可能存在的误差和高程估计中不可避免的误差来源，这一误差水平在实际应用中可以被认为是可接受的。
图11 分别选取的20个特征点

Fig. 11 The selected 20 feature points

基于提取的道路二维几何结构信息，进一步引入轨迹高程信息构建户外三维徒步旅行路网，如图12所示。相比二维导航路网，三维路网在表现地形起伏、道路交叉等方面更为直观和准确，不仅能展示道路的平面布局，还能反映道路在垂直方向上的变化，适应不同地形条件下的步行需求，为步行者提供更加全面的导航信息。通过叠加高程信息，进一步观察和分析本文提取的三维户外徒步旅行路网与岳麓山景区实际情况的契合程度。结果显示，两者之间重合度较高，不但道路的位置和形状与真实情况大致相符，而且拓扑关系也在一定程度上得到了准确呈现，这验证了本文所提方法的有效性。
图12 不同观察视角下的三维户外步行导航路网构建结果

Fig. 12 The constructed outdoor three-dimensional pedestrian navigation network

与此同时，本文结果还能够检测和揭示现有商业地图上不完整的信息，发现尚未被更新的允许行人通行的道路，如图13所示。因此，本文方法提取结果也可以为现有地图数据的更新提供支撑。
图13 提取的商业地图中不存在的道路

Fig. 13 The extracted roads that are absent in commercial maps

进一步，对提取的研究区域内的三维徒步旅行路网进行坡度、坡向的提取，结果如图14所示。根据三维徒步旅行导航路网生成的坡度、坡向图揭示了岳麓山山体的起伏和坡度变化，与实际情况相符，这也证明了本文方法的有效性和真实性。
图14 坡度坡向图

Fig. 14 The slope and aspect maps

对于给定的起始点（即P和Q），分别基于本文提取的三维步行路网与二维步行路网进行最短路径规划，路径规划结果如图15所示。可以发现，缺乏高程信息的二维步行路网与三维步行路网规划的最短路径存在差异，包含高程信息的三维路网能够提供更真实、精准的路径规划，它能更准确地反映实际地理环境，避免了二维路网可能存在的不真实或不符合实际的路径规划结果。此外，三维路网还能提供更全面的信息，包括地形、地貌等，有助于用户更好地理解周围环境，提高导航的可靠性和用户体验。在户外环境中，考虑高程信息的路径规划还能增强导航的安全性，帮助用户避开陡峭或危险的地形，选择更安全、更易行的路径，减少意外风险。因此，三维徒步旅行导航路网在路径规划中的应用具有更大的优势和必要性，可以为户外导航提供更加可靠和有效的解决方案。
图15 基于二维路网和三维路网的路径规划结果对比

Fig. 15 The comparison of route planning results based on the constructed two-dimensional road network and three-dimensional road network

4 结论与展望

本文针对当前研究对复杂户外环境下的三维徒步旅行路网关注度不足、路网生成算法难以适应户外步行轨迹数据空间密度分布不均、噪声水平高等特征的问题，提出了一种融合众源轨迹数据的户外三维徒步旅行导航路网地图构建方法。该方法利用户外众源轨迹数据，通过结合轨迹密度分层策略和高程估计与优化技术，实现对户外徒步旅行路网二维几何形态和三维高程信息的有效重建。在芝加哥和柏林公开轨迹数据集上的模拟实验表明，本文方法能够有效应对轨迹数据规模较大、分布复杂且噪声显著等多重挑战，相比对比方法F1分数综合更高，表现出更强的鲁棒性。在岳麓山户外活动轨迹数据集上的实际应用分析表明： ① 在户外二维空间中，本文方法构建的路网水平定位平均偏移距离为4.201 m，显著优于根据模拟实验选取的对比方法的11.318 m，表明本文方法在处理噪声较大且密度分布差异大的户外步行轨迹数据时具有更强的适应性，在复杂户外环境下表现出较好的二维定位精度； ② 高程估计结果与DEM数据对比的平均误差为7.656 m，反映了本文方法在三维高程信息重建方面的准确性较高，匹配的高程信息与实际情况基本相符，能较好地体现地形信息； ③ 本文结果能够发现商业地图中缺失的行人道路，为步行者提供更加全面准确的导航服务。
综上所述，本文方法能够有效处理复杂的户外步行轨迹数据，并结合高程信息对路网信息进行丰富，突破了传统路网生成算法仅针对路网二维空间结构的局限性。该方法不仅能够保持较好的路网二维定位精度，还能提供三维高程信息，并在实际应用中展现出较强的适应性，为户外徒步者提供更加全面的导航支持。然而，由于缺乏研究区域真实的二维路网数据，本文通过选取特征点来进行定量评价，但特征点的质量、分布以及与实际地形的对应关系都会直接影响评价结果的准确性，不同特征点的选择可能导致评价结果存在差异，未来的研究可以进一步优化特征点的选择策略以提高评价的准确性和一致性。此外，尽管本文方法在户外三维徒步旅行导航路网的构建上取得了较好的效果，但轨迹数据的质量、噪声水平以及高程估计过程中使用的模型和算法也可能影响结果的精度，尤其在高程信息的提取和优化方面，仍有进一步改进空间，高程信息的精度有待进一步提高。未来的研究可以考虑使用高精度的数字高程模型数据对提取的高程信息进行校正，以期为户外步行路网提供更加贴近真实地形、更加精确的三维数据支持，为复杂户外场景下的精细化导航服务提供更好的数据基础。
■ 本文图文责任编辑： 蒋树芳 黄光玉

利益冲突：Conflicts of Interest 所有作者声明不存在利益冲突。

All authors disclose no relevant conflicts of interest.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Zhou B D, Zheng T J, Huang J C, et al. A pedestrian network construction system based on crowdsourced walking trajectories[J]. IEEE Internet of Things Journal, 2021, 8(9):7203-7213. DOI:10.1109/JIOT.2020.3038445

[2]
Haustein S, Nielsen T A S. European mobility cultures: A survey-based cluster analysis across 28 European countries[J]. Journal of Transport Geography, 2016, 54:173-180. DOI:10.1016/j.jtrangeo.2016.05.014

[3]
Saeidizand P, Fransen K, Boussauw K. Revisiting car dependency: A worldwide analysis of car travel in global metropolitan areas[J]. Cities, 2022,120:103467. DOI:10.1016/j.cities.2021.103467

[4]
Szell M. Crowdsourced quantification and visualization of urban mobility space inequality[J]. Urban Planning, 2018, 3(1):1-20. DOI:10.17645/up.v3i1.1209

[5]
Rhoads D, Rames C, Solé-Ribalta A, et al. Sidewalk networks: Review and outlook[J]. Computers, Environment and Urban Systems, 2023,106:102031. DOI:10.1016/j.compenvurbsys.2023.102031

[6]
Yang X, Tang L L, Niu L, et al. Generating lane-based intersection maps from crowdsourcing big trace data[J]. Transportation Research Part C: Emerging Technologies, 2018, 89:168-187. DOI:10.1016/j.trc.2018.02.007

[7]
陆川伟, 孙群, 陈冰, 等. 车辆轨迹数据的道路学习提取法[J]. 测绘学报, 2020, 49(6):692-702.

[ Lu C W, Sun Q, Chen B, et al. Road learning extraction method based on vehicle trajectory data[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6):692-702. ] DOI:10.11947/j.AGCS.2020.20190305

[8]
Holone H, Misund G. People helping computers helping people: Navigation for people with mobility problems by sharing accessibility annotations[C]// International Conference on Computers for Handicapped Persons. Berlin, Heidelberg: Springer, 2008:1093-1100. DOI:10.1007/978-3-540-70540-6_164

[9]
Karimi H A, Kasemsuppakorn P. Pedestrian network map generation approaches and recommendation[J]. International Journal of Geographical Information Science, 2013, 27(5):947-962. DOI:10.1080/13658816.2012.730148

[10]
Kuntzsch C, Sester M, Brenner C. Generative models for road network reconstruction[J]. International Journal of Geographical Information Science, 2016, 30(5):1012-1039. DOI:10.1080/13658816.2015.1092151

[11]
Heipke C. Crowdsourcing geospatial data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2010, 65(6):550-557. DOI:10.1016/j.isprsjprs.2010.06.005

[12]
范红超, 孔格菲, 杨岸然, 等. 众源地理信息研究现状与展望[J]. 测绘学报, 2022, 51(7):1653-1668.

[ Fan H C, Kong G F, Yang A R, et al. Current status and prospects of research for volunteered geographic information[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(7):1653-1668. ] DOI:10.11947/j.AGCS.2022.20220192

[13]
Zhang L J, Thiemann F, Sester M. Integration of GPS traces with road map[C]// Proceedings of the Third International Workshop on Computational Transportation Science. ACM, 2010:17-22. DOI:10.1145/1899441.1899447

[14]
Zheng R J, Liu Q, Rao W X, et al. Topic model-based road network inference from massive trajectories[C]//2017 18th IEEE International Conference on Mobile Data Management (MDM). IEEE, 2017:246-255. DOI:10.1109/MDM.2017.41

[15]
Buchin K, Buchin M, Duran D, et al. Clustering trajectories for map construction[C]// Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2017:1-10. DOI:10.1145/3139958.3139964

[16]
刘敬一, 彭举, 唐建波, 等. 融合多特征的轨迹数据自适应聚类方法[J]. 地球信息科学学报, 2023, 25(7):1363-1377.

[ Liu J Y, Peng J, Tang J B, et al. An automatic trajectory clustering method integrating multiple features[J]. Journal of Geo-information Science, 2023, 25(7):1363-1377. ] DOI:10.12082/dqxxkx.2023.230066

[17]
Zhou J, Guo Y, Bian Y A, et al. Lane information extraction for high definition maps using crowdsourced data[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(7):7780-7790. DOI:10.1109/TITS.2022.3222504

[18]
Gao S, Li M X, Rao J M, et al. Automatic urban road network extraction from massive GPS trajectories of taxis[M]// Handbook of Big Geospatial Data. Cham: Springer, 2021:261-283. DOI:10.1007/978-3-030-55462-0_11

[19]
Cao L L, Krumm J. From GPS traces to a routable road map[C]// Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2009:3-12. DOI:10.1145/1653771.1653776

[20]
Chao P F, Hua W, Zhou X F. Trajectories know where map is wrong: An iterative framework for map-trajectory co-optimisation[J]. World Wide Web, 2020, 23(1):47-73. DOI:10.1007/s11280-019-00721-w

[21]
Lyu H Y, Pfoser D, Sheng Y H. Movement-aware map construction[J]. International Journal of Geographical Information Science, 2021, 35(6):1065-1093. DOI:10.1080/13658816.2020.1863409

[22]
Yuan M Y, Yue P, Yang C, et al. Generating lane-level road networks from high-precision trajectory data with lane-changing behavior analysis[J]. International Journal of Geographical Information Science, 2024, 38(2):243-273. DOI:10.1080/13658816.2023.2279977

[23]
陈欣, 向隆刚, 焦凤伟. 基于众源轨迹的OSM路网转向信息增强[J]. 地球信息科学学报, 2023, 25(10):1954-1967.

[ Chen X, Xiang L G, Jiao F W. Turning information enhancement of OpenStreetMap Road network based on crowdsourcing trajectory data[J]. Journal of Geo-information Science, 2023, 25(10):1954-1967. ] DOI:10.12082/dqxxkx.2023.230070

[24]
李思宇, 向隆刚, 张彩丽, 等. 基于低频出租车轨迹的城市路网交叉口提取研究[J]. 地球信息科学学报, 2019, 21(12):1845-1854.

[ Li S Y, Xiang L G, Zhang C L, et al. Extraction of urban road network intersections based on low-frequency taxi trajectory data[J]. Journal of Geo-information Science, 2019, 21(12):1845-1854. ] DOI:10.12082/dqxxkx.2019.190187

[25]
Kasemsuppakorn P, Karimi H A. A pedestrian network construction algorithm based on multiple GPS traces[J]. Transportation Research Part C: Emerging Technologies, 2013, 26:285-300. DOI:10.1016/j.trc.2012.09.007

[26]
Yang X, Tang L L, Ren C, et al. Pedestrian network generation based on crowdsourced tracking data[J]. International Journal of Geographical Information Science, 2020, 34(5):1051-1074. DOI:10.1080/13658816.2019.1702197

[27]
Yang X, Stewart K, Fang M Y, et al. Attributing pedestrian networks with semantic information based on multi-source spatial data[J]. International Journal of Geographical Information Science, 2022, 36(1):31-54. DOI:10.1080/13658816.2021.1902530

[28]
郑恬静, 黄金彩, 周宝定, 等. 基于众源轨迹数据的行人路网提取[J]. 测绘通报, 2021,3:69-74.

[ Zheng T J, Huang J C, Zhou B D, et al. Pedestrian road network extraction based on crowdsourcing trajectory data[J]. Bulletin of Surveying and Mapping, 2021, 3(1):69-74. ] DOI:10.13474/j.cnki.11-2246.2021.0080

[29]
Li C, Chai W N, Yang X H, et al. Crowdsourcing-based indoor semantic map construction and localization using graph optimization[J]. Sensors, 2022, 22(16):6263. DOI:10.3390/s22166263

[30]
Zhou B D, Ma W, Li Q Q, et al. Crowdsourcing-based indoor mapping using smartphones: A survey[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2021, 177:131-146. DOI:10.1016/j.isprsjprs.2021.05.006

[31]
Li W T, Xu X J, Wang Y C, et al. A survey of crowdsourcing-based indoor map learning methods using smartphones[J]. Results in Control and Optimization, 2023,10:100186. DOI:10.1016/j.rico.2022.100186

[32]
周宝定, 张文香, 黄金彩, 等. 基于众源数据的室内外一体化行人路网构建[J]. 测绘学报, 2022, 51(5):718-728.

[ Zhou B D, Zhang W X, Huang J C, et al. Indoor and outdoor integrated pedestrian network construction based on crowdsourced data[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(5):718-728. ] DOI:10.11947/j.AGCS.2022.20210276

[33]
Biagioni J, Eriksson J. Map inference in the face of noise and disparity[C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. ACM, 2012:79-88. DOI:10.1145/2424321.2424333

[34]
Rappos E, Robert S, Cudré-Mauroux P. A force-directed approach for offline GPS trajectory map matching[C]// Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2018:319-328. DOI:10.1145/3274895.3274919

[35]
淦文燕, 李德毅. 基于核密度估计的层次聚类算法[J]. 系统仿真学报, 2004, 16(2):302-305,309.

[ Gan W Y, Li D Y. Hierarchical clustering based on kernel density estimation[J]. Journal of System Simulation, 2004, 16(2):302-305,309. ] DOI:10.3969/j.issn.1004-731X.2004.02.031

[36]
刘锐, 胡伟平, 王红亮, 等. 基于核密度估计的广佛都市区路网演变分析[J]. 地理科学, 2011, 31(1):81-86.

[ Liu R, Hu W P, Wang H L, et al. The road network evolution of Guangzhou-Foshan metropolitan area based on kernel density estimation[J]. Scientia Geographica Sinica, 2011, 31(1):81-86. ] DOI:10.13249/j.cnki.sgs.2011.01.008

[37]
Chen C, Cheng Y H. Roads digital map generation with multi-track GPS data[C]// 2008 International Workshop on Education Technology and Training & 2008 International Workshop on Geoscience and Remote Sensing. IEEE, 2008:508-511. DOI:10.1109/ETTandGRS.2008.70

[38]
Shi W H, Shen S H, Liu Y C. Automatic generation of road network map from massive GPS, vehicle trajectories[C]// 2009 12th International IEEE Conference on Intelligent Transportation Systems. IEEE, 2009:1-6. DOI:10.1109/ITSC.2009.5309871

[39]
Douglas D H, Peucker T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: the International Journal for Geographic Information and Geovisualization, 1973,10:112-122. DOI:10.3138/FM57-6770-U75U-7727

[40]
王少槐. 基于GPS轨迹的路网生成与地图匹配算法研究[D]. 广州: 华南理工大学, 2019.

[ Wang S H. Research on road network generation and map matching algorithm based on GPS trajectory[D]. Guangzhou: South China University of Technology, 2019. ]

[41]
高文超, 李国良, 塔娜. 路网匹配算法综述[J]. 软件学报, 2018, 29(2):225-250.

[ Gao W C, Li G L, Ta N. Survey of map matching algorithms[J]. Journal of Software, 2018, 29(2):225-250. ] DOI:10.13328/j.cnki.jos.005424

[42]
Ahmed M, Karagiorgou S, Pfoser D, et al. A comparison and evaluation of map construction algorithms using vehicle tracking data[J]. GeoInformatica, 2015, 19(3):601-632. DOI:10.1007/s10707-014-0222-6

[43]
Karagiorgou S, Pfoser D. On vehicle tracking data-based road network generation[C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. ACM, 2012:89-98. DOI: 10.1145/2424321.2424334

[44]
Davies J J, Beresford A R, Hopper A. Scalable, distributed, real-time map generation[J]. IEEE Pervasive Computing, 2006, 5(4):47-54. DOI:10.1109/MPRV.2006.83

[45]
Ahmed M, Wenk C. Constructing street networks from GPS trajectories[C]// European Symposium on Algorithms. Berlin, Heidelberg: Springer, 2012:60-71. DOI:10.1007/978-3-642-33090-2_7

[46]
csu-mapping. Yuelu trajectory data[DS/OL].[2021-11-30].

Options
Outlines

/

〈 〉