基于压缩感知的正交匹配算法图像重建_毕业设计论文

1、基于压缩感知的正交匹配算法图像重建摘要：压缩感知理论是由Donoho和Candes提出的一种充分利用信号稀疏性的全新的信号采样理论。该理论说明，用远低于Nyquist采样定理要求的频率对信号进行采样也能实现信号的精确重构。该理论突破了传统的以Nyquist定理为基准的信号处理方法，实现了在获取数据的同时对其进行适当的压缩，克服了采样数据量大，采样时间长及数据存储空间浪费严重的问题，因此进一步降低了信号处理的时间和器件本钱。压缩感知理论有三个核心方面：1稀疏变换，即对一个非稀疏的信号，找到一个适宜的正交基使该信号在它上可以稀疏表示；2测量矩阵，与变换基不相干且平稳的矩阵；3重构算法，利用数学算法

2、完成对信号的精确重构，该过程可看为求解一个优化问题。本文介绍了主要介绍了压缩感知原理和目前最为成熟的压缩感知重建算法正交匹配追踪算法，通过MATLAB平台设计实现了根本的正交匹配追踪算法，对一维、二维信号进行了重建仿真。关键词：压缩感知；稀疏变换；正交匹配；图像重建Based On Compressed Sensing Of Orthogonal Matching Algorithm Image RecoveryAbstract：Compressed sensing is a novel sampling theory which is proposed by Donoho and Cands

3、. This theory is under the condition that the signal is compressible or sparse. In this case, using far less than the required sampling frequency of the Nyquist theory to sample the signal is able to accurately reconstruct the signal.Compressed theory breaks though the traditional Nyquist sampling t

4、heory, which overcomes a lot of problems such as a great number of sampling data, time wasting, data storage space wasting and so on. As a result, it reduces signal processing cost and device cost.The compressed theory has three key sides: (1) Sparse transformation, for a non- sparse signal, we need

5、 to find a proper orthogonal basis on which the signal has a sparse representation; (2) Observation matrix, it is irrelevant with the orthogonal basis; (3) reconstruction algorithms, using a reconstruction algorithm to ensure the accuracy of the signal reconstruction, the whole process can be consid

6、ered as the solve to a optimization problem.This paper introduces CS and most mature compression perception algorithm at present-Orthogonal matching algorithm. Through the MATLAB design realize basic orthogonal matching algorithms, Through the MATLAB design realize basic orthogonal matching algorith

7、m of one-dimensional, two-dimensional signal processing simulation.Key words：Compressed sensing; Sparse transform; Orthogonal matching; Image recovery.目 录 TOC o 1-3 u 第一章 绪论 PAGEREF _Toc357415638 h 21.1选题的背景及意义 PAGEREF _Toc357415639 h 21.2本课题在国内外的开展现状 PAGEREF _Toc357415640 h 21.3 本论文的结构安排 PAGEREF _T

8、oc357415641 h 3第二章 压缩感知理论相关知识 PAGEREF _Toc357415642 h 42.1压缩感知理论框架 PAGEREF _Toc357415643 h 42.2压缩感知的根本理论及核心问题 PAGEREF _Toc357415644 h 52.2.1 信号的稀疏表示 PAGEREF _Toc357415645 h 62.2.2 信号的观测矩阵 PAGEREF _Toc357415646 h 82.2.3 信号重构 PAGEREF _Toc357415647 h 92.3.压缩感知的应用 PAGEREF _Toc357415648 h 112.4 压缩感知有待研究的

9、几个问题 PAGEREF _Toc357415649 h 13第三章 正交匹配追踪重建算法 PAGEREF _Toc357415650 h 163.1最小L0范数模型 PAGEREF _Toc357415651 h 163.2匹配追踪算法 PAGEREF _Toc357415652 h 163.3正交匹配追踪算法(OMP) PAGEREF _Toc357415653 h 173.3.1 OMP算法原理 PAGEREF _Toc357415654 h 173.3.2 OMP算法实现步骤 PAGEREF _Toc357415655 h 173.3.3 OMP算法的Matlab语言实现 PAGERE

10、F _Toc357415656 h 17第四章 基于MATLAB的压缩感知图像重建仿真 PAGEREF _Toc357415657 h 204.1不同采样率下的仿真结果 PAGEREF _Toc357415658 h 20一维信号在不同采样率下的OMP仿真 PAGEREF _Toc357415659 h 20二维信号在不同采样率下的OMP仿真 PAGEREF _Toc357415660 h 224.2OMP算法与多种压缩感知算法的仿真比拟 PAGEREF _Toc357415661 h 244.3结论 PAGEREF _Toc357415662 h 26结束语 PAGEREF _Toc3574

