基于多準則粒子濾波算法的車輛軌跡重構(gòu)

唐進君，王凱，葉峻青

(中南大學 交通運輸工程學院，湖南 長沙 410075)

車輛軌跡數(shù)據(jù)兼具時空屬性，能夠為許多研究提供數(shù)據(jù)支撐，如行程時間估計[1]、車輛排放估計[2]和OD模式估計[3]等。近些年，隨著位置跟蹤和存儲技術(shù)的快速發(fā)展，人們已經(jīng)能夠獲取大量的車輛軌跡數(shù)據(jù)，但由于設備條件的限制，這些軌跡數(shù)據(jù)中仍存在一些不完整的軌跡。不完整的車輛軌跡會極大地限制后續(xù)研究對軌跡數(shù)據(jù)的應用[4]。因此，如何重構(gòu)車輛軌跡數(shù)據(jù)一直是交通及相關(guān)領(lǐng)域?qū)W者研究的熱點問題。車輛軌跡數(shù)據(jù)通常由2類傳感器采集得到[5]：移動傳感器和固定傳感器。移動傳感器數(shù)據(jù)包括GPS數(shù)據(jù)、智能卡數(shù)據(jù)等；固定傳感器數(shù)據(jù)包括地磁檢測數(shù)據(jù)和自動車牌識別(ALPR)數(shù)據(jù)。其中ALPR數(shù)據(jù)相較于其它交通采集源具有易獲取、數(shù)據(jù)格式豐富、采集持續(xù)時間長等優(yōu)點。目前基于ALPR數(shù)據(jù)進行軌跡重構(gòu)，國內(nèi)外學者已經(jīng)進行了一系列的研究。FENG等[6]采用粒子濾波器作為框架，所有候選軌跡均被視作一個初始粒子，將軌跡時空校正因子作為粒子更新的狀態(tài)輸入粒子濾波器，粒子濾波器的輸出即為重構(gòu)軌跡；YANG等[7]在FENG等[6]研究的基礎(chǔ)上，將路徑流模型與粒子濾波器模型相結(jié)合，融合了宏觀角度和微觀角度的收益，對車輛軌跡進行了更準確的重構(gòu)；RAO等[3]在先前研究[6-7]的基礎(chǔ)上，通過引入時間地理學中的時空棱鏡概念縮小了軌跡搜索的范圍，提高了算法運行的效率，使其更加適應大規(guī)模網(wǎng)絡場景；王龍飛[8]通過把基于限速的拓撲尋優(yōu)法(topologicaloptim iza‐tion based on speed constraint,SC+TO)與TOPSIS法相結(jié)合進行決策完成了車輛出行軌跡的提取及重構(gòu)。阮樹斌等[9]提出了一種k則最短路徑(KSP)和灰色關(guān)聯(lián)法(GRA)的組合算法，KSP算法用于搜索前k條最短路徑組成候選路徑集，GRA算法用于從路徑集決策出最優(yōu)的重構(gòu)路徑。徐建閩等[10]提出了一種基于梯度提升決策樹(Gradient Boosting Decision Tree,GBDT)的車輛軌跡重構(gòu)方法，通過挖掘車牌識別數(shù)據(jù)中與用戶路徑選擇相關(guān)的變量并利用這些變量組成的數(shù)據(jù)集進行訓練還原丟失路徑；QI等[11]在已有研究[3,6-9,12]基礎(chǔ)上提出了路徑長度、道路等級、交叉口個數(shù)、轉(zhuǎn)彎次數(shù)、行程時間一致性和路徑偏好6個決策指標，這些決策指標作為自編碼器模型中的多個屬性以重構(gòu)不完整的車輛路徑。上述方法確定的決策特征大多帶有一定的主觀因素，主觀因素的存在使得該類決策特征忽略了少數(shù)人的出行偏好，降低了重構(gòu)的穩(wěn)定性。徐建閩等[10]提出的GBDT算法將車牌識別數(shù)據(jù)中與用戶路徑選擇相關(guān)的變量(如時間窗、進口方向、下一目標交叉口等)作為決策特征，雖然解決了決策特征帶有主觀因素的問題，但該方法所提出的決策特征存在可解釋性差、不同區(qū)域之間不統(tǒng)一等缺點。本文針對上述重構(gòu)方法的局限性，考慮主觀因素和客觀因素的差異對決策特征進行分類，稱含主觀因素低的決策特征為基礎(chǔ)校正因子，含主觀因素高的決策特征為拓展校正因子。為減小拓展校正因子主觀因素高對結(jié)果穩(wěn)定性的影響，在拓展校正因子的重采樣過程設置了概率參數(shù)，提出了一種粒子濾波框架下的多準則城市車輛軌跡重構(gòu)方法，在保留決策特征可解釋性的同時增加了重構(gòu)的穩(wěn)定性。首先，對重構(gòu)算法的結(jié)構(gòu)和功能進行了介紹；然后，詳細闡述了重新設計后的決策特征；最后，結(jié)合實際路網(wǎng)數(shù)據(jù)驗證了改進算法的有效性。

