結合行駛場景語義的軌跡-路網實時匹配方法

傅 琛，黃升鈳，湯 焱，吳杭彬,3，劉 春,3，姚連璧,3，黃 煒

1. 同濟大學測繪與地理信息學院，上海 200092； 2. 北京大學地球與空間科學學院，北京100871； 3. 同濟大學城市交通研究院，上海 200092

近年來，隨著各種感知技術與傳感器設備的發展，自動駕駛技術成為新的研究熱點。自動駕駛過程中，實時地圖匹配技術在車輛定位、路線規劃、實時導航、路況上報與更新、駕駛決策等過程中起到了重要的作用[1]。

地圖匹配技術(map matching)是指將單個或系列GNSS點與地圖匹配的過程，其本質是利用地圖對GNSS數據進行約束。在實時導航、軌跡數據分析等領域中，地圖匹配作為數據分析的前期處理流程，為原始數據賦予路網語義信息，并為路徑規劃、交通分析、軌跡分析等技術提供基礎數據[2]。

針對不同特性的GNSS數據與地圖數據，學者們提出了多種地圖匹配算法和多種地圖匹配算法分類體系。文獻[3]對2007年以前已有的地圖匹配算法進行了回顧，將地圖匹配算法分為基于幾何的算法、基于拓撲的算法、基于概率的算法與使用先進技術的算法。文獻[4]根據地圖匹配算法的時效性將地圖匹配算法分為在線匹配算法[5-8]與離線匹配算法[9-12]。在線匹配算法(又稱局部匹配)需要實時或在較短時間內根據當前定位點數據或結合歷史匹配結果，將當前點捕捉至地圖上[13]；而離線匹配(又稱全局匹配)是在已知完整軌跡的情況下對軌跡進行整體匹配[12,14-17]。應用于導航和自動駕駛的地圖匹配算法需要在短時間內確定車輛位置，因此需要在線匹配算法。引入隱馬爾可夫模型[18]、模糊匹配理論[19]等先進方法的在線匹配算法在處理采樣頻率較低的軌跡時占有優勢，但通常計算復雜度較高[4]、存在一定的延時，難以適用于硬件處理能力有限、對實時性要求高的場景。

隨著城市不斷建設完善、電子地圖技術不斷發展，城市電子地圖越來越復雜，尤其是在城市主干道、高架快速路等路段，在三維空間中不同高度的道路在平面地圖上重疊、交織，單一采樣點搜索到的備選路段數量快速上升。當前對地圖匹配技術的研究中，針對高架沿途路段匹配問題的研究較少，文獻[19]利用出租車數據中的特定字段，如載客、載客狀態變化等屬性，結合車輛的行駛速度與行駛模式，通過模糊推理系統推斷車輛是否在高架上。而實際情況可能不滿足假設的某些條件要求(如在高架堵車時，高架上車輛也會出現走走停停的模式)，從而造成錯誤匹配。

駕駛過程中拍攝的圖像蘊含著豐富的信息，隨著圖像采集設備的普及和成本的降低，部分研究開始使用駕駛過程中拍攝的圖像作為GNSS軌跡數據的補充。目前此類研究通常將圖像用于車道線識別，結合車道級高精度地圖實現在單一道路內部的車道匹配和相對定位，而非作用于軌跡與不同道路間的匹配。文獻[20]對手機拍攝的圖像進行逆透視變換和Hough變換提取車道線，并結合車輛行駛方向確定行駛車道。文獻[21]同時使用圖像提取的車道線和拓撲匹配法分別進行車道級地圖匹配，最終使用擴展卡爾曼濾波將兩種匹配結果與GNSS軌跡、航位推算結果進行融合，提高了車道級相對定位精度。

綜上所述，現有的普通在線匹配算法在高架、立交等復雜區域容易出現誤匹配的現象，而結合圖像進行復雜道路場景下道路級軌跡匹配的研究較少。針對這一問題，本文利用與行車軌跡同步采集的系列行車記錄圖像，提出了一種結合行駛場景分類的地圖匹配技術，利用圖像確定車輛與高架道路的關系，進而提高在線匹配算法在高架路段的匹配正確率。

1 結合行駛場景分類的軌跡-路網實時匹配方法(DSCMM)

1.1 數據定義

本文使用的軌跡-相片數據來源于自帶定位功能的行車記錄設備或無人駕駛車。在車輛行駛過程中，按照一定采樣頻率對車輛位置進行定位，在定位的同時保存相應的視頻幀圖像，作為屬性數據附加在定位點上，得到一組軌跡-相片數據。相關定義如下。

定義1：采樣點p

