一种稀疏和低秩联合表达的视频前景对象精准提取方法

摘要

本发明提供一种稀疏和低秩联合表达的视频前景对象精准提取方法，该方法首先选取输入视频中能够代表视频特征的帧作为关键帧，然后根据关键帧中的已知像素点训练出字典，接着根据字典获取满足低秩、稀疏和非负约束的重构系数，并根据重构系数建立输入视频中每个像素之间的非局部关系矩阵，同时建立多帧之间的拉普拉斯矩阵，再根据输入视频的已知像素点的α值和字典中样本点的α值、非局部关系矩阵和拉普拉斯矩阵，获取输入视频的视频掩像，最后根据视频掩像提取出输入视频的前景对象，保证了视频掩像在时域上的一致性，提高了提取的前景对象的质量。

说明书

技术领域

本发明涉及图像处理技术，尤其涉及一种稀疏和低秩联合表达的视频前 景对象精准提取方法。

背景技术

视频前景对象精准提取旨在视频中提取出移动的前景物体，并且能够保 证良好的时域一致性。视频前景对象精准提取作为计算机视觉领域的重要技 术问题，在毛发建模、去雾等方面具有广泛的应用，近几年有不少提取方法 也相继被提出，以实现在复杂的视频图像中提取高质量的前景对象。

随着稀疏表达已经被广泛地应用于人脸识别、图像分类、图像修复和视 频去噪等领域，Jubin等人提出了基于稀疏表达的图像前景物体精准提取的方 法，该方法用整个视频的前景像素点重构原图像，根据稀疏表达系数矩阵中 每个像素点相应系数的和来估计像素点的不透明度α(alpha)值。该方法能 够自动选取合适的样本点来重构原图像，但是其不能保证具有相似特征的像 素点的α值相近，从而不能保证视频掩像(alphamatte)的时域一致性，且只 采用前景像素点作为字典，表达能力差，从而导致采用该方法提取的前景对 象质量不高。

X.Chen和Q.Chen等人提出了引入非局部先验的方法来获取视频掩像， 通过构建视频掩像的非局部结构来提高提取质量。该方法在实现时，对每个 像素点都直接选取固定数量的样本点来重构该像素点，但是样本点选取少了 会导致遗漏掉好的样本点，样本点选取多了会导致噪声，并且很难为具备相 似特征的像素点构建一致的非局部结构，这样可能会导致视频掩像时域上的 不一致，从而采用该方法提取的背景对象质量不高。

上述两种方法，在进行视频前景对象提取时，都具有诸多缺点而导致提 取的背景对象质量不高，因此，有必要提出一种新的方案来提高提取的前景 对象的质量。

发明内容

针对现有技术的上述缺陷，本发明提供一种稀疏和低秩联合表达的视频 前景对象精准提取方法，用于提高提取的前景对象的质量。

本发明提供一种稀疏和低秩联合表达的视频前景对象精准提取方法，包 括：

确定输入视频中的已知像素点和未知像素点，设置已知像素点的不透明 度α值，并选取输入视频中能够代表视频特征的帧作为关键帧，其中已知像 素点包括前景像素点和背景像素点；根据关键帧中的已知像素点训练出字典， 并设置字典中样本点的α值，字典包括前景字典和背景字典；根据字典获取 输入视频关于字典的重构系数，并根据重构系数建立输入视频中每个像素之 间的非局部关系矩阵，其中，重构系数满足低秩、稀疏和非负；建立多帧之 间的拉普拉斯矩阵；根据输入视频的已知像素点的α值和字典中样本点的α 值、非局部关系矩阵和拉普拉斯矩阵，获取输入视频的视频掩像；根据视频 掩像提取出输入视频的前景对象。

在本发明的一实施例中，确定输入视频中的已知像素点和未知像素点， 具体包括：

采用画笔式交互标记确定输入视频中的已知像素点和未知像素点，或者， 根据输入视频的三分图确定输入视频中的已知像素点和未知像素点。

在本发明的一实施例中，设置已知像素点的不透明度α值，具体包括：

将已知的前景像素点的α值设置为1，将已知的背景像素点的α值设置 为0。

