基于隱馬爾可夫模型的運(yùn)動目標(biāo)軌跡識別

摘 要：引入改進(jìn)的隱馬爾可夫模型算法，針對真實(shí)場景中運(yùn)動目標(biāo)軌跡的復(fù)雜程度對各個軌跡模式類建立相應(yīng)的隱馬爾可夫模型，利用訓(xùn)練樣本訓(xùn)練模型得到可靠的模型參數(shù)；計算測試樣本對于各個模型的最大似然概率，選取最大概率值對應(yīng)的軌跡模式類作為軌跡識別的結(jié)果，對兩種場景中聚類后的軌跡進(jìn)行訓(xùn)練與識別。實(shí)驗(yàn)結(jié)果表明，平均識別率分別達(dá)到87.76 %和94. 19%。

關(guān)鍵詞：軌跡識別；運(yùn)動分析；行為模式；隱馬爾可夫模型

中圖分類號：TP242．62 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)07-1988-04



Trajectory recognition of moving objects based on hidden Markov model

PAN Qiming1，CHENG Yongmei2

（1.Dept. of Automation， Zhongshan Institute， University of Electronic Science Technology of China， Zhongshan Guangdong 528402， China;2.College of Automation， Northwestern Polytechnical University， Xi’an 710072， China）

Abstract:Using modified hidden Markov model， firstly， aiming at the complex degree of the objects’ trajectories in real scene， the models were built for every trajectory pattern， and the training samples were used to get the credible parameters of the model.Finally， the maximum likelihood probability of test samples were computed to all of the trained model， the maximum value was saved and the corresponding model was the recognition result. Then train and recognize the samples clustered， and average recognition rate reach 87.76 % and 94. 19% respectively.



Key words:trajectory recognition；movement analysis；activity pattern；hidden Markov model(HMM)

近年來，基于目標(biāo)運(yùn)動軌跡的分析和識別^[1]是計算機(jī)視覺領(lǐng)域一個新興的研究方向，引起了科學(xué)界研究者們的濃厚興趣。它是運(yùn)動分析中的基本問題，其功能是解釋所監(jiān)視場景中發(fā)生的事件，對所監(jiān)視場景中運(yùn)動目標(biāo)軌跡的行為模式^[2]進(jìn)行分析與識別，智能地自動分類；由當(dāng)前目標(biāo)所處的狀態(tài)對將要發(fā)生的事件進(jìn)行預(yù)測，根據(jù)要求對異常事件及時報警^[3]，從而達(dá)到安全監(jiān)控的目的^[4]。其應(yīng)用范圍非常廣泛。例如，自動地進(jìn)行基于運(yùn)動員運(yùn)動模式的運(yùn)動分析^[3]；在繁忙的室內(nèi)或室外交通環(huán)境中自動完成各種目標(biāo)的行為理解^[5]等。本文利用HMM算法，采用CDHMM模型，對真實(shí)場景中運(yùn)動目標(biāo)軌跡進(jìn)行識別。

1 隱馬爾可夫模型

1．1 隱馬爾可夫模型的定義和基本概念

隱馬爾可夫模型^[6，7]是一種很成熟的匹配時變數(shù)據(jù)的技術(shù)，它是隨機(jī)狀態(tài)機(jī)器。HMM的使用涉及到訓(xùn)練和分類兩個階段。訓(xùn)練階段包括指定一個隱馬爾可夫模型的隱狀態(tài)個數(shù)，并優(yōu)化相應(yīng)的狀態(tài)轉(zhuǎn)移和輸出概率以便產(chǎn)生的輸出符號與在特定的運(yùn)動類別之內(nèi)所觀察到的圖像特征相匹配。對于每一個軌跡模式類別，訓(xùn)練一個HMM。匹配階段涉及到一個特定的HMM可能產(chǎn)生相應(yīng)于所觀察圖像特征的測試符號序列的概率計算。

本文采用基于模型描述的方法獲得軌跡的動態(tài)特性，將軌跡T投影到參數(shù)空間λ，這個參數(shù)用一系列的HMM參數(shù)描述。軌跡信息就是發(fā)射的可觀測輸出信號。隱狀態(tài)捕捉連續(xù)幀軌跡坐標(biāo)的轉(zhuǎn)移特性。對于給定的軌跡，最大化概率的狀態(tài)序列就成為給定軌跡相應(yīng)的模型。

一個K狀態(tài){S1，S2，…，Sk}的輸出為高斯分布的HMM。簡單說明如下：

