基于改進(jìn)譜聚類的人群移動(dòng)行為檢測(cè)

楊玉成，張 乾，2，邵定琴，岳詩(shī)琴

(1. 貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院，貴州 貴陽(yáng) 550025；2. 貴州省模式識(shí)別與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025)

1 引言

公共場(chǎng)所人群密度越來越高，例如機(jī)場(chǎng)、火車站、公園、旅游區(qū)等，大量人群聚集和離散容易引起安全事故的發(fā)生，因此公共場(chǎng)所人群事件實(shí)時(shí)監(jiān)測(cè)變得越來越重要[1]。傳統(tǒng)人群監(jiān)測(cè)方法需要人工實(shí)時(shí)觀察視頻情況，導(dǎo)致公共場(chǎng)所人群事件監(jiān)測(cè)效率低[2]。為了提高人群監(jiān)測(cè)效率、降低監(jiān)測(cè)成本。通過借助計(jì)算機(jī)分析公共場(chǎng)所人群移動(dòng)行為，自動(dòng)檢測(cè)和識(shí)別公共場(chǎng)所存在的異常行為，從而提高公共場(chǎng)所的安全防控效率，因此人群移動(dòng)行為檢測(cè)成為模式識(shí)別、機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺等領(lǐng)域研究的新問題。

在人群移動(dòng)行為檢測(cè)中，雖然已經(jīng)出現(xiàn)許多理論知識(shí)和檢測(cè)方法，但是仍然存在許多技術(shù)難題：①人群移動(dòng)會(huì)伴隨跳躍、奔跑、肢體扭動(dòng)等帶來的不確定性影響因素[3]；②擁擠場(chǎng)景中的人群存在嚴(yán)重遮擋、倒影等噪聲；③在時(shí)域和空域?qū)θ巳阂苿?dòng)行為進(jìn)行分析[4]；④人群移動(dòng)過程中，人群密度、形狀、邊界等隨時(shí)間不斷變化[5]。同時(shí)群體移動(dòng)行為檢測(cè)比個(gè)體移動(dòng)行為檢測(cè)難度大，群體移動(dòng)行為表現(xiàn)為一種高層次的語(yǔ)義互動(dòng)[6]，為人群行為分析建模帶來巨大挑戰(zhàn)[7]。

2 群體研究

群體行為是生物界中一種極為普遍的現(xiàn)象，生物群體研究主要分為兩個(gè)領(lǐng)域：①宏觀領(lǐng)域；②微觀領(lǐng)域。宏觀領(lǐng)域主要針對(duì)人群、魚群、羊群、鳥群等群體進(jìn)行研究[8]；微觀領(lǐng)域主要針對(duì)菌落進(jìn)行研究。隨著人們對(duì)公共安全關(guān)注度的不斷提高，人群移動(dòng)行為分析成為熱點(diǎn)問題。人群移動(dòng)行為分析分為社會(huì)學(xué)范疇和計(jì)算機(jī)視覺的研究；在社會(huì)學(xué)范疇中，個(gè)體的運(yùn)動(dòng)往往與周圍群體存在一定聯(lián)系[6][8-10]，個(gè)體行為會(huì)受到周圍人群的影響，即在群體活動(dòng)中不存在個(gè)體自主行為；在計(jì)算機(jī)視覺領(lǐng)域中，大多數(shù)研究將群體結(jié)構(gòu)進(jìn)行細(xì)化，從個(gè)體之間的相互作用出發(fā)，將個(gè)體之間的社會(huì)關(guān)系進(jìn)行空間量化，從而對(duì)群體移動(dòng)行為進(jìn)行客觀描述，同時(shí)對(duì)存在不同社會(huì)關(guān)系的人群進(jìn)行檢測(cè)分析。在計(jì)算機(jī)視覺領(lǐng)域中，經(jīng)過長(zhǎng)期發(fā)展與積淀，出現(xiàn)許多經(jīng)典的人群移動(dòng)行為檢測(cè)方法。人群移動(dòng)行為檢測(cè)方法分為：①基于群體組的檢測(cè)方法；②基于視圖的檢測(cè)方法。

