基于MATLAB的图像压缩感知算法的实现毕业设计说明书

《基于MATLAB的图像压缩感知算法的实现毕业设计说明书》由会员分享，可在线阅读，更多相关《基于MATLAB的图像压缩感知算法的实现毕业设计说明书（50页珍藏版）》请在装配图网上搜索。

1、毕业设计（论文） 基于MATLAB的图像压缩感知算法的实现系： 电气工程系 专业： 电子信息工程 目录目录I第1章 绪论31.1 研究背景和意义31.2 数据压缩技术41.2.1 传统数据压缩技术41.2.2 压缩感知理论（Compressed/Compressive Sensing/Sampling, CS）51.3 无线传感器网络71.3.1 无线传感器网络概述71.3.2 无线传感器网络数据压缩的必要性91.4 本文主要工作和内容安排10第2章 压缩感知理论112.1压缩感知的前提条件稀疏性和不相干性112.2 三个关键技术142.3信号的稀疏表示152.4 观测矩阵设计172.5 稀疏

2、信号的重构192.6 重构算法202.7 压缩感知优势及不足212.8 压缩感知在传感网中的观测方式22第3章 压缩感知理论应用概述243.1 压缩成像243.2 模拟信息转换243.3 生物传感253.4 本章小结25第4章 CS在无线传感网中的应用264.1 研究背景264.1.1 基于感知数据相关性的压缩264.1.2传统压缩重构方法274.1.3 图像压缩重构质量的评价274.2 压缩感知理论算法对一维信号的实现294.2.1 CS用于WSN的优势294.2.2 观测重构模型304.2.2 正交匹配追踪算法（OMP）304.2.3 算法的实现及结果分析314.3 压缩感知理论算法对二维

3、图像重构的实现354.3.1 基于小波变换的分块压缩感知理论354.3.2 实现步骤364.3.3 重构结果及分析394.4 本章小结42第5章 总结与展望435.1 工作总结435.2 后续展望43参考文献44致谢46附录47摘要数据压缩技术是提高无线数据传输速度的有效措施之一。传统的数据压缩技术是基于奈奎斯特采样定律进行采样，并根据数据本身的特性降低其冗余度，从而达到压缩的目的。近年来出现的压缩感知理论（Compressed Sensing,CS）则不受制于奈奎斯特采样定律，它是采用非自适应线性投影来保持信号的原始结构，以直接采集压缩后的数据的方式，从尽量少的数据中提取尽量多的信息。本文阐

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

5、stract 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, Co

6、mpressed 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

7、 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 th

8、e 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 conclu

9、sion. 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 orthog

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

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

12、也会在各个节点之间传输，在这种分布式传感网络中，数据传输功耗和带宽需求非常大，所以，如何对这样的分布式信号进行压缩，从而减小通信开销已经成为非常紧迫的需求。压缩感知理论与传统奈奎斯特采样定理不同，它指出，只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。 在该理论框架下，采样速率不决定于信号的带宽，而决定于信息在信号中的结构和内容。 事实上，压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论， 最

13、近由Cands，Romberg ，Tao和Donoho等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。从信号分析角度来讲，傅立叶变换是信号和数字图像处理的理论基础，小波分析将信号和数字图像处理带入到一个崭新的领域。 多尺度几何分析是继小波分析后的新一代信号分析工具，它具有多分辨、局部化和多方向性等优良特性，更适合于处理图像等高维信号。 这些研究工作都为压缩感知理论奠定了基础。显然，在压缩感知理论中，图像/信号的采样和压缩同时以低速率进行，使传感器的采样和计算成本大大降低，而信号的恢复过程是一个优化计算的过程。 因此，该理论指出了将模拟信号直接采样压缩为数字形式的有效途径，具有直接

14、信息采样特性。 由于从理论上讲任何信号都具有可压缩性，只能找到其相应的稀疏表示空间，就可以有效地进行压缩采样，这一理论必将给信号采样方法带来一次新的革命。1.2 数据压缩技术数据压缩技术就是对原始数据进行数据编码或者压缩编码，从而用最少的数码来表示信源发出的信号。数据压缩的对象很广泛，可以是通信时间、传输带宽、存储空间甚至发射能量。数据压缩的作用是能够快速地传输各种信号；在已有的一些通信干线并行开通更多的多媒体业务；紧缩数据存储容量；降低发信机功率等等。1.2.1 传统数据压缩技术前较成熟的数据压缩技术有许多种，按照压缩后对信息的失真程度,主要分为无损压缩和有损压缩。 无损压缩是利用数据中的统

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

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

