基于HOG3D描述器與稀疏編碼的異常行為檢測方法

何聰芹， 朱 煜， 陳 寧（華東理工大學信息科學與工程學院，上海 200237）

基于HOG3D描述器與稀疏編碼的異常行為檢測方法

何聰芹， 朱 煜， 陳 寧
（華東理工大學信息科學與工程學院，上海 200237）

提出了一種基于稀疏編碼理論的視頻異常行為檢測方法，并使用HOG3D空-時描述器表征視頻序列的形態及運動信息。首先，從正常視頻序列中提取空-時興趣點，獲得其特征向量作為訓練樣本。通過K-SVD字典訓練算法構建過完備字典，使得正常樣本在所構建字典上的表達具有很好的稀疏性。在稀疏編碼過程中，按視頻段讀取測試視頻序列，求解特征信息在字典上的關于其稀疏系數的凸優化問題，然后根據稀疏編碼改進公式求得重構誤差數值。最后的判斷階段，計算視頻段的相對重構誤差，相對重構誤差為正表明為異常視頻段，否則為正常視頻段。在UMN數據庫3個場景及Weizmann數據庫上進行實驗，驗證了本文算法的有效性。將實驗拓展到現實監控視頻中，結果表明本文方法在實踐中同樣具有較好的應用價值。

稀疏編碼；異常行為檢測；重構誤差；HOG3D描述器；K-SVD

在視頻監控領域，異常事件檢測扮演了非常重要的角色。監控視頻數量龐大，難以完全依靠人力觀察發現異常事件，因此，智能化異常事件檢測備受關注。本文以基于視頻智能分析的異常事件檢測為目標，在實現算法上進行了研究。“異常事件”，作為一個與“正常事件”相對應的概念，它的檢測應當是基于“正常事件”訓練樣本的。一種思想是，在適應關于訓練樣本的概率模型時，異常測試樣本相較正常測試樣本具有較低的概率［1-4］。其中的難點在于，模型訓練過程中需要大量的訓練數據，并且視頻信息往往需要高維度特征來表征。事實上，視頻中往往僅有小部分顯著內容包含檢測所需的重要信息。目前針對空-時興趣點［5-7］信息進行的異常檢測最受關注。Adam［1］利用光流直方圖描述空-時興趣點的局部信息；Kratz［3］提取空-時梯度來適應高斯模型，然后使用HMM檢測異常事件；Mehran［4］提出了一種社會力模型（Social force model）［8］，適用于群體異常行為檢測的新方法，該方法利用LDA（Latent dirichlet allocation）檢測異常。在特征描述上不斷更新的研究結果表明，采用合適的特征描述子會對檢測結果起到積極作用。由Klaser等［9］提出的HOG3D描述器可以被看成是SIFT描述器在空-時域的一種擴展，它的特征基于3D梯度方向直方圖，且梯度的計算由積分視頻［10］完成，正多面體用于空-時梯度方向的均勻量化，因此，這個描述符能夠同時結合形狀信息和運動信息。

文獻［11］提出了一種基于正常事件樣本的稀疏重構方法，稀疏表示（Sparse Representation，SR）適用于高維度特征表示［11-12］。正常事件基于正常特征基的重構誤差小，而異常事件基于正常特征基的重構誤差大，這是基于稀疏重構方法的異常檢測的關鍵思想。文獻［13］對稀疏編碼公式進行了改進，在計算稀疏重構誤差時引入了一個鄰接矩陣，使得在最后將重構誤差與閾值比較判斷時，相鄰興趣點之間的運動信息也被考慮其中。其思想是，相鄰興趣點運動越相似，則視頻中發生的事件是正常事件的可能性越大。

本文在上述研究的基礎上，將拓展到空間領域的HOG3D描述子引入表征，提出了一種基于HOG3D描述器與稀疏編碼的異常檢測方法。在稀疏編碼過程中，構建字典也是一個重點，由高維度特征向量構建的過完備字典無法被直接使用于稀疏編碼當中，文獻［14］提出了一種基于K-SVD的字典訓練算法。KSVD是一種泛化K-mean算法，先基于現有字典對訓練樣本進行稀疏編碼，再更新字典原子去適應稀疏系數，接著再進入下一輪稀疏編碼和更新字典，根據預設迭代次數如此循環計算。本文在構建字典上使用了上述K-SVD適應稀疏性的字典構建算法，提出的檢測方法在實驗中獲得了驗證，并且在靈敏度方面較其他類似算法有良好的表現。

1　空-時興趣點的HOG3D描述法

