劉 月

（銀川市勘察測(cè)繪院 寧夏 銀川 750004）

0 引言

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

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

1.1 點(diǎn)到點(diǎn)匹配

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

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

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

基于以上兩個(gè)原因，點(diǎn)到點(diǎn)的匹配一般用在匹配起始位置，即匹配第一個(gè)GPS 點(diǎn)的時(shí)候。 具體過(guò)程是先找到和第一個(gè)GPS 點(diǎn)距離最近的交叉節(jié)點(diǎn)，然后將和該交叉節(jié)點(diǎn)相連通的所有路段作為備選路段用其它匹配方法進(jìn)一步匹配后續(xù)GPS 點(diǎn)。 注意這時(shí)點(diǎn)到點(diǎn)的匹配結(jié)果也往往是錯(cuò)誤的，因?yàn)槲覀儾荒鼙ＷC用戶剛剛是在位于某個(gè)路口的時(shí)候開始匹配算法的， 但是它起碼可以縮小匹配后續(xù)GPS 點(diǎn)時(shí)的備選路段的范圍，并且匹配結(jié)果可以很快被后續(xù)的匹配算法校正。

1.2 點(diǎn)到線匹配

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

圖1 GPS 點(diǎn)到路段的距離

圖2 交叉點(diǎn)附近的點(diǎn)到線匹配

圖3 近似平行路段中間的點(diǎn)到線匹配

圖4 存在異常點(diǎn)情況的線到線匹

點(diǎn)到線匹配實(shí)現(xiàn)起來(lái)也比較簡(jiǎn)單，而且在一般情況下的準(zhǔn)確度也比較高，但是在以下幾種情況下也會(huì)很容易發(fā)生錯(cuò)誤。

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

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

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

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

1.3 線到線匹配

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

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

2 基于地圖拓?fù)浣Y(jié)構(gòu)的地圖匹配算法

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

針對(duì)上述兩個(gè)缺點(diǎn)， 我們可以利用地圖的拓?fù)湫畔⒆鳛檠a(bǔ)充，保證結(jié)果匹配路段的拓?fù)湟恢滦裕⑻岣咂ヅ涞男?。具體方法如下：假設(shè)GPS 點(diǎn)Pt匹配到路段S， 則將S 以及和S 相連通的路段作為GPS點(diǎn)Pt+1的備選路段。 這種方法明顯降低了選擇備選路段的復(fù)雜度，同時(shí)提高了匹配結(jié)果的準(zhǔn)確性。

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

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

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

4 綜合性的地圖匹配算法

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

最典型的是利用地圖幾何信息和拓?fù)湫畔⒌氖噶康貓D匹配算法。矢量地圖匹配算法的步驟大致如下：

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

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

5 結(jié)束語(yǔ)

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

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

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