王 杰,范曉武,何逸昕,陶 峰

(浙江綜合交通大數(shù)據(jù)中心有限公司,杭州 310005)

大規(guī)模的車輛軌跡數(shù)據(jù)可通過GPS、手機(jī)信令、視頻監(jiān)控、感應(yīng)線圈等技術(shù)獲取[1]. 利用地理信息系統(tǒng)(geographic information system,GIS)將這些軌跡數(shù)據(jù)投影在電子地圖上,能直觀地顯示交通環(huán)境,進(jìn)行實(shí)時(shí)的交通智能信息分析. 同時(shí),深入分析車輛軌跡數(shù)據(jù)還可獲取道路起訖點(diǎn)(origin-destination,OD)、出行偏好等信息. 為公路規(guī)劃、建設(shè)養(yǎng)護(hù)等工作提供重要決策支撐[2].

在上述的交通信息采集技術(shù)中,使用部署在道路上的攝像采集設(shè)備,通過自動(dòng)車牌識(shí)別技術(shù)能獲取車輛的行駛狀態(tài),如時(shí)間、車牌號(hào)、速度、車道和方向.這些行駛狀態(tài),結(jié)合道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),即可得到車輛時(shí)序軌跡數(shù)據(jù). 與基于GPS[3,4]、手機(jī)信令[5]、感應(yīng)線圈[6]等方法相比,使用攝像采集技術(shù)具有覆蓋面積廣、安裝維護(hù)便捷、連續(xù)性強(qiáng)、樣本量大的優(yōu)勢(shì). 同時(shí)還可提供可視化圖像,以保證數(shù)據(jù)的精準(zhǔn)性[7]. 由此產(chǎn)生了大量基于車牌識(shí)別數(shù)據(jù)的交通特性分析研究,但現(xiàn)有的研究[7–10]主要集中在交通小區(qū)交通量、出入站情況、通行效率等宏觀特性提取,很少有研究關(guān)注到微觀的車輛出行軌跡提取與分析. 然而,完整可靠的車輛出行軌跡蘊(yùn)含豐富的交通運(yùn)行狀態(tài)信息,能系統(tǒng)、全面地再現(xiàn)復(fù)雜的道路交通運(yùn)行場(chǎng)景,對(duì)交通管控至關(guān)重要.

基于車牌識(shí)別數(shù)據(jù)的出行軌跡的研究具有很大挑戰(zhàn),主要原因在于以下2 點(diǎn): 1)受設(shè)備采樣頻率、信號(hào)質(zhì)量、天氣環(huán)境等多種因素影響,導(dǎo)致部分軌跡數(shù)據(jù)錯(cuò)誤或者漏檢,使得車輛軌跡數(shù)據(jù)呈現(xiàn)稀疏不完整性. 2)以往的出行路徑還原方法沒有充分利用視頻圖像檢測(cè)器獲取的駕駛狀態(tài),忽略了出行者路徑?jīng)Q策的主觀行為.

直觀地說,針對(duì)稀疏不完整的車牌軌跡數(shù)據(jù),充分考慮每2 個(gè)監(jiān)測(cè)點(diǎn)之間不同的路線選擇方案,以挖掘駕駛員潛在的行駛規(guī)律,可有效提升算法的魯棒性. 為實(shí)現(xiàn)此目標(biāo),本文提出一種新的OD 軌跡還原算法. 該算法的主要貢獻(xiàn)有: 1)設(shè)計(jì)一種基于K 則最短路徑算法(K shortest paths,KSP)的候選路徑生成方法,以模擬出行者復(fù)雜的路徑?jīng)Q策行為. 2)應(yīng)用變分自編碼器(variational auto-encoder,VAE)對(duì)多個(gè)候選軌跡就行最優(yōu)化估計(jì),以此重建還原車輛的完整通行軌跡. 該算法在杭州市蕭山區(qū)實(shí)際交通小區(qū)進(jìn)行驗(yàn)證評(píng)估. 實(shí)驗(yàn)結(jié)果表明,該方法在軌跡還原精準(zhǔn)度上準(zhǔn)達(dá)到了95%,遠(yuǎn)高于用于對(duì)比的基準(zhǔn)模型. 此外,該方法還被證明能有效適應(yīng)數(shù)據(jù)缺失率高的場(chǎng)景,在基于稀疏數(shù)據(jù)的軌跡重建上顯示出巨大的應(yīng)用前景.

