基于RPCA视频去噪算法的自适应优化方法

李小利　杨晓梅

(四川大学电气信息学院自动化系　四川 成都 610065)



基于RPCA视频去噪算法的自适应优化方法

李小利杨晓梅

(四川大学电气信息学院自动化系四川 成都 610065)

传统去噪算法不能在尽量滤除噪声的同时很好地保持原始图像信息。针对这种情况，提出基于鲁棒主成分分析的自适应视频去噪算法。首先根据视频数据的低秩性和噪声的稀疏性，利用加速近端梯度方法重建出原始视频的低秩部分和稀疏部分，实现噪声的初步分离；其次利用自适应中值滤波器进行预滤波处理，提高块匹配精度，进一步去除视频噪声；最后引入自适应奇异值阈值法，增强图像细节边缘信息，降低迭代优化算法的时间复杂度。实验结果表明，该方法不仅能极大程度地恢复出原始视频序列， 还能自适应地去除干扰噪声。不论从客观指标PSNR值还是从主观视觉，该方法与传统去噪方法相比都具有很大的优势。

视频去噪低秩性鲁棒主成分分析自适应奇异值阈值

0　引　言

随着计算机和多媒体技术的发展，海量视频文件的出现对视频的整理、分析以及检索提出了越来越多的需求。从现实意义的角度来看，图像视频技术需求非常普遍，如高质量成像设备、视频成像软件和面向公共安全的成像设备等[8]。然而在大多数情况下，如在拍摄、采样、传输等过程中，视频数据常常受到各种类型噪声的干扰而退化。尤其是在低光条件、高ISO设定和高捕获频率等敏感环境下，都能使视频图像变得模糊。作为计算领域的一个研究热点，视频去噪效果的好坏将对后续的视频分析和理解等处理产生至关重要的影响。

目前，国内外根据图像特点、噪声的统计特征、频谱分布规律已提出了许多关于图像去噪的传统方法，大致可分为空间域法和变换域法[5]两类。前者主要利用平滑模板的卷积处理，通过数据运算直接对像素灰度值进行处理。其常用方法主要中值滤波法[6]，它是一种基于非线性的信号处理方法，其基本原理就是利用领域模板中灰度值的中值来替换该点像素值。这种方法对于带有椒盐噪声的图像恢复有较好的效果。然而中值滤波器作为一种非参数估计，处理方式单一，可能会造成图像细节和边缘信息的丢失。对于变换域法，先对图像进行变换将其转到变换域，再对变换域中的系数进行滤波处理，最后反变换到原始空间域得到去噪图像。常见的方法有频域滤波[7]、小波变换法[8]、BM3D法[17]等。通过对信号变换使得换系数具有明显的分布特征，对噪声的滤波处理变得更加有效。

近年来，基于压缩感知技术的稀疏模型[4]和非局部模型成为图像去噪研究的热门，并被广泛运用于图像处理的各个领域。非局部均值[16]去噪利用图像结构的自相似性，通过对相似块进行加权平均得到去噪图像。稀疏模型本质上是属于变换域，采用全新的采样理论，突破了Nyquist采样定理的瓶颈。它主要是利用观测矩阵将原始信号稀疏化[9，10]，其关键在于观测矩阵的设计，主要强调样本数据在观测矩阵下的稀疏表示，从而忽略了图像块的非局部信息。低秩恢复[11-13]是随着稀疏理论的发展而提出的，其基本思想是通过约束矩阵奇异值的稀疏性，使矩阵的秩降到最低。随着稀疏与低秩的发展，近一两年来，出现了一种基于块的联合稀疏与低秩模型[3]。该方法在原始图像的重构算法中，不仅对椒盐噪声有很好的抑制效果，还能在去除图像中随机噪声和异常值基础上，较好地保留细节信息。基于该方法，本文引入了自适应阈值迭代的思想提出了改进，并应用于视频图像去噪。

1　预备知识

定理1矩阵奇异值分解。设X的秩为r，它的奇异值分解为：

(1)

其中，U和V分别为m×r,r×n的正交矩阵，对角矩阵∑r=diag(λ1,λ2,…,λr)，λi代表矩阵X的第i个奇异值，且λ1≥λ2≥…≥λr，那么X核范数定义如下：

(2)

对于每一个τ≥0，定义收缩算子[1]如下：

S(x，τ)=sgn(x)max(|x|-τ,0)

(3)

奇异值收缩算子：

