稀疏表示

基于Gabor冗余字典的稀疏表示10级硕士汪俊一、稀疏表示的研究史和一些应用二、稀疏表示的核心问题三、冗余字典的构造四、新的知识的引入稀疏表示研究史：1、1959年，Davidhubel和TorestenWiesel通过对猫的视觉条纹皮层简单细胞感受野的研究得出这样一个结论：视觉皮层V1区神经元的感受野能够对视觉感知信息产生一种“稀疏表示”。2、1988年，Michison明确提出了神经稀疏编码的概念，然后又牛津大学的E.T.Roll等人正式引用。3、1996年，B.A.Olshausen和D.J.Field在Nature上发表了一篇题为“Emergenceofsimple-cellreceptivefieldpropertiesbylearningasparsecodefornatureimages”的重要论文，他们的实验结果表示人类视觉系统只用最少的视觉神经元就能捕获自然场景中的关键信息。在1997年，这两位又提出了超完备基的稀疏编码算法。稀疏表示的应用图像恢复，又左侧图像恢复出右侧结果图像修补，左侧图像修补得到右侧结果图像去模糊左上为输入模糊图像，右下为输出清晰图像，中间均为迭代过程物体检测自行车，左侧输入图像，中间为位置概率图，右侧为检测结果工具包一、稀疏表示的应用二、稀疏表示的核心问题三、冗余字典的构造四、新的知识的引入SparseRepresentation问题的核心假设是一个信号:假设，是一个基向量的集合，我们称D为字典。mxRnmnRddD*1],...,[如果存在一个n维的稀疏向量（一个向量中的非零元素占全部元素的百分比很小）α，使得X≈D*α，也就是用字典D中少数几个原子，就能够近似的将X表示出来。可能会觉得这是个很简单的问题，但是如果要求向量α尽可能的稀疏，那么这个问题就不一样了。更直观的稀疏表示示意图上面的问题：给定一组过完备的字典，如何选择最少个数的原子，重构给定向量X，其严格定义可以写成一个带约束条件的求解问题α：时间来到2003~2004年，Donoho&Elad做了一个证明，如果矩阵D满足某种条件，具体而言是：上面的符号表示：最小的线性相关的列向量所含的向量个数。那么对于0范数优化问题就会有一个唯一的解。可即便是证明了唯一性，求解这个问题仍然是NP-Hard。XDts..||||min0nmRD*0||||2)(D时间继续来到2006年，华裔的数学家TerrenceTao出现，Tao和Donoho的弟子Candes合作证明了在RIP条件下，0范数优化问题与以下1范数优化问题具有相同的解：其中的RIP条件，即存在满足某种条件的（与N相关）常数μ，N：RIP条件是对于矩阵D列向量正交性的一种衡量。其实早在1993年Mallat就提出过MutualCoherence对于正交性机型度量，还提出了matchingpursuit方法。XDts..||||min1NNDN0222222||||||||)1(||||||||)1(到此sparserepresentation的理论坑就被大牛挖出来了，总结一下：1、如果矩阵满足，则0范数优化问题有唯一解；2、进一步如果矩阵A满足RIP条件，则0范数优化问题和1范数优化问题一致；3、1范数优化问题是凸优化，故其唯一解即为0范数优化问题的唯一解。0||||2)(D对于上面的公式可以进一步考虑含噪声的情况，即：目前，用于求解这类稀疏表示最优化问题的稀疏优化方法主要分为贪婪算法和全局优化方法。贪婪算法主要包括：匹配追踪(MP)、正交匹配追踪(OMP)。全局优化方法主要包括：基追踪算法(BP)、及追踪去噪算法(BPDN)。||-||..||||min0XDts人物介绍DavidDonoho：斯坦福利亚大学~donoho/index.htmlEmmanuelCandes：斯坦福利亚大学教授~candes/TerenceTao，24岁的时候就于洛杉矶加利福尼亚大学担任教授。~tao/一、稀疏表示的应用二、稀疏表示的核心问题三、冗余字典的构造四、新的知识的引入我们接下来谈另外一个问题：上面的优化问题中的已知条件包括了矩阵D和向量X，通过这两个条件求稀疏向量α。但是如果我们不知道矩阵D，只知道一堆向量{xi}，那么我们应该如何构造D，使得这一字典下{xi}的表示最稀疏？这个问题被称为DictionaryLearning。其实对于字典的构造，有两个大类：参数化方法和基于学习的方法。参数化的方法：参数化的方法通过对某种分析函数的参数进行冗余采样来构造一些原子组成字典。基于参数化的方法，介绍怎么样利用Gabor函数来生成原子构成字典：人类的视觉系统能够自适应于自然环境中输入刺激的统计特性，视觉皮层中的大部分神经元只对特定的刺激才具有最优响应，通过视觉皮层中不同感受野的神经元的层次处理实现了对于自然图像的稀疏编码。人类神经元对于外部刺激的响应特性如下图：输入的刺激即照片不一样，则响应神经元也不一样模拟人类视觉系统的感知机制来形成对于图像的稀疏表示，将字典中的每个原子看作一个神经元，整个字典则对应人类视觉皮层中神经元整体，并且字典中原子具有类似视觉皮层中神经元的响应特性：空间局部性、方向性和频率选择性。Daugman采用二维Gabor函数作为简单细胞的感受野函数，刻画其响应特性。)2cos()2exp()(2222xykxKgsin)(cos)(x00yyxxcos)(sin)(00yyxxyGabor函数在上面的Gabor函数中有七个参数，根据参数化的方法来构造字典。方向不变，尺度改变尺度不变，方向改变上面的那张图，只是涉及到尺度和方向的变化，在Gabor函数中是有7个参数的，对这7个参数在一定参数范围内进行冗余采样，这样就会生成一地数量的原子构成冗余的Gabor字典。字典构造完成，接下来进行稀疏分解。贪婪算法中的MP是一种迭代的递归算法，每一步从字典D中选择一个与残差信号r（初始为原始图像）最匹配的原子，每一步都使得信号的逼近更为优化。MP的目标函数L表示非零个数的上限算法步骤：1、2、3、while&do4、选择与残差信号r最匹配的原子5、更新残差和α：6、endwhileLtsDX022R||||..||-||minn00，X)(残差L0||||Tinidi,...,1maxargˆiTiTidddiiˆˆˆ)(]ˆ[]ˆ[α=（0，0，0）α=（0，0，0），d3单位长度向量。α=（0，0，0）α=（0，0，0.75）α=（0，0，0.75）α=（0，0，0.75）α=（0，0.24，0.75）α=（0，0.24，0.75）α=（0，0.24，0.65）基于学习的方法：是采用对训练样本进行自适应学习的方式来构造字典。这类方法将字典的构造问题转化为某个目标函数的最优化问题，这个目标函数一般由重构误差和稀疏性组成。利用KSVD方法来训练字典。1||||||-||minXD对于上面求内积找最匹配原子的一步，当时鉴于原子个数太多，就想了可否在这里做个优化，就用了PSO（粒子群优化算法）查找最优原子，这个比遗传算法要简单，我觉得这个算法也还挺有意思的。一、稀疏表示的应用二、稀疏表示的核心问题三、冗余字典的构造四、新的知识的引入1、对X基于字典D稀疏表示结果α进行一些处理：空间金字塔的引入&最大池输出方法2、加入监督学习的字典训练这里的字典学习的目的是为了分类，已知一组训练样本，其label也人工给定，首先我们需要训练字典。在基于学习的方法中我们给定了一个目标函数：1||||||-||minXD但是训练字典的目的不一样，所以目标函数形式上也有点不同：对于上面目标函数的求解，使用的是astochasticwaywithgradientdescent（随机的梯度下降方法），还有一种梯度下降方法是batchgradientdecent。如果训练样本过大，相比之下前者的速度会快点。斯坦福大学机器学习课程第二课，监督学习的应用与梯度下降。资料推荐：09年ICCV上的指南谢谢！