基于HMM的交叉口交通事件预测研究

周 君,程 琳,周凌云,褚昭明

(1.淮阴工学院交通学院,江苏淮安223003；2.东南大学交通学院,南京210096)

基于HMM的交叉口交通事件预测研究

周 君*1,程 琳2,周凌云1,褚昭明2

(1.淮阴工学院交通学院,江苏淮安223003；2.东南大学交通学院,南京210096)

交叉口是一个交通事故多发区,除了交叉口设计复杂外,更重要的是交叉口车辆行驶情况比较杂乱,使得交叉口交通冲突的检测难度增加.本文以淮安市淮海南路与解放路交叉口为例,根据车辆运行与相位配时总结在该四相位控制的交叉口具有冲突的两辆车的相对运动情况,在车辆跟踪的基础上对具有冲突的车辆进行运动矢量量化,采用HMM(隐马尔可夫模型)对该交叉口的交通冲突进行分类,并通过实验验证该算法能对正常交通下的车辆运行状态进行冲突分类.通过冲突的检测可以提前预测发生在交叉口处的交通事故(如碰撞、追尾、突然停车等)和危险状态.

智能交通;事件预测;隐马尔可夫模型;交叉口;交通冲突

1 引 言

近年来,我国城市道路交通事故的发生率居高不下,特别是城市交叉口处每年有大量的事故发生.这是由于车辆在交叉口处行驶比较自由,不受方向限制,多个方向行驶的车辆将会在交叉口处发生冲突,导致交通事件的发生.在交叉口交通事件处理期间,救护车和警车占据道路时间比较长,这些原因使得交叉口交通事件检测难度增加[1].目前国外已有科研机构致力于开展交叉路口的碰撞检测仿真实验,采用数据挖掘等技术,想找出一种适合各种交叉口的交通流模型,以便对比交叉路口的交通流状况来预测交通事件的发生[2]. Cuchira et.al[3]采用交通规则的推理去反映在一条单行线直道的简单交通状况.Jung et.al[4]从交通图像中跟踪车辆得到更精确的交通检测信息. Oikawa et.al[5]从视频序列中探测交通拥堵.国内目前对于交叉口的交通状况研究主要还处于设计交通控制器和埋设检测线圈或直接利用高速路上的交通流模型预测事件.本文在目前城市交叉口的交通事件检测比较薄弱的基础上,研究并提出一套适合我国城市交叉口的交通冲突检测算法.

2 交叉口处具有冲突的两辆车的相对运动情况分析

图1为淮安市淮海南路与解放路交叉口的整个平面图,该交叉口为四相位控制的交叉口.根据车辆运行与相位配时,总结在四相位控制的交叉口具有冲突的两辆车的相对运动情况分析,如图2所示.图2(a)表示南北或东西方向直行的车辆；图2 (b)表示南北或东西方向左转的车辆；图2(c)表示两相邻方向一方直行车辆与另一方右转车辆行驶冲突情况；图2(d)表示南北或东西方向一方的左转车辆与另一方的右转车辆行驶情况.冲突示意图如图3所示.

图1 交叉口平面图Fig 1 The plane figure of intersection

图2 具有冲突的两辆车相对运动(假设车辆2在车辆1的前面)Fig 2 The relative motion of two vehicle with conflict(suppose vehicle 2 is before vehicle 1)

图3 冲突示意图Fig 3 The schematic diagram of conflict

3 特征提取

3.1 相对运动矢量的特征提取

本文提出的交通冲突检测算法适用于各种几何形状的交叉口,不用考虑摄像头的安装角度,文中以四相位控制的交叉口为例.在研究中,车辆的运行方式是多样的,在视频每一帧图像里,冲突有可能随时随地发生.因此,随着交叉口几何依赖性增加,HMM冲突检测所需的训练数据也将增加.为了避免这种情况的发生,该算法尽量不使用图像强度自身特征,因为图像强度依赖于车辆的颜色,而所处理的图像是灰度图像.算法先对车辆运动矢量的特征进行提取[6-8],具体过程如图4和图5所示.

图4 相对运动矢量的特征提取Fig 4 Feature extracion about relative motion vector

图5 相对位置的特征提取Fig 5 Feature extraction about relative location

(1)估计两辆车之间的运动矢量差,即车辆1的运动矢量减去车辆2的运动矢量.

(2)旋转两车的运动矢量到不同的位置,使运动矢量差V→d沿图4中虚线指针逆时针旋转到实线指针位置,矢量差V→d到矢量V→r形成圆弧分布在以地理坐标为划分界限的四个区之间.

