基于的观察序列的识别

5．2．4．1 HMM理论

1．HMM的初始状态

设有一个有限状态的过程，在每一个离散时刻t，它只能处于有限个多种状态下的某一种状态。假设允许出现的状态有N种，记为Sj，j＝1～N。

若该过程在时刻t所处的状态用Xt表示，那么Xt只能等于S1～SN中的某一个状态，这可表示为，对于任意的t，如果该过程运行的时间起点设定为t＝1，那么在以后的每一时刻t它所处的状态以概率方式取决于初始状态概率矢量π和状态转移矩阵A。

这里π是一个N维行矢量，即π＝［π1…πN］，它的每一个分量π1表示初始状态为Sj的概率，即π1＝Pr［X1＝Sj］，j＝1～N。

2．HMM的转移状态

矩阵A是一个N×N维方阵，它的每一个元素用表示，它是由状态Si转移到状态Sj的概率，是状态转移的概率分布。这是一个条件概率，可表示为：

即为已知相邻时刻中前一时刻的状态Si的条件下后一时刻状态为Sj的概率。

显然，j＝1 1，对于任意的i。状态转移矩阵可表示为ij］。

可以看到，对于任意时刻t，该过程的状态Xt取S1～SN中哪一种的概率只取决于前一时刻t－1所处的状态，而与更前的任何时刻所处的状态无关。

3．HMM的输出状态

如果Yt具有离散分布，它的概率分布只取决于Xt，可表示为：

PXt＝Sj［Yt］＝Pr［Yt／xt＝Sj］，t≥1，j＝1～N

它表示在Sj状态下，输出Yt的概率分布。

假设一个HMM模型从t＝1时刻开始运行，在t＝1～N时刻所给出的N个随机矢量Yt构成一个广义N维矢量及矩阵Y＝［Y1，Y2，…，YN］。对于HMM模型，其每一次运行过程所产生的Markov链X是外界看不见的，可观测的只是Y。

上述概率密度函数与t取何值无关，只取决于状态Sj。N个概率密度函数构成一个N维行的矢量B，它可表示为。

4．观察序列产生的步骤

给定HMM模型λ＝f（A，B，π），则观察序列Y＝Y1，Y2，…，YN可由以下步骤产生：

步骤1 根据初始状态分布概率π，选择一个初始状态，置时刻t＝1；

步骤2 根据输出矩阵B，得出Si状态下输出的概率分布为；

步骤3 根据转移矩阵A，由t时刻的Si状态转移到t＝t＋1时为Sj状态的转移概率分布确定下一个状态；

步骤4 如果t＜N，则回到第2步，否则结束。

为此，可以用式（5－4）来说明这个过程。即HMM可定义为：

λ＝f（A，B，π）（5－4）

在A、B、π这三个模型参数中，π（初始概率分布）最不重要，B（某状态下系统输出的概率分布）最为重要，因为它就是外界观察到的系统输出的概率。而A（状态转移概率分布）的重要性要差一些。

5．HMM的三个基本问题

令λ＝f（A，B，π）为给定HMM的参数，令Y＝Y1，Y2，…，YN为观察值序列，则有关于HMM的三个基本问题：

（1）评估问题：对于给定HMM模型，求某个观察值序列的概率P（Y｜λ）；

（2）解码问题：对于给定HMM模型和观察值序列，求可能性最大的状态序列max｛P（X｜Y，λ）｝；

（3）学习问题：对于给定的一个观察值序列Y，调整HMM模型参数λ，使得观察值出现的概率P（Y｜λ）最大。

5．2．4．2 HMM三个基本问题的求解算法

1．评估问题

图5．7 HMM观察序列图

（1）公式推导过程

假设观察值都是独立的，则：

某一状态的序列概率为：

P（Y，X｜λ）＝P（Y｜X，λ）P（X｜λ）（5－7）

评估问题的概率值为：

（2）前向算法

评估问题的解决方案目前比较盛行的有前向算法和后向算法，下面对前向算法的过程进行介绍：

前向算法是在时间步t，得到t之前的所有观察序列，且时间步t的状态是Si这一事件的概率，记为：αt（i）＝P（Y1，…，Yt，Xt＝Si｜λ）。

算法过程为：

步骤1 α1（i）＝P（Y1，X1＝Si｜λ）＝π（i）bi（Y1）

步骤2

步骤3

图5．8 前向算法示意图

（3）后向算法

后向算法是在时间步t，得到t之前的所有观察序列，且时间步t的状态是Si这一事件的概率，记为算法过程为：，1≤t≤T－1。

算法过程为：

步骤1 βT（i）＝1，1≤t≤T

步骤2

步骤3

图5．9 后向算法示意图

2．解码问题

给定观察序列Y和HMMλ＝（A，B，π），计算与序列Y相对应的最佳状态序列X。（1）公式推导过程

定义：

通过前向算法的推导得：ψt（j）为记忆变量，记录概率最大路径上当前状态的前一个状态。

（2）Viterbi算法

Viterbi算法也是类似于前向算法的一种网格结构。给定一个观察序列和HMM模型，如何有效选择“最优”状态序列X，以“最好地解释”观察序列Y。

算法过程为：

步骤1

步骤2

步骤3

步骤4

3．学习问题

（1）公式推导过程

也称训练问题、参数估计问题。在HMM中，模型的训练是指在给定初始模型参数后，用模型输出对其进行校正，来优化模型参数。由于HMM的随机性，最初的模型不可能是最佳的。参数优化的过程表明HMM的模型参数可根据状态的变化不断调整。

