基于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