17、现了第三类压缩技术：混合压缩。它主要是求取在压缩效率、压缩比以及保真度之间的最佳平衡，如静止图像压缩标准JPEG和活动图像压缩标准MPEG就是采用混合编码的压缩方法。1.2.2 压缩感知理论（Compressed/Compressive Sensing/Sampling, CS）在传统理论的指导下，信号主要的一些压缩方法都要基于奈奎斯特采样定律进行采样，即信息采样速率至少为信号带宽的两倍。信号的编解码过程如图1.1所示：编码端首先获得X 的N点采样值，经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码，最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。实际上，采样得到的大部

18、分数据都是不重要的，即K值很小，但由于奈奎斯特采样定理的限制，采样点数N可能会非常大，采样后的压缩是造成资源浪费的根本所在。图1.1 传统编解码理论框图CS 理论的信号编解码框架和传统的框架大不一样，如图1.2 所示。CS 理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下，利用信号稀疏分解中已有的重构方法在概

19、率意义上实现信号的精确重构或者一定误差下的近似重构，解码所需测量值的数目远小于传统理论下的样本数。压缩感知的核心思想是压缩和采样合并进行，并且测量值远小于传统采样方法的数据量，突破了香农采样定理的瓶颈，使高分辨率的信号采集成为可能。 压缩感知理论主要包括信号的稀疏表示、随机测量和重构算法等三个方面。稀疏表示是应用压缩感知的先验条件，随机测量是压缩感知的关键过程，重构算法是获取最终结果的必要手段。图1.2 CS理论下数据的编解码过程压缩感知关键要素包括稀疏表示、测量矩阵和重构算法。信号在某种表示方式下的稀疏性，是压缩感知应用的理论基础，经典的稀疏化的方法有离散余弦变换（DCT）、傅里叶变换（FF

20、T）、离散小波变换（DWT）等。最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。 这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：一是如何构造一个适合某一类信号的冗余字典，二是如何设计快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分为匹配追踪（Matching Pursuit）和基追踪（Basis Pursuit）两大类。压缩感知理论中，通过变换得到信号的稀疏系数后，需要设计压缩采样系统的观测部分，它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值，并保证从

21、中能重构出长度为N的信号X或者稀疏基基下等价的稀疏系数向量。CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。2007年Candes等研究者建立了著名的约束等距性（RIP）理论，即要想使信号完全重构，必须保证观测矩阵不会把两个不同的 K项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。Donoho给出压缩感知概念的同时定性和定量的给出测量矩阵要满足三个特征：(1)由测量矩阵的列向量组成的子矩阵的最小奇异值必须大于一定的常数；(2)测量矩阵的列向量体现某种类似噪声的独立随机性；(3)满足稀疏度的解是满足1范数最小的

22、向量。目前常用的测量矩阵包括：（1）随机高斯矩阵。矩阵每个元素独立地服从均值为0，方差为的高斯分布。（2）随机贝努利矩阵。矩阵的每个元素独立地服从对称的贝努利分布，等概率为或-。 （3）部分正交矩阵。先生成NN的正交矩阵U（如傅里叶矩阵），然后在矩阵U中随机地选取M行向量，对MN矩阵的列向量进行单位化得到测量矩阵。（4）部分哈达玛矩阵。生成大小为NN的哈达玛矩阵，然后在生成矩阵中随机地选取M行向量，构成一个MN的矩阵。（5）托普利兹和循环矩阵。首先生成一个向量u，由向量u生成相应的轮换矩阵或托普利兹矩阵U，然后在矩阵U中随机地选取其中的M行而构造的矩阵。（6）稀疏随机矩阵。首先生成一个零元素的

23、矩阵，在矩阵的每一个列向量中，随机地选取d个位置，然后在所选取的位置的值赋为1。 压缩感知的重构算法主要分为两大类，一是贪婪算法，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。二是凸优化算法，它是把0范数放宽到1范数通过线性规划求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。凸优化算法算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。 此外，迭代阈值法也得到了广泛的应用，此类算法也较易实现，计算量适中，在贪婪算法和凸优化算法中都有应用。但是，迭代阈值法对于迭代初值和阈值的选取均

