虽然车载导航定位系统已经比较成熟，但汽车却一直行驶在道路上其算法也是依据行驶的距离和方位就能很好地匹配，而人的运动却复杂得多，因为人的运动包括水平面的运动和垂直方向的运动，也就是说匹配应该是三维匹配，所以匹配算法应包括两个方面：一是依据所走路线的改变而进行的匹配（平面匹配）；二是沿地物轮廓线的螺旋上升而进行的匹配（高程匹配）。该文综合了平面与垂直两个方向运动，提出了一种在三维空间中对人的运动进行高精确度跟踪的匹配算法
（一）概述
在GPS信号因遮挡而丢失的情况下，其定位误差将增大甚至可能出现不能定位的情况，这就需要建立完善的定位算法来覆盖这些地区对人的行动进行高精度的跟踪，使用加速陀螺传感器配合GPS接收器的个人定位系统已经发展成一种成熟的定位方法，但是定位误差的积累却是不可避免的。车载GPS地图匹配算法中是假设用户一直在与地图相对应的道路上行驶的前提下，不断修改用户位置的估计值，因此这种匹配算法远远不能满足个人定位系统的定位要求。因为从步伐大小和行走的方向中得到的数据远没有从车轮中得到的速度和方向准确，另外在车载GPS的匹配算法中假定汽车总是行驶在路上，允许系统不断修正汽车的估计数据，使之与数据库中的由点线组成的道路相一致。而个人的运动却是复杂的，个人运动很难达到总是在道路的中心行走或者以固定的速度行驶，例如从道路的这一边到那一边，垂直方向如爬山上楼梯等。为了解决这一问题，提出了一种组合地图匹配算法，此算法使用三维数据库，把运动的区域（道路、山、楼梯等）作为一多边形来看待，这样能够很好地解决个人运动的不确定性，包括平面和垂直运动。
（二）个人定位系统的匹配算法及其研究发展
从大的方面划分目前通用的算法主要分为两类：一类方法是根据个人运动过程中经过的明显特征点（例如出现拐弯）进行的匹配，也就是说当个人的运动中出现明显特征点时，根据电子地图中对应的地物网格的相似性和映射关系，决定人最可能走在哪一条道路的哪一侧。匹配的一般思路是“在拐弯处拐弯”，但这是没有规律的事件经常会出现到交叉路口不拐弯的情况，由于匹配的过程是按一定的时间间隔进行的，所以不拐弯的情况会带来误差的积累。另一种算法是实时计算估算点到与其对应的地图匹配点的距离，保证了在人离开匹配道路一定距离范围内，能够对估算点进行重新定位，从而找到正确的匹配点。虽然这种方法有效地避免了由于误差的积累所造成的错误匹配，但是此算法设计思想的前提是，假定匹配边是正确的，匹配过程中只对估算点进行修正，而不能对匹配边修正，一旦错误地选择了某一条匹配轮廓线，则错误的匹配将一直延续下去。大量的跑车实验和模拟实验发现这种错误的匹配开始往往出现在道路交叉口，总之这两种方法都是各有优势与缺点，于是在这两种通用算法的基础上我们提出综合这两种算法的地图匹配算法。
（三）设计原理
(1)组合匹配算法原理
在对算法进行详尽的描述之前我们先对算法的基本框架和原理作一些解释基准数据库包括两部分:一是组成地物轮廓线的点数据；二是由节点和线组成的网状数据。估算点和其对应修正点的坐标和时间分别存储在这些数据库中。
只要没有超出某一地物区域（如双线墙的边界线），则人每走一步的估算位置按其实际坐标投影在地图上，也就是将估算点重新定位在由地物轮廓线组成的面上，而不是由节点和线组成的网格上，当运动轨迹和地物轮廓线出现交叉点时，采用局部修正算法把此交叉点和前一交叉点之间的所有点位置局部修正到正确的地形上。这是一种不断修正的方法，边修正边实时地记录位置。
循环使用局部修正算法，如果运动轨迹拐弯角度大于某一阈值，则对角度变化前后之间轨迹上的所有点进行全局修正。使用全局修正算法能够将运行轨迹按转弯角度正确地拟合到匹配道路上，当然全局修正算法使用的是网状数据库。
(2)局部修正匹配算法
当人的运行轨迹与地物轮廓线出现交叉点时，根据轨迹和轮廓线组成的角度来对估算点进行重新定位。如果角度小于阈值，则认为错误的定位是由于速度陀螺仪的漂移误差引起的，修正方法以前一拐弯点为中心按比例旋转当前位置点到正确的方向；如果角度大于阈值，一般是因为距离误差使得运行轨迹与地物轮廓线相交，解决方法是调整轨迹的长度对当前位置重新定位。
(3)全局修正匹配算法
使用同一方向的数据过程中，如果在短距离内突然出现大幅度的匹配角度变化，则匹配算法应该从局部修正算法转到全局匹配算法。在交叉点的附近可以设置一定的阈值半径，按照变化的角度在网格数据库中查找拐弯点或者曲弧判断出用户最可能在哪一条道路的哪一侧运行。根据对应的匹配形状修正轨迹的长度和角度。
（四）算法设计
(1)主程序流程
1)从位置数据存储器中取出当前估算点和前面匹配点的坐标和时间（x，y，z，T）。
2)计算出两点之间的运行轨迹。
3)通过拟合函数对误差进行修正，得到正确的距离和角度即运行轨迹。拟合函数的拟合系数是由前面的匹配得到
4)从数据库中取出估算点附近的地物数据。
5)判断轨迹是否穿过其地物轮廓线，如果穿出了则转到局部匹配算法；如果没有越过轮廓线，则把估算位置的坐标和时间作为修正点的坐标和时间存储。
6)把当前位置的修正值存入位置数据库中。
主程序流程如上图所示。
（2）局部修正匹配算法流程
1）判断轨迹和轮廓线的交点是否位于另一地物的入口，如果正好位于另一地物的入口，则把估算位置和时间作为修正位置和时间存入数据库。如果交叉点没有位于两地物的边界，则把整条路径从最近的拐弯点开始计算。
2）计算路径上每一步的角度并且和阈值作比较，得出最近的拐弯点，并计算出此拐弯点的坐标和时间。
3）在路径与地物相交的轮廓线上判断交叉点的附近有没有其他地物的入口。
4）如果存在与其他地物的交叉点，则把与轮廓线的交叉点定位在其他地物的入口点。
5）如果拐弯点的附近没有其他地物的入口，则计算路径和轮廓线的角度。如果拐角≥90°则把地物轮廓线绕最近的拐弯点旋转180°得出夹角。
6）如果角度<90°，则把此角和阈值相比较，若夹角小于阈值，则把路径绕最近拐弯点转过此角度；若大于阈值，则把估计值定位到距离轮廓线30cm的地方继续向前进行匹配。
7）修正路径上所有点的坐标和时间一并存储。
8）记录下修正前后的距离和角度的比率，计算出距离和角度的修改系数并存储。
局部修正匹配算法流程如下图所示：
（3）全局修正匹配算法
1）从数据库中取出此拐弯点附近一定范围内的所有节点和边。
2）根据节点和边计算出当前拐弯点和前面节点的距离。
3）在距交点的距离<</span>阈值的范围内找到最符合的节点，否则退出匹配过程。
4）在所有与此节点有连接的边中找到形成此角度的最短的边。
5）从此节点起改变路径的形状，使以后的运行轨迹以最近似的角度使之与估算位置相拟合。
（五）结论
对于以上介绍的算法，主要用于在三维空间中对个人运动的跟踪。通过对个人定位系统中模拟数据的真值和误差的分析，表明此组合算法不仅适用于三维空间的定位，而且极大地提高了个人的定位精度
联系客服
