一种改进的RK-SVD随机噪声去噪方法

An Improved Denoising Algorithm Based on RK-SVD Method

摘要: 在图像的传递、形成和保存的过程中往往会受到外界因素的影响。稀疏表示是通过图像原子的信号组合来重现图像信号，而这些原子源自一个过完备冗余字典。字典的形成有两种方法，一种是设计字典来适应模型，另一种是使字典适应一组训练信号，以实现稀疏信号的表示。K-SVD算法是一种迭代方法，它在基于当前字典的列的稀疏编码和更新字典原子以更好地适应数据的过程中交替进行。本文在正则化K-SVD (即RK-SVD)算法基础上，通过改进了RK-SVD算法模型中计算误差项，使得改进的RK-SVD算法对数据的处理更加的准确，并且有效的阻止模型过拟合和欠拟合的发生。最后在实验的基础上，比较了改进后的RK-SVD算法的有效性。

Abstract: In the process of image transmission, formation and preservation, it is often affected by external factors. Sparse representation reproduces image signals by combining the signals of image atoms, which originate from an over complete redundant dictionary. There are two ways to form a dictionary, one is to design a dictionary to adapt to the model, the other is to make the dictionary adapt to a group of training signals to achieve sparse signal representation. K-SVD algorithm is an iterative method, which alternates between sparse coding of columns based on the current dictionary and updating dictionary atoms to better adapt to data. Based on the regularized K-SVD algorithm, this paper improves the calculation error term in the RK-SVD algorithm model, which makes the improved RK-SVD algorithm more accurate in data processing, and effectively prevents the occurrence of over fitting and under fitting of the model. Finally, on the basis of experiments, the effectiveness of the improved RK-SVD algorithm is compared.

1. 前言

在现今的生活中人们获取的信息80%来自于各种图像，图像视频的等视觉信息从网络的大面积普及开始已经成为人们获得信息的主要来源，社交网站Facebook的年上传照片总量达到6000亿张，且以每天上传5亿张照片的速度增长；视频分享网站Youtube上的视频日均浏览量更是高达80亿次，一张清晰优秀的图像可以让看图片的人获得完美的观看体验而质量较差的图像则会给观看的人带来糟糕的体验。质量较差的图像是因为图像在图像的获取或者传输的过程中受到各种外部环境或传感元件本身质量的影响而产生。图像噪声是指存在于图像数据中的不必要的或多余的干扰信息、扰乱人们对图像中有用信息的观测的孤立像素点或者像素块。而因为图像在传输、网络丢包或者计算处理本身过程对图像带来的退化影响是无法根据更换设备或者其他外部条件来解决这一问题的，在这种情况下利用图像处理、机器视觉以及数值分析等消除图像噪声的工作称为图像的去噪，目的就是得到原图像的估计值，尽可能的让这一估计接近原图像。最开始的去噪技术是在1964年NASA的喷气动力实验室在计算机上首次使用数字图像处理技术对航天探测器徘徊者7号传回的数千张月球照片进行例如灰度变换、去噪等技术处理，这是数字图像处理技术的第一次成功。而现如今图像处理技术已经遍布于生活的各个方向如科学研究、军事技术、工农业生产、医学、气象以及天文地理等 [1]。目前为止图像噪声去除大概分为传统的空域与频域滤波去噪方法、基于小波变换的图像去噪方法、基于偏微分方程的去噪方法、基于稀疏表示理论的图像去噪技术等。空域滤波是在原图像上直接进行数据运算，再对像素的灰度值进行技术处理 [2]。常见的空间域图像去噪算法有邻域平均法、中值滤波、低通滤波等 [3]。频域滤波去噪算法就是将原本的图像进行某种变换将其从空域映射到频域上根据图像斑点噪声的频率范围，进而通过滤波器实现去噪。小波变换其实是基于变换域滤波的去噪技术就是对图像进行某种变换，将图像从空间域转换到变换域，再对变换域中的变换系数进行处理，再进行反变换将图像从变换域转到空间域 [4]。偏微分方程近些年才兴起的一种图像处理方法，是依据图像的局部特征将对图像的处理转为对偏微分方程的求导问题对低层图像处理具有很好的效果。其方程具有各向异性的特点能够并保持边缘区域的边界特征。其中全变分去噪方法是一个能够较好地解决了抑制噪声与保持细节信息的矛盾，尽可能地保留了原来图像的细节和边缘信息的技术 [5]。基于过完备冗余字典的稀疏表示去噪算法已经成为目前图像去噪领域的主要方法，其主要思想是将原始的图像用训练完成的过完备冗余字典中的原子稀疏表示。这种新型算法相对于传统的变换有更好的适应性，能够根据新图像来选择更优的原子。但是当图像的噪声过大的时候，稀疏表示方法容易产生过拟合现象，从而使得到的图片有一定的模糊现象。伴随着科技的不断发展，字典学习的方式，也在不断的更新，越来越多的人加入图像去噪领域，使得算法更加的方便快捷。因此该方法被使用在各个领域。