D(x，τ)=US(∑，τ)VT

(4)

Sτ(x)和Dτ(x)在鲁棒主成分分析(RPCA)模型的求解算法中起着十分重要的作用，它们分别用来解以下两种最小化问题：

(5)

(6)

2　鲁棒主成分分析

2.1矩阵恢复

在具体问题中，很多信号都可以用数据矩阵来表示，这使得对数据的分析、建模极为方便。矩阵恢复理论最早由john wright等提出[14]，即鲁棒主成分分析(RPCA)，是指当矩阵某些元素被严重破坏后，自动识别出被破坏的矩阵并恢复出原始矩阵[15]。其具体描述为：将给定矩阵P分解为两个矩阵之和，即：P=L+S，其中L是逼近于原始矩阵的低秩矩阵，S是稀疏的噪声矩阵。将低秩矩阵恢复转化为如下最小化问题：

(7)

显然，式(7)的求解是一个NP难问题。Candes等[13,14]提出：在一定条件下，矩阵0范数的最小化和矩阵秩的最小化分别等价于矩阵1范数和矩阵核范数的最小化问题，于是将上述最小化问题转化成如下凸优化问题：

(8)

以此模型，将RPCA方法应用于视频去噪。对原始视频序列，利用其时空域的冗余性，采用基于块的方法来去除图像噪声。然而对存在显著噪声的图像，如何找到精确的匹配块不是一个简单的任务，因此，本文采用一个快速三步分层搜索法[1]来简单实现。将每一个块排列成一个向量，再将所有相似块对应的向量排列成一个矩阵，则稳定的图像信息对应矩阵的低秩部分，而随机干扰噪声对应于矩阵的稀疏部分。基于模型式(8)，本文将采用一种鲁棒性算法来恢复低秩矩阵L。

2.2优化模型的建立

上一节提出的最小化模型式(8)用来提取噪声数据的低维结构，它作为对主成分分析(PCA)的补充，对异常值具有一定的鲁棒性。在具体算法中，我们对式(8)引入拉格朗日算子[1]，将其转换如下形式：

(9)

选择合适的μ时，式(8)与式(9)等价。因此，正则化方法式(9)的有效性高度依赖于参数λ和μ的设定。在本文方法中，λ的值设定如下[1]：

(10)

至于μ，根据文献[1],我们选择其经验值：

(11)

其中，m、n 是相似块矩阵的大小，σ为图像噪声的标准差。

2.3加速近端梯度法

针对式(9)的低秩矩阵恢复问题，Goldfarb等[14]给出了集中具体的求解方法，如：迭代阈值(IST)方法、交替增广拉格朗日(ADAL)方法和加速近端梯度法(APG)方法等。在此，本文采用基于APG的矩阵恢复方法，根据其基本原理，设：

g(L,S)=μ‖L‖*+λμ‖S‖1

(12)

(13)

(14)

其中，Lf为Lipschitz常数，本文取Lf=2。针对式(14)的优化问题，本文采用快协调下降方法[1]进行交替迭代优化求解，其基本思路就是求解当前变量时固定其变量，具体步骤如下(用MATLAB编程的具体过程见算法1)：

1) 计算S*，固定L，目标函数转化成如下形式：

上式全局最小值为：

(15)

2) 计算L*，固定S，目标函数转化成如下形式：

上式全局最小值为：

(16)

3) 视频合成。在本文方法中，由于图像块的采样区域有重叠，因此每个像素由多个去噪图像块覆盖。与大多数基于块的方法类似，在视频合成过程中，图像的每个像素值由该像素点所有去噪图像块的平均估计值[1,3]确定，这将有利于消除块边界不连续的伪影。

算法1加速近端梯度(APG)算法，Lf=2

1) 输入矩阵P,λ,μ ;

2) 初始化:L0=L-1=0,S0=S-1=0,t0=t-1=0;

3) While not converged do

9) Until converged

10) 输出:Lk,Sk

3　空间自适应迭代奇异值阈值法

3.1奇异值阈值分析

上节提到的奇异值阈值算子式(4)，仅对奇异值进行了硬阈值操作，使之向无噪值收缩逼近，这在实际应用中明显不妥。一般情况下，如果输入矩阵的奇异值小于阈值，经过阈值处理之后的输出矩阵就是低秩的。根据文献[8]，阈值的选择不仅依赖于噪声水平，还与数据本身性质有关：阈值太大会使图像出现过平滑现象而导致其边缘细节模糊，太小又会导致去噪效果不明显。因此，选择恰当的阈值是改进算法的关键。接下来本文将对矩阵进行扰动分析，进一步讨论噪声对奇异值的影响。

