隐马尔可夫

隐马尔可夫（精选8篇）

隐马尔可夫 篇1

摘要：在网络教学过程中, 为了强化学生对知识的灵活运用, 教师通常会引入虚拟实验实训、在线测试之类的系统对学生进行知识训练。以数据库课程SQL在线测试系统为例, 为了发现抄袭和异常的学习行为, 引入隐马尔可夫模型, 对正常的学习行为进行建模, 并使用滑动窗口技术解决学习序列长度不一而影响输出概率的问题。实验结果表明, 评估模型对抄袭和异常学习行为的识别率比普通方法高, 准确率达到93%。

关键词：隐马尔可夫模型,学习行为,滑动窗口,抄袭,学习异常

0 引言

网络教学打破传统课堂教学的时空限制, 具有便捷、泛在访问等特点, 正成为时下高校流行的教学方式。学生可通过丰富的网络媒介 (如浏览网页、讨论板、博客、wiki、提问等) 进行学习。当前已有学者使用BP神经网络和C4.5算法对学生使用网络媒介的学习行为进行效果评估[1,2]。为了强化学生对知识的灵活运用, 教师通常会引入虚拟实验实训、在线测试之类的系统对学生进行知识训练。文献[3]使用隐马尔可夫模型HMM (Hidden Markov Model) 实现知识点智能引导。笔者曾使用模糊聚类方法对CSCL学习者的混合分组进行了基础研究[4]。在小组学习过程中, 有时候学生为了应付教师, 往往弄虚作假。对于学生抄袭或学习异常的学习行为, 系统反馈的有可能是虚假信息, 教师难以及时发现隐藏在虚假信息背后的真实行为, 无法及时帮助学生纠正错误。

隐马尔可夫模型在语音识别、网络异常检测、行为异常检测方面得到广泛的应用[5,6]。为了从大量学习记录中挖掘和提取有用信息, 本文引入隐马尔可夫模型, 以数据库课程SQL在线测试系统为例, 建立基于隐马尔可夫模型的学习行为评估模型, 评估和发现学生的抄袭和异常行为。

1 隐马尔可夫模型

1.1 隐马尔可夫模型定义

隐马尔可夫模型是一个双重随机过程, 包含两个随机变量序列:一个是观察不到的马尔可夫链, 用来描述状态的转移, 用转移概率表示;另一个是可以观察到的随机序列, 用来描述状态与观察值的关系, 用观察值概率表示。完整的隐马尔可夫模型由一个五元组λ= (S, V, A, B, π) 表示[7], 其中:

(1) S为隐藏状态集合, S={s1, s2, …, sN}, |S|=N, 并记t时刻的状态为qt, qt∈S。

(2) V为观察符号集合, V={v1, v2, …, vM}, |V|=M并记t时刻观察到的符号为ot, ot∈V。

(3) A为状态转移概率矩阵, A= (aij) , aij表示如果在t-1时刻状态为si, 则在t+1时刻转移到状态sj的概率, 即aij=P (qt+1=sj|qt=si) 1≤i, j≤N。

(4) B为状态的观察符号概率分布, B={bj (k) }, bj (k) 表示在状态sj下观察到符号vk的概率, 即bj (k) =P (ot=vk|qt=sj) 1≤k≤M, 1≤j≤N。

(5) π为初始状态的概率分布, π={πi}, πi表示在时刻t=1时, 处于状态si的概率, 即πi=P (q1=si) 1≤i≤N。

隐马尔可夫模型的性质完全由A、B、π所确定, 为了方便, 简记为λ= (A, B, π) 。如无特别说明, 这里指的是一阶隐马尔可夫模型。

1.2 隐马尔可夫模型的应用

已知观察序列O= (o1, o2, …, oT) 和模型λ= (A, B, π) , HMM在实际的应用中要解决下列三个问题:

(1) 评估问题:求模型λ产生观察序列O的条件概率P (O|λ) , 可使用前向算法求解。

(2) 解码问题:求模型λ产生观察序列O的最可能的状态序列, 可使用Viterbi算法求解。

(3) 学习问题:使用观察序列O, 调整模型λ参数, 使得条件概率P (O|λ) 最大, 可使用Baum-Welch算法求解。

1.3 Baum-Welch算法介绍[8]

给定模型λ和观察序列O:

(1) 定义前向变量:

表示在给定模型λ的条件下, 在t时刻, 产生部分观察序列 (o1, o2, …, ot) , 并处于状态si的概率。前向变量可由下式进行迭代计算:

其中, α1 (i) =πibi (o1) 。

(2) 定义后向变量:

表示t时刻状态为si的条件下, 在t+1时刻到最后, 产生部分观察序列 (ot+1, ot+2, …, oT) 的概率。后向变量可由下式进行迭代计算:

其中, βT (i) =1。

(3) 定义输出概率:

(4) 定义t时刻在状态si, t+1时刻在状态sj的概率:

(5) 定义t时刻处于状态si的概率:

(6) 定义从状态si转移到状态sj的期望次数与从状态si转移的期望次数之比:

(7) 定义处于状态sj且观察符号为vk的期望次数与处于状态sj的期望次数之比:

(8) 定义t=1时刻处于状态si的概率:

构成新的HMM重估模型。给定初始模型λ= (A, B, π) , 利用训练序列, 通过反复迭代, 计算重估模型。当重估模型收敛时, 即可得出局部最优的HMM重估模型参数。Baum-Welch算法如下:

输入:A, B, π, O

输出:

(1) 初始化终止条件δ。

(2) 迭代计算:

(3) 如果Δp>δ, 继续迭代;否则终止。

2 建立隐马尔可夫模型

2.1 SQL在线测试系统介绍

本文设计了一个SQL在线测试系统。学生登录系统, 在题库中选择训练题, 按要求编写并在线提交SQL语句。测试系统编译并运行SQL语句, 并对运行结果进行自动评估。测试系统反馈六种结果:结果正确、SQL错误、行数不等、列数不等、数值不等和列名不等。学生做题是随机的, 每道题都会产生6种反馈结果中的一种。教师无法直接了解学生对题目知识的掌握程度, 只能通过学生做题时系统的反馈结果进行观察。

笔者把SQL在线测试系统应用在计算机专业二个教学班上, 经过一学期的实际教学使用, 共收集到94个学生的2万多个做题记录。

2.2 设置模型参数

学生选题是随意的、无序的, 但做题尝试是和时间相关的。学生的每次做题尝试, 都可看作是对知识点掌握程度的一个反映 (观察值) 。做题尝试序列反映知识点掌握程度状态的转移。

根据学生的学习情况, 定义对知识点的掌握程度状态集S={完全掌握, 基本掌握, 了解一点, 完全不会, 抄袭}, 状态数N=5。定义观察符号集V={结果正确, SQL错误, 行数不等, 列数不等, 数值不等, 列名不等}, 观察符号数M=6。初始为全体学生做题序列里符号vi的数量。根据学生的学习状态, 估计初始状态转移矩阵和状态观察符号概率分布, 作为模型的初始训练参数。

2.3 模型训练

以学生为单位, 以时间先后次序, 生成每个学生的做题反馈结果序列 (观察序列) 。先从全体学生样本中随机抽取15%样本作为未知集 (待检验集) 。然后根据教师观察学生的课堂练习情况, 通过人工方式把剩下的学生样本归为:正常集、抄袭集和异常集。正常集中抽取65%数据作为训练集, 剩下35%作为基准集。

本文前面列出的Baum-Welch算法公式只适用于单个训练样本, 对于训练集里存在多个学生样本序列的情况, 这里使用适用于多训练样本的推广的Baum-Welch算法。对训练集应用推广的Baum-Welch算法进行训练, 得出正常行为HMM模型。

3 模型应用

3.1 引入滑动窗口技术

由于每个学生的做题记录是不同的, 因而观察序列的长度也差别较大。因此不能简单地直接比较各个学生观察序列的模型输出概率。为了使输出概率的比较更具科学性, 引入滑动窗口技术[9]来分割观察序列。令l为滑动窗口大小, 滑动窗口每次向后移动一位, 整个观察序列可分为T-l+1个子序列 (T为整个观察序列的长度) 。令W={wk} (1≤k≤T-l+1) 为子序列的集合, 使用滑动窗口求解所有子序列输出概率P (wk|λ) 的滑窗-前向算法如下 (为了突出输出概率, 方便比较, 这里取输出概率的对数) :

输入:N, O, T, π, A, B, l

输出:log P (wk|λ)

(1) 循环:wk= (ok, ok+1, …, ok+l-1) k=1, …, T-l+1

(2) 对每个wk进行:

(3) 初始化:α1 (i) =πibi (ok) 1≤i≤N;

(4) 迭代计算:

(5) 迭代终止:

(6) 循环结束。

3.2 评估学生做题序列

使用滑窗-前向算法应用正常行为HMM模型对基准集每一个样本求所有子序列的输出概率对数均值:

取所有样本的均值作为学生做题的正常值。

对抄袭集和异常集, 分别对集合里每个学生样本的观察序列使用滑窗-前向算法求各个子序列的log P (wk|λ) 。将所有的子序列标记为“抄袭”。定义所有“抄袭”的子序列数φhigh与总子序列数φ的比值为抄袭度:

将所有的子序列标记为“异常”。定义所有“异常”的子序列数φlow与总子序列数φ的比值为异常度:

4 实验结果

4.1 实验数据与分析

由于学生做题的平均尝试次数约为7次, 这里设定滑动窗口大小为7。正常集、抄袭集、异常集里所有样本的对比如表1所示。

由表1可知, 抄袭集的输出概率均值比基准集高, 原因是学生都是抄袭别人正确答案, 观测值都是“结果正确”居多, 其它观测值很少, 自然输出概率均值比正常值高;异常集的输出概率均值比基准集低, 原因是学生正确做题的数量不多, 但是错误反馈比基准集多。

对各个数据集的每个学生样本计算其抄袭度和异常度, 结果如表2所示 (限于篇幅, 只列出部分典型样本数据) 。

