出租車GPS軌跡集聚和精細(xì)化路網(wǎng)提取

鄔群勇，吳祖飛，張良盼

1. 福州大學(xué)空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室，福建 福州 350002； 2. 衛(wèi)星空間信息技術(shù)綜合應(yīng)用國家地方聯(lián)合工程研究中心，福建 福州 350002； 3. 福建省空間信息工程研究中心，福建 福州 350002

路網(wǎng)數(shù)據(jù)作為重要的基礎(chǔ)地理信息數(shù)據(jù)源[1]，在地圖匹配[2-4]、交通擁堵治理[5]等領(lǐng)域具有重要的應(yīng)用，如何快速獲取現(xiàn)勢性強、精細(xì)化程度高的路網(wǎng)信息成為當(dāng)前交通地理信息領(lǐng)域的重要研究方向[6]。伴隨移動端定位技術(shù)的成熟，攜帶定位裝置的出租車在短時間內(nèi)便能獲取大量城市道路網(wǎng)數(shù)據(jù)，因此出租車GPS軌跡數(shù)據(jù)成為挖掘路網(wǎng)信息的重要數(shù)據(jù)源[7]。

利用出租車GPS軌跡數(shù)據(jù)提取路網(wǎng)信息主要有如下幾種方法：

(1) 基于軌跡聚類提取路網(wǎng)，通常利用軌跡點位置和方位角信息，運用聚類算法對軌跡進(jìn)行聚類提取道路網(wǎng)[8-9]。文獻(xiàn)[10]假設(shè)每條軌跡段附近存在勢能場，通過對軌跡點的移動實現(xiàn)同一條道路上的軌跡匯集，然后運用軌跡增量方法遍歷軌跡段提取路網(wǎng)，該方法難以將交叉路口處不同轉(zhuǎn)向關(guān)系的軌跡完全分離，尤其在停車場附近的路網(wǎng)提取結(jié)果并不理想。文獻(xiàn)[11]運用文獻(xiàn)[10]提出的軌跡分離方法對軌跡進(jìn)行預(yù)處理，然后通過軌跡點的方位角變化確定交叉路口位置，單獨提取交叉路口內(nèi)部的路網(wǎng)信息。文獻(xiàn)[12]根據(jù)距離和方向?qū)壽E段進(jìn)行聚類，對同一類簇的軌跡點運用B樣條曲線進(jìn)行擬合得到路網(wǎng)，該方法計算復(fù)雜，提取結(jié)果受路網(wǎng)區(qū)域特征影響明顯。

(2) 軌跡增量法提取路網(wǎng)，這類方法以軌跡為研究單元，融合位置和形態(tài)相似的共同軌跡段，在路段交叉處分割軌跡從而實現(xiàn)路網(wǎng)提取[13-14]。文獻(xiàn)[15]基于軌跡點的速度及方向變化特征提出了交叉路口的識別方法。文獻(xiàn)[16]通過遍歷軌跡段集合，基于軌跡的空間位置關(guān)系確定是否將軌跡段添加到待生成的路網(wǎng)集合當(dāng)中，由于道路交叉處的確定受閾值影響明顯，該方法提取得到的路網(wǎng)平滑度不夠。

(3) 軌跡柵格化提取單線路網(wǎng)，該類方法將軌跡柵格化為二維的數(shù)字灰度圖，通過骨架線提取方法從圖像中識別道路網(wǎng)[17]。文獻(xiàn)[18]基于二值化的軌跡數(shù)據(jù)分別使用Douglas-Pecuker算法和多元自回歸適應(yīng)樣條算法獲取道路中心線。文獻(xiàn)[19]提出了一種改進(jìn)的核密度方法，該方法能夠基于灰度圖生成路網(wǎng)骨架，然后采用地圖匹配算法完善道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和幾何特征。文獻(xiàn)[20]運用圖像細(xì)化算法從柵格化后的軌跡數(shù)據(jù)提取路網(wǎng)。但大多基于柵格化方法提取的路網(wǎng)數(shù)據(jù)通常存在明顯的鋸齒，難以反映交叉路口的細(xì)部信息。

(4) 顧及車輛行駛特征的其他路網(wǎng)提取方法。文獻(xiàn)[21]根據(jù)軌跡點的分布位置，通過計算軌跡點重復(fù)的數(shù)量來識別可能的路口交叉點，然后以一定的規(guī)則將交叉點進(jìn)行連接得到路網(wǎng)；文獻(xiàn)[22]運用軌跡增量的方法提取道路幾何特征，結(jié)合地址標(biāo)簽信息提取道路屬性信息；文獻(xiàn)[23]對軌跡構(gòu)建Delunay三角網(wǎng)得到道路輪廓，然后在道路輪廓基礎(chǔ)上二次構(gòu)建Delunay三角網(wǎng)，通過對不同類型三角形邊的中點進(jìn)行連接提取道路中心線。

