基于稀疏表达的图像恢复算法研究

摘 要

摘 要

图像去噪即从一张带有噪声的图像中去除其中所包含的附加噪声。本文主要研究基于稀疏表达的高斯噪声和椒盐噪声去噪模型与算法。由于高斯噪声和椒盐噪声特性的不同，我们分别对高斯噪声和椒盐噪声建立了模型。使得针对不同的噪声应用相应的模型处理可以得到更好的去噪效果。

首先，我们学习与研究基于稀疏表达的高斯噪声图像模型。该类算法和模型的基本思想是将原始图像表达为局部的基元线性组合，并约束线性组合系数的稀疏性，从而建立解决去噪问题的能量函数，在极小化过程中通过OMP和K-SVD算法优化该能量函数。在实现中，我们可以用离散余弦变换（DCT）构造其中的基元组，也可以自适应的学习该基元组。我们实现了该算法，并应用于高斯噪声图像的去噪问题。

另一方面，我们研究椒盐噪声的图像去噪问题。我们发现，应用经典的稀疏表达模型会在处理去除椒盐噪声图像中失效，因此我们提出一种新的基于稀疏性的椒盐噪声图像去噪模型。结合椒盐噪声的特性，我们用更为鲁棒的带权稀疏表达模型，在使用基元组时采用DCT基元组，并通过OMP方法优化该稀疏表达模型。通过实验表明，该方法相对于经典的稀疏表达模型能更好的去除椒盐噪声。

关 键 词：图像去噪；基元表示；OMP；K-SVD；稀疏编码

I

西安交通大学本科毕业设计（论文）

ABSTRACT

Image denoising is to remove the noises from a given observed noisy image. This paper mainly concentrates on how to remove Gaussian noises and pepper noises based on image sparse representation. Based on the characteristics of Gaussian noises and pepper noises, we learned and proposed the sparse representation based denoising model and algorithms to achieve image denoising.

Firstly, we learn and investigate the sparse representation based Gaussian noise removal. The main idea is to represent the image by the local sparse linear combination over a dictionary of basis, and then OMP and K-SVD methods are used to optimize the deduced energy function. In implementation, the dictionary of basic can be set as constant or learned adaptively from the noisy images. We implemented this model and applied it to Gaussian noise removal.

Secondly, we investigate the pepper noise removal based on image sparse representation. We find that, the traditional sparse representation model cannot handle the pepper noise removal problem perfectly. In this paper, we propose a novel weighted sparse representation model to remove the pepper noises, which uses the dictionary of DCT basis and optimize it by OMP algorithm. Experiments show that this proposed method can accurately remove pepper noises with much higher Peak Signal to Noises Ratio (PSNR).

KEY WORDS: Image denoising;Dictionary learing;OMP;K-SVD;Sparse coding

II

目录

目 录

1 绪论 .................................................................. 1 1.1 研究背景 .......................................................... 1 1.2 本文主要研究工作 .................................................. 2 2 基于稀疏线性表达的高斯噪声去噪模型 .................................... 4 2.1 模型介绍 .......................................................... 4 2.1.1 局部块上建立去噪模型 ........................................... 4 2.1.2 图像整体上建立去噪模型 ......................................... 5 2.2 模型优化求解 ...................................................... 6 2.2.1 采用DCT基元组优化模型 ......................................... 6 2.2.2 全局学习基元组优化模型 ......................................... 7 2.2.3 自适应学习基元组优化模型 ....................................... 7 2.3 迭代求解算法 ...................................................... 8 3 基于稀疏线性表达的椒盐噪声去噪模型 .................................... 2 3.1 模型的建立 ........................................................ 2 3.2 模型优化求解 ...................................................... 3 3.3 迭代求解算法 ...................................................... 5 4 实验 .................................................................. 6 4.1 高斯噪声去噪实验 .................................................. 7 4.2 椒盐噪声去噪实验 .................................................. 8 5 结论与展望 ........................................................... 10 参考文献 ............................................................... 11 附 录 ................................................................. 12 致 谢 ................................................................. 25

III

西安交通大学本科毕业设计（论文）

IV

1 绪论

1 绪论

1.1 研究背景

20世纪20年代，图像处理技术首次得到应用。上个世纪60年代中期，随着计算机科学的发展和计算机的普及，图像处理得到广泛的应用。60年代末期，图像处理技术不断完善，逐渐形成一个新兴的学科。图像在形成，传输和记录过程中，由于受多种原因的影响，图像质量会有所下降，比较典型的就是产生噪声，因此研究图像去噪问题具有较强的实用性和重要性。本文关注图像的去噪问题，即研究如何从观测到的低质量图像（例如噪声图像）恢复为高质量的原始图像。

我们这里研究的图像噪声模型，主要关注的是一种加性噪声，即在一张图片中加入一种噪声，我们假定有一个理想的图像为x，加进一个噪声v，处理后的图像y为：

y?x?v， （1-1）

我们要研究的就是希望能够设计一个好的算法可以从y中消除噪声，尽可能地恢复为原来的图像x。

本文主要研究两类噪声的去噪问题，即：①高斯噪声，所谓高斯噪声是指它的概率密度函数服从高斯分布（即正态分布）的一类噪声；②椒盐噪声，在该噪声影响下，图像像素点会变为2个极值灰度（例如0，255），而图像中的每个像素点以一定的概率受到该噪声的影响，因此它表现为图象某些点特别暗或特别亮，而其他象素点不受到影响，类似我们的胡椒粉和晶体盐的亮度的感觉，所以叫椒盐噪声。高斯噪声和椒盐噪声的模型如下：

（1）高斯噪声模型：

pz(z)?1e2???(z?u)22?2， （1-2）

这里均值?一般取为0，标准差为?。

（2）椒盐噪声模型：

?Pa,z?a?pz(z)??Pb,z?b?0,其他? ， （1-3）

b?255，这里a?b，一般取a?0，即像素点z以概率Pa受到噪声影响变为a,以概率Pb受到噪声影响而变为b。

过去对于图像去噪问题的研究有着众多不同的看法和观点[1]-[7]。例如统计估计、空间自适应滤波器、随机分析、偏微分方程、变换域的方法、形态分析、顺序统

1

西安交通大学本科毕业设计（论文）

计方法等，都是研究探讨这个问题的方向，并延其形成了许多典型的去噪方法，例如我们常见的高斯滤波去噪，均值滤波去噪，中值滤波去噪，边缘保持滤波去噪。其中高斯滤波和均值滤波是线性滤波，即输出像素是输入像素邻域像素的线性组合；而中值滤波和边缘保持滤波均为非线性滤波。

近年来基于稀疏和冗余表达的图像信号去噪方法引起了人们的关注。在本文中我们同样采用这种思路，利用基于基元组的稀疏和冗余表达研究图像噪声模型。之所以用到冗余表达是因为我们希望在处理图像去噪问题过程中能保持转换不变性，与此同时我们引入匹配追踪技术[8]可以很方便地优化问题求解过程中的稀疏表达系数[9]-[12]。

在研究学习基于稀疏表达的图像去噪模型时，我们的基本思想是首先将图像分解为图像块的集合，对于每一个小的图像局部块，将其从上而下，从左至右依次排列成一个列向量，将图像块对应向量x用基元组D的线性组合进行表达：

x?D? （1-4）

并约束线性表达系数?的稀疏性。

基于该思想建立起来的经典的稀疏表达模型：

X??argmin??xl?yl2?xl?D?l2???lXl?220 ?， （1-5）

该模型中X?为欲求的去噪图像，xl和yl分别表示原始图像X和噪声图像Y的第l个局部块，D表示基元组，?表示稀疏表达系数，?和?分别为系数。此模型是通过定义关于X的后验概率分布并进行优化而引出的能量模型。由于模型中第一个和第二个惩罚项中重构误差使用l2范数测度，该范数能够很好的建模高斯噪声，因此利用这个模型能够很好地去除高斯噪声。

1.2 本文主要研究工作

（1）针对高斯噪声，研究和学习经典的基于基元组的稀疏线性表达去噪模型，并实现它的数值解法。

在建立好模型后，便需要对这个模型的数值求解进行算法研究，使之具有实用性。对于模型的数值求解的难点，关键是基元组D和稀疏表达系数?处理。从后文中我们可以看到使用OMP算法可以在每个局部块上求解出稀疏表达系数?。对于基元组D，离散余弦变换（DCT）是一个相当不错的选择，还可以考虑通过使用简单和高效率的K-SVD算法[6]-[7]自适应地学习得到基元组D。在训练学习时，我们考虑两个方案：1）从噪声图像本身中训练基元组，或2）从一组高质量图片中的图像块中训练。我们实现上述模型的数值解法，并应用于自然图像的高斯噪声去噪问题。

（2）研究如何改进经典去噪模型使得模型可以更有效地去除椒盐噪声。 由于椒盐噪声的特性，使之与高斯噪声差别很大，因此我们不能够再用先前的基于稀疏表达的经典去噪模型对椒盐噪声去噪。从实验中我们可以看出，采用经典模型

2

1 绪论

会使得到的结果非常不理想。通过分析，考虑到图像像素点或者完全没有受到噪声影响或者受到影响很大使得其完全变成过亮点或者过暗点，应用l2范数测度，将使得学习到的基元表达系数受到椒盐噪声的严重影响，影响去噪精度。因此我们在研究改进工作时，考虑引进对图像像素点的噪声可能性的权重函数，并建立带权的稀疏表达模型，减少噪声点对稀疏表达模型的影响。

