基于矩阵分解的小计算代价RPCA模型及应用

王永丽，苑庆美，陈勇勇，孙志鹏，徐 菲，钟 勇

（山东科技大学 数学与系统科学学院，山东 青岛266590）

视频监控系统通常用于场景分析和运动目标检测［1］等实际问题。前景-背景分离［2］作为求解这类问题的一个关键预处理步骤，已在目标跟踪、行为识别、交通监控以及显著运动检测等领域得到了广泛应用，其基本操作是将静态的背景与运动的前景进行精确有效地分割。鲁棒主成分分析（robust principal component analysis，RPCA）［3-4］作为主成分分析（principal component analysis，PCA）模型的改进，是处理前景-背景分离问题的最有效模型之一。该模型的优势在于：即使存在较大误差或异常值，也能充分利用原始数据中潜在的低秩结构。

2009年Wright等［3］提出了RPCA模型。2011年，Candès等［4］将该模型应用于前景-背景分离。原始RPCA模型可表述为：

其中：λ 是一个正参数，用以平衡低秩背景B 和稀疏前景F；X= ［x1，x2，…，xn］∈Rm×n表示n帧原始输入图像序列，且xi为X 中第i列包含m 个元素的向量。

然而，由于秩函数和l0范数的非凸非连续性，导致模型（1）的求解是一个NP-难问题。为了更好地求解该问题，最为常用的方法是分别用核范数和l1范数来代替秩函数和l0范数，进而得到如下凸优化模型：

尽管上述凸近似模型（2）在一些实际场景的应用中取得了成功，但仍然存在以下缺点：①将所有奇异值进行简单求和意味着每个奇异值被同等对待［5-7］，使得较大的奇异值受到过度惩罚，进而导致有偏差估计的产生；②核范数的求解往往需要在每次迭代中对一个大规模的矩阵进行奇异值分解（singular value decomposition，SVD），这一过程非常耗时，使计算代价变得十分昂贵；③传统的RPCA 可能无法处理比较复杂的动态背景问题。例如，对数据集“Fall”而言，传统RPCA会将其背景中不断随风飘动的树叶也视为运动的前景，与真实前景一起提取，导致前景-背景分离的精确度降低。

针对以上缺陷，近年来几种改进的前景-背景分离方法［8-12］被相继提出。IALM［8］是解决秩最小化问题的一种高效且省时的经典算法，通常用于前景-背景分离问题。2010年，Zhou等［9］提出稳定主成分追踪（SPCP）模型，该模型的优势在于：即使存在噪声，每一项仍然可以被较为稳定和准确地恢复。随后，Oreifej等［10］提出三项分解（3WD）模型，该模型可以看作SPCP模型的进一步改进。为了更好地处理前景-背景分离问题，Ye等［11］于2015年提出运动辅助矩阵恢复（MAMR）模型及其扩展模型（RMAMR）。在3WD 和RMAMR两种改进模型的基础上，Sobral等［12］提出了基于形状和置信图的双约束RPCA 模型（SCM-RPCA）以改进前景检测效果。此外，Cao等［13］针对前景-背景分离问题，提出新的TVRPCA 模型，该模型使用全变差正则化将前景分成平滑分量和稀疏分量。与原始模型相比，上述模型在前景检测应用中检测效果显著提高。但遗憾地是，计算耗时这一根本问题仍然没有得到有效解决。

为了解决上述模型中存在的计算耗时问题，本研究引入矩阵分解技巧，利用核范数的正交不变性，将原始大规模矩阵转化为两个小规模因子矩阵乘积的形式，来有效避免模型求解过程中计算代价昂贵的问题。此外，考虑到时空约束信息对前景-背景分离的关键作用，为了提高前景-背景的分离效果，引入二值模板对前景稠密运动进行估计，同时加入置信图以期获得有关运动物体位置的先验信息，提出一种基于矩阵分解的小计算代价RPCA模型，并应用增广拉格朗日乘子法进行求解。最后，将新模型应用于视频序列的前景-背景分离问题，通过大量实验验证了改进模型的有效性。

1 预备知识

本节分别对二值模板M 和置信图Π 的求解进行详细介绍，同时给出矩阵分解的定义及性质。

1.1 二值模板

为了对运动显著的前景区域进行稠密运动估计，参照文献［14］，引入二值模板，即表示稠密运动信息的权重矩阵M。为了确定M，首先计算原始输入图像序列中每连续两帧图片之间的密集光流区域，以获得水平运动矢量Vx和垂直运动矢量Vy两个分量，具体计算方法如下：

