李　沖，　王　蓉，　陳　鵬

(中國(guó)人民公安大學(xué)警務(wù)信息工程學(xué)院， 北京　100038)

?

基于壓縮感知的人群密度估計(jì)方法研究

李沖，王蓉，陳鵬

(中國(guó)人民公安大學(xué)警務(wù)信息工程學(xué)院， 北京100038)

摘要實(shí)時(shí)監(jiān)測(cè)人群密度是預(yù)防群體性事件的有效手段之一。針對(duì)較高密度人群，提出一種基于壓縮感知的人群密度估計(jì)方法。首先，利用離散余弦變換和隨機(jī)高斯矩陣獲取壓縮感知測(cè)量值；然后利用主成分分析進(jìn)行降維處理，得到人群密度特征；最后利用支持向量機(jī)將人群密度分為中、高、很高3類。通過(guò)某中學(xué)校門口的視頻圖像進(jìn)行仿真實(shí)驗(yàn)，測(cè)試、比較、分析了該方法與經(jīng)典的基于紋理方法的實(shí)時(shí)性與準(zhǔn)確性。

關(guān)鍵詞人群密度估計(jì)； 壓縮感知； 主成分分析； 支持向量機(jī)

0引言

群體性事件以及人群擁擠往往會(huì)危及人的生命安全，一旦發(fā)生事故就會(huì)造成很大損失。但是，僅僅依靠傳統(tǒng)的人防及技防手段并不能實(shí)現(xiàn)對(duì)人群全方位、不間斷的監(jiān)管。隨著視頻監(jiān)控系統(tǒng)的普及和視頻分析技術(shù)的發(fā)展，利用人群密度估計(jì)技術(shù)實(shí)時(shí)監(jiān)測(cè)人群密度，及時(shí)發(fā)現(xiàn)高密度人群并報(bào)警，是實(shí)現(xiàn)有效預(yù)警的手段之一。

壓縮感知(Compressing Sense，CS)是2006年提出的一種新采樣理論，在信號(hào)滿足稀疏性的條件下，對(duì)信號(hào)的高概率精確重構(gòu)僅需要遠(yuǎn)少于信號(hào)維數(shù)的測(cè)量值即可完成[1-4]，在數(shù)據(jù)存儲(chǔ)及實(shí)時(shí)處理方面均具有優(yōu)勢(shì)，在圖像處理領(lǐng)域得到了廣泛的研究和應(yīng)用，如背景分割[5]、圖像檢索[6]、圖像融合[7]等。

基于像素和基于紋理是兩種經(jīng)典的人群密度估計(jì)方法?；谙袼氐姆椒ㄓ蒁avies等人[8]首次提出，計(jì)算簡(jiǎn)單，但不適用于估計(jì)較高密度人群?；诩y理的方法由Marana等人[9]首次提出，以灰度共生矩陣統(tǒng)計(jì)值為人群密度特征，在較高密度人群情況下具有較高的準(zhǔn)確率。由于基于像素的方法準(zhǔn)確度較低，目前很多學(xué)者以文獻(xiàn)[9]中基于灰度共生矩陣的方法為基礎(chǔ)開展研究，如張文倩[10]將分形維數(shù)和灰度共生矩陣相結(jié)合，所提取的人群密度特征包括水平、垂直兩個(gè)方向上灰度共生矩陣的能量、熵、對(duì)比度、逆差距8個(gè)統(tǒng)計(jì)量以及1個(gè)分形維數(shù)；劉小銳等人[11]結(jié)合二維快速傅里葉變換與灰度共生矩陣，將圖像經(jīng)快速傅里葉變換后的幅度譜看做紋理圖像，提取其灰度共生矩陣特征；唐清等人[12]將模糊集理論與BP(Back Propagation)神經(jīng)網(wǎng)絡(luò)相結(jié)合，通過(guò)灰度共生矩陣特征估計(jì)人群密度。