本文的内容结构如下：

第2章——介绍如何建立经典的基于稀疏表达的图像去噪模型，并实现该模型迭代数值求解算法，包括如何使用OMP算法求解稀疏表达系数，及如何使用K-SVD算法进行基元组更新；

第3章——主要讨论如何对经典的稀疏表达去噪模型进行改进，使之针对椒盐噪声的特性可以达到更好的去噪效果。我们提出解椒盐噪声的带权稀疏表达模型，并提出其迭代优化策略。

第4章——在这章里我们将展示一些实验结果以表明我们建立的模型及算法的有效性，在这一章节中我们将看到利用建立起的经典模型对高斯噪声去噪有着相当不错的效果，并且改进后的模型在处理椒盐噪声去噪时比经典模型有更好的表现。

3

西安交通大学本科毕业设计（论文）

2 基于稀疏线性表达的高斯噪声去噪模型

本章我们主要研究基于稀疏线性表达的高斯噪声去噪模型。高斯噪声是指它的概率密度服从高斯分布（即正态分布）的一类噪声。高斯噪声的形式为：

?1pz(z)?e2??(z?u)22?2， （2-1）

这里均值?一般取为0，标准差为?。

我们现在学习与研究基于稀疏表达的高斯噪声图像模型及其数值求解算法。该类算法和模型的基本思想是：首先将原始图像划分为一个个小的图像块，然后将原始图像表达为局部的基元线性组合，并约束这个线性组合系数的稀疏性，从而建立解决去噪问题的能量函数，在极小化过程中将通过OMP和K-SVD算法优化该能量函数。

本章的主要内容有两个方面，一是沿着基于基元组的稀疏线性表达的思路，介绍如何建立一个高斯图像去噪模型，使得这个模型针对高斯噪声有着良好的去噪效果；二是在模型建立的基础上，我们需要学习与研究此类模型的算法求解过程，主要采用正交匹配追踪（OMP）和K-SVD的方法。

2.1 模型介绍

我们的目的是要建立一个基于稀疏线性表达的高斯噪声去噪模型，为方便问题分析，我们先从小的图像块上着手。再将其推广到较大的图像上。

2.1.1 局部块上建立去噪模型

首先我们考虑从原图X中取出的一个大小为n?n像素的图像块，将块中的像素点按照从上到下，从左到右的原则排成一个列向量，令其作为列向量x?Rn。下来我们来构建一个稀疏表达模型，先定义一个冗余的基元组D?Rn?k（k?n时，冗余）。我们假定这个基元组是已知确定的。此时，通过这个基元组我们可以用下面的稀疏表达模型来表示这个图像块x。如下：

???argmin?0 s.t. D??x (2-2)

?上式中使用l0范数对线性组合系数?的稀疏性进行约束。符号?0表示?的非零项个数。从这个模型中我们可以看到每个图像块都可以表示成冗余基元组D的一个线性组合。

对稀疏表达系数??的稀疏强度我们需要作出定义，令??0?L??n，这表明用稀疏线性组合来表达图像块x最多只使用了基元组D中的l个基元。此外，对上述模型我

4

2 基于稀疏线性表达的高斯噪声去噪模型 们采用D??x2??来表示重构误差会更精确。

现在我们考虑图像块x的一个噪声图像y，加入了一个零均值的高斯噪声，标准偏差为?。要去除图像块y中的噪声，需要对y做MAP估计，由于是高斯噪声，重构误差我们采用l2范数对其测度，于是问题变为

argmin?0 s.t. D??y2?T （2-3）

?2T由?，?确定。上述优化过程还可以改为

???argminD??y2???0 （2-4）

?2使约束项变为惩罚项，适当选择?，这两个问题是等价的。于是去噪图像x?就可以由x??D??给出。这样我们就得到了局部块上基于稀疏线性表达的高斯去噪模型。

2.1.2 图像整体上建立去噪模型

这一节我们将推广局部块上的高斯去噪模型，使之适用于整幅图像上。 假如我们要处理的未知图像X大小为N?N(N??n)，仍然可以从图像X中取出图像块。我们可以做如下处理：假定要取出的局部图像块大小为n?n，将一个大小为n?n的窗口放在图像X中按照从上至下，从左至右滑动，滑动距离视需要而定。这样处理后我们便得到一系列的局部块?xl?，这样做块边界可能会出现重叠，不过我们可以在重叠部分做平均得到最后结果。

接下来我们推广上述局部块上的高斯去噪模型，基元组D?Rn?k已知，对图像X做MAP估计（2-4）变为

??l??,X??argmin??l,XX?Y2??D??RlX2l22????l0 （2-5）

lRl是一个n?N基元组，xl?RlX。

上式也可表述为

??l?,?xl??????argmin???xl?yl?l,xll?????x??b??? ?ll0? （2-6）2i?2?2ili2在（2-5）中，第一项是整体X对数似然，要求之间的处理过的含噪图像Y和它的已去噪（未知）图像X相接近。作为约束，此惩罚项X?Y222?（C?）,这反映了?和?之间的关系。第二项和第三项说明每个大小为n?n的局部块xl?RlX在有限误差内都有一个稀疏表达。

5

西安交通大学本科毕业设计（论文）

2.2 模型优化求解

在建立上述模型过程中，我们一直都假设基元组D是已知的。对于基元组D，采用离散余弦变换（DCT）确实是一个相当不错的选择。当然我们还可以考虑通过使用简单和高效率的K-SVD算法自适应地学习得到基元组D。在训练学习时，我们考虑两个方案：1）从噪声图像本身中学习基元组；2）从一组高质量图片中的图像块中学习。如果使用DCT基元组，模型的优化求解大致分为两个部分，分别为求稀疏表达系数??l???和去噪图像?xl?；如果自适应地学习基元组，那么问题迭代求解过程中还应包含基元组的更新。

2.2.1 采用DCT基元组优化模型

假定基元组D已知，（2-6）模型的优化求解分为两个部分，分别要求每个局部块上的稀疏表达系数??l?和整体去噪图像?xl?。我们从初始化X?Y开始，寻找最优值

????l??。

问题（1）

??l?

?2???argmin??xl???libi???l?ll?i2??? （2-7） 0???在每一个图像块上，采用正交匹配追踪（OMP）对稀疏表达系数求解。使用标准正交匹

2配追踪，一次加一个基元，当误差xl???libi小于T时停止。因此，这个阶段又称稀

i2疏编码阶段，随着滑动的窗口在每个n?n块上同时运算。

得到了所有的稀疏表达系数??l?后，我们现在可以固定它们的值然后开始求解

??xl??。于是有

问题（2）

X??argmin?X?Y2??D?l?RlX2 （2-8）

Xl22对这个问题数值求解，我们可以建立能量函数E(X)，极小化E(X)即其中，

?E(X)?2??X?Y2??D?l?RlX?X?Xl=2?(X?Y)??2(?Rl)(D?l?RlX)

l?E(X)?0。 ?X22

6

2 基于稀疏线性表达的高斯噪声去噪模型 =2?X?2?Y??2RlTD?l?2?RlTRlX

ll=2(?I??RlTRl)X?2(?Y??RlTD?l)

ll因此，令2(?I??RlTRl)X?2(?Y??RlTD?l)=0，则

ll(?I??RlTRl)X?(?Y??RlTD?l)

ll即得

（2-9） X?(?I??RlTRl)?1(?Y??RlTD?l)

ll（2-9）的计算可以在每一个像素点上进行，按照前面描述的滑动窗口稀疏编码的步骤，但需要在边界处做平均处理。当我们得到X后，我们可以重复迭代，在已经去噪图像上的图像块上着手继续稀疏编码阶段，等等。这个过程即是我们通过稀疏表达来迭代去除噪声[13]-[15]。

2.2.2 全局学习基元组优化模型

从一张高质量样例图像中取出一组图像块Z??zl?l?1，每个图像块大小为n?n，

M我们搜寻基元组D通过最小化

?(D,??Mll?1?（2-10） )??[??l0?D?l?zl2]

l?1M2我们试图寻找Z中每个图像块的稀疏表达，并获得一个较小的表达误差。 首先我们要将D和?（2-10）即为一组稀?l?l?1分开计算，初始化D为DCT基元组，

M疏编码运算，类似（2-7）。因此，可以继续使用OMP获得近似最优的稀疏表达系数??l?l?1。

M然后再固定稀疏表达系数??l?l?1，使用K–SVD算法每次将基元组每列更新一次。这种

M更新是最优的，使得满足SVD可以在剩余基元组上运算，只在使用这一列的图像块上计算。经过以上处理，?(D,??l?l?1)的值在每个基元组基元的每次更新都是下降的，并

M随着更新，稀疏表达系数??l?l?1也随着优化[6]-[7]。

M2.2.3 自适应学习基元组优化模型

从含噪的图像中选取大小为n?n的图像块Z??yl?l?1，其M?(N?n?1)。回

到（2-6），我们可以将D看做未知的，并定义我们的模型为

M D?,?l,X??argmin?X?YD,?l,X???2??D?l?RlX2????l2ll20 （2-11）

根据先前构建的算法，我们可以初始化基元组D和整体去噪图像X，和先前的处

