第12章-稀疏表示及其应用

第12章稀疏表示及其应用

孙延奎清华大学计算机科学与技术系内容提要从小波表示到稀疏表示典型分析式字典设计

超完备字典及学习式字典稀疏表示模型

模型求解方法字典学习

图像去噪图像分类

从信号的小波表示到稀疏表示小波分析研究的核心在于建立时频分解、构造小波正交基或Xlet，利用小波基可获得信号的稀疏表示。信号的稀疏性表示已成为一个重要研究方向，其中冗余字典代替了标准正交基。本课程将讲授稀疏表示模型、稀疏编码与字典构建，以及稀疏表示在图像去噪和图像分类中的应用如果一个信号中只有少数几个元素是非零的，那么该信号就是稀疏的。但是在一般的情况下，时域内的自然信号都是非稀疏的，只有在某些变换域中才可能是稀疏的。a）Lena图像b）12%幅值最大的小波系数重构c）8%幅值最大的小波系数重构图

6-3对于什么类型的一维信号，它的正交小波基具有很好的稀疏表示？

对于二维数字图像，它的二维可分离小波正交基的稀疏表示如何？（a）2D-DWT表示时用较多小波系数(b)方向性小波表示时用较少小波系数曲线边界的二维小波表示虽然具有较好的频率和空间局部化特性，但是不具备对人眼方向的敏感性。这表明，二维小波不能充分利用图像数据本身特有的几何特征，不是最优的或者说“最稀疏”的图像表示方法。图像的多尺度几何分析方法脊波（Ridgelet）曲波（Curvelet）轮廓波（Contourlet）Bandelet…..压缩传感（CompressedSensing，CS）理论传统的信号获取和处理过程主要包括采样、变换、压缩和重构四个部分压缩感知理论指出：信号的近似重构与信号的带宽之间并无绝对必然的联系，当信号具有稀疏性和可压缩性时，可以通过采集少量的从高维空间到低维空间的信号投影值来实现信号的准确或近似重构。

压缩传感理论可以认为是一种特殊的稀疏表示方法，它主要包括信号的稀疏表示、编码测量和重构算法等三个方面信号稀疏表示如何用更少的稀疏数据，逼近地表示原始信号发展成为了一个研究主题，即信号稀疏表示及其应用。信号的稀疏表示用已构建的字典的少数原子的线性组合表示信号。字典中的元素是表示信号的基元，称为原子。在稀疏表示中，字典的构建是关键经历了从正交基到适当冗余的紧框架，以及从紧框架到超完备字典的发展过程经历了从“基于数据的数学模型设计字典“到“直接从数据中学习字典”的重要转变稀疏表示的主要研究内容及应用研究内容

稀疏表示模型、稀疏编码和字典构建应用在图像去噪、图像恢复、压缩传感、多源分离、图像超分辨、图像分割，及人脸识别、图像分类等分析式字典设计

（近似）紧框架的性质对于紧框架A=B，有

当0<𝐴≤𝐵<2时，K个标准正交基的并是紧框架

分析式字典设计方法快速傅里叶变换（FFT）基字典FFT采用的正交基字典为，因三角基函数缺乏局部支撑性，因而FFT特别适合分析平稳信号。对于有限长信号，FFT隐含假定信号是周期延拓的，因而引入了边缘处的不连续性。离散余弦变换DCT假定信号是反对称延拓的，在信号边缘处是连续的，因而，DCT比FFT能够得到信号更稀疏的表示。而且，DCT还具有变换系数无虚部的优点，因而，2DDWT在图像编码中获得了广泛应用。FFT和DCT采用固定基字典分析信号，是与信号无关的线性变换方法KLT基字典KLT是一种与信号相关的线性变换方法，已知数据协方差矩阵，则KLT原子是如下特征值分解的前K个特征向量：与DCT相比，KLT产生自适应的信号基字典，将信号投影到低维线性空间，稀疏表示性能更好。但KLT缺乏快速算法，影响了它的实际应用，通常用DCT作为KLT的一个良好逼近。短时傅里叶时频框架字典如何对时频参数和进行离散采样，能使

构成的框架，从而构成信号f

完全和稳定的表示?Daubechies给出了窗函数取高斯函数时（此时=）的主要结论：离散小波时频框架字典

小波包字典

具有几何不变性的小波字典具有平移不变性的字典

二进小波字典双树复小波字典可操控小波变换（Steerablewavelettransform）

方向小波字典

的二进方向小波变换为类似定理9.1的证明，若存在两个常数使得则方向平移不变族就构成框架。二维Gabor滤波器(函数)

在一定的约束条件下[110],上述二维Gabor小波族可以通过对如下母Gabor小波旋转和伸缩得到：

