低秩矩阵和结构化稀疏分解的视频背景差分方法

刘鑫,张钊强,姚佳文,郭莉莉,齐春

(1.西安交通大学电子与信息工程学院,710049,西安;2.云南大学信息学院,650091,昆明)



低秩矩阵和结构化稀疏分解的视频背景差分方法

刘鑫1,张钊强1,姚佳文1,郭莉莉2,齐春1

(1.西安交通大学电子与信息工程学院,710049,西安;2.云南大学信息学院,650091,昆明)

针对基于矩阵分解的视频前景检测传统算法中忽视前景元素之间相关性会导致检测结果容易受噪声干扰和运动目标检测不完整等问题,提出了一个低秩矩阵和结构化稀疏分解的视频背景差分算法。该算法充分考虑到视频前景区域的结构化分布特征,利用结构化稀疏范数对前景进行约束;针对矩阵分解方法中参数选择的难题,采用了一种基于运动显著性判定的两步法来实现动态背景去除和正则化参数的自适应选择,即第一步利用低秩和结构化稀疏分解获得运动候选块,第二步对运动候选块进行显著性分析并利用自适应正则化参数的块稀疏分解进行前景检测。实验结果表明:与现有的基于矩阵分解的前景检测方法相比,该算法能够更加适应复杂多变的视频环境,在I2R测试库中检测出的前景有较高的精确度和召回率。

前景检测;背景差分;矩阵分解;低秩表示;结构化稀疏

视频前景检测是智能视频监控、行为分析[1]等计算机视觉系统的关键步骤,伴随着近几年来人们对于社会安全问题的日益关注而得到广泛的研究和应用。在各种检测算法中,背景差分被认为是提取前景目标的最有效方法,而背景差分算法核心问题在于如何进行有效的背景建模。作为更高层视觉任务(如目标跟踪和行为识别)的基础环节,背景模型的好坏将直接影响到整个系统的准确性和鲁棒性。

目前国内外关于背景建模的方法大致可以归为以下2类。一类方法为基于像素级的背景模型,包括混合高斯(MoG)模型[2-3]、贝叶斯模型[4]、马尔科夫随机场(MRF)模型[5]、背景字典(Code Book)模型[6]、像素采样(ViBe)模型[7]等,但以上基于单像素建模的方法都对背景做了特殊的、固定的假设,并且单像素的独立建模往往忽略了像素间的联系和相关性。综上原因,在复杂多变的视频场景下,基于像素的前景检测算法的表现往往不尽人意。另外一类方法是基于图像级的背景模型,最新的研究热点是基于压缩感知理论的前景检测方法。在压缩感知的理论框架下,Candes等人提出了一种鲁棒主成分分析法(RPCA)[8-9],假设由视频中的帧组成的矩阵可以分解成2个分别具有低秩和稀疏特性的矩阵,认为背景矩阵具有低秩特性,前景矩阵具有稀疏特性,从而提出了一个基于主成分追踪(PCP)的鲁棒主成分分析法[9],用核范数对背景矩阵进行约束,用l1范数对前景矩阵进行约束。与之前所介绍的方法相比,这类视频前景检测算法仅仅需要矩阵分解,同时矩阵分解的机制不需要初始训练,因而可以实现背景估计和前景检测任务的同步进行,而传统的背景提取方法(如混合高斯法等)有着繁多的输入参数。

因此,基于矩阵分解的视频前景检测方法如PCP方法是近年来的一个研究热点。然而,PCP方法有2个可改进之处:①PCP方法没有考虑到前景信号的结构特性;②PCP方法中单一的、固定的尺度参数设置导致模型容易受到动态背景的干扰。针对这2个问题,本文提出了一个两步的框架,如图1所示。首先利用结构化稀疏范数对前景进行建模,提出了一个基于低秩和结构化稀疏分解的前景检测方法,该方法考虑了前景元素的结构信息;然后采用一种时间片段数据运动显著性分析的方法,通过对分解后得到的候选目标进行统计,并计算出相应的平均运动显著性,再根据平均显著性值对每个目标块给予相应的正则参数值;最后采用块稀疏鲁棒主成分分析法进行前景检测。

图1 本文两步框架算法图