上述基于紋理的方法雖然提高了較高密度人群的估計(jì)準(zhǔn)確性，但由于灰度共生矩陣的計(jì)算量較大，其實(shí)時(shí)性還有待提高。為了改善基于紋理方法的實(shí)時(shí)性，本文結(jié)合壓縮感知理論和主成分分析法(Principal Component Analysis，PCA)進(jìn)行人群密度估計(jì)，這主要是基于以下3方面的考慮：第一，壓縮感知測(cè)量值含有豐富的原始圖像信息，能夠表征人群密度特征；第二，壓縮感知測(cè)量值的維度遠(yuǎn)少于原始信號(hào)的維度，減少人群密度特征提取的計(jì)算量，算法復(fù)雜度較低，能夠縮短人群密度特征提取時(shí)間；第三，采用主成分分析法對(duì)壓縮感知測(cè)量值做降維處理，降低人群密度特征向量的維度，能夠縮短人群密度分類時(shí)間。

本文提出的基于壓縮感知的人群密度估計(jì)方法首先利用DCT(Discrete Cosine Transform，離散余弦變換)和隨機(jī)高斯矩陣獲取壓縮感知測(cè)量值；然后利用主成分分析進(jìn)行降維處理，得到人群密度特征向量；最后利用SVM(Support Vector Machines，支持向量機(jī))進(jìn)行人群密度估計(jì)。與文獻(xiàn)[9]中基于灰度共生矩陣的方法及文獻(xiàn)[10]中基于灰度共生矩陣和分形維數(shù)的方法相比，本文提出的方法在實(shí)時(shí)性和準(zhǔn)確率方面均有較大提高。

1基礎(chǔ)理論

壓縮感知是由E. J. Candes[1]、J. Romber[2]、T. Tao[3]和David L. Donoho[4]等人提出的新采樣理論。在信號(hào)滿足稀疏性的條件下，利用遠(yuǎn)少于原始信號(hào)維數(shù)的測(cè)量值完成信號(hào)的高概率精確重構(gòu)，關(guān)鍵步驟包括稀疏表示、信號(hào)測(cè)量和信號(hào)重構(gòu)。

1.1稀疏表示

稀疏性是壓縮感知的前提，有兩種方式。第一種方式，對(duì)于一維離散信號(hào)x∈RN，當(dāng)其元素xi,i∈[1,N]中非零個(gè)數(shù)為k(k?N)時(shí)，稱信號(hào)x本身具有稀疏性。第二種方式，將信號(hào)x表示為某個(gè)正交基Ψ∈RN×N的線性組合形式，如式(1)所示，

x=Ψs

(1)

其中，s∈RN是x的變換系數(shù)向量，即x的等價(jià)表示，當(dāng)s中僅有k(k?N)個(gè)值非零時(shí)，稱信號(hào)x在Ψ域下具有稀疏性，s即為x的k稀疏表示，Ψ為x的稀疏基[3]。

從圖像的角度來(lái)說(shuō)，稀疏性可以理解為像素灰度取值中含有大量的零值或近似零值，即少量的非零值即可有效表示原始圖像的信息。對(duì)于自然界圖像而言，除了二值圖像本身是稀疏信號(hào)外，很多圖像本身并不具備稀疏性，因此需要尋找合適的稀疏基將圖像映射為稀疏信號(hào)。

1.2信號(hào)測(cè)量

信號(hào)測(cè)量是利用測(cè)量矩陣將稀疏信號(hào)映射到低維空間獲取測(cè)量值的過(guò)程，如式(2)所示。

y=Φx=ΦΨs

(2)

其中，Φ∈RM×N(M?N)為測(cè)量矩陣，測(cè)量值y∈RM。

Candes等人[3]的研究表明，當(dāng)測(cè)量矩陣Φ滿足如式(3)所示的RIP(Restricted Isometry Property)準(zhǔn)則時(shí)，測(cè)量值y即包含重構(gòu)原始信號(hào)的足夠信息，

