压缩感知及其图像处理应用研究进展与展望

408Vol.40,No.820148ACTAAUTOMATICASINICAAugust,20141;211(Compressedsensing,CS),.,,.CS,,CS,,.,,,,,,..,2014,40(8):1563¡1575DOI10.3724/SP.J.1004.2014.01563AdvancesandPerspectiveonCompressedSensingandApplicationonImageProcessingRENYue-Mei1;2ZHANGYan-Ning1LIYing1AbstractCompressedsensing(CS)canperceivetheoriginalstructureofsignalsthroughafewmeasuredvalues,andreconstructthesignalbysolvinganoptimalproblemaccurately.ThetheoryofCSnotonlyreducesthecostofthestorageandtransmissionduringtheacquisitionofimagesandvideos,butalsoprovidesnewopportunitiesforthefollow-upimageprocessingandrecognition,promotingthecombinationoftheoryandengineeringapplication.ThispaperpresentstheprinciplesofCS,andsurveysthelatesttheoryachievementsanddevelopmentofsparserepresentation,designofmeasurementmatrixandreconstructionalgorithm.ThenthispaperanalyzesanddiscussestheresearchanddevelopmentofCStheoryinitsapplicationofimageprocessing¯eld.Intheend,thepaperpointsouttheexistingproblemsandthefutureapplication.KeywordsCompressedsensing,sparserepresentation,measurementmatrix,reconstructionalgorithm,imageprocessingCitationRenYue-Mei,ZhangYan-Ning,LiYing.Advancesandperspectiveoncompressedsensingandapplicationonimageprocessing.ActaAutomaticaSinica,2014,40(8):1563¡15752.,,,,.,,2012-02-282013-12-18ManuscriptreceivedFebruary28,2012;acceptedDecember18,2013(61231016,61301192,61272288,61201291),(142102210557),(JCT20130108,JC201120,JC201148)SupportedbyNationalNaturalScienceFoundationofChina(61231016,61301192,61272288,61201291),KeyScienceandTechnologyProgramofHenanProvince(142102210557),NPUFoundationforFundamentalResearch(JCT20130108,JC201120,JC201148)RecommendedbyAssociateEditorDAIQiong-Hai1.7101292.4730001.SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi0an7101292.DepartmentofComputerEngi-neering,HenanPolytechnicInstitute,Nanyang473000,,.,,,,,.\,.2006,Candes[1],CS.,Donoho[2](Compressedsensing,CS).,,,.,,CS156440[3¡4].,CS,[3¡7],.,CS:1),,;2),,(),;3),,.,CS,CS,CS.1'''iRN,ª=['''1;'''2;¢¢¢;'''N],RNxxx:xxx=NXi=1®®®i'''iorxxx=ª®®®(1),xxx®®®ª.®®®N,,xxx.CS,,ª©2RM£N(M¿N)xxxyyy,yyyxxx.1.1Fig.1Theoryframeworkofcompressedsensing1CS,,ª,ª;,,ª©,yyy=©ª®®®(2);,(2)l0yyy®®®®®®¤:®®®¤=argmin®®®k®®®ks:t:©ª®®®=yyy(2)®®®¤,xxx=ª®®®¤,,.2CSFig.2LinearmeasurementofcompressedsensingCS,.DuarteCS(Distributioncompressivesens-ing,DCS)[8],,,,.,Wang[9]DCS.DCS,.BayesianCS(BCS)BayesCS[10].,.,BCS,.Multi-taskCS(MCS)[11](),.,.22.1CS,3,,,CS.,3,,,,.8:15653LenaFig.3Lenaimageandits1Dand3Dhistograms().,ª,'''i,ªxxx(3).4.®®®¤=argmin®®®k®®®k0s:t:xxx=ª®®®(3)4Fig.4Imagesparsedecompositionandreconstruction,,,.,.,,,.,,,2.1.1,.Fourier,[12],,,(3(c)).1996,Olshausen[13].,,(Multiscalegeometricanalysis,MGA)[14¡16].MGA,,.Ridgelet[14];Curvelet[15],.MGA.(5(a)).[17]GaussAnisotropicre¯nement-Gaussian(AR-Gauss),,(6(a)).,,[18¡19],,.Peyr[20].[21]RanMeyer,Gabor(Multi-componentGaborperceptiondictionary,McGP),(6(b)).,K-SVD[22](5(b))[23],.5Fig.5Di®erentsparserepresentationdictionaries1566406Barbara[21]Fig.6ReconstructionofBarbaraimagebydi®erentdictionaries[21]2.1.2,.,ªmxxx.:mink®®®k0s:t:xxx=k=K¡1Xk=0ªk®®®k(4)k®®®k0f®®®kg.NP.,,,.2.1.3,,.l0.,,l0.SF.:SF=]fi;jxxxijTg]fxxxg(5),.,,;,.lp,0p1,.:kxxxkp=(Xi=1jxxxijp)1=p(6)lp,.2.2CS,,KRN!RM,.CandesTao©(Restrictedisometryproperty,RIP)[24],(K)xxx2RN,8T½f1;2;¢¢¢;Ng,jTj·K,©T©2RM£NTM£jTj,±K2(0;1),(7),©KRIP.(1¡±K)kxxxk22·k©Txxxk·(1+±K)kxxxk22(7)RIP,.Bara-niukRIP[25],©ª.CandesCS1-CS3[1].,CS,.,,:.,N,M=O(Klog(N)),[26].N(0;1=N),,.,K·C¢M=log(N=M),,.[27],M£NM,[28].,,O(K¤log(N)).NN=2K.Do[29],./,.,,,..Chirps(Toeplitz).Toeplitz[30¡31]K·C¢M3=ln(N=M),RIP,,.[32],,,.[33]8:1567,©b,©.,.,.Shi[34]Hashing,HashingRIP.[35],,.,,,..7.,,.,.7LenaFig.7ReconstructionofLenaimagebydi®erentmeasurementmatrices2.3CS,...2.3.1yyyxxx,:argminxxxkxxxk0s:t:yyy=©xxx(8)argminxxxkxxxk0s:t:kyyy¡©xxxk22·(9),.(8)(9)xxx,NP-hard.,l0,xxx,.(Matchingpursuit,MP).©,,,.,,.OMP(Orthogonalmatchingpursuit)[30]MP,,.,,.,,OMP.OMP(Regularizedorthogonalmatchingpursuit,ROMP)[36]RIP.(CoSaMP)[37](Subspacepur-suit,SP)[38],,,.SPO(mNK),O(mNlogK),.CoSaMP,.K.K,KSAMP[39],,,.,,K,OMP.ROMPSAMP,[40](Regularizedadaptivematchingpursuit,RAMP),,K.MP,Blmensath[41],,(Stagewiseweakconjugategradientpursuit,SWCGP).,156840,SWCGP.SWCGPMP,,,,[42](Spectralprojectedgradient,SPG)CS.,,..,[43]2D-OMP,,.2.3.2ª©,(8)(9):argminxxxkxxxk1s:t:yyy=©xxx(10)argminxxxkxxxk1s:t:kyyy¡©xxxk22·(11)(10)(11),.,,CS,.,,.,,Candes[44],,,minTV(xxx)s:t:yyy=©xxx(12),TV(xxx)=Pp(xxxi+1;j¡xxxi;j)2+(xxxi;j+1¡xxxi;j)2,(12)..l1TV,(Basicpursuit,BP)(Interor-pointmethods)[45](Iterativeshrinkagethresholding,IST)[46](Pro-jectedgradientmethods,PGM)[47].,BPOMP,OMP,.,PGM,.IST,.,,.,Bioucas-Dias(Two-stepiterativeshrink-agethresholding,TwIST)[48],IST,,IST.WrightSpaRSA[49],,.[50¡51].Afonso(SplitaugmentedLagrangianshrinkagealgo-rithm,SALSA)[50],,.[50;52].CS,89.TwIST,,,;SpaRSA,,;SALSA,,.,,Varadarajan[53].,.8CSbarksdaleafbFig.8`barksdaleafb'imagerestorationbasedoncompressedsensing8:15699barksdaleafbFig.9Approximateimagesof`barksdaleafb'imagebydi®erentoptimizationalgorithms,,.,,,,.,,,,,.CS.3CS,,CS[54¡56][57].CS.3.1CSCS