假设xi和xi-1分别表示原始视频序列X 在t和t-1时刻的两帧连续图片，则相应二值模板M 中列向量mi中的每个元素mi，k∈{0，1 }可由下式计算：

1.2 置信图

为了获得有关运动物体位置的先验信息，引入置信图。首先对原始输入视频序列X 中的每一帧图片xi进行标准化处理，将每一项标准化到0～1范围内。具体计算公式如下：

其中，Π= ［π1，…，πi，…，πn］为表示置信图的线性算子。xi，（a，b）表示第i帧图片中第a 行和第b列的像素值。xi，min和xi，max分别是第i帧图片中的最小像素值和最大像素值。

通过将置信图Π 作用于稀疏前景项F 上，可使最可能属于运动前景的像素值几乎保持不变，而对应于背景的像素值则变得非常小，几乎趋近于零。这样，属于背景的部分就会被消除，而属于前景的部分则会更加凸显，进而有利于前景和背景的进一步分离。

1.3 矩阵分解

考虑到现有的大多数运用核范数近似矩阵秩函数的文献中，求解过程每步迭代都要进行奇异值分解，当矩阵规模较大时通常会导致计算代价昂贵这一问题，引入矩阵分解技巧，以期降低原始RPCA 模型及相关改进模型中计算量过大问题。

具体地，设矩阵B ∈Rm×n且rank（B）=r（r ≪min{m，n }），则由文献［15］可知，存在因子矩阵U ∈Rm×r，V ∈Rr×n，使得B=UV 成立，其中，因子矩阵U 为正交规范列矩阵，即UTU=Ir，V 是一个秩为r的行满秩矩阵。

根据上述矩阵分解的定义及核范数的正交不变性，有：

由（5）式可知，利用矩阵分解技术可以将一个大规模低秩矩阵的核范数转换为一个较小矩阵的核范数，且小矩阵的规模远小于原始矩阵的规模，从而可以有效解决原始RPCA 模型求解过程中存在的计算量过大问题。

2 基于矩阵分解的小计算代价RPCA 模型

本节将把第1节中介绍的二值模板、置信图以及矩阵分解等技术引入RPCA 模型，建立新模型，利用增广拉格朗日乘子法对新模型进行求解，并对求解过程的计算复杂度进行分析。

2.1 模型建立

将第1节中介绍的矩阵分解技巧与文献［10］中的三项分解模型相结合，并类似于文献［12］引入二值模板M 和置信图Π 等时空约束信息，可得如下基于矩阵分解的小计算代价鲁棒主成分分析模型（MFRPCA）：

其中，U ∈Rm×r是一个正交规范列矩阵，V ∈Rr×n是一个秩为r（r≤min{m，n}）的较小矩阵。相较于模型（2），此处矩阵U 和V 的规模都小于原始矩阵B 的规模，从而使得求解过程的计算复杂度大大降低。M 和Π 分别是1.1和1.2节中定义的二值模板与置信图矩阵，其作用是为了提高前景-背景分离效果。

2.2 模型求解

本节将采用交替方向策略的增广拉格朗日乘子法［8，16］求解凸优化模型（6）。首先给出问题（6）的增广拉格朗日函数如下：

其中，Y ∈Rm×n和μ ＞0分别表示增广拉格朗日乘子和惩罚参数。如公式（13）所示，在每次迭代中，μ 的取值逐渐增大，以使低秩背景B、稀疏前景F 和噪声项S 之和更接近原始观测矩阵X。采用交替方向策略迭代求解每个变量U，V，F，S，Y，μ，具体迭代如下：

由上可知，对原始问题的求解可分别转化为对子问题U、V、F、S、Y 和μ 的迭代求解过程。当交替更新每个变量时，将其他变量固定为其最新值。以下是对每个子问题的详细求解过程。

2.2.1 Uk+1的更新

给定Vk、Fk、Sk、Yk、μk，通过求解简化公式（8）来更新子问题U：

问题（14）是著名的Orthogonal Procrustes问题，其全局最优解可以通过SVD求出。具体地，设R1的奇异值分解为可以通过如下公式更新：

其中，R1=（X-M◦Fk-Sk+μ-kYk）（Vk）T，A1、B1和Σ1分别是左奇异向量、右奇异向量矩阵和矩阵R1的奇异值矩阵。

2.2.2 Vk+1的更新

