基于步行軌跡的復雜道路中心線提取方法

李俊杰， 劉鵬程， 頓玉多吉

(1.武漢大學遙感信息工程學院， 武漢 430079；2.華中師范大學城市與環境科學學院 地理過程分析與模擬湖北省重點實驗室， 武漢 430079；3.西藏自治區氣象局， 拉薩 850000)

數字地圖作為國家重要的基礎地理信息，也是智能交通系統構建的基礎，在交通管理、車輛導航、城市規劃以及網絡地圖服務等方面發揮著巨大作用[1].相較于傳統的使用測繪和遙感影像判讀獲取數字地圖路網數據，基于GPS軌跡的路網提取具有精度高、采集成本低、數據來源廣、實時性強等特點.隨著物聯網技術和眾源地理信息技術的發展，如何從海量的GPS時空軌跡數據中有效地挖掘豐富的道路信息，成為地理信息領域研究的熱點[2].

目前，使用GPS軌跡數據提取路網主要分為4類方法：1)基于軌跡聚類，例如文獻[3]采用K-Means算法對軌跡點進行聚類，并引入了樣條曲線擬合道路轉彎區域；文獻[4]采用數學模型中的直線和弧來描述GPS軌跡，根據定位點和行駛方向將大量GPS軌跡點聚類后連接成軌跡鏈，采用非線性最小二乘法擬合出了道路中心線.2)基于增量化的方法，如文獻[5]對軌跡點進行分類，判斷空間和語義關系，將軌跡點合并到候選路網中；文獻[6]基于軌跡合并提出了一種通用地圖生成方法，使用人工智能算法推斷道路的幾何特征，采用聚類算法增量生成路網.3)基于Delaunay三角網，如文獻[7]基于約束Delaunay三角網提取道路中軸線從而建立街道路網；文獻[8]引入約束Delaunay三角網及其對偶Voronoi圖幾何模型，從車輛軌跡線中提取出了道路邊界.4)基于柵格圖像細化，如文獻[9]對車輛GPS軌跡數據柵格化，基于數學形態學合并離散數據點，最后使用SPTA算法細化得到道路網；文獻[10]對車輛軌跡數據創建緩沖區，然后采用交叉數細化算法細化出租車軌跡數據，構建路網.相較于前3種方法，柵格細化方法將大量矢量軌跡數據點轉化為圖像運算，提高了計算效率.

當前現有研究多基于車載GPS軌跡數據(出租車、公交車、專業采集車)提取城市車道級路網，忽略了校園、社區、公園、旅游景區等小范圍區域內的復雜道路信息.其主要原因在于車道級道路級別高、路面寬闊，而類似于校園、景區等小范圍區域往往包含復雜的道路信息，不僅具有行車道，還有縱橫交錯、形態多樣的小路，交通方式以步行為主，不適用于GPS采集車進行軌跡采集.步行GPS軌跡相較于車載GPS軌跡具有如下特點：1) 自由度高，不受現有路網約束，能夠達到車載GPS不能到達的地方；2) 方向多變，下一時刻的方向存在任意性；3) 速度較慢，變化幅度小，一般在0.5～6 km/h之間[11]；4) 受采集人員的經驗、采集過程、采集設備等因素影響，數據質量具有不確定性.為此，本文在顧及區域中存在人車混行、小路交錯的情況下，設計了一種基于步行GPS軌跡數據的復雜區域道路中心線提取方法.

1 復雜道路中心線提取原理和方法

使用步行GPS軌跡數據提取復雜道路中心線技術路線如圖1所示，首先對大量步行GPS數據進行清洗，根據GPS軌跡點分布密度進行柵格化，然后基于柵格細化思想構建小范圍內的矢量路網.柵格細化能夠在保證拓撲結構和道路連通性不變的情況下，保留道路特征點并提取出柵格路網的道路中心線.

1.1 GPS軌跡數據清洗

步行GPS軌跡點由于定位精度誤差、多路徑效應、網絡狀態不穩定、長時間駐留在某區域會產生大量冗余的甚至錯誤的定位數據，數據清洗能夠避免給道路提取算法帶來額外開銷，還有利于提高精度.軌跡數據清洗主要包括去除漂移點和停留點，如圖2所示，漂移點是由于GPS定位誤差產生的明顯偏離實際道路的異常點，停留點是GPS采集設備在小范圍內長時間停留和聚集的區域，也被稱為停滯點和感興趣區域.

圖1 復雜道路中心線提取技術路線圖Fig.1 Technical roadmap of complex road centerline extraction

