近年来，公共安全问题日益突出，视频监控场景下的异常事件能被及时发现并进行积极的救援，从而减少了群众的人身伤亡与财产损失。因此，在视频监控场下事件的视频异常检测则显得特别重要。整个视频异常检测算法主要包括特征感知和模型异常检测，本文所针对的是视频监控场景下事件的群体异常。群体异常检测所提取的特征包括光流、高频空时特征、行为熵、群体密度等^[1-3]。Wang等人^[1]提出高频空时特征(HFST)来检测事件的异常行为，通过利用小波变换来提取高频信息，在频域上体现出随时间变化的动态特征。Ren等人^[2]引入行为熵来表示人类行为的不确定性，利用个体信息间的信息交互特性来挖掘场景中的重要信息，构建熵模型并实现异常检测。Kim等人^[3]通过频域纹理特征来估计群体密度，并利用群体密度特征判断人群是否异常。针对群体异常事件检测其建模方法主要分为基于重构误差的异常事件建模^[4-6]、基于分类与聚类的异常事件建模^[7-8]和基于统计学习的异常事件建模^[9-10]。重构误差建模首先根据事件间的关联性来构建正常事件的稀疏字典完成事件稀疏表示。然后以事件的重构误差与阈值间的对比来判定事件是否异常。Xie等人^[4]提出了基于贝叶斯惊奇计算的视频异常检测方法。该方法运用块匹配提取特征并得到多尺度运动矢量直方图在空间维度与时间维度上惊奇计算结合来达到异常检测的目的。该方法采用了惊奇算法虽然保证了高效鲁棒性，但持续更新模型将造成耗时过高。Cong等人^[5]提出了用稀疏重建成本(SRC)来给出异常检测的标准，通过非完全正态基集的加权线性重建来确定保证高检测率，但其高耗时性则影响了异常检测的快速检测的特性。Duan等人^[6]提出了一种基于稀疏重建的异常检测方法，训练集提取光流特征的多尺度直方图以及生成完备字典，在目标函数的系数项加权稀疏重建代价来检测异常与否。分类与聚类建模根据提取的特征中既含有正常数据又含有异常数据这一特性，因此把事件建模看成二分类问题。将仅含有正常数据看成聚类问题，距离聚类中心较远的特征视为异常数据。Mehranet等人^[7]提出了以简化的社会动力模型为基础，通过使用光流特征结合潜在狄利赫雷分配(LDA)的方法来完成异常检测。由于LDA是基于离散的有限单词表，因此该方法未将运动信息表达出来。Wang等人^[8]根据光流计算量大和空时梯度需要包含轮廓信息的缺陷，提出利用KLT角点作为特征代表运动的物体，在能减少数据处理的计算量的同时又保持丰富的运动信息，但该方法中的特征提取受到光照变化与相机距离的影响，这对运动物体的描述不够精确。统计学习建模是通过对大量训练样本特征进行学习，构建异常检测模型并将检测到的小概率事件判为异常。Zhu等人^[9]提出一种基于光流的高频特征(HFOF)来对拥挤场景下的异常检测，改变了以往在空时域上特征提取的传统，该方法很好的捕获目标运动的动态特性。Li等人^[10]提出了用混合动态纹理的方法进行检测，当用多个纹理模型建模时，需用纹理前后帧之间的对比信息。该方法的复杂度要远超过一般的纹理特征，其高耗时性则影响了异常检测的速度。

针对视频场景中数据量大检测速度慢的问题，对特征数据的提取及优化处理则十分重要。因此特征数据的优化成为异常事件检测算法研究的热点。由于图结构更好表述特征间的空间关系，并且在图结构尺度化后的特征仍然保留较强的关联性。本文为了进行特征数据的优化，提出了多尺度变换下的图结构的异常检测方法。在略微降低检测精度的前提下，尽可能减少待处理特征数据的计算量，实现特征数据的优化，从而达到快速的检测视频中的异常事件。