p={timestamp,lon,lat,speed,direction,image}

單個采樣點是由單臺設備使用其定位模塊獲取車輛當前位置信息，并同步記錄當前時刻視頻圖像得到的一組數據集合。其中，timestamp代表采樣點的時間戳，(lon,lat)代表車輛所處經緯度，speed代表GNSS設備采集的采樣點車速，direction代表車輛行駛方向的方位角，image代表與當前采樣點同步采集的行車記錄圖像。

定義2：車輛軌跡T

T={p1,p2,…,pn}

車輛軌跡T是指由同一車輛按照一定時間間隔連續采樣得到的一組順序排列的采樣點集合。n表示軌跡點的個數。

定義3：城市道路網絡G

G=(Node,Seg)

城市道路網絡G為由節點與路段構成的有向圖，其中，Node表示兩條道路的交點，在節點處，車輛可以在相鄰道路內按照轉向規則進行轉移；Seg表示路段，是指兩個節點之間表示道路中心線的單向或雙向線段，一條道路由多個路段組成。各路段具有相應的道路類別屬性。

定義4：候選路段集C

C=(Seg1,Seg2,…,Segm)

候選路段集C表示當前待匹配點p的候選路段集合。m代表集合中的路段數量。

定義5：最佳匹配路段M

對當前采樣點的備選路段集C，以匹配指標得分最高的路段Segj作為最佳匹配路段M。

定義6：行駛場景定義

行駛場景指車輛行駛過程中所處的道路環境，考慮到地圖匹配的難點所在，本文將車輛行駛場景分為城市快速道路、普通道路、室內道路(隧道、地下停車場等)3類。圖1給出了3種類型典型場景的圖像。

圖1 各行駛場景行車記錄圖像Fig.1 Images of each driving scene

1.2 結合行駛場景分類的軌跡-路網實時匹配方法框架(DSCMM)

本文提出的結合行駛場景分類的軌跡-路網實時匹配方法(a real-time map matching method for road network using driving scenario classification，DSCMM算法)(圖2)，將車輛或設備實時采集的圖像所獲得的場景語義信息加入匹配過程，提高行駛車輛位于城市快速路、普通道路、室內道路等場景時實時地圖匹配的精度。

圖2 算法流程Fig.2 The workflow of map-matching algorithm

算法包括候選路段搜索、行駛場景分類和地圖匹配計算等3個步驟。輸入采樣點后，在路網數據內搜索候選路段集；當車輛處于復雜道路區域時，利用訓練好的行駛場景分類模型對圖像進行分類，計算圖像屬于各類行駛場景的概率；計算當前采樣點候選路段集中每一條路段各相應指標得分，綜合評價該路段得分，取其中得分最高的路段作為當前采樣點的匹配結果，完成單個采樣點的匹配。

1.3 候選路段集搜索

GNSS設備采集的采樣點存在定位誤差，且路網中的路段表示的是道路行駛方向的中心線，在實際行車過程中，行駛車道與道路中心線之間存在一定偏差。因此，對當前采樣點pi，設置一定閾值d構建緩沖區，與緩沖區相交道路將會被識別為當前采樣點pi的候選路段集Ci。地圖匹配的目的，就是從Ci集合中選擇最合適的匹配結果。

當候選集合Ci中只有一類道路時，現有算法已經能完成地圖匹配，不需要進行分類。而當Ci中存在不同類型的道路時(如快速路與普通道路)，傳統的地圖匹配方法存在困難，因此需要借助軌跡點的視頻圖像數據進行場景分類，提高匹配精度。

1.4 行駛場景分類

本文采用支持向量機完成行駛場景的分類。支持向量機(support vector machine，SVM)是文獻[22]提出的一種機器學習模型，其本質為構造能正確劃分數據集且幾何間隔最大的超平面。針對非線性分類問題，SVM將樣本映射到高維線性特征空間，從而轉化為線性可分問題進行求解[23]。利用支持向量機對圖像進行分類，實際上是將圖像每一像素當作一個特征值，利用支持向量機對不同類別圖像的特征進行分類訓練，獲得當前樣本下最佳分類超平面，并利用該分類結果對輸入圖像進行預測，獲得其對應的分類。SVM模型進行預測的時間復雜度為O(M·S)，其中M與核函數相關，S為支持向量數[24]。

