压缩感知及应用.pdf
- 文档编号:3432147
- 上传时间:2023-05-05
- 格式:PDF
- 页数:5
- 大小:681.09KB
压缩感知及应用.pdf
《压缩感知及应用.pdf》由会员分享,可在线阅读,更多相关《压缩感知及应用.pdf(5页珍藏版)》请在冰点文库上搜索。
第31卷第3期2010年3月微计算机应用MICROCOMPUTERAPPLICATIONSVol131No13Mar12010压缩感知及应用3李卓凡1,2闫敬文2(11韩山师范学院物理与电子工程系潮州52104121汕头大学工学院汕头515063)摘要:
传统的信号采样必须遵循香农采样定理,产生的大量数据造成了存储空间的浪费。
压缩感知(CS)提出一种新的采样理论,它能够以远低于奈奎斯特采样速率采样信号。
压缩感知的基本论点是如果信号具有稀疏性,可投影到一个与变换基不相关的随机矩阵并获得远少于信号长度的测量值,再通过求解优化问题,精确重构信号。
本文详述了压缩感知的基本理论,压缩感知适用的基本条件:
稀疏性和非相干性,测量矩阵设计要求,及重构算法的RIP准则,并介绍了压缩感知的应用及仿真。
仿真结果表明当采样个数大于Klog(N/K),就能将N维信号稳定地重建出来。
关键词:
压缩感知观测矩阵稀疏性RIPTheoryandApplicatonofCompressiveSensingLIZhuofan,YANJingwen(1Physicsandelectronicengineeringdepartment,HanshanNormalCollege,Chaozhou,521041,China;2CollegeofEngineering,ShantouUniversity,Shantou,Guangdong,515063,China)Abstract:
ConventionalapproachestosamplingsignalsfollowShannonprinciple1Ittakegreatcostsondatastorage1Inthispaper,thetheoryofCompressivesensingisintroduced1CompressivesensingprovidesanewsamplingtheorytosamplesignalbelowtheNyquistrate1Ifsignalorimageissparseinsomeorthonormalbasis,signalorimagecanberecoveredfromsmallnumberofmeasurementusinganoptimizationprocess1Thestructureofthesignalispreservedinthemeasurementandthemeasurematrixisincoherentwiththeor2thonormalbasis1CSreliesontwoprinciples:
sparsityandincoherence1RIPprincipleistheprecondictionofdesigningreconstructionalgorithm1TheapplicationofCStheoryareintroducedandthesimulationisillustratedindetails1ThesimulationshowthatthesignalcanbereconstructedstablelywhenthenumberofsamplesislargerthanKlog(N/K)1Keywords:
compressivesensing,measurementmatrix;sparsity,RIP1引言传统的信号采样以奈奎斯特采样定理为基础。
在获取信号时,为了不丢失信号的信息,采样频率必须大于信号中最高频率的两倍,才能精确重构信号。
但是随着科技的迅速发展,高分辨率的数码装置的采样产生了庞大的数据,如何更高效地处理这些数据并最大限度地节省存储和传输的成本是一大难题。
实际上采样得到的大部分数据是不重要的,在信号或图像的处理过程中,只保留了某些重要的数据,舍弃了大量的剩余数据,重构后的信号或图像并不会引起视觉上的差异。
于是科学家们提出一个构想,既然采集到的数据大部分都是不重要的,可以被丢弃,能否直接地采集那部分重要的、最后没有被丢弃数据,并且能够精确地本文于2009-12-14收到。
3基金项目:
国家自然科学基金(项目批准号:
40971206)。
3期李卓凡等:
压缩感知及应用重构原始信号或图像。
在2004年,由Donoho等人提出了压缩感知(compressedsensing,简称CS)理论1,9。
压缩感知理论表示:
如果信号通过某种变换(如傅立叶变换,小波变换等)后,是可稀疏表示或可压缩的,则可设计一个与变换基不相关的测量矩阵测量信号,得到的测量值通过求解优化问题,可实现信号的精确或近似重构。
测量后,信号f由N维减少到M维(MK);或者经排序后按指数级衰减并趋近于零,可认为信号是稀疏的。
信号的可稀疏表示是压缩感知的先验条件。
在已知信号是可压缩的前提下,压缩感知过程可分为二步:
(1)设计一个与变换基不相关的MN(MN)维测量矩阵对信号进行观测,得到M1维的测量向量。
(2)从M1维的测量向量重构信号。
图1压缩感知观测流程图(K=3)211测量矩阵用一个与变换矩阵不相关的MN(MN)测量矩阵对信号进行线性投影,得到线性测量值y:
y=f
(2)测量值y是一个M1矩阵,这样使测量对象从N维降为M维(如图1(a)所示)。
观测过程是非自适应的,即测量矩阵的选择不依赖于信号f的。
测量矩阵的设计要求信号从f转换为y的过程中,所测量到的K个测量值不会破坏原始信号的信息,保证信号的精确重构。
由于信号f是可稀疏表示的,
(2)式可以表示为下式:
y=f=(3)其中是一个MN矩阵。
转换过程如图1所示。
(3)式中,方程的个数远小于未知数的个数(即MN),方程无确定解,无法重构信号。
但是,由于信号是K稀疏的(KM),若(3)式中的满足有限等距性质(RestrictedIsometryProper2ty,简称RIP),即对于任意K稀疏信号f和常数k(0,1),矩阵满足:
1-kf22f221+k(4)则K个系数能够从M个测量值准确重构。
RIP性质的等价条件是测量矩阵和稀疏基不相关。
31微计算机应用2010年目前,用于压缩感知的测量矩阵主要有以下几种:
高斯随机矩阵2,二值随机矩阵(伯努力矩阵)2,傅立叶随机矩阵2,7,哈达玛矩阵,一致球矩阵等。
212信号重构RIP性质从理论上保证K稀疏信号能由M个测量值y重构长度为N的信号f。
这类求逆问题的传统解法可以通过求解最小l2范数解决:
=argmin2s1t1=y(5)(5)的近似解为:
=T(T)-1y。
但是最小化l2范数得到的向量是非稀疏的,而我们要寻找的向量是K稀疏的,所以这种方法并不能找到我们需要的解,进而采用求解l0范数来代替:
=argmin0s1t1=y(6)运用最小l0范数法,只需M=K+1个测量值,就能精确重建K稀疏信号。
求解(6)式需要列出中非零值位置的NK种可能组合,但是求解的数值运算不稳定而且是一个NP-hard问题。
于是Donoho等人提出用l1代替范数l0范数会得到相同的解:
=argmin1s1t1=y(7)当服从独立同一分布的高斯测量值的个数McKlog(N/K)时,用l1范数能够高概率地精确重建K稀疏向量,这样问题变成了一个凸优化问题,可以转化成线性规划问题求解5。
典型算法有基追踪(BasisPur2suit,BP)算法,内点法,共轭梯度投影法8,迭代阈值法等。
其他重构算法还有正交匹配追踪算法(OMP)3,最小全变分法4以及一些综合的改进算法。
图2源信号及重构信号3应用使用一定数量的非相关测量值能够高效率地采集可压缩信号的信息,这种特性决定了压缩感知应用的广泛性。
6例如低成本数码相机和音频采集设备;节电型音频和图像采集设备;天文观测;网络传输;军事地图;雷达信号处理等等。
以下归纳了压缩感知几个方面的应用:
(1)数据压缩在某些情况下,稀疏基在编码中是未知的或在数据压缩中是不能实际实现的。
由于测量矩阵是不需要根据的结构来设计的,随机测量矩阵可认为是一个通用的编码方案,而只有在解码或重建信号的时候需要用到。
这种通用性在多信号装置(如传感器网络)的分布式编码特别有用。
(2)信道编码压缩感知的稀疏性、随机性和凸优化性,可以应用于设计快速纠错码以防止错误传输。
(3)逆问题在其他情况下,获取信号的唯一方法是运用特定模式的测量系统。
然而,假定信号存在稀疏变换基,并与测量矩阵不相关,则能够有效的感知的信号。
这样的应用在文献4中的MR血管造影术有提到,记录了傅立叶变换子集,所得到的期望的图像信号在时域和小波域都是稀疏的。
(4)数据获取413期李卓凡等:
压缩感知及应用图3重构误差曲线图在某些重要的情况下,完全采集模拟信号的N个离散时间样本是困难的,而且也难以对其进行压缩。
而运用压缩感知,可以设计物理采样装置,直接记录模拟信号离散、低码率、不相关的测量值,有效地进行数据获取。
基于RIP理论,目前已研制出了一些设备,有莱斯大学研制的单像素相机和A/I转换器,麻省理工学院研制的编码孔径相机,耶鲁大学研制的超谱成像仪,麻省理工学院研制的MRIRF脉冲设备,伊利诺伊州立大学研制的DNA微阵列传感器。
4仿真源信号是一维稀疏信号,长度N=128,稀疏个数K=8。
变换矩阵为傅立叶正交变换矩阵,编码端采用高斯测量矩阵,解码端采用正交匹配追踪法。
具体算法流程如下:
(1)产生测量矩阵(随机高斯矩阵),并对信号f进行测量,得到测量值y。
(2)产生傅立叶变换矩阵,并与测量矩阵相乘得到恢复矩阵。
(3)运用正交匹配追踪算法,确定迭代次数t(tk),运用最小二乘法求解未知量,即变换系数=T(T)-1y。
(4)由计算傅立叶逆变换求得重构信号f。
图2为程序仿真后的源图像和重构图像,当测量次数M=56时,重构信号与源信号误差为11218310-14,重构效果非常好;当测量次数M=15时,重构信号与源信号误差为111847,这是由于测量次数太少造成的。
理论上当测量次数MKlog(N/K)=32,N维信号的K个最大值能稳定地重建出来。
在实际应用中是否与理论吻合呢?
表一是测量次数分别取M=15,17,20,22,24,25,26,28,30,32,40,56,通过实验仿真得到结果,图3为重构误差曲线图。
可以看出当M小于25时,重建结果极不稳定,误差波动大;当M接近但小于32时,误差的数量级是10-14,但波动范围较大,总体误差也偏大;当M大于或等于32时,误差小且误差范围稳定,重建结果稳定。
因此,为了保证重建结果的稳定性,减少或避免出错,观测次数必须取偏大于32次。
表1M=15,17,20,22,24,25,26,28,30,32,40,56时重构信号误差测量次数M151720222425262830324056重构误差919588E+00211075E-14118548E-14116814E-14119434E-14119721E-14118874E-14116068E-14115185E-14113166E-14116096E-14112305E-14118652E+00712500E-02119760E-14118391E-14813500E-02210252E-14115964E-14116501E-14211640E-14114791E-14113448E-14114450E-14111792E+00212551E-14216961E-14110680E-01111963E+00116442E-14116173E-14119044E-14113191E-14113786E-14116757E-14112704E-14111364E+00119725E-14413870E-01913100E-02115314E-14116646E-14116609E-14118504E-14114924E-14116105E-14112977E-14112978E-14112546E+00816200E-02117744E-14614400E-02118372E-14114485E-14119613E-14113673E-14113965E-14114895E-14116285E-14113018E-14112341E+00416470E-01112426E+00813500E-02119370E-14116890E-14119682E-14115456E-14114561E-14114061E-14114712E-14112592E-14214215E+00610000E-02215080E-01812200E-02116773E-14114257E-14119393E-14117427E-14115401E-14114785E-14115429E-14113042E-14713730E-01215480E-01817000E-02118747E-14212555E-14115772E-14115514E-14115599E-14115657E-14114732E-14112898E-14111822E-14112837E+00216544E-14216961E-14413000E-01117938E-14115144E-14119915E-14210860E-14115407E-14116488E-14115659E-14111696E-14118390E+00916700E-02111892E+00119495E-14410910E-01114674E-14210134E-14116578E-14116696E-14115962E-14113028E-14115923E-14110451E+00110620E-01112569E+00212442E-14117367E-14211685E-14210926E-14116984E-14114535E-14113744E-14115029E-14112701E-14平均值211777E+00110374E-01410593E-01718182E-02115354E-01116906E-14118436E-14116972E-14115560E-14114774E-14114756E-14113021E-1451微计算机应用2010年5结束语本文介绍了压缩感知的框架理论;通过仿真程序模拟了信号测量及重构的过程,并用实验数据表明,测量次数的选择必须大于Klog(N/K),否则信号不能稳定地重构,出错概率大。
但为了尽量地压缩数据,测量次数也不宜太大。
CS理论的诞生说明香农采样定理并不是获得信号的唯一途径。
它运用了信号的稀疏性,对信号进行测量,通过解决凸优化问题重构信号。
CS理论的前提是稀疏性(sparsity)和不相关性(inco2herence),前者由信号本身决定,后者由感知系统决定。
观测矩阵的随机不相关性是准确恢复信号的保证,因此观测矩阵的设计是CS的关键部分。
观测矩阵若满足RIP性质,那么K3log(N/K)个采样就能将N维信号的K个最大值稳定地重建出来。
对观测矩阵的研究是目前压缩感知理论的一个热点,其中包括观测矩阵的构造、优化算法及硬件实现等等。
将压缩感知理论应用于硬件设计是该理论实用性的标志,本文总结了CS理论的实际应用,这是该理论迈向实用化的一大步,但目前仅能处理有限难数据的信号,无法处理无限维信号,有待进一步的研究。
压缩感知作为一门新生的理论,虽然在很多方面还不完善,但依然给信号处理领域注入了新生的力量,开创了广阔的研究前景。
参考文献1DONOHOD1CompressedsensingJ1IEEETrans1InformationTheory,2006,52(4):
1289-13062EJCandsandTTao1Nearoptimalsignalrecoveryfromrandomprojections:
UniversalencodingstrategiesJ1IEEETrans1Info1Theory12006,52(12):
5406-54253TroPPJ,GilbertA1Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit1TransactionsonInformationTheo2ry,2007,53(12):
4655-46664CandsE,RombergJ,TaoT1Robustuncertaintyprinciples:
Exactsignalreconstructionfromhighlyincompletefrequencyinforma2tion1IEEETransactionsonInformationTheory12006,52
(2):
489-5095RBaraniuk1AlectureoncompressivesensingJ1IEEESignalProcessingMagazine1July2007,24(4):
118-1216EJCandsandMBWakin11AnIntroductiontoCompressiveSamplingJ1IEEESignalProcessingMagazine1March2008,25
(2):
21-307ZOUJ,GILBERTAC,STRAUSSMJ,etal1TheoreticalandexperimentalanalysisofarandomizedalgorithmforsparseFouriertransformanalysisJ1JournalofComp-utationalPhysics,2006,211
(2):
572-5958FIGUEIREDOMAT,NOWAKRD,WRIGHTSJ1Gradientprojectionforsparsereconst-ruction:
applicationtocompressedsens2ingandotherinverseproblemsJ1IEEEJ-STSP,2007,1(4):
586-5989ECands1CompressivesamplingA1ProceedingsoftheInternationalCongressofMathematiciansC1Madrid,Spain,2006,3:
1433-1452110D1Takhar,V1Bansal,M1Wakin,M1Duarte,D1Baron,J1Laska,K1F1Kelly,andR1G1Baraniuk1Compressedsensingcamera:
Newtheoryandanimplementationusingdigitalmicromirrors1inProc1Comput1ImagingIVSPIEElectronicImaging1SanJose,Jan120061作者简介李卓凡,女,(1979-),实验师,主要研究方向为图像处理。
闫敬文,男,(1964-),教授,博导,主要研究方向为数字视频处理、SAR图像处理与识别、小波分析及应用。
61
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 压缩 感知 应用