Fast Normalized Cross-Correlation

1 Thisis an expandedversionof apaperfromVisionInterface,1995(reference [10])FastNormalizedCross-CorrelationJ. P. Lewis IndustrialLight&MagicAbstractAlthoughit iswellknownthatcrosscorrelationcanbeeffi cientlyimplementedin thetransformdomain,thenor-malizedformofc rosscorrelationpreferredforfeaturematchi ngapplicationsdoesnothave a signals(crosscorrelation)isa standardapproachtofeaturedetection[6, 7]aswellasa componentofmoresophisticatedtechniques( [3]).Textbookpresentationsofcorrelationd escribetheconvo-lutiontheoremandtheatten dantpossibilityofefficientlycomputingcor relationinthefrequency (correlationcoefficient)preferredintempl atematchingdoesnothave a correspondinglysim-pleandefficientfreque ncy ( ,[7], ).Duetothecom-putationalcostofspatialdom ainconvolution,severalin-exactbut fastspatialdomainmatchingmethodshave alsobeendeveloped[2].

2 Thispaperdescribesa recentlyin-troducedalgorithm[10] (Section5).Sincewearepresentinga versionofa familiarandwidelyusedalgorithmnoattemptw illbemadetosur-vey theliteratureonselectionoffeatures,white ning,fastconvolutiontechniques,extension s,alternatetech-niques, 7, 13] andrecentpaperssuchas[1, 19].Neverthe-less,duetothevarietyoffeatu retrackingschemesthathave beenadvocatedit maybenecessarytoestablishthatnormalizedc ross-correlationremainsa viablechoiceforsomeif thepaperselfcontained,section2 de-scribesnormalizedcross-correlationand section4 describeshow mo-tivatedbythedistancemeasure(squaredEu clideandis-tance)d2f;t(u; v) =Xx;y[f(x; y) t(x u; y v)]2(wherefis theimageandthesumis overx; yunderthewindowcontainingthefeaturetposi tionedatu; v).Intheexpansionofd2d2f;t(u; v) =Xx;y[f2(x; y) 2f(x; y)t(x u; y v)+t2(x u; y v)]thetermPt2(x u; y v) (x; y)is approximatelyconstantthentheremainingcro ss-correlationtermc(u; v) =Xx;yf(x; y)t(x u; y v)(1)is a (1)fortemplatematching: If theimageenergyPf2(x; y)varieswithposition,matchingusing(1) ,thecorre-lationbetweenthefeatureandanex actlymatchingregionintheimagemaybelessth anthecorrelationbetweenthefeatureanda brightspot.

3 Therangeofc(u; v)is dependentonthesizeofthefeature. Eq.(1)is ,yieldinga cosine-like correlationcoefficient (u; v) =(2)Px;y[f(x; y) fu;v][t(x u; y v) t]nPx;y[f(x; y) fu;v]2Px;y[t(x u; y v) t]2o0:5where tis themeanofthefeatureand fu;vis themeanoff(x; y) referto(2) is clearthatnormalizedcross-correlation(NCC )is nottheidealapproachto featuretrackingsinceit is notinvari-antwithrespecttoimagingscale,r otation,andperspec-tive beenaddressedinvariousschemesincludingso methatincorporateNCCasa , thefollowingdiscussionwillpointoutsomeof theissuesinvolvedinvariousapproachestofe aturetracking,andwillconcludethatNCCis a (SSDA)[2]is theobservationthatfullprecisionis onlyneedednearthemaximumofthecross-corre lationfunction, [2] describeseveralwaysofimplementing reducedprecision .AnSSDA implementationofcross-correlationproceed sbycomputingthesummationin(1)inrandomord erandusesthepartialcomputationasaMonteCa rloestimateofwhethertheparticularmatchlo -cationwillbeneara a particularlocationis terminatedbe-forecompletingthesumif theestimatesuggeststhatthelocationcorres pondstoa performswellwhenthecorrelationsurfacehas shallow probablysatisfiedinmany applications,it is evidentthatimagescontainingarraysofobjec ts(pebbles,bricks,othertextures)cangen-e ratemultiplenarrowextremainthecorrelatio nsurfaceandthusmisleadanSSDA secondarydisad-vantageofSSDA is thatit hasparametersthatneedto de-termined(thenumberoftermsusedtoforman estimateofthecorrelationcoefficient,andt heearlyterminationthresholdonthisestimat e).