在本发明的一实施例中，根据关键帧中的已知像素训练出字典，具体包 括：

根据最小化以下能量方程(1)训练出字典：

$\underset{\left(D,Z\right)}{\mathrm{argmin}}\underset{i,j}{\Sigma }\left(\left|\right|\hat{X}-DZ|{|}_F^2+||{\hat{X}}_i-D_i{Z}_i|{|}_F^2+\underset{j\ne i}{\Sigma }\left|\right|D_j{Z}_i^j|{|}_F^2\right)---\left(1\right)$

其中，表示关键帧中的已知像素点，和分别表示关键帧 中已知的前景像素点和背景像素点；D＝{D_f,D_b}表示训练出的字典，D_f和D_b分 别表示前景字典和背景字典；Z＝{Z_f,Z_b}表示已知像素点关于字典D的重构系 数，表示前景点关于字典D的重构系数，表示背景 点关于字典D的构造矩阵的系数，表示已知点关于子字典D_j的重构系数。

在本发明的一实施例中，根据字典获取输入视频关于字典的重构系数， 具体包括：

根据最小化以下能量方程(2)获取输入视频关于字典的重构系数：

$min\underset{i}{\overset{n}{\Sigma }}\left(\right||X_i-{\mathrm{DW}}_i|{|}_0+\left|\right|W_i\left|{|}_0\right)+\left|\right|W|{|}_{*}\forall p,q,{\left(w_i\right)}_{p,q}\in W_i,s.t.{\left(w_i\right)}_{p,q}>=0.---\left(2\right)$

其中，X＝{X₁,…,X_n}，n表示输入视频共n帧，X_i表示第i帧的RGBXY特 征，||·||_*表示核范数，为矩阵奇异值的和，||·||₀表示零范数，为非零元素的个 数，m表示每一帧中共m个像素点，t 表示字典D共有t个样本点，(w_i)_q,p表示第i帧中第p个像素点对字典中第q个 样本点的重构系数。

在本发明的一实施例中，根据重构系数建立输入视频中每个像素之间的 非局部关系矩阵，具体包括：

根据公式(3)建立非局部关系矩阵：

$min\underset{i}{\overset{n}{\Sigma }}\underset{j}{\overset{m}{\Sigma }}{({\alpha }_{ij}-{\alpha }_D{w}_{ij})}^2---\left(3\right)$

其中α_ij表示第i帧中第j个像素点的α值，m表示每一帧中像素点的数量， α_D＝{α_f,α_b}表示字典D中所有样本点的α值，α_f＝1表示前景字典中的样本点 的α值，α_b＝0表示背景字典中的样本点的α值，w_ij＝[(w_i)_1,j,...,(w_i)_t,j]表示第i帧 中第j个像素点对字典D的重构系数。

在本发明的一实施例中，建立多帧之间的拉普拉斯矩阵，具体包括：

根据公式(4)建立多帧之间的拉普拉斯矩阵：

其中，表示拉普拉斯矩阵，δ控制局部平滑的强度，k表示一帧中窗 口的个数，c_k表示第k个窗口，C_i表示第i个像素点的颜色值，μ_k和Σ_k分别 表示窗口中的颜色均值和方差，ò为正规系数，d×m²为窗口的尺寸，表示选 取相邻d帧，每帧取m²窗口内的像素点作为邻居，I表示单位矩阵。

在本发明的一实施例中，将正规系数ò设置为10^-5，m设置为3，d设置为 2。

在本发明的一实施例中，根据输入视频的已知像素点的α值和字典中样 本点α值、非局部关系矩阵和拉普拉斯矩阵，获取输入视频的视频掩像，具 体包括：

根据公式(5)获取输入视频中每个未知像素点的α值：