文献[8]指出，相似块矩阵P各元素服从高斯分布，假定其秩为r，对P进行SVD分解：

(17)

其中ui和vi分别对应矩阵U和V的列向量, λ1≥λ2≥…≥λr，揭示了矩阵P的特征分量强度。这样，通过SVD分解就将含噪数据中真实的相关信号分离出来。也就是说，相似矩阵P的奇异值在一定程度上反映了真实的原始信号。因此，有必要进一步分析噪声对奇异值λi的影响。

该理论表明噪声强度是影响含噪矩阵与无噪低秩矩阵奇异值之差的主要因素，也进一步解释了低秩矩阵的恢复与其奇异值密切相关。不妨假设L的秩为l，则:

因此，当λ满足:

(18)

此时，可以选择矩阵P的前p个奇异值来作为对低秩矩阵L的估计。通过SVD分解，矩阵P的奇异值在空间上依此减小，特别的，从λl+1开始，奇异值的迅速减小趋近于0。据统计[8]，前10%甚至更少的奇异值之和在所有奇异值之和中有高达99%的比例，这样就可以通过选择恰当的阈值去掉较小奇异值，以最大程度逼近低秩矩阵。在上一节的算法中，用一个经验值作为对奇异值的硬阈值处理，本节我们将通过对P和L奇异值差异的估计，得到一个自适应的奇异值阈值。

3.2空间自适应迭代奇异值阈值法

由于噪声在每个奇异值上的分布并不均匀，不能直接选取同一个阈值，而应对不同的奇异值设计一个自适应的阈值，即空间自适应迭代奇异值阈值法(SAIST)[2]，其基本思想就是奇异值越大，含噪值和真实值差异越小，则奇异值阈值也就越小；反之，奇异值阈值就越大。

根据文献[2],将奇异值建模成零均值的拉普拉斯分布，根据空间自适应的先验知识，将阈值参数设为：

(19)

其中，σi代表位置i上的局部方差估计，采用单样本的最大似然估计如下：

(20)

此外，当下最新的迭代正则化技术提供了另外一种空间自适应方法，其基本思想就是将滤波噪声信号反馈到原始含噪图像，即：

(21)

其中，k为迭代次数，δ为松弛参数。我们将这种迭代正则化思想分别扩展到噪声估计和信号估计：

(22)

(23)

算法2空间自适应迭代奇异值阈值(SAIST)

2) While not converged do

3) 块匹配，构造相似块矩阵Y;

6) (U,∑,V)=svd(y)

388 Protective effects of dexmedetomidine on alveolar epithelial cells in sepsis mice

9) Until converged

3.3基于RPCA模型的自适应去噪算法

算法3基于SAIST 的APG改进算法(本实验中Lf=2)

1) 输入矩阵P,λ,μ;

3) While not converged do

11) Until converged

12) 输出Lk,Sk

图1　算法3的工作流程

4　实验结果及分析

4.1预滤波改进实验

在第2节的建模过程中，给定一个参考块，穷举搜索相似块可能是非常耗时的。且当视频数据被图像噪声严重损坏时，直接对噪声数据进行块匹配的结果非常不可靠。特别的，当有强脉冲噪声(如椒盐噪声)存在时，块匹配的性能将严重降低。

对此，本文在块匹配之前进行了一个去除脉冲噪声的预处理加以改进。在具体实现中，采用文献[24]提出的自适应中值滤波法，在算法中内置一个异常值去除器，用小邻域中值来替换被脉冲噪声损坏的像素。实验结果如图2和图3所示，值得注意的是，预滤波处理数据仅仅作为块匹配的输入，整个去噪模型的输入仍然是原始含噪图像。

图3　APG算法加预滤波局部放大效果

根据图2和图3，从视觉上已经能看出二者的差别。由其是从局部放大图来看，方法改进之后，去噪效果也明显提高。另外，从客观量化指标来看，APG算法恢复图像的PSNR值为23.8964，加预滤波方法恢复图像的PSNR值为26.8347，高出将近3 dB。由此可见，改变块匹配算法的输入能使整个去噪方法达到更优的去噪效果，这种改进的有效性得以验证。

4.2基于RPCA的自适应去噪实验