(3)

其中，ε>0，v為任意嚴(yán)格k稀疏的矢量。但是直接判斷矩陣是否滿足RIP條件很困難，Baraniuk表明，測(cè)量矩陣Φ與稀疏基Ψ不相關(guān)是RIP的一個(gè)近似等價(jià)條件[13]，實(shí)際操作中常利用該等價(jià)條件選擇測(cè)量矩陣。

由于隨機(jī)高斯矩陣與絕大多數(shù)稀疏基均不相關(guān)，常用于壓縮感知中的測(cè)量矩陣。隨機(jī)高斯矩陣Φ∈Rm×n的各元素均服從正態(tài)分布，如式(4)所示。

(4)

1.3信號(hào)重構(gòu)

信號(hào)重構(gòu)首先通過(guò)最小l0范數(shù)下的優(yōu)化問(wèn)題求式(2)的最佳稀疏解s，如式(5)所示，

min‖s‖0,y=Φx=ΦΨs

(5)

然后通過(guò)式(1)由稀疏信號(hào)s恢復(fù)出原始信號(hào)x。

由于測(cè)量值y的維度M遠(yuǎn)小于原始信號(hào)x的維度N，因此，求解式(2)的最佳稀疏解s是一個(gè)NP(Non-deterministicpolynomial)難問(wèn)題。Donoho等人[14]表明，當(dāng)測(cè)量矩陣滿足RIP準(zhǔn)則時(shí)，可通過(guò)求解最小l1范數(shù)問(wèn)題重構(gòu)信號(hào)，成為實(shí)際求解原始信號(hào)的理論依據(jù)。

2基于壓縮感知的人群密度估計(jì)方法

本文所提方法的流程如圖1所示，人群密度特征提取和人群密度估計(jì)是兩個(gè)關(guān)鍵環(huán)節(jié)。

圖1　基于壓縮感知的人群密度估計(jì)方法流程圖

2.1人群密度特征提取

本文利用壓縮感知測(cè)量值表征人群密度特征，并結(jié)合主成分分析法進(jìn)一步降低信號(hào)維度，最終得到6D(Dimension)人群密度特征向量。如圖1所示，人群密度特征是訓(xùn)練支持向量機(jī)的輸入向量，具體計(jì)算過(guò)程如下。

2.1.1圖像分塊

將原始圖像劃分為8×8像素大小的子圖像。一般圖像都具有較強(qiáng)的局部相關(guān)性，因此將圖像劃分為8×8像素的子圖像能夠保持圖像的空間相關(guān)性；同時(shí)，8×8像素的子圖像由于相關(guān)性強(qiáng)，變化平緩，含有的空間頻率較低，因此，在經(jīng)過(guò)DCT等圖像變換后，其能量主要集中在少數(shù)幾個(gè)系數(shù)上，有利于圖像的稀疏表示。

2.1.2稀疏表示

首先，對(duì)每一個(gè)子圖像執(zhí)行DCT變換，得到大小為8×8的DCT變換系數(shù)。DCT變換系數(shù)反映了圖像的不同頻率成分，“左上角”為較低頻率，“右下角”為較高頻率。一般而言，圖像的局部區(qū)域內(nèi)變化緩慢，因此低頻成分較多，高頻成分較少，即經(jīng)過(guò)DCT變換后的子圖像能量主要集中于“左上角”的低頻部分。因此，DCT變換系數(shù)在“左上角”位置處的數(shù)值較大，越往“右下角”方向數(shù)值越接近于零。然后，對(duì)DCT變換系數(shù)進(jìn)行量化。量化是對(duì)DCT變換系數(shù)進(jìn)行壓縮和取整的過(guò)程，經(jīng)過(guò)量化后，DCT變換系數(shù)中的零值個(gè)數(shù)增多，即可得到稀疏子圖像。量化過(guò)程如式(6)所示。

(6)

