A-class-of-algorithms-for-fast-digital-image-regis

IEEETRANSACTIONSONCOMPUTERS,VOL.c-21,NO.2,FEBRUARY1972179AClassofAlgorithmsforFastDigitalImageRegistrationDANIELI.BARNEA,MEMBER,IEEE,ANDHARVEYF.SILVERMAN,MEMBER,IEEEAbstract-TheautomaticdeterminationoflocalsimilaritybetweentwotionVgeneralizesthisclassofalgorithmsandpresents,instructureddatasetsisfundamentaltothedisciplinesofpatternrecognitionandimageprocessing.Aclassofalgorithms,whichmaybeusedtodeter-timinesimilarityinafarmoreefficientmannerthanmethodscurrentlyinmentofthegivenexamples.use,isintroducedinthispaper.Theremaybeasavingofcomputationtimeoftwoordersofmagnitudeormorebyadoptingthisnewapproach.Theproblemoftranslationalimageregistration,usedforanexamplethroughout,isdiscussedandtheproblemswiththemostwidelyusedRegistrationisinherentlybasictoanyimageprocessingmethod-correlationexplained.Simpleimplementationsofthenewalgo-..irithmsareintroducedtomotivatethebasicideaoftheirstructure.Realsystem.WhenitisdesiredtodetectchangesorperformadatafromITOS-1satellitesarepresentedtogivemeaningfulempiricalmappingoftwosimilarimages,itisnecessaryformeaningfuljustificationfortheoreticalpredictions.resultstohavetheimagesregistered.IfthepicturesdonotIndexTerms-Registrationefficiency,sequentialsimilaritydetectiondifferinmagnificationandrotation,thenthebesttransla-algorithms,spatialcrosscorrelation,spatialregistrationofdigitalimages.tionalfitwillyieldtherequiredregistration.(Theproblemsarisingfrommagnificationandrotationwillnotbecon-I.INTRODUCTIONsideredhereforthesakeofbrevity.However,themethodsTHEAUTOMATICdeterminationoflocalsimilarityareapplicablewhenpropermodificationsareintroduced.)betweentwostructureddatasetsisfundamentaltoLettwoimages,SthesearchareaandWthewindowbethedisciplinesofpatternrecognitionandimagedefinedasshowninFig.1.SistakenasanLXLarrayofprocessing.Aclassofalgorithms,whichmaybeusedtodigitalpictureelementswhichmayassumeoneofKgreydeterminesimilarityinafarmoreefficientmannerthanlevels;i.e.,methodscurrentlyinuse,isintroducedinthispaper.By0S(i,j)K-1adoptingthisnewapproachtheremaybeasavingofcom-1.jL.putationtimeoftwoordersofmagnitudeormore.ThemethodmostwidelyusedforsimilaritydetectionisWisconsideredtobeanMXM,MsmallerthanLarrayofcorrelation.Infactthesimilaritydetectionproblemitselfispictureelementshavingthesamegreyscalerange;generallycalledcorrelation.Inthispaper,however,theigtdistinctionbetweenthemathematicalmethod,correlation,i..andtheclassofsimilaritydetectionproblemswillbemain-0W(1,m)K-1tained;foritwillbeshownthatproceduresotherthan1i)mMI.thosecurrentlyinpracticewillyieldefficientandaccurateresults.ItwillbeconvenienttointroduceanotationforMXMTheclassofsequentialsimilaritydetectionalgorithmswhollycontainedsubimages.(SSDAs)introducedheremaybeappliedtotheentirespectrumofsimilaritydetectionproblems.AbroadtheorySMiA(l,m)S(i+I-1,j+m-1),relatinggeneralpropertiesofthesealgorithmscanbede-I11m_veloped.Inthispaper,however,theutilityofSSDAswillbei,jL-M+1.(1)illustratedbytheirapplicationtoaspecificproblem,transla-tionalregistration,whichisbasictoimageprocessing.EachMXMsubimageofScanbeuniquelyreferencedbyInSectionII,thetranslationalregistrationproblemwillbethespecificationofitsupperleftcorner'scoordinates(i,j).introduced.SectionIIIwilldescribethecomputationalThesewillbeusedtodefinereferencepoints.Itwillbeefficiencyofcorrelationmethods.InSectionIVsomeex-assumedthatenoughaprioriinformationisknownaboutamplesofSSDAsarepresentedintheordertheywerethedislocationbetweenthewindowandsearchareasothatchronologicallyinvestigated.ItisintendedthatthissectiontheparametersLandMmaybeselectedwiththevirtualimpartanintuitivefeelingaboutSSDAstothereader.Sec-guaranteethat,atregistration,acompletesubimageiscon-tainedinthesearchareaasshowninFig.1.ManuscriptreceivedMay13,1971;revisedAugust6,1971.Translationalregistration,therefore,isasearchoversomeD.I.BarneawaswiththeIBMT.J.WatsonResearchCenter,subsetoftheallowedrangeofreferencepointstofindaYorktownHeights,N.Y10598.HeisnowwithBijim,Holon,Israel-oniehcniaeuiaetasmsiiaH.F.SilvermaniswiththeIBMT.J.WatsonResearchCenter,poni,])wihidctsauiaetasmsiiaYorktownHeights,N.Y.10598.tothegivenwindow.180IEEETRANSACTIONSONCOMPUTERS,FEBRUARY1972LthetworeasonswhicharegenerallygivenforusingtheALLOWMcorrelationmethodarethat:1)correlationappearstobeaRANGEOFnaturalsolutionforthemean-square-errorcriteria[31;andREFERENCEmensur-roadL-M+IPOINTSSUBIMAGESi'J2)thatanalog-opticalmethodsimplementcorrelationeasily[4].I-U|TrjHowever,thereisnoguaranteeforanymethodthataL\\\Msolutioniscorrectorunique.Thereseemstobe,therefore,tfLIInoadequatejustificationfortheuseofcorrelationtosolveSEARCHAREA-SWINDOW-Walldigitalregistrationproblems.Algorithms,suchasthoseFig.1.Searchspace.presentedinthispaper,whichhaveselectabledistancemeasurepropertiesandlowercomputationalcomplexity,III.COMPUTATIONALEFFICIENCYappeartobeamorefittingchoice.OFCORRELATIONMETHODSB.TheCostofCorrelationA.CorrelationMethodThenormalizedcorrelationsurfacemaybecalculatedbyThemethodmostwidelyusedfortheautomaticdetermi-directmeansorbyfastFouriertransform(FFT)methodsnationoftran