萬(wàn)子健，李連營(yíng)，楊 敏，周校東

1. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430072； 2. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710054

軌跡數(shù)據(jù)由定位設(shè)備實(shí)時(shí)記錄并上傳產(chǎn)生，描述移動(dòng)對(duì)象的時(shí)空位置信息。隨著網(wǎng)絡(luò)及定位技術(shù)的普及，多種途徑匯集形成的眾源軌跡數(shù)據(jù)成為地理大數(shù)據(jù)的重要部分。這種眾源軌跡數(shù)據(jù)具有來(lái)源廣泛、時(shí)效性強(qiáng)、隱含特征豐富等特點(diǎn)，對(duì)交通流量分析[1]、出行模式挖掘[2]、智能位置推薦[3]等具有重要價(jià)值。在地理數(shù)據(jù)更新領(lǐng)域，大量的車(chē)輛軌跡數(shù)據(jù)背后蘊(yùn)含了道路分布、交通條件(如車(chē)流量、通行限制)、設(shè)施興趣點(diǎn)(如加油站、停車(chē)場(chǎng))等最新信息，提取上述隱含信息并實(shí)施數(shù)據(jù)建庫(kù)與一致性更新，對(duì)于解決當(dāng)前基礎(chǔ)測(cè)繪數(shù)據(jù)更新維護(hù)面臨的技術(shù)手段單一、效率低、成本高等問(wèn)題有積極意義。

利用車(chē)輛軌跡數(shù)據(jù)提取道路分布信息是當(dāng)前的研究熱點(diǎn)，存在兩種不同的解決思路。第1種是采用柵格化思想[4-7]，對(duì)軌跡點(diǎn)分布空間進(jìn)行剖分形成密度圖，利用核密度估計(jì)等方法提取道路分布的平面區(qū)域，然后通過(guò)形態(tài)分析操作(如骨架化)獲得道路結(jié)構(gòu)線。該類(lèi)方法優(yōu)點(diǎn)在于可以充分利用圖像處理領(lǐng)域積累的成熟技術(shù)。然而，受柵格單元大小、軌跡點(diǎn)分布密度不均衡等因素影響，局部區(qū)域提取的道路線容易出現(xiàn)連接破碎，需要后期進(jìn)行一致性維護(hù)補(bǔ)救。第2種是矢量化處理策略，以軌跡點(diǎn)(或軌跡線段)為基本單元，通過(guò)統(tǒng)計(jì)聚類(lèi)方法探測(cè)道路分布特征。例如，文獻(xiàn)[8—11]利用k-means方法結(jié)合距離、航向指標(biāo)對(duì)軌跡點(diǎn)進(jìn)行聚類(lèi)，在此基礎(chǔ)上通過(guò)不同的聚類(lèi)簇處理策略生成道路弧段。文獻(xiàn)[12]采用Douglas-Peucker算法[13]探測(cè)關(guān)鍵軌跡點(diǎn)，然后采用DBSCAN方法對(duì)關(guān)鍵軌跡點(diǎn)進(jìn)行迭代式聚類(lèi)提取道路交叉口。文獻(xiàn)[14—15]設(shè)計(jì)了力學(xué)模型剔除異常軌跡點(diǎn)，然后利用局部G統(tǒng)計(jì)熱點(diǎn)分析方法提取道路網(wǎng)結(jié)構(gòu)。文獻(xiàn)[16]考慮角度變化、時(shí)長(zhǎng)間隔提取轉(zhuǎn)向點(diǎn)對(duì)，在空間聚類(lèi)方法支持下獲得轉(zhuǎn)向點(diǎn)對(duì)簇，繼而獲得道路網(wǎng)交叉口結(jié)構(gòu)信息。文獻(xiàn)[17]引入約束Delaunay三角網(wǎng)探測(cè)軌跡點(diǎn)空間集聚性，通過(guò)軌跡點(diǎn)的空間剖分面積以及相鄰軌跡點(diǎn)距離實(shí)現(xiàn)道路邊界的精確提取。為提高道路生成過(guò)程效率，相關(guān)學(xué)者還提出增量式的處理策略。例如，文獻(xiàn)[18]通過(guò)建立軌跡數(shù)據(jù)與參考路網(wǎng)間的位置、語(yǔ)義關(guān)系漸進(jìn)式地生成道路信息。文獻(xiàn)[19]將空間認(rèn)知規(guī)律引入到軌跡線提取路網(wǎng)過(guò)程中，基于Delaunay三角網(wǎng)構(gòu)建軌跡線融合處理模型，通過(guò)不斷修正細(xì)化獲得完整的道路網(wǎng)信息。與第1種思路相比較，上述方法不僅利用車(chē)輛軌跡的空間分布特征，而且能夠獲得移動(dòng)方向、速度等隱含的動(dòng)力學(xué)特征支持。