在视频异常检测过程中，为了实现视频异常检测算法的优化而达到快速异常检测的目的。本文利用光流特征、网格位置、边缘轮廓来构建光流特征图结构，然后对光流特征图结构进行尺度化操作，即对光流特征图结构进行图下采样和图规约来实现光流特征的优化^[11-12]。如图 1所示，利用光流特征图结构的最大特征向量的极性下采样来选择光流特征图结构的顶点集，再对下采样后的光流特征图结构进行Kron规约来构建顶点间的连接，达到重构尺度化后的子图结构。这样可以削减光流特征图结构的复杂程度并通过减少特征数来完成特征优化，最终实现快速异常检测。图结构的多尺度变换则是迭代尺度化变换，该部分在异常检测算法整体框图中有所体现。

利用金字塔Lucas-Kanade光流算法提取每一视频帧的光流特征$\left( {\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{v}}} \right)$，对应的网格大小为$M \times N$，设定光流划分阈值$T$，对高于阈值的光流分量进行颜色编码并且累积变化区域，得到运动区域边缘轮廓。将运动区域边缘轮廓，网格位置和光流特征构成光流特征图结构

$ \mathit{\boldsymbol{G}} = \left\{ {\mathit{\boldsymbol{V}}, \mathit{\boldsymbol{\varepsilon }}, \mathit{\boldsymbol{W}}} \right\} $

(1)

式中，$\mathit{\boldsymbol{V}}$是顶点(节点)的集合$\left| \mathit{\boldsymbol{V}} \right|{\rm{ = }}\mathit{\boldsymbol{N}}, \mathit{\boldsymbol{\varepsilon }}$是无向边集合，$\mathit{\boldsymbol{W}}$是含权重的邻接矩阵。利用阈值化得高斯核函数定义一条无向边$\mathit{\boldsymbol{e}} = \left( {i, j} \right)$连接顶点$i$和$j$的边权重${\mathit{\boldsymbol{W}}_{i, j}}$。

度矩阵$\mathit{\boldsymbol{D}}$是一个对角矩阵

$ \mathit{\boldsymbol{D}} = \left\{ {{d_{i, i}}} \right\} = \sum\limits_{j \in {N_i}} {{\mathit{\boldsymbol{W}}_{i, j}}} $

(2)

式中，${\mathit{\boldsymbol{N}}_i}$是图结构$\mathit{\boldsymbol{G}}$中相邻顶点的集合。

图拉普拉斯矩阵

$ \mathit{\boldsymbol{L}} = \mathit{\boldsymbol{D}}-\mathit{\boldsymbol{W}} $

(3)

图拉普拉斯矩阵$\mathit{\boldsymbol{L}}$是实对称矩阵，其完整的正交特征向量${\left\{ {{\mathit{\boldsymbol{u}}_\mathit{\boldsymbol{l}}}} \right\}_{\mathit{\boldsymbol{l}}{\rm{ = }}0, 1 \cdots, N-1}}$与非负特征值${\left\{ {{\mathit{\boldsymbol{\lambda }}_\mathit{\boldsymbol{l}}}} \right\}_{\mathit{\boldsymbol{l}} = 0, 1, \cdots, N-1}}$间的关系对于$\mathit{\boldsymbol{l}} = 0,1, \cdots ,\mathit{\boldsymbol{N}} - 1$满足$\mathit{\boldsymbol{L}}{\mathit{\boldsymbol{u}}_\mathit{\boldsymbol{l}}} = {\mathit{\boldsymbol{\lambda }}_\mathit{\boldsymbol{l}}}{\mathit{\boldsymbol{u}}_\mathit{\boldsymbol{l}}}$。并且按照特征值大小进行递增排序${\mathit{\boldsymbol{\lambda }}_0} \le {\mathit{\boldsymbol{\lambda }}_1} \le {\mathit{\boldsymbol{\lambda }}_2} \le \cdots \le {\mathit{\boldsymbol{\lambda }}_{N-1}}$，定义最大特征值与对应的特征向量为${\mathit{\boldsymbol{\lambda }}_{{\rm{max}}}} = {\mathit{\boldsymbol{\lambda }}_{N-1}}$和${\mathit{\boldsymbol{u}}_{{\rm{max}}}} = {\mathit{\boldsymbol{u}}_{N-1}}$^[13]。