目前，关于视频修复方法，国内外已有大量丰富的研究文献。它们本质上可以分为三种类型：局部、非局部以及二者混合，本文研究的是一种非局部方法。因此，我们将从两个方面来，与传统的中值滤波器、非局部均值(NLM)去噪，以及目前公认的去噪效果最好的VBM3D算法进行对比，从主观视觉效果和峰值信噪比PSNR两个指标来评价去噪效果。

首先是传统的局部去噪法，我们选择中值滤波器来作为对比，它是一种基于非线性的信号处理方法，其基本原理就是利用领域模板中灰度值的中值来替换该点像素值。对于非局部方法，NLM是利用图像自相似性的开创方法之一。在NLM方法中[16]，每个像素估计值是在空间域和时间域上所有像素强度值加权平均，该权重值由集中在该像素的图像块与集中在其他像素的块的相似性测量来确定。特别的，近年来比较流行的BM3D算法在图像去噪中也采取了类似的做法。在VBM3D方法中[17]， 通过寻找相似块并将其聚集形成一个三维数组，然后在3D变换域上对这些三维数组进行联合滤波处理，从而去除噪声。最后，通过对去噪块的聚集合成得到真实图像的最终估计。

为了验证本文去噪算法的有效性，在相同实验环境下，将本文算法与上述三种方法进行比较，其结果如图4和图5所示。

图4　各方法去噪效果对比图

图5　各方法去噪效果局部放大对比

由图可以清楚地看到，总体上本文去噪算法的视觉效果及PSNR值都是最优。中值滤波器方法的结果仍有许多明显的噪声，在四中方法中效果最差；基于NLM及BM3D方法的结果对图像细节太平滑，由其是在凌乱部位，还会出现切断失真，但相比之下BM3D方法效果更优。相反，本文算法由于引入了稀疏矩阵来代表异常值，在恢复低秩矩阵的同时也能实现异常值的检测。因此，该算法能较好地保留图像的边缘细节信息。

4.3量化对比及结果分析

为了量化评估算法的性能，本文采用峰值信噪比(PSNR)客观指标来衡量图像质量。PSNR是一个表示信号最大可能功率与影响其精度的噪声功率的比值。基于信号较宽的动态范围，一般用对数分贝单位来表示：

其中，x(i,j)表示图像在位置(i,j)上的灰度值，y(i,j)表示含噪图像在位置(i,j)上的灰度值。 PSNR是根据失真信号与原始信号之间的误差差异定义的，计算方法清晰易懂，是评价图像质量最常用的客观标准，其值越大表明去噪效果越好。

从表1 可见，本文算法对不同水平的噪声都具有一定的鲁棒性。选择bus视频序列的第25帧作为输出，视频被高斯噪声和椒盐噪声同时污染， 其中σ和S的变化范围分别为5～40和0.01～0.05。我们可以看到，随着高斯噪声和椒盐噪声水平的加强，去噪效果呈下降趋势：横向来看，椒盐噪声加强，PSNR值缓慢下降；纵向来看，高斯噪声加强，PSNR快速下降。

也就是说高斯噪声比椒盐噪声更难去除，由此可以判断，算法1对椒盐噪声的鲁棒性优于高斯噪声。从另外一个角度，对于原始图像，加入高斯噪声之后，图像质量下降缓慢；相反，椒盐噪声却使图像质量快速下降。这是由于椒盐噪声只有两个极值，当图像像素被污染时，原始信息被完全破坏；而当图像被高斯噪声污染时，有大部分信息都被保留了下来。

表1　不同噪声水平在APG算法下的PSNR值

本文方法的目的在于针对第2节提出的去噪算法的不足，提出了一种基于RPCA的自适应阈值去噪法。该方法结合了非局部和RPCA技术，克服了硬阈值的局限，降低了迭代优化算法的时间复杂度。与第2节的结果相比，改进之后的算法在去除噪声的同时，能够保持更多的细节纹理。另外，从实验结果表2和图4、图5，可以清楚地看到，该方法与其他三种算法相比，具有更优越的视觉效果和PSNR指标，说明该算法的有效性和实用性。

表2　不同噪声水平在APG算法下的PSNR值

5　结　语