從圖論角度看，道路網(wǎng)由道路交叉口和連接交叉口的道路弧段構(gòu)成。其中，交叉口的識(shí)別與提取是道路網(wǎng)生成的關(guān)鍵步驟。車(chē)輛移動(dòng)過(guò)程中，道路交叉口區(qū)域產(chǎn)生的軌跡路徑在形態(tài)結(jié)構(gòu)、轉(zhuǎn)向幅度、速度變化、停留時(shí)長(zhǎng)方面與其他區(qū)域存在顯著差異。然而，已有方法大多將軌跡點(diǎn)作為基本分析單元，對(duì)局部軌跡路徑體現(xiàn)的形態(tài)及動(dòng)力特征變化的缺乏有效考慮，同時(shí)如何集成不同類(lèi)型參量進(jìn)行綜合決策也是面臨的難題。基于上述觀察以及研究現(xiàn)狀分析，本文提出了一種利用車(chē)輛軌跡提取道路交叉口特征的方法。首先，分析交叉口的變道軌跡片段與常規(guī)非變道軌跡片段間的差異，并定義曲直比、轉(zhuǎn)向角度、行駛速度三個(gè)描述參量；然后，利用決策樹(shù)方法構(gòu)建多因子決策的軌跡片段分類(lèi)模型，并結(jié)合移動(dòng)開(kāi)窗式的軌跡線剖分模型建立交叉口區(qū)域變道軌跡片段提取方法；最后，基于相似性原則對(duì)交叉口區(qū)域軌跡片段實(shí)施聚類(lèi)，并提取軌跡片段簇中心線獲得交叉口結(jié)構(gòu)信息。利用多個(gè)城市的車(chē)輛軌跡數(shù)據(jù)作為試驗(yàn)測(cè)試數(shù)據(jù)，通過(guò)對(duì)比式評(píng)估驗(yàn)證本文方法的有效性，并對(duì)方法的不足之處進(jìn)行了深入分析。

1 決策樹(shù)支持下的交叉口識(shí)別

為了準(zhǔn)確描述本文所提出的方法，首先給出以下定義：

定義1 軌跡線(T)：由一系列按時(shí)間次序排列的點(diǎn)集構(gòu)成，即T={p1,p2,…,pn}(n≥2)。其中，pi=(xi,yi,ti)，xi和yi為軌跡點(diǎn)pi的空間坐標(biāo)，ti表示pi產(chǎn)生的時(shí)間信息。