a）π=[π1，π2，…，πk]為初始分布，用于描述觀察序列O在t＝1時刻所處狀態(tài)的概率分布，即πi=P(q1=Si)(i=1，2，…，k)，它滿足ki=1πi=1；

b）B={bi， j|i， j=1，2，…，k}為狀態(tài)轉(zhuǎn)移概率矩陣，即bi， j=P(qt=Sj|qt-1=Si，qt-2=Sk，…)=P(qt=Sj|qt-1=Si)，它滿足ki=1bi， j=1；

c）均值、方差和混合模型的權(quán)值N(Ot；μj;Σj)。其中：μj和Σj是處于j狀態(tài)時的均值和協(xié)方差；qt和Qt分別是t時刻的狀態(tài)和觀察。

1．2 HMM的三個基本問題

HMM常見的三個基本問題是：

a)在給定模型λ條件下，如何有效地計算產(chǎn)生觀察序列O的概率P（O|λ）。這在識別分類中是一個非常重要的環(huán)節(jié)。

b)如何選擇在某種意義下最佳的狀態(tài)序列Q=q1，q2，…，qT，以最好地解釋觀察序列O。這是HMM的識別隱形狀態(tài)鏈問題。

c）如何調(diào)整模型參數(shù)λ，才能使P(O|λ)達(dá)到最大，這屬于HMM模型的訓(xùn)練問題。

利用HMM進(jìn)行軌跡識別前，必須先有效解決第三個問題，得到最優(yōu)模型以計算軌跡相對于各個軌跡模式類所對應(yīng)模型的概率。

本文采用從左到右的HMM（狀態(tài)是有序的序列，并從左到右轉(zhuǎn)移，或連續(xù)幾幀停留在一個狀態(tài)，如圖1）作為模型依據(jù)。在HMM建模階段，每條有效軌跡對應(yīng)一個HMM。訓(xùn)練中模型的狀態(tài)數(shù)的選取，理論上是越多越好。這是因?yàn)殡S著狀態(tài)數(shù)的增加，訓(xùn)練的模型越能真實(shí)、準(zhǔn)確地描述軌跡，然而這卻會增加實(shí)驗(yàn)的難度。所以對狀態(tài)數(shù)的選取是有區(qū)分的，實(shí)驗(yàn)中每條軌跡的狀態(tài)數(shù)按其復(fù)雜程度確定。

2 基于HMM的軌跡識別

2．1 HMM模型參數(shù)選擇及初始化

根據(jù)軌跡的復(fù)雜程度，HMM模型的狀態(tài)數(shù)取4～6不等。模型的結(jié)構(gòu)為自左到右且無跳轉(zhuǎn)，如圖1所示，且假設(shè)所有模型均從初始狀態(tài)出發(fā)，沿著狀態(tài)序號增加的方向逐步轉(zhuǎn)移，最后終止于末狀態(tài)。當(dāng)狀態(tài)數(shù)N=S時，初始狀態(tài)概率為

即假定每個軌跡序列必定從初始狀態(tài)出發(fā)。A=[aij]N×N代表狀態(tài)轉(zhuǎn)移概率矩陣。由于狀態(tài)轉(zhuǎn)移概率的變化遠(yuǎn)遠(yuǎn)小于狀態(tài)輸出概率的變化，可以令狀態(tài)轉(zhuǎn)移概率矩陣A為一恒定矩陣或隨機(jī)矩陣，即矩陣A中的元素為0～1的數(shù)值。本文令其允許的狀態(tài)轉(zhuǎn)移概率均為0．5，最后停留在末狀態(tài)，即

