本文内容来源于《测绘学报》2024年第2期（审图号GS京(2024)0297号）
适应不同轨迹数据场景的道路线形组合优化提取方法姚志鹏1
, 彭程1, 唐建波1,2
, 刘国平3, 杨学习1,2, 刘慧敏1, 邓敏1,2 1. 中南大学地球科学与信息物理学院, 湖南 长沙 410083;
2. 湖南省地理空间信息工程技术研究中心, 湖南 长沙 410007;
3. 北京滴滴出行科技有限公司, 北京 100089基金项目：国家自然科学基金（42271462；42171441；42271485）；国家重点研发计划（2022YFB3904203）；湖南省自然科学基金（2021JJ40727；2022JJ30703；2020JJ4749）摘要：车辆轨迹数据是当前城市导航路网地图动态更新的一种重要数据源，从杂乱无序的轨迹点或轨迹线中提取并拟合道路几何形态，进而生成结构化的道路矢量地图是基于轨迹数据进行道路网地图构建与更新的关键步骤。现有的道路中心线提取方法主要采用单一的线形拟合算法进行轨迹数据拟合，然而真实道路的几何形态复杂多样和车辆轨迹数据质量参差不齐，导致单一的道路线形拟合算法只能在某些特定的数据场景下适用，无法针对不同的数据场景自适应的拟合出理想的道路中心线。此外，相比于专业测量方式采集的高频轨迹数据，出租车等采集的低频轨迹数据存在轨迹点稀疏、噪声多、定位误差大等问题，这使得从低频轨迹数据中提取理想的道路中心线仍具有挑战，尤其是针对复杂的交叉口区域。为此，本文基于分治策略的思想，提出了一种适应不同轨迹数据场景的道路线形组合优化提取方法。该方法在轨迹数据预处理的基础上，根据轨迹数据的分布特点对数据进行场景分类；进而，针对不同的数据场景匹配最优的线形拟合算法，通过组合优化策略生成理想的道路中心线。本文方法融合不同拟合算法的互补优势，可以有效解决数据分布稀疏、道路结构复杂（如自相交立交桥）等不同数据场景下的道路线形拟合问题。采用北京市出租车轨迹数据进行试验与对比分析，本文方法生成道路的平均位置精度为1.24 m，显著优于现有代表性方法。关键词：轨迹数据 道路中心线 线形拟合 自适应 路网提取
引文格式：姚志鹏, 彭程, 唐建波, 等. 适应不同轨迹数据场景的道路线形组合优化提取方法[J]. 测绘学报，2024，53(2)：379-390. DOI: 10.11947/j.AGCS.2024.20220606
YAO Zhipeng, PENG Cheng, TANG Jianbo, et al. An adaptive road centerline extraction method for different trajectory data scenarios based on combinatorial optimization[J]. Acta Geodaetica et Cartographica Sinica, 2024, 53(2): 379-390. DOI: 10.11947/j.AGCS.2024.20220606
阅读全文：http://xb.chinasmp.com/article/2024/1001-1595/20240216.htm引言
现势性导航路网地图是路径规划、行车时间估计等基于位置服务的重要数据基石。由于车辆GNSS轨迹数据记录了车辆位置、运动方向和状态等信息，轨迹数据量大且动态更新快，可实时对道路的几何、拓扑和交通状态进行感知，蕴含了丰富的道路网信息，已经成为导航路网地图生成与变化更新的重要数据源[1-3]。从杂乱无序的轨迹点或轨迹线中提取道路几何中心线是基于车辆轨迹数据进行道路网地图生成与更新的关键步骤。现有基于轨迹数据的道路中心线提取研究主要有以下几类方法。
曲线拟合方法通常基于数学方法得到一条曲线与已知数据相吻合，并将该条曲线作为道路中心线。文献[4—5]基于最小二乘法的数学思想拟合道路中心线，该方法简单方便，但是容易受噪声轨迹的影响。文献[6—8]采用B样条拟合法拟合出光滑连续的曲线，可以避免因异常数据而导致整条曲线发生偏移的情况，该方法需要根据道路形态设置合适的控制点，否则会影响拟合效果。文献[9]采用分段线性拟合法拟合新增的直线道路，但对于非直线道路场景使用时存在一定的局限。主曲线拟合是从轨迹数据中提取道路中心线的另一个常用曲线拟合算法[10-15]，能够提取存在自相交的任意道路线形，但该方法在轨迹稀疏场景下，容易受到噪声影响而生成错误的道路形态。
轨迹栅格化方法先将轨迹数据转换成二值图像，再用图像形态学和细化算法提取道路中心线[16]。文献[17—18]通过核密度估计将轨迹数据转换成二值图像，再根据密度分层提取道路中心线。该类方法能减少噪声数据的干扰并且能适应数据比较稀疏的场景，但是提取结果会存在毛刺现象和拓扑信息丢失问题。针对立体交叉口等道路形态复杂区域，栅格化的方法很难提取出道路的精细几何结构。
随机选取方法从经过道路的轨迹簇中随机选择一条轨迹作为道路中心线，在高质量的轨迹数据中简单高效，但是在低频轨迹数据中容易受到噪声轨迹的影响。文献[19]用轨迹增量法提取路网，随机选取轨迹作为道路中心线，增量式扩增路网。文献[20]采用基于引力-斥力模型的轨迹聚合方法[21]来聚拢轨迹，提高了轨迹数据质量，但由于低频采样轨迹数据的高噪声、稀疏性等特征，随机选取的方法在应用于低频轨迹数据时仍存在较多的局限性。
基于图论的方法一般通过轨迹点构建图，再基于图论算法提取图中基元的中心，依次连接这些中心构成道路中心线。文献[22]和文献[23—24]分别提出基于Voronoi图和Delaunay三角网的方法来提取道路中心线。文献[25—26]提出一种横截道路中心方法，该方法按照一定的步长切割轨迹簇，获得横截中心，再连接横截中心得到道路中心线。类似地，文献[27]通过寻找密度中心点作为种子点进行连接提取道路中心线。当轨迹数据较稀疏时，该类方法计算基元的中心点时容易产生位置偏差，且基于图的方法对噪声比较敏感。
综上所述，现有的轨迹数据中道路中心线提取方法大多采用单一的算法或策略进行道路中心线提取，没有充分考虑轨迹数据分布及道路形态的复杂多样性，导致这些方法只能在某些特定的数据场景下适用，而无法自适应地根据轨迹数据自身特征提取理想的道路中心线。如图 1所示，受道路形态结构复杂和低频轨迹数据的高噪声、稀疏采样等问题的影响，如何在复杂多样的数据场景下，自适应地拟合出理想的道路中心线仍是当前道路中心线提取研究中的一个难题。
| |
| 图 1 低频轨迹数据中道路中心线拟合的主要挑战Fig. 1 Challenges of road centerline extraction from low frequency trajectory data |
| 图选项 |
为此，本文基于分治策略，提出了一种适应不同轨迹数据场景的道路线形组合优化提取方法。本文方法借鉴集成学习思想，通过对现有方法的系统梳理与适用性分析，集成现有方法针对不同数据场景下的道路线形提取优势，建立不同数据场景与道路线形提取算法间的最优匹配规则，构建基于分治策略的轨迹数据中复杂道路中心线的自适应拟合方法。相比于现有方法，本文方法的优势在于可以适用于不同轨迹数据场景下提取道路中心线，有效解决低频轨迹数据中复杂道路(如自相交立交桥)的线形自适应拟合问题。
1 道路中心线自适应提取方法
车辆轨迹是车辆在道路上行驶所留下的运动足迹，能够反映道路的实时状态信息，是目前进行导航路网地图构建与动态更新的重要数据源之一。虽然专业测量车采集的轨迹数据采样频率高(≤5 s)、数据噪声少、定位精度高，但是由于采集成本较高，还很难实现对城市大范围道路网的实时数据采集。以出租车轨迹数据为典型代表的众包轨迹数据，因数据更新快、覆盖范围广、获取成本低等特征成为目前道路信息实时获取与更新的重要数据源[3, 28-30]。然而，出租车等采集的众包轨迹数据平均采样频率较低(>30 s)、噪声多、定位不准确，单条轨迹很难反映道路中心线的准确位置。因此，在基于轨迹数据的道路中心线提取研究中，通常将轨迹沿道路方向的数据分布中心作为道路中心线，先通过轨迹线聚类[14, 20, 27]或轨迹点聚类[15, 28-29]的方法找到分布在同一条车道上的轨迹簇，然后从轨迹簇中提取道路中心线，生成矢量化的道路网地图。为此，在现有轨迹聚类基础上，本文主要解决的问题是面向不同的轨迹数据场景，如何从轨迹簇中拟合出一条代表当前道路或车道的道路中心线。为了方便描述，给出以下定义。
(1) 定义1(轨迹)：一条轨迹T是由多个轨迹点pi组成的序列。一条轨迹被定义为T={p1, p2, …, pn}，其中轨迹点pi包含车辆ID、采样点坐标、采样时间、运动方向和速度等信息。
(2) 定义2(轨迹簇)：一段轨迹簇T-cluster是一条及以上相似轨迹Ti组成的集合。一段轨迹簇被定义为T-cluster={T1, T2, …, Tk}，轨迹簇中每条轨迹采集于同一条道路或车道上，在形态上相似，在距离上相近，轨迹的始末点也分别邻近。
(3) 定义3(中心轨迹)：一条中心轨迹Tcenter是指轨迹簇中最靠近中心的那条轨迹。一条中心轨迹被定义为：与轨迹簇中其他轨迹的距离总和最小的轨迹。距离度量方法可以采用Hausdorff距离来度量，Hausdorff距离定义如式(1)所示
(1)
式中，TA和TB表示轨迹簇中的两条不相同轨迹；pi和pk表示TA和TB上的轨迹点。
(4) 定义4(道路中心线)：道路中心线C表示一段轨迹簇沿着道路方向的数据分布中心点依次连接而成的特征线，能反映道路的平面位置和曲直变化。本文中道路中心线是通过算法从一段轨迹簇中拟合得到，是由多个拟合点fi组成的序列。一条道路中心线被定义为C={f1, f2, …, fn}，其中拟合点fi=(xi, yi)为二维坐标点。单条轨迹、轨迹簇、道路中心线的简单示例如图 2所示。
| |
| 图 2 轨迹、轨迹簇和道路中心线Fig. 2 Trajectory, trajectory cluster and road centerline |
| 图选项 |
针对现有方法大多采用单一算法拟合道路中心线，难以适应不同复杂数据场景的问题。基于分治策略的思想，本文综合现有方法的优势，提出了一种适应不同轨迹数据场景的道路线形组合优化提取方法。首先，对原始轨迹数据进行预处理，减少噪声轨迹的影响；然后，根据轨迹数目、长度等特征对复杂多样的数据进行场景分类；最后，分析现有拟合方法特点，并针对分类后的数据场景，选取并提出最优的拟合算法进行道路中心线组合提取。本文方法的总体流程如图 3所示。
| |
| 图 3 道路中心线自适应提取方法Fig. 3 The adaptive road centerline extraction method |
| 图选项 |
1.1 轨迹簇预处理
由于GNSS设备存在定位误差或信号遮挡等影响，导致车辆轨迹数据中可能存在一些偏离实际道路或车道中心线很远的轨迹，这些噪声轨迹会影响道路中心线提取精度。本文受同一车道上的轨迹分布近似符合高斯分布[27]特征的启发，将距离中心轨迹Tcenter一定阈值范围内的轨迹提取出来，而将偏离中心轨迹较远的轨迹作为噪声剔除。如图 4(a)所示，显示了本文试验中某条道路上轨迹簇中的各轨迹到中心轨迹的距离统计分布，可以发现偏离中心轨迹越远轨迹分布越少。基于此，根据式(1)计算轨迹簇的中心轨迹Tcenter，然后分别计算轨迹簇中的其他轨迹(如Ti)到中心轨迹Tcenter的Hausdorff距离dT，如果dT满足以下条件则判别轨迹Ti为噪声轨迹，并将其从轨迹簇中剔除
(2)
| |
| 图 4 轨迹分布特征及噪声轨迹剔除示例Fig. 4 Distribution characteristics of trajectories and noise trajectory filter process |
| 图选项 |
式中，dT表示轨迹到中心轨迹的Hausdorff距离；x和σ分别表示轨迹簇中所有轨迹到中心轨迹的Hausdorff距离的平均值和标准差；c表示调节系数，本文试验中根据3σ准则设置c=3。式(2)的物理意义是以中心轨迹为中心划分出一个合理的距离区间来筛选出更靠近中心的轨迹，如图 4(b)所示，因此即使轨迹簇内的轨迹分布不符合高斯分布特征，依旧能筛选出更靠近中心的轨迹。
同时，由于低频轨迹数据采样频率低，导致轨迹簇内轨迹点稀疏而影响曲线拟合算法的效果。本文在剔除噪声轨迹后，采用简单线性插值算法对轨迹簇内的每条轨迹进行轨迹点加密，该方法简单高效，能够在不改变轨迹原始形态的情况下增加轨迹点的数目，满足拟合算法对轨迹点数目的要求，减少因轨迹点数目过少而带来的拟合误差。具体地，当一条轨迹中相邻轨迹点之间的距离大于一定距离阈值s时，则进行轨迹点插值，否则不进行插值。距离阈值s越小，则插值后轨迹点越密集，以轨迹点集来表示该条轨迹线的误差也越小，但轨迹点处理的计算量也会相应增加，为了均衡轨迹表示误差和计算效率，本文试验中将s设置为3 m。本文采用线性插值进行轨迹点插值，算法简单高效，能够在不改变轨迹原始形态的情况下增加轨迹点的数目，满足拟合算法对轨迹点数目的要求，减少因轨迹点数目过少而带来的拟合误差。
1.2 数据场景分类
由于车辆轨迹在不同道路上分布密度不同，且道路形态复杂多样，尤其是城市立体交叉口，单一拟合算法很难适用于不同数据场景下的道路中心线提取。如图 5所示，对比了当前常用的K段主曲线算法[31]和B样条拟合算法[32]在不同数据场景的适用性。对于复杂的立交桥自相交场景(图 5(a))，K段主曲线算法的拟合效果明显较B样条拟合算法更好，但是对于轨迹较少的数据稀疏场景(图 5(b))及长距离场景(图 5(c))，B样条拟合算法更有优势。不同拟合算法的适用数据场景存在差异，因此有必要对数据进行场景分类，为不同数据场景找到最优的方法提取道路中心线，提高算法的普适性和轨迹数据中道路中心线提取精度。通过对大量轨迹数据的观察与对比试验分析，本文根据轨迹数目、轨迹长度、轨迹形态这3种数据特征，对轨迹簇进行数据场景分类：
| |
| 图 5 K段主曲线算法与B样条拟合的提取结果比较Fig. 5 Comparison of K-segment principal curve algorithm and B-spline fitting method |
| 图选项 |
(1) 根据轨迹簇内的轨迹数目，将数据划分成稀疏和非稀疏场景。当轨迹簇中轨迹数目小于tnum时，表示为稀疏场景，否则为非稀疏场景。
(2) 根据轨迹簇内轨迹平均长度，划分成短距离、中距离和长距离场景。当轨迹平均长度小于tshort时，表示为短距离场景；大于tlong时，表示为长距离场景；其他则为中距离场景。
(3) 根据轨迹簇内的轨迹形态特征，划分成轨迹自相交和非自相交场景。
1.3 道路中心线的组合提取策略与优化方法
1.3.1 不同拟合算法的适用场景分析
通过对轨迹数据进行场景分类，能够更有针对性地选取合适的道路中心线提取方法。针对专业设备采集的高频轨迹数据而言，采用常用的曲线拟合算法(如B样条拟合)均能取得较好的结果。现有研究中，面向低频轨迹数据的道路中心线提取仍是一个难点。其中，轨迹栅格化方法[17]、横截道路中心方法[25](图 6(a))、B样条拟合算法[32]和K段主曲线算法[31]是当前低频轨迹数据中道路中心线提取的代表性方法。但是，这些方法仍存在一定的局限性。例如，轨迹栅格化方法提取的道路中心线容易产生毛刺现象且容易丢失转向信息；横截道路中心方法提取的线段不够光滑，且容易受相邻轨迹和噪声的影响而使得横截中心产生偏移，如图 6(b)所示；B样条拟合算法可以提取光滑曲线，但容易受噪声干扰，提取的道路中心线可能偏离真实的中心位置。
| |
| 图 6 横截道路中心方法及其存在的问题Fig. 6 Illustration of the sweeping method and its limitations |
| 图选项 |
K段主曲线算法相比于前面几种方法能够提取出光滑且靠近数据中心的道路中心线，该方法的主要原理为：在不考虑轨迹点方向的情况下，通过不断插入并更新主成分线段位置来拟合数据，直到达到拟合误差阈值或最大预定值时停止插入新的线段，然后以插入的线段为骨架，通过图优化连接这些线段提取出光滑且靠近数据中心的道路中心线。该算法的一个简单线段插入示例如图 7(a)所示。该方法的原理使得其能更好地适应低频轨迹数据，但也存在以下问题：①在稀疏场景下，数据过少影响线段插入效果，导致曲线拟合效果不佳，如图 5(b)所示；②在短距离或长距离场景下，容易出现过拟合或欠拟合问题，如图 7(b)所示拟合结果及其对应的线段插入结果，短距离场景下一些插入线段的方向估计有误导致连接错误导致过拟合，长距离场景下容易出现插入线段不足而导致拟合结果未能靠近数据分布中心导致欠拟合；③在一些容易诱发线段插入错误或连接错误的场景下(如U形的车辆掉头场景)，可能会出现拟合错误。
| |
| 图 7 K段主曲线方法及其存在的问题Fig. 7 K-segment method and its existing problem |
| 图选项 |
1.3.2 基于组合优化策略的道路中心线提取方法
通过对现有方法适用数据场景和存在局限性的分析，在现有方法的基础上，本文提出了一种基于组合优化策略的道路中心线提取方法。该方法包括一个组合提取策略和一个优化步骤。组合提取策略是当遇到K段主曲线算法适应的数据场景时，优先采用K段主曲线算法提取道路中心线；当K段主曲线生成的结果出错或者遇到K段主曲线算法不适用的数据场景时，则采用改进的横截道路中心方法来提取道路中心线。本文提出的改进的横截道路中心方法是先以中心轨迹的轨迹点作为锚点来横截得到道路中心(图 6(a))，再将横截的道路中心点用B样条曲线拟合方法进行拟合得到光滑的道路中心线。试验分析中发现采用该组合提取策略能够适用大部分的数据场景，但是在轨迹数据稀疏且存在杂乱的局部自相交情形时(如图 8(b)所示，因车辆路边临时停留或掉头转向等产生的局部杂乱轨迹)，改进的横截道路中心方法容易受这些杂乱轨迹段的影响。为此，本文进一步提出一种基于K-means算法的中心轨迹优化方法，在遇到轨迹稀疏且存在自相交场景或轨迹掉头场景时，代替改进的横截道路中心方法来提取道路中心线。
| |
| 图 8 基于K-means的中心轨迹优化算法Fig. 8 Road center line optimization algorithm based on K-means |
| 图选项 |
本文方法先对中心轨迹插值加密后的轨迹点进行K-means聚类，剔除轨迹点数目异常聚集的簇(局部杂乱的轨迹段)；再将各簇的中心点作为控制点(锚点)按照原始轨迹顺序依次连接，采用B样条拟合方法拟合得到平滑的道路中心线。采用该方法可以对中心轨迹进行以下两方面优化：①局部自相交位置由于轨迹形态卷曲，在进行聚类后，会形成比其他位置轨迹点数目更多的异常簇(图 8(b))，通过剔除点数目异常的簇，可以达到去除中心轨迹局部轨迹噪声的目的(图 8(b))；②可以将中心轨迹分割成多个顺序排列的簇团，再将每个簇的中心点作为控制点进行B样条曲线拟合，可使中心轨迹更加平滑，如图 8所示在立交桥自相交和局部自相交场景下中心轨迹优化前后的结果。该方法有两个关键参数需要确定，一个是K-means聚类的初始聚类个数，另一个是点数目异常簇的判定阈值，其确定方法如下。
(1) 对中心轨迹进行K-means聚类，本质上是对中心轨迹进行区域分割，通过K-means得到的每个簇就是一小段区域，通过预设每个簇的大概长度Δl，通过轨迹中心线的总长度与Δl的比值即可确定K-means初始聚类个数；同时为了避免将相邻道路上的轨迹点错误聚合在一起，Δl的设置可以根据研究区域内道路的平均宽度进行设置，本文中Δl设置为10 m。
(2) 低频轨迹数据中存在轨迹局部自相交、形态异常的区域，影响道路中心线提取精度。这些区域内的轨迹点分布相比于正常轨迹段上的轨迹点更密集，当簇内轨迹点数目n满足式(3)时，判定为异常簇
(3)
式中，u和δ表示簇内轨迹点数目的均值和标准差，m为系数(本文试验中设置m为2)。
综上分析，本文采取K段主曲线算法优先提取，改进的横截道路中心方法与中心轨迹优化方法相互补充提取的道路中心线组合优化提取策略，方法流程如图 9所示。其中，可以通过分段将长距离场景转化为中距离场景，进而采用K段主曲线方法提取道路中心线；拟合质量评价环节是对道路中心线提取结果进行质量控制，即当提取结果与中心轨迹的Hausdorff距离大于给定阈值tdist时，则认为该提取结果质量不佳，再采用其他两种方法进行代替；判断掉头场景是针对改进的横截道路中心方法在掉头场景时会存在图 6(b)所示问题，因此在掉头场景中也采用中心轨迹优化方法来提取道路中心线。
| |
| 图 9 道路中心线组合提取策略Fig. 9 The road centerline combination extraction strategy |
| 图选项 |
2 试验分析
2.1 数据与试验环境
为了验证本文方法的有效性，采用北京市出租车轨迹数据进行试验分析。轨迹数据采集时间为2020年8月20日上午8点到12点，包含车辆ID、采样时间和坐标信息，采样频率为10~40 s，约38万条轨迹，轨迹平均长度为4.2 km。本文道路中心线提取算法基于Python语言实现，试验测试环境为基于Ubunu系统上运行的Spark 10节点集群环境，每个节点配备8核Intel处理器和16 GB内存。
2.2 算法参数确定
(1) K段主曲线算法参数[13, 29]。本文将拟合误差设置为3 m，连接各线段的角度平滑惩罚系数设为1.0，最大值设为30，一方面避免因插入线段太多影响算法效率和过拟合问题，另一方面也能对中距离场景的轨迹簇提取理想的道路中心线。
(2) 数据场景分类参数的确定。通过对不同轨迹数目和轨迹长度的轨迹簇进行测试，统计分析了K段主曲线结果与中心轨迹的Hausdorff距离，考虑到车辆导航路网位置精度需求，以5 m作为合格界限，当K段主曲线算法在轨迹数目为3条及以上时，能够保证拟合效果，且当轨迹平均长度大于100 m且小于2 km时，能有效避免过拟合和欠拟合问题。因此，本文试验中将tnum设置为3，tshort和tlong分别设置为100 m和2 km。
(3) 道路中心线的组合提取策略与优化方法参数的确定。在质量评价环节需要判断K段主曲线算法是否存在拟合错误，考虑到车辆导航路网位置精度需求，本文将tdist设置为5 m。基于K-means的中心线优化算法中，根据道路平均宽度，参数Δl设置为10 m。
2.3 结果分析
交叉口是道路网中结构最复杂的区域，也是当前基于轨迹数据的道路结构提取最具挑战性的部分。因此，为了验证本文方法提取复杂道路中心线能力，试验中先采用文献[15]中交叉口识别与轨迹聚类方法将轨迹数据分割为交叉口区域和非交叉口区域，并得到交叉口和非交叉口区域内的轨迹簇，进而采用本文方法提取路网道路中心线结构，如图 10所示。其中，A—D分别放大显示了部分交叉口区域内的轨迹簇和道路中心线提取结果。可以发现，本文方法能够从原始轨迹簇中准确地提取出平滑的道路中心线，提取结果反映了交叉口的真实道路形态，与人工识别结果一致。进一步，从研究区域中选出一些其他有代表性的数据场景进行道路中心线提取试验分析，提取结果如图 11所示。试验结果表明，本文方法在一些复杂数据场景下，也能准确提取道路中心线。
| |
| 图 10 研究区域内道路中心线提取结果Fig. 10 Some results of road center lines extracted by the proposed method |
| 图选项 |
| |
| 图 11 典型数据场景下的道路中心线提取结果Fig. 11 Results in some representative data scenarios |
| 图选项 |
2.4 对比分析
为了验证本文方法适用性，分别选取轨迹稀疏、复杂道路等几个典型的数据场景，将本文方法与现有代表性方法的提取结果进行对比分析。本文试验对比的代表性方法包括：随机选取方法[19]、B样条拟合方法[32]、分段线性拟合方法[33]、K段主曲线方法[31]、轨迹栅格化方法[17]、横截道路中心方法[25]。本文方法与对比方法的提取结果如图 12所示。在轨迹稀疏和存在局部噪声轨迹段的数据场景下(图 12(a))，轨迹栅格化方法和本文方法能够在保持原始轨迹形态特征的同时，减少局部自相交噪声轨迹段的影响，分段线性拟合方法、横截道路中心方法和K段主曲线方法的道路中心线提取结果存在较大的位置偏差；如图 12(b)和图 12(c)所示，在立交桥等复杂道路结构的数据场景下，分段线形拟合方法、轨迹栅格化方法提取自相交道路中心线的结果质量较差，随机选取方法、B样条拟合方法、横截道路中心方法可以提取道路主要形态，但受噪声等影响，提取道路中心线位置偏离轨迹数据分布中心，K段主曲线方法和本文方法能够准确提取复杂道路中心线，与轨迹数据分布中心贴合度较高。
| |
| 图 12 不同道路中心线提取方法的结果对比Fig. 12 Comparison of results by different methods |
| 图选项 |
进一步，为了定量评价本文方法提取道路中心线精度，将原始轨迹数据与OSM路网数据进行叠加，发现轨迹数据与OSM路网数据存在较大的位置偏移(图 13(a))。为此，本文通过人工标注方式在轨迹数据中标记了652个特征点(如道路中心点、交叉点等)，如图 13(b)所示，进而计算这些人工标记的特征点与算法提取的同名点间的平均偏移距离来评估提取道路中心线的位置精度。表 1显示了7种对比方法的位置精度，可以发现本文方法提取的道路中心线的位置精度显著优于其他代表性方法。
| |
| 图 13 精度评价方法的选择Fig. 13 Selection of accuracy evaluation method |
| 图选项 |
表 1 不同方法提取道路中心线的位置精度比较Tab. 1 Accuracy evaluation of road centerlines extracted by different methods m
表选项
3 结论
轨迹数据中道路中心线提取是基于轨迹数据生成矢量化的道路网地图和路网地图更新的关键步骤。虽然针对该研究目前已经提出了许多经典算法，但现有方法大多针对特定数据场景采用单一拟合策略进行道路中心提取，难以适用于轨迹数据稀疏、复杂道路形态等不同数据场景下的道路中心线提取需求。同时，由于低频轨迹数据的高噪声、采样点稀疏等问题，如何从低频轨迹数据中准确提取道路中心线仍是一个有待解决的难题。针对现有方法存在的问题，本文基于分治策略，结合不同道路中心线提取算法的优势，提出了一种适应不同轨迹数据场景的道路线形组合优化提取方法，根据数据分布特征对不同的数据场景进行分类，并针对不同的数据场景选择最优的道路中心线拟合方法。采用北京市出租车轨迹数据进行试验分析，结果表明本文方法能够针对不同数据场景有效提取道路中心线，且位置精度明显优于现有代表性方法。与现有研究相比，本文方法主要贡献为：①考虑到了复杂多样的数据场景会让单一的道路中心线提取方法不适用，对数据进行了合理的场景分类，针对不同类型的数据场景选取适合的方法进行道路中心线提取，能够得到更好的结果。②针对低频轨迹数据噪声多、采样点稀疏等特征，本文方法在稀疏、有噪声的低频轨迹数据场景下也能拟合出较好的道路中心线结果。后续将继续完善复杂道路中心线拟合方法，进一步提高本文方法的精度和适用性，并开展三维道路中心线的提取研究。
作者简介第一作者简介：姚志鹏(1998—), 男, 硕士, 研究方向为时空轨迹数据挖掘与分析。E-mail: [email protected]通信作者：唐建波 E-mail：[email protected]
初审：张艳玲复审：宋启凡
终审：金 君
资讯