上述絕大多數(shù)方法的路網(wǎng)提取結(jié)果為單線路網(wǎng)數(shù)據(jù)，更詳細(xì)的道路網(wǎng)信息需要另做處理；部分算法的路網(wǎng)提取結(jié)果在道路中間部分為雙線路網(wǎng)，但以節(jié)點的方式代表交叉路口，難以反映道路的真實轉(zhuǎn)向關(guān)系，或者通過確定交叉路口的范圍單獨提取內(nèi)部的路網(wǎng)信息，然而當(dāng)交叉路口存在復(fù)雜轉(zhuǎn)向關(guān)系時，交叉路口位置的確定精度受閾值影響明顯[11]。

本文在上述問題基礎(chǔ)上，提出一種軌跡點集聚和路網(wǎng)提取方法。該方法假設(shè)道路兩側(cè)的軌跡點會受到來自道路中間區(qū)域軌跡點的吸引力，而中間區(qū)域的軌跡點受到來自道路兩側(cè)軌跡點相反方向的吸引力；然后根據(jù)軌跡點受到的吸引力大小對軌跡點進(jìn)行偏移，進(jìn)而實現(xiàn)同一條道路上相同行駛方向軌跡的集聚；最后剔除未成功集聚的軌跡點，將聚集后的軌跡按車輛ID和時間順序連成軌跡線，對每條軌跡做緩沖區(qū)并融合為面要素，運用柵格數(shù)字化的方法提取道路網(wǎng)。本文方法的優(yōu)勢在于能很好地分離不同行駛方向的軌跡分別進(jìn)行集聚，并完整的提取復(fù)雜交叉路口處道路的精細(xì)轉(zhuǎn)向關(guān)系。

1 精細(xì)化路網(wǎng)提取策略

由于受到GPS設(shè)備定位誤差、城市高層建筑及車輛運營的影響，出租車原始GPS軌跡數(shù)據(jù)存在以下特點：①包含眾多離散軌跡點及遠(yuǎn)離城市主要道路的停留點；②道路上不同行駛方向的軌跡點交錯混雜；③路口轉(zhuǎn)彎處的車輛軌跡無法反映真實的道路幾何特征。以上原因?qū)е萝壽E數(shù)據(jù)無法直接用于提取精細(xì)化的路網(wǎng)。因此首先對軌跡點進(jìn)行預(yù)處理，剔除離散及異常軌跡點，并對轉(zhuǎn)彎路口稀疏的軌跡點進(jìn)行一定程度的加密；其次，分離道路上不同行駛方向的軌跡點；最后基于偏移之后的軌跡點提取道路網(wǎng)。

在對原始軌跡數(shù)據(jù)進(jìn)行預(yù)處理時，引入了軌跡點集合、行駛方向角及相似軌跡點集合3個概念，其中相似軌跡點集合基于行駛方向角而定義。假定位于道路上的軌跡點周圍通常也聚集了較多行駛方向角相似的軌跡點，因此對軌跡點集合進(jìn)行遍歷，當(dāng)軌跡點周圍沒有行駛方向角相近的軌跡點時，則認(rèn)為該軌跡點位于支路上或者不位于道路上，視為離散點進(jìn)行剔除。

定義1：軌跡點集合traj，多個GPS軌跡點Pi組成的序列。其中軌跡點Pi包含移動對象的車輛ID、采樣時間、墨卡托平面直角坐標(biāo)、載客狀態(tài)等信息。

定義2：行駛方向角θ，從軌跡點Pi-1的指北方向線起依順時針方向至Pi-1和Pi+1連線間的夾角視為軌跡點Pi的行駛方向角，本文定義射線Pi-1-Pi+1方向為車輛在軌跡點Pi處的行駛方向；軌跡的起點和終點的行駛方向角則由后序和前序軌跡點共同確定。如圖1所示，軌跡起點O1和終點O5的行駛方向角分別為θ1、θ5。對應(yīng)的行駛方向分別為射線O1-O2，O4-O5方向。

定義3：相似軌跡點集Trajs，與軌跡點Pi空間位置鄰近、行駛方向角相近的軌跡點集合。