HOG3D特征是一種基于空-時興趣點的局部特征。局部空-時特征能表征人物在視頻中的狀態和運動，并做到在有尺度變換、空時平移、背景模糊、多目標情況下的正常識別。這種特征通常直接作用于視頻流本身，省去了預處理中的一些步驟，例如運動分割和運動跟蹤。二維平面的Harris-Corner［6］興趣點檢測算法是檢測圖像在平面中x軸和y軸都有顯著變化的點。本文采用的空-時興趣點檢測方法是上述二維檢測算法向三維的擴展，這樣檢測的興趣點需要滿足在空間和時間的維度上都具有顯著的變化，只對這些興趣點進行是否異常的判斷。圖1展示了視頻數據庫中部分幀畫面及檢測得到的興趣點。

圖1　Weizmann數據庫jack和jump行為單幀圖像中檢測得的空-時興趣點Fig.1 Example spatio-temporal interest points detected in Weizmann database

對檢測得到的興趣點進行基于HOG3D的興趣點描述。HOG3D是三維空間的興趣點描述子，是SIFT描述子從二維空間到三維空間的擴展。HOG3D描述子是在一個興趣點周圍某個空間尺度和時間尺度下的特征向量，代表了這個空間尺度和時間尺度下的點。計算過程如圖2所示。描述子計算方式如下：

首先，在空-時興趣點檢測之后，不僅得到了興趣點的三維坐標（x，y，t），還得到了空間尺度σ和時間尺度τ，根據h=w=σ·σ0和l=τ·τ0，在興趣點周圍區域建立一個以h，w，l為長、寬、高的立方體，定義其為Q（cuboid），如圖2（a）所示。

將區域Q（x－w/2∶x＋w/2；y－h/2∶y＋h/2，t－l/2∶t＋l/2）分割成M×M×N個單元C（Cell），單個單元標記為ci（i=1，2，3，…，M2N），再根據S=2將ci分割成S3=23=8的子塊B（Block），單個子塊標記為bj（j=1，2，3，…S3），如圖2（b）所示。

對b內所有點的梯度均值進行統計，如圖2（d）所示，計算得到梯度均值然后采用正十二面體作為量化的多面體，每個面的中心坐標為P=（p1，p2，…，p12）T，pi=（0，±1，叫做黃金比例。如圖2（c）所示。通過式（1）得到映射結果q—b：

再將其經過閾值處理就得到了qb。

最后一步，對ci內的S3個qb取平均得到每個ci的，將M2N個ci按照H=（qb1，…，qbM2N）T順序排好，組成HOG3D描述器的最終特征向量H。

圖23　D梯度方向直方圖獲得過程Fig.2 HOG3D descriptor formulation

2　K-SVD字典訓練算法

訓練字典過程使得訓練樣本在所構建的字典上具有稀疏表示，本文采用K-SVD算法訓練字典。作為泛化K-mean算法，K-SVD是一種迭代算法，先基于現有字典對訓練樣本進行稀疏編碼，再更新字典原子去適應稀疏系數，接著進入下一輪稀疏編碼和更新字典，根據預設迭代次數如此循環計算。

設特征向量為Y，每列稀疏系數為xi，在字典D上，K-SVD算法根據稀疏性質定義的目標函數如下：

在字典更新階段，同時固定稀疏矩陣X和字典D中除了dk的其他列，尋找一個新的dk，使得對應的系數，X中的第K行xkT，具有最小的均方誤差。式中的懲罰項被改寫為

在稀疏編碼階段，首先固定字典D，對系數矩陣X進行尋優計算，優化問題則重寫為如下形式：其中：矩陣Ek表示去掉原子dk的成分后，在所有N個樣本中造成的誤差。對Ek和做變換，中只保留系數X中的非零值，Ek則只保留用相應乘積中非零值位置之項，記為，將做SVD分解，最后更新dk。

3　基于稀疏編碼模型的異常檢測

本文中，對異常事件的檢測被看作是一個稀疏編碼的問題。其基本思想是以獲得的關于正常事件的描述信息構建訓練字典D，D的每一列都用來作為重構信號的基。

在包含F幀的測試視頻段內，檢測得n個興趣點，提取包含興趣點的滑動窗內特征作為測試樣本，表示為Xi∈Rl，i=1，…，n，單段視頻的特征描述矩陣X=｛X1，…，Xn｝。通過訓練獲得過完備字典D=｛d1，…，dk｝，測試樣本在過完備字典D的投影為Xi=D ai，ai為展開系數。計算重構誤差J的公式如下：

