基于稀疏編碼的異常檢測(cè)

袁玲

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

近年來(lái)，隨著人口的持續(xù)增長(zhǎng)及城市化進(jìn)程的不斷加快，人群活動(dòng)變得日益頻繁，在交通路口、機(jī)場(chǎng)、火車站、旅游景區(qū)等人群密集的公共場(chǎng)所發(fā)生重大異常事件的現(xiàn)象屢見(jiàn)不鮮。因此，在智能視頻監(jiān)控中對(duì)大規(guī)模人群的異常檢測(cè)則顯得尤為重要。異常檢測(cè)早期研究方案集中在建立目標(biāo)軌跡模型，這種方法大體思想是一個(gè)目標(biāo)的軌跡如果偏離正常模型訓(xùn)練出來(lái)的軌跡，則該目標(biāo)被標(biāo)記為異常。然而，這些基于追蹤的方法有其缺點(diǎn)：①對(duì)于遮擋場(chǎng)景下，是不穩(wěn)定的；②在擁擠場(chǎng)景中，這些方法的計(jì)算復(fù)雜。

為了解決這些困難，有學(xué)者提出了一些基于時(shí)空低級(jí)視覺(jué)特征的方法，例如光流和梯度特征，然后使用這些特征訓(xùn)練出相應(yīng)的模型，在這些模型下，出現(xiàn)的可能性小于一定閾值的則為異常[1]。使用人群正常的視頻訓(xùn)練出隱馬爾科夫模型（HMM），可以解決由于異常訓(xùn)練數(shù)據(jù)的稀缺性以及難于預(yù)先定義異常事件帶來(lái)的問(wèn)題。

考慮到人群本身的行為，社會(huì)力模型被Mehran 等人[2]引進(jìn)，首先，該模型提出人的實(shí)際行為是受自身的期望以及周圍人的排斥力影響的理論，然后使用排斥力訓(xùn)練出LDA 模型，最后，實(shí)驗(yàn)證明該模型在人群異常檢測(cè)中是一個(gè)有效的運(yùn)動(dòng)模型。以上模型強(qiáng)調(diào)了時(shí)間上運(yùn)動(dòng)的變化，但是忽略了人群的外觀變化，因此Mahadevan 等人使用了混合動(dòng)態(tài)紋理模型（MDT）[3-4]來(lái)檢測(cè)異常，該模型把異常分為時(shí)間上的異常和空間上的異常，時(shí)間上的異常被認(rèn)為是出現(xiàn)可能性低的行為，而空間上的異常是視頻中與周圍場(chǎng)景相比，具有顯著性特征的行為。

最近，基于稀疏編碼的研究受到了很多關(guān)注，其中，基于稀疏編碼的異常事件檢測(cè)也取得不錯(cuò)的效果。文獻(xiàn)[5-6]提出了動(dòng)態(tài)稀疏表示的方法；Yang Cong等人[7]在此基礎(chǔ)上制定了基于稀疏編碼檢異常檢測(cè)的標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)稱為稀疏重構(gòu)代價(jià)（SRC）。但是在實(shí)際應(yīng)用中，訓(xùn)練樣本的有限性會(huì)導(dǎo)致在新場(chǎng)景的視頻中，異常檢測(cè)結(jié)果出現(xiàn)偏差，因此，在線學(xué)習(xí)和更新稀疏編碼字典的方法[8-9]被提出。盡管以上大多數(shù)基于稀疏編碼的方法在檢測(cè)效果上表現(xiàn)良好，但是實(shí)時(shí)性有待提高。

本文在原有稀疏編碼的思想上，提出一種新的有效的稀疏表示方法，該方法在檢測(cè)速度上，具有不錯(cuò)的效率，同時(shí)檢測(cè)率也能得到保證。

1 稀疏編碼

1.1 定義

