形象易懂讲解算法II.docx

《形象易懂讲解算法II.docx》由会员分享，可在线阅读，更多相关《形象易懂讲解算法II.docx（24页珍藏版）》请在三一办公上搜索。

1、形象易懂讲解算法II压缩感知之前曾经写过一篇关于小波变换的回答，得到很多赞，十分感动。之后一直说要 更新，却不知不觉拖了快一年。此次更新，思来想去，决定挑战一下压缩感知 (compressed sensing, CS)这一题目。在我看来，压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果，并 在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学 表述背后蕴含着非常精妙的思想。基于一个有想象力的思路，辅以严格的数学证 明，压缩感知实现了神奇的效果，突破了信号处理领域的金科玉律一一奈奎斯特 采样定律。即，在信号采样的过程中，用很少的采样点，实现了和全采样一样的 效果。正是被

2、它的精妙思想所打动，我选择它作为专栏第二篇的主题。理解压缩感知的 难度可能要比之前讲的小波还要大，但是我们从中依然可以梳理出清晰的脉络。 这篇文章的目标和之前一样，我将抛弃复杂的数学表述，用没有公式的语言讲清 楚压缩感知的核心思路，尽量形象易懂。我还绘制了大量示意图，因为排版问题， 我将主要以PPT的形式呈现，并按slice标好了序号。一、什么是压缩感知(CS)？compressed sensing又称compressed sampling，似乎后者看上去更加直观一些。 没错，CS是一个针对信号采样的技术，它通过一些手段，实现了 “压缩的采样”， 准确说是在采样过程中完成了数据压缩的过程。因此

3、我们首先要从信号采样讲起：模拟信号采样模拟信号用多大的采样频率?数字信号采样1. 我们知道，将模拟信号转换为计算机能够处理的数字信号，必然要经过采样 的过程。问题在于，应该用多大的采样频率，即采样点应该多密多疏，才能完整 保留原始信号中的信息呢？奈奎斯特采样定理奈更酬.乩 1839-19762. 奈奎斯特给出了答案信号最高频率的两倍。一直以来，奈奎斯特采样定 律被视为数字信号处理领域的金科玉律。为什么是这样？ME履始1BUQ原始伯号采衅信当3. 至于为什么是两倍，学过信号处理的同学应该都知道，时域以T为间隔进行 采样，频域会以1/T为周期发生周期延拓。那么如果采样频率低于两倍的信号 最高频率，

4、信号在频域频谱搬移后就会发生混叠。一定要如此吗?2004 ,几位大牛还明如果信号是稀蔬的,那么它可以由远低 于采样定理要求的采样点重建恢复，并于2007年正式提出了 “压缩 知(Compressed Sensing )这个概念，陶哲轩 Emmanuef Candes压缩感知David Donoho4. 然而这看似不容置疑的定律却受到了几位大神的挑战。Candes最早意识到了 突破的可能，并在不世出的数学天才陶哲轩以及Candes的老师Donoho的协助下， 提出了压缩感知理论，该理论认为：如果信号是稀疏的，那么它可以由远低于采 样定理要求的采样点重建恢复。压缩感知采样频率须大于信号中最高频率的

5、2倍采样频率.等间距采料等间距采样f频域捋以1/丁为周期延拓,界 癖低螂引起混鱼,如果是不等间距采样呢？如果是随机采样呢？5. 而突破的关键就在于采样的方式。当我们说“采样频率”的时候，意味着做 的是等间距采样，数字信号领域通常都是做等间距采样，也服从奈奎斯特采样定 律。但是如果是不等间距采样呢？依然必须要服从采样定理吗?6. 答案是，随机的亚采样给了我们恢复原信号的可能。上图非常关键，它可以简单直观地表述压缩感知的思路。如图b、d为三个余弦 函数信号叠加构成的信号，在频域的分布只有三条线（图a）。如果对其进行8 倍于全采样的等间距亚采样（图b下方的红点），则频域信号周期延拓后，就会 发生混叠

6、（图c），无法从结果中复原出原信号。压缩采样频域时域7. 而如果采用随机亚采样（图b上方的红点），那么这时候频域就不再是以固 定周期进行延拓了，而是会产生大量不相关（incoherent）的干扰值。如图c， 最大的几个峰值还依稀可见，只是一定程度上被干扰值覆盖。这些干扰值看上去 非常像随机噪声，但实际上是由于三个原始信号的非零值发生能量泄露导致的 （不同颜色的干扰值表示它们分别是由于对应颜色的原始信号的非零值泄露导致的）P.S：为什么随机亚采样会有这样的效果？这可以理解成随机采样使得频谱不再是整齐地搬移，而是一小部分一小部分胡乱 地搬移，频率泄露均匀地分布在整个频域，因而泄漏值都比较小，从而有