通過實(shí)驗(yàn)發(fā)現(xiàn)，此近似對識別性能無很大的影響。連續(xù)HMM能直接對軌跡序列數(shù)據(jù)進(jìn)行處理。為了獲得較高的識別率，本文系統(tǒng)輸出概率函數(shù)選擇連續(xù)混合高斯概率密度函數(shù)。混合高斯的方法是對各個混合單元的概率加權(quán)，起到了平滑的作用^[8]。因此，本文采用連續(xù)混合高斯HMM^[9]。為了克服訓(xùn)練數(shù)據(jù)不足的缺點(diǎn)，本文采用多觀察序列訓(xùn)練算法來訓(xùn)練HMM模型。在連續(xù)密度混合高斯HMM下，混合數(shù)M的大小對識別率是有很大影響的，它決定了輸出概率的精度。在訓(xùn)練數(shù)據(jù)充分的條件下，增大混合數(shù)M，輸出概率精度越高，對屬于該狀態(tài)中的矢量在軌跡空間中的分布描述得越細(xì)致 ，也就越接近實(shí)際的軌跡空間。但是混合數(shù)M增大時，處于某個狀態(tài)時被劃分到該狀態(tài)的軌跡序列幀數(shù)目要充分，而且計算量也隨之增大。另一方面，高斯分布本身就是對大樣本分布的一種近似，混合數(shù)M太少的高斯混合會導(dǎo)致對訓(xùn)練樣本集描述得不充分。因此，即使是在訓(xùn)練數(shù)據(jù)充分的情況下，對訓(xùn)練過程也是有要求的，即模型數(shù)據(jù)分布要均勻，且要考慮軌跡幀數(shù)多少不同造成的影響。本文選取M=2，即每個狀態(tài)對應(yīng)的輸出序列數(shù)據(jù)由兩個混合高斯概率密度函數(shù)的線性組合擬合其分布。設(shè)O為待擬合的觀察矢量，則

其中:M為混合數(shù);N(O，μjm，Σjm)代表多元高斯概率密度函數(shù)，μjm、Σjm、Cjm分別是狀態(tài)j所對應(yīng)的觀察中，第m個高斯分量的均值矢量、協(xié)方差矩陣和混合權(quán)系數(shù)。因此，Cjm

對各狀態(tài)的混合高斯概率密度函數(shù)的均值矢量、協(xié)方差矩陣和混合權(quán)系數(shù)的初始化均采用K均值算法。首先將訓(xùn)練樣本中已經(jīng)聚為一個軌跡模式類的觀察序列值讀入一個數(shù)組，依據(jù)狀態(tài)數(shù)，對其數(shù)據(jù)進(jìn)行平均分段，也就是將這些軌跡看做一些點(diǎn)集，采用K均值自動聚類，聚類數(shù)等于HMM模型的狀態(tài)個數(shù);然后將這些觀察序列中屬于一個狀態(tài)的數(shù)據(jù)組成一個矩陣，再根據(jù)混合單元的個數(shù)M，利用K均值算法求得各狀態(tài)的均值矢量、協(xié)方差矩陣和混合權(quán)系數(shù);最后得到了一個N個狀態(tài)的連續(xù)密度HMM（CDHMM）模型參數(shù)的初始值為：N=5，M=2，π，A=[a

2．2 軌跡的HMM模型訓(xùn)練

為了克服單個觀察值序列訓(xùn)練的缺點(diǎn)，本文采用了多觀察值序列訓(xùn)練算法，初始模型λ由上得到。其訓(xùn)練步驟如下(算法流程圖如圖2所示)：

a)給定軌跡模式類Ci的訓(xùn)練樣本集，包含L個觀察值序列，開始第n次迭代，l=1。

b)取第l個觀察值序列O(l)=O(l)1，O(l)2，…，O(l)Tl進(jìn)行訓(xùn)練，1≤l≤L。

c)給定觀察值序列O(l)及模型λ，利用式(6)(7)計算前向變量及后向變量(1≤t≤T)：

d)利用式(8)(9)計算ξ(l)t(i， j)。模型λ和觀察值序列O(l)下，時間t時處于狀態(tài)Si，且在時間t+1時處于狀態(tài)Sj的概率，以及γ(l)t(i)(即時間t時處于狀態(tài)

λ下的狀態(tài)Si轉(zhuǎn)移到狀態(tài)Sj的頻率，及狀態(tài)Si的出現(xiàn)頻率，暫存計算結(jié)果。返回步驟b)并取下一個觀察值序列進(jìn)行計算，直到l=L。最后，利用多觀察值序列訓(xùn)練HMM模型的重估式(10)～(14)，對模型參數(shù)進(jìn)行重估，得到新的模型。

f)模型評價。計算P(O|λ)=Ll=1P(O(l)|λ)，設(shè)定一個閾值Tthreshold=4×10-4，并計算ΔP/。其中:

判斷模型是否收斂？如果ΔP/＜Tthreshold，則模型收斂，結(jié)束軌跡類別Ci的訓(xùn)練；否則返回步驟a）進(jìn)行下一次迭代。

2．3 運(yùn)動目標(biāo)軌跡識別

