压缩感知新技术专题讲座(二)第3讲 压缩感知技术中的信号稀疏表示方法X周 彬1,朱 涛2,张雄伟3(1.解放军理工大学指挥自动化学院研究生2队,江苏南京210007;2.中国人民解放军66242部队,内蒙古锡林郭勒026000;3.解放军理工大学指挥自动化学院信息作战系)摘 要:信号的稀疏表示是信号分析领域的基本问题,也是近几年兴起的压缩感知理论的基础。
文章首先分析了信号稀疏表示的基本原理,然后介绍了当前信号稀疏表示的主要方法,并重点阐述了基于过完备字典的稀疏表示方法及其在压缩感知中的应用,最后总结了稀疏表示所面临的问题和未来发展方向。
关键词:稀疏表示;压缩感知;字典学习中图分类号:T N 911.7文献标识码:A 文章编号:CN 32-1289(2012)01-0085-05Sparse Representation of Signals in Compressive SensingZH OU Bin 1,ZH U T ao 2,ZH A N G X iong -w ei 3(1.Postg r aduate T eam 2ICA ,PL A U ST ,Nanjing 210007,China ; 2.U nit 66242of P LA ,Xiling uole 026000,China; 3.Depar tment of I nfo rm atio n O peration Studies ICA ,PL A U ST )Abstract :T he sparse representation is a basic problem in signal analy sis field and also thebasis o f the new emerging compressiv e sensing theory .The definitio n and principles of the sparserepresentation w ere firstly reviewed.And then some m ain m ethods o f the sparse representation,especially those based on the overco mplete dictionary w er e inv estig ated .The applications of thesparse repr esentation in CS w er e discussed.Some problem s to so lve were given and further devel-opm ent w as pointed out .Key words :sparse representation;com pressive sensing ;ov ercomplete dictionary 随着现代传感器技术的发展,许多领域面临着日益膨胀的海量数据,如地球物理数据、视频数据、天文数据、基因数据等。
如何实现对这些数据更为灵活、简洁的表达已成为一个倍受关注的问题。
传统的信号表示方法通常是基于正交基(如傅里叶基,小波基)的展开。
为了实现信号的灵活、简洁和自适应的表示,一种更好的信号分解方式是根据信号本身的特点,自适应地选择合适的基函数,来完成信号的分解,从而得到信号的一个非常简洁的表达,即稀疏表示。
由于信号的稀疏表示能在一定程度上自然地贴近信号的本质特征,因而对稀疏分解的研究有极其重要而深远的理论意义和广泛的应用价值。
目前,稀疏表示被广泛应用于信号处理和图像处理的各个领域,如图像压缩、音频压缩、噪声抑制、盲信号分离、地震数据处理、系统辨识、雷达成像处理等等。
尤其是近年来新兴起的压缩感知(com pressed sensing)理论[1,2],其优点就是针对可稀疏表示的信号,将传统的数据采集与数据压缩合二为一,在获取信号同时对数据进行压缩。
压缩感知理论的一个重要基础和前提就是选择信号的稀疏域,只有选择合适的基矩阵才能保证信号的稀疏度,从而保证信号的恢复精度。
由于压缩感知理论的提出和蓬勃发展,稀疏表示越来 第33卷第1期 2012年3月军 事 通 信 技 术Jour na l o f M ilitar y Co mmunicatio ns T echnolog y V ol.33N o.1M ar.2012X 收稿日期:2011-10-18;修回日期:2011-12-12作者简介:周 彬(1986-),男,博士生.越表现出它的优越性,许多人将目光投向这个领域,并进行了大量的研究,取得了广泛而深入的研究成果[3]。
1 信号稀疏表示1.1 信号的稀疏性 考虑R N 空间一个实值的有限长一维离散时间信号x ,假设{W i ûi =1,…,N }是R N 的一组基向量,则R N 空间的任何信号x 可以线性表示为x =∑Ni =1s i W i 或 x =7s (1)图1 信号在7域稀疏表示其中,7=[W 1ûW 2û…ûW N ]是N ×N 的基矩阵,s 是x 在7域的变换向量,s i =<x ,W i >。
显然,x 和s 是同一个信号的等价表示,x 是信号在时域的表示,s 是信号在7域的表示。
如果s 仅仅有K 个非零项,且Kn N ,或者s 中的各个分量按一定量级呈现指数衰减,具有非常少的大系数(K 个)和许多小系数,则称s 是K 项稀疏的,或x 在7域是K 项稀疏的。
图1是信号x 在7域稀疏表示的形象描述,图中s 为信号x 在7域的变换向量,且s 仅包含三个非零分量(用图中的非空白格子表示),即信号s 是3项稀疏的。
(a )原始图像(b )图像小波系数(c )压缩重构图像图2 基于小波变换的图像稀疏表示参考文献[1]给出信号稀疏性的另一种定义:如果信号x 在7域的变换系数s i =〈x ,W i 〉的支撑域{i ;s i ≠0}的势小于等于K ,则可以说信号x 在7域是K 项稀疏的。
通常时域内的自然信号都是非稀疏的,但在某些变换域可能是稀疏的。
例如,自然图像在小波变换域具有稀疏性。
图2为基于小波变换的图像稀疏表示示意图。
其中图2(a )是一幅大小为512×512的原始图像,图中几乎所有的像素值都是非零的;图2(b)为原始图像的小波变换系数,为便于观察,图中将这些系数随机排列,从中可以看出,大多数小波系数的绝对值都接近于零,取其中绝对值最大的10%部分系数进行小波重构,得到的重构图像如图2(c)所示,从中可以看出,重构图像与原始图像差别很小,由此可得出结论有限的大系数包含了原始图像的绝大部分信息,可用于近似表示图像。
目前广泛采用的JPEG2000图像编码标准正是以此为基础,通过小波变换实现图像压缩的[4]。
1.2 压缩感知中的信号稀疏表示信号的稀疏性是压缩感知的重要前提和理论基础。
因此,对信号稀疏表示的研究是压缩感知理论的首要任务。
稀疏表示对于压缩感知的基础性作用主要体现在:只有选择合适的稀疏矩阵,才能保证表示系数具有足够的稀疏性或衰减性,才能在减少压缩测量的同时保证压缩感知的重建精度。
(1)根据压缩感知理论,高概率重构稀疏信号的充分条件是感知矩阵(((∈R M ×N )必须满足约束等距性RIP(Restricted Isom etry Property )条件,即对于任意K 稀疏信号x (x ∈R N )和常数D k ∈(0,1),(1-D k )‖x ‖22≤‖(T x ‖22≤(1+D k )‖x ‖22(2)成立,其中T <{1,…,N },且ûT û≤K ,(T 为(中由索引T 所指示的相关列构成的大小为K ×ûT û的子矩阵。
从上式可以看出,信号的稀疏度K 越小,即信号越稀疏,约束等距性条件越容易满足。
86军 事 通 信 技 术2012年 (2)Candes 等进一步指出,在感知矩阵(满足约束等距性条件的前提下,如果要精确重构K 稀疏信号x ,测量次数M 必须满足M ≥O (K log (N ))。
因此,信号的稀疏度K 越小,稀疏性越强,保证信号重构所需的测量次数越少。
在研究信号的稀疏表示时,可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。
Candes 和T ao 研究表明,满足具有幂次衰减速度的信号,可利用压缩感知理论得到恢复。
2 压缩感知中信号稀疏表示的主要方法目前,信号的稀疏分解已经发展了多种算法。
从信号展开的基的选择出发,概括起来说可以分为三大类:正交基展开方法、多尺度几何分析方法和基于过完备字典的展开方法。
2.1 正交基展开方法正交基展开方法主要基于调和分析理论。
常用的正交分解包括傅里叶变换、短时傅里叶变换和小波变换。
从傅里叶变换到小波分析,信号分析处理能力不断加强。
傅里叶变换只对频率空间进行均匀划分;短时傅里叶变换增加了时间轴的划分,具有时频局部特性,但是各个时频窗口的形状大小都是一致的;小波变换的时频窗口可变,时频局部化能力大大增强,但是小波分析在一维时所具有的优良特性并不能简单地推广到二维或者更高维。
它们共同的特点就是对于给定信号的表示形式唯一,一旦信号的特性与基函数不完全匹配,则不一定能够获得信号的稀疏分解结果。
因此,迫切需要寻求新的信号稀疏表示方法。
2.2 多尺度分析方法多尺度几何分析M GA (Multiscale Geom etric Analysis)是以“最优”图像表示理论为基础而提出的一类新方法,它的提出主要是为了解决高维空间数据稀疏表示的问题。
根据生理学家和人类视觉系统的研究结果和自然界图像统计模型,“最优”图像表示方法应该具有如下特性:¹多分辨率,能够对图像从粗分辨率到细分辨率进行连续近似,也即“带通”性;º局域性,在空域和频域,该表示的“基函数”都必须是局部的;»方向性,表示的“基函数”应该具有不同的形状,特别地具有不同的纵横比,这样有利于更稀疏地表示图像的轮廓。
自从多尺度几何分析的首次提出,短短的几年时间内,其理论构建和应用已经得到深入展开,广泛应用于数学分析、计算机视觉、模式识别、统计分析等不同学科领域。
到目前为止,提出的多尺度几何分析方法有Hou 等人提出的Beam let 变换,Candes 等人提出的Ridg clct 变换和Curvelet 变换,Meyers 等人提出的Br usheflet 变换,Donolct 等人提出的Wedgelet 和Edgelet 变换,Do 等人提出的Co ntourlet 变换,Per mec 提出的Bandelet 变换,Velisavljevic 等人提出的Directionlet 变换,以及Yue 等人提出的Sur facelet 变换等。