鄔群勇，吳祖飛，張良盼

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

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

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

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

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

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

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

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

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

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

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

在對(duì)原始軌跡數(shù)據(jù)進(jìn)行預(yù)處理時(shí)，引入了軌跡點(diǎn)集合、行駛方向角及相似軌跡點(diǎn)集合3個(gè)概念，其中相似軌跡點(diǎn)集合基于行駛方向角而定義。假定位于道路上的軌跡點(diǎn)周?chē)ǔＲ簿奂溯^多行駛方向角相似的軌跡點(diǎn)，因此對(duì)軌跡點(diǎn)集合進(jìn)行遍歷，當(dāng)軌跡點(diǎn)周?chē)鷽](méi)有行駛方向角相近的軌跡點(diǎn)時(shí)，則認(rèn)為該軌跡點(diǎn)位于支路上或者不位于道路上，視為離散點(diǎn)進(jìn)行剔除。

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

定義2：行駛方向角θ，從軌跡點(diǎn)Pi-1的指北方向線(xiàn)起依順時(shí)針?lè)较蛑罰i-1和Pi+1連線(xiàn)間的夾角視為軌跡點(diǎn)Pi的行駛方向角，本文定義射線(xiàn)Pi-1-Pi+1方向?yàn)檐?chē)輛在軌跡點(diǎn)Pi處的行駛方向；軌跡的起點(diǎn)和終點(diǎn)的行駛方向角則由后序和前序軌跡點(diǎn)共同確定。如圖1所示，軌跡起點(diǎn)O1和終點(diǎn)O5的行駛方向角分別為θ1、θ5。對(duì)應(yīng)的行駛方向分別為射線(xiàn)O1-O2，O4-O5方向。

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) 計(jì)算所有軌跡點(diǎn)的行駛方向角。

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

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

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

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

圖3 軌跡點(diǎn)偏移流程Fig.3 Track point offset flowchart

2.2.1 相似軌跡點(diǎn)集獲取

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

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

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

2.2.2 軌跡點(diǎn)偏移計(jì)算

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

為便于分析待偏移軌跡點(diǎn)受到周?chē)嗨栖壽E點(diǎn)的引力作用，每次都以待偏移軌跡點(diǎn)為原點(diǎn)建立平面直角坐標(biāo)系，如圖5所示，以軌跡點(diǎn)O3為原點(diǎn)，平行于O3的行駛方向(射線(xiàn)O2O4方向)作為y軸的正方向，與行駛方向順時(shí)針成90°的方向作為x軸正方向建立平面直角坐標(biāo)系Oxy，軌跡起始點(diǎn)O1、O5的Oxy坐標(biāo)系建立方式同理，以軌跡點(diǎn)為原點(diǎn)，行駛方向?yàn)閥軸正方向，如圖5所示?；谝源栖壽E點(diǎn)為原點(diǎn)的Oxy坐標(biāo)系，計(jì)算出相似軌跡點(diǎn)在Oxy坐標(biāo)系下的x、y軸坐標(biāo)

(2)

圖5 軌跡點(diǎn)偏移計(jì)算Fig.5 Schematic diagram of track point offset calculation

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

(3)

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

(4)

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

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

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

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

3 試驗(yàn)與分析

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

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

3.2 試驗(yàn)參數(shù)選取

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 結(jié)果分析

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

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

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

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

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

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

圖9 本文提取的路網(wǎng)與OSM路網(wǎng)疊加結(jié)果(紅色實(shí)線(xiàn)為本文提取路網(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 精度評(píng)價(jià)

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

圖10 精度評(píng)價(jià)Fig.10 Accuracy evaluation

4 結(jié) 論

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

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

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

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

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