道路匹配MapMatching：HMM模型、维特比算法Viterbi、道路匹配基本算法ST、STD、IVVM算法介绍

àì夳堔傛蜴生んèń 2024-03-30 14:01 42阅读 0赞

#### 道路匹配MapMatching：HMM模型、维特比算法Viterbi、道路匹配基本算法ST、STD、IVVM算法介绍 ####

*  前言
 *  一、隐马尔科夫模型（HMM）
 *  二、维特比算法Viterbi
 *  三大基本算法ST、STD、IVMM
 *   *  （1）ST
     *  （2）STD
     *  （3）IVMM
 *  总结

--------------------

## 前言 ##

我曾经做过有关`道路匹配(MapMatching)`的相关研究，学习过几个重要的道路匹配算法，我将先对`重要的匹配模型：隐马尔科夫模型（HMM）`进行介绍，再介绍`维特比算法Viterbi`，最后对`ST、STD、IVMM`三种算法做一个简单的介绍，供大家参考。

--------------------

## 一、隐马尔科夫模型（HMM） ##

隐马尔科夫模型（Hidden Markov Model，简称为HMM）是一种常见的统计学模型，是在马尔科夫链的基础上发展而来。由一个隐藏的马尔可夫链随机生成的不可观测的状态序列，再由各个状态生成一个观测而产生观测随机序列的过程，就是隐马尔可夫模型。

**部分图片和内容来自：**  
HMM具体介绍: [隐马尔可夫模型（Hidden Markov Model）][Hidden Markov Model]

链接中写的很详细，有文字有图片，大家可以去认真学习一下。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3oyNTM2MDgzNDU4_size_16_color_FFFFFF_t_70][]  
![Alt][]![Alt][Alt 1]

## 二、维特比算法Viterbi ##

维特比算法的过程简单来说就是：1.先从前向后推出一步步路径的最大可能，最终会得到一个从起点连接每一个终点的n条路径(假设有n个终点)。  
![Alt][Alt 2]  
**部分内容和图片来自：**  
维特比算法介绍: [机器学习：维特比算法（Viterbi Algorithm）][Viterbi Algorithm]

## 三大基本算法ST、STD、IVMM ##

首先，我建议所有学习路网匹配内容的同学都去看一篇论文：  
论文链接: [路网匹配算法综述][Link 1]  
这篇论文介绍了很多常见的路网匹配算法，经典之作，非常值得认真学习

### （1）ST ###

ST算法后面把空间分析函数和时间分析函数作了乘积，相当于考虑是空间（Spatial）和时间（Temporal）的因素，简称为ST算法。

参考链接: [地图匹配之ST-Matching和IVVMM][ST-Matching_IVVMM]

### （2）STD ###

STD算法在ST算法的基础上发展而来，增加了方向分析（Direction），考虑了单个轨迹点的方向对整体匹配的影响。  
![在这里插入图片描述][1ea586aad4124bf5bc525cfea819183a.png]

### （3）IVMM ###

内容来自：[An Interactive-Voting Based Map Matching Algorithm][]  
ST-Matching 在匹配路网时,会把 GPS 点对应到距离较近的路段上,并不考虑其相邻点的关系,所以会出现锯齿形的线路.IVMM 的提出,就是为了“拉直”不匹配的路段,使其更适合地面真实路径.它在 ST-Matching 的基础上加入了“互动投票”,就是说,每个候选点会对在同一条单点最优的轨迹上的其他候选点进行加强,即投票,最后打分最高的点连起来形成匹配路径.  
![在这里插入图片描述][748a6cd2e9ce4afe9ad47a4df8cf3e64.png]

## 总结 ##

本文介绍了HMM模型、维特比算法、三种常见路网匹配算法（ST、STD、IVMM）。文中部分内容和图片来自学术论文，建议大家先去看论文，再看看文章中的介绍来增加自己的理解。  
希望对大家有用！

[Hidden Markov Model]: https://blog.csdn.net/z2536083458/article/details/99696875
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3oyNTM2MDgzNDU4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7f3c506d481a424e8fc538aca4522361.jpg
[Alt]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6a91d89705a04a50aab13c43149387fa.png
[Alt 1]: https://img-blog.csdnimg.cn/20191117215321819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Zlbmc1MTIyNzU=,size_16,color_FFFFFF,t_70
[Alt 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/414a2bd19bb24d41b0dcdb6cf84ded67.png
[Viterbi Algorithm]: https://blog.csdn.net/u013250861/article/details/122284630
[Link 1]: http://www.jos.org.cn/josen/article/abstract/5424
[ST-Matching_IVVMM]: https://blog.csdn.net/Feng512275/article/details/103113341
[1ea586aad4124bf5bc525cfea819183a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5e08315f3f2c41c79076be512c44c6bd.png
[An Interactive-Voting Based Map Matching Algorithm]: https://ieeexplore.ieee.org/abstract/document/5489808/
[748a6cd2e9ce4afe9ad47a4df8cf3e64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/63a062c8672b47cf9b4cebf2f22439a8.png