真實(shí)場(chǎng)景運(yùn)動(dòng)目標(biāo)軌跡有效性判斷與自動(dòng)聚類算法研究

摘要：提出了真實(shí)場(chǎng)景中的運(yùn)動(dòng)目標(biāo)軌跡有效性判斷與自動(dòng)聚類方法。利用軌跡長(zhǎng)度、坐標(biāo)值方差及目標(biāo)相鄰兩幀運(yùn)動(dòng)方向等信息，對(duì)軌跡進(jìn)行了預(yù)處理，得到有效的軌跡，然后以其作為樣本，計(jì)算軌跡之間的空間相似距離，采用K均值聚類法，按軌跡的幾何形狀完成了軌跡聚類。提出了利用目標(biāo)運(yùn)動(dòng)的起始點(diǎn)及整個(gè)運(yùn)動(dòng)過程中目標(biāo)的運(yùn)動(dòng)方向信息，采用K均值聚類方法，進(jìn)一步按目標(biāo)的運(yùn)動(dòng)方向完成了軌跡聚類。兩種真實(shí)場(chǎng)景的目標(biāo)軌跡聚類結(jié)果證明了該方法的有效性。其研究結(jié)果為學(xué)習(xí)軌跡模式、目標(biāo)運(yùn)動(dòng)軌跡識(shí)別、分類、異常檢測(cè)奠定了基礎(chǔ)。

關(guān)鍵詞：軌跡聚類； K均值； 軌跡識(shí)別； 分類； 異常檢測(cè)

中圖分類號(hào)：TP242.6+2文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)04-0158-03

近年來，隨著視頻監(jiān)控系統(tǒng)的不斷發(fā)展及全球范圍內(nèi)打擊恐怖分子的迫切需要，基于目標(biāo)運(yùn)動(dòng)軌跡的分析^[1]和識(shí)別成為研究熱點(diǎn)，并引起了科學(xué)界研究者們的濃厚興趣。例如，自動(dòng)進(jìn)行基于運(yùn)動(dòng)員運(yùn)動(dòng)模式的運(yùn)動(dòng)分析；在繁忙的室內(nèi)或室外交通環(huán)境中自動(dòng)完成各種目標(biāo)軌跡的分類、識(shí)別、行為理解，進(jìn)一步實(shí)現(xiàn)異常檢測(cè)等。

通過跟蹤獲取的目標(biāo)運(yùn)動(dòng)軌跡有助于進(jìn)一步分析目標(biāo)的行為。目前軌跡分類的方法主要有HMM（Hidden Markov Model）和NN（Neural Network）。Bashir等人^[2]利用HMM進(jìn)行基于目標(biāo)軌跡的行為分類和識(shí)別。Owens and Hunter^[3]運(yùn)用一種基于自組織映射（SelfOrganising Mapping，SOM）的方法進(jìn)行軌跡分類。胡衛(wèi)明等人^[4，5]采用層次自組織神經(jīng)網(wǎng)絡(luò)方法學(xué)習(xí)軌跡分布模式。但是他們都沒有對(duì)軌跡進(jìn)行預(yù)處理，不能克服跟蹤算法不魯棒的缺點(diǎn)。對(duì)此，本文提出一種軌跡預(yù)處理的方法，并完成了基于K均值（Kmeans）算法的軌跡聚類。

1軌跡的預(yù)處理

由于目標(biāo)跟蹤過程中可能伴隨有失跟、誤跟及遮擋等，獲取的軌跡有的是不完整的，并且受噪聲的干擾，這些都會(huì)影響進(jìn)一步的軌跡分類、識(shí)別、行為分析等。在進(jìn)行軌跡聚類之前有必要進(jìn)行軌跡的預(yù)處理。本文主要是基于三種信息，即軌跡長(zhǎng)度、軌跡上點(diǎn)坐標(biāo)值的方差，以及目標(biāo)相鄰兩幀運(yùn)動(dòng)方向角度等，對(duì)目標(biāo)軌跡進(jìn)行有效性判斷以獲得有效的軌跡。通過預(yù)處理，可簡(jiǎn)化后續(xù)工作，減少計(jì)算量，同時(shí)提高聚類的準(zhǔn)確率。

1.1長(zhǎng)度信息

