An-Iterative-Image-Registration-Technique-with-an-

121AnIterativeImageRegistrationTechniquewithanApplicationtoStereoVisionBruceD.LucasTakeoKanadeComputerScienceDepartmentCarnegie-MellonUniversityPittsburgh,Pennsylvania15213AbstractImageregistrationfindsavarietyofapplicationsincomputervision.Unfortunately,traditionalimageregistrationtechniquestendtobecostly.WepresentanewimageregistrationtechniquethatmakesuseofthespatialintensitygradientoftheimagestofindagoodmatchusingatypeofNewton-Raphsoniteration.Ourtechniqueisfasterbecauseitexaminesfarfewerpotentialmatchesbetweentheimagesthanexistingtechniques.Furthermore,thisregistrationtechniquecanbegeneralizedtohandlerotation,scalingandshearing.Weshowshowourtechniquecanbeadaptedforuseinastereovisionsystem.1.IntroductionImageregistrationfindsavarietyofapplicationsincomputervision,suchasimagematchingforstereovision,patternrecognition,andmotionanalysis.Untortunately,existingtechniquesforimageregistrationtendtobecostly.Moreover,theygenerallyfailtodealwithrotationorotherdistortionsoftheimages.Inthispaperwepresentanewimageregistrationtechniquethatusesspatialintensitygradientinformationtodirectthesearchforthepositionthatyieldsthebestmatch.Bytakingmoreinformationabouttheimagesintoaccount,thistechniqueisabletofindthebestmatchbetweentwoimageswithfarfewercomparisonsofimagesthantechniqueswhichexaminethepossiblepositionsofregistrationinsomefixedorder.Ourtechniquetakesadvantageofthefactthatinmanyapplicationsthetwoimagesarealreadyinapproximateregistration.Thistechniquecanbegeneralizedtodealwitharbitrarylineardistortionsoftheimage,includingrotation.Wethendescribeastereovisionsystemthatusesthisregistrationtechnique,andsuggestsomefurtheravenuesforresearchtowardmakingeffectiveuseofthismethodinstereoimageunderstanding.2.TheregistrationproblemThetranslationalimageregistrationproblemcanbecharacterizedasfollows:WearegivenfunctionsF(x)andG(x)whichgivetherespectivepixelvaluesateachlocationxintwoimages,wherexisavector.WewishtofindthedisparityvectorhwhichminimizessomemeasureofthedifferencebetweenF(x+h)andG(x),forxinsomeregionofinterestR.(Seefigure1).Figure1:TheimageregistrationproblemTypicalmeasuresofthedifferencebetweenF(x+h)andG(x)are:•L1norm=|()()|FxhGxxR+-∑ε•L2norm=FxhGxxR()()/+-[]()∑212ε•negativeofnormalizedcorrelation=-++()()∑∑∑FxhGxFxhGxxRxRXR()()()()//εεε212212Wewillproposeamoregeneralmeasureofimagedifference,ofwhichboththeL2normandthecorrelationarespecialcases.TheL1normischieflyofinterestasaninexpensiveapproximationtotheL2norm.FromProceedingsofImagingUnderstandingWorkshop,pp.121-130(1981).1223.ExistingtechniquesAnobvioustechniqueforregisteringtwoimagesistocalculateameasureofthedifferencebetweentheimagesatallpossiblevaluesofthedisparityvectorh—thatis,toexhaustivelysearchthespaceofpossiblevaluesofh.Thistechniqueisverytimeconsuming:ifthesizeofthepictureG(x)isNXN,andtheregionofpossiblevaluesofhisofsizeMXM,thenthismethodrequiresO(M2N2)timetocompute.Speedupattheriskofpossiblefailuretofindthebesthcanbeachievedbyusingahill-climbingtechnique.Thistechniquebeginswithaninitialestimateh0ofthedisparity.Toobtainthenextguessfromthecurrentguesshk,oneevaluatesthedifferencefunctionatallpointsinasmall(say,3X3)neighborhoodofhkandtakesasthenextguesshk+1thatpointwhichminimizesthedifferencefunction.Aswithallhill-climbingtechniques,thismethodsuffersfromtheproblemoffalsepeaks:thelocaloptimumthatoneattainsmaynotbetheglobaloptimum.ThistechniqueoperatesinO(M2N)timeontheaverage,forMandNasabove.Anothertechnique,knownasthesequentialsimilaritydetectionalgorithm(SSDA)[2],onlyestimatestheerrorforeachdisparityvectorh.InSSDA,theerrorfunctionmustbeacumulativeonesuchastheL1orL2norm.Onestopsaccumulatingtheerrorforthecurrenthunderinvestigationwhenitbecomesapparentthatthecurrenthisnotlikelytogivethebestmatch.Criteriaforstoppingincludeafixedthresholdsuchthatwhentheaccumulatederrorexceedsthisthresholdonegoesontothenexth,andavariablethresholdwhichincreaseswiththenumberofpixelsinRwhosecontributiontothetotalerrorhavebeenadded.SSDAleavesunspecifiedtheorderinwhichtheh’sareexamined.NotethatinSSDAifweadoptasourthresholdtheminimumerrorwehavefoundamongthehexaminedsofar,weobtainanalgorithmsimilartoalpha-betapruninginmin-maxgametrees[7].Herewetakeadvantageofthefactthatinevaluatingminh∑xd(x,h),whered(x,h)isthecontributionofpixelxatdisparityhtothetotalerror,the∑xcanonlyincreaseaswelookatmorex’s(morepixels).Someregistrationalgorithmsemployacoarse-finesearchstrategy.See[6]foranexample.Oneofthetechniquesdiscussedaboveisusedtofindthebestregistrationfortheimagesatlowresolution,andthelowresolutionmatchisthenusedtoconstraintheregionofpossiblematchesexaminedathigherresolution.Thecoarse-finestrategyisadoptedimplicitlybysomeimageunderstandingsystemswhichworkwithapyramidofimagesofthesamesceneatvariousresolutions.Itshouldbenatedthatsomeofthetechniquesmentionedsofarcanbecombinedbecausetheyconcernorthogonalaspectsoftheimageregistrationproblem.Hillclimbingandexhaustivesearchconcernonlytheorderinwhichthealgorithmsearchesforthebestmatch,andSSDAspecifiesonlythemethodusedtocalculate(anestimateof)thedifferencefun