运动目标检测的l0群稀疏RPCA模型及其算法

周　伟，孙玉宝,2，刘青山，吴　敏

(1.江苏省南京信息工程大学大数据分析技术重点实验室，江苏南京 210044； 2.江苏省大气环境与

装备技术协同创新中心，江苏南京 210044； 3.南京军区南京总医院医学工程科，江苏南京 210002)



运动目标检测的l0群稀疏RPCA模型及其算法

周伟1，孙玉宝1,2，刘青山1，吴敏3

(1.江苏省南京信息工程大学大数据分析技术重点实验室，江苏南京 210044； 2.江苏省大气环境与

装备技术协同创新中心，江苏南京 210044； 3.南京军区南京总医院医学工程科，江苏南京 210002)

摘要：经典的鲁棒主成分分析(Robust Principal Component Analysis，RPCA)目标检测算法使用l1范数逐一判别每一像素点是否属于运动目标，未能考虑到运动目标在空间分布的连续性，不利于提升运动目标检测的鲁棒性.本文提出了一种基于l0群稀疏RPCA模型的运动目标检测方法.首先运用Ncuts算法进行区域过分割，生成多个同性区域，将其作为群稀疏约束的分组信息；第二步构造基于l0群稀疏RPCA模型，运用群稀疏准则判别过分割后的各同性区域是否为运动目标，采用交替方向乘子算法对模型进行快速求解，约束过分割形成的同性区域具有相同检测结果，进而将背景环境和运动前景分离，能够更加准确地度量运动目标的区域边界，且对复杂的背景扰动更加鲁棒，达到了运动目标鲁棒检测的目的.

关键词:RPCA模型；l0群稀疏；过分割；交替方向乘子法；运动目标检测

1引言

视频运动目标检测[1,2]是视频智能分析中的一个基本问题，也是当前计算机视觉领域中的热点问题之一.视频运动目标检测就是将运动目标从复杂的背景环境中自动提取出来.从模式识别角度，可视为将复杂的背景环境和运动的前景目标的分类问题.它是实现视频分析的基础，在基于对象的视频编码、基于内容的视频检索、智能视频监控等领域中也具有广泛的应用[3,4].

近年来，国内外科研工作者提出了诸多的视频运动目标检测算法，根据检测模型的不同，主要可分为背景差分法[5,6]，帧间差分法和光流法[7,8].虽然这些目标检测方法取得了一定成功，但它们对场景的复杂动态变化仍不够稳健.例如视频中光照的变化、目标运动形式的多样性(非刚性形变)、运动目标同背景间的相似性、场景背景的动态变化(雨、波浪、喷泉和摄像机的抖动)等因素均给运动目标检测的研究带来了挑战.实践表明视频运动目标检测的算法还远未成熟，如何寻求一个更为有效的检测模型仍是一个难点问题.

当前，研究者们将鲁棒主成分分析(RPCA)理论[9,10]引入视频运动目标检测问题.视频中的背景通常具有较强的相关性，近似位于同一低秩的子空间内，而前景目标呈现出与背景不同的运动形式以及纹理特征，可被视为偏离该低秩空间的少量显著误差，符合误差稀疏性的约束.因此RPCA模型假设数据矩阵M由两个成分L与S组成，其中矩阵L具有低秩特性，可较好建模背景；矩阵S具有稀疏性，可有效分离运动目标.通过矩阵的低秩(核范数)与稀疏性(l1范数)约束，恢复出矩阵的低秩成分L和稀疏成分S，对视频背景的建模取得了为较为出色的结果，为该问题开启了新的研究思路.在后续的研究中，文献[11]提出了GoDec模型，在原有模型上引入了噪声部分G，允许原矩阵存在一定的噪声成分，通过非凸的秩rank(L)和稀疏度card(S)约束来进行分离，能够对背景中的噪声保持一定的鲁棒性，但在复杂的动态背景下，稀疏部分仍包含大量的背景成分.文献[12]提出用基于概率的鲁棒矩阵因子分解RPMF模型，它引入了Laplace-error和高斯分布先验，运用l1-loss约束和l2范数正则项约束进行建模，此模型对光照变化具有较强鲁棒性，但对复杂背景的表示仍然不足.