由定义可知, 正常的抄袭度和异常度应该都是在0.5上下小幅浮动。表2的数据显示, 抄袭集的抄袭度和异常集的异常度都高于正常值。通过人工分类的抄袭集和异常集, 在HMM里得到正确标记。

HMM对未知集样本评估结果显示:S128比值偏高, 属典型的抄袭行为;S137和S244显示正常;S235比值偏低, 可能学习存在问题。通过课堂观察和学生面谈等人工调查, 结果显示, S128课堂常开小差, 大部分题目抄袭别人答案;S137独立完成;S235对知识掌握得不好, 常常出现语法等错误;S244是学习尖子, 喜欢独立钻研。观察S244的学习序列, 发现某些错误连续多次出现, 长度是普通学生的2倍多, HMM因而把其判定异常。除S244估计有偏差外, HMM对未知数据集其余样本的学习行为评估基本正确。

4.2 HMM和其它方法对比

当前还没发现和本文相似的研究文献, 为了对比HMM对各个数据集评估的正确率, 这里使用一种简单可行的方法:以学生每道题的平均尝试次数 (题均数) 来检测抄袭和异常学习行为。正常的题均数的范围为3~9之间, 低于此区间的定为抄袭, 高于此区间的定为异常。HMM与题均数法的结果对比如图1所示。

由图1可以看出, 通过人工分类的抄袭集和异常集, HMM都能正确标记, 但题均数方法就存在偏差, 对未知集的评估比HMM差。总的来说, HMM方法的正确率比题均数法要高。

5 结语

本文介绍了隐马尔科夫模型的原理。以SQL在线测试系统为例, 使用HMM建立学习行为评估模型。引入滑动窗口技术来解决学习序列长度不一而影响输出概率的问题。使用正常的学习序列进行训练, 由此评估学生的学习行为是否偏离正常。实验结果表明, HMM模型识别抄袭和异常学习行为的正确率比普通方法要高。虽然以SQL在线测试系统为例, 但本文使用的方法完全可以推广到其它一般系统。本文在实际应用中也存在一些需要改进的地方, 如对知识点掌握程度的状态集的分类有待更深入研究, 可使用半监督的建模方法[10]改进人工标记数据集进行建模。

参考文献

[1]姜华, 赵洁.基于BP神经网络的学习行为评价模型及实现[J].计算机应用与软件, 2005, 22 (8) :89-91.

[2]范洁, 杨岳湘, 温璞.C4.5算法在在线学习行为评估系统中的应用[J].计算机工程与设计, 2006, 27 (6) :946-948.

[3]翟琳琳, 陈仪香.隐马尔科夫模型在智能学习系统中的应用[J].计算机工程与应用, 2007, 43 (6) :178-180.

[4]黄志成.基于模糊聚类的CSCL学习者混合属性分组[J].计算机应用与软件, 2011, 28 (2) :118-121.

[5]温凯, 郭帆, 余敏.自适应的Web攻击异常检测方法[J].计算机应用, 2012, 32 (7) :2003-2006.

[6]李战明, 宋丙菊.基于隐马尔可夫模型的ATM机用户异常行为识别[J].兰州理工大学学报, 2012, 38 (5) :77-81.

[7]Rabiner L R.A tutorial on hidden Markov models and selected applications in speech recognition[J].Proceedings of the IEEE, 1989, 77 (2) :257-289.

[8]杜世平.隐马尔可夫模型的原理及其应用[D].四川:四川大学, 2004:1-10.

[9]张响亮, 王伟, 管晓宏.基于隐马尔可夫模型的程序行为异常检测[J].西安交通大学学报, 2005, 39 (10) :1056-1059.

[10]李和平, 胡占义, 吴毅红, 等.基于半监督学习的行为建模与异常检测[J].软件学报, 2007, 18 (3) :527-537.

隐马尔可夫 篇2

In this paper,we define a model of random dynamical systems(RDS)on graphs and prove that they are actually homogeneous discrete-time Markov chains.Moreover,a necessary and sufficient condition is obtained for that two state vectors can communicate with each other in a random dynamical system(RDS).

作 者：郑洁 刘朝阳 ZHENG Jie LIU Chao-yang 作者单位：郑洁,ZHENG Jie(Department of Applied Mathematics,Donghua University,Shanghai 20,China)

刘朝阳,LIU Chao-yang(Zhengzhou Dongxifang Computer Network Engineering Limited,Henan University,Zhengzhou 450008,China)

隐马尔可夫 篇3

隐马尔可夫模型的概念是一般马尔可夫链概念的自然推广, 近年来, 在弱相依变量的建模上得到了广泛应用, 是研究发音过程、神经生理学与生物遗传等问题的有力工具。在理论方面, Leroox[1]与Bickel和Ratof[2]分别给出了隐马尔可夫模型在大数定律与中心极限定理方面的一些性质。在实际当中经常遇到隐藏链为非齐次马氏链的情况, 如动态的图形处理、气候的预测等均需要建立非齐次马尔可夫模型来处理[3,4]。所以研究隐非齐次马可夫模型的极限性质具有十分重要的意义[5,6]。

定义1.1 设S={1, 2, …, M}, T={1, 2, …, N}为两个有限集, {Xn, n≥0}与{Yn, n≥0}是概率空间 (Ω, F, P) 上的取值于S与T的随机变量序列.假设{Xn, n≥0}是非齐次马氏链其初始分布为 (q (1) , q (2) , …, q (M) ) , 转移矩阵为Pn= (an (i, j) ) M×M, i, j∈S, n≥1, 其中an (i, j) =P (Xn=j│Xn-1=i) , 称{Xn, n≥0}为状态链.它不能被直接观测到, 称为隐藏链;而能观测到的是{Yn, n≥0}, 称为观测链.如果存在矩阵B= (bij) M×N (i∈S, l∈T) 满足

P (X0=x0, Y0=y0, …, Xn=xn, Yn=yn) =q (x0) bx0y0a1 (x0, x1) …an (xn-1, xn) bxnyn。

则称{Xn, Yn, n≥0}为一个马尔可夫模型[7]。由于隐藏的马尔可夫链是非齐次的, 文中不妨称之为隐非齐次马尔可夫模型。

引理1[8] 设{Xn, Yn, n≥0}是如前定义的隐非齐次马尔可夫模型, f (x, y, z) 为定义在S×S×T上的实值函数, 令Fn=σ (Xm, Ym, 0≤m≤n) , 则有

引理2[9] 设{Xn, n∈N}是鞅差序列, {an, n∈N}为单调上升趋向于无穷的数列, 且${\displaystyle \sum _{n=1}^{\infty }a}{}_n{}^{-2}EX{}_n^2<\infty$, 则

$\underset{n\to \infty }{{\displaystyle \lim }}\frac{1}{a{}_n}$${\displaystyle \sum _{i=1}^n}$Xi=0 a.s. (1.2)

2 主要结果

定理1 设{Xn, Yn, n≥0}是如前定义的隐非齐次马尔可夫模型, fn (x0, x1, …, xn, xn+1) 为定义在Rn+2上有界Borel可测函数且│fn│≤M, 若{an, n≥0}是趋向于无穷的增序列, 且对任意自然数n,

│${\displaystyle \sum _{k=1}^{n}a}{}_k{}^{-2}│\le L(0<L<+\infty )$ (2.1)

则

$\begin{array}{l}\underset{n\to \infty }{{\displaystyle \lim }}\frac{1}{a{}_n}{\displaystyle \sum _{k=1}^n\{}f{}_k(X{}_0,\cdots ,X{}_k,Y{}_k)-\\ E[f{}_k(X{}_0,\cdots ,X{}_k,Y{}_k)│X{}_{k-1}]\}=0\text{a}.\text{s}.(2.2)\end{array}$

证明 令

Zk=fk (X0, …, Xk, Yk) -E[fk (X0…, Xk, Yk) │Xk-1], k≥1 (2.3)

设Fn如引理1的定义, 下证{Zk, k≥1}是一个鞅差序列, 因为E[fk│Xk-1]为Fk-1可测的, 故

由引理1, (2.3) 式与 (2.4) 式, 有

E[Zk│Fk-1]=0 a.s. k≥1 (2.5)

故序列{Zk, k≥1}是一个鞅差序列.又

由条件期望Jensen的不等式, 有

故由 (2.1) 式与 (2.7) 式有

$\begin{array}{l}{\displaystyle \sum _{n=1}^{\infty }a}{}_n{}^{-2}E\{E[f(X{}_0,\cdots ,X{}_n,Y{}_n)│X{}_{k-1}]\}{}^2\le \\ {\displaystyle \sum _{n=1}^{\infty }a}{}_n{}^{-2}E[f{}^2(X{}_0,\cdots ,X{}_n,Y{}_n)]\le {\displaystyle \sum _{n=1}^{\infty }{\rm M}}{}^{2}a{}_n{}^{-2}(2.8)\end{array}$

由 (2.1) 式有${\displaystyle \sum _{n=1}^{\infty }a}{}_n{}^{-2}<+\infty$.从而

$\begin{array}{l}{\displaystyle \sum _{n=1}^{\infty }a}{}_n{}^{-2}E\{E[f(X{}_0,\cdots ,X{}_n,Y{}_n)│X{}_{k-1}]\}{}^2\le \\ {\displaystyle \sum _{n=1}^{\infty }{\rm M}}{}^{2}a{}_n{}^{-2}<+\infty (2.9)\end{array}$

由 (2.1) 式, (2.3) 式与 (2.8) 式, 有

${\displaystyle \sum _{n=1}^{\infty }a}{}_n{}^{-2}E{\rm Z}{}_n{}^2<\infty$ (2.10)

由 (2.10) 式与引理2有

$\underset{n\to \infty }{{\displaystyle \lim }}\frac{1}{a{}_n}{\displaystyle \sum _{k=1}^n{\rm Z}}{}_k=0\text{a}.\text{s}$. (2.11)

由 (2.3) 式与 (2.11) 式, 即得 (2.2) 式。

参考文献