1 OD 軌跡還原算法

本文提出了一種基于稀疏車牌數(shù)據(jù)的軌跡還原算法. 如圖1,該算法框架主要由4 個(gè)模塊組成: 1)出行鏈驗(yàn)證分離; 2)候選路徑生成; 3)路徑校驗(yàn); 4)路徑?jīng)Q策. 本節(jié)將對(duì)以上模塊展開詳細(xì)描述.

圖1 OD 軌跡還原算法框架

為了便于描述,設(shè)定G=(V,E)為交通小區(qū)的網(wǎng)絡(luò)拓?fù)鋱D,V={r1,r2,···,rm}為該小區(qū)路口集合,E={,···}為路段集合,其中,m表示交叉路口數(shù)量,表示第i個(gè)交叉口與第j個(gè)交叉口之間的路段.設(shè)定車牌識(shí)別技術(shù)與路網(wǎng)匹配得到的時(shí)序車牌序列為S={s1,···,sn},同時(shí)將序列中每個(gè)樣本表示為sk=(tk,uk,gk,,dk). 其中,n代表統(tǒng)計(jì)時(shí)間內(nèi)該車輛所有被識(shí)別到的樣本數(shù);tk表示第k條樣本的檢測(cè)時(shí)間;uk表示攝像采集設(shè)備的ID 編碼;gk表示該設(shè)備所在位置,由經(jīng)緯度表示; 為設(shè)備所在路段;dk代表識(shí)別車 輛的行駛方向.

1.1 出行鏈驗(yàn)證分離

對(duì)識(shí)別到的所有行駛狀態(tài)按車牌號(hào)進(jìn)行分組,再以檢測(cè)時(shí)間排序,可得到采樣時(shí)間段內(nèi)每輛車的出行鏈. 如圖2 所示,該出行鏈來自于多個(gè)時(shí)間段統(tǒng)計(jì)聚合,可能包含多個(gè)不同目的的OD 出行. 本節(jié)首先對(duì)整個(gè)出行鏈進(jìn)行驗(yàn)證,結(jié)合相鄰樣本間空間距離與通行間隔將原始時(shí)序數(shù)據(jù)劃分為多個(gè)OD 片段,從而保證軌跡推導(dǎo)模型數(shù)據(jù)的真實(shí)可靠.

圖2 多OD 出行鏈?zhǔn)纠?/p>

具體來說,給予一輛車在統(tǒng)計(jì)時(shí)間內(nèi)的出行鏈,即車牌時(shí)序序列S={s1,···,sn},對(duì)任意2 個(gè)相鄰樣本點(diǎn)si和si+1,通過樣本點(diǎn)中記錄的位置信息gi和gi+1可計(jì)算得到最短的曼哈頓街區(qū)距離d. 同時(shí),相鄰樣本點(diǎn)通行的時(shí)間間隔 ?t可由檢測(cè)時(shí)間ti+1和ti相減得到. 這樣每?jī)蓚€(gè)相鄰樣本點(diǎn)的通行平均速度可以表示為:

然后,判定vi,i+1是否處于預(yù)定的最低通行速度閾值vmin和最高通行速度閾值vmax之間. 當(dāng)vi,i+1偏離預(yù)設(shè)速度閾值時(shí),將該檢測(cè)樣本點(diǎn)si標(biāo)記為上一段OD 的終止點(diǎn),si+1標(biāo)記為下一段OD 的起始點(diǎn).

1.2 候選軌跡生成

出行鏈經(jīng)過驗(yàn)證分離轉(zhuǎn)化為僅包含一個(gè)O 點(diǎn)和D 點(diǎn)的獨(dú)立軌跡片段. 在實(shí)際道路環(huán)境中,設(shè)備的未覆蓋、漏檢或者錯(cuò)檢,導(dǎo)致這些獨(dú)立的OD 片段往往呈現(xiàn)出稀疏不完整的性質(zhì). 為獲取完整的OD 軌跡供后續(xù)分析使用,需要對(duì)缺失的軌跡數(shù)據(jù)進(jìn)行補(bǔ)全還原.