定義2 軌跡片段(TS)：由軌跡線T上部分連續(xù)軌跡點(diǎn)構(gòu)成，如TS(pl,pm)={pl,pl+1,…,pm}(1≤l

定義3 軌跡直線段(e)：由相鄰軌跡點(diǎn)組成的直線段，例如ei表示軌跡點(diǎn)由pi和pi+1連接而成的直線段。

特別地，根據(jù)軌跡點(diǎn)和直線段的關(guān)系，上文中軌跡線T和軌跡片段TS也可對(duì)應(yīng)表示為{e1,e2,…,en-1}和{el,el+1,…,em-1}(1≤l

1.1 道路交叉口車(chē)輛變道軌跡片段分析

道路交叉口是兩條或兩條以上道路實(shí)體交匯銜接處，如圖1(b)—(e)列出的幾種典型道路交叉口結(jié)構(gòu)。道路交叉口在整個(gè)交通運(yùn)輸過(guò)程扮演重要角色，是車(chē)輛實(shí)現(xiàn)匯集、疏散、行駛道路變更轉(zhuǎn)換的關(guān)鍵區(qū)域。在道路實(shí)體建模與表達(dá)中，交叉口對(duì)應(yīng)道路網(wǎng)絡(luò)中連接不同道路弧段的結(jié)點(diǎn)。本研究將車(chē)輛在交叉口區(qū)域變道過(guò)程產(chǎn)生的軌跡片段稱(chēng)為變道軌跡片段。如圖1(a)所示，車(chē)輛從pi點(diǎn)開(kāi)始進(jìn)入交叉路口至pj點(diǎn)駛出，完成了從道路R1至R2的變道轉(zhuǎn)換，pi、pj兩點(diǎn)間的軌跡片段即稱(chēng)為變道軌跡片段(記為L(zhǎng)C_TS(pi,pj))。受道路物理結(jié)構(gòu)和車(chē)輛交匯影響，道路交叉口發(fā)生的變道行為使得車(chē)輛運(yùn)行狀態(tài)產(chǎn)生變化。這種變化直接反映在變道軌跡片段的幾何形態(tài)、隱含動(dòng)力學(xué)特征上。具體地，本文定義以下幾個(gè)參量描述變道軌跡片段與非變道軌跡片段間的差異性。

圖1 道路交叉口與變道軌跡片段(紅色)示例Fig.1 Samples of road intersection and lane-changing trajectory segment

1.1.1 直曲比

與同一道路上行駛產(chǎn)生的軌跡片段相比較，變道軌跡片段最直觀的差異表現(xiàn)在幾何形態(tài)上，即車(chē)輛通過(guò)交叉口時(shí)行駛軌跡彎曲程度明顯增大。這種彎曲程度可通過(guò)直曲比進(jìn)行描述。軌跡片段TS(pl,pm)的直曲比定義如下

(1)

式中，Len(pi,pj)表示軌跡點(diǎn)pi和pj間的直線段長(zhǎng)度。以圖2(a)所示某車(chē)輛產(chǎn)生的軌跡線為例，從p1開(kāi)始分析移動(dòng)窗口內(nèi)軌跡片段的直曲比(圖2(b))，可以發(fā)現(xiàn)同一路段行駛時(shí)軌跡片段直曲比接近1，而在道路交叉口變道階段的軌跡片段直曲比出現(xiàn)異常波動(dòng)。除少數(shù)特殊結(jié)構(gòu)道路和交通狀況外(如車(chē)輛非正常轉(zhuǎn)向)，軌跡片段直曲比越小，所在區(qū)域?yàn)榈缆方徊婵诘目赡苄栽酱蟆?/p>

圖2 軌跡片段直曲比分析Fig.2 Curvature analysis of trajectory segments

1.1.2 轉(zhuǎn)向角度

車(chē)輛在道路交叉口完成變道行為時(shí)伴隨行駛方向的顯著變化。這種變化可以通過(guò)軌跡片段起點(diǎn)與終點(diǎn)間的轉(zhuǎn)向角度進(jìn)行度量。如圖3(a)所示，軌跡片段TS(pl,pm)在起始點(diǎn)pl處的航向角度為θl，終止點(diǎn)pm處用其前一個(gè)點(diǎn)pm-1的航向角度近似代替，即θm-1，則TS(pl,pm)的轉(zhuǎn)向角度計(jì)算如下

Δθ=|θm-1-θl| (0°≤Δθ≤180°)

(2)

式中，pi處航向角度定義為正北方向與車(chē)輛行駛方向間沿順時(shí)針的夾角。圖3(b)展示了圖3(a)所示移動(dòng)窗口包含軌跡片段的轉(zhuǎn)向角度。可以發(fā)現(xiàn)，同一道路上行駛時(shí)軌跡片段轉(zhuǎn)向角度較小(≤30°)，而在交叉口區(qū)域軌跡片段轉(zhuǎn)向角度較大(≥60°)。

1.1.3 行駛速度

道路交叉口銜接路段呈顯著彎曲結(jié)構(gòu)，車(chē)輛需要降低行駛速度，同時(shí)，不同方向車(chē)輛需要交互完成變道行為，導(dǎo)致車(chē)輛低速甚至短暫停止移動(dòng)。因此，軌跡片段隱含的速度特征可以作為區(qū)分變道軌跡片段與非變道軌跡片段的又一有效指標(biāo)。假設(shè)相鄰軌跡點(diǎn)間車(chē)輛運(yùn)動(dòng)速度均勻，軌跡片段TS(pl,pm)隱含的速度計(jì)算如下

(3)

式中，v(pi)表示車(chē)輛經(jīng)過(guò)pi時(shí)的速度，可由pi與pi+1間的距離和時(shí)間間隔計(jì)算得到。如圖4(a)所示，車(chē)輛經(jīng)過(guò)W2和W5區(qū)域時(shí)均發(fā)生大幅度轉(zhuǎn)向變化，僅通過(guò)直曲比、轉(zhuǎn)向角度難以區(qū)分變道轉(zhuǎn)向和非變道轉(zhuǎn)向。從圖4(b)所示的速度變化看，W2處行駛速度較大，而道路交叉口的W5處行駛速度出現(xiàn)谷值。

圖3 軌跡片段轉(zhuǎn)向角度分析Fig.3 Turning angle analysis of trajectory segment

圖4 行駛速度分析Fig.4 Speed analysis of trajectory segments

1.2 基于CART決策樹(shù)的變道軌跡片段識(shí)別模型

變道軌跡片段識(shí)別面臨兩個(gè)難點(diǎn)問(wèn)題。一方面，單一指標(biāo)難以準(zhǔn)確區(qū)分變道軌跡片段與非變道軌跡片段，需要集成幾何形態(tài)、轉(zhuǎn)向幅度、速度變化進(jìn)行綜合判斷。例如，受交通堵塞等因素影響，非道路交叉口區(qū)域車(chē)輛也可能以較低速度行駛；局部道路呈現(xiàn)彎曲形態(tài)分布，導(dǎo)致軌跡片段轉(zhuǎn)向角度較大。另一方面，作為完整軌跡線的一部分，變道軌跡片段準(zhǔn)確識(shí)別需要專(zhuān)門(mén)的軌跡線剖分模型進(jìn)行支撐。針對(duì)上述問(wèn)題，本研究設(shè)計(jì)了一種移動(dòng)開(kāi)窗策略與決策樹(shù)學(xué)習(xí)分類(lèi)相結(jié)合的變道軌跡片段識(shí)別模型。

1.2.1 基于移動(dòng)開(kāi)窗的軌跡線剖分模型

以軌跡線起始點(diǎn)為錨點(diǎn)，創(chuàng)建大小為s的窗口w，以步長(zhǎng)μ移動(dòng)窗口，直至完整遍歷該軌跡線。其中，s定義為窗口包含的軌跡直線段數(shù)量，μ定義為窗口移動(dòng)前與移動(dòng)后錨點(diǎn)間的軌跡直線段數(shù)量。在窗口移動(dòng)過(guò)程中，記錄每一位置狀態(tài)下窗口包含的軌跡片段，作為后續(xù)變道軌跡片段識(shí)別的基本單元。圖5中軌跡線T={e1,e2,…,e12}，設(shè)置大小s為3、移動(dòng)步長(zhǎng)μ為1的移動(dòng)窗口，則產(chǎn)生軌跡片段TS1={e1,e2,e3}、TS2={e2,e3,e4}、…、TS10={e10,e11,e12}。窗口尺寸設(shè)置需考慮道路交叉口區(qū)域大小及通行條件。假設(shè)軌跡點(diǎn)采樣間隔為1 s，常規(guī)條件下交叉口車(chē)輛完成變道過(guò)程耗時(shí)約為5 s，則窗口尺寸可設(shè)置為5。窗口移動(dòng)步長(zhǎng)越小，則變道軌跡片段位置識(shí)別的準(zhǔn)確性越高。

圖5 基于移動(dòng)開(kāi)窗策略的軌跡線剖分處理Fig.5 Trajectory subdivision using a sliding window method

1.2.2 基于決策樹(shù)學(xué)習(xí)的軌跡片段分類(lèi)模型

如前文所述，區(qū)分變道軌跡片段與非變道軌跡片段需要綜合考慮多重特征，可采用機(jī)器學(xué)習(xí)方法構(gòu)建分類(lèi)模型。決策樹(shù)學(xué)習(xí)是機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用最為廣泛的分類(lèi)學(xué)習(xí)方法之一[20]，其本質(zhì)是通過(guò)歸納推理構(gòu)建樹(shù)狀結(jié)構(gòu)的分類(lèi)規(guī)則組合。樹(shù)結(jié)構(gòu)從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑代表一條分類(lèi)規(guī)則，路徑內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)某個(gè)特征的測(cè)試，葉節(jié)點(diǎn)對(duì)應(yīng)規(guī)則的分類(lèi)結(jié)果。與神經(jīng)網(wǎng)絡(luò)等其他監(jiān)督學(xué)習(xí)方法構(gòu)建的分類(lèi)器相比較，決策樹(shù)具有分類(lèi)速度快、效率高、無(wú)須對(duì)輸入數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理的優(yōu)點(diǎn)。同時(shí)，決策樹(shù)表達(dá)的分類(lèi)規(guī)則視覺(jué)直觀、解譯性強(qiáng)易于移植(如轉(zhuǎn)換為If-Then形式)。在地理信息領(lǐng)域，決策樹(shù)方法已廣泛應(yīng)用于道路網(wǎng)結(jié)構(gòu)識(shí)別[21]、地圖數(shù)據(jù)變化探測(cè)與更新[22]、空間數(shù)據(jù)匹配融合[23]等問(wèn)題。決策樹(shù)構(gòu)建可采用算法包括ID3、C4.5、CART，其中CART算法具有準(zhǔn)確率高、計(jì)算量小、操作簡(jiǎn)單靈活，能夠從復(fù)雜樣本數(shù)據(jù)抽象出清晰易解譯的分類(lèi)規(guī)則。CART決策樹(shù)模型構(gòu)建包括生成和剪枝兩個(gè)步驟：①根據(jù)訓(xùn)練數(shù)據(jù)廣延地生長(zhǎng)決策樹(shù)；②基于最小復(fù)雜性代價(jià)準(zhǔn)則[24]對(duì)已生成的決策樹(shù)實(shí)施剪枝，并使用測(cè)試數(shù)據(jù)驗(yàn)證，選擇最優(yōu)子樹(shù)。

