Sampling schemes for multidimensional signals with

IEEETRANSACTIONSONSIGNALPROCESSING,VOL.X,NO.XX,NOVEMBER20061SamplingSchemesforMultidimensionalSignalswithFiniteRateofInnovationPanchamShukla*,StudentMember,IEEE,andPierLuigiDragotti,Member,IEEESPEDICS:DSP-WAVL(Waveletstheoryandapplications),DSP-SAMP(Sampling,extrapolation,andinterpolation),andDSP-RECO(Signalreconstruction)AbstractConsidertheproblemofsamplingsignalsthatarenonbandlimitedbuthavefinitenumberofdegreesoffreedomperunitoftimeandcallthisnumbertherateofinnovation.StreamsofDiracsandpiecewisepolynomialsaretheexamplesofsuchsignals,andthusareknownassignalswithfiniterateofinnovation(FRI)[3].Weknowthattheclassical(‘bandlimited-sinc’)samplingtheorydoesnotenableperfectreconstructionofsuchsignalsfromtheirsamplessincetheyarenotbandlimited.However,therecentresultsonFRIsampling[3],[4]suggestthatitispossibletosampleandperfectlyreconstructsuchnonbandlimitedsignalsusingarichclassofkernels.Inthispaper,weextendtheresultsof[4]inhigherdimensionsusingcompactlysupportedkernelsthatreproducepolynomials(satisfyStrang-Fixconditions).Infact,thepolynomialreproductionpropertyofthekernelmakesitpossibletoobtainthecontinuous-momentsofthesignalfromitssamples.Usingthesemomentsandtheannihilatingfiltermethod(Prony’smethod),theinnovativepartofthesignal,andtherefore,thesignalitselfisperfectlyreconstructed.Inparticular,wepresentlocal(directionalderivativesbased)andglobal(complex-moments,Radontransformbased)samplingschemesforclassesofFRIsignalssuchassetsofDiracs,bilevelandplanarpolygons,quadraturedomains(e.g.circles,ellipses,cardioids),2-Dpolynomialswithpolygonalboundaries,andn-dimensionalDiracsandconvexpolytopes.Thisresearchhasbeenpromisinglyexploredinsuper-resolutionalgorithms[5]anddistributedcompression[6],andmightfinditsapplicationsinphotogrammetry,computergraphics,andmachinevision.ManuscriptreceivedAug14,2006;revisedNov21,2006.ThisworkwassupportedbytheEngineeringandPhysicalSciencesResearchCouncil(EPSRC)ofUKunderthegrantGR/S57631/01.ThematerialofthispaperwaspresentedinpartattheIEEEInt.Conf.onImageProcessing(ICIP05),Genova,Italy,Sep2005[1],andatICIP06,Atlanta,USA,Oct2006[2].Correspondingauthor:PanchamShuklaiswiththeCommunicationsandSignalProcessingGroup,DepartmentofElectricalandElectronicEngineering,ImperialCollegeLondon,LondonSW72AZ,UK(e-mail:[e-mail],[e-mail]).PierLuigiDragottiiswiththeCommunicationsandSignalProcessingGroup,DepartmentofElectricalEngineering,ImperialCollegeLondon,LondonSW72AZ,UK;Tel:[phone];Fax:[phone](e-mail:[e-mail]).November27,2006DRAFT2IEEETRANSACTIONSONSIGNALPROCESSING,VOL.X,NO.XX,NOVEMBER2006I.INTRODUCTIONSamplingplaysanimportantroleinmodernsignalprocessingandcommunicationapplications.Shannon’sclassicalsamplingtheoryanditsextensionsareverypowerfulandhavebeenextensivelyutilizedforbandlimitedsignals[7],[8].Moreover,theclassicalsamplingisalsoextendedtotheclassesofnon-bandlimitedsignalsthatresideinashift-invariantsubspace[9],[8].Foracomprehensiveaccountonthemodernsamplingdevelopments,wereferto[7],[8].Recently,novelsamplingschemeshavebeenpresentedforlargerclassesof1-Dsignalsthatareneitherbandlimitednorresideinafixedsubspace.Suchsignalsenjoyafinitenumberofdegreesoffreedom(orrateofinnovation)andareclassifiedassignalswithFiniteRateofInnovation(FRI)[3].StreamsofDiracs,nonuniformsplines,andpiecewisepolynomialsareexamplesofsuchsignals.Thekeyfeatureof[3]isperfectreconstructionofFRIsignalsfromafinitenumberofsamplesusingannihilatingfiltermethod(Prony’smethod).Subsequently,theschemesof[3]areextendedfortheclassesof2-DFRIsignalssuchassetsof2-DDiracs,andpolygonsin[10]and[11].Theschemesof[10]relyonglobalalgorithmsinFourierdomain,andcanbeunstableattimes.Mostimportantly,alltheseschemes[3],[10],[11]useinfinitesupportsincandGaussiankernels,andtherefore,arenotconvenientinpractice.However,theresultsof[12],[4]showthatmany1-DFRIsignalswithlocalrateofinnovationcanbesampledandperfectlyreconstructedusingcompactlysupportedkernels(e.g.B-splines[13])thatsatisfyStrang-Fixconditions[14],andtherefore,reproducepolynomials.Inthispaper,weextendtheresultsof[12],[4]formultidimensionalFRIsignalsusinglocalkernelsthatreproducepolynomials.Itisimportanttorememberthatthepolynomialreproductionpropertyofkernelsplaysapivotalroleinoursamplingschemes.Inparticular,itallowsustoobtainthemomentsofthesignalsfromtheirsamples,andusingthesemomentsthesignalsarereconstructed.Inthispaper,weproposelocalandglobalreconstructionschemeswithvaryingdegreesofcomplexities.Ourschemesarebasedonthreedifferentapproaches:1)Directionalderivativesbasedapproach:Thisisalocalapproachforreconstructingaplanarpolygonfromitscornerpoints.Itusesalinkbetweencontinuousdomaindirectionalderivativesanddiscretedomaindirectionaldifferencesbasedonthefundamentalsoflatticetheory[15],[16],[17].2)Complex-momentsbasedapproach:Inthisglobalapproach,weexploitcomplex-momentsandshowthatitispossibletoreconstructbilevel-convexpolygons,setsof2-DDiracs,polygonallines,andquadraturedomains(e.g.ellipses,cardioids,andlemniscates)fromtheirsamples.Implicitly,wederiveasamplingp