軌跡的識別過程^[10]（圖3）實(shí)質(zhì)上是在已經(jīng)訓(xùn)練好的HMM模型中選取一個能夠最好地描述觀察值序列的模型，也即：假設(shè)通過軌跡的預(yù)處理模塊，得到待識別的軌跡樣本序列（也就是測試樣本）O=O1，O2，…，OT，對于模型庫中的模型集λ={λ1，λ2，…，λn}中的每一個模型λi(i=1，2，…，n)，計算測試樣本相對于這些模型的條件概率

將結(jié)果保存到一個數(shù)組中。其中:Q為給定的觀察值序列O最優(yōu)的狀態(tài)序列。然后利用Viterbi算法，并根據(jù)如下的最大似然式(4)，把條件概率最大的軌跡模式類作為該軌跡序列的類別即為識別結(jié)果（由于讀入模型的順序是固定的，用數(shù)組的索引即可）：

3 仿真實(shí)驗(yàn)結(jié)果與分析

系統(tǒng)采用CDHMM對真實(shí)場景(圖4和5)中運(yùn)動目標(biāo)軌跡進(jìn)行建模^[11]、識別和分類。系統(tǒng)結(jié)構(gòu)如圖6所示。實(shí)驗(yàn)系統(tǒng)建立在768 MB內(nèi)存的P4 3.0 GHzPC機(jī)上，采用MATLAB 6.5進(jìn)行實(shí)驗(yàn)仿真。在實(shí)驗(yàn)過程中用到了由Kevin Murphy編寫的HMM Toolbox。

本文實(shí)驗(yàn)系統(tǒng)中采用預(yù)處理并自動聚類后的軌跡樣本，包括兩個真實(shí)場景(花園中人的運(yùn)動軌跡、交通場景中汽車行駛的軌跡)中運(yùn)動目標(biāo)的軌跡視頻數(shù)據(jù)。輸入圖像序列大小為320×240。

本文實(shí)驗(yàn)首先采用文獻(xiàn)[12]中的跟蹤算法得到運(yùn)動目標(biāo)的軌跡數(shù)據(jù)；然后送入軌跡預(yù)處理模塊，將受噪聲干擾嚴(yán)重的軌跡以及錯跟、失跟的軌跡去掉，保留完整的、有效的軌跡，并采用K均值自動聚類^[13]，將場景中的軌跡聚為幾個大的軌跡模式類，以便提高后續(xù)軌跡識別、分類的準(zhǔn)確率。通過跟蹤，將視頻中運(yùn)動目標(biāo)的軌跡樣本數(shù)據(jù)以目標(biāo)所在位置的坐標(biāo)數(shù)據(jù)序列對的形式存儲，然后進(jìn)行預(yù)處理，得到軌跡樣本庫（包括訓(xùn)練樣本和測試樣本）；隨后，將聚為一個模式類的訓(xùn)練樣本的軌跡坐標(biāo)數(shù)據(jù)經(jīng)訓(xùn)練模塊訓(xùn)練，得到對應(yīng)每一個軌跡模式類的HMM參數(shù)；最后計算各個測試樣本的軌跡坐標(biāo)數(shù)據(jù)對于每一個HMM模型的概率，經(jīng)識別模塊識別出結(jié)果（即選取最大概率對應(yīng)的模型作為軌跡所屬的模式類）并輸出。

首先，將場景1中預(yù)處理后的樣本分為8組4類，將場景2中預(yù)處理后的樣本分為4組2類，如表1和2所示；然后采用BaumWelch算法進(jìn)行參數(shù)迭代，直到觀察序列相對于HMM模型的輸出概率不再發(fā)生明顯的改變。本文是指當(dāng)?shù)星耙淮屋敵龅母怕逝c本次輸出的概率之差的絕對值相對于這兩次輸出概率絕對值的平均值比例小于4×10-4時停止迭代。經(jīng)過訓(xùn)練后得到的HMM模型參數(shù)保存到對應(yīng)的文檔中。模型參數(shù)包括HMM狀態(tài)數(shù)N、高斯混合單元個數(shù)M、觀察矢量的維數(shù)O、初始狀態(tài)概率矩陣π、狀態(tài)轉(zhuǎn)移概率矩陣A、混合高斯的權(quán)系數(shù)矩陣Cjm、均值矢量μjm、協(xié)方差矩陣Σjm、狀態(tài)駐留分布矩陣vote。然后取出測試樣本，計算測試樣本相對于已經(jīng)訓(xùn)練出的各個模型的最大似然概率值，取其中的最大值，并索引對應(yīng)的模型即得到該軌跡所屬的軌跡模式類。表3和4是利用HMM算法對上述兩個真實(shí)場景中運(yùn)動目標(biāo)軌跡進(jìn)行識別的結(jié)果。實(shí)驗(yàn)結(jié)果如下：