本文采用決策樹(shù)CART算法構(gòu)建道路交叉口變道軌跡片段和非變道軌跡片段的分類(lèi)模型。CART決策樹(shù)屬于監(jiān)督分類(lèi)方法，需要提供訓(xùn)練樣本進(jìn)行模型構(gòu)建與評(píng)價(jià)。針對(duì)軌跡線T包含的某一軌跡片段TS(i)，按1.1節(jié)定義的參量(即直曲比、轉(zhuǎn)向角度、行駛速度)構(gòu)建如下數(shù)組

L(TS(i))=(Cur(TS(i)),Cur(TS(i-1)),

Cur(TS(i+1)),Δθ(TS(i)),Δθ(TS(i-1)),Δθ(TS(i+1)),v(TS(i)),v(TS(i))-

v(TS(i-1)),v(TS(i))-v(TS(i+1)),R)

式中，TS(i-1)和TS(i+1)分別表示與TS(i)相鄰的前、后軌跡片段；R為標(biāo)簽向量，表示軌跡片段類(lèi)別(標(biāo)識(shí)為“Y”(屬于變道軌跡片段)或者“N”(屬于非變道軌跡片段))。表1所示為歸一化后的樣本數(shù)據(jù)組織格式。

表1 樣本數(shù)據(jù)組織格式

1.2.3 變道軌跡片段提取過(guò)程

基于移動(dòng)開(kāi)窗剖分模型和樣本數(shù)據(jù)訓(xùn)練得到的決策樹(shù)分類(lèi)器，從完整軌跡線提取變道軌跡片段的過(guò)程設(shè)計(jì)如下：

(1) 針對(duì)移動(dòng)窗口產(chǎn)生的每一條軌跡片段，計(jì)算當(dāng)前軌跡片段以及其前、后窗口內(nèi)軌跡片段的直曲比、轉(zhuǎn)向角度、行駛速度參量值(若為起/止軌跡片段，則將其前/后窗口內(nèi)軌跡片段參量值置空)，輸入分類(lèi)器進(jìn)行類(lèi)型識(shí)別。進(jìn)一步將分類(lèi)結(jié)果作為屬性標(biāo)注到該軌跡片段包含的每一條軌跡直線段上。如圖6(b)所示，軌跡直線段e1、e2、e3構(gòu)成的軌跡片段判定為“N”(即非變道軌跡片段)，則e1、e2、e3各自增加一個(gè)“N”的類(lèi)型標(biāo)識(shí)。

(2) 依次遍歷軌跡線包含的所有軌跡直線段，對(duì)于每條軌跡直線段統(tǒng)計(jì)其記錄的所有類(lèi)型標(biāo)識(shí)。若“Y”數(shù)量大于等于“N”數(shù)量，則將該軌跡直線段最終標(biāo)識(shí)為“Y”；否則，該軌跡直線段最終標(biāo)識(shí)為“N”。如圖6(c)中e4的屬性標(biāo)識(shí)為(“Y”，“N”，“N”)，則最終標(biāo)識(shí)為“N”；e5的屬性標(biāo)識(shí)為(“Y”，“Y”，“N”)，則最終標(biāo)識(shí)為“Y”。

