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

(1.淮陰工學(xué)院交通學(xué)院,江蘇淮安223003；2.東南大學(xué)交通學(xué)院,南京210096)

基于HMM的交叉口交通事件預(yù)測研究

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

(1.淮陰工學(xué)院交通學(xué)院,江蘇淮安223003；2.東南大學(xué)交通學(xué)院,南京210096)

交叉口是一個(gè)交通事故多發(fā)區(qū),除了交叉口設(shè)計(jì)復(fù)雜外,更重要的是交叉口車輛行駛情況比較雜亂,使得交叉口交通沖突的檢測難度增加.本文以淮安市淮海南路與解放路交叉口為例,根據(jù)車輛運(yùn)行與相位配時(shí)總結(jié)在該四相位控制的交叉口具有沖突的兩輛車的相對運(yùn)動(dòng)情況,在車輛跟蹤的基礎(chǔ)上對具有沖突的車輛進(jìn)行運(yùn)動(dòng)矢量量化,采用HMM(隱馬爾可夫模型)對該交叉口的交通沖突進(jìn)行分類,并通過實(shí)驗(yàn)驗(yàn)證該算法能對正常交通下的車輛運(yùn)行狀態(tài)進(jìn)行沖突分類.通過沖突的檢測可以提前預(yù)測發(fā)生在交叉口處的交通事故(如碰撞、追尾、突然停車等)和危險(xiǎn)狀態(tài).

智能交通;事件預(yù)測;隱馬爾可夫模型;交叉口;交通沖突

1 引 言

近年來,我國城市道路交通事故的發(fā)生率居高不下,特別是城市交叉口處每年有大量的事故發(fā)生.這是由于車輛在交叉口處行駛比較自由,不受方向限制,多個(gè)方向行駛的車輛將會(huì)在交叉口處發(fā)生沖突,導(dǎo)致交通事件的發(fā)生.在交叉口交通事件處理期間,救護(hù)車和警車占據(jù)道路時(shí)間比較長,這些原因使得交叉口交通事件檢測難度增加[1].目前國外已有科研機(jī)構(gòu)致力于開展交叉路口的碰撞檢測仿真實(shí)驗(yàn),采用數(shù)據(jù)挖掘等技術(shù),想找出一種適合各種交叉口的交通流模型,以便對比交叉路口的交通流狀況來預(yù)測交通事件的發(fā)生[2]. Cuchira et.al[3]采用交通規(guī)則的推理去反映在一條單行線直道的簡單交通狀況.Jung et.al[4]從交通圖像中跟蹤車輛得到更精確的交通檢測信息. Oikawa et.al[5]從視頻序列中探測交通擁堵.國內(nèi)目前對于交叉口的交通狀況研究主要還處于設(shè)計(jì)交通控制器和埋設(shè)檢測線圈或直接利用高速路上的交通流模型預(yù)測事件.本文在目前城市交叉口的交通事件檢測比較薄弱的基礎(chǔ)上,研究并提出一套適合我國城市交叉口的交通沖突檢測算法.

2 交叉口處具有沖突的兩輛車的相對運(yùn)動(dòng)情況分析

圖1為淮安市淮海南路與解放路交叉口的整個(gè)平面圖,該交叉口為四相位控制的交叉口.根據(jù)車輛運(yùn)行與相位配時(shí),總結(jié)在四相位控制的交叉口具有沖突的兩輛車的相對運(yùn)動(dòng)情況分析,如圖2所示.圖2(a)表示南北或東西方向直行的車輛；圖2 (b)表示南北或東西方向左轉(zhuǎn)的車輛；圖2(c)表示兩相鄰方向一方直行車輛與另一方右轉(zhuǎn)車輛行駛沖突情況；圖2(d)表示南北或東西方向一方的左轉(zhuǎn)車輛與另一方的右轉(zhuǎn)車輛行駛情況.沖突示意圖如圖3所示.

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

