基于压缩感知的正交匹配算法图像重建设计

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

2、利用数学算法完成对信号的精确重构，该过程可看为求解一个优化问题。本文介绍了主要介绍了压缩感知原理和目前最为成熟的压缩感知重建算法一一正交匹配追踪算法，通过MATLAB平台设计实现了基本的正交匹配追踪算法，对一维、二维信号进行了重建仿真。关键词：压缩感知；稀疏变换；正交匹配；图像重建BasedOnCompressedSensingOfOrthogonalMatchingAlgorithmImageRecoveryAbstract:CompressedsensingisanovelsamplingtheorywhichisproposedbyDonohoandCandes.Thistheoryis

3、undertheconditionthatthesignaliscompressibleorsparse.Inthiscase,usingfarlessthantherequiredsamplingfrequencyoftheNyquisttheorytosamplethesignalisabletoaccuratelyreconstructthesignal.CompressedtheorybreaksthoughthetraditionalNyquistsamplingtheory,whichovercomesalotofproblemssuchasagreatnumberofsampli

4、ngdata,timewasting,datastoragespacewastingandsoon.Asaresult,itreducessignalprocessingcostanddevicecost.Thecompressedtheoryhasthreekeysides:(1)Sparsetransformation,foranon-sparsesignal,weneedtofindaproperorthogonalbasisonwhichthesignalhasasparserepresentation;(2)Observationmatrix,itisirrelevantwithth

5、eorthogonalbasis;(3)reconstructionalgorithms,usingareconstructionalgorithmtoensuretheaccuracyofthesignalreconstruction,thewholeprocesscanbeconsideredasthesolvetoaoptimizationproblem.ThispaperintroducesCSandmostmaturecompressionperceptionalgorithmatpresent-Orthogonalmatchingalgorithm.ThroughtheMATLAB

6、designrealizebasicorthogonalmatchingalgorithms,ThroughtheMATLABdesignrealizebasicorthogonalmatchingalgorithmofone-dimensional,two-dimensionalsignalprocessingsimulation.Keywords：Compressedsensing;Sparsetransform;Orthogonalmatching;Imagerecovery.第一章绪论21.1 选题的背景及意义21.2 本课题在国内外的发展现状21.3 本论文的结构安排3第二章压缩感知

7、理论相关知识42.1 压缩感知理论框架42.2 压缩感知的基本理论及核心问题52.2.1 信号的稀疏表示62.2.2 信号的观测矩阵82.2.3 信号重构92.3 .压缩感知的应用112.4 压缩感知有待研究的几个问题13第三章正交匹配追踪重建算法163.1 最小L0范数模型163.2 匹配追踪算法163.3 正交匹配追踪算法(OMP)173.3.1 OMP算法原理173.3.2 OMP算法实现步骤173.3.3 OMP算法的Matlab语言实现17第四章基于MATLAB的压缩感知图像重建仿真204.1 不同采样率下白仿真结果204.1.1 一维信号在不同采样率下的OMP仿真204.1.2 二

8、维信号在不同采样率下的OMP仿真224.2 (OMP)算法与多种压缩感知算法的仿真比较244.3 结论26结束语27致谢28参考文献29附录一源程序清单30附录二英文文献翻译37第一章绪论1.1 选题的背景及意义众所周知，传统的信号采样以奈奎斯特（Nyquist）采样定理为基础。为了不丢失信号的信息，精确重构信号，在获取信号时，采样频率要大于信号中最高频率的两倍。但是随着各种信号处理系统获取能力的不断增强，需要后期处理的数据量也快速增加，奈奎斯特定理的局限性给系统的处理能力提出了更高的要求，同时也给相应的硬件设施的设计带来了极大的挑战。如何高效处理这些数据并且最大限度的节省存储空间及传输成本已