1 粒子濾波框架下的多準則城市車輛軌跡重構(gòu)方法

1.1 問題描述

車輛軌跡重構(gòu)問題可根據(jù)圖1(a)來進行說明。圖1(a)是一個4×4的網(wǎng)絡，其中方形節(jié)點的路口安裝了ALPR設備，圓形節(jié)點的路口沒有安裝，ALPR設備能直接獲取車輛牌照、車輛經(jīng)過路口時間等數(shù)據(jù)。當車輛在網(wǎng)絡中行駛時，局部路徑可以通過ALPR設備觀測到。假設路口1，5，6，11的設備依次觀測了車輛a，車輛a的路徑鏈可表示為{1，5，6，11}。由于ALPR設備在該網(wǎng)絡的覆蓋率較低，車輛a在節(jié)點6和11之間的行駛軌跡沒有被觀測到。節(jié)點6和11之間共存在22種軌跡重構(gòu)方案。隨著網(wǎng)絡規(guī)模的增大(如圖1(b)所示)，軌跡重構(gòu)方案也會變得更加復雜。因此，如何確定重構(gòu)方案是解決車輛軌跡重構(gòu)問題的關(guān)鍵。本文中的軌跡丟失主要針對路口檢測設備缺失造成的丟失。

圖1 車輛軌跡重構(gòu)問題示意圖Fig.1 Schematic diagram of vehicle trajectory reconstruction

1.2 算法結(jié)構(gòu)

為實現(xiàn)對不完整軌跡的重構(gòu)，本文的重構(gòu)方法主要包含3個模塊，分別是：斷點識別、軌跡搜索和改進后的粒子濾波模型，如圖2所示。以下對3個模塊的功能進行逐一介紹。

圖2 車輛軌跡重構(gòu)算法結(jié)構(gòu)Fig.2 Structure of vehicle trajectory reconstruction algorithm

1.2.1 斷點識別

“斷點”指的是車輛軌跡序列中非連續(xù)路口之間的部分，一旦軌跡序列中存在斷點，那么該軌跡就是不完整軌跡。如圖1(a)所示，假設提取到車輛a的路徑鏈為{1，5，6，11}，通過遍歷其中的路口能發(fā)現(xiàn)路口6與11非連續(xù)形成斷點。因此，斷點識別的主要功能在于找到不完整軌跡中需要重構(gòu)部分的起終點，當一條軌跡存在多個斷點時，以斷點出現(xiàn)的順序進行重構(gòu)。

1.2.2 軌跡搜索

為了搜索斷點部分的可能軌跡并提高搜索的效率，本文在該部分采用Yen算法[13]。Yen算法由Yen在1971年提出，又名k則最短路算法，在軌跡搜索領(lǐng)域一直被廣泛運用[14]。與DFS算法不同的是，Yen算法僅能求出2點間的前k條最短路徑而非全部路徑。然而，通過實驗發(fā)現(xiàn)選用Yen算法進行軌跡搜索在保證重構(gòu)準確率的同時還提高了重構(gòu)算法的運行效率。

1.2.3 改進的粒子濾波器