11、15663 h 27致谢 PAGEREF _Toc357415664 h 28参考文献 PAGEREF _Toc357415665 h 29附录一 源程序清单 PAGEREF _Toc357415666 h 30附录二 英文文献翻译 PAGEREF _Toc357415667 h 37第一章 绪论1.1选题的背景及意义众所周知，传统的信号采样以奈奎斯特Nyquist采样定理为根底。为了不丧失信号的信息，精确重构信号，在获取信号时，采样频率要大于信号中最高频率的两倍。但是随着各种信号处理系统获取能力的不断增强，需要后期处理的数据量也快速增加，奈奎斯特定理的局限性给系统的处理能力提出了更高的要求，

12、同时也给相应的硬件设施的设计带来了极大的挑战。如何高效处理这些数据并且最大限度的节省存储空间及传输本钱已成为目前信息领域进一步向前开展的主要瓶颈之一。实际上，奈奎斯特采样定理是信号精确重构的充分条件而不是必要条件，奈奎斯特采样定理并不是唯一、最优的采样理论。因此研究如何突破以奈奎斯特采样定理为根底的信息的提取、处理、融合、存储、及传输是推动信息领域开展的关键。在2004年Donoho等人针对稀疏性信号，提出了压缩感知Compressive sensing,简称CS理论。在随后的几年间该理论迅速开展，为解决上述问题奠定了根底。与传统信号处理方式不同，压缩感知理论以空间变换为根底，随机观测矩阵作为

13、手段，优化求解作为恢复信号的方法。压缩感知理论在获取信号的同时对数据进行适当的压缩，其采样频率低于奈奎斯特采样频率，减少了采样数据，节省了存储空间，同时又包含了足够的信息量，能通过适宜的重建算法对特定的图像或者信号进行精确重构。它将传统的数据采集和压缩合二为一，并且不需要复杂的数据编码算法，非常适合于要求采用小型器件的实现场合。信号的稀疏重建与压缩感知理论有重大的实用价值和应用前景，已经成为信号领域中一个新的研究方向1。1.2本课题在国内外的开展现状1国外研究状况及开展趋势目前，CS理论与应用研究正在如火如荼地进行：在美国、欧洲等许多国家的知名大学如麻省理工学院、莱斯大学、斯坦福大学、杜克大学

14、等都成立了专门课题组对CS进行研究；2021年，贝尔实验室,Intel,Google等知名公司也开始组织研究CS；2021年,美国空军实验室和杜克大学联合召开了CS研讨会，美国国防先期研究方案署(DARPA)和国家地理空间情报局(NGA)等政府部门成员与数学、信号处理、微波遥感等领域的专家共同探讨了CS应用中的关键问题；第二次以?压缩感知和高维数据分析?为主题的研讨会也将在2021年的7月26至28日在杜克大学召开2。2国内研究状况及开展趋势在国内，一些高校和科研机构也开始跟踪CS的研究,如清华大学、中科院电子所、西安交通大学和西安电子科技大学等。自从2006年CS的提出，在IEEE的信号处理

15、汇刊、信号处理快报汇刊、信号处理杂志、信息论汇刊等国际知名期刊上开始涌现出上百篇关于CS理论与应用方面的文献。2021年，IEEE Journal of Selected Topics in Signal Processing专门出版了一期关于CS的专刊，促进了CS理论在各个领域应用成果的交流。2021年4月，第一本关于CS的专著?Compressed Sensing: Theory and Applications?出版，不仅系统的介绍了CS的概念，而且聚集了世界各国学者在CS理论和应用上的观点和成功范例。国家自然科学基金委也自2021年起资助了多项压缩感知方法的研究，涉及认知无线电、雷达成

16、像、信号稀疏表示、多媒体编码、人脸识别等领域。1.3 本论文的结构安排本文在对压缩感知理论以及现有的重构算法进行系统的研究之后，围绕正交匹配追踪重建算法展开研究来实现信号的重建，基于上述工作，本文内容分为四章，具体结构安排如下：第一章：绪论。首先介绍了压缩感知理论的研究背景及意义，然后介绍了国内外研究背景和现状，最后整理出全文内容的结构安排。第二章：压缩感知理论相关知识。首先介绍了压缩感知的框架，进而对信号的稀疏变换、观测矩阵的设计以及信号的重构三个主要方面的内容展开进一步详述，最后详细介绍了压缩感知理论在不同领域的应用及有待解决的几个问题。第三章：正交匹配追踪重建算法。这一章着重分析了正交匹