1 低秩和结构化稀疏分解前景检测

1.1 PCP方法回顾

PCP法可用公式表示为

‖L‖*+λ‖S‖1,D=L+S

(1)

式中:D∈Rm×n为观测数据,由多个视频帧通过列重排后构成,即D矩阵中的每一列对应原始视频的一帧;L和S分别表示进行分解之后得到的背景矩阵和前景矩阵;‖L‖*表示矩阵L的核范数(nuclear norm),即矩阵L的奇异值之和;‖S‖1为矩阵的l1范数,即矩阵S中元素绝对值之和。

统计信号处理的知识表明[10],当PCP法利用l1范数约束问题中的稀疏度时,其假设稀疏信号的每一个元素是独立分布的,然而在许多实际问题当中,稀疏信号的分布并不是独立的。例如,在人脸识别领域,实际进行测试的人脸图像中由光照变化造成的阴影、遮挡等不属于人脸部分的异常值在空间上是连续分布的;在视频前景检测中,前景信号可以看成是不属于背景模型的异常值,但前景像素并不是无意义的随机出现在某个位置,它们通常在空间上具有结构化分布的特征。

1.2 基于重叠块的结构化稀疏诱导范数

为了能够定义更加复杂的结构,Mairal等人提出了重叠块结构的结构化稀疏诱导范数[11],定义式为

(2)

式中:s为具有结构化分布特性的稀疏信号;sj为s的第j个元素;‖·‖∞代表l∞范数,指所有元素的最大绝对值;ηg为每个组的权重,一般取值为1;G为预先定义的组分布的集合,其中每一个组分布为g;sg为组分布为g的s的子集。

图2给出了本文所采用的基于3×3像素大小重叠块的图结构G。在一个8×8像素大小图片上,从最左上角开始,每一个块分别向右和向下移动一个像素,直至完成整个遍历。在这种设计下,3×3像素大小重叠块的组结构对于一个8×8像素大小的图片有36个组,即G={g1,…,g36},每一个块与其4邻域的邻居块会重叠6个元素,而每一个块内元素就构成了一个组g。

图2 3×3像素大小重叠块图结构

1.3 低秩和结构化稀疏模型

因为结构化稀疏范数允许定义复杂的结构,所以能够很好地体现出实际问题中稀疏信号的结构化分布特性,本文利用重叠块作为结构特征对视频中的前景信号进行约束。

对于视频前景检测问题,式(2)给出的是一帧视频中前景信号的结构化约束,这相当于对前景矩阵的一列元素进行定义。通过对式(2)进行扩展,本文引入如下一个能够对整个前景矩阵进行结构化稀疏的约束

‖sj,g‖∞

(3)

式中:S∈Rm×n是由具有结构化分布特性的前景信号组成的矩阵,其第j列向量sj∈Rm,利用式(2)对sj进行约束。

由于背景矩阵的每一列表示一帧视频的背景信号,这些不同列的背景信号前后之间具有很大的相关性,可以分布到一个较低维度的空间上。因此,用低秩特性对背景矩阵进行约束。同时,受到文献[12-13]的启发,对于L,本文还采用了l2,1约束,以及对应的正则化参数κ、v设置,从而保证恢复得到的背景矩阵L中对应于前景所在的位置具有零值。最终得到本文模型

‖L‖*+κ(1-v)‖L‖2,1+κvΩ(S)

s.t.D=L+S

(4)

1.4 模型的求解

采用增广拉格朗日乘子法(ALM)求解式(4)的目标函数

L(L,S,Y;μ)=‖L‖*+κ(1-v)‖L‖1,2+

(5)

式中:μ为正惩罚参数;Y为拉格朗日乘子向量;〈·〉代表内积操作;‖·‖F表示Frobenius范数。

最小化拉格朗日函数式(5)的问题可以转化为下面3个子问题

(6)

(7)

Y=Y+μ(D-L-S)

(8)

当S和Y固定时,求解L的子问题式(6)可以写为

‖L‖*+κ(1-v)‖L‖2,1

(9)

‖L‖*+κ(1-v)‖L‖2,1

(10)