在行車軌跡的對應圖像中，當車輛在高架下方行駛時，天空會被高架橋遮擋；在高架或高速上行駛時，多數情況下不會受到遮擋，且畫面內容與普通道路區別較大；而隧道(包括地下停車場等)內的圖像也與其他場景的圖像存在較大區別。基于各類場景的特點，這些場景存在較大的可分性，本文基于與采樣點pi對應的圖像image，利用SVM支持向量機對圖像進行分類，將行駛場景分為快速路(包括高架快速路和高速公路)、普通道路(包含高架輔道及高架附近普通道路場景)、室內(包括隧道、地下停車場等)3種場景。利用SVM模型對圖像進行預測，得到輸入圖像屬于各類別的概率P

(1)

1.5 地圖匹配指標計算

本文提出的結合行駛場景分類的軌跡-路網實時匹配方法綜合考慮了駕駛過程中的場景語義信息、車輛行駛方向信息、距離指標、鄰接指標等，通過不同指標的綜合運算，確定候選路段集中各路段的匹配概率。

1.5.1 行駛場景指標

(2)

式中，i表示第i個采樣點；Pi,express、Pi,normal、Pi,indoor分別表示當前圖片為快速道路、普通道路和室內道路的概率。

(3)

例如，假設當前點Pi對應圖像的分類結果為Pi,express=0.95，Pi,normal=0.03，Pi,indoor=0.02。若某候選路段為城市快速路，則其行駛場景指標為0.95；若另一候選路段為普通道路，則其行駛場景指標為0.03。

1.5.2 方向指標

(4)

圖3 方向指標Fig.3 Schematic diagram of direction index

式中，αj表示當前采樣點pi的車輛行駛方向與備選路段集Ci中第j條路段首尾方向之間的夾角，當備選路段為雙向道路時，使用兩個方向中的較小角度作為兩個方向的夾角。使用指數函數降低大角度備選路段的匹配可能性，并增加對小角度區域的容忍性。k為縮放因子(k>0)，用于控制方向指標在最終得分中的影響力。

1.5.3 距離指標

采用零均值的高斯分布的概率密度函數[25]作為距離指標，對候選路段是采樣點真實匹配路段的概率進行評估

(5)

1.5.4 鄰接指標

鄰接指標是指對當前采樣點pi的第j條備選路段，若該備選路段與上一采樣點pi-1的最終匹配路段Mi-1共享至少一個節點(Node)，則認為該路段與上一采樣點的匹配路段鄰接，即該路段可能與上一采樣點的匹配路段直接連接，或為同一路段。鄰接指標函數定義為

(6)

自動駕駛車或行車記錄設備一般以高頻率采樣得到數據，因此采樣點之間距離近，采用鄰接指標可以提高匹配正確率，同時也避免了使用最短路徑算法產生的計算量。

1.5.5 最優匹配選擇

假設以上各指標之間相互獨立，用聯合概率計算當前采樣點pi的候選路段Ci中，第j條候選路段Segj是真實匹配路段的概率，則各路段的最終得分的計算方法為

(7)

遍歷候選路段集Ci中的各路段得分，將得分最高的路段作為最優匹配結果。

2 試驗與分析

2.1 試驗數據

使用3組位于上海市的行車軌跡和OpenStreetMap數據進行試驗，具體信息見圖4和表1。軌跡1和軌跡2為正常條件下采集的數據，天氣狀況好，光照適宜，圖像清晰；軌跡3則在早晨5～6點采集，光照較弱，天氣狀況差，全程降雨且部分路段為大暴雨，能見度較差。軌跡1～3途經上海內環高架、中環高架、逸仙高架、滬嘉高速、京滬高速、滬昆高速等城市快速路和高速路及其附近普通道路，以及大柏樹立交、邯鄲路地道、外環立交、莘莊立交、共和新路立交等復雜道路區域。

圖4 試驗軌跡Fig.4 Trajectories used in the experiment

表1 試驗數據情況

使用3條試驗軌跡的圖像和部分零散圖像構建行駛場景分類數據集，通過人工判斷標注每張圖像的行駛場景類別。數據集包含各類場景圖像共7801張，其中城市快速道路5980張，普通道路1031張，室內道路790張。數據集中包含了不同清晰度、不同天氣(晴朗、小雨、中雨、暴雨)拍攝的圖像。

2.2 對比方法及評價指標

本文選取了3種在線匹配算法進行對比：

(1) 最短距離地圖匹配方法[13](簡稱point-to-curve算法)。該算法只使用距離指標，將與采樣點最近的路段作為匹配結果。

(2) 局部增量算法[26](簡稱Incremental算法)。該算法使用距離和角度差加權計算候選路段的相似度，采用一種前瞻規劃算法計算沿所有候選路段前進k步之后的總相似度，從中選出相似度最高的作為匹配結果。

