压缩感知课件

压缩感知理论与应用智能感知与图像理解教育部重点实验室2011年8月IntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChinaIntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChina上次课内容回顾Lecture1：压缩感知概述为什么研究压缩感知压缩感知的涵义压缩感知的过程压缩感知的关键问题FromNyquisttoCSCompressionOriginal2500KB

100%Compressed950KB

38%Compressed392KB

15%Compressed148KB

6%“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”DonohoSparserepresentationofanimageviaamultiscalewavelettransform.(a)Originalimage.(b)Waveletrepresentation.Largecoefficientsarerepresentedbylightpixels,whilesmallcoefficientsarerepresentedbydarkpixels.Observethatmostofthewaveletcoefficientsareclosetozero.Sparse

inwavelet-domainSparseapproximationofanaturalimage.(a)Originalimage.(b)Approximationofimageobtainedbykeepingonlythelargest10%ofthewaveletcoefficients.Sparse

inwavelet-domainOurPoint-Of-ViewCompressedSensing(CS)mustbebasedonsparsityandcompressibility.Thesignalsmustbesparseintime-domainorinfrquency-domain.

CompressedSensing“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”Donoho“sensing…asawayofextractinginformationaboutanobjectfromasmallnumberofrandomlyselectedobservations”Candèset.al.Nyquistrate

SamplingAnalog

Audio

SignalCompression

(e.g.MP3)High-rateLow-rateCompressed

SensingConceptGoal:Identifythebucketwithfakecoins.Nyquist:Weighacoin

fromeachbucketCompressionBucket#numbers1numberCompressedSensing:Bucket#1numberWeighalinearcombination

ofcoinsfromallbucketsMathematicalToolsnon-zeroentries

atleastmeasurementsRecovery:brute-force,convexoptimization,

greedyalgorithms,andmore…CStheoryCompressedsensing(2003/4andon)–MainresultsMaximalcardinalityoflinearlyindependentcolumnsubsetsHardtocompute!isuniquelydeterminedbyDonohoandElad,2003Smallestnumberofcolumnsthatarelinearly-dependent.isuniquelydeterminedbyisrandomwithhighprobabilityDonoho,2006andCandèset.al.,2006NP-hardConvexandtractableGreedyalgorithms:OMP,FOCUSS,etc.Donoho,2006andCandèset.al.,2006Tropp,Cotteret.al.Chenet.al.andmanyotherCompressedsensing(2003/4andon)–MainresultsCStheoryDonohoandElad,2003RIPcriterion(a)Themeasurementscanmaintaintheenergyoftheoriginaltime-domainsignal.(b)Ifissparse,themustbedensetomaintaintheenergy.

VectorspaceUnitspheresinforthenormswith,andforthequasinormwithVectorspaceThenormsisusedtoreconstructthesignalBestapproximationofapointinbyaone-dimensionalsubspaceusingthenormsfor,andthequasinormwith

Lecture2:ModernSamplingMethodsandCS

16Sampling:“AnalogGirlinaDigitalWorld…”JudyGorman99DigitalworldAnalogworldSignalprocessingDenoisingImageanalysis…ReconstructionD2ASamplingA2D(Interpolation)Applications: SamplingRateConversionCommonaudiostandards:

8KHz(VOIP,wirelessmicrophone,…)

11.025KHz(MPEGaudio,…)

16KHz(VOIP,…)

22.05KHz(MPEGaudio,…)

32KHz(miniDV,DVCAM,DAT,NICAM,…)

44.1KHz(CD,MP3,…)

48KHz(DVD,DAT,…)

…LensdistortioncorrectionImagescalingApplications: ImageTransformationsApplications:CTScansApplications: SpatialSuperresolutionOurPoint-Of-ViewThefieldofsamplingwastraditionallyassociatedwithmethodsimplementedeitherinthefrequencydomain,orinthetimedomainSamplingcanbeviewedinabroadersenseofprojectionontoanysubspaceorunionofsubspacesCanwesampleasignalbelowNyquistsamplingrate.(Wemustknowsomethingaboutthesignals).

Shannon’ssamplingtheoremrevisited

Cauchy(1841):Whittaker(1915)-Shannon(1948):A.J.Jerri,“TheShannonsamplingtheorem-itsvariousextensionsandapplications:Atutorialreview”,Proc.IEEE,pp.1565-1595,Nov.1977.BandlimitedSamplingTheorems

LimitationsofShannon’sTheorem