理一样设D为DCT基元组，X?Y。接下来使用OMP算法展开稀疏编码阶段计算稀疏

表达系数?l。得出稀疏表达系数?l后使用一系列K-SVD运算即可以对基元组D进行更新。

7

??西安交通大学本科毕业设计（论文）

输出图像应用（2-9）式可以得到。但是，对输出图像的迭代更新改变了噪音水平?，

我们在稀疏表达系数迭代和基元组更新时使用相同的?值。

2.3 迭代求解算法

综合上述讨论，下面介绍如何采用稀疏表达进行图像去噪的具体算法流程。算法如下： 任务：对加入了高斯噪声的含噪图像Y进行去噪。

算法参数：n-图像块大小，k-基元组大小，J-迭代训练次数，?-拉格朗日算子，C-噪声强度。

??22min??X?Y2??D?l?RlX2????l0?， D,?l,Xll??初始化：令X?Y，D=超完备DCT基元组。 迭代J次：

①稀疏编码阶段：在每个图像块RlX上，使用OMP算法计算稀疏表达系数?l： min?l0 s.t. D?l?RlX?l22?(C?)2.

②基元组更新阶段：对基元组D中的每一列j=1,2，??，k， i找出使用这列的图像块，?j??l?l(j)?0?. ii对指数l??j，计算它的表达误差 elj?RlXl??bm?l(m).

m?j iii基元组Ej的列向量由eljT??l??j组成.

~ iv应用SVD分解Ej?U?V.选择更新后的基元bj为U的第一列. 通过乘?(1,1)更新稀疏表达系数??l(j)?l??j为V的系数.

3．令：

X?(?I??RlTRl)?1(?Y??RlTD?l)

ll

8

西安交通大学本科毕业设计（论文）

3 基于稀疏线性表达的椒盐噪声去噪模型

本章要讨论如何应用稀疏表达去除椒盐噪声，椒盐噪声的形式如下：

?Pa,z?a?pz(z)??Pb,z?b?0,其他?， （3-1）

椒盐噪声的特点是：这种噪声的噪声值不是连续变化，图像像素点在该噪声影响下以一定的概率变为极值灰度值，例如0或者255,，因此它表现为图像某些点特别暗或特别亮，类似我们的胡椒粉和晶体盐的亮度的感觉，所以叫椒盐噪声。

如果采用上一章建立的经典的稀疏表达模型对椒盐噪声做去噪处理，我们会发现结果会非常不理想，即经典模型对椒盐噪声失效。本章将研究如何对经典模型进行改进，使得新的模型对椒盐噪声有较好的去噪效果。改进的基本想法是：在经典稀疏表达模型中，通过引入能够反映像素点噪声可能性的权重函数，使得经典稀疏表达模型中主要使用未受噪声影响的像素进行学习稀疏表达系数，从而消除椒盐噪声点对系数学习的影响。

本章的第一节将介绍如何建立新的带权稀疏表达模型；第二节我们主要关注分析该模型如何数值求解；在第三节将解决算法求解过程中初始化问题并给出具体的迭代算法流程。

3.1 模型的建立

首先我们需要分析经典稀疏表达模型对椒盐噪声去噪失效的原因：在经典稀疏表

2达模型中，重建误差xl???lbi用l2范数测度，该范数假定了它的稀疏表达误差是高

ii2斯的，所以蕴含的是高斯噪声模型，因此能够很好的建模高斯噪声。但是针对椒盐噪声图像有如下特点：图像像素点或者完全没有受到噪声影响或者受到影响完全变成过亮点或者过暗点。如果应用l2范数测度描述时会显得非常不鲁棒，使得学习到的基元表达系数受到椒盐噪声的严重影响，影响去噪精度。因此我们需要设计一种更为鲁棒的重构误差，我们尝试采用如下改进：引入对图像像素点的噪声可能性的权重函数，并建立带权的稀疏表达模型，减少噪声点对稀疏表达模型的影响。

通过上面的分析我们可以重新建立起一个新的模型，我们将新的模型分为两个子问题：①在给定基元组的情况下，如何学习每个图像块上的稀疏线性组合系数；②给定图像块的稀疏线性组合形式，如何通过优化重建去噪图像。整个模型优化形式如下： （1）给定?xl,bi?，这里xl初始为原来的噪声图像，bi假设已知，设为DCT基元组

2

3基于稀疏线性表达的椒盐噪声去噪模型 ??l??2??i?argmin??wl(xl???lbi)???l?ll?i2??? （3-2） 0???2（2）给定??l,bi?。

?2??xl?argmin???wl(xl?yl)2?(1?wl)(xl???libi)xll?i?xl?yl??（3-3） ?

2??其中的wl为一个反映像素点为噪声点可能性的函数。其定义如下：

) （3-4）

?2我们采用中值滤波去噪方法结果初始化xl，并不断迭代更新xl。wl越大反映对应像素点是噪声点的可能性越小；反之，wl越小反映对应像素点是噪声点的可能性越大。

新的模型中问题（1）主要是对稀疏表达系数进行学习，相较于经典稀疏表达模型我们加入了反映像素噪声可能性的权重向量wl，之所以做这种处理，是因为wl如果很

wl?f(xl?yl)?exp(?小，即像素点是噪声点的可能性越大，对应的像素点在稀疏表达模型中起到的作用越小；而如果wl很大，即象素点更可能没有受到噪声的影响，因此其对应像素点在稀疏表达模型中的作用更大。总而言之，就是我们尽可能只使用图像中那些受噪声影响较小的点学习稀疏表达系数。这样做便可以减少噪声点对稀疏表达系数学习的影响。

新的模型中的问题（2）在给出稀疏线性组合形式下，通过优化重建去噪图像。我们可以看出式（3-3）中第一个惩罚项和第二个惩罚项相互竞争。如果是噪声点可能性越大，则wl越小，1?wl越大，式（3-3）在极小化过程中第二个惩罚项作用更大，对此项做极小化处理意味着要求xl与我们学习得到的基元组稀疏表达形式相像。反之，如果是噪声点的可能性越小，则wl越大，1?wl就越小，式（3-3）在极小化过程中第一个惩罚项作用更大，对此项做极小化处理意味着要求xl与原来的图像yl相像。

3.2 模型优化求解

模型的优化求解分为两个部分，分别为求稀疏表达系数??l?和去噪图像?xl?。首

??先我们先对问题进行简化，假定基元组D已知，设为DCT基元组。

对问题（1）

2???argmin??wl(xl???libi)???l?ll?i2???l????， （3-5） 0?????， （3-6） 0???与经典模型的区别在于在第一个惩罚项中加入了权重向量wl，将上式写为

??l??2???argmin??(wlxl)???li(wlbi)???l?ll?i2?问题的求解同经典稀疏表达模型类似，我们仍然采用正交匹配追踪（OMP）对稀疏

3

西安交通大学本科毕业设计（论文）

表达系数求解。

对问题（2），对能量函数E(x)做极小化处理，令

?2?E????wl(xl?yl)?(1?wl)(xl???libi)l?i?2?E(x)?0， ?x(p)?????

令??libi?tl，则

iE???wl(xl?yl)?(1?wl)(xl?tl)l?22?

22????E(x)[?wx?y?(1?w)]x?t=??p'p'p'p'p'p'?

?x(p)?x(p)?p'?N(p)?= = =

p'?N(p)?[2?w(p)(xp'(p)?yp'(p))?2(1?w(p))(xp'(p)?tp'(p))]

p'p'?N(p)?[2?w(p)(x(p)?y(p))?2(1?w(p))(x(p)?t(p))]

p'p'?N(p)?[2?w(p)x(p)?2?w(p)y(p)?2(1?w(p))x(p)?2(1?w(p))t(p)]

?E(x)?0??2?w(p)x(p)?2?w(p)y(p)?2(1?w(p))x(p)?2(1?w(p))tp'(p)?0 ?x(p)p'?N(p)??p'?N(p)?(?w(p)?1?w(p))x(p)??[?w(p)y(p)?(1?w(p))tp'?N(p)p'?N(p)p'(p)]

??w(p)y(p)?p'?N(p)x(p)?

p'?N(p)?(1?w(p))tp'(p) （3-7）

?(?w(p)?1?w(p))??xpyp wp · p w(p) (c)权重W

? · p x(p) (a)图像X

y(p) · p (b)含噪图像Y

图3-1：图像X、Y及权重W示意图

y(p)图1直观展示了上述推导过程中的某些量,x(p)表示图像X中点p的灰度值，

表示图像Y中点p的灰度值，w(p)表示点p权重值；xp表示以点p为中心的图像块像素点向量表示，yp，wp同理；xp'(p)表示以点p'为中心的图像块中点p的灰度值，

yp'(p)，wp'(p)，tp'(p)同理；N(p)=xp。

4

3基于稀疏线性表达的椒盐噪声去噪模型

3.3 迭代求解算法

基于上述讨论，我们下面将给出迭代求解实现椒盐噪声去噪的具体算法步骤。步骤如下：

任务：对加入了椒盐噪声的含噪图像Y进行去噪。

算法参数：n-图像块大小，k-基元组大小，J-迭代训练次数，?-拉格朗日算子，C-噪声强度。

