基于非负矩阵分解与相似性分析的运动目标检测

范新南，薛瑞阳，史朋飞，李 敏，倪建军

(河海大学物联网工程学院，江苏 常州 213022)

0 引 言

运动目标检测指的是将运动目标从图像序列中提取出来，是计算机视觉处理领域的重要一步，在目标追踪、视频监控、异常行为分析等领域有着广泛的应用[1]。目前，常用的目标检测算法有：基于差分的方法、基于光流场的方法以及基于多特征融合的方法。

基于差分的方法[2-4]主要是指背景差分法和帧间差分法，这一类方法通过观察当前帧相对于背景模型或相邻帧发生变化的像素点，从而检测出运动目标。这一类方法计算速度快，对静态背景下的运动目标检测具有较好的检测效果，但对光照变化与背景噪声点十分敏感，而且它仅考虑了像素点在时间域上的变化，忽略了像素点的空间关系。基于光流场[5-6]的方法是通过观察各个像素点在相邻帧中的空间位置变化，从而构建出像素点的运动场。光流法不仅包含了运动目标信息，同时包含了关于运动场景的三维信息，但这种方法对光照变化非常敏感，而且引入平滑约束条件后的光流计算方法复杂度高，很难满足运动目标检测实时性的要求。基于多特征融合的方法[7-9]是通过提取图像在时空域上的纹理、颜色、亮度等特征，使用特征匹配的方法实现运动目标检测。这一类方法针对不同的动态背景的干扰使用不同的特征进行融合，可以获得较好的检测结果。

本文在基于非负矩阵分解(NMF)的背景恢复算法[10]的基础上，提出一种改进的非负矩阵分解背景恢复算法；同时针对自然场景中树叶晃动等干扰提出使用核密度估计(KDE)进行前景区域检测的方法，在检测出的前景区域中，通过分析背景模型与当前帧像素点的相似性实现前景目标的检测。

1 基于NMF的背景恢复算法

1.1 非负矩阵分解问题描述

非负矩阵分解[11]指的是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。对于一个给定的非负矩阵V∈Rn×m,NMF算法可以找到2个非负矩阵W∈Rn×r和H∈Rr×m，使得下式成立：

V≈W×H

(1)

式(1)可以理解为：对于原始矩阵V，其列向量可以看作是对矩阵W中所有的列向量进行加权求和的结果，而所使用的权重系数就是矩阵H中对应列向量的元素。因此，矩阵W也称为基矩阵，它表示原始数据中隐藏的基本结构信息。

相对于主成分分析(PCA)、矢量量化(VQ)等矩阵分解方法，NMF可以保证分解结果的非负性。在进行图像处理时，图像矩阵中的负值数据往往没有实际意义，仅仅是一种数学计算的结果，而非负元素则可以解释为图像灰度值的变化情况，更加符合实际情况。

1.2 非负矩阵分解实现原理

NMF求解过程可以看作是一个优化过程[12]，根据公式(1)可以构造出噪声矩阵E:

E=V-W×H

(2)

NMF的求解问题就可以转换为寻找非负矩阵W和H，使得‖E‖最小，若以欧氏距离作为代价函数，该问题就转化为求解下式：

(3)

考虑到非负的约束条件，在使用梯度下降法进行求解时，需要采用乘性迭代规则对目标矩阵W和H进行迭代，最终得到如下的迭代规则[13]：

(4)

从式(4)可以看出，由于采用了乘性迭代，所以只要初始化的W与H矩阵是非负的，就可以保证迭代结果的非负性。

1.3 基于修正的NMF背景恢复算法

正如1.1节中所提到的，一个原始数据矩阵经过非负矩阵分解后得到的基矩阵表示的是原始矩阵的基本结构信息。而在连续的图像序列中，背景区域基本保持不变，每一帧图像都可以看作是由背景图像叠加前景对象得到的，因此背景图像可以看作是一个图像序列的基本结构信息。基于上述理论，可以通过非负矩阵分解的方法从连续的图像序列中恢复出背景图像。

在进行背景恢复时，通常将第i帧原始图像转换成为列向量vi，由连续m帧构成的m个列向量组成原始矩阵V=[v1,v2,…,vm]，对V进行非负矩阵分解后得到的基矩阵W就是背景模型[10]。可以看出，原始矩阵中包含的背景越纯净，恢复出来的背景模型越精确。但在实际情况中，由于有运动目标的信息与噪声点的影响，虽然可以恢复出大致的背景图像，但是会包含各种各样的干扰点，这对后续的精确提取会造成很大的影响，因此提出了对原始数据矩阵进行“异常数据”修正的处理。这里所定义的“异常数据”是指对相同位置的像素点灰度值进行统计后的离群点，满足下式：