其中，F(xiàn)(u,v)為DCT變換系數(shù)，Q(u,v)為量化步長(zhǎng)，F(xiàn)q(u,v)為量化后的DCT系數(shù)。

人眼對(duì)不同頻率分量對(duì)應(yīng)圖像的敏感度和分辨能力不同，一般對(duì)低頻分量較為敏感，因此，常采用不同的量化步長(zhǎng)對(duì)DCT變換系數(shù)進(jìn)行量化，以更好地符合人眼對(duì)圖像的主觀感受。表1是JPEG標(biāo)準(zhǔn)采用的亮度量化步長(zhǎng)，本文據(jù)此對(duì)DCT變換系數(shù)進(jìn)行量化。

表1　JPEG標(biāo)準(zhǔn)亮度量化表

最后，將量化后的DCT系數(shù)轉(zhuǎn)換為長(zhǎng)度為64的1D信號(hào)，得到稀疏信號(hào)。

2.1.3信號(hào)測(cè)量

文獻(xiàn)[15]通過(guò)一系列實(shí)驗(yàn)比較分析了不同采樣率下信號(hào)重構(gòu)效果的好壞，結(jié)果表明，當(dāng)采樣率為30%時(shí)即可滿足精確恢復(fù)原始信號(hào)的要求。因此，本文將采樣率設(shè)為31.25%，構(gòu)造大小為20×64的隨機(jī)高斯矩陣作為測(cè)量矩陣，獲取長(zhǎng)度為20的測(cè)量值；

重復(fù)上述圖像分塊、稀疏表示、信號(hào)測(cè)量的步驟，得到所有子圖像的測(cè)量值，并轉(zhuǎn)換為1D信號(hào)。

2.1.4主成分分析

對(duì)壓縮感知測(cè)量值進(jìn)行主成分分析，所保留的主成分個(gè)數(shù)即為人群密度特征向量的維數(shù)。特征向量維數(shù)越低，計(jì)算越簡(jiǎn)單，實(shí)時(shí)性越好，但同時(shí)也可能會(huì)降低識(shí)別準(zhǔn)確性。為了均衡準(zhǔn)確性和實(shí)時(shí)性，本文分別計(jì)算了不同特征向量維數(shù)下基于壓縮感知的人群密度估計(jì)方法的準(zhǔn)確性和實(shí)時(shí)性。

特征向量維數(shù)范圍設(shè)定為2～20D，分別計(jì)算每種向量維數(shù)下人群密度估計(jì)的準(zhǔn)確性和實(shí)時(shí)性。其中，準(zhǔn)確性由100幅測(cè)試圖像中正確分類圖像所占比例衡量，結(jié)果如圖2所示；實(shí)時(shí)性由單幅圖像的人群密度特征提取時(shí)間衡量，結(jié)果如圖3所示。

圖2　不同特征向量維數(shù)下的正確率

圖3　不同特征向量維數(shù)下的實(shí)時(shí)性

由圖2可知，當(dāng)特征向量維數(shù)低于6D時(shí)，隨著維數(shù)的提高分類正確率總體呈上升趨勢(shì)；當(dāng)特征向量維數(shù)高于6D時(shí)，分類正確率處于穩(wěn)定狀態(tài)，且均在95%以上，能夠滿足人群密度估計(jì)要求。因此，當(dāng)特征向量維數(shù)大于6時(shí)，本文方法能夠滿足準(zhǔn)確性要求。

由圖3可知，當(dāng)特征向量維數(shù)從2～20D變化時(shí)，單幅圖像的特征提取時(shí)間變化范圍在5 ms以內(nèi)。這是因?yàn)?，人群密度特征提取時(shí)間包括獲取測(cè)量值和主成分映射兩部分，其中，前者占據(jù)絕大部分時(shí)間，后者約為1 ms。因此，特征向量的維數(shù)在小范圍內(nèi)變動(dòng)時(shí)，對(duì)本文方法的實(shí)時(shí)性影響不大。