本文主要是针对自然图像的去噪方法，以稀疏冗余表示理论为基础，围绕稀疏编码和字典训练对分析字典和学习字典进行研究，针对字典训练采用K-SVD算法和RK-SVD算法，研究了其原理及去噪效果。然后对RK-SVD的计算过程进行优化改进，并对图片进行加噪及加噪后基于三个算法的字典训练以及去噪处理和结果对比。

2. 基于K-SVD的图像去噪算法

K-SVD算法是在2006年由以色列理工学院的Michal Aharon、Michael Elad等人提出来的，这些数学家基于K-SVD算法构筑了一个矩阵也就是字典，通过这个字典将与含噪图像相似的向量进行稀疏编码 [6] [7]。

K-SVD算法的适用性很广，几乎可以和任何的追踪算法结合使用，根据给定的字典，K-SVD算法获得具有匹配追踪(MP)或者正交匹配追踪(OMP)的稀疏表示系数，然后假设系数是固定的情况下，K-SVD算法再一次对字典进行一列更新。这个时候再固定字典对稀疏表示系数进行第二次更新，系数发生变化。然后再固定系数，更新字典。重复此过程，直到最后的残差满足一定的条件，这时停止迭代。

在这里我们假设字典 $D\in R^{n\times k}$ 是一个过完备冗余字典，其中包括K列原子，信号 $Y\in R^n$ 可以表示为这些原子的稀疏线性组合，而 $X\in R^K$ 则是稀疏线性组合的稀疏表示系数。Y的表示为：

$Y=DX$ (1)

但是在通常情况下原子的线性组合不能够完全将原始信号表示出来，因此Y表示为：

$Y\approx DX,\text{s}\text{.t}\text{.}{\Vert Y-DX\Vert }_p\le \epsilon$ (2)

其中p范数可以看作2范数的拓展，但是p范数的范围是 $\left[1,+\infty \right)$。

$Y={\left\{y_i\right\}}_{i=1}^N$ 包含N个训练信号，相应的系数为X和为了信号集Y的稀疏表示来寻找适应性最好的字典。这就形成了一个优化问题：

$\underset{D,X}{\text{min}}\left\{{\Vert Y-DX\Vert }_F^2\right\}\text{s}\text{.t}\text{.}\forall i,{\Vert x_i\Vert }_0\le T_0$ (3)

其中 $T_0$ 是系数的非零项的上限即稀疏度，F范数是对于矩阵的运算的，与向量的2范数相似，也就是矩阵的每个元素的平方和的开方。

一旦完成了稀疏编码的任务，那么接下来的任务就是寻找更好的字典。这个过程每进行一次就会更新字典的一列。不断的更新稀疏系数X和字典D的所有列d直到更新到 $d_k$ 及其对应的位于第i行的系数表示为 $x_T^i$ 返回(3)，此时的惩罚项可以写为：