17、配追踪算法的原理、实现步骤和Matlab的语言实现。第四章：基于MATLAB的压缩感知图像重建仿真。首先介绍了OMP算法的思想以及算法步骤，然后再matlab上进行试验仿真，得出实验数据。最后将OMP算法与其他算法进行比拟研究做出总结分析。第二章 压缩感知理论相关知识2.1压缩感知理论框架传统的信号采集、编解码过程如图2.l所示。编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的2倍，使得硬件系

18、统面临着很大的采样速率的压力。此外在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。图2.1传统编解码理论的框图压缩感知理论对信号的采样、压缩编码发生在同一个步骤如下列图2.2所示，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源别离中的求逆思想下利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构。解码

19、所需测量值的数目远小于传统理论下的样本数。图2.2缩感知理论的编解码框图2.2压缩感知的根本理论及核心问题压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术3。或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集个样本这一步骤，直接获得压缩的信号的表示。CS理论利用到了许多自然信号在特定的基上具有紧凑的表示。即这些信号是“稀疏的或“可压缩的。由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。对于一个实值的有限长一维离散时间信号，可以看作为一个空间1的维的列

20、向量，元素为，,=1，2，。空间的任何信号都可以用1维的基向量的线性组合表示。为简化问题，假定这些基是标准正交的。把向量作为列向量形成的基矩阵=,，于是任意信号都可以表示为： (式2.1)其中是投影系数，=构成的1的列向量。显然，和是同一个信号的等价表示，是信号在时域的表示，那么是信号在域的表示。如果的非零个数比小很多，那么说明该信号是可压缩的。一般而言，可压缩信号是指可以用个大系数很好地逼近的信号，即它在某个正交基下展开的系数按一定量级呈现指数衰减，具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。在数据采样系统中，采样速率高但信号是可压缩的，采样得到点采样信号；通过变

21、换后计算出完整的变换系数集合；确定个大系数的位置，然后扔掉个小系数；对个大系数的值和位置进行编码，从而到达压缩的目的。由Candes、Romberg、Tao和Donoho等人在2004年提出的压缩感知理论说明，可以在不丧失逼近原信号所需信息的情况下，用最少的观测次数来采样信号，实现信号的降维处理，即直接对信号进行较少采样得到信号的压缩表示，且不经过进行次采样的中间阶段，从而在节约采样和传输本钱的情况下，到达了在采样的同时进行压缩的目的4。Candes证明了只要信号在某一个正交空间具有稀疏性，就能以较低的频率采样信号，而且可以以高概率重构该信号。即，设长度为的信号在某正交基或框架上的变换系数是稀

22、疏的，如果我们可以用一个与变换基不相关的观测基：对系数向量进行线性变换，并得到观测集合。那么就可以利用优化求解方法5从观测集合中精确或高概率地重构原始信号。图2.3是基于压缩感知理论的信号重构过程框图。可压缩信号稀疏变换观测得到的维向量重构信号满足图2.3 基于压缩感知理论的信号重构过程2.2.1 信号的稀疏表示压缩感知的第一步，即对于信号，如何找到某个正交基或紧框架，使其在上的表示是稀疏的，即信号的稀疏表示问题。所谓的稀疏，就是指信号在正交基下的变换系数向量为，假设对于和，这些系数满足： (式2.2)那么说明系数向量在某种意义下是稀疏的。如何找到信号最正确的稀疏域？这是压缩感知理论应用的根底

23、和前提，只有选择适宜的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究说明，满足具有幂次速度衰减的信号，可利用压缩感知理论得到恢复，并且重构误差满足： (式2.3)其中r=1/p1/2，0p1.文献6指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一个有待进一步研究的问题。Peyr

24、e把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理。用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。字典的选择应尽可能的符合被逼近信号的结构，其构成可以没有任何限制。从冗余字典中找到具有最正确线性组合的项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近。从非线性逼近角度来讲，信号的稀疏逼近包含两个层面：一是根据目标函数从一

25、个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最正确的K项组合。因此，目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1)如何构造一个适合某一类信号的冗余字典；(2)如何设计快速有效的稀疏分解算法。在构造冗余字典方面，文献7中提出使用局部Cosine基来刻画声音信号的局部频域特性；利用bandlet基来刻画图像中的几何边缘；还可以把其它的具有不同形状的基函数归入字典，如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet基等等。在稀疏分解算法的设计方面，基于贪婪迭代思想的MP(Matching Pursuit)算法表现出极大的优越性，但不是全局最优解。Donoho等人之后

