基于出租車軌跡的可導(dǎo)航路網(wǎng)構(gòu)建

張彩麗，向隆剛，李雅麗，王文龍

1. 武漢大學(xué)測繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430079； 2. 邵陽學(xué)院城鄉(xiāng)建設(shè)學(xué)院，湖南 邵陽 422000； 3. 國網(wǎng)思極神往位置服務(wù)(北京)有限公司，北京 100000

道路網(wǎng)絡(luò)作為智慧城市發(fā)展的重要基礎(chǔ)條件，不僅需要交叉口與路段來表達(dá)幾何與拓?fù)湫畔?，而且需要?dǎo)航信息來承載道路連接語義，從而支撐大規(guī)模車輛在道路網(wǎng)絡(luò)中的有序流動(dòng)。傳統(tǒng)路網(wǎng)信息獲取主要依靠野外測量及遙感影像處理[1]，不僅時(shí)間長、成本高、現(xiàn)勢(shì)性差，還難以獲得道路的轉(zhuǎn)向、單雙向等導(dǎo)航信息。隨著便攜式定位設(shè)備的普及，利用成本低、覆蓋廣，易于獲取，現(xiàn)勢(shì)性強(qiáng)，蘊(yùn)含豐富道路語義信息[2]的出租車軌跡數(shù)據(jù)開展可導(dǎo)航路網(wǎng)構(gòu)建成為可能。然而，一方面，出租車軌跡數(shù)據(jù)噪聲大，采樣頻率低，采樣間隔不固定，另一方面，城市道路網(wǎng)具有非常復(fù)雜的空間結(jié)構(gòu)，且在轉(zhuǎn)向關(guān)系上有多種約束。從出租車軌跡中提取城市道路信息，形成可導(dǎo)航路網(wǎng)模型是一件相當(dāng)有挑戰(zhàn)性的工作。

目前，業(yè)界基于GPS軌跡數(shù)據(jù)開展了大量路網(wǎng)構(gòu)建方面的研究工作，主要集中于路網(wǎng)骨架結(jié)構(gòu)的提取，包括增量法、聚類法、柵格法，以及交叉口連接法。增量法通過逐步插入軌跡來不斷完善初始路網(wǎng)，先后提出了引力斥力模型[3]、加權(quán)Delaunay三角網(wǎng)[4]、信息熵[5]等方法；聚類法針對(duì)大規(guī)模軌跡點(diǎn)或軌跡段進(jìn)行聚類，然后通過擬合聚類簇或表征點(diǎn)形成路網(wǎng)，代表性方法有k-means[6-7]、DBSCAN[8-9]、OPTICS[10]等；柵格法對(duì)軌跡數(shù)據(jù)進(jìn)行柵格化處理，然后利用Voronoi分割[11]、形態(tài)學(xué)處理[12]、LDA推導(dǎo)[13]等方法進(jìn)行道路中心線提取；交叉口連接法首先利用軌跡點(diǎn)密度等隱含語義特征[14-15]，軌跡點(diǎn)方向等隱含動(dòng)力學(xué)特征[16-17]，以及道路幾何特征[18-20]等識(shí)別道路交叉口，然后提取連接交叉口[21-22]的路段信息。在路網(wǎng)導(dǎo)航信息挖掘方面，文獻(xiàn)[23]引入置信點(diǎn)概念，而文獻(xiàn)[16—17,24]考慮交叉口影響范圍內(nèi)子軌跡，通過聚類等方法分析交叉口轉(zhuǎn)向規(guī)則。上述工作大多要求高頻率、高精度的軌跡數(shù)據(jù)輸入，不能滿足低頻高噪出租車軌跡數(shù)據(jù)的路網(wǎng)構(gòu)建。

在文獻(xiàn)[2，14，20]中，基于交叉口連接特征及出租車軌跡密度特征，設(shè)計(jì)了一種交叉口優(yōu)先的城市路網(wǎng)生成方法。首先通過結(jié)合數(shù)學(xué)形態(tài)學(xué)處理與密度峰值聚類(CFDP)[25-26]，開展矢柵融合的交叉口識(shí)別；然后據(jù)此對(duì)形態(tài)學(xué)方法生成骨架線進(jìn)行位置調(diào)整及斷裂修復(fù)，在一定程度上解決了從低質(zhì)量出租車軌跡提取交叉口及其關(guān)聯(lián)路段的問題。由于城市路網(wǎng)的復(fù)雜性，仍然有大量未識(shí)別和錯(cuò)提取的現(xiàn)象。為此，本文一方面致力于交叉口及其路段的全面精確識(shí)別；另一方面著眼于轉(zhuǎn)向等導(dǎo)航信息的提取，從而構(gòu)建出面向城市的可導(dǎo)航路網(wǎng)結(jié)構(gòu)。具體而言，考慮到交叉口的連接本質(zhì)，采用“交叉口位置—路段幾何—導(dǎo)航屬性”的研究思路(圖1)。首先，在已有工作基礎(chǔ)上設(shè)計(jì)顧及多模特征的交叉口集成識(shí)別方法及零樣本監(jiān)督式去偽策略；然后，考慮Delaunay三角網(wǎng)鄰接特征，軌跡分布特征及道路幾何特征，識(shí)別交叉口之間的拓?fù)潢P(guān)系，并融合形態(tài)學(xué)結(jié)果生成路段幾何；最后，分析出租車軌跡在交叉口處的方向與連接信息，推導(dǎo)交叉口轉(zhuǎn)向規(guī)則及路段單雙向?qū)傩?，從而?shí)現(xiàn)城市可導(dǎo)航路網(wǎng)的構(gòu)建。

