第1章 绪 论
1.1 背景及意义
1.1.1 压缩感知理论
现代社会是信息的社会，随着信息技术的不断提高，人们的生活水平有了很大提高，含有丰富信息的图像、视频成为人类主要的信息源。同时人们对信息的质量与信息传输的速度都提出了更高的要求。虽然信息技术发展很快，但由于硬件的限制和对提高传输效率的成本考虑，使通过很少的数据对目标的重要信息进行表示再进行传输、储存成为解决这些问题的有效方法。
压缩感知理论利用部分测量数据就可以对原信号进行较为精确的重构，在采样速率上突破了Shannon-Nyquist采样定理的限制，实现了对信号采样到信息采样的转变，降低了采样频率、信号处理的时间和计算量，从而减少了数据存储与传输的成本。压缩感知理论从信号的稀疏性出发，分为两个过程：1）把一个复杂的信号转变为大部分为零或者接近零的稀疏信号，即稀疏表示的过程。2）通过稀疏表示后的信号对原信号进行重构，即稀疏重构的过程。图1为压缩感知信号处理流程。
稀疏重构的过程可以表示为一个最优化的问题，通过求解最优化的问题就完成了对于信号重构。压缩感知理论在信息量丰富的数字图像处理领域应用广泛，有着很好的应用前景。
1.2 国内外研究现状
早在20世纪70年代人们就发现，”Shannon-Nyquist采样定理的限制是可以突破的”[3]。这种利用有限的数据和一定的先验知识的信号表示方法充分利用了信号里的信息，使重构信号的条件更加宽松。但直到近二十年，人们证明了对于满足一定条件的测量矩阵，可以通过随机矩阵进行采样，得到的稀疏信号以很高概率较准确地重构出原信号。之后人们对于信号的稀疏性才渐渐重视起来。同时也使带有”稀疏性”约束的优化问题的求解方法得到进一步发展。
2006年，在Cand`es、Romberg与Tao等人发表的论文中，提出了一种新的信息采集和重构的方法，即压缩感知理论（Compressed Sensing，CS）。证明了满足约束等距性条件（RestrictedIsometryProperty，RIP）的矩阵能精确重构稀疏或近似稀疏的信号。并构造了相关算法。压缩感知理论的提出使稀疏约束的优化问题的研究得到进一步发展。发展出许多有效的处理稀疏重构问题的算法。主要分为6类算法：
1)求解非凸优化的算法，通过直接求解非凸优化的近似解，如FOCUSS、IterativeRe-weighted Least Squares、稀疏贝叶斯学习算法、基于蒙特卡罗算法等。
2)组合次线性算法，针对信号进行高度结构化的采样，由群测试来快速获取信号支撑，主要有链式追踪（Chaining Pursuit,CP）算法、Heavy Hitters on Steroid-s（HHS）算法、傅立叶描述法等。
3)迭代阈值算法，主要针对最小化l1模的线性规划算法，有软阈值迭代（IterativeSoft Thresholding，IST）、硬阈值迭代（Iterative Hard Thresholding，IHT）等算法。
4)松弛凸优化算法，与迭代阈值类似求解凸优化近似解，算法有基追踪（BasisPursuit，BP）算法、LASSO算法等。
5)贪婪迭代算法，主要思想为迭代地在字典中选择原子，计算系数，每次迭代选择原子填补表示结果和测量数据间的差距，常见的有匹配追踪（MatchingPur-suit，MP）算法、正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法等。
6)Bregman迭代算法，利用次梯度方向迭代高效求解优化问题。
这些算法分别从不同角度求解了稀疏重构问题。其中贪婪优化的算法速度较快，较为常见。Mallat等人在1993年提出的匹配追踪的思想，利用超完备字典进行稀疏分解，将机器学习中的方法引入稀疏表示问题。
信号稀疏表示的方式常以调和变换或学习的方法获得。调和分析中经典的傅立叶变换、离散余弦变换以及小波变换等均可以用于构造稀疏表示的基。另外，基于学习的字典构造方式可以自适应地学习、训练得到表示字典，使表示后的信号具有更好的稀疏性。2000年K.Engan等人提出了最优方向法（MethodofOptimalDirections，MOD）简单地完成了字典的更新。2006年M.Aharon,M.Elad等人利用K-Means聚类的思想提出K-SVD方法完成了对字典的有效学习。
使用调和变换的字典构造方法无法对信号自适应地处理，对于大部分图像可以表示成较稀疏的形式，但并不能像学习字典那样充分利用图像中的信息，因此在表示信号的稀疏性上有局限性。而学习字典所需的时间复杂度较高，使用较为复杂，仍有待进一步研究。
第2章 稀疏表示基本理论
压缩感知理论表明了对于一个具有稀疏性的信号可以利用随机矩阵以远低于Shannon-Nyquist采样定理的采样频率进行采样，这样得到的信号可以利用信号的稀疏性对其进行精确重构。但自然界的大部分信号原本并不是稀疏的，需要利用字典将其表示成大部分为零的稀疏信号以进行信号重构，因此信号的稀疏表示是压缩感知中重要的一环。对信号稀疏表示的处理过程可以简单地看作对原信号的变换。为保证稀疏表示后信号的稀疏性与信号重构的准确性，需要考虑信号重构的目标，求解优化问题，构造稀疏表示的字典。
2.1 稀疏约束下的信号表示与重构问题
2.1.1 带有稀疏约束的优化问题
先给出lp范数的定义，当p在[0,1)区间取值时，定义的范数可能不满足三角不等式，故这里的范数并不是真正意义上的范数，但通常我们还是将其称作范数，并不影响讨论。
2.1.2学习字典目标
根据信号是s稀疏的的定义可知，信号的稀疏度是与表示的字典相关的，一个合适的字典可以使信号稀疏度更高，以此重构的精度也越高。按照机器学习的想法，利用已知的样本对字典进行训练，学习得到的字典可以适应一类信号使其稀疏度更高。学习字典的过程也可以看作重复对信号进行重构的过程。因此其问题类似于稀疏重构的问题。可以以下面模型表示：
学习字典问题中只有稀疏表示后的信号y是已知的，目标是获得稀疏表示性能最好的字典。
2.2 稀疏约束优化问题求解方法
对稀疏约束的优化问题有很多不同的求解方式，由于P0问题是一个非凸优化问题，通常会求其近似解或者求解可解的同解问题。追踪算法是求解原问题的常见算法。
2.2.1 匹配追踪算法
匹配追踪(MatchingPursuit,MP)[18]算法是通过度量与残差的相似性从字典中逐个挑选原子，逐步实现对原信号的稀疏逼近的有效方法。MP算法是一种迭代贪婪算法，在其每一次迭代中，依次从字典中选取了最能匹配信号结构的原子用来重构信号，以使重构的信号中非零元素最少。
设A = {am}m∈Γ是由M个范数为1的原子组成的字典，该字典至少包含N个线性无关的向量，构成信号空间CN的一组基，其中Γ = {1,2,··· ,M}，且M > N。
MP算法先将b投影到一个向量am0∈ A，并计算出残差r，即
匹配追踪算法以指数级收敛，但当信号空间的维数N增大时，MP算法不再以指数级收敛，收敛速度变慢。
第3章学习字典算法设计 ··········11
3.1 常见学习字典算法 ········· 11
3.1.1 MOD字典学习算法················ 11
3.1.2 K-SVD字典学习算法 ·················· 12
第4章基于GSAP-KSVD和APG-KSVD算法的图像去噪 ··················23
4.1 图像稀疏表示模型 ················· 23
4.1.1 图像块稀疏表示模型 ······················ 23
第4章 基于GSAP-KSVD和APG-KSVD算法的图像去噪
基于冗余字典的稀疏表示模型用于图像去噪可以有效提取图像的复杂特征，去噪效果良好。Curvelets、Contourlets等冗余字典的波形固定，对于一些图像进行稀疏表示的效果较好。而基于学习字典的稀疏表示可以通过训练的方式得到图像自身的特性，从而对于图像信号自适应地进行稀疏表示。
4.1 图像稀疏表示模型
稀疏表示的模型在用于图像处理时需要解决很多问题。当图像的尺寸比较大时，如果利用一个大字典直接进行稀疏表示，一次运算的运算量很大，效率很低。对于图像去噪问题需要重新构造模型，将算法用于解决图像去噪模型。本节将介绍这些问题的解决方法。
本章将基于GSAP-KSVD和APG-KSVD学习字典的图像去噪与DCT字典、全局字典和K-SVD字典的去噪效果进行对比实验，分析各个算法的性能。
DCT字典是构造字典，是通过离散余弦变换构造得到。对于图像的学习字典，其训练集的选取主要有两种方式：1)利用带有噪声的图像直接进行训练。2)从自然图像训练集或指定的图像集中选定若干幅，对其进行训练，得到全局字典。GSAP-KSVD、APG-KSVD与K-SVD字典均属于利用带噪图像训练的学习字典。
对lena、barbara、boat和house四幅标准测试图像利用GSAP-KSVD算法进行图像去噪，其中lena、barbara和boat是512×512的灰度图像，house是256×256的灰度图像。这里加入方差为20的高斯白噪声，分别用DCT字典、全局字典、GSAP-KSVD训练得到的字典和K-SVD训练得到的字典进行去噪。字典大小均为64×256。学习字典以图像加入噪声后选取其中部分8×8的可重叠的图像块作为训练集进行训练得到。图7是四种字典，其中GSAP-KSVD字典和K-SVD字典是对lena图像通过10次迭代训练得到的。
结论与展望
信号的稀疏表示是近些年随着压缩感知的发展兴起的研究热点。通常自然信号都具有一定的稀疏性，一个好的字典可以对于信号进行更稀疏的表示，且具有很高的准确性。通过对于样本进行学习得到的字典可以自适应地表示一类信号，得到更稀疏和准确的表示。与构造字典相比，学习字典具有更好的表示能力。字典对于信号的稀疏表示程度是信号能否准确重构的重要条件。具有很高的应用价值和发展前景。
本文第一章介绍了压缩感知理论以及压缩感知过程中的稀疏表示字典的设计，阐述了稀疏表示与重构的基本原理，并对稀疏重构的基本方法，表示字典研究的发展现状进行了简要介绍。
第二章介绍了带有稀疏约束优化的基本问题以及学习字典的基本目标，并对于求解稀疏约束优化问题的求解方法进行了简单分析与说明。
第三章为本文的重点内容。通过对于常见字典学习算法最优方向法和K-SVD算法的介绍和分析，指出现有的算法中的不足之处。对于K-SVD算法进行改进，得到全局支撑交错追踪K-SVD算法，并再次对提出的算法进行改进，提出交错追踪先导K-SVD算法。从算法的准确性、有效性和复杂度上均较K-SVD算法有了一定提高。最后通过实验对比了MOD、K-SVD与APG-KSVD算法，验证了提出算法的有效性。
第四章用提出的字典学习算法对于图像去噪问题进行了实验，进一步验证了提出算法的可行性，并将结果与MOD、K-SVD算法进行对比。首先对于全局支撑交错追踪K-SVD算法进行了验证。算法效果好于DCT字典以及全局字典，但稍逊于K-SVD算法，但在时间上要远远小于K-SVD算法。然后对APG-KSVD算法进行图像去噪实验，得到很好的效果，在各方面均对K-SVD有了一定提高。
综上所述，采用字典更新单元对于K-SVD算法进行引导是可行有效的，APG-KSVD算法可以更快速高效地提取信号中的特征。交错追踪先导K-SVD的算法减少了K-SVD算法稀疏表示阶段的复杂度浪费。同时，在一定程度上解决了一些过编码的问题。是一种学习字典的有效方法。
本文在学习字典算法上进行了大量研究，但还有很多相关的方向可以研究。学习字典的问题也可以和很多现在热门的方法相结合，比如张量分解。如果可以建立张量字典，也可以看作是对于低维数据建立高维字典，其表示系数将会极大程度地得到稀疏。对于学习字典的应用方向目前也还有很多可以发掘的地方。
参考文献（略）