[1]Leroux B G.Maximum-likelihood estimation for hidden Markov mod-els.Stoc hastic Processes and their Appl, 2002;40:127—143

[2]Bickel P J.Ritov Y, Ryden T.Aymptotic nomality of the maximum-like lihood estimator for general hidden Markov models.The Annals of Statistics, 2005;26 (4) :1614—1635

[3]Bates B C, Charles P, Hughes J P.Stochastic down-scaling of nu-merrical climate model simulations.Environmental Modeling soft-ware, 2006;13:325—331

[4]Lacruz B, Lasala P, Lekuona A.ynamic graphical models and nonhomo-geneous hidden Markov models.Stat Proba Letts, 2006;49:377—385

[5]Shaohua.Aconclusion about the transition matrix.World acdemic U-nion, 2006;112—115Theory, 1990;36 (5) :1006—1018

[6]Jin Shaohua.关于极限定理的一个结果及其推广.数学的实践与认识, 2007;37 (13) :118—123

[7]龚光鲁, 钱敏平.应用随机过程教程.北京:清华大学出版社, 2004:249

[8]Chung K L.A course in probability theory.New York;Academic Press, 1974

隐马尔可夫 篇4

作为图像识别的重要研究方向,人脸识别技术是当前生物特征识别技术中的研究热点。与其他生物特征的识别相比,人脸图像能更直观、更方便地核查人的身份,在商业、安全、法律等领域具有广阔的应用前景。

由于人脸识别受到光照,姿态,角度等环境因素影响,其识别率难以得到保证。从上世纪八九十年代起,各种人脸识别方法层出不穷,隐马尔可夫模型HMM(Hidden Markov Model)方法是一种重要的方法。Samaria[1]最早将HMM方法引入人脸识别,Nefian[2]发展这一方法,提出使用2D-DCT特征取代直接使用灰度值作观察值的方法,减少计算量。之后Nefian[3]、Eickler[4]等人又提出了各自的伪二维嵌入式隐马尔可夫模型EHMM(Embedded HMM),细化了HMM的结构。刘小军[5]使用局部奇异值分解作为图像特征,更充分的表征人脸图像。Li[6]等人提出一种自适应HMM,包含的状态数并不固定,而是随着信号源的不同而改变,可以更细致地反映模式的信息。Chien[7]等人提出最大置信HMM,通过最大化来自目标HMM观察向量的置信度,得到一种新的区分性训练准则,提高识别率。Huang[8]等人将人脸图像分为五个五官的子区域,对于每个区域建立独立的HMM,再通过一个脸部的语法网络将这些子HMM重组为一个人脸HMM,可以处理图像部分遮挡问题。Cai[9]等人提出使用非重叠的采样窗口扫描图像,并将采样窗口的奇异值与2D-DCT通过典型相关分析融合,结果减少训练与识别的计算量。Vaseghi[10]等人将提取的特征向量量化本实用K均值算法分为两类,使得一幅人脸图像产生两个HMM,识别结果为两个HMM的相似度之和,可以提高识别率。由此可以看出,大多数研究重点都是放在模型的训练与识别率的提高上。但是由于HMM脸识别的训练结果是每个人脸都得到一个模型,识别时需要把待识别人脸图像的特征序列代入每个人脸的HMM用Viterbi算法计算最大相似度。这就引发了一个问题,是否可以找到一个识别的方法,不需要对每个人脸模型都计算相似度,并且几乎不降低识别率的前提下,提高识别的速度。本文提出一种改进的基于HMM的人脸识别方法,将观察序列进行分割,通过逐步将观察序列使用Viterbi算法计算,每次排除若干HMM,达到提高识别速度的效果。

1 HMM的基本概念

HMM是马尔可夫链的一种,用于描述随机过程统计特性。包括双重随机过程,一个是隐含的状态,它的状态不能直接观察到。另一个是观测向量序列,每一个观测向量是由一个具有相应概率密度分布的状态序列产生。

HMM包括5个元素:

(1)隐含状态的数目N,状态集为S={s1,s2,…,sN};

(2)观察序列的数目M,观察序列集为V={v1,v2,…,vm};

(3)状态转移矩阵A,A={aij},aij=P[qt+1=sj|qt=si],1≤i,j≤N。其中qt为在时刻t的状态。A为N×N的方阵,行和列都对应所有的状态,表示状态之间转移的概率;

(4)观察序列概率矩阵B,B={bj(k)},bj(k)=P[vtat t |qt=sj],1≤j≤N,1≤k≤M,连续型HMM的B通过一个连续的函数得到观察序列与状态的关系,常用的是混合高斯概率密度函数。

(5)初始状态分布概率∏={πi},πi=P{s1=q1},其中1≤i≤N。显然有。

HMM主要可以解决3个基本问题:

1)评估问题即给定一个模型λ={A,B,π}和一组观察序列O=O1,O2,…,OT,计算在此模型下产生该观察序列的概率P(Oλ)。评估问题用前向或后向算法解决。

2)解码问题,即给定一个模型λ={A,B,π}和一组观察序列O=O1,O2,…,OT,求解对应的最大概率的状态序列Q=q1,q2,…,qT。解码问题用Viterbi算法解决。

3)学习问题,即给定观察序列O=O1,O2…,OT,如何调整模型参数A,B,π,使得P(O|λ)最大。学习问题用Baum-Welch算法解决。

2 人脸HMM的识别

2.1 HMM的人脸识别基本方法

对于一张人脸图片来说,自然特征包括头发、额头、眼睛、鼻子和嘴巴等显著的区域,它们的次序从上到下或从左到右保持不变,可以认为这些显著区域隐含着若干个“状态”。这样,可以对人脸图像建立HMM。常见的模型结构有一维的HMM和在此基础上发展的EHMM。模型结构如图1和图2所示。

一维HMM从上到下顺序对人脸图像提取观察序列,每个隐含的状态只能转移到自身或下一个状态。而EHMM将一维的一个状态作为超状态,超状态内部扩展为一个水平方向的子HMM。每一个子HMM的状态都可以转移到自身或者下一个子状态,子HMM的最后一个状态都能转移到超HMM中下一个超状态中。EHMM在水平方向更好地刻画了人脸的信息。

人脸HMM建立好后,需要进行训练,确定人脸模型的各个参数。一个人脸的HMM可以用一幅或多幅图像进行训练。一维HMM的训练主要包括特征提取,初始化模型参数,BaumWelch算法对参数进行迭代的重估等步骤进行训练。训练完成后每个人脸都对应一个HMM。EHMM的训练流程与一维HMM基本相似,只是特征提取时的使用更窄的采样窗口,从左到右也需要一次采样,得到更多的观察序列,并且改用双重Viterbi划分和二维重估式进行训练。

在人脸图像的识别阶段一维HMM与EHMM相同,首先对图像进行采样和特征提取,得到观察序列并代入所有HMM中,依次计算P(O(k)|λn),最后取最大值,m即为识别的结果,识别步骤如下:

(1)对人脸图片窗口进行采样和特征提取。假定人脸图像宽度为W,高度为H,用宽度为W,高度为L的采样窗口对图像从上到下进行采样,两个相邻采样窗之间的重叠部分为P,采样数为,实验证明,采用较大的P能增加识别率,而L则需要取得相对适中,较大或较小都会影响识别结果。

(2)对采样窗口进行和特征提取。较为常用的方法是对采样窗口进行DCT变换,取最大的前n个值,组成n维特征,作为观察序列。

(3)将观察序列代入到每个训练好的人脸HMM中,计算最大相似度P(O(k)|λn)。

(4)计算所有相似度的最大值及所属的HMM,,m即为识别的结果,识别流程如图3所示。

2.2 HMM的人脸识别方法的改进

考虑Viterbi算法,通过递归求出最大相似度,起始状态δ1(i)=πibi1,1≤i≤N,递归情况,2≤t≤T,1≤j≤N,终止状态P=1≤mia≤xN[δT(i)]。Viterbi算法通过上一个最佳路径节点算出下一个最佳路径节点及其概率。识别时判定待识别图像是某个人就等价于求出每个HMM的pl,1≤l≤M,求arglmaxpl即为最相似人脸。再考虑人脸HMM的特点,由于人脸图像的采样总是从上到下的顺序进行的,总可以令π1=1,πi≠1=0,并且由于建立的人脸HMM的状态只能转到下一个状态或者自身,所以状态转移矩阵A的元素aij当i>j或j>i+1有aij=0,且aij>ai+1,j,因此,猜想若观察序列O=O1O2…OT求出arglmaxpl,则与从起始开始的部分序列O=O1O2…,Ot,1<t<T求出的模型l的pl在所有模型的p中依然比较大。反复实验也证明,即使取待识别图片的观察序列的一部分,识别率也不会降低很多。

提出一种改进的识别方法,具体步骤如下:

(1)在得到待识别图片的T个观察序列O后,将O平均分割为n份。

(2)第一次将代入所有m个HMM中计算,得到m个,淘汰最小的m/n个对应的HMM。

(3)第二次,将代入m-m/n个HMM中,同样得到m-m/n个,淘汰掉最小的m/n个对应的HMM。

(4)这样进行n步,每次都带入T/n个观察序列,保存中间结果δ(i),然后根据δ(i)排除最小的m/n个HMM,最后在剩余的m/n中计算Pl=max[δT(i)],求出arglmaxpl,即为识别的结果。

这样不必带入将所有的观察序列都代入每个HMM中,使得识别速度加快。改进的识别流程如图4所示。

3 实验结果与分析

实验使用ORL(Olivetti Research Laboratory)人脸图像库和Yale人脸图像库进行实验。ORL图像库采集了40个人,每个人10张人脸图像,包括了各种角度和表情,共400张图像,每张图像大小为92×112。Yale图像库采集了15个人,每个人11张人脸图像,共165张图像,每张图像大小为100×100。本文使用图像的2D-DCT作为特征,采样窗口大小为10×10,重叠区域大小为8×8,对采样窗口做2D-DCT,取左上角的64个系数,做zigzag排序取前10个作为一个观察向量。整幅图像的所有采样窗口都提取特征后形成一个观察序列。以混合高斯概率密度函数为混合矩阵的密度函数。ORL库中每个人取5张图片作为样本训练EHMM,剩余5张作为测试图片。Yale库每个人取6张图片作为样本训练EHMM,剩余5张作为测试图片。实验中观察序列代入EHMM中的计算次数对比如图5所示。