$E=\lambda \underset{s\in S}{\Sigma }{\left({\alpha }_s-g_s\right)}^2+\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}{\left({\alpha }_{ij}-{\alpha }_D{w}_{ij}\right)}^2+\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}{\left({\Sigma }_{(k\in N_j}{W}_{jt}^{mlap}\left({\alpha }_{ij}-{\alpha }_k\right)\right)}^2---\left(5\right)$

其中，S表示输入视频的已知像素点的α值和字典中样本点α值构成的 集合，N_j为像素点j在d×m²的窗口中的邻接点，g_s＝1表示集合S中的像素点 s为前景像素点，g_s＝0表示集合S中的像素点s为背景像素点；

根据输入视频的已知像素点的α值和未知像素点的α值获取输入视频的 视频掩像。

本实施例提供的稀疏和低秩联合表达的视频前景对象精准提取方法，根 据选取的关键帧中已知的前景像素点和背景像素点训练出具有较强表达性的 字典；然后根据该字典获取满足低秩、稀疏和非负约束的重构系数，根据重 构系数建立输入视频中每个像素之间的非局部关系矩阵，同时建立多帧之间 的拉普拉斯矩阵，从而保证了获取的输入视频的视频掩像的时域一致性和局 部光滑性，进而使得根据该视频掩像提取的输入视频的前景对象的质量也得 到了有效的提高。

附图说明

图1为本发明提供的视频前景对象提取方法实施例一的流程示意图；

图2为本发明中多帧之间的拉普拉斯矩阵的构建图；

图3为本发明提供的视频前景对象提取方法实施例二的流程示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发 明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述， 显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于 本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获 得的所有其他实施例，都属于本发明保护的范围。

图1为本发明提供的视频前景对象提取方法实施例一的流程示意图，本 方法的执行主体可以是计算机等处理设备，如图1所示，本实施例提供的方 法包括：

S101、确定输入视频中的已知像素点和未知像素点，设置已知像素点的 不透明度α值，并选取输入视频中能够代表视频特征的帧作为关键帧。

具体的，已知像素点包括前景像素点和背景像素点，前景像素点就是需 要提取出的图像内容所在区域中的像素，背景像素点就是不需要提取的图像 内容所在区域中的像素；已知像素点就是根据输入视频可以明确确定属于前 景图像或背景图像的像素点，未知像素点就是前景图像和背景图像交叉难以 区别的区域中的像素。

在确定已知像素点和未知像素点时，可以采用画笔式交互标记确定输入 视频中的已知像素点和未知像素点，例如：采用画笔标记视频图像中的前景 像素和背景像素，其中，用白色画笔覆盖的像素点为已知的前景像素点，用 黑色画笔覆盖的像素点为已知的背景像素点；其他未用画笔做标记的像素点 为未知像素点。

或者，也可以根据输入视频的三分图确定输入视频中的已知像素点和未 知像素点，具体的，可以提供与输入视频相同尺寸的黑白灰三分图，白色区 域所对应的像素点为已知的前景像素点，黑色区域所对应的像素点为已知的 背景像素点，灰色区域所对应的像素点为未知像素点。

需要说明的是，在确定输入视频中的已知像素点和未知像素点时，可以 根据实际情况对全部输入视频采用上述方式进行处理，也可以只对部分输入 视频进行处理，其他未确定已知像素点的视频图像中的所有像素点均确定为 未知像素点。

在确定完设置输入视频中的已知像素点后，可以对已知像素点的不透明 度α值进行设置，将需要提取出的前景像素点的α值设置为较大的值，将不 需要提取出的背景像素点的α值设置为较小的值。优选的，本实施例中，将 已知的前景像素点的α值设置为最大值1，将已知的背景像素点的α值设置 为最小值0。

另外，整个输入视频的数据量较大，本实施例中，选取输入视频中能够 代表视频特征的帧作为关键帧来训练字典，以减少计算量。在选取关键帧时， 可以每隔若干帧图像选取一帧图像，将选取的几帧图像作为关键帧；也可以 在变化较大的视频段多选取几帧图像，在变化较小的视频段少选取几帧图像 作为关键帧，具体都可根据情况任意选择，只要能够代表视频特征即可。

S102、根据关键帧中的已知像素点训练出字典，并设置字典中样本点的 α值。

获取关键帧之后，即可根据关键帧中的已知像素点训练出字典，字典包 括前景字典和背景字典，其特征空间为包括RGBXY特征值在内的五维特征 空间，其中RGB是像素点的RGB颜色值，XY是像素点在图像中的坐标位 置。字典的训练过程可转化为最小化以下能量方程：

$\underset{\left(D,Z\right)}{\mathrm{argmin}}\underset{i,j}{\Sigma }\left(\right||\hat{X}-DZ|{|}_F^2+\left|\right|{\hat{X}}_i-D_i{Z}_i|{|}_F^2+\underset{j\ne i}{\Sigma }|\left|D_j{Z}_i^j\right|{|}_F^2)---\left(1\right)$

其中，表示关键帧中的已知像素点，和分别表示关键帧 中已知的前景像素点和背景像素点；D＝{D_f,D_b}表示训练的字典，D_f和D_b分 别表示前景字典和背景字典；Z＝{Z_f,Z_b}表示已知像素点关于字典D的重构系 数，表示前景点关于字典D的重构系数，表示背景 点关于字典D的构造矩阵的系数，表示已知点关于子字典D_j的重构系数。

上述公式(1)中，第一项表示该字典能够重构所有已知的像素 点，从而能够保证该字典具有较强的表达能力；第二项表示字典D_i能够重构出已知像素点X_i，即前景像素点能够由前景字典重构出来并且背景 像素点能够由背景字典重构出来；第三项约束已知像素点X_i关于字 典D_j的重构系数要接近于0，即前景点对前景字典有响应但对背景字典几 乎没有响应，并且背景点对背景点有响应但是对前景字典几乎没有响应，前 景字典和背景字典有较强的区分性，也就是说，前景点是由前景字典重构出 来的但不能由背景字典重构出来，背景点是由背景字典重构出来但不能由前 景字典重构出来。

对于字典中各样本点的α值，可将前景字典中样本点的α值设置为1， 将背景字典中样本点的α值设置为0。

S103、根据字典获取输入视频关于字典的重构系数，并根据重构系数建 立输入视频中每个像素之间的非局部关系矩阵。

由于不同视频帧的描述的相同物体的像素点来自于一个完全相同的特征 子空间，所以每一个像素点都能够由特征子空间中的元素通过线性组合表达 出来，进而整个视频可以由字典通过低秩稀疏的表达矩阵(即下述的重构系 数矩阵)重构出来。对于整个输入视频，其中的每个像素点关于字典D都有 一个重构系数，整个输入视频的重构系数可以表示为：

对整个输入视频的重构系数的求解过程可归结为最小化以下能量方程：

$min\underset{i}{\overset{n}{\Sigma }}\left(\right||X_i-{\mathrm{DW}}_i|{|}_0+\left|\right|W_i\left|{|}_0\right)+\left|\right|W|{|}_{*}\forall p,q,{\left(w_i\right)}_{p,q}\in W_i,s.t.{\left(w_i\right)}_{p,q}>=0.---\left(2\right)$

其中，X＝{X₁,…,X_n}，n表示输入视频共n帧，X_i表示第i帧的RGBXY特 征，||·||_*表示核范数，为矩阵奇异值的和，用于约束重构系数低秩，||·||₀表示 零范数，为非零元素的个数，用于约束重构系数稀疏，m表示每一帧中共m个 像素点，t表示字典D共有t个样本点，(w_i)_q,p表示第i帧中第p个像素点对字 典中第q个样本点的重构系数。

在上述公式(2)中，稀疏约束能够保证视频中的每个像素点能够由字典 中的几个元素重构出来，低秩约束能够保证视频掩像时域上的一致性。具体 的，低秩约束能够保证一帧中具有相似特征的像素点能够由字典中相同的元 素重构出来，这样便保证了视频掩像在空间上的一致性；低秩约束还能够保 证连续视频中具有相似特征的像素点也能够由字典中的相同元素重构出来， 这样便保证了视频掩像在时间上的一致性。优选的，低秩要求W的秩远小于 它的行数和列数，稀疏要求W中的0的数量超过50％。

在求解出输入视频的重构系数之后，可以根据重构系数建立输入视频中 每个像素之间的非局部关系矩阵：

$min\underset{i}{\overset{n}{\Sigma }}\underset{j}{\overset{m}{\Sigma }}{({\alpha }_{ij}-{\alpha }_D{w}_{ij})}^2---\left(3\right)$

其中α_ij表示第i帧中第j个像素点的α值，m表示每一帧中像素点的数量， α_D＝{α_f,α_b}表示字典D中所有样本点的α值，α_f＝1表示前景字典中的样本点 的α值，α_b＝0表示背景字典中的样本点的α值，w_ij＝[(w_i)_1,j,...,(w_i)_t,j]表示第i帧 中第j个像素点对字典D的重构系数。

上述求解的重构系数满足低秩和稀疏约束，从而根据该重构系数构建的 非局部关系矩阵能够保证视频掩像在非局部关系上的时域一致性。

S104、建立多帧之间的拉普拉斯矩阵。

在建立非局部关系的同时，可以通过建立帧间的拉普拉斯矩阵来保证视 频掩像在局部关系上的时域一致性。具体可以根据公式(4)建立多帧之间的 拉普拉斯矩阵

其中，δ控制局部平滑的强度，k表示一帧中窗口的个数，c_k表示第k个 窗口，C_i表示第i个像素点的颜色值，μ_k和Σ_k分别表示窗口中的颜色均值和 方差，ò为正规系数，d×m²为窗口的尺寸，表示选取相邻d帧，每帧取m²窗 口内的像素点作为邻居，I表示单位矩阵。

上述拉普拉斯矩阵由单帧图像扩展到多帧图像，除了考虑在本帧中邻域 窗口内的像素点外，还会考虑相邻视频帧间邻域窗口内的像素点，由这些像 素点共同作为邻居构建该点的颜色线模型，从而既能够增强视频掩像的局部 光滑性，还能够增强相邻帧的视频掩像的时域一致性。

优选的，在上述公式(4)中，将正规系数ò设置为10^-5，m设置为3，d 设置为2。图2为本发明中多帧之间的拉普拉斯矩阵的构建图，如图2所示， 图中说明了构建两帧拉普拉斯矩阵的方法。对于当前帧的像素点j来说，不 仅要考虑本帧中3×3的窗口内的像素点，还要考虑相邻帧中3×3的窗口内 的像素点，这两部分像素点共同构成像素j的邻居，然后构建拉普拉斯矩阵。

需要说明的是，步骤S103和步骤S104之间没有严格的时序关系，步骤 S104也可以在步骤S103之前执行，还可以与步骤S103同时执行。

S105、根据输入视频的已知像素点的α值和字典中样本点的α值、非局 部关系矩阵和拉普拉斯矩阵，获取输入视频的视频掩像。

根据S101中确定的所有已知像素点的α值、S102中训练出的字典中各 样本点的α值、S103中建立的非局部关系矩阵和S104中建立的拉普拉斯矩 阵，可以构建连续多帧中所有像素点额能量方程，通过最小化能量方程可以 解得每一个像素点属于前景的概率(即α值)，从而得到视频掩像。

具体的，可以根据公式(5)构建能量方程：

$E=\lambda \underset{s\in S}{\Sigma }{\left({\alpha }_s-g_s\right)}^2+\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}{\left({\alpha }_{ij}-{\alpha }_D{w}_{ij}\right)}^2+\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}{\left({\Sigma }_{(k\in N_j}{W}_{jt}^{mlap}\left({\alpha }_{ij}-{\alpha }_k\right)\right)}^2---\left(5\right)$

其中，S表示输入视频的已知像素点的α值和字典中样本点α值构成的 集合，N_j为像素点j在d×m²的窗口中的邻接点，g_s＝1表示集合S中的像素点 s为前景像素点，g_s＝0表示集合S中的像素点s为背景像素点。

在根据上述公式(5)求得输入视频中未知像素点的α值后，再结合输入 视频的已知像素点的α值，即可获取输入视频的视频掩像。

对于上述公式(5)的求解，具体可以通过以下方式实现：

上述能量方程E用矩阵形式可以表示为：

E＝(α-G)^TΛ(α-G)+α^TLα(6)

其中Λ为对角线矩阵，如果像素点s属于集合S则设Λ_ss为很大的常数， 例如200，否则设为0，G是一个向量，其值在步骤S102中确定的α值，如 果像素点s属于已知的前景像素点则设G_s为1，否则设为0，$L=\left(\begin{array}{cc}{L}_D& -W\\ -W^T& L_u\end{array}\right),$其中W是输入视频关于字典D的重构系数矩阵，L_D＝W*W^T，L_u对角线是每一 帧的多帧拉普拉斯矩阵，即L_u＝diag(W₁^mlap；...；W_n^mlap)，上述能量方程的矩阵形式 表示(6)是关于α的二次方程，可通过求解下列线性方程最小化α值：

(Λ+L)α＝ΛG(7)

上述方程是一个稀疏线性方程组，可以通过预处理共轭梯度方法求解一 个全局最优的闭合解。

S106、根据视频掩像提取出输入视频的前景对象。

对于输入视频X，其每个像素点X_i都是由前景图像的颜色F_i和背景图像 的颜色B_i线性组合而成的，即X_i＝F_i×α_i+B_i×(1-α_i)，因此将上述获取的视频 掩像中各像素点的α值与输入视频中各像素点进行点乘，即可提取出输入视 频的前景对象，具体用公式可以表示为：

C＝X×α(7)

其中C表示提取后的视频图像，X表示输入视频，α表示与输入视频对 应的视频掩像中各像素点的α值。

现有的基于稀疏表达的图像前景物体精准提取的方法，只采用前景像素 点重构原图像，不能保证视频掩像的时域一致性，且只采用前景像素点作为 字典，表达能力差，导致采用该方法提取的前景对象质量不高；而相比该方 法，本实施例中通过低秩约束和多帧之间的拉普拉斯矩阵来保证具有相似特 征的像素点具有相似的α值，从而保证了视频掩像的时域一致性，并且用来 训练字典的已知像素点包括背景像素点和前景像素点，构造出的前景字典和 背景字典具有较强的区分性，表达能力强，有效的提高了提取的前景对象的 质量，此外本实施例中只采用关键帧中的像素点训练字典，计算量小。现有 的引入非局部先验的方法来获取视频掩像的方法，选取固定数量的样本点来 重构原图像，很难为具备相似特征的像素点构建一致的非局部结构，从而可 能会导致视频掩像时域上的不一致，采用该方法提取的前景对象质量不高； 而本实施例提供的方法，首先根据已知像素点构造出前景字典和背景字典， 然后在求解重构系数时通过稀疏约束来自动选取字典中的样本点，并且通过 低秩约束和多帧之间的拉普拉斯矩阵来保证具有相似特征的像素点具有相似 的α值，从而保证了视频掩像的时域一致性，进而有效的提高了提取的前景 对象的质量。

本实施例提供的方法，经过多次实验，在处理物体快速运动时留下的残 影问题、半透明物体的边缘和不同的半透明度、以及拓扑结构变化很大的物 体时，都具有很大的优势，可广泛应用到影视节目制作等图像处理领域。

本实施例提供的稀疏和低秩联合表达的视频前景对象精准提取方法，根 据选取的关键帧中已知的前景像素点和背景像素点训练出具有较强表达能力 和区分性的字典；然后根据该字典获取满足低秩、稀疏和非负约束的重构系 数，根据重构系数建立输入视频中每个像素之间的非局部关系矩阵，同时建 立多帧之间的拉普拉斯矩阵，从而保证了获取的输入视频的视频掩像的时域 一致性和局部光滑性，进而使得根据该视频掩像提取的输入视频的前景对象 的质量也得到了有效的提高。

图3为本发明提供的视频前景对象提取方法实施例二的流程示意图，本 实施例主要是对上述步骤S103中获取输入视频关于字典的重构系数的详细 步骤进行说明。在上述实施例的基础上，如图3所示，本实施例中，步骤S103 根据字典获取输入视频关于字典的重构系数，具体包括：

S201、将公式(2)等价转化为公式(8)：

$\begin{array}{ccc}min\underset{i}{\overset{n}{\Sigma }}\left(\right|\left|W_i\right|{|}_1+\lambda \left|\right|E_i\left|{|}_1\right)+\gamma \left|\right|W|{|}_{*}& s.t.& X_i=D_i{S}_i+E_i;W=J_i;W=S_i;W_i=T_i,T_i>=0.\end{array}---\left(8\right)$

其中，X_i表示第i帧的RGBXY特征，λ和γ表示平衡系数， S₁,…,S_n,…,J₁,…,J_n,…,T₁,…,T_n为辅助变量。

S202、将公式(3)等价转化为公式(9)：

$\begin{array}{c}min\left(\gamma \right|\left|W\right|{|}_{*}+\underset{i}{\overset{n}{\Sigma }}\left(\left|\right|J_i|{|}_1+\lambda |\left|E_i\right|{|}_1\right)+\underset{i}{\overset{n}{\Sigma }}(<A_i,W_i-J_i>+<Y_i,X_i-D_i{S}_i-E_i>+<V_i,W_i-S_i>\\ +<U_i,W_i-T_i>+\frac{\mu }{2}\left|\right|X_i-D_i{S}_i-E_i|{|}_F^2+\frac{\mu }{2}||W_i-J_i|{|}_F^2+\frac{\mu }{2}\left|\right|W_i-S_i|{|}_F^2+\frac{\mu }{2}||W_i-T_i|{|}_F^2\left)\right)\end{array}---\left(9\right)$

其中，E_i为对第i帧的重构误差，A₁,…,A_n,…,Y₁,…,Y_n,…,V₁,…,V_n,U₁,…,U_n为 是拉格朗日乘子。

S203、采用交替方向法(alternatingdirectionmethod，ADM)求解公式(9)。

ADM算法也就是增广拉格朗日乘子法(inexactaugmentedLagrange multiplierMethod；inexactALM)，该ADM算法主要采用迭代求解方法，输 入变量有n帧视频X、字典D和平衡系数λ、γ。具体的步骤如下：

首先进行初始化A＝U＝V＝Y＝0,S＝T＝J＝0,μ＝10^-6，然后开始迭代过程：

1、固定其他变量，更新J_i，具体采用的公式为：

$J_i=\underset{J_i}{\mathrm{argmin}}\frac{1}{\mu }\left|\right|J_i|{|}_1+\frac{1}{2}||J_i-\left(W_i+\frac{A_i}{\mu }\right)|{|}_F^2.$

2、固定其他变量，更新S_i，具体采用的公式为：

$S_i={(D^{T}D+I)}^{-1}\left(D^T\left(X_i-E_i\right)+W_i+\frac{(D^T{Y}_i+V_i)}{\mu }\right)·$

3、固定其他变量，更新T_i，具体采用的公式为：

$T_i=W_i+\frac{U_i}{\mu },T_i=max(T_i,0)·$

4、固定其他变量，更新W，具体采用的公式为：

$W_i=\underset{W}{\mathrm{argmin}}\frac{\gamma }{2\mu }\left|\right|W|{|}_{*}+\frac{1}{2}||W-M|{|}_F^2.$

其中，M＝[F₁,F₂,…,F_n]，$F_i=\frac{1}{3}\left(J_i+S_i+T_i=\frac{(A_i+V_i+U_i)}{\mu }\right).$

5、固定其他变量，更新重构误差E_i，具体采用的公式为：

$E_i=\underset{E_i}{\mathrm{argmin}}\frac{\lambda }{\mu }\left|\right|E_i|{|}_1+\frac{1}{2}||E_i-(X_i-{\mathrm{DS}}_i+\frac{Y_i}{\mu })|{|}_F^2.$

6、更新每个拉格朗日乘子A_i,Y_i,V_i，具体采用的公式为：

A_i＝A_i+μ(W_i-J_i),Y_i＝Y_i+μ(X_i-DS_i-E_i),

V_i＝V_i+μ(W_i-S_i),U_i＝U_i+μ(W_i-T_i).

7、更新μ，具体采用的公式为：

μ＝min(1.1μ,10¹⁰).(ρ＝1.9).

8、检查收敛条件是否达到，即 X_i-DS_i-E_i→0,W_i-J_i→0,W_i-S_i→0andW_i-T_i→0，如果不收敛则继续迭代，直 到收敛或者达到最大的迭代次数。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对 其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通 技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改， 或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并 不使相应技术方案的本质脱离本发明各实施例技术方案的范围。