尽管基于RPCA的视频目标检测算法取得了一定的成果，但动态背景的表示能力仍存在不足[13]，容易将背景中动态背景误判为前景运动目标.如何构建复杂动态背景的低秩表示模型是一个难点问题.视频中运动目标区域并不是随机出现的，因此在空间上具有一定的相关性和连续性，然而现有的RPCA模型进行运动目标检测时，l1范数没有蕴含系数本身与尺度和结构信息相关的“结构化稀疏性”[14,15]，未能有效利用运动目标的空间分布连续性先验，同时也不利于消除由于噪声以及背景随机扰动引起的非结构化稀疏分量.基于这一思想，本文提出了一种新的基于群稀疏RPCA模型的运动目标检测方法，它构建了一种结构化稀疏性度量标准，在保持稀疏性约束的同时，更注重运动目标区域的空间相关性的度量，可以实现对复杂动态背景下的视频运动目标的鲁棒检测.

2l0群稀疏RPCA模型

经典的RPCA检测方法使用l1范数独立判别每一个像素是否为运动目标，不利于消除由于噪声以及背景随机扰动引起的非结构化稀疏分量.鉴于运动目标空间分布的连续性，分离运动目标的稀疏部分也应具有这种结构化的相关性特征.为此，本文提出了基于群稀疏RPCA的运动目标检测算法，通过l0群稀疏范数约束运动目标分布的连续性，提升检测算法的鲁棒性.算法主要包含两个步骤：第一步，运用过分割算法对视频序列进行同性区域分组；第二步，运用构建群稀疏模型，进行背景和运动前景的分离，进而精确定位运动区域，实现对复杂动态背景的有效分离.本文算法的流程如图1所示.

2.1同性区域的过分割分组

在本节中，首先将各视频帧作为列向量依次排列形成视频矩阵D∈Rm×n(m为视频每帧的像素数，n为视频帧数)，然后运用Normalized Cuts算法[16～18]方法将每帧图像过分割为“超像素”，形成同性区域.同性区域不仅具有局部性和连续性，而且它为后续的处理提供了有效的目标边界信息.

本文运用Normalized Cuts算法完成每帧图像的超像素的分割.该算法把整幅图像表示为一个加权无向图I=(V,H,W)，V为图中所有顶点的集合，H为图中边的集合，W为边权重.图像中每一个像素对应了图中的一个节点，边上的权值w(u,v)代表像素u,v之间的相似关系.通过移除图的某些边，可以把图分割成为两个不相交的顶点集A∪B=V,A∩B=∅，进而形成图像区域的分割.移除边的总和，作为A和B两个子图的不相似度来计算，在图论中叫做图割，计算为cut(A,B)=∑u∈A,v∈Bw(u,v).为了生成平衡的分割，Shi和Malik提出Ncuts分割标准，定义为：

(1)

其中assoc(A,V)=∑v∈A,t∈Vw(v,t)为A中的节点到图中的所有节点的连接权重总和，B中的节点到图中的所有节点的连接权重总和也可表示为assoc(B,V)=∑v∈B,t∈Vw(v,t)，该标准测量两个子图之间不相关度，有利生成大小均匀的子图.Ncuts方法将计算最优的Ncuts值问题转换到对矩阵的特征值与特征向量的求解上，并通过递归应用方法，可生成多类区域的分割.

本文利用灰度、纹理与边缘等作为特征计算各像素间的权重，通过求解相应的特征方程，对视频矩阵D中的每一帧图像进行过分割.gi为过分割后形成的第i个Group所包含的像素坐标集合，整个视频序列的分组信息为G={gi|1≤i≤J}，J为总分组数，满足gi∩gj=∅，∀i≠j，且G为整个视频序列的坐标集合.过分割后形成的分组G能够覆盖整个视频序列，同时各区域gi为同性区域，有效定位运动目标的边界.图2为WaterSurface序列中一帧图像的过分割结果，过分割后形成的区域能够有效定位行人的轮廓边界，各同性的区域趋向于具有相同的运动特性，因此可以将各同性区域作为分组信息G，构建群稀疏度量标准.

2.2群稀疏RPCA模型构建