圖2 具有沖突的兩輛車相對運(yùn)動(dòng)(假設(shè)車輛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 相對運(yùn)動(dòng)矢量的特征提取

本文提出的交通沖突檢測算法適用于各種幾何形狀的交叉口,不用考慮攝像頭的安裝角度,文中以四相位控制的交叉口為例.在研究中,車輛的運(yùn)行方式是多樣的,在視頻每一幀圖像里,沖突有可能隨時(shí)隨地發(fā)生.因此,隨著交叉口幾何依賴性增加,HMM沖突檢測所需的訓(xùn)練數(shù)據(jù)也將增加.為了避免這種情況的發(fā)生,該算法盡量不使用圖像強(qiáng)度自身特征,因?yàn)閳D像強(qiáng)度依賴于車輛的顏色,而所處理的圖像是灰度圖像.算法先對車輛運(yùn)動(dòng)矢量的特征進(jìn)行提取[6-8],具體過程如圖4和圖5所示.

圖4 相對運(yùn)動(dòng)矢量的特征提取Fig 4 Feature extracion about relative motion vector

圖5 相對位置的特征提取Fig 5 Feature extraction about relative location

(1)估計(jì)兩輛車之間的運(yùn)動(dòng)矢量差,即車輛1的運(yùn)動(dòng)矢量減去車輛2的運(yùn)動(dòng)矢量.

(2)旋轉(zhuǎn)兩車的運(yùn)動(dòng)矢量到不同的位置,使運(yùn)動(dòng)矢量差V→d沿圖4中虛線指針逆時(shí)針旋轉(zhuǎn)到實(shí)線指針位置,矢量差V→d到矢量V→r形成圓弧分布在以地理坐標(biāo)為劃分界限的四個(gè)區(qū)之間.

(3)運(yùn)動(dòng)矢量差V→r除以兩車之間的距離表示兩車相距的遠(yuǎn)近程度,最短距離通過測量兩車距離最近的塊所得,因?yàn)殡x得最近的塊更容易發(fā)生沖突,如圖4中3個(gè)不同半徑大小的圓弧代表兩車的遠(yuǎn)近程度.

所以圖2中所示的兩車相對沖突點(diǎn),車輛之間的位置及運(yùn)動(dòng)矢量關(guān)系很重要.稱具有沖突的車輛之間的位置叫“相對位置”.圖2(a)中車輛1和車輛2之間的相對運(yùn)動(dòng)矢量和圖2(b)中是一樣的,但是發(fā)生沖突的情況是不一樣的.圖2(c)和圖2 (d)中雖然都具有右轉(zhuǎn)的運(yùn)動(dòng)矢量,但是發(fā)生沖突情況也是不一樣的.假設(shè)車輛2位于車輛1的后面,則車輛2相對車輛1的位置為“60”,如果車輛2位于車輛1的左邊,則車輛2相對車輛1的位置為“40”,依此類推相對位置如圖5所示.

3.2 相對位置的特征提取

盡管運(yùn)動(dòng)矢量基本一致,但沖突點(diǎn)會(huì)因?yàn)橄鄬ξ恢玫牟煌煌?因此,為了區(qū)分圖2中四種沖突情況,有必要考慮來自相對運(yùn)動(dòng)矢量和相對位置的特征.然后結(jié)合來自相對運(yùn)動(dòng)矢量的觀察序號和來自相對位置的觀察序號,作為總的觀察序號.這里來自相對運(yùn)動(dòng)矢量的觀察序號是從1到12,小于20,如圖4所示.總的觀察序號是運(yùn)動(dòng)矢量的觀察序號結(jié)合相對位置的觀察序號,并且為20的倍數(shù).因此每一個(gè)總的觀察序號都代表獨(dú)一無二的位置.

4 基于隱馬爾可夫模型的交叉口交通沖突識別

4.1 HMM理論

對于一個(gè)隨機(jī)事件,有一個(gè)觀察值序列:Y= Y1,Y2,…,YT,該事件隱含著一個(gè)狀態(tài)序列:X= X1,X2,…,XT,如圖6所示.一個(gè)隱馬爾可夫模型(HMM)是由一個(gè)五元組描述的:λ=(X,Y,A, B,π).