gabnormal={g|g∉(μ-kσ,μ+kσ)}

(5)

其中gabnormal为离群点集合，即“异常数据”，g为同一位置上所有像素点的灰度值集合，μ为g的均值，σ为其标准差，k为任意正整数。式(5)认为一组统计值中与均值偏差超过k倍的标准差的数据即为离群点。在连续图像序列中，背景点通常分布在统计均值附近，而前景点则远离均值成为离群点。对于检测出来的离群点，可以使用g的众数代替原始值进行修正。

在进行背景恢复时，对于由图像序列组成的原始矩阵V，对其每一行的数据按照上述过程进行“异常数据”的判定与修正，得到修正后的矩阵V′，然后使用NMF算法进行对V′进行分解，得到基矩阵W，对W进行重构，使其与原始图像大小一致，即可恢复出较为精准的背景图像。

对修正前后的背景恢复算法进行对比，结果如图1所示，主要对比区域为图中矩形框区域。图1(a)为CDNET数据集中highway测试视频中的第421帧，图1(b)为使用NMF进行背景恢复得到的结果，图1(c)为修正后的背景恢复结果。图1(d)上下2幅图片分别为图1(b)与图1(c)中矩形的区域，可以看出，修正前的背景恢复图像有明显的“条状”残留，而修正的NMF恢复出来的背景更加纯净。按照下式可以计算恢复出的背景与原始背景间的均方误差，可作为评价背景恢复效果的一个指标：

(6)

其中M与N代表图像的分辨率,bij代表恢复出的背景中像素点(i,j)的灰度值，rij代表真实背景中像素点(i,j)的灰度值。通过计算得到图1(b)与真实背景之间的均方误差为321.3351，图1(c)与真实背景之间的均方误差为44.8123，这进一步说明了修正后的背景恢复更接近真实背景。

(a) 原始图像 (b) NMF恢复结果

(c) 修正NMF恢复结果 (d) 区域对比图1 背景恢复结果

2 前景区域提取

将背景恢复出来以后，可以通过计算背景与当前帧像素点之间的相似性来实现前景的提取，但由于树叶晃动等干扰的存在，逐点判断会产生较大误差，而且会将大部分计算资源浪费在一些明显具有背景特征的区域。如果先将运动区域提取出来，然后在这些区域进行精确提取，就可以避免上述问题的发生。

通过观察运动目标与动态背景在空间的变化，可以发现，在连续的图像帧内，运动目标的空间位置会不断变化，而动态背景，诸如树叶扰动等干扰，其空间位置虽然会发生变化，但只发生在一个固定范围的区域内，在这一区域内，像素点的总体特征不会发生较大的变化，这一特性可以用图像块内像素点的统计特征的变化来表示。在一个固定大小为m×n的图像块内，如果有运动目标经过，则该图像块的整体特征会发生较大的变化，否则不会有太大的变化，该变化过程可用核密度估计(KDE)的方法进行估计。这里使用高斯核作为KDE的核函数[14]，其表达式为：

(7)

其中xt代表第t帧m×n大小的图像块内所有像素的灰度统计特征，本文取块内像素的灰度均值，N代表连续图像帧的帧数，xi为第i帧图像块信息，σi代表核宽，使用相邻帧间样本的绝对差中位数计算[14]。式(7)利用t时刻前后相邻N帧图像块的灰度均值作为采样样本，计算观察到的第t帧各图像块灰度均值为xt的概率，KDE充分利用了图像块的历史帧信息，通过对比其历史帧信息与当前帧的信息，判断其属于前景的可能性。式(7)得到的值越小，代表该图像块属于前景的可能性越小，反之代表其属于前景的可能性越大。

前景区域提取的实验结果如图2所示，图2为对图1(a)进行前景区域提取的结果。图2(a)为对图像按照式(7)计算得到的结果，分块大小为10×10，图2(a)中各小方块亮度大小代表该图像块属于前景的概率的大小。由于进行了分块，因此图2(a)的分辨率是原始图片的1/(10×10)，实验为了方便观察，将图2(a)进行了手动放大。对于图2(a)中每个可能为前景的图像块，将其对应的原始图像中的区域标记为前景区域，即可得到图2(b)的前景区域提取结果。