26、提出了基追踪(basis pursuit，BP)算法。BP算法具有全局最优的优点，但计算复杂度极高。之后又出现了一系列同样基于贪婪迭代思想的改良算法，如正交匹配追踪算法(OMP)，分段匹配追踪(STOMP)算法等。2.2.2 信号的观测矩阵如何设计一个平稳的、与变换基不相关的维的观测矩阵，保证稀疏向量从维降到维时重要信息不遭破坏，是第二步要解决的问题，也就是信号低速采样问题。压缩感知理论中，通过变换得到信号的稀疏系数向量后，需要设计压缩采样系统的观测局部，它围绕观测矩阵展开。观测器的设计目的是如何采样得到个观测值，并保证从中能重构出长度为的信号或者基下等价的稀疏系数向量。显然，如果观测过程破坏

27、了中的信息，重构是不可能的。观测过程实际就是利用观测矩阵的个行向量对稀疏系数向量进行投影，即计算和各个观测向量之间的内积，得到个观测值，记观测向量，即 (式2.4)这里，采样过程是非自适应的，也就是说，无须根据信号而变化，观测的不再是信号的点采样而是信号的更一般的线性泛函。对于给定的从式(2.4)中求出是一个线性规划问题，但由于，即方程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。然而，如果具有-项稀疏性()，那么该问题有望求出确定解。此时，只要设法确定出中的个非零系数的适宜位置，由于观测向量是这些非零系数对应的个列向量的线性组合，从而可以形成一个的线性方程组来求解这些非零项的具

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

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

30、为进一步简化观测矩阵，在某些条件下，以随机为元素构成的Rademacher矩阵也可以证明具有RIP性质和普适性。对观测矩阵的研究是压缩感知理论的一个重要方面。Donoho给出了观测矩阵所必需具备的三个条件9，并指出大局部一致分布的随机矩阵都具备这三个条件，均可作为观测矩阵，如：局部Fourier集、局部Hadamard集、一致分布的随机投影(uniform Random Projection)集等，这与对RIP性质进行研究得出的结论相一致。但是，使用上述各种观测矩阵进行观测后，都仅仅能保证以很高的概率去恢复信号，而不能保证百分之百地精确重构信号。对于任何稳定的重构算法是否存在一个真实确实定性的

31、观测矩阵仍是一个有待研究的问题。2.2.3 信号重构如何设计快速重构算法，从线性观测中恢复信号，是第三步要将解决的问题，即信号的重构问题。在压缩感知理论中，由于观测数量远小于信号长度，因此不得不面对求解欠定方程组的问题。外表上看，求解欠定方程组似乎是无望的，但是，文献10和11均指出由于信号是稀疏的或可压缩的，这个前提从根本上改变了问题，使得问题可解，而观测矩阵具有RIP性质也为从个观测值中精确恢复信号提供了理论保证。为更清晰地描述压缩感知理论的信号重构问题，首先定义向量的范数为： (式2.5)当时得到范数，它实际上表示中非零项的个数。于是，在信号稀疏或可压缩的前提下，求解欠定方程组的问题转化

32、为最小范数问题： s.t. (式2.6)但是，它需要列出中所有非零项位置的种可能的线性组合，才能得到最优解。因此，求解式2.6)的数值计算极不稳定而且是NP难问题。注意，这和稀疏分解问题从数学意义上讲是同样的问题。于是稀疏分解的已有算法可以应用到CS重构中。Chen，Donoho和Saunders指出，求解一个更加简单的优化问题会产生同等的解(要求和不相关)： s.t. (式2.7)稍微的差异使得问题变成了一个凸优化问题，于是可以方便地化简为线性规划问题，典型算法代表：BP算法尽管BP算法可行，但在实际应用中存在两个问题：第一，即使是常见的图像尺寸，BP算法的计算复杂度也难以忍受，在采样点个数

