基于二维隐马模型的车行轨迹分类
周珊，王小捷**
作者简介：周珊(1987-),女,自然语言处理 通信联系人：王小捷（1969-），男，教授，自然语言处理. E-mail: xjwang@bupt.edu.cn
（北京邮电大学智能科学与技术中心,北京,100876）
5
摘要：本文利用二维隐马可夫模型对车行轨迹分类。针对车行轨迹的独特性，提出了适用的二维特征提取方案，与以往轨迹分类中所采用的特征提取方案相比，能明显的提升了轨迹分类性能。此外，本文分析了隐马可夫模型的拓扑结构对分类结果的影响，以及不同拓扑结构下隐状态的抽象含义与车行轨迹的物理性质之间的映射关系。
关键词：自然语言处理；轨迹分类；行为模式；二维隐马模型 10
 0 引言
近年来，车行轨迹的分类逐渐受到学者们的关注。这是因为，无论是从理论研究的角度还是从实际应用的角度，车行轨迹的研究都具有非常重要的意义。一方面，轨迹作为视觉和语言双模态连接的媒介，是动态视觉信息和语言信息转换的重要途径，轨迹分类的研究为双模态连接的大框架起到支撑作用；另一方面，车辆交通在人们的日常生活，车行轨迹分类的30 研究使得车辆视频的文本检索变得可行，同时也能对非法行车的监控提供帮助。
AbderrahmaneBoubezoul等人提出了基于Support Vectors Machines（SVM）的轨迹分类方案[1]，车行轨迹中蕴含了丰富的时空信息，虽然SVM模型是非常优秀的分类工具，但它本身却不具备表征时序信息的能力。潘奇明等人提出了基于隐马可夫模型（HMMs）的运动目标轨迹分类方案[2]，然而文中将同形轨迹即视为一类，没有对轨迹的方向性进行区分，这35 超出了HMMs模型的分类能力，同时文中以运动物体的位置信息为特征，容易造成数据稀疏，导致准确率低下。基于手势轨迹的研究中，Hyeon-Kyu Lee在其研究中以反应轨迹斜率信息的弧度值为特征[3]，较好的实现了手势轨迹的分类，但是车行轨迹具备其特殊性，轨迹的斜率信息并不足以表征车行轨迹的特点。
HMMs是一种成熟的表征时序信息的模型，因此本文采用此模型进行车行轨迹的分类。40 针对车行轨迹的特殊性，同时考虑车辆实时车道的变化和车辆轨迹的斜率信息，使得行车轨迹分类具有较高的准确率。
 1 HMMs基础理论