對(duì)于訓(xùn)練模型，一個(gè)高維的特征顯然能更好地描述事件，但是隨著特征的維數(shù)增加，需要的訓(xùn)練數(shù)據(jù)呈現(xiàn)指數(shù)增長(zhǎng)，在現(xiàn)實(shí)生活中，收集的訓(xùn)練數(shù)據(jù)是很難滿足要求的。例如，在全局的異常檢測(cè)中，要訓(xùn)練出一個(gè)較好的高斯模型，但是只有400 個(gè)訓(xùn)練樣本的情況下，這是比較困難的。但是稀疏表示卻適合代表具有高維特征的樣本。稀疏編碼，是通過(guò)正常樣本訓(xùn)練出一個(gè)字典，該字典的線性組合可以訓(xùn)練樣本。這個(gè)字典用D∈Rp×q來(lái)表示。對(duì)于一個(gè)測(cè)試樣本X，我們可以通過(guò)以下公式來(lái)表示：

其中β∈Rp×1是稀疏系數(shù)，而是數(shù)據(jù)擬合項(xiàng)，‖ β‖0是稀疏重構(gòu)項(xiàng)，而s 是（＜＜q）是稀疏數(shù)量控制參數(shù)。給定訓(xùn)練樣本[x1,...,xn]，我們可以通過(guò)公式（1）去訓(xùn)練字典D。

1.2 異常檢測(cè)

使用公式（1）訓(xùn)練出的字典D，引用文獻(xiàn)[7]中定義的稀疏重構(gòu)代價(jià)來(lái)檢測(cè)異常。通常情況下，對(duì)于正常的事件應(yīng)該是以很小的代價(jià)且以很少的基礎(chǔ)向量（字典中的列向量）構(gòu)建，也就是β為0 的個(gè)數(shù)比較少，而異常事件要么不能以很小的代價(jià)構(gòu)建出，要么即使能以很小的代價(jià)構(gòu)建出，也需要大量的基礎(chǔ)向量。前人的研究驗(yàn)證了這個(gè)方法可以達(dá)到較高的檢測(cè)率。

1.3 傳統(tǒng)稀疏編碼的效率問(wèn)題

顯然，在公式（1）中的字典具有高度冗余，因此在異常檢測(cè)階段中存在效率問(wèn)題，因?yàn)樵谶@個(gè)階段中，需要在q 個(gè)基礎(chǔ)向量中找到不大于s 個(gè)基礎(chǔ)向量，而s 是遠(yuǎn)遠(yuǎn)小于q 的（q 足夠大是為了能夠表示更多的訓(xùn)練樣本），那么這個(gè)過(guò)程是比較耗時(shí)的，因此研究怎樣減小q是很必要的，本文就是針對(duì)這個(gè)問(wèn)題進(jìn)行優(yōu)化。

2 本文算法

針對(duì)1.3 小節(jié)提出的問(wèn)題，本文提出了一種新的字典學(xué)習(xí)方法。對(duì)于字典D，我們用n 個(gè)子字典構(gòu)成，其中每一個(gè)字典由一些基礎(chǔ)向量構(gòu)成，并且使該子字典盡可能多的表示訓(xùn)練樣本，在測(cè)試階段，只需要在這些子字典中找到一個(gè)合適的子字典來(lái)表示樣本。通過(guò)這樣的優(yōu)化，q 的數(shù)量大大減少，而針對(duì)找到的子字典，只需要通過(guò)最小平方誤差找到合適的向量組合就能表示樣本。本文框架如圖1 所示。接下來(lái)，將詳細(xì)介紹本文的方法。

圖1 本文框架流程圖

2.1 字典的學(xué)習(xí)

對(duì)于字典的學(xué)習(xí)，我們首先得提取訓(xùn)練樣本的特征數(shù)據(jù)，用以表示該樣本。本文主要提取視頻中的3D梯度特征，如文獻(xiàn)[10]中定義的那樣，該特征能較好地表示局部特征，因此使用該特征不但能檢測(cè)出某一幀出現(xiàn)異常，且能更好的定位該異常。同時(shí)，我們將每一幀視頻劃分成10×10 圖像塊，然后在時(shí)間序列上每5幀組成一個(gè)10×10×5 的立方體，每一個(gè)立方體表示一個(gè)事件。

對(duì)于每一個(gè)立方體，我們提取其3D 梯度特征，然后組成訓(xùn)練樣本數(shù)據(jù)X={x1,...,xn}∈Rp×n，我們的目標(biāo)是找到一個(gè)基礎(chǔ)字典組合S={S1,...,SK}，其中每一個(gè)Si∈Rp×s。這個(gè)學(xué)習(xí)過(guò)程可以由公式（2）給出：