33、满足，时，重构计算复杂度的量级在；第二，由于范数无法区分稀疏系数尺度的位置，所以尽管整体上重构信号在欧氏距离上逼近原信号，但存在低尺度能量搬移到了高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。基于上述问题，2005年1月Candes和Romberg提出了不同的信号恢复方法，该方法要求对原信号具有少量的先验知识，同时也可以对所求结果施加适当的期望特性，以约束重构信号的特性。通过在凸集上交替投影的方法，可以快速求解线性规划问题。Tropp和Gilbert提出利用匹配追踪(MP)和正交匹配追踪(OMP)算法来求解优化问题重构信号，大大提高了计算的速度，且易于实现。树形匹配追踪(

34、TMP)算法是2005年La和NDo提出的。该方法针对BP、MP和OMP方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系，是将稀疏系数的树型结构加以利用，进一步提升了重构信号的精度和求解的速度。匹配追踪类算法都是基于贪婪迭代算法，以多于BP算法需要的采样数目换取计算复杂度的降低。例如OMP算法，需要，个采样点数才能以较高的概率恢复信号，信号重构的计算复杂度为。2006年Donoho等人提出了分段正交匹配追踪(STOMP，Stagewise OMP)算法。它将OMP进行一定程度的简化，以逼近精度为代价进一步提高了计算速度(计算复杂度为O(N)，更加适合于求解大规模问题。匹配追踪类方法为其

35、近似求解提供了有力工具，且该类方法用于稀疏信号重建时具有一定的稳定性。文献12中提出的OMP算法延续了匹配追踪算法中原子的选择准那么，但是实现了递归地对已选原子集合进行正交化以保证迭代的最优性，从而减少了迭代次数。此后，Needell和Vershynin等人在OMP算法的根底上将正那么化过程用于稀疏度的OMP算法中，提出了ROMP算法。ROMP算法与OMP算法的不同之处在于，该算法首先根据相关原子挑选多个原子作为候选集，然后从候选集中按照正那么化原那么挑选出局部原子，最后将其并入最终的支撑集，从而实现了原子的快速、有效选择。最近出现的子空间匹配追踪算法(Subspace Pursuit，SP)

36、和压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit，CoSaMP)引入了回退筛选的思想，这些算法的重建质量与线性规划方法相当，同时重建复杂度低，但是这些算法都是建立在稀疏度的根底上。然而实际应用中信号的稀疏度往往是未知的，由此出现了对稀疏度自适应的稀疏自适应匹配追踪算法(Sparsity Adaptive Matching Pursuit,SAMP)，它通过设置一个可变步长，逐步对信号稀疏度进行估计，因此可以在K未知的情况下获得较好的重建效果，速度也远快于OMP算法。基于ROMP算法和SAMP算法的突出优势。2.3.压缩感知的应用这里主要介绍CS

37、理论在成像系统、图像融合、图像跟踪以及数据获取等方面的应用。1成像系统在成像方面，CS理论的出现激起了人们研究新型传感器的热情，CS采样对昂贵的成像器件的设计产生了重大影响。在地震勘探和核磁共振成像中，对于目标信号，将有望采用少量的随机观测次数就能获得高精度重构，取代传统数码相机拍照时采集大量像素的一种新型单像素CS相机已经得到论证。相对于CS的理论研究进展，美国Rice大学也已经研制出单像素相机，如下列图2.4所示。该相机具有一种全新的相机结构，使用数字微镜阵列完成图像在伪随机二值模型上线性投影的光学计算。它可利用单一的信号光子检测器采样得到比图像像素点数少得多的点恢复图像，并具有对图像波长

38、自适应的能力，这种自适应能力是传统的CCD和CMOS成像器件所不具备的。ARI-ZONA大学Baheti和Neifeld设计了具有特定功能的结构成像设备，DUCK大学研制了单景光谱成像装置。然而由于压缩重构算法的计算量比拟大，难以到达实时性要求，因此实时高性能压缩感知成像系统是未来重要的研究方向。图2.4单像素相机2图像融合图像融合是信息融合范畴内以图像为对象的研究领域。图像融合将多个成像传感器或同一成像传感器在不同模式下获取的同一场景的图像信息加以综合，获取更为精确、全面、可靠的图像描述。图像融合技术在自动目标识别、计算机视觉、遥感、机器人、自动小车、复杂智能制造系统、医学图像处理以及军事应

39、用等领域有着广泛的应用潜力13。将不同模式下的融合图像采用CS理论进行稀疏表示，如下列图2.5所示。使其在测量举证的作用下，用远小于原图像的数据量进行计算得到融合结果复原为图像表示，可节省中间融合所需的计算量，并且能够更好地利用原图像中像素间的内在联系，是一个非常值得研究的课题。图2.5 CS用于图像融合的流程框图3目标跟踪视频目标跟踪是使用可见、红外等被动式成像传感器实现目标测量的核心技术之一，是目标识别、视频图像的压缩编码等高层次的视频处理和应用理解的根底，也是视频监控技术自动化和实时应用的关键。目标跟踪的实质是通过对图像传感器拍摄到的视频序列进行分析，计算出目标在每帧图像中的位置、大小和

40、运动速度。CS理论自从被D.Donoho美国科学学院院士E.Candes(Ridgelet.Curvelet创始人)及T.Tao(华裔科学家，2006年菲尔茨获奖得主，2021年被评为世界上最聪明的科学家)等人提出后，在信息论、信号/图像处理、医疗成像、模式识别、地质勘探、光学/雷达成像、无线通信等领域受到高度关注，并被美国科技评论为2007年度10大科技进展之一14。基于CS理论的目标跟踪。首先对目标进行建模，而后对后续帧图像进行相应的模型建立，将求取两模型最相似的问题转化为求取某相似参数的L1范数最小化问题，对高维数据的特征信息处理有明显优势，但是计算量大，复杂度高，是否对所有目标都具有鲁

