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

    声明:

    本文为转载,

    原作者Rachel-Zhang

    原博客地址:http://blog.csdn.net/abcjennifer

    原文地址,http://blog.csdn.net/abcjennifer/article/details/7721834/


    压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。最近粗浅地看了这方面一些研究,对于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.

    展开全文
  • 压缩感知,图像处理,运行的MATALB代码,有参考意义!
  • 压缩感知图像处理

    2020-07-12 23:30:22
    压缩感知图像处理 DCT稀疏 JND测量矩阵 OMP重建算法
  • 文件中包含多种压缩感知图像重构方法,CoSaMp,omp,sp等,能实现图像重构
  • 最近看到GitHub上有一个利用压缩感知重建图像的matlab代码,代码里方法很全,在这里做一下分享 关于压缩感知的原理以及一维实现参考我上一篇博文 https://blog.csdn.net/Di_Wong/article/details/81191211 因为...

    最近看到GitHub上有一个利用压缩感知重建图像的matlab代码,代码里方法很全,在这里做一下分享

    关于压缩感知的原理以及一维实现参考我上一篇博文

    https://blog.csdn.net/Di_Wong/article/details/81191211


    因为本人已经没有在压缩感知方向做更深入的研究,所以只分享相关的资料,感兴趣的可以深入研究

    利用压缩感知重建图像的GitHub地址:

    https://github.com/thomaskuestner/CS_MoCo_LAB

     

    下载后解压缩,得到下图中的文件,acquisition和docker不用管,进入reconstruction\ matlab文件夹。

    acquisition和docker不用管,进入reconstruction\ matlab文件夹。可以看到有两个文件夹CS_LAB_matlab和CS_LAB_GUI,其中CS_LAB_matlab里是各类压缩感知重建方法的源码,有兴趣的可以研究下。

    进入CS_LAB_GUI文件夹,运行demo,得到下图,这是对MRI图像的重建结果。

    此外,作者还开发了图像重建的GUI,运行CS_LAB_GUI.m文件,可以通过GUI处理自己的图像

     

     

    展开全文
  • 压缩感知CS最全matlab程序,二维三维图像处理,恢复算法,CSDN中最全的压缩感知程序包,12M的程序,也包含陶哲轩的关于压缩感知的PPT及文章
  • 利用压缩感知来实现图像处理,从而进行信息隐藏。这在大数据的处理中有很好的应用。
  • 利用MATLAB生成phantom,利用医学图像在某些变换域内的稀疏性,编程实现 CT图像的重建。并计算RMSE,与原图像比对。改变bm、bn数值可以改变分块大小,改变p值可以改变采样率。运行时间随着这些参数的改变而改变,原...
  • lena,cameraman,baboon,barbara,boat,fruits,house,peppers,phantom,plane,sar,stadium...
  • 压缩感知技术应用的程序,包括一些实例,既包括信号处理,也包括图像处理
  • 图像压缩Vs.压缩感知

    2019-04-14 12:22:56
    SparseCoding,压缩感知。对样本集合进行超完备重建,使用非监督学习方法,寻找样本特征集的超完备基,而对任一样本来说,使用此组基的表示稀疏是稀疏的,即只有少量的基向量非0。 小品文 压缩感知科普文两则:...

         SparseCoding,压缩感知。对样本集合进行超完备重建,使用非监督学习方法,寻找样本特征集的超完备基,而对任一样本来说,使用此组基的表示稀疏是稀疏的,即只有少量的基向量非0。

    小品文

    压缩感知科普文两则:原文链接:http://www.cvchina.info/2010/06/08/compressed-sensing-2/

    compressed sensing

            这几天由于happyharry的辛勤劳动,大伙纷纷表示对稀疏表达,压缩感知很感兴趣啊。我是搞不太懂这个前沿啊,只好转两篇科学松鼠会的科普文,都是译文,说不定大伙都看过了原文。

    第一篇是陶哲轩写的。

    这是数学家陶哲轩在他自己的blog上写的一篇科普文章,讨论的是近年来在应用数学领域里最热门的话题之一:压缩感知compressed sensing)。所谓压缩感知,最核心的概念在于试图从原理上降低对一个信号进行测量的成本。比如说,一个信号包含一千个数据,那么按照传统的信号处理理论,至少需要做一千次测量才能完整的复原这个信号。这就相当于是说,需要有一千个方程才能精确地解出一千个未知数来。但是压缩感知的想法是假定信号具有某种特点(比如文中所描述得在小波域上系数稀疏的特点),那么就可以只做三百次测量就完整地复原这个信号(这就相当于只通过三百个方程解出一千个未知数)。可想而知,这件事情包含了许多重要的数学理论和广泛的应用前景,因此在最近三四年里吸引了大量注意力,得到了非常蓬勃的发展。陶哲轩本身是这个领域的奠基人之一(可以参考《陶哲轩:长大的神童》一文),因此这篇文章的权威性毋庸讳言。另外,这也是比较少见的由一流数学家直接撰写的关于自己前沿工作的普及性文章。需要说明的是,这篇文章是虽然是写给非数学专业的读者,但是也并不好懂,也许具有一些理工科背景会更容易理解一些。

    【作者 Terence Tao;译者 山寨盲流,他的更多译作在;校对 木遥】

    最近有不少人问我究竟”压缩感知”是什么意思(特别是随着最近这个概念名声大噪),所谓“单像素相机”又是怎样工作的(又怎么能在某些场合比传统相机有优势呢)。这个课题已经有了大量文献,不过对于这么一个相对比较新的领域,还没有一篇优秀的非技术性介绍。所以笔者在此小做尝试,希望能够对非数学专业的读者有所帮助。

    具体而言我将主要讨论摄像应用,尽管压缩传感作为测量技术应用于比成像广泛得多的领域(例如天文学,核磁共振,统计选取,等等),我将在帖子结尾简单谈谈这些领域。

    相机的用途,自然是记录图像。为了简化论述,我们把图像假设成一个长方形阵列,比如说一个1024×2048像素的阵列(这样就总共是二百万像素)。为了省略彩色的问题(这个比较次要),我们就假设只需要黑白图像,那么每个像素就可以用一个整型的灰度值来计量其亮度(例如用八位整型数表示0到255,16位表示0到65535)。

    接下来,按照最最简化的说法,传统相机会测量每一个像素的亮度(在上述例子中就是二百万个测量值),结果得到的图片文件就比较大(用8位灰度值就是2MB,16位灰度就是4MB)。数学上就认为这个文件是用超高维矢量值描绘的(在本例中就是约二百万维)。

    在我开始讲“压缩感知”这个新故事之前,必须先快速回顾一下“老式压缩”的旧故事。(已经了解图像压缩算法的读者可以跳过这几段。)

    上述的图片会占掉相机的很多存储空间(上传到计算机里还占磁盘空间),在各种介质之间传输的时候也要浪费时间。于是,相机带有显著压缩图像的功能就顺理成章了(通常能从2MB那么大压缩到十分之一——200KB的一小坨)。关键是尽管“所有图片”所构成的空间要占用2MB的“自由度”或者说“熵”,由“有意义的图片”所构成的空间其实要小得多,尤其是如果人们愿意降低一点图像质量的话。(实际上,如果一个人真的利用所有的自由度随机生成一幅图片,他不大可能得到什么有意义的图像,而是得到相当于电视荧屏上的静电雪花那样的随机噪声之类。)

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

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

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

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

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

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

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

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

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

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

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

    • 基追踪(又名L1模最小化):在所有与录得数据匹配的小波组合中,找到一个“最稀疏的”,也就是其中所有系数的绝对值总和越小越好。(这种最小化的结果趋向于迫使绝大多数系数都消失了。)这种最小化算法可以利用单纯形法之类的凸规划算法,在合理的时间内计算出来。

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

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

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

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

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

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

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

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

    第二篇

    压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。关于这个题目,松鼠会已经翻译了两篇文章,一篇来自于压缩感知技术最初的研究者陶哲轩(链接),一篇来自威斯康辛大学的数学家艾伦伯格(本文正文)。这两篇文章都是普及性的,但是由于作者是专业的研究人员,所以事实上行文仍然偏于晦涩。因此我不揣冒昧,在这里附上一个画蛇添足的导读,以帮助更多的读者更好了解这个新颖的研究领域在理论和实践上的意义。

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

    稍加思量就会发现,这种压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下,采集并处理数据的设备,往往是廉价、省电、计算能力较低的便携设备,例如傻瓜相机、或者录音笔、或者遥控监视器等等。而负责处理(即解压缩)信息的过程却反而往往在大型计算机上进行,它有更高的计算能力,也常常没有便携和省电的要求。也就是说,我们是在用廉价节能的设备来处理复杂的计算任务,而用大型高效的设备处理相对简单的计算任务。这一矛盾在某些情况下甚至会更为尖锐,例如在野外作业或者军事作业的场合,采集数据的设备往往曝露在自然环境之中,随时可能失去能源供给或者甚至部分丧失性能,在这种情况下,传统的数据采集-压缩-传输-解压缩的模式就基本上失效了。

    压缩感知的概念就是为了解决这样的矛盾而产生的。既然采集数据之后反正要压缩掉其中的冗余度,而这个压缩过程又相对来说比较困难,那么我们为什么不直接「采集」压缩后的数据?这样采集的任务要轻得多,而且还省去了压缩的麻烦。这就是所谓的「压缩感知」,也就是说,直接感知压缩了的信息。

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

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

    这一思路可以扩展到很多领域。在大量的实际问题中,我们倾向于尽量少地采集数据,或者由于客观条件所限不得不采集不完整的数据。如果这些数据和我们所希望重建的信息之间有某种全局性的变换关系,并且我们预先知道那些信息满足某种稀疏性条件,就总可以试着用类似的方式从比较少的数据中还原出比较多的信号来。到今天为止,这样的研究已经拓展地非常广泛了。
    但是同样需要说明的是,这样的做法在不同的应用领域里并不总能满足上面所描述的两个条件。有的时候,第一个条件(也就是说测量到的数据包含信号的全局信息)无法得到满足,例如最传统的摄影问题,每个感光元件所感知到的都只是一小块图像而不是什么全局信息,这是由照相机的物理性质决定的。为了解决这个问题,美国 Rice 大学的一部分科学家正在试图开发一种新的摄影装置(被称为「单像素照相机」),争取用尽量少的感光元件实现尽量高分辨率的摄影。有的时候,第二个条件(也就是说有数学方法保证能够从不完整的数据中还原出信号)无法得到满足。这种时候,实践就走在了理论前面。人们已经可以在算法上事先很多数据重建的过程,但是相应的理论分析却成为了留在数学家面前的课题。

    但是无论如何,压缩感知所代表的基本思路:从尽量少的数据中提取尽量多的信息,毫无疑问是一种有着极大理论和应用前景的想法。它是传统信息论的一个延伸,但是又超越了传统的压缩理论,成为了一门崭新的子分支。它从诞生之日起到现在不过五年时间,其影响却已经席卷了大半个应用科学。

     

    展开全文
  • 摘要 获取项目源文件,联系Q:1415736481,可指导...近年来出现的压缩感知理论(Compressed Sensing,CS)则不受制于奈奎斯特采样定律,它是采用非自适应线性投影来保持信号的原始结构,以直接采集压缩后的数据的方式...

    摘要

    获取项目源文件,联系Q:1415736481,可指导毕设,课设

    数据压缩技术是提高无线数据传输速度的有效措施之一。传统的数据压缩技术是基于奈奎斯特采样定律进行采样,并根据数据本身的特性降低其冗余度,从而达到压缩的目的。近年来出现的压缩感知理论(Compressed Sensing,CS)则不受制于奈奎斯特采样定律,它是采用非自适应线性投影来保持信号的原始结构,以直接采集压缩后的数据的方式,从尽量少的数据中提取尽量多的信息。

    本文阐述了压缩感知方法的基本原理,分析了CS理论框架及关键技术问题,介绍了压缩感知技术应用于无线传感的优势,并着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展,对研究中现存的难点问题进行了探讨。并运用matlab软件,在离散傅里叶变换(DFT)和离散余弦变换(DCT)分块CS的基础上,采用正交匹配追踪算法(OMP)实现了对一维信号和二维图像的高概率重构。将重构结果与原始信号对比,结果表明,只要采样数M(远小于奈奎斯特定理所需要的采样率)能够包含图像所需要的有用信息时,CS算法就能精确的完成对图像的重构,并且重构效果也比较好。

     

    关键词:压缩感知 无线传感 正交匹配 稀疏表示 观测矩阵

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    Abstract

    The data compression technology is one of the efficient measures for increasing the speed of wireless data communication. Traditional data compression technology is based on Nyquist sampling theorem, reaching the goal of compression by decreasing redundancy of information. In recent years, Compressed Sensing(CS) comes out as a new sampling theory, it does not have to obey Nyquist sampling theorem, and it can keep the original structure of signals by attaining the non-adaptive linear projections. So, CS can gather the compressed data directly and get more information from less data.

    This paper reviews the theoretical framework and the key technical problems of compressed sensing and introduces the latest developments of signal sparse representation, design of measurement matrix and reconstruction algorithm. Then this paper also discusses the existing difficult problems. Based on the discrete fourier transform (DFT) and discrete cosine transform (DCT), we use MATLAB software, realizes the accurate reconstruction of one-dimension signal two-dimension image by applying the OMP algorithm. Then make a comparison to the reconstruction of signal to original signals and make a conclusion. If only the sampling measurements M (far less than Nyquist sampling measurements ) contain the useful information of signals, CS algorithm can complete the accurate reconstruction, and the effect of reconstruction signal is good too.

     

    Key words:  compressed sensing   wireless sensor networks   orthogonal matching pursuit   sparse presentation   measurement matri

     

    第1章 绪论

    在当今的信息社会,电脑、手机、传感器、驱动器等都要连接到因特网,这样的无线通信系统中,将会产生并且传播大量数据信息,从而对信号的采样、存储、传输和恢复造成巨大压力,增加了通信设备的成本。对人们来说,如何有效的处理这些数据,成为一个新的挑战。近几年来,在信号处理领域出现的压缩感知理论(CS)打破了传统采样过程中信号采样速率必须达到信号带宽两倍以上才能精确重构原始信号的奈奎斯特采样定理,使得信息存储、处理和传输的成本大大降低。

    1.1 研究背景和意义

    随着人们对信息需求量的增加,网络通信、多媒体技术、存储技术的发展越来越快,网络的规模也越来越大,寻找高效的信息技术来降低数据量成为无线传输系统中急需处理的问题之一。这是因为数字化的各类信息的数据量十分庞大,若不对其进行有效的压缩就难以得到实际的应用,因此,数据压缩技术成为人们研究的一项重要技术。无线传感器网络是近来研究的热点方向之一。它是由分布在监测区域内的大量微型传感器节点通过无线电通信而形成的一个自组织网络系统。这个系统的目的是协作的感知、采集和处理网络覆盖区域里被监测对象的信息,并将结果发送给用户。在一个传感器网络中,常常包含大量传感器节点,每个传感器都会采集大量的数据。这些数据将会被传输到一个控制中心,也会在各个节点之间传输,在这种分布式传感网络中,数据传输功耗和带宽需求非常大,所以,如何对这样的分布式信号进行压缩,从而减小通信开销已经成为非常紧迫的需求。

    压缩感知理论与传统奈奎斯特采样定理不同,它指出,只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号,可以证明这样的投影包含了重构信号的足够信息。 在该理论框架下,采样速率不决定于信号的带宽,而决定于信息在信号中的结构和内容。 事实上,压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论, 最近由Candès,Romberg ,Tao和Donoho等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。从信号分析角度来讲,傅立叶变换是信号和数字图像处理的理论基础,小波分析将信号和数字图像处理带入到一个崭新的领域。 多尺度几何分析是继小波分析后的新一代信号分析工具,它具有多分辨、局部化和多方向性等优良特性,更适合于处理图像等高维信号。 这些研究工作都为压缩感知理论奠定了基础。显然,在压缩感知理论中,图像/信号的采样和压缩同时以低速率进行,使传感器的采样和计算成本大大降低,而信号的恢复过程是一个优化计算的过程。 因此,该理论指出了将模拟信号直接采样压缩为数字形式的有效途径,具有直接信息采样特性。 由于从理论上讲任何信号都具有可压缩性,只能找到其相应的稀疏表示空间,就可以有效地进行压缩采样,这一理论必将给信号采样方法带来一次新的革命。

    1.2  数据压缩技术

    数据压缩技术就是对原始数据进行数据编码或者压缩编码,从而用最少的数码来表示信源发出的信号。数据压缩的对象很广泛,可以是通信时间、传输带宽、存储空间甚至发射能量。数据压缩的作用是能够快速地传输各种信号;在已有的一些通信干线并行开通更多的多媒体业务;紧缩数据存储容量;降低发信机功率等等。

    1.2.1 传统数据压缩技术

    前较成熟的数据压缩技术有许多种,按照压缩后对信息的失真程度,主要分为无损压缩和有损压缩。

    无损压缩是利用数据中的统计冗余进行压缩。数据中间存在的一些多余成分,称之为冗余度。例如,在某一份计算机文件中,一些符号会反复出现、一些符号比其它的符号出现得更频繁、一些符号总是出现在各数据块中的可预见的位置上,以上讲述的这些冗余部分便可在数据编码中除去或者减少。这种无损压缩机制可以完全恢复原始数据而不引起任何失真,但是压缩率却受到数据统计冗余度的理论限制,一般为2:1到5:1。这类方法可以广泛用于文本数据、程序以及特殊应用场景的图像数据(如医学图像)的压缩。它的主要压缩机制包括Huffman编码、算术编码、游程编码和字典编码等系列。

    有损压缩是利用了人类对图像或者声音中的某些频率成分不敏感的特殊性质,允许压缩过程中损失一定的信息;尽管不能完全恢复出原始数据,但是所缺失的数据部分对于我们理解原始图像的影响很小,却使得压缩比大了许多。有损压缩广泛应用于语音,图像和视频数据的压缩。它一般有两种基本的压缩机制,一种是有损变换编解码(如傅立叶变换、离散余弦变换、小波变换),即首先对图像或者声音进行采样、切成小块、变换到一个新的空间、量化,接着对量化值进行熵编码;另外一种是预测编解码(如脉冲编码调制、差分脉冲编码调制、自适应差分脉冲编码调制等),即利用先前的数据和随后解码的数据来预测当前的声音采样或者图像帧,并对预测数据与实际数据之间的误差以及其它一些重现预测的信息进行量化与编码。

    综合无损压缩和有损压缩的优点,还出现了第三类压缩技术:混合压缩。它主要是求取在压缩效率、压缩比以及保真度之间的最佳平衡,如静止图像压缩标准JPEG和活动图像压缩标准MPEG就是采用混合编码的压缩方法。

    1.2.2 压缩感知理论(Compressed/Compressive Sensing/Sampling, CS)

    在传统理论的指导下,信号主要的一些压缩方法都要基于奈奎斯特采样定律进行采样,即信息采样速率至少为信号带宽的两倍。信号的编解码过程如图1.1所示:编码端首先获得X 的N点采样值,经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码,最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。实际上,采样得到的大部分数据都是不重要的,即K值很小,但由于奈奎斯特采样定理的限制,采样点数N可能会非常大,采样后的压缩是造成资源浪费的根本所在。

     

     

     

     
     

    图1.1 传统编解码理论框图

     

     

    CS 理论的信号编解码框架和传统的框架大不一样,如图1.2 所示。CS 理论对信号的采样、压缩编码发生在同一个步骤,利用信号的稀疏性,以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身,而是从高维到低维的投影值,从数学角度看,每个测量值是传统理论下的每个样本信号的组合函数,即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程,而是在盲源分离中的求逆思想下,利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构,解码所需测量值的数目远小于传统理论下的样本数。

    压缩感知的核心思想是压缩和采样合并进行,并且测量值远小于传统采样方法的数据量,突破了香农采样定理的瓶颈,使高分辨率的信号采集成为可能。

     压缩感知理论主要包括信号的稀疏表示、随机测量和重构算法等三个方面。稀疏表示是应用压缩感知的先验条件,随机测量是压缩感知的关键过程,重构算法是获取最终结果的必要手段。

     

     

     
     

    图1.2 CS理论下数据的编解码过程

     

     

     

    压缩感知关键要素包括稀疏表示、测量矩阵和重构算法。

    信号在某种表示方式下的稀疏性,是压缩感知应用的理论基础,经典的稀疏化的方法有离散余弦变换(DCT)、傅里叶变换(FFT)、离散小波变换(DWT)等。

    最近几年,对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。 这是一种全新的信号表示理论:用超完备的冗余函数库取代基函数,称之为冗余字典,字典中的元素被称为原子。目前信号在冗余字典下的稀疏表示的研究集中在两个方面:一是如何构造一个适合某一类信号的冗余字典,二是如何设计快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分为匹配追踪(Matching Pursuit)和基追踪(Basis Pursuit)两大类。

    压缩感知理论中,通过变换得到信号的稀疏系数后,需要设计压缩采样系统的观测部分,它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值,并保证从中能重构出长度为N的信号X或者稀疏基基下等价的稀疏系数向量。

    CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。2007年Candes等研究者建立了著名的约束等距性(RIP)理论,即要想使信号完全重构,必须保证观测矩阵不会把两个不同的 K项稀疏信号映射到同一个采样集合中,这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。

    Donoho给出压缩感知概念的同时定性和定量的给出测量矩阵要满足三个特征:(1)由测量矩阵的列向量组成的子矩阵的最小奇异值必须大于一定的常数;(2)测量矩阵的列向量体现某种类似噪声的独立随机性;(3)满足稀疏度的解是满足1范数最小的向量。

    目前常用的测量矩阵包括:

    (1)随机高斯矩阵。矩阵每个元素独立地服从均值为0,方差为的高斯分布。

    (2)随机贝努利矩阵。矩阵的每个元素独立地服从对称的贝努利分布,等概率为或-。         

    (3)部分正交矩阵。先生成N×N的正交矩阵U(如傅里叶矩阵),然后在矩阵U中随机地选取M行向量,对M×N矩阵的列向量进行单位化得到测量矩阵。

    (4)部分哈达玛矩阵。生成大小为N×N的哈达玛矩阵,然后在生成矩阵中随机地选取M行向量,构成一个M×N的矩阵。

    (5)托普利兹和循环矩阵。首先生成一个向量u,由向量u生成相应的轮换矩阵或托普利兹矩阵U,然后在矩阵U中随机地选取其中的M行而构造的矩阵Φ。

    (6)稀疏随机矩阵。首先生成一个零元素的矩阵Φ,在矩阵Φ的每一个列向量中,随机地选取d个位置,然后在所选取的位置的值赋为1。

        压缩感知的重构算法主要分为两大类,一是贪婪算法,它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近,此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。二是凸优化算法,它是把0范数放宽到1范数通过线性规划求解的,此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。凸优化算法算法比贪婪算法所求的解更加精确,但是需要更高的计算复杂度。

        此外,迭代阈值法也得到了广泛的应用,此类算法也较易实现,计算量适中,在贪婪算法和凸优化算法中都有应用。但是,迭代阈值法对于迭代初值和阈值的选取均较敏感,且不能保证求出的解是稀疏的。

    就目前主流的两种重建算法而言,基于1范数最小的重建算法计算量巨大,对于大规模信号无法应用;贪婪算法虽然重建速度快,但是在信号重建质量上还有待提高。

    目前,上述理论已经应用到各个领域,如传感网、频谱感知、雷达、医学信号处理、信道预测等方面,取得了很好的效果。以上是关于压缩感知理论与分布式压缩感知理论的简单介绍,详细阐述将在第二章和第三章进行展开。

    1.3 无线传感器网络                      

     无线传感器网络是计算、通信和传感器这三项技术相结合的产物,一开始在军事应用中收集数据,对战场情况和威胁及其重要程度进行适时的完整评价,后发展到民事运用,如监控大型设备,灾区临时通信,卫生保健等等。

    1.3.1 无线传感器网络概述

    无线传感器网络一般由若干传感器节点组成,节点是组成无线传感器网络的基本单位,它负责完成采集信息、融合并传输数据的功能。每一个传感器节点由数据采集模块(传感器、A/D转换器)、数据处理和控制模块(微处理器、存储器)、通信模块(无线收发器)和供电模块(电池、DC/DC能量转换器等)组成,如图1-3所示。

     

     

     
     

     图1.3 无线传感器网络节点结构图

     

     

     

     

    其中,数据采集模块负责感知所需要的信息,数据处理和控制模块负责对感知所得的信息和接收信息进行处理,通信模块负责与其他节点进行通信,即发送或者接收信息,供电模块则负责提供所需要的能量。

    根据节点在传感网网络体系中所起作用的不同,节点在网络中可以充当数据采集者、数据处理中转站或簇头节点几种角色:

    (1)数据采集者,这类节点的数据采集模块专门采集周围的环境数据(如温度、压力),然后通过通信路由协议直接或间接地将采集到的数据传输给远方基站(Base Station,BS)或汇聚节点(Sink);

    (2)数据处理中转站,这类节点不仅要完成采集的任务,还要接收邻居节点的数据,一起转发给距离基站更近的邻居节点或者直接转发到基站或汇聚节点;

    (3)簇头节点,这类节点负责收集节点采集的数据,经数据融合后,发送到基站或汇聚节点。

    传感器节点都分散在特定的感知区域,相互合作、实时监测、感知和采集网络周边环境或监测对象的温度、声波等各种信息。这些信息一经采集,就将通过嵌入式系统进行处理,最终通过随机自组织无线通信网络以多跳中继方式将所感知信息传送到用户终端,使人们无论在何时、何地、何种情况下都能获取大量详实可靠的信息,实现人、物和事件之间的无缝连接,从而真正实现“无处不在的计算”理念。

    与传统的网络不同的是,传统网络以传输数据为目的,而无线传感器网络则是以数据为中心;与传统的Ad Hoc网络相比,无线传感器网络具有以下几点特征:

    (1)网络节点密度高,传感节点数量多

    (2)传感器节点由电池供电

    (3)网络拓扑变化频繁

    (4)网络具有容错能力

    1.3.2 无线传感器网络数据压缩的必要性

    因为在无线传感器网络中,每个传感节点体积很小,而且分布非常密集,若是对所有采集的数据直接进行传输,则所需传输的数据量将是非常惊人的,会导致网络拥塞,也会导致网络寿命缩短;又由于传感器节点由电池供电, 所以节点能量有限,而且无线传感器网络所布置的地方一般为人们不便于到达的地方,因此传感器节点中的的电池很难更换。为了节约能量,延长传感器网络的寿命,需要采用能效高的网络通信协议和数据局部处理策略(如数据融合技术、数据压缩技术)。

    在这里,我们将说明利用压缩技术来减少传输的数据量的必要性和可行性。相对于数据采集、数据压缩这两项功能,数据传输所需要的能量是最多的,所以,如果要节约传感器节点的电池能量,必定要减少传输的数据量,因此在无线传感器网络中运用数据压缩技术来减少数据量一直是一个值得深入研究的问题。无线传感器网络中的感知数据能够进行压缩是因为它具备数据压缩的前提条件:首先,传感器节点密度很大,节点之间感知的范围相互重叠,这种高密度的节点分布一方面使得感知数据可靠性增强,另一方面也引起了数据冗余,使得相邻节点之间所采集的数据具有高度相关性,称为空间相关性;其次,由于传感节点感知的物理数据大多数随着时间变化很缓慢,所以同一个传感器节点所感知的数据之间也有相关性,称为时间相关性。利用这两种相关性,可以对感知数据采取相应的数据压缩技术。

    图1-4中监测区域中有大量的无线传感节点,传感节点可以感知各种物理环境,包括声音、温度、压力、地震等。人们将传感器节点采集的大量数据采用某种压缩技术压缩,压缩后的少量数据传送到sink节点(或者是融合中心),再由sink节点按照对应的恢复算法恢复出采集的数据。这样,通过传输少量数据就可以得到整个监测区域内的详细情况。

     

     

     
     

     图1.4 无线传感网通信体系结构

     

     

    1.4 本文主要工作和内容安排

    本文在介绍压缩感知理论/分布式压缩感知理论的基础上,将它们应用到无线传感数据压缩领域,用于压缩传感节点采集的信号,降低传输能耗,节约电池能量。

    本文内容安排如下:

    第一章 简单介绍了课题的研究背景,包括现有的数据压缩技术和有关无线传感网络的基本知识。

    第二章 详细阐述了压缩感知理论,深入介绍了压缩感知理论的核心思想— 可压缩信号(信号稀疏化)、测量矩阵和重构算法,总结了压缩感知理论的优势及不足。

    第三章 进一步介绍由压缩感知理论发展而来的分布式压缩感知理论,分别描述了三种联合稀疏模型及其应用范围,最后,将其与压缩感知理论作了仿真性能比较。

    第四章 将传感网中数据传输与压缩感知理论结合,分别利用压缩感知和分布式压缩感知框架下的信号压缩、重构方法对实际的感知数据进行处理,给出了实际的应用效果,并重点研究了量化对于算法的影响。

    第五章 对全文进行总结并展望下一步的研究工作。

     

     

     

    第2章 压缩感知理论

    传统通信系统中的采样遵循的是奈奎斯特抽样定理,该定理指出,为防止在获得信号时损失信息,抽样速率必须大于信号带宽的两倍。在许多应用中,包括数字图像和视频摄像中,奈奎斯特抽样速率太高,不利于数据存储和传输;在其他应用,包括图像系统(医疗浏览和雷达)、高速模数转换中,增加抽样速率代价也很昂贵。压缩感知则是保存原始信号结构的线性投影,然后再从这些投影中将信号重构出来,其速率远远低于奈奎斯特抽样率。CS理论系统与传统通信系统的类似关系如图2-1所示:

     

     

     

     图2.1 CS理论系统与传统通信系统的类似关系

     

     

    CS测量

     

    CS恢复

     

     
       

     

     

     

     

     

    由图2-1可知,在CS系统中,信源和信道编码被CS测量(即一个矩阵与信号矢量相乘的形式)代替;信道和信源解码则用CS恢复(即依赖于优化准则的恢复算法)替代。

    压缩感知理论主要由三部分构成:稀疏信号、观测矩阵和重构算法。下面将从这三个方面详细讲述压缩感知的关键技术。

    2.1压缩感知的前提条件—稀疏性和不相干性

    CS隐含的两个基本前提:稀疏性和不相关性。前者属于信号的性质,后者和感知(观测)形式有关。

    稀疏性:稀疏性表达了这样一个思想,一个连续时间信号的“信息速率”可能比由带宽所决定的香农采样率要低很多,或者,一个离散时间信号所依赖的自由度数目远远低于它的长度。更准确地说,CS利用了这样一个事实,即许多自然信号在某个合适的基Ψ下具有简洁的表达。

    不相关性:不相关性说明用于采样信号的波在基Ψ下有很稠密的表达。不相关性表达了这样的思想,正如时间域的Dirac或者冲击信号可以在频域展开那样,在基Ψ下具有稀疏表示的信号一定可以在获得它们的某个域中展开。

     

     

    1 稀疏性

    众所周知,任意长度为N 的离散信号X 都可以表示为一系列基函数的叠加,

    即可以在任何正交基下用下式表示:

    (式2.1)

     

    其中由一组基向量构成的正交基,例如,sinusoids,尖峰spikes、B-splines,wavelets。为展开系数。展开系数大,说明信号和基足够相似。如果信号在基下的展开系数在很小的集合上有值,我们就说该信号在域是稀疏的,如果有值序列集中在一个小范围内,那么我们就说该信号是可以压缩的。本章我们将集中研究具有稀疏表示的信号,其中XK个基向量的线性组合,K<<N。也就是说,中仅有K个非零,另外N -K个都是零。

    许多自然信号在一些基下有简洁的表达。图3.3(a)是一幅具有NN =512×512)个像素点的coins图像向量,我们在9/7小波基下展开该向量,如(式3.4),其中是为列向量构成的的矩阵,是正交基。图3.3(b)是coins图像的9/7小波系数在一维下的表示。图2.3(c)展示了这样一个事实:将图像在9/7小波变换域丢掉93.75%的小系数后得到的逼近图像尽管PSNR只有29.09dB,但肉眼很难察觉到失真。由此可见,尽管原图中几乎所有的像素都是非零值,它在9/7小波域中却是稀疏的:大部分小波系数都很小,少数的大系数(1/16)就可以捕获信号的大部分信息。

    本例中仅仅保留展开(式3.4)中的个大系数得到,其中表示系数向量的除K个大系数外其余置0的向量。该向量从严格意义上说是稀疏的,因为K<<N ,即除了极少数项外其余均为0。

    现在稀疏的含义很清楚了:如果x在某个变换域下是稀疏或者可压缩的,就意味着将x的系数按幅值大小排列衰减很快,那么x可以由K个大系数很好地逼近。图3.3(c)所示告诉我们,可以丢弃除了少数几个系数外的所有小系数而不会带来视觉上的损失。我们称至多有K个非零项的向量为K -稀疏,且有。稀疏性原理是大部分现代有损压缩编码算法和许多其它应用的基础。不过在传统编码中,这K个大系数的位置必须事先确定。更一般地,稀疏性是一个基本的建模工具,可以进行信号的精确统计估计和分类、有效的数据压缩等等。而近几年来Candès等人提出的压缩感知理论使得稀疏性有了更加令人惊奇的深远含义,即信号稀疏性对采样本身有重要意义,稀疏性决定了我们可以摆脱奈奎斯特采样频率的约束,并可以做到高效地非自适应地采样信号。

     

     

     

     

    (b)coins图像的9/7小波系数在一维下的表示

     

     

     

           
         
       
     

     

     

     

     

     

     

     

               
     

    (a)512x512的coins原始图像

       

    (c)1/16系数重构图像(PSNR=29.09dB)

     
     
       

    图2.2稀疏重构图像案例

     

     

     

     

    2 不相关性

        Candès, Romberg等人已经证明一个降维的投影集合包含了重构稀疏信号的足够信息。这就是压缩感知(CS)理论的核心内容。在CS中,假定信号在某个变换域的系数是K项稀疏的,我们不直接对K个重要的系数直接编码,而是将信号的系数向量投影到另一个基函数集合上,观测得到M (<<N)个投影然后再编码。用矩阵表示,则有,。其中Y 是一个的列向量,观测矩阵是一个以每个基向量作为行向量的矩阵。由于M<<N,从观测向量y中重构信号x是一个欠定问题,然而信号稀疏的附加假设使得恢复成为可能也是可行的。

    CS理论告诉我们,当满足一定条件时,也即是基不能稀疏表示(该条件被称为两组基不相关)并且观测值个数M足够大,那么就可以从一个相似规模的集合中恢复大系数集合,继而也就可以得到信号X。许多对基都满足不相关性质,例如,三角尖峰和傅里叶基中的正弦波不相关,傅里叶基和小波基不相关。重要的是,任意一个固定的基和一个随机产生的基也以高概率满足这种不相关。因此在CS理论中随机矩阵被广泛应用于CS观测中。在框架下或者基下可以找到稀疏表示的信号都可以以同样的方式从不相关观察中恢复。

    文献[3]给出了相关性度量的具体定义,如下。

    定义3.2:观测系统和表示系统之间的相关性度量用表示,则有如下式子成立:

        (式2.2)

     

    简单来讲,相关性度量的是两个矩阵和的元素之间的最大相关性。如果和包含了相关的元素,则相关性很大;否则,就很小。相关系数取值范围为。压缩采样研究的是具有低相关性的两个系统。下面给出一些例子。

    (1)是尖峰基,为傅立叶基,则有。进一步讲,尖峰信号和正弦信号不仅在一维而且在任何维,例如2D,3D空间都具有最大的不相关性。

    (2)为小波基,是noiselet。这里,noiselet和Haar小波基间的相关系数是,noiselet和Daubechies db4及db8小波基间的相关性分别是2.2和2.9。这也可以扩展到高维情况。noiselets也和尖峰信号及傅立叶基高度不相关。人们对noiselets感兴趣基于以下两个事实:1)它们和为图像数据和其它类型的数据提供稀疏表示的系统不相关;2)它们具有快速算法。noiselet变换的时间复杂度为O(N),而且类似于傅立叶变换,noiselet矩阵不需要存储。这一点对于高效的数字计算是至关重要的。如果没有高效的计算,CS的实用性就会大打折扣。

    (3)为随机矩阵,则可以是任何固定的基。此时它们之间具有极大不相关。例如,可以通过在单位球面上独立均匀地采样并做规范正交化得到,此时,和间的相关性以很高的概率为。各项服从独立同分布的随机波形,例如高斯分布或者,也表现出和任何固定基具有很小的相关性。

    研究者们通过大量的实验分析,得出如下结论:精确重构所需要的观测值个

    数依赖于稀疏变换基和观测基之间的不相关性。不相关性越强,所需的个数越少;反之,相关性越强,例如,则需要采样所有的系数才能保证精确重构。

    2.2 三个关键技术

    从以上压缩感知理论的介绍中我们可以看出,压缩感知理论主要包括以下三个方面的内容:

    (1)信号稀疏表示;

    (2)信号的编码测量即观测矩阵的设计;

    (3)信号重构算法的设计。

    信号的稀疏表示是指当将信号投影到某个正交变换基时,一般情况下绝大多数的变换系数的绝对值都是很小的,得到的变换向量也是稀疏的或者是近似稀疏的,这是原始信号的一种简洁的表达方式,也是压缩传感理论的先验条件。信号必须得在某种变换下才可以进行稀疏表示。通常我们可以选取的变换基有离散傅里叶变换基(DFT)、离散余弦变换基(DCT)、离散小波变换基(DWT)、Curvelet 变换基、Gabor 变换基还有冗余字典等。在信号的编码测量即观测矩阵的设计过程中,要选择稳定的观测矩阵,观测矩阵的选取必须满足受限等距特性(Restricted Isometry Property,RIP)准则,才能保证信号的投影能够保持原始信号的结构特征。通过原始信号与观测矩阵相乘我们可以获得原始信号的线性投影值。最后设计合适的重构算法从所得到的观测值和原来的观测矩阵来重构原始始号。

    所以对压缩感知理论的研究也主要是基于这三个方面的内容:

    (1)信号的稀疏表示。即对于信号 ,如何找到一个合适的正交基或者紧框架Ψ,以使得原始信号在Ψ上的表示是稀疏的。

    (2)观测矩阵的设计。即如何设计一个平稳且满足受限等距特性条件或者与变换基Ψ 满足不相关约束条件的M × N 维观测矩阵Φ,以保证信号稀疏表示后的向量Θ能从原来的N 维降到M 维时所包含的重要信息没有受到破坏,从而保证原始信号的准确重构。这个过程也就是压缩感知理论中信号的低速采样过程。

    (3)重构算法的设计。即如何设计快速有效且稳定的重构算法,从所得到的低维观测向量中准确地恢复原始信号。

    下面我们对压缩感知理论的这三个关键技术做一个详细的总结和分析,以为后文对压缩感知理论在图像重构方面的研究打下基础。

    2.3信号的稀疏表示

    从傅立叶变换到小波变换再到后来兴起的多尺度几何分析(Ridgelet,Curvelet,Bandelet,Contourlet),科学家们的研究目的均是为了研究如何在不同的函数空间为信号提供一种更加简洁、直接的分析方式,所有这些变换都旨在发掘信号的特征并稀疏表示它,进一步研究用某空间的一组基函数表示信号的稀疏程度或分解系数的能量集中程度。

    文献[23]给出稀疏的定义:信号X在正交基下的变换系数向量为,假如对于0<p<2和R> 0,这些系数满足:

      

              (式2.3)

     

    则说明系数向量在某种意义下是稀疏的。文献[34]给出另一种定义:如果变换系数的支撑域的势小于等于K,则可以说信号X K -项稀疏。

    如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提,只有选择合适的基表示信号才能保证信号的稀疏度,从而保证信号的恢复精度。在研究信号的稀疏表示时,可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candès 和Tao通过研究发现,满足幂定律衰减的信号,可利用压缩感知理论进行恢复,并且重构误差满足:

         (式2.4)

    其中r=1/p-1/2,0<p<1。

    文献[30]指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性,可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基,以求得信号的最稀疏表示,这是一个有待进一步研究的问题。Gabriel Peyré把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里,自适应地寻找可以逼近某一种信号特征的最优正交基,根据不同的信号寻找最适合信号特性的一组正交基,对信号进行变换以得到最稀疏的信号表示。

    最近几年,对稀疏表示研究的另一个热点是信号在过完备字典下的稀疏分解。

    字典的选择应尽可能好地符合被逼近信号的结构,其构成可以没有任何限制。从

    从过完备字典中找到具有最佳线性组合的K项原子来表示一个信号,称作信号的稀疏逼近或高度非线性逼近。

    过完备库下的信号稀疏表示方法最早由Mallat和Zhang于1993年首次提出, 并引入了MP算法。文献以浅显易懂的表达说明了过完备字典对信号表示的必要性,同时还指出字典的构成应尽量符合信号本身所固有的特性。

    目前信号在过完备字典下的稀疏表示的研究集中在两个方面:(1)如何构造一个适合某一类信号的过完备字典;(2)如何设计快速有效的稀疏分解算法。这两个问题也一直是该领域研究的热点,学者们对此已做了一些探索,其中,以非相干字典为基础的一系列理论证明得到了进一步改进。

    从非线性逼近角度来讲,信号的稀疏逼近包含两个层面:一是根据目标函数从一个给定的基库中挑选好的或最好的基;二是从这个好的基中挑选最好的K项组合。

    从过完备字典的构成角度来讲,文献[38]中提出使用局部Cosine基来刻画声音信号的局部频域特性;利用bandlet基来刻画图像中的几何边缘。还可以把其它的具有不同形状的基函数归入字典,如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet基等等。

    从稀疏分解算法角度来讲,在音视频信号处理方面,基于贪婪迭代思想的MP算法表现出极大的优越性,但不是全局最优解。Donoho等人另辟蹊径,提出了BP算法。BP算法具有全局最优的优点,但计算复杂度极高,例如对于长度为8192的信号,采用小波字典分解,等价于求解一个长度为8192*212992的线性规划。MP算法虽然收敛速度较BP快,但不具备全局最优性,且计算复杂度仍然很大。之后又出现了一系列同样基于贪婪迭代思想的改进算法,如正交匹配追踪算法(OMP),树形匹配追踪(TMP),分段匹配追踪(StOMP)算法等。

    2.4 观测矩阵设计

    观测部分的设计其实就是设计高效的观测矩阵,换句话说,就是要设计一个

    能捕捉稀疏信号中有用信息的高效的观测(即采样)协议,从而将该稀疏信号压

    缩成少量的数据。这些协议是非自适应的,仅仅需要用少量的固定波形和原信号

    联系起来,这些固定波形和为信号提供简洁表示的基不相关。此外,观测过程独

    立于信号本身。进一步讲,使用优化方法可以收集到的少量的观测值中重构信号。

    压缩感知理论中,通过变换得到信号的稀疏系数向量后,需要设计观测部分,它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值,并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然,如果观测过程破坏了X中的信息,重构是不可能的。观测过程实际就是利用观测矩阵的M个行向量对稀疏系数向量进行投影,即计算和各个观测向量之间的内积,得到M个观测值,

    ,记观测向量,即

     

         (式2.5)

     

     

    (b)

    (a)


        

     

     
     

    图2.3  观测矩阵的图形表示

     

     

     

    图3.4(a)是(式3.7)的形象描述。这里,采样过程是非自适应的,也就是说,无须根据信号X 而变化,观测的不再是信号的点采样而是信号的更一般的线性泛函。

    图3.4(a)随机高斯矩阵作为观测矩阵,稀疏域选择DCT变换域,对信号X进行DCT变换后再进行观测。(b)是(a)图的另一种表达,变换后的系数向量是稀疏的,K=3,观测得到的Y是非零系数对应的四个列向量的线性组合。

    对于给定的Y从(式3.7)中求出是一个线性规划问题,但由于M<< N,即方程的个数少于未知数的个数,这一欠定问题一般来讲无确定解。然而,如果具有K -项稀疏性(K<<M),则该问题有望求出确定解。此时,只要设法确定出中的K个非零系数的合适位置,由于观测向量Y是这些非零系数对应的K个列向量的线性组合,从而可以形成一个的线性方程组来求解这些非零项的具体值。对此,有限等距性质(restricted isometry property, RIP)给出了存在确定解的充要条件。这个充要条件和Candès、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即,要想使信号完全重构,必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中,这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。从中可以看出,问题的关键是如何确定非零系数的位置来构造出一个可解的线性方程组。

    然而,判断给定的是否具有RIP性质是一个组合复杂度问题。为了降低

    问题的复杂度,能否找到一种易于实现RIP条件的替代方法成为构造观测矩阵 的关键。

    文献[24]指出如果保证观测矩阵和稀疏基不相干,则在很大概率上满足RIP性质。不相干是指向量不能用稀疏表示。不相干性越强,互相表示时所需的系数越多;反之,相关性则越强。通过选择高斯随机矩阵作为即可高概率保证不相干性和RIP性质。例如,可以生成多个零均值、方差为1/ N 的随机高斯函数,将它们作为观测矩阵的元素,使得以很高的概率具有RIP性质。随机高斯矩阵具有一个有用的性质:对于一个的随机高斯矩阵,可以证明当时在很大概率下具有RIP性质(其中c是一个很小的常数)。因此可以从M个观测值中以很高的概率去恢复长度为NK-项稀疏信号。总之,随机高斯矩阵与大多数固定正交基构成的矩阵不相关,这一特性决定了选它作为观测矩阵,其它正交基作为稀疏变换基时,满足RIP性质。为进一步简化观测矩阵,在某些条件下,以随机为元素构成的Rademacher矩阵也可以证明具有RIP性质和普适性。

        目前,对观测矩阵的研究是压缩感知理论的一个重要方面。在该理论中,对

    观测矩阵的约束是比较宽松的,Donoho在文献[23]中给出了观测矩阵所必需具备的三个条件,并指出大部分一致分布的随机矩阵都具备这三个条件,均可作为观测矩阵,如:部分Fourier集、部分Hadamard集、一致分布的随机投影(uniform Random Projection)集等,这与对RIP条件进行研究得出的结论相一致。但是,使用上述各种观测矩阵进行观测后,都仅仅能保证以很高的概率去恢复信号,而不能保证百分之百地精确重构信号。对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。文献[56]则从信息论角度描述了信息论与CS之间的联系。它指出,在模拟系统中,观测噪声也是影响观测次数的重要因素,为说明这一点,作者从信息论的角度研究了稀疏信号的率失真函数,给出了观测噪声对信号重建效果的影响。

    2.5 稀疏信号的重构

    压缩感知理论的核心问题是从观测得到的有限的M<<N个观测样本中重构出N长的原信号,即未知量个数比观测量要多得多。由于观测数量M 远小于信号长度N,因此不得不面对求解欠定方程组的问题,需要列举出空间的个稀疏空间,在计算上是相当复杂的。乍一看,我们几乎不可能期望从Y 恢复每个。然而,文献[23-26,28]的近期研究结果表明如果信号X 是稀疏的,那么(1)精确恢复是可能的;(2)真实信号实际上就是一个简单凸优化问题的解。但是,文献[30]和[23]均指出由于信号X 是稀疏的或可压缩的,这个前提从根本上改变了问题,使得问题可解,而观测矩阵具有RIP性质也为从M 个观测值中精确恢复信号提供了理论保证。

    为更清晰地描述压缩感知理论的信号重构问题, 首先定义向量的p-范数为

                           (式2.6)

    p=0时得到0-范数,它实际上表示X中非零项的个数。

    在信号X 稀疏或可压缩的前提下,求解欠定方程组的问题转化为最小0-范数问题:

       s.t.                 (式2.7)

         但是,它需要列出X中所有非零项位置的种可能的线性组合,才能得到最优解。因此,求解(式3.9)式的数值计算极不稳定而且是NP难问题。可见,压缩感知和稀疏分解问题从数学意义上讲是同样的优化问题。于是稀疏分解的已有算法可以应用到CS重构中。

    Chen,Donoho和Saunders指出,求解一个更加简单的1-范数最小优化问题会

    产生同等的解(要求和不相关):

       s.t.                 (式2.8)

    稍微的差别使得问题变成了一个凸优化问题,于是可以方便地化简为线性规划问题,典型算法代表:BP算法。

    不过,1-范数最小化不是寻找稀疏解的唯一方法;其它方法,例如贪婪算法也已被提出。

    由以上讨论我们可以得出结论:(1)相关性在CS中起着至关重要的作用:和相关性越小,需要采样的数目就越少。(2)仅仅观测比信号长度小得多的任何M 个系数的集合,不会损失信息。(3)最小化带线性方程约束的1-范数可以很容易地被转化为线性规划问题,于是可以找到更高效的求解算法。已经证明,如果,那么重构成功的概率超过。

    2.6 重构算法

    由前面的分析可知,过完备库下的稀疏分解问题和压缩感知理论的重构问题都是线性约束下的0-范数求解问题。因此这两类问题的求解本质上是一样的。于是用于过完备库下稀疏分解的方法都可以用于求解压缩感知理论的重构计算。

    定理2已证明:对于一个K项-稀疏(K<<N)长度为N的信号仅仅需要投影到另一个不相关基上的K+1个系数就可以以高概率被重构。然而,求得最小的0-范数解需要进行组合搜索,计算复杂度相当高。Candès 和Donoho 近来提出一种可行的基于线性规划的重构方法,论证了只使用对信号的cKc =3或者4)个观测值,利用线性规划的方法就可以得到和组合搜索相同的解。尽管BP算法可行,但在实际应用中存在两个问题:第一,即使对常见的图像尺寸,算法的计算复杂度也难以忍受,在采样点个数满足,时,重构计算复杂度的量级在;第二,由于1-范数无法区分稀疏系数尺度的位置,所以尽管整体上重构信号在欧氏距离上逼近原信号,但存在低尺度能量搬移到了高尺度的现象,从而容易出现一些人工效应,如一维信号会在高频出现振荡。

    针对上述问题,2005 年1 月Candès 和Romberg 提出了不同的信号恢复方法,该方法要求对原信号具有少量的先验条件,同时也可以对所求结果施加适当的限制,以约束重构信号的特性。通过在凸集上交替投影(Projections onto Convex Sets)的方法,可以快速求解线性规划问题。

    另一类基于贪婪思想的迭代算法以更多的观测数量作为代价达到了更加快速重构的目的。

    J.Tropp和A.C.Gilbert提出利用匹配追踪(MP)和正交匹配追踪(OMP)算法来求解优化问题重构信号,大大提高了计算的速度,且易于实现。树形匹配追踪(TMP)算法是2005年Chinh La 和Minh N.Do提出的。该方法针对BP、MP和OMP方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系,将稀疏系数的树型结构加以利用,进一步提升了重构信号的精度和求解的速度。匹配追踪类算法都是基于贪婪迭代算法,以多于BP算法需要的采样数目换取计算复杂度的降低。例如OMP算法,需要,个采样点数才能以较高的概率恢复信号,信号重构的计算复杂度为。2006年Donoho等人提出了分段正交匹配追踪(StOMP,stagewise OMP)算法。它将OMP进行一定程度的简化,以逼近精度为代价进一步提高了计算速度(计算复杂度为O(N)),更加适合于求解大规模问题。E. Hale, W. Yin基于分裂算子和同伦算子提出了求解最小1-范数大规模问题的方法,适合于纠错编码、磁共振成像、NMR波谱研究等领域的大规模问题求解。

        在上述各种方法中,观测矩阵中的所有值都非零,这样信号采样过程的计算量是O(MN),在大规模的数据面前,这个量级还是非常大的。因此一类利用稀疏矩阵作为观测矩阵进行采样的方法出现了。Graham Cormode等人,提出利用分组测试和随机子集选取来估计稀疏信号的非零系数的位置和取值,该方法需要的采样数为,信号重构的计算复杂度为,得到重构信号的速度更快。

    Gilbert等人在2006 年4 月提出了链式追踪(CP,Chaining Pursuit)方法来恢复可压缩信号。利用个采样观测重构信号,需要计算量为,该方法对特别稀疏信号的恢复计算性能较高,但当信号的稀疏度减少,需要的采样点数会迅速增加,甚至超过信号本身的长度,这就失去了压缩采样的意义。

    总之,目前为止出现的重构算法都可归入以下三大类:

    (1)贪婪追踪算法:这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号。这些算法包括MP算法,OMP算法,分段OMP算法(StOMP)和正则化OMP(ROMP)算法。

    (2)凸松弛法:这类方法通过将非凸问题转化为凸问题求解找到信号的逼近,

    如BP算法,内点法,梯度投影方法和迭代阈值法。

    (3)组合算法:这类方法要求信号的采样支持通过分组测试快速重建,如傅

    立叶采样,链式追踪和HHS追踪等。

    总之,每种算法都有其固有的缺点。凸松弛法重构信号所需的观测次数最少,

    但往往计算负担很重。贪婪追踪算法在运行时间和采样效率上都位于另两种算法

    之间。

    由上面的分析可知,重构算法和所需的观测次数密切相关,当前,压缩感知

    理论的信号重构问题的研究主要集中在如何构造稳定的、计算复杂度较低的、对

    观测数量要求较少的重构算法来精确地恢复原信号。

    2.7 压缩感知优势及不足

    相对于传统的信息处理方式,压缩感知理论毫无疑问是具有优势的,这体现在以下几个方面:

    (1)采集数据的时候只需要采集一部分数据(包含了原信号的全局信息),一开始就可以传输长度较短的信号。这样做的好处就是将信号压缩这一端的过程简单化,而将复杂的部分交给数据还原的这一端来做。这种优势在医学图像领域体现的愈为明显,因为采集数据的过程往往是对病人带来很大麻烦甚至身体伤害的过程。以 X 光断层扫描为例,众所周知 ,X 光辐射会对病人造成身体损害,而压缩感知的特点使得我们可以用比经典少得多的辐射剂量来进行数据采集,这在医学上的意义是不言而喻的。

    (2)由于直接感知压缩后的数据,所以不受奈奎斯特采样定律的局限,降低了对采样系统硬件设备的要求,这对于宽带信号非常实用。

    (3)具有抗干扰能力。由于感知到的测量值中的任何一项都是重要的,或者说不重要的, 所以如果测量值丢失了其中的某几项,仍然可以完美重构信号。

    当然,目前的压缩感知理论还不是特别完善, 尚存在一些问题需要研究,在这里将列出其中几个问题:

    (1)实际应用领域中,测量到的数据可能无法包含信号的全局信息,例如最传统的摄像问题,每个感光器件所感知到的只是一小块图像而不是什么全局信息。

    (2)感知到的测量值的长度一般是重要分量长度的4倍,才能近乎完美地重构。

    (3)重构算法是NP问题。即使将0-范数转化为1-范数,由于不可微性(indifferentiable),算法的计算复杂度仍然很高。而且,目前的重构算法对含噪信号或者采样过程中引入噪声的信号重构效果不够理想。

    (4)压缩感知理论是采用非自适应线性投影来保持信号的原始结构,不够灵活,需要研究自适应传感技术,根据不同的信号类型采用不同的数据采样和重构策略。

    2.8 压缩感知在传感网中的观测方式

    之前已经提及将压缩感知运用到传感网中,即在节点处得到观测值数据并传给sink节点(或者融合中心)。现在将分别讲述压缩感知在传感网中的两种观测方式。

    1. 第一种:模拟通信方式

    模拟通信,即传输的测量值是模拟数据,具体步骤如下(假设有个传感节点):

    1. 对于个节点而言,每一个节点都要利用其节点网络地址(或者编号)作为产生伪随机的种子(seed),得到随机投影矢量的个K元素。sink节点在知道种子和节点在网络中的地址后,也能够很容易的为每个传感节点j(j=1,...,n)重建出随即矢量
    2. )编号为j的传感节点将所感知数据与,相乘得到个元组

          (式2.9)

    所有的节点在k个时隙内(次传输)连贯的将相应的以模拟方式传至融合中心。由于无线电波的累加性质,在k次传输后sink节点最终得到的接收信号为

          (式2.10)

    其中ω为通信过程中产生的噪声。

    以上步骤是以完全分散的形式将感知数据的k个随机投影在k次传输中传给sink节点。

    1. 第二种:数字通信方式

    数字通信方式,即传输的测量值是量化后的值。这种方式可以达到同样的目的。假设节点能够进行本地通信,并能建立一条路由,从而与某个确定的簇头节点之间形成生成树。具体步骤如下:

    1)首先传感节点能够计算测量值;

    2)然后这些测量值可以经过聚合在簇头节点得到所有测量值V=Ax,然后对这些值进行编码传至sink节点。

    这两种方法主要的不同就在于第一种方式不需要复杂的路由信息。但考虑到数字通信的抗噪声能力强,远距离传输能保证信号质量,在本文中将选取第二种方式。

     

     

     

     

     

     

     

     

    第3章 压缩感知理论应用概述

    压缩传感理论带来了传统信号采样理论的变革,而且具有很广阔的应用前景和场合。现有的应用主要包括压缩感知成像、模拟信息的转换、生物传感等方面。

    3.1 压缩成像

    运用压缩感知原理,美国RICE大学已经成功研制了“单像素”压缩数码照相机,设计的原理是首先通过光路系统将成像目标投影到一个数字微镜器件上,然后其反射光由透镜聚焦到单个光敏二极管上,光敏二极管两端的电压值即为一个测量值y,将此投影操作重复M次,得到测量向量y,然后用最小全变分算法构建的数字信号处理器重构原始图像f。数字微镜器件由数字电压信号控制微镜片的机械运动以实现对入射光线的调整,相当于随机观测矩阵Φ。由于该相机直接获取的是M次随机线性测量值,而不是获取原始信号的N (M << N)个像素值,为低像素相机拍摄高质量的图像提供了可能。而且压缩感知技术也可以应用于雷达成像领域,与传统雷达成像技术相比,压缩感知雷达成像主要实现了两个重要改进:在接收端省去了脉冲压缩匹配滤波器;同时因为避开了对原始信号的直接采样,降低了接收端对模数转换器件带宽的要求。设计的重点由传统的设计昂贵的接收端硬件转化成为设计新颖可靠的信号恢复算法,从而简化了雷达成像系统。Bhattacharya等人将压缩感知理论应用到合成孔径雷达图像数据获取上,从而解决了海量数据的采集和存储问题,显著降低了卫星图像处理的计算代价。另外,压缩传感技术也可以应用于医学成像领域,如稀疏核磁共振成像、压缩感知三维磁共振波谱成像等等。

    3.2 模拟信息转换

    对于带宽非常高的信号,比如雷达和通信信号处理系统涉及的射频信号,根据奈奎斯特定理,要获得完整的信号信息,所采用的模数转换器必须具有很高的采样频率。然而由于传感器及转换硬件性能的限制,获得的信号的带宽要远远低于实际信号的带宽,存在较大的信息的丢失。对此Kriolos等人设计了基于压缩感知理论的模拟/信息转换器,利用压缩感知理论中测量信息可以得到完整信号的原理。首先获得原始信号的线性测量,再利用后端数字信号处理器重构原始信号或者直接计算原始信号的统计数据等信息。Laska等人进一步发展了基于随机采样系统的模拟/信息转换器,并给出了随机抽样系统的两种实现模型:第一种模型采用多个并行低采样率的模数转换器,每个模数转换器之间有等间隔的位移,通过随机控制来自不同的模数转换器的采样,实现随机采样。然而这种方法却需要多个模数转换芯片,每个芯片利用率不太高。第二种模型采用一组电容和数字控制换向器随机采样,该系统只需要一个模数转换芯片即可。

    3.3 生物传感

    生物传感中的传统DNA芯片能平行测量多个有机体,但是只能识别有限种类的有机体,Sheikh等人运用压缩感知和群组检测原理设计的压缩感知DNA芯片克服了这个缺点,压缩感知DNA芯片中的每个探测点都能识别一组目标,从而明显减少了所需探测点数量。此外,基于生物体基因序列稀疏特性,Sheikh等验证了可以通过置信传播的方法实现压缩感知DNA芯片中的信号重构。

    除此之外,压缩感知理论还被应用于信号的检测分类、数据的通信、无线传感器网络应用和地球物理数据的分析等众多的领域。

    3.4 本章小结

    本章详细描述了压缩感知理论基本框架。压缩感知理论是一个非常简单有效的信号采集协议,它以较低采样速率和独立于信号的采样方式采样信号,然后又用强大的计算能力从看上去不完整的观测集合中重构原信号。对压缩感知理论实现的两个前提要求——信号稀疏性及观测矩阵和稀疏表示基之间满足不相干性进行了详细的论述,着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新研究进展情况。

     

    压缩感知理论是近几年刚刚兴起的理论,但却展现了强大的生命力引起了广泛的关注,下面我们将对该理论的历史和发展历程做出介绍。

     

     

     

     

     

     

     

     

     

     

     

    1. CS在无线传感网中的应用

    前文我们已经对压缩感知(CS)理论做了叫详细的介绍,下面我将介绍将压缩感知应用于无线传感的优势以及采用OMP算法,实现对一维信号和二维信号图像的CS重构。

    4.1 研究背景

    前面绪论中已经提到无线传感网中的一些感知数据具有时间相关性和空间相关性,利用这种数据特点,人们可以对感知数据进行了压缩处理。下面将介绍已有的基于相关性的数据压缩技术,并阐明利用CS压缩数据的优势。

    4.1.1 基于感知数据相关性的压缩

    利用传感数据间的时间相关性,文献[13]提出了节省一个传感器节点内存和计算资源的无损压缩算法。利用传感数据间(相邻传感器节点在同一时刻所采集的数据之间)的空间相关性,文献[17]提出了在多层架构中,运用多重主成分分析法(Multiple Principal Component Analysis, MPCA)去除了普通节点间的数据相关性以及相邻簇头节点主成分之间的相关性,而文献[26]则将近年提出压缩感知算法运用到基于分簇的传感网数据压缩中,降低了传输能耗。文献[33]在时域和空间域提出了多分辨率和查询(Multiresolution Compression and Query, MCQ)架构,用离散余弦变换和差分编码技术来降低数据冗余度,延长网络寿命。但是这些算法并没有综合考虑时间相关性和空间相关性,文献[46]将融合了这两种相关性的分布式信源编码运用到传感网的数据压缩中。在一些分布式编码算法中,需要进行传感器节点间的信息交换,传输这些信息需要消耗能量,因此,文献[13,22]提出了基于联合稀疏模型的分布式压缩感知算法,既采用了两种相关性,又不需要传感器节点之间交换信息,而且能够大大降低所需要传输的测量值的数目,在此基础上,文献[21]还利用贝尔实验室所采集的实际数据进行了仿真验证。另外文献[26]在分布式架构的基础上利用小波提升算法来压缩数据,而文献[23]则优化了簇内信息的交换,此外,文献[25]也都各自阐述了相应的数据压缩技术。

    4.1.2传统压缩重构方法

    信号压缩一般是通过改变信号的表示方式来实现的,所以压缩和编码也是分不开的。信号压缩的分类方法根据不同的原理大致可以分为两种。首先根据编码的原理和处理的空间域的不同可以将图像压缩方法分为在空间域和变换域编码表示这两大类。

    (1)空间域处理方法

    空间域处理方法是指直接在图像所在的空间对图像进行压缩处理。包括点处理方法(基于像素)和模块处理方法(基于模板)。空间域处理方法的特点是具有较强的实时处理能力,但缺点是压缩比不太高。

    (2)变换域处理方法

    变换域处理方法是指图像编码在图像的某个变换域中进行处理。将图像从空间域变换到一个变换域来进行描述。图像经过变换之后去掉了像素之间的相关性,而且此时能量比较集中,比较有助于后续进一步的压缩处理;在变换域对图像进行处理的效果会比直接在空间域处理的效果要好。变换域编码处理的优点是抗信道误码的能力较强,缺点是算法较复杂,对硬件设备技术要求较高,成本相对较高。常用的图像变换处理方式有:离散傅里叶变换(Discrete FourierTransfrom,DFT),离散余弦变换(Discrete Cosine Transform,DCT),离散沃尔什—哈达玛变换(Walsh-Hadamard),还有近些年来发展起来的小波变换等。

    变换域编码的流程图如图4.1所示:

     

     
     
    1. 编码框图

     

     

     

     

     

     

     
       

     

     

           
       
    1. 解码框图

     

     
     

    图4.1 基于变换域的编解码框图

     

     

     

     

    4.1.3 图像压缩重构质量的评价

    1.主观评价方法

    图像的最终接收者是人。所以,图像质量的好坏一般取决于人的主观判断。人眼是图像压缩重构后质量主观评价的工具。主观画质评价的实验方法有很多。例如:多用于图像阈值评价的调整法、极限法和恒值法。还有根据图像系统的各种物理心理因素有着一定关系的评价方法,如:排序法、评定尺度法、序列范畴法、配对比较法、谢菲配对比较法等。其中主观评价利用度较高、应用范围较广的是评定尺度法,该方法是给已排好顺序的范畴分别定一个相应的分数,用这个分数值来表达所评价对象的好坏程度。例如,将“非常不好”、“不好”、“一般”、“好”、“非常好”这五种范畴分别定为1,2,3,4,5 分,就可以以这个评价尺度上的数值为心理尺度来按照线性能否保证、能否估计等方式来评价。评价尺度如表4.1 所示:

     

     
     

    表4.1 图像质量主观评价尺度表

     

     

    评价得分

    画质好坏程度

    画质失真效果

    5

    非常好

    感觉不到失真

    4

    感觉到失真,但没有不舒服感觉

    3

    一般

    稍有感觉到不舒服

    2

    较差

    不舒服

    1

    非常不舒服的感觉

     

    2.客观评价方法

    所谓的客观评价方法,就是先定义一个数学公式,然后通过运算,得到一个数字量作为评测结果,这个方法经常被用于评价图像的失真程度。图像压缩编码的好坏一般有这样几个量来表征:

    (1)压缩比CR(Compression Ratio)

                                                       (式4.1)

    其中B代表图像压缩前所含的比特数,代表图像压缩后所含的比特数。

    每个像素所占的比特数又被称之为比特率,单位是bit/s,它是刻画压缩技术或系统的一个重要的性能指标。

    (2)图像压缩编解码速度和所需要的时间

    (3)峰值信噪比PSNR

                      (式4.2)

    式中L代表图像的灰度值的量化级数,例如对于8比特的量化,L=255,MSE 则代表归一化处理后的均方误差,它的定义形式为:

              (式4.3)

    其中M × N 代表图像的尺寸大小,Ψ(x, y)、Ψ’ (x, y)则分别代表原图像和压缩重建后图像在点(x, y)处的灰度值。

    一般来说,PSNR值是对图像重构质量客观评价的一个很重要的指标。通常情况下,当图像的PSNR值超过30dB 时,人们便很难从主观视觉感觉上找出重构后图像与原始图像之间的差异。应该注意的是,MSE和PSNR是从总体上来反映原始图像和重构图像的差别的,并不能反映局部的差别。有时候在同样的信噪比条件下,视觉效果还是会存在一定的差异,这主要还是由于误差的均匀程度所造成的。一般来讲,误差均匀时视觉效果较好,反之视觉效果不理想。所以大多数情况下,我们都可以用PSNR值来对图像的质量进行客观的评价,但有时候其结果可能会与主观评价结果不太相符。

    4.2 压缩感知理论算法对一维信号的实现

    正如本章引言中所提出,压缩感知理论突破了传统的乃奎斯特采样定理,将信号或图像的采样和压缩结合成一起,避免了传统的高速采样再压缩过程中大量采样资源的浪费。从而有效地减少了采样系统的复杂度,降低了系统成本,并且加快了信号和图像的重构速度。

    下面我们将重点介绍基于贪婪迭代思想的正交匹配追踪算法(OMP)是如何进行图像的压缩重构的。

    4.2.1 CS用于WSN的优势

    对于无线传感器网络来说,压缩感知相对于普通的信息压缩技术的最大优势就在于压缩率高,所需要的传输数据量小。绪论中提到无线传感器节点的信息处理能力有限,使得无线传感器网络中的汇聚节点无法接收和处理太多的信息,从而导致汇聚节点只能处理少数传感器节点所传输的信息,压缩感知理论的应用,恰好使得汇聚节点能够从这些少量的传输信息中得到整个网络的情况。

    文献中则详述了CS算法用于传感网络的优点:

    (1)为任意的联合稀疏信号群提供了一个通用编码方法;

    (2)传感节点之间完全不用合作,也就不需要有通信开销;

    (3)由于计算复杂度几乎都转移到了收集点的解码端,所以该算法可以在传感节点上的最简单的通信硬件上实施应用;

    (4)能够容错;对于测量和量化噪声具有鲁棒性,而且具有安全性;对于有损通信环节具有鲁棒性;

    (5)能够应用于一组传感网络信号的处理,可以用于信号的压缩、预测、检测和分类。

    4.2.2 观测重构模型

    在本章中,将采用OMP算法进行传感网中感知数据的重构。首先,根据第二章的介绍,得到基于OMP的模型图,如图4.2所示。

     

     

     

     

     

     

     
     

    图4.2 OMP算法观测重构模型

     

     

    在上图中,Xj(j{1,2,...J})是第j个节点的原始感知数据(长度为N),在各自的节点处经过计算得到相应的模拟测量值矢量Yj(j{1,2...J})(长度为M),这些模拟测量值经过无线传感网传输到簇头节点之后,在簇头节点集中进行量化编码得到量化的测量值矢量Yj’(j{1,2...J}),并再次通过无线传感网传输到sink节点,最后在sink节点利用OMP算法对每一个测量值矢量进行独立的解码恢复,得到重构后的信号Xj’(j{1,2,...J})。

    4.2.2 正交匹配追踪算法(OMP)

    匹配追踪算法是一种贪婪迭代算法,该算法的思想是在每次迭代过程中,首先从原子库中选择与信号最为匹配的原子,并同时求出原始信号并表示残差,再选择和信号残差最为匹配的原子,再经过一定数目的迭代过程之后,原始信号便可以由一些原子线性地表示出来。该算法的流程如图4.3所示。

     

     

     
     

    图4.3 OMP算法流程图

     

     

    OMP算法法继续沿用匹配追踪算法中的原子选择的准则,然后通过递归地对原子集合进行正交化的处理从而保证了迭代的最优性,这样便大大减少了迭代的次数。对K稀疏N维离散时间信号x,采用M×N 维高斯矩阵观测,一般只需要M = O(K ln N)的代价。OMP算法能够高概率重构原始信号,而且该算法的速度比l范数算法的速度更快。但是,该算法能够精确重构原始信号的理论保证却比l范数算法要弱,而且并非对所有的信号都能够非常准确地重构,它对于观测矩阵的要求也比较严格。

    4.2.3 算法的实现及结果分析

    为了实现压缩感知理论对信号的重建, 本文选取一维正弦波叠加测试信号:,采样频率,采样间隔,采样序列为,则原信号为:,其中信号长度N选取256。首先对一维测试信号进行离散傅里叶正交变换,得到它在傅里叶变换域的稀疏表示形式。然后选取M × N 维的随机高斯分布的白噪声矩阵作为观测矩阵。因为压缩感知理论要求观测值的长度一般要达到信号重要分量即信号稀疏度大小的四倍才能近乎完美重构,即要求M ≈ 4K 或 。信号的重构算法选取压缩感知理论工程领域应用最多的正交匹配追踪算法。

    该算法的流程框图如图4.3所示。具体算法实现步骤如下所示:

    (1)在MATLAB 中生成M×N维的高斯随机分布白噪声观测矩阵Φ=randn(M, N),并通过与原信号相乘获得原信号的M个线性测量值s = Φx,其中;

    (2)在MATLAB 中生成傅里叶正交变换矩阵Ψ = fft(eye(N, N))/ sqrt(N) 其中

    ,原信号x通过傅里叶正交变换得到变换域向量y = Φx,反变换则得到重构信号,其中是待求变换域向量,是K项稀疏的。令恢复矩阵,则约束等式可改写成。因为中未知数有N 个,方程只有M 个,且M<<N。因此,该方程有无穷多解。而由于是K 稀疏的,K<M,所以该方程有确定解;

    (3) 先假设稀疏度K=1,则在向量中,唯一非零元素在中对应的位置为q,于是便是恢复矩阵T的第q列与中的非零元素的乘积, 即

    , 且,其中δ 是一个小的常数。换句话说,T 的

    第q列与s的相似程度最高,即可以得

    ,所以只要求恢复矩阵T 的所有列与s的内积,找到内积绝对值最大的那列即可。该列对应的位置即为q;

    (4)根据最小二乘法,可得,此时,最小。

     

    计算余量,始终与正交;

     

    (5)对于本实验中K>1,再继续找到余量与T 中所有列向量最大的值即可(但第一次找到的那列要排除,因为已将它保留),即找到使的那列要排除,因为已将它保留)。

     

    (6)令,则余量 被更新为:

     

    (7)重复以上步骤,直至找到变换域所有K 个重要的分量。其中迭代次数要求m K ,当满足条件:,迭代终止,此时便得到重构的谱域向量y^。本实验中,为留有余量,迭代次数m从K至2K之间也选取了多个不同值进行测试。

    (8)做傅里叶逆变换重构得到时域向量。

    由此可将主程序分以下为四个模块(图4.4):

    (1)信号输入模块,本模块完成一维信号的输入和参数的设定,参数有主要有稀疏度K和测量数M等;

    (2)稀疏表示模块,将信号x稀疏表示;

    (3)OMP重构信号模块,本模块完成对信号的降维投影和重构;

    (4)信号输出模块,本模块输出原始信号x和重构信号x^。

     

     

     

     

     

     

    信号输入模块

    稀疏表示模块

    OMP重构模块

    信号输出模块

     

     
       

     

     

     

     
     

    图4.4 一维信号CS重构算法框架

     

     

     

    程序流程图如图4.5:

     

     

     
       

     

     

     

     
     

    图4.5 基于傅里叶变换的一维信号正交匹配算法压缩感知流程图

     

     

    在 MATLAB7.0 实验平台下,为验证高概率重构原始信号所需观测值M的大小,本文选取了不同M值的观测矩阵对原信号进行观测采样,得到了不同的重构效果。不同M值的选取所得到重构误差如表4.2所示。

     

     

     
     

    表4.2 不同测量数下的重构误差

     

    M值

    10

    15

    20

    25

    重构误差

    1.8051

    1.2772

    1.0908

    0.6689

    M值

    30

    40

    50

    64

    重构误差

    7.0638e-014

    6.9980e-014

    7.7848e-014

    5.9400e-014

     

     

    从表4.2 可以看出当观测值M的大小超过30时,重构误差在e-14数量级,从图4.6 也可以看出重构信号与原始信号非常接近,重构效果较好。而当M值较小时,重构误差较大,从图4.7也可以看出重构效果不理想。这也验证了压缩感知理论要求观测值的长度一般要达到信号重要分量四倍左右才能近乎精确重构这一条件要求。

    在实验过程中,并不是每次相同的观测值都会重构出相同误差值的信号,因为我们采用的是高斯随机观测矩阵。而且会出现经过多次以较小的M值(如20)进行运算后也能得到高精度的信号,但经过多次的实验表明,对一维测试信号,当观测值的长度达到信号重要分量即信号稀疏度四倍(M ≈ 4K )或时重构效果较为理想。算法性能较为稳定。这些也充分说明了该算法对维数较低的小尺度信号的重构效果较为理想,重构速度也较快。

     

     

     

     
     

    图4.6 基于DFT的一维信号OMP重构效果图(M=64)

     

     

     

     

     
     

    图4.7 基于DFT的一维信号OMP重构效果图(M=25)

     

     

     

    4.3 压缩感知理论算法对二维图像重构的实现

    4.3.1 基于小波变换的分块压缩感知理论

    由前面内容可以得知:压缩感知图像重建是利用图像在某个变换域具有稀疏表示的先验知识来完成的。而大部分图像本身却并不是稀疏的,一般都是通过某种稀疏变换进行稀疏表示的。现在的实际图像则常采用离散余弦变换和小波变换等非冗余的正交变换来进行表示。

    由于对图像进行小波变换之后小波系数的稀疏性,本文通过对测试图像进行小波稀疏变换,得到稀疏的小波系数矩阵;然后通过设计合适的观测矩阵对小波变换后的稀疏小波系数进行观测,得到数据量远小于原信号或图像维数N 的M 个观测值;最后通过采用合适的重构算法即求解一个基于严格的数学最优化问题来重构出小波变换域下的稀疏小波矩阵,从而得到重构后的图像。该方法的处理流程如图4.8所示:

     

     

    图4.8 基于小波变换的二维图像cs重构理论流程图

     

    4.3.2 实现步骤

    本文分别选取不同特性的两幅标准测试图像:大小为256×256的lena 图像、大小为256×256的rice图像,采用上述压缩感知方法对分别在不同的采样率下对图像进行变化重构。具体实现步骤如下所示:

    (1)选取大小为N×N的测试图像X,根据测试图像的大小进行适当的分块,把原始图像数据分成适当大小的不同块,如8×8块,16×16块,32×32等;

    (2)对每个子块进行离散余弦变换,以得到它在变换域的变换系数;

    (3)然后对变换域的系数进行量化处理,构成一个系数矩阵;

    (4)对每个数据块单元的稀疏变换系数用Z(Zigzag)行扫描将其变成一维的数列,以有利于后面的熵编码步骤;

    (5)对系数矩阵的直流(DC)、交流(AC)系数进行编码。

    (6)解码重构图像,计算峰值信噪比psnr

     

    (式4.4)

     

    其中,MSE 代表归一化处理后的均方误差,其计算公式为:

     

    (式4.5)

     

    整个编解码流程可以归纳为以下几个步骤:

    (1)首先像素大小为X = N×N的图像均匀分成互不覆盖大小为B×B的子块,i=1,2,…,n,

    (2)对每个块进行二维DCT 变换以得到它在变换域的系数表示形式,然后对变换域的系数进行量化Z行扫描以得到变换域系数稀疏矩阵的一维数列形式。

       (3)设计维数为的高斯随机观测矩阵,对量化扫描后的变换域系数进行观测采样得到长度为的观测值向量。对i子块的整个采样过程可表示为:          

     

    (式4.6)

                                                                             

    式中代表量化算子,Τ(⋅)是指二维离散余弦变换算子,则是序列长度为

    的观测采样向量。

       (4)定义为一个子块的采样算子,则整幅图像的等价采样矩阵可写成一个基于采样算子的对角矩阵Φ

     

     

    (式4.7)

     

     

     

    (5)重构算法可以通过求解一个基于范数的最小优化问题解决:

    目标函数:     且满足等式约束:    (式4.8)

    其中,s′是s的近似估计。

    根据以上步骤,我们将程序分为五个模块(图4.9):

     

     

     
     

    图4.9 二维图像CS重构算法框架

     

     

    (1)输入模块。本模块完成图像的输入和参数的设定;

    (2)CS压缩感知模块。本模块将输入图像进行DCT稀疏变换,降维投影,压缩编码;

    (3)OMP解码重构模块。本模块将压缩后的信号解码重构;

    (4)误差计算模块。本模块计算重构图像与原始图像的psnr值和mse值;

    (5)输出模块。本模块完成重构图像和各结果参数的输出。

     

     

    主程序流程图如图4.10:

     

     

     
     

    图4.10 基于离散余弦变换(DCT)的二维图像CS分块重构流程图

     

     

     

    CS压缩编码子程序流程图如图4.11:

     

     

     
     

    图4.11 CS压缩编码子程序流程图

     

     

    OMP重构子程序如图4.12:

     

     
     

    图4.12 二维图像OMP重构子程序

     

     

    4.3.3 重构结果及分析

    首先我们令分块都为8×8不变,通过选取大小不同的观测矩阵,即在不同的观测长度下,研究采样率对重构效果和重构时间的影响。本实验所选取的观测长度M分别为16、32、64、128。

    重构效果如图4.13和图4.14所示。

     

    (a) 原图

    (c) M=32

    (b) M=16

     

     

    (d) M=64

    (e) M=128

     

     

     
     

    图4.13 8×8分块CS在不同M值下lena图像重构效果图

     

     

    图4.14 8×8分块CS在不同M值下对coins图像重构效果图

     

    (e)M=128

    (d)M=64

    (a)原始图像

    (c)M=32

    (b)M=16

     

     

    过重构效果图可以看出,图像的质量随着采样率的增加而显著提高,当采样率较低时,采样信息不能包含图像的所有有效信息,重构会出现很多误差,甚至根本不能实现重构。在实验过程中对于不同稀疏度的图像重构的效果也是不一

    样的,重构的时间也相同。当采样率太低而重构算法不能有效进行时,重构时间会特别长,而重构效果也不好。表4.4 给出了在不同的测量值M下,该方法对两幅图像重构所用重构时间、PSNR(峰值信噪比)、MSE(均方差)的对比。

     

     
     

    表4.3 8×8分块CS在不同测量值下图像重构参数对比

     

     

     

    观测长度M

    Psnr(dB)

    MSE

    重构时间(s)

    lena

    16

    NaN

    NaN

    41.30

    32

    24.3720

    1.5572e+007

    20.03

    64

    33.2605

    2.0114e+006

    24.36

    128

    37.2576

    8.0131e+005

    27.43

     

    coins

    16

    NaN

    NaN

    21.49

    32

    24.2518

    1.6010e+007

    10.54

    64

    33.0032

    2.1342e+006

    12.86

    128

    37.5355

    7.5164e+005

    14.66

    从表4.3可以看出:当测量数增加时,重构图像的PSNR值有明显的提高,重构效果也相应增强,但当测量数偏低,如测量数为16时,PSNR值明显过低,重构效果很差。这也说明当采样率过低时,该算法的性能很低,达不到压缩感知重构算法的要求。但当采样率较高时,虽然重构图像的效果和PSNR值较高,但整个重构过程所花费的时间也随之增长。重构所需要的观测值数量较多的话,便体现不了压缩感知理论对信号重构所需要的低采样率的优势。所以该算法的性能还需得到进一步的改进和优化。

    上面我们只是在8×8分块的情况下运行算法进行图像重构,如果将图像分块为16×16时,会有什么效果呢?下面我们给出16×16分块下,图像cameraman和rice的重构效果图并做出结果分析。

    重构效果如图4.15和图4.16所示。

     

    (c)M=32

    (b)M=16

    (a)原图

     

     

    图4.15 16×16分块CS在不同M值下对coins图像重构效果图

    (e)M=128

    (d)M=64

     

     

     

    (e)M=128

    (d)M=64

    (a)原始图像

    (b)M=16

    (c)M=32

     

     

     
     

    图4.16 16×16分块CS在不同M值下对lena图像重构效果图

     

     

     

    通过实验分析可得采用不同分块重构效果的性能参数的比较如表4.4和表4.5所示:

     

     
     

    表4.4 分块压缩感知对lena不同分块的性能比较

     

     

    lena

    分块(8×8)

    分块(16×16)

    测量值M

    PSNR(dB)

    重构时间(s)

    PSNR(dB)

    重构时间(s)

    16

    NaN

    41.30

    NaN

    11.57

    32

    24.3720

    20.03

    17.9850

    6.03

    64

    33.2605

    24.36

    20.9283

    7.32

    128

    37.2576

    27.43

    25.0834

    8.72

     

    表4.5 分块压缩感知对coins不同分块的性能比较

     

     

     

    coins

    分块(8×8)

    分块(16×16)

    测量值M

    PSNR(dB)

    重构时间(s)

    PSNR(dB)

    重构时间(s)

    16

    NaN

    21.49

    NaN

    6.88

    32

    24.2518

    10.54

    17.3982

    3.38

    64

    33.0032

    12.86

    21.1624

    4.31

    128

    37.5355

    14.66

    25.9449

    5.03

     

    通过重构效果图可以很明显的看出,随着测量数的增加,重构效果明显增强,重构图像的信噪比PSNR值也随之提高。而从不同分块的效果图以及表4.5和表4.6中的数据可以得出,对于相同的采样数,随着分块大小的减小,图像的重构效果会有很大的提高,但重构时间则会随之增加。分块16×16的重构时间比分块8×8的重构时间少的多,但相应的其重构质量却大为下降。如何构造稳定的、计算复杂度较低的、对观测次数较少的重构算法来精确的恢复可压缩信号,将是未来压缩感知的一个重要的研究方向。

    4.4 本章小结

    本章说明了压缩感知/分布式压缩感知用于无线传感网的优势。重点对基于变换域处理的图像压缩方法做了详细的研究,在此基础上实现了小波变换编解码对一维信号和二维图像的变换重构。在离散傅里叶变换和小波变换的基础上,采用压缩感知理论框架的正交匹配追踪算法实现了对一维信号和二维图像的高概率重构,通过实验结果分析对其进行了重构效果的主客观评价。

    第5章 总结与展望

    5.1 工作总结

    利用信号的稀疏特性,压缩感知理论将传统的基于奈奎斯特采样定理的信号采样过程转化为基于优化准则恢复信号的观测过程,省去了高速采样过程中获得大批冗余数据然后再舍去大部分无用数据的中间过程,从而有效缓解了高速采样实现的压力,减少了处理、存储和传输的成本,使得用低成本的传感器将模拟信息转化为数字信息成为可能。 在压缩感知理论上,结合分布式信源编码技术,得到适合分布式网络数据处理的分布式压缩感知理论。在分布式压缩感知理论的框架下,分析了适合不同特点的感知数据的三种模型。 本文的研究工作主要是在介绍上述理论的基础上,首先,将用于压缩感知理论的OMP算法与用于传统算法在处理多信号的测量速率、信号平均信噪比等性能上作了比较,并首次分析了在多信号情况下,这两种算法平均处理单个信号所需要的时间复杂度。接着,将上述两种算法用于无线传感网中的实际的感知数据,结果表明OMP算法在不增加终端编码复杂度的情况下,更能够显著降低传输的测量速率,从而节省传感器节点的能量消耗,但是它对于量化比特数的影响更为敏感。

    5.2 后续展望

    由于自身能力和时间的限制,本文所做的研究工作还不是十分完善,有待进一步改进,今后可以从以下几个方面进行深入的探讨和研究:

    (1) 本文中直接采用了固定的稀疏基、测量矩阵以及信号重建算法,以后可以根据实 际感知数据的分布情况,选择最合适的搭配方式。

    (2) 本文仅仅对OMP算法和传统小波算法的时间复杂度作了简单比较,下一步可以研究如何有效降低这两种算法复杂度(包括空间复杂度),并且可以在综合考虑测量速率和复杂度的基础上提出折中方案。

    (3) 将压缩技术和路由策略相结合,进一步降低网络中的能量消耗。

    展开全文
  • Matelab 编程CS图像重构算法怎么输出均方差、峰值信噪比等,有没有谁给我完整的程序,让我做完毕业设计
  • 压缩感知原理简介

    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:浅谈压缩感知系列——博客园(非常丰富)
    压缩感知理论
    机器学习——低秩矩阵分解中低秩的意义、矩阵填补、交叉验证

    展开全文
  • 转自乔治亚理工大学官网,利用convex optimization算法压缩图片,运行前请先进行compile
  • 在我看来,压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果之一,并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学表述背后蕴含着非常精妙的思想。基于一个有想象力的思路,辅以...
  • 压缩感知(Compressed sensing),也被称为压缩采样(Compressive sampling)或稀疏采样(Sparse sampling),是一种寻找欠定线性系统的稀疏解的技术。如果一个线性方程组未知数的数目超过方程的数目,这个方程组被称为...
  • 压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。最近粗浅地看了这方面一些研究,对于Compressive Sensing有了初步理解,在此分享一些资料与精华。本文针对陶哲轩和Emmanuel Candes上次到北京的...
  • 点击链接进入相关博文 1.来自西弗吉利亚大学li xin整理的CV代码合集 ... 1.图像去噪,编码,去马赛克,超分辨,分割,去模糊,纹理合成,修复,质量评估等 ... 2.... 4.... 5.压缩感知
1 2 3 4 5 ... 20
收藏数 12,033
精华内容 4,813
关键字:

压缩感知技术 图像处理