經(jīng)過預(yù)處理階段后的軌跡點大多位于道路上，但不同行駛方向的軌跡點仍然難以區(qū)分，直接對軌跡點進(jìn)行處理時無法有效地分離軌跡點的方向，再引入影響權(quán)重和軌跡點偏移距離兩個概念，提出軌跡點偏移策略分離不同行駛方向的軌跡點，近似認(rèn)為行駛在道路上的車輛隨機分布于道路中心線的兩側(cè)，假設(shè)每個軌跡點都會受到周圍與其具有相近行駛方向軌跡點的吸引力的作用，使其具有向相似軌跡點移動的趨勢，綜合軌跡點受到的所有吸引力作用，將受到的吸引力作用轉(zhuǎn)化為移動的距離和方向。為了保證基于偏移后的軌跡點所提取的路網(wǎng)仍然與道路中心線吻合，對軌跡點偏移時，區(qū)分偏移的方向，使得道路兩側(cè)的軌跡點向道路中間移動，而位于道路中間區(qū)域的軌跡點同時受到兩側(cè)軌跡點的吸引力大致相等并不移動，以此實現(xiàn)不同行駛方向軌跡點的分離。

在經(jīng)過軌跡集聚之后，軌跡點能夠按照行駛方向和空間位置集聚到相應(yīng)的道路中心線附近，路網(wǎng)的輪廓已經(jīng)非常的清晰，最后采用柵格化的方法提取道路網(wǎng)。

定義4：影響權(quán)重ωs，為模擬相似軌跡點產(chǎn)生的引力作用，用來反映軌跡點Pi受到相似軌跡點集合Trajs中軌跡點Ps影響大小的因子。權(quán)重與距離呈負(fù)相關(guān)，距離越遠(yuǎn)，影響權(quán)重越小，具體計算公式如下

(1)

式中，ωs為相似軌跡點Ps對Pi的影響權(quán)重；ds是Pi和Ps的歐氏距離；k為常數(shù)。

定義5，軌跡點偏移距離Δdi：軌跡點Pi在受到相似軌跡點集合吸引力作用下，垂直行駛方向移動的距離，如圖1所示。

圖1 軌跡點行駛方向角示意Fig.1 Schematic diagram of the direction of travel of the track point

2 軌跡集聚和道路網(wǎng)提取方法

出租車行駛過程中絕大部分軌跡點位于道路上，同一條道路上不同車輛的軌跡具有空間位置臨近，行駛方向相近的特點。鑒于此，本文提出的軌跡集聚和精細(xì)化路網(wǎng)提取方法，主要分為軌跡預(yù)處理、軌跡集聚和路網(wǎng)提取3部分，如圖2所示。

軌跡點預(yù)處理：通過判斷軌跡點是否存在相似軌跡點集合的方法，識別載客軌跡數(shù)據(jù)中的異常和離散點；為提高交叉路口區(qū)域軌跡集聚的水平，在預(yù)處理時對軌跡段按固定步長進(jìn)行加密處理。

軌跡集聚：首先計算所有軌跡點的行駛方向角，然后顧及位置和行駛方向獲取相似軌跡點集合，計算每個相似軌跡點產(chǎn)生的偏移距離，并按偏移方向求和取平均得到待偏移軌跡點的偏移距離，當(dāng)所有軌跡點的平均偏移距離大于閾值時，以偏移后的坐標(biāo)重新計算軌跡點的行駛方向角，直至平均偏移距離小于閾值。

圖2 軌跡集聚和道路網(wǎng)提取方法Fig.2 Trajectory agglomeration and road network extraction method

精細(xì)化路網(wǎng)提取：基于軌跡集聚的結(jié)果，剔除未集聚的軌跡點后得到能夠反映道路結(jié)構(gòu)的軌跡數(shù)據(jù)，然后運用柵格數(shù)字化的方法提取道路網(wǎng)。

2.1 軌跡數(shù)據(jù)預(yù)處理

(1) 篩選載客軌跡。在出租車實際運營過程中，載客狀態(tài)下的出租車通常以接近交通流的速度在快速車道上行駛，其軌跡與真實路網(wǎng)重合度較高，而車輛空載時由于受到尋找客源或停車等因素的影響，車輛通常在慢車道以較為緩慢的速度行駛，存在因停車造成的局部區(qū)域軌跡點聚集明顯和軌跡偏離路網(wǎng)等問題。為提高路網(wǎng)提取精度，本文根據(jù)出租車原始軌跡數(shù)據(jù)中的載客狀態(tài)信息，篩選載客數(shù)據(jù)作為路網(wǎng)提取的數(shù)據(jù)源。