基于群體組檢測(cè)的方法包括：①粒子法；②軌跡分析法[10]。粒子法是通過觀察圖像上驅(qū)動(dòng)粒子的流動(dòng)來檢測(cè)人群移動(dòng)，Mehran等人[11]通過社會(huì)力模型應(yīng)計(jì)算粒子之間的相互作用力，根據(jù)作用力大小對(duì)人群異常區(qū)域進(jìn)行定位；Raghavendra等人[12]采用粒子群算法對(duì)社會(huì)力模型進(jìn)行優(yōu)化，并通過分割算法對(duì)人群異常區(qū)域進(jìn)行分割；Ullah等人[13]提出一種流體動(dòng)力學(xué)模型對(duì)人群進(jìn)行檢測(cè)。軌跡分析法是對(duì)人群移動(dòng)軌跡進(jìn)行聚類分析，Cui等人[14]采用K-means算法對(duì)人群移動(dòng)軌跡點(diǎn)進(jìn)行聚類，從而將人群分成不同的群組；Mousavi等人[15]提出一種增強(qiáng)定向軌跡直方圖方法，對(duì)公共場(chǎng)所異常人群進(jìn)行檢測(cè)。Zhou等人[16]提出一種混合動(dòng)力模型模擬人群行為，再通過移動(dòng)軌跡判斷人群在過去某時(shí)刻的行為和預(yù)測(cè)即將發(fā)生的行為。雖然基于群組檢測(cè)的方法能夠檢測(cè)到場(chǎng)景中的不同人群，但是由于人群處于不斷移動(dòng)的狀態(tài)，群組形態(tài)隨時(shí)間不斷不斷變化，因此群組關(guān)系難以確定，導(dǎo)致該類方法檢測(cè)精度不高。

基于視圖的檢測(cè)方法主要是對(duì)視頻圖像進(jìn)行聚類，視圖聚類又分為單視圖聚類和多視圖聚類。Peng等人[17]針對(duì)場(chǎng)景中人群存在遮擋問題，提出一種貝葉斯網(wǎng)絡(luò)模型，用于多攝像頭人群檢測(cè)。Li等人[18]設(shè)計(jì)一種人群移動(dòng)的個(gè)體結(jié)構(gòu)特征，并提出一種自加權(quán)多視圖聚類方法對(duì)個(gè)體結(jié)構(gòu)特征進(jìn)行聚類，隨后Wang等人[10]又提出一種基于自加權(quán)多視圖聚類的人群檢測(cè)框架。雖然該類方法可對(duì)場(chǎng)景中的人群進(jìn)行有效聚類，但是該類方法需要通過先驗(yàn)知識(shí)設(shè)定閾值，并且算法結(jié)構(gòu)、參數(shù)較多，所以該類方法在實(shí)際應(yīng)用中難以實(shí)現(xiàn)。

針對(duì)上述問題，本文對(duì)譜聚類算法進(jìn)行改進(jìn)，提出一種基于改進(jìn)譜聚類的人群移動(dòng)行為檢測(cè)算法。首先構(gòu)造一種新的鄰接矩陣作為譜聚類算法的輸入?yún)?shù)；然后構(gòu)造一種新的拉普拉斯矩陣，并隨機(jī)選取拉普拉斯四個(gè)特征值組成特征向量，最后采用K-means算法對(duì)特征向量進(jìn)行聚類得到人群簇。通過在各大國(guó)際公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果證明了本文提出算法的有效性。

3 譜聚類算法

譜聚類算法是一種基于圖論的聚類方法，該算法具有結(jié)構(gòu)簡(jiǎn)單、計(jì)算量小、容易實(shí)現(xiàn)、魯棒性強(qiáng)等優(yōu)點(diǎn)，在對(duì)復(fù)雜數(shù)據(jù)聚類時(shí)，也能得到較高聚類精度。因此本文采用譜聚類算法對(duì)人群進(jìn)行聚類。

在譜聚類算法中，將人群場(chǎng)景圖像視為一張無(wú)向加權(quán)圖I(λ，E)，其中λ是數(shù)據(jù)點(diǎn)λ1，λ2，…，λn的集合，E是連接任意兩個(gè)數(shù)據(jù)點(diǎn)的連接線e1，e2，…，en的集合，ωi，j(i，j∈λ)是e1，e2，…，en所對(duì)應(yīng)的權(quán)值[20]，即i，j兩點(diǎn)的相似度，具體定義為

(1)