41、棒的跟踪效果有待于在目标跟踪方面做进一步研究。4数据获取在某些重要的情况下，完全采集模拟信号的N个离散时间样本是困难的，而且也难以对其进行压缩。而运用压缩感知，可以设计物理采样装置，直接记录模拟信号离散、低码率、不相关的测量值，有效地进行数据获取。基于RIP理论，目前已研制出了一些设备，有莱斯大学研制的单像素相机和A/I转换器，麻省理工学院研制的编码孔径相机，耶鲁大学研制的超谱成像仪，麻省理工学院研制的MRI RF脉冲设备，伊利诺伊州立大学研制的DNA微阵列传感器。2.4 压缩感知有待研究的几个问题压缩感知经过近年来的迅猛开展，已根本形成了自己的理论框架，包括根底理论、实现方法和实际应用。但是

42、，压缩感知理论还有很多亟待解决的问题，为此本文列出了压缩感知有待解决的几个关键问题。根底理论层面：1基于非正交稀疏字典的压缩感知信号重建理论。在等距约束性准那么驱动的可压缩信号压缩感知定理中，关于稀疏字典和测量矩阵仅要求两者乘积满足RIP。但是，测量矩阵设计局部关于压缩测量个数M的界定还额外附加了假设条件，即稀疏字典是正交基。当测量矩阵依然通过三种方式生成，但是稀疏字典不再正交时，是否满足RIP？压缩测量个数M的下限是否不变？由于过完备的稀疏字典才能保证表示系数具有足够的稀疏性或衰减性，进而能够在减少压缩测量的同时保证压缩感知的重建精度，所以需要设计鲁棒的测量矩阵使之与过完备稀疏字典依然满足R

43、IP，同时需要重新估计压缩测量个数M的下限，这时所需的压缩测量定会减少。2自然图像的自适应压缩感知信号重建理论。虽然基于线性投影的压缩感知理论能够直接应用于自然图像这样的复杂高维信号，但是由于没有考虑到自然图像的固有特性，诸如结构多成分性、高阶统计性等,对于自然图像压缩采样本身没有特殊的指导作用。事实上，相对于一维离散信号,自然图像的复杂性和高维性使之需要自适应的压缩采样和重建算法。例如，基于图像多成分性的特点能够提高重建图像的峰值信噪比和视觉效果。压缩感知理论的大局部文献中，测量矩阵都是线性的且设计好的，不需根据观测信号自适应地变化。对于自然图像，假设能够实现非线性自适应的压缩测量，压缩感知

44、的压缩性能势必会获得大幅度的提高。目前，自然图像的自适应压缩感知信号重建理论根本空白。这项工作对压缩感知的理论推广和实际应用都具有重要意义。实现方法层面：1基于学习的自然图像过完备字典设计。目前，基于构造方法的自然图像过完备字典设计具有很好的理论支撑，正那么化几何方法、几何多尺度分析、基于信息论的“有效编码假设为其奠定了坚实广阔的理论根底。但是，从国际上关于过完备字典设计的整体情况看，基于学习的自然图像过完备字典设计的工作非常少，主要在于：设计难度大、性能要求高，同时缺乏严格的理论支撑。这项工作对于稀疏字典和压缩感知都将是重要的理论完善。(2)硬件易实现确实定性测量矩阵设计。在等距约束性准那么

45、驱动的可压缩信号压缩感知定理中，要求稀疏字典和测量矩阵的乘积=满足RIP。其中，稀疏字典可以是正交的也可以是非正交的，测量矩阵可以是随机的也可以是确定的。但是，面向应用且硬件易实现的测量矩阵应该具有以下根本特点：满足等距约束性、压缩测量个数少、采样计算本钱低、存储矩阵的空间小、以及测量矩阵最好是确定性的。设计出硬件容易实现的测量矩阵和快速稳定的重建算法是将压缩感知理论推向实用的关键。3噪声情形大尺度问题的快速鲁棒重建算法15设计。快速稳定的信号重建算法是将压缩感知理论推向实用的关键技术之一，特别适用于纠错编码、核磁共振成像、NMR波谱研究等大尺度问题。通常，基于最小化松弛算法的计算复杂度相对较

46、高。因而，在最小化驱动的压缩感知理论完善工作的根底上，希望能够基于稀疏性自适应的贪婪迭代和基于多层超先验建模的非凸迭代思想设计适于噪声情形大尺度问题的快速鲁棒重建算法。第三章 正交匹配追踪重建算法3.1最小L0范数模型从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数量少于待解的未知数)的最简单解的问题，L0范数刻画的就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏。通常我们采用下式描述最小L0范数最优化问题： s.t. (式3.1)实际中，允许一定程度的误差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中是一个极小的常量： s.t. (式3.2)但