本文采用了文献[13]中的Douglas/Peaceman-Rachford(DR)迭代算法进行求解。DR迭代算法在第j次迭代中分别更新L(j+1/2)和L(j+1)两个值,然后进行循环迭代,直至收敛得到最优的解L。

采用类似的方法,将求解S的子问题式(7)化简为

(11)

对于问题式(11),本文采用一个二次最小割方法[12]去求解。

当L和S都求解完毕后,最后更新拉格朗日乘子Y,即式(8)。

利用ALM方法求解本文低秩和结构化稀疏分解问题式(4)的计算流程如下(具体的参数设置请参考文献[12-13]):

(1) 输入矩阵D,参数初始化;

(2) while not converge do;

(6) while not converge do;

(10)j←j+1;

(11)end while;

(16)Yk+1=Yk+μk(D-Lk+1-Sk+1);

(17)μk+1=ρμk;k←k+1;

(18) end while。

图3给出了利用本文算法在光照突变的情况下进行前景检测的结果,并且与现有的基于矩阵分解的检测方法DECOLOR法[14]、LBD法[12]和PCP法[9]进行了对比。从图中可以看出,由于采用了结构化特征的约束,采用本文法得到的前景检测结果更加完整,并且能够及时响应光线的变化,得到了更加准确的背景估计。

(a)视频帧得到的背景 (b)本文方法得到的背景 (c)DECOLOR法到的背景 (d)LBD法得得到的背景 (e)PCP法得到的背景

(f)本文方法得得到的前景 (g)DECOLOR法到的前景 (h)LBD法得到的前景 (i)PCP法得到的前景图3 本文低秩和结构化稀疏分解方法与DECOLOR、LBD及PCP方法结果比较

2 自适应正则参数设置的块稀疏分解

利用上述低秩和结构化稀疏分解,可以得到运动候选块,但是由于矩阵分解的方法存在参数选择的难题,这些运动候选块既包含真正前景,也包含背景部分的运动。本文利用运动显著性分析技术来判断经过分解后得到的运动候选块中哪些属于背景运动,哪些属于真正的前景运动。

在矩阵分解方法的模型中,很难选择单一的参数去适应所有场景。简单来讲,在式(1)中,因为参数λ控制着矩阵分解后背景和前景的比例,对于前景检测任务,希望λ值小一点从而使得得到完整的前景目标;对于背景估计任务,同样也希望λ值小一点,从而使得恢复的背景中不会具有前景的残影。考虑到得到完整目标的重要性,在以往的算法中往往采用了一个较小的、固定的λ值,但是这种全局的、统一的参数设置使得模型很难去除复杂多变的背景运动的干扰。

2.1 运动显著性分析

(a)视频帧 (b)候选块 (c)运动显著图图4 利用运动显著图进行运动分析

2.2 块稀疏分解

经过运动显著性分析之后,平均运动显著性值较低的(背景运动)块会被滤掉。对于其他候选块,已知块的大小和位置以及运动显著性参数,在第二步中采用块稀疏鲁棒主成分分析方法[15](Block-sparse RPCA)进行最终的前景检测

(12)

式中:D为观测数据;L为分解得到的低秩部分;S为分解得到的块稀疏部分;‖·‖F为矩阵的Frobenius范数;pi代表一个操作函数,用来将S的每一列中表示第i块的元素提取出来,用作下一步的处理。根据文献[15,17],第i块的正则化参数计算如下

(13)

由于本文提出的两步框架是在图像块的层面上对视频进行处理,并且针对背景变化和前景运动来设置不同的正则参数值,因此能够在得到准确的背景估计的同时得到完整的前景检测结果(见图5b和图5e),而PCP方法采用单一的参数设置,如图5c、图5f所示,虽然λ较小时能得到较完整的前景目标(人),但是同时也误检出运动的背景(海浪);如果设置较大的λ,那么运动目标被融入背景中,动态背景(海浪)也并没有被完全过滤掉,如图5d及图5g所示。

(a)视频帧

(b)本文方法得 (c)λ=m-1/2时PCP (d)λ=2m-1/2时PCP到的背景方法得到的背景方法得到的背景

(e)本文方法得 (f)λ=m-1/2时PCP (g)λ=2m-1/2时PCP到的前景方法得到的前景方法得到的前景图5 本文方法与PCP方法前背景分离结果对比