(3) 在線隱馬爾可夫匹配法[18](簡稱OHMM算法)。隱馬爾可夫模型被廣泛應用于地圖匹配算法中，該類算法核心是將每個采樣點的備選路段作為整條軌跡中的一個狀態，通過計算輸出概率與相鄰狀態之間的轉移概率，輸出全局可能性最高的路徑。

地圖匹配領域常用匹配率[27]、召回率、精確率[28-29]作為評價指標。

其中，匹配率是指在所有匹配結果中，匹配正確的采樣點數占總采樣點數的比例，計算公式見式(8)。匹配率越高，說明錯誤匹配的點越少，匹配方法越有效。受GNSS定位精度影響，采樣點在路段交點附近時較難判斷車輛真實行駛的路段，本文采用以下標準判斷采樣點是否匹配正確：

(1) 對任一采樣點p，經過匹配計算后當其匹配路段屬于該軌跡真實路段集時，認為該采樣點匹配正確。

(2) 對于OHMM、Incremental等采用滑動時間窗口的地圖匹配算法，其匹配結果是一段匹配路段集，因此在對比這兩種方法時，本文使用point-to-curve法將滑動時間窗口內的各采樣點匹配到匹配路段集上，采用(1)指標判斷該采樣點匹配正確情況。

(8)

召回率和精確率計算公式分別為

(9)

(10)

召回率越高，匹配結果中真實路徑的長度越長，算法對真實路徑的重建效果越好，匹配結果中漏匹配路段越短；精確率則衡量算法匹配結果中誤匹配的比例，精確率越高，匹配結果中誤匹配的路段越短。

2.3 試驗參數設置

在本文中，各計算過程使用的參數設置如下：

Incremental算法的參數為：μd=10,a=0.17,nd=1.4,μα=10,nα=3，其中除nα外均為原文推薦參數。

為了保證實現在線算法，OHMM算法中最大滑動窗口尺寸設置為5，并使用A*最短路徑算法計算轉移概率。

同時，為比較相關算法在不同采樣頻率下的匹配性能，本文逐步提高采樣間隔至15秒，利用2.2節提出的指標對比各種相關算法。由于各算法均未開源，本文按照文獻內的算法描述實現了相應算法。

使用開源機器學習庫scikit-learn[30]訓練行駛場景SVM分類模型，其中核函數使用多項式核函數(poly核函數)，為了計算各分類概率，probability參數設為True。使用行駛場景數據集60%的圖像進行訓練，其余圖像進行測試。SVM模型訓練和預測的速度受到特征維度的影響，為了加快速度，在試驗中將原始大小為1920×1080像素的圖像統一縮小為192×108像素并轉換為8 bit灰度圖像。本文使用SVM模型輸出圖像對應不同類別的概率，時間復雜度略高于僅輸出分類結果，但通過試驗其速度仍在可接受范圍內。

2.4 試驗結果與分析

2.4.1 行駛場景分類效果

利用行駛場景分類數據集中的訓練集訓練SVM模型，在測試集上進行測試，得到的五折交叉驗證平均分類準確率為98.0%，測試集混淆矩陣與各類別召回率、精確率計算結果如下。

表2 行駛場景分類的混淆矩陣與召回率、精確率計算結果

2.4.2 不同方法的匹配結果對比

將本文方法與3種對比方法分別作用于3條軌跡，并對比在不同采樣間隔下的試驗結果(見圖5和表3)。其中，實線代表本文方法，其余線型代表其他3種對比方法。橫軸的采樣間隔代表將原始的數據按不同的間隔(2～15 s)采樣。

表3 4種算法匹配精度

圖5 3段軌跡試驗結果Fig.5 The experiment result of all trajectories

在原始采樣間隔1 s的情況下，本文算法匹配率達96.68%，召回率達99.47%，精確率達到90.59%，表明在實時匹配的情況下，本文算法可以保證較高匹配正確率，且能較完整地恢復行駛軌跡，漏匹配的現象不明顯；匹配出的路段中，誤匹配的情況較少。

隨著采樣間隔的增加，采樣點之間的距離增大，本文算法的匹配率與精確率受到的影響較小(匹配率從96.68%至97.17%，精確率從90.59%至95.04%)，召回率有所下降(從99.47%至90.86%)，這是因為本文算法只獲取與采樣點對應的匹配路段，隨著采樣點之間的距離增大，可能會出現跳過某些中間路段的情況[31]，因此召回率會有所下降。