9、成为目前信息领域进一步向前发展的主要瓶颈之一。实际上，奈奎斯特采样定理是信号精确重构的充分条件而不是必要条件，奈奎斯特采样定理并不是唯一、最优的采样理论。因此研究如何突破以奈奎斯特采样定理为基础的信息的提取、处理、融合、存储、及传输是推动信息领域发展的关键。在2004年Donoho等人针对稀疏性信号，提出了压缩感知（Compressivesensing,简称CS）理论。在随后的几年间该理论迅速发展，为解决上述问题奠定了基础。与传统信号处理方式不同，压缩感知理论以空间变换为基础，随机观测矩阵作为手段，优化求解作为恢复信号的方法。压缩感知理论在获取信号的同时对数据进行适当的压缩，具采样频率低于奈奎

10、斯特采样频率，减少了采样数据，节省了存储空间，同时又包含了足够的信息量，能通过合适的重建算法对特定的图像或者信号进行精确重构。它将传统的数据采集和压缩合二为一，并且不需要复杂的数据编码算法，非常适合于要求采用小型器件的实现场合。信号的稀疏重建与压缩感知理论有重大的实用价值和应用前景，已经成为信号领域中一个新的研究方向1。1.2 本课题在国内外的发展现状1 .国外研究状况及发展趋势目前，CS理论与应用研究正在如火如荼地进行：在美国、欧洲等许多国家的知名大学如麻省理工学院、莱斯大学、斯坦福大学、杜克大学等都成立了专门课题组对CS进行研究；2008年，贝尔实验室，Intel,Google等知名公司也

11、开始组织研究CS;2009年，美国空军实验室和杜克大学联合召开了CS研讨会，美国国防先期研究计划署（DARPA）和国家地理空间情报局（NGA）等政府部门成员与数学、信号处理、微波遥感等领域的专家共同探讨了CS应用中的关键问题；第二次以压缩感知和高维数据分析为主题的研讨会也将在2011年的7月26至28日在杜克大学召开22 .国内研究状况及发展趋势在国内，一些高校和科研机构也开始跟踪CS的研究，如清华大学、中科院电子所、西安交通大学和西安电子科技大学等。自从2006年CS的提出，在IEEE的信号处理汇刊、信号处理快报汇刊、信号处理杂志、信息论汇刊等国际知名期刊上开始涌现出上百篇关于CS理论与应用

12、方面的文献。2010年，IEEEJournalofSelectedTopicsinSignalProcessing专门出版了一期关于CS的专刊，促进了CS理论在各个领域应用成果的交流。2011年4月，第一本关于CS的专著«CompressedSensing:TheoryandApplications»出版，不仅系统的介绍了CS的概念，而且汇集了世界各国学者在CS理论和应用上的观点和成功范例。国家自然科学基金委也自2009年起资助了多项压缩感知方法的研究，涉及认知无线电、雷达成像、信号稀疏表示、多媒体编码、人脸识别等领域。3 .3本论文的结构安排本文在对压缩感知理论以及现有的

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

14、首先介绍了OMP算法的思想以及算法步骤，然后再matlab上进行试验仿真，得出实验数据。最后将OMP算法与其他算法进行比较研究做出总结分析。第二章压缩感知理论相关知识2.1压缩感知理论框架传统的信号采集、编解码过程如图2.1所示。编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的2倍，使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中,大量变换计算得到的小系数被丢弃，造成了数据计算和内

15、存资源的浪费。信号采杼丫变换、压缩解码一*恢复信号X解接收数据1般*解压缩i反变换x而Y图2.1传统编解码理论的框图压缩感知理论对信号的采样、压缩编码发生在同一个步骤如下图2.2所示，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构。解码所需测量值的数目远小于传统理论

16、下的样本数。公稀疏信号编y码-*版测量编码-Y解接收数据码7晒1解码重构愎复信号*X图2.2缩感知理论的编解码框图2.2压缩感知的基本理论及核心问题压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术30或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示。CS理论利用到了许多自然信号在特定的基上具有紧凑的表示。即这些信号是“稀疏”的或“可压缩”的。由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。对于一个实值的有限

