基于多層自適應(yīng)聚類模型的密集人群分群檢測(cè)算法

邵 潔, 趙 倩

(上海電力學(xué)院 電子與信息工程學(xué)院, 上海 210090)

?

基于多層自適應(yīng)聚類模型的密集人群分群檢測(cè)算法

邵 潔, 趙 倩

(上海電力學(xué)院 電子與信息工程學(xué)院, 上海 210090)

針對(duì)存在更復(fù)雜運(yùn)動(dòng)模式的無序運(yùn)動(dòng)人群密集場(chǎng)景,提出了一種基于多層自適應(yīng)聚類模型的分群檢測(cè)算法.以基于高斯混合模型的背景去除算法和自適應(yīng)初始化聚類算法為核心,通過建立多層自適應(yīng)聚類模型實(shí)現(xiàn)密集人群的分群檢測(cè).實(shí)驗(yàn)數(shù)據(jù)庫(kù)選用了大量真實(shí)室內(nèi)外密集人群運(yùn)動(dòng)場(chǎng)景視頻,并通過大量對(duì)比實(shí)驗(yàn)驗(yàn)證了算法的有效性、可靠性和優(yōu)越性.

密集人群; 分群檢測(cè); 自適應(yīng)聚類; 多層聚類模型

密集場(chǎng)景中的人群運(yùn)動(dòng)分析和異常檢測(cè)是當(dāng)前智能監(jiān)控研究領(lǐng)域的熱點(diǎn)課題,也是計(jì)算機(jī)視覺和智能交通研究的重要方向之一.它在保障社會(huì)公共安全、提高城市工程建設(shè)和交通規(guī)劃的科學(xué)性等方面具有重要的研究?jī)r(jià)值.

密集人群運(yùn)動(dòng)場(chǎng)景從宏觀上可分為有序運(yùn)動(dòng)場(chǎng)景和無序運(yùn)動(dòng)場(chǎng)景兩種類型.有序運(yùn)動(dòng)場(chǎng)景中主要存在遵從一定規(guī)律運(yùn)動(dòng)的人群,大多因?yàn)橹骺陀^規(guī)則的聯(lián)合制約,如在狹窄的走道中被限制行進(jìn)方向的人群、具有共同行為意愿的人群;參加馬拉松運(yùn)動(dòng)、遵從單項(xiàng)交通信號(hào)標(biāo)志運(yùn)動(dòng)的人流等.然而在更多公共場(chǎng)景中,人群普遍呈現(xiàn)一種無規(guī)律運(yùn)動(dòng)的組合形式,即無序運(yùn)動(dòng)場(chǎng)景,如寬敞區(qū)域中散亂的人群.由于大多數(shù)的人員密集場(chǎng)所均充斥著無序的運(yùn)動(dòng)人群,針對(duì)無序場(chǎng)景的運(yùn)動(dòng)分析具有更高的實(shí)用價(jià)值,但其更加復(fù)雜的運(yùn)動(dòng)屬性大大增加了研究的難度,因此研究成果較少.本文將專注于無序運(yùn)動(dòng)密集場(chǎng)景的運(yùn)動(dòng)分群檢測(cè).

密集人群運(yùn)動(dòng)分析通常采用自下而上和自上而下兩種算法思路.自下而上是指將密集人群看作大量個(gè)體的集合,首先從個(gè)體分析的角度出發(fā)提取其運(yùn)動(dòng)速度和方向,再將其組合得到整體的運(yùn)動(dòng).如GE W等人[1]以多目標(biāo)檢測(cè)和跟蹤算法為基礎(chǔ),分別得到每個(gè)行人的運(yùn)動(dòng)軌跡,再進(jìn)行從個(gè)體到整體的運(yùn)動(dòng)模式分析.從算法設(shè)計(jì)角度而言,該方法在低密度人群運(yùn)動(dòng)分析中能夠得到理想的效果,但這種有效性將隨著人群密度的增加而迅速降低.

自上而下的方法則是以人群整體為出發(fā)點(diǎn),依據(jù)運(yùn)動(dòng)屬性將其劃分為一系列具有相似運(yùn)動(dòng)的小團(tuán)體.有研究數(shù)據(jù)表明,群體中70%的行人并非為單獨(dú)行走個(gè)體,而是屬于某個(gè)“三五成群”的小團(tuán)體[2].因此,分群檢測(cè)是通過自上而下的分析方法實(shí)現(xiàn)對(duì)密集群體中存在相似的運(yùn)動(dòng)團(tuán)體的劃分.自上而下分析的基礎(chǔ)是首先獲取群體的整體運(yùn)動(dòng)特征,目前普遍采用的方法是通過采集點(diǎn)的位移來表征人群的運(yùn)動(dòng).

