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], ).

2 Duetothecom-putationalcostofspatialdomai nconvolution,severalin-exactbut fastspatialdomainmatchingmethodshave alsobeendeveloped[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).

3 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. 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.

4 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).

5 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].)

6 Insomeschemeswaveletconvolutionisinfacti mple-mentedusingtheFourierconvolutionthe orem),efficientfeaturetrackingcanbeimple mentedwithwaveletsandothermulti-resoluti onrepresentationsusinga ,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]. A ,it is probablyfairtosaythata besearchedbytheuser.

7 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 (!)

8 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].

9 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.

10 Theimagemeanandlocal(RMS)energymustbecom putedat eachu; v, (M N+1)2locations,resultingin almost3N2(M N+1)2oper-ations(countingadd,subtract,mu ltiplyasoneoperationeach).Thiscomputatio nis 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].