Fast Discrete Curvelet Transforms theorem of a new mathematical transform

This paper describes two digital implementations of a new mathematical transform, namely,the second generation curvelet transform [12, 10] in two and three dimensions.

FastDiscreteCurveletTransforms

EmmanuelCand`es ,LaurentDemanet ,DavidDonoho andLexingYing

AppliedandComputationalMathematics,Caltech,Pasadena,CA91125

DepartmentofStatistics,StanfordUniversity,Stanford,CA94305

July2005,revisedMarch2006

Abstract

Thispaperdescribestwodigitalimplementationsofanewmathematicaltransform,namely,thesecondgenerationcurvelettransform[12,10]intwoandthreedimensions.The rstdigitaltransformationisbasedonunequally-spacedfastFouriertransforms(USFFT)whilethesecondisbasedonthewrappingofspeciallyselectedFouriersamples.Thetwoimplementationsessentiallydi erbythechoiceofspatialgridusedtotranslatecurveletsateachscaleandangle.Bothdigitaltransformationsreturnatableofdigitalcurveletcoe cientsindexedbyascaleparameter,anorientationparameter,andaspatiallocationparameter.AndbothimplementationsarefastinthesensethattheyruninO(n2logn) opsfornbynCartesianarrays;inaddition,theyarealsoinvertible,withrapidinversionalgorithmsofaboutthesamecomplexity.

Ourdigitaltransformationsimproveuponearlierimplementations—baseduponthe rstgenerationofcurvelets—inthesensethattheyareconceptuallysimpler,fasterandfarlessredundant.ThesoftwareCurveLab,whichimplementsbothtransformspresentedinthispaper,isavailableatdoc.docsou.com.

Keywords.2Dand3DCurveletTransforms,FastFourierTransforms,UnequispacedFastFourierTransforms,SmoothPartitioning,Interpolation,DigitalShear,Filtering,Wrapping.

Acknowledgments.E.C.ispartiallysupportedbyaNationalScienceFoundationgrantDMS01-40698(FRG)andbyaDepartmentofEnergygrantDE-FG03-02ER25529.L.Y.issupportedbyaDepartmentofEnergygrantDE-FG03-02ER25529.WewouldliketothankEricVerschuurandFelixHerrmannforprovidingseismicimagedata.

1

第1页下一页