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

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

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

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

文章編號(hào)：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)

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

1 隱馬爾可夫模型

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

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

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

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

a）π=[π1，π2，…，πk]為初始分布，用于描述觀察序列O在t＝1時(shí)刻所處狀態(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)時(shí)的均值和協(xié)方差；qt和Qt分別是t時(shí)刻的狀態(tài)和觀察。

1．2 HMM的三個(gè)基本問(wèn)題

HMM常見的三個(gè)基本問(wèn)題是：

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

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

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

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

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

2 基于HMM的軌跡識(shí)別

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

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

即假定每個(gè)軌跡序列必定從初始狀態(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)，即

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

系統(tǒng)采用CDHMM對(duì)真實(shí)場(chǎng)景(圖4和5)中運(yùn)動(dòng)目標(biāo)軌跡進(jìn)行建模^[11]、識(shí)別和分類。系統(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)過(guò)程中用到了由Kevin Murphy編寫的HMM Toolbox。

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(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]國(guó)立新，莫福源，李昌立.基于連續(xù)高斯混合密度HMM的漢語(yǔ)全音節(jié)語(yǔ)音識(shí)別研究[J].聲學(xué)學(xué)報(bào)， 1995，20(5):321-329.

[10]張博洋.復(fù)雜背景下的手勢(shì)分割與軌跡識(shí)別[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í)場(chǎng)景運(yùn)動(dòng)目標(biāo)軌跡有效性判斷與自動(dòng)聚類算法研究[J].計(jì)算機(jī)應(yīng)用研究，2007，24(4):158160.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>