3 实验结果及分析

为了验证本文算法的有效性,在实验部分,与现有的4种方法进行了对比,包含3个目前最新的基于矩阵分解的方法(DECOLOR[14],LBD[12]和PCP[9])和一个基于单像素建模的经典算法ViBe[7]。

本文采用I2R测试视频数据库[4]进行实验,这个测试库共包含9段视频,主要包括了动态背景(树枝、水面、窗帘运动、喷泉、电梯等)、光照渐变及突变(开关灯)、

阴影等测试场景。首先给出针对复杂动

态背景的定性对比实验的结果图。从图6～8可以看出,针对包含复杂动态背景的视频Campus(CAM),Fountain(FT),Escalator(ES),本文方法能有效地去除动态背景的干扰,同时也能准确地检测出前景目标。DECOLOR方法往往得出过于光滑的检测效果,产生了大量的误检,其他方法则不能有效地去除动态背景的干扰,本文方法有效地处理了这些视频,比其他算法得到了更好的检测结果。

定量实验中,采用以下3个指标来评价检测结果

(14)

(a)视频帧 (b)标准结果 (c)本文方法 (d)DECOLOR (e)LBD (f)PCP (g)ViBe图6 I2R综合测试视频数据库CAM视频的前景检测结果比较

(a)视频帧 (b)标准结果 (c)本文方法 (d)DECOLOR (e)LBD (f)PCP (g)ViBe图7 I2R综合测试视频数据库ES视频的前景检测结果比较

(a)视频帧 (b)标准结果 (c)本文方法 (d)DECOLOR (e)LBD (f)PCP (g)ViBe图8 I2R综合测试视频数据库FT视频的前景检测结果比较

(15)

(16)

式中:T为检测结果当中属于正确分割的前景像素个数;FN为结果当中没有检测出来的部分,即漏检的前景像素的数目;FP为结果当中错误认为前景的部分,即误检为前景像素的数目;F为综合测量指标,是综合考虑召回率(r)和精确率(p)后可代表方法性能的指标,若某个方法的F值越高,则表明该方法对于该视频的前景检测结果越好。

表1给出了定量实验下的F测量指标,由表1可以看出,本文方法在6段视频下的F最高,在其余3段视频中排名第2。综合来看,本文方法在I2R综合测试视频数据库上有最高的平均F测量值。

表1 I2R综合测试视频数据库各个方法的F指标

注:黑体数据为同一条件下的最高值。

4 结 论

本文充分考虑了视频前景的结构化分布特性以及背景图像之间的相关性,提出了一个基于低秩和结构化稀疏分解的视频前景检测方法,实现了背景矩阵估计和前景矩阵分割的同步进行。此外,针对目前基于矩阵分解方法中存在参数选择的尺度问题,利用一个基于运动显著性的两步框架来实现参数的自适应选择。实验结果表明,本文提出的两步框架可以处理动态背景视频下的正则化参数选择问题,在标准测试数据库上进行视频场景的对比实验中取得了更好的检测效果。目前,本文方法的讨论只局限于固定相机下的视频处理,未来将考虑处理其他运动特征从而可以将工作扩展到移动相机下的视频前景检测。

[1] 王伟嘉, 刘辉, 沙莉, 等. 滞留与偷窃物体实时检测与分类算法 [J]. 计算机应用, 2007, 27(10): 2591-2594. WANG Weijia, LIU Hui, SHA Li, et al. Real time detection and classification algorithm for abandoned and stolen objects [J]. Computer Applications, 2007, 27(10): 2591-2594.