圖1 可導(dǎo)航路網(wǎng)構(gòu)建流程Fig.1 Navigable road network construction

1 交叉口位置探測

作為路網(wǎng)結(jié)構(gòu)提取及導(dǎo)航屬性分析的首要環(huán)節(jié)，交叉口識(shí)別的全面性與準(zhǔn)確度直接影響可導(dǎo)航路網(wǎng)的生成質(zhì)量。為此，本文分析與挖掘出租車軌跡在矢柵空間關(guān)于交叉口的多模特征，設(shè)計(jì)道路交叉口的集成識(shí)別技術(shù)，提出基于隨機(jī)森林方法的零標(biāo)注監(jiān)督式分類，實(shí)現(xiàn)待定交叉口的去偽留真。具體技術(shù)流程如圖2所示。

圖2 交叉口識(shí)別流程Fig.2 Road intersection recognition

1.1 交叉口多模特征分析

由于交叉口處紅綠燈限制、兩條以上道路實(shí)體交匯銜接以及行駛車道變更轉(zhuǎn)換，出租車經(jīng)過時(shí)往往發(fā)生停留、轉(zhuǎn)向等行為，不僅形成不同于其他區(qū)域的軌跡點(diǎn)密度、行進(jìn)方向及速度等低階特征，還呈現(xiàn)出交叉口拓?fù)溥B接、方向多樣性、反向交匯點(diǎn)密度、主成分比[14]、轉(zhuǎn)向聚類個(gè)數(shù)等高階特征。這些多模多階特征形成了關(guān)于交叉口的高判別性互補(bǔ)特征集，可作為識(shí)別交叉口的基礎(chǔ)與依據(jù)?？紤]到不同特征在矢量空間和柵格空間計(jì)算互補(bǔ)優(yōu)勢(shì)，本文選擇軌跡點(diǎn)密度、拓?fù)溥B接、反向交匯點(diǎn)密度等柵格空間特征進(jìn)行交叉口集成提取與融合，其他矢量空間特征用于零標(biāo)注監(jiān)督式去偽。具體特征設(shè)計(jì)如下。

1.1.1 軌跡點(diǎn)密度特征fP

為消除噪聲軌跡點(diǎn)影響，本文將軌跡數(shù)據(jù)進(jìn)行格網(wǎng)化，以核密度代替單位面積內(nèi)軌跡點(diǎn)個(gè)數(shù)來表征軌跡分布情況。給定搜索半徑h，柵格單元的核密度估計(jì)可基于K函數(shù)[16]進(jìn)行計(jì)算，可以看到高密度區(qū)域總是分布在交叉口周圍，如圖3(a)所示。

1.1.2 拓?fù)溥B接特征fN

設(shè)置合適閾值k，從上述軌跡核密度分布圖中提取高密度區(qū)域，對(duì)其進(jìn)行形態(tài)學(xué)細(xì)化，8鄰域內(nèi)像素點(diǎn)個(gè)數(shù)刻畫了道路不同區(qū)域的連接特征，如圖3(b)所示。

1.1.3 反向交匯點(diǎn)密度fT

基于文獻(xiàn)[26]提出的反向交匯點(diǎn)(圖3(c))，進(jìn)一步進(jìn)行核密度分析(圖3(d))可加強(qiáng)交叉口表征特性?？紤]到彎道段上距離較遠(yuǎn)轉(zhuǎn)向點(diǎn)對(duì)反向交匯點(diǎn)會(huì)落在道路外，本文基于轉(zhuǎn)向點(diǎn)對(duì)距離統(tǒng)計(jì)直方圖(圖3(e))，對(duì)轉(zhuǎn)向點(diǎn)對(duì)距離d進(jìn)行限制，限制后轉(zhuǎn)向點(diǎn)對(duì)基本分布于交叉口周邊(圖3(g))。

1.1.4 方向多樣性fH