本文提出了一种基于RPCA模型的自适应视频去噪算法。该方法运用低秩矩阵恢复理论讲视频去噪转化为基于稀疏与低秩恢复的问题，极大程度地去除了干扰噪声并恢复原始视频序列。此外，通过加入预滤波处理与自适应阈值的改进，该方法能很好地适应各种强度的噪声，鲁棒性和自适应性较强。在未来的工作中，我们将研究如何用将高阶思想(即张量模型)运用在该算法中。同时，也将探索如何将该算法在视频图像处理方面的其他运用。

[1] Ji H, Huang S, Shen Z, et al. Robust video restoration by joint sparse and low rank matrix approximation[J].SIAM Journal on Imaging Sciences, 2011,4(4):1122-1142.

[2] Dong W, Shi G, Li X. Nonlocal image restoration with bilateral variance estimation: a low-rank approach[J].IEEE Trans on Image Processing，2012,2(22):700-711.

[3] Ji H, Liu C, Shen Z, et al. Robust video denoising using low rank matrix completion[C]//In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on,2010:1791-1798.

[4] Candàs C, Romberg J. Sparsity and incoherence in compressive sampling[J]. Inverse Problems, 2007, 23(3):969-985.

[5] 郑毅贤, 江浩淼, 金波, 等. 基于自适应压缩感知的图像去噪方法[J]. 通信技术, 2013 (3): 74-76.

[6] 任倩儒. 压缩感知理论及其在图像去噪中的应用研究[D]. 长安大学2012.

[7] 郑毅贤. 基于稀疏表示理论的图像去噪方法研究[D]. 上海交通大学, 2013.

[8] 唐中和. 低秩逼近理论及其在自然图像去噪中的应用[D]. 西安电子科技大学, 2013.

[9] 樊立. 压缩感知在图像去噪中的应用研究[D]. 北方工业大学,2013.

[10] 邹建成, 樊立. 一种基于压缩感知的图像去噪方法[J]. 北方工业大学学报, 2012, 24(1): 1-3.

[11] 马坚伟, 徐杰, 鲍跃全, 等. 压缩感知及其应用: 从稀疏约束到低秩约束优化[J]. 信号处理, 2012, 28(5): 609-623.

[12] 刘钢. 基于压缩感知和稀疏表示理论的图像去噪研究[D]. 电子科技大学, 2013.

[13] 彭义刚, 索津莉, 戴琼海, 等. 从压缩传感到低秩矩阵恢复: 理论与应用[J]. 自动化学报, 2013, 39(7): 981-994.

[14] 史加荣, 郑秀云, 魏宗田, 等. 低秩矩阵恢复算法综述[J]. 计算机应用研究, 2013, 30(6): 1601-1605.

[15] 张磊, 彭伟才, 原春晖, 等. 奇异值分解降噪的改进方法[J]. 中国舰船研究, 2012, 7(5): 83-88.

[16] 罗亮, 冯象初, 张选德, 等. 基于非局部双边随机投影低秩逼近图像去噪算法[J]. 电子与信息学报, 2013, 35(1): 99-105.

[17] 李政, 刘文江, 戎蒙恬, 等. BM3D 视频去噪算法实现与评估[J]. 信息技术, 2012(4):30-32.

AN ADAPTIVE OPTIMISATION METHOD BASED ON RPCA VIDEO DENOISING

Li XiaoliYang Xiaomei

(Department of Automation, School of Electrical Engineering and Information, Sichuan University, Chengdu 610065, Sichuan, China)

Traditional denoising algorithm cannot well reserve primitive image information while filtering the noise as much as possible. In light of this situation, the paper presents an RPCA-based adaptive video denoising algorithm. First, according to the low-rank property of video data and the sparsity of noise, it utilises the accelerated proximal gradient approach to reconstruct the low-rank component and sparse component of original video, and realises the initial separation of the noise. Then, it uses adaptive median filter to make pre-processing of filtration to improve block matching accuracy, and further removes video noise. Finally, it introduces adaptive singular-value threshold method to enhance the detailed edge information of image, reduces the time complexity of iterative optimisation algorithm. It is demonstrated by experimental result that the proposed algorithm can restore original video sequence to a great deal extent, besides it can also adaptively remove interference noise. The algorithm has significant advantage no matter in objective quantitative indicator PSNR or subjective vision quality compared with traditional denoising algorithms.

Video denoisingLow-rank propertyRobust principal component analysis (RPCA)Adaptive singular-value threshold

2015-06-09。李小利，硕士生，主研领域：视频图像去噪。杨晓梅，副教授。

TP3

A

10.3969/j.issn.1000-386x.2016.09.051