24、较敏感，且不能保证求出的解是稀疏的。就目前主流的两种重建算法而言，基于1范数最小的重建算法计算量巨大，对于大规模信号无法应用；贪婪算法虽然重建速度快，但是在信号重建质量上还有待提高。目前，上述理论已经应用到各个领域，如传感网、频谱感知、雷达、医学信号处理、信道预测等方面,取得了很好的效果。以上是关于压缩感知理论与分布式压缩感知理论的简单介绍，详细阐述将在第二章和第三章进行展开。 1.3 无线传感器网络 无线传感器网络是计算、通信和传感器这三项技术相结合的产物，一开始在军事应用中收集数据，对战场情况和威胁及其重要程度进行适时的完整评价，后发展到民事运用，如监控大型设备，灾区临时通信，卫生保健等等

25、。 1.3.1 无线传感器网络概述 无线传感器网络一般由若干传感器节点组成，节点是组成无线传感器网络的基本单位，它负责完成采集信息、融合并传输数据的功能。每一个传感器节点由数据采集模块（传感器、A/D转换器）、数据处理和控制模块（微处理器、存储器）、通信模块（无线收发器）和供电模块（电池、DC/DC能量转换器等）组成，如图1-3所示。 图1.3 无线传感器网络节点结构图 其中，数据采集模块负责感知所需要的信息，数据处理和控制模块负责对感知所得的信息和接收信息进行处理，通信模块负责与其他节点进行通信，即发送或者接收信息，供电模块则负责提供所需要的能量。 根据节点在传感网网络体系中所起作用的不同，

26、节点在网络中可以充当数据采集者、数据处理中转站或簇头节点几种角色： （1）数据采集者，这类节点的数据采集模块专门采集周围的环境数据（如温度、压力），然后通过通信路由协议直接或间接地将采集到的数据传输给远方基站（Base Station，BS）或汇聚节点（Sink）; （2）数据处理中转站，这类节点不仅要完成采集的任务，还要接收邻居节点的数据，一起转发给距离基站更近的邻居节点或者直接转发到基站或汇聚节点; （3）簇头节点，这类节点负责收集节点采集的数据，经数据融合后，发送到基站或汇聚节点。传感器节点都分散在特定的感知区域，相互合作、实时监测、感知和采集网络周边环境或监测对象的温度、声波等各种信息

27、。这些信息一经采集，就将通过嵌入式系统进行处理，最终通过随机自组织无线通信网络以多跳中继方式将所感知信息传送到用户终端，使人们无论在何时、何地、何种情况下都能获取大量详实可靠的信息,实现人、物和事件之间的无缝连接，从而真正实现“无处不在的计算”理念。 与传统的网络不同的是，传统网络以传输数据为目的，而无线传感器网络则是以数据为中心；与传统的Ad Hoc网络相比，无线传感器网络具有以下几点特征： （1）网络节点密度高，传感节点数量多 （2）传感器节点由电池供电 （3）网络拓扑变化频繁 （4）网络具有容错能力 1.3.2 无线传感器网络数据压缩的必要性 因为在无线传感器网络中，每个传感节点体积很小

28、，而且分布非常密集，若是对所有采集的数据直接进行传输，则所需传输的数据量将是非常惊人的，会导致网络拥塞，也会导致网络寿命缩短；又由于传感器节点由电池供电， 所以节点能量有限，而且无线传感器网络所布置的地方一般为人们不便于到达的地方，因此传感器节点中的的电池很难更换。为了节约能量，延长传感器网络的寿命，需要采用能效高的网络通信协议和数据局部处理策略（如数据融合技术、数据压缩技术）。 在这里，我们将说明利用压缩技术来减少传输的数据量的必要性和可行性。相对于数据采集、数据压缩这两项功能，数据传输所需要的能量是最多的，所以，如果要节约传感器节点的电池能量，必定要减少传输的数据量，因此在无线传感器网络中

29、运用数据压缩技术来减少数据量一直是一个值得深入研究的问题。无线传感器网络中的感知数据能够进行压缩是因为它具备数据压缩的前提条件：首先，传感器节点密度很大，节点之间感知的范围相互重叠，这种高密度的节点分布一方面使得感知数据可靠性增强，另一方面也引起了数据冗余，使得相邻节点之间所采集的数据具有高度相关性，称为空间相关性；其次，由于传感节点感知的物理数据大多数随着时间变化很缓慢，所以同一个传感器节点所感知的数据之间也有相关性，称为时间相关性。利用这两种相关性，可以对感知数据采取相应的数据压缩技术。 图1-4中监测区域中有大量的无线传感节点，传感节点可以感知各种物理环境，包括声音、温度、压力、地震等。