隐马尔可夫模型（Hidden Markov Models，HMMs）[4]作为一种包含时序信息的统计分析模型，被广泛的应用在分类任务中，现已成功地用于语音识别，文字识别[5]，行为识别[6]45 等领域。
隐马可夫模型是一个双层的随机过程，如图1所示，隐状态序列（X序列）是马尔可夫过程，观察值序列（Y序列）是一般随机过程。隐马科夫模型可以用五元组(Q,O,π,A,B)表示，包括两个状态集合（Q,O）和三个概率矩阵(π,A,B)。 50
1. 隐状态集合Q = {x1,x2…xN}
2. 观察值集合O={y1,y2…yM}
3. 隐状态转移概率矩阵A={aij}，其中aij = P{ q(t+1) = xj | qt = xi} 1 ≤i,j≤N
4. 发射概率矩阵B={bj(k)}，表示每个隐状态j55
条件下出现相应观察值k的概率。bi(k) = P{ot = yk |qt = Si}
5. 初始概率矩阵π，其中πi = P{q1=xi}。
一般的，可以用λ=(π,A,B)三元组来简洁的表示一个N状态的隐马尔可夫模型。
HMMs可以用来解决三类问题。
1. 评估：对给定的模型λ，计算观测序列O产生的概率P(O|λ)。它能解决分类问题。 60
2. 解码：对给定的模型λ，计算观测序列O对应的最佳隐状态序列。它能进行对隐状态物理含义的探究。
3. 学习：对给定的观测序列O，计算得到最佳的模型λ，使得P(O|λ)具有最大值。它能实现训练得到模型参数。
2 基于二维隐马可夫模型的车行轨迹分类 65
HMMs运用于K分类时，每个类Ci对应一个模型λi。训练时，利用训练数据计算出每个类Ci对应的模型参数λi；测试时，然后在训练好的K个模型{λ1,，λ2…λK}上，计算新数据在每个模型下的似然，似然最大的模型λi所对应的类Ci，即为新数据被分的类。
基于HMMs的车行轨迹分类的流程[7]如图2所示，分为训练过程和分类过程，两个过程之前，都需要先进行预处理过程，将视频输入编码成的HMMs能接受的观察值。 70
预处理过程：
1. 从车行视频中提取原始车行轨迹
2. 对车行轨迹进行特征提取，并编码为HMMs所对应的观察值
训练过程：
1. 确定K种车行方式 75
2. 对K个类，通过各自的观察值，训练与该类对应的模型参数λi
测试过程：
1. 计算每条观察值在K个HMMs模型下的似然
2. 选择似然最大的HMMs模型所对应的类Ci，作为分类结果。
原始轨迹视频跟踪特征选择、编码观察值HMMs训练视频原始轨迹视频跟踪特征选择、编码观察值待分类视频参数学习相似概率分类结果80 图2 HMMs分类过程示意图
Fig. 2 Flow of how to use HMMs in classification
图1 HMMs的双重随机过程
Fig. 1 Random processes of HMMs
x1x2x3y3y1y2
 因此基于HMMs的车行轨迹分类，有三个重要的任务点：
1. 特征提取
2. HMMs的拓扑结构； 85
3. 二维HMMs分类模型；
本章剩余部分将分别对以上部分进行说明。
2.1 特征提取
原始位置（POS）[2]、速度方向（SD）[3]是轨迹分类中得到广泛应用的两种特征。其中，原始位置以采样点的坐标为特征，从而构建连续的特征空间；而速度方向则通过相邻两个采90 样点的位置计算速度矢量，取此矢量的角度值。
这两种特征的优缺点对于我们的任务来说都是很明显的：原始的位置特征保留了所有的信息，但它将构造庞大的特征空间，并因此带来数据稀疏问题；速度方向能够用较小的特征数量拟合轨迹形状，但它忽略了一些重要的位置信息（比如，初始位置）。车道（LANE）是车行轨迹相比其他轨迹具备的独特信息，对于5*5车道，编95 码如图[]中所示。
因此，我们选择速度方向作为基础特征，为弥补它的不足，还使用了一个附加的特征，PD，即以初始车道为基准，当前车道所在的方向。
这一方向被简化为9个值，如图3所示 100
利用视频捕捉技术[8]获取的原始轨迹T，可以表示为目标运动体位置在时间轴上的序列。T = d1d2d3….dN,其中di=<xi,yi>，xi,yi分别为第i个采样点在x轴和y轴的投影值。
对每条得到采样点坐标的轨迹，我们有PD+SD的综合特征序列F=<SD1,PD1><SD2,PD2><SD3,PD3>….<SDn,PDn>，其中，105 SDi表示第i个采样点处SD的编码，PDi表示第i个采样点处PD的编码。
其中，SDi = artctan((yi - yi-1) / (xi - xi-1))，(令d0 = d1)
PDi与初始车道位置和当前车道位置有关，取值如图3所示。
2.2 HMMs的拓扑结构 110
HMMs是双层的随机过程，有显层（观测层）和隐层（状态层）。其最重要的特点是隐层为马尔科夫过程。HMMs的结构包括两个方面，隐层中隐状态的数目，和隐状态的连接方式即HMMs的拓扑结构。
HMMs中的隐状态是对观察值的抽象表达，隐状态的数目决定了这种表达的抽象程度，一般认为，特征变化越复杂，表达特征需要的隐状态数目越多。随着隐状态数目的增加，运115 算复杂度的相应的增加，所以选择合适的隐状态数目，对于车行轨迹的分类很重要。
隐马模型的隐状态的拓扑结构主要有两种，从左至右连接和全连接，其中从左至右连接又可依据连接的跳跃数分为从左至右k连接。在轨迹的分类任务中，[6]使用了全连接HMMs，[3]使用了从左至右连接HMMs，[2]使用了从左至右2连接HMMs。 0 1
2 3 4 5 6
7 8 9
10
11
12
13
14 15 16
17 18 19 20 21
22 23 24
图3 PD编码示意图
Fig. 3 Codings of PD
注：在5*5车道中，当初始状态位于编码为12的车道位置上，当前的车道位置相对于初始车道位置的9种方向特征（左，左上，左下，上，中，下，右，右上，右下）。
 1234 a 1234 b 1243 c 120 图4 HMMs的拓扑结构 Fig. 4 topology of HMMs 注：图4为隐状态数为4时的HMMs拓扑结构图。a为从左至右连接HMMs,b为从左至右2连接HMMs，c为全连接HMMs。 125 从左至右连接的HMMs一旦到达了末状态，就只能驻留在该状态。为了利用从左至右连接HMMs的特性，又能在即使到达末状态后，也能有机会跳转。本文另外定义了两种拓扑结构，环k连接和双向k连接，以实验结果为依据，为车行轨迹的分类选取最合适的HMMs拓扑结果。 1234 a 1234 b 130 图5 HMMs的拓扑结构 Fig. 5 topology of HMMs 注：图5为隐状态数为4时的HMMs拓扑结构图。a为环2连接HMMs，b为双向2连接HMMs。