(3)运动矢量差V→r除以两车之间的距离表示两车相距的远近程度,最短距离通过测量两车距离最近的块所得,因为离得最近的块更容易发生冲突,如图4中3个不同半径大小的圆弧代表两车的远近程度.

所以图2中所示的两车相对冲突点,车辆之间的位置及运动矢量关系很重要.称具有冲突的车辆之间的位置叫“相对位置”.图2(a)中车辆1和车辆2之间的相对运动矢量和图2(b)中是一样的,但是发生冲突的情况是不一样的.图2(c)和图2 (d)中虽然都具有右转的运动矢量,但是发生冲突情况也是不一样的.假设车辆2位于车辆1的后面,则车辆2相对车辆1的位置为“60”,如果车辆2位于车辆1的左边,则车辆2相对车辆1的位置为“40”,依此类推相对位置如图5所示.

3.2 相对位置的特征提取

尽管运动矢量基本一致,但冲突点会因为相对位置的不同而不同.因此,为了区分图2中四种冲突情况,有必要考虑来自相对运动矢量和相对位置的特征.然后结合来自相对运动矢量的观察序号和来自相对位置的观察序号,作为总的观察序号.这里来自相对运动矢量的观察序号是从1到12,小于20,如图4所示.总的观察序号是运动矢量的观察序号结合相对位置的观察序号,并且为20的倍数.因此每一个总的观察序号都代表独一无二的位置.

4 基于隐马尔可夫模型的交叉口交通冲突识别

4.1 HMM理论

对于一个随机事件,有一个观察值序列:Y= Y1,Y2,…,YT,该事件隐含着一个状态序列:X= X1,X2,…,XT,如图6所示.一个隐马尔可夫模型(HMM)是由一个五元组描述的:λ=(X,Y,A, B,π).

4.2 模型定义

根据图6所示的HMM的理论图,城市交叉口的观察序列的识别可以用HMM来描述.模型中存在有限个隐藏状态,这些状态代表抽象数量(如直行、左转和右转等4个方向的交通运行的组合)与之相对应的具有相似性的观察值的分布概率.本文采用简单的从左至右的HMM模型进行事件检测,其转移过程如图7所示.

图6 HMM结构图Fig 6 The diagram of HMM

图7 从左至右的HMMFig 7 Left to right HMM

T=图像序列的长度；

X={X1,...,XT}:状态的有限集合；

Y={Y1,...,YT}:观察值的有限集合；

A={aij},aij=P(Xt=Sj|Xt-1=Si):状态转移概率矩阵；

B={bik},bik=P(Yt=Oi|Xt=Si):观察值概率分布矩阵；

π={πi},πi=P(X1=Si):初始状态概率分布；

bik:状态i时,输出观察值k的概率.算法中定义前向变量α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到最后的概率,βt(i)= P(Yt-1,Yt-2,…,YT,Xt=Si/λ),1≤t≤T-1.

4.3 算法实现

4.3.1 算法流程

HMM算法实现的过程就是对时间序列图像转变成符号或数字序列输出的过程,其具体操作过程如图8所示.

图8 HMM处理流程图Fig 8 The flow chart of HMM

4.3.2 前向算法

前向算法是在时间步t,得到t之前的所有观察序列,且时间步t的状态是Si这一事件的概率,记为αt(i)=P(Y1,...,Yt,Xt=Si|λ).

算法过程:

Step1

Step2

Step3

4.3.3 Baum-Welch算法

Step1初始化πi,aij,bik；

Step2EM步骤；

E步骤——计算ξt(i,j)和γt(i):

给定HMM和观察序列,ξt(i,j)为在时间t位于状态i,时间t+1位于状态j的概率为

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

M步骤——用E步骤所得的期望值,重新估计模型λ=(πi,aij,bik),得到新模型

Step3循环设计i=i+1；重复EM步骤,直到πi,aij,bik收敛.

5 交通事件的预测

5.1 碰撞事件的预测

模型λ=f(A,B,π)对每一个被识别的事件进行分类.在交叉口处通过HMM算法对上述的4种冲突[pas-00]、[pas-11]、[pas-02]、[pas-12]进行分类,然后对冲突中的碰撞事件进行准确识别.这是因为涉及碰撞事件的车辆的观察序列与正常情形不一样,该系统通过HMM算法从正常情况下对获得的碰撞事件观察序列加以区分并进行碰撞事件检测.结合交叉口冲突情况下的总的观察序列分析,发现典型的碰撞事件的观察序列为61、62、63和27、28、29.这也意味着此时两车相距很近.当观察序列为“60”或“20”时,代表碰撞发生的瞬间,当观察序列变成69、68、67或23、22、21时,代表碰撞发生后的反应.