为有效利用运动目标区域的空间分布相关性，本文构建一种l0群稀疏RPCA模型，利用l0群稀疏约束过分割形成的同性区域具有相同的检测结果，同为背景或同为运动目标.建立视频数据D∈Rm×n(m为视频每帧的像素数，n为视频帧数)的群稀疏(group sparse)RPCA模型如下：

(2)

(3)

3交替方向迭代优化算法

本文通过交替方向迭代优化[19]算法对模型(2)进行优化求解，模型(2)的增广拉格朗日函数为：

(4)

其中Y∈Rm×n为拉格朗日乘子，这是一个多变量的优化问题，需要进行迭代求解.假定当前为第k次迭代，变量的交替优化与乘子更新过程如下.

(1)固定A，更新E，目标函数如下：

(5)

(6)

(2)固定E，更新A，目标函数：

(7)

(3)更新拉格朗日乘子和惩罚参数：

Yk+1=Yk+μ(D-Ak+1-Ek+1)

(8)

重复执行此过程直至满足给定收敛条件.为了加速算法的收敛速度，乘子法在迭代过程中应适时更新惩罚参数μk+1.

μk+1=max(ρμk，μmax)

(9)

其中ρ>1为倍数因子，具体的参数设置请参见算法1.重复执行此过程直至满足给定的收敛性条件，判断算法的收敛性，计算收敛性条件：

(10)

如果RelErr1>ε1或RelErr2>ε2，则进行步骤3，否则结束迭代，算法收敛.

本文算法1中Step3需要进行奇异值分解操作，是算法的主要耗时部分，Step4进行软阈值收缩，为线性复杂度，运算复杂度较低.算法1的整体复杂度与文献[10～12]相同，奇异值分解操作可采用PROPACK软件包进行快速求解[22]，每次迭代的运算复杂度为O(r·m·n)，r为A的秩(通过预估获得).交替方向乘子优化算法的收敛性已经有了较为成熟的理论结果[19,22]，在参数λ、ρ等参数适当选值时，算法1能够趋于稳定并收敛.以Airport序列数据为例，依据上述算法按算法1中Step1设置各算法参数，求解模型(2)，图3给出了相对误差RelErr1和RelErr2随迭代次数的变化曲线，可以看出，相对误差均能够随着迭代次数快速衰减并趋于稳定，验证了本文优化算法的收敛性.

4实验设计及结果分析

4.1实验设计

本文选取五个视频序列来验证算法的有效性.五个视频序列分别为：(a)Bootstrap视频序列，视频序列描绘的是餐厅吧台的忙碌的景象；(b)Airport视频序列，机场大厅序列上每一帧都有行人；(c)SwitchLight视频序列，序列为光照变化明显的图书馆的一角；(d)和(e)两个室外的测试序列，分别为WaterSurface序列和Campous序列，前一个序列背景中海面存在很大的波浪扰动，后一个序列中随风摆动的树叶给检测带来了较大的挑战.为了更好的评估本文算法，将它与主流的检测算法RPCA、GoDec以及PRMF作比较，并通过使用定性和定量两种方法来分析结果.

4.2定性分析结果

从图4(a)～(c)三个室内场景检测效果图的结果来看，在受到光照变化、运动目标相互遮挡等干扰影响下，从各模型算法检测效果中可以看出，本模型算法检测效果的背景扰动基本被消除了，相比于RPCA、GoDec以及PRMF，获得的检测目标的轮廓也更加完整、平滑，达到了很高的检测精度.

从定性的角度可以看出RPCA和GoDec算法在检测中，存在明显的“幻影”现象，这一问题在图5中的室外WaterSurface测试序列中，可以较为明显的看出，这对于检测精度存在很大影响.在室外Campous测试序列的检测效果中可以明显的看出，本文算法检测到的运动前景的轮廓更为完整，且背景更为干净.

4.3定量分析结果

关于定量比较分析，使用F-score来评判.其中，F-score同时将真阳性(True Positive，TP)、假阳性(False Positive，FP)和假阴性(False Negative，FN)都考虑在内，计算如下：

(11)

TP、FP和FN分别是真阳性、假阳性和假阴性.在背景建模问题中，F-score的计算如下：

(12)

其中Rs由背景建模得到的区域，Rg是真实的目标区域.好的背景建模应该提供大的F-score.

