基于距离变换的轨迹群组相似性度量.pdf

2097-3012(2023)02-0228-07 Journal of Spatio-temporal Information 时空信息学报 收稿日期:2022-08-18；修订日期:2023-06-26 基金项目:安徽省自然科学基金项目（1908085QD164）；安徽省重点研发计划项目（2022l07020027）；自然资源部城市国土资源监测与仿真重点实验室开放基金项目（KF-2019-04-035）；安徽省高校自然科学研究项目（2022AH050095）作者简介:梁明，研究方向为时空数据挖掘。E-mail: 基于距离变换的轨迹群组相似性度量 梁明1,2，李娇1，郭昱1，吴艳兰1,2，倪建华1,2，杨根1 1.安徽大学 资源与环境工程学院，合肥 230601；2.安徽大学 湿地生态保护与修复安徽省重点实验室，合肥 230601 摘 要：从海量轨迹中挖掘移动对象的时空运动规律一直广受关注。轨迹数据的聚类、异常检测、多尺度概化等，都是以轨迹数据的相似性度量为基础的。相较于单一轨迹的相似性，轨迹群组的相似性受到尺度、轨迹数据的多维特征等多种因素的影响，缺乏广泛共识的度量方法。面向轨迹群组相似性度量的需求，本文提出了基于距离变换的轨迹骨架线提取方法，以实现轨迹群组的骨架线提取；并利用最长公共子序列算法开展轨迹群组骨架线的相似性度量；最后，基于 GeoLife 数据集对本文方法进行了验证。结果表明，基于距离变换的方法能够较好地顾及轨迹数据的多种形态特征。这可为轨迹群组相似性度量提供新思路。关键词：轨迹相似性；距离变换；骨架线提取；LCSS 引用格式：梁明,李娇,郭昱,吴艳兰,倪建华,杨根.2023.基于距离变换的轨迹群组相似性度量.时空信息学报,30(2):228-234 Liang M,Li J,Guo Y,Wu Y L,Ni J H,Yang G.2023.Similarity measurement of trajectory group based on distance transformation.Journal of Spatio-temporal Information,30(2):228-234,doi:10.20117/j.jsti.202302009 1 引 言 随着定位技术的快速发展，移动对象的轨迹数据激增。然而，海量的数据本身并不能直观地给出研究对象的时空运动规律（江俊文和王晓玲，2015；赵东保和邓悦，2023）。针对轨迹数据开展分析和挖掘有助于掌握空间对象的移动规律，细化对客观对象运动和演化的认知，从而帮人们更好地探究海量轨迹中潜在的时空模式，以支撑道路优化、动物保护政策制定等。例如，通过对轨迹数据的挖掘提取旅游用户的感兴趣地点（范海林等，2019）、发掘特定人群的出行习惯（俞庆英，2019；李丞等，2023）、识别城市的功能区（张慧杰等，2018）、评价候鸟的栖息地（李旭源等，2015）。轨迹数据相似性度量作为轨迹数据挖掘基础，一直备受研究人员的关注。一方面，目前的研究多集中在单一轨迹相似性度量上，无法描述轨迹群组的整体运动特征（Tang 等，2021；Sepulvado 等，2022）。然而，这些整体特征对于道路规划、交通管制、动物迁徙研究等领域至关重要。另一方面，已有研究的度量算法主要基于欧氏距离，如动态时间规整、编辑距离和隐马尔可夫模型等方法（Sabarish 等，2020；李珍等，2021；Liu 等，2022）。然而，轨迹数据除了空间距离特征外，还包括时间、形状、方向、速度等多维时空特征（Mao 等，2017；Wan 等，2017；周星星等，2018）。上述经典算法无法充分考虑这些多维特征。因此，本文探讨一种综合的度量方法，以尽可能全面地衡量轨迹之间的相似程度，并进一步探索轨迹群组的相似性度量方法。轨迹群组构成了特定的时空场景，其中潜藏着空间对象的运动规律。Bruns 和 Egenhofer（1997）较早提出了场景相似性度量的基本原则。Aksoy 等（1996）用属性关系图场景相似性加以度量。郭庆胜等（2019）提出了栅格面状要素空间方向相似性的度量方法，但是仅仅考虑了方向相似性。丁虹（2004）则尝试将方向关系、距离关系综合考虑。当前的场景相似性度量研究大多针对面状、点状等 梁明 等：基于距离变换的轨迹群组相似性度量 229 对象（张丁文等，2018；Shen 等，2022），针对轨迹群组的研究鲜见。因此，本文提出先通过提取轨迹群组的骨架线对轨迹群组进行概化，然后对概化后的轨迹群组骨架线进行相似性度量的思路，最后，以真实轨迹数据集 GeoLife 进行验证。2 方 法 2.1 基于距离变换的轨迹群组骨架线提取 轨迹群组由多条形态和运动特征各异的子轨迹组成。两个轨迹群组的相似性，无法通过逐条轨迹的相似性进行度量。而轨迹群组的骨架线作为一组相似轨迹的概化表达，能够综合表征一组轨迹的距离、位置、时间、方向、速度等多维特征（黄窈蕙等，2018；赵东保等，2020），并在一定程度上表征轨迹群组的变化趋势和总体形态。此外，构成骨架线的点可以附加时间戳，从而具有表达骨架线的方向和速度的能力。因此，可以用其骨架线的相似性度量两组轨迹相似性。骨架线提取有两种思路：一种基于矢量；另一种基于栅格。其中，基于矢量的方法主要是采用Delaunay 三角网剖分的思想（刘远刚等，2015；肖冰等，2019）。然而，如果将 Delaunay 三角网剖分的方法用于群组骨架线提取，则需要不断递归，从而导致算法复杂度高、效率低，且易受异常值影响。因此，本文提出一种基于栅格思想的距离变换的方法，来实施轨迹群组的骨架线提取。距离变换是地图代数理论中一种基于栅格思想的特征提取方法（Shamir 和 Shaham，2006；丁颐等，2005；徐超等，2012）。无论对象是矢量数据还是栅格数据，皆可用栅格的方式实施距离变换。距离变换常用欧氏距离作为权重，计算空间每一点与处理对象的距离，并将距离作为栅格像素值存储。处理完整个空间中的像素，就产生了距离变换图。根据不同因子作距离变换的参数可得到不同的距离图（江威等，2015；Elizondo-Leal 等，2020）。2.1.1 轨迹权重的设置 每条轨迹赋予一个权重值（value），存储到矢量线数据的属性表中转为栅格数据时，也是以这个权重值作为像素值，具体为：如果研究重点为轨迹群组在时空上的分布格局，则可以将权重设为相同的一个值，如设置为 1。那么在栅格轨迹叠加之后，取像素值较高的部分提取的骨架线就是描述这些用户都经过的地方，即通行频率较高的主要道路。如果研究重点为轨迹群组一段时间的速度分布，则可以按照轨迹的速度赋予权重，速度较大的轨迹权重较大。在此基础上，通过叠加栅格轨迹数据提取高密度或低密度区域，提取的骨架线就是描述某段时间的高速路段或低速路段。此外，时空轨迹数据具有多维特征，如方向、加速度等都可以作为权重因子用于提取对应的骨架线。由于本文主要考虑时空轨迹群组的分布、态势等，因此每条轨迹权重都设置为相同的值。2.1.2 提取权重最大的部分 本文中轨迹权重最大的部分也是轨迹密度最大的部分。对每条轨迹赋予一定的宽度 L1。宽度因研究尺度和数据特征而异：小尺度下，宽度可设置稍大一些。因为要采集概括的信息，多条轨迹叠加起来可以将轨迹之间的缝隙填补。大尺度下，宽度可设置稍小一些，为了在提取时使临近的不同轨迹区分明显，多条轨迹叠加之后要保留一些缝隙以表现局部的轨迹密度分布。由图 1 可知，在不同线宽 L1的取值情景下，轨迹群组叠加之后覆盖范围不同。当宽度 L1取值较小时各条轨迹之间会露出缝隙，而当宽度 L1取值较大时则可将空间上邻近轨迹之间的几何缝隙完全覆盖。此外，轨迹线宽 L1的设置应当顾及轨迹叠加的实际需求。若轨迹线宽 L1取值过小，则轨迹叠加后会出现密度较大区域发生严重断裂的情形，且分层情况不明显。因此，需要通过多次试错的方式选择 图 1 不同线宽 L1下各条轨迹叠加情况 Fig.1 Superposition of trajectories with different line width L1 230 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)合适的轨迹宽度 L1。当通过多次试错迭代找到合适的轨迹宽度 L1之后，再提取权重累积最大的部分，才构成了轨迹群组的骨架线雏形。2.1.3 距离变换 经过上述步骤后，以初始骨架线为基础向外作距离变换。距离变换长度记为 L2。L2的具体取值由研究的空间尺度和数据分布特征来确定：若数据分布较为松散，即断裂和缝隙宽度大，则 L2值设置需要稍大一些以保证骨架线的连通性；若数据分布紧凑，则 L2值可设置稍小一些，以保证将轨迹群组中间的密度较小的部分不被舍弃；若提取小尺度骨架线信息，可设置较大的 L2值，此时中间的小密度区域可忽略不计，只提取主要几条骨干线；若提取大尺度局部细节信息，可设较小的L2值，此时中间小密度区域和轨迹群组局部弯曲部分都要提取，得到较细致的骨架线。详情如图 2 所示。图 2 不同距离变换值 L2生成的距离图 Fig.2 Distance map generated with different distance transform values L2 2.1.4 骨架线提取 在经过距离变换得到的栅格距离图上，采用距离分配的方法提取不同尺度下栅格距离图的中轴线，并将其作为该尺度下的轨迹群组骨架线。其核心是在栅格距离图上寻找“凸点”，并用“凸点”打断距离图边界线，再对边界线进行距离分配，从而得到中轴线，即骨架线。本文采用双缓冲变换提取“凸点”，具体过程如图 3 所示。首先，对多边形作双缓冲区变换。先向内作 L长度缓冲区，再以当前缓冲区作向外L长度缓冲区，并与原始图形进行裁剪得到凸出部分图形，即图 3（d）中的 a 部分。图 3 双缓冲变换提取“凸点”多边形示意图 Fig.3 Schematic diagram of“convex points”polygons extracted using dual-buffer transformation 然后，对突出部分 a 通过判断“基高比”是否保留或剔除。这里“基高比”可定义为凸出图形 a的面积除以 a 与 C 的交线的长度。大于“基高比”阈值的则保留，否则剔除。最后，开展障碍距离变换从而得到“凸点”。图形以外的部分为障碍区域，以裁剪边为基线作障碍距离变换，最终将距离最大的位置作为“凸点”，如图 4 所示。图 4 障碍距离变换获得“凸点”示意图 Fig.4 Schematic diagram of“convex points”obtained with obstacle distance transformation 梁明 等：基于距离变换的轨迹群组相似性度量 231 找到“凸点”后，用“凸点”打断多边形的边界，再以每段边界为发生元作距离分配，得到最终的骨架线。2.2 基于 LCSS 的骨架线相似性度量 轨迹群组的骨架线代表了轨迹群组的总体特征。轨迹群组的相似性度量可以转化为骨架线的相似性度量。骨架线相似性的度量可直接借用成熟的轨迹相似性度量方法。其中，最长公共子序列（longest common subsequence，LCSS）算法在轨迹数据的相似性度量中的应用最为广泛（Aksoy 等，1996）。LCSS 算法对于噪声数据具有较高的鲁棒性，以得分的形式度量序列之间的相似度，最长公共子序列长度越长则轨迹越相似。LCSS 算法可以较好兼顾时空轨迹的多维特征，尤其在距离相似度和时间相似度方面度量能力突出。与 LCSS类似的编辑距离类算法，还有实序列编辑距离（edit distance on real sequence，EDR）算法（Li 等，2019）、带有实值惩罚的编辑距离（edit distance with real penalty，ERP）算法（Han 等，2021）。但是 EDR算法和 ERP 算法度量更为细致，这导致计算开销较大。综合考虑度量能力和计算开销，选用 LCSS 算法作为轨迹骨架线的相似性度量方法。3 结果与分析 3.1 数据来源 为了验证所提出的轨迹群组相似性度量的方法，以开源轨迹数据集 GeoLife 为基础开展实验验证。GeoLife 数据集从2007 年4 月2012 年8 月总共收集了 182 个用户的轨迹数据。这些数据包含了一系列以时间为序的点，每个点包含经度、纬度、海拔等信息。数据集共包含 17621 条轨迹，总距离为 1251654 km，总持续时间为 48203 h。由于这些轨迹使用不同的GPS 记录器和 GPS 电话记录，所以具有不同的采样频率。91%的轨迹拥有较频繁的采样频率，大概每15 s 或 510 m 记录一个点。这些数据不仅仅记录了日常工作的位置轨迹，还记录了大范围户外活动轨迹，包括娱乐和体育活动。3.2 实验结果 一方面，距离变换算法过程虽然简单，但由于算法基于栅格的思想，在实施过程中需要进行多次矢量栅格数据转换，导致耗时较长；另一方面，初次叠加距离变换图累积像素值获得的骨架线存在断裂情况，需要额外进行膨胀粘连的工作，之后才对多边形进行骨架线提取。距离变换过程中关键环节包括：轨迹权重的设置。每条轨迹的权重可以根据不同提取目的设置，权重可以是速度、加速度、方向等，也可以是单个固定值。权重不同提取得到的骨架线物理意义不同，描述的信息也不同。每条轨迹宽度 L1的设定。这一参数显著影响着提取效果，甚至包括断裂情况也受 L1参数的影响。因此在设置线宽 L1前可能要先对数据整体有一定的宏观掌握，以便设置合理的取值。对于不同距离变换轨迹群组骨架线的提取，关键是设置不同的距离变换长度 L2。若需要提取高度概化的轨迹群组特征，设置较大的 L2值，提取最主要的骨干线；需要提取细节信息时，设置较小的 L2值，将轨迹群组内部的空洞挖出来，提取较为细致的骨架线。本文选取了不同的空间距离作为距离变换值L2，开展多尺度轨迹群组骨架线的提取实验，以分析空间尺度对骨架线提取结果的影响。不同距离变换值 L2对应提取到的骨架线，如图 5 所示。当距离变换值较小时，轨迹群组的一些缝隙和弯曲细节都能较好地作为骨架线被保留和提取出来（图 5（a）。随着变换距离值的增加，轨迹群组的细节特征逐渐丧失，例如，轨迹群组有些孔洞便不能被提取出来，相应的骨架线也不会将孔洞描述（图 5（b）。如果距离变换值的取值进一步提高，得到的距离变换图就已经呈一个凸多边形状，很少有大角度的弯曲和孔洞，因此，所提取的轨迹群组骨架线只是轨迹群组的大致分布轴线，轨迹细节基本不再保留（图 5（c）、（d）。综上所述，距离变换思想可以用于轨迹群组的骨架线提取。接下来，利用 LCSS 的方法度量轨迹骨架线的相似性，以近似表征轨迹群组的相似性程度。并应用于 GeoLife 数据集中不同尺度的轨迹群组间相似性的度量。首先，基于 Douglas-Peucker 算法对 GeoLife 数据集开展多尺度压缩，以获取不同尺度的轨迹群组；然后，提取不同尺度轨迹群组的骨架线；最后，开展基于 LCSS 算法的相似性度量。由表 1 知，序号 14 不同尺度的轨迹群组分别为 GeoLife 原始轨迹群组（序号 1）、压缩距离为 5 m的轨迹群组（序号 2）、压缩距离为 10 m 的轨迹群 232 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)图 5 不同距离变换值 L2提取得到的骨架线 红色线为骨架线 Fig.5 Skeletonization extracted with different distance transformation values L2 组（序号 3），以及压缩距离为 30 m 的轨迹群组（序号 4）。从结果来看，不同压缩尺度下的轨迹群组与GeoLife 原始轨迹群组间的相似度量结果依次为91%、86%和 72%。结果表明，压缩尺度显著影响轨迹群组间的相似性。压缩尺度越接近，轨迹群组的相似度越高；压缩尺度差异越大，相似度越低。表 1 不同压缩尺度轨迹群组与 GeoLife 原轨迹群组的相似性 Tab.1 Similarity between trajectory groups with different compression scales and the original GeoLife trajectory group 序号 压缩距离/m 相似性/%1 0 2 5 91 3 10 86 4 30 72 4 结 论 轨迹的相似性度量作为轨迹数据挖掘的基础性问题一直受到普遍关注。本文聚焦轨迹群组的相似性度量，从栅格的视角出发，利用地图代数的距离变换思想，开展轨迹群组相似性度量的研究；并利用 GeoLife 数据集进行了实验。结果表明：不同的线宽 L1值决定了叠加之后断裂和缝隙的情况，同时也会影响提取效果。若线宽设置的太小，不足以将距离很近的轨迹之间的缝隙覆填充，也会造成多处断裂；若线宽设置过大，则会导致轨迹之间的大面积空白被覆盖，提取的骨架线不够精细。不同的距离变换 L2值决定了膨胀的范围。L2取值较小时，轨迹群之间的孔洞可以被挖出来，提取的骨架线就比较贴合轨迹群组的弯曲形态；若取值较大，则轨迹群之间的孔洞都被覆盖，提取的骨架线更适合描述轨迹群组整体的分布。尺度是应用轨迹群组骨架线提取的重要因素。不同尺度下的骨架线相似程度不同。尺度越接近，相似度越高；尺度差异越大，相似度越低。对同一尺度下的骨架线度量相似性，可以判断两条骨架线代表的轨迹群组是否具有相同或相近的布局和模式；对不同尺度下的骨架线度量相似性，可以用来判断轨迹压缩、轨迹概化或其他类型轨迹处理的算法的优劣程度。综上所述，基于距离变换的轨迹群组相似性度量，不但可以解释轨迹群组的相似程度，还可用于挖掘不同尺度轨迹群组的总体特征，以支撑路网优化、交通管制、动物保护等多种任务。参考文献 丁虹.2004.空间相似性理论与计算模型的研究.博士学位论文.武汉:武汉大学 丁颐,刘文予,郑宇化.2005.基于距离变换的多尺度连通骨架算法.红外与毫米波学报,24(4):281-285 范海林,梁明,李佳,段平,王姗姗,王彤.2019.顾及地理语境的旅游轨迹停留点语义标注.测绘通报,(6):66-70 郭庆胜,刘洋,李萌,程晓茜,何捷,王慧慧,魏智威.2019.基于网格模型的导航道路图渐进式化简方法.测绘学报,48(11):1357-1368 黄窈蕙,范文涛,刘柳杨.2018.利用轨迹数据进行道路网更新及轨迹融合.测绘通报,(8):119-123 江俊文,王晓玲.2015.轨迹数据压缩综述.华东师范大学学报(自然科学版),(5):61-76 江威,吴艳兰,谭树东,马艺文.2015.一种多发生元 Voronoi 图的栅格生成方法.地理与地理信息科学,31(5):39-43,2 李丞,花向红,赵不钒,李琪琪,代许松,邹禄杰.2023.一种利用GNSS 数据进行城市交通状况变化探测的方法.测绘地理信息,48(1):132-137 李旭源,罗泽,阎保平.2015.一种基于节点删除法的候鸟栖息地重要性评估方法研究与实现.计算机应用研究,32(2):409-412 李珍,夏吉喆,张海涛.2021.基于交通大数据的城市医疗可达性分 梁明 等：基于距离变换的轨迹群组相似性度量 233 析研究.地理信息世界,28(3):100-106 刘远刚,郭庆胜,孙雅庚,林青,郑春燕.2015.地图目标群间骨架线提取的算法研究.武汉大学学报(信息科学版),40(2):264-268 肖冰,王亮,徐胜华,梁勇,刘晓.2019.Delaunay 三角网的鄱阳湖水陆地形数据整合研究.测绘科学,44(1):48-52 徐超,肖潇,骆燕,胡慧杰,刘明.2012.基于距离变换的新型骨架提取方法.仪器仪表学报,33(12):2851-2856 俞庆英.2019.时空轨迹数据挖掘及其在城市居民出行行为模式分析中的应用研究.博士学位论文.芜湖:安徽师范大学 张丁文,陈占龙,谢忠.2018.利用松弛标记法进行空间场景匹配.武汉大学学报(信息科学版),43(5):752-758 张慧杰,王蓉,陈斌,侯亚芳,曲德展.2018.基于轨迹和兴趣点数据的城市功能区动态识别与时变规律可视分析.计算机辅助设计与图形学学报,30(9):1728-1740 赵东保,邓悦.2023.顾及轨迹压缩的车辆路径查询算法.测绘学报,52(3):501-514 赵东保,孟俊贞,刘文玉.2020.群组相似轨迹的特征点映射数据压缩方法.测绘科学,45(3):143-149 周星星,吉根林,张书亮.2018.时空轨迹相似性度量方法综述.地理信息世界,25(4):11-18 Aksoy D,Yazici A,George R.1996.Extending similarity-based fuzzy object-oriented data model/Proceedings of the 1996 ACM Symposium on Applied Computing(SAC),542-546 Bruns H T,Egenhofer M J.1997.Similarity of spatial scenes/Seventh International Symposium on Spatial Data Handling,173-184 Elizondo-Leal J C,Ramirez-Torres J G,Barrn-Zambrano J H,Diaz-Manrquez A,Nuo-Maganda M A,Saldivar-Alonso V P.2020.Parallel raster scan for Euclidean distance transform.Symmetry,12(11):1808 Han K,Xu Y F,Deng Z L,Fu J W.2021.DFF-EDR:An indoor fingerprint location technology using dynamic fusion features of channel state information and improved edit distance on real sequence.China Communications,18(4):40-63 Li R,Yang H,Zheng G,Chen Q,Sun Q C.2019.Study of granular state transition in a rotation drum by using speckle visibility spectroscopy and the edit distance with real penalty algorithm.Powder Technology,347:10-16 Liu X,Tan X Y,Guo Y C,Chen Y S,Zhang Z.2022.CSTRM:Contrastive self-supervised trajectory representation model for trajectory similarity computation.Computer Communications,185:159-167 Mao Y C,Zhong H S,Xiao X J,Li X F.2017.A segment-based trajectory similarity measure in the urban transportation systems.Sensors,17(3):524 Sabarish B A,Karthi R,Kumar T G.2020.Graph similarity-based hierarchical clustering of trajectory data.Procedia Computer Science,171:32-41 Sepulvado B,Wood M L,Fridmanski E,Wang C,Chandler M J,Lizardo O,Hachen D.2022.Predicting homophily and social network connectivity from dyadic behavioral similarity trajectory clusters.Social Science Computer Review,40(1):195-211 Shamir A,Shaham A.2006.Skeleton based solid representation with topology preservation.Graphical Models,68(3):307-321 Shen J W,Shi K F,Ma M G.2022.Exploring the construction and application of spatial scene knowledge graphs considering topological relations.Transactions in GIS,26(3):1531-1547 Tang C H,Chen M Y,Zhao J H,Liu T,Liu K,Yan H R,Xiao Y J.2021.A novel ship trajectory clustering method for finding overall and local features of ship trajectories.Ocean Engineering,241:110108 Wan Y,Zhou C H,Pei T.2017.Semantic-geographic trajectory pattern mining based on a new similarity measurement.ISPRS International Journal of Geo-Information,6(7):212 Similarity measurement of trajectory group based on distance transformation LIANG Ming1,2,LI Jiao1,GUO Yu1,WU Yanlan1,2,NI Jianhua1,2,YANG Gen1 1.School of Resources and Environmental Engineering,Anhui University,Hefei 230601,China 2.Anhui Province Key Laboratory of Wetland Ecosystem Protection and Restoration,Anhui University,Hefei 230601,China Abstract:With the widespread adoption of mobile positioning technology and the accumulation of trajectory data,trajectory data mining has emerged as a highly prominent research area.Clustering,outlier detection,and multiscale generalization of trajectory data are all rely on measuring the similarity of trajectory data.Among these approaches,measuring the similarity among trajectory groups has become a crucial aspect of trajectory analysis.Accurate quantification of trajectory group similarity is essential for uncovering concealed patterns and regularities within trajectory data.Therefore,exploring effective methods for measuring trajectory group similarity holds paramount importance in fully realizing the potential value of trajectory data.The purpose of this study is to investigate an efficient approach for measuring the similarity of trajectory groups from a grid-based perspective,utilizing the concept of distance transformation in map algebra.Through empirical research conducted on the GeoLife dataset,this study aims to validate the feasibility of the proposed method and derive conclusions to guide trajectory data mining and processing.234 Journal of Spatio-temporal Information 时空信息学报 2023,30(2)In this study,a distance transformation-based method is adopted to measure trajectory group similarity.Firstly,the impact of different line widths values(L1)on the extraction of overlapping fractures and gaps is assessed,to observe their influence on feature extraction.Subsequently,different distance transformation values(L2)are employed to determine the scope of dilation,enabling the extraction of skeleton lines that adequately describe the overall distribution of trajectory groups.Finally,the similarity of skeleton lines at various scales is evaluated to assess trajectory group similarity and compare the effectiveness of different trajectory processing algorithms.The experimental results emphasize the significance of selecting appropriate line widths and distance transformation values for extracting skeleton lines of trajectory groups.Smaller line widths and distance transformation values help retain detailed features of trajectory groups,while larger values are more suitable for capturing the overall distribution.Additionally,the scale of skeleton lines is a pivotal factor influencing their similarity.Skeleton lines at the same scale exhibit higher similarity,whereas those at different scales exhibit lower similarity.The distance transformation-based method provides a means to not only quantify the similarity among trajectory groups but also capture the overall characteristics of extensive trajectory datasets.The choice of line widths and distance transformation values,along with the discrepancies in skeleton line scales,significantly impact the measurements of trajectory group similarity.Therefore,when processing and mining trajectory data,it is imperative to select appropriate parameters and methodologies based on specific application contexts and objectives.This study introduces a novel approach for measuring trajectory group similarity based on distance transformation,offering fresh insights and methodologies for trajectory data mining.Accurate measurement of trajectory group similarity facilitates the discovery of concealed patterns and regularities within trajectory data,providing essential guidance for trajectory data processing and analysis.Furthermore,this method can optimize the design of trajectory processing algorithms,thereby enhancing the efficiency and effectiveness of trajectory data mining.Key words:trajectory similarity;distance transformation;skeleton line extraction;LCSS Supported by Natural Science Foundation of Anhui Province(1908085QD164);Key Research and Developm