17、长一维离散时间信号X,可以看作为一个RN空间NX1的维的列向量，元素为n,n,=1,2,N。RN空间的任何信号都可以用NX1维的基向量i二的线性组合表示。为简化问题，假定这些基是规范正交的。把向量Ni作为列向量形成NN的基矩阵=1,2,?,n,于是任意信号X都可以表示为：X(式2.1)其中是投影系数，=i(X,)构成的NX1的列向量。显然，X和是同一个信号的等价表示，X是信号在时域的表示，则是信号在域的表示。如果的非零个数比N小很多，则表明该信号是可压缩的。一般而言，可压缩信号是指可以用K个大系数很好地逼近的信号，即它在某个正交基下展开的系数按一定量级呈现指数衰减，具有非常少的大系数和许多小系

18、数。这种通过变换实现压缩的方法称为变换编码。在数据采样系统中，采样速率高但信号是可压缩的，采样得到N点采样信号X;通过TX变换后计算出完整的变换系数集合1;确定K个大系数的位置，然后扔掉NK个小系数；对K个大系数的值和位置进行编码，从而达到压缩的目的。由Candes、Romberg、Tao和Donoho等人在2004年提出的压缩感知理论表明，可以在不丢失逼近原信号所需信息的情况下，用最少的观测次数来采样信号，实现信号的降维处理，即直接对信号进行较少采样得到信号的压缩表示，且不经过进行N次采样的中间阶段，从而在节约采样和传输成本的情况下，达到了在采样的同时进行压缩的目的4。Candes证明了只要

19、信号在某一个正交空间具有稀疏性，就能以较低的频率MN采样信号，而且可以以高概率重构该信号。即，设长度为N的信号X在某正交基或框架上的变换系数是稀疏的，如果我们可以用一个与变换基不相关的观测基：MNMN对系数向量进行线性变换，并得到观测集合Y:M1。那么就可以利用优化求解方法从观测集合中精确或高概率地重构原始信号X。图2.3是基于压缩感知理论的信号重构过程框图。图2.3基于压缩感知理论的信号重构过程2.2.1信号的稀疏表示压缩感知的第一步，即对于信号XRN,如何找到某个正交基或紧框架，使其在上的表示是稀疏的，即信号的稀疏表示问题。所谓的稀疏，就是指信号X在正交基下的变换系数向量为TX,假如对于0

20、p2和R0,这些系数满足：1/PIIIpIR（式2.2）i则说明系数向量在某种意义下是稀疏的。如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幕次速度衰减的信号，可利用压缩感知理论得到恢复，并且重构误差满足：E望X之Cr（K/logN）6r（式2.3）其中r=1/p-1/2,0<p<1.文献6指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具

21、有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一个有待进一步研究的问题。Peyre把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理。用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。字典的选择应尽可能的符合被逼近信号的

22、结构，其构成可以没有任何限制。从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近。从非线性逼近角度来讲，信号的稀疏逼近包含两个层面：一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最佳的K项组合。因此，目前信号在冗余字典下的稀疏表示的研究集中在两个方面：（1）如何构造一个适合某一类信号的冗余字典；（2）如何设计快速有效的稀疏分解算法。在构造冗余字典方面，文献7中提出使用局部Cosine基来刻画声音信号的局部频域特性；利用bandlet基来刻画图像中的几何边缘；还可以把其它的具有不同形状的基函数归入字典，如适合刻画纹理的Gab

23、or基、适合刻画轮廓的Curvelet基等等。在稀疏分解算法的设计方面，基于贪婪迭代思想的MP（MatchingPursuit）算法表现出极大的优越性，但不是全局最优解Donoho等人之后提出了基追踪（basispursuit,BP）算法。BP算法具有全局最优的优点，但计算复杂度极高。之后又出现了一系列同样基于贪婪迭代思想的改进算法，如正交匹配追踪算法（OMP）,分段匹配追踪（STOMP）算法等。2.2.2信号的观测矩阵如何设计一个平稳的、与变换基不相关的MN维的观测矩阵，保证稀疏向量从N维降到M维时重要信息不遭破坏，是第二步要解决的问题，也就是信号低速采样问题。压缩感知理论中，通过变换得到信