4.2 模型定義

根據(jù)圖6所示的HMM的理論圖,城市交叉口的觀察序列的識別可以用HMM來描述.模型中存在有限個(gè)隱藏狀態(tài),這些狀態(tài)代表抽象數(shù)量(如直行、左轉(zhuǎn)和右轉(zhuǎn)等4個(gè)方向的交通運(yùn)行的組合)與之相對應(yīng)的具有相似性的觀察值的分布概率.本文采用簡單的從左至右的HMM模型進(jìn)行事件檢測,其轉(zhuǎn)移過程如圖7所示.

圖6 HMM結(jié)構(gòu)圖Fig 6 The diagram of HMM

圖7 從左至右的HMMFig 7 Left to right HMM

T=圖像序列的長度；

X={X1,...,XT}:狀態(tài)的有限集合；

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

A={aij},aij=P(Xt=Sj|Xt-1=Si):狀態(tài)轉(zhuǎn)移概率矩陣；

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

π={πi},πi=P(X1=Si):初始狀態(tài)概率分布；

bik:狀態(tài)i時(shí),輸出觀察值k的概率.算法中定義前向變量αt(i)和后向變量βt(i).αt(i)表示為在給定模型λ,t時(shí)刻,狀態(tài)為Si時(shí)的部分觀察序列的概率αt(i)=P(Y1,Y2,…,Yt,Xt=Si/λ),1≤t≤T.βt(i)表示為在給定模型λ下,t時(shí)刻,狀態(tài)為Si時(shí)的部分觀察序列t+1到最后的概率,βt(i)= P(Yt-1,Yt-2,…,YT,Xt=Si/λ),1≤t≤T-1.

4.3 算法實(shí)現(xiàn)

4.3.1 算法流程

HMM算法實(shí)現(xiàn)的過程就是對時(shí)間序列圖像轉(zhuǎn)變成符號或數(shù)字序列輸出的過程,其具體操作過程如圖8所示.

圖8 HMM處理流程圖Fig 8 The flow chart of HMM

4.3.2 前向算法

前向算法是在時(shí)間步t,得到t之前的所有觀察序列,且時(shí)間步t的狀態(tài)是Si這一事件的概率,記為αt(i)=P(Y1,...,Yt,Xt=Si|λ).

算法過程:

Step1

Step2

Step3

4.3.3 Baum-Welch算法

Step1初始化πi,aij,bik；

Step2EM步驟；

E步驟——計(jì)算ξt(i,j)和γt(i):

給定HMM和觀察序列,ξt(i,j)為在時(shí)間t位于狀態(tài)i,時(shí)間t+1位于狀態(tài)j的概率為

給定HMM和觀測序列,在時(shí)間t位于狀態(tài)i的概率為

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

Step3循環(huán)設(shè)計(jì)i=i+1；重復(fù)EM步驟,直到πi,aij,bik收斂.

5 交通事件的預(yù)測

5.1 碰撞事件的預(yù)測

模型λ=f(A,B,π)對每一個(gè)被識別的事件進(jìn)行分類.在交叉口處通過HMM算法對上述的4種沖突[pas-00]、[pas-11]、[pas-02]、[pas-12]進(jìn)行分類,然后對沖突中的碰撞事件進(jìn)行準(zhǔn)確識別.這是因?yàn)樯婕芭鲎彩录能囕v的觀察序列與正常情形不一樣,該系統(tǒng)通過HMM算法從正常情況下對獲得的碰撞事件觀察序列加以區(qū)分并進(jìn)行碰撞事件檢測.結(jié)合交叉口沖突情況下的總的觀察序列分析,發(fā)現(xiàn)典型的碰撞事件的觀察序列為61、62、63和27、28、29.這也意味著此時(shí)兩車相距很近.當(dāng)觀察序列為“60”或“20”時(shí),代表碰撞發(fā)生的瞬間,當(dāng)觀察序列變成69、68、67或23、22、21時(shí),代表碰撞發(fā)生后的反應(yīng).

