首页 >
论文范文 >
自然科学论文 >
数学论文 >
数理统计论文 >
基于隐马尔可夫模型地图匹配算法进行动态距离权重因子分析
摘要：针对低频采样时地图匹配算法易出错、稳定性差等问题,提出了一种基于动态距离权重因子的隐马尔可夫模型地图匹配算法。引入动态距离权重因子优化路段检索区域,计算定位点与候选道路间的匹配度M,其数值较大的候选路段所对应的为最终确定的候选路段。研究结果表明:本文提出的匹配算法的单点匹配时间约为5.20ms,匹配准确率可以达到90%以上,优于其他3种对比算法。
加入收藏
定位数据和电子地图均存在难以避免的误差[1],导致车辆的定位结果显示错误。地图匹配算法可以解决误差干扰的问题,将定位点匹配到正确的路段上。现有的地图匹配算法可分为4种类型:基于几何信息的算法,基于拓扑关系的算法,基于概率统计的算法以及复合匹配算法。基于几何信息的算法未考虑道路拓扑结构,易造成错误匹配[2,3,4,5]。基于拓扑关系的算法易受噪声、数据稀疏性等因素的影响,难以解决复杂路网匹配的问题[6,7]。基于概率统计的算法涉及复杂的公式证明与推导,算法稳定性不佳[8,9]。卡尔曼滤波、D-S证据理论等复合匹配算法虽然准确率很高,但低频采样时错误率较高[10,11,12,13,14,15]。基于隐马尔可夫模型的地图匹配算法,可以很好地解决低频采样错误率较高的问题,但是随着城市道路拓扑结构越来越复杂,导致该算法准确率不稳定,单点匹配耗时长[16,17]。
综上所述,单一算法很难较好地权衡准确率和时效性,因此,本文结合了几何匹配算法和基于隐马尔可夫匹配算法两种思想,重新定义匹配程度的概念。对传统点到线的匹配算法进行改进,提出了一种融入动态距离权重因子的隐马尔可夫模型地图匹配算法。借助仿真实验,验证了本文HMM地图匹配算法的单点匹配时间更少且准确率更高。
1、确定路段检索区域
经典算法选择以车辆定位位置为区域中心的方形或圆形区域作为路段检索区域。为了提高算法的运行效率,本文通过两次筛选确定路段检索区域,第1次筛选利用网格索引对电子地图进行划分,合理选择以车辆当前定位位置为中心的九宫格区域,尽可能减少候选道路数量;第2次筛选以行车方向为长轴作椭圆形,剔除没有经过椭圆形区域的候选路段,进一步减少计算量,确定最终的路段检索区域。
建立网格索引,以l(依据工程经验一般选取200m)为边长划分网格,以G(gx,gy)为分块网格索引号。若定位点为P(i,j),则定位点的网格索引号为:
图1路段检索区域示意图
图1为路段检索区域示意图。如图1所示,以定位点P(i,j)为中心的3×3的网格区域为经过第1次筛选后的路段检索区域,此时候选路段为A、C;接着以行车方向为长轴作椭圆形,则可以排除路段C,区域内的路段A为经过第2次筛选后的候选路段,确定路段A作为车辆定位点P的最佳匹配路段。
图1中,a为路段检索区域长轴的1/2,b为短轴的1/2,Ψ为a与正北方向之间的角度,且Ψ≤π。a、b和Ψ由以下公式确定[18]:
其中:σi和σj为正北方向与正东方向测量误差的均方差;σij为协方差;σ20为单位权值的后验方差,可以通过改变σ0的大小来改变椭圆形路段检索区域的大小,从而产生不同的路段检索区域。
2、匹配程度
点到线的匹配算法把全部路段都视为候选路段,计算定位点到所有路段之间的垂直距离,由最小距离确定最佳匹配路段。如果点到几条路段的距离都相等,那么会造成无法执行匹配的情况,从而发生错误。与点到点的匹配算法相比较,点到线的匹配算法的准确率有所提升,但是未考虑道路拓扑结构和车辆行驶轨迹曲线等因素,因此稳定性相对较差,容易产生错误匹配。
本文在传统算法的基础上,引入车辆行驶速度和历史匹配程度两个因素,采用多个因素重新定义匹配程度的概念,并将距离权重因子改为动态,应用到基于HMM的地图匹配算法中,可在一定程度上改善本文算法的时效性和准确率。定位点与候选匹配路段的匹配程度为:
其中:α为距离权重因子;D为待匹配点与候选路段间距离的特征值参数;dlp为定位点P到候选路段l的投影距离;β为角度权重因子;θ为车辆此时行进方向与候选路段之间夹角的特征值参数;ω为车辆行驶方向与路段方向的夹角;γ为速度权重因子;v为车辆此时速度的特征值参数;τ和lτ分别为行驶时间和距离;λ为历史匹配程度权重因子;M′为历史匹配程度;Mik为第k个定位点到第i条候选路段的匹配程度;j为当前定位点数。
3、基于HMM的改进算法
本文提出的改进算法主要包括两部分:数据预处理以及改进地图匹配算法。匹配算法流程图如图2所示。数据预处理是除去全部无效的、异常的以及冗余的定位数据;改进地图匹配算法包含标准差σ的估计、4个特征值参数的权重因子计算等。
图2匹配算法流程图
3.1数据预处理
定位数据会受到多种因素的影响,比如对流层、电离层传播延时,从而产生不可避免的定位误差,使定位点远离候选路段,产生大幅度漂移,这些有误差的定位数据会给地图匹配算法的准确率和时效性带来严重的影响,可能会增加计算量和工作难度。所以,在执行地图匹配算法之前要先将获取的定位数据进行分类、汇总,然后除去全部无效的、异常的以及冗余的定位数据。具体筛选规则如下:
(Ⅰ)如果定位数据远离候选路段,根据定位点构建的路段检索区域内没有候选路段,则这些定位数据为漂移点,视为无效的数据并删除。
(Ⅱ)如果定位数据记录中,在连续时间段内车辆的经纬度坐标出现多次重复,则判定该条数据记录为异常数据并剔除。
(Ⅲ)如果定位数据记录中,同一车辆出现采集时间多次重复的若干条记录,则判定此数据记录为冗余数据,经过处理后只需保留一条格式正确的、不再重复的数据记录,将冗余数据全部删除。
3.2改进地图匹配算法
为了权衡地图匹配算法的准确率和时效性,本文首先使用多模态鲁棒回归估计,对观测概率矩阵B中的标准差σ进行估计,选取概率最大的两条候选路段;然后引入动态的距离权重因子α,通过多个因素构建的函数分别计算两条候选路段的匹配程度M,其数值较大的候选路段所对应的为最终确定的候选路段。
文献[19]结合时空特性,包括几何、拓扑以及速度等约束条件,采用均值μ=0、标准差σ=20m的高斯分布表示在隐含状态下得到的观测概率矩阵B:
可以用一个定位点和候选路段之间距离的高斯分布来表示定位点的误差。文献[20]仍然使用均值μ=0的高斯分布,而标准差σ是采用绝对中位差来进行鲁棒估计,得到了噪声的合理值,σ的计算公式为:
σ=1.4826mediant(|ot−rj|great_circle),(7)
其中:|ot−rj|为观测点和待匹配点之间的大圆距离;σ值越大,噪声越大,代表位置测量越不可信。因此,本文采用多模态鲁棒回归估计,对参数σ执行运算时,式(7)可更改为:
其中:ρM为损失权函数,选用胡贝尔权函数;σ∧e为残差散布度量。由于篇幅限制,不能给出该方法的具体实现步骤,其具体细节见文献[21]。通过多模态鲁棒回归估计可得到更小的σ值,大约为3.87m,这也是噪声的合理值。
本文采用多个因素构造的函数确定匹配程度,并引入动态的距离权重因子,使匹配准确率在一定程度上更优。在路段检索区域内,对于定位点P及其候选路段,若路段检索区域内只有一条候选路段,则该路段为最佳匹配路段;若候选路段不只一条,此时需要对候选路段进行筛选,对候选路段的观测概率进行排序,通过上述方法得到观测概率排名前两位的候选路段la和lb,计算两条候选路段的匹配程度M,其数值较大的候选路段所对应的为最终确定的候选路段。
一些匹配算法的权重因子大多是由主观经验确定的,使得匹配算法的结果差异很大,准确率不稳定[22,23,24],针对这个问题,引入动态距离权重因子,使其不再由主观经验确定,可在一定程度上提高本文算法的稳定性。文中提出的匹配程度由4种参数确定,历史匹配程度M′与之前匹配的轨迹数据有关联,可以将其权重因子λ设置为:
(Ⅰ)确定α值
引入动态的距离权重因子,通过对20000个定位点的分析得出,距离D小于Dmax=50m的定位点所占比例接近99%,距离D小于Dmin=0.5m的定位点所占比例不足1%。综上所述,定义动态的距离因子α为:
(Ⅱ)确定β值
根据上文分析,路段检索区域内有两条候选路段,得到观测概率排名前两位的候选路段la和lb,定义ρ1和ρ2为两条候选路段的观测概率,相应的评价Rz和β分别为:
(Ⅲ)确定γ值
车辆当前的行驶速度与道路网的信息、驾驶人员的行为都有着密不可分的关系,在500s的时间内对车辆的速度误差进行仿真实验分析,结果如图3所示。
图3车辆的速度误差
图3a为东向速度误差,经过多次仿真发现速度误差最大值在0.5m/s以内,并通过计算500s内的速度误差得出标准差约为0.27m/s。图3b为北向速度误差,其最大值约为0.8m/s,取平均值经计算得出标准差约为0.35m/s。图3c为天向速度误差,其速度误差最大值约为0.5m/s,取平均值经计算得出标准差约为0.18m/s。由以上数据可以看出:3个方向速度误差的标准差最大值为0.35m/s,该值在可接受的误差范围之内,低频采样条件下,完全可以适应各种道路拓扑结构。因此,根据速度误差的仿真结果,当车辆在一定区间内行驶的平均速度小于路网的限制速度时,将其权重因子γ置为1;否则,认为车辆不具备在该路段上行驶的条件,将其权重因子γ置为0。
4、仿真实验
首先通过仿真实验验证本文算法的运行效率,分别从4种不同的路段中随机选取240个定位点,对其单点匹配时间进行统计分析。图4为本文算法与其他3种对比算法的单点匹配时间的仿真结果比较。从图4中可以看出:本文算法的单点匹配时间在5ms上下浮动,约为5.20ms;点到线匹配算法的单点匹配时间大部分集中在20～25ms,约为22.73ms;固定权重匹配算法的单点匹配时间和传统HMM算法的单点匹配时间大致相同,约为13.81ms。本文提出的改进算法的单点匹配时间相对较少,在时效性上更加具有优势。
在单一路段、平行路段、交叉路段以及复杂路段4种路段拓扑结构下,对本文算法与其他3种地图匹配算法的准确率进行比较,结果如图5所示。
图4单点匹配时间仿真结果比较
图5匹配准确率比较
由图5可知:当车辆在简单路段行驶时,4种匹配算法的准确率都比较高,本文改进算法的匹配准确率和其他3种算法的准确率相近。当车辆驶入平行、交叉甚至更为复杂的路段时,本文改进算法的匹配准确率依然能达到90%以上。随着路况复杂程度的增加,本文算法的准确性明显优于其他3种对比算法的准确性。
当车辆驶入复杂路段时,对4种地图匹配算法位置误差的标准差进行统计,结果见表1。从表1中可以看出:本文算法东向位置误差的标准差为4.30m,北向为4.36m,天向为4.26m,本文算法3个方向的误差比其他3种对比算法的误差都要小,并且位置误差波动的幅度均在可以接受的范围之内。
表1不同地图匹配算法位置误差的标准差对比导出到EXCEL
5、结束语
本文以基于HMM的匹配算法为基础,采用多个因素定义匹配度,引入动态的距离权重因子,结合几何匹配算法和基于HMM匹配算法的思想,提出一种改进的地图匹配算法,以降低定位点的单点匹配时间,提高算法整体的运行效率,使算法在时效性上更加具有优势。通过仿真验证,改进后的匹配算法准确率有所提高,即使在低频采样条件下,复杂路况的准确率依然可以达到90%以上,与3种传统的匹配算法进行比较,本文算法在时效性和准确性上均有所改善。下一阶段将重点研究高频采样时的算法优化,在保证时效性的前提下获得更高的准确率。
参考文献:
[1]许建新,熊智,刘建业,等.基于车辆运动模型辅助的智能手机平台车载组合导航算法[J].中国惯性技术学报,2017,25(2):203-208.
[5]朱递,刘瑜.一种路网拓扑约束下的增量型地图匹配算法[J].武汉大学学报(信息科学版),2017,42(1):77-83.
[11]郭庆胜,谢育武,刘纪平,等.顾及尺度变化和数据更新的道路网匹配算法[J].测绘学报,2017,46(3):381-388.
[12]杨茂,黄宾阳,江博,等.基于卡尔曼滤波和支持向量机的风电功率实时预测研究[J].东北电力大学学报,2017,37(2):45-51.
[15]杜文军,孙斌.基于正态云模型的果蝇优化算法[J].东北电力大学学报,2018,38(6):68-74.
[16]高文超,李国良,塔娜.路网匹配算法综述[J].软件学报,2018,29(2):225-250.
[17]吴刚,邱煜晶,王国仁.基于隐马尔可夫模型和遗传算法的地图匹配算法[J].东北大学学报(自然科学版),2017,38(4):472-475.
[18]李磊磊,陈家斌,杨黎明,等.基于道路信息的智能地图匹配算法[J].中国惯性技术学报,2016,24(2):170-174.
[22]廖佳,俞荐中,李俊峰.一种利用网格划分及方向加权的地图匹配算法[J].测绘通报,2017,63(3):124-127.
[23]赵庶旭,张金秋,屈睿涛.一种改进的浮动车地图匹配算法[J].测绘通报,2018,64(1):97-102.
[24]罗鹏飞,李明.一种特征融合的小目标车辆检测算法[J].河南科技大学学报(自然科学版),2019,40(2):40-44.
滕志军,李昊天,张宇,何义昌.动态距离权重因子的隐马尔可夫模型地图匹配算法[J].河南科技大学学报(自然科学版),2020,41(04):40-45+6-7.
基金:国家自然科学青年基金项目(61501107);吉林省教育厅“十三五”科学研究规划基金项目(JJKH20180439KJ).
分享：
遵义市普通高校羽毛球教师普遍存在着年轻化的趋势，教学内容与教学方法都比较单一，教学内容的学时均未达到国家指定的标准。因此，为了提高遵义市普通高校羽毛球选项课的开展，笔者提出了以下建议：1.实施人才引进。2.增加教学内容。3.转变教师的教学方法。4.严格遵循《指导纲要》的相关规定。
2020-07-09
数理统计的应用原理主要是通过随机现象的有限次数来实验和观测所得数据进行归纳和分析，并在得出的数据中找出一定的规律性来制定出一个具有科学依据的有效判断和推断。其特点是不仅具有能够为行业发展、管理工作提供有效参考数据的实际应用性，通过合理应用还可以提高行业竞争力。
2020-07-09
“概率论与数理统计”是研究随机现象数量规律的一门学科，也是研究生产生活中随机现象中隐藏的固有统计规律的一门数学学科，该课程的应用几乎遍及自然科学、社会科学、工程技术、军事科学及生活实际等各领域。“概率论与数理统计”课程的系统学习，可以培养学生认识问题、研究问题与处理相关实际问题的能力[1]。
2020-07-09
概率论和数理统计课程是国内高等院校理工类和经管类专业的一门基础性课程。这门课程具有很强的实践性,里面涉及到的理论和方法可以应用到很多领域,帮助解决问题,大数据统计分析更是一种非常实用的统计法[1]。它在医学、金融、保险等很多领域都发挥着非常重要的作用,因此被很多高校的很多专业所青睐,将其设置为公共基础课程。
2020-07-09
概率论与数理统计是一门通过演绎和归纳的方法研究随机现象及其规律性的一门学科。其理论和方法已被广泛应用于金融、经济、军事、生物、大数据等诸多领域中，是理科、工科、经济管理类专业必修的一门数学基础课程。尤其是随着计算机的普及和大数据时代的到来，概率论和数理统计是进行数据分析和数据处理的核心基础课程。
2020-07-09
《概率论与数理统计》是应用型本科院校各专业一门重要基础课,该课程的教学质量直接关系到人才培养的规格和质量,而该课程的建设是保证和提高教学质量的基础和前提。课程由概率论与数理统计两部分组成。概率论部分侧重于理论探讨介绍概率论的基本概念,建立一系列定理和公式,寻求解决统计和随机过程问题的方法。
2020-07-09
《概率论与数理统计》是一门研究和探索客观世界随机现象统计规律性的数学学科,是全国各类高等院校理科、工科、经济、管理、医学、农林等专业的必修基础课。它是以概率论为基础,研究如何以有效的方式获得、整理和分析受到随机性影响的数据,并以这些数据为依据,建立有效的数学模型,从而揭示所研究问题的统计规律性。
2020-07-09
《概率论与数理统计》是工科专业的一门必修课,是基础课中难度最大的学习领域,是一门处理随机现象的学科,其思想方法不同于高等数学、线性代数等研究确定性现象的数学分支。传统的教学方法注重理论的推导及简单应用,不能很好地将概率统计的知识应用于实际的问题中,使这门应用性很强的课程与实际存在一定距离。
2020-07-09
数学文化这个词的内涵,简单地说,是指数学的思想、精神、方法、观点,以及它们的形成和发展;广泛地说,除了上面的内涵之外,还包括数学家、数学史、数学美、数学发展的人文成分、数学与社会的联系等等。数学在人类文明的历史进程中一直都是先进的文化。人类历史每一个重大的事件背后都有数学的身影。
2020-07-09
在氨纶生产过程中，工艺、设备、自控以及人工智能方面飞速发展，工厂的生产规模已经从年产几千吨发展到年产十几万吨，以数理统计结果为决策依据的工作方法被越来越多的技术人员所认同。数理统计，甚至是大数据分析所发挥的作用会越来越大。本文介绍了氨纶生产中一些可以作为工具使用的数理统计方法。
2020-07-09
人气：4772
人气：3095
人气：2962
人气：2783
人气：2446
我要评论
期刊名称：大学数学
期刊人气：2138
主管单位：中华人民共和国教育部
主办单位：大学数学课程教学指导委员会(原数学与统计学教学指导委员会),合肥工业大学
出版地方：安徽
专业分类：科学
国际刊号：1672-1454
国内刊号：34-1221/O1
创刊时间：1984年
发行周期：双月刊
期刊开本：大16开
见刊时间：7-9个月
影响因子：0.553
影响因子：0.322
影响因子：0.352
影响因子：0.000
影响因子：0.000
科普杂志阅读、期刊信息查询、论文下载、文献查询、原创文章检测等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-05-26
697
上传者：管理员