$\begin{array}{c}{\Vert Y-DX\Vert }_F^2=\Vert Y-{\displaystyle \underset{j=1}{\overset{k}{\sum }}{d}_j{x}_T^j}\Vert \\ ={\Vert \left(Y-{\displaystyle \underset{j\ne k}{\sum }{d}_j{x}_T^j}\right)-d_k{x}_T^k\Vert }_F^2\\ ={\Vert E_k-d_k{x}_T^k\Vert }_F^2\end{array}$ (4)

$E_k$ 代表的是误差矩阵，同时矩阵DX被分解为K个一阶矩阵的总和，在这些矩阵中一直到 $K-1$ 个向量是被确定的，第K个仍然是不确定的。在这种条件下使用SVD算法了来寻找 $d_k$ 和 $x_T^k$ 是不正确的。因为新的 $x_T^k$ 很有可能会被代替，因此在更新 $d_k$ 的时候不执行稀疏约束。

3. 基于RK-SVD的图像去噪算法及其改进

RK-SVD又叫做正则化K-SVD算法，是在K-SVD算法的基础上加入正则化因子，从而防止模型产生过拟合、缩小解空间和减小求出错误解的可能性等，通常情况下RK-SVD算法比K-SVD算法具有更好的去噪能力。在解决通常的数学物理方程的问题中，一般只研究适定问题。对于不适定问题一般通过正则化方法来解决 [8]。正则化方法就是用一组初始不适定问题相近的适定问题的解去逼近原问题的解 [9] [10]。稀疏表示正是经典的不适定问题。

根据K-SVD算法给出RK-SVD算法的目标函数模型：

$\underset{D,X}{\arg \min }{f}_{\mu }\left(D,X\right)={\Vert Y-DX\Vert }_F^2+\mu {\Vert X\Vert }_F^2$ (5)

其中 $\mu$ 是正则化参数且大于0，在K-SVD算法的更新原子部分，将待更新原子设为 $d_j$， ${\theta }_j$ 是待更新原子 $d_j$ 的信号索引，因此将RK-SVD的模型可以变为：

$\underset{d_j,x_{j,{\theta }_j}}{\arg }\min f_{\mu }\left(d_j,x_{j,{\theta }_j}\right)={\Vert Y_{{\theta }_j}-{\displaystyle \underset{i\ne j}{\sum }{d}_i{x}_{i,{\theta }_j}-d_j{x}_{j,{\theta }_j}}\Vert }_F^2+\mu {\Vert x_{j,{\theta }_j}\Vert }_F^2$ (6)

则这些信号的表示误差为：

$E=Y_{{\theta }_j}-{\displaystyle \underset{i\ne j}{\sum }{d}_i{x}_{i,{\theta }_j}}$ (7)

对误差项E进行SVD分解可以得到：

$E={\displaystyle \underset{i=1}{\overset{r}{\sum }}{\sigma }_i}{u}_i{v}_i^{\text{T}}$ (8)

在此处令 $d=d_j,x^{\text{T}}=x_{j,{\theta }_j}$ 那么上式的最优化模型就变成如下所示

$\underset{\Vert d\Vert =1,x^{\text{T}}}{\arg }\min f\left(d,x^{\text{T}}\right)={\Vert E-d{x}^{\text{T}}\Vert }_F^2+\mu {\Vert x^{\text{T}}\Vert }_F^2$ (9)

其中 $\Vert d\Vert =1$ 是因为字典原子为单位向量。在进行SVD分解的时候秩 $r\ge 1$ 是不相关的。那么上式的解为：

$d=u_1,x=\frac{1}{1+\mu }{\sigma }_i{v}_i$ (10)

与此同时上式的函数还可以表示为：