例如:车辆2追尾撞上车辆1,车辆2相对于车辆1的观察序列以[tdm-0]表示,它的观察序列期待值为61、62、63、60、69、68、67；车辆1相对于车辆2的观察序列以[tdm-1]表示,它的观察序列期待值为27、28、29、20、23、22、21,具体表示如下所示.这样,此类序列被定义为TDM-01.

[tdm-0]61 62 63 60 60 60 69 68 67

[tdm-1]27 28 29 20 20 20 23 22 21

5.2 跟驰事件的预测

然而,当车辆出现跟驰现象时,这时的观察序列跟发生碰撞时的观察序列相似,当相对运动的观察序列为“9”和“3”结尾时,代表危险情况,这是因为此时相对运动矢量比较大,两辆车的距离很近.观察序列“7”、“8”、“9”的出现取决于具有冲突的两辆车的相对运动矢量和相对距离.所以很难仅仅通过观察序列来区分碰撞和跟驰现象,前者属于事件,后者属于正常情况.对于这种无法用观察序列来区分碰撞和跟驰现象的情形,可以利用交通规则来区分.

第1条:观察序列被定义为TDM-01的具有冲突的2辆车发生碰撞；

第2条:当有1辆车由于熄火等正常原因停在交叉口某处时,从此处开始,如果具有冲突的另一辆车通过交叉口,可以判断为跟驰现象；如果具有冲突的另一辆车停在交叉口内不能行驶时,则可判断为碰撞；

第3条:如果检测到其它车辆绕过静止的车辆时,这很可能发生了不正常事件.绕道可以通过第4节中的轨迹线来判断.

通过上述分析,对发生的交通事故分成3种类型.

第一种:碰撞事故；

第二种:追尾；

第三种:突然停车.

6 实验结果及分析

6.1 交通冲突的识别

为了验证HMM的观察序列的有效性,本文拍摄了3组交叉口视频图像,每组视频时间为3 min,速度为10帧/s,其每组视频里都有直行、左转和右转车辆.实验将对这3组视频图像分别进行试验,即对直行[pas-0]、左转[pas-1]、右转[pas-2]交通进行识别.每一组观察序列由12个观察值组成,其观察值为具有冲突的两辆车的特征值,实验观察序列值如表1所示.

表1 观察序列值Table 1 Observed sequence value

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

结合上述3种观察序列,直行[pas-0]、左转[pas-1]、右转[pas-2],对图2中的4种冲突分类如下:

[pas-00]图2(a):表示直行与直行冲突；

[pas-11]图2(b):表示左转与左转冲突；

[pas-02]图2(c):表示直行与右转冲突；

[pas-12]图2(d):表示左转与右转冲突.

为了验证HMM模型对4种冲突的识别效果,本文采用实际交通视频对交叉口的交通事件检测方法进行验证.交通视频的采集地点为淮安市淮海南路与解放路十字信号交叉口.此交叉口由两条主路组成,为四相位控制的交叉口.

图9中4幅图分别展现了通过HMM算法对交叉口大量具有冲突的车辆,结合它们的观察序列分类成[pas-00]、[pas-11]、[pas-02]、[pas-12]四种冲突.图(a)表示由南向北标号为25的直行车辆与由北向南标号为23的直行车辆被检测为[pas-00]类冲突；图(b)表示标号为26的左转车辆与对向标号为27的左转车辆被检测为[pas-11]类冲突；图(c)表示标号为29的直行车辆与相邻右转标号为27的车辆被检测为[pas-02]类冲突；图(d)表示标号为11的左转车辆与对向标号为9的右转车辆被检测为[pas-12]类冲突.

6.2 交通事件预测

由于在交叉口发生交通事故的数据比较少,难以拍摄到发生交通事故的视频.所以本文所采用的视频文件只是直行与右转冲突的一个特例,如图10所示为算法检测到的跟驰碰撞事件.该事件是通过对具有冲突的两辆车的观察序列进行分类而被识别的.此序列被定义为TDM-01,然而仅仅从序列难以判断此交通事故为碰撞,由于此段视频时间短,没有具有其它冲突的车辆.

这时需要根据交通规则对图10进行事件识别,算法成功检测出一例发生在标号为21的车辆与标号为22的车辆之间的交通事件.事件检测步骤为:(1)算法检测到具有冲突的两辆车的观察序列,并判断该观察序列属于TDM-01类；(2)算法检测到具有冲突的两辆车停了一小会；(3)算法检测出有其它车辆绕过停止的车辆继续行驶,最终算法判断标号为21的车辆与标号为22的车辆将会发生跟驰碰撞事件.