通过对比可以看出,使用本文方法后,由于对观察序列分割并逐步筛选模型,识别时的计算次数明显减少,并且随n值的增大,计算次数也会相对减少。识别结果如表1所示。

图6所示为以n=3为例的ORL库部分实验结果,其中图像有黑叉的表示识别错误,其余部分为识别正确。实验结果显示本文的方法可以在基本不降低识别率的情况下提高识别速度,识别速度随观察序列划分数n的值增加而增加,由于观察序列的长度限制,在n取值大于5时,识别速度增加不多,识别率也会有所降低。

4 结语

经过许多年的发展,HMM方法用于人脸图像识别领域已经较为成熟,有很多人在模型训练及模型结构方面都提出了改进方法,提高了识别率。本文改进了HMM用于人脸图像的识别方法。通过利用人脸HMM的结构特征和Viterbi算法的特性,将观察向量分割,并在计算相似度时通过中间结果来排除可能性较小的人脸模型。一边识别,一边筛选人脸HMM。经过实验对比,该方法在ORL库和Yale库中都有良好的效果。今后可以结合HMM的模型相关性进行研究,给出更快的查找HMM的方法。

摘要：提出一种改进的基于隐马尔可夫模型的人脸识别方法。利用人脸隐马尔可夫模型的结构特征和Viterbi算法的特点,对特征观察序列进行分割,使用部分序列对所有隐马尔可夫模型递进地计算最大相似度,同时排除相似度最小的隐马尔可夫模型,减少观察序列的计算次数,提高识别效率。实验结果表明,该方法能在不降低识别率的情况下,有效提高识别速度。

关键词：人脸识别,隐马尔可夫模型,观察序列分割

参考文献

[1]Samaria F,Young S.HMM based architecture for face recognition[J].Image and Computer Vision,1994,12(10):537-543.

[2]Nefian.A hidden Markov model-based approch for face detection andrecognition[D].Georgia:Georgia Instituete of Technology,1999.

[3]Nefian M,Hayes.Face recognition using an embedded HMM[C]//IEEE International Conference Audio Video Biometric Based PersonAuthentication,Washington D.C,1999.

[4]Eickeler S,Müller S,Rigoll G.Recognition of JPEG compressed faceimages based on statistical methods[J].Image and Vision Computing,2000,18:279-287.

[5]刘小军.人脸识别技术研究[D].北京:中国科学院电子学研究所,2001.

[6]Li J,Wang J,Zhao Y,et al.Self-adaptive design of hidden Markov models[J].Pattern Recognition Letters,2004,25(2):197-210.

[7]Chien J,Liao C.Maximum confidence hidden Markov modeling for facerecognition[J].Pattern Analysis and Machine Intelligence,2008,30(4):606-616.

[8]Huang S,Yang J,Chang S.Robust face recognition using subface hid-den Markov models[C]//Circuits and Systems(ISCAS),IEEE Inter-national Symposium,2010:1547-1550.

[9]Cai J,Ren H,Yin Y.Non-overlapped sampling based hidden Markovmodel for face recognition[C]//Image and Signal Processing(CISP),3rd International Congress,2010:1901-1904.

隐马尔可夫 篇5

目前常用的协议识别技术主要是基于端口映射表或静态的报文特征来识别网络报文所属的协议类型[1],这样做的依据是大多数操作系统和应用软件都是在假定RFC被严格遵守的情况下编写的。在协议规范公开的同时已经设定好该协议默认使用的通信端口并且假定使用者们都会遵守这些规范。但是近年来,随着网络协议的发展出现了一批新型的协议,包括SIP(Session Initiation Protocol)和P2P(Peer to Peer Protocol)协议等,它们并不采用固定协议端口,而是在协议运动过程中动态地协商端口;此外,目前各种木马、P2P软件为躲避检测都采用了一些特殊的处理方式[2],主要表现在:

(1) 不使用固定通信端口进行通信;

(2) 复用公开端口进行私有协议通信(比如QQ2006版开始实用80端口并且数据报中没有明显特征字串);

(3) 采用已知公开协议的传输工具(比如迅雷采用HTTP传输);

(4) 有些通信业务采用了加密技术,这就使得特有的静态特征无法进行有效的提取。

以上这些特征都给协议的准确识别带来了困难。对于加密后的协议报文识别,某些技术将变得不再适用[3]。本文针对这些问题提出基于隐马尔可夫模型的协议识别技术。实验结果证明,这种技术能有效地解决上述的实际问题,比传统的基于端口映射和静态特征匹配协议识别技术具有较大的优越性。

2 隐马尔可夫模型(HMM)简介

隐马尔可夫模型是一种用参数表示的,用于描述随机过程统计特性的概率模型[4],它是由马尔可夫链[5]演变而来的。这里所说的随机过程,一般都是有限长的随机序列。它可能是一维的观察值序列或编码符号序列,也可以是多维的矢量序列。比如一个语音段(如词、音素或短语)可以用一串特征矢量表示,这就是一个观察矢量序列,如果把这一串矢量逐个地进行矢量量化,每个矢量用一个编码符号代表,这就变成了观察符号序列。不管它是观察矢量序列还是观察符号序列,统称观察序列,记为O=o1o2…oT,它当然是一种随机序列。一个有N个状态(记为S1,S2,…,SN)的HMM是由三元组参数λ={π,A,B}表示的用于描述一种随机序列的统计特性的概率模型[9],其中:

(1) π=[π1,π2,…,πN]为初始分布,用于描述观察序列O在t=1时刻所处状态q1属于模型中各状态的概率分布,即:

undefined

它当然满足:

undefined

(2) A={aij|i,j=1,2,…,N}为状态转移概率矩阵,这里只考虑一阶HMM,当前所处状态qt只与前一时刻所处状态qt-1有关,即:

undefined

它满足:

undefined