30、人们将传感器节点采集的大量数据采用某种压缩技术压缩，压缩后的少量数据传送到sink节点(或者是融合中心)，再由sink节点按照对应的恢复算法恢复出采集的数据。这样，通过传输少量数据就可以得到整个监测区域内的详细情况。 图1.4 无线传感网通信体系结构1.4 本文主要工作和内容安排 本文在介绍压缩感知理论/分布式压缩感知理论的基础上，将它们应用到无线传感数据压缩领域，用于压缩传感节点采集的信号，降低传输能耗，节约电池能量。 本文内容安排如下： 第一章 简单介绍了课题的研究背景，包括现有的数据压缩技术和有关无线传感网络的基本知识。 第二章 详细阐述了压缩感知理论，深入介绍了压缩感知理论的核心思想

31、可压缩信号（信号稀疏化）、测量矩阵和重构算法,总结了压缩感知理论的优势及不足。 第三章 进一步介绍由压缩感知理论发展而来的分布式压缩感知理论，分别描述了三种联合稀疏模型及其应用范围，最后，将其与压缩感知理论作了仿真性能比较。 第四章 将传感网中数据传输与压缩感知理论结合，分别利用压缩感知和分布式压缩感知框架下的信号压缩、重构方法对实际的感知数据进行处理，给出了实际的应用效果，并重点研究了量化对于算法的影响。 第五章 对全文进行总结并展望下一步的研究工作。 第2章 压缩感知理论 传统通信系统中的采样遵循的是奈奎斯特抽样定理，该定理指出，为防止在获得信号时损失信息，抽样速率必须大于信号带宽的两倍。

32、在许多应用中，包括数字图像和视频摄像中，奈奎斯特抽样速率太高，不利于数据存储和传输；在其他应用，包括图像系统（医疗浏览和雷达）、高速模数转换中，增加抽样速率代价也很昂贵。压缩感知则是保存原始信号结构的线性投影，然后再从这些投影中将信号重构出来，其速率远远低于奈奎斯特抽样率。CS理论系统与传统通信系统的类似关系如图2-1所示：CS恢复CS测量 图2.1 CS理论系统与传统通信系统的类似关系 由图2-1可知，在CS系统中，信源和信道编码被CS测量（即一个矩阵与信号矢量相乘的形式）代替；信道和信源解码则用CS恢复（即依赖于优化准则的恢复算法）替代。 压缩感知理论主要由三部分构成：稀疏信号、观测矩阵和

33、重构算法。下面将从这三个方面详细讲述压缩感知的关键技术。 2.1压缩感知的前提条件稀疏性和不相干性CS隐含的两个基本前提：稀疏性和不相关性。前者属于信号的性质，后者和感知（观测）形式有关。稀疏性：稀疏性表达了这样一个思想，一个连续时间信号的“信息速率”可能比由带宽所决定的香农采样率要低很多，或者，一个离散时间信号所依赖的自由度数目远远低于它的长度。更准确地说，CS利用了这样一个事实，即许多自然信号在某个合适的基下具有简洁的表达。不相关性：不相关性说明用于采样信号的波在基下有很稠密的表达。不相关性表达了这样的思想，正如时间域的Dirac或者冲击信号可以在频域展开那样，在基下具有稀疏表示的信号一定

34、可以在获得它们的某个域中展开。1 稀疏性众所周知，任意长度为N 的离散信号X 都可以表示为一系列基函数的叠加，即可以在任何正交基下用下式表示：（式2.1）其中由一组基向量构成的正交基，例如，sinusoids，尖峰spikes、B-splines，wavelets。为展开系数。展开系数大，说明信号和基足够相似。如果信号在基下的展开系数在很小的集合上有值，我们就说该信号在域是稀疏的，如果有值序列集中在一个小范围内，那么我们就说该信号是可以压缩的。本章我们将集中研究具有稀疏表示的信号，其中X是K个基向量的线性组合，KN。也就是说，中仅有K个非零，另外N -K个都是零。许多自然信号在一些基下有简洁的

35、表达。图3.3（a）是一幅具有N（N =512512）个像素点的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）中的个大系数得到，其中表示系数向量的

36、除K个大系数外其余置0的向量。该向量从严格意义上说是稀疏的，因为KN ，即除了极少数项外其余均为0。现在稀疏的含义很清楚了：如果x在某个变换域下是稀疏或者可压缩的，就意味着将x的系数按幅值大小排列衰减很快，那么x可以由K个大系数很好地逼近。图3.3（c）所示告诉我们，可以丢弃除了少数几个系数外的所有小系数而不会带来视觉上的损失。我们称至多有K个非零项的向量为K -稀疏，且有。稀疏性原理是大部分现代有损压缩编码算法和许多其它应用的基础。不过在传统编码中，这K个大系数的位置必须事先确定。更一般地，稀疏性是一个基本的建模工具，可以进行信号的精确统计估计和分类、有效的数据压缩等等。而近几年来Cands