记Curvelet框架字典Curvelet是一种图像的多尺度几何分析方法，也是一种方向小波，同样是通过对基本小波的旋转、伸缩和平移得到的，但又与上述方向小波有不同之处，主要是小波伸缩的方式不同。方向小波中对基本小波的两个坐标轴用相同的伸缩因子，而Curvelet对基本小波的坐标轴使用不同伸缩因子，是由抛物尺度准则得到的，这种各向异性的波形比方向小波对方向更敏感

发展过程Curvelet框架，1999，Candes和Donoho第二代Curvelet变换，2002两种快速离散Curvelet变换算法，2005母Curvelet小波的伸缩、旋转和平移

在频域中定义第二代Curvelet函数

平移不变二进curvelet字典

离散curvelet字典

curvelet原子每个curvelet原子与一个具体的位置、方向和尺度相对应，其支撑基本上是长条形的椭圆状，沿着宽度方向振荡、长度方向平滑

curvelet原子由相应的各向异性特征所刻画，满足抛物尺度规则：M-项curvelet逼近

X-lets1999~2005，Wedgelet，Ridgelet,Contourlet,

Bandlets等，这些字典原子针对图像的不同类型几何结构，具有更多方向的分辨率及各向异性，进而能够更有效地表示和分解图像的轮廓和边缘等正则性当构造图像的稀疏表示时需要用到比基更大的字典，通过这种冗余字典来实现信号的稀疏表示典型的分析式字典分类非自适应的框架字典

DCT基、短时傅里叶时频框架字典、离散小波时频框架字典、小波包字典、具有几何不变性的小波字典、方向小波字典、curvelet、wedgelet、ridgelet和contourlet自适应框架字典KLT基,

经验小波框架和Bandlets等基于数据的数学模型法构建字典的特点以上介绍了信号稀疏表示的字典设计从正交基到适当冗余的紧框架的发展阶段，属于基于数据的数学模型法构建字典。

特点：信号f在基字典中有稀疏的合成与它在该字典下有稀疏的分解是一致的。线性变换是稀疏的

f在基字典下有稀疏的合成，具体地，取M项绝对值最大的系数，相应M个原子的线性组合构成信号f的M-逼近超完备字典

学习式字典1996年Olshausen与Field在Nature杂志上发表的论文是字典学习领域的奠基性工作。作者利用来自自然图像中的图像片训练字典，获得的字典原子与哺乳动物的视觉感受野的表示特性有惊人的相似性

重要意义标志着稀疏信号表示从“基于数据的数学模型设计字典“到“直接从数据中学习字典”的重要转变，也即从“分析式字典”到“学习式字典”的转化。稀疏表示模型

稀疏性度量

稀疏表示的数学模型

转化为无约束最小化问题

匹配追踪在冗余字典中选取M个原子，计算信号的最优M-项逼近是一个NP难的问题。利用算法构造一个有效的、未必是最优的逼近是常采样的策略。匹配追踪算法主要求解基于过完备字典的单个信号稀疏编码问题。在每次迭代中从字典中选择最能匹配信号结构的一个原子，并迭代地进行下去，最终得到信号的逼近。设字典是一个超完备字典，，其中字典原子已单位化，即，。匹配追踪首先从中选择一个最优匹配原子，该原子下标满足条件：；将投影到上并计算出残差，即。因与正交，故追踪算法对残差进一步做分解而迭代这一过程，直到满足迭代终止条件一般而言，不等于在上的正交投影，其中是由M个原子生成的线性空间。Mallat等提出的正交匹配追踪（Orthogonalmatchingpursuit,OMP）将所选原子正交投影到已选的原子张成的子空间，提高了稀疏表示的精度。正交匹配追踪第1次迭代从中选择一个与最优匹配原子，该原子下标满足如下条件

将投影到上并计算出残差，即

其中，为的系数，。第2次迭代第n次迭代

如何计算投影系数？由可得MP和OMP的许多改进算法正则的OMP(RegularizedOMP,ROMP)压缩感知匹配追踪(CompressivesamplingMP,CoSaMP)分段匹配追踪（StagewiseOMP,StOMP）子空间追踪(Sub-spacepursuit,SP)稀疏自适应匹配追踪(Sparsityadaptivematchingpursuit,SAMP)基于树的正交匹配追踪(Tree-basedorthogonalmatchingpursuit,TBOMP)等基追踪BP算法

最小绝对值收缩选择算子（Leastabsoluteshrinkageandselectionoperator,LASSO）最小角回归软件（Leastangleregressionsoftware,LARs）梯度投影稀疏表示（Gradientprojectionforsparsereconstruction,GPSR）基于内点法的L1-magic等一个理论问题匹配追踪和基追踪算法能否计算出问题的最稀疏解？解的逼近程度如何？对于超完备字典及线性方程组，若存在满足的解，则该解必定是最稀疏的，而且匹配追踪和基追踪均能追踪到关于的最稀疏解。其中，是字典的互相关（Muturalcoherence），是刻画字典的各列原子间相关性的一种方式。说明了在实际应用中，匹配追踪和基追踪近似求解的次优性。一般地，基追踪算法比匹配追踪算法能够得到更优解，但计算效率相对较低