2.3 二维HMMs分类模型 135
使用Baum-Welch算法[4]时，通过每类的观察值学习到该类对应的HMMs参数。对该算法改进后，能解决观察值为二维向量时HMMs的参数训练[9]问题。Baum-Welch 算法是一类EM算法，随机初始化HMMs参数，通过E步骤和M步骤的不断迭代，使最终参数值逼近最优值。车行轨迹分类问题中，为设定的K个轨迹类，通过每个类的观察值，利用Baum-Welch算法，学习到K个类对应的模型参数{λ1,，λ2…λK}。 140 评估时，对于新的观察值O，分别利用前向算法[4]计算它与每个模型的似然，似然最大的类被视为分类结果。
3 实验结果及分析
实验中，定义了六种车行方式：左转、右转、左后转、右后转、直行、换道。东南西北个方向的145 六种车行方式，构成了24个轨迹类.图6中示例了以西为起点的六种车行方式的轨迹，实验数据中如无特殊说明，分类准确率均是对24类车行轨迹的分类结果。
为降低视频跟踪任务对实验结果的影响，能真150 实的反应分类模型对车行轨迹分类的效果，我们利用adobe的视频制作软件AE，制作了一系列车行视频，
图6 车行轨迹示意
Fig. 6 vehicle trajectories
 真实的模拟了复杂的车行情境，视频的持续时间分布在2至20秒之间，采样频率为25帧/s，图像序列的尺寸为720*576。
车行视频的总数据量是3000条，利用[8]中的算法从视频中获取车行的原始轨迹数据。155 为保证实验结果的可靠性，采用十倍交叉验证，即将总数据分为10份，依次取其中的9份做为训练数据，1份作为测试数据，然后取平均值。
3.1 不同特征下的车行轨迹分类结果
原始位置（POS）[2]、速度方向（SD）[3]是轨迹分类中得到广泛应用的两种特征。原始位置特征构造了庞大的特征空间，并因此带来数据稀疏问题；速度方向特征能够用较小的特160 征数量拟合轨迹形状，但它忽略了一些重要的位置信息（比如，初始位置）。
PD特征是以初始车道为基准，当前车道所在的方向。PD特征反应了车道的变化，SD特征拟合车行轨迹的形状，<SD,PD>从两个必要角度表征了车行轨迹。
<SD,PD>、<SD,LANE>、<SD> 、<POS>、<SD,POS>五组特征提取方案进行十倍交叉验证后的准确率如表1所示。 165
学术论文网Tag：代写论文 代写代发论文 职称论文发表 代写代发