在（9）式中，固定Uk+1为其最新值，并基于U 的正交不变性，即UTU=Ir，求解如下子问题来更新Vk+1：

其中，R2的奇异值分解为：，阈值算子Tt（Σ2）=diag（max{σi-t，0}）是一个对角矩阵，σi是Σ2的对角元素。

2.2.3 Fk+1的更新

固定Uk+1，Vk+1在（18）式中的最新值，求解子问题来更新Fk+1：

3.2.4 Sk+1的更新

固定Uk+1、Vk+1、Fk+1为其最新值，子问题（11）可以写为如下形式：

2.2.5 Yk+1和μk+1的更新

最后，固定Uk+1，Vk+1，Fk+1，Sk+1为其最新值，分别由（12）式和（13）式更新增广拉格朗日乘子Yk+1和惩罚参数μk+1。

综上可得凸优化模型（6）的求解算法。

算法1：基于矩阵分解的小计算代价鲁棒主成分分析模型（MFRPCA）的求解算法

2.2.6 计算复杂度分析

本模型的主要计算量在于对子问题U 和V 的求解。U 和V 的计算时间分别为Ο（mr2+mnr）和Ο（nr2+mnr），而子问题F，S 以及Y 的计算复杂度均为Ο（mn）。由上述分析可知，当矩阵的秩r满足r≪n＜m时，在每次更新迭代中，本模型的整体计算量为Ο（mnr），大大提高了模型的求解效率。

3 数值实验

本节将分别对包含静态背景和动态背景的真实数据集进行实验，以验证模型的有效性。其中，动态背景相较于前景-背景分离而言，是一个更具挑战性的问题。将本模型分别与IALM［8］、3WD［10］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］等5种方法进行比较。为了保持比较的公正客观性，5种算法用到的数据集以及运行环境均相同。所有方法采用相同的停止标准，即当最大迭代次数达到100次或者相对误差小于10-5时，停止计算。此外，所有的数值实验都是基于PC Intel Core i3-3240T 2.90 GHz CPU，4GB RAM 环境，使用MATLAB R2014a实现。

3.1 测试数据集与定量评估指标

实验使用的数据集主要包括Scene background modeling.net（SBM.net）、Change Detection.net（CDnet）2014［17］和12R［18］。这些数据集包括各种具有挑战性的场景，如动态背景、室外和室内环境、突然的光照变化等。表1给出了所选数据集的具体信息，其中，前三列分别代表3个不同的数据集、每个数据集的子数据集以及帧分辨率和处理的帧数量，最后一列给出了背景的静态或动态描述。

前景检测本质上是一项二进制分割任务，将每个像素分成背景和前景。为了准确、全面地衡量改进模型的前景检测效果，分别使用召回率、精确度、相似度和F-measure（具体定义见表2）四个指标来衡量各模型的客观性能。通过对每个公式的分析，发现每个评价指标的取值范围均在0～1之间，且最理想的结果是1，即地面真实情况（文献［17-18］中给出）。

表1 实验中选用数据集的详细信息Tab.1 Details of datasets selected in our tests

表2 召回率、精确度、相似度和F-Measure指标Tab.2 Recall，precision，similarity and F-measure metrics

3.2 参数设置

本模型主要包括两类参数：①收敛性参数μ、ρ和r，主要影响模型收敛的速度；②性能参数λ1、λ2和r，主要影响模型的性能。

1）收敛性参数：对于参数μ 和ρ，分别设置μ=0.005和ρ=1.6。实际上，参数r 的取值是同时影响计算效率和实验效果的一个关键性因素。实验发现，r 的取值过大将无法实现降低计算复杂度这一根本性目标，进而导致矩阵分解技巧的引入失去意义。相反，r的取值过小，单方面追求计算效率，则又无法得到预期的前景-背景分离效果。因此，为同时兼顾计算效率和实验效果两方面，根据多次实验结果的总结，最终设定参数r=4作为其最优取值并用于本研究所有实验。

2）性能参数：参数λ1和λ2的选择是否恰当，对于协调低秩、稀疏和噪声项至关重要。为了选出最优参数并获得最佳实验结果，首先建立λ1、λ2与最优指标Fm之间的联系。设定λ1=λ2={0.001，0.01，0.05，0.1，1，10，50，100，500，1 000，5 000}，分别对应于图1中参数λ1和λ2的取值，即λ1=λ2={1，2，3，…，9，10，11}。由图1可以看出，参数λ1和λ2对最优指标Fm有显著影响，并且当λ1=50，λ2=1和λ1=500，λ2=10以及λ1=5 000，λ2=100时，均可以获得动态背景数据集WaterSurface的最优指标值，即Fm=0.91。需要特别强调的是，对于没有给出地面实况的静态背景数据集而言，本研究则主要是基于具体实验的视觉效果来选择相对应的最优参数λ1和λ2的取值。