举例：不同算法效果对比构造复杂信号

信号是用鸣叫声、截断正弦波、短时瞬变成分以及Dirac脉冲合成的信号，该信号包含多种局部化时-频结构构造小波包超完备字典设信号的大小为N，利用Daubechies小波滤波器db4首先计算一个小波包字典，该字典包含个时-频原子，这是一个超完备字典。

算法效果比较比较最佳基选择、匹配追踪、正交匹配追踪和基追踪算法在这个小波包字典上稀疏编码过程中获得的字典原子的时频结构。原信号最佳小波包匹配追踪正交匹配追踪基追踪不同算法在小波包字典上稀疏编码过程中获得的字典原子的时频结构字典学习在稀疏表示理论中，字典的构造非常关键。字典的构成应该与信号本身所固有的特性尽量保持一致，如何根据一类信号自身的特点，自适应地构造一个冗余字典，最稀疏地表达该信号集，是稀疏表示理论研究的重点。稀疏表示理论实现了从设计字典到学习字典的转化傅立叶基，小波基，Gabor小波，curvelets等字典设计方法，这种方法并不要先验地知道信号本身的特征，而是直接将信号在上述字典上进行分解，摆脱了对信号自身结构的依赖，其优点是计算效率高，但难以得到高维信号如图像的最优稀疏表示。KLT基和Bandlets等字典设计方法，考虑到了信号自身的特点，能得到信号更好的稀疏表示，但计算代价比较高。对于一个信号类F中的采样信号集，构造一个字典Φ（通常是高度冗余的），使得F中每个信号在该字典下有最稀疏的表示，并且稀疏编码能够快速计算得到。DL字典学习的数学模型样本集：，

超完备字典：，，

稀疏表示：，是在字典下的稀疏表示

字典学习:基于样本集，在稀疏测度约束下寻找字典及稀疏表示：

s.t.其中，为矩阵的Frobenius范数。

（矩阵所有元素的平方和的开方）该模型是一个组合搜索且严格非凸问题，因此，只能采用近似算法获得局部最优解。

MOD和K-SVD由于和其中一个固定时，上式中的模型变成凸优化问题。因此，该模型常通过交替优化稀疏编码和字典更新进行求解。通过交错迭代一定次数得到模型的解。字典已知时，通过稀疏编码方法如OMP求解

在已知时，更新字典的两种典型方法MODMOD方法使用最小二乘更新，它同时更新字典的每个原子K-SVDK-SVD方法对中的原子逐个更新，比MOD算法简单而高效K-SVD字典学习对于给定的原子，有其中，是稀疏表示的第j行;是残差矩阵更新原子及其相应系数最直接的方法是计算的奇异值（SVD）分解，但可能在中引入新的非零系数而影响稀疏表示性。为了避免在中引入新的非零系数，更新过程仅对当前表示中用到的样本上进行。K-SVD字典学习令用到的样本下标依次为，表示仅由中各列构成的行向量，；为仅由中各列构成的残差矩阵，即则和可以如下计算：中的非零值由中的相应值替换得到。K-SVD算法D为上次迭代更新后的字典L为字典大小将D中第j个原子清零将d赋给D的第j列作为新的第j个原子K-SVD算法的高效算法K-SVD算法处理图像及计算性能在K-SVD算法中，样本集中的样本都是一维信号。该算法比较适合表示小尺寸的信号；同时问题的强非凸性使求解容易陷入局部最优。

如何应用K-SVD到图像？对于图像的稀疏表示应用，常将K-SVD应用到图像的片（patch）上，如的图像片，这时将图像片逐行从上至下顺次排列起来（字典序）构成一维信号，或提取图像片的特征，再用K-SVD算法处理。有关整幅图像的去噪算法会稍后讲解。

算法计算效率K-SVD在算法中用到了正交匹配追踪OMP算法和奇异值分解SVD算法。人们提出了近似高效计算方法。字典构造的分析法和学习法分析法得到的字典具有高结构性，且能快速进行数值实现

学习法通过机器学习由一系列例子得到字典，相比隐字典更方便调整，但形成这样的非结构的字典成本很高结合这两种方法优点改进分析法或学习法的字典构造方法得到了深入研究和应用双稀疏字典

trainlets

…….双稀疏字典双稀疏字典是一个旨在结合训练字典和分析字典优点的例子双稀疏字典结构