光流特征图结构的下采样是由光流特征图结构的图拉普拉斯矩阵$\mathit{\boldsymbol{L}}$最大特征向值$\mathit{\boldsymbol{\lambda }}_{{\rm{max}}}$对应最大特征向量$\mathit{\boldsymbol{u }}_{{\rm{max}}}$的极性来选择顶点集$\mathit{\boldsymbol{V}}$。即

$ {\mathit{\boldsymbol{V}}_ + }: = \left\{ {i \in \mathit{\boldsymbol{V}}:{\mathit{\boldsymbol{u}}_{{\rm{max}}}}\left( i \right) \ge 0} \right\} $

(4)

$ {\mathit{\boldsymbol{V}}_ - }: = \left\{ {i \in \mathit{\boldsymbol{V}}:{\mathit{\boldsymbol{u}}_{{\rm{max}}}}\left( i \right) < 0} \right\} $

(5)

式中将光流特征图结构的顶点集$\mathit{\boldsymbol{V}}$分成$\mathit{\boldsymbol{V}}_ +$和$\mathit{\boldsymbol{V}}_ -$两个部分。该图拉普拉斯矩阵$\mathit{\boldsymbol{L}}$最大特征向量的非负极性对应的顶点集$ \mathit{\boldsymbol{V}}_ +$，该顶点集所连接的均为高权重边，能保持原光流特征图结构的基本属性。因此保留顶点集$\mathit{\boldsymbol{V}}_ +$并对顶点集$\mathit{\boldsymbol{V}}_ -$进行剔除，通过对顶点的筛选来完成光流特征图结构的下采样。

光流特征图结构的Kron规约是利用下采样后所选的顶点重新连接高权重边从而重构出光流特征图结构，并保留重要的结构特性。在特征光流图结构$\mathit{\boldsymbol{G}} = \left\{ {\mathit{\boldsymbol{V}}, \mathit{\boldsymbol{\varepsilon }}, \mathit{\boldsymbol{W}}} \right\}$上，根据其对应的图拉普拉斯矩阵$\mathit{\boldsymbol{L}}$和下采样后所选择的顶点的子集合${\mathit{\boldsymbol{V}}_1} \subseteq \mathit{\boldsymbol{V}}$形成规约后的光流特征图结构。Kron规约中根据下采样中选择的顶点来重新构建拉普拉斯矩阵$\mathit{\boldsymbol{L}}$，其重要公式为

$\mathit{\boldsymbol{K}}\left( {\mathit{\boldsymbol{L}}, {\mathit{\boldsymbol{V}}_1}} \right): = {\mathit{\boldsymbol{L}}_{{v_1}, {v_1}}}-{\mathit{\boldsymbol{L}}_{{v_1}, v_1^c}}\mathit{\boldsymbol{L}}_{v_1^c, v_1^c}^{-1}{\mathit{\boldsymbol{L}}_{v_1^c, {v_1}}} $

(6)

式中，${\mathit{\boldsymbol{L}}^{\rm{k}}}$是拉普拉斯矩阵$\mathit{\boldsymbol{L}}$关于${\mathit{\boldsymbol{L}}_{v_1^c, c_1^c}}$的Schur补，${\mathit{\boldsymbol{V}}_1}$为图下采样中被选择的顶点集，$\mathit{\boldsymbol{V}}_1^c$为待剔除的顶点集。这里的${\mathit{\boldsymbol{L}}_{A, B}}$表明子矩阵的$\left| \mathit{\boldsymbol{A}} \right| \times \left| \mathit{\boldsymbol{B}} \right|$组成整个拉普拉斯矩阵$\mathit{\boldsymbol{L}}$，其矩阵大小为$\mathit{\boldsymbol{A}}$的行数和$ \mathit{\boldsymbol{B}}$的列数。与可以看出与Kron规约的拉普拉斯矩阵${\mathit{\boldsymbol{L}}^{\rm{k}}} = \mathit{\boldsymbol{K}}\left( {\mathit{\boldsymbol{L}}, {\mathit{\boldsymbol{V}}_1}} \right)$相关的的加权光流特征图结构${\mathit{\boldsymbol{G}}^{\rm{k}}}$为