如圖3 所示,車輛在兩個(gè)間斷點(diǎn)有多條距離相當(dāng)?shù)目蛇x通行路徑,直接假設(shè)車輛以最短路徑行駛顯然不再適用. 本文設(shè)計(jì)了一種新的路徑還原思路. 對(duì)兩個(gè)間斷樣本點(diǎn)潛在路徑求解,以模擬真實(shí)道路交通場(chǎng)景下,出行者復(fù)雜的道路選擇; 再對(duì)候選路徑進(jìn)行校驗(yàn),擇優(yōu),以獲取最終的通行路徑.

圖3 OD 缺失拓?fù)鋱D

具體來說,給予分割后的OD 軌跡序列S′={so,···,sd},o,d≤n,生成潛在候選軌跡的步驟如下:

步驟1: 判斷S′中任意2 個(gè)相鄰樣本點(diǎn)所在的路段 和在路網(wǎng)空間中是否相鄰.

步驟2: 如果存在有 和空間不相鄰,采用K 則最短路徑算法(KSP)在交通小區(qū)內(nèi)搜索候選路徑. 根據(jù)實(shí)際道路行駛路徑選擇一般特性,一段短距離OD 點(diǎn)內(nèi)出行可能路徑小于或等于3,由此本文設(shè)定每?jī)蓚€(gè)間斷點(diǎn)的候選路徑數(shù)目不超過3.

步驟3: 匯總并排列組合,得到so至sd中所有可供選擇的候選軌跡集合q1,q2,···,qn. 需要注意,為提高復(fù)雜路網(wǎng)下軌跡生成效率,本文設(shè)定n=10,即僅保留可行軌跡中路徑最短的前10 條路徑.

1.3 路徑校驗(yàn)

生成候選路徑的方式將求解完整出行軌跡的問題轉(zhuǎn)化為從多個(gè)可行路徑中選取一條最符合出行者駕駛風(fēng)格路徑的問題. 為此,本文構(gòu)建了一系列的決策指標(biāo)以模擬出行者路徑選擇決策過程. 從實(shí)際出行決策角度,需要考慮的主要因素包括: 路徑距離、通行時(shí)間、含信號(hào)交叉口、轉(zhuǎn)彎次數(shù)等[11–13]. 然而,以上因素同屬于靜態(tài)因素,缺乏與出行者固有行駛習(xí)慣的關(guān)聯(lián).

為解決這個(gè)問題,本文特別設(shè)計(jì)了通行時(shí)間一致性和軌跡偏好2 個(gè)動(dòng)態(tài)指標(biāo). 其中,通行時(shí)間一致性表示當(dāng)前候選OD 軌跡先驗(yàn)的平均通行時(shí)間與實(shí)際的通行時(shí)間?tqi之間的相符程度,其計(jì)算過程如式(2)所示:

值越大表示該候選路徑與實(shí)際通行路徑越接近.而軌跡偏好程度用于描述該候選軌跡的實(shí)際通行情況占所有軌跡通行情況的比例,求解過程可以描述為:

其中,函數(shù)number(·)表示該路徑在車牌識(shí)別數(shù)據(jù)集中出現(xiàn)的次數(shù),n=10表示生成的候選路徑的數(shù)量.

此外,為區(qū)分每個(gè)指標(biāo)內(nèi)部的顯著性,本文使用zscore 方法對(duì)所有指標(biāo)進(jìn)行歸一化:

其中,ei屬于路徑距離、通行時(shí)間、含信號(hào)交叉口、轉(zhuǎn)彎次數(shù)、通行時(shí)間一致性和軌跡偏好6 個(gè)指標(biāo)的集合,μ表示當(dāng)前指標(biāo)的均值.

1.4 最優(yōu)路徑選擇

