数字图像处理 小波和多分辨率处理

DigitalImageProcessingWaveletandMultiresolutionProcessing

MultiresolutionAnalysisManysignalsorimagescontainfeaturesatvariouslevelsofdetail(i.e.,scales). Smallsizeobjectsshouldbeexaminedatahigh

resolution.Largesizeobjectsshouldbeexaminedatalow

resolution.MultiresolutionAnalysis(cont’d)Localimagestatisticsarequitedifferentfromglobalimagestatistics.Modelingentireimageisdifficultorimpossible.Needtoanalyzeimagesatmultiplelevelsofdetail.Transform:AmathematicaloperationthattakesafunctionorsequenceandmapsitintoanotheroneTransformsaregoodthingsbecause…Thetransformofafunctionmaygiveadditional/hiddeninformationabouttheoriginalfunction,whichmaynotbeavailable/obviousotherwiseThetransformofanequationmaybeeasiertosolvethantheoriginalequationThetransformofafunction/sequencemayrequirelessstorage,henceprovidedatacompression/reductionAnoperationmaybeeasiertoapplyonthetransformedfunction,ratherthantheoriginalfunction(recallconvolution)Introduction(RobiPolikar,RowanUniversity)

WhatisaTransformandWhydoWeNeedOne?Mostusefultransformsare:Linear:wecanpulloutconstants,andapplysuperpositionOne-to-one:differentfunctionshavedifferenttransformsInvertible:foreachtransformT,thereisaninversetransformT-1usingwhichtheoriginalfunctionfcanberecovered(kindof–sortoftheundobutton…)Continuoustransform:mapfunctionstofunctionsDiscretetransform:mapsequencestosequencesTfFT-1fIntroduction

PropertiesofTransformsComplexfunctionrepresentationthroughsimplebuildingblocksCompressedrepresentationthroughusingonlyafewblocks(calledbasisfunctions/kernels)Sinusoidsasbuildingblocks:FouriertransformFrequencydomainrepresentationofthefunctionIntroduction

WhatDoesaTransformLookLike?FourierseriesContinuousFouriertransformLaplacetransformDiscreteFouriertransformZ-transformIntroduction

WhatTransformsareAvailable?JeanB.JosephFourier(1768-1830)“Anarbitraryfunction,continuousorwithdiscontinuities,definedinafiniteintervalbyanarbitrarilycapriciousgraphcanalwaysbeexpressedasasumofsinusoids” J.B.J.FourierDecember,21,1807Introduction

FourierWho…?RecallthatFTusescomplexexponentials(sinusoids)asbuildingblocks.Foreachfrequencyofcomplexexponential,thesinusoidatthatfrequencyiscomparedtothesignal.Ifthesignalconsistsofthatfrequency,thecorrelationishighlargeFTcoefficients.Ifthesignaldoesnothaveanyspectralcomponentatafrequency,thecorrelationatthatfrequencyislow/zero,small/zeroFTcoefficient.Introduction

HowDoesFTWorkAnyway?Introduction

FTatWorkFFFIntroduction

FTatWorkFIntroduction

FTatWorkComplexexponentials(sinusoids)asbasisfunctions:FAnultrasonicA-scanusing1.5MHztransducer,sampledat10MHzIntroduction

FTatWorkFTidentifiesallspectralcomponentspresentinthesignal,howeveritdoesnotprovideanyinformationregardingthetemporal(time)localizationofthesecomponents.Why?StationarysignalsconsistofspectralcomponentsthatdonotchangeintimeallspectralcomponentsexistatalltimesnoneedtoknowanytimeinformationFTworkswellforstationarysignalsHowever,non-stationarysignalsconsistsoftimevaryingspectralcomponentsHowdowefindoutwhichspectralcomponentappearswhen?FTonlyprovideswhatspectralcomponentsexist

,notwhereintimetheyarelocated.NeedsomeotherwaystodeterminetimelocalizationofspectralcomponentsIntroduction

StationaryandNon-stationarySignalsStationarysignals’spectralcharacteristicsdonotchangewithtimeNon-stationarysignalshavetimevaryingspectraConcatenationIntroduction

StationaryandNon-stationarySignals5Hz25Hz50HzPerfectknowledgeofwhatfrequenciesexist,butnoinformationaboutwherethesefrequenciesarelocatedintimeIntroduction

Non-stationarySignalsComplexexponentialsstretchouttoinfinityintimeTheyanalyzethesignalglobally,notlocallyHence,FTcanonlytellwhatfrequenciesexistintheentiresignal,butcannottell,atwhattimeinstancesthesefrequenciesoccurInordertoobtaintimelocalization

ofthespectralcomponents,thesignalneedtobeanalyzedlocally,BUTHOW?Introduction

FTShortcomingsChooseawindowfunctionoffinitelengthPutthewindowontopofthesignalatt=0TruncatethesignalusingthiswindowComputetheFTofthetruncatedsignal,save.SlidethewindowtotherightbyasmallamountGotostep3,untilwindowreachestheendofthesignalForeachtimelocationwherethewindowiscentered,weobtainadifferentFTHence,eachFTprovidesthespectralinformationofaseparatetime-sliceofthesignal,providingsimultaneoustimeandfrequencyinformationIntroduction

ShortTimeFourierTransform(STFT)Introduction

ShortTimeFourierTransform(STFT)STFTofsignalx(t):Computedforeachwindowcenteredatt=t’TimeparameterFrequencyparameterSignaltobeanalyzedWindowingfunctionWindowingfunctioncenteredatt=t’FTKernel(basisfunction)Introduction