與路段相比，交叉口的車輛行駛方向更加多樣化。給定搜索半徑h，每隔30°對(duì)0°～360°進(jìn)行劃分，計(jì)算每個(gè)方向間隔內(nèi)軌跡點(diǎn)數(shù)Ni占落入搜索半徑h內(nèi)總軌跡點(diǎn)數(shù)N的比例，利用辛普森多樣性指數(shù)(式(1))即可統(tǒng)計(jì)路網(wǎng)不同區(qū)域軌跡點(diǎn)方向多樣性

fH(Ni,N)=1-∑(Ni/N)2

(1)

1.1.5 轉(zhuǎn)向聚類個(gè)數(shù)fC

由于路段的通行特性，一般不會(huì)像交叉口處一樣發(fā)生大量轉(zhuǎn)向，因此以某點(diǎn)為中心，搜索h范圍內(nèi)反向交匯點(diǎn)(圖3(f)中的紅色五角星)，進(jìn)而反推轉(zhuǎn)向點(diǎn)對(duì)TP(如(P1,P2)(P3,P4))，基于轉(zhuǎn)向點(diǎn)對(duì)起始與終止方向進(jìn)行層次聚類，并統(tǒng)計(jì)轉(zhuǎn)向點(diǎn)方向聚類個(gè)數(shù)，即可有效區(qū)分交叉口與其他區(qū)域。

1.1.6 主成分比fΔ

由于交叉口連接多個(gè)路段，軌跡點(diǎn)在交叉口分布時(shí)一般呈現(xiàn)非線性特性，如圖3(h)所示。以某點(diǎn)為中心，截取一定范圍h內(nèi)軌跡點(diǎn)，以軌跡點(diǎn)集合的x和y坐標(biāo)為變量，構(gòu)造協(xié)方差矩陣，計(jì)算特征值λ1和λ2，基于式(2)即可判斷軌跡點(diǎn)分布特征，值越小非線性特征越強(qiáng)，越有可能為交叉口

圖3 交叉口多模特征示例Fig.3 The illustration of multi-mode features for road intersection

fΔ(λ1,λ2)=[max(λ1,λ2)-min(λ1,λ2))/

max(λ1,λ2)]

(2)

1.1.7 速度特征

車輛經(jīng)過交叉口一般需要減速，因此，軌跡點(diǎn)速度平均值fSa及速度標(biāo)準(zhǔn)差fSd也可作為區(qū)分交叉口與其他區(qū)域的有效指標(biāo)。

1.2 交叉口提取與融合

基于軌跡點(diǎn)密度特征fP或反向交匯點(diǎn)密度特征fT獲取的密度信息ρ，對(duì)高密度區(qū)域進(jìn)行局部距離δ計(jì)算，即可采用CFDP算法進(jìn)行類簇中心(道路交叉口)識(shí)別。為保證提取更多交叉口，本文僅對(duì)局部距離進(jìn)行限制[14]，基于決策圖將局部距離大于D的柵格單元識(shí)別為交叉口。特征fP、fT雖可有效識(shí)別候選交叉口，但卻無法保證交叉口的準(zhǔn)確性，因此，為獲取更高置信交叉口，本文進(jìn)一步引入交叉口連接特征fN，將8鄰域內(nèi)像素點(diǎn)個(gè)數(shù)大于2的單元識(shí)別為候選交叉口?；谔卣鱢P、fT、fN識(shí)別的候選交叉口結(jié)果設(shè)計(jì)了相應(yīng)融合機(jī)制，見表1，可有效區(qū)分真交叉口、偽交叉口及待定交叉口如圖4所示。

表1 交叉口融合規(guī)則

圖4 交叉口融合結(jié)果Fig.4 The fusion results of road intersections

1.3 零標(biāo)注監(jiān)督式去偽

考慮到基于融合規(guī)則判別的真?zhèn)谓徊婵?圖4(a))分布均勻且代表性強(qiáng)，本文隨機(jī)將真?zhèn)谓徊婵?0%作為訓(xùn)練樣本，40%作為驗(yàn)證樣本。首先利用訓(xùn)練樣本，基于隨機(jī)森林分類器對(duì)上述特征進(jìn)行重要性度量，如圖5(a)所示，優(yōu)先選擇重要性分值最高的3個(gè)特征fΔ、fH和fC；然后對(duì)fΔ、fH和fC隨機(jī)組合進(jìn)行訓(xùn)練，得到各組合訓(xùn)練的模型；利用驗(yàn)證樣本，基于各組合訓(xùn)練的模型，得到各特征子集識(shí)別準(zhǔn)確率，最終選擇識(shí)別率最高組合(fΔ、fH、fC)訓(xùn)練的模型對(duì)待定交叉口進(jìn)行零樣本監(jiān)督式去偽。與僅考慮交叉口非線性特征的主成分分析去偽方法相比，該方法既較大程度保留了真交叉口(圖5(b))，又剔除了大量偽交叉口，有效解決了監(jiān)督分類需要標(biāo)注及單特征識(shí)別精度不高等問題。為保證分類模型計(jì)算速度及精度，所有特征均進(jìn)行了min-max標(biāo)準(zhǔn)化處理。