本文采用的方法是先統(tǒng)計(jì)每條軌跡上坐標(biāo)點(diǎn)的個(gè)數(shù)p，設(shè)定一個(gè)閾值T1。如果p≥T1，保留該軌跡，并用q記錄其相應(yīng)軌跡的下標(biāo)。通過此處理，可以將跟蹤過程中的一部分受噪聲干擾的軌跡，以及沒有跟蹤完整的軌跡濾掉，減少進(jìn)一步分析的計(jì)算量和誤差。

1.2方差信息

在軌跡長(zhǎng)度有效的基礎(chǔ)上，計(jì)算每條軌跡上所有點(diǎn)橫坐標(biāo)的方差Vx與縱坐標(biāo)的方差Vy，并設(shè)定兩個(gè)閾值T2、T3。如果Vx＞T2，或者Vy＞T3，則認(rèn)為該條軌跡是有效的；否則是無效的。經(jīng)過這個(gè)步驟處理后，可進(jìn)一步濾掉受噪聲干擾及一些錯(cuò)跟目標(biāo)的運(yùn)動(dòng)軌跡。

1.3軌跡編碼

軌跡編碼^[5]是在上述兩個(gè)步驟處理的基礎(chǔ)上，根據(jù)目標(biāo)的軌跡計(jì)算出其在各時(shí)刻的運(yùn)動(dòng)方向。

圖像序列的目標(biāo)運(yùn)動(dòng)軌跡，通常由目標(biāo)在不同時(shí)刻的質(zhì)心點(diǎn)連接而成，軌跡上的點(diǎn)是等時(shí)間間隔采樣得到的，即間隔Δt采樣一次。對(duì)于目標(biāo)o，設(shè)第i次采樣時(shí)其質(zhì)心位置的坐標(biāo)為(xi，yi)，作n次采樣后可以得到一個(gè)由n個(gè)坐標(biāo)點(diǎn)組成的序列：T0={(x1，y1)，…，(xi，yi)，…，(xn-1，yn-1)，(xn，yn)}。

由式（1）可以算出相鄰幀同一個(gè)運(yùn)動(dòng)目標(biāo)的運(yùn)動(dòng)方向角度θi。

本文以方向作為軌跡的特征。因此確定了有效軌跡之后，采用前后幀坐標(biāo)點(diǎn)間的連線的角度作為軌跡的特征矢量進(jìn)行矢量編碼。將x-y坐標(biāo)平面360°按逆時(shí)針方向等間隔分為16等分，并依次編碼為1，2，3，…，15，16，可以得到夾角量化編碼示意圖及方向矢量圖^[6]如圖1所示。

根據(jù)軌跡的復(fù)雜程度將軌跡夾角量化為16個(gè)等級(jí)。這樣可以很容易地獲取軌跡的方向鏈碼，用它來計(jì)算軌跡的局部變化更為直接和有效。因?yàn)檐壽E被定義為一個(gè)具有時(shí)空上下文的模式，所以在本文中，可將一條軌跡表示成一個(gè)由運(yùn)動(dòng)方向角度編碼后組成的特征矢量的序列組合。這樣一條軌跡可以表示為由這些碼字組成的一個(gè)序列。

例如，圖2中，軌跡a被編碼為3，1，1，15，16，16，1，1，2，1，1，2，2，2，1;而軌跡b被編碼為1，1，1，1，2，2，1，1，16，1，2，2，2，1，1。

由于方向鏈碼是以方向?yàn)榛A(chǔ)的，而受噪聲干擾的軌跡多表現(xiàn)為局部鄰域內(nèi)鏈碼的快速變化。噪聲小則表現(xiàn)為局部鄰域內(nèi)鏈碼的緩慢變化。可以利用統(tǒng)計(jì)方向鏈碼的變化來反映軌跡的局部鄰域內(nèi)受噪聲干擾的程度。

本文采用滑窗的方法進(jìn)一步去除受噪聲干擾嚴(yán)重的軌跡。得到每條軌跡的方向鏈碼后，計(jì)算相鄰兩幀鏈碼的變化值，設(shè)滑窗長(zhǎng)度為L(zhǎng)，閾值為T4。對(duì)于每條軌跡，統(tǒng)計(jì)其相鄰兩幀鏈碼變化值。

假設(shè)第i幀的鏈碼值為e，第i+1幀的鏈碼值為f，則鏈碼變化值Δ定義為

