压缩感知毕业论文.docx

压缩感知毕业论文压缩感知毕业论文 压缩感知毕业论文 目录 第1章 绪论 . 1 1.1 研究背景和意义 . 1 1.2 CS理论框架 . 2 1.3 本文框架结构 . 4 第2章 国内外研究现状 . 6 2.1 从稀疏重构到压缩感知 . 6 2.2 稀疏重构算法和重构条件研究 . 7 2.3 压缩感知在光学成像中的应用 . 9 第3章 压缩感知基本理论 . 12 3.1 压缩感知背景 . 12 3.2 压缩感知理论 . 13 3.2.1压缩感知的前提条件稀疏性和不相干性 . 13 3.2.2 三个关键技术 . 17 I 压缩感知毕业论文 3.2.3信号的稀疏表示 . 17 3.2.4 观测矩阵设计 . 19 3.2.5 稀疏信号的重构 . 21 3.2.6 重构算法 . 22 3.3压缩感知理论应用概述 . 24 3.3.1压缩成像 . 24 3.3.2 模拟信息转换 . 25 3.3.3 生物传感 . 25 3.4 本章小结 . 25 第4章 压缩感知实现及结果分析 . 26 4.1图像压缩基本理论 . 26 4.1.1传统图像压缩重构方法 . 26 4.1.2 图像压缩重构质量的评价 . 27 4.2 压缩感知理论算法对一维信号的实现 . 29 4.2.1 正交匹配追踪算法 . 29 4.2.2 算法的实现及结果分析 . 31 4.3 压缩感知理论算法对二维图像重构的实现 . 34 4.3.1 基于小波变换的分块压缩感知理论 . 34 4.3.2 实现步骤 . 35 4.3.3 重构结果及分析 . 38 4.4 本章小结 . 43 第5章 总结与展望 . 44 5.1 总结 . 44 5.2 展望 . 44 参考文献 . 46 致谢 . 47 II 压缩感知毕业论文 附录 . 49 III 压缩感知毕业论文 第1章 绪论 信号采样是联系模拟信源和数字信息的桥梁。随着信息技术日新月异的进步，人们对信息的巨量需求造成了信号采样、传输和存储的巨大压力。如何缓解这种压力又能有效提取承载在信号中的有用信息是信号与信息处理中急需解决的问题之一。近几年来，在信号处理领域出现的压缩感知理论打破了传统采样过程中信号采样速率必须达到信号带宽两倍以上才能精确重构原始信号的奈奎斯特采样定理，使得信息存储、处理和传输的成本大大降低。 1.1 研究背景和意义 信息技术的飞速发展使得人们对信息的需求量剧增。现实世界的模拟化和信号处理工具的数字化决定了信号采样是从模拟信源获取数字信息的必经之路。 奈奎斯特采样定理则是指导如何采样的重要理论基础。它指出，采样速率必须达到信号带宽的两倍以上才能精确重构信号。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高，因而对宽带信号处理的困难在日益加剧。例如高分辨率地理资源观测，其巨量数据传输和存储就是一个艰难的工作。另一方面，在实际应用中，为了降低存储、处理和传输的成本，人们常采用压缩方式以较少的比特数表示信号，大量的非重要的数据被抛弃。这种高速采样再压缩的过程浪费了大量的采样资源，于是很自然地引出一个问题:能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于奈奎斯特采样定理要求的速率采样信号，同时又可以完全恢复信号? 即能否将对信号的采样转变成对信息的采样? 如果这个问题被解决，就可以极大地降低信号的采样频率及数据存储和传输代价，显著地降低信号处理时间和计算成本，并将带领信号处理进入一个新的革命时代。近几年来出现的一种新颖的理论Compressed sensing(也称为Compressive sampling) 表明这是可能的。 目前还没有一个统一的中文词汇与之对应，有人称之为压缩传感，也有人称其为压缩感知(以下均采用压缩感知) 。 压缩感知理论与传统奈奎斯特采样定理不同，它指出，只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。 在该理论框架下，采样速率不决定于信号的带宽，而决定于信息在信号中的结构和内容。 事实上，压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论， 最近由1 压缩感知毕业论文 Candès，Romberg ，Tao和Donoho等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。从信号分析角度来讲，傅立叶变换是信号和数字图像处理的理论基础，小波分析将信号和数字图像处理带入到一个崭新的领域。 多尺度几何分析是继小波分析后的新一代信号分析工具，它具有多分辨、局部化和多方向性等优良特性，更适合于处理图像等高维信号。 这些研究工作都为压缩感知理论奠定了基础。显然，在压缩感知理论中，图像/信号的采样和压缩同时以低速率进行，使传感器的采样和计算成本大大降低，而信号的恢复过程是一个优化计算的过程。 因此，该理论指出了将模拟信号直接采样压缩为数字形式的有效途径，具有直接信息采样特性。 由于从理论上讲任何信号都具有可压缩性，只能找到其相应的稀疏表示空间，就可以有效地进行压缩采样，这一理论必将给信号采样方法带来一次新的革命。 压缩感知理论的引人之处还在于它对应用科学和工程的许多领域具有重要的影响和实践意义， 如统计学、信息论、编码等。本文以稀疏信号的压缩观测及重构为主线，综述了压缩感知理论以及与之相关的信号稀疏变换、观测矩阵设计、重构算法等一系列最新理论成果和应用研究，描述了国内外的研究进进展，讨论了其中的公开问题，展望了未来的研究方向。 1.2 CS理论框架 在传统理论的指导下，信号X的编解码过程如图1.1所示：编码端首先获得X 的N点采样值，经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码，最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。实际上，采样得到的大部分数据都是不重要的，即K值很小，但由于奈奎斯特采样定理的限制，采样点数N可能会非常大，采样后的压缩是造成资源浪费的根本所在。 NX采样压缩K存储和传输K接收解压缩NX图1.1 传统编解码理论框图 CS 理论的信号编解码框架和传统的框架大不一样，如图1.2 所示。CS 理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低2 压缩感知毕业论文 维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下，利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构，解码所需测量值的数目远小于传统理论下的样本数。 压缩感知的核心思想是压缩和采样合并进行，并且测量值远小于传统采样方法的数据量，突破了香农采样定理的瓶颈，使高分辨率的信号采集成为可能。 压缩感知理论主要包括信号的稀疏表示、随机测量和重构算法等三个方面。稀疏表示是应用压缩感知的先验条件，随机测量是压缩感知的关键过程，重构算法是获取最终结果的必要手段。 M接收重构NXNX线性观测过程M存储和传输图1.2 CS理论下数据的编解码过程 压缩感知关键要素包括稀疏表示、测量矩阵和重构算法。 信号在某种表示方式下的稀疏性，是压缩感知应用的理论基础，经典的稀疏化的方法有离散余弦变换、傅里叶变换、离散小波变换等。 最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。 这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：一是如何构造一个适合某一类信号的冗余字典，二是如何设计快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分为匹配追踪和基追踪两大类。 压缩感知理论中，通过变换得到信号的稀疏系数后，需要设计压缩采样系统的观测部分，它围绕观测矩阵F展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者稀疏基基Y下等价的稀疏系数向量。 CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。XX年Candes等研究者建立了著名的约束等距性理论，即要想使信号完全重构，必须保证观测矩阵不会把两个不同的 K项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。 3 压缩感知毕业论文 Donoho给出压缩感知概念的同时定性和定量的给出测量矩阵要满足三个特征：(1)由测量矩阵的列向量组成的子矩阵的最小奇异值必须大于一定的常数；(2)测量矩阵的列向量体现某种类似噪声的独立随机性；(3)满足稀疏度的解是满足1范数最小的向量。 目前常用的测量矩阵包括： 随机高斯矩阵。矩阵每个元素独立地服从均值为0，方差为1M的高斯分布。 随机贝努利矩阵。矩阵的每个元素独立地服从对称的贝努利分布，等概率为1M或-1M。 部分正交矩阵。先生成N×N的正交矩阵U，然后在矩阵U中随机地选取M行向量，对M×N矩阵的列向量进行单位化得到测量矩阵。 部分哈达玛矩阵。生成大小为N×N的哈达玛矩阵，然后在生成矩阵中随机地选取M行向量，构成一个M×N的矩阵。 托普利兹和循环矩阵。首先生成一个向量u，由向量u生成相应的轮换矩阵或托普利兹矩阵U，然后在矩阵U中随机地选取其中的M行而构造的矩阵。 稀疏随机矩阵。首先生成一个零元素的矩阵，在矩阵的每一个列向量中，随机地选取d个位置，然后在所选取的位置的值赋为1。 压缩感知的重构算法主要分为两大类，一是贪婪算法，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。二是凸优化算法，它是把0范数放宽到1范数通过线性规划求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。凸优化算法算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。 此外，迭代阈值法也得到了广泛的应用，此类算法也较易实现，计算量适中，在贪婪算法和凸优化算法中都有应用。但是，迭代阈值法对于迭代初值和阈值的选取均较敏感，且不能保证求出的解是稀疏的。 就目前主流的两种重建算法而言，基于1范数最小的重建算法计算量巨大，对于大规模信号无法应用；贪婪算法虽然重建速度快，但是在信号重建质量上还有待提高。 1.3 本文框架结构 本文通过对压缩感知理论进行系统认真的学习和研究，查阅了大量的国内外相关的文献和资料，主要完成了围绕正交匹配追踪算法的信号和图像重构处理。本文的主要结构如下所示： 第一章，绪论。本章首先介绍了压缩感知理论研究的背景和意义，然后综述了4 压缩感知毕业论文 CS理论的理论框架，最后陈述了本文的内容安排。 第二章，国内外研究现状。本章介绍了压缩感知理论的历史、发展及将来的研究方向。然后介绍了其在光学成像方面的应用。 第三章，压缩感知基本理论。本章详细阐述了压缩感知理论的基本原理。 首先讲述了CS理论的数学原理，然后围绕压缩感知的三个关键技术，信号的稀疏表示、观测矩阵的设计和重构算法展开讨论，介绍了该理论是如何实现的。最后介绍了其在现实中的最新应用及一些不足和需要改进之处。 第四章，压缩感知实现及结果分析。本章首先简单介绍了传统图像压缩技术在变换编码方面的重构方法。然后完成了分别基于离散傅里叶变换和离散余弦变换的一维信号和二维图像的OMP算法重构，并进行了性能参数方面的对比。 第五章，总结和展望。本章总结了本设计所完成的工作，并对其中的缺陷做出了说明，指出了所采用算法的不足指出，对下一步的工作做了展望。 5 压缩感知毕业论文 第2章 国内外研究现状 压缩感知理论是近几年刚刚兴起的理论，但却展现了强大的生命力引起了广泛的关注，下面我们将对该理论的历史和发展历程做出介绍。 2.1 从稀疏重构到压缩感知 早在压缩感知理论正式提出以前，XX年代的石油勘探地震数据处理中，人们已经发现香农-奈奎斯特采样定理的限制是“可以突破的”。由于测量条件的限制，获取的数据十分有限，根据传统理论并不足以重构地层结构。幸运的是，地层内部是均质的，只是层与层之间又不连续，且这种不连续是“稀疏的”。当理由这种稀疏性先验知识时，便可以较好的反演地质结构。 从数学上看，地层结构反演属于典型的逆问题，逆问题往往是病态的，需要加入正规化约束以得到有用的结果。”稀疏性”是近二十年来逐步发展起来的一种正规化约束，含稀疏性约束的逆问题被称为稀疏重构问题，其本质是从超完备字典F中寻找尽可能少的原子，通过它们的线性组合来逼近给定的向量y。即 Findsparset x，s.t y»Fx (式2.1) 定义2.1：对于M´N维矩阵F，若其各列具有单位长度，则称之为字典，矩阵的各列fi,i=1,.,N被称为原子。 稀疏重构问题本质上是一种后端处理方法。其应用是在数据获取之后，并没有与前端的数据获取系统相结合。 采样理论的研究自Shannon以后也经历着不断的发展，其中基于“新息率”的采样策略与压缩感知理论密切相关。考虑在单位时间内具有有限自由度的信号，称该自由度为新息率。实际应用中有很多这样的信号，如Poisson过程、非均匀采样和分段多项式等。这些信号不是带限的，根据Shannon定理，均匀矩形脉冲采样条件下无法精确重构。文献11-14指出基于高于新息率的非均匀采样和适当构造的核函数，这些信号仍可以精确重构。 Analog-to-information conversion(AIC)是根据压缩感知理论设计的一种新概念采样体制，其充分利用这样一个事实：许多射频信号虽然具有很大的带宽，但是他们的“新息率”有限，因此可以根据其新息率，而非带宽进行采样。 随着稀疏重构和新兴采样定理研究的不断深化，很多学者发现，当测量数据不完全时，有时甚至只有很小一部分测量数据，利用该方法仍可以很好的重构原图像。XX年Candes, Romberg及Tao等人在研究高度欠定的核磁共振成像问题时，得出一个重要的结论：当测量矩阵为Fourier矩阵时，O(K*log(N)的数据采集量能将N维空间的6 压缩感知毕业论文 K稀疏信号精确重建。XX年，Candes和 Romberg将Fourier测量方式推广到任意正交测量并得到类似的结论。这两项工作表述了一个问题：可通过低维频域(或时域)信号实现高维稀疏时域(或频域)信号的精确重建。 这个令人惊喜的发现促使压缩感知理论的诞生：既然利用部分测量数据就可以精确重构原图像，那么为什么不在测量时就仅获得所需的数据，而不是耗费大量资源来获取全部数据。其后Candes, Romberg及Tao等人，初步建立了压缩感知的理论基础。 压缩成像的组成可以分为两个部分：数据的获取过程和图像的重构过程。其中，后者和稀疏重构的研究一脉相传，但需特别考虑二维图像所涉及的大规模数据下的保精确度快速计算问题；前者的研究理论上需研究使得“稀疏重构”能够恢复原信号的测量矩阵的行质，即可重构条件，应用中还需考虑满足重构条件的测量矩阵的物理实现问题，即利用适当的硬件设备完成压缩采样。 2.2 稀疏重构算法和重构条件研究 首先给出lp范数的定义，需要指出的是，当参数p在某些范围内取值时， (式2.2)的定义可能不满足三角不等式，因此不是真正意义上的范数，但不影响讨论，仍称其为范数。 定义2.3： 信号x=(x1,.,xN)T的lp范数x x = ( å i = 1 x i )1 / p pNpp为： 其中当p=0时，等价于计算x中的非零元素的个数，当p=2时，为空间中的欧氏范数，当p®¥时， xp®maxxi1£i£N根据定义2.1，图像的稀疏性最本质的度量为l0范数，则的数学描述为 minx0 s.t. y=Fx x若测量噪声中含有噪声，则重构模型为 minx0 s.t. y=Fxx2£d 其中参数d反映了测量噪声的水平。 和等含l0范数的稀疏重构问题已被证明是NP难解的，需要寻找多项式时间内可解得近似方法，现有的主要方法可以分为： 1)贪婪算法 基本思想是迭代地从字典中选择原子，并计算相应的系数，使得这些原子的线性组合与测量数据之间的差别逐渐缩小。以最基本的正交匹配追踪算法为例，设当前迭代结果为xk，已选取原子1,.N,的一个子集，令Wc=1,.N,W；设残差的索引为W，它是7 压缩感知毕业论文 rk=y-Fxk，计算rk与字典中的原子的相关性FTrk，取其中绝对值最大的元素，即为索引j；令更新后的索引集为W=WÈj，则更新后的信号为 xk+1=argminy-FWx，其中FW为按W索引F的各列后得到的子矩阵。由于FWx2是线性无关的，因此xk+1可以通过最小二乘计算得到。 其它的贪婪算法还有StOMP算法、Regularized OMP(ROMP)算法以及Compressive Sampling Matching Pursuit(CoSaMP)等。 在计算复杂度方面，从形式上看，若字典F是显示的，则贪婪算法涉及矩阵向量之间的乘法运算FTrk，其运算量为O(MN),若F具有隐式的快速变换，则计算量可显著降低。此外，求解xk+1的最小二乘过程可以利用FW的QR分解，其运算量为O(MK)。 注：称F是显式的，若Fx和FTr的运算可以通过矩阵和向量的乘法运算完成；相对应的，称F是隐式的，是指Fx和FTr的运算可以通过函数运算完成。 2）凸优化 基本思想是将和“松弛”为凸优化问题，利用凸函数性质，实现多项式时间内的稀疏重构。由于l1范数是最接近l0范数的凸函数，因此常将l0范数松弛为l1范数，文献27-31讨论了l0范数与l1范数之间的等价特性条件。 内点法为最早的l1范数凸优化求解方法，可用的软件包有SeDuMi和MOSEK等。但总的来说，内点法的重构结果受参数选取影响较大，且计算复杂度高，不适用于二维像等大数据量应用问题。 梯度下降类算法是一阶精度的l1范数凸优化求解方法，该类算法在每步的迭代中计算残差的梯度： Txtemp=argmin(z-xk)FT(Fxk-y)+akz-xkx22+tz1xk+1=xk+gk(xtemp-xk) 其中t，ak，gk均为控制参数。 其它类似的方法包括TwIST和GPSR等。当测量矩阵满足可重构条件时，这些方法能迅速识别信号中稀疏分量的位置，并重构原信号。 3)其它算法 一些非凸优化算法，如将l0范数松弛为lp，0<p<1范数；或者通过先验分布引入稀疏性，再用贝叶斯方法实现稀疏重构；此外，还有一些启发式算法,用借鉴图模型和编码理论中的belief-propagation和message-passing技术。 重构条件的研究就是讨论稀疏重构解得唯一性条件。设x1和x2是两个稀疏解，则有：Fx1=Fx2ÞF(x1-x2)=0，即矩阵F将稀疏度为2K的信号x1-x2映8 压缩感知毕业论文 射为零，这意味着当且仅当F的每个2K列子矩阵均为单射时，稀疏解是唯一的。在实际运用中，不仅要求稀疏解是唯一的，还要求其实稳定的，假设测量数据有扰动Ñy，其导致解的变化Ñx满足：Ñy=FÑx，稳定性是指微小的Ñy不会导致较大Ñx。 约束等距性是压缩感知理论中用以描述重构条件的指标，但对于给定的测量矩阵F，验证其是否满足RIP是NP难解问题。此外，稀疏重构理论中常用的字典相关性，也可以用于重构条件的描述，它的优点是计算简单，缺点是得到的条件不是紧致的，如根据相关性理论，M个测量数据至多可恢复稀疏度K=O(M)的信号，而根据RIP当测量矩阵为特定的随机矩阵时，可重构信号的稀疏度可以放宽为K=O(M/log(N)。 2.3 压缩感知在光学成像中的应用 压缩感知应用于光学成像的首个实际系统是Rice大学Baraniuk等建立的“单相素相机”，其原理图与实际系统如图2.3.1 图2.3.1 单相素相机与实际系统图 左图中，入射光线经过第一个透镜之后进入成像系统，照射在放置于像平面的数字微镜设备阵列上。DMD阵列由数百万个尺寸为um量级的微小反射镜组成，每个反射镜的角度可以独立控制，从而可以控制其上的反射光线的方向。DMD阵列的反射光线经过第二个透镜，其中仅一个方向的光线进入不具备空间分辨力的单相素光子探测器，经过AD转换后以数字信号的形式被记录下来。DMD上的每个微小反射镜的角度是可以控制的，频率可以到达103Hz，所有小反射镜角度控制的一次实现称为一个“测量模式”。每个“测量模式”下，探测采集一个数字信号，为了获得足够多的数9 压缩感知毕业论文 据，需要进行多次测量。“单相素相机”实际系统如右图所示，该系统目前已可获取原理验证性图像。值得一提的是rice大学的单像素相机硬件成本昂贵，重建算法效率低下，还有很大的改进空间。 其它基于压缩感知原理建立的成像系统有：Compressive Structured Light for Recovering Inhomogeneous Participating Media, Compressive Dual Photography, Random Lens Imager和Tranform Imager等。 特别地，美国国防高级研究计划局资助的Multiple Optical Non -Redundant Aperture Generalized Sensors(MONTAGE)致力于通过有机结合光学系统、检测和后处理技术的最新进展，开发革命性的成像系统。Compressive Optical MONTAGE Photography Initiative(COMP-I)是MONTAGE计划下的一个子项目，其目标是在不损失成像系统分辨率的条件下，减小焦距，制造“超薄”成像系统。目前，已实现了一个5mm的环形孔径透镜，其分辨率与40mm焦距的传统成像系统相当。 “超薄”成像的关键技术之一是所谓的焦平面编码，即在焦平面处设置二值幅度调制掩膜，固定于探测器上，以完成对焦平面光场的某种变换，而探测器测量的是这种变换下的“系数”。最后在计算机上将测量数据逆变换得到原图像。 在光学成像领域，将与之相类似的技术称之为“计算成像”。传统的成像系统利用透镜或反射镜系统形成图像，并利用探测器进行采样。数据处理在传统概念中被认为是后处理过程，并不纳入成像系统设计的考虑之中。随着电子学的发展，在探测器和光场操控、编码方面取得了重大的进展；另一方面，光学系统的设计却受限于信息光学中物理定理的限制，为了提高分辨率，体积重量不断增加。因此，现代成像系统的设计不能仅考虑前端的光学系统，还需考虑探测器和图像重构的因素。“计算成像”的概念就是在这样的背景下提出的，它同时需要光学系统、采样以及图像重构的技术，于压缩成像有着异曲同工之处。 目前，已有若干类似的“计算成像”原理验证系统。Duke大学Duke Image and Spectroscopy Program(DISP)小组在DARPA MONTAGE计划的支持下，在多路光学技术中开展了很多研究。例如，验证了红外相机可以采用同时利用多路小孔径光学透镜收集若干低分辨率图像，但不是当长焦距大孔径透镜，是想高分辨率成像。 如上所述，CS测量矩阵的实现硬件是将CS推向实用的必备条件。在RIP理论指导下，莱斯大学R. Baraniuk教授等研制的单像素相机和A/I转换器。随后，有多种CS硬件相继报道，例如，麻省理工学院教授等人研制的MRI RF脉冲设备，麻省理工学院W. T. Freeman教授等人研制的编码孔径相机，耶鲁大学研制的超谱成像仪，伊利诺伊州立大学O. Milenkovic等人研制的DNA微阵列传感器，我们课题组研制的CS滤波器和混沌腔，等等。这些CS硬件实现将CS向实用化推进了一大步，然而仅10 压缩感知毕业论文 能处理有限维信号，无法处理无限维信号。另外，由于缺乏有效的CS矩阵判别理论，除rice大学的单像素相机(硬件成本昂贵，重建算法效率低下)外，其它硬件均缺乏严格的理论分析。 11 压缩感知毕业论文 第3章 压缩感知基本理论 信号的稀疏重构主要包括三个方面内容：1）信号的稀疏表示方法，它是重构的前提；2）稀疏约束项的构造，它在一定程度上决定了重构所需的压缩采样数量和重构过程的复杂度；3）含稀疏约束项的最优化求解方法，它决定了重构的计算复杂度、精度和稳健性。信号的压缩采样理论主要讨论为使稀疏重构能精确、稳定恢复原信号，测量矩阵需满足的条件。 3.1 压缩感知背景 考虑一个实值的有限长一维离散时间信号X， 可以看作为一个RN空间N ×1 维的列向量， 元素为X n ， n = 1 ，2 ， N。RN空间的任何信号都可以用N ×1N维的基向量Yii=1的线性组合表示。 为简化问题，假定这些基是规范正交的。把向N量YiiN 的基矩阵: = Y1,Y2,.,YN ， 于是任意信号X =1作为列向量形成N ×都可以表示为： X=到： 其中是投影系数Q=qi=<X,Yi>构成的N ×1 的列向量。反变换后得Q=YTX 显然， X 和是同一个信号的等价表示， X是信号在时域的表示，则是信qiYi or Xåi=1N=YQ 号在 域的表示。 如果的非零个数比N 小很多，则表明该信号是可压缩的。一般而言，可压缩信号是指可以用K 个大系数很好地逼近的信号， 即它在某个正交基下的展开的系数按一定量级呈现指数衰减， 具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。 变换编码在数据采样系统中，比如数码相机，发挥了重要作用。 在这些系统中， 采样速率高但信号是可压缩的，采样得到N 点采样信号X；通过Q=YTX变换后计算出完整的变换系数集合i ；确定K个大系数的位置，然后扔掉N-K个小系数；对K个大系数的值和位置进行编码，从而达到压缩的目的。 12 可压缩信号高速采样变换压缩第一步第二步第三步传输、存储重构信号图3.1 传统方法压缩过程 压缩感知毕业论文 但这种传统的信号编解码方法存在显著的一些缺点： 考虑到奈奎斯特采样定理，为了能获得很好的信号分辨率，采样间隔会取的很小，这样便造成了原始信号长度会很长，因此变换过程也会消耗较长的时间。 K个需要保留的重要分量的位置，是随着信号的不同而不同的。因此，这种策略是“自适应”的，而且需要分配多余的空间来存储这些位置。 一旦在传输的过程中K 个分量的某几个丢失了，后果便可想而知。例如按照以上方法制作一个音频设备，便会存在以下的一些缺点：带来电力的大量消耗和用户的不满、带来存储空间的增加、带来较差的抗干扰能力等。 针对上述所遇到的问题，压缩感知理论指出：对于信号XÎRN+1，如果它在某个正交变换基上是可进行稀疏变换的，则选取一个与不相关的M × N 维观测矩阵来观测得到原始信号的M个降维观测向量Y，即Y = ，其中FÎRM´N，是原始信号在正交变换基 域的稀疏表示形式。拥有了这M 个测量值Y 和观测矩阵，最后通过求解一个优化问题便可以得到原始信号的精确重构或近似逼近。重构算法的问题是基于如下严格的数学最优化问题： 目标函数：minQ，且满足等式约束：FYTX=Y 0综合以上所述，得到了基于压缩感知理论框架下的信号编解码流程图，如图 3.2所示。 原始信号X稀疏变换观测得到降维向量重构信号图3.2 压缩感知理论框架下的信号编解码流程 3.2 压缩感知理论 3.2.1压缩感知的前提条件稀疏性和不相干性 CS隐含的两个基本前提：稀疏性和不相关性。前者属于信号的性质，后者和感知形式有关。 稀疏性：稀疏性表达了这样一个思想，一个连续时间信号的“信息速率”可能比由带宽所决定的香农采样率要低很多，或者，一个离散时间信号所依赖的自由度数目远远低于它的长度。更准确地说，CS利用了这样一个事实，即许多自然信号在某个合适的基下具有简洁的表达。 不相关性：不相关性说明用于采样信号的波在基下有很稠密的表达。不相关性表达了这样的思想，正如时间域的Dirac或者冲击信号可以在频域展开那样，在基下13 压缩感知毕业论文 具有稀疏表示的信号一定可以在获得它们的某个域中展开。 1 稀疏性 众所周知，任意长度为N 的离散信号X 都可以表示为一系列基函数的叠加， 即可以在任何正交基下用下式表示： 其中Y由一组基向量Yii=1构成的正交基，例如，sinusoids，尖峰spikes、NB-splines，wavelets。Q为展开系数。展开系数大，说明信号和基足够相似。如果信号在基Y下的展开系数在很小的集合上有值，我们就说该信号在Y域是稀疏的，如果有值序列集中在一个小范围内，那么我们就说该信号是可以压缩的。本章我们将集中研究具有稀疏表示的信号，其中X是K个基向量的线性组合，K<<N。也就是说，min<f,g>0中仅有K个非零qi，另外N -K个都是零。许多自然信号在一些基下有简洁的表达。图3.3是一幅具有N个像素点的coins图像向量XÎRN，我们在9/7小波基Y=y1,y2,.,yN,下展开该向量，如，其中Y是y1,y2,.,yN,为列向量构成的N´N的矩阵，是正交基。图3.3是coins图像的9/7小波系数在一维下的表示。图2.3展示了这样一个事实：将图像在9/7小波变换域丢掉93.75%的小系数后得到的逼近图像尽管PSNR只有29.09dB，但肉眼很难察觉到失真。由此可见，尽管原图中几乎所有的像素都是非零值，它在9/7小波域中却是稀疏的：大部分小波系数都很小，少数的大系数就可以捕获信号的大部分信息。 本例中仅仅保留展开中Q的K(K=(116)N)个大系数得到XK=YQK，其中QK表示系数向量的除K个大系数外其余置0的向量。该向量从严格意义上说是稀疏的，因为K<<N ，即除了极少数项外其余均为0。 现在稀疏的含义很清楚了：如果x在某个变换域下是稀疏或者可压缩的，就意味着将x的系数qi,i=1,.,N按幅值大