圖5 待定交叉口去偽Fig.5 False intersection removal from undetermined results

2 路段幾何提取

任意兩交叉口之間可能有路段連接，但相距較近的交叉口之間存在路段的可能性更大?？紤]Delaunay三角網(wǎng)邊在一定程度上反映交叉口之間的鄰接信息，本文綜合軌跡點(diǎn)分布特征及道路幾何特征，融合形態(tài)學(xué)細(xì)化結(jié)果，提出一種基于Delaunay三角網(wǎng)的多階段路段生成方法，不僅有效避免了掃描所有組合而引發(fā)的計(jì)算風(fēng)暴實(shí)現(xiàn)大規(guī)模路段的高效探測，還解決了間隔較小交叉口附近路段的扭曲問題，識(shí)別了密集區(qū)域及稀疏區(qū)域路段信息，具體流程如圖6所示。

圖6 可導(dǎo)航路網(wǎng)生成流程Fig.6 Navigable road network generation

2.1 路段識(shí)別

由于Delaunay三角網(wǎng)邊緣存在許多狹長三角形，直接進(jìn)行路段提取會(huì)引入偽結(jié)果，因此本文首先迭代剔除兩公共邊角度大于135°的狹長三角形并將剩余三角形邊作為候選路段集S進(jìn)行后續(xù)多階段路段識(shí)別：

(1) 真路段軌跡點(diǎn)分布一般較為密集，因此本文首先將軌跡點(diǎn)高密度區(qū)域矢量化與候選路段集S疊加，如圖7(a)所示，保留重疊長度與其長度比值大于γ的路段，記入集合T1，可得到圖7(c)中的紅色路段。

(2) 考慮到Delaunay三角網(wǎng)的最大空?qǐng)A準(zhǔn)則及上述策略無法識(shí)別彎曲路段和研究區(qū)邊緣路段，如圖7(a)中A、B、C區(qū)域，本文將形態(tài)學(xué)骨架線矢量化并化簡，與路段集T150 m緩沖區(qū)進(jìn)行匹配，保留長度大于l的未匹配路段，如圖7(b)所示，并基于方向與距離將其延伸到相應(yīng)交叉點(diǎn)及缺失路段端點(diǎn)。完成以上3種狀況路段的補(bǔ)充，記為T2，如圖7(c)中的綠色路段。

(3) 以上得到路段集T={T1，T2}皆位于高密度區(qū)域。考慮城市相鄰道路夾角通常不會(huì)小于60°[22]，最后本文進(jìn)一步從S集中識(shí)別與路段集T具有公共結(jié)點(diǎn)，夾角大于60°，且不與其他無公共結(jié)點(diǎn)路段相交的路段，記入T3集合，結(jié)果如圖7(c)中的黃色路段。

圖7 基于Delaunay三角網(wǎng)的路段提取Fig.7 The extraction of road segment based on Delaunay triangulation network

2.2 路段擬合

T1集合與T2集合識(shí)別的路段可直接表達(dá)為該路段的幾何中心線。T3集合仍包含偽路段，且直線段不足以表達(dá)路段的幾何形狀，需進(jìn)一步判斷連接路段兩交叉口間是否存在子軌跡進(jìn)行偽路段剔除，并對(duì)識(shí)別真路段進(jìn)行分段擬合。

如果某條軌跡中一點(diǎn)Pi落在交叉口Ii影響范圍ri內(nèi)，存在另一點(diǎn)Pj落在交叉口Ij影響范圍rj內(nèi)，則表明軌跡段[Pi,Pj]為交叉口Ii和Ij之間的子軌跡段。由于道路交叉點(diǎn)影響距離不會(huì)超過以該交叉點(diǎn)為公共頂點(diǎn)的最短邊直線距離d，顧及軌跡采樣頻率及道路寬度影響，本文將ri、rj設(shè)置為β×d，如圖8(a)所示。為剔除偽子軌跡，本文還進(jìn)行了如下的范圍及方向限制。

(1) 范圍限制。以Ii與Ij之間的中點(diǎn)Pcenter為原點(diǎn)，IiIj為X軸，IiIj的垂線為Y軸，如圖8(b)所示。則子軌跡點(diǎn)到原點(diǎn)的距離在X軸方向投影disx(Pi,Pcenter)及在Y軸方向投影disy(Pi,Pcenter)滿足以下條件