常見的應(yīng)用于密集群體的運(yùn)動(dòng)點(diǎn)采集方法有兩類:一類是粒子流算法,如光流(Optical flow)[3]、線性流(Streakline flow)[4]等;另一類是特征點(diǎn)匹配算法,如HOG[5]和 KLT[6-7]等.如WANG W等人[3]利用光流建立了一個(gè)連續(xù)運(yùn)動(dòng)判別域,再利用兩級(jí)聚類算法實(shí)現(xiàn)對(duì)連續(xù)運(yùn)動(dòng)區(qū)域的語義分析,即按照連續(xù)運(yùn)動(dòng)類型劃分實(shí)現(xiàn)區(qū)域分析.實(shí)驗(yàn)顯示,其算法能夠達(dá)到較高的運(yùn)動(dòng)分割正確率.但該算法僅針對(duì)連續(xù)運(yùn)動(dòng)進(jìn)行了研究,即在一定時(shí)間的某區(qū)域內(nèi)運(yùn)動(dòng)保持不變,文中并未提供非連續(xù)運(yùn)動(dòng)場(chǎng)景的實(shí)驗(yàn)結(jié)果.ZHOU B等人[6]提出了一種更適用于一般場(chǎng)景的群體運(yùn)動(dòng)分析算法——一致性運(yùn)動(dòng)濾波(Coherent Filtering,CF).該算法在提取特征點(diǎn)軌跡的基礎(chǔ)上,計(jì)算其距離與速度的相關(guān)性,完成一致運(yùn)動(dòng)鄰域不變性特征描述,再由此建立個(gè)體的局部一致性運(yùn)動(dòng)關(guān)系,最終利用一致性運(yùn)動(dòng)濾波算法實(shí)現(xiàn)密集群體的分群檢測(cè).此后,作為CF算法的延伸,SHAO J等人[7]又提出了一致性轉(zhuǎn)換先驗(yàn)信息(Collective Transition Prior,CT)的概念,并認(rèn)為群體中的行人運(yùn)動(dòng)是由有限量的CT信息決定的.

受到CF和CT的啟發(fā),本文提出的算法也將以特征點(diǎn)運(yùn)動(dòng)軌跡描述為基礎(chǔ)展開.但另一方面,考慮到CF及CT算法需要背景圖像作為先驗(yàn)信息,本文引入了一種前景自動(dòng)提取策略;且區(qū)別于CF的由點(diǎn)及面的點(diǎn)分類思路,又引入了方向特征,提出了面向整體的多層聚類算法實(shí)現(xiàn)分群檢測(cè).本算法無論在特征提取還是聚類過程中均不需要任何先驗(yàn)信息,實(shí)現(xiàn)了對(duì)多重復(fù)雜無序運(yùn)動(dòng)群體分群檢測(cè)的自動(dòng)實(shí)現(xiàn).通過引入背景去除策略,不僅能夠自動(dòng)去除背景中的噪聲,還能夠?qū)崿F(xiàn)前景區(qū)域的關(guān)鍵點(diǎn)自動(dòng)提取.此外,本文還改進(jìn)了一種自適應(yīng)聚類算法,并由此建立多層聚類模型,通過融合關(guān)鍵點(diǎn)的時(shí)空特征描述,實(shí)現(xiàn)聚類分割,完成群體的分群檢測(cè).

1 分群檢測(cè)算法

圖1給出了整個(gè)算法流程.算法分為預(yù)處理和多層聚類分群檢測(cè)兩個(gè)步驟.在預(yù)處理中,利用基于高斯混合模型[8]的背景去除算法將前景和背景分離,得到如圖1所示的白色前景部分,再在前景區(qū)域進(jìn)行Harris特征點(diǎn)檢測(cè),在圖1中采用黑色點(diǎn)標(biāo)注.經(jīng)過多幀KLT點(diǎn)跟蹤算法得到運(yùn)動(dòng)軌跡.多層聚類模型針對(duì)KLT特征點(diǎn)軌跡提取的時(shí)空特征進(jìn)行多層次聚類,每層引入自適應(yīng)聚類算法實(shí)現(xiàn).

