3S系統(tǒng)中地圖匹配算法的技術(shù)特點探析

劉 月

（銀川市勘察測繪院 寧夏 銀川 750004）

0 引言

“3S 系統(tǒng)”即GIS/GPS/LBS 系統(tǒng)，就是采取GPS 作為定位手段，為用戶提供LBS 服務的嵌入式GIS 系統(tǒng)。 “地圖匹配”研究的問題就是如何在3S 系統(tǒng)的導航地圖和GPS 信號精度都比較低下的情況下，將接收到的GPS 位置匹配到地圖上的實際位置上去。

1 基于地圖幾何信息的地圖匹配算法

1.1 點到點匹配

這種方法簡單易行，運行效率高，切合嵌入式軟件的實時性要求，但缺點也是顯而易見的，具體來講，主要表現(xiàn)在如下幾個方面：

（1）精確度太低，只能匹配到節(jié)點，不能匹配到鏈路或者路段，這是最大的缺點；

（2）跟中間節(jié)點的密度有很大關系。很顯然，特定鏈路上的路段劃分得越細致，中間節(jié)點的數(shù)目越多，點到點匹配的精度就越高。

基于以上兩個原因，點到點的匹配一般用在匹配起始位置，即匹配第一個GPS 點的時候。 具體過程是先找到和第一個GPS 點距離最近的交叉節(jié)點，然后將和該交叉節(jié)點相連通的所有路段作為備選路段用其它匹配方法進一步匹配后續(xù)GPS 點。 注意這時點到點的匹配結(jié)果也往往是錯誤的，因為我們不能保證用戶剛剛是在位于某個路口的時候開始匹配算法的， 但是它起碼可以縮小匹配后續(xù)GPS 點時的備選路段的范圍，并且匹配結(jié)果可以很快被后續(xù)的匹配算法校正。

1.2 點到線匹配

這是最直觀的匹配方法， 其實也是現(xiàn)實世界中采用較多的方法。 具體步驟是分別計算待匹配的GPS 點向待匹配路段的距離，然后選取距離最短的路段作為匹配結(jié)果。 這里的待匹配路段既可以選取地圖上的所有路段（一般是在匹配無歷史歷史記錄的第一個GPS點的情況下），也可以選取落在GPS 點周圍某段距離內(nèi)的路段。另外需要注意的是，路段是線段而不是直線，點到線段的距離跟點到直線的距離是不同的。 如果GPS 點到路段的投影落在路段的延長線上，則一般取GPS 點到路段起點和終點距離的較小值作為點到路段的距離。 如圖1 所示，P0在路段S0上的投影落在S0上，則P0到S0的距離即為P0到S0的垂直距離；P1 在路段S0上的投影落在S0的延長線上，則P1 到S0的距離就是P1 到S0兩端點距離的較小值。

圖1 GPS 點到路段的距離

圖2 交叉點附近的點到線匹配

圖3 近似平行路段中間的點到線匹配

圖4 存在異常點情況的線到線匹

點到線匹配實現(xiàn)起來也比較簡單，而且在一般情況下的準確度也比較高，但是在以下幾種情況下也會很容易發(fā)生錯誤。

（1）在匹配帶方向的路段時。通?，F(xiàn)實世界中的道路都是雙行道，因此在地圖上是由兩條端點互換方向相反的單向路段表示的。點到線匹配僅考慮了路段的位置，沒有考慮路段的方向性，因此是無法區(qū)分兩條端點互換方向相反的單向路段的。

（2）交叉點附近。交叉點是兩條或多條路段交匯的地方，路段的分布比較密集，因此交叉點附近的GPS 點到各路段的距離均比較小，很難利用點到路段的距離將正確的路段篩選出來。 如圖2 所示，P0到三條路段S0、S1和S2的距離相差無已，很容易將P0匹配到錯誤的路段。

（3）在兩條近似平行的路段中間。在現(xiàn)代城市中，道路的規(guī)劃有時候會仿照經(jīng)緯度，構(gòu)建成一個類似于棋盤狀的道路網(wǎng)。 在這種類棋盤狀道路網(wǎng)中，兩條相距不遠的同向道路往往是近似平行的。這時候，如果GPS 點在兩條道路中間不規(guī)則地浮動， 則GPS 點也會相應地匹配到距離最近的路段上去。 如圖3 所示，GPS 點會交替地匹配到S0和S1上，非常不穩(wěn)定，給用戶帶來困擾。

盡管存在著以上不足，但由于點到點匹配實現(xiàn)簡單，因此在地圖精度和GPS 信號精度都比較高， 或者移動設備軟硬件資源比較緊張以至于不適合采用復雜的地圖匹配方法的情況下，仍然經(jīng)常采用點到線的匹配。

1.3 線到線匹配

線到線匹配是將一系列相鄰的兩個或多個GPS 點連成一條線段或折線，然后比較該軌跡折線和備選路段或鏈路的相似度。 這里沒有考慮折線的方向，只考慮其位置和形狀。 通常做法是定義出一種計算兩條折線之間的距離的方法，然后用兩條折線間的距離來衡量它們之間的相似度。

