图像降噪算法——低秩聚类：WNNM算法

同样是为了完善自己知识版图的完整性，我决定再补充下低秩聚类算法的相关算法，低秩聚类算法同样是一大类算法，这篇博客是挑选了其中最经典的一种算法WNNM算法进行展开学习，由于没有在这方面做过太多相关的工作，因此可能理解相对肤浅，还请读者见谅

1. 基本原理

在写这篇博客之前，我先学习了稀疏表达相关的知识，这里我从稀疏表达算法出发，引入低秩聚类算法的相关解释：

在稀疏表达相关算法中，将图像建模成$\mathbf{Y}=\mathbf{D}\mathbf{X}$的形式，其中$\mathbf{Y}$是有单个样本按列组成而成的样本矩阵，注意这里的样本并没有要求是相似的，$\mathbf{D}$是字典矩阵，矩阵中每一列为一个基向量或者子空间，$\mathbf{X}$则为系数矩阵，在系数表达中给定的限制条件是要求系数矩阵是稀疏的。我们通过一个过完备的字典和稀疏的系数矩阵就可以还原样本，而噪声不行，因此可以通过稀疏表达进行去噪。

而在低秩聚类相关算法中，是将图像建模成$\mathbf{Y}=\mathbf{X}-\mathbf{N}$，其中$\mathbf{Y}$同样是由带有噪声的相似样本组成而成的样本矩阵。$\mathbf{X}$和$\mathbf{N}$分别为对应的的无噪声的样本矩阵以及噪声。我们给出的限制条件是$\mathbf{X}$是低秩矩阵。由于相似样本组成的矩阵具备低秩性，噪声不具备低秩性，因此通过低秩聚类可以实现图像降噪的效果。

由此可见，从降噪的本质上来将，稀疏表达的稀疏和低秩聚类中的聚类是具有一定相关性的。

为什么相似样本具备低秩性呢？参考图像降噪方法综述中的说法，当我们拍摄一张大草原的图片时，草原是由草组成的，而草是相似的，如果图片上全是草，那么这张图片实际包含的信息是很少的，因此可以理解为草是草的复制品，这就是低秩性的一个直观理解。

那么接下来就开始具体将WNNM算法的实现，主要参考
非局部相似性去噪算法研究
Weighted Nuclear Norm Minimization with Application to Image Denoising

WNNM的全称是Weighted Nuclear Norm Minimization，中文翻译成加权核范数最小化方法，算法的流程如下图所示：

如果在图像上搜索相似patch的流程就不用赘述了，方法多种多样，重要的是，假定我们要降噪的图像块为${\mathbf{P}}_{\mathbf{i}}$，由该图像块以及图像上与其相似的图像块组成的矩阵为${\mathbf{Y}}_{\mathbf{i}}$，对应的降噪后的矩阵为${\mathbf{X}}_{\mathbf{i}}$，低秩矩阵最小化可以用来求矩阵的解，于是我们得到目标函数：$${\mathbf{X}}_i={\mathrm{argmin}}_{x_i}{\Vert {\mathbf{Y}}_i-{\mathbf{X}}_i\Vert }_F^2+\mathrm{rank}\left({\mathbf{X}}_i\right)$$但是，其中${\Vert \mathbf{X}\Vert }_F$是F范数，F范数的定义是矩阵$\mathbf{X}$各项元素的绝对值平方的总和，即$$\Vert \mathbf{X}{\Vert }_F\equiv \sqrt{\sum _{i=1}^m\sum _{j=1}^n{\left|x_{ij}\right|}^2}$$上式是一个非凸函数，求解过程将是一个NP问题，因此需要对该问题转为凸优化问题后再求解，为此，前辈提出了标准核范数最小化的求解方法，也就是NNM——本文要介绍的WNNM算法的前身，NNM的目标函数如下：$${\mathbf{X}}_i={\mathrm{argmin}}_{X_i}{\Vert {\mathbf{Y}}_i-{\mathbf{X}}_i\Vert }_F^2+\lambda {\Vert {\mathbf{X}}_i\Vert }_{\ast }$$式中，$\lambda$是一个正数，${\Vert {\mathbf{X}}_i\Vert }_{\ast }$是核范数，核范数的定义为$$\Vert \mathbf{X}{\Vert }_{\ast }=\mathrm{tr}\left(\sqrt{{\mathbf{X}}^T\mathbf{X}}\right)=\mathrm{tr}(\mathbf{\Sigma })$$