(2) 剔除離散軌跡點。對于周圍沒有相似軌跡點的離散點，在集聚過程中坐標(biāo)并不會發(fā)生偏移，為提高軌跡點集聚的效率，在預(yù)處理階段剔除離散軌跡點。離散軌跡點的識別通過判斷軌跡點是否存在相似軌跡點集來實現(xiàn)，若無則視為離散點進(jìn)行剔除，相似軌跡點集合的具體獲取方法見2.2.1節(jié)。

(3) 加密軌跡點。由于出租軌跡的采樣頻率限制，將軌跡點連接得到的軌跡線與道路真實的幾何形態(tài)通常存在較大差異，尤其在交叉路口和道路轉(zhuǎn)向區(qū)域更為明顯。為提高軌跡集聚水平，本文提出對軌跡段進(jìn)行軌跡點加密處理。加密的具體方法為線性加密，軌跡點加密數(shù)量由相鄰兩軌跡點間的歐氏距離與加密步長確定，當(dāng)相鄰兩軌跡點的距離小于加密步長，則加密點數(shù)量為零。

2.2 顧及位置和行駛方向的軌跡集聚

軌跡集聚的本質(zhì)是通過軌跡點的迭代偏移使得同一條道路上相同行駛方向的軌跡匯集在一起。在對軌跡點進(jìn)行偏移時，首先獲取待偏移軌跡點的相似軌跡點集合，然后根據(jù)相似軌跡點的空間位置計算待偏移軌跡點的偏移距離，偏移過程中只分析待偏移軌跡點受到相似軌跡點的影響所產(chǎn)生的偏移距離，其余軌跡點的位置保持不變，直至軌跡點集合完成一次遍歷；當(dāng)所有軌跡點平均偏移距離低于設(shè)定的閾值時，則認(rèn)為軌跡已經(jīng)實現(xiàn)集聚，反之基于軌跡點偏移之后的坐標(biāo)重新計算每個軌跡點的行駛方向角，重復(fù)以上步驟繼續(xù)對軌跡點進(jìn)行偏移，直至完成軌跡集聚。軌跡點偏移的具體步驟如下(圖3)：

(1) 計算所有軌跡點的行駛方向角。

(2) 遍歷軌跡點集合，獲取待偏移軌跡點Pi的相似軌跡點集合。

(3) 遍歷相似軌跡點集合中的所有軌跡點，計算待偏移軌跡點Pi的偏移距離Δdi和偏移后的坐標(biāo)。

(4) 直至軌跡點集合完成遍歷，更新偏移后的坐標(biāo)為當(dāng)前坐標(biāo)，計算所有軌跡點的平均偏移距離Δd。

(5) 若Δd大于設(shè)定的閾值，則重復(fù)步驟(1)—(4)，反之完成軌跡點的集聚。

圖3 軌跡點偏移流程Fig.3 Track point offset flowchart

2.2.1 相似軌跡點集獲取

本文顧及行駛方向角和空間位置獲取相似軌跡點集，目的在于篩選出與待偏移軌跡點位于同一條道路上具有相同行駛方向的軌跡點，用于軌跡點偏移計算。獲取相似軌跡點集合時，引入行駛方向角替代軌跡點方位角作為篩選條件，是由于基于行駛方向角篩選得到的相似軌跡點集合能更好地提高軌跡點集聚的精度。一方面降低軌跡點因定位不準(zhǔn)導(dǎo)致該點方位角與實際方位角存在偏差所造成的誤差；另一方面能提升不同道路車流并入時的軌跡集聚效果，如圖4所示，圖4(a)為采用軌跡點的方位角進(jìn)行集聚的效果，在道路交匯處軌跡集聚效果差，圖4(b)為本文引入行駛方向角集聚的效果，能很好地將軌跡點按道路行駛方向分別進(jìn)行集聚。

圖4 引入行駛方向角進(jìn)行軌跡點偏移Fig.4 Introduce the direction of travel angle to offset the track point