(3)

(2) 方向限制。車輛在道路上行駛時(shí)，除非在十字路口轉(zhuǎn)彎，否則行駛方向不會(huì)發(fā)生太大變化，因此子軌跡點(diǎn)方向限制如下

(4)

式中，Pi、Pj為子軌跡點(diǎn)(0≤i

基于IiIj兩方向子軌跡即可對(duì)路段進(jìn)行擬合，首先將路段的直連線段劃分為M等份，然后提取每一段局部密度極大點(diǎn)，最后將起點(diǎn)、局部密度極大點(diǎn)及終點(diǎn)依次連接，利用道格拉斯算法對(duì)形成的折線段進(jìn)行簡化，完成分段擬合，如圖8(c)所示。

圖8 子軌跡提取及路段擬合Fig.8 Sub-trajectory extraction and road segment fitting

需要說明的是，如果T1集合中存在三角形3條邊都被識(shí)別，并且至少一個(gè)非斜邊不是其他三角形斜邊，則該三角形斜邊為偽路段，需要從T1集合剔除。如果T1集合中存在懸掛邊，且該邊與其他T1集合具有公共結(jié)點(diǎn)路段之間夾角小于60°，則為偽路段，也需從T1集合中剔除?；谔崛÷肪W(wǎng)T=[T1,T2,T3]，進(jìn)一步剔除一些少于3條道路與之相連，違反交叉口定義的偽交叉點(diǎn)，并對(duì)路網(wǎng)進(jìn)行拓?fù)錂z查，合并偽節(jié)點(diǎn)連接的兩條路段，完成道路網(wǎng)拓?fù)浼m錯(cuò)。

3 導(dǎo)航屬性分析

轉(zhuǎn)向關(guān)系的有效性直接決定了城市路網(wǎng)導(dǎo)航信息的質(zhì)量，是導(dǎo)航信息計(jì)算的重中之重。本文顧及出租車軌跡采樣頻率及城市路段的短連接特性，以“路段-交叉點(diǎn)-路段”[23]的形式進(jìn)行交叉口與路段的關(guān)聯(lián)分析，研究路段到路段的轉(zhuǎn)向模式，進(jìn)一步分析路段的單雙向信息，實(shí)現(xiàn)可導(dǎo)航路網(wǎng)構(gòu)建的有效探索。

3.1 路段轉(zhuǎn)向關(guān)系識(shí)別

考慮到出租車軌跡采樣頻率較低，難以探測交叉口轉(zhuǎn)向片段，本文將轉(zhuǎn)向與直行關(guān)系區(qū)分對(duì)待，基于相似性評(píng)價(jià)指標(biāo)分別對(duì)交叉口轉(zhuǎn)向點(diǎn)對(duì)(圖3(f))及直行片段進(jìn)行層次聚類，然后計(jì)算交叉口關(guān)聯(lián)路段，分析路段之間轉(zhuǎn)向關(guān)系進(jìn)行路網(wǎng)轉(zhuǎn)彎信息識(shí)別。對(duì)于任意的兩個(gè)轉(zhuǎn)向點(diǎn)對(duì)/直行片段(t1,t2)，其空間相似性主要體現(xiàn)在起始點(diǎn)方向差異和終止點(diǎn)方向差異[16,24]，設(shè)立如下指標(biāo)進(jìn)行轉(zhuǎn)向點(diǎn)對(duì)/直行片段的相似性評(píng)價(jià)

sim=w1e-dis(θs1,θs2)+w2e-dis(θe1,θe2)

(5)

式中，dis(θs1,θs2)、dis(θe1,θe2)為起始點(diǎn)及終止點(diǎn)頭方向歐氏距離。為了更好地度量角度之間的距離，本文將方向進(jìn)行了極坐標(biāo)轉(zhuǎn)換[27]。w1和w2與起始點(diǎn)之間、終止點(diǎn)之間相似度有關(guān)，如果e-dis(θs1,θs2)和e-dis(θe1,θe2)的值都大于0.5，則w1、w2均設(shè)置為0.5；否則，如果e-dis(θs1,θs2)>e-dis(θe1,θe2)，設(shè)置w1=0.01、w2=0.99，如果e-dis(θs1,θs2)