通過候選OD 軌跡的各項(xiàng)校驗(yàn)指標(biāo)可計(jì)算得到最合適的行駛軌跡,這本質(zhì)上可視為多屬性決策問題. 以往通常使用主成分分析、灰色關(guān)聯(lián)分析等方法進(jìn)行多屬性決策的研究,但這樣的方法存在計(jì)算復(fù)雜度高,特征提取效率低等缺陷. 受Wu 等人[14]的啟發(fā),他們?cè)陲L(fēng)格遷移任務(wù)中首次提出圖像的風(fēng)格可以由實(shí)例的均值和方差來表示. 基于此,本文設(shè)計(jì)了一種基于VAE 模型的多屬性路徑?jīng)Q策方法. 該方法可以通過VAE 算法的編碼器得到輸入候選軌跡校驗(yàn)指標(biāo)的均值和方差,并以此作為出行者固定的風(fēng)格習(xí)慣,從而將最符出行者出行風(fēng)格的路徑中候選路徑中挑選出來.

圖4 展示了VAE 模型的計(jì)算流程. 基于VAE 的路徑?jīng)Q策方法以候選軌跡的指標(biāo)組成的多維向量作為輸入,通過模型學(xué)習(xí)軌跡指標(biāo)之間的分布關(guān)系. 最終,每條候選軌跡計(jì)算得到的均值和方差會(huì)與代表出行者出行固有習(xí)慣的先驗(yàn)值比較,越接近代表越符合最優(yōu)路徑,如圖5 所示.

圖4 VAE 模型流程圖

圖5 候選軌跡均值方差(▲)與先驗(yàn)值(X)的空間分布

通過VAE 優(yōu)化校驗(yàn)指標(biāo)的目標(biāo)函數(shù)可以表示為:

2 結(jié)果與分析

2.1 數(shù)據(jù)說明

本文所述算法在杭州蕭山S103 交通小區(qū)進(jìn)行測(cè)試驗(yàn)證. 實(shí)施范圍如圖6 所示,該路網(wǎng)包括34 個(gè)路口、50 個(gè)路段. 每個(gè)路段皆配備1–2 個(gè)攝像采集設(shè)備,總計(jì)117 個(gè). 在2021 年5 月6 日至2021 年8 月6 日時(shí)間范圍內(nèi),通過自動(dòng)車牌識(shí)別技術(shù)對(duì)該交通小區(qū)路網(wǎng)內(nèi)車輛的交通狀態(tài)進(jìn)行提取. 所提取識(shí)別數(shù)據(jù)中包含亂碼信息、邏輯關(guān)系混亂 、以及車牌不符合規(guī)范等異常軌跡信息,剔除后最終得到259219 條可用的稀疏車輛行駛軌跡序列. 每條序列包含了檢測(cè)設(shè)備編碼、時(shí)間、地點(diǎn)、車牌號(hào)等信息,詳細(xì)數(shù)據(jù)如表1 所示.

圖6 杭州蕭山S103 交通小區(qū)

表1 預(yù)處理后的車牌識(shí)別

2.2 實(shí)驗(yàn)結(jié)果

本小節(jié)將展示一系列的數(shù)值化和可視化結(jié)果,對(duì)本文提出的OD 還原算法進(jìn)行評(píng)估.

2.2.1 軌跡還原對(duì)比實(shí)驗(yàn)

本文選取了幾個(gè)比較有競(jìng)爭(zhēng)力的模型作為基準(zhǔn)來驗(yàn)證算法性能. 包括: (1)最短路徑法(SP)[15],以間斷點(diǎn)最短路徑作為補(bǔ)全還原的路徑; (2)主成分分析法(PCA)[16],將每個(gè)候選軌跡的校驗(yàn)指標(biāo)映射到2 個(gè)維度,并以此作為均值方差的替代; (3)自編碼器(AE)[17],同PCA,可自動(dòng)學(xué)習(xí)數(shù)據(jù)映射規(guī)律,并映射到2 個(gè)維度.

