图像的稀疏表⽰（SparReprentation）
⽂章⽬录
前⾔
在进⼊正题前先结合⾃⼰的经验对稀疏理论的相关内容扯⼏句。⾃⼰的话本⾝之前做了⼀段时间的图像融合内容，后来这块也放了放。但是之前在看论⽂的时候，基于稀疏理论的图像融合相关的论⽂还挺多的，但是⼀直没去仔细看这个，也没系统的整理过。最近看到好⼏篇2020年的论⽂，都是⽤这个做的融合，当然稀疏理论的应⽤场景远不⽌此。于是还是想再好好查⼀查，梳理⼀下。其实之前刚开始看这个东西的时候，挺抽象的，包括什么稀疏编码、字典学习等等，看着还挺吓⼈的。
因此在这⾥总结⼀下⾃⼰的学习过程，希望给每位学习图像稀疏表⽰的同学⼀点帮助。当然限于个⼈⽔平，很多内容我也不⼀定能说的特别清楚，尽量通过通俗清晰的⽅式说明。本⽂的主旨并不在于严密的数学论证和公式推导，更多的是帮助理解稀疏理论，整合⼀些或许有启发的思想，更详细的算法等已经有很多⼈整理的很好了。
其实⽹上相关的博⽂已经很多了，如果有⼀定的了解应该就明⽩，稀释表⽰⾥⾯最核⼼的两个任务：
1. 稀疏分解
2. 字典⽣成
由此衍⽣出来的，为了完成这两个任务的相关算法。但是其实，对于⼀个刚接触这个理论的⼈，⼀下⼦就直接就看这些内容，看了⼀圈可能还是对稀疏的概念不那么清晰。因此，建议刚开始学习稀疏表⽰的朋友按以下过程循序渐进，充分理解稀疏表⽰再进⼀步去看后续的算法，应该能对⼤家的学习有事半功倍的效果。
1. 稀疏信号
2. 稀疏表⽰
3. 稀疏分解
塘鱼4. 字典⽣成
5. 应⽤
接下来，我会根据以上思路，根据我的理解结合⽹上的许多相关博⽂和相关论⽂，尽可能把这个问题讲的通俗⼀点。许多博⽂都写的很好，对我的学习也有很⼤的启发，我会尽量引⽤上，如有疏漏的，可以留⾔提醒。
那正式开始之前，对于⼀些喜欢看视频学习的或者想要系统过⼀遍的同学，在这⾥放上⼀个Duke⼤学的公开课视频链接，以及B站搬运的中⽂字幕版，但是这个翻译的很抽象，视频下⽅有YouTube的视频地址。
稀疏信号
信号本⾝就是⼀个很⼴义的概念，图像、语⾳、⽂本、光、电等等都可以是信号。那在数学层⾯上，信号可以认为是⼀组反映原始信号特征的数据。将⼀个⼀维信号记为⼀个长度为N的向量，假设只有K个元素为⾮零的，其中K<<N，那就认为这个向量是K稀疏的或者严格K稀疏。同时，要做到严格K稀疏并不容易，所以⼀般除了K个值以外的元素只要⾜够⼩，就认为该向量是K稀疏的，这也是以下讨论的基础。
但是即便放宽稀疏性条件，现实中信号本⾝也都基本不满⾜稀疏性。例如，⼀副灰度图像可以认为是⼆维信号，但是如果该图像⾜够稀疏，也就是说⼤部分像素值都是0，那基本就是⿊⾊的⼀⽚，⽽⼤部分情况下的图像都不是这样的。但是经过研究，⼀般的⾃然信号都可以通过⼀定的变换，在其变换域上呈现稀疏性，对这样的信号，⼀般认为是可稀疏的或者可压缩的，也即⾃然信号的稀疏性，以上先验也是信号稀疏表⽰的基础。
⾃然信号和⼈⼯信号的概念参考⾃这⾥:
信号变换的过程就是信号的稀疏表⽰过程，⼀个信号在⼀组过完备字典（基）上进⾏稀疏分解，在该字典上⽤尽可能少的原⼦来表⽰原始信号，由此得到⼀个稀疏向量，称这个稀疏向量是信号在这组基上的稀疏表⽰。
稀疏表⽰
上图为信号的稀疏表⽰模型，⽤数学公式可以描述为，其中设为单⼀原始信号，为过完备字典，为稀疏表⽰结果。对于字典的每⼀列元素，称为原⼦(Atom)，记为，进⼀步，为了让该式的满⾜稀疏性，我们加
上范数的稀疏性约束，最终得到以下公式：
说说稀疏模型也就这么回事，但是刚看到的朋友可能总感觉这个过程很抽象，也不清楚在⼲啥，或者说为什么这样这样做。什么字典啊，原⼦啊，过完备啊，到底是⼀个什么样的概念。那我在这⾥结合我的理解，⼀定程度上简化上⾯的过程，⽤更形象的图解要阐述瞎扯这个问题。
我本⼈并⾮⼀个LEGO爱好者，但是我最近想着，稀疏分解⼤概也就是搭积⽊、拆积⽊这么⼀回事。结合上⾯的数学公式，我从最简单的模型⼀步步向实际问题推进。
为了让问题显得更加简单，我们现在假设信号都是1维的，即每⼀个给定的乐⾼模型和每⼀块积⽊都对应于1个原⼦。据百度百科，LEGO现在⼤概有1300多种形状的积⽊，简单⼀点就假设⼀本LEGO字典有1000个原⼦，包含了所有可能的LEGO积⽊形状。
那⼀般来说，这个字典都是过完备的，或者说是冗余的，具体的解释⼤家可以参考⽹上的回答，如，简单的说就是所有原⼦之间并⾮线性⽆关，⽽是存在可以相互表⽰的情况，⽽在稀疏表⽰⾥⾯，这个字典的冗余度还⽐较⾼。⽽LEGO零件库也显然符合这个特征，下图是假设
的包含1000个原⼦的字典局部⽰意图。
可以明显的感受到2号原⼦可以由2个1号原⼦来表⽰，4号原⼦可以有1个1号原⼦加1个2号原⼦，或者直接由3个1号原⼦来表⽰，这就说明了所有原⼦并⾮正交的，⽽是冗余的，⽽这种冗余性是稀疏表⽰所必要的。为什么必要，我们继续看下⾯的例⼦，我们⽤上⾯的字典分别
去表⽰以下⼏个简单信号，我们的原始信号恰好是字典中的原⼦。
请看上图中A、B、C三种信号的稀疏分解结果。
A信号在字典中恰好等于1号原⼦，对A信号在D上进⾏稀疏分解，我们可以得到稀疏表⽰的结果，这是显然的且该结果是唯⼀的，也满⾜稀疏性，信号A被我们分解为了⼀个1000维的稀疏向量，稀疏度为1。
B信号相对于A信号相对复杂了，同时的解不是唯⼀的，正如我们之前说的，B可以由原⼦1、2、4不同的线性组合得到。但是别忘了我们还有稀疏度的约束条件，，稀疏度要越⼩越好，最终我们得到的稀疏解为，稀疏度仍然为1。很好，我们的原始信号变复杂了，但是基于当前的字典D，他们的稀疏表⽰却没有变得复杂。这也解释了为什么我们要建⽴⼀个过完备字典，正是为了简化模型的复杂度，更好的表现信号的特征，同时我们保留了原始信号⼀个完整的特征，⽽不是把它拆成⼀些碎⽚的特征。这是冗余字典的优势，也即是稀疏表⽰的优势。
C信号的稀疏分解结果也就没什么好说了，我们很⾃然的可以得到⼀个稀疏度为2的解。但是同样的，除了图中的解，我们还有⼀个同样稀疏度为2的解，虽然是同样的稀疏度，但是我们还是选择了图中的解。正如B信号分解中所说的，冗余字典是为了尽可能保存原始信号的完整特征，图中的解系数均为1，复杂度更低，这种思想在之后稀疏分解的算法中也都有体现，如MP和OMP算法，都是基于贪婪算法，每次迭代寻找内积最⼤的原⼦。
看到这⾥，⼤家应该对信号稀疏分解有了更清晰的认识，甚⾄感觉有点简单？
天福宫
不过很残念的是，现实中，⽆论是信号还是字典⼀般都没有那么规规矩矩，描述⼀个信号的稀疏解也往往没有那么简单，因此在实际寻找稀疏分解算法的时候仍有很多问题。我们继续基于上述假设的LEGO字典探究这个问题，假设原始信号如下图所⽰。
X =DαX ∈R N D ∈R N ×K α∈R K d ∈i R i =N
1,2,...,K αL 0X =d α=i =1∑K i Dαs.t.min ∣∣α∣∣0
沉下心来(1)D 1×1000D α=[1 0 ... 0]T ααmin ∣∣α∣∣0α=[0 0 0 1 0 ... 0]α=2[2 0 1 0 ... 0]
这下原始信号的复杂度⼤⼤提⾼，但是基于上述字典，假设我们利⽤任意⼀种追踪算法计算出了，且是K稀疏的，K<<1000。显然我们没法⽤以上字典原⼦的稀疏组合拼出⼀辆⼀⽑⼀样的迈凯伦，根据计算得到的和，我们可以重建信号。假设原始信号为，重建的信号为
，就得到了以下结果：显然，实际情况⼤多数是这样的，由于解的稀疏性约束，我们往往尽可能获得⼀个逼近的近似结果（还是不得不说⼀句⽜逼）。基于以上结果，记残差为，可以得。现在我们的模
型已经接近实际问题了，只不过实际信号⼀般维度会更⾼，但是从字典中每⼀列表⽰⼀个原⼦的⾓度来讲已经⾜以说明问题了。当然，还有更实际的情况是，我们的原始信号往往还包含噪声，这部分暂时先不提，放在应⽤图像去噪中说明。
能够看到这⾥，并且理解上⾯的例⼦，⼤家应该明⽩稀疏表⽰是怎么⼀回事了，不过是将原始信号在某⼀组字典基上分解变换，得到另⼀个稀疏的表⽰⽽已。
讲到这⾥，我们终于回到了当前稀疏表⽰领域下的两个核⼼问题，稀疏分解⽅法和字典⽣成。
1. 在之前的乐⾼积⽊例⼦中，或是因为分解情况简单可以直接看出，或是假设我们可以分解，⽽未给出⼀种实际可⾏通⽤的算法。
2. 同时，我们的字典固定为乐⾼当前所有的积⽊类型，这是可⾏的，因为乐⾼积⽊的种类确实有限，也符合过完备字典的要求。
因此，当前稀疏表⽰领域中，以上两个任务是⼤家⽐较关⼼的，也是研究热点。当然，⽂章开头也说了，本⽂对这两块的算法不会具体展开讲，⽽是系统的概括和整理，更为详细的算法和流程⽹上已有许多很好的⽂章来说明，这⾥也会给出⼏个我参考的博客。
稀疏分解
服务管理制度
在上⼀部分中提到，优化⽬标为：
上式也等同于
在某种条件下，范数的优化问题有唯⼀解，但是该问题依旧是NP难的，但是后来进⼀步证明了，在RIP条件下，0范数的优化问题与范数的优化问题有相同的解，即满⾜下式：
该理论可以参考：进⼀步的，考虑到原始信号的噪声，该问题还可以表⽰为以下公式：
总之，不管是什么形式，⽬前解决这个问题主要有以下两类：αααD Y Y =′
Dαz Y =Y +′
z =Dα+z X =d α=i =1∑K i Dαs.t.min ∣∣α∣∣0
(1)min ∣∣α∣∣s.t.X =0Dα(2)
L 0L 1min ∣∣α∣∣s.t.X =1
Dα(3)
min ∣∣α∣∣s.t.∣∣X −0
Dα∣∣≤22ϵ(4)
1. 在范数上直接优化的贪婪算法：MP，OMP以及各种改进的匹配追踪算法等
平凡的世界读后感
2. 在范数上作为凸优化来求解：BP等
字典⽣成
回到之前的例⼦，针对⼀个给定的原始信号（物体），我们的LEGO字典似乎总能求得⼀个近似的稀疏解。那在实际的信号处理中，是否存在⼀类字典，可以⼴泛⽤于各类信号的稀疏分解中，答案是肯定的。很多研究都基于某个数学模型来构造字典，常见的⽐如DCT变换，⼩波变换，gabor变换等。
以DCT（离散余弦变换）为例，DCT字典本⾝是⼀个⽤于余弦变换时所采⽤的变换矩阵，但是它本⾝是⼀个正交字典（⽅阵），它是个完备字典，却不是过完备字典。但是通过对字典中的原⼦进⾏⼀定的操作可以调制出⼀个过完备字典，具体⽅法可以参考：
但是说到底，⽆论我们的LEGO字典还是以上提到的过完备字典，其表达能⼒终究是有限的，远不能满⾜⾃然界中各种信号的复杂性和多样性。其在遇到某种表达能⼒之外的信号时，提取特征的能⼒就会⼤⼤下降。以LEGO为例，⾯对许多光滑曲⾯的物体，LEGO字典总是⽆法很好的描述这样的特征，从⽽导致重建的结果出现残差，究其原因还是其零件库⾥就缺少具备这类特征的积⽊，这在信号
的稀疏分解过程中也是⼀样。
所以为了解决这个问题，提出了不少针对原始信号⾃适应的字典学习⽅法。
梦见很多鸟其中⽐较的著名的如K-SVD算法，其思想上相当于K-means的⼀种推⼴和拓展，迭代交替更新字典中的原⼦和稀疏解，最终算法收敛的时候就⽣成了⾃适应字典以及对应的稀疏系数。与K-means类似的是，算法需要指定迭代次数或者收敛误差。具体实现可以参考：
原⽂ K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Spar Reprentation - 2006
应⽤
其实，稀疏表⽰还是算⽐较新的理论，近些年也还有很多包括理论和应⽤的论⽂。但是深度学习⽬前在各个领域展现出的优秀性能，其他各类理论都被统⼀成了传统算法，以及稀疏表⽰⾃⾝的⼀些问题，导致在有些应⽤上表现显得不够突出。
但是不管怎么说，在许多问题的求解上，稀疏表⽰还是很有价值的，这⾥简单说⼀下应⽤，之后有时间或者有感的话会结合具体的论⽂写⼀下⽅法什么的。
图像稀疏表⽰
之前讲来讲去都是信号，所以图像到底怎么进⾏稀疏表⽰。假设图像的⼤⼩为，直接把整个图像拉成⼀个⼀维信号显然是不合适的，我们看看这个优化问题的⼤⼩，信号⼤⼩为，由于字典的冗余特性，字典⼤⼩⾄少为，这⾥k表⽰⼀个冗余系数，即过完备的程度，k越⼤，字典约冗余，字典的⼤⼩也到了⼀个夸张的地步。⼀⽅⾯计算效率低，⼀⽅⾯不能很好描述局部特征，所以⼀般都是在图像上⽤滑动窗⼝取⼀个Patch，⼀般是8×8的窗⼝。
具体⽅法在下⾯图像去噪论⽂中有提到。例如⼀个⼤⼩为20×20的图像，以8×8的窗⼝和1的步长滑动，将图像分成列向量信号表⽰，每⼀次窗⼝可以提取64维列向量，⼀次遍历可以得到个列向量，假设冗余系数k取4，即需要计算169个稀疏解。
然后重构图像，并将对应的结果还原回图像中，即可得的稀疏表⽰后的图像。
图像去噪
Image Denoising Via Spar and Redundant Reprentations Over Learned Dictionaries
L 0L p M ×N MN ×1MN ×kMN (20−8+1)=2169Y =64×169D α64×256256×169
与K-SVD算法⼀起，同⼀个作者在同年发表了⼀个去噪论⽂。传统上基于滤波的图像去噪⽅法，假设噪声总是⾼频信息，然后基于⼀定的局部约束进⾏去噪。⽽稀疏表⽰去噪的理论基于，⾃然图像信号
总是可以稀疏表⽰的，⽽噪声是⽆法稀疏表⽰的，假设含噪图像（观测图像）为，其噪声模型满⾜以下公式：
则即为图像噪声，重构结果即是去噪图像。实际中，图像往往受到多种类型的噪声的影响，根据中⼼极限定理，多个独⽴同分布的噪声叠加趋近于正态分布，因此我们可以⽤⾼斯噪声模型先验来给定的误差阈值，控制稀疏分解停⽌的条件，对进⾏稀疏表⽰后再重建，即可得到去噪结果。
那说到为啥噪声⼀般不能进⾏稀疏表⽰，之前看到的⼀个类⽐的说法是，例如，对于任⼀⼤⼩n×m的8bit图像，在每个像素点上的可能性有256级灰度，因此整个图像的所有可能情况为，⽽实际的⾃然图像信号往往只涵盖了其中很⼩⼀部分，⽽这部分往往是可稀疏的，即可压缩的，这算是长期以来的经验性知识，⽐如最经典的jpeg图像压缩算法的泛⽤性已经证明了这⼀点。
该论⽂在⽹上有Matlab版的K-SVD以及图像去噪的Demo可获取，很适合学习，⼤家应该搜⼀下就可以搜到，之后有空会做⼀个去噪的笔记，也会贴⼀个中⽂注释后的代码帮助理解。
更多改进的论⽂这⾥就不提了。
图像融合
在⽹上其实很少看到稀疏表⽰⽤于图像融合领域的博客什么，但是⽂章开头也说了，我⾃⼰在图像融
属龙和属羊合领域有⼀定的浸淫，所以会相对关注⼀些。最早把稀疏理论⽤于图像融合是湖南⼤学的李树涛教授，其在稀疏表⽰，图像融合，模式识别等领域研究⽔平都相当⾼，很多论⽂的引⽤都很⾼，这是教授的简介：
最早的⼀篇稀疏表⽰⽤于像素级图像融合的论⽂为
Pixel-level Image Fusion with Simultaneous Orthogonal Matching Pursuit - 2012
该⽂提出了⼀种对多源图像在同⼀个字典上进⾏稀疏分解的算法，SOMP（Simultaneous Orthogonal Matching Pursuit）即同时正交匹配追踪，对多幅图像相同位置计算出的稀疏系数取绝对值较⼤值，得到融合后的稀疏系数，然后结合字典进⾏重建得到融合后的图像。以及我曾写过的⼀篇基于引导滤波的图像融合笔记也是他的⼀作论⽂在这⾥不作更多展开的介绍了，之后有空会稍微整理⼀下利⽤稀疏理论进⾏图像融合的思路。啊啊啊，什么都是等有空再做，疯狂挖坑，简直⽆情，危
图像重构压缩感知，图像修复，图像超分辨率重建（SR，CSR卷积稀疏表⽰等，感觉效果挺好的，之后有空再补，继续挖坑）
等等等等等。
⽬标跟踪
⼈脸识别
后⾯两个没怎么研究过，也不熟，⼤家有兴趣⾃⼰去探索。
其他
劳动合同⽂章可能还不完善，还有很多点没有详细展开，之后看⾃⼰是否有时间和需求再⾏补充。
这⾥再放⼀个稀疏⼯具包，⽤C++编写的，可以达到很⾼的性能，同时提供了Matlab和Python的接⼝，有兴趣的朋友可以⾃⼰去试试。Y Y =Dα+noi (5)
noi Dαnoi Y 256mn