為提高獲取相似軌跡點集的效率，本文首先將研究區(qū)域劃分為ρ×ρm的網(wǎng)格單元，ρ為獲取相似軌跡點時定義的距離閾值，根據(jù)網(wǎng)格的頂點坐標(biāo)為網(wǎng)格進(jìn)行唯一編號，將同一個網(wǎng)格內(nèi)的軌跡點集中存儲并與其所在網(wǎng)格的編號進(jìn)行關(guān)聯(lián)。遍歷軌跡點集合中的軌跡點時，根據(jù)坐標(biāo)確定待偏移軌跡點所在的網(wǎng)格編號，遍歷以該網(wǎng)格為中心的九宮格所包含的所有軌跡點，依次計算與待偏移軌跡點行駛方向角差值和距離， 篩選出符合限制條件的相似軌跡點集。若軌跡點所在網(wǎng)格位于研究區(qū)域最外層，則遍歷研究區(qū)域內(nèi)與該網(wǎng)格相鄰網(wǎng)格內(nèi)的軌跡點，其余步驟相同。

2.2.2 軌跡點偏移計算

由于同一條道路上的軌跡通常近乎平行分布，軌跡點偏移時限制軌跡點僅垂直行駛方向偏移能夠縮短軌跡集聚的時間；同時軌跡點并非均勻分布，即使是同一條軌跡的前后相鄰軌跡點，其相似軌跡點集合也可能存在很大差異，如果允許軌跡點沿著行駛方向偏移，可能改變相鄰軌跡點在道路上的位置順序，影響軌跡點集合下一次迭代偏移，反復(fù)迭代容易造成誤差累積。因此在對軌跡點進(jìn)行偏移計算時，本文提出軌跡點僅垂直車輛行駛方向偏移。

為便于分析待偏移軌跡點受到周圍相似軌跡點的引力作用，每次都以待偏移軌跡點為原點建立平面直角坐標(biāo)系，如圖5所示，以軌跡點O3為原點，平行于O3的行駛方向(射線O2O4方向)作為y軸的正方向，與行駛方向順時針成90°的方向作為x軸正方向建立平面直角坐標(biāo)系Oxy，軌跡起始點O1、O5的Oxy坐標(biāo)系建立方式同理，以軌跡點為原點，行駛方向為y軸正方向，如圖5所示。基于以待偏移軌跡點為原點的Oxy坐標(biāo)系，計算出相似軌跡點在Oxy坐標(biāo)系下的x、y軸坐標(biāo)

(2)

圖5 軌跡點偏移計算Fig.5 Schematic diagram of track point offset calculation

根據(jù)相似軌跡點與待偏移軌跡點的距離、影響權(quán)重以及在Oxy坐標(biāo)系下的x軸坐標(biāo)，求解待偏移軌跡點的偏移距離Δdi

(3)

基于軌跡點在Oxy坐標(biāo)系下沿x軸的偏移距離Δdi，轉(zhuǎn)換得到軌跡點偏移后在投影坐標(biāo)系下的坐標(biāo)，計算公式如下

(4)

當(dāng)所有軌跡點完成一次偏移計算后，將偏移后的坐標(biāo)更新為軌跡點當(dāng)前坐標(biāo)，并計算所有軌跡點偏移距離的平均值Δd。若Δd大于預(yù)先設(shè)定的閾值δ，則以偏移后的坐標(biāo)重新計算軌跡點的行駛方向角θ，繼續(xù)迭代偏移；反之認(rèn)為軌跡點集聚完成，結(jié)束偏移。

2.3 精細(xì)化路網(wǎng)提取

(1) 剔除未集聚的軌跡點。經(jīng)過軌跡點偏移后，絕大多數(shù)位于同一條道路上的軌跡能完成集聚，但部分軌跡點的相似軌跡點集合數(shù)量較少，使得反復(fù)迭代過程中軌跡點的偏移距離很小，導(dǎo)致部分軌跡點無法完全集聚。為提高交叉路口路網(wǎng)信息的提取精度，需要識別出未完全集聚的軌跡點并進(jìn)行剔除。考慮到軌跡集聚之后位于同一條道路上的軌跡點間隔非常近，本文通過遍歷軌跡點集合，判斷軌跡點周圍是否存在相似軌跡點來識別未集聚的軌跡點，將識別出的未集聚軌跡點進(jìn)行剔除。判斷是否存在相似軌跡點集的方法見2.2.1節(jié)，與預(yù)處理階段的區(qū)別在于距離和角度閾值的不同。

(2) 柵格化提取道路網(wǎng)。將剔除未集聚軌跡點之后的軌跡點集合按車輛ID和采樣的時間順序連成軌跡線，接著對每條軌跡線作距離為γ的緩沖區(qū)，并融合為單部件的面要素。由于局部道路軌跡稀疏，當(dāng)軌跡間的最大距離超過緩沖區(qū)半徑γ的2倍時，道路緩沖區(qū)融合后的面要素容易在道路內(nèi)部形成孔洞，進(jìn)行二值化之前需要根據(jù)孔洞的面積設(shè)定閾值填充孔洞。最后利用ArcScan工具提取道路中心線，剔除距離過短的線段和懸掛線，提取得到精細(xì)化的雙線路網(wǎng)信息。

