pqqgraph

EcientNeighbourhoodComputingforDiscreteRigidTransformationGraphSearchYukikoKenmochi1,PhucNgo2,HuguesTalbot1,andNicolasPassat31UniversiteParis-Est,LIGM,CNRS,France2CEALIST–DIGITEOLabs,France3UniversitedeReimsChampagne-Ardenne,CReSTIC,FranceAbstract.
Rigidtransformationsareinvolvedinawidevarietyofimagepro-cessingapplications,includingimageregistration.
Inthiscontext,werecentlyproposedtodealwiththeassociatedoptimizationproblemfromapurelydiscretepointofview,usingthenotionofdiscreterigidtransformation(DRT)graph.
Inparticular,alocalsearchschemewithintheDRTgraphtocomputealocallyopti-malsolutionwithoutanynumericalapproximationwasformerlyproposed.
Inthisarticle,weextendthisstudy,withthepurposetoreducethealgorithmiccomplex-ityoftheproposedoptimizationscheme.
Tothisend,weproposeanovelalgo-rithmicframeworkforjust-in-timecomputationofsub-graphsofinterestwithintheDRTgraph.
Experimentalresultsillustratethepotentialusefulnessofourap-proachforimageregistration.
Keywords:imageregistration,discreterigidtransformation,discreteoptimiza-tion,DRTgraph.
1Introduction1.
1DiscreteRotationsandDiscreteRigidTransformationsIncontinuousspaces(i.
e.
,Rn),rotationsaresomeofthesimplestgeometrictransfor-mations.
However,inthediscretespaces(i.
e.
,Zn),theiranalogues,namelydiscreterotations,aremorecomplex.
Theinducedchallengesarenotsimplyduetohigh-dimensionality:indeed,eveninZ2,discreterotationsraisemanydiculties,derivingmainlyfromtheirnon-necessarybijectivity[1].
Inthiscontext,discreterotations–andthecloselyrelateddiscreterigidtansformations–havebeenwidelyinvestigated.
Fromacombinatorialpointofview,discreterotationshavebeencarefullystudied[2–4],inparticulartoshedlightonremarkablecongurationsinducedbytheperiodicityofrotationswithrespecttothediscretegrid.
Atthefrontierbetweencombinatoricsandalgorithmics,theproblemof2Dpatternmatchingunderdiscreterotationshasalsobeenexplored[5,6].
Fromanalgorithmicpointofview,eortshavebeendevotedtoeectivelycom-putediscreterotations.
Inparticular,thequasi-shearrotations[7,8]wereintroducedtopreservebijectivity,bydecomposingrotationsintosuccessivequasi-shears.
TheresearchleadingtotheseresultshasreceivedfundingfromtheFrenchAgenceNationaledelaRecherche(GrantAgreementANR-2010-BLAN-0205).
E.
Barcuccietal.
(Eds.
):DGCI2014,LNCS8668,pp.
99–110,2014.
cSpringerInternationalPublishingSwitzerland2014100Y.
Kenmochietal.
Finally,fromanapplicativepointofview,discreterotationshavebeenusedforim-age/signalprocessingpurposes[9,10].
Otherstrategieshavealsobeenproposedtopre-process2Dimagesinordertoguaranteethepreservationoftopologicalpropertiesunderdiscreterigidtransformations[11].
Recently,weproposedanewparadigmtodealwithdiscreterotations,andmoregen-erallyrigidtransformations.
Thisparadigmreliesonacombinatorialstructure,calleddiscreterigidtransformationgraph(DRTgraph,forshort)[12].
Thisstructuredescribesthequanticationoftheparameterspaceofrigidtransformations,intheframeworkofhingeangles,pioneeredin[13–15].
TheDRTgraphhasalreadyallowedustocontributetothestateoftheartonrigidtransformationsfromacombinatorialpointofview,byestablishingthecomplexityof"free"[12]and"constrained"[16]discreterigidtransformations.
Fromanalgorithmicpointofview,ithasbeenusedtocharacterisetopologicaldefectsintransformedimages[17].
Finally,werecentlystartedtoexploretheapplicativepossibilitiesoeredbytheDRTgraph.
Inparticular,wehaveconsidereditspotentialusefulnessinthecontextofimageregistration[18].
1.
2RegistrationIssuesInthecontextofimageprocessing,geometrictransformationsareoftenconsideredforregistrationpurposes[19].
Registrationisindeedacomplex,oftenill-posedproblem,thatconsistsofdeningthetransformationthatisrequiredtocorrectlymapasourceimageontoatargetimage.
Registrationismandatoryinvariousapplicationelds,fromremotesensing[20]tomedicalimaging[21].
Accordingtothespecicitiesoftheseelds,registrationcanimplicatedierenttypesofimages(2D,3D)andtransformations,bothrigidandnon-rigid.
However,theproblemremainsalmostthesameinallapplications.
GiventwoimagesAandB,weaimatndingatransformationTwithinagiventransformationspaceT.
ThistransformationminimizesagivendistancedbetweentheimageAandthetransformedimageT(B)oftheimageBbyT,i.
e.
T=argminT∈Td(A,T(B))(1)Inrecentworks[18],weinvestigatedhowtousetheDRTgraphinordertosolvethisprobleminthecaseofrigidregistrationof2Dimages.
Thenoveltyofthisapproach,withrespecttothestateoftheart,wastoprovideexacttransformationelds,soastoavoidanyinterpolationprocessandnumericalapproximations.
Inthiscontext,apreliminaryalgorithmwasproposedforcomputingalocalmin-imumforEq.
(1),thusprovidingasolutioninaneighbourhoodofdepthk≥1,totheaboveregistrationproblem.
ThisalgorithmstronglyreliesontheDRTgraph,andconsistsofexploringasub-graphdenedaroundagivenvertex,modelinganinitialtransformation.
ItstimecomplexitywasO(mkN2),whichislinearwithrespecttotheimagesize,butexponentialwithrespecttotheneighbourhooddepth(withmthesizeofthe1-depthneighbourhood).
EcientNeighbourhoodComputingforDRTGraphSearch1011.
3ContributionWeproposeanimprovedalgorithm(Sec.
3),whichdramaticallyreducestheexponentialcomplexityofthatdevelopedin[18].
Indeed,weshowthatthek-depthneighbourhoodofaDRTgraphcanbecomputedwithatimecomplexityO(kN2)(Sec.
4).
Experimentsemphasisethemethodologicalinterestoftheproposedapproach(Sec.
5).
2IntroductiontoDiscreteRigidTransformationGraphs2.
1RigidTransformationSpaceInthecontinuousspaceR2,arigidtransformationisabijectionT:R2→R2,dened,foranyx=(x,y)∈R2,byT(x)=cosθsinθsinθcosθxy+a1a2(2)wherea1,a2∈Randθ∈[0,2π[(TissometimesnotedTa1a2θ).
InordertoapplysuchrigidtransformationsonZ2,apost-processingdigitizationisrequired.
Moreprecisely,adigitizedrigidtransformationT:Z2→Z2isdenedasT=DTwhereD:R2→Z2isaroundingfunction.
Inotherwords,foranyp=(p,q)∈Z2,wehaveT(p)=pq=DT(p)=[pcosθqsinθ+a1][psinθ+qcosθ+a2](3)TheuseoftheroundingfunctionDimpliesthatdigitizedrigidtransformationsarenotcontinuouswithinthe3Dparameterspaceinducedbya1,a2andθ.
Thetransfor-mationsleadingtosuchdiscontinuitiesarecalledcriticaltransformations.
Inthespace(a1,a2,θ),thesubspaceofcriticaltransformationsiscomposedof2DsurfacesΦpqpandΨpqq,analyticallydened,foranyp=(p,q)∈Z2andanyvertical(resp.
horizon-tal)pixelboundaryx=p+12(resp.
y=q+12)withp∈Z(resp.
q∈Z),byΦpqp:pcosθqsinθ+a1=p+12(4)Ψpqq:psinθ+qcosθ+a2=q+12(5)Foragiventriplet(p,q,p)(resp.
(p,q,q)),Φpqp(resp.
Ψpqq)iscalledavertical(resp.
horizontal)tippingsurfaceintheparameterspace(a1,a2,θ),andavertical(resp.
hori-zontal)tippingcurveinthe2Dplane(a1,θ)(resp.
(a2,θ)).
ForanimageofsizeN*N,ΦpqpandΨpqqverifyp,q∈[[0,N1]]andp,q∈[[0,N]].
ExamplesoftippingsurfacesandcurvesareillustratedinFig.
1.
2.
2DiscreteRigidTransformationGraphAsetoftippingsurfacesinducesasubdivisionofthe(a1,a2,θ)spaceintoclasses,eachconsistingoftransformationsTa1a2θsuchthat(a1,a2,θ)→T=DTa1a2θiscon-stant.
Theseclasses–calleddiscreterigidtransformations(DRTs)–indeedform3D102Y.
Kenmochietal.
a1a2(a)a2a1(b)Fig.
1.
(a)Tippingsurfacesinthespace(a1,a2,θ),and(b)theirtippingcurves[16]a2a1(a)a1a2(b)Fig.
2.
(a)Subdivisionofthe(a1,a2,θ)parameterspaceinto3Dcellsbytippingsurfaces,and(b)theassociatedDRTgraph[17]cells,boundedbytippingsurfacesthatcorrespondtodiscontinuities.
Bymappingeachcellontoavertex,andeachtippingsurfacepieceontoanedge,inaVoronoi/Delaunayparadigm,wecanmodelthissubdividedparameterspaceasagraph,calledtheDRTgraph,asillustratedinFig.
2.
Denition1([12]).
ADRTgraphG=(V,E)isdenedsuchthat(i)eachvertexv∈VmodelsaDRT;and(ii)eachlabellededgee=(v,w,f)∈E,wherefiseitherΦpqporΨpqq,connectstwoverticesv,w∈Vsharingthetippingsurfacefasboundary.
ForagivenimageI,eachvertexisassociatedwithauniquetransformedimage,inducedbytheDRTcorrespondingtothevertex.
Theexistenceofanedgebetweentwoverticesindicatesa"neighbouring"relationbetweenthetwoassociatedDRTs.
MorepreciselythetwotransformedimagesdierbyatmostoneovertheN2pixelsofI;theedgelabelfprovidesthisinformation.
ThisallowsustousetheDRTgraphtoproduceallthetransformedimagesviasuccessiveelementary(i.
e.
,single-pixel)modications.
2.
3DiscreteRigidTransformationGraphandImageRegistrationTheregistrationproblemformalisedinEq.
(1)consistsofndingthetransformationthatbestmapsasourceimageontoatargetimage,withrespecttoagivendistance.
EcientNeighbourhoodComputingforDRTGraphSearch103Inthediscreteframework,thenumberoftransformationsisactuallynite.
Inpar-ticular,inthecaseofrigidregistration,thesolution(s)toEq.
(1)canbefoundwithintheDRTsexhaustivelymodeledbytheDRTgraph.
Inotherwords,byconsideringabrute-forcesearch,asolution,i.
e.
,aglobaloptimum,canbedetermined.
However,theDRTgraphGofanimageofsizeN*N,hasahighspacecomplexityO(N9)[12]thatinducesthesametimecomplexitybothforitsconstructionandexhaustivesearch.
Thislimitsexplorationofthewholestructuretorelativelysmallimages.
Neverthe-less,asalreadydiscussedin[18],itispossibletoperformalocalsearchonGinordertodeterminealocaloptimum.
2.
4LocalSearchonaDiscreteRigidTransformationGraphTondsuchanoptimum,alocalsearchbeginsatagiventransformation,i.
e.
,achosenvertexvofG.
Then,itmovestowardsabettersolutioninitsneighbourhood–followingagradientdescent–aslongasanimprovedsolutioncanbefound.
Beyondthechoiceoftheinitialvertex–oftenguidedbytheapplicationcontext–themostcriticalissueisthechoiceofa"good"searchareaaroundthisvertex,i.
e.
,adepthofitsneighbourhood.
Inparticular,thetrade-oistimeeciencyversusexhaustiveness.
Theneighbourhoodofdepth1,notedN1(v),actuallycorrespondstothesetN(v)ofverticesadjacenttovinG.
Moregenerally,neighbourhoodsofdepthk≥1,alsocalledk-neighbourhoods,arethenrecursivelyobtainedasNk(v)=Nk1(v)∪u∈Nk1(v)N(u)(6)whereN0(v)={v}.
Ourinitialalgorithm[18]wasdirectlymappedonthisrecursivedenition.
Asacon-sequence,thisapproachledtoahightimecomplexityO(mkN2),thatisexponentialwithrespecttothedepthkoftheneighbourhoodwithvertexdegreem,whichissupposedtobeconstantinaverage(Sec.
4.
2).
Inthenextsection,weproposeamoreecientalgorithm,thatremovesthisexponentialcost.
3k-NeighbourhoodConstructionAlgorithmWenowproposeanalgorithmthatecientlycomputesthepartofaDRTgraphthatmodelstheneighbourhoodofdepthkaroundagivenvertex.
Tothisend,weneedtohandletheanalyticalrepresentationofthecellsassociatedtotheDRTgraphvertices,insidethesubdividedparameterspaceof(a1,a2,θ)(Sec.
3.
1).
Then,wedevelopacon-structionstrategythatreliesonasweepingplanetechniqueintroducedin[12](Sec.
3.
2).
ThenalalgorithmisdescribedandformalizedinSec.
3.
3.
3.
1TippingSurfacesAssociatedtoaDiscreteRigidTransformationAvertexvofaDRTgraphGcorrespondstoonediscreterigidtransformation,thatinducesauniquetransformedimageIvobtainedbyapplyingthistransformationonan104Y.
Kenmochietal.
initialimageI.
Inotherwords,foreachpixel(pi,qi)ofIv,weknowwhichpixel(pi,qi)ofItransfersitsvalueto(pi,qi).
ThiscorrespondenceismodeledbythefollowinginequalitiesderivingfromEq.
(3)pi12graphlocally,orforobtainingtopologicalinformationfromaDRTgraphsuchasaneighbourhood.
Onemaynoticethatitissucienttoconsideronlytippingsurfacesof(S+(Iv)∪S(Iv))inordertoobtainthek-neighbourhoodofv,ifkgraphConstructionInournewalgorithm,thepurposeistobuildak-neighbourhood"similarly"tothecon-structionofa1-neighbourhoodinourpreviousversion[18],thatisbyusingasweepingplanetechniquefromonevalueθvwithinRv,toboththeleft-handandright-handsidesalongtheθ-axisinthespace(a1,a2,θ).
Thedierencesbetweenthisnewalgorithmandtheformeraretwofold.
Ontheonehand,therangeoftheconsideredθvaluesiswider.
Indeed,thesweepmustbecarriedoutinsideRvbutalsooutside.
Ontheotherhand,alargernumberoftippingsurfacesareconsideredaroundRv,whileonlyimmediateneighbourswerepreviouslyinvolved.
Toeasetheunderstandingofthisalgorithm,werstrecallthegeneralideaofthesweepingplanetechnique.
GivenasetSofs1verticalands2horizontaltippingsurfaces,weaimtoconstructtheDRTsub-graphGcorrespondingtoagivenrange[θstart,θend].
Bycomparisonto[12],theplaneisthensweptfromθstarttoθend,insteadof0to2π.
Fromtheverydef-initionoftippingsurfaces,thisplaneissubdividedinto(s1+1)*(s2+1)2Drectan-gularcells,generatedbyitsintersectionwiththetippingsurfacesofS.
Moreprecisely,wehave(s+1)divisionsineacha-direction,exceptattheintersectionoftippingEcientNeighbourhoodComputingforDRTGraphSearch105(a)(b)Fig.
3.
DRTgraphconstructionbythesweepingplanealgorithm,with2vertical(blue,cyan)and2horizontal(red,magenta)tippingsurfaces.
(a)3*3rectangularcellsgeneratedbythetippingsurfacesineachsweepingplane.
(b)TheassociatedDRTgraphineachplane(ingreen:newverticesandedgesinthesecondandthirdplanes).
surfaces,wherearectangledisappearswhileanewappears.
Byobservingtheserect-angleupdatesduringtheplanesweepingfromθstarttoθend,wecanconstructtheDRTsub-graph,whereeachrectanglecorrespondstoavertexwhileeachtippingsurfacebe-tweentworectanglescorrespondstoanedge.
Inotherwords,ateachintersectionoftippingsurfaces,snewverticesandtheirassociated(3s+2)edgesaregenerated,asillustratedinFig.
3.
(Thereaderisreferredto[12]formoredetails.
)Ourmodiedalgorithmconsistsofusingatopologicalsweep[22]inordertondthenextclosestintersectionoftippingsurfacesforupdatingtheplanardivision.
Weconsideratmost|S|2intersectionsateachupdate,byconsideringonlytheintersec-tionsofconsecutivetippingsurfacesintheirorderedstructureinthesweepingplanealongeacha-axis,andndtheclosestoneamongthem.
Aftereachupdate,themod-icationsofsuchintersectionscanbeperformedinconstanttime.
Wecanalsoignoretheintersectionsthatarenotintherangebetweenθstartandθend.
Inparticular,sincewehave|θendθstart|2π,thenumberofintersectionscanbeconsideredasmallconstant.
Hereafter,wedenotethisspecicprocedurebySweep(S,θstart,θend),andwewriteG=Sweep(S,θstart,θend)fortheoutputDRTsub-graph.
3.
3k-NeighbourhoodConstructionFindingtheneighbouringverticesandedgesofagivenvertexvwithdepthk,isactu-allyequivalenttoconstructingtheDRTsub-graphcontainingthoseverticesandedgesaroundv.
Here,weassumetoknowavalueθvlyingintoRv,andweuseitasinitialvalueofthesweepingalgorithm.
Theplaneisthusswepttwice,inthespace(a1,a2,θ),alongthetwodirectionsoftheθ-axis.
Thekey-pointishowtolimittheconstructionoftheDRTsub-graph.
Forthispurposeweverify,foreachgeneratedvertexu,itsneighbourhooddepthtv(u)withrespecttov.
Iftv(u)>kforallverticesinthecurrentsweepingplane,theprocessends.
106Y.
Kenmochietal.
Algorithm1.
k-neighbourhoodcomputation(intheleft-handsidealongtheθ-axis)Input:ADRTv(oritsassociatedimageIv);apositiveintegerk.
Output:TheDRTsub-graphF=(V,E)containingthek-neighboursofv.
1for=1,2do2Determinethetippingsurfacesassociatedtov:S+(Iv),S(Iv)(Sec.
3.
1).
3InS+(Iv)(resp.
S(Iv)),ndthe(k+1)-thlowest(resp.
uppermost)tippingsurfacef+(resp.
f),thatintersectstheinitialplaneatθv.
4Findandsortthek+1tippingsurfacesthatarelower(resp.
upper)orequaltof+(resp.
f),andputtheminanorderedsetS.
5InitializeV=,E=6Initializeθprev=θv7repeat8for=1,2do9Findthenextleftintersectionθ+off+(resp.
θoff)withtheothersurfaceinSforθk;Whenavertexuiscreated,itsdepthtv(u)dependsonthatofthetwoverticesw1andw2towhichitisadjacentinthea-directionofthetippingsurfaceintersection.
Wethenhavetv(u)=1+min{tv(w1),tv(w2)}.
(Aniterativebacktrackingprocessisalsoneededtoupdatethedepthofwanditssuccessiveneighbours,whenevertv(w)>tv(u)+1.
)Ineacha-direction,byconsideringthe(k+1)closesttippingsurfacesaroundRv,wecanobtainalltheverticesusuchthattv(u)≤k.
Intheθ-direction,weneedtocheckiftv(u)>kforallverticesuinthecurrentsweepingplane;ifso,thesweepingends.
TheglobalprocessisdescribedinAlg.
1.
(Notethatthealgorithmdescribesonlythek-neighbourhoodconstructionintheleft-handsidealongtheθ-axis,buttheright-handsidecanbeconstructedsimilarly.
)Therstloop(Lines1–4)initializesthesetoftippingsurfacesthatareneededtogeneratethek-neighboursofagivenDRTv.
Weobtain2(k+1)vertical(resp.
horizontal)tippingsurfacesclosetoRvatθ=θv,andsortandstoretheminthelistsS.
Inthesecondloop(Line7),werstverifyhowlongwecankeepthesametippingsurfacesetsS(Lines9–10),andthenbuildaDRTsub-graphbyusingtheSweepalgorithmforthisveriedθinterval(Line11).
Afterverifyingiftherestillexistsageneratedvertexwhoseneighbourhooddepthis≤k(Line12),weupdatethetippingsurfacesetsSforthenextinterval(Lines14–17).
Obviously,Fisnotthesmallestsub-graphGincludingthek-neighboursofv.
ToobtainGfromF,wesimplykeepverticeswhoseneighbourhooddepthis≤k.
EcientNeighbourhoodComputingforDRTGraphSearch1072.
02.
53.
03.
54.
0ImagesizeAveragedegreevaluesofvertices134567892(a)0.
00.
10.
20.
30.
40.
50.
6DegreesoftheverticesNumberofverticesImagesize9x9Imagesize8x8Imagesize7x7Imagesize6x6Imagesize5x5Imagesize4x4Imagesize3x3Imagesize2x20123456789(b)Fig.
4.
(a)Averagevertexdegreeina2DDRTgraph.
(b)Normalisedvertexdegreedistributionina2DDRTgraph.
4ComplexityAnalysis4.
1TimeComplexityofk-NeighbourhoodConstructionAlgorithmInordertoobtaintheinitial2(k+1)vertical(resp.
horizontal)tippingsurfacesofS,thetimecomplexityisO(N2)forLine2;O(N2)forLine3ontheaveragecaseifweuseHoare'sFINDalgorithm[23];andO(N2)andO(klogk)forndingandsortingthetippingsurfacesinLine4,respectively.
Then,wecarryouttheplanesweepforeachupdatedS1∪S2.
Foreachiterationintheloop,themostcostlypartsareLines9and11,whichrequireO(N2)andO(k2),respectively.
ThenextquestionconcernsthenumberofupdatesforS1∪S2.
IfmisthedegreeofanyvertexuofaDRTgraph,thisupdatenumbercanbeestimatedasm(2k+1),sincetheunionofRuforalluinthek-neighbourhoodofagivenvertexvcontainsatmost2k+1adjacentRuintheθ-direction.
Therefore,thetimecomplexityisO(mkN2)forthisiterativeplanesweeploop.
ThetimecomplexityofAlg.
1isthusO(mkN2),whichissignicantlylowerthanthatofourpreviousalgorithm[18],namelyO(mkN2).
Weobserve,inthenextsection,thatmcanbeestimatedasalowconstantvalue,leadingtoanalcomplexityofO(kN2).
4.
2AverageDegreeofDRTGraphsTheDRTgraphspacecomplexityforanimageofsizeN*NisO(N9),bothforverticesandedges[12].
Inotherwords,thenumberofverticesandthatofedgesgrowatthesamerate.
Wecantheninferthatmisactuallybounded,independentlyofN.
Byanalogy,letusimaginethatwedividea2Dplanewithstraightlinesdenedrandomly.
Threelineswillalmostneverintersectatasamepoint,andforanumberoflinessucientlylarge,thecellsoftheinducedsubdivisionwillbemostlytriangles.
Followingthisanalogy,wemayinferthatthedegreeoftheverticesofthe2DDRTgraphsintheplanes(a1,θ)and(a2,θ)iscloseto3,inaverage.
However,thisanalogyhassomelimits.
Indeed,theconsideredtippingcurvesarenotstraightlines,whiletheirveryregularstructureimpliesthatmanycurvesoftenintersectatasamepoint.
108Y.
Kenmochietal.
0123456Fig.
5.
Degreedistributionina2DDRTgraph,viewedinthedualsubdivisionoftheparameterspace.
Eachcolourrepresentsagivendegree,thatcorrespondsheretothenumberofcurvesboundingeachcell(3:red,4:green,5:blue;6:yellow).
(a)(b)(c)(d)(e)(f)(g)(h)Fig.
6.
Inputimagesandresultsoftheiteratedlocalsearchforimageregistration.
(a)Refer-enceimage,(b)targetimage,and(c)theinitialtransformedimageof(b)with(a1,a2,θ)=(0.
365,0.
045,0.
1423).
(d–h)Localoptimaobtainedfrom(c)byusingk-neighboursfork=1,3,5,10,15respectively.
Notethatin(c–h),pixelsarecolourediftheyaredierentfromthosein(a);yellow(resp.
red)pixelsarewhite(resp.
black)in(c–h)andblack(resp.
white)in(a).
Nevertheless,wecanassimilatea2DDRTgraph(whichistheprojectionofa3DDRTgraphontothe(a,θ)plane)toaplanargraphwheneverNissucientlylarge.
Undersuchassumption,theEulerformulaisvalid,i.
e.
,wehaveve+f=2,wherev,eandfarethenumberof(0D)vertices,(1D)edgesandinduced(2D)cells,respectively.
FromtheverydenitionoftheDRTgraph,wehave4f≤2e.
Itthencomesthat2e/v≤48/v.
Asv8inDRTgraphs,wehave2e/vgraph.
Itfollowsthattheaveragedegreemofthe3DDRTgraph(obtainedbyCartesianproductoftwo2DDRTgraphs)islowerthan2*4=8.
Thisisconrmedbytheexperimentalanalysis,illustratedinFig.
4(a).
Inpractice,themaximaldegreeoftheverticeswithinaDRTgraphalsoremainsclosetothisaveragevalue.
Indeed,thehistogramsdepictedinFig.
4(b)showthattheEcientNeighbourhoodComputingforDRTGraphSearch109Fig.
7.
DistanceevolutionduringiterationsoflocalsearchfortheinputsinFig.
6(a)and(b),fromtheinitialtransformationinFig.
6(c),withrespecttodierentdepthsk2DDRTvertexdegreesconvergerapidlytoastabledistributionthatcontainsmainlydegreesofvalue3and4(withamaximalvalueexperimentallyidentiedat8).
Morequalitatively,Fig.
5illustratesthedistributionofthesedegreesofa2DDRTgraph.
5ExperimentsIteratedlocalsearchwasappliedtoimageregistration.
InthissectionwevalidateAlg.
1inpractice,andweobserveitslocalbehaviourwhenvaryingk.
Forsimplicity,weusethesameexperimentalsettingsasin[18],i.
e.
,twoinputbinaryimagesandasigneddistance[24]forEq.
(1).
Inordertondaninitialtransformation,weusetherstandsecondordercentralmomentsofabinaryshape[25].
Experimentsarecarriedoutwithdierentneighbourhoodsizes,k=1,3,5,10,15onbinaryimagesofsize53*53fromtheinitialtransformation,asillustratedinFig.
6.
WecanobserveinFig.
7thatthelocallyoptimaldistanceimproveswhenweusealargerneighborhood,whichiscoherentinagradientdescentparadigm.
6ConclusionWehavesignicantlyimprovedthetimecomplexityoftheprocessofcomputinganeighbourhoodofgivendepthwithinaDRTgraph,withoutrequiringthecomputationofthewholegraph.
Thistimecomplexitymaybereducedinsomecases,inparticulariftheimageisbinarybydealingonlywiththepixelsthatcomposethebinaryobjectborder.
Theproposedapplicationsonlyvalidateourapproachasaproofofconcept.
Nevertheless,anexact–i.
e.
,numericalerror-free–strategyisnovelintheeldofimageregistrationandmayopenthewaytonewimageprocessingparadigms.
InfutureworkwewillexplorethenotionofDRTgraphinZ3.
References1.
Nouvel,B.
,Remila,E.
:Characterizationofbijectivediscretizedrotations.
In:Klette,R.
,ˇZunic,J.
(eds.
)IWCIA2004.
LNCS,vol.
3322,pp.
248–259.
Springer,Heidelberg(2004)110Y.
Kenmochietal.
2.
Nouvel,B.
,Remila,E.
:Congurationsinducedbydiscreterotations:Periodicityandquasi-periodicityproperties.
DiscreteAppl.
Math.
147,325–343(2005)3.
Berthe,V.
,Nouvel,B.
:Discreterotationsandsymbolicdynamics.
Theor.
Comput.
Sci.
380,276–285(2007)4.
Nouvel,B.
:Self-similardiscreterotationcongurationsandinterlacedSturmianwords.
In:Coeurjolly,D.
,Sivignon,I.
,Tougne,L.
,Dupont,F.
(eds.
)DGCI2008.
LNCS,vol.
4992,pp.
250–261.
Springer,Heidelberg(2008)5.
Jacob,M.
A.
,Andres,E.
:Ondiscreterotations.
In:Proc.
DGCI,pp.
161–174(1995)6.
Amir,A.
,Kapah,O.
,Tsur,D.
:Fastertwo-dimensionalpatternmatchingwithrotations.
Theor.
Comput.
Sci.
368,196–204(2006)7.
Reveill`es,J.
P.
:Geometriediscr`ete,calculennombresentiersetalgorithmique.
Th`esed'Etat,UniversiteStrasbourg1(1991)8.
Andres,E.
:Thequasi-shearrotation.
In:Miguet,S.
,Ubeda,S.
,Montanvert,A.
(eds.
)DGCI1996.
LNCS,vol.
1176,pp.
307–314.
Springer,Heidelberg(1996)9.
Richman,M.
S.
:Understandingdiscreterotations.
In:Proc.
ICASSP,vol.
3,pp.
2057–2060.
IEEE(1997)10.
Andres,E.
,Fernandez-Maloigne,C.
:Discreterotationfordirectionalorthogonalwaveletpackets.
In:Proc.
ICIP,vol.
2,pp.
257–260.
IEEE(2001)11.
Ngo,P.
,Passat,N.
,Kenmochi,Y.
,Talbot,H.
:Topology-preservingrigidtransformationof2Ddigitalimages.
IEEET.
ImageProcess.
23,885–897(2014)12.
Ngo,P.
,Kenmochi,Y.
,Passat,N.
,Talbot,H.
:Combinatorialstructureofrigidtransforma-tionsin2Ddigitalimages.
Comput.
Vis.
ImageUnd.
117,393–408(2013)13.
Nouvel,B.
:Rotationsdiscr`etesetautomatescellulaires.
PhDthesis,EcoleNormaleSuperieuredeLyon(2006)14.
Nouvel,B.
,Remila,E.
:Incrementalandtransitivediscreterotations.
In:Reulke,R.
,Eckardt,U.
,Flach,B.
,Knauer,U.
,Polthier,K.
(eds.
)IWCIA2006.
LNCS,vol.
4040,pp.
199–213.
Springer,Heidelberg(2006)15.
Thibault,Y.
,Kenmochi,Y.
,Sugimoto,A.
:Computingupperandlowerboundsofrotationanglesfromdigitalimages.
PatternRecogn.
42,1708–1717(2009)16.
Ngo,P.
,Kenmochi,Y.
,Passat,N.
,Talbot,H.
:On2Dconstraineddiscreterigidtransforma-tions.
Ann.
Math.
Artif.
Intell.
(inpress),doi:10.
1007/s10472-014-9406-x17.
Ngo,P.
,Kenmochi,Y.
,Passat,N.
,Talbot,H.
:Topology-preservingconditionsfor2Ddigitalimagesunderrigidtransformations.
J.
Math.
ImagingVis.
49,418–433(2014)18.
Ngo,P.
,Sugimoto,A.
,Kenmochi,Y.
,Passat,N.
,Talbot,H.
:Discreterigidtransformationgraphsearchfor2Dimageregistration.
In:Huang,F.
,Sugimoto,A.
(eds.
)PSIVT2013.
LNCS,vol.
8334,pp.
228–239.
Springer,Heidelberg(2014)19.
Zitova,B.
,Flusser,J.
:Imageregistrationmethods:Asurvey.
ImageVisionComput.
21,977–1000(2003)20.
Schowengerdt,R.
A.
:RemoteSensing:ModelsandMethodsforImageProcessing,3rdedn.
ElsevierAcademicPress(2007)21.
Noblet,V.
,Heinrich,C.
,Heitz,F.
,Armspach,J.
P.
:Recalaged'imagesmedicales.
TechIng(MED910)(2014)22.
Edelsbrunner,H.
,Guibas,L.
J.
:Topologicallysweepinganarrangement.
JournalComput.
Syst.
Sci.
38,165–194(1989);Corrig.
42,249–251(1991)23.
Hoare,C.
A.
R.
:Algorithm65:nd.
Commun.
ACM4,321–322(1961)24.
Boykov,Y.
,Kolmogorov,V.
,Cremers,D.
,Delong,A.
:Anintegralsolutiontosurfaceevolu-tionPDEsviageo-cuts.
In:Leonardis,A.
,Bischof,H.
,Pinz,A.
(eds.
)ECCV2006.
LNCS,vol.
3953,pp.
409–422.
Springer,Heidelberg(2006)25.
Flusser,J.
,Zitova,B.
,Suk,T.
:MomentsandMomentInvariantsinPatternRecognition.
Wiley(2009)