基于路段幾何提取信息，可進(jìn)一步根據(jù)轉(zhuǎn)彎/直行聚類簇起止方向確定交叉口的關(guān)聯(lián)路段。為消除少數(shù)非法掉頭與隨機(jī)轉(zhuǎn)彎情況，根據(jù)經(jīng)驗(yàn)將轉(zhuǎn)向點(diǎn)對(duì)數(shù)量小于3的聚類簇剔除。以圖9中交叉口I為例，對(duì)于每類聚類簇(如0類簇)，計(jì)算起始、終止方向中位數(shù)作為該簇起始方向及終止方向，如果存在I2-I路段結(jié)點(diǎn)P到I方向與該簇起始方向差異最小，存在I到I-I3路段結(jié)點(diǎn)Q方向與終止方向差異最小，則交叉口I轉(zhuǎn)彎規(guī)則即可映射到交叉口關(guān)聯(lián)路段I2-I與I-I3之間的關(guān)系。考慮到彎曲道路對(duì)結(jié)果的影響，P、Q取路段中離交叉點(diǎn)I最近的路段結(jié)點(diǎn)。以P-I為前進(jìn)方向，表示為向量a，I-Q表示為向量b，則轉(zhuǎn)向規(guī)則可基于向量b與向量a的夾角θ進(jìn)行判斷。如果兩向量叉積(a×b)的坐標(biāo)Z>0，則向量b逆時(shí)針偏離向量a，表示從I2-I路段，轉(zhuǎn)到I-I3路段的轉(zhuǎn)角α=θ，如果Z<0，則表示α=-θ。路段轉(zhuǎn)彎規(guī)則與轉(zhuǎn)角關(guān)系如下。

圖9 交叉口關(guān)聯(lián)關(guān)系 Fig.9 The association relationship for road intersection

(1) 如果45°≤α≤135°，則路段轉(zhuǎn)彎規(guī)則為左轉(zhuǎn)。

(2) 如果-135°≤α≤-45°，則路段轉(zhuǎn)彎規(guī)則為右轉(zhuǎn)。

(3) 如果-45°<α<45°，則路段轉(zhuǎn)彎規(guī)則為直行。

(4) 如果135°<α≤180°/-180°<α≤-135°，則路段轉(zhuǎn)彎規(guī)則為掉頭。

3.2 路段單雙向判斷

路網(wǎng)中路段的單雙向信息也是導(dǎo)航屬性的重要組成部分，可由交叉口識(shí)別的關(guān)聯(lián)路段間轉(zhuǎn)彎信息進(jìn)一步推導(dǎo)獲得。以圖9交叉口I為例，I2-I路段右轉(zhuǎn)向I-I3路段，即存在軌跡由路段I2-I途徑交叉口I至I-I3。進(jìn)一步而言，如果存在路段途經(jīng)交叉口I至I-I2，則路段I2-I為雙向通行路段，否則為單向通行路段。

4 試驗(yàn)分析

4.1 研究區(qū)域與數(shù)據(jù)集

本文試驗(yàn)數(shù)據(jù)包括漢口出租車軌跡數(shù)據(jù)、武漢大學(xué)出租車軌跡數(shù)據(jù)及芝加哥校園巴士軌跡數(shù)據(jù)(圖10)。文獻(xiàn)[28]認(rèn)為當(dāng)采集周期超過7 d后，武漢市路段上出租車數(shù)據(jù)覆蓋寬度逐漸趨于穩(wěn)定，因此，武漢兩個(gè)研究區(qū)域選取2014-05-29—06-04的1周內(nèi)出租車軌跡數(shù)據(jù)進(jìn)行試驗(yàn)。漢口區(qū)為武漢市中心城區(qū)，新舊建筑交錯(cuò)，道路間距不一；武漢大學(xué)研究區(qū)道路曲折多樣，無一定幾何形狀，都對(duì)低頻軌跡應(yīng)用于道路信息提取的分析與挖掘有一定代表性。由于武漢大學(xué)數(shù)據(jù)集噪聲較大，連續(xù)點(diǎn)間的時(shí)間間隔及空間間隔不一致，本文對(duì)武漢大學(xué)數(shù)據(jù)進(jìn)行了如下預(yù)處理：①刪除原始軌跡數(shù)中位置重復(fù)記錄、航向?yàn)?、速度為0及速度超過100 km/h的軌跡點(diǎn)；②當(dāng)相鄰軌跡點(diǎn)時(shí)間間隔大于60 s、兩軌跡點(diǎn)之間距離大于100(km/h)×60 s≈1.3 km或兩軌跡點(diǎn)之間距離大于(v1+v2)×(t2-t1)/2時(shí)，對(duì)軌跡進(jìn)行打斷，刪除軌跡點(diǎn)個(gè)數(shù)小于1的軌跡。芝加哥數(shù)據(jù)集為公共數(shù)據(jù)集，其采樣頻率(2～3 s)及定位精度較高，為驗(yàn)證本文方法處理低頻軌跡效果，將其進(jìn)行了30 s抽稀。表2為預(yù)處理后軌跡數(shù)據(jù)情況。

圖10 研究區(qū)軌跡數(shù)據(jù)集Fig.10 The trajectory datasets of study area

表2 數(shù)據(jù)集描述

4.2 參數(shù)設(shè)置

