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

基于压缩感知的正交匹配算法图像重建 摘要：压缩感知理论是由 Donoho 和 Candes 提出的一种充分利用信号稀疏性的全新的信号采样理论。该理论表明，用远低于 Nyquist采样定理要求的频率对信号进行采样也能实现信号的精确重构。该理论突破了传统的以 Nyquist定理为基准的信号处理方法，实现了在获取数据的同时对其进行适当的压缩，克服了采样数据量大，采样时间长及数据存储空间浪费严重的问题，因此进一步降低了信号处理的时间和器件成本。压缩感知理论有三个核心方面：（1）稀疏变换，即对一个非稀疏的信号，找到一个合适的正交基使该信号在它上可以稀疏表示；（2）测量矩阵，与变换基不相干且平稳的矩阵；（3）重构算法，利用数学算法完成对信号的精确重构，该过程可看为求解一个优化问题。本文介绍了主要介绍了压缩感知原理和目前最为成熟的压缩感知重建算法正交匹配追踪算法，通过 MATLAB平台设计实现了基本的正交匹配追踪算法，对一维、二维信号进行了重建仿真。关键词：压缩感知；稀疏变换；正交匹配；图像重建 Based On Compressed Sensing Of Orthogonal Matching Algorithm Image Recovery Abstract：Compressed sensing is a novel sampling theory which is proposed by Donoho and Cand s.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 theory,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 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 considered 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 algorithm of one-dimensional,two-dimensional signal processing simulation.Key words：Compressed sensing;Sparse transform;Orthogonal matching;Image recovery.西安文理学院本科毕业设计（论文）第1页 目 录 第一章 绪论.2 1.1 选题的背景及意义.2 1.2 本课题在国内外的发展现状.2 1.3 本论文的结构安排.3 第二章 压缩感知理论相关知识.4 2.1 压缩感知理论框架.4 2.2 压缩感知的基本理论及核心问题.5 2.2.1 信号的稀疏表示.6 2.2.2 信号的观测矩阵.8 2.2.3 信号重构.9 2.3.压缩感知的应用.11 2.4 压缩感知有待研究的几个问题.13 第三章 正交匹配追踪重建算法.16 3.1 最小 L0范数模型.16 3.2 匹配追踪算法.16 3.3 正交匹配追踪算法(OMP).17 3.3.1 OMP 算法原理.17 3.3.2 OMP 算法实现步骤.17 3.3.3 OMP 算法的 Matlab 语言实现.17 第四章 基于 MATLAB 的压缩感知图像重建仿真.20 4.1 不同采样率下的仿真结果.20 4.1.1 一维信号在不同采样率下的 OMP 仿真.20 4.1.2 二维信号在不同采样率下的 OMP 仿真.22 4.2（OMP）算法与多种压缩感知算法的仿真比较.24 4.3 结论.26 结束语.27 致谢.28 参考文献.29 附录一 源程序清单.30 附录二 英文文献翻译.37 西安文理学院本科毕业设计（论文）第2页 第一章 绪论 1.1 选题的背景及意义 众所周知，传统的信号采样以奈奎斯特（Nyquist）采样定理为基础。为了不丢失信号的信息，精确重构信号，在获取信号时，采样频率要大于信号中最高频率的两倍。但是随着各种信号处理系统获取能力的不断增强，需要后期处理的数据量也快速增加，奈奎斯特定理的局限性给系统的处理能力提出了更高的要求，同时也给相应的硬件设施的设计带来了极大的挑战。如何高效处理这些数据并且最大限度的节省存储空间及传输成本已成为目前信息领域进一步向前发展的主要瓶颈之一。实际上，奈奎斯特采样定理是信号精确重构的充分条件而不是必要条件，奈奎斯特采样定理并不是唯一、最优的采样理论。因此研究如何突破以奈奎斯特采样定理为基础的信息的提取、处理、融合、存储、及传输是推动信息领域发展的关键。在 2004 年 Donoho 等人针对稀疏性信号，提出了压缩感知（Compressive sensing,简称 CS）理论。在随后的几年间该理论迅速发展，为解决上述问题奠定了基础。与传统信号处理方式不同，压缩感知理论以空间变换为基础，随机观测矩阵作为手段，优化求解作为恢复信号的方法。压缩感知理论在获取信号的同时对数据进行适当的压缩，其采样频率低于奈奎斯特采样频率，减少了采样数据，节省了存储空间，同时又包含了足够的信息量，能通过合适的重建算法对特定的图像或者信号进行精确重构。它将传统的数据采集和压缩合二为一，并且不需要复杂的数据编码算法，非常适合于要求采用小型器件的实现场合。信号的稀疏重建与压缩感知理论有重大的实用价值和应用前景，已经成为信号领域中一个新的研究方向1。1.2 本课题在国内外的发展现状 1国外研究状况及发展趋势 目前，CS 理论与应用研究正在如火如荼地进行：在美国、欧洲等许多国家的知名大学如麻省理工学院、莱斯大学、斯坦福大学、杜克大学等都成立了专门课题组对 CS 进行研究；2008 年，贝尔实验室,Intel,Google等知名公司也开始组织研究CS；2009 年,美国空军实验室和杜克大学联合召开了 CS 研讨会，美国国防先期研究计划署(DARPA)和国家地理空间情报局(NGA)等政府部门成员与数学、信号处理、微波遥西安文理学院本科毕业设计（论文）第3页 感等领域的专家共同探讨了 CS 应用中的关键问题；第二次以压缩感知和高维数据分析为主题的研讨会也将在 2011 年的 7 月 26 至 28 日在杜克大学召开2。2国内研究状况及发展趋势 在国内，一些高校和科研机构也开始跟踪 CS 的研究,如清华大学、中科院电子所、西安交通大学和西安电子科技大学等。自从 2006 年 CS 的提出，在 IEEE 的信号处理汇刊、信号处理快报汇刊、信号处理杂志、信息论汇刊等国际知名期刊上开始涌现出上百篇关于CS 理论与应用方面的文献。2010 年，IEEE Journal of Selected Topics in Signal Processing 专门出版了一期关于 CS 的专刊，促进了 CS 理论在各个领域应用成果的交流。2011 年 4 月，第一本关于 CS 的专著 Compressed Sensing:Theory and Applications出版，不仅系统的介绍了 CS 的概念，而且汇集了世界各国学者在 CS 理论和应用上的观点和成功范例。国家自然科学基金委也自 2009 年起资助了多项压缩感知方法的研究，涉及认知无线电、雷达成像、信号稀疏表示、多媒体编码、人脸识别等领域。1.3 本论文的结构安排 本文在对压缩感知理论以及现有的重构算法进行系统的研究之后，围绕正交匹配追踪重建算法展开研究来实现信号的重建，基于上述工作，本文内容分为四章，具体结构安排如下：第一章：绪论。首先介绍了压缩感知理论的研究背景及意义，然后介绍了国内外研究背景和现状，最后整理出全文内容的结构安排。第二章：压缩感知理论相关知识。首先介绍了压缩感知的框架，进而对信号的稀疏变换、观测矩阵的设计以及信号的重构三个主要方面的内容展开进一步详述，最后详细介绍了压缩感知理论在不同领域的应用及有待解决的几个问题。第三章：正交匹配追踪重建算法。这一章着重分析了正交匹配追踪算法的原理、实现步骤和 Matlab的语言实现。第四章：基于 MATLAB的压缩感知图像重建仿真。首先介绍了 OMP算法的思想以及算法步骤，然后再 matlab 上进行试验仿真，得出实验数据。最后将 OMP算法与其他算法进行比较研究做出总结分析。西安文理学院本科毕业设计（论文）第4页 第二章 压缩感知理论相关知识 2.1 压缩感知理论框架 传统的信号采集、编解码过程如图 2.l 所示。编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的 2 倍，使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。图 2.1 传统编解码理论的框图 压缩感知理论对信号的采样、压缩编码发生在同一个步骤如下图 2.2 所示，利用信号的稀疏性，以远低于 Nyquist 采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构。解码所需测量值的数目远小于传统理论下的样本数。西安文理学院本科毕业设计（论文）第5页 图 2.2 缩感知理论的编解码框图 2.2 压缩感知的基本理论及核心问题 压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术3。或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示。CS 理论利用到了许多自然信号在特定的基上具有紧凑的表示。即这些信号是“稀疏”的或“可压缩”的。由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。对于一个实值的有限长一维离散时间信号X，可以看作为一个NR空间N1的维的列向量，元素为 n，n,=1，2，N。NR空间的任何信号都可以用N1维的基向量 1iNi的线性组合表示。为简化问题，假定这些基是规范正交的。把向量 1iNi作为列向量形成NN的基矩阵=12,N，于是任意信号X都可以表示为：X (式2.1)其中是投影系数，=,iiX 构成的N1的列向量。显然，X和是同一个信号的等价表示，X是信号在时域的表示，则是信号在域的表示。如果的非零个数比N小很多，则表明该信号是可压缩的。一般而言，可压缩信号是指可以用K个大系数很好地逼近的信号，即它在某个正交基下展开的系数按一定量西安文理学院本科毕业设计（论文）第6页 级呈现指数衰减，具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。在数据采样系统中，采样速率高但信号是可压缩的，采样得到N点采样信号X；通过TX变换后计算出完整的变换系数集合i；确定K个大系数的位置，然后扔掉NK个小系数；对K个大系数的值和位置进行编码，从而达到压缩的目的。由Candes、Romberg、Tao和Donoho 等人在2004年提出的压缩感知理论表明，可以在不丢失逼近原信号所需信息的情况下，用最少的观测次数来采样信号，实现信号的降维处理，即直接对信号进行较少采样得到信号的压缩表示，且不经过进行N次采样的中间阶段，从而在节约采样和传输成本的情况下，达到了在采样的同时进行压缩的目的4。Candes证明了只要信号在某一个正交空间具有稀疏性，就能以较低的频率MN采样信号，而且可以以高概率重构该信号。即，设长度为N的信号X在某正交基或框架上的变换系数是稀疏的，如果我们可以用一个与变换基不相关的观测基：MNMN对系数向量进行线性变换，并得到观测集合:1YM。那么就可以利用优化求解方法5从观测集合中精确或高概率地重构原始信号X。图2.3 是基于压缩感知理论的信号重构过程框图。图 2.3 基于压缩感知理论的信号重构过程 2.2.1 信号的稀疏表示 压缩感知的第一步，即对于信号XNR，如何找到某个正交基或紧框架，使其在上的表示是稀疏的，即信号的稀疏表示问题。所谓的稀疏，就是指信号X在正交基下的变换系数向量为TX，假如对于02p 和0R，这些系数满足：1/PPiPiR (式2.2)则说明系数向量在某种意义下是稀疏的。如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏可压缩信号 稀疏变换 TX 观测得到的M维向量Y 重构信号 0minTX满足CSAXY 西安文理学院本科毕业设计（论文）第7页 度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幂次速度衰减的信号，可利用压缩感知理论得到恢复，并且重构误差满足：62(/log)rrEXXCKN (式2.3)其中r=1/p1/2，0p1.文献6指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一个有待进一步研究的问题。Peyre把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理。用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。字典的选择应尽可能的符合被逼近信号的结构，其构成可以没有任何限制。从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近。从非线性逼近角度来讲，信号的稀疏逼近包含两个层面：一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最佳的K项组合。因此，目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1)如何构造一个适合某一类信号的冗余字典；(2)如何设计快速有效的稀疏分解算法。在构造冗余字典方面，文献7中提出使用局部Cosine基来刻画声音信号的局部频域特性；利用bandlet基来刻画图像中的几何边缘；还可以把其它的具有不同形状的基函数归入字典，如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet基等等。在稀疏分解算法的设计方面，基于贪婪迭代思想的MP(Matching Pursuit)算法表现出极大的优越性，但不是全局最优解。Donoho等人之后提出了基追踪(basis pursuit，BP)算法。BP算法具有全局最优的优点，但计算复杂度极高。之后又出现了一系列同样基于贪婪迭代思想的改进算法，如正交匹配追踪算法(OMP)，分段匹配追踪(STOMP)算法等。西安文理学院本科毕业设计（论文）第8页 2.2.2 信号的观测矩阵 如何设计一个平稳的、与变换基不相关的MN维的观测矩阵，保证稀疏向量从N维降到M维时重要信息不遭破坏，是第二步要解决的问题，也就是信号低速采样问题。压缩感知理论中，通过变换得到信号的稀疏系数向量TX后，需要设计压缩采样系统的观测部分，它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然，如果观测过程破坏了X中的信息，重构是不可能的。观测过程实际就是利用MN观测矩阵的M个行向量1Mjj对稀疏系数向量进行投影，即计算和 各 个 观 测 向 量1Mjj之 间 的 内 积，得 到M个 观 测 值,1,2,Mjjyj,，记观测向量12(,y)MYy y，即 TCSYXAX (式2.4)这里，采样过程是非自适应的，也就是说，无须根据信号X而变化，观测的不再是信号的点采样而是信号的更一般的K线性泛函。对于给定的Y从式(2.4)中求出是一个线性规划问题，但由于MN，即方程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。然而，如果具有K-项稀疏性(KM)，则该问题有望求出确定解。此时，只要设法确定出中的K个非零系数i的合适位置，由于观测向量Y是这些非零系数i对应的K个列向量的线性组合，从而可以形成一个MK的线性方程组来求解这些非零项的具体值。对此，kkff112222即有限等距性质（RIP）给出了存在确定解的充要条件。这个充要条件和Candes、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即，要想使信号完全重构，必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。从中可以看出，问题的关键是如何确定非零系数的位置来构造出一个可解的MK线性方程组。西安文理学院本科毕业设计（论文）第9页 然而，判断给定的CSA是否具有RIP性质是一个组合复杂度问题。为了降低问题的复杂度，能否找到一种易于实现RIP条件的替代方法成为构造观测矩阵的关键。文献8指出如果保证观测矩阵和稀疏基不相干，则CSA在很大概率上满足RIP性质。不相干是指向量j不能用i稀疏表示。不相干性越强，互相表示时所需的系数越多；反之，相关性则越强。通过选择高斯随机矩阵作为观测矩阵即可高概率保证不相干性和RIP性质。例如，可以生成多个零均值、方差为1/N的随机高斯函数，将它们作为观测矩阵的元素j，使得CSA以很高的概率具有RIP性质。随机高斯矩阵具有一个有用的性质：对于一个MN的随机高斯矩阵，可以证明当McKlog(NK)时TCSA 在很大概率下具有RIP性质(其中c是一个很小的常数)。因此可以从M个观测值12(,y)MYy y，中以很高的概率去恢复长度为N的K-项稀疏信号。总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关，这一特性决定了选它作为观测矩阵，其它正交基作为稀疏变换基时，CSA满足RIP性质。为进一步简化观测矩阵，在某些条件下，以随机1为元素构成的Rademacher矩阵也可以证明具有RIP性质和普适性。对观测矩阵的研究是压缩感知理论的一个重要方面。Donoho给出了观测矩阵所必需具备的三个条件9，并指出大部分一致分布的随机矩阵都具备这三个条件，均可作为观测矩阵，如：部分Fourier集、部分Hadamard集、一致分布的随机投影(uniform Random Projection)集等，这与对RIP性质进行研究得出的结论相一致。但是，使用上述各种观测矩阵进行观测后，都仅仅能保证以很高的概率去恢复信号，而不能保证百分之百地精确重构信号。对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。2.2.3 信号重构 如何设计快速重构算法，从线性观测CSYAX中恢复信号，是第三步要将解决的问题，即信号的重构问题。在压缩感知理论中，由于观测数量M远小于信号长度N，因此不得不面对求解欠定方程组CSYAX的问题。表面上看，求解欠定方程组似乎是无望的，但是，文献10和11均指出由于信号X是稀疏的或可压缩的，这个前提从根本上改变了问题，使得问题可解，而观测矩阵具有RIP性质也为从M个观测值中精确恢复信号提供了理西安文理学院本科毕业设计（论文）第10页 论保证。为更清晰地描述压缩感知理论的信号重构问题，首先定义向量12,nXx x，x的p 范数为：1/p1NpiPiXx (式2.5)当0p 时得到0范数，它实际上表示X中非零项的个数。于是，在信号X稀疏或可压缩的前提下，求解欠定方程组CSYAX的问题转化为最小0范数问题：0minTX s.t.CSTAXXY (式2.6)但是，它需要列出M中所有非零项位置的KNC种可能的线性组合，才能得到最优解。因此，求解式（2.6)的数值计算极不稳定而且是NP难问题。注意，这和稀疏分解问题从数学意义上讲是同样的问题。于是稀疏分解的已有算法可以应用到CS 重构中。Chen，Donoho 和Saunders 指出，求解一个更加简单的1l优化问题会产生同等的解(要求和不相关)：1minTX s.t.CSTAXXY (式2.7)稍微的差别使得问题变成了一个凸优化问题，于是可以方便地化简为线性规划问题，典型算法代表：BP算法尽管BP算法可行，但在实际应用中存在两个问题：第一，即使是常见的图像尺寸，BP算法的计算复杂度也难以忍受，在采样点个数满足McK，2log/1cNK时，重构计算复杂度的量级在3()O N；第二，由于1范数无法区分稀疏系数尺度的位置，所以尽管整体上重构信号在欧氏距离上逼近原信号，但存在低尺度能量搬移到了高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。基于上述问题，2005年1月Candes和Romberg 提出了不同的信号恢复方法，该方法要求对原信号具有少量的先验知识，同时也可以对所求结果施加适当的期望特性，以约束重构信号的特性。通过在凸集上交替投影的方法，可以快速求解线性规划问题。西安文理学院本科毕业设计（论文）第11页 Tropp和Gilbert 提出利用匹配追踪(MP)和正交匹配追踪(OMP)算法来求解优化问题重构信号，大大提高了计算的速度，且易于实现。树形匹配追踪(TMP)算法是2005年La和NDo 提出的。该方法针对BP、MP 和OMP 方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系，是将稀疏系数的树型结构加以利用，进一步提升了重构信号的精度和求解的速度。匹配追踪类算法都是基于贪婪迭代算法，以多于BP算法需要的采样数目换取计算复杂度的降低。例如OMP 算法，需要McK，2ln()cN个采样点数才能以较高的概率恢复信号，信号重构的计算复杂度为2()O NK。2006年Donoho等人提出了分段正交匹配追踪(STOMP，Stagewise OMP)算法。它将OMP进行一定程度的简化，以逼近精度为代价进一步提高了计算速度(计算复杂度为O(N)，更加适合于求解大规模问题。匹配追踪类方法为其近似求解提供了有力工具，且该类方法用于稀疏信号重建时具有一定的稳定性。文献12中提出的OMP算法延续了匹配追踪算法中原子的选择准则，但是实现了递归地对已选原子集合进行正交化以保证迭代的最优性，从而减少了迭代次数。此后，Needell和Vershynin等人在OMP算法的基础上将正则化过程用于稀疏度K已知的OMP算法中，提出了ROMP算法。ROMP算法与OMP算法的不同之处在于，该算法首先根据相关原子挑选多个原子作为候选集，然后从候选集中按照正则化原则挑选出部分原子，最后将其并入最终的支撑集，从而实现了原子的快速、有效选择。最近出现的子空间匹配追踪算法(Subspace Pursuit，SP)和压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit，CoSaMP)引入了回退筛选的思想，这些算法的重建质量与线性规划方法相当，同时重建复杂度低，但是这些算法都是建立在稀疏度K已知的基础上。然而实际应用中信号的稀疏度K往往是未知的，由此出现了对稀疏度K自适应的稀疏自适应匹配追踪算法(Sparsity Adaptive Matching Pursuit,SAMP)，它通过设置一个可变步长，逐步对信号稀疏度进行估计，因此可以在K未知的情况下获得较好的重建效果，速度也远快于OMP算法。基于ROMP算法和SAMP算法的突出优势。2.3.压缩感知的应用 这里主要介绍 CS 理论在成像系统、图像融合、图像跟踪以及数据获取等方面的应用。（1）成像系统 西安文理学院本科毕业设计（论文）第12页 在成像方面，CS 理论的出现激起了人们研究新型传感器的热情，CS 采样对昂贵的成像器件的设计产生了重大影响。在地震勘探和核磁共振成像中，对于目标信号，将有望采用少量的随机观测次数就能获得高精度重构，取代传统数码相机拍照时采集大量像素的一种新型单像素CS 相机已经得到论证。相对于 CS 的理论研究进展，美国 Rice大学也已经研制出单像素相机，如下图 2.4所示。该相机具有一种全新的相机结构，使用数字微镜阵列完成图像在伪随机二值模型上线性投影的光学计算。它可利用单一的信号光子检测器采样得到比图像像素点数少得多的点恢复图像，并具有对图像波长自适应的能力，这种自适应能力是传统的 CCD和 CMOS成像器件所不具备的。ARI-ZONA大学 Baheti和 Neifeld 设计了具有特定功能的结构成像设备，DUCK大学研制了单景光谱成像装置。然而由于压缩重构算法的计算量比较大，难以达到实时性要求，因此实时高性能压缩感知成像系统是未来重要的研究方向。图 2.4 单像素相机（2）图像融合 图像融合是信息融合范畴内以图像为对象的研究领域。图像融合将多个成像传感器或同一成像传感器在不同模式下获取的同一场景的图像信息加以综合，获取更为精确、全面、可靠的图像描述。图像融合技术在自动目标识别、计算机视觉、遥感、机器人、自动小车、复杂智能制造系统、医学图像处理以及军事应用等领域有着广泛的应用潜力13。将不同模式下的融合图像采用 CS 理论进行稀疏表示，如下图 2.5所示。使其在测量举证的作用下，用远小于原图像的数据量进行计算得到融合结果还原为图像表示，可节省中间融合所需的计算量，并且能够更好地利用原图像中像素间的内在联系，是一个非常值得研究的课题。西安文理学院本科毕业设计（论文）第13页 图 2.5 CS 用于图像融合的流程框图（3）目标跟踪 视频目标跟踪是使用可见、红外等被动式成像传感器实现目标测量的核心技术之一，是目标识别、视频图像的压缩编码等高层次的视频处理和应用理解的基础，也是视频监控技术自动化和实时应用的关键。目标跟踪的实质是通过对图像传感器拍摄到的视频序列进行分析，计算出目标在每帧图像中的位置、大小和运动速度。CS 理论自从被 D.Donoho（美国科学学院院士）E.Candes(Ridgelet.Curvelet创始人)及 T.Tao(华裔科学家，2006 年菲尔茨获奖得主，2008 年被评为世界上最聪明的科学家)等人提出后，在信息论、信号/图像处理、医疗成像、模式识别、地质勘探、光学/雷达成像、无线通信等领域受到高度关注，并被美国科技评论为 2007 年度 10 大科技进展之一14。基于 CS 理论的目标跟踪。首先对目标进行建模，而后对后续帧图像进行相应的模型建立，将求取两模型最相似的问题转化为求取某相似参数的 L1范数最小化问题，对高维数据的特征信息处理有明显优势，但是计算量大，复杂度高，是否对所有目标都具有鲁棒的跟踪效果有待于在目标跟踪方面做进一步研究。（4）数据获取 在某些重要的情况下，完全采集模拟信号的N 个离散时间样本是困难的，而且也难以对其进行压缩。而运用压缩感知，可以设计物理采样装置，直接记录模拟信号离散、低码率、不相关的测量值，有效地进行数据获取。基于RIP理论，目前已研制出了一些设备，有莱斯大学研制的单像素相机和A/I转换器，麻省理工学院研制的编码孔径相机，耶鲁大学研制的超谱成像仪，麻省理工学院研制的MRI RF 脉冲设备，伊利诺伊州立大学研制的DNA 微阵列传感器。2.4 压缩感知有待研究的几个问题 压缩感知经过近年来的迅猛发展，已基本形成了自己的理论框架，包括基础理论、实现方法和实际应用。但是，压缩感知理论还有很多亟待解决的问题，为此本西安文理学院本科毕业设计（论文）第14页 文列出了压缩感知有待解决的几个关键问题。基础理论层面：（1）基于非正交稀疏字典的压缩感知信号重建理论。在等距约束性准则驱动的可压缩信号压缩感知定理中，关于稀疏字典和测量矩阵仅要求两者乘积满足RIP。但是，测量矩阵设计部分关于压缩测量个数M的界定还额外附加了假设条件，即稀疏字典是正交基。当测量矩阵依然通过三种方式生成，但是稀疏字典不再正交时，是否满足RIP？压缩测量个数M的下限是否不变？由于过完备的稀疏字典才能保证表示系数具有足够的稀疏性或衰减性，进而能够在减少压缩测量的同时保证压缩感知的重建精度，所以需要设计鲁棒的测量矩阵使之与过完备稀疏字典依然满足RIP，同时需要重新估计压缩测量个数M的下限，这时所需的压缩测量定会减少。（2）自然图像的自适应压缩感知信号重建理论。虽然基于线性投影的压缩感知理论能够直接应用于自然图像这样的复杂高维信号，但是由于没有考虑到自然图像的固有特性，诸如结构多成分性、高阶统计性等,对于自然图像压缩采样本身没有特殊的指导作用。事实上，相对于一维离散信号,自然图像的复杂性和高维性使之需要自适应的压缩采样和重建算法。例如，基于图像多成分性的特点能够提高重建图像的峰值信噪比和视觉效果。压缩感知理论的大部分文献中，测量矩阵都是线性的且设计好的，不需根据观测信号自适应地变化。对于自然图像，假如能够实现非线性自适应的压缩测量，压缩感知的压缩性能势必会获得大幅度的提高。目前，自然图像的自适应压缩感知信号重建理论基本空白。这项工作对压缩感知的理论推广和实际应用都具有重要意义。实现方法层面：（1）基于学习的自然图像过完备字典设计。目前，基于构造方法的自然图像过完备字典设计具有很好的理论支撑，正则化几何方法、几何多尺度分析、基于信息论的“有效编码假设”为其奠定了坚实广阔的理论基础。但是，从国际上关于过完备字典设计的整体情况看，基于学习的自然图像过完备字典设计的工作非常少，主要在于：设计难度大、性能要求高，同时缺乏严格的理论支撑。这项工作对于稀疏字典和压缩感知都将是重要的理论完善。(2)硬件易实现的确定性测量矩阵设计。在等距约束性准则驱动的可压缩信号压缩感知定理中，要求稀疏字典 和测量矩阵 的乘积=满足RIP。其中，稀疏字典西安文理学院本科毕业设计（论文）第15页 可以是正交的也可以是非正交的，测量矩阵 可以是随机的也可以是确定的。但是，面向应用且硬件易实现的测量矩阵应该具有以下基本特点：满足等距约束性、压缩测量个数少、采样计算成本低、存储矩阵的空间小、以及测量矩阵最好是确定性的。设计出硬件容易实现的测量矩阵和快速稳定的重建算法是将压缩感知理论推向实用的关键。（3）噪声情形大尺度问题的快速鲁棒重建算法15设计。快速稳定的信号重建算法是将压缩感知理论推向实用的关键技术之一，特别适用于纠错编码、核磁共振成像、NMR 波谱研究等大尺度问题。通常，基于最小化松弛算法的计算复杂度相对较高。因而，在最小化驱动的压缩感知理论完善工作的基础上，希望能够基于稀疏性自适应的贪婪迭代和基于多层超先验建模的非凸迭代思想设计适于噪声情形大尺度问题的快速鲁棒重建算法。西安文理学院本科毕业设计（论文）第16页 第三章 正交匹配追踪重建算法 3.1 最小 L0范数模型 从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数量少于待解的未知数)的最简单解的问题，L0范数刻画的就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏。通常我们采用下式描述最小L0范数最优化问题：0min X s.t.YX (式3.1)实际中，允许一定程度的误差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中是一个极小的常量：0min X s.t.22YX (式 3.2)但是这类问题的求解数值计算极不稳定，很难直接求解。匹配追踪类稀疏重建算法解决的是最小L0范数问题，最早提出的有匹配追踪(MP)算法和正交匹配追踪(OMP)算法。3.2 匹配追踪算法 匹配追踪算法的基本思想是在每一次的迭代过程中，从过完备原子库里(即感知矩阵)选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是由于信号在已选定原子(感知矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。匹配追踪类算法通过求余量r与感知矩阵中各个原子之间内积的绝对值，来计算相关系数u：|,1,2,Njjjuuurj，（式3.3）并采用最小二乘法进行信号逼近以及余量更新:2minargXYXRi （式 3.4）西安文理学院本科毕业设计（论文）第17页 r,newYX （式 3.5）3.3 正交匹配追踪算法(OMP)正交匹配追踪算法（Orthogonal Matching Pursuit,OMP），是最早的贪婪迭代算法之一，是压缩感知信号检测的一种算法。本文后面的仿真就是采用基于压缩感知的正交匹配追踪算法来重建图像的。本节将着重介绍此算法的原理、实现步骤以及 Matlab的语言实现。3.3.1 OMP 算法原理 OMP算法实质上还是沿用了匹配追踪算法中的原子选择准则，只是将所选原子利用Gram-Schmidt正交化方法进行正交处理，再将信号在这些正交原子构成的空间上投影，得到信号在各个已选原子上的分量和余量，然后用相同方法分解余量。在每一步分解中，所选原子均满足一定条件，因此余量随着分解过程迅速减小。通过递归地对已选择原子集合进行正交化保证了迭代的最优性，从而有效克服了匹配追踪算法为获得较好的收敛效果往往需要经过较多的迭代次数的问题。OMP的重建算法是在给定迭代次数的条件下重建，这种强制迭代过程停止的方法使得OMP需要非常多的线性测量来保证精确重建。总之，它以贪婪迭代的方法选择的列，使得在每次迭代中所选择的列与当前的冗余向量最大程度地相关，从测量向量中减去相关部分并反复迭代，直到迭代次数达到稀疏度K，强制迭代停止。3.3.2 OMP 算法实现步骤 OMP算法的具体步骤如下：(1)初始余量Yr 0，迭代次数1n，索引值集合，J；(2)计