在軌跡2中，本文算法在召回率這一指標上弱于OHMM算法。召回率表示正確匹配路段長度占整個軌跡所有路段長度的比例，由于本文算法僅針對單點進行匹配，當時間間隔增大時，本文算法會跳過部分路段，因為這些路段上沒有對應的采樣點。而OHMM使用隱馬爾可夫模型，基于路網拓撲計算轉移概率從而恢復車輛途經的路段，匹配結果連續性更強但可能出現“繞路”的現象，漏匹配較少而錯匹配較多，因此OHMM表現出召回率較高而精確率低的特點。

本文方法與其他3種算法的匹配精度都會隨著采樣間隔的增大而受到影響，但本文算法在采樣間隔增大后，仍保持較高水平。表3為4種算法在3條軌跡1～15 s采樣間隔的平均精度統計結果。本文算法在1～15 s的采樣間隔下平均匹配率為96.86%，平均召回率為97.17%，在4種算法中平均匹配精度最高。

2.4.3 不同算法在復雜路段的比較

在傳統算法中，高架的上下匝道與立交等復雜區域是容易匹配錯誤的地方，因此，選擇軌跡1與軌跡2中經過的復雜區域進行對比，如圖6、圖7所示。

圖6 采樣間隔為2 s情況下4種算法在復雜路口的匹配表現Fig.6 The matching performance of the four algorithms with overpass (sampling interval=2 s)

在復雜路口與高架道路區域，本文算法能夠較好區分高架道路與平行地面道路，從而在復雜路口與高架道路區域實現較好匹配；而其他算法都有出現不同程度的誤匹配與漏匹配現象。

2.4.4 不同算法的計算性能對比

對所使用的4種實時匹配算法進行了計算性能上的對比，采用單點匹配耗時、平均延時、內存消耗量等指標衡量不同算法的計算性能，結果見表4—表5。

在匹配效率方面，本文算法對每個采樣點實時匹配，不存在匹配延遲現象，而OHMM與Incremental算法都有較大的延遲，延遲的長度與最大滑動窗口的尺寸以及采樣頻率有關。在單點匹配時間方面，由于DSCMM算法不涉及復雜的網絡計算，匹配速度較快，單點匹配耗時小于100 ms，雖略慢于point-to-curve算法，但差異較小；DSCMM中的圖像分類過程也未對匹配效率產生明顯影響。

在內存占用量上，4種算法占用內存差異較小(表6)。OHMM算法由于在最短路徑計算過程中涉及對圖的存儲與計算，需要占用更大的內存空間。由此可見，本文算法雖然引入圖像進行地圖匹配，內存占用并未明顯增加，適合用于移動端開發。

圖7 采樣間隔為2 s情況下4種算法在高架道路區域的匹配表現Fig.7 The matching performance of the four algorithms with elevated road (sampling interval=2 s)

表4 1～15 s采樣間隔下平均單點匹配耗時表

表5 1～15 s采樣間隔下平均延時表

表6 內存占用量對比

3 結 論

地圖匹配在自動駕駛、智能交通等領域應用廣泛。傳統的地圖匹配算法在高架、立交等場景容易產生誤匹配，從而對自動駕駛、智能交通造成影響。本文借助帶有圖像的軌跡數據，提出將圖像提取的行駛場景類別信息加入地圖匹配的技術思路，進一步提出采用行駛場景、距離、方向和鄰接等四個指標，計算采樣點與候選路段的匹配概率，從而獲得最佳匹配結果。

從試驗結果看，本文提出的DSCMM算法在1～15 s的采樣間隔下都保持較好的匹配精度與匹配穩定性，整體性能優于現有的算法；同時算法計算耗時短，內存占用較少，適合在移動端實現在線計算。因此，本文算法在復雜城市路網(尤其是高架路網區域)能實現較好的在線匹配效果，在未來可以應用于實時車輛定位與實時軌跡追蹤，為自動駕駛提供服務。

本文算法在高架匝道出入口處有時也會出現誤匹配。這是由于本文算法引入的行駛場景尚未涵蓋上下匝道場景，因此針對此類場景還需借助更多的圖像樣本完成場景識別。在本文算法實現的道路級地圖匹配基礎上，還可以進一步發掘序列圖像的作用，通過識別前方車輛、單目測距實現交通路況監測。目前已有研究使用單目相機拍攝的行駛場景圖像提取車道線，結合高精度地圖進行車道級定位，本文算法可以與相關研究結合，提供更好的道路級定位基礎。單目相機采集的圖像存在一定的局限性，例如單向4、5車道的場景下由于視角有限邊界車道線較難識別；前方車輛對車道線形成遮擋等。如何融合多傳感器，提供快速準確、低成本、多場景適用的高精度匹配結果是未來的研究方向。

致謝：感謝弈人(上海)科技有限公司、弈人數據開放平臺(1Rendata)為本文研究提供數據。