例如:車輛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 跟馳事件的預(yù)測

然而,當(dāng)車輛出現(xiàn)跟馳現(xiàn)象時(shí),這時(shí)的觀察序列跟發(fā)生碰撞時(shí)的觀察序列相似,當(dāng)相對運(yùn)動(dòng)的觀察序列為“9”和“3”結(jié)尾時(shí),代表危險(xiǎn)情況,這是因?yàn)榇藭r(shí)相對運(yùn)動(dòng)矢量比較大,兩輛車的距離很近.觀察序列“7”、“8”、“9”的出現(xiàn)取決于具有沖突的兩輛車的相對運(yùn)動(dòng)矢量和相對距離.所以很難僅僅通過觀察序列來區(qū)分碰撞和跟馳現(xiàn)象,前者屬于事件,后者屬于正常情況.對于這種無法用觀察序列來區(qū)分碰撞和跟馳現(xiàn)象的情形,可以利用交通規(guī)則來區(qū)分.

第1條:觀察序列被定義為TDM-01的具有沖突的2輛車發(fā)生碰撞；

第2條:當(dāng)有1輛車由于熄火等正常原因停在交叉口某處時(shí),從此處開始,如果具有沖突的另一輛車通過交叉口,可以判斷為跟馳現(xiàn)象；如果具有沖突的另一輛車停在交叉口內(nèi)不能行駛時(shí),則可判斷為碰撞；

第3條:如果檢測到其它車輛繞過靜止的車輛時(shí),這很可能發(fā)生了不正常事件.繞道可以通過第4節(jié)中的軌跡線來判斷.

通過上述分析,對發(fā)生的交通事故分成3種類型.

第一種:碰撞事故；

第二種:追尾；

第三種:突然停車.

6 實(shí)驗(yàn)結(jié)果及分析

6.1 交通沖突的識別

為了驗(yàn)證HMM的觀察序列的有效性,本文拍攝了3組交叉口視頻圖像,每組視頻時(shí)間為3 min,速度為10幀/s,其每組視頻里都有直行、左轉(zhuǎn)和右轉(zhuǎn)車輛.實(shí)驗(yàn)將對這3組視頻圖像分別進(jìn)行試驗(yàn),即對直行[pas-0]、左轉(zhuǎn)[pas-1]、右轉(zhuǎn)[pas-2]交通進(jìn)行識別.每一組觀察序列由12個(gè)觀察值組成,其觀察值為具有沖突的兩輛車的特征值,實(shí)驗(yàn)觀察序列值如表1所示.

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

表1中3組視頻的觀察序列在[pas-0]、[pas-1]、[pas-2]3類中都有所區(qū)別,這是因?yàn)?組視頻各自的干擾條件不一樣,仔細(xì)觀察發(fā)現(xiàn)它們之間的區(qū)別比較小,也就是說分類結(jié)果比較穩(wěn)定.通過這次實(shí)驗(yàn)表明,在任何干擾條件下,都可以采用HMM算法對[pas-0]、[pas-1]、[pas-2]進(jìn)行分類,并且能得出比較穩(wěn)定的觀察序列值.

結(jié)合上述3種觀察序列,直行[pas-0]、左轉(zhuǎn)[pas-1]、右轉(zhuǎn)[pas-2],對圖2中的4種沖突分類如下:

[pas-00]圖2(a):表示直行與直行沖突；

[pas-11]圖2(b):表示左轉(zhuǎn)與左轉(zhuǎn)沖突；

[pas-02]圖2(c):表示直行與右轉(zhuǎn)沖突；

[pas-12]圖2(d):表示左轉(zhuǎn)與右轉(zhuǎn)沖突.

為了驗(yàn)證HMM模型對4種沖突的識別效果,本文采用實(shí)際交通視頻對交叉口的交通事件檢測方法進(jìn)行驗(yàn)證.交通視頻的采集地點(diǎn)為淮安市淮海南路與解放路十字信號交叉口.此交叉口由兩條主路組成,為四相位控制的交叉口.