InputbandlimitedImpracticalreconstruction(sinc)IdealsamplingTowardsmorerobustDSPs:GeneralinputsNonidealsampling:generalpre-filters,nonlineardistortionsSimpleinterpolationkernelsGeneralizedanti-aliasingfilterSamplingProcess

SamplingfunctionsEmployestimationtechniquesSamplingProcessNoiseSignalPriors

x(t)bandlimitedx(t)piece-wiselinearDifferentpriorsleadtodifferentreconstructionsSparsityIfasequencehaselementsandonlyofthemarenonzeros.Thenthesequenceissparse.Ifasequenceisasparsevector,thentheSignalPriors：SparsityPriorsWavelettransformofimagesiscommonlysparseSTFTtransformofspeechsignalsiscommonlysparseFouriertransformofradiosignalsiscommonlysparseFromdiscretetoanalogDiscreteCompressedSensingAnalogCompressiveSamplingAnalogCompressedSensingAsignalwithamultibandstructureinsomebasisnomorethanNbands,maxwidthB,bandlimitedto(MishaliandEldar2007)Eachbandhasanuncountablenumberofnon-zeroelementsBandlocationslieonaninfinitegridBandlocationsareunknowninadvanceWhatisthedefinitionofanalogsparsity?(Eldar2008)Moregenerallyonly

sequences

arenon-zeroSamplingandReconstructionSamplingReconstructionUnionofsubspacesPredefined(e.g.linearinterpolation)Ifthefilterisdifferentfrom,thenamultiratecorrectionsystemmustbegiven.(Inpractice,thefiltersareoftenundesirable).ProblemSub-NyquistsamplingBothprocessandrecoveryarebasedonlowratecomputation.Therawdatacanbedirectlystored.SomequestionsabouttheSub-NyquistsamplingHowtoobtainthedigitalsignalatasub-nyquistrate?Canwereconstructthesignalwithhighprobabilityapproximately?Sub-NyquistsamplingandCompressedSensing

38Multi-BandSensing:GoalsbandsSamplingReconstructionGoal:PerfectreconstructionConstraints:MinimalsamplingrateFullyblindsystemAnalogInfiniteAnalogWhatistheminimalrate?Whatisthesensingmechanism?Howtoreconstructfrominfinitesequences?Sub-NyquistsamplingLandauminimumratemeanssamplingatoftheNyquistratecanreconstructthesignalperfectly.（butthespectralsupportmustbeknown）NonuniformsamplingAnalogsignalIneachblockofsamples,onlyarekept,asdescribedbyPoint-wisesamples023002233Multi-Coset:PeriodicNon-uniformontheNyquistgridNonuniformsamplingDenotebythesequenceofsamplestakenattheNyquistrate.Therefore，inwhich.NonuniformsamplingThebuildingblocksareuniformsamplersatrate,sothattheaveragesamplingrateis,whichislowerthantheNyquistratewhere.NonuniformsamplingReconstructionoftheoriginalsignalisachievedifwerecoveritsspectralcomponents.Buttherearefewerequationsthantheunknownforeach.HOWTORECONSTRUCTTHESIGNALNonuniformsamplingAmethodshouldbeusedtoreducethedegreeoftheproblem.Some"subcell"areactive,whiletheothersarenot.Theanalogsignalcanbereconstructedperfectlyiftheamplitudeandlocationsofhasbeenknown.Someproblem1PracticalADCsintroduceaninherentbandwidthlimitation,whichdistortsthesamples.AnyspectralcontentbeyondbHzisattenuatedanddistorted.2Anotherpracticalissueofmulticosetsampling,arisesfromthetimeshiftelements.MaintainingaccuratetimedelaysbetweentheADCsintheorderoftheNyquistintervalisdifficult.IntroducetoRDTosolvetheparcticalproblemssomethingsabouttheRD(randomdemodulated)methordcanbeused.a

Oursystemexploitsspread-spectrumtechniquesfromcommunicationtheory.Ananalogmixingfront-endaliasesthespectrum,suchthataspectrumportionfromeachbandappearsinbaseband.bSignalternatingfunctionscanbeimplementedbyastandard(highrate)shiftregister.Today’stechnologyallowstoreachalternationratesof23GHzandeven80GHz.cBlindmultibandsignal(arbitraryspectrallocations)canbereconstructedbythissystemwithhighprobablity.Advantage多频带信号---许多信号只占用了少量带宽，因而具有稀疏性子空间采样理论MWC模块这里我们需要大量的滤波器，才能精确的重构，也就是