$ {\mathit{\boldsymbol{G}}^{\rm{k}}} = \left\{ {{\mathit{\boldsymbol{V}}_1}, {\mathit{\boldsymbol{\varepsilon }}^{\rm{k}}}, {\mathit{\boldsymbol{W}}^{\rm{k}}}} \right\} $

(7)

式中，$\mathit{\boldsymbol{\varepsilon }}^k$由非零权重的边集合构成的，经过Kron规约后的权重邻接矩阵为

$ W_{i, j}^{\rm{k}} = \left\{ \begin{array}{l} -L_{i, j}^{\rm{k}}\;\;\;\;i \ne j\\ 0\;\;\;\;\;\;\;\;\;\;{\rm{其他}} \end{array} \right. $

(8)

在Kron规约后致使光流特征图结构的顶点数减少，但各顶点间连接的边变得更密集时而无法有效捕获到重要局部连接性的信息，当图结构越不规则越复杂时则表现更为明显。在Kron规约后采用Spielman-Srivastava的频谱稀疏算法来稀疏光流特征图结构，并和Kron规约进行很好的结合^[14]。

针对视频集中需提取的特征数据多和检测速度慢的问题，从几个方面来完成特征的提取及优化，来达到快速异常检测。首先利用金字塔L-K光流算法估算光流值，从粗略到精细地完成底层特征向量的提取；然后设定运动区域，剔除区域外无关的干扰特征；最后对光流特征图结构进行多尺度变换，在不同的尺度化图结构中进行的异常检测，根据对检测精度与检测速度综合考虑后来选择合适的尺度化次数。图 2为快速异常检测算法的总体框图。

将每个场景的前$N$帧正常视频帧作为训练集，剩余的作为测试集。首先利用金字塔L-K光流算法提取训练集每一视频帧的光流特征$\left( {\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{v}}} \right)$，对高于运动区域划分阈值$T$的光流分量进行颜色编码，累积颜色块的变化区域得到运动区域的边界。利用运动区域的边缘轮廓、网格位置、光流特征构建一个稳定的光流特征图结构，并对光流特征图结构进行尺度化操作，即对光流特征图结构拉普拉斯矩阵最大特征向量的极性下采样和对光流特征图结构的Kron规约。在各个尺度的光流特征图结构上分别进行滤波，并将滤波过后的训练光流特征构建词袋形式，并送进LDA-iHMM的联合空时模型中，学习得到“正常”模型参数$\mathit{\boldsymbol{\lambda = }}\left( {\pi, \mathit{\boldsymbol{\varphi }}} \right)$。测试集的光流特征向量作为已训练“正常”模型的输入进行异常检测，计算得到测试集每一帧的对数似然函数。将测试数据集的对数似然与设定阈值进行对比，若连续3帧测试集的对数似然函数的值均大于阈值时，该视频帧判定为异常，反之则判为正常。

图 3是以UMN数据集室外草坪场景为例，光流特征图结构的构建及多尺度变换，这是整个视频异常检测的关键部分。将视频进行网格划分，对每个网格中的特征进行迭代仿射计算得到底层特征光流。对于目标运动区域外的特征剔除，运动区域内的光流特征均在对应光流特征图结构的顶点上。在对光流特征图结构进行图下采样与图规约后，得到较为稀疏且有强的关联的光流特征图结构。利用光流特征图结构的尺度化来减少光流特征的数量，从而减少了光流特征处理的计算时间，实现快速异常检测。