(3) 將相鄰且標(biāo)識(shí)為“Y”的軌跡直線段進(jìn)行連接組織，最終輸出變道軌跡片段。如圖6(d)所示一個(gè)變道軌跡片段LC_TS={e5,e6,…,e9}。

圖6 變道軌跡片段提取過(guò)程Fig.6 The process of lane-changing trajectory segment extraction

2 交叉口區(qū)域軌跡片段聚類(lèi)與道路結(jié)構(gòu)線生成

2.1 軌跡片段聚類(lèi)

進(jìn)一步，對(duì)交叉口區(qū)域的軌跡片段實(shí)施相似性聚類(lèi)形成軌跡片段簇，并提取同一組軌跡片段的中心線作為道路結(jié)構(gòu)線。軌跡片段間相似性由包含軌跡點(diǎn)間的位置關(guān)系決定。Hausdorff距離是描述兩組點(diǎn)集相似程度的一種度量指標(biāo)，但集合中的元素是無(wú)序的，忽略了軌跡點(diǎn)在時(shí)間維上的有序性。文獻(xiàn)[25]提出了改進(jìn)Hausdorff距離，一方面利用平移常量消除了軌跡片段間的公共偏差；另一方面依據(jù)時(shí)間順序進(jìn)行軌跡點(diǎn)間的比較，符合軌跡的時(shí)序特征。如圖7(a)所示，軌跡片段TS(A)和TS(B)間Hausdorff距離計(jì)算如下

(4)

式中，H表示Hausdorff距離；⊕是一個(gè)集合運(yùn)算符號(hào)(A⊕g={a+g|a∈A})；函數(shù)Len計(jì)算軌跡點(diǎn)間的距離；平移常量g定義為兩條軌跡片段間時(shí)間同步軌跡點(diǎn)距離的平均值。當(dāng)兩條軌跡片段間Hausdorff距離小于設(shè)定閾值，則判定兩者屬于同一軌跡片段簇。

提取完整的道路交叉口結(jié)構(gòu)，需要得到兩個(gè)不同層面的軌跡片段聚類(lèi)結(jié)果。一是與道路線相對(duì)應(yīng)的軌跡片段簇，包括變道軌跡片段簇和未發(fā)生變道行為的直行軌跡片段簇；二是屬于不同交叉口區(qū)域的軌跡片段簇的集合。依據(jù)變道軌跡片段識(shí)別結(jié)果，獲得上述兩個(gè)層面聚類(lèi)結(jié)果步驟如下：

(1) 基于Hausdorff距離h對(duì)變道軌跡片段進(jìn)行聚類(lèi)，得到變道軌跡片段簇。聚類(lèi)結(jié)果如圖7(b)所示，同一種顏色表示的軌跡片段屬同一簇。

(2) 針對(duì)每一變道軌跡片段簇，取所有軌跡片段兩側(cè)端點(diǎn)坐標(biāo)的平均值作為定位點(diǎn)；然后，依據(jù)歐氏距離閾值h′對(duì)定位點(diǎn)進(jìn)行聚類(lèi)分組，獲得屬于同一交叉口的變道軌跡片段簇。

(3) 對(duì)于每一個(gè)道路交叉口，取所有軌跡片段簇定位點(diǎn)的中心位置作為交叉口的中心點(diǎn)O，按交叉口范圍取大不取小原則[16]，選取定位點(diǎn)與O距離最大值作為交叉口范圍半徑R(如圖7(c)所示)；利用交叉口范圍圓裁切經(jīng)過(guò)該區(qū)域的非變道軌跡片段，依據(jù)Hausdorff距離h聚類(lèi)成簇(如圖7(d)所示)，最終得到該交叉口區(qū)域所有的變道軌跡片段簇和非變道軌跡片段簇。

圖7 道路交叉口區(qū)域軌跡片段聚類(lèi)Fig.7 Clustering of trajectory segments in an area of road intersection

2.2 道路結(jié)構(gòu)線生成

針對(duì)每一組軌跡片段簇，通過(guò)一種迭代式策略提取中心線作為道路弧段[26]，從而獲得交叉口道路結(jié)構(gòu)特征。假設(shè)軌跡片段簇C={TS1,TS2,…,TSm}(m>1),中心線提取方法如下：

(1) 隨機(jī)選擇軌跡片段簇C中一條軌跡片段作為初步的中心線CL。如圖8(a)所示，C={TS1,TS2,TS3}，CL=TS={p1,p2,p3,p4}。

(2) 以CL包含軌跡點(diǎn)為分組種子點(diǎn)，其他軌跡片段的軌跡點(diǎn)按照距離最近原則分別匹配到不同種子點(diǎn)，形成軌跡點(diǎn)分組并按種子點(diǎn)時(shí)間次序排列。如圖8(b)所示，按次序形成軌跡點(diǎn)分組G1、G2、G3、G4。

圖8 軌跡片段簇中心線提取方法Fig.8 Extracting center line of a cluster of trajectory segments

(3) 計(jì)算每一分組軌跡點(diǎn)的中心位置點(diǎn)(圖8(c))，按次序連接成線后更新原來(lái)中心線CL。如圖8(d)，更新后CL={cp1,cp2,cp3,cp4}。