2???argmin??wl(xl???libi)???l?l?i2??l?①给定?xl,bi?，????； 0???2?2??②给定??l,bi?，xl?argmin???wl(xl?yl)2?(1?wl)(xl???libi)xll?i?xl?yl??? 2??初始化：用中值滤波对噪声图像Y做去噪处理得到初始去噪图像X，wl采用高斯函数wl?f(xl?yl)?exp(?迭代J次：

i.稀疏编码阶段：在每个图像块上，使用OMP算法计算稀疏表达系数?l：

2?2)，D=超完备DCT基元组。

min?l0 s.t. wl(xl???libi)?(C?)2.

?li2 ii.去噪图像更新阶段：

x(p)?p'?N(p)??w(p)y(p)?p'?N(p)p'?N(p)?(1?w(p))tp'(p)

?(?w(p)?1?w(p))xl?yl)

iii.权重系数更新阶段：

wl?f(xl?yl)?exp(??2 5

西安交通大学本科毕业设计（论文）

4 实验

实验中，我们将在标准测试图像上实验高斯噪声和椒盐噪声去噪算法。第一部分我们将展示对两个样例图片lena和barbara加上高斯噪声，然后分别使用基于DCT基元组、全局基元组和自适应基元组的经典稀疏表达模型对图片去噪；在第二部分中我们对boat和lena两个样例图片加入椒盐噪声，先分别使用基于DCT基元组的经典稀疏表达模型去噪，然后再使用基于DCT基元组的改进模型对其进行去噪处理，这样做可以方便地比较两种去噪模型对椒盐噪声的实际去噪效果。

实验过程中我们使用标准的数据测试：所有要处理的图片大小为512?512，DCT基元组大小为64?256，用来处理图像块的大小为8?8像素，高斯噪声模型中我们设

??25，??30/?，椒盐噪声模型中噪声强度统一为P=0.05。

（a）加入高斯噪声\图 (b)采用DCT基元组去噪结果

(c)全局基元组去噪结果 (d)自适应基元组去噪结果 图2：对lena图像(高斯噪声)采用DCT、全局基元组及自适应基元组去噪结果

6

4实验

4.1 高斯噪声去噪实验

我们对\和\两个样例图片加上高斯噪声，??25，然后分别使用基于DCT基元组，全局基元组和自适应基元组的经典稀疏表达模型对图片去噪.

(a)加入高斯噪声\图 (b)采用DCT基元组去噪结果

(c)全局基元组去噪结果 (d)自适应基元组去噪结果

图3：对“barbara”图像加入高斯噪声并分别采用DCT、全局基元组及自适应基元组去噪结果

表4-1：含高斯噪声图像及使用各基元组去噪结果PSNR值比较

PSNR(dB) 噪声图像 DCT基元组去噪 全局基元组去噪 自适应基元组去噪

lena 28.7912 34.9218 35.0290 35.1465

barbara 28.37863 33.0463 32.7629 33.6665

7

西安交通大学本科毕业设计（论文）

从表4-1中我们可以看出，对“lena”和“barbara”两张样例图片加入??25的高斯噪声，使用基于稀疏线性表达的高斯噪声去噪模型分别采用DCT基元组，全局基元组和自适应基元组对图像做去噪处理，均可以达到较满意的去噪效果。

4.2 椒盐噪声去噪实验

我们对“boat”和“lena”两个样例图片加入椒盐噪声，先分别使用DCT基元组的经典稀疏表达模型去噪，然后再使用DCT基元组的改进模型对其进行去噪处理。

(a)加入椒盐噪声“boat”图 (b)高斯噪声稀疏表达模型去噪结果

(c)我们的去噪结果

图4：对“boat”图像加入椒盐噪声并分别采用DCT基元组的经典去噪模型和改进模型去噪结果

8

4实验

(a)加入椒盐噪声的“lena”图 (b)高斯噪声稀疏表达模型去噪结果

(c)我们的去噪结果

图5：对“lena”图像加入椒盐噪声并分别基于DCT基元组采用经典去噪模型和改进模型去噪结果

表4-2：含椒盐噪声图像及两种模型去噪结果PSNR值比较

PSNR(dB) 加入椒盐噪声图像 经典高斯去噪模型 改进的去噪模型

boat 40.0886 33.0430 43.7256

lena 40.0765 34.2431 44.1064

表4-2中所得的数据表明，对加入椒盐噪声的两张样例“boat”和“lena”分别使用基于DCT基元组的经典模型和改进模型对其去噪处理，经典模型得出的结果仍留有不少噪声点，去噪效果差强人意，而改进的去噪模型去噪效果较为令人满意，明显好于原经典模型。这说明我们的改进是非常有效的。

9

西安交通大学本科毕业设计（论文）

5 结论与展望

本文我们系统地研究和学习了基于基元组的稀疏线性表达的方法及其在图像去噪中的应用。针对高斯噪声和椒盐噪声的特性，分别学习和建立了适用于去除高斯噪声的经典的去噪模型和适用于去除椒盐噪声的改进的模型。改进过程中，引进了对图像像素点的噪声可能性的权重函数，并建立带权的稀疏表达模型，减少噪声点对稀疏表达模型的影响。

实现算法方面，我们在稀疏编码阶段常采用正交匹配追踪（OMP）方法，应用K-SVD算法对基元组D迭代更新。实验表明，超完备DCT基元组，从高质量图像中的一组图像块学习得到的基元组，以及对噪声图像本身的图像块学习出的自适应基元组，都有非常好的去噪表现。在高斯去噪模型对椒盐噪声失效时，使用改进的带权稀疏表达模型能得到理想的效果。

进一步的工作包括以下几个方面：

（1）在处理椒盐噪声的带权的稀疏表达模型数值求解过程中，我们可以加入基元组D学习阶段，如高斯去噪模型求解时学习基元组那样，希望获得更好的效果；

（2）更多图像和不同噪声水平下的测试比较，尽量得出客观有效的比较结果； （3）进一步学习与研究图像去噪与稀疏表达的相关内容，寻求更合理的去噪模型及更优的优化方法。

10

参考文献

参考文献

[1] K Engan, SO Aase and JH Hakon-Husoy. Method of optimal directions for frame design[C]. IEEE Int. Conf. Acoustics, Speech, and SignalProcessing, 1999.

[2] K Kreutz-Delgado and BD Rao. Focuss-based dictionary learning algorithms[J]. Electrical&Computer Engineering. 2002, 4119: 459-473.

[3] K Kreutz-Delgado, JF Murray, BD Rao et al. Dictionary learning algorithms for sparse representation[J]. Neur. Comput, 2003, 1(15): 349–396.

[4] MS Lewicki and TJ Sejnowski. Learning overcomplete representations[J]. Neur.Comput, 2000, 1(12): 337–365.

[5] L Lesage, R Gribonval, F Bimbot et al. Learning unions of orthonormal bases with thresholded singular value decomposition[C]. IEEE Intl Conf. Acoustics, Speech, and Signal Processing, 2005, 15, pages:349-396.

[6] M Aharon, M Elad and AM Bruckstein. The K-SVD: An algorithm for designing of overcomplete dictionaries for sparse representation[J]. IEEE Trans. Signal Process, 2006, 54(11): 4311-4322.

[7] M Aharon, M Elad and AM Bruckstein. On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them[C]. Special Issue devoted to the Haifa 2005 conference on matrix theory. 2006.

[8] YC Pati, R Rezaiifar and PS Krishnaprasad. Orthogonal matching pursuit:Recursive function approximation with applications to wavelet decomposition[C].Proceedings of the 27th Annual Asilomar . Conference on Signals, Systems, and Computers, 1993.

[9] J Portilla, V Strela and MJ Wainwright et al. Image denoising using scale mixtures of gaussians in thewavelet doma[J]. IEEE Trans. Image Process. 2003, 1(12): 1338–135.

[10] JL Starck, EJ Candes and DL Donoho. The curvelet transform for image denoising[J]. IEEE Trans. Image Process.2002,1(11): 670–684.

[11] R Eslami and H Radha. Translation-invariant contourlet transform and its application to image denoising[J]. IEEE Trans. Image Process. 2006, 1(15): 3362–3374.

[12] B Matalon, M Elad and M Zibulevsky.Improved denoising of images using modeling of the redundant contourlet transform[C]. The SPIE Conf. Wavelets, 2005.

[13] OG Guleryuz. Weighted overcomplete denoising[C]. The Asilomar Conf. Signals and Systems, Pacific Grove, CA, 2003.

[14] OG Guleryuz. Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising: PartI—Theory[J]. IEEE Trans. Image Process. 2005, 1(15):539–553.

[15] OG Guleryuz. Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising: PartII—Adaptive algorithms[J]. IEEE Trans. Image Process. 2005, 1(15):554–571.

11

西安交通大学本科毕业设计（论文）

附 录

外国文献翻译：

Image Denoising Via Sparse and Redundant Representations Over

Learned Dictionaries

Michael Elad and Michal Aharon

Abstract—We address the image denoising problem, where zero-mean white and homogeneous Gaussian additive noise is to be removed from a given image. The approach taken is based on sparse and redundant representations over trained dictionaries.Using the K-SVD algorithm, we obtain a dictionary that describes the image content effectively. Two training options are considered: using the corrupted image itself, or training on a corpus of high-quality image database. Since the K-SVD is limited in handling small image patches, we extend its deployment to arbitrary image sizes by defining a global image prior that forces sparsity over patches in every location in the image.We show how such Bayesian treatment leads to a simple and effective denoising algorithm. This leads to a state-of-the-art denoising performance,equivalent and sometimes surpassing recently published leading alternative denoising methods.

Index Terms—Bayesian reconstruction, dictionary learning, discrete cosine transform (DCT), image denoising, K-SVD, matching pursuit, maximum a posteriori (MAP) estimation, redundancy,sparse representations.

I.INTRODUCTION

In this paper, we address the classic image denoising problem: An ideal image is measured in the presence of an additive zero-mean white and homogeneous Gaussian noise, v, with standard deviation . The measured image y is, thus

y?x?v (1) We desire to design an algorithm that can remove the noise fromy, getting as close as possible to the original image, x.The image denoising problem is important, not only because of the evident applications it serves. Being the simplest possible inverse problem, it provides a convenient platform over which image processing ideas and techniques can be assessed. Indeed,numerous contributions in the past 50 years or so addressed this problem from many and diverse points of view. Statistical estimators of all sorts, spatial adaptive filters, stochastic analysis,partial differential equations, transform-domain methods,splines and other approximation theory methods, morphological analysis, order statistics, and more, are some of the many directions explored in studying this problem. In this paper, we have no intention to provide a survey of this vast activity. Instead,we intend to concentrate on one specific approach towards the，image denoising problem that we find to be highly effective and promising: the use of sparse and redundant representations overtrained dictionaries.

Using redundant representations and sparsity as driving forces for denoising of signals has drawn a lot of research attention in the past decade or so. At first, sparsity of the unitary wavelet coefficients was considered, leading to the celebrated shrinkage algorithm [1]–[9]. One reason to turn to redundant representations was the desire to have the shift invariance

12

附录

property [10]. Also, with the growing realization that regular separable 1-D wavelets are inappropriate for handling images,several new tailored multiscale and directional redundant transforms were introduced, including the curvelet [11], [12],contourlet [13], [14], wedgelet [15], bandlet [16], [17], and the steerable wavelet [18], [19]. In parallel, the introduction of the matching pursuit [20], [21] and the basis pursuit denoising [22] gave rise to the ability to address the image denoising problem as a direct sparse decomposition technique over redundant dictionaries. All these lead to what is considered today as some of the best available image denoising methods (see [23]–[26]for few representative works).

While the work reported here is also built on the very same sparsity and redundancy concepts, it is adopting a different point of view, drawing from yet another recent line of work that studies example-based restoration. In addressing general inverse problems in image processing using the Bayesian approach, an image prior is necessary. Traditionally, this has been handled by choosing a prior based on some simplifying assumptions, such as spatial smoothness, low/max-entropy,or sparsity in some transform domain. While these common approaches lean on a guess of a mathematical expression for the image prior, the example-based techniques suggest to learn the prior from images somehow. For example, assuming a spatial smoothness-based Markov random field prior of a specific structure, one can still question (and, thus, train) the derivative filters to apply on the image, and the robust function to use in weighting these filters’ outcome [27]–[29].

When this prior-learning idea is merged with sparsity and redundancy,it is the dictionary to be used that we target as the learned set of parameters. Instead of the deployment of a prechosen set of basis functions as the curvelet or contourlet would do, we propose to learn the dictionary from examples. In this work we consider two training options: 1) training the dictionary using patches from the corrupted image itself or 2) training on a corpus of patches taken from a high-quality set of images.

