胡蓉，韓宇，徐永，許偉輝，李誠

(福建工程學(xué)院，福建省大數(shù)據(jù)挖掘與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，福建 福州 350118)

0 引言

隨著互聯(lián)網(wǎng)和智能手機(jī)的快速發(fā)展，基于位置的服務(wù)(location-based services，LBS)已經(jīng)成為人們?nèi)粘Ｉ钪兄匾M成部分(如導(dǎo)航、 點(diǎn)外賣、 線上生活超市等)，從而對(duì)電子路網(wǎng)地圖的實(shí)時(shí)更新產(chǎn)生了更高的需求.因此全自動(dòng)道路檢測技術(shù)成為研究熱點(diǎn)，許多學(xué)者提出了基于遠(yuǎn)程遙感圖像的方法[1-2]，以及光探測和測距點(diǎn)(激光雷達(dá))云數(shù)據(jù)[3]來提取路網(wǎng)信息.這兩種方式數(shù)據(jù)獲取成本高且提取的信息往往滯后于實(shí)際路網(wǎng)的改變[4].近年來，大多數(shù)車輛運(yùn)營車輛(出租車、 公共汽車、 貨車)都裝有全球定位系統(tǒng)(GPS)，這些設(shè)備能收集大量的位置信息，記錄了包括車輛經(jīng)緯度、 速度、 時(shí)間戳、 航向角等信息，這些軌跡信息相互聯(lián)系代表了一定的交通模式，因此通過挖掘和分析車輛軌跡數(shù)據(jù)來更新數(shù)字地圖就成為一種新型低成本而實(shí)時(shí)有效的方式[5].交叉路口是路網(wǎng)的重要部分，能夠提供非常有用的信息，比如連通性、 拓?fù)?，以及允許移動(dòng)的方向.為了從大規(guī)模的網(wǎng)絡(luò)中自動(dòng)產(chǎn)生完整的交通路口地理數(shù)據(jù)，許多研究者對(duì)此展開了研究，以實(shí)現(xiàn)讓車輛安全通過路口的目的[6-8].

目前已有的路口識(shí)別方法主要分為3種基本的類型： 一類是基于空間幾何特征和聚類的方法，如Wu等[9]通過聚類方法尋找停止點(diǎn)和轉(zhuǎn)彎點(diǎn)來識(shí)別路口； 一類是利用軌跡數(shù)據(jù)在路口呈現(xiàn)的空間幾何特征提取路口，如Xie等[10]通過在每一對(duì)軌跡中尋找共同子軌跡，并將其起始點(diǎn)作為采集的連接點(diǎn)，最后對(duì)連接點(diǎn)采用核密度估計(jì)方法檢測路口； 第三類是學(xué)習(xí)方法，如利用決策樹方法構(gòu)建軌跡片段分類模型及軌跡線剖分模型建立交叉口區(qū)域變道軌跡片段提取方法，然后對(duì)這些片段進(jìn)行聚類提取中心線獲取道路交叉口結(jié)構(gòu)[11]，以及通過深度學(xué)習(xí)產(chǎn)生地圖[12-13].

在軌跡數(shù)據(jù)來源上, 有研究者通過分析眾源GPS車輛軌跡數(shù)據(jù)來獲取道路地圖及交通路口信息，如Wang等[14]通過分析航向差從高采樣頻率GPS軌跡中提取轉(zhuǎn)彎曲線，將交叉路口建模成圓形區(qū)域，最后通過聚類的方法獲取路口的位置信息.Keler等[15]基于分析出租車軌跡數(shù)據(jù)，為每個(gè)實(shí)體創(chuàng)建單獨(dú)的軌跡作為多線段表示，然后從所有軌跡多線段中提取交叉點(diǎn).為了提高交叉口的幾何識(shí)別精度，Li等[16]采用融合相似方向并保持沖突方向的獨(dú)立性方法，通過調(diào)整主要方向來提取路口從而減少位置偏移和道路變形帶來的識(shí)別誤差.為了識(shí)別路口的詳細(xì)結(jié)構(gòu)，最近Chen等[17]提出擴(kuò)展分類利用幾何特征道路交叉口，并獲得了較好的召回率和整體性能.Wang等[18]通過分析車輛運(yùn)動(dòng)方向熵來有效識(shí)別路口，采用統(tǒng)計(jì)模型評(píng)估上游車輛的停車位置并進(jìn)而估計(jì)停車流的數(shù)量、 坐標(biāo)和方向.