(3) B为观察序列O中任一观察(它是随机变量或随机矢量在各状态的观察概率空间中的分布。这个分布有离散型HMM和连续型HMM两类,分别相应于离散和连续,其分布分别为:

在离散HMM情况下,观察序列为符号序列,B为一概率矩阵:

undefined

它满足:

undefined

其中M为编码符号集中符号的总数,在用矢量量化编码时,M就是码书大小。

在连续HMM情况下,观察序列为矢量序列(设维数为D),B就是N个D维的概率密度函数的集合B={bj(O),j=1,2,…,N}

其中O为观察矢量空间中的任一矢量,每一个密度函数都满足归一的条件,即:

undefined

其中Ωj表示第j状态的观察概率空间,它可以是矢量O所在的全空间,也可以是其中的一个子空间或一个区域。以上就是隐马尔可夫模型的完整的定义及说明。从这个定义可以看出,HMM与有限状态的一阶马尔可夫链一样地用初始分布、状态转移概率矩阵描述有限长随机序列的统计特性,但它不同于马尔可夫链由每一观察即可确知当前所处状态,而是由每一观察仅能估算出当前处于各种状态的概率。这就是说,它具有双重随机性,是一种双重随机过程。

3 识别算法

本方法选用包的大小、包的到达时间等对加密不敏感的特征,利用隐马尔可夫模型(HMM)对特征进行建模,然后采用Viterbi分类器进行分类。整个过程如图1所示,分为3个阶段:

(1) 数据采集和预处理;

(2) 特征选择,建模和模型选择;

(3) 实验数据分类和识别器性能评估。

3.1 数据采集和特征选择

对于每个截获的TCP连接,按照每个包到达的时间顺序记录下连接中每个数据包的序列长度和到达时间。将包的到达方向编码到包大小的符号位,因此编码后从服务器到客户端的包大小小于零,而从客户端到服务器端的包大小大于零。有成果表明,对于非交互性协议,到达时间服从指数分布。而交互性的协议并不服从指数分布,其拖尾较长,可能更适合用对数正态分布。在到达时间独立的条件下,包到达时间在不同延迟上的自相关函数会非常接近零,但是自相关函数为零并不意味着一定是独立的。应用层协议对于一定的延迟都表现出明显的自相关特性。有文献研究了包大小的自相关函数,结果表明在一定的延迟上,对于同一次的网络会话,包的大小也是明显相关的,因此包大小也作为构建识别模型时的一个特征。

3.2 HMM建模

图1概括了建模的整个过程。给定一个训练序列的集合,首先构建一个初始模型,在模型中状态链的长度等于训练集中序列的平均长度(以包为单位)。每一步为所有包分配均匀概率的初始参数。

利用Baum-Welch算法迭代寻找使得训练序列模型似然函数最大化的HMM参数。应用聚类算法重复进行上面的过程来对一个给定的协议构建多个HMM,然后将多个HMM合并为一个最终的混合模型。建立各种协议的识别模型是一项重要的工作,图2是给出了用训练数据构建HMM的一般过程。

如图3所示,HMM模型的构建可以用一个从左到右模型来很好的表征,围绕2条长的并行隐式状态链,每条链有TCP连接中的1个状态。每个状态以一定的概率发射1个符号,概率对应于其在链中的位置,这些链中的状态称为“Match”状态,因为其符号发射的概率分布“匹配”于包的一般结构。一般的HMM只有一个单一的“Match”状态链,本方法采用2个“Match”状态链。每个位置处的第二个“Match”状态可以更好地表示TCP连接中的连续包的相关性。由于TCP利用滑动窗和握手机制来获得可靠的数据传输,包的传输方向通常是与前一个包的传输方向非常相关的(正相关或负相关)。因此“Server Match”状态匹配从客户端到服务器端所观察到的数据包。例如,从“Client Match”状态到“Server Match”的转移表示观察到了给定协议下从客户端到服务器的数据传输。

用于描述同一协议的TCP连接中的变化,模型对于链中的每个位置都有2个额外的状态,一个称为“Insert”,用于描述1个或多个额外包“插入”到另外的一个序列。另一个称为“Delete”状态,用于描述在给定位置从序列中删除一个通常的包。实际中,“Insert”状态表示复制包和重新传输,而“Delete”状态说明网络中的包丢失或者被检测器去除。两类状态也可以表示协议栈的高层中有关协议的变化。

3.3 模型修正

为迭代找出模型的合适长度,应用一种启发式的称为“模型修正”的技术。模型修正是基于这样一种思想,即链中所有位置都应该表示一个序列中包的相同部分,“Match”状态应该表示一个给定位置中最典型的特性。同样以训练集中长度等于平均包数目的模型开始,在每次迭代中,构建和训练当前长度的模型,然后检查链中每个位置的4种状态。如果“Insert”状态是最可能的状态,意味着模型将失去训练集中的一些关键特性,这会在由链中给定位置的Match状态表示的特性之前发生。为更好地捕捉到这种特性,将模型的长度增加1,反过来,如果“Delete”状态是最有可能的状态,将当前的长度减小。重复这个过程直到最大的步数或者直到当前的长度不再变化。

3.4 Viterbi分类器

基于模型的分类器将完成的任务是,给定一个观测序列Ο和一个集合C(集合中共有k类,模型为λ=λ1,λ2,…,λk,要找出c∈C中的哪一类,即c=class(O)。第一种分类器较为简单,根据最大似然方法判断属于哪一种协议。就是选择class(O)=arg maxc(O|λc),其中arg maxc表示O中产生最大似然值的类c[7]。第二类分类器跟第一类类似,用到了著名的Viterbi分类器算法,寻找对于一个给定的输出序列O和λ最可能的状态序列。Viterbi算法可以用于找出最可能的状态序列(即Viterbi路径),与之相关的概率为Pviterbi(O,λ)=maxSP(O,S|λ)。给定一个输出序列O,Viterbi分类器对于每个模型λi中的序列找出Viterbi路径,选择产生最优Viterbi路径的模型,数学表达式可以表示为class(O)=arg maxcPviterbi(O,λc)。

3.5 多特征识别

如果将大小和时间信息融合为一个模型则可以进一步提高识别性能,采用矢量量化技术将二维包数据变换为一个符号,从而可以利用统一类型的模型和技术同时处理大小和时间信息。矢量量化技术描述如下:给定每一个包的数据<到达时间,大小>,对时间进行对数变换以减小其动态范围,为时间和大小分配相等的权值,将<到达时间的对数,大小>归一化到<-1,+1>区间。

所建立的HMM模型对于不同的包要按照其传输方向区别处理。可以将数据包分为2类:客户端到服务器和服务器到客户端。然后对每个矢量集独立利用k均值聚类算法,对于集合中的数据包找出一个代表性的矢量集或者码字。对于一个有N个码字的码书的量化器,随机选择k=N/2个矢量作为聚类的中心,然后在每次迭代中,对于每个<到达时间、大小>矢量,找出其最近的中心,为相应的聚类分配矢量。在每次迭代结束后重新计算每个中心,作为当前分配给聚类的所有矢量的均值。当从一个聚类移动到另一个聚类的矢量的一部分低于一定的门限时停止迭代。

对于2个包矢量集合聚类完成之后,将中心矢量的列表作为量化器的码书。为量化一个包的矢量表示,找出离矢量最近的码字,将包编码为码书中给定码字的索引。在完成对于训练序列的矢量量化之后,就可以像上面一样构建离散的HMM,利用码字数目作为HMM的输出符号表。在对测试序列进行分类之前,同样需要依据构建序列码书的方式对其进行量化。

4 实验结果

本实验所采用的数据均来自于国防科技大学校园主干网,由实验室的高速网络采包器采集。对TRACE的详细描述请见表1(所指的流均为双向流)。TRACE1被用来对模型进行训练,以得出最符合的模型参数。TRACE2被用来对该模型的识别效果进行验证。

利用上述算法建模,然后用数据TRACE1对模型参数进行训练,得到最佳的识别模型。在把数据TRACE2加密后,用传统的基于端口映射和静态特征匹配的方法进行识别,其准确率均在50%以下,而用该HMM模型技术进行识别,识别结果见表2。

5 结 语

针对传统协议识别技术的局限性,提出了一种基于隐马尔可夫模型的协议识别技术,并对如何建立准确的HMM识别模型给出了详细的阐述。该技术不仅对传统的通信协议具有较高的识别准确率,而且对于新的网络应用协议如SIP,P2P协议以及未知协议等仍能进行准确的识别。由于该技术选用包的大小、传输方向等对于加密不敏感的特征进行建模,使它能有效地识别加密条件下的网络应用协议。与传统的识别技术相比,具有较好的可用性与有效性。

摘要：目前的协议识别技术主要是基于端口映射或静态报文特征匹配的。随着网络协议的发展,一些新的协议采用动态端口进行通信或不具有明显的静态报文特征,且部分协议采用了加密技术。这使得传统的识别技术准确率大幅下降。针对传统协议识别技术的局限性,这里提出一种基于隐马尔可夫模型(Hidden Markov Model,HMM)的协议识别技术。它是一种基于统计特性的识别方法,选用对于加密不敏感的特征如包的大小、达到时间等来实现协议的识别。实验结果证明,与传统识别技术相比,它能有效地提高协议识别的准确率,并能用于加密条件下的协议识别。

关键词：隐马尔可夫模型,协议识别,特征选择,Viterbi分类器

参考文献

[1]Charls Writht,Fabian Monrose.HMM Profiles for NetworkTraffic Classification[J].VizSEC/DMSEC′04:Proceedingsof the 2004 ACM Workshop on Visualization and DataMining for Computer Security,2004:9-15.

[2]Sebasion Zander,Thuy Nguyen.Automated Traffic Classi-fied Application Identification Using Machine Lerarning[A].In:Proceedings of the IEEE Conference on LocalComputer Networks 30th Anniversary[C].2005.

[3]Matthew Gebski,Alex Penev,Raymond K Wong.ProtocolIdentification of Encrypted Network Traffic[A].In:Pro-ceedings of the 2006 IEEE/WIC/ACM/International Con-ference on Web Intelligence,2006 IEEE[C].2006

[4]Anonymized.HMM Profiles for Network Traffic Classifica-tion(Extended Abstract)[A].In:Proceedings of the 2004ACM Workshop on Visualization and Data Mining for Com-puter Security[C].2004:9-15.

[5]Ye N.A Markov Chain Model of Temporal Behavior for A-nomaly Detection[A].In:Proceedings of the IEEE Symposi-um on Security and Privacy[C].2002.

[6]陈亮,龚俭,徐选.应用层协议识别算法综述[J].计算机科学,2007,34(7):73-75.

[7]Baum L E,Petrie T,Soules G.A Maximization of TechniqueOccurring in the Statistical Analysis of Probabilistic Func-tions of Markov Chains[J].Annals of Mathematical Statis-tics,1970,41(1):164-171.

[8]Sebanstian Zander,Thuy Nguyen,Grenville Armitage.Auto-mated Traffic Classification and Application Identificationusing Machine Learning[A].In:Proceedings of the IEEEConference on Local Computer Networks 30th Anniversary[C].2005.

[9]Schliep A,Schonhuth A,Steinhoff C.Using Hidden MarkovModels to Analyze Gene Expression Time Course Data[J].In:Bioioformatics,2003,19(1):255-263.

[10]陈亮,龚俭,徐选.基于特征串的应用层协议识别[J].计算机工程与应用,2006,42(24):16-19,86.

[11]易克初,田斌,付强.语音信号处理[M].北京:国防工业出版社,2000.

隐马尔可夫 篇6

关键词：风险评估,隐马尔可夫模型(HMM),蚁群算法,Snort系统

随着网络信息的发展,网络为人们提供更为方便、高效的服务功能,但网络安全问题也随之而来。如何正确评估网络系统的安全状况,是解决网络安全问题的前提。网络安全动态风险评估是对特定网络系统的安全状况,以及系统信息资产的价值进行定性或定量的评估[1]。本文介绍了一种基于改进隐马尔可夫模型的网络动态风险评估方法,该方法将改进后的蚁群算法引入到隐马尔可夫模型的训练中,与传统使用Baum-Welch算法的训练相比较,提高了隐马尔可夫模型的识别能力,同时使隐马尔可夫模型能有效地解决风险评估的实时性问题。

1 建立网络的HMM模型

隐马尔可夫模型是一种统计模型,可以用参数λ=(S,V,π,Trans,Obs)来简单的表示。使用隐马尔可夫模型必须有效解决三个方面的问题:评估、解码和学习(或者训练)[2]。

为了检测网络是否存在风险,首先建立正常流量的HMM模型。据Moore等人的研究得出:大多数攻击使用TCP包(94%),然后是UDP包(2%)和ICMP包(2%)[3]。因此,考虑分别对TCP包、UDP包和ICMP包建模,描述正常情况下网络流量的统计特征,然后用它来检测网络流量。对TCP标志位组合、UDP报头信息、ICMP报头信息进行处理,产生相应的观测值。通过分析和统计麻省理工学院试验室第一周和第三周不含攻击的数据,得到观测值的个数S和状态数V=S(当V粗略等于S时易于模型收敛[4])。平均初始概率π的计算公式为:

$\pi {}_i={\rm N}{}_i/{\rm N}(1)$

式中:分母N表示各个种类数据包个数;分子Ni表示处于状态Si的数据包的个数。平均状态转移矩阵Trans的计算公式为:

$\text{Τ}\text{r}\text{a}\text{n}\text{s}{}_i={\rm N}{}_{ij}/{\rm N}{}_j(2)$

式中:分母Nj表示转移到状态Sj的数据包个数;分子Nij表示从状态Si转移到状态Sj的数据包个数[5]。

2 基于改进蚁群算法的HMM模型的训练

隐马尔可夫模型的训练就是确定一组HMM参数,使之尽可能反映正常状态下网络流量的实际特征。HMM的参数,即状态数、观测符号数、平均转移概率矩阵以及平均初始概率。

2.1 训练算法

使用林肯实验室的第一周和第三周的训练数据,从中提取出所需要的属性,根据以上提出的输出值计算方法,形成观测符号序列。根据前面得到的HMM模型的初始参数λ=(S,V,π,Trans,Obs)对隐马尔可夫模型进行训练。利用HMM的前向算法,计算观察序列的概率值对数,使用改进的蚁群算法[6]对HMM的参数进行重新估计,从而得到更为优化的参数λ1。具体操作步骤如下:

(1) 建立连续搜索空间X,X是HMM参数S,V,π的合集。假设蚂蚁由蚁巢出发,随机选择一个猎狩点xs,设当前猎狩点的最优点为xb,令xb=xs。

(2) 初始化蚂蚁的搜索半径L,蚂蚁在此搜索半径上进行局部搜索。

(3) 以当前狩猎点为输入点,以搜索半径L为输入半径,生成候选搜索点集。

(4) 蚂蚁随机选择候选点x,利用前向-后向算法计算出所对应的输出值F(x),如果在限定次数k内存在x,使得F(x)>F(xb),则令xb= x,否则放弃搜索,直接跳到步骤(6)。

(5) 将k重置,继续执行步骤(4),直至搜索完候选点集。

(6) 如果xb=xs,扩大搜索半径L,跳转到步骤(3)继续搜索;否则令xs=xb,并执行增加信息素的操作,然后跳转到步骤(2)。

(7) 如果蚂蚁在规定的最大忍耐次数n内仍无法找到比狩猎点更优的点,则重新选择狩猎点。

(8) 根据最后得到的最优解得出优化的参数λ1。

2.2 阈值确定

模型参数确定以后,需要找出一个合适的阈值作为检测网络是否存在风险的标准。该模型的阈值可以通过以下方法确定。将观察值序列分成长度为L的若干段序列,每一个观测值序列按照HMM的前向或后向算法都可以得到一个输出值[2],取所有值中最小的输出值作为阈值δ。实验阶段,对于输出值小于阈值δ的数据包定义为异常数据。其具体算法为:

step 1:输入观察序列。

step 2:取长度为L的子序列。

step 3:调用前向算法计算该子序列概率值的对数作为输出值。

step 4:检查是否到达观察序列末尾,是则跳转到step 5,否则跳转到step 2。

step 5:取最小的输出值作为阈值δ。

3 实验及结果

测试时采用麻省理工学院林肯实验室下载的真实入侵数据进行测试,选择KDD CUP1999数据集来确定概率转移矩阵,其提供的第一周和第三周作为训练数据,第四周和第五周作为测试数据,以此来测试系统性能。

具体算法如下:

(1) 读取训练好的HMM模型参数;

(2) 输入观察序列;

(3) 取长度为L的子序列;

(4) 调用前向算法计算该子序列的概率值对数log Prob;

(5) 比较log Prob是否比阈值小,是则跳到步骤(6),否则跳到步骤(3);

(6) 进入专家评测进行判断,若为攻击则响应,否则为正常,再次进入隐马尔可夫模型学习模块训练参数。

通过实验测试,并与Snort进行比较,发现本系统对网络流量比较敏感,检测率较高,如表1,图1所示。

分析图1,由于Land,Ping of death攻击是拒绝服务类型的攻击,攻击原理是利用协议的漏洞,因此本系统与Snort系统都能够安全地检测出来;Syn flood,Ping flood,Smurf这三种攻击拒绝服务攻击,由于本系统对网络流量的变化比较敏感,因此检测率较高,而Snort系统的检测原理是采用模式匹配技术,故检测率差了一些。

4 结 论

本系统提出了一种使用改进蚁群算法训练隐马尔

可夫模型的网络入侵检测方法,使训练后的模型具有更高的识别能力,对各种攻击具有较高的检测率,可以检测到各种攻击,在检测的全面性和准确性方面有良好的结果,对网络入侵检测具有一定的价值。

参考文献

[1]陈光.信息系统信息安全风险管理方法研究[D].长沙:国防科学技术大学,2006.

[2]徐从福.隐马尔可夫模型[D].杭州:浙江大学人工智能研究所,2005.

[3]MOORE D,VOELKER G,Savage S.Inferring Internet de-nial-of-service activity[C]//Proceeding of the 10th USE-NIX Security Symposium.San Diego:University of Califor-nia,2000(1):9-22.

[4]WARENDER C,FORREST S,PEARLMUTTER B.De-tecting intrusions using systemcalls:altermative data mode[C]//Proceedings of 1999 IEEE Symposium on ComputerSecurity and Privacy.Oakland,California:IEEE ComputerSociety Press,1999:133-145.

[5]韩景灵.基于协议的隐马尔可夫网络入侵检测系统研究[D].太原:山西大学,2007.

[6]汪庆淼,鞠时光,秦剑锋.基于改进蚁群算法的HMM参数估计[J].江南大学学报,2009,8(6):707-710.

[7]朱嘉瑜,高鹰.基于改进粒子群算法的隐马尔可夫模型训练[J].计算机工程与设计,2010,31(1):157-160.

[8]刘建华,侯红霞,张雪峰,等.基于业务的电信网风险评估方法研究[J].现代电子技术,2008,31(17):66-69.

隐马尔可夫 篇7

高斯混合模型 (GMM) [2]是神经学中广泛使用的一种统计学模型, GMM不仅与脑部MR图像的分段常数性质一致, 而且具有较低的计算复杂度。GMM的模型参数可以利用期望最大化 (EM) 算法根据最大似然 (ML) 准则来估计, 然而, 基于EM的ML估计具有过度拟合和容易限于局部最优解的缺点。为了克服这些缺点, 使用几种全局优化技术来替代EM算法, 例如, 文献[3]在似然估计中结合了遗传算法, 提出了GA-EM算法。此外, 当先验知识可用时, 最大后验概率 (MAP) 估计是ML估计的一种常见替代方法。文献[4]提出一种MAP-MRF框架来求解图像分割问题, 通过将体素类标签建模为马尔可夫随机场 (MRF) 来表示体素空间依赖性的先验。文献[5]提出一种基于全局随机搜索的推理方法, 即马尔可夫链蒙特卡尔 (Markov chain monte carl, MCMC) 推理, 用来替代确定性程序。文献[6]受免疫机制启发, 提出一种克隆选择算法 (clonal selection algorithm, CSA) , 基于克隆选择理论, 选择能够识别抗原的抗体来进行繁殖, 繁殖的细胞会通过一个亲和力成熟过程来改进它们对抗原的亲和力, CSA模仿对抗原刺激免疫应答机制来实现全局最优。

将CSA和MCMC技术融合到隐马尔可夫随机场 (hidden Markov random field, HMRF) 模型估计中, 提出一种用于脑部MR图像分割的HMRF-CSA算法。首先, 通过MCMC方法近似最优标签配置, 然后, 由CSA算法估计HMRF模型参数。用全局随机优化技术替代确定性搜索程序, 以此提高分割算法的鲁棒性, 同时, 将MR图像建模为分段常数图像的乘法分量, 根据MCMC推断方法获得的中间分割结果来评估图像的不均匀性。通过仿真实验, 将本文HMRF-CSA算法与现有的GA-EM方法、可变形共同分割 (D-C) 算法、SPM软件包中的统一分割算法和FMRIB软件库 (FSL) 上的HMRF-EM分割算法进行比较, 结果表明该算法具有更好的分割精度。

1 相关技术

1.1 图像不均匀模式

由图像采集的不完善所导致的图像不均匀性, 或称偏场或强度非均匀性 (INU) [7]是MR图像分析的难点之一。设定y={yi;i=1, 2, …, N}表示一副脑部MR图像, 其中yi表示在体素i处的强度, N表示体素的数目, 未知偏场B={bi;i=1, 2, …, N}通常建模为y的乘法分量, 如下式所示

式 (1) 中, 是理想图像, 是附加的高斯白噪声。由于图像中偏场B变化缓慢, 所以可将它定义为在整个图像域上的一个平滑函数。采用正交多项式{Wj:j=1, 2, …, NOP}作为偏置函数来近似偏场[8]

式 (2) 中, φ={φj:j=1, 2, …, NOP}表示组合系数, NOP= (D+1) (D+2) /2是多项式的数目, D是多项式的度。

1.2 统计学模型

假设体素强度y={yj;j=1, 2, …, N}符合GMM;从有先验概率πk的高斯分布N (μkΣk) 中独立采样每个强度值yj, 观察图像的似然, 计算式如下:

通过最大化上述似然函数来估计最优GMM参数, 确定参数后, 利用贝叶斯分类器对每个体素进行分类, 以此求解脑部图像分割问题[7]。

为了将空间约束融入到这个模型中, 本文应用MRF到模型类标签x={xj;j=1, 2, …, N}中, 根据Hammersley-Clifford理论, 类标签p (x) 的先验联合分布符合Gibbs分布。在MAP-MRF框架下, 图像分割等价于通过最大化其后验概率寻找最优配置x*

式 (4) 中, Θ={μk, Σk;k=1, 2, …, K}表示模型参数, p (y|x;Θ) 是图像似然, p (x) 是空间先验。

本文将图像强度y当作在相同图像点阵中另一个随机场建模的模型, 然后将代表潜类标签的MRFx变成HMRF。在这个模型中, 将图像分割问题制定为配置x和参数Θ的最大联合概率

式 (4) 中后验与式 (5) 中联合概率之间的差是惩罚项p (Θ|y, x) , 用于检查模型参数是否与配置x给出的观察值一致。

2 HMRF-CSA算法提出

HMRF模型主要用来估计式 (5) 中的最优类标签和模型参数 (x, Θ) , 估计过程可划分成两个相互依赖的优化步骤:搜索最优配置x*和学习最匹配模型参数Θ*。使用下式三个步骤的迭代程序来实现HMRF模型估计

式 (6) 中, f (., .) 是基于观察y和分割结果x纠正偏场的函数, t∈{1, 2, …, Tmax}表示当前迭代数目。在每次迭代中, 首先采用MCMC方法实现MRF-MAP估计, 在近似的分割结果下估计偏场, 然后利用CSA学习HMRF模型参数, 当达到最大迭代数目或分割结果变成稳态时迭代停止。

2.1 MCMC体素分类

上述迭代步骤中第一步是通过MRF-MAP近似寻找最优配置x*, 使用MCMC方法求解这种优化问题, 根据式 (4) , 对于给定任意特定配置x, 假设yj相互独立且符合基于参数Θk={μk, Σk}的多元高斯分布, 则似然为

MRFx的联合分布可表示为Gibbs函数[9],

式 (8) 中, Z是规范化常量, Vc (x) 表示派系c的潜力, C是根据邻域系统确定的所有派系的集合, T是温度参数。本文使用Potts模型表示派系潜力, 运用式 (7) 和式 (8) 到式 (4) , 并对其进行负对数变换, 得到

根据模拟退火MCMC方法, 为温度参数T定义一个冷却进度表,

式 (10) 中, i=1, 2, …, I表示MCMC算法迭代的数目, C是冷却因子, 本文设置T (0) =4, C=0.97。若给定一幅脑部MR图像y和标签x (0) 的初始配置, 则可计算出模型参数。定义用来表示从x (i) 随机移动的跳跃密度Q (.|x (i) ) 符合高斯分布, 每次迭代中, 从建议密度Q (x* (i+1) |x (i) ) 提取一个候选x* (i+1) , 从均匀分布u (0, 1) 提取一个随机序列, 计算每个体素j的接受率

如果uj<αj, 接受模拟xj (i+1) =xj* (i+1) , 否则拒绝它并保持类标签与上一次迭代xj (i+1) =xj (i) 相同, 当达到最大迭代次数时停止, 如算法1所示。

算法I:体素分类的MCMC采样

2.2 偏场校正

在利用MCMC体素分类之后, 可以获得分割结果x*和最小能量E={Ekj, xj=k, j∈S}。归一化后验概率n={nkj;j=1, 2, …, N, k=1, 2, …, K}作为软分割结果

根据理想MR图像的分段常数性质, 定义软分割与对应平均μk的积作为存储的图像

本文使用奇异值分解 (SVD) 求解下列最小二乘拟合问题, 以此估计偏场。

式 (14) 中, ./表示点对点划分, 根据估计的组合系数, 获得偏场

偏场损坏的图像可恢复如下:

2.3 CSA进行参数估计

第三步是通过最大化后验概率p (Θ|y (t) , x (t) ) 来学习当前图像强度y (t) 和配置x (t) 给出的最优参数

式 (17) 中, p (Θ) 是参数的先验概率, 这个先验指的是基于马尔可夫性质信息p (Θkj) =p (xj=k|kj) 的体素, 可以通过MRF能量计算得到, 定义它作为这些项的混合来平衡参数的收敛和多样性, 对于每个体素j∈S

式 (18) 中, v是平衡常量, Πkj=πk表示分体素全球先验。给定任意具体参数集Θ, 即可计算式 (18) 中所示优化问题的目标函数。为了实现全局最优, 采用CSA[10]求解该问题, 以群体方式模拟所有可能参数。CSA是一种进化优化算法, 通过迭代生成一群编码抗体来寻找全局最优解。本文中, 抗体群np设为100, 定义每个抗体为一个候选参数集Θ, 将有特定抗原的抗体Θk的亲和力定义为后验似然p (Θ|y, x) , 迭代优化过程由下列六个主要步骤组成:

第一步:评估每个抗体的亲和力, 根据其亲和力按降序排列所有抗体;

第二步:从当前群体中选择Ns个抗体, 克隆它们形成克隆群。对于亲和力排序为j的抗体, 定义其克隆的数目正比于其亲和力排序, 如式 (19) 所示。

式 (19) 中, β是常量, 用来控制克隆率, round (.) 用来将实数变换到与其最接近的整数;

第三步:分别对概率为phm和pre的克隆群运用超突变和受体编辑操作。超突变是在动态范围±10%内随机改变抗体的值, 目的是局部搜索最优解。受体编辑是在动态范围±100%内随机改变抗体, 实现全局搜索;

第四步:评估克隆群中抗体的亲和力, 根据其亲和力按降序排列;

第五步:选择克隆群中排名靠前的抗体代替记忆细胞集中较低亲和力的40%抗体, 保证记忆细胞集保存迄今为止获得的最优解, 以便最高亲和力的抗体按代递增;

第六步:用随机生成的抗体代替剩余集中具有最低亲和力的10%抗体, 对新群体引入多样性。

重复迭代这个过程直到达到最大迭代数目, 如图1所示。

2.4 总结

给定K-平均算法产生的初始分割结果, HMRF-CSA算法迭代执行基于MCMC的体素分类、偏场校正和基于CSA的模型参数估计, 直到算法收敛。一旦达到收敛, 则获得最终分割结果、偏场和模型参数。HMRF-CSA算法的主要步骤见算法II。

算法II:HMRF-CSA脑部图像分割算法

3 实验结果

本文从Brain Web数据集[11]获取仿真TI加权脑部MR图像, 比较提出的HMRF-CSA算法与现有的e HMRF算法、GAMIXTURE包中GA-EM算法、D-C算法、FSL包中的经典HMRF-EM算法和SPM包中的统一分割程序。Brain Web数据集提供的一组仿真脑部图像, 这些图像具有各种INU和噪声级别的解剖模型仿真, 每个仿真研究的维度为181×217×181, 体素大小为1 mm×1 mm×1 mm。

图2分别显示了仿真图像中具备40%INU和7%噪声的第88个横切片, 偏长矫正图像, 估计的偏场, 使用六种算法获得的分割结果和地面实况组织图。其中图2 (a) 表示仿真图像的第88个横切片 (7%噪声和40%INU) ; (b) 表示INU校正图像; (c) 估计的INU; (d) 表示HMRF-EM算法的结果; (e) 表示D-C算法的结果; (f) 表示SPM算法的结果; (g) 表示GA-EM算法的结果; (h) 表示e HMRF算法的结果; (i) 表示HMRF-CSA算法的结果; (j) 表示地面实况。可以看出, 本文算法产生的分割结果比其他算法产生的结果更接近地面实况。

接下来, 在两组仿真MR图像上对这些算法进行进一步比较。第一组MR图像包含有20%INU和噪声级别范围从1%到7%的四个图像, 使用骰子相似度系数 (DSC) [12]定量评估每个脑部组织类型分类的性能。

式 (20) 中, Vs (k) 是分割结果中脑部组织类k的体, Vg (k) 是在地面实况上对应的体, |V|代表体V中体素的数目。通过正确分类的脑部体素百分比来计算分割精度, 并评估整体精度。图3表示六种算法获得的分割精度。

从图3可以看出, 在大部分仿真图像中, 本文算法在划分每个脑组织和分类整个脑部体方面都具有较高的精度。而且, 随着噪声和INU级别的增加, 提出算法的精度下降幅度比其他算法低, 这表明本文算法具有较强的抵制噪声和INU影响的能力。

第二个测试组包含有40%INU和噪声级别范围从1%到7%的四个图像, 六种算法获得的分割精度如图4所示。

从图4可以看出, 本文算法能在高噪声和INU级别下保持良好分割性能。

4 讨论

4.1 参数设置

本文提出的HMRF-CSA算法中, 有三组需要近似的参数, 包括MCMC推断、INU估计和基于CSA的参数近似。在INU近似中, 以正交多项式的阶来权衡考虑近似精度和计算复杂度, 由于INU变化非常慢, 对于INU近似, 10个三阶多项式已经足够。式 (19) 中权重参数v决定MRF先验, 较大的v能使MRF的作用更大, 另一方面, 小v则更支持GMM先验。CSA本身需要很多参数, 文献[13]对此进行了详细讨论。本文使用CSA程序的经验参数设置:群体大小Np=100、记忆集大小Nm=0.3Np、选定抗体的数目Ns=0.5Np、克隆率常量β=0.5, 超突变概率phm=0.8、受体编辑概率pre=0.1和最大的代Nt=20。

4.2 计算复杂度

计算机程序的性能与许多因素有关, 包括计算机处理能力、数据表示、编程语言和编码实现等[14]。本文评估了HMRF-CSA算法的计算复杂度, 本文算法在每次迭代中顺序执行MCMC推断、偏场估计和基于CSA的参数估计。设定对于有N个体素的一副图像, MCMC推断的计算复杂度为O (N) ;偏场估计仅进行一些矩阵计算;基于CSA的参数估计的复杂度为O (Np+NcK) , 其中Np表示群体大小, Nc表示总克隆数目。提出的迭代分割算法的迭代次数达到wmax后停止, 其线性整体计算复杂度O (N+Np+NcK) 。需要注意的是, MCMC方法的主要缺点是需要大量仿真图[15], 然而, 由于CSA为MCMC方法配置了一个良好的开始状态, 所以本文算法不需要许多仿真图。同时, MCMC方法的输出使CSA在有限代数之后成熟, 因此, 尽管本文HMRF-CSA算法涉及耗时的MCMC和CSA程序, 然而, 其计算复杂度只稍微高于传统分割方法。

5 结论

提出了HMRF-CSA脑部MR图像分割算法, 在基于HMRF模型分割中结合了CSA和MCMC, 本文算法能够有效的用于基于HMRF模型估计的图像分割问题。在仿真脑部MR图像上进行实验, 将本文算法与GA-EM算法、D-C算法、SPM和FSL软件包算法进行比较, 实验表明该算法获得了更好的分割精度。

隐马尔可夫 篇8

在我们日常交流的过程中,头部会经常做一些无意识的运动,而这些在聋哑人交流的过程中会更加明显。因为手语属于视觉语言,在其表达过程中的头部动作不仅表达一定的心情、感情、性格等多种信息,而且蕴涵一定的语义信息。故而头部运动对手语表达和手语理解都有着重要的意义。

Hideyuki Takagi等人分析了不同角度的头部以及眼睛的运动轨迹,提出了头部以及眼睛的数学运动模型。

C.Vogler等人提出了一种从视频中获取头部运动信息的方法,并在此基础之上,针对美国手语中的头部运动规律进行了分析,将头部运动按照具体的运动方式进行了分类。其研究点停留在运动规律的分析上,并没有对头部运动进行计算机模拟。

Atsushi Nakano等人通过研究提出了基于交谈和整体行为的分层行为合成技术。其侧重点在于坐姿的协调性。

Carlos Busso等人通过对视频信息分析,提取韵律信息以及头部运动数据,提出了韵律驱动的不同情绪下人交流是头部刚体运动模型。其研究点在于根据语音信息建立头部相应的HMMs同时他们研究了不同情绪下的头部运动的合成。

本文分析了中国手语表达过程中的头部运动规律,利用隐马尔科夫模型对头动建模,实现了手语动画中基于HMMs的头部运动合成。本文第2节提出了运动包装盒的概念并介绍了数据处理的方法;第3节介绍了HMMs的建立,以及动画合成;最后对本文进行总结与展望。

2 运动数据采集及处理

本文试验数据是利用MotionAnalysis公司的Hawk系统采集,该系统包括22个帧率为120FPS的摄像头,采集身体主要标记点(如颈,肩等)在进行人际交流时的运动数据,如图1。

演员所穿紧身衣上共有38个标记点,来自采集设备的数据表示标记点在特定时刻相对系统坐标系中心的位置信息,采集数据格式如图2。

数据采集完成以后,头部的旋转角度,以及手部绕肩关节的旋转角度需要计算出来,因为本文利用手部以及头部的旋转角度信息研究手语表达过程中这两个表达通道间的关联模式。采集数据是每个标记点相对系统坐标系中心位的位置信息,所以首先需要将位置数据转化为绕XYZ轴的旋转角度数据。数据采集过程中,演员帽子上有四个标记点分别位于头部的前、后、左、右四个位置,本文取这四个点位置数据的平均值作为头部的位置数据,通过下面公式可以计算出头部绕颈关节标记点的旋转角度,同时我们取手掌上一标记点来计算手部绕父关节的旋转角度。公式如下:

n1为t1时刻某点相对于其旋转点的向量,n2为t2时刻该点相对于其旋转点的向量,dot为两向量点积

为了找出头部运动与手部运动之间的关系,本文采用相关性分析对运动数据进行处理。“相关性”这一概念来自于统计学理论,主要在于揭示数据之间的关联性。相关性系数是描述关联关系程度和方向的统计量,本文采用传统的相关性分析方法,公式如下

其中X,Y为头部和手部的旋转角度,μ为头部和手部旋转角度的均值,E是数学期望

然而通过对采样率为120ps的运动捕获设备采集十分钟的数据进行相关性分析我们发现,头部运动与手部运动的相关性并不大,相关系数仅为0.1-0.2,实际观察发现,当人的手势运动在胸前一个很小的范围内时,头部运动并不是非常明显,并且时常没有运动。为此本文提出了运动包装盒的概念,即位于虚拟人胸前的立方体,当手势运动位于此立方体内时,头部运动没有或者不明显。根据多次实验经验我们可以将包装盒的顶部与肩齐,高度为大臂的一半,宽度距为小臂的长度。

在定义运动包装盒的前提下,首先根据手部的位置判断手部是否在运动包装盒内部,如果在内部则删除该数据,否则取手部与头部的旋转角度来进行相关性计算,此时发现,当手部运动超出运动包装盒时,头部运动数据与头部运动数据的相关性系数(0.73)大于指定阈值(0.6),由此可以确定头部运动和手部的运动之间是存在运动协同机制的。

3 基于隐马尔科夫模型的头动合成

3.1 隐马尔科夫模型

HMMs是在Markov链的基础之上发展起来的。由于实际问题比Markov链模型所描述的更为复杂,观察到的事件并不是与状态一一对应,而是通过一组概率分布相联系,这样的模型就称为HMMs,一个HMM可由下列参数描述:。

1)N:模型中Markov链状态数目。记N个状态为θ1,.....,θN,记t时刻Markov链所处状态为qt显然qt∈(θ1,....,θN)。

2)M:每状态对应的可能观察值数目。记M个观察值为V1,……,VM,记t时刻的观察到的观察值为Qt,其中Qt∈(Q1,....,QM)。