37、等人提出的压缩感知理论使得稀疏性有了更加令人惊奇的深远含义，即信号稀疏性对采样本身有重要意义，稀疏性决定了我们可以摆脱奈奎斯特采样频率的约束，并可以做到高效地非自适应地采样信号。（b）coins图像的9/7小波系数在一维下的表示 （c）1/16系数重构图像（PSNR=29.09dB）(a)512x512的coins原始图像图2.2稀疏重构图像案例2 不相关性 Cands， Romberg等人已经证明一个降维的投影集合包含了重构稀疏信号的足够信息。这就是压缩感知（CS）理论的核心内容。在CS中，假定信号在某个变换域的系数是K项稀疏的，我们不直接对K个重要的系数直接编码，而是将信号的系数向量投影到

38、另一个基函数集合上，观测得到M (N)个投影然后再编码。用矩阵表示，则有，。其中Y 是一个的列向量，观测矩阵是一个以每个基向量作为行向量的矩阵。由于MN，从观测向量y中重构信号x是一个欠定问题，然而信号稀疏的附加假设使得恢复成为可能也是可行的。CS理论告诉我们，当满足一定条件时，也即是基不能稀疏表示（该条件被称为两组基不相关）并且观测值个数M足够大，那么就可以从一个相似规模的集合中恢复大系数集合，继而也就可以得到信号X。许多对基都满足不相关性质，例如，三角尖峰和傅里叶基中的正弦波不相关，傅里叶基和小波基不相关。重要的是，任意一个固定的基和一个随机产生的基也以高概率满足这种不相关。因此在CS理论

39、中随机矩阵被广泛应用于CS观测中。在框架下或者基下可以找到稀疏表示的信号都可以以同样的方式从不相关观察中恢复。文献3给出了相关性度量的具体定义，如下。定义3.2：观测系统和表示系统之间的相关性度量用表示，则有如下式子成立： （式2.2）简单来讲，相关性度量的是两个矩阵和的元素之间的最大相关性。如果和包含了相关的元素，则相关性很大；否则，就很小。相关系数取值范围为。压缩采样研究的是具有低相关性的两个系统。下面给出一些例子。（1）是尖峰基，为傅立叶基，则有。进一步讲，尖峰信号和正弦信号不仅在一维而且在任何维，例如2D，3D空间都具有最大的不相关性。（2）为小波基，是noiselet。这里，nois

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

41、通过在单位球面上独立均匀地采样并做规范正交化得到，此时，和间的相关性以很高的概率为。各项服从独立同分布的随机波形，例如高斯分布或者，也表现出和任何固定基具有很小的相关性。研究者们通过大量的实验分析，得出如下结论：精确重构所需要的观测值个数依赖于稀疏变换基和观测基之间的不相关性。不相关性越强，所需的个数越少；反之，相关性越强，例如，则需要采样所有的系数才能保证精确重构。2.2 三个关键技术从以上压缩感知理论的介绍中我们可以看出，压缩感知理论主要包括以下三个方面的内容：（1）信号稀疏表示；（2）信号的编码测量即观测矩阵的设计；（3）信号重构算法的设计。信号的稀疏表示是指当将信号投影到某个正交变换基

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

43、阵相乘我们可以获得原始信号的线性投影值。最后设计合适的重构算法从所得到的观测值和原来的观测矩阵来重构原始始号。所以对压缩感知理论的研究也主要是基于这三个方面的内容：（1）信号的稀疏表示。即对于信号 ，如何找到一个合适的正交基或者紧框架，以使得原始信号在上的表示是稀疏的。（2）观测矩阵的设计。即如何设计一个平稳且满足受限等距特性条件或者与变换基 满足不相关约束条件的M N 维观测矩阵，以保证信号稀疏表示后的向量能从原来的N 维降到M 维时所包含的重要信息没有受到破坏，从而保证原始信号的准确重构。这个过程也就是压缩感知理论中信号的低速采样过程。（3）重构算法的设计。即如何设计快速有效且稳定的重构算

