导航中道路匹配算法的设计与实现

1、导航中道路匹配算法的设计与实现（第一次）首先，道路匹配（地图匹配）的定义是：在不同条件下获取的同一物景的 地图之间的配准，同一传感器在不同时间，或不同类型传感器在同一时间，或不 同类型传感器在不同时间所获取的两幅地图中的同一地面点所对应像素之间的 配准。其作用我们小组经过网上的查找认为有3个要点：使空间数据实现更加有 效的融合，实现地图的变化检测和自动更新，实现空间数据的质量评估和位置校正。地图匹配是一种基于软件技术的定位修正方法，其基本思想是将车辆定位 轨迹与数字地图中的道路网信息联系起来，并由此相对于地图确定车辆的位置。 地图匹配应用是基于以下2个假设条件：（1）车辆总是行驶在道路上；（2

2、）采用 的道路数据精度要高于车载定位导航系统的定位精度。当上述条件满足时，就 可以把定位数据和车辆运行轨迹同数字化地图所提供的道路位置信息相比较，通 过适当的匹配过程确定出车辆最可能的行驶路段以及车辆在该路段中的最大可 能位置。如果上述假设不成立，则地图匹配将产生错误的位置输出，并可能导致 系统性能的严重下降。一般认为用于匹配的数字地图误差不应超过巧米（真实地 面距离）。由于陆地车辆在除进入停车场等之外的绝大多数时间内都位于公路网 络中，因此使用地图匹配技术的条件是满足的。地图匹配的算法是曲线匹配原理和地理空间接近性分析方法的融合。曲线匹 配算法的基本思想是：如果对一条曲线做任意数量、任意比例

3、的分割，分割点都 落在另一条曲线上，则两条曲线严格匹配。实际应用中，就是计算一条曲线上相 对均匀的某一数量分割点到参考曲线的距离的平均值，将其作为到参考曲线的平 均距离，并将此平均距离的倒数作为匹配优劣的度量。空间接近性分析方法就是 在已知的可能正确的地理数据集中，按照空间最接近的方法匹配当前定位数据。地图匹配算法可分为2个相对独立的过程：一是寻找车辆当前行驶的道路；二是 将当前定位点投影到车辆行驶的道路上。其基本办法是按照曲线匹配的思想在车 辆航迹的邻近区内搜索所有道路路段及其组合，把这些组合路线分别与车辆航迹 求取匹配度量值，将取得最佳匹配度量值的组合路线作为车辆当前行驶路线。地 图匹配的

4、常用算法有以下几种：直接投影算法；相关性算法；半确定性算法；概 率统计算法；模糊逻辑算法；基于计算几何（非数值计算）知识算法。基于计算 几何（非数值计算）知识算法，根据测量点位坐标有2种思路： （1）不断 判断刚测得的点位于道路的哪一侧，如果刚测得的点与前期测得的某个点位于道 路1的两侧，则车辆在道路1上行驶。如果道路1是一条弯曲的路径，那么经多 次测量，并应用该方法也可以判断车辆所处的道路。（2）逐段计算测量点集的凸 壳，依据道路与凸壳的交判断车辆在哪条道路上行驶。但当测量点全部位于1的 同一侧时，算法失败。另该算法没有考虑测量误差，由此对GPS测量误差的抗噪 性差很有可能使算法失败。在算法

5、设计时基于以下4个方面的考虑：一是效率，地图匹配算法必须能够 满足车辆导航实时、快速的要求；二是精度，地图匹配的日的就是有效地提高车 辆定位日标的精度，并保持定位结果的稳定性；三是不同交通状况分别给出策略 处理以提高道路选取得正确率和缩短匹配时间；四是程序设计，必须用可以量化 的方式保证程序设计的可能性。早期的传统地图匹配算法，通过比较航位推算获得车辆行驶方向和道路向量 的方向，确定车辆是否行驶在道路上。该算法比较简单，但使用范围太窄。当车 辆的行驶路线未知车辆驶出预定路线时算法不在适用。而在我国自1994年GPS系统进入全系统运营以来，我国的GPS产品品种齐 全、应用领域广泛，已成为成熟、稳

6、定的系统。不过，在卫星导航车辆应用的市 场与技术方面，中国远远落后于日、美、欧等发达国家。就我国的车辆导航仪 和车辆监控系统而言，前者又明显落后于后者，这是由于车载导航仪一方面受技 术涉及面广、水准要求高、复杂程度大、研制周期长、价格昂贵等因素的制约， 远不是一般中、小公司所能胜任的；另一方面，出于国家安全考虑，国家对地图 数据进行控制，而且中国正在对基础设施及路网进行大规模升级改造，导致获取 相关信息困难。所以，涉足车辆导航仪领域的国内公司远比车辆监控终端厂商要 少得多。此外，相关的基础配套设施与资源也不完备:如实时交通信息发布和完善 的导航电子地图的提供和更新机制，均没有实际有效的解决方案和途径，因而市 场推进困难重重。 但面对庞大的汽车市场，汽车导航的前景不可估量。国内的 汽车导航企业，如瑞图万方、麦士威、城际高科等出现在国人视线中。而国家也 非常关注导航产业的发展，这对汽车导航的发展能起到很大的推动作用，中国的 汽车导航市场正逐步形成。此同时，海外一些技术成熟的导航品牌也开始大举进 入。此外