$\underset{\Vert d\Vert =1,x^{\text{T}}}{\arg }\min f\left(d,x^{\text{T}}\right)=1+\mu {\Vert x\Vert }^2-2x^{\text{T}}{E}^{\text{T}}d+{\Vert E\Vert }_F^2$ (11)

由K-SVD算法可以得到新原子d和原子的相关系数x可以通过误差项来表示即

$d={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\rho }_i}{u}_i,x={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\theta }_i}{v}_i$ (12)

且因为字典原子都是单位向量且用 $t=\Vert x\Vert$ 来表示所以有：

${\Vert d\Vert }^2={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\rho }_i^2}=1,{\Vert x\Vert }^2={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\theta }_i^2}$ (13)

$E^{\text{T}}d={\displaystyle \underset{i=1}{\overset{r}{\sum }}{\sigma }_i{v}_i{u}_i^{\text{T}}d}={\displaystyle \underset{i=1}{\overset{r}{\sum }}{\sigma }_i{\rho }_i{v}_i}$ (14)

因此拟最小化的函数变为：

$\underset{\Vert d\Vert =1,x^{\text{T}}}{\arg }\min f\left(d,x^{\text{T}}\right)=\left(1+\mu \right)t^2-2{\displaystyle \underset{i=1}{\overset{r}{\sum }}{\sigma }_i}{\rho }_i{\theta }_i+{\Vert E\Vert }_F^2$ (15)

由SVD性质可知 ${\sigma }_i$ 是个递减数列，再由柯西施瓦茨不等式可知以下：

${\displaystyle \underset{i=1}{\overset{r}{\sum }}{\sigma }_i}{\rho }_i{\theta }_i\le \left({\displaystyle \underset{i=1}{\overset{r}{\sum }}{\sigma }_i^2}{\rho }_i^2\right){\displaystyle \underset{i=1}{\overset{r}{\sum }}{\theta }_i^2}\le {\sigma }_1^2{t}^2$ (16)

当 ${\rho }_i=0,{\theta }_i=0$ 且在 $i>1$ 的情况下达到了平衡，因此目标函数可变为

$\underset{\Vert d\Vert =1,x^{\text{T}}}{\arg }\min f\left(d,x^{\text{T}}\right)=\left(1+\mu \right)t^2-2{\sigma }_{1}t+{\Vert E\Vert }_F^2$ (17)

显然在当

$t=\frac{{\sigma }_1}{1+\mu }$ (18)

时有最小值从而得到最优解。

若在经典RK-SVD模型中计算误差项的基础上加入偏置b即：

$E=Y_{{\theta }_j}-{\displaystyle \underset{i\ne j}{\sum }{d}_i{x}_{i,{\theta }_j}}+b$ (19)

那么在加入偏置b的基础上可获得改进的最优化模型：

$\underset{d_j,x_{j,{\theta }_j}}{\arg }\min f_{\mu }\left(d_j,x_{j,{\theta }_j}\right)={\Vert Y_{{\theta }_j}-{\displaystyle \underset{i\ne j}{\sum }{d}_i{x}_{i,{\theta }_j}+b-d_j{x}_{j,{\theta }_j}}\Vert }_F^2+\mu {\Vert x_{j,{\theta }_j}\Vert }_F^2$ (20)

4. 加噪实验及对比分析

在这个信息化的时代，图片往往是可以包含大量信息的传递方式，但是图像在传递的过程中往往会受到外来因素的干扰或者拍照设备的好坏从而产生噪声，这就导致了最后得到的图像包含大量噪声信息。本文进行的加噪实验主要为以下两种模型：

(1) 高斯噪声(Gaussian)

高斯噪声就是概率密度函数服从高斯分布的一种噪声 [11]。高斯分布，记为 $N\left(\mu ,{\sigma }^2\right)$，其中 $\mu$ 和 ${\sigma }^2$ 分别为期望和方差。其概率密度函数为：

$p\left(x\right)=\frac{1}{\sigma \sqrt{2\pi }}{\text{e}}^{\frac{-\left(x-\mu \right)}{2{\sigma }^2}}$ (21)