與以K-means為代表的傳統(tǒng)聚類算法相區(qū)別,自適應(yīng)聚類算法通過計(jì)算特征參數(shù)自動(dòng)判決得到聚類中心的位置和個(gè)數(shù),實(shí)現(xiàn)特征點(diǎn)分類,由此實(shí)現(xiàn)運(yùn)動(dòng)區(qū)域的分群檢測(cè).

圖1 算法流程

1.1 預(yù)處理

高斯混合模型被廣泛應(yīng)用于多目標(biāo)檢測(cè)和跟蹤的研究中,將其引入密集群體的運(yùn)動(dòng)前景檢測(cè),不僅能夠得到較為準(zhǔn)確的前景區(qū)域,還能夠消除來源于背景區(qū)域的噪聲干擾.在背景去除中檢測(cè)得到的過小的前景區(qū)域?qū)⒈蛔鳛樵肼暈V除.在自動(dòng)獲取的前景區(qū)域中,首先提取Harris角點(diǎn),再利用KLT跟蹤器實(shí)現(xiàn)角點(diǎn)的連續(xù)跟蹤,以得到其運(yùn)動(dòng)軌跡.每個(gè)具有有效跟蹤軌跡的角點(diǎn)被稱為特征點(diǎn),編號(hào)為P={1,2,3,…,i,…,m}.每一個(gè)特征點(diǎn)i采用(si,di,ti)表示,其中si=(x,y),為特征點(diǎn)i坐標(biāo),di為ti幀時(shí)特征點(diǎn)軌跡在最近連續(xù)n幀的運(yùn)動(dòng)方向,di∈[0,2π).

1.2 自適應(yīng)初始化聚類算法

K-means算法是最為廣泛應(yīng)用的聚類算法之一[9].盡管如此,K-means仍存在一些缺陷,如需要明確的聚類個(gè)數(shù)為先驗(yàn)信息;聚類結(jié)果對(duì)聚類中心點(diǎn)初始化位置很敏感等[10].針對(duì)這些問題,文獻(xiàn)[11]提出了一種改進(jìn)的自適應(yīng)初始化聚類算法.算法基于以下兩個(gè)觀測(cè)條件:一是聚類中心往往處于較高局部密度區(qū)域;二是中心與中心之間通常具有相對(duì)較大距離.因此,以特征數(shù)據(jù)局部密度和相對(duì)距離為參數(shù),作為特征數(shù)據(jù)聚類中心判別的依據(jù).本文對(duì)該算法進(jìn)行了改進(jìn),加入了參數(shù)決策機(jī)制.首先,假設(shè)待聚類數(shù)據(jù)集為χ={x1,x2,x3,…,xn},則xi的局部密度表示為ψ(xi),xi與{xj|ψ(xj)>ψ(xi)}的最小距離表示為ξ(xi).假設(shè)Γψ為數(shù)據(jù)間的距離閾值,則可將ψ(xi)定義為:

(1)

由式(1)可以看出,ψ(xi)為與xi距離小于Γψ的數(shù)據(jù)個(gè)數(shù).統(tǒng)計(jì)xi與χ中所有局部密度大于xi的數(shù)據(jù)間距離,采用最小值存入ξ(xi):

(2)

針對(duì)局部密度最大的數(shù)據(jù),定義ξ(xi)為與其他數(shù)據(jù)間的最大值:

(3)

(4)

(5)

滿足下列條件的數(shù)據(jù)則為聚類中心(CT為參數(shù)閾值):

c=xi

(6)

在確定聚類中心后,依據(jù)最近距離原則完成聚類.

1.3 多層自適應(yīng)聚類模型

圖2 多層聚類模型結(jié)果

2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)測(cè)試數(shù)據(jù)庫(kù)由CUHK密集群體數(shù)據(jù)集[7]和課題組自行收集建立的數(shù)據(jù)集兩個(gè)數(shù)據(jù)集組成,數(shù)據(jù)集中的密集場(chǎng)景中包含各種不同人群密度和多種運(yùn)動(dòng)類型.本算法采用Matlab實(shí)現(xiàn),工作于Intel i5 CPU,4 G RAM,能夠?qū)崿F(xiàn)5幀/s的計(jì)算速度.若將算法移植到C++語言環(huán)境并進(jìn)行算法優(yōu)化,預(yù)期可以達(dá)到實(shí)時(shí)運(yùn)算效果.