定量比较时，从各个测试序列中随机抽取9～10帧，将每帧图片中检测到的运动目标与Groundtruth比对，计算出对应的F值.图6给出了本文算法与RPCA、GoDec以及PRMF在各个测试集上的F指标，并绘制出各算法在不同帧上的F指标相应的曲线图.从图6室内Airport测试序列的曲线图可以看出，本文模型的F值指标均优于其他三种算法，平均高出约4～6个百分点，本文模型优势较为明显.图6(b)为室外Campous测试序列的曲线图，本文算法的F值指标相比其它三种算法均有很大的提升，高出10～15个百分点，当视频背景存在的巨大背景扰动时，显示出本模型较强的鲁棒性，也表明了本文模型的有效性.

5结论

为了能够对有复杂的动态背景的视频序列进行鲁棒的运动目标检测，本文提出了群稀疏RPCA算法.它构建了一种结构化稀疏性度量标准，在保持稀疏性约束的同时，更注重运动目标区域的空间相关性的度量，可以实现对复杂动态背景下的运动目标的鲁棒检测，从实验定性和定量检测结果上看，本文算法在检测效果和精度上，相比之前的主流算法有很高的提升，在牺牲一定的过分割时间基础上，能够获得更高的检测精度.

参考文献

[1]Zhang D,Javed O,Shah M.Video object segmentation through spatially accurate and temporally dense extraction of primary object regions[A].Proceedings of IEEE Int Conf Comp Vis[C].Portland:IEEE,2013.628-635.

[2]Ma T,Latecki L J.Maximum weight cliques with mutex constraints for video object segmentation[A].Proceedings of IEEE Int Conf Comp Vis[C].Rhode Island:IEEE,2012.670-677.

[3]Sharma P,Nevatia R.Efficient detector adaptation for object detection in a video[A].Proceedings of IEEE Int Conf Comp Vis[C].Portland:IEEE,2013.3254-3261.

[4]Papazoglou A,Ferrari V.Fast object segmentation in unconstrained video[A].Proceedings of IEEE Int Conf Comp Vis[C].Portland:IEEE,2013.1777-1784.

[5]Huerta I,Amato A,Roca X,et al.Exploiting multiple cues in motion segmentation based on background subtraction[J].Neurocomputing,2013,100(1):183-196.