44、法，从所得到的低维观测向量中准确地恢复原始信号。下面我们对压缩感知理论的这三个关键技术做一个详细的总结和分析，以为后文对压缩感知理论在图像重构方面的研究打下基础。2.3信号的稀疏表示从傅立叶变换到小波变换再到后来兴起的多尺度几何分析（Ridgelet，Curvelet，Bandelet，Contourlet），科学家们的研究目的均是为了研究如何在不同的函数空间为信号提供一种更加简洁、直接的分析方式，所有这些变换都旨在发掘信号的特征并稀疏表示它，进一步研究用某空间的一组基函数表示信号的稀疏程度或分解系数的能量集中程度。文献23给出稀疏的定义：信号X在正交基下的变换系数向量为，假如对于0p 0，这

45、些系数满足： （式2.3）则说明系数向量在某种意义下是稀疏的。文献34给出另一种定义：如果变换系数的支撑域的势小于等于K，则可以说信号X 是K -项稀疏。如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Cands 和Tao通过研究发现，满足幂定律衰减的信号，可利用压缩感知理论进行恢复，并且重构误差满足： （式2.4）其中r=1/p-1/2，0p1。文献30指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Ga

46、bor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一个有待进一步研究的问题。Gabriel Peyr把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一组正交基，对信号进行变换以得到最稀疏的信号表示。最近几年，对稀疏表示研究的另一个热点是信号在过完备字典下的稀疏分解。字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制。从从过完备字典中找到具有最

47、佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近。过完备库下的信号稀疏表示方法最早由Mallat和Zhang于1993年首次提出， 并引入了MP算法。文献以浅显易懂的表达说明了过完备字典对信号表示的必要性，同时还指出字典的构成应尽量符合信号本身所固有的特性。目前信号在过完备字典下的稀疏表示的研究集中在两个方面：（1）如何构造一个适合某一类信号的过完备字典；（2）如何设计快速有效的稀疏分解算法。这两个问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中，以非相干字典为基础的一系列理论证明得到了进一步改进。从非线性逼近角度来讲，信号的稀疏逼近包含两个层面：一是根据目标

48、函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最好的K项组合。从过完备字典的构成角度来讲，文献38中提出使用局部Cosine基来刻画声音信号的局部频域特性；利用bandlet基来刻画图像中的几何边缘。还可以把其它的具有不同形状的基函数归入字典，如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet基等等。从稀疏分解算法角度来讲，在音视频信号处理方面，基于贪婪迭代思想的MP算法表现出极大的优越性，但不是全局最优解。Donoho等人另辟蹊径，提出了BP算法。BP算法具有全局最优的优点，但计算复杂度极高，例如对于长度为8192的信号，采用小波字典分解，等价于求解一个长度为81

49、92*212992的线性规划。MP算法虽然收敛速度较BP快，但不具备全局最优性，且计算复杂度仍然很大。之后又出现了一系列同样基于贪婪迭代思想的改进算法，如正交匹配追踪算法（OMP），树形匹配追踪（TMP），分段匹配追踪（StOMP）算法等。2.4 观测矩阵设计观测部分的设计其实就是设计高效的观测矩阵，换句话说，就是要设计一个能捕捉稀疏信号中有用信息的高效的观测（即采样）协议，从而将该稀疏信号压缩成少量的数据。这些协议是非自适应的，仅仅需要用少量的固定波形和原信号联系起来，这些固定波形和为信号提供简洁表示的基不相关。此外，观测过程独立于信号本身。进一步讲，使用优化方法可以收集到的少量的观测值中重

50、构信号。压缩感知理论中，通过变换得到信号的稀疏系数向量后，需要设计观测部分，它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然，如果观测过程破坏了X中的信息，重构是不可能的。观测过程实际就是利用观测矩阵的M个行向量对稀疏系数向量进行投影，即计算和各个观测向量之间的内积，得到M个观测值，记观测向量，即 （式2.5）（b）（a） 图2.3 观测矩阵的图形表示图3.4（a）是（式3.7）的形象描述。这里，采样过程是非自适应的，也就是说，无须根据信号X 而变化，观测的不再是信号的点采样而是信号的更一般的线性泛函。图3.4（a

51、）随机高斯矩阵作为观测矩阵，稀疏域选择DCT变换域，对信号X进行DCT变换后再进行观测。（b）是（a）图的另一种表达，变换后的系数向量是稀疏的，K=3，观测得到的Y是非零系数对应的四个列向量的线性组合。对于给定的Y从（式3.7）中求出是一个线性规划问题，但由于M N，即方程的个数少于未知数的个数，这一欠定问题一般来讲无确定解。然而，如果具有K -项稀疏性（KM），则该问题有望求出确定解。此时，只要设法确定出中的K个非零系数的合适位置，由于观测向量Y是这些非零系数对应的K个列向量的线性组合，从而可以形成一个的线性方程组来求解这些非零项的具体值。对此，有限等距性质（restricted isome