2.1 典型密集場(chǎng)景分群檢測(cè)實(shí)驗(yàn)結(jié)果

圖3展示了本算法針對(duì)兩個(gè)真實(shí)拍攝的密集場(chǎng)景視頻的分群檢測(cè)結(jié)果.不同顏色的點(diǎn)的聚類對(duì)應(yīng)不同的分群團(tuán)體.圖3a所示場(chǎng)景1為北京某胡同.在該場(chǎng)景中,雙向行走的人流混雜在狹窄的胡同中,其中還混有騎自行車和佇立觀望的人.由于拍攝角度較低造成人群混疊現(xiàn)象嚴(yán)重,個(gè)體間隔不明顯,場(chǎng)景中運(yùn)動(dòng)類型的復(fù)雜性更加大了分群檢測(cè)的難度.從圖3b可看出,場(chǎng)景中群體被分為13個(gè)小團(tuán)體,處于圖像右側(cè)中部擦肩而過的不同人群被正確區(qū)分(見深灰點(diǎn)和淺灰點(diǎn)集合).但圖中存在一處錯(cuò)誤檢測(cè),即圖中偏上部分騎自行車的人被錯(cuò)誤的分割為上下兩部分.圖3c所示場(chǎng)景2為廣場(chǎng)中采用俯視攝像頭拍攝的視頻畫面.圖3c中行人較為稀疏,但個(gè)體占像素面積大且行進(jìn)方向更為自由多樣.圖3d中群體被分割為10個(gè)小團(tuán)體,不同運(yùn)動(dòng)群體均被正確檢測(cè),但圖3d中左側(cè)偏上部分存在少量錯(cuò)誤檢測(cè)點(diǎn)(見深灰點(diǎn)集合所示).

圖3 典型密集場(chǎng)景分群檢測(cè)結(jié)果

2.2 比較與討論

本文通過計(jì)算特征點(diǎn)錯(cuò)誤率(Particle Error Rates,PER)和分群數(shù)量錯(cuò)誤率(Group Number Error,GNE)兩個(gè)指標(biāo)對(duì)不同實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比.

(7)

(8)

式中:Nwrong——圖中錯(cuò)誤劃分特征點(diǎn)個(gè)數(shù);Ntotal——圖中所有有效特征點(diǎn)個(gè)數(shù);Nd(t)——算法檢測(cè)得到的聚類中心個(gè)數(shù),即分群個(gè)數(shù);

Ngt(t)——實(shí)際分群個(gè)數(shù);

t——視頻幀數(shù).

表1給出了不同算法的統(tǒng)計(jì)比較結(jié)果,這一結(jié)果來源于隨機(jī)選擇數(shù)據(jù)庫(kù)中的20段真實(shí)場(chǎng)景視頻測(cè)試得到的平均值.由表1可以看出,多層聚類模型大大提高了最終的分群正確率.CF算法的計(jì)算所得平均ePER值與本算法相近,但eGNE值要遠(yuǎn)低于本文提出的算法.

表1 不同算法平均ePER和eGNE指標(biāo)比較 %

2.3 參數(shù)比較

式(6)中的閾值CT,在多層自適應(yīng)聚類模型中的第1層和第2層取不同值時(shí)對(duì)分群結(jié)果有極大的影響.為了測(cè)試得到最優(yōu)聚類結(jié)果,通過改變每層的CT值,針對(duì)20個(gè)密集人群運(yùn)動(dòng)視頻計(jì)算特征點(diǎn)錯(cuò)誤率和分群數(shù)量錯(cuò)誤率,得到的計(jì)算結(jié)果如表2所示.表2中,縱軸為第1層聚類采用的參數(shù)閾值,橫軸為第2層聚類參數(shù)閾值.

從表2可以看出,當(dāng)?shù)?層CT為0.9,第2層CT為0.7時(shí),可得到最優(yōu)ePER和eGNE組合值.CT值過低易導(dǎo)致不能正確劃分分群個(gè)數(shù),但隨著CT值的增加,也會(huì)產(chǎn)生過分類的情況,此時(shí),eGNE值會(huì)大幅降低.

表2 不同CT值時(shí)的ePER/eGNE值

3 結(jié) 語

