低秩-稀疏与全变分表示的运动目标检测方法

杨 磊 ,庞 芳 ,胡豁生

(1.上海大学机电工程与自动化学院,上海 200444;2.埃塞克斯大学计算机科学与电气工程学院,埃塞克斯郡科尔切斯特CO4 3SQ)

1 引言

运动目标检测作为计算机视觉领域中重要和基础的研究领域之一,在计算机视觉中有着广泛的应用,它的精确度、完整性和快速性对后续运动目标分析产生很大影响,所以视频序列中的运动目标检测具有非常重要的研究意义.20世纪60年代初,国外就开始了对运动目标检测的研究.运动目标检测的实质就是从视频序列中将变化部分从背景中提取出来.其中,背景差分法[1]是经典的运动目标检测方法之一,其核心思想是利用当前图像与背景图像的差分来检测运动目标区域.背景建模是背景差分法的关键环节,常用的背景模型有高斯模型[2]、支持向量模型[3]、模糊模型[4]、子空间学习模型和鲁棒子空间模型[5]等.其中Wright等人[6]提出的鲁棒主成分分析(robust principal component analysis,RPCA)是一种重要的鲁棒子空间建模法,已被广泛应用到运动目标检测中.基于RPCA的运动目标检测方法通过将视频序列矩阵近似看作是低秩的背景矩阵与稀疏的运动目标矩阵之和,从而实现运动目标检测.该类方法不用背景建模就可以提取出运动目标.然而,基本RPCA方法只有在简单场景[7-9]中检测效果较好,当面对复杂场景时,它的准确度就会急剧退化.为了克服基本RPCA方法的不足,诸多研究者对RPCA进行了改进,GUYON等人[10]提出了低秩和块稀疏矩阵分解的前景检测算法,这种分解增强了背景的低粗糙度和前景的块稀疏性.SHAHID等人[11]提出了一种基于图正则化的RPCA算法,提高了主成分对于遮挡和缺失值的鲁棒性和增强低秩恢复.GAO等人[12]提出全变分正则化的RPCA方法,将空间和时间连续性引入到原始RPCA中,从而在单一目标函数中形成目标问题.Ye等人[13]提出了一个运动辅助矩阵恢复模型的前景与背景分离算法.JAVED等人[14]在Ye的基础上提出了一种基于RPCA 的时空稀疏频谱聚类的正则化算法,该算法在存在遮挡、杂波、抖动和突变强度变化的情况下也能产生准确的背景模型.胡绍华等人[15]针对ViBe算法对于动态背景不鲁棒的问题进行改进,同时引入了超像素特征,提出了基于超像素特征的运动目标检测算法.另外,ZHU等人[16]在RPCA基础上提出一种L1/2和空间连续正则化运动检测算法,NEHORAI[17]引入结构化稀疏范数正则化项来精确地检测前景.赵志伟等人[18]提出了一种基于角度邻域的多目标差分进化算法,通过在选择操作中引入弱支配概念,实现了对多目标优化问题的求解.可见,虽然RPCA在运动目标检测方面取得了一定理论研究成果与实际应用,但仍存在一些值得进一步研究的问题.

在基于RPCA的运动目标检测方法中,由于奇异值分解(singular value decomposition,SVD)的多次迭代运算使得RPCA从损坏的观测值中恢复出低秩矩阵需要较大的计算量,加上初始模型没有利用好运动目标的时空连续的特性,会比较容易将动态背景判定为运动目标.针对RPCA存在的不足,本文利用运动目标在时间和空间上的连续性和背景在时间和空间上的相关性,提出了一种新的运动目标检测方法.由于运动目标在时间和空间上的特征,这在数学上满足全变分的定义,所以本文利用全变分来对运动目标进行约束,从而较为精确地把动态背景和运动目标分离开.另外,由于全变分在视频处理时的计算量相对较大,受Shu等人[19]提出的鲁棒性正交子空间学习(robust orthonormal subspace learning,ROSL)的启发,进一步令低秩矩阵的秩由正交子空间表示系数矩阵的非零行代替,得到新的运动检测模型.实验结果表明本文方法能很好地检测到复杂背景下的运动目标,同时还具有较快的运行速度.

2 基于RPCA的运动目标检测