為避免受人工設(shè)置閾值的影響，本研究提出一種基于長短期記憶(long short time memory，LSTM)深度學(xué)習(xí)的方法對(duì)車輛在路口的轉(zhuǎn)彎軌跡模式進(jìn)行建模學(xué)習(xí)，從而自動(dòng)尋找路口轉(zhuǎn)彎軌跡點(diǎn)； 然后，針對(duì)路口轉(zhuǎn)彎軌跡點(diǎn)的稀疏性缺陷，提出一種基于計(jì)算補(bǔ)償點(diǎn)和轉(zhuǎn)彎角度變化幅度聯(lián)合確定路口候選點(diǎn)的方法，并通過基于密度聚類(density based spatial clustering of applications with noises，DBSCAN)方式對(duì)路口候選點(diǎn)自動(dòng)提取路口中心位置.采用福州市鼓樓區(qū)出租車實(shí)際軌跡數(shù)據(jù)驗(yàn)證該方法.實(shí)驗(yàn)結(jié)果表明, 該方法能快速自動(dòng)識(shí)別轉(zhuǎn)彎軌跡和交通路口，有助于該領(lǐng)域自動(dòng)識(shí)別系統(tǒng)的研發(fā).

1 研究方法

基于LSTM在處理時(shí)間序列數(shù)據(jù)方面的優(yōu)勢，對(duì)具有時(shí)序特性的軌跡數(shù)據(jù)建模.首先，對(duì)浮動(dòng)車軌跡段打上直行、 左轉(zhuǎn)、 右轉(zhuǎn)、 掉頭和小轉(zhuǎn)彎5類標(biāo)簽，提取經(jīng)度、 緯度和航向角作為輸入特征，然后通過建立LSTM模型識(shí)別軌跡類別； 其次，針對(duì)低頻軌跡導(dǎo)致路口轉(zhuǎn)彎點(diǎn)比較少這個(gè)缺陷，提出一種基于補(bǔ)償點(diǎn)計(jì)算和轉(zhuǎn)彎角度變化聯(lián)合確定路口中心候選點(diǎn)的方法； 最后，通過DBSCAN聚類自動(dòng)識(shí)別出路口中心.

1.1 一種基于LSTM的浮動(dòng)車轉(zhuǎn)彎軌跡自動(dòng)提取方法

該方法分為兩個(gè)步驟.首先是構(gòu)建軌跡特征向量，作為LSTM模型的輸入； 然后是基于LSTM轉(zhuǎn)彎軌跡的自動(dòng)提取.

1.1.1 時(shí)空特征的軌跡段特征向量矩陣構(gòu)建

軌跡數(shù)據(jù)是記錄車輛或行人的行駛軌跡序列，具有時(shí)間連續(xù)性及空間幾何特性，在行至路口時(shí)因航向改變而具有幾何特點(diǎn).假設(shè)軌跡數(shù)據(jù)平均回傳率為1/20 Hz(每20 s傳回一次)，空間上考慮每個(gè)樣本點(diǎn)間距為50 m，根據(jù)路口轉(zhuǎn)彎特點(diǎn)，考慮4個(gè)軌跡樣本點(diǎn)可描述路口轉(zhuǎn)彎特性，有如下定義.

定義1： 一個(gè)軌跡樣本點(diǎn)為xi(loni, lati,φi)，其中l(wèi)an, lat,φ分別是車輛行駛時(shí)實(shí)時(shí)傳回的經(jīng)度、 緯度、 航向角.

定義2： 每天傳回軌跡數(shù)據(jù)的車輛集合為{id(i),i=1, 2, …,N}.

定義3： 所有車輛一天的行駛軌跡點(diǎn)的集合為T={T(id(i))},i∈1, 2, 3, …,N

定義4： 每臺(tái)車一天采集到的軌跡點(diǎn)的數(shù)量為n.