相比于傳統的稀疏編碼公式，式（5）等號右邊多了第3項平滑正規項，此項將臨近興趣點之間的行為信息差異納入計算，其中的鄰接矩陣W采用高斯核函數。

解決上述問題可以歸結為解決如下的最優化問題：

在求解重構誤差J的最小值時，固定字典D，轉變一個為關于展開系數ai的凸優化問題。在得到測試視頻段內的所有測試樣本的重構誤差J后，計算其統計平均值：

根據Jre的正負判斷視頻段的異常情況，當Jre為正時，測試段為異常片段，反之，則為正常片段。

4　實驗結果與分析

實驗使用的標準數據庫有UMN群體異常行為數據庫、Weizmann個體行為數據庫。UMN數據庫記錄了群體性突發的異常行為，分辨率為320× 240，包含3個不同場景共7 738幀，場景1、2、3分別包含2、6、3個情節。實驗中分別使用場景1、2、3 中1、1、2個正常情節做訓練，首先檢測其中的空-時興趣點，利用HOG3D描述法得到特征向量集作為訓練樣本，然后經過PCA主成分提取及K-SVD訓練算法構建字典。最后，對同場景中其余的視頻序列進行以20幀為段的異常檢測。本文實驗在特征描述過程中尺度參數使用σ0=4，τ0=2，cell塊的個數選擇M=4，N=2。針對每次異常檢測，作出檢測結果的ROC曲線，選取曲線上最靠近坐標圖左上方的點的閾值為經驗閾值。

圖3、圖5、圖7分別為場景1、2、3中檢測結果為正常行為的部分視頻幀圖像，根據畫面內容可以看到，場景內的人群隨意走動，無異常行為發生，因此，檢測結果符合地面實況。圖4、圖6、圖8分別顯示了在場景1、2、3中檢測結果為異常行為的視頻片段中的部分幀，且首行視頻序列左上角的字體“Abnormal Crowd Activity”為數據庫預先做好的異常標記，“Abnormal Event！”為本文方法檢測得到的異常結果標注。選取經驗閾值為0.029 0時，場景1檢測結果較原視頻異常結果標注提前25幀報警，場景2、場景3的異常檢測結果分別較原視頻異常結果標注提前22幀及44幀。將本文算法與基于社會力模型的檢測［15］、基于時空興趣點與多尺度運動直方圖的稀疏編碼檢測［16］、基于快速稀疏編碼與驚奇計算的檢測［17］進行檢測靈敏度對比，結果列于表1。實驗結果表明，本文方法在各個場景中都表現出較為迅速的檢測能力。

圖3　場景1中正常行為的檢測結果（人群隨意走動）Fig.3 Normal behavior detection in scene 1

圖4　場景1中異常行為的檢測結果（人群突然四散逃逸）Fig.4 Abnormal behavior detection in scene 1

圖5　場景2中正常行為的檢測結果（人群隨意走動）Fig.5 Normal behavior detection in scene 2

圖6　場景2中異常行為的檢測結果（人群突然逃逸）Fig.6 Abnormal behavior detection in scene 2

圖7　場景3中正常行為的檢測結果（人群隨意走動）Fig.7 Normal behavior detection in scene 3

圖8　場景3中異常行為的檢測結果（人群突然逃逸）Fig.8 Abnormal behavior detection in scene 3

表1　UMN數據庫中本文檢測算法與類似方法的靈敏度比較Table 1 Comparison between our anomaly detection method and other similar methods

以檢測序列段首幀為橫坐標，以式（9）計算得到的相對重構誤差Jre為縱坐標作圖，結果如圖9所示。在視頻片段3 804幀至4 164幀間（場景2部分幀）順序連接的，包含正常序列和異常序列的共18段視頻序列中，其中以3 904、3 924、3 944、3 964幀為首，長度均為20幀的視頻序列段實況為異常，而其對應的相對重構誤差值為正值；其余的視頻序列段實況為正常，在圖中對應的相對重構誤差值則體現為負值。由此說明，利用本文檢測方法，將測試樣本用訓練好的字典表達，再計算重構誤差值，取檢測段內所有興趣點的重構誤差均值，求其對應于經驗閾值的相對重構誤差，根據其正負，最終能夠有效判斷出視頻內容是否異常。

圖9　UMN數據庫中不同幀段的相對重構誤差Fig.9 Relative sparse reconstruction errors of different sessions in the UMN database

ROC（Receiver Operating Characteristic）曲線用于評判多閾值情況下的二元分類的準確性。ROC空間將假陽性率（FPR）定義為X軸，真陽性率（TPR）定義為Y軸。TPR體現的是在所有實際為陽性的樣本中，被正確地判斷為陽性之比率，FPR體現的則是在所有實際為陰性的樣本中，被錯誤地判斷為陽性之比率。