(a) KDE结果图 (b) 前景区域提取结果图2 前景区域提取

这一方法通过对图像分块，使用块内像素灰度均值作为各个图像块的特征，弱化了动态背景像素点变化对检测结果的影响，提取出了运动目标所在的大致区域。在后续步骤中，只需要在前景区域进行前景像素点的提取即可。

3 前景像素点提取

在进行前景像素点的精确提取时，只需要分析前景区域中待检测帧的像素点与背景相应位置像素点的相似性即可。考虑到单个像素点包含的信息较少，无法实现较为准确的相似性分析，因此采用一个向量作为待检测像素点的特征进行相似性分析[15]。以待检测帧t为例，像素点(i,j)的特征可以使用由点(i,j)及其邻域中的像素点组成的向量[ti-k,j-k,…,ti,j,…，ti+k,j+k]T表示，其中ti,j表示第t帧像素点(i,j)的灰度值。上式认为在进行前景像素点的判断时，每个像素点与其邻域中的像素点是相互影响的，充分利用了像素点在空间上的联系，使得检测结果更加精准。对于背景相同位置的像素点，使用同样的思想构造向量，并按照下式计算2个向量之间的相似性：

(8)

其中D代表像素点(i,j)的k邻域，Tij表示第t帧像素点(i,j)的向量，Bij表示相应的背景向量。对于公式(8)计算得到的值，如果大于指定阈值Th，则认为当前像素点是前景像素点，否则认为是背景像素点，阈值的选取与当前帧所有像素点的相似性相关。通过计算图2(b)的前景区域与图1(c)恢复出的背景之间的相似性，可以得到如图3所示的统计结果。

图3 相似性统计直方图

图3横坐标为前景区域中所有像素点与相应的背景像素点之间的相似性，纵坐标为相应的统计频数。从图中可以看出，相似性较低的点(即前景点)较多，而相似性比较高的点(即背景点)则较少，这是因为计算区域是提取出来的前景区域，该区域中前景占较大比例。上文提到的阈值Th选取直方图中频数变化趋于平缓的“转折点”，如图3中横坐标为25左右的点。经过反复实验验证，阈值符合下式：

(9)

其中α为0.05～0.1之间的任意实数，F为前景区域。式(9)说明前景像素提取的阈值可以选取为当前帧所有像素点相似性最大值的α倍。

4 实验结果与分析

为了验证算法的有效性，本文使用3段测试视频进行了前景提取实验，同时与GMM算法和滑动窗NMF算法[10]进行了对比，实验所使用的测试数据集为Intelligent_Room(IR)，CDNET中的highway和pedestrians。实验中使用连续的40帧图像，式(5)中“异常点”判定时k取1，前景区域提取阶段的图像分块大小取10×10，前景像素点提取阶段向量的构造选取像素点的8邻域构造向量。

实验结果如图4所示，图4中第一行与第二行主要考察室外前景检测，第一行的highway数据集中有树叶扰动，第二行测试数据集pedestrians中行人由阴影区进入光照区，并且部分背景区域有微弱的光照变化。第三行考察室内的前景检测，在测试集IR中，运动目标处于室内，且光照发生了变化。

(a) 原始帧 (b) GMM检测结果 (c) 滑动窗NMF检测结果 (d) 本文方法图4 实验结果对比

从图4的结果中可以看出GMM算法的检测结果有精准的目标轮廓，但运动目标内部会出现大量的“空洞”，并且GMM模型对噪声的抑制能力有限，在highway数据集中，由于出现较为强烈的背景扰动，GMM检测出来的结果包含了大量的背景噪声干扰点。而文献[10]中提出的NMF与帧差法结合的提取算法则强烈依赖于背景恢复的精确程度，由于原始NMF恢复出的背景包含前景残留，因此导致检测结果会有明显的“拖影”现象，当运动目标运动速度较慢时，这种现象会更加明显，如pedestrians数据集的提取结果，而且由于采用了帧差法，所以如果光照发生变化，就会导致出现图4中IR数据集提取结果中的大面积误检现象。同时，由于GMM算法、NMF结合帧差法这2种算法均是基于像素点的逐点检测方法，因此在前2个数据集中，背景的扰动会导致检测结果出现大量的干扰点。而本文中所提到的方法由于对NMF背景恢复算法进行了修正，恢复出来的背景更加精准，同时先对前景区域进行了提取，因此提取到的运动目标更加完整，同时背景干扰点也更少。为了进一步说明本文算法的有效性，此处使用前景识别率(Re)、精确度(Pre)和综合测度(F-measure)这3个指标对IR数据集的测试结果进行分析，指标计算公式如下[16]：

