基于多分類的車輛軌跡地圖匹配算法的研究

王麗娟

摘要： 關鍵詞： 中圖分類號： 文獻標志碼： A文章編號： 2095-2163

Abstract： In the vehicle navigation system， the movement track of vehicle on the electronic map reflects the realtime measurement of the GPS devices. This thesis explores a kind of mapmatching method based on multiclassification algorithms， adopts SVM to preprocess the training data and designs an algorithm to select the best parameter of ELM. The experimental results show that the multiclassificationbased approach can achieve higher accuracy and faster matching speed.

0引言

在車輛導航系統中，電子地圖上顯示的車輛移動軌跡反映了通過GPS測量設備實時定位的結果。然而，顯示在地圖上的車輛軌跡可能與真實軌跡不一致，一些軌跡可能偏離了實際路網中的道路，很多定位點并不在道路上，導航效果不是很理想。因此，在進一步挖掘和分析地理信息之前，檢測這些誤差是很有必要的。

地圖匹配是一種基于軟件技術的定位修正方法，其基本思想是將車輛定位軌跡結合所在區域的道路網數據集，由此估計車輛在地圖上的路段信息。本文的研究重點就是如何快速準確地完成地圖匹配。

本研究中使用的數據集包括GPS采樣數據集和北京市路網數據集，在預處理過程中使用了Arcgis軟件劃分路網和格式轉換，此外，使用了Hadoop平臺下的MapReduce計算框架提取車輛軌跡。研究中的另一關鍵部分是分類算法，包括支持向量機算法和極限學習機算法。

1數據分析及算法框架

1.1問題定義

在本論文中，根據數據集特征和算法設計分析的需要，對以下概念進行說明。

定義1路段一個路段r是在兩個道路結點間的路徑。一個路段通常包括了一些必要的其它屬性，比如r.id表示路段r的id，r.oneway表示路段r是單向道還是雙向道。

下面兩條觀察結果有助于設計本論文中的地圖匹配算法。為了避免采樣誤差的影響，只考慮方向角在對應路段角度上下浮動15°的GPS點。具體內容如下。

1）觀察1在單向道上，車輛只能在一個方向上行駛。在這種類型的道路上，GPS點的方向角圍繞一個定角小范圍變化，這個定角由道路形狀和道路位置綜合確定。

2）觀察2在雙向道上，車輛允許在兩個方向上行駛。對某個道路結點，假設所在路段與正北方向夾角是α（0～180°），另一個夾角就是α+180°。因此，在雙向道上的GPS點的方向角分別在α和α+180°周圍小范圍浮動。

問題定義給定路網數據集D，歷史GPS點集合P，確定元素p所屬的路段r.id，其中，p∈P，r∈D。概括地說，地圖匹配過程是GPS點集合映射到路網數據集的過程，即P→D。

在本論文中，使用的歷史GPS數據集是由12 000輛北京出租車在2012年11月收集到的數據 ，基本完整地記錄了北京市出租車的移動情況，也大致能夠覆蓋北京市的所有道路。另外，一個數據集是北京市的路網數據集 ，北京市路網十分復雜密集。路網的基本要素為：點實體（節點）和線實體（路段）。

1.3研究框架

本論文提出的基于多分類的車輛軌跡地圖匹配算法的研究框架如圖1所示。

2基于多分類的車輛軌跡地圖匹配

2.1基于網格劃分的數據預處理

在多分類算法中，當訓練的類別越多，需要的訓練時間也會越長。因為研究的路網數據集中有433 391個路段，全部一起訓練的話，需要的訓練時間是相當長的。因此，擬定采用網格劃分對數據進行預處理，每個網格內的操作能夠并行處理。

2.1.1路網的劃分

假設路網地圖長為L，高為H。研究將整個地圖劃分為N×N個大小相同的網格，每一個網格長為l=L/N，高為h=H/N。又設路網地圖左上角的坐標為p_0 （lat_0，lon_0），地圖內任意一點的坐標為p（lat，lon），那么點p所屬的網格ID由如下公式運算得出：ID=floor（N（lat_0-lat）/h）+floor（（lon-lon_0）/l）+1（2）這里，floor（）為向下取整函數。

確定網格劃分方案后，繼而使用ArcMap中提供的裁剪功能，用于創建一個新的特征文件，即感興趣的區域（Area of interest，簡稱AOI）或研究區域，通常，輸入的特征文件是一個比較大的文件，裁剪出來的文件是另一個特征文件的子集，包含了輸入特征文件的地理特性。而設計過程可分述展開如下。

首先，創建裁剪形狀圖層。裁剪形狀也必須是一個圖層，在ArcCatlog目錄下新建一個shapefile文件，創建好的文件保存在default.gdb目錄下，然后用ArcMap打開，編輯成需要的形狀，此處則編輯成對應位置的矩形框。