驗(yàn)證使用的數(shù)據(jù)集是原始車牌識(shí)別數(shù)據(jù)的子集,包括了1208 輛車的總計(jì)15812 條不存在間斷點(diǎn)的軌跡數(shù)據(jù),且每輛車的每個(gè)OD 內(nèi)的軌跡滿足檢測(cè)樣本數(shù)不小于10. 對(duì)于每個(gè)完整OD 軌跡Si′={so,···,sd},實(shí)驗(yàn)中隨機(jī)的刪除首末樣本點(diǎn)間k∈{1,2,3,···,7}個(gè)連續(xù)的節(jié)點(diǎn)以獲取不完整的軌跡. 之后,再通過軌跡還原算法進(jìn)行補(bǔ)全得到完整的重建軌跡S′i′={so?,···,sd?}. 那么OD 軌跡還原算法的準(zhǔn)確率可以表示為:

其中,函數(shù)bool(S′i,S′i′)∈{0,1},當(dāng)重建軌跡S′i′與原始完整軌跡S′i一致時(shí)為1,反之為0.

表2 展示了對(duì)比實(shí)驗(yàn)的結(jié)果,從表中可以發(fā)現(xiàn),SP 算法在軌跡還原的精準(zhǔn)度上表現(xiàn)最差,隨著節(jié)點(diǎn)缺失率的增加,SP 具有最大的降幅(如圖7 所示). 主要原因在于,SP 算法假設(shè)駕駛車輛以最短的路徑行駛,忽略了出行者主觀決策等對(duì)駕駛路徑的影響. 而PCA、AE 和文本提出的算法通過候選軌跡生成模擬出行者的路線選擇過程,在指標(biāo)上明顯優(yōu)于SP 算法. 相較于PCA 和AE,本文使用VAE 對(duì)每條候選軌跡計(jì)算抽象意義的均值和方差,以此作為出行者的出行風(fēng)格、固有習(xí)慣,這促使本文所提出的算法取得更優(yōu)越的性能. 此外,從表2 最后一行指標(biāo)和圖7 的可視化視圖,還可以發(fā)現(xiàn),與表現(xiàn)最好的對(duì)比模型AE 相比,在缺失樣本點(diǎn)低(不超過5 個(gè))時(shí),兩個(gè)算法取得了相當(dāng)?shù)男阅? 但在節(jié)點(diǎn)缺失率更高時(shí),本文的算法表現(xiàn)出更強(qiáng)大的適應(yīng)能力(在缺失節(jié)點(diǎn)為7 時(shí),優(yōu)于表現(xiàn)最好的AE 算法11%).

表2 本文提出算法與對(duì)比算法的準(zhǔn)確率表現(xiàn)

圖7 不同算法的準(zhǔn)確率表現(xiàn)

表3 展示了各個(gè)算法的時(shí)空消耗表現(xiàn). 盡管SP 算法擁有極高的運(yùn)算效率,但在精度上面很難滿足實(shí)際需求. 在精度相對(duì)比較高的PCA、AE 和本文的算法中,本文算法與AE 算法在運(yùn)行效率上都明顯優(yōu)于PCA 算法. 盡管本文所提出的算法擁有最高的參數(shù)量,但減少一定運(yùn)算的時(shí)空效率給算法帶來的是大幅度的精度上的提升.

表3 本文提出算法與對(duì)比算法的時(shí)空消耗

2.2.2 攝像采集設(shè)備覆蓋率分析

利用大數(shù)據(jù)技術(shù)、車牌自動(dòng)識(shí)別技術(shù),借助當(dāng)前高密度、高精度的監(jiān)測(cè)設(shè)備,深挖車牌照的自動(dòng)識(shí)別信息,實(shí)現(xiàn)OD 數(shù)據(jù)與交通運(yùn)行數(shù)據(jù)的智能化提取,是適應(yīng)當(dāng)前復(fù)雜的交通發(fā)展?fàn)顩r與精確的交通數(shù)據(jù)需求的思路.但在實(shí)際道路交通中,并非每個(gè)路口、路段都已部署攝像采集設(shè)備. 研究不同覆蓋率與軌跡還原準(zhǔn)確率的關(guān)系,可以在保證達(dá)到識(shí)別性能和還原效果的情況下,降低設(shè)備覆蓋率,讓軌跡分析系統(tǒng)以更經(jīng)濟(jì)、高效的方式運(yùn)行.