(4) 重復(fù)步驟(2)和(3)，直至CL更新前后不再發(fā)生變化。最后，輸出CL作為軌跡片段簇的中心線。

3 試驗(yàn)分析與評(píng)價(jià)

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

如圖9所示，試驗(yàn)數(shù)據(jù)包括德國(guó)科隆市城區(qū)車(chē)輛移動(dòng)軌跡數(shù)據(jù)集[27]、芝加哥校園巴士軌跡數(shù)據(jù)集和武漢市部分出租車(chē)的軌跡數(shù)據(jù)集。原始軌跡數(shù)據(jù)實(shí)施如下預(yù)處理：①按車(chē)輛組織軌跡點(diǎn)，依據(jù)時(shí)間次序連接形成軌跡線;②當(dāng)相鄰軌跡點(diǎn)時(shí)間間隔大于30 s時(shí)(如在高層建筑、隧道等區(qū)域)，對(duì)軌跡線實(shí)施打斷處理；③過(guò)濾速度異常(大于200 km/h)的軌跡點(diǎn)。表2描述了上述預(yù)處理工作后的車(chē)輛軌跡數(shù)據(jù)情況。相比較而言，來(lái)自科隆和芝加哥的軌跡數(shù)據(jù)定位誤差小，道路上軌跡點(diǎn)分布密度高、車(chē)輛行駛速度相對(duì)均勻；武漢市出租車(chē)軌跡數(shù)據(jù)定位誤差較大，且存在大量低速行駛點(diǎn)以及停留點(diǎn)。考慮到不同數(shù)據(jù)集間車(chē)輛行駛速度、軌跡點(diǎn)采樣頻率存在差異，變道軌跡片段提取時(shí)對(duì)軌跡線進(jìn)行線性加密[28]，加密間距dl=10 m。

建立ArcGIS與Matlab相結(jié)合的試驗(yàn)軟件平臺(tái)。其中，ArcGIS平臺(tái)負(fù)責(zé)軌跡數(shù)據(jù)預(yù)處理、軌跡片段參量計(jì)算、軌跡簇生成及中心線提取等工作，利用Matlab提供的決策樹(shù)學(xué)習(xí)模塊建立變道軌跡片段識(shí)別模型。試驗(yàn)參數(shù)設(shè)置如下：①綜合考慮車(chē)輛行駛速度、道路交叉口范圍大小、相鄰軌跡點(diǎn)時(shí)間間隔等，經(jīng)過(guò)多次試驗(yàn)反饋，設(shè)置移動(dòng)窗口大小s=9，窗口移動(dòng)步長(zhǎng)μ=1；②設(shè)置軌跡片段聚類(lèi)的Hausdorff距離閾值h=10 m，軌跡片段簇定位點(diǎn)聚類(lèi)的歐氏距離h′=80 m。

圖9 試驗(yàn)軌跡數(shù)據(jù)集Fig.9 Experimental trajectory datasets

表2 試驗(yàn)軌跡數(shù)據(jù)描述

3.2 結(jié)果分析

在構(gòu)建軌跡片段決策樹(shù)分類(lèi)模型時(shí)，以人工標(biāo)注方式疊加OpenStreetMap道路數(shù)據(jù)構(gòu)建樣本數(shù)據(jù)。綜合考慮3種不同軌跡數(shù)據(jù)集的數(shù)據(jù)規(guī)模、采樣精度，以及分類(lèi)模型交叉驗(yàn)證的需要，從科隆數(shù)據(jù)集提取數(shù)量為1500的樣本數(shù)據(jù)。其中，變道軌跡片段與非變道軌跡片段數(shù)量比例約1∶3，涵蓋各種典型的道路交叉口以及非交叉路口區(qū)域。對(duì)樣本數(shù)據(jù)進(jìn)行歸一化處理后，按照80%和20%的比例劃分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集。圖10是基于訓(xùn)練數(shù)據(jù)學(xué)習(xí)得到的軌跡片段決策樹(shù)分類(lèi)模型，包括6個(gè)層級(jí)，19個(gè)葉節(jié)點(diǎn)。利用測(cè)試數(shù)據(jù)進(jìn)行驗(yàn)證，該模型對(duì)軌跡片段分類(lèi)的準(zhǔn)確率達(dá)到96.1%。

圖11展示了不同軌跡數(shù)據(jù)集通過(guò)分類(lèi)器提取的變道軌跡片段及道路交叉口結(jié)果。圖中綠色圈形表示變道軌跡片段識(shí)別較為完備的交叉口區(qū)域(TruePositive)、黃色矩形表示非道路交叉口但存在識(shí)別為變道軌跡片段的區(qū)域(FalsePositive)、紅色三角形表示變道軌跡片段識(shí)別與實(shí)際不符的交叉口區(qū)域(FalseNegative)。圖11右側(cè)分別為3個(gè)軌跡數(shù)據(jù)集識(shí)別得到的變道軌跡片段和交叉口結(jié)構(gòu)示例。定義精確率(precision)和召回率(recall)對(duì)交叉口識(shí)別提取結(jié)果進(jìn)行量化分析，precision和recall計(jì)算公式如下

(5)

(6)