然后，用裁剪工具處理。打開ArcMap，在Geoprocessing功能選項里，選擇clip裁剪選項。需要選擇輸入的特征文件、形狀特征文件，此處分別為原始的北京市路網文件和先前創建編輯的特征文件。通過特征文件能夠看到對應的道路網信息也被保存下來，該網格有583個路段，與原始的道路網相比，路段數量大大減少。同時，數據格式與原來完整的路網保持一致。將輸出的特征文件利用ArcMap里的轉換工具layer to kml，轉換成KML（或KMZ）文件，用于在地球瀏覽器中顯示地理數據。endprint

2.1.2糾正路網

直接打開所得的路網裁剪后的KMZ文件，用Google Earth顯示。顯然，矢量路網KMZ文件和衛星地圖上的道路存在著偏移，一些主干道與衛星地圖上的道路并不重合。

實驗處理過程中要對GPS點進行標記，不過GPS點顯示在ArcMap上偏移很大。此外，路網在ArcMap上雖然有道路信息，但不能準確地把GPS點所在的道路分辨出來。所以嘗試將矢量路網地圖和衛星地圖疊加起來以供分析。

疊加之前，需要利用谷地軟件進行糾偏，實驗中對源點坐標和目標點坐標進行參數設置，通過該軟件的坐標糾正功能生成最終的 KML 文件。

糾正以后基本能和衛星地圖重合，把衛星地圖和矢量電子地圖疊加在一起，直接雙擊KML文件上的路段，能夠獲取到道路信息。

2.1.3出租車軌跡的提取

根據網格區域來獲取每輛出租車的GPS采樣軌跡，本文選擇MapReduce計算框架來應用于歷史GPS點數據的研究討論中。分析過程內容如下。

首先，在Map函數中，只提取出租車狀態為0或1的點記錄（分別為空車和載客兩種運營狀態的記錄），同時對每個數據項的類型進行字符檢查和字符數目檢查，以防出現亂碼。

MapReduce框架將所有鍵相同的值歸集在一起傳遞給對應的Reduce函數，此時，鍵是出租車標識符。在Reduce函數里，只保留落在網格區域內的點記錄，將點記錄按照時間依次延展排序。同時，計算當前記錄時間和上一條記錄時間的差值，只有當差值大于30 s才記錄當前的點記錄。此外，還需判斷前后記錄的坐標數據是否相同，若前后兩點的記錄是相同的，只保留一條該位置的記錄。

最后，研究得到每一輛出租車在同一天、同一網格內的GPS點記錄。為方便后續處理，輸出以Excel文件格式組織，每一個Excel文件對應一輛出租車的軌跡記錄。然后使用Excel to kml轉換工具，將滿足要求格式的點記錄Excel文件轉換成KML文件，用于在地球瀏覽器中顯示地理數據。

2.2獲取訓練數據

2.2.1利用GPS數據集進行標注

本文已經得到了目標網格內糾正好的路網矢量地圖和2012年11月中在目標網格內每一輛出租車的軌跡。研究將這些軌跡轉換成能夠在電子地圖上直觀顯示的格式。為了方便標注，將路網矢量地圖和網格內的軌跡疊加顯示在衛星地圖上。根據坐標、時間順序和出租車的行駛方向，就能夠為每一個GPS點標注其所在路段的ID。

將衛星地圖、糾正后的矢量電子地圖和車輛軌跡疊加在一起，再用上述方法標注每一個GPS點，得到的訓練集數據A，可以有效避免由誤差導致的匹配不精確。這樣得到的帶標簽的GPS點記錄準確度比較高。

2.2.2利用路網中的GPS數據進行標注

為了對路網做進一步分析，將目標網格的路網數據（gdb格式）轉換成json格式的文件，由此發現每條路段本身含有大量的GPS點坐標數據，將這些點提取出來（本文用Python語言編寫功能程序），再利用kml to excel工具轉換成KML文件，并用Google Earth軟件顯示在地圖上。結果顯示：其中包含了大量的點，彎曲的路段上的點更加密集。

接下來，深入觀察路段上的點，發現這些點正好落在每條道路上，因此，這些點是每一條道路的關鍵坐標點，而且標志確定了道路的形狀和位置。基于這些關鍵點均來源于自帶路段標簽屬性的路網，因此比較容易地就可獲取其路段ID。