多模特征交叉口提取與融合中參數(shù)主要涉及搜索半徑h、像元大小C、高密度閾值k、轉(zhuǎn)向點(diǎn)對(duì)距離限制閾值d、局部距離閾值D及交叉口融合半徑R。為區(qū)分距離較近交叉口，綜合考慮道路寬度及道路交叉口最小間距，搜索半徑h一般設(shè)置為50 m。像元大小C可通過研究范圍的寬度或高度中的較小值除以250來計(jì)算。局部距離閾值D基于密度-距離決策圖一般設(shè)置為20 m，轉(zhuǎn)向點(diǎn)對(duì)距離限制閾值d則基于轉(zhuǎn)向點(diǎn)對(duì)距離統(tǒng)計(jì)直方圖設(shè)定為最大頻率對(duì)應(yīng)距離。由于抽稀前芝加哥數(shù)據(jù)采樣頻率較高，不需要設(shè)置轉(zhuǎn)向點(diǎn)對(duì)距離限制閾值。閾值k的設(shè)定較為困難，本文基于經(jīng)驗(yàn)設(shè)定為平均密度的α倍。交叉口融合半徑R，可基于交叉口最小間距設(shè)置為75 m。路段提取主要涉及路段重疊率閾值γ及范圍限制閾值β。根據(jù)經(jīng)驗(yàn)，γ一般設(shè)置為0.9。β可根據(jù)不同采樣頻率進(jìn)行設(shè)置，對(duì)于高頻數(shù)據(jù)，β值可相應(yīng)減小為1/2。未匹配路段長度l保留可根據(jù)經(jīng)驗(yàn)進(jìn)行設(shè)置為50 m，不同數(shù)據(jù)集參數(shù)設(shè)置見表3。

表3 路網(wǎng)生成方法參數(shù)設(shè)置

4.3 試驗(yàn)結(jié)果與精度評(píng)價(jià)

漢口區(qū)域、武漢大學(xué)區(qū)域及芝加哥區(qū)域識(shí)別交叉口及路段結(jié)果如圖11所示。漢口和武漢大學(xué)數(shù)據(jù)集為出租車軌跡數(shù)據(jù)，采樣頻率較低且包含大量噪聲，在這種情況下，本文方法均取得了較好的道路提取效果，表明本文方法可有效規(guī)避低頻及噪聲對(duì)識(shí)別結(jié)果帶來的不利影響。芝加哥數(shù)據(jù)在抽稀前后識(shí)別結(jié)果變化不大，進(jìn)一步驗(yàn)證本文方法適用于低頻軌跡數(shù)據(jù)?？梢钥闯?，本文方法不僅可以有效識(shí)別老城區(qū)等道路密集區(qū)域的路網(wǎng)(圖11(a))，而且適合于軌跡分布不均區(qū)域的道路提取(圖11(b))。

圖11(e)—圖11(i)進(jìn)一步展示了本文方法和3個(gè)經(jīng)典算法(Davies方法[11]、Ahmed方法[12]和Karagiorgou方法[21])在交叉口位置與道路中心線的局部提取效果。顯然，本文方法所提取中心線的扭曲很小，且其拓?fù)溥B通性也得到了正確構(gòu)建。通過與OpenStreetMap道路數(shù)據(jù)比較，本文方法所提取的交叉口位置精度更高，所提取中心線的幾何形態(tài)偏差更小。

圖11 本文方法提取結(jié)果Fig.11 The extraction results of our method

為進(jìn)一步驗(yàn)證本文方法完備性與準(zhǔn)確率，使用精確率(precision)、召回率(recall)和F1分?jǐn)?shù)(F1-score)對(duì)本文方法、Davies方法、Ahmed方法和Karagiorgou方法提取結(jié)果進(jìn)一步進(jìn)行精度評(píng)定，見表4。其中交叉口基于鄰域半徑r內(nèi)匹配的交叉口個(gè)數(shù)進(jìn)行精度評(píng)定，而路網(wǎng)則基于像元大小r進(jìn)行柵格化后匹配的單元格數(shù)[19]進(jìn)行精度評(píng)定。

表4 評(píng)價(jià)結(jié)果