式中，Num_TruePositive、Num_FalseNegative和Num_FalsePositive分別表示識(shí)別結(jié)果為T(mén)ruePositive、FalseNegative和FalsePositive的數(shù)量。將本文方法與轉(zhuǎn)向點(diǎn)對(duì)法[16]和局部G統(tǒng)計(jì)法[14]進(jìn)行對(duì)比評(píng)價(jià)。其中，轉(zhuǎn)向點(diǎn)對(duì)法轉(zhuǎn)向角閾值取45°，完成一次轉(zhuǎn)向最大時(shí)間間隔設(shè)為20 s，轉(zhuǎn)向點(diǎn)對(duì)相似度聚類(lèi)閾值取0.75，局部點(diǎn)連通性聚類(lèi)鄰域半徑取35 m；局部G統(tǒng)計(jì)法中交叉口候選軌跡點(diǎn)G*閾值取1.95。表3統(tǒng)計(jì)了3種方法應(yīng)用到不同軌跡數(shù)據(jù)集的交叉口識(shí)別結(jié)果。從中可以發(fā)現(xiàn)：

(1) 本文建立的交叉口提取模型對(duì)科隆和芝加哥數(shù)據(jù)集識(shí)別結(jié)果較好，精確率和召回率接近(或超過(guò))90%，而應(yīng)用到武漢數(shù)據(jù)集的交叉口識(shí)別精確率和召回率分別為62.7%和70.6%。分析原因：一方面武漢數(shù)據(jù)的定位精度較低，車(chē)輛變道產(chǎn)生的軌跡路徑與實(shí)際位置偏移較大，導(dǎo)致出現(xiàn)大量軌跡點(diǎn)在一定范圍內(nèi)“抖動(dòng)”的情況，對(duì)變道軌跡片段識(shí)別及道路線提取產(chǎn)生干擾；另一方面，決策樹(shù)學(xué)習(xí)的樣本數(shù)據(jù)來(lái)自科隆數(shù)據(jù)，構(gòu)建的分類(lèi)模型對(duì)于科隆數(shù)據(jù)以及質(zhì)量特征(如軌跡點(diǎn)定位精度、采樣頻率)相似的芝加哥數(shù)據(jù)效果較好，而武漢數(shù)據(jù)由于樣本學(xué)習(xí)不足導(dǎo)致分類(lèi)器識(shí)別效果不佳。

圖10 構(gòu)建的軌跡片段分類(lèi)決策樹(shù)模型Fig.10 Decision tree model constructed for trajectory segment classification

(2) 面對(duì)采樣頻率高、定位精度較好、同時(shí)軌跡點(diǎn)分布密集的軌跡數(shù)據(jù)(如科隆和芝加哥數(shù)據(jù)集)，3種方法均能取得較高的精確率和召回率；而應(yīng)用到采樣頻率較低、定位精度不佳，有效軌跡點(diǎn)分布相對(duì)稀疏的情形(如武漢數(shù)據(jù)集)，本文方法相比較轉(zhuǎn)向點(diǎn)對(duì)法和局部G統(tǒng)計(jì)法有較大提升。局部G統(tǒng)計(jì)法通過(guò)挖掘軌跡點(diǎn)轉(zhuǎn)向角的局部相關(guān)性，找到大轉(zhuǎn)向角軌跡點(diǎn)分布密集的熱點(diǎn)范圍作為交叉口候選區(qū)域，對(duì)軌跡分布密集的交叉口有較好的識(shí)別效果，但易漏識(shí)別軌跡分布稀疏的交叉口。轉(zhuǎn)向點(diǎn)對(duì)法通過(guò)提取車(chē)輛變道過(guò)程產(chǎn)生的完整轉(zhuǎn)向特征進(jìn)行分析，面對(duì)低精度軌跡數(shù)據(jù)時(shí)具有一定的抗干擾性，從而提升交叉口識(shí)別效果。本文方法除考慮轉(zhuǎn)向特征外，進(jìn)一步增加幾何形態(tài)和速度變化指標(biāo)，并且利用移動(dòng)開(kāi)窗策略對(duì)軌跡剖分片段進(jìn)行連續(xù)式分析，對(duì)局部軌跡點(diǎn)存在的誤差起到平滑過(guò)濾效果，從而能夠更加準(zhǔn)確地探測(cè)道路交叉口變道軌跡特征，得到相對(duì)較高的交叉口識(shí)別精確率與召回率。

表3 試驗(yàn)結(jié)果統(tǒng)計(jì)

本文方法產(chǎn)生的錯(cuò)誤實(shí)例，主要包括兩種不同的情形。

圖11 變道軌跡片段識(shí)別與交叉口結(jié)果提取Fig.11 Lane-changing segments recognition and intersection structure extraction

(1) 漏識(shí)別，即交叉口結(jié)構(gòu)整體或部分丟失。該類(lèi)問(wèn)題常見(jiàn)于Y型交叉口(圖12(a))和大型立交橋區(qū)域。該類(lèi)區(qū)域車(chē)輛行駛產(chǎn)生的轉(zhuǎn)向及速度變化不顯著，難以準(zhǔn)確提取變道軌跡片段。此外，部分交叉口區(qū)域軌跡數(shù)據(jù)分布稀疏(圖12(b))，雖能從中獲得少量變道軌跡片段，但其數(shù)量不足以形成有效的變道軌跡片段簇，從而導(dǎo)致交叉口特征未被完整識(shí)別。

