压缩感知的原理和应用

IntroductiontoComprehensiveSensingGuotaiWang2013-5-3contentsBackground&Problem1TheCompressiveSensing2Application3contentsBackground&Problem1TheCompressiveSensing2Application31.1信号采样•信息技术飞速发展信息需求量剧增•Nyquist采样定理：–采样速率需达到信号带宽的两倍以上才能精确重构信号。•带宽增加采样速率和处理速率增加•弊端–采样硬件成本昂贵–获取效率低下–对宽带信号处理的困难日益加剧1.2信号的压缩和传输•传统压缩方法•为了降低成本–将采样的数经压缩后以较少的比特数表示信号–很多非重要的数据被抛弃•缺点–这种高速采样再压缩的方式浪费了大量的采样资源–一旦压缩数据中的某个或某几个丢失，可能将造成信号恢复的错误1.3亟待解决的问题问题1：能否以远低于Nyquist采样定理要求的采样速率获取信号，而保证信息不损失，并且可以完全恢复信号？问题2：能否将对信号的采样转化为对信息的采样，即直接采集不被丢弃的信息？1.4压缩感知的理论框架•压缩感知的核心思想–压缩和采样合并进行，远小于传统采样方法的数据量–突破了Nyquist采样定理的瓶颈–使高分辨率的信号采集成为可能名词解释：压缩感知—直接感知压缩后的信息基本方法：信号在某一个正交空间具有稀疏性（即可压缩性），就能以较低的频率（远低于奈奎斯特采样频率）采样该信号，并可能以高概率重建该信号。contentsBackground&Problem1TheCompressiveSensing2Application3研究现状2006《RobustUncertaintyPrinciples：ExactSignalReconstructionfromHighlyIncompleteFrequencyInformation》TerenceTao、EmmanuelCandès2006《CompressedSensing》DavidDonoho2007《CompressiveSensing》RichardBaraniuk2.1压缩感知的前提稀疏性的定义：一个实值有限长的N维离散信号，由信号理论可知，它可以用一个标准正交基的线性组合来表示，假定这些基是规范正交的，那么有其中，若在基上仅有个非零系数时，称为信号的稀疏基，是稀疏(K-Sparsity)的。1NxR12,,,TkK1Nkkkx,kkxxKKNkxxK2.2压缩感知流程介绍长度为N的信号在正交基上的变换系数是稀疏的；用一个与基不相关的观测基对系数向量进行线性变换，并得到观测向量利用优化求解的方法从观测集合中精确或高概率地重构原始信号。x:()MNMN:1YMx1，稀疏表示•信号是可压缩的或在某个变换域是稀疏的;2，随机测量•就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上;3，重构算法•然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。2.2压缩感知流程介绍长度为N的信号在正交基上的变换系数是稀疏的；用一个与基不相关的观测基对系数向量进行线性变换，并得到观测向量利用优化求解的方法从观测集合中精确或高概率地重构原始信号。x:()MNMN:1YMx1，稀疏表示•信号是可压缩的或在某个变换域是稀疏的;2，随机测量•就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上;3，重构算法•然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。2.2压缩感知流程介绍长度为N的信号在正交基上的变换系数是稀疏的；用一个与基不相关的观测基对系数向量进行线性变换，并得到观测向量利用优化求解的方法从观测集合中精确或高概率地重构原始信号。x:()MNMN:1YMx1，稀疏表示•信号是可压缩的或在某个变换域是稀疏的;2，随机测量•就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上;3，重构算法•然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。第一步：信号的稀疏表示如图是一个稀疏度为3的稀疏变换，,在时域基本都是非零值，但将其变换到域时，非零值就只有3个了，数目远小于原来的非零数目，实现了信号的稀疏表示。xx2.2压缩感知流程介绍如何找到信号的最佳稀疏域呢？1、基函数字典下的稀疏表示：寻找一个正交基使得信号表示的稀疏系数尽可能的少。比较常用的稀疏基有：高斯矩阵、小波基、正（余）弦基、Curvelet基等。2、超完备库下的稀疏表示：用超完备的冗余函数库来取代基函数目的是从冗余字典中找到具有最佳线性组合的K项原子来逼近表示一个信号称作信号的稀疏逼近或高度非线性逼近。2.2压缩感知流程介绍第二步：观测矩阵的设计观测器的目的是采样得到个观测值，并保证从中能够重构出原来长度为的信号或者稀疏基下的系数向量。观测过程就是利用观测矩阵的个行向量对稀疏系数向量进行投影，得到个观测值，即MNxMNMMTYxx观测矩阵需要满足的条件2.2压缩感知流程介绍第三步：信号重构首先介绍下范数的概念。向量的p-范数为：当p=0时得到0-范数，它表示上式中非零项的个数。由于观测数量，不能直接求解，在信号可压缩的前提下，求解病态方程组的问题转化为最小0-范数问题：11Nppipiss0mins.t.TTxYxMNx2.2压缩感知流程介绍对于0-范数问题的求解是个NP问题，需要列出所有非零项位置的种组合的线性组合才能得到最优解，在多项式时间内难以求解，而且也无法验证其可靠性。Chen，Donoho和Saunders指出求解一个优化问题会产生同等的解。于是问题转化为：Candes等指出，要精确重构k稀疏信号x，测量次数M（必须满足M=O(k·logN)，并且矩阵Φ必须满足约束等距性条件(RestrictedIsometryPrinciple)。求解该最优化问题，得到稀疏域的系数，然后反变换即可以得到时域信号。1min..TTxstYx2.2压缩感知流程介绍重构算法（1）匹配追踪系列：匹配追踪（MatchingPursuit,MP）正交匹配追踪(OrthogonalMatchingPursuit,OMP)稀疏自适应匹配追踪(SparseAdaptiveMP,SAMP)正则化正交匹配追踪(RegularizedOMP,ROMP)等（2）方向追踪系列：梯度追踪(GradientPursuit,GP)共轭梯度追踪(ConjugateGP,CGP)近似的共轭梯度追踪(ApproximationCGP,ACGP)贪婪算法凸优化算法（1）基追踪法(BasisPursuit,BP)（2）最小角度回归法(LeastAngleRegression,LARS)（3）梯度投影法(GradientProjectionforSparseReconstruction,GPSR)另类算法（1）Bayesian类的统计优化算法2.2压缩感知流程介绍contentsBackground&Problem1TheCompressiveSensing2Application33.1单像素相机压缩感知理论带来了信号采样理论的变革，具有广阔的应用前景，包括压缩成像、模拟信息转换、生物传感等。压缩感知应用于光学成像的首个实际系统是Rice大学的“单像素相机”入射光线经过第一个透镜之后进入成像系统，照射在放置于像平面的数字微镜设备(DMD)阵列上。DMD阵列由数百万个尺寸为μm量级的微小反射镜组成，每个反射镜的角度可独立控制。DMD阵列的反射光线经过第二个透镜，其中仅一个方向的光线进入单像素光子探测器。3.1单像素相机•传统百万像素的相机需要百万个探测传感器。•而压缩传感数码相机只使用一个探测器来采光，然后跟捕获后的计算相结合来重构图像。•该相机直接获取的是M次随机线性测量值而不是获取原始信号的N个像素值，为低像素相机拍摄高质量图像提供了可能。3.2动态CT图像重建•Medicalimage&sparse–(1),Aremedicalimagessparse?–(2),Ifamedicalimageisnotsparse,canweusesometransformtomakeitsparse?Imagearenotsparseasshowninbythehistogramsofthepixelvalue.However,asubtractionoperationcanmaketheimagesignificantlysparser3.2动态CT图像重建•CSimagereconstructiontheory–Insteadofdirectlyreconstructingatargetimage,thesparsifiedversionisreconstructed.–Inthesparsifiedimage,significantlyfewerimagepixelshavesignificantimagevalues.–reconstructthesparsifiedimagefromanundersampleddatasetwithoutstreakingartifacts3.2动态CT图像重建•ReconstructdynamicCTimagesequences–thesameimagesliceorthesameimagevolumeissequentiallyscannedmanytimesinordertomeasurethedynamicalchangeintheimageobject.FBPPriorimage(Xp)XpwasutilizedtoconstraintheCSimagereconstructionmethod.Theproposedmethodisreferredtoaspriorimageconstrainedcompressedsensing(PICCS)Theproposedmethodisreferredtoaspriorimageconstrainedcompressedsensing(PICCS)InXp,thedynamicalinformationislostbutthestaticstructuresarewellconstructed3.2动态CT图像重建•ReconstructdynamicCTimagesequences–thesameimagesliceorthesameimagevolumeissequentiallyscannedmanytimesinordertomeasurethedynamicalchangeintheimageobject.FBPPriorimage(Xp)XpwasutilizedtoconstraintheCSimagereconstructionmethod.Theproposedmethodisreferredtoaspriorimageconstrainedcompressedsensing(PICCS)Theproposedmethodisreferredtoaspriorimageconstrainedcompressedsensing(PICCS)InXp,thedynamicalinformationislostbutthestaticstructuresarewellconstructed3.2动态CT图像重建•ReconstructdynamicCTimagesequences–thesameimagesliceorthesameimagevolumeissequentiallyscannedmanytimesinordertomeasu