HMM的训练是三个问题（模型选择、状态序列选择和训练过程）中最困难的一个，目前尚无求解这个问题的解析方法。所以，只能用迭代法（如Baum－Welch法）来解决。Baum－Welch算法具有如下参数：ij：状态i到状态j的转移概率，aij＝0（j≠i，i＋1）。：状态i时，输出观察值k的概率，参数，是通过Baum－Welch算法进行训练得到的。算法中定义前向变量αt（i）和后向变量βt（i）。αt（i）表示为在给定模型λ，t时刻，状态为Si时的部分观察序列的概率αt（i）＝P（Y1，Y2，…，Yt，Xt＝Si／λ），1≤t≤T。βt（i）表示为在给定模型λ下，t时刻，状态为Si时的部分观察序列t＋1到最后的概率， ，1≤t≤T－1。

（2）向前向后算法（Baum－Welch算法）

算法步骤：

步骤1 初始化，，；

步骤2 EM步骤；

E步骤——计算ξt（i，j）和γt（i）：

给定HMM和观察序列，ξt（i，j）为在时间t处于状态i，时间t＋1处于状态j的概率：

给定HMM和观测序列，在时间t位于状态i的概率：

M步骤——用E步骤所得的期望值，重新估计模型，得到新模型λ。

πi＝X1为Si的概率＝γ1（i）

步骤3 循环设计i＝i＋1；重复EM步骤，直到πi，，收敛。

图5．10 Baum－Welch算法示意图

5．2．4．3 算法实现

根据上述HMM的理论知识，对于城市交叉口的观察序列的识别可以用HMM来描述。模型中存在有限个隐藏状态，这些状态代表抽象数量（如直行、左转和右转等4个方向的交通运行的组合）与之相对应的具有相似性的观察值的分布概率。在每一个离散时间单位，在过滤概率分布的基础上输入一个新的状态，新状态的输入取决于输入之前的状态（马尔可夫过程的属性）。每一次转移发生后，观察值的输出是根据分布概率产生的，分布概率只在当前状态下进行修复。

目前有许多时间序列识别方法，如DP匹配算法（Dynamic Programming Matc－hing）、神经网络算法和HMM算法。观察序列的识别是基于随机模型而不是基于具体模型。因为事件序列由大量的随机过程组成，且随机过程能通过随机模型来描述。DP匹配算法是一种精确的识别方法，但是在动态观察中不稳定，所以在动态观察中采用HMM和神经网络算法优于DP匹配算法。另外，在观察序列长度方面，HMM要优于神经网络算法。在本章中采用简单的从左至右的HMM模型进行事件检测，其转移过程如图5．11所示。

图5．11 从左至右的HMM

1．模型定义

对于一个随机事件，有一观察值序列：Y＝Y1，Y2，…，YT，该事件隐含着一个状态序列：X＝X1，X2，…，XT。一个隐马尔可夫模型（HMM）是由一个五元组描述的：λ＝（X，Y，A，B，π）。

T＝图像序列的长度；

X＝｛X1，…，XT｝：状态的有限集合；

Y＝｛Y1，…，YT｝：观察值的有限集合；）：状态转移概率矩阵；）：观察值概率分布矩阵；

π＝｛πi｝，πi＝P（X1＝Si）：初始状态概率分布；：状态i时，输出观察值i的概率。算法中定义前向变量αt（i）和后向变量βt（i）。αt（i）表示为在给定模型λ，t时刻，状态为Si时的部分观察序列的概率αt（i）＝P（Y1，Y2，…，Yt，Xt＝Si／λ），1≤t≤T。βt（i）表示为在给定模型λ下，t时刻，状态为Si时的部分观察序列t＋1到最后的概率，1≤t≤T－1。

2．HMM处理流程

HMM的三个基本问题的求解过程也就是对时间序列图像转变成符号或数字序列输出的过程，其具体操作过程见图5．12流程图。

3．实验结果及分析

为了验证HMM的观察序列的有效性，实验中拍摄了3组交叉口视频图像，每组视频时间为2分钟，速度为10帧／s，其每组视频里都有直行、左转和右转车辆。实验将对这3组视频图像分别进行试验，即对直行［pas－0］、左转［pas－1］、右转［pas－2］ 3种交通进行识别。每一组观察序列由12个观察值组成，其观察值为具有冲突的两辆车的特征值，在5．2节中有详细介绍。实验观察序列值如表5．1所示。

图5．12 HMM处理流程图

表5．1 观察序列值

表5．1中3组视频的观察序列在［pas－0］、［pas－1］、［pas－2］3类中都有所区别，这是因为3组视频各自的干扰条件不一样，仔细发现它们之间的区别比较小，也就是说分类结果比较稳定。通过这次实验表明，在任何干扰条件下，都可以采用HMM算法对［pas－0］、［pas－1］、［pas－2］进行分类，并且能得出比较稳定的观察序列值。

结合上述3种观察序列，直行［pas－0］、左转［pas－1］、右转［pas－2］，对图5．3中的4种冲突分类为：

［pas－00］图5．3（a）：表示直行与直行冲突；［pas－11］图5．3（b）：表示左转与左转冲突；

［pas－02］图5．3（c）：表示直行与右转冲突；

［pas－12］图5．3（d）：表示左转与右转冲突。