由此可得到相似度矩陣W∈Rn×n，而度矩陣D則定義為

(2)

由相似度矩陣W和度矩陣D可構(gòu)建拉普拉斯矩陣L∈Rn×n，其具體定義為[20]

(3)

在實(shí)際數(shù)據(jù)聚類過程中，還需對(duì)拉普拉斯矩陣L進(jìn)行標(biāo)準(zhǔn)化，標(biāo)準(zhǔn)化后的拉普拉斯矩陣為

(4)

對(duì)標(biāo)準(zhǔn)化后的拉普拉斯矩陣L*求K∈R個(gè)特征向量F=(f1，f2，…，fk)，其中K的大小為類別數(shù)。再次對(duì)由K1個(gè)特征向量F進(jìn)行標(biāo)準(zhǔn)化后得到一個(gè)n×k1維的特征矩陣M，然后選擇聚類算法對(duì)矩陣M進(jìn)行聚類，得到聚類維數(shù)K2，即K2為人群類別數(shù)。

4 人群聚類

人群在移動(dòng)過程中會(huì)產(chǎn)生時(shí)空相關(guān)結(jié)構(gòu)，這種結(jié)構(gòu)被稱為集體流形[8]。在文獻(xiàn)[8]中首先定義個(gè)體行為在其鄰域內(nèi)的相似性，即行為一致性。當(dāng)個(gè)體j在鄰域i中，在t時(shí)刻j∈N(i)時(shí)，相似性定義為

(5)

其中δt(i，j)∈[0，1]，Ct(i，j)是i和j在t時(shí)刻的速度相關(guān)系數(shù)。由于當(dāng)i和j為兩個(gè)獨(dú)立個(gè)體時(shí)，即不在同一鄰域內(nèi)的兩個(gè)個(gè)體之間，其行為存在不確定性，長(zhǎng)度為l的路徑行為相似性定義為

υl(i，j)=υγl1(i，j)+υγl2(i，j)+…+υγln(i，j)

(6)

其中pl為所有長(zhǎng)度為l的路徑集合，γlk∈pl(k=1，2，…，n)為特定路徑，υγlk(i，j)為特定路徑γlk的相似性度量。式(6)為長(zhǎng)度為l的路徑相似度，則在l的尺度上將i的集體性定義為

ψl(i)=υl(i，c1)+υl(i，c2)+…+υl(i，cn)

(7)

其中cn為個(gè)體。由此得到群體集體性

ψl=E((ψl(i))

(8)

為將所有路徑上的個(gè)體集體性與群體集體性進(jìn)行擬合，因此定義一個(gè)生成函數(shù)用于度量總體相似性

φi，j=z1υ1(i，j)+z2υ2(i，j)+…+znυn(i，j)

(9)

其中zn為路徑的權(quán)重。在給出了群體相似性和群體集體性的度量定義，在此基礎(chǔ)之上可得到一個(gè)η矩陣

(10)

其中W是鄰接矩陣，r是拓?fù)浞秶?，?duì)η進(jìn)行閾值化處理，去除集體性較低的粒子保留集體性較高的粒子，將運(yùn)動(dòng)中的群體劃分為不同類。

5 本文算法

為解決場(chǎng)景中移動(dòng)人群存在遮擋和倒影問題，本文提出一種基于改進(jìn)譜聚類的人群移動(dòng)行為檢測(cè)方法。首先，本文提出一種鄰接矩陣構(gòu)建方法和拉普拉斯矩陣構(gòu)建方法，將鄰接矩陣作為譜聚類的輸入?yún)?shù)；然后，隨機(jī)選取拉普拉斯矩陣的四個(gè)最小特征值組成特征向量；最后，通過K-means算法對(duì)特征向量進(jìn)行聚類，得到人群聚類數(shù)。

5.1 鄰接矩陣

在構(gòu)造鄰接矩陣之前需要構(gòu)建一個(gè)相似性矩陣，其中相似性矩陣的構(gòu)建方法主要有三種[19]：

1)ε-鄰接法，相似性矩陣定義為

(11)

其中ε為個(gè)體間的距離，由于所有dij值都相同，因此ε-鄰接圖法被稱為未加權(quán)相似性矩陣。

2)k-最近鄰法，相似性矩陣定義為

(12)