定義5： 將每輛車(id(i))的行駛軌跡集合定義為{Tr(id(i))=(x1,x2, …，xn)}.

定義6： 軌跡點(diǎn)按照時(shí)間順序每4個(gè)點(diǎn)構(gòu)成一個(gè)子軌跡

定義7： 軌跡特征向量為一個(gè)4行3列矩陣，選取每個(gè)樣本點(diǎn)的3個(gè)特征，其中l(wèi)oni、 lati和φi分別為第i個(gè)軌跡點(diǎn)的經(jīng)度、 緯度和航向角，形成一個(gè)子軌跡Tri矩陣列，每一個(gè)輸入矩陣都對(duì)應(yīng)于一種軌跡類型： 直行、 左轉(zhuǎn)彎、 右轉(zhuǎn)彎、 掉頭或小轉(zhuǎn)彎，通過人工為每個(gè)子軌跡打上對(duì)應(yīng)的標(biāo)簽構(gòu)成后續(xù)LSTM模型的訓(xùn)練樣本數(shù)據(jù)集，如圖1所示.式(1)所示是一個(gè)獨(dú)立樣本的示例.

(1)

1.1.2 基于長短期記憶網(wǎng)絡(luò)(LSTM)深度學(xué)習(xí)自動(dòng)提取路口轉(zhuǎn)彎軌跡點(diǎn)

深度學(xué)習(xí)領(lǐng)域中，循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network, RNN)被廣泛用來分析時(shí)間序列數(shù)據(jù)的結(jié)構(gòu)，其中LSTM是一種可以通過門控機(jī)制控制輸入、 輸出和神經(jīng)元記憶間的信息流，主要應(yīng)用在語音識(shí)別、 圖像說明、 語言翻譯等，近來也被用來分析軌跡數(shù)據(jù)[19].

LSTM是一種循環(huán)神經(jīng)網(wǎng)絡(luò)，與傳統(tǒng)的前饋神經(jīng)網(wǎng)絡(luò)不同，它具有反饋機(jī)制，不僅可以用來處理單個(gè)的數(shù)據(jù)，也可以用來學(xué)習(xí)時(shí)間序列的數(shù)據(jù).其特點(diǎn)是重復(fù)利用之前的隱藏層輸出，使得神經(jīng)網(wǎng)絡(luò)可以重復(fù)學(xué)習(xí)前面學(xué)到的東西，并結(jié)合上下文的內(nèi)容進(jìn)行學(xué)習(xí)分析，從而對(duì)序列數(shù)據(jù)的處理有獨(dú)特的優(yōu)勢.