基于上述分析，確定人群密度特征向量的維數(shù)為6D，即保留主成分分析的前6個(gè)主成分，構(gòu)成人群密度特征向量。

2.2人群密度分類

本文選擇SVM實(shí)現(xiàn)人群密度分類。SVM是一種監(jiān)督式學(xué)習(xí)方法，解決在原始空間中線性不可分的非線性分類問(wèn)題，能夠在小樣本情況下取得較好的分類效果，但不能直接用于多類別的分類。

為實(shí)現(xiàn)中、高、很高3種密度等級(jí)的分類，本文采取“投票法”策略[16]，首先，由3個(gè)SVM構(gòu)造二級(jí)分類器，如圖4所示，其中第一級(jí)為SVMa，實(shí)現(xiàn)中、很高類別分類，SVMb和SVMc處于第二級(jí)，分別實(shí)現(xiàn)中、高、很高三個(gè)類別的分類。

圖4　SVM結(jié)構(gòu)

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

2.3.1仿真實(shí)驗(yàn)圖像

本文仿真實(shí)驗(yàn)的視頻來(lái)自于某中學(xué)校門口的一段監(jiān)控視頻，其真實(shí)場(chǎng)景面積約為10 m2，圖像大小為320×240。根據(jù)表2所示Polus提出的人群密度等級(jí)的定義[17]，針對(duì)較高密度人群，仿真實(shí)驗(yàn)將人群密度等級(jí)劃分為中、高、很高3類，如表3所示。

以15幀為間隔抽取該監(jiān)控視頻圖像750幀，用于仿真實(shí)驗(yàn)。其中，訓(xùn)練圖像共450幀，中、高、很高

密度各150幀；測(cè)試圖像共300幀，中、高、很高密度各100幀。各密度等級(jí)的示例圖像如圖5所示。

表2　Polus人群密度等級(jí)定義

表3　本文人群密度等級(jí)劃分

圖5　不同人群密度等級(jí)圖像示例

2.3.2仿真實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)的軟件環(huán)境主要包括Visual Studio 2010、SQL Server2012、Qt Creator5.2.0、OpenCV2.4.8；硬件環(huán)境為Inter(R) Core(TM) i5-2450M CPU。

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

為了驗(yàn)證本文所提方法的有效性，對(duì)本文方法、文獻(xiàn)[9]中基于灰度共生矩陣的方法、文獻(xiàn)[10]中基于灰度共生矩陣和分形維數(shù)的方法均進(jìn)行了仿真實(shí)驗(yàn)，并比較分析其實(shí)時(shí)性和準(zhǔn)確率，分別如表4和表5所示。

表4　實(shí)時(shí)性分析

表5　準(zhǔn)確率分析

由表4可知，本文方法的特征提取時(shí)間少于基于灰度共生矩陣的方法和基于灰度共生矩陣以及分形維數(shù)的方法；同時(shí)，人群特征向量?jī)H為6D，分類耗時(shí)較低，實(shí)時(shí)性最好?；诨叶裙采仃嚭头中尉S數(shù)的方法由于增加了對(duì)分形維數(shù)的計(jì)算過(guò)程，所需的特征提取時(shí)間大于基于灰度共生矩陣的方法和本文方法。

由表5可知，與基于灰度共生矩陣的方法和基于灰度共生矩陣和分形維數(shù)的方法相比，本文方法的準(zhǔn)確率有很大提高，這是因?yàn)閴嚎s感知測(cè)量值包含豐富的原始信息，能夠準(zhǔn)確表述圖像特征。

3結(jié)論

實(shí)時(shí)監(jiān)測(cè)人群密度，及時(shí)發(fā)現(xiàn)擁擠人群，是輔助群體性事件預(yù)警的一種有效手段。針對(duì)較高密度人群，本文提出了一種基于壓縮感知的人群密度估計(jì)方法。通過(guò)某中學(xué)校門口的視頻圖像進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明，本文方法與基于灰度共生矩陣的方法，以及基于灰度共生矩陣和分形維數(shù)的方法相比，在準(zhǔn)確率和實(shí)時(shí)性方面均占有優(yōu)勢(shì)。隨著人群密度估計(jì)技術(shù)的研究和發(fā)展，該技術(shù)將在智能視頻分析領(lǐng)域發(fā)揮更加重要的作用。