52、try property， RIP）给出了存在确定解的充要条件。这个充要条件和Cands、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即，要想使信号完全重构，必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。从中可以看出，问题的关键是如何确定非零系数的位置来构造出一个可解的线性方程组。然而，判断给定的是否具有RIP性质是一个组合复杂度问题。为了降低问题的复杂度，能否找到一种易于实现RIP条件的替代方法成为构造观测矩阵F 的关键。文献24指出如果保证观测矩阵和稀疏基不相干，则在很大概率上满足RI

53、P性质。不相干是指向量不能用稀疏表示。不相干性越强，互相表示时所需的系数越多；反之，相关性则越强。通过选择高斯随机矩阵作为即可高概率保证不相干性和RIP性质。例如，可以生成多个零均值、方差为1/ N 的随机高斯函数，将它们作为观测矩阵的元素，使得以很高的概率具有RIP性质。随机高斯矩阵具有一个有用的性质：对于一个的随机高斯矩阵，可以证明当时在很大概率下具有RIP性质（其中c是一个很小的常数）。因此可以从M个观测值中以很高的概率去恢复长度为N的K-项稀疏信号。总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关，这一特性决定了选它作为观测矩阵，其它正交基作为稀疏变换基时，满足RIP性质。为进一步

54、简化观测矩阵，在某些条件下，以随机为元素构成的Rademacher矩阵也可以证明具有RIP性质和普适性。 目前，对观测矩阵的研究是压缩感知理论的一个重要方面。在该理论中，对观测矩阵的约束是比较宽松的，Donoho在文献23中给出了观测矩阵所必需具备的三个条件，并指出大部分一致分布的随机矩阵都具备这三个条件，均可作为观测矩阵，如：部分Fourier集、部分Hadamard集、一致分布的随机投影（uniform Random Projection）集等，这与对RIP条件进行研究得出的结论相一致。但是，使用上述各种观测矩阵进行观测后，都仅仅能保证以很高的概率去恢复信号，而不能保证百分之百地精确重构信

55、号。对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。文献56则从信息论角度描述了信息论与CS之间的联系。它指出，在模拟系统中，观测噪声也是影响观测次数的重要因素，为说明这一点，作者从信息论的角度研究了稀疏信号的率失真函数，给出了观测噪声对信号重建效果的影响。2.5 稀疏信号的重构压缩感知理论的核心问题是从观测得到的有限的MN个观测样本中重构出N长的原信号，即未知量个数比观测量要多得多。由于观测数量M 远小于信号长度N，因此不得不面对求解欠定方程组的问题，需要列举出空间的个稀疏空间，在计算上是相当复杂的。乍一看，我们几乎不可能期望从Y 恢复每个。然而，文献23-2

56、6，28的近期研究结果表明如果信号X 是稀疏的，那么（1）精确恢复是可能的；（2）真实信号实际上就是一个简单凸优化问题的解。但是，文献30和23均指出由于信号X 是稀疏的或可压缩的，这个前提从根本上改变了问题，使得问题可解，而观测矩阵具有RIP性质也为从M 个观测值中精确恢复信号提供了理论保证。为更清晰地描述压缩感知理论的信号重构问题， 首先定义向量的p-范数为 （式2.6）当p=0时得到0-范数，它实际上表示X中非零项的个数。在信号X 稀疏或可压缩的前提下，求解欠定方程组的问题转化为最小0-范数问题： s.t. （式2.7） 但是，它需要列出X中所有非零项位置的种可能的线性组合，才能得到最优

57、解。因此，求解（式3.9）式的数值计算极不稳定而且是NP难问题。可见，压缩感知和稀疏分解问题从数学意义上讲是同样的优化问题。于是稀疏分解的已有算法可以应用到CS重构中。Chen，Donoho和Saunders指出，求解一个更加简单的1-范数最小优化问题会产生同等的解（要求和不相关）： s.t. （式2.8）稍微的差别使得问题变成了一个凸优化问题，于是可以方便地化简为线性规划问题，典型算法代表：BP算法。不过，1-范数最小化不是寻找稀疏解的唯一方法；其它方法，例如贪婪算法也已被提出。由以上讨论我们可以得出结论：（1）相关性在CS中起着至关重要的作用：和相关性越小，需要采样的数目就越少。（2）仅仅

