压缩感知_压缩感知去噪 - CSDN
压缩感知 订阅
压缩感知(Compressed sensing),也被称为压缩采样(Compressive sampling)或稀疏采样(Sparse sampling),是一种寻找欠定线性系统的稀疏解的技术。压缩感知被应用于电子工程尤其是信号处理中,用于获取和重构稀疏或可压缩的信号。这个方法利用讯号稀疏的特性,相较于奈奎斯特理论,得以从较少的测量值还原出原来整个欲得知的讯号。核磁共振就是一个可能使用此方法的应用。这一方法至少已经存在了四十年,由于David Donoho、Emmanuel Candès和陶哲轩的工作,最近这个领域有了长足的发展。 展开全文
压缩感知(Compressed sensing),也被称为压缩采样(Compressive sampling)或稀疏采样(Sparse sampling),是一种寻找欠定线性系统的稀疏解的技术。压缩感知被应用于电子工程尤其是信号处理中,用于获取和重构稀疏或可压缩的信号。这个方法利用讯号稀疏的特性,相较于奈奎斯特理论,得以从较少的测量值还原出原来整个欲得知的讯号。核磁共振就是一个可能使用此方法的应用。这一方法至少已经存在了四十年,由于David Donoho、Emmanuel Candès和陶哲轩的工作,最近这个领域有了长足的发展。
信息
外文名
Compressed sensing
定    义
是一种寻找欠定线性系统的稀疏解的技术
通    过
开发信号的稀疏特性
用    途
获取和重构稀疏或可压缩的信号
中文名
压缩感知
被称为
压缩采样或稀疏采样
压缩感知基本信息
压缩感知(Compressed sensing),也被称为压缩采样(Compressive sampling),稀疏采样(Sparse sampling),压缩传感 [1]  。它作为一个新的采样理论,它通过开发信号的稀疏特性,在远小于Nyquist 采样率的条件下,用随机采样获取信号的离散样本,然后通过非线性重建算法完美的重建信号 [1]  。压缩感知理论一经提出,就引起学术界和工业界的广泛关注。他在信息论、图像处理、地球科学、光学/微波成像、模式识别、无线通信、生物医学工程等领域受到高度关注,并被美国科技评论评为2007年度十大科技进展。
收起全文
  • 压缩感知原理简介

    千次阅读 多人点赞 2019-07-17 21:16:04
    压缩感知,compressed sensing又称compressed sampling,是在采样过程中完成了数据压缩的过程。 压缩感知在信号采样的过程中,用很少的采样点,实现了和全采样一样的效果。 信号采样 学过通信原理或信号与系统的都...

    压缩感知——简介

    压缩感知,compressed sensing又称compressed sampling,是在采样过程中完成了数据压缩的过程
    压缩感知在信号采样的过程中,用很少的采样点,实现了和全采样一样的效果。

    压缩感知——信号采样

    学过通信原理或信号与系统的都知道奈奎斯特采样定理,即想让采样之后的数字信号完整保留原始信号中的信息,采样频率必须大于信号中最高频率的2倍。原因是时域以τ为间隔进行采样,频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率,信号在频域频谱搬移后就会发生混叠。
    2004年,Candes,陶哲轩和Donoho提出了压缩感知理论,该理论认为:如果信号是稀疏的,那么它可以由远低于采样定理要求的采样点重建恢复。
    突破的关键就在于采样的方式。当我们说“采样频率”的时候,意味着做的是等间距采样,数字信号领域通常都是做等间距采样,也服从奈奎斯特采样定律。
    在这里插入图片描述
    但是压缩感知采用不等间距采样,比如采用随机亚采样(图b上方的红点),那么这时候频域就不再是以固定周期进行延拓了,而是会产生大量不相关(incoherent)的干扰值。如图c,最大的几个峰值还依稀可见,只是一定程度上被干扰值覆盖。这些干扰值看上去非常像随机噪声,但实际上是由于三个原始信号的非零值发生能量泄露导致的(不同颜色的干扰值表示它们分别是由于对应颜色的原始信号的非零值泄露导致的)
    之所以随机亚采样会有这样的效果,可以理解成随机采样使得频谱不再是整齐地搬移,而是一小部分一小部分胡乱地搬移,频率泄露均匀地分布在整个频域,因而泄漏值都比较小,从而有了恢复的可能。

    压缩感知——信号恢复

    压缩感知——两个前提条件

    刚刚的例子之所以能够实现最终信号的恢复,是因为它满足了两个前提条件:

    1. 这个信号在频域只有3个非零值,所以可以较轻松地恢复出它们。
    2. 采用了随机亚采样机制,因而使频率泄露均匀地分布在整个频域。
      这两点对应了CS的两个前提条件——稀疏性(sparsity)不相关性(incoherence)
      稀疏性可以简单直观地理解为:若信号在某个域中只有少量非零值,即信号在某个域中非零点远远小于信号总点数,那么它在该域稀疏,该域也被称为信号的稀疏域
      因此,第一个前提条件要求信号必须在某一个变换域具有稀疏性。比如例子中,信号在频域是稀疏的,因而可以通过所述的重建方法轻松地在稀疏域(频域)复原出原信号。
      然而通常信号在变换域中不会呈现完全的稀疏性。其实只要它近似满足稀疏性,即大部分值趋于零,只有少量大的非零值,就可以认为它是可压缩信号,可以对它进行CS亚采样。
      对于之前讲的例子,如果它在频域中不稀疏,我们可以做DWT、DCT等,找到它的稀疏变换。

    前提条件1——稀疏性在这里插入图片描述

    前提条件2——非相关性/等距约束性

    在讲第二个前提条件之前,需要引入必要的数学表达。
    在这里插入图片描述
    上面这张图把亚采样的过程用矩阵的方式表达出来:
    如图,x是为长度N的一维信号,也就是原信号,稀疏度为k。此刻它是未知的。
    Φ为观测矩阵,对应着亚采样这一过程。它将高维信号x投影到低维空间,是已知的。
    y=Φx为长度M的一维测量值,也就是亚采样后的结果。显然它也是已知的。
    因此,压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上,求解欠定方程组y=Φx得到原信号x。
    然而,一般的自然信号x本身并不是稀疏的,需要在某种稀疏基上进行稀疏表示。令x=Ψs,Ψ为稀疏基矩阵,s为稀疏系数。
    于是最终方程就变成了:y=ΦΨs。已知y、Φ、Ψ,求解s。
    y=ΦΨs有点长,我们把ΦΨ合并成一个矩阵,称之为传感矩阵。即令Θ=ΦΨ ,则y=ΘS。问题即为,已知y和Θ,求解S
    对应到一开始的例子中:
    x就是三个正弦信号叠加在一起的原信号a;
    稀疏矩阵Ψ就是傅里叶变换,将信号变换到频域S;
    观测矩阵Φ就是我们采用的随机亚采样方式;
    y就是最终的随机亚采样的结果c。
    在这里插入图片描述
    求解出S后,由x=Ψs即可得到恢复出的原信号x。
    然而在正常情况下,方程的个数远小于未知数的个数,方程是没有确定解的,无法重构信号。但是,由于信号是K稀疏,如果上式中的Φ满足有限等距性质(RIP),则K个系数就能够从M个测量值准确重构(得到一个最优解)。
    陶哲轩和Candès证明了RIP是观测矩阵要满足的准确要求。但是,要确认一个矩阵是否满足RIP非常复杂。于是Baraniuk证明:RIP的等价条件是观测矩阵和稀疏表示基不相关(incoherent)。即压缩感知的第二个前提条件。
    在这里插入图片描述
    在这里插入图片描述
    那怎样找到不相关的观测矩阵呢?陶哲轩和Candès又证明: 独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。
    于是满足高斯分布的随机测量矩阵就成了CS最常用的观测矩阵。
    对于二维信号,往往就采用二维高斯随机测量采样矩阵对图像进行亚采样。
    对于一维信号,采用前文提到的随机不等间距的亚采样即可。

    压缩感知——重建方法

    信号采样后需要将其恢复。CS的重建也就是求解欠定方程组y=ΘS的方法。这是一个零范数(l0)最小化问题,是一个NP完全问题(没有快速解法的问题),因此往往转换成一范数(l1)最小化的求解,或者用一些近似估计的算法。
    匹配追踪是一种典型的算法。以上文中的例子为例:
    (1) 由于原信号的频率非零值在亚采样后的频域中依然保留较大的值,其中较大的两个可以通过设置阈值,检测出来(图a)。
    (2) 然后,假设信号只存在这两个非零值(图b),则可以计算出由这两个非零值引起的干扰(图c)。
    (3) 用a减去c,即可得到仅由蓝色非零值和由它导致的干扰值(图d),再设置阈值即可检测出它,得到最终复原频域(图e)
    (4) 如果原信号频域中有更多的非零值,则可通过迭代将其一一解出。
    在这里插入图片描述

    扩展:图像压缩与压缩感知

    信号的稀疏性已经在图像压缩领域有了很广泛的应用。利用信号的稀疏性,可以对信号进行压缩。如图像压缩领域的JPEG格式,就是将图像变换到离散余弦域,得到近似稀疏矩阵,只保留较大的值,从而实现压缩。
    图像压缩和压缩感知这两个概念有着本质上的区别。
    图像压缩是先进行了全采样,然后再变换域丢弃小系数,完成压缩;
    而压缩感知不同,它的思想其实从图像压缩中借鉴了很多:既然全采样了还要再丢弃,我们为什么不能直接少采样一些点?因此,压缩感知直接进行了亚采样,然后再用算法消除亚采样导致的伪影。可以说,压缩感知直接在采样时就完成了压缩
    在这里插入图片描述
    这种直接减少采样点,采集完后重建的方式,相比于图像压缩的全采用之后再压缩的方式,对于很多情形,比如照相机拍摄照片,并没有优势。因为所有像素的采集在一瞬间就都完成了。但是对于一些采集比较慢的情形,比如核磁共振成像,CS就可以发挥巨大优势。原本一副MRI图像常常需要几十秒,速度慢也是MRI的一大缺陷。而应用CS技术后,只需要采集全采样几分之一的数据,就可以重建出原图。这样就可以把成像速度提高好几倍,同时对图像质量影响不大。

    总结

    什么是压缩感知:
    如果一个信号在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。
    压缩感知理论主要包括三部分:
    (1)信号的稀疏表示;
    (2)设计测量矩阵,要在降低维数的同时保证原始信号x的信息损失最小;
    (3)设计信号恢复算法,利用M个观测值无失真地恢复出长度为N的原始信号。

    从06年提出至今,已经发展出了很多算法,原来的基于l1 minimization的BP算法很慢,现在都是快速算法,而且求解算法也从纯优化方面扩展到了estimation方面,有很多基于贝叶斯估计的方法了,目前最火的也是Donoho他们组搞得AMP算法,是用Graph model里面的message passing算法通过近似求解MMSE(MAP)解。在测量矩阵方面,也已经设计出了各种矩阵,除了i.i.d. Gaussian的矩阵还有很多正交的矩阵,比如partial random DFT/DCT 矩阵。对信号的要求也从稀疏变成了存在某种结构,比如low rank,group sparse等等。(2017年进展)

    压缩感知和矩阵填充

    矩阵填充的要领是通过低秩矩阵中的已知要素还原出该矩阵的其他未知要素的进程。这几年,关于矩阵填充方法的理论研究成为压缩感知技术的一个研究热点。在实际的应用领域中涉及对高维数据的分析与处理,可以运用矩阵填充的方法来解决。其过程主要是:通过观测到的局部数据来准确填充缺失数据,从而获得完整数据矩阵的过程。
    压缩感知和矩阵填充都是稀疏约束下的反问题,压缩感知利用信号本身或在变换域中的稀疏约束性求解欠定方程,矩阵填充利用矩阵的低秩约束性求解欠定方程。
    压缩感知理论的核心问题是信号的稀疏表示、观测矩阵的设计和重构算法,信号本身或在变换域中的系数越稀疏,观测矩阵和稀疏基构成的压缩感知矩阵的受限等距常数越小,则压缩感知的性能越好。
    矩阵填充理论的核心问题是矩阵的低秩特性、非相干特性和重构算法,寻找性能良好的重构算法一直是矩阵填充理论中的一个研究重点。此外,压缩感知的应用领域已经拓展得较为广泛,但矩阵填充的应用尚处于起步阶段,挖掘矩阵填充的应用,进而将矩阵填充和压缩感知结合起来进行应用方面的探索,是非常重要和有意义的课题。
    压缩感知的性能取决于3个要素:信号的稀疏性、压缩感知矩阵的非相干性和重构算法的快速有效性。
    矩阵填充性能也取决于3个要素:矩阵的低秩性、矩阵的不相关性和重构算法的快速有效性。

    低秩矩阵

    还记得我们怎么手工求矩阵的秩吗?为了求矩阵A的秩,我们是通过矩阵初等变换把A化为阶梯型矩阵,若该阶梯型矩阵有r个非零行,那A的秩rank(A)就等于r。从物理意义上讲,矩阵的秩度量的就是矩阵的行列之间的相关性。如果矩阵的各行或列是线性无关的,矩阵就是满秩的,也就是秩等于行数。回到上面线性方程组来说吧,因为线性方程组可以用矩阵描述嘛。秩就表示了有多少个有用的方程了。上面的方程组有3个方程,实际上只有2个是有用的,一个是多余的,所以对应的矩阵的秩就是2了。
    OK。既然秩可以度量相关性,而矩阵的相关性实际上就表示了矩阵的结构信息。如果矩阵之间各行的相关性很强,那么就表示这个矩阵实际可以投影到更低维的线性子空间,也就是用几个向量就可以完全表达了,它就是低秩的。所以我们总结的一点就是:如果矩阵表达的是结构性信息,例如图像、用户-商品推荐表等等,那么这个矩阵各行之间存在这一定的相关性,那这个矩阵一般就是低秩的。
    如果X是一个m行n列的数值矩阵,rank(X)是X的秩,假如rank (X)远小于m和n,则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出,可见它包含大量的冗余信息。利用这种冗余信息,可以对缺失数据进行恢复,也可以对数据进行特征提取。

    应用

    矩阵填充越来越多的应用在协同滤波、系统识别、无线传感网络、视频去噪、人脸识别、医学成像等领域,正在发挥着巨大的作用。特别是在室内定位中的 应用越来越多,是当下的研究热点之一。

    参考网址:
    形象易懂讲解算法II——压缩感知(非常好)
    AndyJee:浅谈压缩感知系列——博客园(非常丰富)
    压缩感知理论
    机器学习——低秩矩阵分解中低秩的意义、矩阵填补、交叉验证

    展开全文
  • 压缩感知MATLAB程序

    2020-07-30 23:33:24
    压缩感知,又称压缩采样,压缩传感。它作为一个新的采样理论,它通过开发信号的稀疏特性,在远小于Nyquist 采样率的条件下,用随机采样获取信号的离散样本,然后通过非线性重建算法完美的重建信号。压缩感知理论一经...
  • 形象易懂讲解算法——压缩感知

    万次阅读 多人点赞 2018-10-16 11:15:00
    在我看来,压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果之一,并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学表述背后蕴含着非常精妙的思想。基于一个有想象力的思路,辅以...

    转自知乎大神的文章:https://zhuanlan.zhihu.com/p/22445302
    在我看来,压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果之一,并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学表述背后蕴含着非常精妙的思想。基于一个有想象力的思路,辅以严格的数学证明,压缩感知实现了神奇的效果,突破了信号处理领域的金科玉律——奈奎斯特采样定律。即,在信号采样的过程中,用很少的采样点,实现了和全采样一样的效果。

    正是被它的精妙思想所打动,我选择它作为专栏第二篇的主题。理解压缩感知的难度可能要比之前讲的小波还要大,但是我们从中依然可以梳理出清晰的脉络。这篇文章的目标和之前一样,我将抛弃复杂的数学表述,用没有公式的语言讲清楚压缩感知的核心思路,尽量形象易懂。我还绘制了大量示意图,因为排版问题,我将主要以PPT的形式呈现,并按slice标好了序号。


    一、什么是压缩感知(CS)?
    compressed sensing又称compressed sampling,似乎后者看上去更加直观一些。没错,CS是一个针对信号采样的技术,它通过一些手段,实现了“压缩的采样”,准确说是在采样过程中完成了数据压缩的过程。

    因此我们首先要从信号采样讲起:
    1模拟信号采样

    1. 我们知道,将模拟信号转换为计算机能够处理的数字信号,必然要经过采样的过程。问题在于,应该用多大的采样频率,即采样点应该多密多疏,才能完整保留原始信号中的信息呢?

    2奈奎斯特采样定理
    2. 奈奎斯特给出了答案——信号最高频率的两倍。一直以来,奈奎斯特采样定律被视为数字信号处理领域的金科玉律。

    奈奎斯特的原理
    3. 至于为什么是两倍,学过信号处理的同学应该都知道,时域以τ为间隔进行采样,频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率,信号在频域频谱搬移后就会发生混叠

    提出了压缩感知理论
    4. 然而这看似不容置疑的定律却受到了几位大神的挑战。Candes最早意识到了突破的可能,并在不世出的数学天才陶哲轩以及Candes的老师Donoho的协助下,提出了压缩感知理论,该理论认为:如果信号是稀疏的,那么它可以由远低于采样定理要求的采样点重建恢复。

    压缩感知介绍
    5. 而突破的关键就在于采样的方式。当我们说“采样频率”的时候,意味着做的是等间距采样,数字信号领域通常都是做等间距采样,也服从奈奎斯特采样定律。
    但是如果是不等间距采样呢?依然必须要服从采样定理吗?

    压缩感知采样
    6. 答案是,随机的亚采样给了我们恢复原信号的可能。
    上图非常关键,它可以简单直观地表述压缩感知的思路。 如图b、d为三个余弦函数信号叠加构成的信号,在频域的分布只有三条线(图a)。 如果对其进行8倍于全采样的等间距亚采样(图b下方的红点),则频域信号周期延拓后,就会发生混叠(图c),无法从结果中复原出原信号。

    压缩感知采样
    7. 而如果采用随机亚采样(图b上方的红点),那么这时候频域就不再是以固定周期进行延拓了,而是会产生大量不相关(incoherent)的干扰值。如图c,最大的几个峰值还依稀可见,只是一定程度上被干扰值覆盖。这些干扰值看上去非常像随机噪声,但实际上是由于三个原始信号的非零值发生能量泄露导致的(不同颜色的干扰值表示它们分别是由于对应颜色的原始信号的非零值泄露导致的)

    P.S:为什么随机亚采样会有这样的效果?
    这可以理解成随机采样使得频谱不再是整齐地搬移,而是一小部分一小部分胡乱地搬移,频率泄露均匀地分布在整个频域,因而泄漏值都比较小,从而有了恢复的可能。

    压缩感知恢复
    8. 接下来的关键在于,信号该如何恢复? 下面讲一种典型的算法(匹配追踪):
    (1) 由于原信号的频率非零值在亚采样后的频域中依然保留较大的值,其中较大的两个可以通过设置阈值,检测出来(图a)。
    (2) 然后,假设信号只存在这两个非零值(图b),则可以计算出由这两个非零值引起的干扰(图c)。
    (3) 用a减去c,即可得到仅由蓝色非零值和由它导致的干扰值(图d),再设置阈值即可检测出它,得到最终复原频域(图e)
    (4) 如果原信号频域中有更多的非零值,则可通过迭代将其一一解出。

    以上就是压缩感知理论的核心思想——以比奈奎斯特采样频率要求的采样密度更稀疏的密度对信号进行随机亚采样,由于频谱是均匀泄露的,而不是整体延拓的,因此可以通过特别的追踪方法将原信号恢复。


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

    前提条件
    10. 关于稀疏性可以这样简单直观地理解:若信号在某个域中只有少量非零值,那么它在该域稀疏,该域也被称为信号的稀疏域。
    因此,第一个前提条件要求信号必须在某一个变换域具有稀疏性。比如例子中,信号在频域是稀疏的,因而可以通过所述的重建方法轻松地在稀疏域(频域)复原出原信号。

    前提条件
    然而通常信号在变换域中不会呈现完全的稀疏性。其实只要它近似满足稀疏性,即大部分值趋于零,只有少量大的非零值,就可以认为它是可压缩信号,可以对它进行CS亚采样。
    对于之前讲的例子,如果它在频域中不稀疏,我们可以做DWT、DCT等,找到它的稀疏变换。

    稀疏性
    11. 这里针对信号的稀疏性和信号压缩额外补充一下:其实,信号的稀疏性已经在图像压缩领域有了很广泛的应用。利用信号的稀疏性,可以对信号进行压缩。如图像压缩领域的JPEG格式,就是将图像变换到离散余弦域,得到近似稀疏矩阵,只保留较大的值,从而实现压缩。

    稀疏性
    12. 比如这个例子中,仅用原图像6.9%的点就复原了和原图像基本相同的图像。我们还可以采用小波变换,即为JPEG-2000,压缩效果更好。

    补充知识
    13. 这里需要指出,图像压缩和压缩感知这两个概念很容易弄混,大家一定要分清。
    它们其实有着本质上的区别。图像压缩是先进行了全采样,然后再变换域丢弃小系数,完成压缩;
    而压缩感知不同,它的思想其实从图像压缩中借鉴了很多:既然全采样了还要再丢弃,我们为什么不能直接少采样一些点?因此,压缩感知直接进行了亚采样,然后再用算法消除亚采样导致的伪影。可以说,压缩感知直接在采样时就完成了压缩。

    数学表达
    14. 接下来,在将第二个前提条件之前,还是需要引入必要的数学表达的。上图是一个大家在压缩感知相关的书籍文献中会经常看到的一张示意图。很多文章试图用这张图给大家讲清楚什么是压缩感知,结果导致大家看得一头雾水,混淆在各种“矩阵”当中。。不过相信有了我之前的讲解,现在这张图会好理解很多。这张图也就是把亚采样的过程用矩阵的方式表达出来而已:
    如图,x是为长度N的一维信号,也就是原信号,稀疏度为k。此刻它是未知的。
    Φ为观测矩阵,对应着亚采样这一过程。它将高维信号x投影到低维空间,是已知的。
    y=Φx为长度M的一维测量值,也就是亚采样后的结果。显然它也是已知的。
    因此,压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上,求解欠定方程组y=Φx得到原信号x。
    然而,一般的自然信号x本身并不是稀疏的,需要在某种稀疏基上进行稀疏表示。令x=Ψs,Ψ为稀疏基矩阵,s为稀疏系数。
    于是最终方程就变成了:y=ΦΨs。已知y、Φ、Ψ,求解s。

    数学表达
    15. 对应一开始的例子大家就能明白:x就是三个正弦信号叠加在一起的原信号;稀疏矩阵Ψ就是傅里叶变换,将信号变换到频域S;而观测矩阵Φ就对应了我们采用的随机亚采样方式;y就是最终的采样结果。

    数学表达
    16. y=ΦΨs有点长,我们把ΦΨ合并成一个矩阵,称之为传感矩阵。即令Θ=ΦΨ ,则y=ΘS。问题即为,已知y和Θ,求解S。
    求解出S后,由x=Ψs即可得到恢复出的原信号x。
    然而在正常情况下,方程的个数远小于未知数的个数,方程是没有确定解的,无法重构信号。但是,由于信号是K稀疏,如果上式中的Φ满足有限等距性质(RIP),则K个系数就能够从M个测量值准确重构(得到一个最优解)。

    前提条件2
    前提条件2
    17.接下来的数学内容可以简短略过:陶大神和Candès大神证明了RIP才是观测矩阵要满足的准确要求。但是,要确认一个矩阵是否满足RIP非常复杂。于是Baraniuk证明:RIP的等价条件是观测矩阵和稀疏表示基不相关(incoherent)。

    这就是压缩感知的第二个前提条件。

    测量矩阵
    18. 那怎样找到不相关的观测矩阵呢?陶哲轩和Candès又证明: 独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。

    于是满足高斯分布的随机测量矩阵就成了CS最常用的观测矩阵。
    对于二维信号,往往就采用如右上图所示的采样矩阵对图像进行亚采样。
    对于一维信号,采用前文提到的随机不等间距的亚采样即可。


    到这里,我们可以这样用一句话概括地描述什么是压缩感知:
    如果一个信号在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。
    以上可以算作是压缩感知的定义吧。但是如果要再简洁一点呢?
    在我看来,压缩感知可以用这样一句话来表述:
    直接采集出一个JPEG
    ——之前图像压缩的方法是全采样之后再压缩,抛弃稀疏变换域中的一些小系数;而CS直接减少了采样点,采集完后、经过重建的图像,就是一副在某变换域稀疏的压缩图像,比如JPEG。

    那这么做有什么优势呢?
    对于很多情形,比如照相机拍摄照片,这样减少采样点并没有优势。因为所有像素的采集在一瞬间就都完成了。
    但是对于一些采集比较慢的情形,比如核磁共振成像,CS就可以发挥巨大优势。原本一副MRI图像常常需要几十秒,速度慢也是MRI的一大缺陷。而应用CS技术后,只需要采集全采样几分之一的数据,就可以重建出原图。这样就可以把成像速度提高好几倍,同时对图像质量影响不大。
    另一个应用是Rice大学开发的单像素相机,也就是说这种相机只需要一个像素,非常有趣。感兴趣的朋友可以自己去调查。


    三、压缩感知的重建方法
    如前文所述,CS的重建也就是求解欠定方程组y=ΘS的方法。这是一个零范数(l0)最小化问题,是一个NP完全问题(没有快速解法的问题),因此往往转换成一范数(l1)最小化的求解,或者用一些近似估计的算法。这部分的具体内容在这里就不再详述了。

    展开全文
  • 白话压缩感知(含Matlab代码)

    万次阅读 多人点赞 2014-08-25 17:31:38
    压缩感知介绍压缩感知(Compressive Sensing,CS),有时也叫成Compressive Sampling。相对于传统的奈奎斯特采样定理——要求采样频率必须是信号最高频率的两倍或两倍以上(这就要求信号是带限信号,通常在采样前...

    压缩感知介绍

    压缩感知(Compressive Sensing,CS),有时也叫成Compressive Sampling。相对于传统的奈奎斯特采样定理——要求采样频率必须是信号最高频率的两倍或两倍以上(这就要求信号是带限信号,通常在采样前使用低通滤波器使信号带限),压缩感知则利用数据的冗余特性,只采集少量的样本还原原始数据。

    这所谓的冗余特性,借助MLSS2014马毅老师的课件上的例子来说明,

    data_property

    因为自然界的数据都存在局部低维结构、周期性、对称性等,因此,传统的固定采样率的采样方法必然存在信息冗余。由于信息冗余的存在,我们就知道有数据压缩那么一门学科。既然这样,为什么要把冗余的数据也采进来,再进行压缩呢,能不能不把冗余的数据采集进来?

    压缩感知的思路就是:在采集的过程中就对数据进行了压缩,而且这种压缩能保证不失真(低失真)的恢复原始数据,这与传统的先2倍频率采集信号→存储→再压缩的方式不同,可以降低采集信号的存储空间和计算量。

    好了,那么就来了解一下压缩感知的具体模型。

    1. 稀疏表示

    使用压缩感知理论首先要求信号能表示为稀疏信号,如x=[1 0 0 0 1 0],其中只有2个1,可认为是稀疏的。我们将信号通过一个矩阵映射到稀疏空间,

    设信号x为N维,即,则为NxN维稀疏表达矩阵,s即是将x进行稀疏表示后的Nx1维向量,其中大部分元素值为0。稀疏表示的原理就是通过线性空间映射,将信号在稀疏空间进行表示。

    比如,信号

    在时域是非稀疏的,但做傅里叶变换表示成频域后,只有少数几个点为非0(如下图)。则该信号的时域空间为非稀疏,频域空间为稀疏空间,组成的矩阵。一般为正交矩阵。

    example1

    若稀疏表示后的结果s中只有k个值不为0,则称x的稀疏表示为k-Sparse。上图对x的频域稀疏表示就是2-Sparse。

    2. 感知测量

    压缩感知的目的是在采集信号时就对数据进行压缩,大牛们的思路集中到了数据采集上——既然要压缩,还不如就从大量的传感器中只使用其中很少的一部分传感器,采集少量的冗余度低的数据。这就是感知测量的通俗的说法,用表达式表示

    其中的x就是稀疏表示中的信号,为MxN维的感知矩阵(M表示测量信号的维度),y则表示M(M远小于N才有意义)个传感器的直接测量,因此维度为Mx1。

    将稀疏表示过程和感知测量过程综合起来:

    Sparse

    数学描述

    对于压缩感知模型,其中每个量的维度一定要了解(通过维度的变化来理解压缩感知很有效):

    yax

    从感知测量中知道:M就是测量的维度(M远小于N)。

    压缩感知的原信号恢复问题描述为:

    由已知条件:

    (1) 测量值y,且,其中e为噪声引入

    (2) s为k-Sparse信号(k未知)

    求解目标:k尽可能小的稀疏表示信号s及对应的

    用数学形式描述为:

    e可以看成告诉随机噪声,e~N(0,δ2)。

    即是要求s使s的0范数(非0值的个数)最小,但0范数优化问题是很难求解的,于是一帮大牛就证明求解1范数也能逼近和上面相同的效果,而求解2范数及其更高的范数则结果相差越来越大(有些人在研究介于0范数与1范数之间的范数求解方法)。因此可转化为1范数求解:

    由拉格朗日乘子法,上面的最优问题可转化成:

    上面的最小值求解问题就可以直接通过凸优化解得结果了。

    程序分析

    先下载CVX或spams工具箱,下面的matlab程序分别使用了时域稀疏信号和频域稀疏信号进行测试,两种不同在于时域稀疏信号不用稀疏表达矩阵(因此稀疏表达矩阵使用单位阵即可),而频域稀疏信号则需要先通过稀疏表达矩阵将信号在频域进行稀疏表示,再压缩感知后进行恢复时也要进行反FFT变换到时域。

    关于M的选取:测量数M>=K*log(N/K),K是稀疏度,N信号长度,可以近乎完全重构

    clc
    clear all
    close all
    
    %% 产生原始信号及相关参数
    n = 512;                          % 信号长度
    s = 25;                           % 稀疏度(从下面知道,分时域和频域的情况)
    m = 5*s;                          % 测量长度 M>=S*log(N/S)
    freq_sparse = 0;                  % 信号频域稀疏则为1
    
    if freq_sparse
        t = [0: n-1]';
        f = cos(2*pi/256*t) + sin(2*pi/128*t);   % 产生频域稀疏的信号
    else
        tmp = randperm(n);    
        f = zeros(n,1);
        f(tmp(1:s)) = randn(s,1);     % 产生时域稀疏的信号
    end
    
    %% 产生感知矩阵和稀疏表示矩阵
    Phi = sqrt(1/m) * randn(m,n);     % 感知矩阵(测量矩阵)
    % A = get_A_fourier(n, m);
    
    y = Phi * f;                      % 通过感知矩阵获得测量值
                                      % Psi 将信号变换到稀疏域
    if freq_sparse                    % 信号频域可以稀疏表示
        Psi = inv(fft(eye(n,n)));     % 傅里叶正变换,频域稀疏正交基(稀疏表示矩阵)
    else                              % 信号时域可以稀疏表示
        Psi = eye(n, n);              % 时域稀疏正交基
    end
    A = Phi * Psi;                    % 恢复矩阵 A = Phi * Psi
    
    %% 优化方法1:使用CVX工具进行凸优化
    addpath('../../cvx-w64/cvx/');
    cvx_startup;                            % 设置cvx环境
    cvx_begin
        variable xp(n) complex;               % 如果xp是复数,则添加complex,否则不加
        minimize (norm(xp, 1));
        subject to
            A * xp == y;      
    cvx_end
    
    %% 优化方法2:使用spams工具箱进行优化
    % addpath('spams-matlab/build');
    % param.L = 100;
    % param.eps = 0.001;
    % param.numThreads = -1;
    % 
    % A=A./repmat(sqrt(sum(A.^2)),[size(A,1) 1]);
    % xp = mexOMP(y, A, param);       % 正交匹配追踪法Orthogonal Matching Pursuit
    
    %% 对比原信号和
    if freq_sparse
        xp = real(ifft(full(xp)));           % 傅里叶逆变换
    else
    
    end
    plot(f+noise);
    hold on
    plot(real(xp), 'r.');
    legend('Original', 'Recovered');
    
    1. 设程序中的freq_sparse = 0时,观察时域稀疏信号的恢复结果为

      time

      在恢复时域稀疏信号时,所使用的测量矩阵Phi为初始化的随机阵,因为本身时域就稀疏,而算法直接在时域进行恢复,所以稀疏表达矩阵就是单位阵Psi=E。上面的时域稀疏恢复结果显得没有误差是因为没有给原始信号添加噪声。

    2. 设程序中的freq_sparse = 1时,观察频域稀疏信号的恢复结果为

      freq

      在恢复时域稀疏信号时,所使用的测量矩阵Phi为初始化的随机阵,因为信号只在频域稀疏,所以稀疏变换矩阵为傅里叶变换基,所以稀疏表达矩阵就是Psi = inv(fft(eye(n,n)))。同理,上面的频域稀疏恢复结果显得没有误差是因为没有给原始信号添加噪声。

    3. 上面都是没有添加噪声的算法结果,我们给信号添加一些噪声,以时域信号为例,

      if freq_sparse
          t = [0: n-1]';
          f = cos(2*pi/256*t) + sin(2*pi/128*t);   % 产生频域稀疏的信号
      else
          tmp = randperm(n);    
          f = zeros(n,1);
          f(tmp(1:s)) = randn(s,1);     % 产生时域稀疏的信号
      end
      
      noise = random('norm', 0, 0.01, [n 1]);
      f = f + noise;                    % 添加噪声
      
      %% Remaining code not changed
      

      从下图的恢复结果看,已经能看到一些恢复误差了,

      err

    展开全文
  • 初识压缩感知Compressive Sensing

    万次阅读 多人点赞 2012-10-23 11:01:03
    压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。最近粗浅地看了这方面一些研究,对于Compressive Sensing有了初步理解,在此分享一些资料与精华。本文针对陶哲轩和Emmanuel Candes上次到北京的...

    压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。最近粗浅地看了这方面一些研究,对于Compressive Sensing有了初步理解,在此分享一些资料与精华。本文针对陶哲轩和Emmanuel Candes上次到北京的讲座中对压缩感知的讲解进行讲解,让大家能够对这个新兴领域有一个初步概念。


    compressive sensing(CS) 又称 compressived sensing ,compressived sample,大意是在采集信号的时候(模拟到数字),同时完成对信号压缩之意。中文的翻译成“压缩感知”,意思变得至少不太好理解了。


    Compressed sensing is a mathematical tool that creates hi-res data sets from lo-res samples. It can be used to resurrect old musical recordings, find enemy radio signals, and generate MRIs much more quickly. Here’s how it would work with a photograph.





    /***********************Compressive Sensing研究背景***********************/

    (1)CS大约是2000年左右的一篇博士论文中,已经出现了雏形。后来被陶哲轩,C牛(Emmanuel Candes)和D(Donoho)牛,完善理论。这几位顶尖高手联手挖出了信号处理领域、机器学习领域,近10年最大的学术大坑。
    2004年左右,大牛们聊天,觉得要起一个简单的名字,因为理论本身是“通过对信号的高度不完备线性测量的高精确的重建”,如果这样名字不响,不能起到理论推广作用。所以就成了现在的名字"compressive sensing"。


    (2)陶哲轩,是这个世界上最聪明的人,他怎么会关注到CS呢?陶哲轩是这个世界上搞调和分析的顶尖高手之一(当然他别的方面也很厉害)。
     压缩感知的发现是一次意外,话说一天,当时是加州理工学院教授(现在去了斯坦福)的Emmanuel Candès在研究名叫Shepp-Logan Phantom的图像,这种标准图像常被计算机科学家和工程师测试图像算法。Candès检查的图像质量非常差,充满了噪声,他认为名叫L1-minimization的数学算法能去除掉噪声条纹,结果算法真的起作用了,突然就觉得好神奇哦,“It was as if you gave me the first three digits of a 10-digit bank account number — and then I was able to guess the next seven,” he says.  He tried rerunning the experiment on different kinds of phantom images; they resolved perfectly every time.。而且在图像变干净的同时,他发现图像的细节出人意料的完美起来。


    某一日Candes去幼儿园接孩子,正好遇上了也在接孩子的陶哲轩,两人攀谈的过程中他提到了自己手头的困难,于是陶哲轩也开始想这个问题,它们成为两人合作的压缩感知领域第一篇论文的基础。Emmanuel Candès认为压缩感知(简写CS)技术具有广阔的应用前景,比如MRI,数码相机。数码相机镜头收集了大量的数据,然后再压缩,压缩时丢弃掉90%的数据。如果有CS,如果你的照相机收集了如此多的数据只是为了随后的删除,那么为什么不一开始就丢弃那90%的数据,直接去除冗余信息不仅可以节省电池电量,还能节省空间




    /***********************大牛介绍***********************/

    陶哲轩澳籍华人数学家,童年时期即天资过人,目前主要研究调和分析偏微分方程组合数学解析数论表示论24岁起,他在加利福尼亚大学洛杉矶分校担任教授。他现在为该校终身数学教授。

    Emmanuel Candes (C牛)是斯坦福大学的数学、统计学,电子工程荣誉教授,同时也是应用计算数学领域的教授。他的 研究领域主要是在这种数学协调分析、数学优化、统计估测,以及在影像科学、信号研究。 Emmanuel Candes  授曾获数项国际奖项,包括国家科学基金会最高个人奖项(该奖项主要奖励 35 岁以下的学者)、 2008 年信息社 会理论论文奖,以及国际行业应用数学学会授予的奖项等等。

    David Donoho   WaveLab是小波和相关的时频变换的一个Matlab例程库,由美国斯坦福大学donoho维护






    /***********************基本思想
    ***********************/

    压缩感知的概念:

    将未知的要获得的信号记为AK,它是一个波形。我们希望它越不连续越好,越扩散越好,而我所要做的是按照 一定的顺序获得图像信号的信息。我们按照高斯分布来收集数据,而不是线性的,所以我们只会有少量的感测次数,而这些数据 的相关性非常低。

    压缩的意思,是指比较先前及当前数据的差异,并记录下这些差异而减少 需储存的资料量。对于压缩感知的问题比压缩难多了,像是我们要收集怎样分布的数据、如何收集、保留一些什 么系数,从而得到最佳的结果。我们会得到一些机变,保留最大的,最有意义的系数在里头。我们可以做一些抽样,把最重要的保留下来。一个信号,我们知道它是非常好的,但这个信号完全是稀疏的,可能并不是我们要损失掉的。

    对核磁共振的图像,来看一下这些系数, 6000 个不连续性系数,我说我们只 要看 1800 不连续的测量,让我们看有什么变化,让我们看看重建后的图片,这些图片是非常接近真实图像的, 我们可以用少于三倍或甚至四倍的测量次数而得到一个非常接近的结果。



    感知压缩难点在于,压缩后的数据并不是压缩前的数据的一个子集,并不是说,本来有照相机的感光器上有一千万个像素,扔掉其中八百万个,剩下的两百万个采集到的就是压缩后的图像,──这样只能采集到不完整的一小块图像,有些信息被永远的丢失了而且不可能被恢复。

    如果要想采集很少一部分数据并且指望从这些少量数据中「解压缩」出大量信息,就需要保证:第一:这些少量的采集到的数据包含了原信号的全局信息,第二:存在一种算法能够从这些少量的数据中还原出原先的信息来。


    有趣的是,在某些特定的场合,上述第一件事情是自动得到满足的。最典型的例子就是医学图像成像,例如断层扫描(CT)技术和核磁共振(MRI)技术。对这两种技术稍有了解的人都知道,这两种成像技术中,仪器所采集到的都不是直接的图像像素,而是图像经历过全局傅立叶变换后的数据。也就是说,每一个单独的数据都在某种程度上包含了全图像的信息。在这种情况下,去掉一部分采集到的数据并不会导致一部分图像信息永久的丢失(它们仍旧被包含在其它数据里)。这正是我们想要的情况。
    上述第二件事就要归功于陶哲轩和坎戴的工作了。他们的工作指出,如果假定信号(无论是图像还是声音还是其他别的种类的信号)满足某种特定的「稀疏性」,那么从这些少量的测量数据中,确实有可能还原出原始的较大的信号来,其中所需要的计算部分是一个复杂的迭代优化过程,即所谓的「L1-最小化」算法。


    把上述两件事情放在一起,我们就能看到这种模式的优点所在。它意味着:我们可以在采集数据的时候只简单采集一部分数据(「压缩感知」),然后把复杂的部分交给数据还原的这一端来做,正好匹配了我们期望的格局。在医学图像领域里,这个方案特别有好处,因为采集数据的过程往往是对病人带来很大麻烦甚至身体伤害的过程。以 X 光断层扫描为例,众所周知 X 光辐射会对病人造成身体损害,而「压缩感知」就意味着我们可以用比经典方法少得多的辐射剂量来进行数据采集,这在医学上的意义是不言而喻的。






    /***********************基本概念详细说明举例***********************/

    本部分为陶哲轩在一篇blog中对于comprehensive sensing 文章翻译过来的精华部分提取了重点并加入了一些理解,这里用来解释CS的概念堪称经典。


    相机的用途,自然是记录图像。为了简化论述,我们把图像假设成一个长方形阵列,比如说一个1024×2048像素的阵列(这样就总共是二百万像素)。为了省略彩色的问题(这个比较次要),我们就假设只需要黑白图像,那么每个像素就可以用一个整型的灰度值来计量其亮度(例如用八位整型数表示0到255,16位表示0到65535)。接下来,按照最最简化的说法,传统相机会测量每一个像素的亮度(在上述例子中就是二百万个测量值),结果得到的图片文件就比较大(用8位灰度值就是2MB(1024*2048*8b),16位灰度就是4MB)。数学上就认为这个文件是用超高维矢量值描绘的(在本例中就是约二百万维),进行。
    在我开始讲“压缩感知”这个新故事之前,必须先快速回顾一下“老式压缩”的旧故事。(已经了解图像压缩算法的读者可以跳过这几段。)


    老式压缩:

    怎么样压缩图像?方式多种多样,其中有些非常先进,不过我来试试用一种不太高科技的(而且也不太精确的)说法来描述一下这些先进技术。图像通常都含有大片无细节部分–比如在风景照里面,将近一半的画面都可能被单色的天空背景占据。我们假设提取一个大方块,比方说100×100像素,其中完全是同一颜色的——假设是全白的吧。无压缩时,这个方块要占10000字节存储空间(按照8位灰度算);但是我们可以只记录这个方块的维度和坐标,还有填充整个方块的单一颜色;这样总共也只要记录四五个字节,省下了可观的空间。不过在现实中,压缩效果没有这么好,因为表面看来没有细节的地方其实是有着细微的色差的。所以,给定一个无细节方块,我们记录其平均色值,就把图片中这一块区域提取出来,只留下微小的残余误差。接下来就可以继续选取更多无细节的方块,抽象成单色色块。最后剩下的是亮度(色彩强度)很小的,肉眼无法察觉的细节。于是就可以抛弃这些剩余的细节,只需要记录那些“可见”色块的大小,位置和亮度。日后则可以反向操作,重建出比原始图像质量稍低一些,占空间却小得多的复制图片。


    其实上述的算法并不适合处理颜色剧烈变动的情况,所以在实际应用中不很有效。事实上,更好的办法不是用均匀色块,而是用“不均匀”的色块——比方说右半边色彩强度平均值大于左半边这样的色块。这种情况可以用(二维)Haar小波系统来描述。后来人们又发现一种”更平滑的”小波系统更能够避免误差,不过这都是技术细节,我们就不深入讨论了。然而所有这些系统的原理都是相同的:把原始图像表示为不同“小波(类似于上文中的色块)”的线性叠加,记录显著的(高强度的)小波的系数,放弃掉(或者用阈值排除掉)剩下的小波系数。这种“小波系数硬阈值”压缩算法没有实际应用的算法(比如JPEG 2000标准中所定义的)那么精细,不过多少也能描述压缩的普遍原理。


    总体来讲(也是非常简化的说法),原始的1024×2048图像可能含有两百万自由度,想要用小波来表示这个图像的人需要两百万个不同小波才能完美重建。但是典型的有意义的图像,从小波理论的角度看来是非常稀疏的,也就是可压缩的:可能只需要十万个小波就已经足够获取图像所有的可见细节了,其余一百九十万小波只贡献很少量的,大多数观测者基本看不见的“随机噪声”。(这也不是永远适用:含有大量纹理的图像–比如毛发、毛皮的图像——用小波算法特别难压缩,也是图像压缩算法的一大挑战。But that is another story。)


    接下来呢,如果我们(或者不如说是相机)事先知道两百万小波系数里面哪十万个是重要的,那camera就可以只计算这十万个系数,别的就不管了。(对于单个系数的计算,可以在图像上应用一种合适的filter“滤波器”或叫mask“滤镜/掩模”,然后计量过滤出来的每个像素的色彩强度)但是,相机是不会知道哪个系数是重要的,所以它只好计量全部两百万个像素,把整个图像转换成基本小波,找出需要留下的那十万个主导基本小波,再删掉其余的。(这当然只是真正的图像压缩算法的一个草图,不过为了便于讨论我们还是就这么用吧。)


    PS: 经典的数据压缩技术,无论是音频压缩(例如 mp3),图像压缩(例如 jpeg),视频压缩(mpeg),还是一般的编码压缩(zip),都是从数据本身的特性出发,寻找并剔除数据中隐含的冗余度,从而达到压缩的目的。这样的压缩有两个特点:第一、它是发生在数据已经被完整采集到之后;第二、它本身需要复杂的算法来完成。相较而言,解码过程反而一般来说在计算上比较简单,以音频压缩为例,压制一个 mp3 文件的计算量远大于播放(即解压缩)一个 mp3 文件的计算量。

    那么,如今的数码相机当然已经很强大了,没什么问题干吗还要改进?事实上,上述的算法,需要收集大量数据,但是只需要存储一部分,在消费摄影中是没有问题的。尤其是随着数据存储变得很廉价,现在拍一大堆完全不压缩的照片也无所谓。而且,尽管出了名地耗电,压缩所需的运算过程仍然算得上轻松。但是,在非消费领域的某些应用中,这种数据收集方式并不可行,特别是在传感器网络中。如果打算用上千个传感器来收集数据,而这些传感器需要在固定地点呆上几个月那么长的时间,那么就需要尽可能地便宜和节能的传感器——这首先就排除了那些有强大运算能力的传感器(然而——这也相当重要——我们在接收处理数据的接收端仍然需要现代科技提供的奢侈的运算能力)。在这类应用中,数据收集方式越“傻瓜”越好(而且这样的系统也需要很强壮,比如说,能够忍受10%的传感器丢失或者各种噪声和数据缺损)。所谓的「压缩感知」,也就是说,直接感知压缩了的信息。


    压缩感知

    就是压缩感知的用武之地了。其理论依据是:如果只需要10万个分量就可以重建绝大部分的图像,那何必还要做所有的200万次测量,只做10万次不就够了吗?(在实际应用中,我们会留一个安全余量,比如说测量30万像素,以应付可能遭遇的所有问题,从干扰到量化噪声,以及恢复算法的故障。)这样基本上能使节能上一个数量级,这对消费摄影没什么意义,对感知器网络而言却有实实在在的好处。

    不过,正像我前面说的,相机自己不会预先知道两百万小波系数中需要记录哪十万个。要是相机选取了另外10万(或者30万),反而把图片中所有有用的信息都扔掉了怎么办?

    ※※


    解决的办法简单但是不太直观就是用非小波的算法来做30万个测量——尽管我前面确实讲过小波算法是观察和压缩图像的最佳手段。实际上最好的测量其实应该是(伪)随机测量——比如说随机生成30万个滤镜(mask)图像并测量真实图像与每个mask的相关程度。这样,图像与mask之间的这些测量结果(也就是“相关性”)很有可能是非常小非常随机的。但是——这是关键所在——构成图像的2百万种可能的小波函数会在这些随机的mask的测量下生成自己特有的“特征”,它们每一个都会与某一些mask成正相关,与另一些mask成负相关,但是与更多的mask不相关。可是(在极大的概率下)2百万个特征都各不相同;这就导致,其中任意十万个的线性组合仍然是各不相同的(以线性代数的观点来看,这是因为一个30万维线性子空间中任意两个10万维的子空间几乎互不相交)。因此,理论上是有可能从这30万个随机mask数据中恢复图像的(至少可以恢复图像中的10万个主要细节)。简而言之,我们是在讨论一个哈希函数的线性代数版本。

    PS: 这里的原理就是说,如果3维线性子空间中的任意两个2维子空间是线性相关的话,比如:

    ①3x+2y=8

    ②6x+4y=16

    ③4x+5y=10

    中,①②就是线性相关的,①③不是线性相关的。将200万个小波函数降维到30万个掩模基的过程就是类似去掉①②中冗余基的过程。


    然而这种方式仍然存在两个技术问题。首先是噪声问题:10万个小波系数的叠加并不能完全代表整幅图像,另190万个系数也有少许贡献。这些小小贡献有可能会干扰那10万个小波的特征,这就是所谓的“失真”问题。第二个问题是如何运用得到的30万测量数据来重建图像。

    我们先来关注后一个问题(怎样恢复图像)。如果我们知道了2百万小波中哪10万个是有用的,那就可以使用标准的线性代数方法(高斯消除法,最小二乘法等等)来重建信号。(这正是线性编码最大的优点之一——它们比非线性编码更容易求逆。大多数哈希变换实际上是不可能求逆的——这在密码学上是一大优势,在信号恢复中却不是。)可是,就像前面说的那样,我们事前并不知道哪些小波是有用的。怎么找出来呢?一个单纯的最小二乘近似法会得出牵扯到全部2百万系数的可怕结果,生成的图像也含有大量颗粒噪点。要不然也可以代之以一种强力搜索,为每一组可能的10万关键系数都做一次线性代数处理,不过这样做的耗时非常恐怖(总共要考虑大约10的17万次方个组合!),而且这种强力搜索通常是NP完备的(其中有些特例是所谓的“子集合加总”问题)。不过还好,还是有两种可行的手段来恢复数据:


    匹配追踪:找到一个其标记看上去与收集到的数据相关的小波;在数据中去除这个标记的所有印迹;不断重复直到我们能用小波标记“解释”收集到的所有数据。

    Matching pursuit: locate a wavelet whose signature seems to correlate with the data collected; remove all traces of that signature from the data; and repeat until we have totally “explained” the data collected in terms of wavelet signatures. 就是先找出一个貌似是基的小波,然后去掉该小波在图像中的分量,迭代直到找出所有10w个小波.


    基追踪(又名L1模最小化):在所有与(image)数据匹配的小波组合中,找到一个“最稀疏的”基,也就是其中所有系数的绝对值总和越小越好。(这种最小化的结果趋向于迫使绝大多数系数都消失了。)这种最小化算法可以利用单纯形法之类的凸规划算法,在合理的时间内计算出来。
    Basis pursuit (or l^1 minimisation): Out of all the possible combinations of wavelets which would fit the data collected, find the one which is “sparsest” in the sense that the total sum of the magnitudes of all the coefficients is as small as possible. (It turns out that this particular minimisation tends to force most of the coefficients to vanish.) This type of minimisation can be computed in reasonable time via convex optimisationmethods such as the simplex method.


    需要注意到的是,这类图像恢复算法还是需要相当的运算能力的(不过也还不是太变态),不过在传感器网络这样的应用中这不成问题,因为图像恢复是在接收端(这端有办法连接到强大的计算机)而不是传感器端(这端就没办法了)进行的。

    现在已经有严密的结果显示,对原始图像设定不同的压缩率或稀疏性,这两种算法完美或近似完美地重建图像的成功率都很高。匹配追踪法通常比较快,而基追踪算法在考虑到噪声时则显得比较准确。这些算法确切的适用范围问题在今天仍然是非常热门的研究领域。(说来遗憾,目前还没有出现对P不等于NP问题的应用;如果一个重建问题(在考虑到测量矩阵时)是NP完备的,那它刚好就不能用上述算法解决。)


    由于压缩感知还是一个相当新的领域(尤其是严密的数学结果刚刚出现),现在就期望这个技术应用到实用的传感器上还为时尚早。不过已经有概念验证模型出现了,其中最著名的是Rice大学研制的单像素相机

    最后必须提到的是,压缩感知技术是一种抽象的数学概念,而不是具体的操作方案,它可以应用到成像以外的许多领域。以下只是其中几个例子:

    磁共振成像(MRI)。在医学上,磁共振的工作原理是做许多次(但次数仍是有限的)测量(基本上就是对人体图像进行离散拉东变换(也叫X光变换)),再对数据进行加工来生成图像(在这里就是人体内水的密度分布图像)。由于测量次数必须很多,整个过程对患者来说太过漫长。压缩感知技术可以显著减少测量次数,加快成像(甚至有可能做到实时成像,也就是核磁共振的视频而非静态图像)。此外我们还可以以测量次数换图像质量,用与原来一样的测量次数可以得到好得多的图像分辨率。
    ps:在C牛的video中也有提到

    天文学。许多天文现象(如脉冲星)具有多种频率震荡特性,使其在频域上是高度稀疏也就是可压缩的。压缩感知技术将使我们能够在时域内测量这些现象(即记录望远镜数据)并能够精确重建原始信号,即使原始数据不完整或者干扰严重(原因可能是天气不佳,上机时间不够,或者就是因为地球自传使我们得不到全时序的数据)。

    线性编码。压缩感知技术提供了一个简单的方法,让多个传送者可以将其信号带纠错地合并传送,这样即使输出信号的一大部分丢失或毁坏,仍然可以恢复出原始信号。例如,可以用任意一种线性编码把1000比特信息编码进一个3000比特的流;那么,即使其中300位被(恶意)毁坏,原始信息也能完全无损失地完美重建。这是因为压缩感知技术可以把破坏动作本身看作一个稀疏的信号(只集中在3000比特中的300位)。

    许多这种应用都还只停留在理论阶段,可是这种算法能够影响测量和信号处理中如此之多的领域,其潜力实在是振奋人心。笔者自己最有成就感的就是能看到自己在纯数学领域的工作(例如估算傅立叶子式的行列式或单数值)最终具备造福现实世界的前景。






    /***********************CS研究内容***********************/

    研究压缩感知的内容有几块呢?
    (1)压缩感知理论,比如测量矩阵,重建性能分析,测量数据量化影响;
    (2)优化算法,本质上是重建算法优化,比如线性规划(LP)、贝叶斯优化等等;
    (3)实际的应用,压缩?后处理?分类?等等


    The main theoretical findings in this recent field have mostly centered on how many multiplexed measurements are necessary to reconstruct the original signal and the attendant nonlinear reconstruction techniques needed to demultiplex these signals. 

    最近的理论研究主要集中在 ①需要多少多维测度才能重建原始信号 ②分解信号所需的非线性重建技术;还有能够直接进行多维信号选择的感知硬件(sensing hardware)。






    /***********************CS的压缩/解压效果***********************/


    由于刚刚看这一方面的资料,未免经验不足,就借鉴了其他人(Ganer)在该领域的探究结果,他的博客中写到:


    很多mpressive sensing的实际用于信号采集效果其实并不是很好。
    就从我的实验而言,对于图像压缩甚至会差的很,远远低于传统的压缩方式。
    那就不难有学者发出感叹,实际上compressive sensing 就是depressive sensing了。

    我的理解是什么呢?有2点牢牢记住的
    (1)compressive sensing实际上是对信号采集的颠覆性的理论,打破了乃奎斯特采样(也称香农采样)。
            实际上,大部分信号是稀疏的,没有必要用乃奎斯特采样,进行时间离散化。
            注意两点:(1)乃奎斯特采样对信号没有稀疏性的假设;
                             (2)CS对信号有稀疏性假设,既K稀疏;
           那么,信号采集过程也就是说从A2D,变成了A2I。
          但是在实际应用角度,2者结合会有很大的收益。(个人观点)
    (2)compressive sensing本事是最大后验(MAP)解码,这点比传统的方式要更为”先进“,也更为”危险“。


    关于Compressive Sensing更多的学习资料将继续更新,敬请关注本博客和新浪微博Sophia_qing


    References:

    1. Compressed sensing and single-pixel cameras - Terrytao

    2. 斯坦福大学Emmanuel Candes教授:压缩感知 video2

    3. An Introduction to Compressed Sensing (斯坦福课程,可根据syllabus分块啃食)

    4.Near Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?-Emmanuel CandesTerence Tao

    5. http://blog.163.com/gan_research/blog/static/16534814820107912256225/

    6. C牛在Stanford的课程

    7. 中国压缩传感资源(China Compressive Sensing Resources)

    8.Using Math to Turn Lo-Res Datasets Into Hi-Res Samples  - Jordan Ellenberg 

    (ellenber@math.wisc.edu), an associate professor of mathematics at the University of Wisconsin, wrote about theNetflix Prize in issue 16.03.





    展开全文
  • 什么是压缩感知压缩感知(compressive sensing)有两部分组成 感知(sensing):所谓感知就是站在计算机角度上,我们作为计算机感知一种信号(图片),也就是计算机去理解这种信号的一种拟人化的描述,比如100100的...
  • 压缩感知(Compressed sensing),也被称为压缩采样(Compressive sampling),稀疏采样(Sparse sampling),压缩传感。它作为一个新的采样理论,它通过开发信号的稀疏特性,在远小于Nyquist 采样率的条件下,用随机...
  • 压缩感知

    万次阅读 多人点赞 2018-09-16 10:23:29
    一、什么是压缩感知(CS)? compressed sensing又称compressed sampling,CS是一个针对信号采样的技术,它通过一些手段,实现了“压缩的采样”,准确说是在采样过程中完成了数据压缩的过程。 因此我们首先要从...
  • 压缩感知理论

    万次阅读 多人点赞 2018-09-18 20:07:17
     简单地说,压缩感知理论指出:只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中...
  • 压缩感知(compressed sensing)的通俗解释

    万次阅读 多人点赞 2019-04-27 16:09:29
    作者:咚懂咚懂咚 来源: 知乎 ... ----------------------------...在我看来,压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果之一,并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的...
  • 压缩感知进阶——有关稀疏矩阵

    万次阅读 多人点赞 2013-04-09 09:08:39
    上一篇《初识压缩感知Compressive Sensing》中我们已经讲过了压缩感知的作用和基本想法,涉及的领域,本文通过学习陶哲轩对compressive sensing(CS)的课程,对压缩感知做进一步理解,针对其原理做出讲解。...
  • 浅谈压缩感知(十三):压缩感知与传统压缩 导言: 压缩感知,顾名思义,就是感知压缩,这里包含两层意思,1、感知,即采集或采样,在传统的信号采集中,为了不失真,必须满足Nyquist采样定理,在上一篇博文已经...
  • 压缩感知的实现(含matlab代码)

    万次阅读 多人点赞 2019-11-06 21:14:42
    压缩感知的图像重建(matlab) https://blog.csdn.net/Di_Wong/article/details/88994551 目录 原理简介 算法实现 测试结果 --------------------------------------------------------------------------------...
  • 经典的介绍压缩感知原理的入门书籍! 1.《Compressed Sensing:Theory and Applications》 2.《A Mathematical Introduction to Compressive Sensing》 3.《Adapted Compressed Sensing for Effective Hardware ...
  • 压缩感知文献综述

    2020-07-30 23:33:20
    随着信息技术的发展,人们对信息的巨量需求以及硬件的发展缓慢造成了信号...本文综述了压缩感知的理论框架及关键的技术问题,并着重介绍了压缩感知稀疏重构中的主流贪婪算法,通过算法实验分析了各种算法的重构性能。
  • OMP在稀疏分解与压缩感知中的异同 压缩感知通过OMP重构信号的唯一性 一、OMP在稀疏分解与压缩感知中的异同 1、稀疏分解要解决的问题是在冗余字典(超完备字典)A中选出k列,用这k列的线性组合近似表达待稀疏分解...
  • 分布式压缩感知简介

    千次阅读 2019-03-12 22:20:22
    分布式压缩感知是针对多个传感器对多个信号进行压缩感知的情景,令每个传感器独立对信号进行测量,然后基于测量结果,综合利用信号内部以及信号之间的关联结构实现稀疏信号的恢复。 分布式压缩感知有一个大前提:...
  • 压缩感知英文综述

    2020-07-30 23:30:30
    国际上出现的压缩感知理论( Compre ss e d S e ns i ng, CS ) 为缓解这些压力提供了解决方法. 本文综述了 CS 理论框架及关键 技术问题, 并着重介绍了信号稀疏变换、 观测矩阵设计和重构算法三个方面的最新进展, 评述...
  • 压缩感知理论简介PDF

    2020-07-30 23:32:50
    压缩感知理论简介压缩感知理论简介压缩感知理论简介压缩感知理论简介
  • 压缩感知 (Compressed Sensing) 是一种利用信号普遍存在低维结构的先验知识,只需极少的采样点,就能以极大概率恢复出原始信号的采样方法。 Orthogonal Matching Pursuit (OMP) 算法是一种贪婪算法,可用于压缩感知...
1 2 3 4 5 ... 20
收藏数 31,639
精华内容 12,655
关键字:

压缩感知