圖2 GPS定位漂移點和停留點Fig.2 GPS positioning drift point and stay point

在圖2(a)中，把GPS軌跡看作連續時間序列，計算定位點A到P的平均速率v.

(1)

若v大于給定的速度閾值T，則判斷P為漂移點，進行去除.其中，Δt為GPS采樣周期，|AP|表示軌跡點AP之間的球面距離，計算表達式如下：

(2)

其中，λ1，λ2是以孤度制表示的兩點經度，φ1，φ2是以弧度制表示的兩點的緯度，R為地球半徑，取R=6378137 m.

本文設計的基于空間聚類去除停留點的主要原理是通過聚類中心替代類簇中的所有點達到軌跡抽稀的目的.考慮到軌跡的方向性，本文在DBSCAN聚類算法基礎上進行改進，算法流程圖如圖3所示，設置掃描半徑r和最小包含點數min Pts，從未被訪問的點開始，掃描該點半徑范圍內包含的軌跡點個數N，當N>min Pts時聚類并計算聚類中心，但不對類簇進行擴展，而是直接以聚類中心點代替本簇中包含的種子點，直到訪問完所有軌跡點.

1.2 基于分布密度的軌跡點柵格化

GPS軌跡點是包含定位信息的點狀要素，而道路是在空間上連續分布的地理實體，GPS軌跡柵格化就是將離散的地理定位點坐標變成連通的數字圖像坐標，旨在實現道路空間上的連通.本文設計了一種基于分布密度的軌跡點柵格化方法，如圖4所示，在GPS軌跡空間定義外包矩形T，對任意軌跡點P，滿足P∈T.以Res×Res方形網格對區域T進行劃分，將GPS軌跡空間劃分為m×n個單元，Res變量確定了最終柵格化的分辨率，既要考慮到空間中大部分軌跡能夠相互連通，又要避免將兩條距離很近的小路歸為一條道路.統計GPS軌跡點在基本單元中的分布密度ρ，設置給定的閾值α.當ρ>α時，認為該區域為道路候選區域.基于軌跡點的分布密度不僅實現了柵格化，同時進一步過濾掉了稀疏的誤差軌跡點.軌跡點柵格化后可能出現空洞點和斷裂，采用數學形態學的閉運算進行填補和修復，如公式(3)所示：

AB=(A⊕B)?B，

(3)

其中，⊕為數學形態學膨脹運算，?為腐蝕運算.

圖3 去除停留點算法流程圖Fig.3 Algorithm flow chart of removal of stay point

圖4 軌跡點柵格化Fig.4 Rasterization of trajectory points

1.3 柵格細化提取道路中心線

路網柵格細化前，需要將柵格圖像進行二值化處理變成黑白二值圖像，如公式(4)所示，二值圖像能夠減小存儲、方便判別，提高圖像處理效率.其中，G(i，j)表示單一像素灰度值，B(i，j)表示二值化結果.

(4)

路網柵格圖像細化，就是不斷去除邊緣像素，生成連通的單位像素寬度的中心線骨架[12]，使用結構元素序列B對二值化柵格圖像A進行細化運算如公式(5)所示：

AB=A-(AB)，

(5)

1.4 道路中心線矢量化

矢量化是將道路中心線的柵格數據結構轉為矢量線狀數據結構的過程，傳統的追蹤法在矢量化過程中容易將細化后產生的邊緣毛刺也進行矢量化，從而影響實際效果.本文在此基礎上進行改進，其中心線矢量化原理如圖5所示，追蹤法需要先搜尋出弧段交點，然后沿弧段追蹤進行矢量化.圖5(a)為細化后的中心線，二值化指定存在道路像素為1，否則為0，遍歷每個像素P(x，y)的八鄰域σP(x，y)={(x-1，y-1)，(x-1，y)，(x-1，y+1)，(x，y-1)，(x，y+1)，(x+1，y-1)，(x+1，y)，(x+1，y+1)}，定義道路的交點節點(Intersection Node，IN)為P(x，y)∈{sum≥3|sum=∑P(xi，yi)，P(xi，yi)∈σP(x，y)}，定義道路的懸掛節點(Dangling Node，DN)為

P(x，y)∈{sum=1|sum=∑P(xi，yi)，

P(xi，yi)∈σP(x，y)}，

如圖5(b)所示.選定其中任意一個交點節點，沿“1”出發，直到到達下一交點或者懸掛節點，計算IN→DN的路徑長度L，若L小于最小懸掛長度閾值，則此路徑不存入結果集合中.對所有交點執行上述操作，最終矢量化結果如圖5(c)，矢量化后對于道路彎曲的情況采用道格拉斯-普克算法[18]進行化簡處理.