7、了恢复 的可能。8. 接下来的关键在于，信号该如何恢复？下面讲一种典型的算法（匹配追踪）：（1）由于原信号的频率非零值在亚采样后的频域中依然保留较大的值，其中较大 的两个可以通过设置阈值，检测出来（图a）。（2）然后，假设信号只存在这两个非零值（图b），则可以计算出由这两个非零 值引起的干扰（图c）。 用a减去c，即可得到仅由蓝色非零值和由它导致的干扰值（图d），再设置 阈值即可检测出它，得到最终复原频域（图e）（4）如果原信号频域中有更多的非零值，则可通过迭代将其一一解出。以上就是压缩感知理论的核心思想一一以比奈奎斯特采样频率要求的采样密度 更稀疏的密度对信号进行随机亚采样，由于频谱是均匀泄

8、露的，而不是整体延拓 的，因此可以通过特别的追踪方法将原信号恢复。二、压缩感知的前提条件接下来我们总结一下，能实现压缩感知的关键在于什么，即需要哪些前提条件。刚才的例子中，满足了两个前提条件:2.随机亚采样9. 在刚才的讲述中大家可以感受到，这个例子之所以能够实现最终信号的恢复， 是因为它满足了两个前提条件：1. 这个信号在频域只有3个非零值，所以可以较轻松地恢复出它们。2. 采用了随机亚采样机制，因而使频率泄露均匀地分布在整个频域。这两点对应了 CS的两个前提条件稀疏性(sparsity)、不相关性(incoherence)。前提条件-1稀疏性信号需要在某一个变换域具有稀疏性中信号在频域是稀

9、i如果信号在某个域中非零点远远小于信号总点9 则信号在该域中是稀疏的.典型蛆推稀瞒号，只有少曲牌项10. 关于稀疏性可以这样简单直观地理解：若信号在某个域中只有少量非零值， 那么它在该域稀疏，该域也被称为信号的稀疏域。因此，第一个前提条件要求信号必须在某一个变换域具有稀疏性。比如例子中， 信号在频域是稀疏的，因而可以通过所述的重建方法轻松地在稀疏域（频域）复 原出原信号。前提条件1稀蔬性对于压缩感知:信号只需要近似满足稀疏性，即为可压缩信号.对于CS ,只要它在某一个变换域满足近似稀疏特性即 可，我们称之为稀疏域，重建将在稀疏域进行。甲可以是频魄 小波变换,离散余弦变换等然而通常信号在变换域中

10、不会呈现完全的稀疏性。其实只要它近似满足稀疏性， 即大部分值趋于零，只有少量大的非零值，就可以认为它是可压缩信号，可以对 它进行CS亚采样。对于之前讲的例子，如果它在频域中不稀疏，我们可以做DWT、DCT等，找到它 的稀疏变换。补充知识稀疏性信号的稀础已经在图像压缩领域有了很好的应用.dAfAa如JPEG格式:11. 这里针对信号的稀疏性和信号压缩额外补充一下：其实，信号的稀疏性已经 在图像压缩领域有了很广泛的应用。利用信号的稀疏性，可以对信号进行压缩。 如图像压缩领域的JPEG格式，就是将图像变换到离散余弦域，得到近似稀疏矩 阵，只保留较大的值，从而实现压缩。补充知识稀疏性12. 比如这个例

11、子中，仅用原图像6.9%的点就复原了和原图像基本相同的图像。 我们还可以采用小波变换，即为JPEG-2000，压缩效果更好。补充知识底I像压缩与压缩感知*保留大系数 I 丢E系数.稀疏变镇I全鞘1大量小系数系数压缩瞰的原动力问题:既然全采样了还刷丢弃，我们为什么不能直接少压缩JO3SHIHS腰一13. 这里需要指出，图像压缩和压缩感知这两个概念很容易弄混，大家一定要分 清。它们其实有着本质上的区别。图像压缩是先进行了全采样，然后再变换域丢弃小 系数，完成压缩；而压缩感知不同，它的思想其实从图像压缩中借鉴了很多：既然全采样了还要再 丢弃，我们为什么不能直接少采样一些点？因此，压缩感知直接进行了亚

12、采样， 然后再用算法消除亚采样导致的伪影。可以说，压缩感知直接在采样时就完成了 压缩。数学表达信观观号测测y = Ws观测I矩阵（P将高维信号X投影到低维空间,对X在甲稀蔬基上进行稀疏表示,x=Ms 中为稀疏基矩阵q为稀疏系凯14. 接下来，在将第二个前提条件之前，还是需要引入必要的数学表达的。上图 是一个大家在压缩感知相关的书籍文献中会经常看到的一张示意图。很多文章试 图用这张图给大家讲清楚什么是压缩感知，结果导致大家看得一头雾水，混淆在 各种“矩阵”当中。不过相信有了我之前的讲解，现在这张图会好理解很多。 这张图也就是把亚采样的过程用矩阵的方式表达出来而已：如图，x是为长度N的一维信号，也