通過LTSM模塊的特征提取學(xué)習(xí)，輸入子軌跡Tri=X, 如式(1)所示作為輸入向量，輸出為預(yù)測的軌跡類別.模型包含輸入、 4個(gè)隱藏層(每層神經(jīng)元1 024個(gè)，激活函數(shù)sigmoid)、 一個(gè)dropout 層(隨機(jī)丟棄率設(shè)置為0.1、 全連接層，最后輸出預(yù)測結(jié)果，優(yōu)化方法選擇Adam, 學(xué)習(xí)率設(shè)置0.001, 損失函數(shù)采用交叉熵，如下式所示.

(2)

1.2 一種補(bǔ)償點(diǎn)計(jì)算和臨近入口點(diǎn)計(jì)算的路口候選點(diǎn)選取方法

其中: (xi,yi)(i=1, 2, 3, 4)是轉(zhuǎn)彎軌跡點(diǎn)pi的經(jīng)緯度.

(4)

由圖3可知，如果Φ1角度大于Φ2，則pi+1離路口點(diǎn)更近，可作為路口中心候選點(diǎn); 反之, 則pi+2離路口點(diǎn)更近而作為路口中心候選點(diǎn).

為了確定補(bǔ)償點(diǎn)和候選點(diǎn)的距離是否超過路口的范圍，要根據(jù)路口覆蓋范圍確定一個(gè)距離閾值.如圖4所示，一個(gè)大型路口的覆蓋半徑一般為60 m左右，因此當(dāng)補(bǔ)償點(diǎn)與最近路口點(diǎn)的距離超過了覆蓋范圍的直徑120 m即可判定補(bǔ)償點(diǎn)已經(jīng)偏離路口，此時(shí)將以靠近路口點(diǎn)作為路口中心的候選點(diǎn).

1.3 基于DBSCAN的路口識(shí)別

如節(jié)1.1和1.2方法獲得路口候選點(diǎn)后，采用DBSCAN對(duì)候選點(diǎn)進(jìn)行聚類，類族族心就是路口位置.該算法能找到多維數(shù)據(jù)的內(nèi)在特征關(guān)系，在聚類數(shù)目未知的情況下，可以發(fā)現(xiàn)任意形狀，任意大小的噪聲數(shù)據(jù)集的簇，并且支持空間數(shù)據(jù).該算法需要用戶根據(jù)實(shí)際情況和經(jīng)驗(yàn)確定簇內(nèi)最小數(shù)目MinPts及簇間最小距離ε，這兩個(gè)參數(shù)的選擇是影響結(jié)果的重要因素-輪廓系數(shù)來評(píng)價(jià)的.

通過實(shí)驗(yàn)選取18<ε<30，MinPts取5～15，計(jì)算出當(dāng)各個(gè)組合的輪廓系數(shù)最大，S(i)=0.760 593、 簇間最小距離ε=25 m、 簇內(nèi)最小數(shù)目MinPts=10、 噪聲比為3.27%時(shí)，該聚類的結(jié)果是最合理，將采用DBSCAN對(duì)前面獲得的路口候選點(diǎn)進(jìn)行聚類，聚類后的每個(gè)族代表一個(gè)路口，從而識(shí)別出路口的大致位置.

2 實(shí)驗(yàn)結(jié)果與分析

采用福建省營運(yùn)車軌跡數(shù)據(jù)，該數(shù)據(jù)是福建省交通廳對(duì)福州市內(nèi)約15萬部營運(yùn)車輛(主要是出租車)在道路運(yùn)營行駛中進(jìn)行實(shí)時(shí)采集而獲得，提取并預(yù)處理2018年5月3—5日的福州市鼓樓區(qū)的浮動(dòng)車軌跡數(shù)據(jù)，得到12.5萬條軌跡數(shù)據(jù)，將5月4—5日的數(shù)據(jù)打上標(biāo)簽作為訓(xùn)練數(shù)據(jù)訓(xùn)練模型.為了驗(yàn)證模型的有效性，用5月3日的數(shù)據(jù)(模型沒用過的數(shù)據(jù))作為輸入數(shù)據(jù)測試模型，輸出y為每一種軌跡類別的概率，選取概率最大的值作為軌跡類別的標(biāo)簽.通過所得到的輸出，提取出左轉(zhuǎn)與右轉(zhuǎn)的軌跡數(shù)據(jù)，并基于計(jì)算補(bǔ)償點(diǎn)和臨近路口點(diǎn)方法選取路口候選點(diǎn)，最后通過DBSCAN聚類識(shí)別路口中心.首先，將2018年5月4—5日的軌跡數(shù)據(jù)分為3部分，70%為訓(xùn)練數(shù)據(jù)構(gòu)建模型，20%作為驗(yàn)證數(shù)據(jù)用于檢驗(yàn)和評(píng)估模型的準(zhǔn)確率.為了輔助模型的構(gòu)建，剩下的10%用來做交叉驗(yàn)證數(shù)據(jù).

2.1 數(shù)據(jù)描述

所選的福州市鼓樓區(qū)為福州市的經(jīng)濟(jì)、 政治和文化交流中心，具有代表性，所用的出租車軌跡數(shù)據(jù)的經(jīng)緯度范圍為： (119.286 7°, 26.065 6°)～(119.352 21°, 26.108 13°).該數(shù)據(jù)的平均采樣頻率為1/20 Hz，主要采樣屬性包括： 車輛ID、 經(jīng)度、 緯度、 時(shí)間戳、 速度和航向角.

2.2 基于LSTM轉(zhuǎn)彎軌跡識(shí)別結(jié)果的分析

通過使用LSTM模型進(jìn)行軌跡類別的識(shí)別，訓(xùn)練初期，模型的訓(xùn)練與測試的準(zhǔn)確率提升較快速.

為了驗(yàn)證模型的準(zhǔn)確性，用2018年5月3日福州市鼓樓區(qū)內(nèi)浮動(dòng)車軌跡數(shù)據(jù)(模型未接觸過的數(shù)據(jù))作為模型路口識(shí)別效果的測試數(shù)據(jù).該數(shù)據(jù)作為訓(xùn)練好的模型的輸入數(shù)據(jù)以自動(dòng)獲取轉(zhuǎn)彎軌跡，分類結(jié)果如表1所示.

表1 測試分類結(jié)果

2.3 補(bǔ)償點(diǎn)與候選點(diǎn)相結(jié)合的路口中心提取結(jié)果與比較

如前所述有的路口點(diǎn)通過補(bǔ)償點(diǎn)計(jì)算存在軌跡點(diǎn)偏移情況，導(dǎo)致后續(xù)識(shí)別出的交叉口偏移正確位置.為此，在轉(zhuǎn)彎軌跡中計(jì)算靠近路口的中心點(diǎn)，然后結(jié)合二者確定路口候選點(diǎn)，以彌補(bǔ)補(bǔ)償點(diǎn)計(jì)算的不足，圖5給出轉(zhuǎn)彎補(bǔ)償點(diǎn)糾正前后的對(duì)比，可以看出路口候選點(diǎn)比較集中，較好地糾正補(bǔ)償點(diǎn)的不足.

2.4 路口的識(shí)別結(jié)果分析與討論

通過計(jì)算補(bǔ)償點(diǎn)和臨近點(diǎn)相結(jié)合的方法確定了候選路口點(diǎn)之后，采用DBSCAN聚類算法對(duì)路口候選點(diǎn)進(jìn)行聚類，從而最終識(shí)別出路口中心.通過試錯(cuò)找出輪廓系數(shù)選取簇間最小距離ε=25 m，簇內(nèi)最小數(shù)目MinPts=10，對(duì)這些簇內(nèi)的路口點(diǎn)求經(jīng)緯度均值后，得到路口中心位置，如圖6所示，紅色的點(diǎn)為算法識(shí)別出的路口中心.從圖中可以看出，紅色點(diǎn)基本都是在路口中心處.

為量化評(píng)估所提出的路口識(shí)別方法的效果，通過計(jì)算查準(zhǔn)率、 查全率和F-score等來實(shí)現(xiàn).查準(zhǔn)率表示正確識(shí)別的路口在算法所識(shí)別的路口中所占的比例； 查全率表示正確識(shí)別的路口在真實(shí)的路口中所占的比例； F-score綜合考慮兩者的影響.通過對(duì)比百度地圖進(jìn)行人工核查，評(píng)估結(jié)果如表2所示.

表2中，TP指實(shí)際地圖上有路口被正確識(shí)別為路口，F(xiàn)P指實(shí)際地圖上有路口沒有被識(shí)別為路口，TN指地圖上沒有路口識(shí)別為非路口(本實(shí)驗(yàn)只識(shí)別路口，非路口就是道路，不做識(shí)別)，F(xiàn)N指地圖上實(shí)際沒有路口被錯(cuò)誤識(shí)別為路口.在該數(shù)據(jù)覆蓋范圍內(nèi)百度地圖上顯示一共有238個(gè)路口，通過方法識(shí)別路口214個(gè)，TP=207，F(xiàn)P=7，F(xiàn)N=24.查準(zhǔn)率=0.967，查全率=0.896，F(xiàn)1-score=0.93，準(zhǔn)確率=0.87%.

表2 路口識(shí)別率評(píng)估

路口識(shí)別錯(cuò)誤的原因主要有3種： 一是兩個(gè)路口太靠近，導(dǎo)致算法得到的路口點(diǎn)很接近，識(shí)別成一個(gè)偏移實(shí)際位置的路口； 第二種情況是小區(qū)或者景區(qū)的入口，由于確實(shí)會(huì)有車輛在該處轉(zhuǎn)彎，導(dǎo)致誤判為路口； 第三種路口漏識(shí)別的主要原因是有的路口的交通流量特別大，導(dǎo)致轉(zhuǎn)彎軌跡及轉(zhuǎn)彎候選點(diǎn)較多，附近的小路口交通流量少且距離大路口過近，容易當(dāng)成噪聲點(diǎn).

傳統(tǒng)方法中通過軌跡數(shù)據(jù)中的航向角變化計(jì)算獲取轉(zhuǎn)彎軌跡點(diǎn)，然后采用聚類方法對(duì)轉(zhuǎn)彎軌跡點(diǎn)直接聚類提取路口信息(如Wu等[9]稱之為CHD(change of head direction).本研究提出的方法采用LSTM學(xué)習(xí)軌跡模式自動(dòng)提取轉(zhuǎn)彎軌跡點(diǎn)，然后通過結(jié)合補(bǔ)償點(diǎn)計(jì)算和臨近路口點(diǎn)計(jì)算聯(lián)合確定路口候選點(diǎn)，最后通過聚類候選點(diǎn)獲取路口位置信息，稱之為LSTM+CCI (LSTM+compensation and closest to intersection).兩種方法的識(shí)別率比較如表3.從表中可以看出，本研究提出的方法明顯優(yōu)于通過僅航向角來識(shí)別路口的方法，無論是識(shí)別率還是查全率、 查準(zhǔn)率都高于CHD方法.

表3 不同算法下路口識(shí)別結(jié)果比較

綜上，提出了基于LSTM深度學(xué)習(xí)對(duì)浮動(dòng)車軌跡模式建模，通過采用福州市出租車一天的軌跡數(shù)據(jù)驗(yàn)證該方法可以快速(1 min之內(nèi)，環(huán)境： Intel CoreTMi5-5200U CPU@ 2.20 GHz)自動(dòng)從軌跡中識(shí)別出轉(zhuǎn)彎軌跡點(diǎn).提出一種補(bǔ)償點(diǎn)計(jì)算和臨近路口點(diǎn)相結(jié)合的路口候選點(diǎn)確定方法； 通過補(bǔ)償點(diǎn)和臨近點(diǎn)計(jì)算兩種情況對(duì)比, 可以看出該方法能有效地解決因采樣或GPS質(zhì)量影響帶來的路口識(shí)別困難； 最后通過DBSCAN聚類方法識(shí)別路口.通過對(duì)比百度地圖與識(shí)別結(jié)果進(jìn)行人工核查，該方法能準(zhǔn)確有效快速(僅一天的軌跡數(shù)據(jù))識(shí)別道路交叉口，為快速持續(xù)更新電子地圖和基于位置的服務(wù)應(yīng)用提供關(guān)鍵技術(shù)支持.

3 結(jié)語

電子地圖信息是地理位置信息的關(guān)鍵組成部分，是城市規(guī)劃、 智能交通、 位置服務(wù)等應(yīng)用中的關(guān)鍵技術(shù)之一.GPS軌跡數(shù)據(jù)為產(chǎn)生電子地圖提供一種快速的方法，交通路口是電子地圖的重要組成部分，在已有的研究中還存在因軌跡數(shù)據(jù)采樣頻率和GPS信號(hào)質(zhì)量等因素影響的挑戰(zhàn).

本研究創(chuàng)新性地提出采用LSTM深度學(xué)習(xí)方法對(duì)車輛軌跡模式進(jìn)行建模學(xué)習(xí)，不僅可實(shí)現(xiàn)對(duì)路口轉(zhuǎn)彎軌跡的自動(dòng)提取，而且還能自動(dòng)過濾掉不屬于路口的轉(zhuǎn)彎模式(如駛?cè)胪＼噲觥?小區(qū)、 加油站等).提出一種補(bǔ)償點(diǎn)計(jì)算和臨近路口點(diǎn)計(jì)算的路口候選點(diǎn)選取方法，能有效解決受GPS軌跡采樣頻率和信號(hào)等影響帶來的識(shí)別精度不高的問題.通過采用福州市真實(shí)的軌跡數(shù)據(jù)驗(yàn)證了本方法可以快速實(shí)時(shí)(一天的軌跡數(shù)據(jù)僅一分鐘內(nèi))地檢測出交通路口變化，為電子地圖的實(shí)時(shí)更新和自動(dòng)駕駛導(dǎo)航等應(yīng)用需求提供技術(shù)支持.