楊玉成，張 乾，2，邵定琴，岳詩琴

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

1 引言

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

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

2 群體研究

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

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

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

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

3 譜聚類算法

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

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

(1)

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

(2)

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

(3)

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

(4)

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

4 人群聚類

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

(5)

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

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

(6)

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

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

(7)

其中cn為個體。由此得到群體集體性

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

(8)

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

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

(9)

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

(10)

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

5 本文算法

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

5.1 鄰接矩陣

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

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

(11)

其中ε為個體間的距離，由于所有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)得到的鄰接矩陣是一個奇異矩陣，在計算時無法得到確定值，從而導(dǎo)聚類失敗，針對這一問題本文把式(15)進(jìn)行改進(jìn)，把鄰接矩陣定義為

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

(16)

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

5.2 K-means聚類

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

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

(17)

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

(18)

其中cin為任意人群，xcin為任意人群cin的個體數(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)為一個單位矩陣，在得到拉普拉斯矩陣之后，首先，隨機選取拉普拉斯矩陣的四個最小特征值組成特征向量；然后，通過人群聚類函數(shù)(式(18))對特征向量進(jìn)行聚類，得到人群聚類數(shù)；最后，聚類結(jié)果將人群聚類數(shù)映射至視頻幀圖像，實現(xiàn)對場景中移動人群聚類。

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

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

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

6 實驗結(jié)果與分析

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

6.1 聚類評價

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

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

圖2 人群聚類效果

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

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

6.2 算法對比

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

表1為本文提出的改進(jìn)譜聚類算法與其他人群聚類算法在CCD數(shù)據(jù)集上的各項指標(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)一步證明本文算法的有效性，對本文提出的改進(jìn)譜聚類算法和其他人群聚類算法進(jìn)行AUC值、人群檢測數(shù)、聚類數(shù)對比。表2為各種算法的聚類AUC值，加粗部分為本文聚類結(jié)果的AUC值，本文提出算法的AUC值比CF算法高0.111，比MCC算法高0.004。

表2 各種算法AUC值

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

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

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

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

7 結(jié)論

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