近年来,RPCA是较热门的运动检测方法.RPCA通过引入低秩表示与稀疏表示联合表示,来获取运动视频序列中的背景和运动目标部分.它主要的思路:将视频序列所构成的观测数据矩阵分为两部分:具有低秩特性的背景部分和稀疏特性的运动目标部分.其公式表达如下式所示:

式中:X∈Rm×n表示视频序列构成的数据矩阵,B∈Rm×n和F∈Rm×n分别表示低秩背景矩阵和稀疏运动目标矩阵;rank(B)表示矩阵B的秩;为矩阵F的l0范数;λ表示缩放因子,用来平衡背景和运动目标之间的比重.由于rank(·)和都是非凸的,求解上式会是一个NP-hard问题,故通过凸松弛将上式转化为

基于RPCA的运动目标检测方法能够同时建立背景模型和提取出运动目标,不需要预先准备好只含有背景的视频序列模型,而且也不存在参数更新的问题.然而,该方法只能很好地处理背景静态和运动目标移动连续的理想情况,动态背景下的RPCA检测准确度就会急剧退化.本文针对动态背景下运动目标检测的问题,在RPCA的基础上提出了新方法,其思路如下:首先,根据运动目标在时空的连续性,利用全变分对其进行约束;其次,令低秩矩阵的秩由其正交子空间表示系数矩阵的非零行代替以加快整体的运行速度;最后,在RPCA的基础上提出本文方法的理论模型并进行求解.图1是本文方法的基本框架.

图1 本文方法的基本框架图Fig.1 Framework of the method

图1中:X表示待处理的视频序列,C表示某正交子空间基,α表示稀疏系数矩阵,M表示动态稀疏矩阵,E表示动态背景矩阵,F表示运动目标矩阵,Ik是单位矩阵.

3 低秩-稀疏与全变分表示的运动目标检测方法

3.1 运动检测模型

RPCA运动检测方法是把数据矩阵分为低秩矩阵和稀疏矩阵,低秩矩阵对应于背景,稀疏矩阵对应于运动目标.由于本文主要研究在动态背景下的运动目标检测,要充分考虑到稀疏矩阵不仅包含运动目标,还包含动态背景.故本文将稀疏矩阵又进一步分解为运动目标矩阵和动态背景矩阵.因为运动目标在时间和空间上连续的特征满足全变分的定义,本文利用全变分范数(total variational,TV)来对运动目标进行约束.为便于本文方法模型的建立和理解,这里首先给出二维TV范数定义:假设二维图像为u∈Rm×n,u(i,j)表示在像素点(i,j)处的灰度值,它的全变分定义为

式中ux(i,j)和uy(i,j)分别表示水平和垂直方向的灰度值变化.本文要处理的视频数据均属于三维空间,根据二维TV范数,可得出三维TV范数定义为

式中:X(i,j,t)表示在t时刻像素点(i,j)的灰度值;X(i,j,t)在像素点(i,j)沿水平、垂直和时间方向的变化量分别表示为

利用三维TV范数对运动目标进行约束,得到本文方法的初级模型如下所示:

式中:X∈Rm×n是视频序列构成的数据矩阵;B∈Rm×n是低秩背景矩阵;M∈Rm×n是稀疏矩阵;E∈Rm×n是动态背景矩阵;F∈Rm×n是运动目标矩阵;是矩阵F的全变分范数;λ1,λ2和λ3是平衡参数因子.

在RPCA中,由于SVD的多重迭代运算,其本身的计算复杂度为O(min(m2n,mn2)),再加上全变分的计算是基于像素级的,如果不对上述模型进行改进,整体的运行速度将会非常缓慢.需要在不影响准确度的条件下,仍能使整体算法保持较快的运行速度.RPCA中的SVD迭代运算占用了较多运行时间,本文在ROSL的启发下,将对低秩矩阵的核范数求解转化其正交子空间下的最小稀疏系数矩阵非零行数目的求解.假设给定一个输入矩阵B∈Rm×n,同时,C={C1,C2,···,Ck}∈Rm×k(m<

式中α=[α1; α2; ...; αk]∈Rk×n是稀疏系数矩阵.

若没有特殊要求,在稀疏表示下Frobenius范数正则化通常是核范数的有效替代,如下式所示:

ROSL中矩阵秩的最小化可以通过最小化稀疏系数的非零行数目获取,具体表示为

式中:CTC=Ik是避免α的消失,对正交字典进行约束;k表示子空间的维度.但求解此问题是NP-hard问题,通常使用核范数作为矩阵秩的凸近似[20],l1范数作为l0范数的凸近似,ROSL得出如下替代式:

3.2 模型求解

本节采用交替方向乘子法(alternating direction method of multipliers,ADMM)依次迭代求解式(11).首先,将式(11)写成增广拉格朗日形式:

式中:Y1∈Rm×n,Y2∈Rm×n是拉格朗日乘子;µ>0是增广拉格朗日参数;<·,·>表示矩阵内积.同时优化这8个变量计算复杂,类似坐标下降法[21],采用每次只最小化一个变量,固定其他变量的方式,具体迭代步骤如下:

1)求解Cj+1,αj+1:

在X+Y1/µ=Cα+M约束下,同时求解C和α是一个非凸问题.但当把这个问题看成一个子问题,即固定一个矩阵,更新另一个矩阵时,该问题就成了一个凸问题.ROSL中使用块坐标下降法(block coordinate descent,BCD)对该问题求解.假设某子空间基C=[C1··· Ct··· Ck]和 系 数 矩 阵α=[α1;··· ; αt;··· ; αk],BCD通过保持所有其他指标不变,依次更新(Ct,αt),如下式:

当考虑正交子空间时,需要通过Gram-Schmidt过程对Ctj+1进行正交化.新的Ctj+1通过3个步骤得到:首先,投 影 到C=[C1··· Ct−1]空 间 上;然 后,将Ctj+1更新为等式(14);最后,通过归一化将其投影到单位球面上.

2)求解Mj+1.

为方便计算,先计算出下式:

则Mj+1更新如下式:

式中:shrink(a,b)表示元素的软阈值运算:shrink(a,b)=sgn a×max(|a|−b,0).

3)求解Ej+1:

4)求解Fj+1:

Fj+1可以通过优化下式得到:

需将Fp∈Rm×1,Gp∈Rm×1重新堆叠为

m1和n1分别是指原视频帧的行长和列长.

把上式分成n个子问题求解,每个子问题使用梯度投影方法.最后,把每个子问题求得的fp再次重新堆叠得到Fpj+1=reshape(fp)∈Rm×1,获得最终更新后的Fj+1:

5)求解Y1j+1,Y2j+1:

6)求解µj+1:

4 实验结果与分析

为了验证本文方法的有效性,实验将采用公开视频库的视频序列和作者拍摄的视频序列进行实验分析.在相同条件下,将本文所提出的方法与其他4种近期的同类方法(DECOLOR[22],GRASTA[23],MAMR[13],RPCA[9])进行对比.实验在MATLAB 2016 环境下实现,实验所选用的计算机是64位操作系统的戴尔笔记本电脑,处理器为Intel(R)Core(TM)i5-8250U CPU@1.60 GHz 1.80 GHz.没有特别说明,本文方法的参数都设置为默认值:

ρ=1.2, nummax=500,µ0=1000/norm(norm是视频矩阵的最大奇异值),λ1=λ2;对于平衡全变分的λ3需要分情况,当处理的视频序列只存在静态背景时λ3=,当处理的视频序列含有动态背景时λ3=,这里的m 和n分别是单个视频帧的宽度和高度.

4.1 静态背景的视频序列运动检测

本文用DECOLOR,GRASTA,MAMR,RPCA 和本文方法先对作者拍摄的单人目标和双人目标运动的视频进行实验,再对Lobyy视频和Hall视频组进行实验.这4组视频序列的背景比较简单,都只是存在光线明暗变化的问题.由于视频序列较大,本文只取了其中连续40帧视频序列进行运动目标检测实验分析.

图2 是DECOLOR,GRASTA,MAMR,RPCA和本文方法在作者拍摄视频序列的运动目标检测结果,第1行分别选取的单人运动目标(左)和双人运动目标(右)视频序列中的两帧图像,第2-5行分别是DECOLOR,GRASTA,MAMR 和RPCA 恢复的背景图像和运动目标检测结果,最后1行是本文方法恢复的背景图像和运动目标检测结果.

图2 5种方法在作者拍摄视频序列上的运动目标检测结果Fig.2 Motion object detection results of 5 methods on video sequences taken by authors