3)π:初始状态概率矢量π=(π1,……,πn),其中πi=P(q1=θi),1<=i<=n.

4)A:状态转移概率矩阵,

5)B:观察值概率矩阵,

HMM的几个重要参数如下:状态数N,观察值个数M,观察值序列的长度T。

本文采用头部的运动状态作为HMM的状态,所以首先采用K均值聚类的方法对头部运动状态进行聚类。头部状态的聚类数目即HMM的状态数N。K均值聚类的算法如下:

1)首选我们手工挑选N个具有代表性的头部动作,作为初始码本。

2)按照最近邻方法,以码字为中心,将训练集中的所有矢量分类,形成N个区域。

3)重新计算每个区域新的中心作为该区域的新码字。计算新的平均失真率。

4)跳回2)重新执行,直到完成预先设定的训练次数或者平均失真率小于某个事先设定的阈值。

本文中,手势数据在预处理中被量化为256个码字,在HMM中量化后的码字被作为观察值来输入的。HMM的状态数N取为8,取头部状态聚类中数据量较多的8类。对每一个类通过HTK开发包训练出一条隐马尔科夫链。

通过训练,我们可以得到头部每一种状态相对应的隐马尔科夫模型,在后面的动画合成过程中,我们可以将手势数据作为参数输入,然后通过查找HMMs可以得到相应的头部运动数据。