(2) 椒盐噪声(Salt-and-Pepper)

椒盐噪声又叫做脉冲噪声，椒盐噪声和高斯噪声很像，但椒盐噪声和高斯噪声的位置和噪点深度都不尽相同，是在图像中极为容易见到的噪声。椒盐噪声的影响形式是随机出现一些白点或者黑点从而改变图像的某些部位的像素值，比如说图像中黑色像素的部分出现白色像素或者白色像素的部分出现黑色像素亦两者皆有之。椒盐噪声的出现原因是图像传感器的某些零件的损坏或者是图像在传播的过程中受到突如其来的强烈的干扰产生的。

图1是原图及含噪声图片。图2是加入了高斯噪声(参数为(1.0,50))的噪声、K-SVD、RK-SVD和改进的RK-SVD四种图像的对比，可以很清楚的看到改进的RK-SVD对于细节的还原更为清晰。

(a) (b) (c)

Figure 1. Original and noisy image. (a) Original image; (b) image with Gaussian noise; (c) image with salt and pepper noise

图1. 原图及含噪声图片。(a) 无噪声原图；(b) 加入高斯噪声图片；(c) 加入椒盐噪声图片

(a) (b) (c) (d)

Figure 2. Comparison of Gaussian noise denoising. (a) Image with Gaussian noise; (b) denoising image with K-SVD; (c) denoising image with RK-SVD; (d) denoising image with imporved RK-SVD

图2. 高斯噪声去噪的对比。(a) 含高斯噪声图像；(b) K-SVD去噪结果；(c) RK-SVD去噪结果；(d) 改进的RK-SVD去噪结果

图3可以看到，在椒盐噪声背景下改进的RK-SVD的处理效果比RK-SVD的效果更为明显，在这里还是用图像再进行一次对比。

由于改进算法中加入了偏置参数，偏置的大小同样会对去噪效果产生不同的影响。首先尝试加入较大的偏置，令偏置为b = 0.1以高斯噪声为噪点来观测其对去噪效果的影响。可以清晰的从图中看到加了偏置之后的RK-SVD相比于初始的RK-SVD有更好的去噪效果。

(a) (b) (c) (d)

Figure 3. Comparison of salt and pepper noise denoising. (a) image with salt and peppernoise; (b) denoising image with K-SVD; (c) denoising image with RK-SVD (d) denoising image with imporved RK-SVD

图3. 椒盐噪声去噪的对比。(a) 含椒盐噪声图像；(b) K-SVD去噪结果；(c) RK-SVD去噪结果；(d) 改进的RK-SVD去噪结果

为了解决人们对图像的观测的好坏与否，本文分别使用信噪比(SNR)、结构相似性(SSIM)和峰值信噪比(PSNR)来评估算法的去噪能力。去噪图与原图的SNR、PSNR与SSIM的值越大说明去噪效果更优越。从表1~3的数据中可以看出一般情况下，并不是偏置越小去噪效果越好，但整体效果要优于经典RK-SVD算法。

Table 1. Comparison of SNR after image denoising

表1. 图像去噪后SNR数据对比

Table 2. Comparison of SSIM after image denoising

表2. 图像去噪后SSIM数据对比

Table 3. Comparison of PSNR after image denoising

表3. 图像去噪后PSNR数据对比

5. 结论

本文主要是描述和实现基于稀疏表示的K-SVD算法和RK-SVD算法对带有噪声的图像的去噪效果的研究。本文在经典RK-SVD算法的基础上修改了RK-SVD算法模型中计算误差项。实验数据表明，改进的RK-SVD算法相比经典RK-SVD算法在去噪效果方面得到了提升。

致谢

感谢国家自然科学基金项目(11772228)；天津市自然科学基金项目(18JCQNJC69700)；天津市高等学校科技发展基金计划项目(2020KJ115，JWK1611)对本文的支持。