本文在原有粒子濾波器[6]的基礎(chǔ)上進行了校正因子的修正。首先將上一模塊搜索到的候選軌跡作為初始粒子，利用車輛軌跡的5個時空校正因子，對這些粒子的真實狀態(tài)空間概率進行更新。這些校正因子分別是行程時間一致性因子、可測性準則因子、路徑尺寸因子、轉(zhuǎn)彎次數(shù)因子和取的，定義為基礎(chǔ)校正因子；后面的3個校正因子是考慮駕駛行為特征，包含了主觀因素，定義為拓展校正因子。粒子濾波器的步驟如下。

步驟1：初始化粒子集(x1,x2,…,xI)

將搜索到的候選軌跡x1,x2,…,xI作為初始粒子集，P(x1),P(x2),…,P(xI)表示粒子的先驗概率。在沒有歷史軌跡數(shù)據(jù)的情況下，各粒子的先驗概率被設置為1/I，其中I表示粒子的數(shù)量。

步驟2：重要性采樣

對于i=1,2,…,I，假定粒子的先驗分布服從由上一個的重要性采樣得到的密度函數(shù)。5個重要采樣過程基于5個校正因子。拓展校正因子的重采樣過程在開始前需要進行一次輪盤賭法，輪盤賭法的概率α是事先設定好的，3個拓展校正因子的概率分別設為α，β和γ。若輪盤賭法的結(jié)果在所選擇的概率區(qū)間內(nèi)，那么所有粒子將執(zhí)行該拓展校正因子的重采樣過程；否則，不執(zhí)行?；A(chǔ)校正因子的重采樣過程在開始前則不需要進行輪盤賭法，直接執(zhí)行后面的內(nèi)容。

在第1個重要性采樣(行程時間一致性)中，初始粒子質(zhì)量服從均勻分布，可以表示為表示行程時間一致性概率密度函數(shù)，后驗概率分布服從

行程時間一致性的權(quán)值更新方程為：

其中，表示行程時間一致性更新后可能軌跡i的非標準化權(quán)值；表示可能軌跡i的初始先驗權(quán)值，開始時均為1；yt:t+Δt代表從時間t到時間t+Δt收集的客觀數(shù)據(jù)或經(jīng)驗標準，其中t是開始收集數(shù)據(jù)的時間，Δt是僅取決于車輛軌跡重構(gòu)計算區(qū)間的變量；表示行程時間一致性下可能軌跡i的狀 態(tài) 空 間；表示初始情況可能軌跡i的狀態(tài)空間；表示基于行程時間一致性的可能軌跡i的概率；表示從先驗數(shù)據(jù)到行程時間一致性狀態(tài)空間的轉(zhuǎn)換概率，對于靜態(tài)計算過程，可能的軌跡不存在空間或時間的過渡關(guān)系，故狀態(tài)轉(zhuǎn)移概率可以視為常數(shù)；表示先驗概率密度函數(shù)，該函數(shù)可以看作是一個常數(shù)概率密度函數(shù)。

為了簡化計算過程，同原粒子濾波模型，沒有考慮粒子權(quán)重的歸一化計算；相應地，使用粒子聚集方程計算，其中的粒子權(quán)重為更新后的粒子權(quán)重。粒子聚集方程表示為：

其中，表示行程時間一致性計算后可能軌跡i的粒子聚集數(shù)；N表示粒子總數(shù)目。

在第1次重要性采樣后，還需要進行基礎(chǔ)校正因子的重采樣和若干拓展校正因子的重采樣。第一個重要性采樣過程稱為步驟2.1，計算過程如下：步驟1-步驟2.1-步驟2.2-步驟2.3-步驟2.4-步驟2.5-步驟3，具體流程如圖2所示。

步驟3：輸出真實軌跡

經(jīng)過若干次重采樣過程后，粒子聚集數(shù)最大的可能軌跡作為最優(yōu)軌跡輸出。

2 粒子濾波器中的時空校正因子

2.1 校正因子1：行程時間一致性

區(qū)別于之前的研究[6]，本文采用行程時間分布作為一致性評價準則，該準則需要擬合所有可能軌跡在斷點時間區(qū)間內(nèi)的行程時間分布函數(shù)(本文采用高斯混合模型)，再將真實行程時間代入各分布函數(shù)中得到結(jié)果，如式(3)所示。