圖5 基于追蹤法的中心線矢量化Fig.5 Center line vectorization based on tracking method

2 實驗結果及分析

2.1 數據來源

實驗數據來源于19名采集人員3周時間內使用GPS軌跡采集軟件在華中師范大學校園(不包括南湖校區)采集的1 022 026個軌跡點，覆蓋了校園教學樓、辦公樓、食堂、運動場和學生宿舍等日?；顒訁^域，軌跡點信息如表1所示，采集的GPS軌跡點分布如圖6所示.

表1 軌跡點信息表

圖6 GPS軌跡點分布圖Fig.6 GPS Trajectory points distribution diagram

2.2 道路中心線提取實驗

實驗在普通PC機上進行，處理器為Intel Core i7-6700 3.40 GHz，內存RAM為32 GB，編程語言采用python.設置速度閾值為2 m/s去除漂移點，設置掃描半徑eps為1 m，最小包含點數min Pts為5，去除停留點.為提高路網提取的效率和精度，對不同細化算法進行比較，效果如圖7所示，并統計細化時間，如表2所示.

圖7 不同細化算法結果Fig.7 Results of different thinning algorithms

表2 不同細化算法處理時間

細化效果上，Hilditch經典算法產生的邊緣毛刺較多，Pavlidis算法邊緣毛刺最少，但細化后容易出現斷裂，基于數學形態學的細化算法則斷裂更為嚴重.Zhang-Suen快速細化算法和Rosenfeld 細化算法效果類似，但處理時間上，Zhang-Suen快速細化更有優勢，因此，采用Zhang-Suen快速細化算法作為路網柵格細化算法.最終提取的矢量道路中心線如圖8所示.

圖8 校園矢量路網Fig.8 Campus vector network

2.3 精度評價

采用Goodchild等提出的基于緩沖區的道路中心線幾何精度評價方法[19]定量評價提取精度，以百度地圖為參考路網，建立半徑為d的緩沖區，實際提取的道路中心線落入到緩沖區中的長度占總長度的比值即為提取精度.這里，分別設置緩沖區半徑2 m、5 m和7 m，同時將本研究實驗結果與文獻[10]中的方法進行對比，結果如圖9所示.

圖9 道路提取精度評價Fig.9 Evaluation of road extraction accuracy

由圖9分析可知，當以2 m、5 m和7 m容錯范圍建立緩沖區時，本文方法提取的路網精度分別為29.2 %、68.8 %和78.6 %，相較于文獻[10]中的方法有明顯提高.因為傳統的GPS軌跡點柵格化以固定緩沖區半徑實現路網的連通，本文采用基于軌跡點密度的柵格化方法，能夠較好的自動適應不同寬度的道路.實驗結果驗證了本研究設計的基于步行GPS軌跡數據的道路中心線提取方法能夠實現復雜道路的提取，且提取效果較好.

在7 m緩沖區范圍內仍有部分道路未被提取出來，考慮到本文提出的方法依賴于大量的GPS軌跡，當此路段未采集到GPS軌跡點或者GPS軌跡點數量較少時，在數據清洗和柵格化過程中會被過濾，出現道路缺失的情況.但同時，本文的方法提取出了復雜的小路信息，極大豐富了路網密度，相較于GPS采集車具有明顯的優勢.

3 結論

1) 針對包含復雜道路的校園景區等區域的道路提取，提出了一種基于步行GPS軌跡數據的道路中心線提取方法，且提取效果較好，為復雜路況區域的道路提取提供了新的思路.

2) 與傳統的柵格細化提取路網方法相比，本文在數據清洗的基礎上，根據人車混行的復雜道路特點，以GPS軌跡點分布密度作為柵格化標準，這樣在保證道路連通性的基礎上最大限度適應不同道路寬度，提高了細化提取中心線的精細程度，同時進一步過濾了定位誤差數據.

3) 校園、景區和社區是人流量較密集的區域，互聯網時代，人人都是傳感器[20]，人人能夠自發分享日常出行、活動、娛樂等路途中步行GPS軌跡，將志愿者地理信息(Volunteered Geographic Information， VGI)[20]作為路網更新的數據源，能夠節省人力物力，在較短時間內有效地整合大量軌跡數據資源.因此，今后需要建立和完善VGI數據采集平臺，基于道路提取算法自動化完成路網的及時提取和更新，為導航定位、出行安全、區域規劃、應急救援等提供高效的基礎地理服務.