稀疏表示分类 - CSDN
  • 稀疏表示分类(SRC)

    千次阅读 2018-03-27 11:20:34
    转载 2015年11月07日 10:51:57标签:压缩感知...基于超完备字典的信号稀疏分解是一种新的信号表示理论,其采用超完备的冗余函数系统代替传统的正交基函数,为信号自适应的稀疏扩展提供了极大的灵活性。稀疏分解可以...


    转载 2015年11月07日 10:51:57

    基于超完备字典的信号稀疏分解是一种新的信号表示理论,其采用超完备的冗余函数系统代替传统的正交基函数,为信号自适应的稀疏扩展提供了极大的灵活性。稀疏分解可以实现数据压缩的高效性,更重要的是可以利用字典的冗余特性捕捉信号内在的本质特征。

    信号稀疏分解的基本思想是:使用超完备的冗余函数字典作为基函数,字典的选择尽可能地符合被逼近信号的结构,字典中的元素被称为原子。利用贪婪算法或者自适应追踪算法,从字典中找到具有最佳线性组合的很少的几项原子来表示一个信号,也称作高度非线性逼近。本文主要利用字典的冗余特性可以更好地捕捉信号本质特征这一特点,提出数据分类算法SRC。实验结果表明,SRC算法在分类准确性上优于SVM和Fld算法,不平衡数据集的分类实验结果显示了该算法的鲁棒性。

     

    几个专业名词解析:

    原子:字典的列向量。

    完备字典与过完备字典:如果字典D中的原子恰能够张成n维的欧式空间,则字典D是完备的。如果m》n,字典D是冗余的,同时保证还能张成n维的欧式空间,则大字典D是过完备的。

    面对稀疏表示模型,有三个关键问题需要解决,如下:

    1.如何有效获取图像在字典中下最稀疏的分解系数。2.如何设计与构建有效的图像稀疏表示字典。3.如何将图像稀疏表示模型应用于具体的图像处理反问题中。

     

    首先,Dictionary是一种sparse representation(稀疏表示)的模型。比如你的数据是y,字典是D,y=Dx,其中x是稀疏的。如果你的D是方阵或者长方形矩阵(正交矩阵除外),字典很可能是不确定的。相反的,如果你的D是个fat matrix 冗余矩阵,形象地讲,你拥有多于必要的列来表达这个数据(冗余)。这样的字典称为Overcomplete dictionary。这种字典的优势是更有利于表达highly diversified(高度多元化)的数据(图像)。

     

    特征学习的过程中,假设学习的码书D的大小为M。每个码字的维数为N。每个原始特征Yi的维数也为N。假设原始特征投影到码书上以后的特征向量是Xi(M维的矢量),那么用D和Xi对Yi重建的过程就是:Yi=D*Xi。 

     

     

    coding的过程就变成了已知Yi和D,求Xi的过程了。显然这是一个非齐次方程组求解的问题,方程组有解的条件是rank(D)≤M,其中取等号时方程组有唯一解。过完备的定义是M>>N,所以此时 rank(D)≤N<<M,此时方程组有无穷多解。(你可能会问,这和最小化平方误差为目标函数不一样啊!其实求个导,就变成这个方程组了。)这就是过完备造成的问题了。怎么办呢?办法就是对Xi做约束------稀疏的约束,这样Xi就有唯一解了。这就是需要加约束的原因。而为什么是稀疏的约束,这个再谈。

    特征选择的过程,也是一样的。假设此时有n个样本,每个样本有个measurement(这个measurement可以是regression中的output,也可以是classification中的label)。每个样本的特征是p维的,n个样本的特征组成n*p的矩阵A。目标是对这p维特征做一个选择,选择的系数用x记录。此时将如下图所示:

     

    这与第一个图是等价的,特征选择过程中的over-complete是指p>>n,不加约束的情况下x将有无穷多组解,所以和特征学习一样,加系数的约束。xi为0表示相应的特征不被选择。(而xi<0,等价于取一个|xi|,而将相应的特征的值取负号。)

     

    如果measurement不是一维的咋办?比如multi-label的问题。我猜测把x的列维数也扩展成相应大小,然后根据label之间的correlation加低秩等约束吧。

     

    稀疏表示是最近几年信号处理领域的热点之一,简单来说,它其实是一种对原始信号的分解过程,该分解过程借助一个事先得到的字典(也有人称之为过完备基,overcomplete basis,后面会介绍到),将输入信号表示为字典的线性近似的过程。即:

    展开全文
  • 稀疏表示(Sparse representation)原理理解

    万次阅读 多人点赞 2019-03-21 16:21:41
    最近他很想了解我最近在搞的东西,在此,就发一片博客来简单说明一下自己最近研究的稀疏表示算法。因为本人能力有限,我会尽自己最大的努力将稀疏表示算法讲的清楚简单。此外,博客中避免不了会有一些差错,希望各位...

    谨以此文献给我最好的朋友

    我有一个十分好学的朋友,一起度过了三年的大学时光(大二认识的),最终他选择了工作,我继续读书。最近他很想了解我最近在搞的东西,在此,就发一片博客来简单说明一下自己最近研究的稀疏表示算法。因为本人能力有限,我会尽自己最大的努力将稀疏表示算法讲的清楚简单。此外,博客中避免不了会有一些差错,希望各位大佬理解。

    正文

    稀疏表示(Sparse Representation)也叫作稀疏编码(Sparse Coding),就是用字典中元素的线性组合去表示测试样本。

    我们现在考虑图片分类问题,如下:

    图片分类

    现在给定一个任务,在字典中找出10张图片,用这10张图片的一个线性组合去尽可能的表示测试样本,如果是你的话,你会怎么选,你会选10张桌子图片去表示 一张狗的图片吗?不会的,你会选10张狗的图片竟可能的描述测试样本。这也就是稀疏表示的过程。表示,就是用字典中的元素(就是字典中的样本)的线性组合尽可能的描述(还原)测试样本。稀疏表示要用尽可能少的字典中的元素去描述测试样本。为什么要稀疏呢?为什么选用的字典中的样本要尽可能少呢?你可以想象对于一个狗的图片,我用大量的字典中桌子的的样本,东补补西凑凑,只要桌子的样本够多,我也是可以用大量桌子图片的线性组合去表示狗这张图片的。所以对字典中选取的样本的数量要求尽可能的少。

    然后,我们的任务就是怎么将这个想法,用数学的公式表示出来,然后用计算机编程实现。

    对应的数学表示

    在图片分类的问题上,通常把一个两维图像,展成一个一维的向量(一般说向量,是列向量),来方便后边的操作。如何将一个二维图像展成一个一维向量呢,很简单,就是以列展开,第一列下边接上第二列,第二列下边接上第三列.....

    完整之后就是这样一个情况:

    转化为向量

    下面我将详细的解释这图途中每一个字母的含义

    Y_{i} 表示的是第i个测试样本(就是上个图中左侧的狗这个测试样本),上边我们提到我们已经将二维图像展成了一个一维图像,在这里Y_{i} 为N*1的向量,N表示样本的维度。

    D表示的是字典(就是上一个图中的字典),这里对字典中的每一个二维图像也展成了一个向量。D是一个N*M的矩阵,N表示样本的维度,所有的样本的维度都是相同的,用图像处理可以很简单的做到。M表示字典中训练样本的个数。

    注意这个图中D=[\varphi _{1}^{^{T}};\varphi _{2}^{^{T}};...;\varphi _{n}^{^{T}}] 的表述是不准确的,实际上应该是D=[\varphi _{1},\varphi _{2},...,\varphi _{n},] ,其中\varphi _{i} 表示的是第i类训练样本的训练集,n表示类别总共n类。假设i个类别中训练样本的个数用p_{i} 表示,那么可以得到n类样本总的样本个数为\sum _{1}^{n} p_{i}=M

    X_{i} 就是对应第i个测试样本的稀疏系数。

    下面我将讲明这个公式代表的具体意思(很重要),

    Y_{i}=D\times X_{i}

    我们把D矩阵写成行向量的形式,上个公式就变成了

    Y_{i}=[d_{1},d_{2},...,d_{M}]\times X_{i}

    注意这里的d_{i} 与上边提到的\varphi _{i} 所表示的意思是不一样的,d_{i} 是一个N*1的向量,表示字典中第i个元素(训练样本),而\varphi _{i} 表示的是一个N*p_{i} 的矩阵,表示的是字典中第i个训练样本的总体。

    我们再把X_{i} 展开,

    Y_{i}=[d_{1},d_{2},...,d_{M}]\times [x_{1};x_{2};...x_{M}]

    [x_{1};x_{2};...x_{M}] 表示列向量,我们继续变换

    Y_{i}=x_{1}\times d_{1}+x_{2}\times d_{2}+...+x_{n}\times d_{n}

    这个公式的含义是什么呢?你可以想仔细想想,是不是很兴奋,他代表这用的d1,d2...等训练样本去表示测试样本,这不就是我们在开头提出的问题吗?选10张照片去表示狗。

    现在稀疏表示,表示已经出来了,稀疏怎么办呢,很好办,我们约束系数X_{i}  是稀疏的,具体的约束就是X_{i} 中非零项的个数不能超过10,用数学公式表示就是 ||X_{i}||_{0}<T, 这个叫做0范数,就是要求X_{i} 中非零项的个数不能超过T。

    最后还有一个问题怎么描述 误差呢,因为 

    Y_{i}=x_{1}\times d_{1}+x_{2}\times d_{2}+...+x_{n}\times d_{n}

    要做到严格的相等太难了,实际中是存在误差的,如何描述这个误差呢?

    是不是已经想到办法了

    (Y_{i}-x_{1}\times d_{1}+x_{2}\times d_{2}+...+x_{n}\times d_{n})^{2}

    最终上边所提的到的表示的问题,最终就转化成了如下公式:

    \arg \min ||Y_{i}-D\times X_{i}||_{2}^{2} \quad s.t. ||X_{i}||_{0}<T

    arg min这个单词下边应该有一个X_{i} (CSDN的公式编辑器中没有找到如何编写),表示在s.t.的约束下,使得上个公式最小的X_{i} 的值。

    如何求解这个问题,我们就直接用现成的算法就好,我一般用OMP算法,具体见https://blog.csdn.net/scucj/article/details/7467955

    最后最后的问题来了?怎么分类呢??先想几分钟,其实很简单

    那就是用字典中每一个类别对应的训练样本乘以与之对应的稀疏系数中的分量。

    我们上边提到

    Y_{i}=[d_{1},d_{2},...,d_{M}]\times [x_{1};x_{2};...x_{M}]

    现在我不这么划分了,我将D字典不按照样本数量划分了,我按照样本类别划分。

    Y_{i}=[D_{1},D_{2},...,D_{n}]\times [\alpha _{1};\alpha _{2};...\alpha _{n}]

    Di表示字典D中第i个类别中所有的样本,\alpha _{i} 表示Di 在系数X中对应的分量。

    最终||Y_{i}-D_{i}\times \alpha _{i}||_{2} 表示用字典D中的第i类去重建测试样本 Y_{i} 的误差。我们将误差最小的类别最为Y_{i} 的预测类别。

    具体的流程请见:

    SRC具体流程

     

     

    至此本片文章结束。

    但是我的朋友要求我要理论+实践,理论部分讲完了,实践部分,你们自己写吧。我觉得我讲的已经十分清楚了,这么清楚的一片博客,一个认真阅读的读者,应该可以自己写出代码来了吧

    (来自朋友的一顿毒打)

    所以,我还写了代码(真香),用稀疏表示来进行人脸识别(人脸分类)的。(脸好疼)

    这是结果

    用稀疏表示人脸分类的结果

    code:code

     

    展开全文
  • 人脸识别是机器视觉中非常火的一个领域了,在近十几年来发展迅猛,而本文介绍的方法是基于稀疏表示分类(Sparse Representation based classification,SRC)的人脸识别,稀疏表示理论非常强大,突破了传统采样定了...

           人脸识别是机器视觉中非常火的一个领域了,在近十几年来发展迅猛,而本文介绍的方法是基于稀疏表示分类(Sparse Representation based classification,SRC)的人脸识别,稀疏表示理论非常强大,突破了传统采样定了的束缚,信号的稀疏表示即用尽可能少的非零元素表示信号主要信息,简化信号处理的求解过程,马毅在09年将稀疏表示引入人脸识别中,其性能相比之前的人脸识别方法具有突破性的进展。

           相信很多同学都听说过NN和NS两种分类器,NN对与测试样本的分类是根据单个训练样本与测试样本之间的表示,而NS则是根据每类的训练样本对测试样本的线性表示进行分类识别,SRC则是介于这两种分类器之间的一种人脸分类器,选用部分训练样本对测试样本进行紧凑表示。

           接下来对SRC主要步骤进行阐述:在进行稀疏表示人脸分类之前,对训练样本和测试样本进行预处理,即对齐、剪切、归一化,假设有k类带标签的样本,将每张图片按列进行排放,Ai=[vi,1,vi,2,...,vi,ni],根据子空间理论,来自同一样本的样本位于相同的线性子空间中,故假设第ith训练样本数目充足,来自第ith的测试样本y可表示为:
                                              y=αi,1vi,1+αi,2vi,2+...+αi,nivi,ni
    其中αi,jvi,j为系数。但是由于测试样本是未知的,不知道它来自哪个类别,怎么办呢?于是采用这个训练样本对测试样本进行表示(这里就为接下来的稀疏表示埋下伏笔),K类训练样本组成矩阵A:
                                       A=[A1,A2,...,Ak]=[v1,1,v1,2,...,vk,nk]
    于是,测试样本y可以由A线性表示为:
                                                                          y=Ax0
    其中系数向量为x0=[0,...,0,αi,1,αi,2,...,αi,ni,0,...,0]T,对于分类来说,上述的系数想来是非常理想的,现在看这个系数向量,例如k=20,只有的元素不为零,根据稀疏表示理论看来就熟悉了呢,这就是典型的对测试样本的稀疏表示。
           接下来讨论y=Ax的求解问题,求解向量的稀疏解,可以转化成为下面优化问题:
    x^0=argminx0s.t.Ax=y,但是在求解l0norm时是个NP-Hard问题(优化问题具体我也不懂,反正就是不好正面求解,既然正着不好求,那就想别的办法,这里用近似求解),此处转化成l1norm求解问题:
                                                      x^1=argminx1s.t.Ax=y
    (论文中有解释,几何意义上的,数学不好,不能分析了,自行看吧。马毅的主页还有很多关于优化问题的文献)
    这里写图片描述
    上图是SRC的完整过程Latex写公式太费劲了就截图了。
    实验部分
           作者针对传统人脸识别过程中特征提取方式和样本处于遮挡进行分析,对于特征提取方式对SRC的影响,在大于120D时各种方法差别不大,所以通常的特征提取方法对于分类系统没有影响;对于遮挡问题,本文采用在字典加入单位矩阵作为误差矩阵,消除遮挡或噪声干扰影响,实验非常丰富,总而言之证明,SRC在对于普通遮挡效果还是行的(但是效果提高空间巨大,所以这是做稀疏人脸识别的改进点之一)。
           PS:对于认证问题,本文提出SCI,可以判定是否为数据库中的图片或者非人脸,残差进行分类,稀疏系数进行认证判别,提高识别率;对于表情识别也是有效的。
    稀疏表示人脸识别作为突破性发现,经过验证,识别率远远高于传统方法,具有效性和鲁棒性,但是他自身也是有缺陷的,主要有两点:一、训练样本数目充足,但是在现实生活中数据采样不是很充足,制约之一,改进点(著名的论文就是ESRC,引用率非常高);二、对于遮挡问题效果还是不好,这也是关于稀疏人脸识别改进工作的重要点之一,当然其他的改进点还有,上面两点只是主要突破点,从事这方面工作的同学可以进行思考改进。
    上述就是这篇论文的大概内容,当然还有其他小的内容没有全部加进来,有兴趣的同学可以仔细阅读以下,09年这篇论文还有一个appendix,里面有内容的推导,仔细看看会有很大的收获。

    展开全文
  • 稀疏表示分类

    千次阅读 2015-10-28 11:35:52
    稀疏表示可作为基础理论用于构建稀疏表示分类器[14](Sparse Representation Classifier, SRC)。SRC 假定当测试样本所在类的训练样本数足够多时,测试样本可由这些训练样本进行线性表示,而其它类的样本对重构该测试...
          稀疏表示可作为基础理论用于构建稀疏表示分类器[14](Sparse Representation Classifier, SRC)。SRC 假定当测试样本所在类的训练样本数足够多时,测试样本可由这些训练样本进行线性表示,而其它类的样本对重构该测试样本的贡献为 0,从而将一般信号的分类问题转化为了一种稀疏表示问题。大量实验证明,这类分类器能够较好地应用于图像分类和目标跟踪问题。Wright 指出 SRC 对数据缺损不敏感,当所求系数足够稀疏时,特征空间的选取变得不再重要;这些优势使得
     SRC成为一种非常优秀的分类算法。虽然大量实验证明基于SRC是一种具有潜力的图像分类器,但近期一些文献[20][21]指出,对于小样本分类问题,系数的稀疏性对分类准确率并没有实质的帮助。针对此题,Huang等在文献[4]中指出结合线性判别分析技术能够提升类间的区分度,提升稀疏分类效果。Shenghua等在文献[22]中成功将核函数(Kernel)技巧与稀疏分类结合在了一起,此文献提出了基于Feature-Sign Search(FSS)的核函数稀疏分类(KSRC)算法并将其成功应用于人脸识别问题中。然而,Cuicui
     Kang等在文献[6]中指出使用FSS方法求取KSRC中凸优化问题的效率较低,此文献提出了核函数坐标下降法(KCD)用以求解凸优化问题,并结合LBP特征构建了人脸识别系统。



    展开全文
  • 稀疏表示分类器代码

    2020-07-30 23:30:25
    这个代码是关于人脸识别里面稀疏表示分类器,对于初学者来说很有用。
  • 文章来源 Jia K, Chan T H, Ma Y. Robust and practical face recognition via structured sparsity[J]. Computer Vision–ECCV 2012, 2012: 331-344.Highlight 作为一种 sparse representation based ...
  • 用于稀疏表示的线性分类器~可对稀疏表示的字典进行分类训练以及测试~
  • 稀疏表示(SRC)

    千次阅读 2015-01-30 21:35:06
    基于表示的分类方法(representation based classification method, RBCM)研究较多的就是John Wright等在2009年提出的稀疏表示分类(sparse representation based classification, SRC)方法了,Google...
  • 关于稀疏表示的理解

    千次阅读 2018-03-27 11:33:51
    稀疏表示可作为基础理论用于构建稀疏表示分类器[14](Sparse Representation Classifier, SRC)。SRC 假定当测试样本所在类的训练样本数足够多时,测试样本可由这些训练样本进行线性表示,而其它类的样本对重构该测试...
  • 稀疏表示人脸识别SRC matlab代码实现。附带l1范数优化代码。可以顺利跑通。测试数据集为YaleB。
  • (SRC)基于稀疏表示的人脸识别

    万次阅读 热门讨论 2013-11-01 18:14:13
    本文主要记录自己在学习稀疏表示在人脸识别中的应用所遇到的问题作一简单的总结。 1. 问题背景  信号的稀疏表示并不是新的东西。我们很早就一直在利用这一特性。例如,最简单的JPEG图像压缩算法。原始的图像...
  • 字典学习与稀疏表示

    千次阅读 2017-09-13 15:36:52
    字典学习(Dictionary Learning)和稀疏表示(Sparse Representation)在学术界的正式称谓应该是稀疏字典学习(Sparse Dictionary Learning)。该算法理论包含两个阶段:字典构建阶段(Dictionary Generate)和利用...
  • 稀疏表示字典的显示(MATLAB实现代码)

    万次阅读 多人点赞 2016-05-03 22:13:24
    本文主要是实现论文--基于稀疏表示的图像超分辨率《Image Super-Resolution Via Sparse Representation》中的Figure2,通过对100000个高分辨率和低分辨率图像块训练得到的高分辨率图像块字典,字典原子总数为512,...
  • 稀疏表示(Sparse Representation)

    千次阅读 2013-09-04 16:30:01
    稀疏表达是近年来SP, ML, PR, CV领域中的一大热点,文章可谓是普天盖地,令人目不暇给。老板某门课程的课程需要大纲,我顺道给扩展了下,就有了这个上中下三篇介绍性质的东西。遗憾的是,我在绝大多数情况下实在不算...
  • 稀疏表示

    2014-06-18 09:55:04
    稀疏表示最重要的思想即是,在一个足够大的训练样本空间内,对于一个类别的物体,可以大致的由训练样本中同类的样本子空间线性表示,因此在当该物体有整个样本空间表示时,其表示的系数是稀疏的。这是稀疏表示思想最...
  • 稀疏表示与字典更新KSVD算法

    千次阅读 2018-05-11 10:14:59
    1. 算法简介 K-SVD可以看做K-means的一种泛化形式,K-means算法总每个信号量只能用一个...K-SVD通过构建字典来对数据进行稀疏表示,经常用于图像压缩、编码、分类等应用。 2. 主要问题 Y = DX Where&nbsp;...
  • 这些天一直在看稀疏表示和协同表示的相关论文,特此做一个记录: 这篇文章将主要讨论以下的问题: 1.稀疏表示是什么? 2.l1正则化对于稀疏表示的帮助是什么,l0,l1,l2,无穷范数的作用? 3.稀疏表示的robust为...
1 2 3 4 5 ... 20
收藏数 34,945
精华内容 13,978
热门标签
关键字:

稀疏表示分类