浅析稀疏表示

1、,浅析稀疏表示,姓名：袁其政 导师：邵枫老师,1、如何有效获取图像在字典下最稀疏的分解系数 2、如何设计与构建有效的图像稀疏表示字典 3、如何将图像稀疏表示模型应用于具体的图像处理反问题（Inverse Problems）中,对于一个完整的稀疏表示模型，要解决三个关键的问题：,稀疏表示的思想是自然信号可以被压缩表示，将信号看作是有限个元素的线性组合。,稀疏表示模型可如表达式(1)所示，其中xRn为待处理信号，DR(NL)为字典，aRL为稀疏系数，|a|0m。|a|0为a的0范数，它表示x中非0的个数，即表示a的稀疏度。 s.t. min|a|0 (1),x N1,D NL,a L1,其中：D过

2、完备字典， di原子， a稀疏表示的系数， a只有有限个（k个)非零元素，则称a是k稀疏的。,1、获取稀疏的分解系数方法,s.t. min|a|0,已知信号x和字典D求解稀疏系数a是求解欠定方程组的问题，可以得到无数多个解，在这些解构成的解空间中求最稀疏的解，就是要求的系数向量a中的非零向量最少，稀疏问题就可以表示为求解公式（2），在实际中，我们还要将公式（2）转换成公式（3）的形式，转化为稀疏逼近问题来求近似解。,（1）,（2）,（3）,公式（3）本质上式组合优化问题。,1、获取稀疏的分解系数方法,对于组合优化的问题，很难求出来，所以公式（3）要转化为公式（4），对其进行求解：,（3）,（4

3、）,目前有很多方法对公式（4）进行求解： 贪婪算法：匹配追踪（Matching Pursuit，MP） 正交匹配追踪（Orthogonal Matching Pursuit，OMP） 子空间追踪（Subspace Pursuit，SP） 松弛算法：最小绝对收缩和选择操作算法（Least Absolute Shrinkage And Selection Operator，LASSO） 最小角回归算法（Least Angle Regression，LAR） 非凸算法：迭代重新加权算法 Beyesian算法,1、获取稀疏的分解系数方法,贪婪算法的主要流程思想：根据事前设定的度量准则,通过迭代从过完备

4、字典中逐次选择最有用的原子(即与目标信号分量残差值最小的原子)构建逼近过程。 匹配追踪算法（Matching Pursuit，MP）：此算法的每次迭代,根据目标信号分量与字典原子之间的残差值为主要的度量原则,从过完备原子库里(即过完备字典矩阵D)选择与信号分量之间残差值最小(也就是“最匹配”)的原子,然后迭代重复执行上述过程,经过一定次数的迭代,最终信号的每一个分量均可以由若干字典原子的线性组合再加上最后的残差值来表示。MP算法一般得到的都是次优解。 正交匹配追踪算法（Orthogonal Matching Pursuit，OMP）：OMP算法是在MP算法的基础上改进而来的,有效克服了次优问题

5、。在原子选择准则的选取上,OMP算法与MP算法是一样的,不同之处在于OMP算法通过对迭代的每一步实现对所选的全部原子进行正交化处理这一目的,这样的处理可以保证迭代的最优性,同时大大减少了迭代的次数。,1、获取稀疏的分解系数方法,图像信号自身在空间域通常是不稀疏的，但在特定的字典下，其分解系数可能会变得稀疏，因此字典的设计也是稀疏表示中的一个重要问题。当前构造字典的方式有以下几种： （1）直接使用现有的正交基作为稀疏表示字典，如，离散的DCT字典，小波字典等，这类字典能够实现快速变化但是不能充分地对信号进行稀疏分解。 （2）将正交基，紧框架系统之间进行组合，从而能够反映图像中不同的几何结构，可以

6、形成更稀疏的表示。 （3）通过学习的方法获得稀疏字典。其基本思想是由一些训练样本通过机器学习得到特定的稀疏表示字典。常用的方法有最佳方向法(Method of Optional Directions, MOD)，K-SVD法，以及在线学习算法(Online Learning)等。,2、设计与构建有效的图像稀疏表示字典,最佳方向法(Method of Optional Directions, MOD)：找到一个字典D和稀疏表示矩阵A使得目标函数的误差最小，如下式： ai稀疏系数矩阵A的第i列。 优化的过程包括稀疏系数的更新和字典更新两个阶段。稀疏系数更新时，对每一个向量xi，用任一匹配追踪算法求

7、解其稀疏系数，字典更新时考虑信号的表示误差： 要得到更新的字典，要上式进关于D求导； 这种MOD方法总体还是有效的，但是由于涉及到矩阵的逆运算，计算量很大。与之相比，KSVD算法在字典更新上大大降低了计算复杂度。,2、设计与构建有效的图像稀疏表示字典,K-SVD算法通过对字典的每一列进行操作,而不是采用对矩阵求逆的方法。同时更新现有的原子和与之相关的稀疏系数，使得算法更具效率。因此相对于MOD算法,K-SVD是一种要求更低的高效快速算法。 K-SVD法包括稀疏求解和字典更新两个阶段，其核心步骤为： 1，系数更新 对每一个向量xi，用任一匹配追踪算法求解其稀疏系数； 2，字典更新： 更新D(J-

8、1)中的每一列 式中 K 字典的原子总数； k 要更新的原子索引。 从Ek中除去没有用到原子dk(J-1)的列得到EkR，对EkR进行SVD分解从而更新dk(J-1)，同时更新aRk。,2、设计与构建有效的图像稀疏表示字典,2、设计与构建有效的图像稀疏表示字典,DCT方法训练字典,MOD方法训练字典,K-SVD方法训练字典,字典训练的两种方式： 1，把失真图像为先验知识来训练字典。 2，把原始无失真图像作为先验知识来训练字典。,3、稀疏表示的应用,系数表示在图像处理的反问题中，主要有三种应用： 1、图像去噪：主要适用于加性噪声 2、图像超分辨率的重建：训练高低分辨率图像的两个字典（有的文章给出两个字典之间的关系系数）。 3、图像修复：利用待修复图像内的有效信息,采用K-SVD算法对所有不重叠取块后的图像块进行训练,得到与待修复图像相适应的新字典,求出稀疏系数,更新图像块,修复受损图像。,3、稀疏表示的应用（稀疏去噪）,N是噪声,用K-SVD方法训练出字典D,用OMP算法求出稀疏系数,此公式中的T是一个阈值，它与噪声N 有一定的关系，一个合理的阈值T可以让去噪效果达到更好。 则去噪之后的图像X为,3、稀疏表示的应用（稀疏去噪）,3、稀疏表示的应用（稀疏去噪）,原始图像,JPEG失真图像 psnr=21.