13、就是原信号，稀疏度为k。此刻它是未知的。0为观测矩阵，对应着亚采样这一过程。它将高维信号X投影到低维空间，是 已知的。y=0 x为长度M的一维测量值，也就是亚采样后的结果。显然它也是已知的。因此，压缩感知问题就是在已知测量值y和测量矩阵0的基础上，求解欠定方 程组y=0 x得到原信号x。然而，一般的自然信号X本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示。 令x=W s，W为稀疏基矩阵，s为稀疏系数。于是最终方程就变成了： y=ew s。已知y、。、甲，求解s。15. 对应一开始的例子大家就能明白：x就是三个正弦信号叠加在一起的原信 号；稀疏矩阵中就是傅里叶变换，将信号变换到频域S；而观测矩

14、阵0就对应 了我们采用的随机亚采样方式；y就是最终的采样结果。数学表达今。=中甲f。称为彳专感矩阵已知 求解若M=N ,则可轻携而MN ,可根据S|：16. y=6W s有点长，我们把中合并成一个矩阵，称之为传感矩阵。即令0 =6中，则 y=0 So 问题即为，已知y和。，求解So 求解出S后，由x=W s即可得到恢复出的原信号x。然而在正常情况下，方程的个数远小于未知数的个数，方程是没有确定解的，无 法重构信号。但是，由于信号是K稀疏，如果上式中的0满足有限等距性质(RIP)， 则K个系数就能够从M个测量值准确重构(得到一个最优解)。不相关陶哲轩和燮于2005年给出了更为准确的相麹的定义:前

15、提条件2之前已提到，采用随机亚采样才能实现信号的恢复。；|要求:观测矩阵0）应满足约束等距性条件y （Restricted Isometry Property ,简称RIP）:uy即对于任意和常数,有：iSK （17）|1或|脸揆（1+砌或Baraniuk证明:Rl P的等价条件是观测矩阵和稀疏表方(incoherent)y = 4中$一 W火中，中）=扬max I伽人U的范围：四（,申）1,如1色和中越不相17. 接下来的数学内容可以简短略过：陶大神和Candes大神证明了 RIP才是观测 矩阵要满足的准确要求。但是，要确认一个矩阵是否满足RIP非常复杂。于是 Baraniuk证明：RIP的

16、等价条件是观测矩阵和稀疏表示基不相关(incoherent)。这就是压缩感知的第二个前提条件。陶哲轩和知篮证明:独立同分布的高斯随机测量矩阵可以成为晋适I 知测量矩阵18. 那怎样找到不相关的观测矩阵呢？陶哲轩和Candes又证明：独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。于是满足高斯分布的随机测量矩阵就成了 CS最常用的观测矩阵。对于二维信号，往往就采用如右上图所示的采样矩阵对图像进行亚采样。对于一维信号，采用前文提到的随机不等间距的亚采样即可。到这里，我们可以这样用一句话概括地描述什么是压缩感知: 如果一个信号在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测 矩

17、阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就 可以从这些少量的投影中以高概率重构出原信号。以上可以算作是压缩感知的定义吧。但是如果要再简洁一点呢？在我看来，压缩感知可以用这样一句话来表述：直接采集出一个JPEG之前图像压缩的方法是全采样之后再压缩，抛弃稀疏变换域中的一些小系 数；而CS直接减少了采样点，采集完后、经过重建的图像，就是一副在某变换 域稀疏的压缩图像，比如JPEG。那这么做有什么优势呢？对于很多情形，比如照相机拍摄照片，这样减少采样点并没有优势。因为所有像 素的采集在一瞬间就都完成了。但是对于一些采集比较慢的情形，比如核磁共振成像，CS就可以发挥巨大优势。

18、原本一副MRI图像常常需要几十秒，速度慢也是MRI的一大缺陷。而应用CS技 术后，只需要采集全采样几分之一的数据，就可以重建出原图。这样就可以把成 像速度提高好几倍，同时对图像质量影响不大。另一个应用是Rice大学开发的单像素相机，也就是说这种相机只需要一个像素， 非常有趣。感兴趣的朋友可以自己去调查。三、压缩感知的重建方法如前文所述，CS的重建也就是求解欠定方程组y=0S的方法。这是一个零范数 （10）最小化问题，是一个NP完全问题（没有快速解法的问题），因此往往转 换成一范数（11）最小化的求解，或者用一些近似估计的算法。这部分的具体内 容在这里就不再详述了。以上就是压缩感知的简单讲述。各方面都只是浅尝辄止，更多内容需还要大家自 己研究。其实写这篇文章之前我已经做好了受冷落的准备，毕竟不像小波变换，压缩感知 的受众面比较小，理解难度又比较大，大家阅读时还请耐心一点。如果看后能对 压缩感知的主要思想有了一定的认识，也就不枉我费劲力气画了这么多图、码了 这么多字。