压缩感知介绍PPT--最终版.ppt

压缩感知理论及应用,Compressed Sensing (CS)：Theory and Applications 南京航空航天大学电子工程学院 张 弓,1 背景介绍 1.1 传统采样理论介绍及问题提出 1.2 压缩感知理论的基本思想 2 压缩感知理论分析 2.1 压缩感知的前提 2.2 压缩感知流程介绍 第一步：信号的稀疏表示 第二步：观测矩阵的设计 第三步：信号重构 3 压缩感知应用 3.1 波形信号仿真分析 3.2 CS图像融合 3.3 单像素CS相机 3.4 CS雷达,1 背景介绍 1.1 传统采样理论介绍及问题提出 1.2 压缩感知理论的基本思想,1.1 传统采样理论介绍及问题提出,传统的基于Nyquist采样定理指导下的信息的处理主要表现在两个方面： 1、采样速率需达到信号带宽的两倍以上才能精确重构信号。这样的采样硬件成本昂贵，获取效率低下，对宽带信号处理的困难日益加剧。 2、在实际应用中，为了降低成本，人们常将采样的数据经压缩后以较少的比特数表示信号，而很多非重要的数据被抛弃，这种高速采样再压缩的方式浪费了大量的采样资源，另外一旦压缩数据中的某个或某几个丢失，可能将造成信号恢复的错误。,1 背景介绍,而现实生活中，随着信息技术的高速发展，信息量的需求增加，携带信息的信号所占带宽也越来越大 这就大大考验了数字化社会对信息处理的能力，包括：数据存储、传输和处理速度，基于Nyquist采样的理论遭到严峻的考验。,1 背景介绍,能否以远低于Nyquist采样定理要求的采样速率获取信号，而保证信息不损失，并且可以完全恢复信号？ 即能否将对信号的采样转化为对信息的采样？,一个亟待解决的问题：,1 背景介绍,1.2 压缩感知理论的基本思想,一种新的理论Compressed Sensing(CS,压缩感知，亦称压缩传感)。 由Candes、Romberg、Tao和Donoho等人在2004年提出，2006年才发表文献 基本思想： 1、信号是可压缩的或在某个变换域是稀疏的; 2、就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上; 3、然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。,1 背景介绍,2 压缩感知理论分析 2.1 压缩感知的前提 2.2 压缩感知流程介绍 2.3 第一步：信号的稀疏表示 2.4 第二步：观测矩阵的设计 2.5 第三步：信号重构,2.1 压缩感知的前提,稀疏性的定义： 一个实值有限长的N维离散信号 ，由信号理论可知，它可以用一个标准正交基 的线性组合来表示，假定这些基是规范正交的，其中 表示矩阵 的转置，那么有 其中 ，若 在基 上仅有 个非零系数 时，称 为信号 的稀疏基， 是 稀疏(K-Sparsity)的。,2 压缩感知理论分析,E.Candes等人证明了：信号的稀疏性是CS的必备条件。 信号是可压缩的或在某个变换域是稀疏的，这个条件的限制等同于信号带宽对于Nyquist采样定理的约束。,2 压缩感知理论分析,2.2 压缩感知流程介绍,长度为N的信号 在正交基 上的变换系数是稀疏的； 用一个与基 不相关的观测基 对系数向量进行线性变换，并得到观测向量 利用优化求解的方法从观测集合中精确或高概率地重构原始信号 。,2 压缩感知理论分析,如同信号带宽对于Nyquist，信号的稀疏性是CS的必备条件； 如同Nyquist采样规则对于Nyquist-Shannon采样定理，CS的关键是非相关测量（该测量称为测量矩阵），他们都是信号得以精确恢复的条件； 如同Fourier变换对于Nyquist，非线性优化是CS重建信号的手段。,2 压缩感知理论分析,第一步：信号的稀疏表示,如图是一个稀疏度为3的稀疏变换， ,在时域 基本都是非零值， 但将其变换到 域 时，非零值就只有3 个了，数目远小于 原来的非零数目，实 现了信号的稀疏表 示。,2 压缩感知理论分析,如何找到信号的最佳稀疏域呢？,这是压缩感知理论的基础和前提，也是信号精确重构的保证。对稀疏表示研究的热点主要有两个方面： 1、基函数字典下的稀疏表示： 寻找一个正交基使得信号表示的稀疏系数尽可能的少。比较常用的稀疏基有：高斯矩阵、小波基、正（余）弦基、Curvelet基等。Candes和Tao经研究发现光滑信号的Fourier 系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor 系数及具有不连续边缘的图像信号的Curvelet 系数等都具有足够的稀疏性,可以通过压缩感知理论恢复信号。 2、超完备库下的稀疏表示： 用超完备的冗余函数库来取代基函数，称之为冗余字典，字典中的元素被称之为原子，目的是从冗余字典中找到具有最佳线性组合的K项原子来逼近表示一个信号，称作信号的稀疏逼近或高度非线性逼近。,2 压缩感知理论分析,超完备库下的稀疏表示涉及到两个问题： 一是如何构造这样一个适合某一类信号的冗余字典； 二是在已知冗余字典的前提下如何设计快速有效的分解方法来稀疏地表示某一个信号。 右图为一些不 同的字典,2 压缩感知理论分析,第二步：观测矩阵的设计,观测器的目的是采样得到 个观测值，并保证从中能够重构出原来长度为 的信号 或者稀疏基下的系数向量 。 观测过程就是利用 观测矩阵的 个行向量对稀疏系数向量进行投影，得到 个观测值，即,2 压缩感知理论分析,2 压缩感知理论分析,观测矩阵要满足什么样的条件呢？,从上式中求出 是一个线性规划问题，但由于方程的个数少于未知数的个数 ，这是一个病态问题 但如果 具有稀疏性，则有可能求出确定解。Candes、Tao等人提出必须保证观测矩阵不会把两个不同的 项稀疏信号映射到同一个采样几何中，这就要求从观测矩阵中抽取的每个列向量构成的矩阵是非奇异的， 这跟有限等距特性(RIP)条件的要求是一致的。 R.Baraniuk将上述条件简化为如果保证观测矩阵和稀疏基不相干，则在很大概率上满足RIP性质。不相干是指 不能用 稀疏表示，不相干性越强，互相表示时所需的系数越多。,2 压缩感知理论分析,第三步：信号重构,首先介绍下范数的概念。向量的p-范数为： 当p=0时得到0-范数，它表示上式中非零项的个数。 由于观测数量 ，不能直接求解，在信号 可压缩的前提下，求解病态方程组的问题转化为最小0-范数问题：,2 压缩感知理论分析,对于0-范数问题的求解是个NP问题，需要列出所有非零项位置的种组合的线性组合才能得到最优解，在多项式时间内难以求解，而且也无法验证其可靠性。 Chen，Donoho和Saunders指出求解一个优化问题会产生同等的解。于是问题转化为： 或者： 求解该最优化问题，得到稀疏域的系数，然后反变换即可以得到时域信号。,2 压缩感知理论分析,目前出现的重构算法主要可归为三大类：,1)第一类贪婪算法：这类算法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号，典型的贪婪算法-MP算法，贪婪算法是针对组合优化提出, 目前已发展了多种变形，例如，OMP, OOMP, CosMP等。该类重建算法速度快, 然而需要的测量数据多且精度低。 2)第二类凸优化算法：这类方法是将非凸问题转化为凸问题求解找到信号的逼近，如BP算法，梯度投影方法等。该类算法速度慢，然而需要的测量数据少且精度高。 3)第三类组合算法：这类方法要求信号的采样支持通过分组测试快速重建，如代表性方法Sparse Bayesian。该类方法位于前两者之间。,2 压缩感知理论分析,3 压缩感知应用 3.1 波形信号仿真分析 3.2 CS图像融合 3.3 单像素CS相机 3.4 CS雷达,3.1 波形信号仿真分析,基于CS理论的一个简单的信号分析。 信号长度为N=256，稀疏度为K=7，测量数M=32。信号为三个频率叠加的正弦信号，傅里叶正交变换矩阵作为系数矩阵，高斯矩阵来测量，并用OMP算法重构原信号。,3 压缩感知应用,原信号与恢复结果对照图：,3 压缩感知应用,3.2 CS图像融合,图像融合是对来自单一传感器不同时间、不同环境下获取的图像或由多个传感器同一时间获取的信息进行多级别、多层次的处理与综合，从而获得更丰富、更精确、更可靠的有用信息。 图像融合的目的是提高图像显示的质量、实现图像的特征提取、图像去噪、目标识别和跟踪以及图像的三维重构。 大部分图像的稀疏特性为CS的应用带来可能，同时CS的引入为图像的融合在计算速度、融合策略上都带来了新的飞跃。,3 压缩感知应用,图像融合结果图：,3 压缩感知应用,3.3 单像素CS相机,运用压缩感知原理，RICE大学成功研制了单像素CS相机。 传统百万像素的相机需要百万个探测传感器，而压缩传感数码相机只使用一个探测器来采光，然后跟捕获后的计算相结合来重构图像。这种样机的镜头由两部分组成：一个光电二极管和一个微镜阵列。 该相机直接获取的是M次随机线性测量值而不是获取原始信号的N 个像素值，为低像素相机拍摄高质量图像提供了可能。,3 压缩感知应用,“数字微镜阵列”完成图像在伪随机二值模型上的线性投影的光学计算，其反射光由透镜聚焦到单个光敏二极管上，光敏二极管两端的电压值即为一个测量值y，将此投影操作重复M次，即得到测量向量Y， 然后用最小全变分算法构建的数字信号处理器重构原始图像x。 数字微镜器件由数字电压信号控制微镜片的机械运动以实现对入射光线的调整，相当于随机观测矩阵。,3 压缩感知应用,字母R的 实验结果：,3 压缩感知应用,3.4 CS雷达,在雷达目标探测中，目标相对于背景高度稀疏，与复杂的雷达系统、海量数据呈现极度的不平衡，这就为CS技术在雷达目标探测与识别的应用提供了必要的条件。 3.4.1 CS与传统的高分辨雷达 3.4.2 CS与MIMO雷达 3.4.3 CS与雷达成像,3 压缩感知应用,3.4.1 CS与传统的高分辨雷达,CS雷达的三个关键点 （1）发射信号必须是充分不相关的； （2）在CS方法中，不需要使用匹配滤波器； （3）目标场景可以恢复是在假设目标满足稀疏性约束的条件下。,3 压缩感知应用,3.4.1 CS与传统的高分辨雷达,CS技术很重要的思想是设计一个观测矩阵 ，用来表示稀疏信号的字典集 ，并且 与 是不相关的。利用这个思想设计出CS雷达接收机如下图所示。,3 压缩感知应用,假设空间有若干个稀疏目标，将目标所在的距离向与方位向分割成网格形式。CS雷达可以检测的目标数量 ， 为稀疏单元数目。如果 ，则可以采用CS理论，通过优化问题求解，精确分辨出空间的多个目标。,3 压缩感知应用,3.4.2 CS与MIMO雷达,2004年Fishler等人提出了多输入多输出(Multiple Input Multiple Output，MIMO)雷达的概念 MIMO雷达收发阵列配置图,3 压缩感知应用,3.4.2 CS与MIMO雷达,文献Yao Yu, Athina P. Petropulu, H. Vincent Poor, MIMO Radar Using Compressive Sampling, IEEE Journal Of Selected Topics in Signal Processing, Vol. 4, NO. 1, FEB 2010基于小规模的无线网络将CS理论应用于非相参MIMO雷达系统, 求得目标的角度和多普勒解。 文献Chun-Yang Chen and P. P. Vaidyanathan, Compressed Sensing in MIMO Radar, Signals, Systems and Computers, 2008 42nd Asilomar Conference on，26-29 Oct. 2008结合MIMO雷达目标在距离-多普勒-角度域的稀疏特点,研究了CS在相参MIMO雷达系统中的信号重构和波形优化问题。 文献Yao Yu, Athina P. Petropulu and H. Vincent Poor, Compressed Sensing for MIMO Radar . ICASSP 2009.已经开展了CS用于MIMO雷达的参数估计。,3 压缩感知应用,对于均匀线阵的MIMO雷达信号模型，利用CS方法估计目标波达方向(Direction of Arrival，DOA)，可以高概率的精确估计目标的DOA。 均匀线阵MIMO雷达估计结果1 均匀线阵MIMO雷达估计结果2,3 压缩感知应用,分布式压缩感知（Distributed Compressive Sensing, DCS）与MIMO雷达,相参MIMO雷达系统通过多发多收形成大数量的虚拟阵列，在发射机、目标以及接收机之间构成对目标的分布式探测系统，这与分布式压缩感知（DCS）的思想不谋而合。 如果多个信号都在某个变换基下是稀疏的,并且这些信号彼此相关,那么每个信号都能够通过测量矩阵进行联合压缩测量，利用优化方法对待测量进行联合重构。,3 压缩感知应用,分布式压缩感知（DCS）与MIMO雷达,（1）基于MIMO雷达体系的DCS变换基构造,3 压缩感知应用,（2）联合稀疏表示 构造压缩测量矩阵 对接收信号 进行联合稀疏表示，即是充分利用接收信号自身以及接收信号之间的相关性信息，对变换域系数进行联合编码，对接收信号进行降低冗余度的信息融合 。,分布式压缩感知（DCS）与MIMO雷达,3 压缩感知应用,（3） DCS-MIMO联合重构算法 求解欠定方程的处理过程，实现DCS-MIMO雷达信号重构。 常采用的方法有贪婪算法、粒子群算法、模拟退火算法等优化算法。,分布式压缩感知（DCS）与MIMO雷达,3 压缩感知应用,3.4.3 CS与雷达成像,基于CS的SAR成像需要解决的主要问题有: 目标场景的稀疏基设计， 非相关测量 最优化重构算法等。,3 压缩感知应用,3.4.3 CS与雷达成像,实际场景信号的构成模式比点目标模型要复杂得多； 大场景雷达成像，由于噪声的缘故，在实际雷达系统中非相关测量的设计是一个有待解决的问题 ； 压缩感知需要求解一个非线性最优化问题，即需要较高的信噪比，然而大场景雷达成像的数据量特别大，且信噪比很差。因此，如何利用CS实施大场景雷达成像是一件非常具有挑战性的课题。,3 压缩感知应用,穿墙雷达成像和探地雷达成像 余慧敏等 压缩感知理论在探地雷达三维成像中的应用 电子与信息学报，2010 Richard Baraniuk et al， Compressive Radar Imaging, Preprint, 2008 A. Gurbuz, et al, Compressive sensing for GPR imaging, Preprint, 2008,3 压缩感知应用,3.4.3 CS与雷达成像,穿墙雷达成像和探地雷达成像 /110050241.html,3 压缩感知应用,3.4.3 CS与雷达成像,基于压缩感知的含旋转部件目标ISAR成像方法,3 压缩感知应用,成像结果对比,利用RD算法成像图,基于Hough变换剔除微多普勒成像图,基于CS方法成像图 （压缩60%）,基于CS方法成像图 （压缩80%）,3 压缩感知应用,3.4.5 CS在雷达目标检测与识别中的应用,CS在雷达目标识别中的应用，可涉及到两大