47、是这类问题的求解数值计算极不稳定，很难直接求解。匹配追踪类稀疏重建算法解决的是最小L0范数问题，最早提出的有匹配追踪(MP)算法和正交匹配追踪(OMP)算法。3.2匹配追踪算法匹配追踪算法的根本思想是在每一次的迭代过程中，从过完备原子库里(即感知矩阵)选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是由于信号在已选定原子(感知矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。匹配追踪类算法通过求余量r与感知矩阵中各个原子之间内积的绝对值，

48、来计算相关系数u： 式3.3并采用最小二乘法进行信号逼近以及余量更新: 式3.4 式3.53.3正交匹配追踪算法(OMP)正交匹配追踪算法Orthogonal Matching Pursuit,OMP，是最早的贪婪迭代算法之一，是压缩感知信号检测的一种算法。本文后面的仿真就是采用基于压缩感知的正交匹配追踪算法来重建图像的。本节将着重介绍此算法的原理、实现步骤以及Matlab的语言实现。3.3.1 OMP算法原理OMP算法实质上还是沿用了匹配追踪算法中的原子选择准那么，只是将所选原子利用Gram-Schmidt正交化方法进行正交处理，再将信号在这些正交原子构成的空间上投影，得到信号在各个已选原子

49、上的分量和余量，然后用相同方法分解余量。在每一步分解中，所选原子均满足一定条件，因此余量随着分解过程迅速减小。通过递归地对已选择原子集合进行正交化保证了迭代的最优性，从而有效克服了匹配追踪算法为获得较好的收敛效果往往需要经过较多的迭代次数的问题。OMP的重建算法是在给定迭代次数的条件下重建，这种强制迭代过程停止的方法使得OMP需要非常多的线性测量来保证精确重建。总之，它以贪婪迭代的方法选择的列，使得在每次迭代中所选择的列与当前的冗余向量最大程度地相关，从测量向量中减去相关局部并反复迭代，直到迭代次数到达稀疏度，强制迭代停止。3.3.2 OMP算法实现步骤OMP算法的具体步骤如下：(1)初始余量

50、，迭代次数，索引值集合，；(2)计算相关系数u,并将u中最大值对应的索引值存入中；(3)更新支撑集，其中；(4)应用(式3.4)得到，同时用(式3.5)对余量进行更新；(5)假设，令，转步骤(2)；否那么，停止迭代。3.3.3 OMP算法的Matlab语言实现因为OMP算法只能对稀疏信号进行精确重构，所以为了实现对OMP的仿真，首先需要将图片转换为稀疏信号，如FFT、DCT、小波变换等，在本文中采取小波变换，然后将得到的稀疏信号与测量矩阵相乘得到测量值Y，然后通过OMP算法，根据Y精确重建出原始信号最后经过小波反变换得到原始图像。由于在Matlab平台上对图像的处理、小波变换、矩阵的求逆合并等

51、运算的实现较为方便，因此本文首先选择在Matlab上实现OMP算法并对其进行仿真。具体流程图如图3.1所示开始：读入图片文件x获取图片的大小a*b对图片进行小波变换得到稀疏信号x1产生随机测量矩阵，并与x1相乘得到测量值Y对Y按列处理i=1i=K*log(N/K),至少40,但有出错的概率)f1=50; % 信号频率1f2=100; % 信号频率2f3=200; % 信号频率3f4=400; % 信号频率4fs=800; % 采样频率ts=1/fs; % 采样间隔Ts=1:N; % 采样序列x=0.3*sin(2*pi*f1*Ts*ts)+0.6*sin(2*pi*f2*Ts*ts)+0.1*

52、sin(2*pi*f3*Ts*ts)+0.9*sin(2*pi*f4*Ts*ts); % 完整信号plot(x,r) % 原始信号程序2：一维重建信号的生成clc;clear% 1. 时域测试信号生成K=7; % 稀疏度(做FFT可以看出来)N=256; % 信号长度M=64; % 测量数(M=K*log(N/K),至少40,但有出错的概率)f1=50; % 信号频率1f2=100; % 信号频率2f3=200; % 信号频率3f4=400; % 信号频率4fs=800; % 采样频率ts=1/fs; % 采样间隔Ts=1:N; % 采样序列x=0.3*sin(2*pi*f1*Ts*ts)+0