值越大越好（对应的采样频率也逐渐增大），由于信号的稀疏性，一般要求，

为频带个数实际采样框图傅里叶变换原子如果是离散信号的重构，我们可以直接通过优化求解，模拟信号我们有无穷多个方程要解，必须转化成有限的模型，高概率的重构原始信号引入一个CTF模型，通过和支撑区间

，我们可以重构出信号AICviaRandomDemodulation理论框图

公式描述Qusi-Toeplitz矩阵观测理论框图几个参数的说明

B随机滤波器的长度，d是信号的长度，N是采样点数，s是原始信号，h是随机滤波器可以看成是其中观测矩阵为每一行元素移位个单元，构成的观测矩阵实验结果

Definition：Thosethataredeterminedbyafinitenumberofparameterspertimeunit.Theτ-localrateofinnovationofasignalx(t),denotedρτ,istheminimalnumberofparametersdefininganylength-τsegmentofx(t),dividedbyτ.AnFRIsignalisoneforwhichρτisfinite,atleastforlargeenoughτ.PerhapsthesimplestclassofFRIsignalscorrespondstofunctionsthatcanbeexpressedasFiniterateofinnovationSignalsThissetofsignalsisalinearsubspaceofL2,whichisoftentermedashift-invariant(SI)space.FiniterateofinnovationSignalsAunionofsubspacesThismodelgeneralizesthefamilyofmultibandsignalsThefrequencies{ωℓ}determinethesubspaceandtheamplitudes{aℓ,m}determinethepositionwithinthesubspace.OurgoalistorecoverxbyobservingNgeneralizedsamplesc=(c1,...,cN)TobtainedaswhereS:H→RNissome(possiblynonlinear)Frechetdifferentiableoperator.Thisrepresentationismoregeneralthanthewidelyusedlinearsetting,inwhichforsomesetofvectors{sn}inH.Inparticular,itmayaccountfornonlineardistortionsintroducedbythesamplingdevice.Forexample,Scanrepresentthesampleswheref(·)isanonlinearsensorresponse.WesaythatasamplingoperatorSisstablewithrespecttoXifthereexistconstants0<αs≤βs<∞suchthatforallx1,x2∈XSamplingmethodThepulseshapeisknowna-priori,andthereforethesignalhasonly2Kdegreesoffreedomperperiod.SincexisperiodicitcanberepresentedintermsofitsFourierseriescoefficientswhereinaweusedPoissonsummationformula,andwhereukand^p-1denotesthemultiplicativeinverseofp.Sincepisknowna-priori,weassumeforsimplicityofnotationthat^p=1.Inordertondthevaluesukin(1.23),lethdenotethefilterwhosez-transformis,wherethelastequalityisduetothefactthath=0.Thefilteriscalledanannihilatingfilter,sinceitzeroesthesignal^xm.Itsrootsuniquelydefinethesetofvaluesuk,providedthatthelocationstkaredistinct.SinckernelsE-splinekernelsSoskernelsSuper-resolutionUltrasoundimagingSuper-resolutionradarSinc函数观测矩阵Sinc函数观测矩阵加入个周期的观测矩阵Poisson求和公式的变形为的傅里叶变换用有限个求和表示无穷多个周期相加的观测矩阵Sinc函数观测矩阵CompressedSensing

ExplosionofinterestintheideaofCS:Recoveravectorxfromasmallnumberofmeasurementsy=AxManybeautifulpaperscoveringtheory,algorithms,andapplicationsAnalogCompressedSensingCanweusetheseideastobuildnewsub-NyquistA/Dconverters?Priorwork:Yuet.al.,Raghebet.al.,Troppet.al.

Input

Sparsity

Measurement

Recovery

StandardCSvectorxfewnonzerovaluesrandom/det.matrixconvexoptimizationgreedymethods AnalogCSanalogsignalx(t)?RFhardwareneedtorecoveranaloginput

