陳沖

【摘要】簡要介紹基于D-S證據(jù)推理的地圖匹配算法的理論概念，以及算法的建立與實現(xiàn)。簡要分析了該算法存在的局限性。

【關(guān)鍵詞】D-S證據(jù)推理；地圖匹配；誤差修正

1. 引言

（1）在車載導(dǎo)航系統(tǒng)中，定位系統(tǒng)的準(zhǔn)確性是非常關(guān)鍵的，只有準(zhǔn)確地知道車輛位置，才能在地圖上正確地顯示車輛位置，并向司機提供準(zhǔn)確的行駛指令。因此，如何向用戶提供實時、準(zhǔn)確的車輛位置就成了車輛導(dǎo)航系統(tǒng)的重點和難點。因此作為汽車導(dǎo)航系統(tǒng)中核心部分的地圖匹配算法研究就顯得尤為重要了。

（2）D-S證據(jù)推理有較強的理論基礎(chǔ)，既能處理隨機性所導(dǎo)致的不確定性，又能處理模糊性所導(dǎo)致的不確定性，依靠證據(jù)的積累，不斷縮小假設(shè)集，將“不知道”和“不確定”區(qū)分開來。該理論最先由Dempster提出，后來由Shafer進一步發(fā)展，所以稱為D-S證據(jù)推理。D-S證據(jù)推理與概率決策理論相比，不但能處理由于知識不準(zhǔn)確引起的不確定性而且你能處理由于未知而引起的不確定性，它作為一種不確定推理理論是概率論的推廣。由于在證據(jù)理論中需要的先驗數(shù)據(jù)比概率推理理論更為直觀、更容易獲得，再加上Dempster合成公式可以綜合不同專家或數(shù)據(jù)，使得證據(jù)理論在專家系統(tǒng)，信息融合等領(lǐng)域得到了廣泛應(yīng)用。

2. D-S證據(jù)推理的理論概念

識別框式描述整個假設(shè)空間所有元素的集合，用θ 表示， θ 中的各個元素要求是互相排斥的。稱函數(shù)m為 θ 上的一個基本概率分配函數(shù)，且滿足以下三個條件：

其中， m（A）表示該證據(jù)支持A的精確程度，A為θ 中的任意一個子集。從定義可以看出，m為函數(shù)和概率函數(shù)P不同，前者把一個單位的總信度分配給θ 的各個子集，而后者把這個總信度分配給θ 的各個元素。也就是說，對于有限集可以 看出，基本概率分配函數(shù)和概率函數(shù)是有差別的。

信任函數(shù)Bel定義為： 信任函數(shù)與m函數(shù)是互相唯一確定的，他們是同一證據(jù)的不同表示。信任函數(shù)Bel（A）表示對命題A的總支持度，或在該證據(jù)下決策者有理由相信A的程度。和概率函數(shù)不同的是，信任函數(shù)不具有可加性。從上式可以得到：

似然函數(shù)pl定義為：其中， pl（A）是所有與A相交的子集的基本概率分配函數(shù)的和，表示證據(jù)不否定A的信任度，顯然，0 信任函數(shù)和似然函數(shù)組合成的信任區(qū)間 描述命題A的確認程度，分別是信任區(qū)間的上界和下界，則命題A的類概率函數(shù)f（A）表示如下，其中|A| 和 |Θ|分別表示集合A、θ 中的元素的個數(shù)。

D-S合成公式如下：假設(shè)性質(zhì)不同的兩個證據(jù)，他們在識別框θ 上的基本概率分配函數(shù)分別為 m1和 m2，則按下式定義的函數(shù)m：

函數(shù)m是識別框 θ上一個基本概率分配函數(shù)，簡記為m=m1 m2 ，即求取正交和，得到綜合概率分布函數(shù)。G、H、A分別是θ的命題，m（A）反應(yīng)了m1和 m2對應(yīng)兩個證據(jù)對命題A的聯(lián)合支持程度。

D-S合成公式反應(yīng)了證據(jù)的聯(lián)合作用。給定幾個同一識別框架上基于不同證據(jù)的信任函數(shù)，如果這幾個證據(jù)不是完全沖突的，就可以利用合成公式計算出一個總的信任函數(shù)，作為這幾個證據(jù)聯(lián)合作用下產(chǎn)生的信任函數(shù)。

圖1誤差矩形

3. 地圖匹配算法的設(shè)計與實現(xiàn)

3.1確定誤差區(qū)域。

