基于改進譜聚類的人群移動行為檢測

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

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

1 引言

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

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

2 群體研究

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

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

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

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

3 譜聚類算法

譜聚類算法是一種基于圖論的聚類方法，該算法具有結構簡單、計算量小、容易實現、魯棒性強等優點，在對復雜數據聚類時，也能得到較高聚類精度。因此本文采用譜聚類算法對人群進行聚類。

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

(1)

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

(2)

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

(3)

在實際數據聚類過程中，還需對拉普拉斯矩陣L進行標準化，標準化后的拉普拉斯矩陣為

(4)

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

4 人群聚類

人群在移動過程中會產生時空相關結構，這種結構被稱為集體流形[8]。在文獻[8]中首先定義個體行為在其鄰域內的相似性，即行為一致性。當個體j在鄰域i中，在t時刻j∈N(i)時，相似性定義為

(5)

其中δt(i，j)∈[0，1]，Ct(i，j)是i和j在t時刻的速度相關系數。由于當i和j為兩個獨立個體時，即不在同一鄰域內的兩個個體之間，其行為存在不確定性，長度為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)

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

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

(9)

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

(10)

其中W是鄰接矩陣，r是拓撲范圍，對η進行閾值化處理，去除集體性較低的粒子保留集體性較高的粒子，將運動中的群體劃分為不同類。

5 本文算法

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

5.1 鄰接矩陣

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

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

(11)

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

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

(12)

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

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

(13)

其中ωk∈ωi，j。

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

(14)

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

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

(15)

由式(15)得到的鄰接矩陣是一個奇異矩陣，在計算時無法得到確定值，從而導聚類失敗，針對這一問題本文把式(15)進行改進，把鄰接矩陣定義為

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

(16)

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

5.2 K-means聚類

K-means算法在數據聚類中表現出優越的性能，在對復雜數據進行聚類時也能得到較高聚類精度，因此本文采用K-means算法作為譜聚類的聚類模塊。

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

(17)

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

(18)

其中cin為任意人群，xcin為任意人群cin的個體數。

在得到K-means算法的聚類函數之后，需要構建拉普拉斯矩陣作為輸入參數。本文提出一種拉普拉斯矩陣構造方法，即定義拉普拉斯矩陣為

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

(19)

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

5.3 改進譜聚類人群檢測算法

為更加形象說明本文提出算法的實現過程，因此繪制了本文算法結構流程圖。算法結構流程如圖1所示。

圖1 改進譜聚類算法

6 實驗結果與分析

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

6.1 聚類評價

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

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

圖2 人群聚類效果

表1統計了本文算法與其它算法對場景中人群的檢測點數，本文提出算法所檢測到的點數比CF算法高618個點，比MCC算法高178個點，結果表明本文提出算法能夠檢測場景中的大多數人群，證明了本文算法優越的檢測性能。

表1 各種算法聚類指標

6.2 算法對比

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

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

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

表2 各種算法AUC值

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

表3 各種算法人群檢測數

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

圖3 各種算法聚類數

7 結論

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