3 試驗與分析

3.1 數(shù)據(jù)與試驗環(huán)境

本文以福州市鼓山高架橋附近的道路作為試驗路段(圖6)，該區(qū)域道路網(wǎng)交錯，包含較多的轉(zhuǎn)彎路口，能很好地驗證方法的有效性。試驗數(shù)據(jù)選用福州市2015年5月22日至5月30日的出租車軌跡數(shù)據(jù)，采樣頻率在10～30 s之間，軌跡數(shù)據(jù)包括車輛ID、采樣時間、投影坐標(biāo)系下的XY坐標(biāo)及載客狀態(tài)信息，共計39 087個軌跡點，1959條軌跡。本試驗在普通PC(Intel Core i5/CPU 3.20 GHz/8 G/Win10)環(huán)境下，基于ArcGIS 10.3平臺、JAVA編程語言進(jìn)行軌跡集聚和路網(wǎng)提取試驗。

3.2 試驗參數(shù)選取

3.2.1 數(shù)據(jù)預(yù)處理參數(shù)的確定

預(yù)處理階段，需要確定獲取相似軌跡點的距離、行駛方向角閾值及加密步長。具體思路是首先分析軌跡數(shù)據(jù)，結(jié)合試驗區(qū)域內(nèi)的道路幾何特征確定閾值范圍，而后選取不同參數(shù)進(jìn)行試驗，綜合路網(wǎng)提取效果和算法運行效率確定具體的閾值。

考慮到選取的試驗區(qū)域存在快速路和高架橋道路重疊，道路寬度從4～20 m不等，本文分別選取5 m、10 m、15 m、20 m作為相似軌跡點篩選的距離閾值進(jìn)行軌跡集聚試驗，結(jié)果表明過小的距離閾值容易剔除道路邊緣的軌跡點，距離閾值過大則無法有效剔除離散點，當(dāng)距離閾值為15 m時，能很好地分離不同道路上的軌跡；軌跡集聚后道路交匯處的位置精度則與行駛方向角閾值的選取密切相關(guān)，行駛方向角閾值過小造成道路交匯的位置提前，過大導(dǎo)致道路交匯的位置延后。由于試驗區(qū)域涉及不同類型、不同級別的道路交匯，本文分別以2.5°、5°、7.5°、10°作為行駛方向角閾值進(jìn)行軌跡集聚試驗，結(jié)果表明，行駛方向角閾值設(shè)置為5°時，軌跡集聚得到的道路交叉口與真實位置較為接近。因此預(yù)處理時獲取相似軌跡點集合的距離閾值設(shè)為15 m，行駛方向角閾值設(shè)為5°。

試驗數(shù)據(jù)的軌跡段間隔通常在80～120 m之間，為使得軌跡集聚后道路轉(zhuǎn)彎處盡可能的平滑，本文分選取5 m、10 m、15 m、20 m作為加密步長進(jìn)行試驗，其中步長為5 m和10 m時，交叉路口處的軌跡集聚效果良好，但步長為5 m時，加密后的軌跡點數(shù)量過大導(dǎo)致軌跡集聚時間延長，步長大于15 m時在局部轉(zhuǎn)彎角度較小區(qū)域軌跡集聚并不理想。因此本文選取10 m作為步長對軌跡段進(jìn)行加密。

3.2.2 軌跡集聚參數(shù)的選取

軌跡集聚過程中相似軌跡點獲取參數(shù)同預(yù)處理時剔除離散軌跡點的參數(shù)，以下分別討論影響權(quán)重常數(shù)k和偏移距離閾值的選取。

最佳的影響權(quán)重常數(shù)k應(yīng)當(dāng)使軌跡點的偏移符合由外向內(nèi)逐漸集聚的趨勢。本文分別對影響權(quán)重常數(shù)0.25、0.5、0.75進(jìn)行了軌跡集聚試驗，限定迭代次數(shù)為100次，結(jié)果顯示影響權(quán)重常數(shù)過大將導(dǎo)致軌跡點偏移過遠(yuǎn)，無法完成軌跡集聚；過小使得軌跡點每次偏移距離過小，迭代終止時尚未完成軌跡集聚；k為0.5時，軌跡集聚效果良好，因此本文選取影響權(quán)重常數(shù)為0.5。