3.2 头部运动合成

当合成头部运动的时候,手势相对于肩关节的运动角度p(xi,yi,zi)作为参数输入HMMs,而HMMs的输出序列列V=(V1,V2,...,Vn是最相关的头部运动序列,Vi是头部的旋转角度。

此时两个相邻聚类间运动角度的离散性,往往在视觉效果上存在突变,从而造成不真实的感受,甚至在同一个聚类中的角度也会存在跳跃,如图4所示。因此序列P(vi)不能直接应用于头部运动的合成,必须对序列P(vi)进行插值获得更为平滑的运动效果。一种简单的方法是采用线性插值算法对每个欧拉角进行插值,然而这却不是一种最优的方法,因为,运动本身时急时缓,而且受其他因素影响,譬如“Gimbal lock”[8]。然而Shoemake等人提出了一种球面插值算法,这种方法的基本思想是把欧拉角转换四元数,并在此空间内对关键帧进行插值。本文采用四元数三次球面插值算法,四元数三次球面插值算法,squad,它是建立在四元数线性插值(slerp)的基础之上的。对于两个四元数q0,q1,四元数线性插值算法(slerp)定义如下:,其中q0,q1为源和目标四元数,t为插值参数,通过在区间[0,1]间采样实现从源到目标的过渡,θ为两个四元数之间的实际夹角。对于四个四元数,四元数三次球面插值算法定义如下:

图5中的红线为插值算法计算后的头部运动角度序列,经过插值角度趋于平滑过渡,画面的突变感大大降低,图6是对应插值后数据的动画序列。

4 结论

本文分析了手语表达过程中头部运动与手部运动两个表达通道间的关联模式,在对手部数据及头部数据进行分析的基础上建立了头部运动与手部运动之间的隐马尔科夫模型,并实现了基于HMMs的头部运动合成,该方法简单实用,并大大提高了手语合成系统的真实性,增加了手语合成系统的真实感。然而现实生活中聋哑人交流时,头部的运动也会受心情,性格等因素影响,本文中没有涉及心理部分对头部运动的影响。

摘要：手语是一种靠动作、视觉进行交流的特殊语言,在手语表达过程中,头部运动蕴涵语义以及情感信息。本文分析了手语表达中手势动作和头部动作的运动相关性,利用隐马尔可夫模型(HMMs)为每一个离散的头部动作表示建模,基于一阶马尔科夫模型和插值算法生成平滑的头动动画。

关键词：手语,头部动画,HMMs

参考文献

[1]Hideyuki Takagi,Movement Models of Head and Eyes for Computer Graphics,Electronics and Communications in Japan,Part3,Vol.82,No.1,1999,Translated from Denshi Joho Tsushin Gakkai Ronbunshi,Vol.J80-A,No.8,Au-gust1997,pp.1304-1311.

[2]C.Vogler and S.Glodenstein.Analysis of Facial Expressions in American Sign Language.Fourth International Workshop on Autonomous Agents.2000.

[3]Atsushi Nakano,Kenta Shioiri,Junichi Hoshino,Synthesizing Pose,Unconscious Movement,and Gesture for Mental Behavior Expression of Interactive Characters ACE,June14-16,2006.

[4]Cassell,J.,Vilhjálmsson,H.,Bickmore,T.:BEAT:the Behavior Expression Animation Toolkit,Pro-ceedings of SIGGRAPH'01,pp.477-486(2001).

[5]Stone.M.,DeCarlo,D.,Oh,I.,Rodriguez,C.,Stere,A.,Lees,A.and Bregler,C.:Speaking with hands:creating animated conversational characters from recordings of human performance,ACM Transactions on Graphics23(3),pp.506-513(2004).

[6]Carlos Busso,Zhigang Deng,Michael Grimm,Rigid Head Motion in Expressive Speech Animation:Analysis and Synthesis.IEEE TRANSACTIONS ON AUDIO,SPEECH,AND LANGUAGE PRO-CESSING,VOL.15,NO.3,MARCH2007.

[7]K.G.Munhall,J.A.Jones,D.E.Callan,T.Kuratate,and E.Bateson,“Visual prosody and speech intelligibility:Head movement improves auditory speech perception,”Psychol.Sci.,vol.15,no.2,pp.133–137,Feb.2004.

[8]K.Shoemake.Animating rotation with quaternion curves.Computer Graphics(Proceedings of SIG-GRAPH85),19(3):245–254,July1985.