求解方法是对${\mathbf{Y}}_{\mathbf{i}}$进行奇异值分解为${\mathbf{Y}}_j=\mathbf{U}\mathbf{\Sigma }\mathbf{V}$，然后对奇异值进行软阈值收缩：$${\mathcal{S}}_{\lambda }(\mathbf{\Sigma }{)}_{ii}=\max \left({\mathbf{\Sigma }}_{ii}-\lambda ,0\right)$$其中，${\mathbf{\Sigma }}_{ii}$为奇异矩阵$\mathbf{\Sigma }$对角线元素，于是得到目标函数的解：$${\mathbf{X}}_i=\mathbf{U}{\mathcal{S}}_{\lambda }\left(\mathbf{\Sigma }\right)\mathbf{V}$$在NNM算法中，是使用同一个$\lambda$值对所有奇异值进行软阈值收缩，这样做没有考虑到图像的信息主要集中在数值较大的上这个特点，因此会导致图像细节过度平滑而变得模糊，为了解决这个问题，于是就诞生了WNNM算法，使用不同的$\lambda$值对奇异值进行软阈值收缩，数值大的奇异值对应数值小的$\lambda$。由此我们得到目标函数：$${\hat{\mathbf{X}}}_i={\mathrm{argmin}}_{X_i}\frac{1}{{\sigma }_n^2}{\Vert {\mathbf{Y}}_i-{\mathbf{X}}_i\Vert }_F^2+{\Vert {\mathbf{X}}_i\Vert }_{\mathbf{w},\ast }$$其中${\sigma }_n^2$为噪声方差，用于归一化F范数，而其中$\mathbf{w}=\left[w_1,\dots ,w_n\right]$中的每一项都为非负数，对应每一个奇异值，如下：$$w_i=c\sqrt{k}/\left({\sigma }_i\left(\mathbf{X}\right)+\epsilon \right)$$$其中，{\sigma }_i\left(\mathbf{X}\right)$为$\mathbf{X}$的第$i$奇异值，可以观察到，当奇异值越大时权重越小。$k$w为相似图像patch的数量，$\epsilon$为防止被零正常的小参数。但是这里有个问题是，${\sigma }_i\left(\mathbf{X}\right)$是未知的呀，我们可以假设在初始时刻，噪声能量是在各个特征上分布是均匀的，因此初始化${\sigma }_i\left(\mathbf{X}\right)$为：$${\sigma }_i\left(\mathbf{X}\right)=\sqrt{\max \left({\sigma }_i^2\left(\mathbf{Y}\right)-k{\sigma }_n^2,0\right)}$$最后同样我们对${\mathbf{Y}}_{\mathbf{i}}$进行奇异值分解为${\mathbf{Y}}_j=\mathbf{U}\mathbf{\Sigma }\mathbf{V}$，然后目标函数的解为：$${\mathbf{X}}_i=\mathbf{U}{\mathcal{S}}_{\mathbf{w}}\left(\mathbf{\Sigma }\right)\mathbf{V}$$

2. matlab代码

matlab代码我就直接贴上链接好了 csjunxu/WNNM_CVPR2014 ，这份matlab代码我也没有细读，仅仅跑了一下，感兴趣的同学可以多画时间研究研究。

3. 结论

1. 低秩聚类不仅仅可以用在图像降噪，在图像分割、分类等方面也有广泛的应用。
2. 论文中的图像效果如下：
   我测试的结果也差不多，相对BM3D其文理细节保留会更好一些，但是一些纹理密集的区域会出现一些artifact，至于好不好，就要看大家对图片质量的要求了，这篇文章写的比较浅显，有问题欢迎交流

此外，这里我写一个各种算法的总结目录图像降噪算法——图像降噪算法总结，对图像降噪算法感兴趣的同学欢迎参考