在軌跡點的迭代偏移過程中，隨著軌跡集聚水平的提高，軌跡點的平均偏移距離將越來越小。若設(shè)置的偏移距離閾值過低會導(dǎo)致偏移的迭代時間過長，但集聚水平無明顯提升；過高容易造成迭代循環(huán)過早結(jié)束，影響軌跡集聚效果。經(jīng)試驗，偏移距離閾值小于0.005 m時，軌跡集聚速度下降，效果無明顯提升，因此設(shè)定偏移距離閾值為0.005 m時，在迭代時間與集聚效果之間能取得較好的平衡。

3.2.3 路網(wǎng)提取參數(shù)的確定

路網(wǎng)提取過程中，需要確定獲取相似軌跡點的閾值參數(shù)以及緩沖區(qū)半徑：

(1) 剔除未集聚的軌跡點時，道路上相同行駛方向的軌跡線在集聚后寬度通常在10 cm以內(nèi)，因此本文選取篩選相似軌跡點集合的距離閾值為1 m，行駛方向角度閾值為5°，確保軌跡稀疏路段上的軌跡點不被視為未完成集聚的軌跡點。

(2) 在運用柵格化方法提取路網(wǎng)時，為保證道路交叉路口的路網(wǎng)提取質(zhì)量，要求緩沖區(qū)半徑盡量的小，使得交叉路口的緩沖區(qū)面積不會過大。

經(jīng)試驗，半徑選取為0.1 m時，能很好地減少同一條道路上軌跡間因軌跡線稀疏融合緩沖區(qū)時形成的孔洞。

3.3 結(jié)果分析

采用上述選取的參數(shù)，利用福州市軌跡數(shù)據(jù)進(jìn)行軌跡集聚和道路網(wǎng)提取試驗。試驗結(jié)果如圖6所示。

圖6 軌跡點預(yù)處理、軌跡集聚和路網(wǎng)提取結(jié)果Fig.6 Trajectory point preprocessing, trajectory agglomeration and network extraction results

經(jīng)軌跡集聚后，將軌跡點按車輛ID和時間連成軌跡線，得到的軌跡線已基本能夠反映道路網(wǎng)結(jié)構(gòu)，但仍存在部分軌跡點未完全集聚，在剔除這部分軌跡點之后，結(jié)果如圖7所示，圖7(b)、(c)中不同類型道路交叉口的轉(zhuǎn)向關(guān)系完成提取，能清晰反映道路間的連通情況；圖7(d)、(e)中局部區(qū)域的軌跡未完全集聚到一起，這是軌跡采樣頻率不高，車輛在轉(zhuǎn)向時軌跡點過少所導(dǎo)致的。

為定性評價本文方法提取的路網(wǎng)，首先與試驗區(qū)域的谷歌衛(wèi)星影像疊加對比，如圖8所示，道路上相同行駛方向的軌跡已完成集聚，與谷歌衛(wèi)星影像上的道路重合良好，基本完全落在衛(wèi)星影像的道路范圍內(nèi)，交叉路口區(qū)域軌跡集聚后能夠反映真實的車輛行駛路徑。

圖7 軌跡集聚后部分交叉路口細(xì)節(jié) Fig.7 After trajectory agglomeration partial intersection details

圖8 集聚后的軌跡與Google衛(wèi)星影像疊加結(jié)果(紅色實線為本文提取路網(wǎng))Fig.8 Accumulated trails and Google satellite image overlay results(red solid line extracts for this article)

本文提取的路網(wǎng)結(jié)果與OSM路網(wǎng)疊加如圖9所示，紅色實線為本文方法提取的路網(wǎng)，黑色為OSM矢量路網(wǎng)，兩者整體上基本重合。OSM路網(wǎng)在交叉路口通過人為干預(yù)處理，以道路相交代表復(fù)雜的轉(zhuǎn)向，難以反映道路間的真實連接關(guān)系。與OSM路網(wǎng)相比，本文提取的路網(wǎng)在交叉路口信息更為精細(xì)，能反映道路的具體轉(zhuǎn)向關(guān)系，如圖9(b)—(c)所示。同時本文提取得到的路網(wǎng)數(shù)據(jù)要比OSM路網(wǎng)數(shù)據(jù)更詳細(xì)，由于OSM路網(wǎng)未及時更新路網(wǎng)變化信息，在局部區(qū)域缺少新增道路以及部分無效路段未及時刪除， 而本文提取的路網(wǎng)具有更為合理的路段連通關(guān)系，不存在孤立的路段以及較少的懸掛線，如圖9(d)—(e)所示。