關于兩條折線間的距離一種最簡單的定義是兩條折線上的點的最小距離。 即給定兩條折線A 和B，在A 上取一點a，在B 上取一點b，使得a、b 之間的距離最小。a、b 之間的距離就表示A 和B 之間的距離。 用公式表示為||A-B||min=mina∈A,b∈B||a-b||。

2 基于地圖拓撲結(jié)構(gòu)的地圖匹配算法

基于地圖幾何信息的匹配方法的最大缺點是不能保證連續(xù)GPS點的匹配路段的連續(xù)性，尤其是點到點匹配和點到線匹配，其匹配結(jié)果只是一些離散的路段，相互之間沒有連接成一條連續(xù)折線，這與用戶的運動軌跡的連續(xù)性不相符合。如果我們想在地圖上輸出用戶的運動軌跡，那么基于地圖幾何信息的匹配方法往往顯得力不從心。另外，基于地圖幾何信息的匹配方法在選取備選路段時，往往只能選取地圖上的所有路段，這在地圖數(shù)據(jù)比較龐大時會極大地影響算法的效率。

針對上述兩個缺點， 我們可以利用地圖的拓撲信息作為補充，保證結(jié)果匹配路段的拓撲一致性，并提高匹配的效率。具體方法如下：假設GPS 點Pt匹配到路段S， 則將S 以及和S 相連通的路段作為GPS點Pt+1的備選路段。 這種方法明顯降低了選擇備選路段的復雜度，同時提高了匹配結(jié)果的準確性。

但是，這種方法也帶來一個隱患，即一次匹配錯誤會導致后續(xù)一系列匹配錯誤。 如圖4 所示，P0、P1應該分別匹配到S2和S4，但是如果在匹配P0時錯誤地將其匹配到S1上， 則在匹配時， 由于備選路段為{S1，S3}，會將P1錯誤地匹配到S1或S3上去，或者匹配失敗。

3 基于統(tǒng)計學和模糊理論的地圖匹配算法

與基于地圖幾何信息和拓撲結(jié)構(gòu)信息的地圖匹配算法不同，有一類地圖匹配算法開始引入了統(tǒng)計學和模糊理論的方法。這些算法本質(zhì)上還是基于地圖的幾何信息和拓撲信息的，只是在運算過程和表現(xiàn)形式上運用了統(tǒng)計學和模糊理論的方法。例如，國外有人提出一種叫做路段約化過濾的算法。每一個原始的GPS 點都被分別投影到附近的路段上， 形成一組虛擬的GPS 參考點。 顯然，正確的匹配結(jié)果就是其中某一個GPS 參考點。 兩個連續(xù)的GPS 參考點連接起來形成的矢量線段， 與它們相應的兩個GPS 參考點連接起來形成的矢量線段， 兩者的長度和方向應該是近似相等的?；谶@一點可以過濾掉不符合條件的參考點組合。

4 綜合性的地圖匹配算法

現(xiàn)在成熟的地圖匹配算法一般都是綜合性的，即將多方面的匹配度進行擬合，首先將每一方面的匹配度量化，再乘以某個權(quán)重系數(shù)，累加起來得到一個總的匹配度值?？梢愿鶕?jù)實際情況或?qū)嶋H測試結(jié)果通過調(diào)整權(quán)重系數(shù)來使計算出來的匹配度值更加精確。

最典型的是利用地圖幾何信息和拓撲信息的矢量地圖匹配算法。矢量地圖匹配算法的步驟大致如下：

（1）初始化算法。 當匹配第一個GPS 點，或者由于GPS 信號被屏蔽等原因?qū)е虑懊娴钠ヅ涫r，用點到點匹配或點到線匹配的方法匹配該GPS 點。 點到點匹配和點到線匹配的目的都是為了選擇初始備選路段集，其中點到線匹配是從GPS 點到周圍的路段做垂線，垂線長度小于某個閾值的對應路段均作為備選路段；點到點匹配是首先找到和GPS 點距離最近的交叉點， 然后將所有和該交叉點相連通的路段作為備選路段。

（2）當接收到新的GPS 點Pt時，將Pt-1和Pt 連接形成一條矢量線段Pt-1Pt。 備選路段為當前路段，以及與該路段相連的其它路段。 分別計算Pt-1Pt和每條路段的匹配度， 然后選擇匹配度最高的作為Pt的匹配結(jié)果。

5 結(jié)束語

總之， 我們需要實時地將接收到的GPS 點匹配到最可能的地圖路段上， 并且這些連續(xù)的被匹配的路段要形成一條合理的運動軌跡（即這些路段要兩兩相連，形成一條連續(xù)的折線）。 而如何為當前GPS點選擇最合理的匹配路段就是本課題要研究的問題。

［1］陳佳瑜,肖桂榮. 基于權(quán)重的地圖匹配算法[J]. 計算機工程與應用，2005（11）.

［2］周穎,程蔭杭. 基于曲線擬合的地圖匹配算法[J]. 交通運輸系統(tǒng)工程與信息，2004（02）.