实验采用Matlab编程并使用GSPBOX(A toolbox for signal processing on graphs)图结构上的信号处理工具箱^[15]，其中Matlab版本为R2016a，实验电脑配置Windows10的64位操作系统、2.53 GHz Inter I3 CPU、6 GB RAM。

为测试本文中异常检测的效果，引用了明尼苏达大学的一个最近公开逃逸数据集UMN，共3个分辨率均为240×320像素视频场景。实现的主要参数设置如下：训练的正常视频帧$N$=180，网格大小为24×32，保留图像小尺度信息$FineScale$=1，牛顿拉法森算法迭代次数$K$=100，运动区域划分阈值$T$=0.095，图稀疏参数$X$=0.25。图 4是根据测试集的对数似然函数所对应于事件的正常与异常情况。

为了比较不同尺度光流特征图结构下异常事件的检测效果，统计各个视频集异常帧数量。采用帧速率为15帧/s的UMN数据集，UMN1共有726帧，其中118帧异常，UMN2共有2 072帧，其中320帧异常，UMN 3共有1 071帧，其中138帧异常。在相同场景下的测试视频，各次尺度化的光流特征图结构的异常检测所得到真阳性率(TPR)和假阳性率(FPR)，画出ROC曲线。通过比较ROC曲线下的面积(AUC)来判断在各个尺度光流特征图结构下检测效果，AUC值越大，则对应检测效果就越好。为了实现快速异常检测的目的，在得到各检测效果的基础上，还考虑在各个尺度光流特征图结构下的检测速度和其他检测算法的检测速度间的比较。

图 5为不同尺度化光流特征图结构下异常检测的ROC曲线图。图 6为各尺度下图结构的检测算法与其他检测算法间ROC曲线的对比。表 1为各个检测算法在UMN数据集中AUC值。表 2给出各尺度下光流特征图结构的检测速度对比情况。结合表 1和表 2可得出随着尺度化次数的增加，虽然检测精度会依次略微的降低，而且其检测速度得到很大的提升。尺度化图结构仅一次时的AUC值为0.924，与原图结构下检测AUC值0.955相比下降了3.2 %，而检测速度由0.246 s/帧到0.199 s/帧提升了19.1 %，这对于整个视频集的检测速度提升效果较为明显。但是随着尺度化次数的提高，尺度化两次的检测精度降低了7.3 %，这时检测效果开始不符合要求。表 3为各检测算法的检测速度的比较，可以看出本文的算法提升后的检测速度明显高于对比的算法。

为了评估本文方法的有效性，增加了更有挑战性难度的Web数据集来进行实验。该数据集主要包括12个正常场景和8个异常场景。将所有的视频场景的分辨率统一调整为480×360像素，帧速率为15帧/s。将网格大小设为48×36，将所有正常场景的视频帧作为训练集，其他参数设置保持不变。图 7为Web数据集的6个场景样本帧。

图 8为Web数据集中各检测算法的ROC曲线。表 4为Web数据集中各个检测算法在Web数据集中AUC值。表 5为Web数据集中各检测算法的检测速度的比较。结合表 4和表 5可也依然可知随着尺度化次数的增加，虽然检测精度会依次略微的降低，而且其检测速度得到很大的提升。尺度化一次图结构的AUC值为0.770，与原图结构下检测AUC值0.785相比下降了1.9 %，而检测速度由0.419 s/帧到0.285 s/帧提升了32 %；尺度化两次图结构的检测精度降低了4.8 %，检测速度提升了51 %。因此，需要根据检测精度与检测速度的综合考虑后选择尺度化次数是一次还是两次。但是随着尺度化次数的提高，此时检测效果开始不符合要求。

针对视频监控场景下，存在着待处理的数据量大和异常检测速度太慢的问题，提出了图结构多尺度变换来完成特征优化的方法，从而进行快速异常检测。本文利用不规则的网络图结构来更好表述特征之间的空间关系，并且图结构尺度化后的特征之间仍然保留有较强的空间关系。本文方法应用在不同的视频监控场景下，根据对检测精度与检测速度的综合考虑后选择合适的尺度化次数，这有利于快速异常检测。