[2] STAUFFER C, GRIMSON W E L. Adaptive background mixture models for real-time tracking [C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 1999: 246-252.

[3] 刘鑫, 刘辉, 强振平, 等. 混合高斯模型和帧间差分相融合的自适应背景模型 [J]. 中国图象图形学报, 2008, 13(4): 729-734. LIU Xin, LIU Hui, QIANG Zhengping, et al. Adaptive background modeling based on mixture Gaussian model and frame subtraction [J]. Journal of Image and Graphic, 2008, 13(4): 729-734.

[4] LI L Y, HUANG W M, GU I H, et al. Statistical modeling of complex backgrounds for foreground object detection [J]. IEEE Transactions on Image Processing, 2004, 13(11): 1459-1472.

[5] SHEIKH Y, SHAH M. Bayesian modeling of dynamic scenes for object detection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(11): 1778-1792.

[6] KIM K, CHALIDABHONGSE T H, HARWOOD D, et al. Realtime foreground-background segmentation

using codebook model [J]. Real-Time Imagine, 2005, 11(3): 172-185.

[7] BARNICH O, VAN DROOGENBROECK M. ViBe: a universal background subtraction algorithm for video sequences [J]. IEEE Transactions on Image Processing, 2011, 20(6): 1709-1724.

[8] CANDES E J, LI X, MA Y, et al. Robust principal component analysis? [J]. Journal of the ACM, 2011, 58(3): 11-47.

[9] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.

[10]TIBSHIRANI R. Regression shrinkage and selection via the lasso [J]. Journal of the Royal Statistical Society: Series B Methodological, 1996, 58(1): 267-288.

[11]MAIRAL J, JENATTON R, BACH F R, et al. Network Flow Algorithms for Structured Sparsity [C]∥Proceedings of Neural Information Processing Systems. Vancouver, Canada: NIPS, 2010: 1558-1566.

[12]GUYON C, BOUWMANS T, ZAHZAH E H. Foreground detection based on low-rank and block-sparse matrix decomposition [C]∥Proceedings of the IEEE International Conference on Image Processing. Piscataway, NJ, USA: IEEE, 2012: 1225-1228.

[13]TANG G, NEHORAI A. Robust principal component analysis based on low-rank and block-sparse matrix decomposition [C]∥Proceedings of the Annual Conference on Information Sciences and Systems. Piscataway, NJ, USA: IEEE, 2011: 1-5.

[14]ZHOU X W, YANG C, YU W. Moving object detection by detecting contiguous outliers in the low-rank representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(3): 597-610.

[15]GAO Z, CEONG L F, SHAN M. Block-sparse RPCA for consistent foreground detection [C]∥Proceedings of the European Conference on Computer Vision. Heidelberg, Germany: Springer, 2012: 690-703.

[16]CUI X Y, LIU Q S, ZHANG S T, et al. Temporal Spectral Residual for fast salient motion detection [J]. Neurocomputing, 2012, 86: 24-32.

[17]LIN Z, CHEN M, MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices [EB/OL]. (2013-10-18)[2015-11-20]. http: ∥arxiv.org/pdf/1009.5055v3.pdf.

(编辑 刘杨)

A Background Subtraction Method Based on Decomposition of Low Rank and Sparsity Matrices

LIU Xin1,ZHANG Zhaoqiang1,YAO Jiawen1,GUO Lili2,QI Chun1

(1. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2. School of Information Science and Engineering, Yunnan University, Kunming 650091, China)

A background subtraction method based on decomposition of low-rank and structured sparsity matrices is proposed to solve the problem that detection results are sensitive to noise and incomplete caused by ignoring the relationship between foreground pixels in traditional foreground detection methods based on matrix decomposition. The method takes the structural distribution of the foreground into account, and a structured sparsity constraint is used on the foreground pixels. Moreover, a two-stage framework based on motion saliency is introduced to address the parameter setting issue in dynamic background videos and to tune regularization parameters adaptively. Motion block candidates are obtained by using the low rank and structured sparsity decomposition in the first step. Then, motion saliency analysis is applied to these candidates and the adapt block sparsity decomposition is used to detect the foreground in the second step. Experimental results show that the performance of the proposed method is more adaptive than the existing foreground detection methods based on matrix decomposition in complex videos, and that the proposed approach outperforms the state-of-the-art methods according to the precision and recall results on dataset I2R.

foreground detection; background subtraction; matrix decomposition; low rank representation; structured sparsity

2015-12-25。 作者简介:刘鑫(1981—),男,博士生;齐春(通信作者),男,教授,博士生导师。 基金项目:国家自然科学基金资助项目(61572395)。

时间:2016-04-26

10.7652/xjtuxb201606004

TP391

A

0253-987X(2016)06-0023-07

网络出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160426.2016.002.html