This idea of learning a dictionary that yields sparse representations for a set of training image-patches has been studied in a sequence of works [30]–[37]. In this paper, we propose the K-SVD algorithm [36], [37] because of its simplicity and efficiency for this task. Also, due to its structure, we shall see how the training and the denoising fuse together naturally into one coherent and iterated process, when training is done on the given image directly.

Since dictionary learning is limited in handling small image patches, a natural difficulty arises: How can we use it for general images of arbitrary size? In this work, we propose a global image prior that forces sparsity over patches in every location in the image (with overlaps). This aligns with a similar idea, appearing in [29], for turning a local MRF-based prior into a global one. We define a maximum a posteriori probability (MAP) estimator as the minimizer of a well-defined global penalty term.Its numerical solution leads to a simple iterated patch-by-patch sparse coding and averaging algorithm that is closely related to the ideas explored in [38]–[40] and generalizes them.

When considering the available global and multiscale alternative denoising schemes (e.g., based on curvelet, contourlet,and steerable wavelet), it looks like there is much to be lost in working on small patches. Is there any chance of getting a comparable denoising performance with a local-sparsity based method? In that respect, the image denoising work reported in[23] is of great importance. Beyond the specific novel and highly effective algorithm described in that paper, Portilla and his coauthors posed a clear set of comparative experiments that standardize how image denoising algorithms should be assessed and compared one versus the other. We make use of these exact experiments and showthat the newly proposed algorithm performs similarly, and, often, better, compared to the denoising performance reported in their work.

To summarize, the novelty of this paper includes the way we use local sparsity and

13

西安交通大学本科毕业设计（论文）

redundancy as ingredients in a global Bayesian objective—this part is described in Section II, along with its emerging iterated numerical solver. Also novel in this work is the idea to train dictionaries for the denoising task, rather than use prechosen ones. As already mentioned earlier, when training is done on the corrupted image directly, the overall training-denoising algorithm becomes fused into one iterative procedure that comprises of steps of denoising of the image, followed by an update of the dictionary. This is described in Section III in detail. In Section IV, we show some experimental results that demonstrate the effectiveness of this algorithm.

II. FROM LOCAL TO GLOBAL BAYESIAN RECONSTRUCTION

In this section, we start the presentation of the proposed denoising algorithm by first introducing how sparsity and redundancy are brought to use. We do that via the introduction of the Sparseland model. Once this is set, we will discuss how local treatment on image patches turns into a global prior in a Bayesian reconstruction framework.

A. Sparseland Model for Image Patches

We consider image patches of sizen?n pixels, ordered lexicographically as column vectorsx?Rn . For the construction of the Sparseland model, we need to define a dictionary (matrix) of size D?Rn?k (withk?n , implying that it is redundant). At the moment, we shall assume that this matrix is known and fixed. Put loosely, the proposed model suggests that every image patch, x , could be represented sparsely over this dictionary, i.e., the solution of

??argmin?0 subject toD??x (2)

??is indeed very sparse, ?0??n. The notation ? stands for the count of the nonzero

0?entries in ?. The basic idea here is that every signal instance from the family we consider can be represented as a linear combination of few columns (atoms) from the redundant dictionary D.

This model should be made more precise by replacing the rough constraint D??x with a clear requirement to allow a bounded representation error, D??x2??. Also, one needs to define how deep is the required sparsity, adding a requirement of the form

??L??n, that states that the sparse representation uses no more than atoms from the

0?dictionary for every image patch instance. Alternatively, a probabilistic characterization

can be given, defining the probability to obtain a representation with nonzeros as a decaying function of some sort. Considering the simpler option between the two, with the triplet (?,L,D) in place, our model is well defined.

Now assume that indeed belongs to the (?,L,D)-Sparseland signals. Consider a noisy version of it,y , contaminated by an additive zero-mean white Gaussian noise with standard deviation ?. The MAP estimator for denoising this image patch is built by solving

??argmin?0 subject to D??y2?T (3)

??2where is dictated by?,? . The denoised image is, thus, given by [22], [41], [42]. Notice that the above optimization task can be changed to be

14

附录

??argminD??y2???0 (4)

??2so that the constraint becomes a penalty. For a proper choice of?, the two problems are equivalent. We will use this alternative terminology from now on, as it makes the presentation of later parts simpler to follow.

While this problem is, in general, very hard to solve, the matching and the basis pursuit algorithms can be used quite effectively [20]–[22] to get an approximated solution. Recent work established that those approximation techniques can be quite accurate if the solution is sparse enough to begin with[41], [42]. In this work, we will make use mainly of the orthonormal matching pursuit (OMP) because of its simplicity [21]and efficiency.

B. From Local Analysis to a Global Prior

If we want to handle a larger image X of size N?N, and we are still interested in using the above described model, one option is to redefine the model with a larger dictionary. Indeed, when using this model with a dictionary emerging from the contourlet or curvelet transforms, such scaling is simple and natural [26].

However, when we insist on using a specific fixed and small size dictionary D?Rn?k, this option no longer exists. Thus,a natural question arises concerning the use of such a small dictionary in the first place. Two reasons come to mind: 1) when training takes place (as we will show in the next section), only small dictionaries can be composed; and furthermore; 2) a small dictionary implies a locality of the resulting algorithms, which simplifies the overall image treatment.

We next describe possible ways to use such a small dictionary when treating a large image. A heuristic approach is to work on smaller patches of size n?nand tile the results. In doing so, visible artifacts may occur on block boundaries. One could also propose to work on overlapping patches and average the results in order to prevent such blockiness artifacts, as, indeed,practiced in [38]–[40]. As we shall see next, a systematic global approach towards this problem leads to this very option as a core ingredient in an overall algorithm.

If our knowledge on the unknown large image X is fully expressed in the fact that every patch in it belongs to the (?,L,D)-Sparseland model, then the natural generalization of the above MAP estimator is the replacement of (4) with

22???? (5) ?,X?argmin?X?Y????D??RX?ij???ijij0ijij2?ij,X??ijij2In this expression, the first term is the log-likelihood global force that demands the proximity between the measured image, X,and its denoised (and unknown) version X. Put as a

2constraint, this penalty would have read X?Y2?Const.?2, and this reflects the direct relationship between ?and ?.