識別率=正確識別數(shù)/總測試樣本數(shù)×100%

從實(shí)驗(yàn)仿真過程及所得結(jié)果可見，HMM識別速度較快，但是訓(xùn)練耗費(fèi)的時間較多。為了得到可靠的模型參數(shù)，HMM用多個軌跡序列樣本作為訓(xùn)練序列，充分反映每個軌跡模式的特征，大大提高了識別率。

4 結(jié)束語

運(yùn)動目標(biāo)軌跡識別是視頻監(jiān)控中運(yùn)動分析的基本問題，它的功能是解釋所監(jiān)視場景中發(fā)生的事件，對所監(jiān)視場景中運(yùn)動目標(biāo)軌跡的行為模式進(jìn)行分析與識別，由當(dāng)前目標(biāo)所處的狀態(tài)對將要發(fā)生的事件進(jìn)行預(yù)測，根據(jù)要求對異常事件進(jìn)行報警，從而達(dá)到安全監(jiān)控的目的。本文引入改進(jìn)的隱馬爾可夫模型算法，采用CDHMM模型， 對兩個真實(shí)場景中六種不同的目標(biāo)運(yùn)動軌跡進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)達(dá)到了較高的平均識別率。

參考文獻(xiàn)：

［1］JOHNSON N，HOGG D C.Learning the distribution of object trajectories for event recognition[J].Image and Vision Computing， 1996，14(8):609-615.

[2]HU Weiming，XIE Dan，TAN Tieniu.A hierarchical selforganizing approach for learning the patterns of motion trajectories[J].IEEE Trans on Neural Networks，2004，15(1):135144.

[3]PORIKLI F，HAGA T.Event detection by eigenvector decomposition using object and frame features[C]//Proc of 2004 Conference on Computer Vision and Pattern Recognition Workshops (CVPRW’04).Washington DC:IEEE Computer Society，2004.

[4]FORESTI G L，ROLI F.Learning and classification of suspicious events for advanced visualbased surveillance[M]//FORESTI G L，MHNEN P，REGAZZONI C S.Multimedia videobased surveillance system:requirements.Boston:Kluwer Academic Publishers，2000.

[5]LOU Jianguang，LIU Qifeng，TAN Tieniu，et al.Semantic interpretation of object activities in a surveillance system[C]//Proc of the 16th International Conference on Pattern Recognition，ICPR2002.Washington DC:IEEE Computer Society，2002.

[6]PORITZ A B.Hidden Markov models:a guided tour[C]//Proc of IEEE International Conference on Acoustics， Speech and SignalProcessing.New York:IEEE Press，1988:713.

[7]RABINER L R.A tutorial on hidden Markov models and selected applications in speech recognition[J].Proc of IEEE，1989，77(2):257-286.

[8]BASHIR F，KHOKHAR A，SCHONFELD D.Automatic object trajectorybased motion recognition using Gaussian mixture models[C]//Proc of IEEE International Conference on Multimedia Expt (ICME 2005).Amsterdam:[s.n.]，2005:15321535.

[9]國立新，莫福源，李昌立.基于連續(xù)高斯混合密度HMM的漢語全音節(jié)語音識別研究[J].聲學(xué)學(xué)報， 1995，20(5):321-329.

[10]張博洋.復(fù)雜背景下的手勢分割與軌跡識別[D].山東大學(xué)，2003.

[11]LEE K K，XU Yangsheng.Boundary modeling in human walking trajectory analysis for surveillance[C]//Proc of IEEE International Conference on Robotics Automation.Piscataway，New Jersey:IEEE Press，2004:5201-5205.

[12]TAO Y，LI S Z，PAN Quan，et al.Realtime multiple object tracking with occlusion handling in dynamic scenes[C]//Proc of IEEE Computer Vision and Pattern Recognition Conference (CVPR’05).Washington DC:IEEE Computer Society，2005:970-975.

[13]潘奇明，程詠梅，楊濤，等.真實(shí)場景運(yùn)動目標(biāo)軌跡有效性判斷與自動聚類算法研究[J].計算機(jī)應(yīng)用研究，2007，24(4):158160.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”