本文内容來源于《測繪學報》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]
初審：張豔玲複審：宋啟凡
終審：金 君
資訊