3.1.1確定誤差區(qū)域是進行地圖匹配的第一步，以便從這個置信區(qū)域中提取出待匹配道路的信息。所以誤差區(qū)域就是以一定的概率包含車輛的真實位置的區(qū)域范圍，它應(yīng)當(dāng)以一定的準(zhǔn)則進行選擇。若誤差區(qū)域太大則會增加匹配的計算量；誤差區(qū)域過小則可能不包含車輛的真是位置，地圖匹配則會輸出錯誤的位置。因為誤差區(qū)域以一定的概率包含車輛的實際位置，通常根據(jù)概率準(zhǔn)則來確定誤差區(qū)域。

3.1.2除了傳感器本身的誤差以外，數(shù)字地圖的數(shù)據(jù)誤差。計算誤差等都具有不確定性，隨機性，且隨著匹配過程的推進會不斷增大，因此定義誤差橢圓的擴展因子應(yīng)該適當(dāng)?shù)卦龃蟆暗?，判斷哪些路段是否落在橢圓區(qū)域內(nèi)，需要執(zhí)行大量的開方和乘積運算，對于選取候選路段很不方便”為了克服這個缺點，可以將誤差區(qū)域定義為矩形區(qū)域，該矩形為橢圓區(qū)域的最小包圍矩形如圖1所示。

求長和寬的公式如下：

在求出矩形誤差區(qū)域后，誤差矩形內(nèi)與矩形相交的道路即為待匹配路段，就可以進行待匹配道路的提取。

圖2匹配點位置確定

3.2選擇匹配道路。

當(dāng)前時刻車輛正沿著某一條道路行駛，由于車輛定位系統(tǒng)各方面誤差的存在，定位系統(tǒng)給出的車輛軌跡可能偏離車輛實際所行駛的道路。根據(jù)D-S證據(jù)推理理論，首先建立一個識別框，車輛位置信息和方向信息作為兩個初始證據(jù)。

3.3修正定位結(jié)果。

3.3.1確定處車輛所在的道路后，可利用車輛在該道路上的匹配位置來修正定位系統(tǒng)給出的位置通常采用正交投影法來確定車輛的匹配位置。如圖2所示，不存在誤差的情況下，車輛的真實位置是Q點，而由于存在誤差，定位系統(tǒng)給出的車輛位置是偏離道路的S點，S在道路上的正交投影點是P點則P點就當(dāng)作車輛在該道路上的匹配位置。

3.3.2通過解方程可得到P點的坐標(biāo)。跟新此刻定位點的坐標(biāo)，即用計算后的新坐標(biāo)代替定位點的坐標(biāo)，存儲在數(shù)據(jù)庫中，并顯示在電子地圖上P點作為當(dāng)前時刻的匹配位置點可以進行下一時刻的匹配。

3.4地圖匹配算法分析。

該地圖匹配算法直接或間接將投影點作為匹配位置點，消除了路段垂直方向上的誤差，而對于路段水平方向上的誤差卻沒有消除，雖然在一定程度上減小了整個系統(tǒng)的誤差，但是，這對匹配的精度還有一定的影響。由于地圖匹配是一種基于軟件的修正方法，每種算法都有自己的評判標(biāo)準(zhǔn)，也都存在著局限性，結(jié)合實際道路，不同的情況采用不同的匹配算法，將是以后發(fā)展和完善的方向，這將更進一步滿足系統(tǒng)的實時性和精度要求。

4. 結(jié)語

隨著各種技術(shù)的發(fā)展和應(yīng)用，將地圖匹配技術(shù)與GIS相結(jié)合，利用電子地圖數(shù)據(jù)庫的道路信息和交通信息實現(xiàn)車輛自動駕駛將是交通系統(tǒng)的一個重要發(fā)展方向。地圖匹配技術(shù)已經(jīng)成為定位系統(tǒng)中運用地圖信息的一種重要手段。進一步完善地圖匹配技術(shù)將在智能交通系統(tǒng)中發(fā)揮重要的作用。

參考文獻

[1]畢軍、付夢印編?；贒-S證據(jù)推理的車載導(dǎo)航系統(tǒng)地圖匹配算法。[J]北京理工大學(xué)學(xué)報。2002.6.

[2]孫世博?；贕PRS的GPS車輛定位系統(tǒng)及其證據(jù)推理地圖匹配算法。[J]哈爾濱工業(yè)大學(xué)學(xué)報。2006.6.

[3]常菲。現(xiàn)代物流中車輛智能定位與導(dǎo)航系統(tǒng)中關(guān)鍵技術(shù)研究。[J]大連理工大學(xué)學(xué)報。2004.1.