4 Isassumedthatfeaturetranslationbetweenad jacentframesissmallthenthetranslation(an dparametersofanaffinewarpin[19]) canbeobtainedbygradientdescent[12]. many , (aswithSSDA)texturedtemplatesre-sultinma tchingerrorsurfaceswithnarrow thatthesearchis inherentlyserial, (active contourmodels)have thedisad-vantagethatthey cannottrackobjectsthatdonothave adefinablecontour. Some objects donothave a clearlydefinedboundary(whetherduetointri nsicfuzzynessorduetolightingconditions), butneverthelesshave a contourmodelsaddressa moregeneralproblemthanthatofsimpletempla tematchinginthatthey providea , featurethatmovesbyasignificantfractionof itsownsizeacrossframes,whereasthisamount oftranslationcouldputa snake usefulconvolutiontheoremforwaveletsissti lla matterofdiscussion( ,[11];insomeschemeswaveletconvolutionisi nfactimple-mentedusingtheFourierconvolut iontheorem),efficientfeaturetrackingcanb eimplementedwithwaveletsandothermulti-re solutionrepresentationsusinga ,however, thattheimagescontainsufficientlowfrequen cy section6, idealfeaturesaresome-timesunavailableand onemustresorttopoorlydefined features thatmayhave littlelow-frequency informa-tion,suchasa hasbeenadvo-catedbyvariousauthors, [19] derivesanop-timalfeaturetrackingschemewi thinthegradientsearchframework, templatematch-ingalgorithmsinthepresence ofvariousimagedistor-tions[4] foundthatNCCprovidesthebestperformancein allimagecategories, generalhierarchicalframeworkformotiontra ck-ingis discussedin[1].

5 A ,it is probablyfairtosaythata besearchedbytheuser. NCCcanbeused asis toprovidesimplefeaturetracking,orit canbeusedasa componentofa moresophisticated(possiblymulti-resoluti on)matchingschemethatmayaddressscaleandr otationinvariance,featureupdating, [18]. We acknowledgeNCCasa defaultchoiceinmanyapplicationswherefeat uretrackingis notinitselfa sub-jectofstudy, aswellasanoccasionalbuildingblockinvisio nandpatternrecognitionresearch( [3]).A fastalgorithmis (2)andassumethatwehaveimagesf0(x; y) f(x; y) fu;vandt0(x; y) t(x; y) tinwhichthemeanvaluehasalreadybeenremove d:num (u; v) =Xx;yf0(x; y)t0(x u; y v)(3)Fora searchwindow ofsizeM2anda featureofsizeN2(3)requiresapproximatelyN 2(M N+ 1)2additionsandN2(M N+ 1) (3)isa convolutionoftheimagewiththereversedfeat uret0( x; y)andcanbecomputedbyF 1fF(f0)F (t0)g(4) conju-gateaccomplishesreversalofthefeatu reviatheFouriertransformpropertyFf ( x) =F (!)

6 ImplementationsoftheFFTalgorithmgenerall yrequirethatf0andt0beextendedwithzerosto a (3)isthen12M2log2 Mrealmultiplicationsand18M2log2 spa-tial computation(3)isapproximatelyN2M2multipl i-cations/additions,andthedirectmethodis ; fast convolutionalgo-rithmsthatdonotusetransf ormdomaincomputation[13].Theseapproaches fallintotwo categories:algo-rithmsthattrademultiplic ationsforadditionaladditions,andapproach esthatfinda lowerpointontheO(N2)characteristicof(one -dimensional)convolutionbyem-beddingsect ionsofa one-dimensionalconvolutionintoseparatedi mensionsofa [13] andinany casetheydonotaddresscomputationofthedeno minatorof(2). (4)canbeefficientlycomputedinthetransfor mdomain,severaltransformdomainmethodsofa pproxi-matingtheimageenergynormalization in(2)have domainprocessing,butselectionofthecutoff frequency is problematic alow cutoff mayleave significantimageenergyvariations,whereas a highcutoff mayremove [9].