參考文獻(xiàn)

[1]Candes E. Compressive sampling[A]. Proceedings of the International Congress of Mathematicians[C]∥Proceedings of the Intemational Congress of Mathematicans, 2006(3):1433-1452.

[2]Candes E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Trans. on Information Theory, 2006, 52(2):489-509.

[3]Candes E, Tao T. Near optimal signal recovery from random projections: Universal encoding strategies[J]. IEEE Trans. Info. Theory, 2006, 52(12): 5406-5425.

[4]David L. Donoho. Compressed sensing[J]. IEEE Transaction on Information Theory, 2006, 52(4): 1289-1306.

[5]李杰,程旺宗. 基于壓縮傳感的背景差分方法研究[J]. 數(shù)字社區(qū)&智能家居, 2010(2):410-412.

[6]周燕,曾凡智,盧炎生,周月霞. 基于壓縮感知的圖像檢索方法研究[J]. 中山大學(xué)學(xué)報(bào)：自然科學(xué)版, 2014, 53(1):57-62,66.

[7]Tao W, Nishan C, Alin A. Compressive Image Fusion[J]. In: Proc of IEEE Int Conf on Image Processing. California, 2008:1308-1311.

[8]Davies A C, Jia Hong Yin Velastin, S A. Crowd monitoring using image processing[J]. IEEE Electronics & Communication Engineering Journal, 1995,7(1):37-47.

[9]Marana A N, Velastin S A, Costa L F, et al. Automatic estimation of crowd density using texture [J]. Safety Science, 1998, 28(3): 165-175.

[10]張文倩. 基于灰度共生矩陣和分形的人群密度估計(jì)[J]. 電子測(cè)試, 2012(5):36-39,45.

[11]劉小銳,周激流,李曉華. 頻域基于灰度共生矩陣的人群密度估計(jì)[J]. 微計(jì)算機(jī)信息, 2008,24(34):310-311,314.

[12]唐清, 王知衍, 嚴(yán)和平, 等. 基于模糊神經(jīng)網(wǎng)絡(luò)的大場(chǎng)景人群密度估計(jì)方法[J]. 計(jì)算機(jī)應(yīng)用研究,2010,27(3):989-991.

[13]Baraniuk R. A lecture on compressive sensing [J]. IEEE Signal/Processing Magazine, 2007, 24(4): 118-121.

[14]Donoho D L, Elad M, Temlyakov V N. Stable recovery of sparse over complete representations in the presence of noise[J]. IEEE Transactions on Information Theory, 2006, 52(1): 6-18．

[15]Liu L, P. Fieguth, Texture classification from random features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(3): 574-586.

[16]劉志剛,李德仁,秦前清,等. 支持向量機(jī)在多類分類問(wèn)題中的推廣[J]. 計(jì)算機(jī)工程與應(yīng)用, 2004, 40(7):10-13,65.

[17]Schofer J, Ushpiz A, Polus A. Pedestrian flow and level of service[J]. J. Transportation Eng, 1983, 109(1): 46-56.

(責(zé)任編輯于瑞華)

中圖分類號(hào)D035.33

作者簡(jiǎn)介李沖(1992—)，女，河南周口人，2013級(jí)在讀碩士研究生。研究方向?yàn)閿?shù)字圖像處理、模式識(shí)別。

基金項(xiàng)目國(guó)家自然基金(71203229)項(xiàng)目；2014北京市支持中央高校共建項(xiàng)目公安視聽(tīng)專業(yè)建設(shè)項(xiàng)目；中國(guó)人民公安大學(xué)2015年中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2015JKF01243)。