[6]Han B,Davis L S.Density-based multifeature background subtraction with support vector machine[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(5):1017-1023.

[7]Bao L,Yang Q,Jin H.Fast edge-preserving patch match for large displacement optical flow[J].IEEE Transactions on Image Processing,2014,23(12):4996-5006.

[8]Sundberg P,Brox T,Maire M,et al.Occlusion boundary detection and figure/ground assignment from optical flow[A].Proceedings of IEEE Int Conf Comp Vis[C].Colorado Springs:IEEE,2011.2233-2240.

[9]Cand′es E,et al.Robust principal component analysis[J].Journal of ACM,2011,58(3):1-37.

[10]Chandrasekaran V,Sanghavi S,Parrilo P A,et al.Rank-sparsity incoherence for matrix decomposition[J].SIAM Journal on Optimization,2011,21(2):572-596.

[11]T.Zhou,D.Tao,GoDec:Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case[M].Berlin Heidelberg:Springer Press,2011.33-40.

[12]Wang N,Yao T,Wang J,et al.A Probabilistic Approach to Robust Matrix Factorization[M].Heidelberg,Berlin:Springer Press,2012.126-139.

[13]Ding X,He L,Carin L.Bayesian robust principal component analysis[J].IEEE Transactions on Image Processing,2011,20(12):3419-3430.

[14]Gao Z,Cheong L F,Shan M.Block-Sparse RPCA for Consistent Foreground Detection[M].Heidelberg,Berlin:Springer Press,2012.690-703.

[15]Guyon C,Zahzah E,Bouwmans T.Robust Principal Component Analysis for Background Subtraction:Systematic Evaluation and Comparative Analysis[M].Lapochelle:Intech,2012.223-238.

[16]Moore A P,Prince S J D,Warrell J.“Lattice Cut”-Constructing superpixels using layer constraints[A].Proceedings of IEEE Int Conf Comp Vis[C].San Francisco:IEEE,2010.2117-2124.

[17]Shu G,Dehghan A,Shah M.Improving an object detector and extracting regions using superpixels.[A].Proceedings of IEEE Int Conf Comp Vis[C].Portland:IEEE,2013.3721-3727.

[18]Grote A,Butenuth M,Gerke M,et al.Segmentation based on normalized cuts for the detection of suburban roads in aerial imagery[A].Urban Remote Sensing Joint Event[C].Paris:IEEE,2007.1-5.

[19]Yuan X,Yang J.Sparse and low-rank matrix decomposition via alternating direction methods[J].Pacific Journal of Optimization,2013,9(1) :167-180.

[20]Cai J F,Candès E J,Shen Z.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization,2010,20(4):1956-1982.

[21]王佰玲,田志宏,张永铮.奇异值分解算法优化[J].电子学报,2010,38(10):2234-2239.

Wang Bai-ling,Tian Zhi-Hong,Zhang Yong-zheng.Optimization of singular vector decomposition algorithm[J].Acta Electronica Sinica,2010,38(10):2234-2239.(in Chinese)

[22]Larsen R M.Lanczos bidiagonalization with partial reorthogonalization[J].DAIMI Report Series,1998,27(537):1-101.

周伟男，1990年生于江苏苏州.南京信息工程大学硕士研究生在读,研究方向为图像处理与模式识别、稀疏表示与压缩感知术.

E-mail:zyxxpyzhouwei@gmail.com

孙玉宝(通信作者)男，1983年生于江苏连云港.南京信息工程大学讲师.研究方向多维信号稀疏表示与压缩感知、高光谱图像处理.

E-mail:sunyub@nuist.edu.cn

刘青山男，1975年生于安徽合肥，教授,博士生导师，研究方向为图像与视频分析、大数据处理与分析.

E-mail:qsliu@nuist.edu.cn

吴敏女，1973年生于江苏南通.南京军区南京总医院，高级工程师,研究方向为压缩感知理论与应用、EEG信号处理.

E-mail:njzywm@163.com

l0Group Sparse RPCA Model and Algorithm for Moving Object Detection

ZHOU Wei1,SUN Yu-bao1,2,LIU Qing-shan1,WU Min3

(1.JiangsuKeyLaboratoryofBigDataAnalysisTechnology,NanjingUniversityofInformationScience&Technology,Nanjing,Jiangsu210044,China;2.JiangsuCollaborativeInnovationCenteronAtmosphericEnvironmentandEquipmentTechnology,Nanjing,Jiangsu210044,China;3.DepartmentofMedicalEngineering,NanjingGeneralHospitalofNanjingAreaCommand,Nanjing,Jiangsu210002,China)

Abstract:Classical robust principal component analysis (RPCA) algorithm uses l1-norm to discriminate whether each pixel belongs to motion object,without taking advantage of the spatial continuity distribution of the movement object.Thus,the accuracy and robustness of detection algorithm is negatively influenced.In order to use the spatial continuity prior,this paper proposes an object detection method based on l0 group sparse regularized RPCA model.First,our algorithm over-segments the video sequence into multiple homogeneous groups using normalized cuts over-segmentation algorithm,and these groups are treated as grouping information for group sparse constraint.The next step is to construct l0 group sparse regularized RPCA model,which uses l0 group sparse criterion to discriminate whether each homogeneous group belongs to motion object.Alternative direction of multiplier method (ADMM) is adopted to solve our l0 group sparse RPCA model quickly.Homogeneous groups are restricted to have the same detection results.Thus,our model can be more robust to background movement and increase the detection accuracy of object boundary.

Key words:RPCA model;l0 group sparse;over-segmentation;alternative direction of multiplier method (ADMM);moving object detection

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.020

中图分类号:TP753

文献标识码：A

文章编号：0372-2112 (2016)03-0627-06

基金项目:国家自然科学基金项目(No.61300162,No.81201161);江苏省自然科学基金(No.BK2012045,No.BK20131003);中国博士后基金(No.20110491429);江苏省博士后基金(No.1101083C);江苏省光谱成像与智能感知重点实验室基金(No.30920130122003)

收稿日期:2015-01-20;修回日期:2015-05-22；责任编辑：覃怀银