(10)

(11)

(12)

其中TP与TN分别为正确检测的前景与背景像素点数，FP为误判为前景的像素点数，FN为误判为背景的像素点数。结果如表1所示，可以看出，本文中的算法在各个指标上均有良好的表现，优于GMM与滑动窗口NMF算法。

表1 算法性能对比

算法指标GMM滑动窗NMF本文算法Re0.25280.57940.7758Pre0.72570.26300.9441F0.37500.36180.8517

5 结束语

本文提出了一种运动目标检测算法。首先使用改进的NMF背景恢复算法对背景进行恢复，然后通过KDE估计出运动目标区域，最后使用相似性分析判断像素点是否属于前景。实验结果表明，改进的NMF背景恢复算法可以较为有效地恢复出背景，基于KDE的前景区域提取可以有效抑制空间位置变化不大的背景干扰，本文提出的算法适应大部分自然场景的运动目标检测。但该算法在进行前景区域提取时依赖于分块大小，因此，在后续的研究中，将主要研究如何确定合适的分块大小，或者根据图像内容实现自适应的分块。

参考文献：

[1] 马超,沈微,董景峰. 复杂背景中一种特定运动目标检测与跟踪方法[J]. 计算机工程, 2015,41(5):219-223.

[2] Yoshinaga S, Shimada A, Nagahara H, et al. Object detection based on spatiotemporal background models[J]. Computer Vision and Image Understanding, 2014,122:84-91.

[3] Liu Wei, Yu Hongfei, Yuan Huai, et al. Effective background modelling and subtraction approach for moving object detection[J]. IET Computer Vision, 2015,9(1):13-24.

[4] 吴剑舞,翁玲瑜,童怀. 一种基于改进ViBe的运动目标检测方法[J]. 计算机与现代化, 2015(7):50-54.

[5] Hariyono J, Hoang V D, Jo K H. Moving object localization using optical flow for pedestrian detection from a moving vehicle[J]. The Scientific World Journal, 2014-07-10, doi: 10.1155/2014/196415.

[6] 高军军,王创新. 基于时空结构张量的高速公路视频车辆检测[J]. 计算机与现代化, 2011(2):5-7.

[7] 王顺飞,闫钧华,王志刚. 改进的基于局部联合特征的运动目标检测方法[J]. 仪器仪表学报, 2015,36(10):2241-2248.

[8] 秦利斌,刘纯平,王朝晖,等. 一种改进的时空线索的视频显著目标检测方法[J]. 计算机工程与应用, 2015,51(16):161-165.

[9] Wang Xin, Ning Chen, Xu Lizhong. Spatiotemporal saliency model for small moving object detection in infrared videos[J]. Infrared Physics & Technology, 2015,69:111-117.

[10] 祝加祥,胡鹏程,何璇,等. 基于滑动窗非负矩阵分解的运动目标检测方法[J]. 计算机技术与发展, 2017,27(1):20-24.

[11] Yang Shangming, Yi Zhang, Ye Mao, et al. Convergence analysis of graph regularized non-negative matrix factorization[J]. IEEE Transactions on Knowledge and Data Engineering, 2014,26(9):2151-2165.

[12] Lee D D, Seung H S. Algorithms for non-negative matrix factorization[C]// Proceedings of the 13th International Conference on Neural Information Processing Systems. 2000:535-541.

[13] 毛翊君,赵知劲,尚俊娜. 不同学习速率下NMF盲源分离算法[J]. Hans Journal of Wireless Communications, 2015,5(5):91-97.

[14] Elgammal A, Harwood D, Davis L. Non-parametric model for background subtraction[C]// Proceedings of the 2000 European Conference on Computer Vision. 2000:751-767.

[15] Subudhi B N, Ghosh S, Ghosh A. Change detection for moving object segmentation with robust background construction under Wronskian framework[J]. Machine Vision and Applications, 2013,24(4):795-809.

[16] Zhang Erhu, Li Y C, Duan J H. Moving object detection based on confidence factor and CSLBP features[J]. Journal of Photographic Science, 2016,64(5):253-261.