其中，表示基于行程時間一致性，可能軌跡i的后驗概率；表示2個ALPR設備間可能軌跡i的平均行程時間；t'(AVI1,AVI2)表示2個ALPR設備間的真實行程時間；Fi(t)表示基于高斯混合模型，可能軌跡i的行程時間分布函數(shù)；

所有軌跡的初始權(quán)重相等，視作1/N，N為粒子總數(shù)。遵循式(3)的概率密度函數(shù)?？梢钥醋魇且粋€常數(shù)概率密度函數(shù)。

2.2 校正因子2：可測性準則

可測性準則是基于ALPR設備檢測誤差的逆向推理過程[5]。有2種原因可能導致ALPR設備沒有檢測到車輛：第1種原因是車輛通過了設置ALPR設備的路口，但由于設備檢測錯誤而沒有檢測到車輛；另一種原因是車輛沒有通過設置ALPR設備的路口。基于這2種原因，當2個ALPR設備間的可能軌跡i包含其他設置ALPR設備的路口或鏈路時，可以認為這些路口或鏈路上的ALPR設備在檢測時出現(xiàn)了錯誤。

其中，表示基于可測性準則，可能軌跡i的后驗概率；ε表示ALPR設備檢測出錯的概率；n表示可能軌跡i中包含其他設置ALPR設備的路口或鏈路的個數(shù)。

2.3 校正因子3：路徑尺寸Path-Size

Path-Size這一概念在Path-Size Logit模型中提出[15]，主要用于解決路徑選擇行為中的路徑重疊問題，盡管該模型有較多的拓展[16-17]，但這些拓展都是在式(5)的基礎(chǔ)上進行的。在這個模型中，效用函數(shù)添加了一個稱為路徑尺寸(PS)的確定性修正項，PS定義為：

其中，PSin表示可能軌跡i的路徑尺寸的大?。沪表示所有組成可能軌跡i路段的集合；lk表示路段k的長度；Li表示可能軌跡i的長度；當路段k在軌跡j上時，δkj的值為1；當路段k不在軌跡j上時，δkj的值為0。若軌跡i與軌跡集Cn中的其他路徑不重疊，則其PSin值為1。否則，與其他路徑共享的路段越多，其PSin值越低。

當可能軌跡i的PSin值越低，該軌跡中的路段重疊指數(shù)越高，重疊指數(shù)高表示這些路段會被更多車輛駛過，該軌跡也越有可能成為真實軌跡。令服從式(6)中的概率密度函數(shù)。可以視作一個常數(shù)概率密度函數(shù)。

轉(zhuǎn)彎次數(shù)校正因子、行駛距離校正因子[8]與路徑尺寸校正因子具有相似的描述，即可能軌跡i的轉(zhuǎn)彎次數(shù)/行駛距離值越小，該軌跡更可能被駕駛?cè)诉x擇，越有可能成為真實軌跡。故和服從的概率密度函數(shù)與式(6)形式一致，不同之處僅在于式(6)中的路徑尺寸被替換成了轉(zhuǎn)彎次數(shù)和行駛距離，和均可視作常數(shù)概率密度函數(shù)。

3 方法驗證與結(jié)果評價

3.1 數(shù)據(jù)預處理

本文所做工作的數(shù)據(jù)來源于長沙市天心區(qū)五一廣場附近ALPR設備所拍攝到的數(shù)據(jù)，數(shù)據(jù)的時間區(qū)間為2019年3月11日00:00至2019年3月17日24:00。本文在研究過程中選取了五一廣場附近的22個安裝了ALPR設備的路口，如圖1(b)所示。