其中：真陽性（TP）是判斷正確的異常事件；真陰性（TN）是判斷正確的正常事件；假陽性（FP）是判斷錯誤的異常事件；假陰性（FN）是判斷錯誤的正常事件。實驗以UMN視頻的目測實況為判別基準，對視頻片段的檢測結果做出真假判斷，然后取多個閾值，繪制出UMN數據庫基于視頻段的ROC曲線如圖10所示。

圖10　基于視頻段的UMN數據庫異常檢測的ROC曲線Fig.10 ROCs of abnormal behavior detection in the UMN database

Weizmann數據庫包含90個低分辨率視頻序列，為9名實驗人員各自10種不同的自然行為。實驗預先定義其中一種行為（如walk）作為正常行為，對Ira的walk行為視頻序列進行興趣點檢測，共88幀，獲得了53個興趣點。應用HOG3D描述法獲得53個興趣點的特征向量，并將其作為訓練樣本構建字典。以20幀為段截取針對不同人員及不同行為的視頻序列，以獲得的興趣點特征向量作為測試樣本進行異常檢測。圖11、圖12顯示了Weizmann數據庫中的部分幀、幀內空-時興趣點的檢測結果，以及求解優化問題獲得的針對字典中每個樣本的稀疏系數。根據不同行為的測試段針對walk行為的檢測結果，根據式（9）計算得的相對重構誤差值列于表2。從表中數據可以看出，與預先定義的正常行為walk相一致的，不同實驗人員的walk行為，均具有負值的相對重構誤差，說明其重構誤差小于經驗閾值。而無論是同一人或不同人的異于walk的行為，均具有正值的相對重構誤差，即其重構誤差大于經驗閾值。

以上分析是對UMN和Weizmann這兩個經典數據庫進行實驗分析的結果。本文算法還在實際監控視頻中進行實驗。實驗對象是不同光照下的同一個禁止出入大門的監控視頻，圖13、圖14所示為夜間監控視頻中的部分幀，圖15、圖16所示為日間監控視頻中的部分幀。實驗取視頻正常幀中前400幀做訓練，對其余的視頻序列做檢測，檢測結果顯示，正常事件中獲得的空-時興趣點主要集中在大門外疾馳的車輛上，如圖13、圖15所示。當有人靠近或攀爬大門時，檢測結果顯示發生異常，如圖14、圖16所示。實驗結果表明，對于背景有運動干擾的較復雜監控畫面，本文提出的異常檢查方法仍能具有良好的檢測效果，并具有良好的光照魯棒性。

圖11　walk行為的興趣點及其稀疏系數Fig.11 Sparse and dense representative coefficients of normal samples

圖12　Skip、jack行為的興趣點及其稀疏系數Fig.12 Sparse and dense representative coefficients of abnormal samples

表2　Weizmann數據庫中各種行為的相對重構誤差Table 2 Relative sparse reconstruction errors of test activities in the Weizmann database

圖13　夜間環境下檢測結果為正常事件的部分幀Fig.13 Normal event detection in thesurveillance video（midnight）

圖14　夜間環境下檢測結果為異常事件的部分幀Fig.14 Abnormal event detection in thesurveillance video（midnight）

圖15　日間環境下檢測結果為正常事件的部分幀Fig.15 Normal event detection in thesurveillance video（daytime）

圖16　日間環境下檢測結果為異常事件的部分幀Fig.16 Abnormal event detection in thesurveillance video（daytime）

5　結束語

本文提出了一種視頻異常檢測方法，應用HOG3D空-時興趣點描述器，并結合稀疏編碼算法進行異常行為分析。在初始字典構建時使用了K-SVD算法，使得初始字典在正常事件的表達上有很好的稀疏性。在UMN群體異常數據庫和Weizmann個體行為數據庫中進行了算法實踐。實驗結果表明，本文算法能夠快速、有效地檢測出異常事件并給出提示，算法的實用性同樣在實際拍攝的監控視頻上得到有效驗證。

［1］ ADAM A，RIVLIN E，SHIMSHONI I，et al.Robust real-time unusual event detection using multiple fixed-location monitors ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（3）：555-560.

［2］ KIM J，GRAUMAN K.Observe locally，infer globally：A space-time MRF for detecting abnormal activities with incremental updates［C］//2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR 2009）.Miami，Florida，USA：IEEE，2009：2921-2928.