The second and the third terms are the image prior that makes sure that in the constructed image, X, every patch xij?RijXof size n?n in every location (thus, the summation by i,j)has a sparse representation with bounded error. Similar conversion has also been practiced by Roth and Black when handling an MRF prior [29].

The matrix Rijis an n?Nmatrix that extracts the (i,j) block from the image. For an

N?Nimage X the summation over i,j includes (N?n?1)2items, considering all image patches of size

n?n in X with overlaps. As to the coefficients ?ij

15

西安交通大学本科毕业设计（论文）

, those must be location dependent, so as to comply with a set of constraints of the form

D?ij?xij.

22

C. Numerical Solution

When the underlying dictionary D is assumed known, the proposed penalty term in (5) has two kinds of unknowns: the sparse representations ?ijper each location, and the overall output image X. Instead of addressing both together, we propose a block-coordinate minimization algorithm that starts with an initialization X=Y, and then seeks the optimal

??ij. In doing so, we get a complete decoupling of the minimization task to many smaller ones, each of the form

??ij?argmin?ij?ij0??D?ij?xij (6)

?ij2?2handling one image patch. Solving this using the orthonormal matching pursuit [21] is easy, gathering one atom at a time, and stopping when the error D?ij?xijgoes below T. This

22way,the choice of ?ijhas been handled implicitly. Thus, this stage works as a sliding windowsparse coding stage, operated on each block of n?nat a time.

Given all , we can now fix those and turn to update . Returning to (5), we need to solve

X?argmin?X?YX22??D?ij?RijXij2?2 (7)

This is a simple quadratic term that has a closed-form solution of the form

X?(?I??RRij)(?Y??RD?ij) (8)

Tij?1Tijijij??This rather cumbersome expression may mislead, as all it says is that averaging of the denoised patches is to be done, with some relaxation obtained by averaging with the original noisy image.The matrix to invert in the above expression is a diagonal one,and, thus, the calculation of (8) can be also done on a pixel-bypixel basis, following the previously described sliding window sparse coding steps.

So far, we have seen that the obtained denoising algorithm calls for sparse coding of small patches, and an averaging of their outcomes. However, if minimization of (5) is our goal,then this process should proceed. Given the updated X , we can repeat the sparse coding stage, this time working on patches from the already denoised image. Once this is done, a new averaging should be calculated, and so on, and so forth. Thus,we obtain exactly what Guleryuz suggested in his work—iterated denoising via sparse representation, and we may regard the analysis proposed here as a rigorous way to justify such iterated scheme [38]–[40].

III. EXAMPLE-BASED SPARSITY AND REDUNDANCY

The entire discussion so far has been based on the assumption that the dictionary D?Rn?kis known.We can certainly make some educated guesses as to which dictionaries to use. In fact,following Guleryuz’swork, the DCT seems like such a plausible choice [38]–[40]. Indeed, we might do better by using a redundant version of the DCT,1 as practiced in [36]. Still, the question remains: Can we make a better choice for D based on training? We now turn to discuss this option. We start with the simpler(and less effective) option of training the

16

附录

dictionary on a set of image patches taken from good quality images, and then turn to discuss the option of training on the corrupted image itself. A. Training on the Corpus of Image Patches

MGiven a set of image patches Z??zj?j?1, each of size n?n, and assuming that they emerge from a specific(?,L,D)-Sparseland model, we would like to estimate

this model parameters, (?,L,D). Put formally, we seek the dictionary D that minimizes

?(D,??j?j?1)??[?j?j0?D?j?zj2] (9)

M2j?1MJust as before, the above expression seeks to get a sparse representation per each of the examples in Z, and obtain a small representation error. The choice for ?j dictates how those two forces should be weighted, so as to make one of them a clear constraint. For example, constraining ?j?j0?Limplies specific values for ?j, while requiring

?jD?j?zj0??2leads to others.

The K-SVD proposes an iterative algorithm designed to handle the above task effectively [36], [37]. Adopting again the block-coordinate descent idea, the computations of

?j?MD and?are separated. Assuming that D is known, the penalty posed in (9) reduces to a j?1set of M sparse coding operations,very much like the ones seen in (6). Thus, OMP can be used again to obtain the near-optimal (recall that OMP is an approximation algorithm, and,

?j?Mthus, a true minimization is not guaranteed) set of representation vectors ?. j?1Assuming these representation vectors fixed, the K-SVD proposes an update of the

dictionary one column at a time. As it turns out, this update can be done optimally, leading to the need to perform a SVD operation on residual data matrices, computed only on the