orspecificdata(demodulation)Oneapproachtotreatingcontinuous-timesignalswithintheCSframeworkisviadiscretizationAlternative:UsemorestandardsamplingtechniquestoconvertthesignalfromanalogtodigitalandthenrelyonCSmethodsinthedigitaldomain(Xampling=CS+Sampling)Possiblebenefits:Simplehardware,compatibilitywithexistingmethods,smallersizedigitalproblemsPossibledrawbacks:SNRsensitivitiesCanwetiethetwoworldstogether?Sampling/CompressedSensingRobustnessinthePresenceofNoiseGedalyahu,Tur&Eldar(2010)Proposedscheme:Mix&integrateTakelinearcombinationsfromwhichFouriercoeff.canbeobtainedSupportsgeneralpulseshapes(timelimited)OperatesattherateofinnovationStableinthepresenceofnoise–achievestheCramer-RaoboundPracticalimplementationbasedontheMWCFouriercoeff.vectorSamplesSub-NyquistsamplerinhardwareCombinesanalogpreprocessingwithdigitalpostprocessingSupportingtheoryprovestheconceptandrobustnessforavarietyofapplicationsincludingmultibandsignalsAllowstimedelayrecoveryfromlow-ratesamples(GedalyahuandEldar09-10)Applicationstoultrasound(TurandEldar09)Xampling:Sub-NyquistSampling(MishaliandEldar,08-10)OnlineDemonstrationsGUIpackageoftheMWCVideorecordingofsub-Nyquistsampling+carrierrecoveryinlabCantheseideasbeexploitedtocharacterizefundamentallimitsinotherareas?DegreesofFreedomToday:Applicationstolineartime-varying(LTV)systemidentificationSub-NyquistsamplingofpulsestreamscanbeusedtoidentifyLTVsystemsusinglowtime-bandwidthproductLowratesamplingmeansthesignalcanberepresentedusingfewerdegreesoffreedomTheXamplingframeworkimpliesthatmanyanalogsignalshavefewerDOFthanpreviouslyassumedbyNyquist-ratesampling

美国RICE大学的研究者们将微列阵与单一光学传感器结合起来创造了一种图像/摄像式照相机，这一相机具有图像压缩功能。这所大学的电子工程学教授Baraniuk说：“白噪声是关键，得益于那些数学理论，我们能够在随机分散的测量中得到有效且连贯的图像。单像素相机结构及成像原理这种单像素照相机使用了一款来自德州仪器的数字微反射镜（DMDdigitalmicromirrordevice）及单一光电二极管。有趣的部件是数字微反射镜，这款芯片主要用在数字背投或是投影机中。DMD芯片由大量只有细菌大小的镜片组成，每块微型镜片都一面反光，一面不反光，并可以快速翻转。一种伪随机模式可映射到上面。这种微反射镜可倾斜12，在芯片的表面有黑白两部分区域，白色部分表示反射镜可倾斜+12.黑色部分表示反射镜可倾斜-12.这一系列黑白区域中的反射光集中在光电二极管上。每一种伪随机模式都会发出一组系数（光电压），应用这些系数和随机种子87，可重新建立图像。Baraniuk说：“压缩传感的好处在于我们对样本的图片及影像的测量次数要多于对实际像素的测量。这能大大减少为获得图像/录影编码所要进行的计算。”

在整套系统中，被拍摄物体的图像经过镜头打在DMD上，而经过DMD反射的图像又经过二次镜头聚焦在只有一个像素的传感器上，形成一个光信号。而在拍摄过程中，DMD上每个镜片反射的明暗矩阵以伪随机码的形式快速变换，每变化一次形成一个像素的型号。最后，经过将每次的信号和伪随机码综合进行计算，就得到了物体的影像.实现设备

由于每次拍照只需要得到多个单像素信号，而在接收端和伪随机码综合计算得到影像。因此解压成像之前的信号量非常小，做到了很有效的数据压缩，十分有利于远距离无线传输（如：航天摄影）。另外，只需要单像素传感器的特点，使得在科学领域中，一些原本需要大面积传感器，或是传统方法无法拍摄的非可见光领域，这种拍摄方法都有其很大的应用价值。研发人员还称，DMD可以每秒数百万次的速度翻转，因此想把这种拍摄方法转为民用，甚至做成和现在一样的掌上相机也不是没有可能。尽管现在这套系统只对静止物体进行拍摄，拍一张照片需要5分钟，整套设备要占据一张大桌子。针对数字摄影不能应用在很多科学领域，需对照相机进行改进，例如：有可能应用在消费者市场的Terahertz图像技术。

拍摄效果

拍摄效果

具有单像素探测器的太赫兹相机可以提高测量速度，在太赫兹频段快速成像，能够在机场中的隐蔽武器探测以及航天飞机隔热层泡沫材料中的定位缺陷探测等方面发挥重要作用。基于单像素相机概念的太赫兹成像的新方法，有望改进太赫兹相机的性能，使其克服现有成像系统的缺点，同时提供较高的速度和较强的探测能力。这种成像方法的另一个优点是硬件的简单性和多功能性。通过采用一个连续波太赫兹光源，如一台太赫兹量子级联激光器，这种相机可以使用灵敏的单像素探测器（如高莱盒探测器）取代探测器阵列，因此降低了对光源功率的要求。如果采用脉冲光源，这种相机还可以将其成像能力扩展到捕获光谱相位其他超光谱特征。