然而，作為訓練數據，這些點還少了方向角這個特征。本文根據連續點間的坐標關系設計出一種方法來計算方向角。給定一組連續的關鍵點，可以通過給出的坐標計算每一個點的方向角。注意，出租車行駛在單向道和雙向道的方向角是不同的，因此要將路網中oneway這個屬性的值利用起來。假設當前點位于單向道上，設其坐標為p_0 （lon_0，lat_0），當前點下一點的坐標為p_1 （lon_1，lat_1）。由平面幾何知識可知，已知平面上兩點的坐標，可以求出一個點相對于另一個點的經度增量和緯度增量，易求得變化率，該變化率即是正切值，相應地，求得反正切值即能求得方向角。假設p_0的方向角是α，反正切由下式可得：α=arctan（（lon_1-lon_0）/（lat_1-lat_0））（3）最后，通過象限處理得到當前點的方向角，這里角度變化范圍是0～360°，順時針方向增加，取整數。如果點在雙向道上，同一個坐標對應兩個點記錄，差別在方向角上，二者的方向角是相反的關系，一個方向角為α，另一個方向角為α+180°。通過這種方式，就可將在一個網格區域內獲取的數據作為訓練數據集B。

2.3插值獲取訓練數據

將多輛出租車的軌跡顯示到地圖上，發現這些采樣點主要分布在道路中心線兩側，部分點偏離較大。據此，本文提出以道路中心線為基準，允許一定范圍內的坐標變化來模擬真實的采樣情況。根據前面的研究，計算得到了每條路段中的關鍵點的記錄，這些記錄自帶路段標簽且補充了方向角屬性，在這些記錄的基礎上進行模擬操作。操作過程可表述如下。

首先，采取等比例插值，插值是比較均勻、線性的。其次，采用兩點之間隨機插值。

經過多次實驗，決定采取如下方案進行隨機插值，插值點的坐標在區間長度為相鄰兩個點坐標的經緯度增量的區間內隨機變化。插值結果比較接近真實的GPS點分布。 為此，研究順次提出各點規律展示如下。

3結束語

本論文提出一種利用模式識別的方法來解決地圖匹配問題。采用支持多分類算法的解決方案來預測GPS點的真實位置，從而將地圖匹配問題轉換成多分類問題，能夠運用多分類算法獲得有效設計解決；提出使用GPS采樣數據集獲取訓練數據的方法；挖掘相關路網數據中路段信息，得到另外一種快速準確獲取帶標簽點記錄的方法，即利用路段本身關鍵點進行插值；進而設計了尋找最優ELM參數的算法，同時，對基本的ELM輸入進行調整，使得匹配精度大幅提升。endprint

但是該方法還有待更詳盡的實驗和分析，未來發展還需要考慮影響匹配結果的潛在因素。

參考文獻：

[1] 杜江平. 基于 GPS/GIS 車輛定位導航系統的研究[D]. 成都： 電子科技大學， 2009.

[2] QUDDUS M A， OCHIENG W Y， NOLAND R B. Current mapmatching algorithms for transport applications： State-of-the art and future research directions[J]. Transportation Research Part C： Emerging Technologies， 2007， 15（5）： 312-328.

[3] BERNSTEIN D， KORNHAUSER A L. An introduction to map matching for personal navigation assistants[J]. Geometric Distributions， 1998，122（7）：1082-1083.

[4] GREENFELD J. Matching GPS observations to locations on a digital map[C]// Proceedings of the 81th Annual Meeting of the Transportation Research Board. Washington DC， USA： [s.n.].2002：1-14.

[5] YAMG Dakai， CAI Baigen， YUAN Yifang. An improved mapmatching algorithm used in vehicle navigation system[C]//Intelligent Transportation Systems， 2003. Proceedings.2003 IEEE. Shanghai， China： IEEE， 2003， 2： 1246-1250.

[6] HUANG Guangbin， ZHU Qinyu， SIEW C K. Extreme learning machine： A new learning scheme of feedforward neural networks[C]// IEEE International Joint Conference on Neural Networks. Budapest， Hungary：IEEE， 2004， 2： 985-990.

[7] 梁冬萍，戴迎春，劉兵. 基于Geodatabase的城市綠化現狀數據庫建設[C]//第七屆ArcGIS暨ERDAS中國用戶大會. 北京：中國地理信息系統協會，中國遙感協會，2006：397-400.

[8] 李銳， 王斌. 文本處理中的 MapReduce 技術[J]. 中文信息學報， 2012， 26（4）： 9-20.

[9] 林關成， 李亞安. 一種支持向量機訓練集選取算法改進[C]//2009年中國西部地區聲學學術交流會論文集. 西雙版納：中國聲學學會， 2009：83-86.

[10]李靜. 支持向量機多分類算法研究[D]. 武漢：湖北大學，2008.

[11]王義發. 車輛定位導航系統中的地圖匹配算法研究[D]. 武漢：武漢理工大學， 2007.endprint