ShortTimeFourierTransform(STFT)0100200300-1.5-1-0.500.510100200300-1.5-1-0.500.510100200300-1.5-1-0.500.510100200300-1.5-1-0.500.51WindowedsinusoidallowsFTtobecomputedonlythroughthesupportofthewindowingfunctionIntroduction

STFTatWorkIntroduction

STFT300Hz200Hz100Hz50HzSTFTprovidesthetimeinformationbycomputingadifferentFTsforconsecutivetimeintervals,andthenputtingthemtogetherTime-FrequencyRepresentation(TFR)Maps1-Dtimedomainsignalsto2-Dtime-frequencysignalsConsecutivetimeintervalsofthesignalareobtainedbytruncatingthesignalusingaslidingwindowingfunctionHowtochoosethewindowingfunction?Whatshape?Rectangular,Gaussian,Elliptic…?Howwide?Introduction

STFTTwoextremecases:W(t)infinitelylong:

STFTturnsintoFT,providingexcellentfrequencyinformation(goodfrequencyresolution),butnotimeinformationW(t)infinitelyshort:

STFTthengivesthetimesignalback,withaphasefactor.Excellenttimeinformation(goodtimeresolution),butnofrequencyinformationIntroduction

SelectionofSTFTWindowWideanalysiswindowpoortimeresolution,goodfrequencyresolutionNarrowanalysiswindowgoodtimeresolution,poorfrequencyresolutionOncethewindowischosen,theresolutionissetforbothtimeandfrequency.Timeresolution:HowwelltwospikesintimecanbeseparatedfromeachotherinthetransformdomainFrequencyresolution:HowwelltwospectralcomponentscanbeseparatedfromeachotherinthetransformdomainBothtimeandfrequencyresolutionscannotbearbitrarilyhigh!!!

Wecannotpreciselyknowatwhattimeinstanceafrequencycomponentislocated.WecanonlyknowwhatintervaloffrequenciesarepresentinwhichtimeintervalsIntroduction

HeisenbergUncertaintyPrincipleIntroduction

STFTGaussianwindowfunction:a=0.01a=0.0001a=0.00001OvercomesthepresetresolutionproblemoftheSTFTbyusingavariablelengthwindowAnalysiswindowsofdifferentlengthsareusedfordifferentfrequencies:AnalysisofhighfrequenciesUsenarrowerwindowsforbettertimeresolutionAnalysisoflowfrequenciesUsewiderwindowsforbetterfrequencyresolutionThisworkswell,ifthesignaltobeanalyzedmainlyconsistsofslowlyvaryingcharacteristicswithoccasionalshorthighfrequencybursts.Heisenbergprinciplestillholds!!!Thefunctionusedtowindowthesignaliscalledthewavelet

Introduction

WaveletTransformContinuouswavelettransformofthesignalx(t)usingtheanalysiswavelet(.)Translationparameter,measureoftimeScaleparameter,measureoffrequencyThemotherwavelet.Allkernelsareobtainedbytranslating(shifting)and/orscalingthemotherwaveletAnormalizationconstantSignaltobeanalyzedScale=1/frequencyIntroduction

WaveletTransformHighfrequency(smallscale)Lowfrequency(largescale)Introduction

WTatWorkIntroduction

WTatWorkIntroduction

WTatWorkIntroduction

WTatWorkIntroduction

TimeandFrequencyResolutionBackgroundImagePyramidsComputeareduced-resolutionapproximationoftheinputimageFiltering(Averaging,Gaussian)Down-samplingUp-sampletheoutputofthepreviousbyafactor2Computethedifferencebetweenthepredictionofstep2andtheinputto

Step1.ImagePyramidsImagePyramidsInMulti-resolutionAnalysis(MRA),aScalingFunctionisusedtocreateaseriesofapproximationsofafunctionorimage,eachdifferingbyafactor2fromitsnearestneighboringapproximations.Additionalfunctions,calledWavelet,areusedtoencodethedifferenceininformationbetweenadjacentapproximationMulti-ResolutionExpansionMulti-ResolutionExpansion

SeriesExpansionReal-valuedexpansioncoefficientsReal-valuedexpansionfunctionsIftheexpansionisUNIQUE-thatis,thereisonlyonesetofforanygiven-thearecalledbasisfunctions,andtheexpansionset,,iscalledaBASISfortheclassoffunctionsthatcanbesoexpressed.TheexpressiblefunctionsformafunctionspacethatisreferredtoastheclosespanoftheexpansionsetMulti-ResolutionExpansion

SeriesExpansionDualFunctionsMulti-ResolutionExpansion

SeriesExpansionCASE1:ExpansionfunctionsformanorthonormalbasisCASE2:Expansionfunctionsarenotorthonormal,butareanorthogonalbasis(biorthogonalbasis)CASE3:ExpansionsetisnotabasisMulti-ResolutionExpansion

ScalingFunctionsMulti-ResolutionExpansion

ScalingFunctionsThescalingfunctionsisORTHOGONALtoitsintegertranslations.Thesubspacespannedbythescalingfunctionatlowscalesarenestedwithinthosespannedathigherscales.TheonlyfunctionthatiscommontoallVj

is

f(x)=0AnyfunctioncanberepresentedwitharbitraryprecisionMulti-ResolutionExpansion

MRARequirementsMulti-ResolutionExpansion

MRARequirementsScalingVectorMulti-ResolutionExpansion

WaveletFunctionsUnionofSpacesMulti-ResolutionExpansion

Wavele