53、.6*sin(2*pi*f2*Ts*ts)+0.1*sin(2*pi*f3*Ts*ts)+0.9*sin(2*pi*f4*Ts*ts); % 完整信号% 2. 时域信号压缩传感Phi=randn(M,N); % 测量矩阵(高斯分布白噪声)s=Phi*x.; % 获得线性测量 % 3. 正交匹配追踪法重构信号(本质上是1-范数最优化问题)m=2*K; % 算法迭代次数(m=K)Psi=fft(eye(N,N)/sqrt(N); % 傅里叶正变换矩阵T=Phi*Psi; % 恢复矩阵(测量矩阵*正交反变换矩阵)hat_y=zeros(1,N); % 待重构的谱域(变换域)向量 Aug_t=; %

54、增量矩阵(初始值为空矩阵)r_n=s; % 残差值for times=1:m; % 迭代次数(有噪声的情况下,该迭代次数为K) for col=1:N; % 恢复矩阵的所有列向量 product(col)=abs(T(:,col)*r_n); % 恢复矩阵的列向量和残差的投影系数(内积值) end val,pos=max(product); % 最大投影系数对应的位置 Aug_t=Aug_t,T(:,pos); % 矩阵扩充 T(:,pos)=zeros(M,1); % 选中的列置零实质上应该去掉，为了简单我把它置零 aug_y=(Aug_t*Aug_t)(-1)*Aug_t*s; % 最小二

55、乘,使残差最小 r_n=s-Aug_t*aug_y; % 残差 pos_array(times)=pos; % 纪录最大投影系数的位置endhat_y(pos_array)=aug_y; % 重构的谱域向量hat_x=real(Psi*hat_y.); % 做逆傅里叶变换重构得到时域信号% 4.恢复信号和原始信号比照figure(1)hold on;plot(hat_x,k.-) % 重建信号plot(x,r) % 原始信号legend(Recovery,Original)norm(hat_x.-x)/norm(x) % 重构误差程序3：二维图像OMP重建function Wavelet_OM

56、Pclc;clearX=imread(lena256.bmp); % 读文件X=double(X);a,b=size(X);ww=DWT(a); % 小波变换矩阵生成X1=ww*sparse(X)*ww; % 小波变换让图像稀疏化注意该步骤会消耗时间，但是会增大稀疏度X1=full(X1);M=190; % 随机矩阵生成R=randn(M,a);Y=R*X1; % 测量% OMP算法X2=zeros(a,b); % 恢复矩阵for i=1:b % 列循环 rec=omp(Y(:,i),R,a); X2(:,i)=rec;endfigure(1); % 原始图像imshow(uint8(X);t

57、itle(原始图像);figure(2); % 变换图像imshow(uint8(X1);title(小波变换后的图像);figure(3); % 压缩传感恢复的图像X3=ww*sparse(X2)*ww; % 小波反变换X3=full(X3);imshow(uint8(X3);title(恢复的图像);% 误差(PSNR)errorx=sum(sum(abs(X3-X).2); % MSE误差psnr=10*log10(255*255/(errorx/a/b) % PSNR% OMP的函数% s-测量；T-观测矩阵；N-向量大小function hat_y=omp(s,T,N)Size=si

58、ze(T); % 观测矩阵大小M=Size(1); % 测量hat_y=zeros(1,N); % 待重构的谱域(变换域)向量Aug_t=; % 增量矩阵(初始值为空矩阵)r_n=s; % 残差值for times=1:M/4; % 迭代次数(稀疏度是测量的1/4) for col=1:N; % 恢复矩阵的所有列向量 product(col)=abs(T(:,col)*r_n); % 恢复矩阵的列向量和残差的投影系数(内积值) end val,pos=max(product); % 最大投影系数对应的位置 Aug_t=Aug_t,T(:,pos); % 矩阵扩充 T(:,pos)=zeros(

59、M,1); % 选中的列置零实质上应该去掉，为了简单我把它置零 aug_y=(Aug_t*Aug_t)(-1)*Aug_t*s; % 最小二乘,使残差最小 r_n=s-Aug_t*aug_y; % 残差 pos_array(times)=pos; % 纪录最大投影系数的位置 if (norm(r_n)9) % 残差足够小 break; endendhat_y(pos_array)=aug_y; % 重构的向量程序4：BP、OMP、STOMP_FDR重建图像x=imread(lena.bmp); %读文件m,n=size(x);xrec_BP=size(x);xrec_OMP=size(x);x

60、rec_FDR=size(x);t_BP=0;t_OMP=0;t_FDR=0;for i=1:m x1=x(i,:); cA,cD=dwt(x1,db1); % 小波变换 c1=length(cD) Mdetail=c1; Ndetail=floor(c1*0.4);A=randn(Ndetail,Mdetail); % 随机矩阵生成y=A*cD;q=0.5;S=10;tic;alpha=SolveBP(A,y,Mdetail); % BP算法处理图像t_BP=t_BP+toc;rec1=idwt(cA,alpha,db1);xrec_BP(i,1:n)=rec1;tic;alpha,iter