本文使用SQL Server和Matlab對數(shù)據(jù)進行預處理，數(shù)據(jù)集屬性包含：車輛牌照(“湘AMXXXX”)、車輛類型(01或02；01是大車，02是小車)、車輛通過路口時ALPR設備記錄的時間(“2019/3/14 10:33:52”)、車輛通過路口的編號、車輛所在車道的編號、車輛駛?cè)肼房诘姆较?1-4分別代表著：由東往西、由西往東、由南往北，由北往南)。由于圖像識別技術(shù)的局限性，一些車輛的車牌號碼無法被清晰地捕捉到，因此需要將這些未識別的記錄從數(shù)據(jù)集中刪除。另外，由于路口的紅燈使得車輛在路口停留，某些設施識別的數(shù)據(jù)也可能是重復的。故需要從數(shù)據(jù)集中刪除這些重復記錄，重復記錄具體指相鄰的2條記錄包括時間字段在內(nèi)完全相同。

在數(shù)據(jù)預處理完成后，通過車牌號分類來提取車輛出行軌跡，最終得到的車輛軌跡形式為一個按車輛通過時間排序的路口編號列表。這樣的軌跡可能是由車輛在一段時間內(nèi)的多次出行組成的。在此基礎(chǔ)上，還需要使用出行時間閾值B來分割該軌跡，這樣才能保證每個列表中存儲的都是車輛的單次出行。本文將單次出行定義為車輛連續(xù)通過2個路口的時間間隔不超過時間閾值B。如果時間間隔大于B，將較長的出行劃分為2個較短的出行。閾值B可以通過式(7)確定：

其中，T是研究區(qū)域各路口間行程時間集合，T={t1,t2,t3,…,tn}，該集合通過統(tǒng)計車輛經(jīng)過2個路口的差值來得到；t為可變時間閾值，本文將t設置為5m in。

3.2 軌跡重構(gòu)與結(jié)果分析

首先從ALPR數(shù)據(jù)提取出車輛初始軌跡，由于所選取的研究區(qū)域的ALPR設備基本上覆蓋了各主要路口，因此提取到的初始軌跡大多是完整的，驗證集由這些完整軌跡組成。為測試所提出的軌跡重構(gòu)算法的效果，假定部分路口未設置ALPR設備，例如，當覆蓋率為70%時，會有30%的路口未設置ALPR設備，即7個路口；當覆蓋率為50%時，會有50%的的路口未設置ALPR設備，即11個路口，以此類推。這些未設置ALPR設備的路口將從完整軌跡中剔除，從而生成丟失樣本集。將丟失樣本集代入算法中進行重構(gòu)，重構(gòu)結(jié)果與原軌跡一致則視作成功，準確率根據(jù)重構(gòu)成功的軌跡數(shù)量與總重構(gòu)的軌跡數(shù)量之比得到。為確定拓展校正因子最合適的概率參數(shù)，對概率α，β和γ：(0.1，0.1，0.1)、(0.1，0.1，0.2)、(0.1，0.1，0.3)、……、(1.0，1.0，1.0)，共1 000種參數(shù)組合進行實驗。根據(jù)實驗結(jié)果，將概率參數(shù)α，β和γ設置為準確率最高的參數(shù)組合(1.0，0.1，0.5)。

由于算法的穩(wěn)定性需要多組實驗結(jié)果來進行驗證，因此選取一周7天7個早高峰6個晚高峰共13個時段的數(shù)據(jù)，每個時段的數(shù)據(jù)進行10次實驗，算法可以得到130組結(jié)果。如圖3所示，橫軸表示實驗序號，縱軸表示軌跡重構(gòu)的準確率。路網(wǎng)ALPR覆蓋率設置為40%～90%之間。

圖3 車輛軌跡重構(gòu)結(jié)果Fig.3 Vehicle trajectory reconstruction results

為了突出算法的有效性，進行如下幾組對比實驗。

1)將本文方法與TOPSIS算法及候選圖算法進行比對。將每次實驗設定為相同的條件用3種算法進行計算，得到圖4的結(jié)果。

圖4 70%覆蓋率3種算法準確率對比Fig.4 Accuracy comparison of three algorithmsw ith 70%coverage

通過以上結(jié)果可以看出粒子濾波算法的結(jié)果最穩(wěn)定，在70%ALPR覆蓋率的路網(wǎng)中，平均準確率能達到94.8%，TOPSIS決策法次之，最短路徑法結(jié)果波動最大。該結(jié)果說明對于重構(gòu)車輛軌跡，本文提出的算法相較于TOPSIS決策法和最短路徑法具有更高的準確率和穩(wěn)定性，在實際應用中的效果更好。