采用滑窗的方法，求得各窗中鏈碼變化的平均值C。對(duì)每一條軌跡，如果某一段窗中的鏈碼變化平均值C＞T4，則去除該條軌跡，即認(rèn)為該軌跡無效。通過這種方式可以進(jìn)一步去掉一部分受噪聲干擾嚴(yán)重的軌跡，最后獲得有效的樣本。

2基于空間相似距離的K均值軌跡聚類

經(jīng)過上述三個(gè)方面的預(yù)處理后獲得的軌跡認(rèn)為是有效的。針對(duì)軌跡序列長(zhǎng)度不固定的特點(diǎn)，計(jì)算軌跡間的距離^[7]。采用K均值算法對(duì)軌跡樣本進(jìn)行聚類。

2.1軌跡之間的距離

給定兩條軌跡A和B，其中軌跡A上有n個(gè)點(diǎn)，軌跡B上有m個(gè)點(diǎn)。它們之間的空間相似距離d^[10]定義為

其中，

其中，di， j是一條軌跡上的第i個(gè)點(diǎn)到另一條軌跡上的第j個(gè)點(diǎn)之間的歐氏距離。可見，如果軌跡A和B越相似，它們之間的距離就越小，反之則越大。

2.2基于K均值的軌跡聚類

在上述軌跡之間相似性度量的基礎(chǔ)上采用K均值對(duì)軌跡進(jìn)行聚類。

令Ω為L(zhǎng)個(gè)樣本序列的集合，Ω={X1，X2，…，XL}。其中，每一個(gè)元素Xl為經(jīng)過預(yù)處理后的軌跡序列。對(duì)每?jī)蓚€(gè)序列利用式（3）～（5）進(jìn)行相似性計(jì)算，得相似距離d(Xi，Xj)，對(duì)所有樣本序列計(jì)算則得到一個(gè)L×L的距離矩陣。聚類的目的是將樣本集Ω聚成K個(gè)不同的類{wi;i=1，2，…，K}，使Ω=∪Ki=1wi。在同一類中各序列模式比較接近，類內(nèi)距離較小，類的總數(shù)K可以事先確定，也可以聚類時(shí)根據(jù)某種準(zhǔn)則自動(dòng)確定。本文實(shí)驗(yàn)中類數(shù)事先確定，每一類可以用一條典型的軌跡來代表（本文采用每一類的“中心”軌跡代表其所屬的類別）。實(shí)現(xiàn)的步驟及算法流程（圖3）如下：

（1）初始化聚類“中心”。隨機(jī)選取一條軌跡作為第一類的中心，即選取一個(gè)軌跡序列作為聚類的初始“中心”。

然后在剩下的L-1個(gè)序列中選取一個(gè)序列X2作為第二類的中心C2，設(shè)定一個(gè)閾值ρ，使其到第一類的中心C1的距離滿足

與此相似，在剩下的L-2個(gè)序列中選取X3作為第三類的中心C3，使其到前兩類的中心距離均大于ρ，即d(C3，C2)≥ρ，d(C3，C1)≥ρ。同理得到C4，…，CK。

（2）計(jì)算樣本到初始中心的距離并確定其所屬的類。所有的軌跡被分到與類“中心”距離最近的類。

（3）調(diào)整聚類“中心”。由步驟(2)可得到對(duì)應(yīng)每類的樣本個(gè)數(shù)n1，…，nK。對(duì)每一類，找出屬于該類的所有樣本，尋找一個(gè)新的代表，使其到該類內(nèi)所有樣本的空間相似距離（本文采用距離之和）最小。對(duì)應(yīng)下標(biāo)索引即可找出新的聚類“中心”。Xl，i表示屬于第i類的第l個(gè)樣本。

（9）

（4）重復(fù)步驟（2）和（3），直到連續(xù)兩次的迭代結(jié)果（即聚類中心）不再發(fā)生變化為止。此時(shí)的“中心”就是聚類的“中心”，各個(gè)類中的樣本就屬于同一類軌跡模式。

2.3基于運(yùn)動(dòng)方向的K均值聚類

根據(jù)軌跡的空間相似距離（即幾何形狀）聚成大的類別后，在此基礎(chǔ)上把每大類聚為運(yùn)動(dòng)方向相反的兩類。

上面介紹的軌跡聚類沒有考慮目標(biāo)運(yùn)動(dòng)方向相反的情況。為了使聚類更清楚細(xì)致，可以考慮目標(biāo)的運(yùn)動(dòng)方向。采用K均值聚類后得到的同一類軌跡的幾何形狀是相似的，但是它們之間的運(yùn)動(dòng)方向并不都相同。本文提出兩種依據(jù)運(yùn)動(dòng)方向聚類軌跡的方法：