其中γ={γ1,...,γn}，對(duì)于每一個(gè)γj∈K，用來(lái)指示Si集合是不是能被選擇用來(lái)表示X 的第j 個(gè)數(shù)據(jù)。而用來(lái)表明是對(duì)于子字典Si構(gòu)成Xj的系數(shù)。由上面的公式可以看出，Xj至少在S 中能有一個(gè)基礎(chǔ)子字典能以很小的代價(jià)e 組成。很顯然,選擇合適的K 是很重要的，太小則不足夠表示所有的訓(xùn)練樣本，而太大則可能導(dǎo)致所有樣本的重構(gòu)代價(jià)幾乎趨近于0，即使是異常樣本。因此，對(duì)于K，不是固定，而是采取自適應(yīng)學(xué)習(xí)的方法，也即是迭代，對(duì)于e 設(shè)置一個(gè)下限λ，當(dāng)訓(xùn)練樣本的所有的重構(gòu)代價(jià)都達(dá)到了這個(gè)下限，此時(shí)的迭代次數(shù)K 就是最合適的。因此公式（2）可以變成為：

更新{Si,β,γ}，對(duì)于公式（3），學(xué)習(xí)過(guò)程中要學(xué)習(xí)的參數(shù)有Si,β,γ。本文把這個(gè)學(xué)習(xí)過(guò)程分成兩步，首先保持γ不變，更新{Si,β}，然后利用已經(jīng)學(xué)習(xí)好的{Si,β}，更新γ。

第一步，給定該γ，此時(shí)可以把公式（3）變?yōu)椋?/p>

其中j∈Ωc，表示剩下的不能由S 表示的X 集合。上面這個(gè)公式可以看成求函數(shù)的最小值。對(duì)于公式（4）也將分成兩步，一是保持Si不變，其中γj不等于0，求取

更新Si，這里采用塊梯度下降方法，每一次用公式（6）更新Si，直到收斂。

更新γ，使用公式（5）、（6）得到的{Si,β}，對(duì)于每一Xj，公式（3）可以轉(zhuǎn)化為公式（7）：

使用上文描述的字典學(xué)習(xí)過(guò)程，就可以得到一個(gè)合適的字典D，該字典能很好地描述訓(xùn)練樣本，算法過(guò)程如下所示：

算法1：訓(xùn)練字典

輸入：X，Xc=X

重復(fù)

重復(fù)

利用公式（5），（6）更新{Si,β}

利用（7）更新γ

直到（4）收斂

把Si加入到集合S

去除已經(jīng)滿足條件（γj=0）的Xj

i=i+1;

2.2 測(cè)試

對(duì)于已經(jīng)學(xué)習(xí)好的字典組合S={S1,...,SK}，就可以在測(cè)試階段尋找是否存在一個(gè)Si，滿足重構(gòu)代價(jià)小于閾值，可以使用（8）式得到合適的Si。

顯然這是一個(gè)二次函數(shù)，可以優(yōu)化成公式（9）：

然后，重構(gòu)代價(jià)就可表示為：

測(cè)試算法流程如下：

算法2：測(cè)試

輸入：X，{R1,...,RK}，閾值T

for j=1 →K

輸出正常

else

輸出異常

end

3 實(shí)驗(yàn)

本文實(shí)驗(yàn)環(huán)境為MATLAB 2015，Windows 10，在UCSD 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。對(duì)于給定的視頻將大小重新定義成為120×160，并把視頻分成10×10×5 的立方體。

3.1 UCSD數(shù)據(jù)集

USCD 數(shù)據(jù)集主要有分為兩個(gè)子集（UCSDped1,UCSDped2），每一個(gè)子集里面都有訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)，而且測(cè)試數(shù)據(jù)里面含有像素級(jí)別的異常標(biāo)記掩模。其中UCSDped1 訓(xùn)練數(shù)據(jù)含有34 個(gè)視頻，每一個(gè)視頻有200 幀，測(cè)試數(shù)據(jù)有36 個(gè)視頻，10 個(gè)帶有異常標(biāo)記的視頻，而UCSDped2 訓(xùn)練數(shù)據(jù)有10 個(gè)視頻，測(cè)試數(shù)據(jù)16 個(gè)，每一個(gè)測(cè)試數(shù)據(jù)都含帶有標(biāo)記的掩模，且視頻幀數(shù)為120 幀。本文把兩個(gè)子集的訓(xùn)練數(shù)據(jù)都當(dāng)成訓(xùn)練樣本，只使用帶有人工標(biāo)記異常幀的視頻進(jìn)行測(cè)試。因此，本文獲得的訓(xùn)練數(shù)據(jù)集（3D 梯度特征）總共有307200 個(gè)10×10×5 維的特征。

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