图9 四种冲突的检测结果Fig 9 Recognition results of pas-00,pas-11,pas-02 and pas-12

图10 跟驰事件Fig 10 The event of car following

根据算法的这些检测原则,图9(d)中标号为9的车辆与标号为11的车辆虽然满足前两项,但是由于该两辆车周围没有其它车辆绕行,所以不满足第三项,这两辆车将不会发生跟驰碰撞事件.

7 研究结论

本文以淮安市淮海南路与解放路交叉口为例,分析了交叉口事件检测研究现状以及交叉口处具有冲突的两辆车的相对运动情况,并以提高事件检测率,缓解交通拥挤,减少交通事故为目的提出了一种基于HMM的交通事件预测算法.本文的研究结论:

(1)提出的事件检测算法适用于各种几何形状的交叉口,文中以四相位控制的交叉口为例,找出在四相位控制的交叉口具有冲突的两辆车的相对运动类型；

(2)算法结合来自相对运动矢量的观察序号和来自相对位置的观察序号采用HMM模型对具有冲突的两辆车分类,并通过实验成功检测出文中提到的四种冲突；

(3)HMM模型能成功预测潜在的交通事故,如碰撞,也能对正常的停车进行事故排除.

[1] Veeraraghavan H,Masoud O,Papanikolopoulos N P. Computer vision algorithms for intersection monitoring [J].IntelligentTransportationSystems,IEEE Transactions on,2003,4(2):78-89.

[2] Kamijo S,Matsushita Y,Ikeuchi K,et al.Traffic monitoring and accident detection at intersections[J]. Intelligent Transportation Systems,IEEE Transactions on,2000,1(2):108-118.

[3] Cucchiara R,Piccardi M,Mello P.Image analysis and rule-based reasoning for a traffic monitoring system[J]. Intelligent Transportation Systems,IEEE Transactions on,2000,1(2):119-130.

[4] Jung Y,Lee K,Ho Y.Content-based event retrieval using semantic scene interpretation for automated traffic surveillance[J].Intelligent Transportation Systems, IEEE Transactions on,2001,2(3):151-163.

[5] Oikawa K,Kaneko Y,Matano M.Study of abnormal incident detection aimed at automatic wide-Area traffic flowmonitoring[C]//WorldCongressonITS, Washington D C:IEEE,2002:767-770.

[6] Xie D,Hu W,Tan T,et al.A multi-object tracking systemforsurveillancevideoanalysis[C]// InternationalConferenceonPatternRecognition, Cambridge,United Kingdom:IEEE,2004:767-770.

[7] Zhang Y,Brady M,Smith S.Segmentation of brain Mr Images through a hidden Markov random field model andtheexpectation-maximizationalgorithm[J]. Medical Imaging,IEEE Transactions on,2001,20 (1):45-57.

[8] Salim F D,Loke S W,Rakotonirainy A,et al. Collisionpatternmodelingandreal-timecollision detection at road intersections[J].Proceeding of IEEE ITSC,2007,9:161-166.

Traffic Incident Prediction on Intersections Based on HMM

ZHOU Jun1,CHENG Lin2,ZHOU Ling-yun1,CHU Zhao-ming2
(1.Faculty of Transportation Engineering,Huaiyin Institute of Technology,Huai'an 223003,Jiangsu,China；2.School of Transportation,Southeast University,Nanjing 210096,China)

The intersection is an area where many accidents occur.Reasons for accidents are due to complicated intersection designs and the congested travel conditions.For these reasons,traffic incident detection is more complicated.This paper uses the intersections of Huaihai South Road and Jiefang Road as an example.According to the vehicle operation and phase timing,the situations of two vehicle's relative movement on four phase intersections are summarized.The motion vectors of the conflicting vehicle are quantized on the basis of vehicle tracking.Then,the HMM is used to classify the traffic conflicts of the intersection.Finally,numerical experiments verify that the algorithm is able to classify the conflict when the traffic is normal.Furthermore,the algorithm can forecast the traffic accidents(such as bumping,tandem, and stop)which occurred in the intersection.

intelligenttransportation；incidentdetection；hiddenMarkovmodel；intersection；traffic conflict

U491

A

U491

A

1009-6744(2013)06-0052-08

2013-05-02

2013-06-05录用日期:2013-06-13

国家自然科学基金(51078085).

周君(1980-),女,湖南南县人,博士.

*通讯作者:joujou1980@163.com