3.3 对比实验结果分析

3.3.1 静态背景数据集实验

为了验证本研究所提出模型的有效性，首先在静态背景视频序列如Highway、Camouflage以及Blurred等数据集上进行实验。具体实验结果如图2所示，其中Highway（1 643）表示视频序列Highway的第1 643帧的前景-背景分离结果。

由 图2 可 见，与 现 有 模 型IALM［8］、3WD［10］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］相比，本模型实现了更好的前景-背景分离。具体来说，由图2中的第1行Highway可以看出，本方法不易受移动物体的遮挡和污染，可以获得更为干净的背景（见矩形符号），并可以提取出更完整的前景运动目标，如图2中第6行Camouflage（见矩形符号）所示。

图1 参数对数据集“WaterSurface”的影响Fig.1 Effect of parameters for dataset“WaterSurface”

图2 静态背景视频中前景检测和背景提取结果的视觉质量比较Fig.2 Visual quality comparison for foreground detection and background extraction results achieved by different methods on static background videos

3.3.2 动态背景数据集实验

为了更好地评估本模型的有效性，本研究进一步在更具挑战性的动态背景视频上进行了大量实验，分别对9个典型的动态视频序列，即Billboard、Boats1以及WaterSurface等数据集进行了实验。图3给出了本模型以及相应对比模型［8，10-13］的具体分离效果。由图3可以看出，本模型对于大多数动态背景数据集而言，尤其是对Billboard、Boats1以及Fall等数据集，实现了良好的前景-背景分离效果。

首先，对于前景检测而言，如第1行数据集Billboard所示，由于广告牌屏幕一直在变化，进而导致对比方法3WD［10］、IALM［8］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］会将其作为运动前景对象，并与真实前景（即行驶的车辆）一起提取，尤其是3WD的结果更差。然而，本方法仅将行驶中的车辆进行了提取，避免了背景对前景的干扰（见矩形框）。此外，对于第5行数据集Fall而言，所有方法都可以较好地提取行驶的车辆，但是对于马路对面的行人，只有本模型和SCM-RPCA 模型实现了更好的检测和提取（见箭头所指）。其次，对于背景提取，如第4行Boats1所示，本方法和对比方法RMAMR取得良好的视觉效果，而IALM、SCM-RPCA和TVRPCA的提取效果稍差，3WD最差（见矩形符号）。

图3 动态背景视频中前景检测和背景提取结果的视觉质量比较Fig.3 Visual quality comparison for foreground detection and background extraction results achieved by different methods on dynamic background videos

定量评估实验结果如表3所示，本研究所提方法在动态背景视频中取得了较好的前景检测效果，在召回率、精确度、相似度和F-Measure等几乎所有评估指标方面都达到了最佳结果。表中的粗体数字表示最优结果，下划线数字代表次最优结果。

3.4 运行时间和迭代次数

为了说明本模型在计算时间和计算量上的优势，将其分别与现有的3WD［10］、IALM［8］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］等方法进行了比较。通过比较可以看出，对于大多数数据集而言，本方法不仅计算量少，而且迭代次数也少。具体结果详见表4和表5（100+：迭代限制达到100）。

表3 不同算法在动态背景视频上的实验结果比较Tab.3 Comparisons results achieved by the different algorithms on dynamic background videos

表4 静态背景视频中不同算法的计算时间、迭代次数和相对误差的比较Tab.4 Comparison of computation time，iteration times and relative error under different algorithms on static background videos

表5 动态背景视频中不同算法的计算时间、迭代次数和相对误差的比较Tab.5 Comparison of computation time，iteration times and relative error under different algorithms on dynamic background videos

4 总结与展望

通过引入矩阵分解技巧，并结合二值模板和置信图，提出了一种改进的RPCA 模型用于前景-背景分离问题。通过大量实验，与现有的方法相比，本模型在节省计算时间和降低计算复杂性上具有明显的优势，且实验结果更接近真实情况。然而，在实际应用中仍然存在一些挑战，如合理构建数学模型去处理背景中包含喷泉的情形以及在恶劣天气情况下的视频前景-背景分离等问题，将是下一步研究的课题。