图3是DECOLOR,GRASTA,MAMR,RPCA和本文方法在Lobyy和Hall视频的运动目标检测结果,第1行分别选取的Lobyy视频(左)和Hall视频(右)中的两帧图像,第2-5分别是DECOLOR,GRASTA,MAMR和RPCA恢复的背景图像和运动目标检测结果,最后1行是本文方法恢复的背景图像和运动目标检测结果.

图3 5种方法在Lobyy和Hall视频上的运动目标检测结果Fig.3 Motion object detection results of 5 methods on Lobyy and Hall videos

通过图2和图3可以看出,对于背景只存在光线明暗变化的单人运动目标视频、Lobyy视频和Hall视频序列,GRASTA 的检测效果最差;本文方法和DECOLOR,MAMR,RPCA都能很好的把运动目标检测出来,且较好的恢复出背景.对于前半段运动比较缓慢的双人运动目标视频序列,GRASTA检测效果最差;RPCA的检测效果次之,其检测出来的运动目标存在明显的“空洞”现象;而本文方法和剩余2种方法均能把运动目标很好地检测出来.除了检测效果上的比较,本文对5种方法在相同的运算精度(10−3)情况下的运行时间比较如表1所示.

表1 5种方法的运行时间对比表Table 1 Comparing tables of running time of 5 methods

从表1可以看出,在精度要求相同的条件下,本文方法在运行速度上虽然不是最优,但始终要小于RPCA.本文把对低秩矩阵的核范数求解转化为最小稀疏系数矩阵非零行数目的求解,使得方法在运行速度上与其他同类方法相当.

4.2 动态背景的视频序列运动检测

为了验证本文算法在动态背景下的运动检测效果,选取Overpass视频序列[24]进行实验对比分析.Overpass是CDnet数据集中包含动态背景的运动视频序列,该视频数据集中不仅包含输入视频每帧的原图,还包含二值化处理后的标准运动目标检测图,这为运动检测方法的准确度对比提供了标准.

图4是用DECOLOR,GRASTA,RPCA,MAMR和本文方法在Overpass视频上的运动检测结果.从图4的检测效果可看出,这5种方法都能把运动目标大体标示出来,但GRASTA的检测效果算是相对最差的,它只能把轮廓给提取出来,且受抖动树叶影响较大;尽管RPCA可以更好地检测到运动目标,但它也受抖动树叶影响较大;DECOLOR和MAMR比前两种方法检测出来的效果要好,都能够较完整的检测出运动目标,受抖动树叶影响也较小.通过对比发现,以上4种方法都存在一个共同的问题:4种方法后面检测到的运动目标上方都存在拖尾的现象,几乎无法辨别出人形.其中原因是后面几帧图像中运动目标移动比较缓慢,致使恢复的背景受运动目标的影响.而本文方法所检测到的运动目标中几乎没有受抖动树叶的影响,检测效果较好,且后期不存在拖尾现象.

图4 5种方法在Overpass视频上的运动目标检测结果Fig.4 Motion object detection results of 5 methods on Overpass video

为了定量的比较,采用准确度p来比较本文方法与其他4种方法的运动目标检测结果,如下式所示:

式中:TMn是Overpass视频中对应的标准运动目标图像中总的像素个数(运动目标像素总数+背景像素总数);Mn是各个方法实际检测到的运动目标像素个数的总和;Bn是各个方法实际检测到的背景像素个数的总和.

通过式(29)计算出参考方法和本文方法的准确率如表2所示,同时将各个方法在相同精度条件下运行时间进行对比如表3所示.由表2可见,本文方法在准确率上比其他4种方法都高.由表3可见,本文方法的运行时间虽不是最快的,但快于RPCA和其他几种同类方法.

表2 5种方法准确度对比表Table 2 5 methods accuracy comparison table

表3 5种方法运行时间对比表Table 3 5 methods running time comparison table

5 结论

为了有效地检测复杂背景视频序列中的运动目标,本文提出了一种低秩-稀疏与全变分表示的运动目标检测方法.该方法根据运动目标在时间和空间上的连续性,对其进行全变分约束;同时考虑到全变分的计算对运行速度的影响,进而把对低秩矩阵的核范数求解转化最小稀疏系数矩阵非零行数目的求解,以此提高方法的运行速度,得到新的运动检测模型并进行求解.实验结果表明,与其他同类方法相比,本文方法在含复杂背景的视频序列运动目标检测的准确率有明显优势,而且运行速度较快.优化提出方法的效率是本文进一步的工作.