淺談基于D—S證據(jù)推理的地圖匹配算法研究

陳沖

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

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

1. 引言

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

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

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

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

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

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

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

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

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

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

圖1誤差矩形

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

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

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

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

求長和寬的公式如下：

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

圖2匹配點(diǎn)位置確定

3.2選擇匹配道路。

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

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

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

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

3.4地圖匹配算法分析。

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

4. 結(jié)語

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

參考文獻(xiàn)

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

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

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