【《基于隐马尔可夫模型的在线地图匹配方法分析》6800字】

基于隐马尔可夫模型的在线地图匹配方法分析目录TOC\o"1-3"\h\u18894基于隐马尔可夫模型的在线地图匹配方法分析 (2-34)即可求得最优路径I∗=i1∗,1.3基于隐马尔科夫模型的地图匹配实现1.3.1离线地图匹配基本原理基于隐式马尔可夫模型（HiddenMarkovModel,HMM）的地图匹配定位，属于隐式马尔可夫模型中的解码问题。解码问题求解的是由一组隐藏状态序列生成一组特定的观测变量序列的联合概率。这个问题要求在所有可能的隐藏状态序列中确定一个最大值，该问题通常使用Viterbi算法进行求解。在室外环境中，针对车辆的GPS、GSM或Wi-Fi等定位结果存在往复跳变、精度低等问题，地图匹配算法将车辆的轨迹与路网进行匹配，提高定位的精度。在室内环境中，隐藏状态可以是室内路网的节点或者边。观测变量是由其他定位算法（行人航位推算或无线信号指纹定位等）得到的估计位置序列，或者是智能手机内置传感器的测量数据序列。当得到一个估计位置时，隐藏状态之间将发生一次转移。为了计算状态转移概率矩阵，需要使用室内路网信息。因为行人只能由一个节点移动到相邻的节点，所以从一个节点到所有与之相邻的节点的状态转移概率的和为1。针对于指纹图模型，从上一时刻的状态到当前时刻的状态转移概率为：Pn（1.SEQ公式\*ARABIC41）其中，ni和nj分别表示当前时刻状态和前一时刻的状态，N表示指纹图模型中节点的数量，ω（1.SEQ公式\*ARABIC42）其中，当指纹图模型G包含边edgei,j，即节点ni和nj之间存在连通关系，ω发散概率为当行人处于某一个隐藏状态时，得到估计位置的概率。显然，由其它定位算法得到的估计位置与隐藏状态位置之间的距离和发散概率之间呈反比关系。发散概率按照如下计算：P（1.SEQ公式\*ARABIC43）其中，ni为当前的隐藏状态，Lt为当给定观测变量序列后，通过使用Viterbi算法计算最可能的隐藏状态序列，如图1.4所示。Viterbi算法是一种动态规划算法，用于寻找最可能的隐藏状态序列，该序列被称为Viterbi路径。在隐式马尔可夫模型中，Viterbi路径是观测序列的形成的原因。Viterbi算法在无线信号解码、语音识别、语音合成等领域有广泛的应用。在地图匹配方法中，通过Viterbi算法求解的隐藏状态序列即为违反室内空间信息约束最少的行人轨迹。图1.4隐式马尔可夫模型与Viterbi算法传统的隐马尔可夫模型使用标准Viterbi算法进行解码来得到解码结果。使用标准Viterbi算法的一个主要前提是需要知道整个观测序列，所以使用标准Viterbi算法对隐式马尔可夫模型进行解码不能符合在线地图匹配对实时性的要求。1.3.2在线地图匹配基本原理常用的在线解码算法有前向解码（Forwardonly）和滑动窗口解码（Slidingwindow）算法。前向解码算法非常直观如图1.5所示，每一个状态在时刻t的概率的计算方法和标准Viterbi算法一致，但是在这个时刻t，将会选取概率最大的状态作为解码结果。因此，整个序列最终的解码状态路径就是由每个时刻t的解码结果（状态）组成。前向解码与标准Viterbi算法相比，无需先后过程，解码发生在每个时刻，所以是介绍的几个算法中时间、空间消耗最少的算法，而且能做到实时输出。但是在它的解码状态路径中，可能会存在有时间相邻的两个状态之间无法相互转移，这是因为每一步的解码结果都忽略了上一步的解码结果。图1.5前向解码过程滑动窗口解码的实现如图1.6所示。该方法有一个固定长度的窗口，即固定数量n的观测量。并在该窗口内使用标准的Viterbi算法进行解码，最后将该窗口内第一个状态的解码结果作为t-n时刻的解码结果（当前时刻t），作为随后t+1时刻新的观测量加入窗口，并重复此过程获得该窗口内第一个状态的解码，即t+1-n时刻的解码结果。这个过程将比前向解码方法实现更精确，但是引入了一个小的延迟，因为当前解码结果只有在n个新观测量加入窗口后才能获得。另一个显而易见的问题是如何确定该窗口的最佳长度。当窗口较小时，将影响解码精度，但是时间延长少。当窗口较大时，该方法有更好的精度，同时时间延长较大。图1.6滑动窗口解码过程1.3.3在线地图匹配实现框架在线地图匹配实现框架如图1.7所示。首先，将从平面地图中按照一定间隔采样出参考点（ReferencePoint）这些参考点是Wi-Fi指纹库的参考点，也是隐式马尔可夫模型的隐藏状态。再根据空间约束将相邻的参考点进行连线，根据这些参考点和边，可以使用Dijkstra计算出任意两个参考点之间的最短参考点路径和其距离。然后，将参考点间的最短路径距离转换为对应的转移概率，构成转移概率矩阵。利用需要地图匹配的定位结果发散概率矩阵将与转移概率矩阵相结合，利用HMM在线解码算法对匹配轨迹进行推理。图1.7在线地图匹配实现框架1.4实验与分析1.4.1实验设置武汉遥感与空间信息工业技术研究院作为测试场景，对上述介绍的两种在线地图匹配方法进行分析验证。该研究院是国家重点研发计划《高可用高精度室内智能混合定位与室内GIS技术》的试验场，占地面积约为1462（86×17）平方米，上下五层包含电梯、楼梯、走廊、房间等常见室内结构，此外还包含了大量开阔空间以及连通两层的中庭和门厅，这增加了室内空间的复杂性。布设多种可以用作室内定位的定位源包括wifi、蓝牙、地磁、声源、光源、视觉等定位源，其平面地图的分布情况（以3楼为例）如图1.8所示。图1.8实验场3楼定位源示意图初始定位结果是将上述定位源进行紧耦合得到的，在本文中将初始定位结果为融合定位结果，本文提出的方法均在融合定位结果的基础上进行改进，改进后的地图匹配结果被称为增强定位结果。图1.9基于android平台定位结果可视化app为了直观地展示结果，使用基于android平台的可视化app，如图1.9所示。该app可以预先选择用于定位的定位源，然后显示界面实时显示，同时在手机根目录下记录每次测试的融合定位结果和增强定位结果数据用来分析精度。基于HMM的地图匹配需要用地图建立路网，图1.10展示了预先设定的参考点，在此实验环境中，选择将格网尺寸设置为1米，最终在3楼得到1372个参考点。再根据空间约束将相邻的参考点进行连线得到路网如图1.11所示。图1.10试验场3楼参考点图1.11试验场3楼路网1.4.2实验结果与分析图1.12和图1.13分别给出了前向解码算法和滑动窗口解码算法的地图匹配结果。其中，图中的绿色点表示使用高精度惯导设备测得的定位结果（误差在10cm内），将此轨迹作为真实轨迹，用于衡量两种在线算法的匹配精度的基准，红点表示通过多种定位源得到的融合定位结果。图1.12和图1.13中，使用黑色虚线标注出两处明显的偏离真实轨迹的融合结果，行人真实行走路径在走廊上，然而融合结果的黑色虚线处从走廊偏移到房间。这是由于融合结果只根据定位源来进行定位，没有考虑到室内空间的拓扑信息。图1.12和图1.13中蓝点分别表示通过前向解码算法和滑动窗口解码算法得到的地图匹配增强定位结果。前向解码算法和滑动窗口解码算法可以达到地图匹配的效果，与真实轨迹的匹配度较高。在黑色虚线标注处，两种方法都可以纠正部分融合结果的穿墙错误。说明基于HMM的在线地图匹配算法对融合结果有纠正作用，可以增强定位效果。图1.12前向解码算法3楼测试结果图1.13滑动窗口解码算法3楼测试结果进一步地，表1.1比较了前向解码和滑动窗口解码两种算法精度和延迟之间的关系。前向解码算法的精度为3.055米，滑动窗口解码算法的解码精度低于前向解码算法，解码精度为1.954米。前向解码算法空间消耗最少没有延迟，而滑动窗口解码算法的延迟为1秒（窗口长度被设置为5）。滑动窗口解码算法的精度和时间延迟与窗口大小直接相关，当窗口被设置为较小值时，匹配精度越差，而延迟时间较短，窗口越大时，该方法的匹配精度越好，然而时间延迟也越大。表1.1前向解码和滑窗解码精度算法精度（米）延迟（秒）Forwardonl