7 Inthisapproachthetransformcoefficientsar enormalizedtounitmagnitudepriortocomputi ngcorrelationinthefrequency ,thecorrelationisbasedonlyonphaseinforma tionandisinsensitive ,it hasthedrawbackthatalltransformcomponents areweightedequally, [16] andis ( 0:95) imagecorrelationthebestpre-filteringisap proximatelyLaplacianratherthana (2),wenotethatthemeanofthefeaturecanbepr ecomputed,leavingnum (u; v)=Xf(x; y)t0(x u; y v) fu;vXt0(x u; y v)Sincet0haszeromeanandthuszerosumtheter m fu;vPt0(x u; y v)is alsozero,sothenumeratorofthenormalizedcr oss-correlationcanbecomputedusing(4).Exa miningthedenominatorof(2),thelengthofthe fea-turevectorcanbeprecomputedinapproxim ately3N2operations(smallcomparedtothecos tofthecross-correlation),andin ;y[f(x; y) fu;v]2. Theimagemeanandlocal(RMS)energymustbecom putedat eachu; v, (M N+1)2locations,resultingin almost3N2(M N+1)2oper-ations(countingadd,subtract,mu ltiplyasoneoperationeach).

8 Thiscomputationis morethanis requiredforthedirectcomputationof(3)andi t mayconsiderablyout-weightthecomputationi ndicatedby(4) (runningsum)oftheimageandimagesquareover thesearcharea, ,s(u; v) =f(u; v)+s(u 1; v)+s(u; v 1) s(u 1; v 1)s2(u; v) =f2(u; v)+s2(u 1; v)+s2(u; v 1) s2(u 1; v 1)withs(u; v) =s2(u; v) = 0wheneitheru; v <0. Theenergyoftheimageunderthefeaturepositi onedatu; vis thenef(u; v) =s2(u+N 1; v+N 1) s2(u 1; v+N 1) s2(u+N 1; v 1)+s2(u 1; v 1) ;y[f(x; y) fu;v]2cannowbecomputedwithveryfewoperati onssinceit ,whichislessthanthecostofcomputingthenum eratorby(4)andconsiderablylessthanthe3N2 (M N+ 1)2requiredtocomputePx;y[f(x; y) fu;v]2at eachu; definitesumfroma pre-computedrunningsumhasbeenindependent lyusedina numberoffields;a computergraphicsapplicationisdevelopedin [5].

9 If thesearchforthemaximumofthecorrelationsu rfaceisdoneina systematicrow-scanor-derit generalpur-posecomputerthesizeofthetable is nota majorconsid-eration,however, (u; v)ands2(u; v)expressionsaremarginallystable,meaning thattheirz-transformH(z) = 1=(1 z 1)(onedimen-sionalversionhere)hasa poleatz= 1, whereasstabil-ityrequirespolestobestrict lyinsidetheunitcircle[14]. ,ForestGump, [20], Matador, Advance[21],andAfterEffects[22].Thealgor ithmdescribedinthispaperwasdevelopedfort hemovieForestGump(1994), thatmovieincludedthereplacementofvarious movingelementsandtheadditionofa contemporaryactorintosearchwindow(s)leng thdirectNCCfastNCC168 200;150 :Two trackingsequencesfromForestGumpwerere-ti medusingbothdirectandfastNCCalgorithmsus ingidenticalfeaturesandsearchwindowsona 100 MhzR4000processor.

10 Thesetimesincludea162sub-pixelsearch[17] (2)(directconvolution) (s)FlintfastNCC40211021 (subpixel=1)4021102n/a21seconds(subpixel =8)Table2:Measuredtrackingtimesona (noswappingoccurred).FlintsettingswereMA TCHLUM(ONLY),FIXEDREF,OVER-SAMPLE OFF. It appearsthatsubpixel searchis onlyavailablein :Measuredrelativeperformanceoftrans-form domainversusspatialdomainnormalizedcross -correlationasa functionofthesearchwindow size(depthaxis) :Atrackedfeaturefroma specialeffectsse-quenceinthemovieForestG ump. Theregionis small( )areafromthisregionwouldnotprovidea sequencewereautomati-callytrackedoverthe remainingframes; performanceofouralgorithmisa performanceincreasesalongthewindowsizeax is( );a higherresolutionplotwouldshowanadditiona lripplereflect-ingtherelationbetweenthes earchwindow illustratestheperformanceobtainedina comparestheperformanceofouralgorithmwith thatofa small( ) featuresizewouldsuf-ficeinanidealdigital image,inpracticemuchlargerfea-turesizesa ndsearchwindowsaresometimesrequiredorpre ferred: Theimagesequencesusedinfilmandvideoareso metimesobtainedfrommovingcamerasandmayha ve considerabletranslationbetweenframesduet ocamerashake.