2)探究3種算法在無檢測數(shù)據(jù)路口個數(shù)、斷點間距離、斷點間行程時間遞增的情況下，軌跡重構(gòu)的準確率變化，結(jié)果如圖5所示。

圖5(a)是軌跡重構(gòu)準確率與斷點間距離的關(guān)系，隨著斷點間距離的增加，重構(gòu)準確率有略微下降的趨勢，當斷點間距離為0m時(斷點的起終點相同)，3種算法的重構(gòu)準確率最低。這是因為當斷點起終點相同時，可搜索到的軌跡數(shù)量會大大增加，從中確定重構(gòu)方案將會變得十分困難。

圖5(b)是軌跡重構(gòu)準確率與斷點間行程時間的關(guān)系，橫坐標是斷點間真實行程時間與最小行程時間之比，該比例能客觀反映真實行程時間的相對長度，行程時間越長，重構(gòu)的難度越大，準確率越低。主要原因在于：行程時間是軌跡重構(gòu)的重要決策特征，隨著行程時間的增大，與其匹配的軌跡重構(gòu)方案的距離及包含路口個數(shù)都會增加，軌跡重構(gòu)方案的數(shù)量會增大，重構(gòu)真實的車輛軌跡會變得更加困難。與另外2種算法相比，本文提出的算法對于行程時間較長的斷點仍能得到更準確的重構(gòu)方案。

圖5 不同影響因素對算法準確率的影響Fig.5 Influence of different factorson the accuracy of the algorithm

圖5(c)是軌跡重構(gòu)準確率與斷點間無檢測數(shù)據(jù)路口個數(shù)的關(guān)系，無檢測數(shù)據(jù)路口數(shù)量越多，重構(gòu)的難度越大，準確率越低。該現(xiàn)象出現(xiàn)的原因與圖5(b)相似，主要是斷點間無檢測數(shù)據(jù)路口個數(shù)增多導致軌跡重構(gòu)方案的數(shù)量增大，使得軌跡重構(gòu)的難度增加。另外，從圖中可以發(fā)現(xiàn)3種算法對于無檢測數(shù)據(jù)路口個數(shù)較多的斷點，其重構(gòu)結(jié)果都較差，這將是算法改進的一個方向。

3)為了表示算法相較于原先粒子濾波算法做出的改進，將使用高斯混合模型與傳統(tǒng)行程時間一致性準則的算法進行對比實驗，得到圖6的結(jié)果。

圖6 行程時間一致性的算法準確率對比Fig.6 Comparison of algorithm accuracy of travel time consistency

結(jié)果顯示在70%的覆蓋率下，使用高斯混合模型作為行程時間一致性準則得到的平均準確率為94.84%，使用傳統(tǒng)行程時間一致性準則得到的平均準確率為93.45%。該結(jié)果說明利用分布函數(shù)評價行程時間一致性能夠更好描述各軌跡行程時間的整體分布狀態(tài)，有助于提升軌跡重構(gòu)的準確率。

4 結(jié)論

1)提出了一種粒子濾波模型框架下多準則為主體的軌跡重構(gòu)方法。本文將這些準則劃分為基礎(chǔ)校正因子和拓展校正因子，并基于拓展校正因子的主觀性對粒子濾波的重采樣過程進行了重新設計。真實路網(wǎng)數(shù)據(jù)的實驗結(jié)果表明改進后的粒子濾波模型相較于原粒子濾波模型能夠得到更高的軌跡重構(gòu)準確率。

2)提出的方法與其他軌跡重構(gòu)方法進行了比較實驗，結(jié)果驗證了所提出的方法具有更高的準確率和穩(wěn)定性。

3)通過對結(jié)果的進一步分析，算法的主要不足表現(xiàn)在當重構(gòu)無檢測數(shù)據(jù)路口個數(shù)較多、時間與距離較長的斷點時準確率較低，未來可從這些方面對軌跡重構(gòu)算法進行優(yōu)化。