浅谈基于D—S证据推理的地图匹配算法研究

陈冲

【摘要】简要介绍基于D-S证据推理的地图匹配算法的理论概念，以及算法的建立与实现。简要分析了该算法存在的局限性。

【关键词】D-S证据推理；地图匹配；误差修正

1. 引言

（1）在车载导航系统中，定位系统的准确性是非常关键的，只有准确地知道车辆位置，才能在地图上正确地显示车辆位置，并向司机提供准确的行驶指令。因此，如何向用户提供实时、准确的车辆位置就成了车辆导航系统的重点和难点。因此作为汽车导航系统中核心部分的地图匹配算法研究就显得尤为重要了。

（2）D-S证据推理有较强的理论基础，既能处理随机性所导致的不确定性，又能处理模糊性所导致的不确定性，依靠证据的积累，不断缩小假设集，将“不知道”和“不确定”区分开来。该理论最先由Dempster提出，后来由Shafer进一步发展，所以称为D-S证据推理。D-S证据推理与概率决策理论相比，不但能处理由于知识不准确引起的不确定性而且你能处理由于未知而引起的不确定性，它作为一种不确定推理理论是概率论的推广。由于在证据理论中需要的先验数据比概率推理理论更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据，使得证据理论在专家系统，信息融合等领域得到了广泛应用。

2. D-S证据推理的理论概念

识别框式描述整个假设空间所有元素的集合，用θ 表示， θ 中的各个元素要求是互相排斥的。称函数m为 θ 上的一个基本概率分配函数，且满足以下三个条件：

其中， m（A）表示该证据支持A的精确程度，A为θ 中的任意一个子集。从定义可以看出，m为函数和概率函数P不同，前者把一个单位的总信度分配给θ 的各个子集，而后者把这个总信度分配给θ 的各个元素。也就是说，对于有限集可以 看出，基本概率分配函数和概率函数是有差别的。

信任函数Bel定义为： 信任函数与m函数是互相唯一确定的，他们是同一证据的不同表示。信任函数Bel（A）表示对命题A的总支持度，或在该证据下决策者有理由相信A的程度。和概率函数不同的是，信任函数不具有可加性。从上式可以得到：

似然函数pl定义为：其中， pl（A）是所有与A相交的子集的基本概率分配函数的和，表示证据不否定A的信任度，显然，0 信任函数和似然函数组合成的信任区间 描述命题A的确认程度，分别是信任区间的上界和下界，则命题A的类概率函数f（A）表示如下，其中|A| 和 |Θ|分别表示集合A、θ 中的元素的个数。

D-S合成公式如下：假设性质不同的两个证据，他们在识别框θ 上的基本概率分配函数分别为 m1和 m2，则按下式定义的函数m：

函数m是识别框 θ上一个基本概率分配函数，简记为m=m1 m2 ，即求取正交和，得到综合概率分布函数。G、H、A分别是θ的命题，m（A）反应了m1和 m2对应两个证据对命题A的联合支持程度。

D-S合成公式反应了证据的联合作用。给定几个同一识别框架上基于不同证据的信任函数，如果这几个证据不是完全冲突的，就可以利用合成公式计算出一个总的信任函数，作为这几个证据联合作用下产生的信任函数。

图1误差矩形

3. 地图匹配算法的设计与实现

3.1确定误差区域。

3.1.1确定误差区域是进行地图匹配的第一步，以便从这个置信区域中提取出待匹配道路的信息。所以误差区域就是以一定的概率包含车辆的真实位置的区域范围，它应当以一定的准则进行选择。若误差区域太大则会增加匹配的计算量；误差区域过小则可能不包含车辆的真是位置，地图匹配则会输出错误的位置。因为误差区域以一定的概率包含车辆的实际位置，通常根据概率准则来确定误差区域。

3.1.2除了传感器本身的误差以外，数字地图的数据误差。计算误差等都具有不确定性，随机性，且随着匹配过程的推进会不断增大，因此定义误差椭圆的扩展因子应该适当地增大“但是，判断哪些路段是否落在椭圆区域内，需要执行大量的开方和乘积运算，对于选取候选路段很不方便”为了克服这个缺点，可以将误差区域定义为矩形区域，该矩形为椭圆区域的最小包围矩形如图1所示。

求长和宽的公式如下：

在求出矩形误差区域后，误差矩形内与矩形相交的道路即为待匹配路段，就可以进行待匹配道路的提取。

图2匹配点位置确定

3.2选择匹配道路。

当前时刻车辆正沿着某一条道路行驶，由于车辆定位系统各方面误差的存在，定位系统给出的车辆轨迹可能偏离车辆实际所行驶的道路。根据D-S证据推理理论，首先建立一个识别框，车辆位置信息和方向信息作为两个初始证据。

3.3修正定位结果。

3.3.1确定处车辆所在的道路后，可利用车辆在该道路上的匹配位置来修正定位系统给出的位置通常采用正交投影法来确定车辆的匹配位置。如图2所示，不存在误差的情况下，车辆的真实位置是Q点，而由于存在误差，定位系统给出的车辆位置是偏离道路的S点，S在道路上的正交投影点是P点则P点就当作车辆在该道路上的匹配位置。

3.3.2通过解方程可得到P点的坐标。跟新此刻定位点的坐标，即用计算后的新坐标代替定位点的坐标，存储在数据库中，并显示在电子地图上P点作为当前时刻的匹配位置点可以进行下一时刻的匹配。

3.4地图匹配算法分析。

该地图匹配算法直接或间接将投影点作为匹配位置点，消除了路段垂直方向上的误差，而对于路段水平方向上的误差却没有消除，虽然在一定程度上减小了整个系统的误差，但是，这对匹配的精度还有一定的影响。由于地图匹配是一种基于软件的修正方法，每种算法都有自己的评判标准，也都存在着局限性，结合实际道路，不同的情况采用不同的匹配算法，将是以后发展和完善的方向，这将更进一步满足系统的实时性和精度要求。

4. 结语

随着各种技术的发展和应用，将地图匹配技术与GIS相结合，利用电子地图数据库的道路信息和交通信息实现车辆自动驾驶将是交通系统的一个重要发展方向。地图匹配技术已经成为定位系统中运用地图信息的一种重要手段。进一步完善地图匹配技术将在智能交通系统中发挥重要的作用。

参考文献

[1]毕军、付梦印编。基于D-S证据推理的车载导航系统地图匹配算法。[J]北京理工大学学报。2002.6.

[2]孙世博。基于GPRS的GPS车辆定位系统及其证据推理地图匹配算法。[J]哈尔滨工业大学学报。2006.6.

[3]常菲。现代物流中车辆智能定位与导航系统中关键技术研究。[J]大连理工大学学报。2004.1.