基于自适应轨迹聚类的城市路网提取与更新方法.pdf

2097-3012(2023)02-0209-09 Journal of Spatio-temporal Information 时空信息学报 收稿日期:2022-09-28；修订日期:2023-06-06 基金项目:国家自然科学基金项目（42271462，42171441）；湖南省自然科学基金项目（2021JJ40727，2022JJ30703，2020JJ4749）；中南大学中央高校基本科研业务费专项资金资助项目（2022zzts105）；湖南省研究生科研创新项目（CX20220193）作者简介:彭程，研究方向为多源数据分析与处理。E-mail： 通信作者:唐建波，研究方向为时空轨迹大数据挖掘分析等。E-mail： 基于自适应轨迹聚类的城市路网提取与更新方法 彭程1，唐建波1,2，彭举1，梅小明1，陈雪莹1，姚志鹏1 1.中南大学 地球科学与信息物理学院，长沙 410083；2.湖南省地理空间信息工程技术研究中心，长沙 410083 摘 要：由于城市路网更新频繁及传统地图更新方法的局限性，很多城市路网地图数据无法及时更新。基于移动轨迹数据的路网地图更新是实现城市路网地图快速、高效更新的有效途径。虽然目前基于移动轨迹数据发展了一些基于栅格化的方法、基于聚类的方法和增量化的方法来提取与更新城市路网，但这些方法对于参数依赖性较强，且难以准确提取较为复杂的道路形状。因此，本文结合移动轨迹数据的特点及道路网的结构特征，提出了一种基于移动轨迹匹配的城市路网地图动态更新方法。首先，通过轨迹点的位置和方向属性进行轨迹点路段匹配；然后，对未匹配的轨迹点采用顾及方向约束的空间自适应聚类算法进行聚类，并对每个聚类进行最优曲线拟合，获得新增道路；最后，以城市浮动车轨迹数据为例进行实验与对比分析。实验结果表明，与现有方法相比，本文方法需要的参数较少，且能够处理复杂形状道路的提取，具有较高的运行效率。关键词：轨迹数据；地图匹配；自适应聚类；城市路网；路网更新 引用格式：彭程,唐建波,彭举,梅小明,陈雪莹,姚志鹏.2023.基于自适应轨迹聚类的城市路网提取与更新方法.时空信息学报,30(2):209-217 Peng C,Tang J B,Peng J,Mei X M,Chen X Y,Yao Z P.2023.Extraction and updating method for urban road network based on adaptive trajectory clustering.Journal of Spatio-temporal Information,30(2):209-217,doi:10.20117/j.jsti.202302007 1 引 言 城市路网信息是重要的基础地理信息数据，也是出行导航、物流配送、设施规划等基于位置服务的数据基石。在大数据时代下，当前泛在、海量的轨迹数据，如浮动车、公交车和用户手机等设备记录的GPS出行轨迹，蕴含了丰富的道路交通信息，能够实时地感知交通道路的物理变化（Lyu 等，2021）。移动轨迹数据以其低成本、高现势性的突出优点已经成为目前道路信息获取和检测道路变化的一个重要数据源（Tang 等，2019）。城市中人们的出行活动一般是沿着交通道路进行的，因此记录人们出行活动的移动轨迹数据，如浮动车 GPS 轨迹数据、手机实时定位数据等，能够反映实时的城市路网结构信息（杨伟和艾廷华，2017）。当城市 道路发生变化或更新时，人们的出行轨迹会“偏离”已有路网，从这些与已有路网不匹配的大量轨迹中可以挖掘出城市路网结构的变化信息，进而指导城市路网变化的动态更新（蒋新华等，2013）。当前，基于移动轨迹数据的路网更新方法主要采取两类研究策略：先依据轨迹数据进行全部路网信息的重构，进而依据重构的路网与已有路网进行对比来探测新增道路；通过移动轨迹与已有路网匹配，探测未匹配的轨迹，进而依据未匹配的轨迹进行道路信息的部分重构，发现新增道路（吴涛等，2017）。第一类方法侧重于从海量轨迹数据中提取整个路网的几何结构特征，主要有基于栅格化的方法（赵东保等，2016；Chen 和 Cheng，2009；李宇光和李清泉，2010）、基于聚类的方法（Edelkamp和 Schrdl，2003；Wang 等，2015；Li 等，2016；210 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)Liu 等，2012a），以及增量融合的路网提取方法（Cao和 Krumm，2009；Ahmed 等，2015；杨伟和艾廷华，2016；唐炉亮等，2015）。这类方法虽然能够有效地提取整个路网的结构信息，但未充分利用已有路网数据，对大量已有路网信息的提取实际上是不必要的，对海量轨迹数据处理的效率问题也制约了此类方法在路网实时动态更新中的应用（Chao 等，2020）。第二类方法侧重于道路局部变化信息的提取，主要通过地图匹配的方法探测轨迹中与已有路网未匹配的部分（即道路变化、新增部分），进而运用聚类、曲线拟合或图像处理等方法从未匹配轨迹数据中提取道路结构信息。例如，Wu 等（2016）利用中心点划分（partitioning around medoids，PAM）算法对未匹配轨迹点聚类，通过对聚类中心进行拟合获得新增（或变化）道路中心线；Zhao 等（2011）利用道路缓冲区分析探测新增道路上的轨迹点，通过形态学算子提取新增道路骨架线；Tang 等（2012）考虑位置、速度和方向等信息获取未匹配的轨迹点和计算密度较大的轨迹点作为种子点，进而依据这些种子点进行多项式拟合得到新增道路中心线。这类方法虽然可以直接对路网变化进行提取，但仍存在两个方面的问题：在利用海量轨迹数据发现道路变化路段或区域时主要采用缓冲区叠置分析法和一些复杂的轨迹匹配算法，如基于隐马尔可夫模型（hidden Markov model，HMM）的地图匹配算法（Wang 等，2013）、ST-Matching（Lou 等，2009），存在着算法复杂度较高、计算量大或针对复杂区域（如交叉口）匹配错误等问题，如图 1 所示（刘卫宁等，2016）；现有方法主要针对单条新增道路几何结构信息的提取，对于变化区域内存在多条新增道路时，道路变化信息不能有效提取。例如，目前道路结构信息提取常用的栅格化方法（Zhao 等，2011）、聚类中心点连线方法（Wu 等，2016）存在如栅格单元大小、聚类数目等参数设置困难的问题（图 2（a）、（b）示，同时栅格化骨架线提取方法生成的道路结构亦存在毛刺噪声等干扰（图 2（c）；曲线拟合方法，对于新增的简单线形道路拟合效果较好，但对于新增复杂道路结构，如 T 字形或十字路口等，无法直接应用，如图 2（d）所示（Lyu 等，2021；Tang，2012）。图 1 基于道路缓冲区的轨迹匹配 Fig.1 Map matching based on road buffer 图 2 栅格化骨架线提取存在问题 Fig.2 Issues with grid-based skeleton extraction 彭程 等：基于自适应轨迹聚类的城市路网提取与更新方法 211 针对目前城市路网更新方法存在的不足，本文提出一种基于自适应轨迹聚类的城市路网提取与更新方法。研究综合考虑城市路网的结构特征和移动轨迹的空间分布、移动方向特征，通过轨迹点的位置、方向约束进行轨迹与路网匹配，实现道路网变化区域的快速识别，减少轨迹点误匹配。对于新增道路中心线的提取，本文方法对未匹配的轨迹点，首先采用顾及方向约束的空间自适应聚类算法进行聚类划分，进而对每个聚类进行最优主曲线拟合获得新增道路几何结构特征，以提高对复杂道路结构信息准确提取的能力。2 城市路网变化探测与动态更新方法 本文方法主要包含轨迹数据预处理、轨迹路网匹配和新增道路中心线提取三个部分，如图 3 所示。轨迹数据预处理是为了消除移动轨迹数据中由于随机噪声和误差的影响产生的冗余、错误的数据，通过轨迹点的位置、方向和速度等信息，剔除位置、方向与速度异常的轨迹 点。针对预处理后的轨迹点，通过建立距离、方向的层次约束进行轨迹路网匹配，识别未匹配的轨迹点；进而，对未匹配的轨迹点通过自适应空间聚类将同一路段上的轨迹点聚集成簇，并对每个聚簇进行最优主曲线拟合生成新增道路中心线；最后，将新增道路与原有路网融合，对路网数据进行更新。2.1 基于轨迹路网匹配的城市路网变化区域识别 轨迹路网匹配是从候选路段中选出与 GPS 轨迹最优匹配的路段。目前，最常用的轨迹路网匹配算法包括缓冲区匹配和基于最短路径距离的匹配。前者只通过轨迹点到路段的投影距离大小判断匹配，需要设置合适的距离阈值，且容易产生误匹配；后者需要计算相邻两个轨迹点间的最短路径距离，计算复杂，如基于 HMM 的地图匹配模型。为了实现轨迹点的快速匹配且最大限度地保证匹配的精度，本文通过距离、方向的层次约束实现轨迹路网的快速匹配，如图 4 所示。图 3 本文方法技术流程图 Fig.3 The flow chart of the proposed method 图 4 轨迹点匹配示意图 箭头所示方向为轨迹点的运动方向 Fig.4 Illustration of track points matching 对于轨迹点 Pi，首先通过距离约束，确定轨迹点 Pi的候选匹配路段e1，e2，e3；进而，计算轨迹点的运动方向与各候选匹配路段方向的相似性，从中选择距离短且方向相似的路段作为 Pi点的匹配路段；如果距离或方向约束不能同时满足，则确定该轨迹点未找到匹配路段，标记为未匹配的轨迹点。给定 GPS 轨迹点数据 GD=P1，P2，Pn，每个轨迹点为一个三元组 Pi=xi，yi，oi，其中，xi和 yi表示轨迹点的投影坐标，oi表示轨迹点的方212 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)向，并将原始路网数据记为 RD=e1，e2，em，ej表示路网中的第 j 条路段，则轨迹点匹配的具体步骤如下。（1）计算当前轨迹点 Pi与路网 RD 中所有路段的最短距离d1，d2，dm，从 RD 中选取到轨迹点 Pi的距离小于距离阈值（=50 m）的路段作为候选匹配路段 C_RD=ej|dj 。（2）如果 C_RD 为空，则标记 Pi为未匹配点，返回步骤（1）；否则，继续下一步。（3）从距离 Pi较近的候选路段开始，计算该候选路段（记为 ek）与 Pi的方向差异：dircos()ike （1）式中，dirke为候选路段 ek的方向。如果（=cos（/4），为方向差异性阈值），则认为 Pi与 ek匹配，返回步骤（1）；否则，继续选取下一条距离较近的候选匹配路段计算其方向差异，并判断是否与 Pi匹配，直到所有的候选匹配路段都计算过时，若 Pi仍未找到匹配路段，则标记 Pi为未匹配轨迹点，并返回步骤（1）。（4）重复以上过程，直到所有轨迹点都处理完时，匹配过程停止。轨迹路网匹配计算过程需要设置距离阈值 和方向差异性阈值 两个参数。其中，的设置主要依据城市道路宽度和 GPS 定位误差进行设置，的设置主要根据城市道路设计规范（北京市市政设计研究院，1991）。实验中取=50 m，=45或=cos（/4）。值得注意的是，由于轨迹路网匹配方法采用了距离和方向双重约束，相比于道路缓冲区方法，其距离阈值 设置可以相对宽松，且不影响匹配的精度。本文方法通过考虑待匹配的轨迹点与候选匹配路段之间的空间位置邻近性和方向一致性两个方面的特征约束来构建轨迹点与路网的匹配算法，以提升轨迹点匹配的准确性；同时相比于基于 HMM 的 轨迹路网匹配算法（Wu 等，2016；Wang 等，2013），本文方法只考虑单个轨迹点与候选路段的匹配关系，不需要计算整条轨迹的匹配概率，从而减少了海量轨迹匹配计算的复杂度。2.2 城市新增道路中心线提取 通过轨迹路网匹配可以识别出与原始路网不匹配的移动轨迹，这些轨迹反映了城市路网中的变化信息。针对新增道路复杂结构信息提取，本文采用分解组合的策略，先采用顾及方向约束的自适应空间聚类算法将未匹配的轨迹点划分为不同方向的轨迹点簇（对应于不同方向的新增路段），进而采用主曲线拟合算法（Deng 等，2018），从每个轨迹簇中提取新增路段中心线，通过拓扑优化将各路段中心线组合，从而实现新增道路复杂结构的有效提取。相比于栅格化骨架线提取、聚类中心点连线的方法，该方法采用改进的自适应空间聚类算法（Liu 等，2012b），能够根据轨迹点分布特征自动确定聚类参数，减少了参数设置的困难，同时相比于曲线拟合的方法能够提取复杂的道路结构信息，如 T 字形、井字形等多条新增道路组合成的复杂道路结构。通过基于方向约束的自适应空间聚类算法识别不同新增道路上的轨迹点聚类（即轨迹点簇），进而针对每一个轨迹点簇采用主曲线拟合算法提取新增道路的中心线。其中，基于方向约束的自适应空间聚类算法是在 Liu 等（2012b）方法基础上的一种改进算法。首先，通过 Delaunay 三角网自适应地获取轨迹点的空间邻近域，利用三角网的边长约束删除三角网中的整体长边（即相离较远的轨迹点）；然后，在边长约束的基础上，通过施加方向约束，将连接两个方向不同的轨迹点的三角网边打断，构建轨迹点的方向约束邻域；最后，将相互邻接且方向相似的轨迹点进行合并生成轨迹点簇，如图 5 所示。图 5 本文方法提取道路中心线示例 Fig.5 Illustration of the proposed method to extract road centerlines 彭程 等：基于自适应轨迹聚类的城市路网提取与更新方法 213 基于方向约束的自适应空间聚类算法，可以区分一条道路上两个相反方向运动的轨迹点簇（即双向车道信息），但在轨迹点稀疏的道路上（新增道路），双向车道轨迹点较稀疏，这样区分双向车道上的轨迹点会降低道路中心线提取的总体精度。为此，本文对于双向车道也作为一条道路进行处理。给定未匹配的轨迹点集合 S=P1，P2，Pm，基于方向约束的自适应空间聚类的实现步骤如下。（1）依据轨迹点的位置坐标构建 Delaunay 三角网 DT（对于坐标相同的点首先进行了清理），针对每个轨迹点 Pi，计算其整体长边阈值：meancutmeanstdmean(DT)(DT)2(DT)()iLLLLLP（2）式中，mean(DT)L为三角网中所有边长的均值；std(DT)L为所有边长的标准方差；mean()iLP为与点Pi直接相连的三角网边长的均值。进而，将与Pi相连的边长大于整体长边阈值的三角网边删除，获得修剪后的连接图G。（2）依次判断G中的每一条边e，如果e连接的两个轨迹点的方向差异大于（=cos（/12），则将边e删除，否则边e保留。（3）从图G中选择一个未标记的轨迹点Pi作为新簇Ck（k=1，2，），标记Pi的类标签为k，将簇Ck的方向初始化为轨迹点Pi的方向，即ikoCo)(；搜索与Pi相邻的未标记轨迹点Pj，如果Pj与簇Ck的方向差异满足：（a）Pj与Ck同向，即cos()jkoo C()/2jkoo C，则直接将Pj与Ck合并成新簇，并计算簇内轨迹点的平均移动方向作为该簇的方向；（b）Pj与Ck反向，即cos()jkoo C()/2jkoo C，则将Pj方向取其反方向，再将 Pj与Ck合并成新簇，计算新簇的方向；（c）Pj与Ck方向垂直或交叉，即cos(jo()ko C，则Pj与Ck不能合并。继续搜索与新簇相连的未标记的轨迹点，并判断合并条件，直到该簇找不到可以合并的轨迹点时停止。（4）迭代执行步骤（3），当所有轨迹点都进行遍历时，聚类结束。最后，对簇内轨迹点数目少于r（r=10）的簇进行清理，标识为噪声。新增道路中心线提取需要设置方向差异阈值和，其中，的设置与轨迹路网匹配中的设置相同；实验中，取值为15或=cos（/12），一般取（0，45，通过实验分析发现，聚类结果对的取值不敏感。通过以上聚类算法，可以将分属于不同方向道路上的轨迹点归为不同的类簇，由此可对每个点簇采用最优曲线拟合，得到道路中心线，如图5（d）所示。2.3 路网数据融合更新与拓扑优化 根据上述方法提取的道路中心线与原有路网还存在一些拓扑问题，如悬挂线等。为此，需要对提取的新增道路做进一步处理，使其能够与原有路网进行融合，主要操作包括断线连接和节点融合。（1）断线连接。对于简单的道路结构，本文所用方法会将其聚为一类，进而拟合可得到一条比较完整的道路中心线，而对于道路结构较为复杂的道路，尤其带有复杂弧段的道路，如高架桥的弧形辅道，可能会将其分成不同的弧段，导致得到多条不连续曲线需要将其进行连接，如图6（a）所示。针对那些端点距离较小的曲线，通过计算端点直接的空间距离（记为d），如果d小于给定的距离阈值，如1 m，则将这些端点距离较小的曲线进行连接，进而对整体曲线进行拟合得到最终的道路中心线，如图6（b）所示。图 6 新增路网融合更新中的拓扑连接优化前后示例图 Fig.6 Example illustrating topological connection optimization in the fusion and updating of newly added road network 214 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)（2）节点融合。对于新增道路中心线的端点，有些新增路段并不能恰好与原有路网融合，如出现悬挂线问题。为此，本文将提取的新增路段与原始路网数据叠加，基于赵东保等（2016）提出的道路拓扑优化算法，对新增路段中心线进行延伸或修剪等处理，使其与原始路网数据进行融合，本文将这些操作统称为节点融合。3 实验与对比分析 为了验证本文方法的有效性，以武汉市青山区城郊某一区域为研究区域，数据采用6150辆出租车在2015年5月1日全天的GPS轨迹数据，轨迹采样间隔为4560 s，如图7（a）所示。GPS轨迹数据因随机噪声和误差等会产生冗余、错误的记录和大量的停滞点，影响道路结构信息的提取。本文 通过速度、行驶方向等剔除数据中速度小于5 km/h或大于80 km/h的轨迹点。原始城市路网数据采用2013年OSM（open street map）路网数据，共包含295条道路，基本涵盖了该区的主要道路，如图7（b）所示。图8（a）显示了轨迹路网匹配算法识别的未匹配GPS轨迹点，可以发现该匹配算法很好地识别出了数据中与原始路网未匹配的轨迹点，且在道路的交叉口区域也进行了较为准确的匹配。为了显示本文方法的有效性，图8（b）、（c）显示了经典的基于道路缓冲区的匹配算法（Zhao等，2011）获得的轨迹点匹配结果。当缓冲区半径R设置较大时，在交叉口区域很多不匹配的轨迹点被错误地进行匹配（图8（b），而当缓冲区半径R设置过小（道路宽度的一半）时，因为GPS定位误差，很多该匹配的轨迹点被错误地认为未匹配（图8（c）。图 7 GPS 轨迹数据和 OSM 路网数据 Fig.7 GPS track points and OSM road data 图 8 未匹配的轨迹点 Fig.8 The unmatched points 对未匹配的轨迹点进行基于方向约束的自适应空间聚类，聚类结果如图9（a）所示。可以发现，本文空间聚类算法将轨迹点分割为不同方向的轨迹点簇，这些轨迹点簇与各新增路段相互吻合，且在较为复杂的交叉路口，如图9（a）中方框所示区域，获得了理想的分割结果。图9（b）显示了未匹 彭程 等：基于自适应轨迹聚类的城市路网提取与更新方法 215 配轨迹点通过PAM聚类算法（聚类数目设为1%）获得的该区域聚类中心点。通过对比可以发现，PAM聚类算法将道路交叉口或轨迹点相对密集的区域用一个或几个中心点表示，无法反映道路的真实结构信息，而本文聚类算法获得的轨迹点簇，能够较好地反映道路真实结构信息。图 9 未匹配轨迹点聚类结果 不同颜色表示不同的轨迹点簇 Fig.9 Clustering results of the unmatched GPS points 跟原始轨迹数据（图7）对比可以发现，通过本文方法提取的研究区域内的新增道路（实验中取=50 m，=45，=15，d=1 m），准确地识别出了研究区域内的新增道路，如图10（a）所示。栅格化方法（Zhao等，2011）提取的新增道路形态弯曲且较零碎，存在很多的毛刺（图10（b）。图10（c）为中心点拟合方法（Wu等，2016）获取的未匹配轨迹点的聚类中心点。中心点识别方法对复杂道路结构识别的能力有限，且中心点拟合方法对于简单道路拟合效果较好，但由于对中心点没有进一步的分割，当存在道路交叉的区域，如图10（c）中框所示，无法自动提取真实的道路结构信息。因此，本文方法能够准确提取出新增道路结构，尤其是当存在多条新增道路连接组合构成的复杂道路结构时，相比于现有方法提取结果更优。图 10 新增道路提取结果对比 Fig.10 Comparison results of the proposed method and the compared methods 4 结 论 针对城市路网数据的实时更新问题，本文提出一种基于自适应轨迹聚类的城市路网提取与更新方法。基于动态更新的轨迹数据，通过轨迹与路网数据匹配发现道路网的变化区域，为了解决海量轨 迹数据与已有道路网的快速匹配问题，首先，利用轨迹点的空间位置和移动方向特征进行轨迹路网局部匹配，提高轨迹匹配计算效率，并识别出轨迹数据中的未匹配轨迹点；然后，为了提取出复杂新增道路结构信息，采取分解组合策略，通过基于方向约束的自适应空间聚类将未匹配轨迹点划分 216 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)为不同的轨迹点聚簇（每个簇表示一条新增道路），并针对不同的轨迹点聚簇进行主曲线拟合提取新增道路的中心线，最后，通过拓扑优化将提取的新增道路与原始道路网进行融合，实现对城市路网新增道路的变化快速更新。本文方法的主要特点为：通过轨迹匹配侧重于道路局部变化信息的提取，避免对整个城市路网的重构，以提高城市路网实时更新的效率；提出了基于位置和方向约束的海量轨迹路网局部匹配方法，能够实现匹配正确率高，计算简单；采用基于方向约束的自适应空间聚类方法能够有效区分不同道路方向上的轨迹聚类，以有效提取道路交叉口等复杂的道路结构信息。经实验分析，本文方法相比于目前常用的栅格化方法和中心点拟合方法能够较好地识别城市路网中的复杂新增道路结构，且需要的参数较少，减少了实际应用中最优参数选择的问题。本文方法也存在着一些有待进一步提升的地方，如提取的新增道路结构主要为道路中心线还无法区分不同车道信息。所提取的新增道路信息主要为不同方向的道路中心线结构，对于道路网精细变化的几何结构特征提取，如车道级路网变化信息，以及基于轨迹数据的道路结构提取精度定量化评价等方面仍需要进一步研究。对于道路网拓扑变化，如临时封路等导致的道路拓扑连通关系变化等，进行智能感知与动态更新的研究也将是下一步的研究方向。参考文献 北京市市政设计研究院.1991.城市道路设计规范(CJJ 37-90).北京:中国建筑工业出版社 蒋新华,廖律超,邹复民.2013.基于浮动车移动轨迹的新增道路自动发现算法.计算机应用,33(2):579-582 李宇光,李清泉.2010.基于矢量道路栅格化的海量浮动车数据快速处理.公路交通科技,27(3):136-141 刘卫宁,汪杰宇,郑林江.2016.基于时空分析的地图匹配算法研究.计算机应用研究,33(8):2266-2269 唐炉亮,刘章,杨雪,阚子涵,李清泉,董坤.2015.符合认知规律的时空轨迹融合与路网生成方法.测绘学报,44(11):1271-1276,1284 吴涛,向隆刚,龚健雅.2017.路网更新的轨迹地图匹配方法.测绘学报,46(4):507-515 杨伟,艾廷华.2016.基于众源轨迹数据的道路中心线提取.地理与地理信息科学,32(3):1-7 杨伟,艾廷华.2017.运用约束 Delaunay 三角网从众源轨迹线提取道路边界.测绘学报,46(2):237-245 赵东保,刘雪梅,张弘弢.2016.基于大规模浮动车轨迹点数据的道路网变化检测与更新方法研究.地理与地理信息科学,32(2):1-5 Ahmed M,Karagiorgou S,Pfoser D,Wenk C.2015.A comparison and evaluation of map construction algorithms using vehicle tracking data.GeoInformatica,19(3):601-632 Cao L L,Krumm J.2009.From GPS traces to a routable road map/Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,3-12 Chao P F,Hua W,Zhou X F.2020.Trajectories know where map is wrong:An iterative framework for map-trajectory co-optimisation.World Wide Web,23(1):47-73 Chen C,Cheng Y H.2009.Roads digital map generation with multi-track GPS data/2008 International Workshop on Education Technology and Training&2008 International Workshop on Geoscience and Remote Sensing,508-511 Deng M,Huang J C,Zhang Y F,Liu H M,Tang L L,Tang J B,Yang X X.2018.Generating urban road intersection models from low-frequency GPS trajectory data.International Journal of Geographical Information Science,32(12):2337-2361 Edelkamp S,Schrdl S.2003.Route planning and map inference with global positioning traces.Klein R,Six H W,Wegner L,Eds.Lecture Notes in Computer Science.Berlin,Heidelberg:Springer Berlin Heidelberg.128-151 Li H F,Kulik L,Ramamohanarao K.2016.Automatic generation and validation of road maps from GPS trajectory data sets/Proceedings of the 25th ACM International on Conference on Information and Knowledge Management,1523-1532 Liu Q L,Deng M,Shi Y,Wang J Q.2012b.A density-based spatial clustering algorithm considering both spatial proximity and attribute similarity.Computers&Geosciences,46(3):296-309 Liu X M,Biagioni J,Eriksson J,Wang Y,Forman G,Zhu Y M.2012a.Mining large-scale,sparse GPS traces for map inference:Comparison of approaches/Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,669-677 Lou Y,Zhang C Y,Zheng Y,Xie X,Wang W,Huang Y.2009.Map-matching for low-sampling-rate GPS trajectories/Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,352-361 Lyu H Y,Pfoser D,Sheng Y H.2021.Movement-aware map construction.International Journal of Geographical Information Science,35(6):1065-1093 Tang J B,Deng M,Huang J C,Liu H M,Chen X Y.2019.An automatic method for detection and update of additive changes in road network with GPS trajectory data.ISPRS International Journal of Geo-Information,8(9):411 Tang L L,Huang F Z,Zhang X Y,Xu H.2012.Road network change detection based on floating car data.Journal of Networks,7(7):1063-1070 Wang J,Rui X P,Song X F,Tan X S,Wang C L,Raghavan V.2015.A novel approach for generating routable road maps from vehicle GPS traces.International Journal of Geographical Information Science,29(1):69-91 Wang Y,Liu X M,Wei H,Forman G,Zhu Y.2013.CrowdAtlas:彭程 等：基于自适应轨迹聚类的城市路网提取与更新方法 217 Self-updating maps for cloud and personal use/Proceeding of the 11th annual international conference on Mobile systems,applications,and services,469-470 Wu T,Xiang L G,Gong J Y.2016.Updating Road networks by local renewal from GPS trajectories.ISPRS International Journal of Geo-Information,5(9):163-180 Zhao Y,Liu J,Chen R Q,Li J,Xie C,Niu W J,Geng D Y,Qin Q M.2011.A new method of road network updating based on floating car data/2011 IEEE International Geoscience and Remote Sensing Symposium,1878-1881 Extraction and updating method for urban road network based on adaptive trajectory clustering PENG Cheng1,TANG Jianbo1,2,PENG Ju1,MEI Xiaoming1,CHEN Xueying1,YAO Zhipeng1 1.School of Geosciences and Info-physics,Central South University,Changsha 410083,China;2.Hunan Geospatial Information Engineering and Technology Research Center,Changsha 410083,China Abstract:Due to the frequent updates of urban roads infrastructure and the limitations of traditional road updating methods,many urban roads cannot be updated promptly.To date,road network updating based on moving trajectories has proven to be an effective way to realize the rapid and efficient updating of urban roads.While some methods based on GPS trajectories,such as grid-based methods,clustering-based methods and incremental methods,have been developed,these methods tend to be sensitive to parameters.Moreover,it is still difficult for these methods to accurately extract the incremental roads with complex structures.In light of these concerns,we propose an automatic urban road updating method based on moving trajectory matching.This method takes into account both the characteristics of the moving trajectory data and the structural characteristics of the urban roads.In this paper,the location and direction of the trajectory points are firstly used to make point-to-line matching.Then,an adaptive spatial clustering algorithm,which incorporates the direction constraint,is developed to segment the unmatched points into tracks,and the optimal curve fitting is performed for each cluster to obtain the center lines of the