由此,本文進(jìn)一步測(cè)試了不同攝像采集設(shè)備覆蓋率下車輛OD 軌跡還原的準(zhǔn)確率. 從交通小區(qū)所有采集設(shè)備中隨機(jī)刪除10%、20%、30%、40%、60%、60%和70%的設(shè)備以及這些設(shè)備對(duì)應(yīng)的識(shí)別數(shù)據(jù),模擬90%至40%之間以10%為間隔的不同設(shè)備覆蓋率情況,并通過本文提出算法和對(duì)比模型中表現(xiàn)最好的自動(dòng)編碼器(AE)進(jìn)行軌跡的還原重建. 圖8 展示了不同設(shè)備覆蓋率下本文提出算法與AE 算法軌跡還原的精準(zhǔn)度變化情況. 從圖中可以發(fā)現(xiàn),隨著設(shè)備覆蓋率的減少,兩者軌跡還原的精度都有所下降. 且覆蓋率越低,對(duì)應(yīng)的下降幅度越大. 不同的是: (1)本文提出的算法在所有覆蓋率下的精度都優(yōu)與AE 算法; (2)在90%–50%的覆蓋率間,本文提出的算法隨覆蓋率下降帶來的準(zhǔn)確率的衰退不超過6.6%,而AE 在覆蓋率由70%減少60%時(shí),精度就大幅度的衰退了10.3%. (3)在覆蓋率50%-30%之間,雖然兩者精度都大幅衰退,本文算法始終保值更高的精度以及更小的下降幅度. 以上這些觀察證明,在覆蓋率高的情況下,本文算法更加準(zhǔn)確、有效. 且在覆蓋率低的情況下,本文算法依然具有非常良好的適應(yīng)能力.

圖8 不同攝像點(diǎn)位覆蓋率下本文提出算法準(zhǔn)確率表現(xiàn)

2.2.3 敏感性分析

第1.3 節(jié)介紹了影響最終最優(yōu)路徑?jīng)Q策的6 個(gè)關(guān)鍵性指標(biāo): 路徑距離、通行時(shí)間、含信號(hào)交叉口、轉(zhuǎn)彎次數(shù)、通行時(shí)間一致性和軌跡偏好. 計(jì)算選擇路徑與以上指標(biāo)的相關(guān)系數(shù)可以得到每個(gè)指標(biāo)對(duì)最終決策的影響程度. 圖9 展示了各校驗(yàn)指標(biāo)與決策路徑的相關(guān)系數(shù)矩陣,其中,顏色越深代表相關(guān)性越強(qiáng).

圖9 各校驗(yàn)指標(biāo)與決策路徑之間的相關(guān)系數(shù)矩陣

由圖9 可知,本文所提出的時(shí)間一致性和軌跡偏好2 個(gè)動(dòng)態(tài)性指標(biāo)最終的決策路徑保持著較高的相關(guān)稀疏,分別為0.65 和0.77. 在通用的靜態(tài)決策指標(biāo)中,含信號(hào)燈交叉路口數(shù)對(duì)最終決策的影響最高,為0.65.總的來說,本文所提出的2 個(gè)動(dòng)態(tài)性指標(biāo),在最終的軌跡還原中起到了非常積極的促進(jìn)作用.

3 總結(jié)

本文提出一種基于車牌識(shí)別數(shù)據(jù)的城市交通網(wǎng)絡(luò)車輛軌跡重建算法. 基于車牌識(shí)別時(shí)序序列,該方法充分考慮到出行者出行過程中復(fù)雜道路選擇決策過程,從而擬合產(chǎn)生最適合出行者主觀行駛風(fēng)格的通行路徑.通過杭州市蕭山區(qū)實(shí)際交通小區(qū)對(duì)該方法進(jìn)行校驗(yàn),綜合實(shí)驗(yàn)結(jié)果表明了算法時(shí)魯棒可靠的,為稀疏車牌數(shù)據(jù)的軌跡還原提供了一個(gè)強(qiáng)有力的基準(zhǔn).