分群檢測(cè)是密集群體運(yùn)動(dòng)分析最常見的基礎(chǔ)步驟,已有的分群檢測(cè)算法往往對(duì)群體運(yùn)動(dòng)類型有限制或需要依靠先驗(yàn)信息.專注于無序隨機(jī)運(yùn)動(dòng)密集場(chǎng)景的自動(dòng)分群檢測(cè)算法的實(shí)現(xiàn),通過將背景檢測(cè)算法與特征點(diǎn)跟蹤算法相結(jié)合得到密集運(yùn)動(dòng)區(qū)域的時(shí)空特征描述,在建立多層自適應(yīng)聚類模型的基礎(chǔ)上,實(shí)現(xiàn)多特征與聚類模型的融合,實(shí)現(xiàn)最終的分群檢測(cè).對(duì)大量真實(shí)密集運(yùn)動(dòng)場(chǎng)景視頻數(shù)據(jù)的實(shí)驗(yàn)驗(yàn)證表明,本算法不僅針對(duì)多種類型密集場(chǎng)景的分群檢測(cè)有效,并且優(yōu)于其他已有算法.

[1] GE W,COLLINS R T,RUBACK B.Automatically detecting the small group structure of a crowd[C]//IEEE Workshop on Applications of Computer Vision (WACV),Utah,USA,2010:1-8.

[2] MOUSSAID M,PEROZO N,GARNIER S,etal.The walking behavior of pedestrian social groups and its impact on crowd dynamics[J].PLoS ONE,2010,5(4):e10047.

[3] WANG W,LIN W,CHEN Y,etal.Finding coherent motions and semantic regions in crowd scenes:a diffusion and clustering approach[C]//Computer Vision ECCV,Lecture Notes in Computer Science,Zurich,Switzerland,2014:756-771.

[4] MEHRAN R,MOORE B E,SHAH M.A streakline representation of flow in crowded scenes[C]//Computer Vision ECCV,Lecture Notes in Computer Science.Heraklion,Crete,Greece,2010:439-452.

[5] GARATE C,BILINSKI P,BREMOND F.Crowd event recognition using HOG tracker[C]//Twelfth IEEE International Workshop on Performance Evaluation of Tracking and Surveillance,Snowbird,UT,United States,2009:1-6.

[6] ZHOU B,TANG X,WANG X.Measuring crowd collectiveness[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(8):1 586-1 599.

[7] SHAO J,LOY C C,WANG X.Scene-independent group profiling in crowd[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,Columbus,OH,USA,2014:2 227-2 234.

[8] ZIVKOVIC Z.Improved adaptive gaussian mixture model for background subtraction[C]//International Conference on Pattern Recognition,Cambridge,UK,2004:28-31.

[9] WU X D,KUMAR V,QUIVLAN J R,etal.Top 10 algorithms in data mining[J].Knowledge and Information Systems,2008,14(1):1-37.

[10] LIAO H,XIANG J,SUN W,etal.Adaptive initialization method based on spatial local information for k-means algorithm[J].Mathematical Problems in Engineering,2014:1-11.

[11] RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1 492-1 496.

(編輯 胡小萍)

Hierarchical Adaptive Clustering Based Group Detection in the Crowd

SHAO Jie, ZHAO Qian

(SchoolofElectronicsandInformationEngineering,ShanghaiUniversityofElectricPower,Shanghai200090,China)

A hierarchical adaptive clustering based group detection algorithm is proposed for the crowded scenes involving multiple complex motion modalities.Gaussian Mixture Models based background subtraction algorithm and the adaptive initialization clustering algorithm are the key to the algorithm.Group detection is implemented by merging spatiotemporal features of salient points into different layers of the model.Our dataset is built by varieties of in-door and out-door real scene videos.The proposed algorithm outperforms many other algorithms in terms of its effectiveness,reliability and superiority by experimental comparisons.

crowd; group detection; adaptive clustering; hierarchical clustering model

10.3969/j.issn.1006-4729.2017.01.020

2016-03-16

邵潔(1981-),女,博士,副教授,江蘇南京人.主要研究方向?yàn)橛?jì)算機(jī)視覺與智能監(jiān)控.E-mail:shaojie@shiep.edu.cn.

國(guó)家自然科學(xué)基金(61302151,61401268);上海市自然科學(xué)基金(13ZR1455100,15ZR1418400).

TP391.41

A

1006-4729(2017)01-0091-06