下圖展示了在UCSDped1 中測(cè)試數(shù)據(jù)中的第三個(gè)視頻中的第142 幀的數(shù)據(jù)。

圖2 異常行為

圖3 圖3的真實(shí)異常標(biāo)記的位置

圖4 本文計(jì)算出來(lái)的異常位置

圖2 用紅色矩形框標(biāo)記的為異常行為（在人行道上騎車），圖3 是人工標(biāo)記的異常位置，圖4 是本文算法檢測(cè)出的異常行為位置，從圖2-圖4 可以看出，本文異常定位的結(jié)果比較準(zhǔn)確。

圖5

圖5 綠色代表測(cè)試數(shù)據(jù)中真實(shí)的正常和異常情況，正常為0，異常為1，紅色代表該異常的代價(jià)（對(duì)于小于一定閾值的值，本文直接計(jì)算為0）。

圖5 是圖2 所在幀的整個(gè)視頻的重構(gòu)代價(jià)函數(shù)變化，橫軸表示視頻幀數(shù)，縱軸表示每一幀的重構(gòu)代價(jià)，當(dāng)閾值取0.25 的時(shí)候，能把含有異常行為的幀檢測(cè)出來(lái)。從圖2-圖5 可以分析出，本文算法對(duì)于異常檢測(cè)與異常定位的方法是有效的。并且經(jīng)過(guò)實(shí)驗(yàn)，本文異常檢測(cè)的準(zhǔn)確率可以達(dá)到94.4%，準(zhǔn)確率的計(jì)算是是根據(jù)本文計(jì)算出來(lái)的掩模（圖4）的面積與真實(shí)數(shù)據(jù)的掩模的面積（圖3）的比值是否大于0.4 得到的。如果比值大于0.4，則判定該幀異常定位結(jié)果正確，最后將所有測(cè)試視頻計(jì)算出來(lái)的平均值作為準(zhǔn)確率。除此之外，本文也采取了ROC 曲線對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，同時(shí)也與其他研究中的實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比。如圖6所示：

圖6 ROC曲線，橫軸為誤檢，縱軸為檢測(cè)正確

從圖6 可以看出，本文算法在被檢測(cè)為異常行為，而實(shí)際為正常行為的概率（FPR）較低的情況下，檢測(cè)率（TPR）也較高。并且也與其他算法相比，AUC（Area Under Curve）也能達(dá)到不錯(cuò)的效果。最后本文在時(shí)間上也與其他算法進(jìn)行了對(duì)比，本文測(cè)試階段主要有兩個(gè)過(guò)程耗時(shí)較長(zhǎng)：一是特征提取，二是使用算法2 進(jìn)行異常檢測(cè)。從表1 可以看出，本文的方法在時(shí)間上能提升不少，因此本文算法在提升時(shí)間效率方面有顯著效果。

表1 幾種方法的時(shí)間比較

4 結(jié)語(yǔ)

本文提出了一個(gè)基于稀疏子字典組合學(xué)習(xí)的異常檢測(cè)方法，對(duì)于字典D，我們用n 個(gè)子字典構(gòu)成，其中每一個(gè)字典由一些基礎(chǔ)向量構(gòu)成，并且使該子字典能盡可能多的表示訓(xùn)練樣本。最后在UCSD 數(shù)據(jù)集上對(duì)檢測(cè)結(jié)果和時(shí)間性能進(jìn)行了驗(yàn)證，該方法能通過(guò)減少傳統(tǒng)稀疏編碼的搜索維數(shù)，在不影響檢測(cè)結(jié)果的情況下，有效地提升檢測(cè)的速度，并且當(dāng)使用MATLAB 在普通臺(tái)式PC 上進(jìn)行計(jì)算時(shí)，本文的方法也能達(dá)到高檢測(cè)率以及高速率。