24、号的稀疏系数向量TX后，需要设计压缩采样系统的观测部分，它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然，如果观测过程破坏了X中的信息，重构是不可能的。观测过程实际M就是利用MN观测矩阵的M个行向量j对稀疏系数向量进行投影，即计算jj1M和各个观测向量j之间的内积，得到M个观测值jj1yj,jj1,2，M,记观测向量Y（yL，Ym）,即YTXACSX（式2.4）这里，采样过程是非自适应的，也就是说，无须根据信号X而变化，观测的不再是信号的点采样而是信号的更一般的K线性泛函。对于给定的Y从式（2.4）中求出是一个线性

25、规划问题，但由于MN,即方程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。然而，如果具有K-项稀疏性（KM）,则该问题有望求出确定解。此时，只要设法确定出中的K个非零系数i的合适位置，由于观测向量Y是这些非零系数i对应的K个列向量的线性组合，从而可以形成一个MK的线性方程组来求解这些非零项的具体值。_12对此，1kM21k即有限等距性质（RIP）给出了存在确定解的充要条件。f2这个充要条件和Candes、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即，要想使信号完全重构，必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵

26、中抽取的每M个列向量构成的矩阵是非奇异的。从中可以看出，问题的关键是如何确定非零系数的位置来构造出一个可解的MK线性方程组。然而，判断给定的ACS是否具有RIP性质是一个组合复杂度问题。为了降低问题的复杂度，能否找到一种易于实现RIP条件的替代方法成为构造观测矩阵的关键。文献8指出如果保证观测矩阵和稀疏基不相干，则ACS在很大概率上满足RIP性质。不相干是指向量j不能用稀疏表示。不相干性越强，互相表示时所需的系数越多；反之，相关性则越强。通过选择高斯随机矩阵作为观测矩阵即可高概率保证不相干性和RIP性质。例如，可以生成多个零均值、方差为1/N的随机高斯函数，将它们作为观测矩阵的元素j,使彳4A

27、CS以很高的概率具有RIP性质。随机高斯矩阵具有一个有用的性质：对于一个MN的随机高斯矩阵，可以证明当McKlog(N/K)时TACS在很大概率下具有RIP性质(其中c是一个很小的常数)。因此可以从M个观测值Y(y1,y2，yM)中以很高的概率去恢复长度为N的K-项稀疏信号。总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关，这一特性决定了选它作为观测矩阵，其它正交基作为稀疏变换基时，ACS满足RIP性质。为进一步简化观测矩阵,在某些条件下，以随机1为元素构成的Rademacher矩阵也可以证明具有RIP性质和普适性。对观测矩阵的研究是压缩感知理论的一个重要方面。Donoho给出了观测矩阵所

28、必需具备的三个条件9,并指出大部分一致分布的随机矩阵都具备这三个条件，均可作为观测矩阵，如：部分Fourier集、部分Hadamard集、一致分布的随机投影(uniformRandomProjection)集等，这与对RIP性质进行研究得出的结论相一致。但是，使用上述各种观测矩阵进行观测后，都仅仅能保证以很高的概率去恢复信号，而不能保证百分之百地精确重构信号。对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。2.2.3信号重构如何设计快速重构算法，从线性观测YACSX中恢复信号，是第三步要将解决的问题，即信号的重构问题。在压缩感知理论中，由于观测数量M远小于信号长

29、度N,因此不得不面对求解欠定方程组YACSX的问题。表面上看，求解欠定方程组似乎是无望的，但是，文献10和11均指出由于信号X是稀疏的或可压缩的，这个前提从根本上改变了问题，使得问题可解，而观测矩阵具有RIP性质也为从M个观测值中精确恢复信号提供了理论保证。为更清晰地描述压缩感知理论的信号重构问题，首先定义向量XXi,X2,Xn的P范数为：NP1/PIXIIp为（式2.5）当p0时得到0范数，它实际上表示X中非零项的个数。于是，在信号X稀疏或可压缩的前提下，求解欠定方程组YACSX的问题转化为最小0范数问题：minTX°s.t.ACSXTXY（式2.6）但是，它需要列出M中所有非零项

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

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

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

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

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

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

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