圖9 本文提取的路網(wǎng)與OSM路網(wǎng)疊加結(jié)果(紅色實線為本文提取路網(wǎng)，黑色為OSM矢量路網(wǎng))Fig.9 Road network extraction results and OSM road network overlay results(red solid line extracts for this article, black means OSM vector road network)

3.4 精度評價

為定量評價本文方法、文獻(xiàn)[14]及文獻(xiàn)[24]3種提取路網(wǎng)方法的精度，本文采取文獻(xiàn)[25]提出的基于線要素緩沖區(qū)的相似度計算方法進(jìn)行評價。該方法以標(biāo)準(zhǔn)矢量數(shù)據(jù)為基準(zhǔn)作不同距離的緩沖區(qū)，通過計算待評價線要素與緩沖區(qū)相交的長度占總長度的百分比來評價不同緩沖區(qū)半徑下的精度。本文以試驗區(qū)域內(nèi)的OSM矢量路網(wǎng)為標(biāo)準(zhǔn)數(shù)據(jù)，分別做2 m、5 m、7 m的緩沖區(qū)，比較3種方法提取得到路網(wǎng)的精度，評價結(jié)果如圖10所示。文獻(xiàn)[14]通過構(gòu)建軌跡點Delunay三角網(wǎng)提取得到的路網(wǎng)為單線形式，本文方法提取結(jié)果為雙線路網(wǎng)，交叉路口信息完整，能夠更加真實地反映道路轉(zhuǎn)向關(guān)系；隨著緩沖區(qū)半徑的增大，本文方法所提路網(wǎng)的精度有明顯提高，緩沖區(qū)距離為7 m時本文方法優(yōu)于文獻(xiàn)[14]結(jié)果，在不同緩沖區(qū)半徑下，本文提取的路網(wǎng)精度與文獻(xiàn)[24]結(jié)果相比都有明顯的提高；試驗區(qū)域內(nèi)OSM矢量路網(wǎng)總長度為33 666.2 m，本文方法提取得到的路網(wǎng)總長度為33 727.5 m，整體上與OSM路網(wǎng)幾乎完全重疊。OSM矢量路網(wǎng)在復(fù)雜交叉路口進(jìn)行了概要處理，而本文提取的交叉路口轉(zhuǎn)向關(guān)系基于車輛行駛軌跡，反映的是車輛轉(zhuǎn)向時的真實行駛路徑。

圖10 精度評價Fig.10 Accuracy evaluation

4 結(jié) 論

本文提出一種通過偏移軌跡點實現(xiàn)軌跡集聚和路網(wǎng)提取方法，以福州市出租車軌跡數(shù)據(jù)進(jìn)行了軌跡集聚和路網(wǎng)提取試驗，結(jié)果表明該方法能對道路網(wǎng)及交叉路口轉(zhuǎn)向信息實現(xiàn)精細(xì)化的提取，為精細(xì)化路網(wǎng)信息提取提供了新的方法。本文方法與已有的路網(wǎng)提取算法相比，具有以下3個特點：

(1) 本文方法受研究區(qū)域內(nèi)路網(wǎng)幾何特征形態(tài)影響小，能夠完成路網(wǎng)精細(xì)幾何特征和道路中心線級別交叉口結(jié)構(gòu)的同時提取；

(2) 方法同時顧及軌跡點的空間位置和行駛方向，能夠?qū)崿F(xiàn)復(fù)雜立交區(qū)域的道路提取，嚴(yán)格區(qū)分空間位置臨近但行駛方向存在差異的路段;

(3) 基于軌跡集聚后的結(jié)果，運用柵格化方法提取得到的道路網(wǎng)能夠反映復(fù)雜交叉路口區(qū)域道路的精細(xì)轉(zhuǎn)向關(guān)系，可及時發(fā)現(xiàn)道路變化情況，為路網(wǎng)信息更新提供幫助。

由于原始軌跡中缺乏高程數(shù)據(jù)，筆者并沒有精細(xì)化識別上下層道路重疊的路段，后續(xù)將繼續(xù)完善精細(xì)化路網(wǎng)提取方法，嘗試?yán)贸鲎廛嘒PS數(shù)據(jù)識別道路網(wǎng)中的上下層路段，進(jìn)一步提高精細(xì)化路網(wǎng)提取的精度。