(2) 結(jié)構(gòu)不準(zhǔn)確，即交叉口識(shí)別結(jié)果與實(shí)際分布狀態(tài)間存在不一致。如圖12(c)所示，對(duì)于交叉口分布密集且間距較小情況，當(dāng)移動(dòng)窗口尺寸設(shè)置偏大時(shí)，本文方法難以準(zhǔn)確提取個(gè)體交叉口結(jié)構(gòu)。此外，圖12(d)所示區(qū)域軌跡點(diǎn)定位誤差較大時(shí)，導(dǎo)致軌跡片段直曲比、轉(zhuǎn)向角和行駛速度計(jì)算結(jié)果失真，從而引起變道軌跡片段的錯(cuò)判以及對(duì)后續(xù)交叉口結(jié)構(gòu)提取產(chǎn)生負(fù)面影響。

圖12 交叉口識(shí)別錯(cuò)誤示例Fig.12 Samples of incorrect extracted road intersections

總結(jié)錯(cuò)誤識(shí)別案例發(fā)生的緣由，包括兩個(gè)方面：一是與軌跡數(shù)據(jù)本身質(zhì)量相關(guān)，如局部軌跡線分布稀疏、軌跡點(diǎn)定位誤差大等；二是與方法本身相關(guān)，如軌跡線剖分模型中移動(dòng)窗口的大小對(duì)交叉口提取結(jié)果有重要影響。窗口太小，導(dǎo)致大型交叉口結(jié)構(gòu)提取不完整；窗口太大，容易丟失小型道路交叉口。以科隆市Merheimer Heide公園旁的大型交叉口為例，圖13對(duì)比了3種不同大小窗口下的變道軌跡片段的識(shí)別結(jié)果。當(dāng)窗口尺寸參數(shù)s=9時(shí)(圖13(a))，僅獲得局部少量變道軌跡片段；增大窗口尺寸至s=39時(shí)(圖13(c))，則可以有效提高變道軌跡片段識(shí)別完整性。因此，合理的窗口大小設(shè)置十分關(guān)鍵。當(dāng)軌跡線加密間距為10 m時(shí)，圖14統(tǒng)計(jì)了科隆數(shù)據(jù)集在窗口尺寸參數(shù)s不同取值下的交叉口識(shí)別結(jié)果?？梢园l(fā)現(xiàn)，當(dāng)s=9(窗口內(nèi)軌跡片段長(zhǎng)度約90 m)時(shí)交叉口提取結(jié)果的精確率和召回率綜合表現(xiàn)最好。另一方面，統(tǒng)計(jì)該區(qū)域所有交叉口的范圍大小，發(fā)現(xiàn)80%以上范圍圓直徑處于60～130 m之間。因此，窗口大小設(shè)置可參考區(qū)域多數(shù)交叉口范圍圓的直徑分布區(qū)間。

圖13 不同大小窗口下變道軌跡片段識(shí)別結(jié)果Fig.13 Results of extracted lane-changing segments under different sizes of opening windows

圖14 不同窗口尺寸下的識(shí)別結(jié)果分析Fig.14 Analysis of results with different window sizes

4 結(jié) 論

利用車(chē)輛軌跡數(shù)據(jù)提取道路交叉口特征，已有方法主要采用基于軌跡點(diǎn)的統(tǒng)計(jì)聚類(lèi)策略。本文方法將軌跡片段作為基本分析單元，綜合幾何形態(tài)、轉(zhuǎn)向幅度、速度變化指標(biāo)識(shí)別道路交叉口的變道軌跡片段，然后通過(guò)軌跡片段的相似性聚類(lèi)與中心線提取方法獲得道路交叉口結(jié)構(gòu)特征。圍繞上述思路，設(shè)計(jì)了移動(dòng)開(kāi)窗式的軌跡線分段剖分模型，并引入機(jī)器學(xué)習(xí)領(lǐng)域的決策樹(shù)學(xué)習(xí)方法建立軌跡片段分類(lèi)模型。試驗(yàn)結(jié)果表明，本文方法相比傳統(tǒng)方法在交叉口特征提取的準(zhǔn)確率與召回率上具有優(yōu)勢(shì)，特別對(duì)采集頻率低、分布相對(duì)稀疏的軌跡數(shù)據(jù)提取道路交叉口效果有較大提升。

本文方法還有不足之處有待改進(jìn)提升。首先，需要建立更加完備的變道軌跡片段樣本數(shù)據(jù)。試驗(yàn)中的樣本數(shù)據(jù)來(lái)自科隆數(shù)據(jù)集，將訓(xùn)練學(xué)習(xí)得到的分類(lèi)器應(yīng)用到武漢數(shù)據(jù)集，交叉口識(shí)別準(zhǔn)確率與召回率明顯低于科隆數(shù)據(jù)集識(shí)別結(jié)果。主要原因是兩種軌跡數(shù)據(jù)采樣間隔、定位精度，以及背后的道路格局、交通擁堵?tīng)顩r存在差異，導(dǎo)致變道軌跡片段表現(xiàn)出不同的幾何形態(tài)與動(dòng)力學(xué)特征。因此，變道軌跡片段樣本數(shù)據(jù)需要結(jié)合區(qū)域交通特點(diǎn)、軌跡數(shù)據(jù)質(zhì)量狀況進(jìn)行補(bǔ)充完善。其次，需要發(fā)展窗口大小自適應(yīng)調(diào)整機(jī)制，滿足不同尺寸變道軌跡片段識(shí)別需求，從而實(shí)現(xiàn)對(duì)不同大小等級(jí)交叉口特征的準(zhǔn)確提取。