37、制造系统、医学图像处理以及军事应用等领域有着广泛的应用潜力130将不同模式下的融合图像采用CS理论进行稀疏表示，如下图2.5所示。使其在测量举证的作用下，用远小于原图像的数据量进行计算得到融合结果还原为图像表示，可节省中间融合所需的计算量，并且能够更好地利用原图像中像素间的内在联系，是一个非常值得研究的课题。一如H稀蟒防孙时史髅器篇普卜1牌台即3n冏M袅示、国使嚣嚣黑雷#:_li，',一；!,t_=."ip;Ir-TTrt-»il?rris-wiiirri.-m-irrTinmiuwt!图2.5CS用于图像融合的流程框图(3)目标跟踪视频目标跟踪是使用可见、红外等被

38、动式成像传感器实现目标测量的核心技术之一，是目标识别、视频图像的压缩编码等高层次的视频处理和应用理解的基础，也是视频监控技术自动化和实时应用的关键。目标跟踪的实质是通过对图像传感器拍摄到的视频序列进行分析，计算出目标在每帧图像中的位置、大小和运动速度。CS理论自从被D.Donoho(美国科学学院院士)E.Candes(Ridgelet.Curvelet创始人）及T.Tao（华裔科学家，2006年菲尔茨获奖得主，2008年被评为世界上最聪明的科学家）等人提出后，在信息论、信号/图像处理、医疗成像、模式识别、地质勘探、光学/雷达成像、无线通信等领域受到高度关注，并被美国科技评论为2007年度10大

39、科技进展之一14基于CS理论的目标跟踪。首先对目标进行建模，而后对后续帧图像进行相应的模型建立，将求取两模型最相似的问题转化为求取某相似参数的Li范数最小化问题，对高维数据的特征信息处理有明显优势，但是计算量大，复杂度高，是否对所有目标都具有鲁棒的跟踪效果有待于在目标跟踪方面做进一步研究。(4)数据获取在某些重要的情况下，完全采集模拟信号的N个离散时间样本是困难的，而且也难以对其进行压缩。而运用压缩感知，可以设计物理采样装置，直接记录模拟信号离散、低码率、不相关的测量值，有效地进行数据获取。基于RIP理论，目前已研制出了一些设备，有莱斯大学研制的单像素相机和A/I转换器，麻省理工学院研制的编码

40、孔径相机，耶鲁大学研制的超谱成像仪，麻省理工学院研制的MRIRF脉冲设备，伊利诺伊州立大学研制的DNA微阵列传感器。2.4 压缩感知有待研究的几个问题压缩感知经过近年来的迅猛发展，已基本形成了自己的理论框架，包括基础理论、实现方法和实际应用。但是，压缩感知理论还有很多亟待解决的问题，为此本文列出了压缩感知有待解决的几个关键问题。?基础理论层面：(1)基于非正交稀疏字典的压缩感知信号重建理论。在等距约束性准则驱动的可压缩信号压缩感知定理中，关于稀疏字典和测量矩阵仅要求两者乘积满足RIP。但是，测量矩阵设计部分关于压缩测量个数M的界定还额外附加了假设条件，即稀疏字典是正交基。当测量矩阵依然通过三种

41、方式生成，但是稀疏字典不再正交时，是否满足RIP?压缩测量个数M的下限是否不变？由于过完备的稀疏字典才能保证表示系数具有足够的稀疏性或衰减性，进而能够在减少压缩测量的同时保证压缩感知的重建精度，所以需要设计鲁棒的测量矩阵使之与过完备稀疏字典依然满足RIP,同时需要重新估计压缩测量个数M的下限，这时所需的压缩测量定会减少。(2)自然图像的自适应压缩感知信号重建理论。虽然基于线性投影的压缩感知理论能够直接应用于自然图像这样的复杂高维信号，但是由于没有考虑到自然图像的固有特性，诸如结构多成分性、高阶统计性等，对于自然图像压缩采样本身没有特殊的指导作用。事实上，相对于一维离散信号，自然图像的复杂性和高

42、维性使之需要自适应的压缩采样和重建算法。例如，基于图像多成分性的特点能够提高重建图像的峰值信噪比和视觉效果。压缩感知理论的大部分文献中，测量矩阵都是线性的且设计好的，不需根据观测信号自适应地变化。对于自然图像，假如能够实现非线性自适应的压缩测量，压缩感知的压缩性能势必会获得大幅度的提高。目前，自然图像的自适应压缩感知信号重建理论基本空白。这项工作对压缩感知的理论推广和实际应用都具有重要意义。?实现方法层面：(1)基于学习的自然图像过完备字典设计。目前，基于构造方法的自然图像过完备字典设计具有很好的理论支撑，正则化几何方法、几何多尺度分析、基于信息论的“有效编码假设”为其奠定了坚实广阔的理论基础

43、。但是，从国际上关于过完备字典设计的整体情况看，基于学习的自然图像过完备字典设计的工作非常少，主要在于：设计难度大、性能要求高，同时缺乏严格的理论支撑。这项工作对于稀疏字典和压缩感知都将是重要的理论完善。(2)硬件易实现的确定性测量矩阵设计。在等距约束性准则驱动的可压缩信号压缩感知定理中，要求稀疏字典于和测量矩阵的乘积日同PW藕思，稀疏字典乎可以是正交的也可以是非正交的，测量矩阵可以是随机的也可以是确定的。但是，面向应用且硬件易实现的测量矩阵应该具有以下基本特点：满足等距约束性、压缩测量个数少、采样计算成本低、存储矩阵的空间小、以及测量矩阵最好是确定性的。设计出硬件容易实现的测量矩阵和快速稳定

44、的重建算法是将压缩感知理论推向实用的关键。(3)噪声情形大尺度问题的快速鲁棒重建算法15设计。快速稳定的信号重建算法是将压缩感知理论推向实用的关键技术之一，特别适用于纠错编码、核磁共振成像、NMR波谱研究等大尺度问题。通常，基于最小化松弛算法的计算复杂度相对较高。因而，在最小化驱动的压缩感知理论完善工作的基础上，希望能够基于稀疏性自适应的贪婪迭代和基于多层超先验建模的非凸迭代思想设计适于噪声情形大尺度问题的快速鲁棒重建算法。第三章正交匹配追踪重建算法3.1 最小L0范数模型从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组（程的数量少于待解的未知数）的最简单解的问题，Lo范数刻画

45、的就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏。通常我们采用下式描述最小Lo范数最优化问题：minIX10s.t.YX（式3.1）实际中，允许一定程度的误差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中是一个极小的常量：IlII2（式3.2）min|x|0s.t.|YX|12但是这类问题的求解数值计算极不稳定，很难直接求解。匹配追踪类稀疏重建算法解决的是最小Lo范数问题，最早提出的有匹配追踪（MP）算法和正交匹配追踪（OMP）算法。3.2 匹配追踪算法匹配追踪算法的基本思想是在每一次的迭代过程中，从过完备原子库里（即感知矩阵）选择与信号最匹配的原子来进行稀疏逼近并求

46、出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是由于信号在已选定原子（感知矩阵的列向量）集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。匹配追踪类算法通过求余量r与感知矩阵中各个原子之间内积的绝对值，来计算相关系数u:uUj|UjI（r,J,j1,2，N（式3.3）并采用最小二乘法进行信号逼近以及余量更新：Xargmin|YX|2(式3.4)iRnewY用(式3.5)3.3正交匹配追踪算法(OMP)正交匹配追踪算法(OrthogonalMatchingPursuit,OMP),是最早的贪

47、婪迭代算法之一，是压缩感知信号检测的一种算法。本文后面的仿真就是采用基于压缩感知的正交匹配追踪算法来重建图像的。本节将着重介绍此算法的原理、实现步骤以及Matlab的语言实现。3.3.1 OMP算法原理OMP算法实质上还是沿用了匹配追踪算法中的原子选择准则，只是将所选原子利用Gram-Schmidt正交化方法进行正交处理，再将信号在这些正交原子构成的空间上投影，得到信号在各个已选原子上的分量和余量，然后用相同方法分解余量。在每一步分解中，所选原子均满足一定条件，因此余量随着分解过程迅速减小。通过递归地对已选择原子集合进行正交化保证了迭代的最优性，从而有效克服了匹配追踪算法为获得较好的收敛效果往

48、往需要经过较多的迭代次数的问题。OMP的重建算法是在给定迭代次数的条件下重建，这种强制迭代过程停止的方法使得OMP需要非常多的线性测量来保证精确重建。总之，它以贪婪迭代的方法选择的列，使得在每次迭代中所选择的列与当前的冗余向量最大程度地相关，从测量向量中减去相关部分并反复迭代，直到迭代次数达到稀疏度K,强制迭代停止3.3.2 OMP算法实现步骤OMP算法的具体步骤如下:(1)初始余量roY,迭代次数n1,索引值集合,J计算相关系数u,并将u中最大值对应的索引值存入J中；(3)更新支撑集，其中J。；应用(式3.4)得到X,同时用(式3.5)对余量进行更新;(5)若卜newr|2,令rrnew,n

49、n1,转步骤（2）;否则，停止迭代。3.3.3OMP算法的Matlab语言实现因为OMP算法只能对稀疏信号进行精确重构，所以为了实现对OMP的仿真,首先需要将图片转换为稀疏信号，如FFT、DCT、小波变换等，在本文中采取小波变换，然后将得到的稀疏信号与测量矩阵相乘得到测量值Y,然后通过OMP算法,根据Y精确重建出原始信号最后经过小波反变换得到原始图像。由于在Matlab平台上对图像的处理、小波变换、矩阵的求逆合并等运算的实现较为方便，因此本文首先选择在Matlab上实现OMP算法并对其进行仿真。对得到的x'进行小波反变换恢复原始图像x一：一（结束）'图3.iMaiia/仿真流程

50、图第四章基于MATLAB的压缩感知图像重建仿真4.1 不同采样率下的仿真结果4.1.1 一维信号在不同采样率下的OMP仿真实验均是采用Matlab编写正交匹配追踪（OMP）算法程序来进行仿真的。首先,我们选取一组一维的正弦信号，即x0.3sin(21"。原始信号图4.1原始信号这个原始信号x是f1=50,f2=100,f3=200,f4=400的混频和采样间隔fs=800的256长度的序列，它的稀释度为7。接下来，取观测向量M的长度为64,即采样率M/N=0.25对其进行重建。重建信号生成图如图4.2所:：RecoveryOriginal0.20-0.2-0.4-0

51、.6-0.8-1501001502002503000图4.2M=64时，原始信号、重构信号对比图由图4.2原始信号和重构信号的效果对比图可看出，当M=64时，能够较好的恢复出原始信号。由计算结果可知二者的相对误差在6.8680e-014左右。由于测量值M必须满足MK*log(N/K),当M值取最小值即M=40时，OMP重构算法的的恢复效果如下图4.3所示：0.20-0.2-0.4-0.6-0.8-1L0图4.3M=40时，原始信号、重构信号对比图从上述仿真可知OMP算法对一维信号的重构效果较好，在采样值较低的情况下也能精确恢复原始信号，相对误差小在5.9352e-014左右，

52、而且具有很好的收敛性。为了进一步说明OMP算法的重构效果，本文将用二维图像继续进行仿真。4.1.2 二维信号在不同采样率下的OMP仿真由第三章OMP算法的Matlab语言实现知识可知，在处理图像时，我们需将图像进行变换，如FFT、DCT、小波变换等，通过变换将图像转换成对应基下的稀疏系数，然后对系数矩阵按列进行处理，最后将处理过的系数反变换回来，就能得到稀疏重构的图像。这里用的重构算法还是正交匹配追踪算法。取原始图像如图4.4所示：原始图像图4.4原始图像仿真生成图如图4.5所示:原始图像小波变换后的图像恢复的图像图4.5OMP二维原始、恢复图像对比图为了让图像更稀疏，首先对原图像进行了小波变

53、换，之后又做了一个N*N的正交矩阵，为什么要用正交矩阵呢？说实话以前我也一直在考虑这个问题，原因是正交基矩阵与原图像不相关，重构时可以减少迭代次数。原始信号进行了小波变换后，变得更加稀疏，高频段的信息基本没了，这样图像缩小了很多，便于保存与传输。接下来就要对这个小波变换的信号进行测量和重构，当它们重构信号后，经过小波逆变换后得到恢复的图像（此过程中测量数选取的是M=190）。由实验结果可得出，原始图像与重构图像之间的重构误差为30.6127。正交匹配算法（OMP）对二维信号的重建效果还算清楚。接下来，我对Lena256*256图像在采样率（M/N）分别为0.9,0.7,0.5,0.3,0.1的

54、情况下又做了仿真，恢复图像如图4.6所示：原始图像恢复的图像，采样率=0.9恢复的图像，采样率=0.7恢复的图像，采样率=0.5恢复的图像，采样率=0.3恢复的图像，采样率=0.1图4.6OMP在不同采样率下恢复图像对比图为了更直观的对比OMP算法在不同采样率下的恢复效果，本文还给出了OMP算法在采样率位0.1,0,3,0,5,0,7,0.9时重建后的PSNR值，如表4-1所示：表4-1不同M/N与PSNR实验结果值比较M/N0.70.9PSNR6.130512,628026,805430,135930,6127由以上表格可以看出，随着采样率M/N值的逐渐增大，PSNR值也逐

55、渐增大。4.2 (OMP)算法与多种压缩感知算法的仿真比较在图像重建过程中，我还选用了基追踪重构算法(BP)、正交匹配追踪算法(OMP)和分段正交匹配追踪FDR阀值算法(STOMP_FDR)同时进行了仿真，并对仿真结果做以对比。基追踪算法(BP),在压缩感知理论中，观测数远小于信号长度，因此信号重构时不得不面对求解欠定方程组的问题。从常理来看，求解欠定方程组是不可能的，但是，由于信号是可压缩的或者说稀疏的，使得问题可解，而观测矩阵具有有限等距性(RIP),也为从观测值中精确恢复信号提供了理论支持。基追踪算法就是基于以上原理从而达到重构和对白噪声去噪的目的。它主要的目的是运作此定方程的解。正交匹

56、配追踪算法(OMP)在重构时每次迭代得到x的支撑集的一个原子，只是通过递推对已经选择原子几何进行正交化以保障迭代的最优性，从而减少迭代次数。分段正交匹配追踪FDR阀值算法(STOMP_FDR)相对于前两种算法而言，迭代次数就更少了，它是对OMP算法进行了一定程度的简化，以逼近精度为代价进一步提高了计算速度，因此在整个恢复原图像的过程中会节省大量的时间。首先先选择一张图片，本文采用的图片如图4,7所示：原始图像图4.7原始图像选择好原始图片后，我们要对图片进行读取数据x=imread('lena.bmp')；m,n=size(x)。这里采用的方法是对数据的每一列进行小波变换后再对

57、每列进行压缩感知，同时对BP,OMP,STOMP_FDR算法进行仿真。仿真如下图4.8所示:OrigineimageN=65536BP,samp=39.8438%time=57.038secOMP,samp=39.8438%time=1.801secFDR,samp=39.8438%time=0.705sec图4.8原始图像与BP、OMP、STOMP_FDR恢复对比图图4.8从图像的重构质量上可以看出，OMP的重建效果次于BP算法但优于STOMP_FDR算法。但从重建时间来看，OMP算法次于STOMP_FDR但明显优于BP算法。由此表明：OMP算法能够兼顾重构时间和重构质量，是一种比较实用的重建算法。4.3结论从上面一维信号到二维图像的压缩感知重建仿真可以得出以下结论：(1)正交匹配算法对一维信号有很优秀的还原恢复。(2)对于二维图像信号，正交匹