（1）聚類類內(nèi)軌跡的起始點(diǎn)

把所有軌跡樣本的起始點(diǎn)找出來，利用K均值聚類即可。如果運(yùn)動(dòng)方向相似或相同，則軌跡的起始點(diǎn)就屬于相同類別，這樣可以把軌跡按運(yùn)動(dòng)方向聚為兩類。

（2）計(jì)算軌跡終點(diǎn)和起點(diǎn)的方向角θsf

找出每條軌跡的起點(diǎn)S(xs，ys)和終點(diǎn)F(xf，yf)，則目標(biāo)運(yùn)動(dòng)的大概方向可用式（10）中的θsf描述。根據(jù)θsf的符號(hào)可以將軌跡聚為兩類。

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

實(shí)驗(yàn)中的圖像序列是采用Sony EVID100攝像機(jī)從高樓上捕獲的視頻序列；輸入圖像序列大小為320×240，選取兩個(gè)不同場(chǎng)景；采用文獻(xiàn)[8]中的跟蹤算法，對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行跟蹤，得到一系列目標(biāo)的運(yùn)動(dòng)軌跡。軌跡由目標(biāo)在不同時(shí)刻的質(zhì)心點(diǎn)連接而成。本文的實(shí)驗(yàn)使用了以下兩個(gè)場(chǎng)景(圖4（b）和圖5（b)）的兩組樣本數(shù)據(jù)：

第一組樣本數(shù)據(jù)是花園中人的運(yùn)動(dòng)軌跡，如圖4（a）所示。

第二組樣本數(shù)據(jù)是實(shí)際交通場(chǎng)景中汽車行駛的軌跡，如圖5（a）所示。

圖中“○”表示每條軌跡的起始點(diǎn)，“×”表示軌跡終點(diǎn)。實(shí)驗(yàn)中有關(guān)閾值的選取如下：

T1=45，T2=20，T3=20，L=8，T4=2.8，K=4，ρ=100 

對(duì)第一組樣本采用K均值聚類方法分為四大類軌跡，有關(guān)實(shí)驗(yàn)結(jié)果如圖4（f）所示。每種顏色代表一個(gè)軌跡類別，分別用紅色、綠色、藍(lán)色、粉紅色標(biāo)注。紅色類別中有的軌跡較長(zhǎng)，但聚類是正確的。對(duì)第二組樣本，其空間形狀信息基本相似，可以認(rèn)為屬于同一個(gè)大的類別，但是其運(yùn)動(dòng)方向不同。因此本文采用基于運(yùn)動(dòng)方向的K均值聚類方法將其聚為運(yùn)動(dòng)方向相反的兩類，分別用紅色和綠色標(biāo)注。有關(guān)實(shí)驗(yàn)結(jié)果如圖5(f)所示，紅色軌跡類中有一條綠色的，這是該場(chǎng)景中的一條異常軌跡——逆向行車。

4結(jié)束語

真實(shí)場(chǎng)景中運(yùn)動(dòng)目標(biāo)的軌跡分類和識(shí)別是近年來視頻監(jiān)控領(lǐng)域中新興的研究方向。本文研究工作的目的是對(duì)真實(shí)場(chǎng)景中目標(biāo)的運(yùn)動(dòng)軌跡進(jìn)行聚類，這是一項(xiàng)很有意義的研究工作。本文提出了基于軌跡點(diǎn)數(shù)、軌跡點(diǎn)的坐標(biāo)方差及相鄰兩幀運(yùn)動(dòng)方向信息的軌跡預(yù)處理方法。使用該方法得到有效軌跡。基于軌跡空間相似距離的K均值聚類方法；按幾何形狀完成了花園場(chǎng)景中行人軌跡的有效聚類，進(jìn)一步提出了基于運(yùn)動(dòng)方向的K均值聚類方法；按軌跡運(yùn)動(dòng)方向完成了交通場(chǎng)景中車輛的運(yùn)動(dòng)軌跡的有效聚類。本文的研究結(jié)果為學(xué)習(xí)軌跡模式^[4]、軌跡識(shí)別和分類、事件檢測(cè)^[9]等，提供了有效的依據(jù)。

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