精华内容
下载资源
问答
  • 稀疏表示

    千次阅读 2018-12-28 20:34:00
     信号的稀疏表示并不是新的东西。我们很早就一直在利用这一特性。例如,最简单的JPEG图像压缩算法。原始的图像信号经过DCT变换之后,只有极少数元素是非零的,而大部分元素都等于零或者说接近于零。这就是信号的...

    1.  问题背景

     

            信号的稀疏表示并不是新的东西。我们很早就一直在利用这一特性。例如,最简单的JPEG图像压缩算法。原始的图像信号经过DCT变换之后,只有极少数元素是非零的,而大部分元素都等于零或者说接近于零。这就是信号的稀疏性。

            任何模型都有建模的假设条件。压缩感知,正是利用的信号的稀疏性这个假设。对于我们处理的信号,时域上本身就具有稀疏性的信号是很少的。但是,我们总能找到某种变换,使得在某个变换域之后信号具有稀疏性。这种变换是很多的,最常见的就是DCT变换,小波变换,gabor变换等。

            然而,这种正交变换是传统视频图像处理采用的方法。目前所采用的一般不是正交变换。它是基于样本采样的。或者说是通过大量图像数据学习得到的,其结果称作字典,字典中的每一个元素称作原子。相关的学习算法称作字典学习。常见的算法例如K-SVD算法。学习的目标函数是找到所有样本在这些原子的线性组合表示下是稀疏的,即同时估计字典和稀疏表示的系数这两个目标。

     

           压缩感知和稀疏表示其实是有些不同的。压缩感知的字典是固定的,在压缩感知的术语里面其字典叫做测量矩阵。但压缩感知的恢复算法和稀疏表示是同一个问题。他们都可以归结为带约束条件的L1范数最小化问题。求解这类泛函的优化有很多种方法。早在80年代,统计学中Lasso问题,其实和稀疏分解的优化目标泛函是等价的。而求解统计学中lasso 问题的LARS算法很早就被提出了,故我们还可以通过统计学的LARS算法求解稀疏表示问题。目前很多统计学软件包都自带LARS算法的求解器。

     

    2. 基于稀疏表示的分类 SRC

     

          人脸的稀疏表示是基于光照模型。即一张人脸图像,可以用数据库中同一个人所有的人脸图像的线性组合表示。而对于数据库中其它人的脸,其线性组合的系数理论上为零。由于数据库中一般有很多个不同的人脸的多张图像,如果把数据库中所有的图像的线性组合来表示这张给定的测试人脸,其系数向量是稀疏的。因为除了这张和同一个人的人脸的图像组合系数不为零外,其它的系数都为零。

           上述模型导出了基于稀疏表示的另外一个很强的假设条件:所有的人脸图像必须是事先严格对齐的。否则,稀疏性很难满足。换言之,对于表情变化,姿态角度变化的人脸都不满足稀疏性这个假设。所以,经典的稀疏脸方法很难用于真实的应用场景。

           稀疏脸很强的地方在于对噪声相当鲁棒,相关文献表明,即使人脸图像被80%的随机噪声干扰,仍然能够得到很高的识别率。稀疏脸另外一个很强的地方在于对于部分遮挡的情况,例如戴围巾,戴眼镜等,仍然能够保持较高的识别性能。上述两点,是其它任何传统的人脸识别方法所不具有的。

     

    3. 稀疏人脸识别的实现问题

     

            一谈到识别问题,大家都会想到要用机器学习的方法。先进行训练,把训练的结果以模板的形式存储到数据库上;真实应用环境的时候,把测试样本经过特征提取之后,和数据库中的模板进行比对,查询得到一个最相似的类别作为识别结果。往往,机器训练的时间都超级长,几天,几个礼拜乃至几个月,那是常见的事情;识别的时间一般是很小的。典型的例如人脸检测问题。这是可以接受的,因为训练一般都是离线的。

     

            然而,基于稀疏分解的人脸识别是不需要训练的,或者说训练及其简单。基于稀疏表示的人脸识别,其稀疏表示用的字典直接由训练所用的全部图像构成,而不需要经过字典学习【也有一些改进算法,针对字典进行学习的】。当然,一般是经过简单的特征提取。由于稀疏表示的方法对使用什么特征并不敏感。故而,其训练过程只需要把原始图像数据经过简单的处理之后排列成一个很大的三维矩阵存储到数据库里面就可以了。

     

            关键的问题在于,当实际环境中来了一张人脸图像之后,去求解这张人脸图像在数据库所有图像上的稀疏表示,这个求解算法,一般比较耗时。尽管有很多的方法被提出,但是对于实时应用问题,依然没法满足。所以,问题的关键还是归结于L1范数最小化问题上来。

     

           L1范数最小化问题已经有很多种快速求解方法,这里主要包括有梯度投影Gradient Projection,同伦算法,迭代阈值收缩,领域梯度Proximal Gradient,增广拉格朗日方法,这几种方法都比正交匹配追踪算法OMP要高效的多。上述几种快速算法中,采用增广拉格朗日的对偶实现相比其它的快速算法要更好。最近流行的Spit Bregman算法也是不错的选择。

          

    4. 稀疏表示人脸识别的改进算法

     

             稀疏人脸识别算法要用于实际的系统,需要在两方面加以改进。首先,要突破人脸图像的对齐这一很强的假设。实际环境中的人脸往往是不对齐的,如何处理不对其的人脸是额待解决的问题。其实,是快速高效的优化算法。最后,也是最重要,实际环境中的应用往往训练样本很少。目前,研究人员已经取得了很多可喜的成果,下面分别予以介绍。

     

    4.1 CRC-RLS算法 

             CVPR2011 LeiZhang  Sparse Representatiion or Callaborative Representation: Which helps Face Recognition? 稀疏表示和协同表示,哪一个有助于人脸识别。该文作 者提出了用L2范数代替L1范数求解原问题。这样,能够非常快速的求解问题,实时性没有任何问题。但稀疏性不像原来的L1范数那样强。但作者对分类准则进行了改进,使得其分类性能几乎接近于原始L1范数最小化问题分类性能。为了对比,我把关键性算法列表如下:

     

                                               

                                             

             SRC算法求解的是方程1的解,而CRC-RLS算法则直接给出了表示系数的最小二乘解。二者另外一个主要的不同点在于计算残差的方式不一样,具体请注意上述方程2和方程10的不同点。后者的计算时间较前者最多情况下加速了1600倍。更多的实现细节可以参考原文。

           

       4.2  RSC算法 

                  CVPR2011 Meng Yang,Robost  Sparse Coding for Face Recognition. 鲁棒的稀疏编码算法。该文作者没有直接求解稀疏编码问题,而是求解Lasso问题,因为Lasso问题的解和稀疏编码的解是等价的。在传统的SRC框架下,编码误差使用L2范数来度量的,这也就意味着编码误差满足高斯分布,然而,当人脸图像出现遮挡和噪声污染的情况下,并非如此。在字典学习框架下,这样的字典是有噪声的。该文作者对原始Lasso问题进行改进,求解加权L1范数约束的线性回归问题。Lasso问题描述如下:

     

                                        

     

                   加权Lasso问题的目标函数描述如下:

                                                                 

                此算法的关键还在于权重系数的确定,文中采用的是logistic函数,而具体的实现则是通过迭代估计学习得到。该方法基于这样一个事实:被遮挡或噪声干扰的像素点赋予较小的权重,而其它像素点的权重相对较大。具体迭代算法采用经典的迭代重加权算法框架,当然内部嵌入的稀疏编码的求解过程。此算法在50%遮挡面积的情况下取得的更好更满意的结果。但是文中没有比较计算时间上的优略而直说和SRC框架差不多。

     

    4.3  RASL算法

            CVPR2010. Yigang Peng.  Robust batch Alignment of Images by Sparse and Low-Rank Decomposition. 这篇文章的作者在这篇文章中讨论的是用矩阵的低秩分解和稀疏表示来对齐人脸的问题。

     

    4.4  RASR算法

           PAMI2011 Wagner. Towards a Practical Face Recognition System:Robust Alignment and Illumination by Sparse Representation.该文的目的和RASL类似。

     

    4.5  MRR算法

              ECCV2012,Meng Yang. Efficient Misalignment-Robust Representation for Real Time Face Recognition.这篇文章又是Meng Yang的大作。这篇文章在充分分析RASR算法的基础上提出了一个高效的快速算法。该文对人脸对齐中求解变换矩阵T分为由粗到细的两个阶段。 这篇文章把稀疏脸应用在实际系统中推进了一大步。具体算法实现本人正在拜读之中。

     

            对稀疏脸的改进算法其实很多,例如分块SRC算法,表情鲁棒SRC等。但本人认为能够把它推向实际应用的却很少。上述文献是本人认为可圈可点的值得仔细拜读的文献

     

     

    1.提出问题:什么是稀疏表示 
    假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。 
    稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且A尽可能的稀疏。A便是X的稀疏表示。 
    书上原文为(将一个大矩阵变成两个小矩阵,而达到压缩

    为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表达形式,从而使学习任务得以简化,模型复杂度得以降低,通常称为‘字典学习’(dictionary learning),亦称‘稀疏编码’(sparse coding)”块内容

    表达为优化问题的话,字典学习的最简单形式为: 
    字典学习表达式
    其中xi为第i个样本,B为字典矩阵,aphai为xi的稀疏表示,lambda为大于0参数。 
    上式中第一个累加项说明了字典学习的第一个目标是字典矩阵与稀疏表示的线性组合尽可能的还原样本;第二个累加项说明了alphai应该尽可能的稀疏。之所以用L1范式是因为L1范式正则化更容易获得稀疏解。具体原因参看该书11.4章或移步机器学习中的范数规则化之(一)L0、L1与L2范数。字典学习便是学习出满足上述最优化问题的字典B以及样本的稀疏表示A(A{alpha1,alpha2,…,alphai})。L1正则化常用于稀疏,可以获得稀疏解。如下图表示,L1正则化交点在轴上,所得的解一般只是在某个轴上有实数,另外的轴为0,从而最终得到稀疏解。

    2.字典学习求解 (学习字典、稀疏表示)
    求解上述最优化问题的总体策略是,对字典B以及样本稀疏表示alphai交替迭代优化。即先初始化字典B,

    1.固定字典B对alphai进行优化。2.固定A对字典B进行优化。重复上述两步,求得最终B以及X的稀疏表示A。 
    其中第一步可采用与LASSO正则化相似的方法(如Proximal Gradient Desent法)进行求解,第二步可采用KSVD方法进行求解。具体步骤参看该书11.5章节内容

     

    1. 之前虽然听过压缩感知和稀疏表示,实际上昨天才正式着手开始了解,纯属新手,如有错误,敬请指出,共同进步。

    2. 主要学习资料是 Coursera 上 Duke 大学的公开课——Image and video processing, by Pro.Guillermo Sapiro 第 9 课。

    3. 由于对图像处理的了解也来自与该课程,没正经儿看过几本图像方面的书籍,有些术语只能用视频中的英文来表达,见谅哈!

     

    1. Denoising 与 MAP

    故事从 denoising 说起,话说手头上有一张含有噪音的图片 Lena,如何除去噪音得到好的 clean image 呢?

    对于上面的问题,用 x 值表示某个像素的灰度值,我们可以建立这样一个最小化的数学模型:

    其中, y 表示已知的观测值,也就是含有噪声的原图, x 表示要恢复成 clean image 的未知值。

    模型的第一项的直观作用就是,预测值 x 不要离观测值 y 太远。数学上的解释是, x 的取值概率可以看做是以 y 为均值的高斯分布,即图像带有 Gaussian noise, 第二项是规则化项。由来如下:假设 x 本来是就带有某种先验概率的分布,现在又已知观测值 y, 根据贝叶斯原理, 现在 x 的分布(后验)正比于先验概率分布与高斯分布的乘积。如果先验概率分布也正是指数分布,将乘积取负对数,就可以得到上述在机器学习里非常常见的 MAP 模型。

    现在的问题是:最好的先验 (prior) 究竟是什么? G(x) 应该取什么形式? 定义图像信号的最好空间是什么?

    在学术界,这方面的工作已经做得非常多,对这个问题的探讨过程可以比喻成类人猿向人类进化的过程:

    第一张图, prior 假设 clean image 能量尽量小, x 要尽可能地小。第二张图, prior 认为恢复后的图像要光滑,于是产生了 Laplacian 和 low energy 的结合,朝前进化了一步。第三张图,prior 认为要考虑 edges 是不光滑滴,需要不同情况不同处理…… Sparse and Redundant 是正在讨论的问题,目前是最新的进化版本,而后面也有一些算法,虽然也成功进化成人类,可惜太胖了,行动不便—— computationally expensive and difficult。 Sparse modeling 的先验究竟是什么?要回答这个问题,还需要了解一些基础概念。

     

    2. Sparsity and Lp Norm

    1. How to Represent Sparsity

      表示一个向量的稀疏程度可以用 Lp norm, 对于 alpha 向量的某一个元素为 x, Lp norm 的计算公式和函数图像如下:

      我们希望不管 x 多大,它非零的惩罚是相同的,L0 norm 正好满足这个要求,它表示的意思是数出 alpha 向量中非零的个数

    2. Sparse Modeling of Signal

      一张 8×8 的图片,可以表示成 64 维的向量 x ,如何进行稀疏表示?下图中假设 N = 64:

      左边矩阵 D 是字典矩阵,由 K 个 N 维的列向量组成。 根据 K 与 N 的关系,又可以划分为:

      1. > N: over-complete, 这种情况在稀疏表示里面最常见

      2. K = N: complete, 例如傅里叶变换和 DCT 变换都是这种情况

      3. < N: under-complete

     

    中间列向量 alpha 是一个稀疏向量,特点是非零项很少,图中只有三个非零项,代表 D 矩阵对应行向量的线性组合。

    最后 x 向量表示恢复后的向量。

    atoms 表示 D 的列向量

    实际上 DCT 变换也可以看做是一种稀疏表示,它的 D 向量是由固定的且刚好完备的正交基向量组成,并且 alpha 向量也具有一定稀疏性。

    对于上图,假设 D 矩阵 K > N,并且是满秩的,那么对于任意个 N 维的向量 b (图中是 x ),肯定有 Ax = b。现在加入 Lp norm 的约束条件,限制只能用少量的 A 的列向量 (atoms 作为基,向量 b 就被固定在某个 span 内,成为了一个 Lp 优化问题:

    用紫色表示平面,用青色表示 norm 取同一个值的球形(等高线),问题如下:在平面 Ax = b 平面内选出 norm 最小的最优解

    当 p >= 1时,norm ball和平面的交点有多个。这是一个凸优化问题,可以用拉格朗日乘子来解决这个问题。

    当 0 < p < 1 时, norm ball 可行解十分稀疏,是一个非凸优化问题,解决这类问题很难,但是却有很好的稀疏性。

    当 p = 0 时, norm ball 上的点除了坐标轴,其他部分无限收缩,与平面的交点在某一个坐标轴上,非零系数只有一个。

    回到第一节将的 MAP 模型, Sparse Modeling 模型就是非零系数限制在 L 个之内(意味着解在至多 L 个 atoms 组成的 span 里),尽可能接近平面:

    这样,我们用少量的 atoms 组合成真实信号,而 noise cannot be fitted very well, 在投影到低维空间的过程中起到了降噪的作用。 

     

     

    3. Some Issues:

     模型可以改成 L0 norm 的形式和其他形式来计算或者求近似吗?

    解集 alpha 向量是唯一的吗?我们可以求它的近似吗?如果可以,如何估计近似程度?

    应该采用什么样的字典矩阵 D 才能较好地消除噪声?字典 D 如何确定?

    展开全文
  • 稀疏表达

    2017-08-04 21:56:53
    稀疏表达是近年来SP, ML, PR,CV领域中的一大热点,文章可谓是普天盖地,令人目不暇给。老板某门课程的课程需要大纲,我顺道给扩展了下,就有了这个上中下三篇介绍性质的东西。遗憾的是,我在绝大多数...

    转载自 lycdx的博客  http://blog.sina.com.cn/s/blog_6d0e97bb01015wol.html

    感谢大神的分享!收获很多!部分图片失效不能显示,请见谅。

     

    稀疏表达是近年来SP, ML, PR,CV领域中的一大热点,文章可谓是普天盖地,令人目不暇给。老板某门课程的课程需要大纲,我顺道给扩展了下,就有了这个上中下三篇介绍性质的东西。遗憾的是,我在绝大多数情况下实在不算是一个勤快的人,这玩意可能充满bug,更新也可能断断续续,尽请诸位看官见谅了。顺道一提,ICCV09有一个相关的tutorial

    据传博文里公式数量和其人气是成反比例关系的,一个公式可以驱散50%的读者,我写完这个(上)之后点了点公式数量,觉得大约是要无人问津了。所以,在介绍稀疏表达之前,让我们先来展示下其在computervision中的应用,吸引下眼球。

    首先是图像恢复(以前有人贴过Obama还记得不),由左侧图像恢复出右侧结果
     

    然后是类似的图像inpainting
     

    然后是图像去模糊,左上为输入模糊图像,右下为输出清晰图像及估计的相机运动(其实是PSF),中间均为迭代过程:

     

    再然后是物体检测(自行车),左侧输入图像,中间为位置概率图,右侧为检测结果
     

    当然我个人还推荐Yi Ma的sparseface,这个在对抗噪声的效果上很棒,比如下图中左侧的那张噪声图像(你能辨认是哪位不?这方法可以!)
     

    且说sparserepresentation这个概念,早在96-97年的时候就火了一把。最著名的大约要数Nature上的某篇文章,将稀疏性加入leastsquare的regularization,然后得到了具有方向特性图像块(basis)。这样就很好的解释了初级视皮层(V1)的工作机理,即对于线段的方向选择特性。几乎同一时期,著名的LASSO算法也被发表在J. Royal. Statist. Soc B。Lasso比较好的解决了least square (l2 norm) error +l1 norm regularization的问题。然而,这个时候绝大多数人没有意识到(或者没法解决)这l1norm和稀疏性之间的联系。其实早在这之前,Osher等人提出的Total Variation (TV)已经包含了l1norm的概念了,只不过TV原本是连续域上的积分形式。(啥?你不知道Osher…想想Level Set吧)

    在进入现代的压缩感知、稀疏表示这一课题前,让我们来首先回顾下这一系列问题的核心,即线性方程组Sparse <wbr>Representation,其中矩阵Sparse <wbr>Representation,通常而言是满秩的。向量Sparse <wbr>Representation。现在已知,求解。学过线性代数的同学可能都会说:这个不难啊,因为Sparse <wbr>Representation,故而这个方程组是欠定的,所以有无穷多组解啊,咱还可以算算基础解系啥的…

    但是如果我们希望其解尽可能的稀疏:比如Sparse <wbr>Representation(即中非零元个数)尽可能的小。那么问题就会变得比较微妙了,下图给出了问题的形象示意。

    换言之给定m维空间中一组过完备的基Sparse <wbr>Representation,如何选择最少个数的基向量,重构给定向量Sparse <wbr>Representation,其严格定义可以写成
    Sparse <wbr>Representation

    时光之轮播快到2003~2004年,Donoho &Elad做了一个很漂亮的证明,如果矩阵满足某种条件,具体而言:

     

    Sparse <wbr>Representation

     

    那么上文提及的0范数优化问题具有唯一的解。这里的Sparse <wbr>Representation是个比较诡异(请允许我使用这词)的定义:最小的线性相关的列向量集所含的向量个数,英文为spark(吐槽:明白了么,我做TA的时候就被这个问题问倒了)。本来想在这个概念上唠叨两句,后来发现了Elad的一个talk,清晰明了。

    即便是唯一性得到了证明,求解这个问题仍然是NP难的。科研的车轮滚滚向前,转眼到了2006年,传奇性的华裔数学家TerrenceTao登场了,Tao和Donoho的弟子Candes合作证明了在RIP条件下,0范数优化问题与以下1范数优化问题具有相同的解:
    Sparse <wbr>Representation
    其中RIP条件,即存在满足某种条件的(与N相关)常数:Sparse <wbr>Representation

    Sparse <wbr>Representation
    RIP条件是对于矩阵列向量正交性的一种衡量(此处咱就不细说了)。其实早在1993年Mallat就提出过MutualCoherence对于正交性进行度量,并提出了下文还要提及的matching pursuit方法。

    实际上以上的1范数优化问题是一个凸优化,故而必然有唯一解,至此sparserepresentation的大坑初步成型。总结一下:
    1. 如果矩阵满足Sparse <wbr>Representation,则0范数优化问题有唯一解。
    2. 进一步如果矩阵满足RIP条件,则0范数优化问题和1范数优化问题的解一致。
    3. 1范数优化问题是凸优化,故其唯一解即为0范数优化问题的唯一解。

    进一步可以考虑含噪声情况,即
    Sparse <wbr>Representation
    可以得到相似的结果,有兴趣的同学可以查阅相关文献。理论坑只有大牛能挖,但一般人也能挖挖这个优化算法啊,于是SP、ML、CV邻域里都有做这个优化算法的,这个出招可就真是五花八门了。据我所知,大致可两大类:
    第一类: 直接优化
    Sparse <wbr>Representation
    一般的方法是greedy algorithm,代表有Matching Pursuit, Orthogonal MatchingPursuit,这类方法循序的(sequentially)选择字典的原子(atoms),这类方法的过程一般包括求信号与字典中每一列(atom)的内积,还包括了一些最小二乘法的方法。
    第二类,将0-norm替换为1-norm问题,使之变成一个凸优化问题,即优化
    Sparse <wbr>Representation
    如果已知拉格朗日乘子,优化无约束凸优化问题
    Sparse <wbr>Representation
    解这个的方法现在基本上soft thresholding的方法一统天下,常见的有coordinate descent, BregmanIteration (又是Osher),BP等
    4. 如果未知拉格朗日乘子,优化
    Sparse <wbr>Representation
    这类方法又叫Homotopy,可以认为是3的扩展。核心出发点是objective function是λ的分段线性函数。

    除此之外,还有利用p范数逐次逼近0范数的方法等等,此处不再赘述。顺道说一句,稀疏表示在不同的领域连名称都不同,搞信号的管这个叫basispursuit,搞统计的叫L1regularization….然后,让我们把话题拉回到Nature的那篇文章:如果我们不知道矩阵,只知道一堆向量Sparse <wbr>Representation。我们应当如何构造,使得在这一字典(矩阵)下的Sparse <wbr>Representation表示最稀疏?类比以上过程,这个问题被称为DictionaryLearning,可以写成以下优化问题:
    Sparse <wbr>Representation

    这个东西可就相对麻烦了,最关键的是这个优化不是凸的(优化变量相乘)。所以一般的想法是blockdescent:首先固定Sparse <wbr>Representation,优化Sparse <wbr>Representation(相当于多个独立的1范数优化问题);其次将计算出的Sparse <wbr>Representation固定,优化Sparse <wbr>Representation,这就是一个(可能带约束)的leastsquare问题。如此反复,直到算法收敛到某个(局部)极小值。实际上解这个问题的方法目前有三种:efficient sparsecoding algorithm NIPS 06; K-SVD tsp 06; Online dictionary learningfor sparse coding, ICML 09 & JMLR10。前两种都是batch的方法,后一种是online的。

    展开全文
  • 为了把压缩传感技术应用到变换域非稀疏信号中,提出了一种能够改善信号非稀疏表达稀疏性的新方法。该方法采用可移动窗口函数把信号在变换域中的非稀疏表达截取成多个窗截表达,只要控制每个窗口函数宽度远小于信号的...
  • 稀疏表示稀疏分解

    2014-04-24 15:07:56
    详细的讲述了信号的稀疏表示稀疏分解问题,很适合做开题报告。
  • 稀疏表示以及字典学习

    万次阅读 多人点赞 2017-03-29 09:22:02
    1.什么是稀疏表示:  假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。 稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一...

    1.什么是稀疏表示:

                假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。 稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且A尽可能的稀疏。A便是X的稀疏表示。

            南大周志华老师写的《机器学习》这本书上原文:“为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表达形式,从而使学习任务得以简化,模型复杂度得以降低,通常称为‘字典学习’(dictionary learning),亦称‘稀疏编码’(sparse coding)”块内容。

            表达为优化问题的话,字典学习的最简单形式为: 


     
    其中xi为第i个样本,B为字典矩阵,aphai为xi的稀疏表示,lambda为大于0参数。 

          上式中第一个累加项说明了字典学习的第一个目标是字典矩阵与稀疏表示的线性组合尽可能的还原样本;第二个累加项说明了alphai应该尽可能的稀疏。之所以用L1范式是因为L1范式正则化更容易获得稀疏解。具体原因参看该书11.4章或移步机器学习中的范数规则化之(一)L0、L1与L2范数。字典学习便是学习出满足上述最优化问题的字典B以及样本的稀疏表示A(A{alpha1,alpha2,…,alphai})。

    2.字典学习:

           该算法理论包含两个阶段:字典构建阶段(Dictionary Generate)和利用字典(稀疏的)表示样本阶段(Sparse coding with a precomputed dictionary)。这两个阶段(如下图)的每个阶段都有许多不同算法可供选择,每种算法的诞生时间都不一样,以至于稀疏字典学习的理论提出者已变得不可考。笔者尝试找了Wikipedia和Google Scolar都无法找到这一系列理论的最早发起人。

    技术分享

    出处:http://www.mamicode.com/info-detail-1568956.html

            字典学习的第一个好处——它实质上是对于庞大数据集的一种降维表示。第二,正如同字是句子最质朴的特征一样,字典学习总是尝试学习蕴藏在样本背后最质朴的特征(假如样本最质朴的特征就是样本最好的特征).稀疏表示的本质:用尽可能少的资源表示尽可能多的知识,这种表示还能带来一个附加的好处,即计算速度快我们希望字典里的字可以尽能的少,但是却可以尽可能的表示最多的句子。这样的字典最容易满足稀疏条件。也就是说,这个“字典”是这个“稀疏”私人订制的。

    第二部分 稀疏字典学习的Python实现

    用Python实现稀疏字典学习需要三个前提条件

    1.安装NumPy

    2.安装SciPy

    3.安装Python机器学习工具包sklearn

    为了避免过于麻烦的安装,这里我干脆建议诸位读者安装Python的商业发行版Anaconda,内含python集成开发环境和数百个常用的python支持包。具体安装过程和使用细节参见我的博客附录D Python接口大法。

    样例一:图片的稀疏字典学习

    这段代码来源于Python的Dictionary Learning的官方文献教材,主要用途是教会用户通过字典学习对图片进行滤波处理。

    step1:首先是各种工具包的导入和测试样例的导入

    from time import time
    
    import matplotlib.pyplot as plt
    import numpy as np
    import scipy as sp
    
    from sklearn.decomposition import MiniBatchDictionaryLearning
    from sklearn.feature_extraction.image import extract_patches_2d
    from sklearn.feature_extraction.image import reconstruct_from_patches_2d
    from sklearn.utils.testing import SkipTest
    from sklearn.utils.fixes import sp_version
    
    if sp_version < (0, 12):
        raise SkipTest("Skipping because SciPy version earlier than 0.12.0 and "
                       "thus does not include the scipy.misc.face() image.")
    try:
        from scipy import misc
        face = misc.face(gray=True)
    except AttributeError:
        # Old versions of scipy have face in the top level package
        face = sp.face(gray=True)
    

    第1行:导入time模块,用于测算一些步骤的时间消耗

    第3~5行:导入Python科学计算的基本需求模块,主要包括NumPy(矩阵计算模块)、SciPy(科学计算模块)和matplotlib.pyplot模块(画图)。有了这三个模块,Python俨然已是基础版的Matlab。

    第7~11行:导入稀疏字典学习所需要的函数,下面分行解释

    第7行:导入MiniBatchDictionaryLearning,MiniBatch是字典学习的一种方法,这种方法专门应用于大数据情况下字典学习。当数据量非常大时,严格对待每一个样本就会消耗大量的时间,而MiniBatch通过降低计算精度来换取时间利益,但是仍然能够通过大量的数据学到合理的词典。换言之,普通的DictionaryLearning做的是精品店,量少而精,但是价格高。MiniBatchDictionaryLearning做的是批发市场,量大不精,薄利多销。

    第8行:导入碎片提取函数extract_patches_2d。调用该函数将一张图片切割为一个一个的patch。如果一张图片相当于一篇文章的话,那么该函数的目标就是把文章中的每个句子都找到,这样才方便提取蕴藏在每个句子中的字。图片和patch的关系如下图所示:

    技术分享

    整张头像的照片是个图片,通过对图片的分割可以将图片分割为一个一个的小块,也就是一个个Pitch。如果对pitch仍然不了解,只好请你看这个:http://blog.csdn.net/zouxy09/article/details/8775488

    第9行:导入图片复原函数reconstruct_from_patches_2d,它可以通过patch复原一整张图片。

    第10行:导入测试工具nose下的异常抛出函数SkipTest

    第11行:导入SciPy版本检测函数sp_version用于检测版本高低,版本低于0.12的SciPy没有我们需要的样本测试用例

    第13~15行:检测SciPy版本,如果版本太低就抛出一个异常。程序运行结束

    第16~21行:尝试打开样本测试用例,如果打不开就抛出一个异常。

    step2:通过测试样例计算字典V

    # Convert from uint8 representation with values between 0 and 255 to
    # a floating point representation with values between 0 and 1.
    face = face / 255.0
    
    # downsample for higher speed
    face = face[::2, ::2] + face[1::2, ::2] + face[::2, 1::2] + face[1::2, 1::2]
    face = face / 4.0
    height, width = face.shape
    
    # Distort the right half of the image
    print(‘Distorting image...‘)
    distorted = face.copy()
    distorted[:, width // 2:] += 0.075 * np.random.randn(height, width // 2)
    
    # Extract all reference patches from the left half of the image
    print(‘Extracting reference patches...‘)
    t0 = time()
    patch_size = (7, 7)
    data = extract_patches_2d(distorted[:, :width // 2], patch_size)
    data = data.reshape(data.shape[0], -1)
    data -= np.mean(data, axis=0)
    data /= np.std(data, axis=0)
    print(‘done in %.2fs.‘ % (time() - t0))
    print(‘Learning the dictionary...‘)
    t0 = time()
    dico = MiniBatchDictionaryLearning(n_components=100, alpha=1, n_iter=500)
    V = dico.fit(data).components_
    dt = time() - t0
    print(‘done in %.2fs.‘ % dt)
    
    plt.figure(figsize=(4.2, 4))
    for i, comp in enumerate(V[:100]):
        plt.subplot(10, 10, i + 1)
        plt.imshow(comp.reshape(patch_size), cmap=plt.cm.gray_r,
                   interpolation=‘nearest‘)
        plt.xticks(())
        plt.yticks(())
    plt.suptitle(‘Dictionary learned from face patches\n‘ +
                 ‘Train time %.1fs on %d patches‘ % (dt, len(data)),
                 fontsize=16)
    plt.subplots_adjust(0.08, 0.02, 0.92, 0.85, 0.08, 0.23)#left, right, bottom, top, wspace, hspace

    第3行:读入的face大小在0~255之间,所以通过除以255将face的大小映射到0~1上去

    第6~7行:对图形进行采样,把图片的长和宽各缩小一般。记住array矩阵的访问方式      array[起始点:终结点(不包括):步长]

    第8行:图片的长宽大小

    第12行:将face的内容复制给distorted,这里不用等号因为等号在python中其实是地址的引用。

    第13行:对照片的右半部分加上噪声,之所以左半部分不加是因为教材想要产生一个对比的效果

    第17行:开始计时,并保存在t0中

    第18行:tuple格式的pitch大小

    第19行:对图片的左半部分(未加噪声的部分)提取pitch

    第20行:用reshape函数对data(94500,7,7)进行整形,reshape中如果某一位是-1,则这一维会根据(元素个数/已指明的维度)来计算这里经过整形后data变成(94500,49)

    第21~22行:每一行的data减去均值除以方差,这是zscore标准化的方法

    第26行:初始化MiniBatchDictionaryLearning类,并按照初始参数初始化类的属性

    第27行:调用fit方法对传入的样本集data进行字典提取,components_返回该类fit方法的运算结果,也就是我们想要的字典V

    第31~41行:画出V中的字典,下面逐行解释

    第31行:figsize方法指明图片的大小,4.2英寸宽,4英寸高。其中一英寸的定义是80个像素点

    第32行:循环画出100个字典V中的字

    第41行:6个参数与注释后的6个属性对应

    运行程序,查看输出结果:

    技术分享

     

    step3:画出标准图像和真正的噪声,方便同之后字典学习学到的噪声相比较

    def show_with_diff(image, reference, title):
        """Helper function to display denoising"""
        plt.figure(figsize=(5, 3.3))
        plt.subplot(1, 2, 1)
        plt.title(‘Image‘)
        plt.imshow(image, vmin=0, vmax=1, cmap=plt.cm.gray,
                   interpolation=‘nearest‘)
        plt.xticks(())
        plt.yticks(())
        plt.subplot(1, 2, 2)
        difference = image - reference
    
        plt.title(‘Difference (norm: %.2f)‘ % np.sqrt(np.sum(difference ** 2)))
        plt.imshow(difference, vmin=-0.5, vmax=0.5, cmap=plt.cm.PuOr,
                   interpolation=‘nearest‘)
        plt.xticks(())
        plt.yticks(())
        plt.suptitle(title, size=16)
        plt.subplots_adjust(0.02, 0.02, 0.98, 0.79, 0.02, 0.2)
    
    show_with_diff(distorted, face, ‘Distorted image‘)

    程序输出如下图所示:

    技术分享

     

    step4:测试不同的字典学习方法和参数对字典学习的影响

    print(‘Extracting noisy patches... ‘)
    t0 = time()
    data = extract_patches_2d(distorted[:, width // 2:], patch_size)
    data = data.reshape(data.shape[0], -1)
    intercept = np.mean(data, axis=0)
    data -= intercept
    print(‘done in %.2fs.‘ % (time() - t0))
    
    transform_algorithms = [
        (‘Orthogonal Matching Pursuit\n1 atom‘, ‘omp‘,
         {‘transform_n_nonzero_coefs‘: 1}),
        (‘Orthogonal Matching Pursuit\n2 atoms‘, ‘omp‘,
         {‘transform_n_nonzero_coefs‘: 2}),
        (‘Least-angle regression\n5 atoms‘, ‘lars‘,
         {‘transform_n_nonzero_coefs‘: 5}),
        (‘Thresholding\n alpha=0.1‘, ‘threshold‘, {‘transform_alpha‘: .1})]
    
    reconstructions = {}
    for title, transform_algorithm, kwargs in transform_algorithms:
        print(title + ‘...‘)
        reconstructions[title] = face.copy()
        t0 = time()
        dico.set_params(transform_algorithm=transform_algorithm, **kwargs)
        code = dico.transform(data)
        patches = np.dot(code, V)
    
        patches += intercept
        patches = patches.reshape(len(data), *patch_size)
        if transform_algorithm == ‘threshold‘:
            patches -= patches.min()
            patches /= patches.max()
        reconstructions[title][:, width // 2:] = reconstruct_from_patches_2d(
            patches, (height, width // 2))
        dt = time() - t0
        print(‘done in %.2fs.‘ % dt)
        show_with_diff(reconstructions[title], face,
                       title + ‘ (time: %.1fs)‘ % dt)
    
    plt.show()

    第3行:提取照片中被污染过的右半部进行字典学习。

    第10~16行:四中不同的字典表示策略

    第23行:通过set_params对第二阶段的参数进行设置

    第24行:transform根据set_params对设完参数的模型进行字典表示,表示结果放在code中。code总共有100列,每一列对应着V中的一个字典元素,所谓稀疏性就是code中每一行的大部分元素都是0,这样就可以用尽可能少的字典元素表示回去。

    第25行:code矩阵乘V得到复原后的矩阵patches

    第28行:将patches从(94500,49)变回(94500,7,7)

    第32行:通过reconstruct_from_patches_2d函数将patches重新拼接回图片

    该程序输出为四中不同转换算法下的降噪效果:

     技术分享技术分享

    技术分享技术分享

     

    第二部分代码出处:

    http://www.mamicode.com/info-detail-1568956.html

    展开全文
  • 稀疏表达论文

    2014-03-11 17:34:55
    任何一种图像总有特征明显的数学表示,怎么才能最简单表达这幅图片,是稀疏表达的理论知识。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,131
精华内容 39,652
关键字:

稀疏表达