?j?M)is guaranteed to drop per examples that use this atom. This way, the value of ?(D,?j?1an update of each dictionary atom, and along with this update, the representation coefficients

change as well (see [36] and [37] for more details).

When adopted to the denoising task at hand, a crucial step is the choice of the examples to train on. Is there really a universal dictionary that fits all images well? If there is one, whichexamples shall we use to find it? The experiments that follow in the next section bring us to the conclusion that while a reasonably good dictionary that fits all is indeed within reach, extracting state-of-the-art denoising performance calls for a more complex model that uses several dictionaries switched by content—an option we do not explore in this work.

Also, since the penalty minimized here in (9) is a highly nonconvex functional, local minimum solutions are likely to haunt us. Thus, a wise initialization could be of great worth. In our experiments we started with the already mentioned redundant DCT, which proves to be a good dictionary choice. This also enabled us to apply fewer number of iterations.

Another puzzling issue is the redundancy factor k/n—How should we choose k, the number of columns in D? Is there an optimal choice? In this work, we do not address this important question, and simply choose a value we find empirically to perform well. Further work is required to explore this matter.

B. Training on the Corrupted Image

Instead of supplying an artificial set of examples to train on, as proposed above, one

Mcould take the patches from the corrupted image, Z??yj?j?1, where M?(N?n?1)2.

17

西安交通大学本科毕业设计（论文）

Since the K-SVD dictionary learning process has in it a noise rejection capability (see experiments reported in [36]), this seems like a natural idea. Furthermore, rather than using unrelated examples that call for the universality assumption of the Sparseland model, this option tailors the dictionary to the image to be treated.

At first sight, this change in the origin of the examples to train on seems to be of technical worth, and has no impact on the overall algorithm. However, a close inspection of

?j?M) (9), and the global MAP penalty in (5), reveals the close both the functional in ?(D,?j?1resemblance between the two. This implies that the dictionary design could be embedded

within the Bayesian approach. Returning to (5), we can regard also as an unknown, and define our problem as

22????? (10) D,?X?argmin?X?Y????D??RXij????ijij0ijij2???ij,X,Dijij2Following the previously constructed algorithm, we can assume a fixed D and X, and compute the representations?ij. This requires, as before, a sparse coding stage that deploys the OMP.Given those representations, the dictionary can be now updated, using a sequence of K-SVD operations.

Once done, the output image can be computed, using (8).However, an update of the output image X changes the noise level ?, which up until now has been considered as known, and was used in the preceding two stages. Therefore, we choose to perform several more iterations of representation computation and dictionary update, using the same value of ?, before finding the output image X. This algorithm is described in detail in Fig. 1.

In evaluating the computational complexity of this algorithm,we consider all three stages—sparse coding (OMP process), dictionary update (these stages are iterated J times), and final averaging process. All stages can be done efficiently, requiring O(nkLj)operations per pixel, where n is the block dimension, k is the number of atoms in the dictionary, and L is the number of nonzero elements in each coefficient vector. L depends strongly on the noise level, e.g., for??10, the average L is 2.96, and for ??20, the average L is 1.12.

IV. CONCLUSION AND FURTHER WORK

This work has presented a simple method for image denoising,leading to state-of-the-art performance, equivalent to and sometimes surpassing recently published leading alternatives.The proposed method is based on local operations and involves sparse decompositions of each image block under one fixed over-complete dictionary, and a simple average calculations.The content of the dictionary is of prime importance for the denoising process—we have shown that a dictionary trained for natural real images, as well as an adaptive dictionary trained on patches of the noisy image itself, both perform very well.

There are several research directions that we are currently considering, such as using several dictionaries and switching between them by content, optimizing the parameters, replacing the OMP by a better pursuit technique, and more. Beyond these,one direction we consider to be promising is a generalization to multiscale dictionaries. This work concentrated on small image patches, completely overlooking the global structure of the

image, and the multiscale analysis that other techniques have exploited rather well.We are studying ways to extend this work to multiscale dictionaries, as it is clear that K-SVD cannot be directly deployed on larger blocks.

18

?

附录

译文：

基于稀疏和冗余表达研究图像去噪问题

摘要：

我们处理的图像去噪问题，就是从一张给定的图像中除去附加的零均值高斯白噪声。采取的办法是基于稀疏及冗余表达。使用K-SVD算法，我们得到一个方法来有效地描述图像内容。有两个训练选项可以考虑：利用含噪图像本身，或通过高品质图像数据库中的一组图像块训练。由于K-SVD 在处理小图像噪点时是有限的，我们把它展开成任意图像大小通过定义一个预先给图像强制让图像中的每个位置上的噪点稀疏开来。我们将展示如何通过贝叶斯处理法得到一个简单有效的降噪算法。这就得到了一个消噪性能相当好的算法。

关键词：贝叶斯重建，学习算法，离散余弦变换（DCT），图像去噪，K-SVD，匹配追踪，最大后验（MAP）的估计，冗余，稀疏表达。

一.引言

在本文中，我们针对传统图像去噪问题：将一个理想的图像x加入一个添加了零均值的白色，均匀的高斯噪声v，标准差为?。从而处理后的图像y为

y?x?v （1） 我们希望设计一个算法可以从y中消除噪声，尽可能恢复为原来的图像x。

图像去噪问题是重要的，不仅是因为它提供的明显的应用服务。作为最简单的反问题，它提供了图像处理的想法和技术进行评估的一个方便的平台。确实，过去50年的众多成果大概都得力于对这个问题众多不同的看法和观点。这从许多不同的看法点问题。统计估计，空间自适应滤波器，随机分析，偏微分方程，变换域的方法，花键和其他逼近理论方法，形态分析，顺序统计，等等，都是众多研究探讨这个问题的方向。在本文中，我们不打算提供对这一问题的进行所有大量工作。相反我们打算集中于找到一个高效的有前途的图像去噪问题特殊的逼近方法：利用在已有训练样本上的稀疏和冗余表达。

在过去10年，利用冗余表达和稀疏作为消除信号中的噪声的推进力量已经吸引了一大批研究者的注意。起初，人们考虑了稀疏的一元微波系数，导致著名的收缩算法[1]-[9]。使人们把目光转向冗余表达的一个原因是希望得到转换不变性。同样，随着对处理图像时规则可分1-D微波是不适当的逐渐认识，一些新的定制的多尺度和定向的冗余表换被提了出来，包括曲波[11], [12],轮廓波[13], [14]，楔波[15]，带波[16], [17],和可操纵的曲波[18], [19]。与此同时，匹配追踪[20], [21]的引入和基础追踪降噪[22]使得将处理图像降噪问题作为一个冗余样本的直接稀疏分解技术。所有这些作为当今被认为是现有的最佳图像去噪方法（见[23]-[26]对一些具有代表性的作品）。 虽然这里的工作也是建立在相似的稀疏性和冗余的概念上，但从近期同步的研究基于实例的恢复工作中可以看出，它是采用不同的的角度来看的。在用贝叶斯逼近的方法处理图像中的一般反问题时，一张预先的图像是必要的。一般地，这些在处理时要预先选择一些简化的假设上，如空间平滑，低/最大熵，或在一些变换域上稀疏。虽然这些共同的方法依靠预先图片一个数学表达式的猜想，不知为何在此基础上的实例的技巧建议研究之前的图像。举例来说，假定一个平滑空间建立在事先给定的特定结

19

西安交通大学本科毕业设计（论文）

构的马尔可夫随机场，仍可衍生出的过滤器应用于这图像上，并且强大的功能用在加权过后这些过滤器的结果[27]-[29]。

当预先学习的想法结合了稀疏性和冗余，我们将样本用来以设置参数为目标。我们打算从实例中学习基元组，而不是一组预先选定的基础函数的展开如同曲波和轮廓波得出的。在训练工作中，我们考虑两个方案：1）从噪声图像本身的噪声中训练算法或2）训练从一组高质量图片中取得的噪声集合。

学习基元组的想法对一组训练噪声图片产生出的稀疏表达已经得出了一系列成果[30]-[37]。在本文中，我们打算K-SVD算法[36]，[37]，因为它对这个任务的简单性和效率性。此外，由于其结构，当给定图像的训练已经完成时，我们将看到训练和去噪是如何自然地融合成一个共同连贯和迭代的过程。

由于基元组学习在处理小图像噪声时有效，于是便出现了一个难点：我们如何将它应用在一般的任意大小的图像？在这项工作中，我们打算将一个预先的全局图像中每个位置的噪声强制使它稀疏（包括重叠部分）。这与一个类似的想法谋合，出现在[29]，将一个局部基于MRF预先图片转化为一个全局的。我们定义一个最大后验概率（MAP）的估计作为一个已定义的全局惩罚项极小。它的数值解将得出一个简单的重复的稀疏编码和接近涉及研究[38]–[40]的思路并概括它们的平均算法。

在考虑可行的全局和多尺度的选择去噪方案时（例如，基于曲波，轮廓波和可操纵小波），看起来似乎在处理小噪声中有很大的丢失。有没有可能得到一个可比去噪性能基于局部稀疏的方法？在这方面，在[23]中的图像降噪是非常重要的。除了在那篇文章中描述了特殊新颖的高效率的算法，Portilla和他的合著者还清楚地得出了一组比较试验使得如何评估图像除噪算法及与其他算法比较标准化了。我们利用这些精确的实验并展示新算法有类似的性能，并且经常，与他们工作中得到的去噪能力表现相比较哪个更好。

总之，本文新颖之处包括我们利用局部的稀疏和冗余表达作为全局贝叶斯目标的因素的方法，这部分第二部分有所描述，沿其形成的迭代数值解法。相比使用预先选定的方法，对去噪工作进行方法训练的想法更新颖。正如前面提到过的，当对噪声图像直接进行训练已经完成时，全面的去噪训练算法融合成一个由图像去噪步骤组成的迭代过程，并接着进行算法更新。这在第三部分将详细叙述。在第五部分，我们将展示一些实验结果以表明这个算法的有效性。

二.从局部到全局贝叶斯重建

在这一部分，我们首先介绍稀疏和冗余如何使用开始慢慢得到除噪算法的表达。我们这样做通过引入Sparseland模型。一旦这样做了，我们将讨论图像噪声上的局部处理怎样转换为一个贝叶斯重建架构上的预先全局的处理。

A.对图像噪声的Sparseland模型

我们考虑图像图像块大小为n?n像素，令作列向量x?Rn。对Sparseland模型的构建，我们需要定义一个基元组大小为D?Rn?k（k?n时，冗余）。这时，我们假定这个基元组是已知确定的。该模型表明每一个图像块x，可以通过这个基元组稀疏表达出来。例如，

??argmin?0 s.t. D??x (2)

??20

附录

该方案确实确保稀疏，?0??n符号?表示?中非零项数。基本思路是从样例图像考

0?虑的每个图像块可以表示成冗余基元组D的一个基元线性足额。

这种模型应该替换掉D??x，明确地要求允许一个有界表示误差，D??x2??使得更精确。此外，需要定义必须的稀疏性强度，加入一个条件??L??n，表明稀疏

0?表达用的只是实例中每个图像图像块的基元组的L个基元。或者，给出一个概率表征，定义概率得到一个?非零的表达作为一些情况的衰减函数。考虑到两者之间的简单

0?选择，(?,L,D)在适当的位置，我们的模型很好的界定。

现在假设x确实属于(?,L,D)Sparseland。考虑它的一个噪声图像，y，加入一个零均值高斯白噪声，标准偏差为?。去除这个图像图像块的噪声的MAP估计建立在解决

??argmin?0 s.t. D??y2?T (3)

??2T由?，?确定。去除了噪声的图像因此由x?D? 给出。注意上面的最佳化过程可以改为

????argminD??y2???0 (4)

??2因此约束项成为惩罚项。适当选择?，这两个问题是等价的。我们从现在开始将使用这种选择性的术语，因为它使得稍后介绍的部分更简单地理解。

虽然这个问题在一般情况下是很难解决的。匹配和基础追踪的算法可以相当有效的用在[20] - [22]得到一个近似的解决办法。最近的研究工作确定了这些近似方法可以相当准确的如果这些解决办法是在[41]，[42]中足够稀疏。这样，我们将主要使用标准正交匹配追踪（OMP），因为它简单[21]，有效。

B.从局部分析到预先全局

如果我们想要处理大点的图像X，大小为N?N(N??n)，我们仍把注意力放在使用上述描述的模型，办法之一是用一个大的基元组重新定义该模型。事实上，当用这个模型使用轮廓波和曲波变换建立起基元组，缩放是简单和自然的[26]。 但是，当我们坚持使用特定的固定的和小基元组D?Rn?k，。因此，一个自然的问题就出现了，关于首先用这样的小基元组。两个需要注意的原因是：1）当训练发生了（我们将在下一节中展示），只有用小基元组才可以构成，进而继续后面工作，2）一个小基元组意味着由此产生的算法，简化了所有的图像处理。

我们下一步要叙述当处理大型影像时使用这种小基元组可能的方法。一种启发的方法是在大小为n?n更小的图像块上应用并并列显示结果。这样做，有形物体可能会出现在块边界。也可以尝试研究图像块重叠部分并结果达到平均水平，以防止这些区块物体，正如事实上[38]-[40]实行的一样。正如我们下面想看到的，对这个问题一个系统全局的方法得到一个全面的算法中以此选择作为一个核心因素。

如果我们对未知的大型图片X的认识基于每个图像块都属于(?,L,D)?Sparseland

21

西安交通大学本科毕业设计（论文）

模型事实上，得到了充分表示，那么自然推广上述MAP估计更换（4）为

22???? ??ij,X??argmin?X?Y2???ij?ij??D?ij?RijX (5)

0?ij,X??ijij2在这个表达式中，第一项是对数似然全局，要求之间的处理过的图像Y和它的已去噪（未知）图像X相接近。把它作为约束，此惩罚项X?Y22?Const.?2而这反映了?和?之间的直接关系。

第二项和第三项是原先的图像用来确保构造的图像X中，每个位置上的大小为n?n的图像块xij?RijX（对i,j求和）在有限误差内有一个稀疏表达。类似的转换也已经由Roth和Black在处理一个预先MRF[29]中尝试过了。

基元组Rij是一个n?N基元组，是从图像提取出的块。对一个N?N图像，对i,j求和包括(N?n?1)2 项，考虑X中所有大小为n?n的图像图像块重叠部分。对于系数?ij，必须依位置而定，使得遵从一组约束条件D?ij?xij22?T。

C.数值求解

当下面的基元组D假定已知，（5）中提及的惩罚项有两种未知数：每个位置上的稀疏表达?ij，以及整体输出图像X。我们不采用同时寻找两个数，而是建议用块极小化算法从初始值X=Y开始，寻找最优值我们提出?ij。这样做，我们得到极小化任务单调减到更小值，每一个

???ij?argmin?ij?ij0??D?ij?xij （6）

?ij2?2处理一个图像图像块。使用标准正交匹配追踪[21]解决这个很容易，一次加一个原子，当误差D?ij?xij小于T时停止。这样，?ij的选择就得到了控制。因此，这个阶段如

22滑动的窗口稀疏编码阶段一样运行，在每个n?n块上同时运算。

给定所有的?ij，我们现在可以固定它们的值然后开始更新X。回到（5），我们需要解出

X?argmin?X?YX22???D?ij?RijXij2?2 (7)

这是一个简单的二次项，它有一个相似的解决形式

X?(?I??RRij)(?Y??RD?ij) （8）

Tij?1Tijijij??这个相当繁琐的表达，它说的是已经将去完噪的图像块平均化了，通过将原有噪声图片平均轻松地得到了。上述表达中基元组的逆是一个对角阵，所以，（8）的计算可以在每一个基础像素上进行，按照前面描述的滑动窗口稀疏编码的步骤。

到目前为止，我们已经看到，已得的图像去噪算法要求小图像块上的稀疏编码，以及这些结果的平均值。但是，如果（5）的最小化值是我们的目标，那么这个进程应该继续。给定新的X，我们可以重复稀疏编码阶段，这时从已经去噪图像上的图像块着手。一旦做到这一点，应该计算一个新的平均值，等等，等等。因此，我们正是取得Guleryuz在他的工作获得的---通过稀疏表示迭代去噪，我们可以把这里提出的分析作

22

附录

为一个严格的方式来证明这种迭代方案[38]-[40]。

三.基于稀疏性和冗余的样本

迄今为止所有讨论都建立在假设基元组D?Rn?k已知上。我们当然可以对使用某个基元组做一些有根据的推测。事实上，以下Guleryuz的研究，DCT似乎是一个可行的选择[38] - [40]。事实上，我们使用冗余的离散余弦变换如[36]所采用的可以做得更好。然而，问题 仍然是：我们能不能在训练的基础上选择更好的D？我们现在讨论这一方案。我们先从简单的（低效的）方案开始，将从高质量图像中得到的一组图像图像块训练基元组，然后再转向讨论对含噪图像本身的训练方案。 A.训练图像图像块样本

M给定一组图像图像块Z??zj?j?1，每个大小为n?n，并假设它们出自一个特殊的(?,L,D)?Sparseland模型，我们将估计这个模型参数，(?,L,D)。搜寻基元组D通过最小化

?(D,??j?j?1)??[?j?j0?D?j?zj2] （9）

M2j?1M正如前面所述，上面的表达式试图寻找Z中每个实例的稀疏表达，并获得一个较小的

表达误差。?j的选择规定了这两种力量该怎样加权，使得它们中的一个完全约束。例如，约束

?j?j?L意味?j的特征值，而要求?jD?j?zj00??2则得其它值。

K-SVD期望得到一个迭代算法用来有效地处理上述问题[36], [37]。再次采用块下

?j?M降的思路，D和?的计算就分开了。假设D已知，（9）产生的惩罚项简化为一组Mj?1稀疏编码运算，就如（6）中所看到的非常相似。因此，可以再次使用OMP获得近似最

?j?M优值（注意OMP是一种近似算法，因此最小值不能保证）表达向量? j?1 假设这些表达向量是固定的，K – SVD每次将基元组每列更新一次。随着结果产

生，这种更新是最优的，使得满足SVD可以在剩余数据基元组上运算，只在使用这个

?j?M)的值可以确保在每个基元组基元每次更基元的块上计算。通过这种方式，?(D,?j?1新都是下降的，并随着更新，表达系数也随着改变。（详情见[36]和[37]）。

当进行去噪工作时，一个重要的步骤就是选择样本来训练。是否真的有通用的基元组适合所有图像呢？如果有，用哪个样本可以找到它？在接下来下一节的实验将为我们给出结论，虽然合理的较好的基元组确实可找到，寻求先进的消噪性能要求更复杂的模型，使用若干基元组在一定条件下转换---我们不探讨这方面的工作。

此外，由于（9）中最小的惩罚项是一高度非凸可行的，局部最小的解决方案有可能萦绕在我们心头。因此，一个好的初始化值可能会有很大的帮助。在我们的我们已开始的使用冗余DCT的实验，证明是一个好的基元组选择。同样我们也能够运用在迭代次数较少的运算中。

另一个令人困惑的问题是冗余因数k/n，如何我们应该如何选择k，D的列数呢？有最佳的选择吗？在本文中，我们不探讨这个重要的问题，只依经验选择一个能很好满足要求的值。将来的工作中需要探讨这个问题。 B.对含噪的图像进行训练

23

西安交通大学本科毕业设计（论文）

如上述提议，可以从含噪的图像中选取图像块，Z??yj?j?1，其中

M由于K-SVD算法学习过程中有一个噪声抑制能力（见[36]中实验），M?(N?n?1)2。

就像一个自然的思路。此外，使用相关的例子要求Sparseland模型中的一般性假设，实现算法处理图像。

乍一看，在对训练样本初始的改变看似很有价值价值，且并没有影响整体算法。

?j?M)和（5）中全局MAP惩罚项，可以看出两者然而，仔细观察（9）中可行的?(D,?j?1之间的紧密的相似性。这意味着该算法的设计可以嵌入贝叶斯方法。回到（5），我们

也可以把D看做未知的，并定义我们的问题为

22????? ?D,?ijX??argmin?X?Y2???ij?ij??D?ij?RijX (10）

0???ij,X,Dijij2根据先前构建的算法，我们可以假设一个固定的D和X，并计算表达式?ij。这和以前一样，要求稀疏编码阶段展开OMP。给出这些表达式，现在使用一系列K-SVD运算可以更新基元组。

一旦这样做，输出图像应用（8）式可以得到计算。但是，对输出图像的更新改变了噪音水平?，?到现在为止一直被认为已知的，被用在前两个阶段。因此，在寻找输出图像之前，我们选择使用相同的?值，执行几次表达式计算迭代和基元组更新。该算法在Fig.1中由详细描述。

评估该算法的计算复杂性时，我们考虑所有这三个阶段：稀疏编码（OMP过程），基元组更新（此阶段迭代J次），最后平均过程。所有阶段都可以高效完成，要求在每个像素点上运算O(nkLj) ，n为块维数，k为基元组中原子数，L为每个系数向量的非零数。L主要依赖于噪声水平，例如，对??10，L的平均数为2.96，对??20，L的平均数位1.12。

四.总结和进一步工作

我们的工作已经给出了一个对图像去噪简单的方法，有相当好的性能，效果相当并且有时甚至超过乐最近发表的主要替代法。该方法基于局部操作且包括在超完备基元组下对每个图像块的稀疏分解，和一个简单的平均计算。基元组的内容是去噪过程中最重要的一块---我们已经表明，在一个高质量的图像上学习出的基元组，以及对噪声图像本身的图像块训练出的自适应基元组，都有非常好的表现。

还有若干个研究方向我们目前正在考虑，例如使用一些算法，通过内容相互转换，优化参数，使用更好的追踪技术替代OMP，等等。除了这些，我们认为是很有前途的一个方向是多尺度算法的一般化。这项工作主要集中在小图片图像块上，完全忽略了图像的全局结构，并且多尺度分析在其他技术方面已经做出了相当好的成绩。我们正在研究如何将这项扩展到多尺度算法，因为很明显K-SVD不能直接应用在较大的块上。

?24

附录

致 谢

此学士论文是在我的导师孙剑老师的亲切关怀和悉心指导下完成的。他平易近人、和蔼亲切的处事态度一直是我深深敬佩和仰慕的；他一丝不苟、不拘一格、严谨细致、认真负责的指导风格是我学习的榜样；他严肃的科学态度，严谨的治学精神，精益求精的工作作风，又深深地感染和激励着我，给了我无尽的启迪和受益终生。从开题到论文的最终完成，孙老师都始终给予我细心的指导和不懈的支持。在此谨向孙老师致以最崇高的敬意和最衷心的感谢！在论文即将完成之际，我要再次感谢那些给了我许多帮助的人，在这里也请接受我最诚挚的谢意！最后，我还要感谢培养我长大，从小学到大学，为供我念书的勤俭节约、含辛茹苦的父母，谢谢你们！正是因为有了你们，我所做的一切才更有意义；也正是因为有了你们，我才有了追求进步的勇气和信心。真的谢谢你们！

我将更加有目的学习，严格要求自己，提高综合能力，为学校争光，以报答学校对我的培养。

25

本文来源：https://www.bwwdw.com/article/469g.html