其中U(i，j)是i和j的鄰域。

3)全連接法，相似性矩陣定義為

(13)

其中ωk∈ωi，j。

由上述三種方法定義的相似性矩陣信息損失較多。式(6)為文獻(xiàn)[8]定義路徑相似度矩陣，由此可得到度矩陣

(14)

由D(i，j)得到鄰接矩陣M(i，j)，則鄰接矩陣可以表示為[8]

M(i，j)=υl(i，j)×M(i，j)

(15)

由式(15)得到的鄰接矩陣是一個(gè)奇異矩陣，在計(jì)算時(shí)無(wú)法得到確定值，從而導(dǎo)聚類失敗，針對(duì)這一問題本文把式(15)進(jìn)行改進(jìn)，把鄰接矩陣定義為

M1(i，j)=[υl(i，j)×M(i，j)]+I1(i，j)

(16)

其中I1(i，j)為一個(gè)元素全為1的矩陣。本文將式(16)作為譜聚類算法的輸入。

5.2 K-means聚類

K-means算法在數(shù)據(jù)聚類中表現(xiàn)出優(yōu)越的性能，在對(duì)復(fù)雜數(shù)據(jù)進(jìn)行聚類時(shí)也能得到較高聚類精度，因此本文采用K-means算法作為譜聚類的聚類模塊。

在數(shù)據(jù)聚類中，K-means將屬于同一類中的數(shù)據(jù)點(diǎn)間距離最小化，將不同類之間的數(shù)據(jù)點(diǎn)距離最大化。在人群聚類中，將人群劃分為C={C1，C2，…，Ck}，Ck∈N*，Ck∈Ν*，所有人群中的個(gè)體間距離均值為

(17)

其中dc為距離之和，由式(17)可得到人群的聚類函數(shù)[20]

(18)

其中cin為任意人群，xcin為任意人群cin的個(gè)體數(shù)。

在得到K-means算法的聚類函數(shù)之后，需要構(gòu)建拉普拉斯矩陣作為輸入?yún)?shù)。本文提出一種拉普拉斯矩陣構(gòu)造方法，即定義拉普拉斯矩陣為

L(i，j)=I(i，j)-D(i，j)-M1(i，j)

(19)

其中I(i，j)為一個(gè)單位矩陣，在得到拉普拉斯矩陣之后，首先，隨機(jī)選取拉普拉斯矩陣的四個(gè)最小特征值組成特征向量；然后，通過人群聚類函數(shù)(式(18))對(duì)特征向量進(jìn)行聚類，得到人群聚類數(shù)；最后，聚類結(jié)果將人群聚類數(shù)映射至視頻幀圖像，實(shí)現(xiàn)對(duì)場(chǎng)景中移動(dòng)人群聚類。

5.3 改進(jìn)譜聚類人群檢測(cè)算法

為更加形象說明本文提出算法的實(shí)現(xiàn)過程，因此繪制了本文算法結(jié)構(gòu)流程圖。算法結(jié)構(gòu)流程如圖1所示。

圖1 改進(jìn)譜聚類算法

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

本文提出改進(jìn)譜聚類人群移動(dòng)行為檢測(cè)算法，為驗(yàn)證本文提出算法的有效性，本文通過在CCD(CUHK Crowd Dataset)[21]，CMD(Collective Motion Database)[8]，MPT(MPT-20×100)[9]三個(gè)數(shù)據(jù)進(jìn)行驗(yàn)證，選取ROC、AUC、Entropy、Purity、F-Measure指標(biāo)，并與CF(Coherent Filtering)[22]，MCC(Measuring Crowd Collectiveness)[8]算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，本文算法具有更好的聚類性能。

6.1 聚類評(píng)價(jià)

本文采用譜聚類算法對(duì)場(chǎng)景人群進(jìn)行聚類，首先提出一種新的鄰接矩陣和拉普拉斯矩陣，然后選取拉普拉斯矩陣的四個(gè)最小特征值組成特征向量，最后通過K-means算法對(duì)特征向量進(jìn)行聚類。為綜合評(píng)價(jià)本文提出算法的有效性，將本文算法與其它算法在各種公開數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比。