面對(duì)低頻高噪的武漢出租車軌跡數(shù)據(jù)，本文所識(shí)別交叉口及道路網(wǎng)較之其他方法，具有更高的精確率與召回率。基于交叉口間最小距離將r設(shè)置為50 m時(shí)，漢口區(qū)域交叉口精確率超過90%，具有不規(guī)則路網(wǎng)的武漢大學(xué)區(qū)域也達(dá)到70%以上?？紤]到本文基于交叉口對(duì)提取路段中心線，較高的交叉口識(shí)別精度有利于道路網(wǎng)的全面與精確識(shí)別，以漢口數(shù)據(jù)集為例，相應(yīng)的道路網(wǎng)在精確率和召回率兩個(gè)指標(biāo)上分別達(dá)到86.53%和79.06%。對(duì)于芝加哥數(shù)據(jù)集，本文方法的交叉口召回率不如Ahmed和Karagiorgou，主要原因在于高置信交叉口判定除方向特征外，其他特征均與密度相關(guān)，導(dǎo)致在僅有少數(shù)幾條軌跡通過的區(qū)域中，交叉口難以被有效識(shí)別。但是在該數(shù)據(jù)集上，本文方法取得了比其他方法更高的精確率，且所提取路網(wǎng)的視覺表現(xiàn)更接近實(shí)際情況。

本文方法充分利用道路多模特征的互補(bǔ)優(yōu)勢(shì)，在高置信交叉口基礎(chǔ)上實(shí)施多階段路段識(shí)別，可以較為全面與精確地從低頻高噪且分布不均的出租車軌跡數(shù)據(jù)中識(shí)別出道路交叉口與道路網(wǎng)。針對(duì)3個(gè)數(shù)據(jù)集的試驗(yàn)表明，本文方法無論從視覺效果還是在定量評(píng)價(jià)上，均取得了比其他方法更優(yōu)的提取結(jié)果，不僅可以有效識(shí)別方格式路網(wǎng)，而且適用于非規(guī)則路網(wǎng)的提取。由于加油站與停車場等POI的出入口與道路交叉口呈現(xiàn)出類似特征，本文方法有可能將其識(shí)別為偽交叉口。此外，對(duì)于軌跡非常稀疏的區(qū)域，本文方法將因其密度過小而發(fā)生交叉口漏提，進(jìn)而導(dǎo)致路網(wǎng)識(shí)別效果下降。

針對(duì)本文方法在轉(zhuǎn)向關(guān)系與單雙向信息識(shí)別方面的有效性，選取試驗(yàn)區(qū)域內(nèi)最為復(fù)雜的沿河大道與晴川街交叉口(圖12(a))開展試驗(yàn)，并與OpenStreetMap導(dǎo)航信息進(jìn)行比對(duì)(圖12(b))。該交叉口關(guān)聯(lián)路段的轉(zhuǎn)向關(guān)系提取結(jié)果見表5，路段單雙向信息見表6。在總共25個(gè)轉(zhuǎn)向關(guān)系中，有19個(gè)被正確提取出來，而單雙向信息被全部正確識(shí)別。錯(cuò)誤轉(zhuǎn)向關(guān)系主要發(fā)生在長度較短的路段上(圖12(a)中80、81號(hào)路段)。由于武漢出租軌跡數(shù)據(jù)的采樣頻率普遍較低，落在該路段與其一階相鄰路段的轉(zhuǎn)向子軌跡非常少，使得轉(zhuǎn)向關(guān)系的判定較為困難。

表5 轉(zhuǎn)向規(guī)則提取結(jié)果

表6 路段單雙向結(jié)果

圖12 沿河大道與晴川街交叉口Fig.12 The road intersection of Yanhe avenue and Qingchuan street

5 結(jié) 論

目前，關(guān)于城市路網(wǎng)提取的研究較多，但大多需要高質(zhì)量軌跡數(shù)據(jù)的支持，難以適用低頻率、低精度、時(shí)空異質(zhì)的出租車軌跡數(shù)據(jù)。由于交叉口識(shí)別精確度不高及路段生成時(shí)缺乏有效的提前判別，大部分方法中交叉口周圍路段扭曲嚴(yán)重，相鄰路段區(qū)分困難，極大影響轉(zhuǎn)向關(guān)系識(shí)別。為此，本文通過挖掘出租車軌跡關(guān)于道路網(wǎng)絡(luò)的多模特征，采用“交叉口位置—路段幾何—導(dǎo)航屬性”的研究思路，分別提出了一種顧及多模特征的道路交叉口集成識(shí)別技術(shù)、一種基于Delaunay三角網(wǎng)的多階段路段生成方法及一種路段到路段的轉(zhuǎn)向關(guān)系識(shí)別模式，在交叉口信息的引導(dǎo)下，逐步生成路網(wǎng)的“骨架”與“血肉”，實(shí)現(xiàn)城市可導(dǎo)航路網(wǎng)的分而治之構(gòu)建，大大降低了可導(dǎo)航路網(wǎng)構(gòu)建的復(fù)雜度。

為了構(gòu)建更為全面的可導(dǎo)航路網(wǎng)結(jié)構(gòu)支撐精細(xì)導(dǎo)航需求，未來將在復(fù)雜交叉口精細(xì)構(gòu)建和多類型導(dǎo)航屬性挖掘兩方面繼續(xù)開展研究。