Pseudo-polarbasedestimationoflargetranslationsrotationsand scalingsinimages ¤ Y.Keller 1,2

Pseudo-polarbasedestimationoflargetranslationsrotationsand

scalingsinimages

¤Y.Keller1;2,A.Averbuch1,M.Isreali3

1SchoolofComputerScience

TelAvivUniversity,TelAviv69978,Israel

2Dept.ofElectricalEngineeringSystems

Tel-AvivUniversityTel-Aviv69978,Israel

3FacultyofComputerScience,Technion,

Haifa32000,Israel

Phone:*972-55-694-464

Fax:*972-151-55-694-464

Email:keller@post.tau.ac.il

SubmittedtotheIEEETransactionsonImageProcessing

August2002

Abstract

Oneofthemajorchallengesrelatedtoimageregistrationistheestimationoflargemotionswithoutpriorknowledge.ThispaperpresentsaFourierbasedapproachthatestimateslargetranslation,scaleandrotationmotions.Thealgorithmusesthepseudo-polartransformtoachievesubstantialimprovedapproximationsofthepolarandlog-polarFouriertransformsofanimage.Thus,rotationandscalechangesarereducedtotranslationswhichareestimatedusingphasecorrelation.Byutilizingthepseudo-polargridweincreasetheperformance(accuracy,speed,robustness)oftheregistrationalgorithms.Scalesupto4andarbitraryrotationanglescanberobustlyrecovered,comparedtoamaximumscalingof2recoveredbythecurrentstate-of-the-artalgorithms.Thealgorithmutilizesonly1DFFTcalculationswhoseoverallcomplexityissigni…cantlylowerthanpriorworks.Experimentalresultsdemonstratetheapplicabilityofthesealgorithms.

Keywords:Globalmotionestimation,Sub-pixelregistration,Gradientmethods,image

alignment

EDICSCategory={2-ANAL,2-MOTD}

11Introduction

Imageregistrationplaysavitalroleinmanyimageprocessingapplicationssuchasvideocompres-

sion[1,2],videoenhancement[3]andscenerepresentation[4,5,6]tonameafew.Thisproblemwas

analyzedusingvariouscomputationaltechniques,suchaspixeldomainGradientmethods[1,4,5],

correlationtechniques[20]anddiscreteFourier(DFT)domainalgorithms[10,16].Gradientmeth-

odsbasedimageregistrationalgorithmsareconsideredtobethestate-of-the-art.But,mayfail

unlessthetwoimagesaremisalignedbyamoderatemotion.Fourierbasedschemes,whichareable

toestimaterelativelylargerotation,scalingandtranslation,areoftenusedasbootstrapforthe

moreaccurategradientmethods.ThebasicnotionrelatedtoFourierbasedschemesistheshift

property[23]oftheFouriertransformwhichallowsrobustestimationoftranslationsusingthenor-

malizedphase-correlationalgorithm[10,12,13,14,15].Hence,inordertoaccountforrotationsand

scaling,theimageistransformedintoapolarorlog-polarFouriergrid(referredtoastheFourier-

Mellintransform).Rotationsandscalingarereducedtotranslationsintheserepresentationsand

areestimatedusingphase-correlation.

Inthispaperweproposetoestimatethepolarandlog-polarDFTusingthepseudo-polarFFT

(PPFFT)[27,28].ThePPFFTestimatestheDFTonanon-Cartesiangrid,whichisgeometri-

callysimilartothepolargrid.Hence,byinterpolatingthepolarandlog-polarDFTusingthe

PPFFTasigni…cantlysmallerinterpolationerrorisachieved.Furthermore,thesmallertherela-

tiverotation/scalingbetweentheimagesbecomes,thesmallerthedi¤erencebetweentheirPPFFT

magnitudesandtheinterpolatedpolar/log-polarDFTmagnitudes.Inpriorworks[16,21]the

relativeinterpolationerrorisnotdecreasedbythedecreaseoftherelativemotion.

Theresultingalgorithmisabletorobustlyregisterimagesrotatedbyarbitraryanglesandscaled

uptoafactorof4.Itshouldbenotedthatthemaximumscalefactorrecoveredin[16]and[21]

was2.0and1.8,respectively.Inparticular,theproposedalgorithmdoesnotresulttointerpolation

ineitherspatialorFourierdomain.Only1DFFToperationsareused,makingitmuchfasterand

especiallysuitedforreal-timeapplications.

Therestofpaperisorganizedasfollows:PriorresultsrelatedtoFFTbasedimageregistration

aregiveninSection2,whilethepseudo-polarFFT,whichisusedasabasisfortheproposedalgo-

rithmispresentedinSection3.Theproposedalgorithm,ispresentedinSection4anditsaccuracy

isanalyzedinSection5.ExperimentalresultsarediscussedinSection6and…nalconclusionsare

giveninSection7.

22Previousrelatedwork

2.1Translationestimation

ThebasisoftheFourierbasedmotionestimationistheshiftproperty[23]oftheFouriertransform.

Denoteby

Fff(x;y)g,bf(!x;!y)(2.1)

theFouriertransformoff(x;y).Then,

Fff(x+¢x;y+¢y)g=bf(!x;!y)ej(!x¢x+!y¢y):(2.2)

Equation(2.2)canbeusedfortheestimationofimagetranslation[10,15].Assumetheimages

I1(x;y)andI2(x;y)satisfy

I1(x+¢x;y+¢y)=I2(x;y):(2.3)

Equation(2.3)isFouriertransformed,yielding

bI1(!x;!y)ej(!x¢x+!y¢y)=bI2(!x;!y)(2.4)

andbI2(!x;!y)bI1(!x;!y)=ej(!x¢x+!y¢y):(2.5)

Thus,thetranslationparameters(¢x;¢y)canbeestimatedinthespatialdomain[10,11]bytaking

theinverseFFTofEq.(2.5)

Corr(x;y),F¡1nej(!x¢x+!y¢y)o=±(x¡¢x;y¡¢y)(2.6)

andby…ndingthepositionofthemaximumvalueofthecorrelationfunctionCorr(x;y):

(x;y)=arg½max(~x;~y)fCorr(~x;~y)g¾:(2.7)

Bynormalizingtheinputimages’magnitude,theNormalizedphasecorrelation[10,11]isderived

]Corr(!x;!y),bI1(!x;!y)bI¤2(!x;!y)¯¯¯bI1(!x;!y)¯¯¯¯¯¯bI¤2(!x;!y)¯¯¯=ej(!x¢x+!y¢y)(2.8)

where*denotesthecomplexconjugate.

Thisestimatorof]Corrisrobusttogainando¤setchanges

I1=a¢I2+b

whereaandbarescalars.TheintensitygainaiscompensatedbyEq.(2.8)whiletheo¤setb

a¤ectsonlytheDCcoe¢cientof]Corr.

3