其中是某种固定的具有快速计算的分析字典，为稀疏矩阵，即原字典的每列原子在分析字典上都有一个稀疏表示。所以，字典不仅具有稀疏表示和快速实现，同时又具有提供的自适应性将字典稀疏结构化之后的优化问题

s.t.该优化问题可以利用修改后的K-SVD算法即SK-SVD求解。

trainlets双稀疏模型能够用于学习比MOD和K-SVD更大的图像片的字典。在实现中，由于小波在小图像片上存在严重的边界效应，因此该模型在具体实现中，常选择超完备2DDCT作为分析字典。截断小波（croppedwavelet）解决了小波变换在小图像上的边界问题，使得小波可被选作分析字典，并利用小波所具有的多尺度性质，使得双稀疏模型可以用于更大的图像片，如甚至，的字典训练。所训练的字典被称为trainlets，利用trainlets可以更好地克服高维信号字典学习时需要大量训练集的缺陷。截断小波介绍截断小波在小信号边界处理方面的应用，不仅是对2.2.4节信号边界延拓方法的补充，也是稀疏表示的一个应用给出一种自适应延拓方法，使得在截断小波变换后几乎没有边界效应，因而可获得信号的稀疏表示

上述分析表明，我们在寻找能完全重构的，使得

是一个解，但不是一个稀疏解。

截断小波解决方法是寻找线性系统的稀疏解，即求解如下优化问题：s.t.可以利用OMP估计上述线性系统的稀疏解。称为截断小波字典。(a)周期性

(b)对称性

(c)零填充

(d)延拓边界效果举例为进一步说明传统（周期）小波和截断小波在边界处理效果上的明显差异，构造了1000个随机平滑函数（三次多项式），由每个函数采样长度为64的信号并在采样32处引入随机阶梯不连续性，对这些信号进行范数单位化。仅用5个小波系数来估计这些函数，并估算重构后每个样本点的误差值。下图显示了各采样点均方误差的分布状况，正如所预期的那样。在线字典学习最初设计的字典学习算法如MOD,K-SVD等都采用迭代的批处理过程，算法在每次跌代中需要访问整个训练集，并在约束下最小化代价函数。但是整体访问样本集无法处理超大规模的样本集或随时间改变的样本集。在线访问训练数据，每次处理一个样本或小批样本。比如，trainlets采用的在线稀疏字典学习算法OSDL（onlinesparsedictionarylearning），能够处理大规模数据集。在线字典学习技术相对于整体处理具有内存占用小、计算负荷低的优势。图像稀疏表示已在图像编解码、图像去噪、图像复原、图像超分辨、压缩感知、图像分类等方面获得了成功的应用。这里仅介绍在图像去噪和图像分类中的应用。图像去噪图像分类图像去噪

字典已知的去噪模型

模型求解

超完备的DCT字典固定字典模型的不足固定字典D可以是各种变换矩阵，如DCT变换，但变换域的缺点是适应性差，也就是说，字典D

不会随着待处理图像的变化而变化，常会出现边缘模糊、伪吉布斯效应等情况。Elad等人对上述方法进行改进：过完备字典不采用固定不变的变换字典，而是根据待处理观测图像的图像片训练字典。一般去噪模型及求解策略

实现代码代码可参考MichaelElad的个人主页http://www.cs.technion.ac.il/~elad/图像分类SRC（sparserepresentation-basedclassification）J.Wright,A.Y.Yang,A.Ganesh,S.S.Sastry,andY.Ma,Robustfacerecognitionviasparserepresentation,IEEETransactionsonPatternAnalysisandMachineIntelligence,2009,31(2):210–227ScSPM（SparseCodingSpatialPyramidMatching）

J.Yang,K.Yu,Y.Gong,andT.Huang,Linearspatialpyramidmatchingusingsparsecodingforimageclassification,inProceedingsoftheIEEEConferenceonComputerVisionandPatternRecognition,2009,1794-1801SRC

SRC步骤3记表示中对应第i类的稀疏系数向量，计算每一类的稀疏逼近误差步骤4确定测试样本的所属的类别

ScSPM2009年，Yang等提出了基于SIFT(ScaleInvariantFeatureTransform)特征稀疏编码的空间金字塔表示及分类方法，即ScSPM该方法的优点是可用线性SVM分类，而且与传统方法相比具有更高的分类精度和速度,为解决大规模图像的训练与分类提供了解决方法。ScSPM分类的基本思想

将训练图像分为图像片，提取每个图像片的SIFT特征将图像片的SIFT特征作为训练样本学习字典

获得每个图像片的稀疏表示；并利用金字塔表示获得每个训练图像的全局特征表示

利用one-against-all训练c类二值线性SVM分类器

对每个测试图像，采用上述方法获得该图像的全局表示；用每个线性