圖2為本文算法與其它算法在CCD、CMD、MPT三個(gè)國(guó)際公開數(shù)據(jù)數(shù)據(jù)集上的人群聚類視覺效果，其中不同顏色所覆蓋的區(qū)域代表不同的人群。由聚類結(jié)果可知，本文提出算法可對(duì)不同場(chǎng)景中不同密度的人群進(jìn)行有效聚類，并能夠檢測(cè)到場(chǎng)景中的所有人群，實(shí)驗(yàn)結(jié)果表明，本文提出算法具有優(yōu)越的人群檢測(cè)性能和人群聚類性能。

圖2 人群聚類效果

表1統(tǒng)計(jì)了本文算法與其它算法對(duì)場(chǎng)景中人群的檢測(cè)點(diǎn)數(shù)，本文提出算法所檢測(cè)到的點(diǎn)數(shù)比CF算法高618個(gè)點(diǎn)，比MCC算法高178個(gè)點(diǎn)，結(jié)果表明本文提出算法能夠檢測(cè)場(chǎng)景中的大多數(shù)人群，證明了本文算法優(yōu)越的檢測(cè)性能。

表1 各種算法聚類指標(biāo)

6.2 算法對(duì)比

為綜合證明本文提出算法的優(yōu)越性能，將本文提出的改進(jìn)譜聚類算法與其他人群聚類算法在CCD數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并對(duì)比人群聚類純度(Purity)和FM值(F-Measure)指標(biāo)。

表1為本文提出的改進(jìn)譜聚類算法與其他人群聚類算法在CCD數(shù)據(jù)集上的各項(xiàng)指標(biāo)值。加粗部分為本文算法所得結(jié)果，本文算法的Purity值比MCC算法高0.067，F(xiàn)-Measure值比MCC算法高0.16，雖然本文算法的Purity值比CF算法低0.042，但是本文算法的F-Measure值比CF算法高0.093，這些結(jié)果都證明了本文提出算法的有效性。

為進(jìn)一步證明本文算法的有效性，對(duì)本文提出的改進(jìn)譜聚類算法和其他人群聚類算法進(jìn)行AUC值、人群檢測(cè)數(shù)、聚類數(shù)對(duì)比。表2為各種算法的聚類AUC值，加粗部分為本文聚類結(jié)果的AUC值，本文提出算法的AUC值比CF算法高0.111，比MCC算法高0.004。

表2 各種算法AUC值

表3統(tǒng)計(jì)了本文提出的改進(jìn)譜聚類算法與其他人群聚類算法對(duì)場(chǎng)景中人群的檢測(cè)點(diǎn)數(shù)，本文提出的改進(jìn)譜聚類算法所檢測(cè)到的點(diǎn)數(shù)比CF算法高618個(gè)點(diǎn)，比MCC算法高178個(gè)點(diǎn)，結(jié)果表明本文提出算法能夠檢測(cè)場(chǎng)景中的大多數(shù)人群，證明了本文算法的有效性。

表3 各種算法人群檢測(cè)數(shù)

圖3為統(tǒng)計(jì)了本文提出的改進(jìn)譜聚類算法與其他人群聚類算法的人群類別數(shù)，本文提出算法對(duì)人群聚類所得類別數(shù)與groundtruth最接近，僅比groundtruth高出1個(gè)類別，CF算法比groundtruth高出2個(gè)類別，MCC算法比groundtruth高出10個(gè)類別。這進(jìn)一步證明了本文算法的有效性。

圖3 各種算法聚類數(shù)

7 結(jié)論

針對(duì)人群場(chǎng)景人群存在遮擋和倒影問題，本文提出一種改進(jìn)譜聚類的人群移動(dòng)行為檢測(cè)方法。首先構(gòu)造一種新的鄰接矩陣和拉普拉斯矩陣，將構(gòu)造的鄰接矩陣作為譜聚類的輸入?yún)?shù)，然后選取拉普拉斯矩陣的四個(gè)最小特征值組成特征向量，最后采用K-means算法對(duì)特征向量進(jìn)行聚類，通過在公開數(shù)據(jù)集數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與目前主流算法進(jìn)行對(duì)比。本文通過對(duì)實(shí)驗(yàn)結(jié)果的定性和定量分析，結(jié)果證明了本文提出算法的有效性。在未來研究工作中，將繼續(xù)探索人群移動(dòng)行為檢測(cè)算法的創(chuàng)新與優(yōu)化。