这种相机的下一代产品将采用电驱动或光驱动的太赫兹空间调制器来取代随机模式的挡板。这将使其能在不需要任何机械移动部件的情况下，非常快速地对太赫兹光束进行调制。预期到那时，相机就能以视频成像的速度获取到充足的图像重建信息了。

下图:在单像素太赫兹相机的实验装置中，光束通过一块由不透明像素的随机图案构成的挡板，对一个带有字母“R”形状的透光孔的不透明物体进行成像。目标物体在白光中成像（左图）。同一物体的太赫兹图像分别通过300个测量值的压缩传感（中图）和600个测量值的压缩传感（右图）重建。

ProposedCSColorCameraRG1G2BRG1G2BRG1G2BRG1G2BA/DColorImageRearrangetoMosiacStructureJointColorCSReconstructionDemosaicingRNG+RotationControlLens1RotatingColorFilterDMDArrayPhotodiodeLens2Fig1:(a)Shows“VirtualBayerFilter”structureontheDMDarray.ThereisnorealBayerfilter,buteachmicromirrorisvirtually“labeled”sothatmosaicstructureofaBayerfilterisformed.(b)ProposedcolorCScameraarchitecture.ThishasaRotatingColorFilter(RCF)andaRotationControlunit(RC)asnewcomponentsintheCameraof[3].ItcapturesR,GandBmeasurementsdirectlyonBayerplanes,(therebyreducingtheoverallmeasurements)andusesjointR-G-Breconstructionschemetoproducebetterqualitycolorimage.s(a)(b)VisualResultsFig.2:Showssomesamplehighresolutioncolorimagesusedfortesting.Fromtopright,Lena,Peppers,Light-House,Lady,Gold-HillandGirl.TheperformanceresultsontheseimagesaretabulatedinTable1,for30%,25%measurementsontheBayerR,G1,G2andBplanes.Fig.3:Showsimagesections&correspondingresults.Column-wise:Col1istheBayersampledanddemoisaicedreferenceimage(bilinearinterpolation),Col2,3arejointR-G-BE-JSM,JSMreconstructedimagesrespectively.Col4isR,G,Bindependentlyreconstructedimages.Row-wise:croppedsectionsoforiginalimages,Lady,Light-HouseandPepperinRows1,2and3respectively.Longersignalsvia“random”transformsNon-GaussianmeasurementschemeLowcomplexitymeasurement(approxO(N)versusO(MN))universallyincoherentLowcomplexityreconstructione.g.,MatchingPursuitcomputeusingtransforms

(approxO(N2)versusO(MN2))PermutedFFT(PFFT)FastTransform

(FFT,DCT,etc.)Truncation

(keepMoutofN)PseudorandomPermutationReconstructionfromPFFTOriginal65536pixelsWaveletThresholding6500coefficientsCSReconstruction26000measurements4xoversamplingenablesgoodapproximationWaveletencodingrequiresextralocationencoding+fancyquantizationstrategyRandomprojectionencodingrequiresnolocationencoding+onlyuniformquantizationRandomFiltering

[withJ.Tropp]Hardware/softwareimplementationStructureofconvolutionToeplitz/circulantdownsamplingkeepcertainrowsiffilterhasfewtaps,issparsepotentialforfastreconstructionCanbegeneralizedtoanaloginputDownsample(keepMoutofN)“Random”FIRFilterTime-sparsesignalsN=128,K=10Fourier-sparsesignalsN=128,K=10ReconstructionfromPFFTCoefficientsOriginal65536pixelsWaveletThresholding6500coefficientsCSReconstruction26000measurements4xoversamplingenablesgoodapproximationWaveletencodingrequiresextralocationencoding+fancyquantizationstrategyRandomprojectionencodingrequiresnolocationencoding+onlyuniformquantizationSensornetworks:

intra-sensorand

inter-sensorcorrelation

dictatedbyphysicalphenomenaCanweexploitthesetojointlycompress?Popularapproach:collaborationinter-sensorcommunicationoverheadcomplexityatsensorsOngoingchallengeininformationtheorycommunityCorrelation

inSignal

EnsemblesBenefits:DistributedSourceCoding:exploitintra-andinter-sensorcorrelationsfewermeasurementsnecessaryzer