一种利用隐马尔可夫地图匹配算法增强手机基站定位精度的方法
一种利用隐马尔可夫地图匹配算法增强手机基站定位精度的方法
【技术领域】
[0001] 本发明属于地图匹配修正技术领域，涉及一种利用隐马尔可夫地图匹配算法增强 手机基站定位精度的方法。
[0002] 地图匹配是目前广泛应用于导航系统定位的一种修正方法，是一种以计算机软件 技术为基础，通过特定的模型和算法，对导航、定位中的误差进行修正的技术。就是将车辆 获取的带有误差的车辆轨迹信息，运用一定方法和算法匹配到数字交通地图上的正确位 置。通过使用地图匹配算法，可以较好的弥补定位点存在的精度误差，因此地图匹配技术也 是提升导航、定位系统性能的一项重要技术。这种匹配技术前提是假定车辆必须行驶在路 上，使用模式识别理论综合分析定位点形成的轨迹和电子地图中的道路网信息，将测得的 车辆位置信息和数字交通地图中的相关数据进行对比，并使用算法对定位点进行匹配，最 终得出车辆所在路段，并相应找出车辆在该路段上的具体位置，然后将车辆定位点由该道 路段之外的位置投影到该道路段上，从而校正了定位点的误差。
【背景技术】
[0003] 当前常用的地图匹配算法有点到点、点到曲线（最短距离法）、曲线到曲线、基于 模糊逻辑、模式识别、误差代价函数等。在实际运用中，无论采用哪一种大都是通过比较定 位轨迹与侯选道路数据形状的相似性、定位轨迹与候选道路方向的相似性、定位轨迹到侯 选道路距离的远近，以及利用路网的拓扑性质来确定车辆行驶道路。
[0004] 点到点和点到曲线的算法实现比较简单，不需利用路网的连通性和历史轨迹，具 有实时性的优点，但此方法对定位精度要求较高，并且路段间距离较近时无法完成相关匹 配。曲线到曲线的算法则利用了道路网的连通性和历史轨迹，匹配率较高。但这种方法需 要知道车辆行驶起始节点，并且要求定位轨迹与道路具有相当的相似性才能实现算法。误 差代价函数算法综合利用了各种定位信息和路网信息，匹配准确率高，适合于复杂的道路 网络，但比较复杂。
[0005] 通过对手机定位误差的实验分析可知，手机定位点随机分布在路段周围，手机定 位误差较GPS大，且定位采样频率较低，因此定位轨迹的形状同真实行驶路线的相似性不 明显，而现有算法大都是通过比较定位轨迹与侯选道路数据形状、方向的相似性，定位轨迹 到侯选道路距离的远近，以及利用路网的拓扑性质来确定车辆行驶道路。若仅用形状相似 性规则判断行驶路段，极易导致误匹配错误。
[0006] 此外，现有算法大都以定位信息精度和定位采样频率较高的GPS定位数据为基 础，由于手机定位的定位信息精度和采样频率较低，这些算法均不能直接用于以手机基站 定位数据为定位信息的匹配算法。
【发明内容】
[0007] 隐马尔可夫模型能够有效地平滑整合定位误差数据和路径约束。利用隐马尔可夫 地图匹配算法来提高手机基站定位的精度。定位点匹配到候选匹配道路上的概率称作初始 匹配概率，候选匹配道路发生转换的概率称作道路转移概率，使用动态编程来快速找到初 始匹配概率和道路转移概率乘积最大的路径。考虑到车辆在实际行驶过程中不可能频繁地 转换道路，计算定位点道路转移概率时引入了约束限制进行改进，从而提高了性能。
[0008] 本发明用模拟数据检验时表明，即使采样周期长达30秒，误差也仅为0. 11%，在 较长的采样周期中，该方法对测量值噪声误差的鲁棒性高达50米的标准偏差。在隐马尔可 夫地图匹配算法中，路段之间的转换是通过路网的连通来管理。如图1所示，HMM离散状态 是队个道路段，用ri表示，其中i= 1…Ny不同道路段之间的转换发生在道路相接的交叉 路口。zt表示某一时刻测量的坐标值，t= 1时，临近zi的三条道路用三个黑点在第一列中 表示。t= 2时，分别从这3条路上最近的点指向靠近z2的两条道路。t= 3时做同样的工 作。每个t时刻选取的道路段组成一个道路网格，目标是在道路网格中找到最可能的路径。
[0009] 本发明的方法利用隐马尔可夫地图匹配算法来提高手机基站定位的精度，将定位 点匹配到候选匹配道路上的概率称作初始匹配概率，将候选匹配道路发生转换的概率称作 道路转移概率，使用动态编程来快速找到初始匹配概率和道路转移概率乘积最大的路径。 考虑到车辆在实际行驶过程中不可能频繁地转换道路，在计算定位点道路转移概率时引入 了约束限制进行改进，从而提高性能。
【附图说明】
[0010] 图1是Zt候选匹配道路段ri及道路段间转换示意图。
[0011]图2是测量值zt在候选匹配道路段ri上的候选匹配点示意图。
[0012] 图3是本发明的示例图。
[0013] 图4是As修正示例图。
[0014] 具体步骤
[0015] 以下结合技术方案和附图详细叙述本发明的具体实施例。
[0016] 1、初始匹配概率
[0017] 点zt与每一条临近的道路ri存在一个匹配概率p (z 11巧）。xt，i表示点z画配到道 路A上的点。由图2可以发现，点z i匹配到候选匹配道路r pivh上的候选匹配点为x 1;1， Xl，2, Xl，：3。坐标点和候选匹配点的大圆距离为IIZt_Xt，iIIgmt。相对于t+l时的点Zt+1 来说，zt+1匹配到道路r」上的点为X t+1,」。点xt,i和点X t+1,」之间车辆行驶的距离称为"路径 距Nl，记做IIxt,厂Xt+1，jIIroute。
[0018] 对于正确匹配来说，坐标点和匹配点之间的这种误差是由定位误差形成的。算法 模拟的定位误差为零均值的高斯误差，这意味着：
[0020] 〇在式中代表定位测量值的标准偏差。
[0021] 初始匹配概率31i，i= 1…队，其表示在地图匹配开始运行前，从所有路段中找出 车辆所在路段的概率。当部分HMM的构想值均匀分布于31i上时，假设没有测量值被采用， 则算法在第一个测量值上开始，这时有Jri=p(zt |ri)，即使用第一测量值Zl。
[0022] 2、道路转移概率，将候选匹配道路发生转换
[0023] 同每个测量值zt-样，下一个测量zt+1也有一个可能匹配道路的列表。转移概率 是指在这两个时间（t到t+1)内，车辆在候选匹配道路之间的转移概率。对于测量值\和 其候选匹配道路段A来说，在ri上最可能匹配点是xu。同样，测量值zt+1在其候选匹配道 路段r」上的候选匹配点是Xt+u。我们比较测量点之间的"路径距离" | |MUte和 大圆距离I|zt-zt+1| |gMatc;iMle，正确匹配时这两个值相当接近，通过比较这两个值就可以判 断道路是否发生转换。
[0024] 举例说明，在图3中有三个道路段ivrjPr3，两个测量点\和zt+1。测量点\有 Xt，l和Xt，：3两个候选匹配点，测量点Zt+1的候选匹配点为Xt+1』。IIZt_Zt+lIIgmtotei#两个测 量点的大圆距离，路径距离有两个，分别为llx^-Xt+ull^tdP|^^-\+1，2||"_。与不正 确匹配相比，正确匹配时的路径距离更接近大圆距离。
[0025] 该算法通过对正确匹配的大圆距离和路径距离差的绝对值进行分析，得出指数概 率分布：
[0030]其中，r和r指的是车辆的真实行驶道路段。
[0031] 3、优化
[0032] 考虑到正常行驶时，驾驶人员在到达目的地之前会尽量沿同一条道路上行驶，不 会轻意改变行驶道路，更不会频繁地转换道路。因此频繁转换的候选匹配道路可能是由于 定位误差产生的错误匹配。为此，我们引入一个参数As来对这一行为进行约束。当定位 点的候选匹配道路发生改变，候选匹配点离开原行1驶的道路，其路径距离就远离大圆距 离50米进行惩罚，就是当路径距离大于大圆距离时，路径距离加上50米，路径距离小于大 圆距离时，路径距离减去50米。不正确匹配点的路径距离就会远离大圆距离，算法更能找 出正确匹配点。
[0033] 在图4中有三个道路段段rp1~2和r3，两个测量点zt和zt+1。第一个测量点zt候 选匹配道路有A上的候选匹配点为Xm，第二个测量点zt+1在候选匹配道路ri，r2,r3上的 匹配候选点分别为11+1，14 +1，24+1，3。|^^+1||~。^ ;16为两个测量点21和21+1之间的大 圆距离，路径距离有三个，分别为II Xy-Xt+u||Mute，||Xw-Xt+u||Mute和 |Ixw-Xt+i，」|MUte〇 从图中可以看出IIxy-Xt+ul|MUte和IIxy-Xt+ul|MUte距离非常接近，如果不引入As进行 约束，就有可能发生错误匹配。由于从候选匹配点到候选匹配点Xt+u的路径距离在道 路巧上，期间没有发生道路转换，而候选匹配点Xt，i到候选匹配点xt+1，2的路径距离包括在 道路r^r2上的两段距离，期间发生了道路转换，因此我们给路径距离IIxu-Xt+ul|MUJj口 上一个As进行约束，首先比较大圆距离| |zt_zt+1 | |greateiMle和路径距离|Ixy-Xt+ul|MUte 的大小，根据大小值的不同相应的给路径距离|Ixu-xt+ul匕_加上或减去一个As，让其 远离大圆距离I|zt-Zt+1||[email protected]。16,从而对匹配实现优化。
[0034] 4、输出最佳匹配路径
[0035] 通过用公式（1)中的匹配概率和公式（2)中的转换概率，使用维特比算法 (Viterbi)在HMM点阵中来计算出最佳匹配路径。维特比算法使用动态编程来快速找到匹 配概率和转移概率乘积最大的路径，从而推断出坐标点的正确匹配道路段。
[0036] 如果对于从t时刻的点zt匹配到道路ri上的点xt;i到达t+1时刻的点zt+1匹配到 r」道路上的点xt+1，j发生道路转换时，这时就要考虑点zt是通过哪条道路段rx到达点zt+1， 此时就不能只单独考虑道路匹配概率P(zt\ri)和p(zt+1\rj)，而且要考虑两点之间发生的道 路转换概率，即匹配概率乘以相应的道路转换概率，从中选出最大值即为此时点的最佳匹 配道路段，并记下该点在此道路段上的最佳匹配值是由哪条道路段转换而来，以此类推。 [0037] 算法对定位点的处理区分为对第一个定位点的处理和对普通定位点的处理。为保 证实时性，算法一般对所有测量点进行分组处理，最后将各组点的结果综合输出得到最终 的最佳匹配路径。所以算法对第一个点的处理区分对车辆定位点的第一个点和对分组第 一个点的处理。
[0038] 具体来说对于一个点zt，它匹配到每条候选道路段上的状态概率为p(zt|ri)。如 果该点是车辆定位点的第一个点，则不需要对此概率进行修正，如果该点不是该车辆定位 点的第一个点，仅为分组后该组点的第一个点，则要对状态概率P(zt|ri)进行修正。需要 将状态概率乘以上时刻点的匹配道路段到本时刻点的匹配路段的转移概率，即P(zt|ri)= pbjri)XpWh)〇
[0039] 对于其余点的处理，只需考虑每个点zt匹配到每条可行弧ri的状态概率。利用 动态规划思想，设P(zt |ri)表示第t个点zt匹配到弧ri的最大概率，设从弧r移到弧 r」的转移概率为p(ri|rp，第t+1个点定位到弧&的状态概率为p(zt+11rp，则其转移方程 为p(zt+1\；Tj) =max(p(zt+1\rj)，p(zt\ri)Xp(zt+1\rj)Xp(；ri\rj))〇 如果p(zt+1|rj)取值为 p(zt\ri)Xp(zt+1\rj)Xp(r^rj)，则需要记录转换路径，在输出结果时可以以此反推最佳匹 配道路段。
[0040] 当计算完全部点的状态概率后，确定最后一个点的最佳匹配道路段，并以此道路 段反向推出从第一个点到最后一个点的车辆实际行驶轨迹的道路段。整个行驶轨迹计算完 毕后，就可以最终输出车辆的最佳匹配路径。
[0041] 应用实例
[0042] 输入：zt，观测序列长度T(测量点个数）
[0043] (1)按照初始状态分布1产生状态z1
[0044] (2)令t= 1
[0045] (3)从状态zt，生成观测概率p(zt\ri)
[0046] (4)从状态zt，生成转移概率p(dt)
[0047] (5)记录qt，! =p(zt，:rDXp(dt)
[0048] (6)令t=t+1,如果t〈T，转步（3);否贝1」，转下步。
[0049] (7)用维特比算法（Viterbi)处理qt，i
[0050] 输出：最佳匹配路径r=(rpr2...，rN)。
【主权项】
1. 一种利用隐马尔可夫地图匹配算法增强手机基站定位精度的方法，其特征在于如下 步骤， (1) 初始匹配概率 点Zt与每一条临近的道路ri存在一个匹配概率P(ZtIri) 表示点Z ,匹配到道 路巧上的点；点21匹配到候选匹配道路Γι，r2, r3上的候选匹配点为Xu，Xl，2, Xl，3;坐标 点和候选匹配点的大圆距离为Il Zt-X^ Il gMat Mrcle;相对于t+1时的点z t+1来说，z t+1匹 配到道路1^_上的点为X t+1，j;点X U和点X t+1，j之间车辆行驶的距离称为"路径距离"，记 Il Xt，i Xt+l，j Il route; 模拟的定位误差为零均值的高斯误差，即：〇 2在式中代表定位测量值的标准偏差； 初始匹配概率π i，i = 1…队，表示在地图匹配开始运行前，从所有路段中找出车辆所 在路段的概率；当部分HMM的构想值均匀分布于31 i上时，假设没有测量值被采用，则在第 一个测量值上开始，有π i = p (z 11 ri)，使用第一测量值Zl; (2) 道路转移概率 转移概率是指在这两个时间（t到t+Ι)内，车辆在候选匹配道路之间的转移概率；对于 测量值Zt和其候选匹配道路段r i来说，在r i上最可能匹配点是X t，i;测量值z t+1在其候选 匹配道路段L上的候选匹配点是X t+1j测量点之间的"路径距离" I I X Μ-χ?+1 J I MUte和大圆 距离I I zt-zt+11 Igreat &。16,正确匹配时这两个值相当接近，通过比较这两个值判断道路是否 发生转换； 通过对正确匹配的大圆距离和路径距离差的绝对值进行分析，得出指数概率分布：其中，iip r指的是车辆的真实行驶道路段； (3) 优化 引入一个参数△ s来对这一行为进行约束；当定位点的候选匹配道路发生改变，候选 匹配点离开原行1驶的道路，其路径距离就远离大圆距离50米进行惩罚，就是当路径距离 大于大圆距离时，路径距离加上50米，路径距离小于大圆距离时，路径距离减去50米；这样 不正确匹配点的路径距离就会远离大圆距离，更容易找出正确匹配点； (4) 输出最佳匹配路径 通过用公式（1)中的匹配概率和公式（2)中的转换概率，使用维特比算法在HMM点阵 中来计算出最佳匹配路径；维特比算法使用动态编程来快速找到匹配概率和转移概率乘积 最大的路径，从而推断出坐标点的正确匹配道路段； 如果对于从t时刻的点Zt匹配到道路r i上的点X t;i到达t+Ι时刻的点Z t+1匹配到r J 道路上的点xt+1，」发生道路转换时，要考虑点z t是通过哪条道路段r x到达点z t+1，不能只单 独考虑道路匹配概率P (zt\ri)和p (zt+1\rj)，要考虑两点之间发生的道路转换概率，即匹配 概率乘以相应的道路转换概率，从中选出最大值即为此时点的最佳匹配道路段，并记下该 点在此道路段上的最佳匹配值是由哪条道路段转换而来，以此类推； 算法对定位点的处理区分为对第一个定位点的处理和对普通定位点的处理；具体如 下： 对于一个点zt，它匹配到每条候选道路段上的状态概率为P(ZtIri);如果该点是 车辆定位点的第一个点，则不需要对此概率进行修正，如果该点不是该车辆定位点的第 一个点，仅为分组后该组点的第一个点，则要对状态概率P(ZtIri)进行修正；需要将状 态概率乘以上时刻点的匹配道路段到本时刻点的匹配路段的转移概率，即P(ZtIri)= P(ZtIri) Xpd1); 对于其余点的处理，只需考虑每个点Zt匹配到每条可行弧r i的状态概率；设p (z 11 ri) 表示第t个点zt匹配到弧r ,的最大概率，设从弧r ,转移到弧q的转移概率为p (r , I rj)， 第t+1个点定位到弧rj的状态概率为p (z t+11 rp，则其转移方程为p (zt+1\rj) = max (p (zt+1\ Tjhp(ZtVri) Xp (ZwVrj) XpCriVrj));如果 P(ZtJrj)取值为 P(ZtVri) Xp (zt+1 Vrj) XpCri' rp，则需要记录转换路径，在输出结果时以此反推最佳匹配道路段； 当计算完全部点的状态概率后，确定最后一个点的最佳匹配道路段，并以此道路段反 向推出从第一个点到最后一个点的车辆实际行驶轨迹的道路段；整个行驶轨迹计算完毕 后，最终输出车辆的最佳匹配路径。
【专利摘要】本发明属于手机基站定位领域，涉及一种利用隐马尔可夫地图匹配算法增强手机基站定位精度的方法。利用隐马尔可夫地图匹配算法来提高手机基站定位的精度，算法将定位点匹配到候选匹配道路上的概率称作初始匹配概率，将候选匹配道路发生转换的概率称作道路转移概率，算法使用动态编程来快速找到初始匹配概率和道路转移概率乘积最大的路径。考虑到车辆在实际行驶过程中不可能频繁地转换道路，我们在算法计算定位点道路转移概率时引入了约束限制进行改进，从而提高了算法性能。
【IPC分类】H04W4/02, H04W64/00, G01C21/30, G08G1/01
【公开号】CN104900059
【申请号】CN201510273848
【发明人】申彦明, 张鹏飞
【申请人】大连理工大学
【公开日】2015年9月9日
【申请日】2015年5月26日
【技术领域】
[0001] 本发明属于地图匹配修正技术领域，涉及一种利用隐马尔可夫地图匹配算法增强 手机基站定位精度的方法。
[0002] 地图匹配是目前广泛应用于导航系统定位的一种修正方法，是一种以计算机软件 技术为基础，通过特定的模型和算法，对导航、定位中的误差进行修正的技术。就是将车辆 获取的带有误差的车辆轨迹信息，运用一定方法和算法匹配到数字交通地图上的正确位 置。通过使用地图匹配算法，可以较好的弥补定位点存在的精度误差，因此地图匹配技术也 是提升导航、定位系统性能的一项重要技术。这种匹配技术前提是假定车辆必须行驶在路 上，使用模式识别理论综合分析定位点形成的轨迹和电子地图中的道路网信息，将测得的 车辆位置信息和数字交通地图中的相关数据进行对比，并使用算法对定位点进行匹配，最 终得出车辆所在路段，并相应找出车辆在该路段上的具体位置，然后将车辆定位点由该道 路段之外的位置投影到该道路段上，从而校正了定位点的误差。
【背景技术】
[0003] 当前常用的地图匹配算法有点到点、点到曲线（最短距离法）、曲线到曲线、基于 模糊逻辑、模式识别、误差代价函数等。在实际运用中，无论采用哪一种大都是通过比较定 位轨迹与侯选道路数据形状的相似性、定位轨迹与候选道路方向的相似性、定位轨迹到侯 选道路距离的远近，以及利用路网的拓扑性质来确定车辆行驶道路。
[0004] 点到点和点到曲线的算法实现比较简单，不需利用路网的连通性和历史轨迹，具 有实时性的优点，但此方法对定位精度要求较高，并且路段间距离较近时无法完成相关匹 配。曲线到曲线的算法则利用了道路网的连通性和历史轨迹，匹配率较高。但这种方法需 要知道车辆行驶起始节点，并且要求定位轨迹与道路具有相当的相似性才能实现算法。误 差代价函数算法综合利用了各种定位信息和路网信息，匹配准确率高，适合于复杂的道路 网络，但比较复杂。
[0005] 通过对手机定位误差的实验分析可知，手机定位点随机分布在路段周围，手机定 位误差较GPS大，且定位采样频率较低，因此定位轨迹的形状同真实行驶路线的相似性不 明显，而现有算法大都是通过比较定位轨迹与侯选道路数据形状、方向的相似性，定位轨迹 到侯选道路距离的远近，以及利用路网的拓扑性质来确定车辆行驶道路。若仅用形状相似 性规则判断行驶路段，极易导致误匹配错误。
[0006] 此外，现有算法大都以定位信息精度和定位采样频率较高的GPS定位数据为基 础，由于手机定位的定位信息精度和采样频率较低，这些算法均不能直接用于以手机基站 定位数据为定位信息的匹配算法。
【发明内容】
[0007] 隐马尔可夫模型能够有效地平滑整合定位误差数据和路径约束。利用隐马尔可夫 地图匹配算法来提高手机基站定位的精度。定位点匹配到候选匹配道路上的概率称作初始 匹配概率，候选匹配道路发生转换的概率称作道路转移概率，使用动态编程来快速找到初 始匹配概率和道路转移概率乘积最大的路径。考虑到车辆在实际行驶过程中不可能频繁地 转换道路，计算定位点道路转移概率时引入了约束限制进行改进，从而提高了性能。
[0008] 本发明用模拟数据检验时表明，即使采样周期长达30秒，误差也仅为0. 11%，在 较长的采样周期中，该方法对测量值噪声误差的鲁棒性高达50米的标准偏差。在隐马尔可 夫地图匹配算法中，路段之间的转换是通过路网的连通来管理。如图1所示，HMM离散状态 是队个道路段，用ri表示，其中i= 1…Ny不同道路段之间的转换发生在道路相接的交叉 路口。zt表示某一时刻测量的坐标值，t= 1时，临近zi的三条道路用三个黑点在第一列中 表示。t= 2时，分别从这3条路上最近的点指向靠近z2的两条道路。t= 3时做同样的工 作。每个t时刻选取的道路段组成一个道路网格，目标是在道路网格中找到最可能的路径。
[0009] 本发明的方法利用隐马尔可夫地图匹配算法来提高手机基站定位的精度，将定位 点匹配到候选匹配道路上的概率称作初始匹配概率，将候选匹配道路发生转换的概率称作 道路转移概率，使用动态编程来快速找到初始匹配概率和道路转移概率乘积最大的路径。 考虑到车辆在实际行驶过程中不可能频繁地转换道路，在计算定位点道路转移概率时引入 了约束限制进行改进，从而提高性能。
【附图说明】
[0010] 图1是Zt候选匹配道路段ri及道路段间转换示意图。
[0011]图2是测量值zt在候选匹配道路段ri上的候选匹配点示意图。
[0012] 图3是本发明的示例图。
[0013] 图4是As修正示例图。
[0014] 具体步骤
[0015] 以下结合技术方案和附图详细叙述本发明的具体实施例。
[0016] 1、初始匹配概率
[0017] 点zt与每一条临近的道路ri存在一个匹配概率p (z 11巧）。xt，i表示点z画配到道 路A上的点。由图2可以发现，点z i匹配到候选匹配道路r pivh上的候选匹配点为x 1;1， Xl，2, Xl，：3。坐标点和候选匹配点的大圆距离为IIZt_Xt，iIIgmt。相对于t+l时的点Zt+1 来说，zt+1匹配到道路r」上的点为X t+1,」。点xt,i和点X t+1,」之间车辆行驶的距离称为"路径 距Nl，记做IIxt,厂Xt+1，jIIroute。
[0018] 对于正确匹配来说，坐标点和匹配点之间的这种误差是由定位误差形成的。算法 模拟的定位误差为零均值的高斯误差，这意味着：
[0020] 〇在式中代表定位测量值的标准偏差。
[0021] 初始匹配概率31i，i= 1…队，其表示在地图匹配开始运行前，从所有路段中找出 车辆所在路段的概率。当部分HMM的构想值均匀分布于31i上时，假设没有测量值被采用， 则算法在第一个测量值上开始，这时有Jri=p(zt |ri)，即使用第一测量值Zl。
[0022] 2、道路转移概率，将候选匹配道路发生转换
[0023] 同每个测量值zt-样，下一个测量zt+1也有一个可能匹配道路的列表。转移概率 是指在这两个时间（t到t+1)内，车辆在候选匹配道路之间的转移概率。对于测量值\和 其候选匹配道路段A来说，在ri上最可能匹配点是xu。同样，测量值zt+1在其候选匹配道 路段r」上的候选匹配点是Xt+u。我们比较测量点之间的"路径距离" | |MUte和 大圆距离I|zt-zt+1| |gMatc;iMle，正确匹配时这两个值相当接近，通过比较这两个值就可以判 断道路是否发生转换。
[0024] 举例说明，在图3中有三个道路段ivrjPr3，两个测量点\和zt+1。测量点\有 Xt，l和Xt，：3两个候选匹配点，测量点Zt+1的候选匹配点为Xt+1』。IIZt_Zt+lIIgmtotei#两个测 量点的大圆距离，路径距离有两个，分别为llx^-Xt+ull^tdP|^^-\+1，2||"_。与不正 确匹配相比，正确匹配时的路径距离更接近大圆距离。
[0025] 该算法通过对正确匹配的大圆距离和路径距离差的绝对值进行分析，得出指数概 率分布：
[0030]其中，r和r指的是车辆的真实行驶道路段。
[0031] 3、优化
[0032] 考虑到正常行驶时，驾驶人员在到达目的地之前会尽量沿同一条道路上行驶，不 会轻意改变行驶道路，更不会频繁地转换道路。因此频繁转换的候选匹配道路可能是由于 定位误差产生的错误匹配。为此，我们引入一个参数As来对这一行为进行约束。当定位 点的候选匹配道路发生改变，候选匹配点离开原行1驶的道路，其路径距离就远离大圆距 离50米进行惩罚，就是当路径距离大于大圆距离时，路径距离加上50米，路径距离小于大 圆距离时，路径距离减去50米。不正确匹配点的路径距离就会远离大圆距离，算法更能找 出正确匹配点。
[0033] 在图4中有三个道路段段rp1~2和r3，两个测量点zt和zt+1。第一个测量点zt候 选匹配道路有A上的候选匹配点为Xm，第二个测量点zt+1在候选匹配道路ri，r2,r3上的 匹配候选点分别为11+1，14 +1，24+1，3。|^^+1||~。^ ;16为两个测量点21和21+1之间的大 圆距离，路径距离有三个，分别为II Xy-Xt+u||Mute，||Xw-Xt+u||Mute和 |Ixw-Xt+i，」|MUte〇 从图中可以看出IIxy-Xt+ul|MUte和IIxy-Xt+ul|MUte距离非常接近，如果不引入As进行 约束，就有可能发生错误匹配。由于从候选匹配点到候选匹配点Xt+u的路径距离在道 路巧上，期间没有发生道路转换，而候选匹配点Xt，i到候选匹配点xt+1，2的路径距离包括在 道路r^r2上的两段距离，期间发生了道路转换，因此我们给路径距离IIxu-Xt+ul|MUJj口 上一个As进行约束，首先比较大圆距离| |zt_zt+1 | |greateiMle和路径距离|Ixy-Xt+ul|MUte 的大小，根据大小值的不同相应的给路径距离|Ixu-xt+ul匕_加上或减去一个As，让其 远离大圆距离I|zt-Zt+1||[email protected]。16,从而对匹配实现优化。
[0034] 4、输出最佳匹配路径
[0035] 通过用公式（1)中的匹配概率和公式（2)中的转换概率，使用维特比算法 (Viterbi)在HMM点阵中来计算出最佳匹配路径。维特比算法使用动态编程来快速找到匹 配概率和转移概率乘积最大的路径，从而推断出坐标点的正确匹配道路段。
[0036] 如果对于从t时刻的点zt匹配到道路ri上的点xt;i到达t+1时刻的点zt+1匹配到 r」道路上的点xt+1，j发生道路转换时，这时就要考虑点zt是通过哪条道路段rx到达点zt+1， 此时就不能只单独考虑道路匹配概率P(zt\ri)和p(zt+1\rj)，而且要考虑两点之间发生的道 路转换概率，即匹配概率乘以相应的道路转换概率，从中选出最大值即为此时点的最佳匹 配道路段，并记下该点在此道路段上的最佳匹配值是由哪条道路段转换而来，以此类推。 [0037] 算法对定位点的处理区分为对第一个定位点的处理和对普通定位点的处理。为保 证实时性，算法一般对所有测量点进行分组处理，最后将各组点的结果综合输出得到最终 的最佳匹配路径。所以算法对第一个点的处理区分对车辆定位点的第一个点和对分组第 一个点的处理。
[0038] 具体来说对于一个点zt，它匹配到每条候选道路段上的状态概率为p(zt|ri)。如 果该点是车辆定位点的第一个点，则不需要对此概率进行修正，如果该点不是该车辆定位 点的第一个点，仅为分组后该组点的第一个点，则要对状态概率P(zt|ri)进行修正。需要 将状态概率乘以上时刻点的匹配道路段到本时刻点的匹配路段的转移概率，即P(zt|ri)= pbjri)XpWh)〇
[0039] 对于其余点的处理，只需考虑每个点zt匹配到每条可行弧ri的状态概率。利用 动态规划思想，设P(zt |ri)表示第t个点zt匹配到弧ri的最大概率，设从弧r移到弧 r」的转移概率为p(ri|rp，第t+1个点定位到弧&的状态概率为p(zt+11rp，则其转移方程 为p(zt+1\；Tj) =max(p(zt+1\rj)，p(zt\ri)Xp(zt+1\rj)Xp(；ri\rj))〇 如果p(zt+1|rj)取值为 p(zt\ri)Xp(zt+1\rj)Xp(r^rj)，则需要记录转换路径，在输出结果时可以以此反推最佳匹 配道路段。
[0040] 当计算完全部点的状态概率后，确定最后一个点的最佳匹配道路段，并以此道路 段反向推出从第一个点到最后一个点的车辆实际行驶轨迹的道路段。整个行驶轨迹计算完 毕后，就可以最终输出车辆的最佳匹配路径。
[0041] 应用实例
[0042] 输入：zt，观测序列长度T(测量点个数）
[0043] (1)按照初始状态分布1产生状态z1
[0044] (2)令t= 1
[0045] (3)从状态zt，生成观测概率p(zt\ri)
[0046] (4)从状态zt，生成转移概率p(dt)
[0047] (5)记录qt，! =p(zt，:rDXp(dt)
[0048] (6)令t=t+1,如果t〈T，转步（3);否贝1」，转下步。
[0049] (7)用维特比算法（Viterbi)处理qt，i
[0050] 输出：最佳匹配路径r=(rpr2...，rN)。
【主权项】
1. 一种利用隐马尔可夫地图匹配算法增强手机基站定位精度的方法，其特征在于如下 步骤， (1) 初始匹配概率 点Zt与每一条临近的道路ri存在一个匹配概率P(ZtIri) 表示点Z ,匹配到道 路巧上的点；点21匹配到候选匹配道路Γι，r2, r3上的候选匹配点为Xu，Xl，2, Xl，3;坐标 点和候选匹配点的大圆距离为Il Zt-X^ Il gMat Mrcle;相对于t+1时的点z t+1来说，z t+1匹 配到道路1^_上的点为X t+1，j;点X U和点X t+1，j之间车辆行驶的距离称为"路径距离"，记 Il Xt，i Xt+l，j Il route; 模拟的定位误差为零均值的高斯误差，即：〇 2在式中代表定位测量值的标准偏差； 初始匹配概率π i，i = 1…队，表示在地图匹配开始运行前，从所有路段中找出车辆所 在路段的概率；当部分HMM的构想值均匀分布于31 i上时，假设没有测量值被采用，则在第 一个测量值上开始，有π i = p (z 11 ri)，使用第一测量值Zl; (2) 道路转移概率 转移概率是指在这两个时间（t到t+Ι)内，车辆在候选匹配道路之间的转移概率；对于 测量值Zt和其候选匹配道路段r i来说，在r i上最可能匹配点是X t，i;测量值z t+1在其候选 匹配道路段L上的候选匹配点是X t+1j测量点之间的"路径距离" I I X Μ-χ?+1 J I MUte和大圆 距离I I zt-zt+11 Igreat &。16,正确匹配时这两个值相当接近，通过比较这两个值判断道路是否 发生转换； 通过对正确匹配的大圆距离和路径距离差的绝对值进行分析，得出指数概率分布：其中，iip r指的是车辆的真实行驶道路段； (3) 优化 引入一个参数△ s来对这一行为进行约束；当定位点的候选匹配道路发生改变，候选 匹配点离开原行1驶的道路，其路径距离就远离大圆距离50米进行惩罚，就是当路径距离 大于大圆距离时，路径距离加上50米，路径距离小于大圆距离时，路径距离减去50米；这样 不正确匹配点的路径距离就会远离大圆距离，更容易找出正确匹配点； (4) 输出最佳匹配路径 通过用公式（1)中的匹配概率和公式（2)中的转换概率，使用维特比算法在HMM点阵 中来计算出最佳匹配路径；维特比算法使用动态编程来快速找到匹配概率和转移概率乘积 最大的路径，从而推断出坐标点的正确匹配道路段； 如果对于从t时刻的点Zt匹配到道路r i上的点X t;i到达t+Ι时刻的点Z t+1匹配到r J 道路上的点xt+1，」发生道路转换时，要考虑点z t是通过哪条道路段r x到达点z t+1，不能只单 独考虑道路匹配概率P (zt\ri)和p (zt+1\rj)，要考虑两点之间发生的道路转换概率，即匹配 概率乘以相应的道路转换概率，从中选出最大值即为此时点的最佳匹配道路段，并记下该 点在此道路段上的最佳匹配值是由哪条道路段转换而来，以此类推； 算法对定位点的处理区分为对第一个定位点的处理和对普通定位点的处理；具体如 下： 对于一个点zt，它匹配到每条候选道路段上的状态概率为P(ZtIri);如果该点是 车辆定位点的第一个点，则不需要对此概率进行修正，如果该点不是该车辆定位点的第 一个点，仅为分组后该组点的第一个点，则要对状态概率P(ZtIri)进行修正；需要将状 态概率乘以上时刻点的匹配道路段到本时刻点的匹配路段的转移概率，即P(ZtIri)= P(ZtIri) Xpd1); 对于其余点的处理，只需考虑每个点Zt匹配到每条可行弧r i的状态概率；设p (z 11 ri) 表示第t个点zt匹配到弧r ,的最大概率，设从弧r ,转移到弧q的转移概率为p (r , I rj)， 第t+1个点定位到弧rj的状态概率为p (z t+11 rp，则其转移方程为p (zt+1\rj) = max (p (zt+1\ Tjhp(ZtVri) Xp (ZwVrj) XpCriVrj));如果 P(ZtJrj)取值为 P(ZtVri) Xp (zt+1 Vrj) XpCri' rp，则需要记录转换路径，在输出结果时以此反推最佳匹配道路段； 当计算完全部点的状态概率后，确定最后一个点的最佳匹配道路段，并以此道路段反 向推出从第一个点到最后一个点的车辆实际行驶轨迹的道路段；整个行驶轨迹计算完毕 后，最终输出车辆的最佳匹配路径。
【专利摘要】本发明属于手机基站定位领域，涉及一种利用隐马尔可夫地图匹配算法增强手机基站定位精度的方法。利用隐马尔可夫地图匹配算法来提高手机基站定位的精度，算法将定位点匹配到候选匹配道路上的概率称作初始匹配概率，将候选匹配道路发生转换的概率称作道路转移概率，算法使用动态编程来快速找到初始匹配概率和道路转移概率乘积最大的路径。考虑到车辆在实际行驶过程中不可能频繁地转换道路，我们在算法计算定位点道路转移概率时引入了约束限制进行改进，从而提高了算法性能。
【IPC分类】H04W4/02, H04W64/00, G01C21/30, G08G1/01
【公开号】CN104900059
【申请号】CN201510273848
【发明人】申彦明, 张鹏飞
【申请人】大连理工大学
【公开日】2015年9月9日
【申请日】2015年5月26日
最新回复(0)