［3］ KRATZ L，NISHINO K.Anomaly detection in extremely crowded scenes using spatio-temporal motion pattern models［C］//2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2009）.Miami，Florida，USA：IEEE，2009：1446-1453.

［4］ MEHRAN R，OYAMA A，SHAH M.Abnormal crowd behavior detection using social force model［C］//2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2009）.Miami，Florida，USA：IEEE，2009：935-942.

［5］ LAPTEV I.On space-time interest points［J］.International Journal of Computer Vision，2005，64（2/3）：107-123.

［6］ DOLLáR P，RABAUD V，COTTRELL G，et al.Behavior recognition via sparse spatio-temporal features［C］//2nd Joint IEEE International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance，2005. USA：IEEE，2005：65-72.

［7］ BLANK M，GORELICK L，SHECHTMAN E，et al.Actions as space-time shapes［C］//Tenth IEEE International Conference on Computer Vision2005，ICCV 2005.Beijing：IEEE，2005，2：1395-1402.

［8］ HELBING D，MOLNAR P.Social force model for pedestrian dynamics［J］.Physical Review E，1995，51（5）：4282.

［9］ KLASER A，MARSZA?EK M，SCHMID C.A spatiotemporal descriptor based on 3d-gradients［C］//BMVC 2008-19th British Machine Vision Conference.UK：British Machine Vision Association，2008，275：1-10.

［10］ WILLEMS G，TUYTELAARS T，VAN GOOL L.An efficient dense and scale-invariant spatio-temporal interest point detector［M］//10th European Conference on Computer Vision.Marseille.France：Springer Berlin Heidelberg，2008：650-663.

［11］ CONG Yang，YUAN Junsong，LIU Ji.Sparse reconstruction cost for abnormal event detection［C］//2011 IEEE Conference on Computer Vision and Pattern Recognition（CVPR）. Providence，RI：IEEE，2011：3449-3456.

［12］ ZHANG Tianzhu，GHANEM B，LIU S，et al.Robust visual tracking via structured multi-task sparse learning［J］. International Journal of Computer Vision，2013，101（2）：367-383.

［13］ ZHAO B，FEI-FEI L，XING E P.Online detection of unusual events in videos via dynamic sparse coding［C］//2011 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）.Colorado Springs，USA：IEEE，2011：3313-3320.

［14］ AHARON M，ELAD M，BRUCKSTEIN A.K-SVD：An algorithm for designing overcomplete dictionaries for sparse representation［J］.IEEE Transactions on Signal Processing，2006，54（11）：4311-4322.

［15］ MEHRAN R，OYAMA A，SHAH M.Abnormal crowd behavior detection using social force model［C］//IEEE Conference on Computer Vision and Pattern Recognition，2009.CVPR 2009.Miami：IEEE，2009：935-942.

［16］ 謝錦生，郭立，趙龍，等.一種基于稀疏編碼模型的視頻異常發現方法［J］.小型微型計算機系統，2014，35（4）：917-921.

［17］ 謝錦生，郭立，趙龍.基于快速稀疏編碼與驚奇計算的視頻異常檢測方法［J］.中國科學技術大學學報，2013，43（7）：561-568.

Abnormal Behavior Detection Using Sparse Coding and HOG3D Descriptor

HE Cong-qin， ZHU Yu， CHEN Ning
（School of Information Science and Engineering，East China University of Science and Technology，Shanghai 200237，China）

In this paper，an abnormality behavior detect method based on sparse coding is proposed and the HOG3D descriptor is utilized to capture appearance and motion information of the surveillance videos. Firstly，a set of training data are extracted from normal events.And then，K-SVD method is utilized to construct the dictionary atoms such that each normal member attains the best representation under the strict sparsity constraints.In the process of sparse coding，by taking a video session as a sample，we introduce the relative sparse reconstruction error over the normal dictionary to measure the level of normal of the testing sample.When the relative sparse reconstruction error is positive，the sample would be judged as abnormal.The proposed method is tested via UMN database，Weizmann database and real world surveillance videos，which show that the proposed method can reliably detect the unusual events in the video sequence.

sparse coding；abnormal behavior detection；sparse reconstruction error；HOG3D descriptor；K-SVD

TP181

A

1006-3080（2016）01-0110-09 DOI：10.14135/j.cnki.1006-3080.2016.01.018

2015-03-24

國家自然科學基金（61271349）；中央高校基本科研業務費專項資金（WH1214015）

何聰芹（1991-），女，浙江人，碩士生，研究方向為數字圖像處理、稀疏表示、異常行為檢測。E-mail：amberhcq@163.com

朱 煜，E-mail：zhuyu@ecust.edu.cn