58、观测比信号长度小得多的任何M 个系数的集合，不会损失信息。（3）最小化带线性方程约束的1-范数可以很容易地被转化为线性规划问题，于是可以找到更高效的求解算法。已经证明，如果，那么重构成功的概率超过。2.6 重构算法由前面的分析可知，过完备库下的稀疏分解问题和压缩感知理论的重构问题都是线性约束下的0-范数求解问题。因此这两类问题的求解本质上是一样的。于是用于过完备库下稀疏分解的方法都可以用于求解压缩感知理论的重构计算。定理2已证明：对于一个K项-稀疏（KN）长度为N的信号仅仅需要投影到另一个不相关基上的K+1个系数就可以以高概率被重构。然而，求得最小的0-范数解需要进行组合搜索，计算复杂度相当高

59、。Cands 和Donoho 近来提出一种可行的基于线性规划的重构方法，论证了只使用对信号的cK（c =3或者4）个观测值，利用线性规划的方法就可以得到和组合搜索相同的解。尽管BP算法可行，但在实际应用中存在两个问题：第一，即使对常见的图像尺寸，算法的计算复杂度也难以忍受，在采样点个数满足，时，重构计算复杂度的量级在；第二，由于1-范数无法区分稀疏系数尺度的位置，所以尽管整体上重构信号在欧氏距离上逼近原信号，但存在低尺度能量搬移到了高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。针对上述问题，2005 年1 月Cands 和Romberg 提出了不同的信号恢复方法，该方法要

60、求对原信号具有少量的先验条件，同时也可以对所求结果施加适当的限制，以约束重构信号的特性。通过在凸集上交替投影（Projections onto Convex Sets）的方法，可以快速求解线性规划问题。另一类基于贪婪思想的迭代算法以更多的观测数量作为代价达到了更加快速重构的目的。J.Tropp和A.C.Gilbert提出利用匹配追踪（MP）和正交匹配追踪（OMP）算法来求解优化问题重构信号，大大提高了计算的速度，且易于实现。树形匹配追踪（TMP）算法是2005年Chinh La 和Minh N.Do提出的。该方法针对BP、MP和OMP方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系，将

61、稀疏系数的树型结构加以利用，进一步提升了重构信号的精度和求解的速度。匹配追踪类算法都是基于贪婪迭代算法，以多于BP算法需要的采样数目换取计算复杂度的降低。例如OMP算法，需要，个采样点数才能以较高的概率恢复信号，信号重构的计算复杂度为。2006年Donoho等人提出了分段正交匹配追踪（StOMP，stagewise OMP）算法。它将OMP进行一定程度的简化，以逼近精度为代价进一步提高了计算速度（计算复杂度为O(N)），更加适合于求解大规模问题。E. Hale， W. Yin基于分裂算子和同伦算子提出了求解最小1-范数大规模问题的方法，适合于纠错编码、磁共振成像、NMR波谱研究等领域的大规模问

62、题求解。 在上述各种方法中，观测矩阵中的所有值都非零，这样信号采样过程的计算量是O(MN)，在大规模的数据面前，这个量级还是非常大的。因此一类利用稀疏矩阵作为观测矩阵进行采样的方法出现了。Graham Cormode等人，提出利用分组测试和随机子集选取来估计稀疏信号的非零系数的位置和取值，该方法需要的采样数为，信号重构的计算复杂度为，得到重构信号的速度更快。Gilbert等人在2006 年4 月提出了链式追踪（CP，Chaining Pursuit）方法来恢复可压缩信号。利用个采样观测重构信号，需要计算量为，该方法对特别稀疏信号的恢复计算性能较高，但当信号的稀疏度减少，需要的采样点数会迅速增加

63、，甚至超过信号本身的长度，这就失去了压缩采样的意义。总之，目前为止出现的重构算法都可归入以下三大类：（1）贪婪追踪算法：这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号。这些算法包括MP算法，OMP算法，分段OMP算法（StOMP）和正则化OMP（ROMP）算法。（2）凸松弛法：这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，如BP算法，内点法，梯度投影方法和迭代阈值法。（3）组合算法：这类方法要求信号的采样支持通过分组测试快速重建，如傅立叶采样，链式追踪和HHS追踪等。总之，每种算法都有其固有的缺点。凸松弛法重构信号所需的观测次数最少，但往往计算负担很重。贪婪追踪算法在运行时间和采样效率上都位于另两种算法之间。由上面的分析可知，重构算法和所需的观测次数密切相关，当前，压缩感知理论的信号重构问题的研究主要集中在如何构造稳定的、计算复杂度较