圖9中4幅圖分別展現(xiàn)了通過HMM算法對交叉口大量具有沖突的車輛,結(jié)合它們的觀察序列分類成[pas-00]、[pas-11]、[pas-02]、[pas-12]四種沖突.圖(a)表示由南向北標(biāo)號為25的直行車輛與由北向南標(biāo)號為23的直行車輛被檢測為[pas-00]類沖突；圖(b)表示標(biāo)號為26的左轉(zhuǎn)車輛與對向標(biāo)號為27的左轉(zhuǎn)車輛被檢測為[pas-11]類沖突；圖(c)表示標(biāo)號為29的直行車輛與相鄰右轉(zhuǎn)標(biāo)號為27的車輛被檢測為[pas-02]類沖突；圖(d)表示標(biāo)號為11的左轉(zhuǎn)車輛與對向標(biāo)號為9的右轉(zhuǎn)車輛被檢測為[pas-12]類沖突.

6.2 交通事件預(yù)測

由于在交叉口發(fā)生交通事故的數(shù)據(jù)比較少,難以拍攝到發(fā)生交通事故的視頻.所以本文所采用的視頻文件只是直行與右轉(zhuǎn)沖突的一個(gè)特例,如圖10所示為算法檢測到的跟馳碰撞事件.該事件是通過對具有沖突的兩輛車的觀察序列進(jìn)行分類而被識別的.此序列被定義為TDM-01,然而僅僅從序列難以判斷此交通事故為碰撞,由于此段視頻時(shí)間短,沒有具有其它沖突的車輛.

這時(shí)需要根據(jù)交通規(guī)則對圖10進(jìn)行事件識別,算法成功檢測出一例發(fā)生在標(biāo)號為21的車輛與標(biāo)號為22的車輛之間的交通事件.事件檢測步驟為:(1)算法檢測到具有沖突的兩輛車的觀察序列,并判斷該觀察序列屬于TDM-01類；(2)算法檢測到具有沖突的兩輛車停了一小會(huì)；(3)算法檢測出有其它車輛繞過停止的車輛繼續(xù)行駛,最終算法判斷標(biāo)號為21的車輛與標(biāo)號為22的車輛將會(huì)發(fā)生跟馳碰撞事件.

圖9 四種沖突的檢測結(jié)果Fig 9 Recognition results of pas-00,pas-11,pas-02 and pas-12

圖10 跟馳事件Fig 10 The event of car following

根據(jù)算法的這些檢測原則,圖9(d)中標(biāo)號為9的車輛與標(biāo)號為11的車輛雖然滿足前兩項(xiàng),但是由于該兩輛車周圍沒有其它車輛繞行,所以不滿足第三項(xiàng),這兩輛車將不會(huì)發(fā)生跟馳碰撞事件.

7 研究結(jié)論

本文以淮安市淮海南路與解放路交叉口為例,分析了交叉口事件檢測研究現(xiàn)狀以及交叉口處具有沖突的兩輛車的相對運(yùn)動(dòng)情況,并以提高事件檢測率,緩解交通擁擠,減少交通事故為目的提出了一種基于HMM的交通事件預(yù)測算法.本文的研究結(jié)論:

(1)提出的事件檢測算法適用于各種幾何形狀的交叉口,文中以四相位控制的交叉口為例,找出在四相位控制的交叉口具有沖突的兩輛車的相對運(yùn)動(dòng)類型；

(2)算法結(jié)合來自相對運(yùn)動(dòng)矢量的觀察序號和來自相對位置的觀察序號采用HMM模型對具有沖突的兩輛車分類,并通過實(shí)驗(yàn)成功檢測出文中提到的四種沖突；

(3)HMM模型能成功預(yù)測潛在的交通事故,如碰撞,也能對正常的停車進(jìn)行事故排除.

[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

國家自然科學(xué)基金(51078085).

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

*通訊作者:joujou1980@163.com