压缩感知的原理和应用.ppt

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,contents,Background&Problem,1,The Compressive Sensing,2,Application,3,contents,Background&Problem,1,The Compressive Sensing,2,Application,3,1.1,信号采样,信息技术飞速发展 信息需求量剧增,Nyquist,采样定理：,采样速率,需达到,信号带宽,的两倍以上才能精确重构信号。,带宽增加 采样速率和处理速率增加,弊端,采样硬件成本昂贵,获取效率低下,对宽带信号处理的困难日益加剧,1.4,压缩感知的理论框架,压缩感知的核心思想,压缩和采样合并进行，远小于传统采样方法的数据量,突破了,Nyquist,采样定理的瓶颈,使高分辨率的信号采集成为可能,名词解释,：压缩感知,直接,感知压缩后的信息,基本方法,：,信号在某一个正交空间具有稀疏性（,即可压缩性,），就能以较低的频率（,远低于奈奎斯特采样频率,）采样该信号，并可能以高概率重建该信号。,contents,Background&Problem,1,The Compressive Sensing,2,Application,3,研究现状,2006Robust Uncertainty Principles,：,Exact Signal Reconstruction from,Highly Incomplete Frequency Information,Terence Tao,、,Emmanuel Cands,2006Compressed SensingDavid Donoho,2007Compressive SensingRichard Baraniuk,2.1,压缩感知的前提,稀疏性的定义：,一个实值有限长的,N,维离散信号 ，由信号理论可知，它可以用一个标准正交基,的线性组合来表示，假定这些基是规范正交的，那么有,其中 ，若 在基 上仅有 个非零系数 时，称 为信号 的稀疏基，是 稀疏,(K-Sparsity),的。,2.2,压缩感知流程介绍,长度为,N,的信号 在正交基 上的变换系数是稀疏的；,用一个与基 不相关的观测基 对系数向量进行线性变换，并得到观测向量,利用优化求解的方法从观测集合中精确或高概率地重构原始信号 。,2.2,压缩感知流程介绍,长度为,N,的信号 在正交基 上的变换系数是稀疏的；,用一个与基 不相关的观测基 对系数向量进行线性变换，并得到观测向量,利用优化求解的方法从观测集合中精确或高概率地重构原始信号 。,2.2,压缩感知流程介绍,长度为,N,的信号 在正交基 上的变换系数是稀疏的；,用一个与基 不相关的观测基 对系数向量进行线性变换，并得到观测向量,利用优化求解的方法从观测集合中精确或高概率地重构原始信号 。,第一步：信号的稀疏表示,如图是一个稀疏度为,3,的稀疏变换，,在时域,基本都是非零值，,但将其变换到 域时，非零值就只有,3,个了，数目远小于原来的非零数目，实现了信号的稀疏表,示。,2.2,压缩感知流程介绍,如何找到信号的最佳稀疏域呢？,1,、基函数字典下的稀疏表示,：,寻找一个,正交基,使得信号表示的稀疏系数尽可能的少。,比较常用的稀疏基有：,高斯矩阵、小波基、正（余）弦基、,Curvelet,基等。,2,、超完备库下的稀疏表示,：,用超完备的冗余函数库来取代基函数,目的是从冗余字典中找到具有最佳线性组合的,K,项原子来逼近表示一个信号,称作信号的稀疏逼近或高度,非线性逼近,。,2.2,压缩感知流程介绍,第二步：观测矩阵的设计,观测器的目的是采样得到 个观测值，并保证从中能够重构出原来长度为 的信号 或者稀疏基下的系数向量 。,观测过程就是利用 观测矩阵的 个行向量对稀疏系数向量进行投影，得到 个观测值，即,观测矩阵需要满足的条件,2.2,压缩感知流程介绍,第三步：信号重构,首先介绍下范数的概念。向量的,p-,范数为：,当,p=0,时得到,0-,范数，它表示上式中非零项的个数。,由于观测数量 ，不能直接求解，在信号 可压缩的前提下，求解病态方程组的问题转化为最小,0-,范数问题：,2.2,压缩感知流程介绍,对于,0-,范数问题的求解是个,NP,问题,，需要列出所有非零项位置的种组合的线性组合才能得到最优解，在,多项式时间内难以求解,，而且也无法验证其可靠性。,Chen,，,Donoho,和,Saunders,指出求解一个优化问题会产生同等的解。于是问题转化为：,Candes,等指出，要精确重构,k,稀疏信号,x,，测量次数,M,（必须满足,M=O(k logN),，并且矩阵,必须满足约束等距性条件,(Restricted Isometry Principle),。,求解该最优化问题，得到稀疏域的系数，然后反变换即可以得到时域信号。,2.2,压缩感知流程介绍,重构算法,（,1,）匹配追踪系列：,匹配追踪（,Matching Pursuit,MP,）正交匹配追踪,(Orthogonal Matching Pursuit,OMP),稀疏自适应匹配追踪,(Sparse Adaptive MP,SAMP),正则化正交匹配追踪,(Regularized OMP,ROMP),等,（,2,）方向追踪系列：,梯度追踪,(Gradient Pursuit,GP),共轭梯度追踪,(Conjugate GP,CGP),近似的共轭梯度追踪,(Approximation CGP,ACGP),贪婪算法,凸优化算法,（,1,）基追踪法,(Basis Pursuit,BP),（,2,）最小角度回归法,(Least Angle Regression,LARS),（,3,）梯度投影法,(Gradient Projection for Sparse Reconstruction,GPSR),另类算法,（,1,）,Bayesian,类的统计优化算法,2.2,压缩感知流程介绍,contents,Background&Problem,1,The Compressive Sensing,2,Application,3,3.1,单像素相机,压缩感知理论带来了信号采样理论的变革，具有广阔的应用前景，包括压缩成像、模拟信息转换、生物传感等。,压缩感知应用于光学成像的首个实际系统是,Rice,大学的“,单像素相机,”,入射光线经过第一个透镜之后进入成像系统，照射在放置于像平面的数字微镜设备,(DMD),阵列上。,DMD,阵列由数百万个尺寸为,m,量级的微小反射镜组成，每个反射镜的角度可独立控制。,DMD,阵列的反射光线经过第二个透镜，其中仅一个方向的光线进入单像素光子探测器。,3.1,单像素相机,传统百万像素的相机,需要百万个探测传感器。,而压缩传感数码相机,只使用一个探测器来采光，然后跟捕获后的计算相结合来重构图像。,该相机直接获取的是,M,次,随机线性测量值而不是获,取原始信号的,N,个像素值，,为低像素相机拍摄高质量,图像提供了可能。,3.2,动态,CT,图像重建,Medical image&sparse,(1),Are medical images sparse?,(2),If a medical image is not sparse,can we use some transform to make it sparse?,Image are not sparse as shown in by the histograms of the pixel value.,However,a subtraction operation can make the image significantly sparser,3.2,动态,CT,图像重建,CS image reconstruction theory,Instead of directly reconstructing a target image,the,sparsified version is reconstructed,.,In the sparsified image,significantly,fewer image pixels,have significant image values.,reconstruct the sparsified image from an,undersampled,data set without streaking artifacts,3.2,动态,CT,图像重建,Reconstruct dynamic CT image sequences,the same image slice or the same image volume is sequentially scanned many times in order to measure the,dynamical change,in the image object.,FBP,Prior image(Xp),Xp was utilized to constrain the CS image reconstruction method.,The proposed method is referred to as prior image constrained compressed sensing(PICCS),The proposed method is referred to as prior image constrained compressed sensing(,PICCS,),In Xp,the dynamical information is lost but the static structures are well constructed,3.2,动态,CT,图像重建,Reconstruct dynamic CT image sequences,the same image slice or the same image volume is sequentially scanned many times in order to measure the,dynamical change,in the image object.,FBP,Prior image(Xp),Xp was utilized to constrain the CS image reconstruction method.,The proposed method is referred to as prior image constrained compressed sensing(PICCS),The proposed method is referred to as prior image constrained compressed sensing(,PICCS,),In Xp,the dynamical information is lost but the static structures are well constructed,3.2,动态,CT,图像重建,Reconstruct dynamic CT image sequences,the same image slice or the same image volume is sequentially scanned many times in order to measure the,dynamical change,in the image object.,FBP,Prior image(Xp),Xp was utilized to constrain the CS image reconstruction method.,The proposed method is referred to as prior image constrained compressed sensing(PICCS),The proposed method is referred to as prior image constrained compressed sensing(,PICCS,),In Xp,the dynamical information is lost but the static structures are well constructed,3.2,动态,CT,图像重建,3.3,快速,MR,成像,Sparsity:,there are relatively few significant pixels with nonzero values,.,Angiograms are extremely sparse,Transform sparsity:,have a sparse representation in terms of transformation,MRI,MRI measures Fourier coefficients,is whether it is possible to reconstruct by measuring only a,subset of k space,?,3.3,快速,MR,成像,the under sampled Fourier transform.,the linear operator that transforms form pixel representation into a sparse representation,m is the reconstructed image,y is the measured k-space data from scanner,3.3,快速,MR,成像,3.4,图像融合,将待融合图像进行,稀疏表示,用远小于原图像的数据量进行,融合,用,重构,算法将融合结果还原为原图像,可节省中间融合所需的计算量,更好地利用原图像中的内在联系,3.5,目标识别和跟踪,目标识别,如果训练样本充足，同类的且不在训练集中的测试样本可大致由训练集的线性组合表示。,若测试图像,属于某一类，则 是稀疏向量,目标跟踪,1,，对目标进行建模,2,，对后续帧图像进行相应的模型建立,两模型最相似问题,求取某相似参数的,N1,范数最小化问题,总结,压缩感知的理论依据,：,设长度为,N,的信号,X,在某个正交基上是,K-,稀疏,的，,如果能找到一个与不相关的,观测基,，,用观测基观测原信号得到,M,个观测值，,KMN,，,得到观测值,Y,，,那么可以利用最优化方法从观测值中高概率,重构,X,。,找到某个正交基,，信号在该基上稀疏,找到一个与不相关，且满足一定条件的观测基,对,Y,采用最优化重建，均是其约束。,以观测真实信号，得到观测值,Y,主要解决的问题,：,信号的稀疏表示,观测基的选取,重构算法的设计,Thank You!,