Y.Y.Sahilliog?luandY.YemezKo?University,ComputerEngineeringDept.,Istanbul,TurkeysubmittedsubmittedtoCOMPUTERGRAPHICSForumsubmittedsubmittedtoCOMPUTERGRAPHICSForumVolumexx(200y),Numberz,pp.Partial3DCorrespondencefromShapeKo?University,ComputerEngineeringDept.,Istanbul,resenta3Dcorrespondencemethodtomatchthegeometricextremitiesoftwoshapeswhicharepartiallyisometric.Weconsiderthemostgeneralsettingoftheisometricpartialshapecorrespondenceproblem,inwhichshapestobematchedmayhavemultiplecommonpartsatarbitraryscalesaswellaspartsthatarenotsimilar.Ourran thespaceofallpossiblepartialmapsbetweencoarselysampledextremities.Thequalifiedtop-rankedmatchingsarethensubjectedtoamoredetailedysisatadenserresolutionandassignedwithconfidencevaluesthataccumulateintoavotematrix.Aminimumweightperfectmatchingalgorithmisfinallyiteratedtocombinetheaccumulatedvotesintoanoptimal(partial)mapbetweenshapeextremities,whichcanfurtherbeextendedtoadensermap.Wetesttheperformanceofourmethodonseveraldatasetsandbenarksincomparisonwithstateoftheart.CategoriesandSubjectDescriptors(accordingtoACMCCS):I.3.5[ComputerGraphics]:3DShapeCorrespondence—partialshapecorrespondence,isometricdistortion,extremitymatching,partialisometryFindingcorrespondencesbetweenshapesisafundamen-ousapplicationssuchasdeformationtransfer,statisticalshapeysis,shaperetrievalandregistration[BBK08][vKZHCO11].Theshapecorrespondenceproblemcanbedividedintotwocategoriesascompleteandpartialcorre-spondence,wherethelatterdealswithshapesthatarecom-monorsimilaronlypartially.Partialshapecorrespondencecsobethoughtofasamoregeneralandhencehardervariantoftheformer,sincethepartialmatchingset,whichisaprioriunknown,needstobedeterminedfromtheglobalsetofsurfacepointsormeshverticesthatdefineashapeasawhole.Inthispaper,weaddressthepartialcorrespondenceproblem,andconsideritinitsmostgeneralsettingwhereshapestobematchedmayhavemultiplecommonpartsatarbitraryscalesaswellaspartsthatarenotsimilaratall.spondencessincesimilarshapepartsusuallyhavesimilarmetricstructures.Althoughpartialmatchingcanbeachievedbyenforcinggeodesicmetricconsistenciesorbysearchingforpartialmapswithminimumisometricdistortion,thearbitraryscaleofsimilarparts,whiaychangefromone

shapetotheother,usuallyposesanimportantchallengethatfirstneedstoberesolved.roposea bine(RAVAC)algo-rithmtofindcorrespondencesbetweenpartiallyisometricshapes.rimarily thepartialcorrespondenceprob-lem,thoughtheproposedschemecanbeusedtogeneratecompletecorrespondencesaswell.Ouralgorithmcollectspartialisometrycuesfromthegivenshapesbyconsideringallpossiblepartialmaps(relations)betweenshapeex-tremitiesandaccumulatesthecollectedinformationintoavotematrixwhichisthenusedtofindanoveralloptimalpartialcorrespondenceviaperfectgraphmatching.ThemainideainRAVACistomeasureacorrespondencepair’sdevia-tionfromisometrybasedononlypartoftheshape.Asmalldeviationfromisometrygivesahighconfidenceforthatcor-respondence,andalargedeviationgivesalowconfidence.Sincethepartsegmentationisnotavailableinadvance,thealgorithmcomputesa agedeviation(distortion)valueovermanycandidatesegmentations.Eachcandidateseg-mentationisgeneratedusingatripletofextremitiesfromthesourceand shapes.The"good"tripletsneededtogen-eratepartsegmentationsareobtainedbyrankingallpossi-blepairsofcorrespondencesbetweenextremitiesinadvanceandpickingthetripletsonlyfromthepairswithlowdistor-tionestimates.Toestimatedistortionsforranking,weem-ployaheuristicbasedonpairsofk-tuplesofextremitiesfromthesourceand withsimilarintrinsics.Thepaperisorganizedasfollows.InSection2,wediscusstherelatedworkandelaborateonourcontributions.ThroughSections3-7,wedescribethemaincomponentsofourcor-respondencescheme,whicharesampling,ranking,voting,combininganddensematching,respectively.Thecomputa-tionalcomplexityoftheoverallshapecorrespondencealgo-rithmisrelativelylow,asyzedinSection8.Wetesttheperformanceofourmethodonseveraldatasetsandbench-sentedinSection9,wherewealsodiscussthelimitationsofourapproach.rovideconcludingremarksandpossibledirectionsforfutureresearchinSection10.Wenotethatthesourcecodeandtheexecutablesforthemethodthatresentinthispaperarepubliclyavailable RelatedTherearedifferentwaysofdealingwiththescaleprob-lemintheliterature,whether ingpartialorcom-pleteshapecorrespondence.Somemethodssimplysumethatshapescomeincompatiblescales[GMGP05],[BBK06],[HAWG08],[TBW?09],[vKZH13]whichisratherastrongassumption,whereasothersnormalizetheoriginalgeometrywithrespecttosomeglobalintrinsicprop-ertysuchas umgeodesicdistance[SY11],[SY12a], umcentricity[ACOT?10]ortotalsur-facearea[OMMG10],[PBB11].Relyingonglobalprop-ertiesfornormalizationmayleadtosatisfactoryresultsinthecaseofperfectisometrybutmayperformpoorlywhentheshapestobematchedarenearlyisometric.Forpartialmatchingontheotherhand,thesuccessdependshighlyonthedegreeofscaledifferencebetweensimilarpartsoftheAsasolution,someshapematchingtechniquesrelyon[BK10],[ZWW?10].Localshapeinformationisforshapecorrespondenceinthecaseofnon-isometricde-formations,butotherwiseitisconsideredaslessreliablethanglobalshapeinformationsuchasisometry.Themeth-odswhichrelyonlyonlocalgeometricinformationmaynotperformwellwhentheshapestobematchedexhibitlargevariationsintheirlocalgeometry,ormayeasilyconfusesur-facepartswhentherearemanypointsthatarelocallysim-ilar.Hencesomefeature-basedcorrespondenceincludealsoapruningprocedurethattakesintoaccountiso-metriccluesbyenforcinggeodesicconsistency[TBW?09],[ZSCO?08],[HAWG08],[ACOT?10].Anotherissuewiththeuseoflocalshapedescriptors,especiallyinthecaseofpartialmatching,isthatdifferent( surfacepartsmayinterferetocomputationofthedescriptoratagivenpoint.Averyrecentwork[vKZH13]addressesthisproblembyintroducingalocalshapedescriptor,namely

thebilateralmap,whoseregionofinterestisdefinedbytwofeaturepoints.ternativetogeodesicmetricforthemeasurementofisometricdistortionsisthediffusionmetricwhichislessac-curatebutgenerallyconsideredasmorerobusttotopologicalnoise[OMMG10].Localscaledifferencesarehoweverdiffi-culttohandleusingdiffusion-basedmetrics.Thecommute-timemetricforexampleaddressesthescaleproblemonlyglobally[WBBP11],hencecannotbeusedforthematchingproblem.Likewise,theheatkernelsignature,asusedin[PBB11],[DLL?10]toaddressthepartmatchingproblem,requiressettingofatimescaleparameterthatselfdependsontheglobalshapescale.Aparticularsettingofthepartialcorrespondenceproblemispartmatchingwhereoneoftheshapestobematchedisanisometricpartoftheotheruptoascale[PBB11],[DLL?10],[SY12b],Inthissetting,thecorrespondence-lessapproachin[PBB11]optimizestheregion-wisesimilarityovertheintegrationdo-mainsrelyingondiffusion-basedlocalshapedescriptors,whereas[SY12b]introducesanovelscale-invariantisomet-Acommonapproachinthecaseofcompleteshapecor-respondenceistoembedinputshapesintospectralwherethescalingproblemisimplicitlyhandled[JZ06],[MHK?08],[SY12a],[CH03].Thesemethodshowevertreatthescaleproblemglobally,hencecannotbeappliedtopar-tialcorrespondence.Abetteralternativeforpartialmatch-ingisbasedontheM?biustransformationwhichisusedforconformalembeddingofthegivenshapesintoacanoni-calcoordinateframeonthecomplexplanewheredeviationsfromisometryareapproximatedbasedonmutuallyclosestpoints[LF09].Thisshapecorrespondencemethodisbasi-callyavotingtechnique(M?biusVoting),whichaimstofindareliablebutsparsematchingbetweentwopartiallyiso-metricshapes.Thealgorithmiterativelysamplesarandomtripletfromeachoftheshapesurfaces.ThetripletpairthendefinestwoM?biustransformationsthatembedthegivenshapes(aftermid-edgeflattening)intoacanonicalcoordi-nateframeonthecomplexplane.Mutuallyclosestpointsonthisplaneareconsideredascandidatesforcorrespondenceandvotedbasedonthedistancesinbetween.Thefinalout-putofthealgorithmisasetofcorrespondenceseachasso-ciatedwithaconfidencevalue.TheM?biusVoting(MV)methodiscapableofproducingasmallnumberofreliablecorrespondences,butusuallyfailstoachieveareliabledensematching.Althoughgoodtripletsofsurfacepointscanbring modatingpartsofthegivenshapestothesameposeandscalesuccessfully,thesametransformationap-pliedtootherpartsthatdonotnecessarilyexpectthesametransformationmayeasilydistracttheglobalvotingprocess.Theexperimentsconductedin[LF09]actuallyshowthatthe esunstablewhentheinputshapesexhibitlessthanapproximay40%similarity.Y.Sahilliog?luY.Sahilliog?luandY.YemezKo?University,ComputerEngineeringDept.,Istanbul,TurkeyPAGE14Y.PAGE14Y.Sahilliog?luandY.YemezKo?University,ComputerEngineeringDept.,Istanbul,TurkeysubmittedsubmittedtoCOMPUTERGRAPHICSForumsubmittedsubmittedtoCOMPUTERGRAPHICSForumformforshapematchinghavethenbeenproposed,thoughnotinthecontextofpartialcorrespondence[ZWW?10],[KLCF10],[KLF11],[LAAD11].Inparticular,theIntrinsicMaps(BIM)methodof[KLF11]canbeconsideredasanextensionofMV,specificallydesignedtoaddressthecompletedensecorrespondenceproblem.Insteadofavot-ingapproach,theBIMmethodusesblending:Itgeneratesbasedontripletsofextremalpoints,weightsthesemapsateverysurfacepointbydistortionandthenblendsthemintoafinalmapbycomputinganapproximategeodesiccen-troidforeverymappedpoint.BIMworksverywellinthecaseofcompleteshapematching,butdoesnotsupportpar-completecandidatemaps.Suchcompletemapsdonotac-tuallyexistwhentheshapestobematchedhavedissimilarpartsthatconstrainthedistortionestimate.Theoreticallyonesinceitblendsteratedcompletemapsbyweighting.ThiswouldhoweveryieldrobustnessproblemssimilarlyasMV(infactmoreseverelythanMV),aswewilldemon-stratebyexperimentsinthispaper.Incontrasttothesetwomethods,ourmethodexplicitlyexploresthespaceofpartialmapsdefinedovershapeextremities.Thesepartialmapsarepopulatedviaregionofinterestsamplingandusedtoaccu-mulatepartialisometricclues(distortions)intoavotema-trix.Henceweusevotingtomatchshapeextremitiesandblendingtoextendtheobtainedsparsecorrespondencetoadenseone.Wenotethat,forthecaseofcompletedensecorrespondence,theBIMmethodhasbeenoutperformedbyseveralrecentworksbasedonfunctionalrepresentationofcorrespondences[OBCS?12],[PBB?13],[ROA?13],whichhoweverlackpartialshapematchingsupport.Anotherstateoftheartcorrespondencemethodisthedeformation-driventechniqueof[ZSCO?08],whichhandlenon-isometricshapevariations(uptoacertainde-gree)aswellaspartialisometries.Inthismethod,anop-timalcorrespondenceissoughtbetweenshapeextremitiesviapriority-basedcombinatorialtreetraversalbypruningthesearchspaceaccordingtosomecriteriabasedonlocalshapesimilarityandgeodesicconsistency.Foreachcandi-datecorrespondenceset,thesourceshapeisdeformedtothebasedonthesesmallnumberoflandmarks(anchorpoints),andthecorrespondencewiththesmallestdistortiongivesthebestmatching.Themajordrawbackofthisschemeistheextensivecomputationalloadduetotheprocessofre-peateddeformations.Another ingistheneedforerrorthresholdparametersemployedintreepruning,whichtosettheseparameterscorrectlyandthecombinatorialtreetraversalmayeasilymisssomeofthecorrectfeaturepair-prunethecombinatorialsearchtreeisnormalizedbasedonsomeglobalinstrinsics,whichisproblematicformatcarbitrarilyscaledshapepartsasdiscussed

ContributionsandInourpreviouswork[SY12b],wehaveaddressedthepartinthemostgeneralsetting)anddescribedamethodthatalsoreliesonshapeextremities.Howevertheframeworkde-scribedinthatworkiscompleydifferentthanourcurrentsolutionandactuallyverysimplistic,aimingtointroduceaisonpromotingthisnoveldistortionmeasure,notapar-tialmatchingalgorithm.ThemethodsimplyassumesthatthetopMshapeextremitiesofoneshapeareallincludedintheothershapeaswellandrunsacombinatorialsearchoverallpossiblepermutationstomatchtheseextremitieswithMtortionmeasure.Themethodthatresentinthiscurrentpaperdoesnotusethisdistortionmetricanddoesnoteitheremploysuchasimplisticcombinatorialsearch,ratheritac-cumulatespartialisometriccluesbytraversingallpossiblepartialmaps,employingmoresophisticatedalgorithmsforranking,votingandcombining.Therearefewmethodsintheliterature,thatarecapableofaddressingthepartialcorrespondenceprobleminthemostgeneralsettingwhereshapesmayhavemultiplepartsatarbitraryscalesaswellaspartsthatarenotsim-ilar[LF09],[FS06],[TBW?09],[ACOT?10],[ZSCO?08].Allthesemethodsmainlyrelyonscale-invariantlocalshapedescriptorsexceptfortheMVmethod[LF09].Notealsothatthemethodsin[TBW?09],[ACOT?10],[ZSCO?08]enforceandhenceresorttoglobalintrinsicpropertiesforshapenor-malization.WhencomparedtoMV,ourmethodhasseveraladvantages.First,wehandlethescaleprobleminherenttopartialcorrespondencedirectlyinthe3DEuclideanspacewhereinisometryisoriginallydefined,henceasfreeofem-beddingerrors.Second,ourmethodcanproducereliabledensecorrespondencesbetweenpartiallyisometricshapes.Third,weimposenorestrictiononshapetopology.Last,ourmethodgeneratesmorereliableandaccuratecorrespon-dences,especiallyatshapeextremities,andcanhandleshapepairswithlesssimilarityoverlap.Inviewoftheabovediscussion,themaincontributionofthisworkisacomputationallyefficientandrobustmethodthatcanaccumulatepartialisometriccluesintoavotematrixandtherebycomputespartialshapecorrespondenceswhichcanbedenseorsparse.Wenotethatthefocusofthisworkisonpartialcorrespondence,thoughtheproposedalgorithmcsogeneratecompletecorrespondences.ickshapeextremitiesofthegivenshapesbyusinglocalextremaoftheintegralgeodesicdistancefunction[HSKK01].Letμ(v)denotetheintegralgeodesicdistanceatvertexv.Priortocomputationofμ,weapplyLaplaciansmoothingtoeachshapemodeltopreventsamplesatnoisybumps.Wetheninitializethesamplesetswithlocalmax-imaandminimaofμ.Thelocal aareexpectedtobeonthetipsofagivenshapewhereaslocalminimacor-respondtosurfacepointswhichlienearthecenterofshape[ZSCO?08].Theinitialsamplesetsarethenexposedtotwostepsofpruning,firstofwhichclustersclosenessthresholdisdeterminedbasedonthe geodesicdistancegmaxonthesurface.Inourexperiments,wehaveusedthevalueobtainedbydividinggmaxwithafactorh∈[10,20]dependingonthedataset.Thehbasicallydeterminesthescaleofsampling,whichwemanuallybyexperimenting.Thesecondstepofpruningre-movesalocal um(minimum)vfromthesamplesetifμ(v)isless(greater)thantheaverageμtocanceloutre-dundantextremitiesthatarenotontips(centralregion).The

evaluatedviaEq.2intheabsenceofgloballynormalizedgeodesicsbyusingatraversallistconsistingofmatchesfromtheshapepartwherethepairsiandtjitselfresidesin.Thegeodesicdistancesforthisquerycanbenormalizedbyus-ingthe umgeodesicdistancewithinthisshapepart.Howeversincethecorrespondingshapepartsarenotknowninadvance,weestimatetheindividualisometricdistortionbytraversinerallpossibleone-to-onemapsofcar-dinalities2to5.Notethatthesemapsdonotincludethequery(si,tj)andthecardinalityofamapisdefinedasthenumberofpairsinit.Wedonotcheckbeyond5duetoefficiencyreasonsaswellasthefactthat5extremities(plussiortj)areusuallysufficienttorepresentanygivenshapepart,e.g.,large-scalelimbsinhumansandanimals.Thees-timate,d?iso(si,tj),oftheindividualisometricdistortionofthecorrespondence(si,tj)isthencomputedverticesresultingfromthissparsesamplingprocess ltutethesetsS(source)andT )tobematched(Fig.l

diso(si,tj)=

l

Intherankingphase,werankallpossiblepairsof

dencesbetweenextremitiesbasedontheirdeviations

notinclulding(si,tj),andLk

|T|?1(k!).Weisometry.Weestimatethedeviationforeachpair,hence notethissetbyisometricdistortion,usingaheuristicbasedonpairsof

.Whilecomputingthedistortiontupleswithsimilaraveragenormalizedgeodesicdistancesonthesourceand .Wedescribetherankingprocessindetailinthesequel(seealsothepseudocodeoftheoverallcorrespondencealgorithmgivenatofthissection).DistortionGivenamap§:S→T,i.e.,asetofcorrespondencepairs,wemeasuretheisometricdistortionDisoasfollows:

Eq.3,thegeodesicdistancefunctiongisnormalizedforeachshapewiththeumgeodesicdistancebetweentheksamplesofthegivenmap.Takingtheminimum(3)guaranteesthatif(si,tj)isagoodmatchandtraversesalistofmatchesfromthesameshapepartitresidesin,thisisappreciatedbyselectingthelowestdistortion.Wethenaverageoversetsofmapswithdifferentcardinalitiessincemapsofsmallsize,e.g.,withk=2or3,arelikelytofallinDiso(§)=

∑diso(si,tj, (si,tj

thesamepartas(si,tj)butmayexhibitsymmetricfliplems,whereasmapswithlargecardinalities,e.g.,k=or5,areunlikelytobeconfusedbyflipsbuthavetheriskwhere

(s,t,§′)isthecontributionoftheindividual

includingirrelevantsamplesfromadistinctisoirespondence(si,tj)totheoverallisometric

Safemapdiso(si,tj,§′)= |g(si,sl)?g(tj, InEq.3,each(si,tj)traversesallpossibleone-to-onel|§′|(s,tlwhereg(.,.)isthegeodesicdistanceb′etweentwoverticesonagivensurface.Thetraversallist§,whichisbydefault§?{(si,tj)},includesthecorrespondencepairstobetra-versedinordertocomputethedistortionofagivenindivid-ualcorrespondencepair(si,tj).Notethatvariantsoftheiso-metricdistortionfunctiondefinedby(1)csobefoundin[BBK06]aswellasinmostofourpreviouswork[SY11],[SY12a],[SY13].Animportantissueincomputationoftheisometricdis-tortionishowtonormalizethescaleofthegeodesicdis-tancefunctionginvolvedinEq.2since,inthecaseofpar-tialmatching,therearenoagreed umgeodesicdis-tancesonthesourceand duetopossiblelocalscaledifferences.Thekeyobservationhereisthattheindividualisometricdistortionofaqueriedmatch(si,tj)cansafelybe

stocomputetheminimumdistortionoverS(k).Toducecomputation, runeS(k)soastokeeponlythepo-tentiallysafemaps, hemapsbetweenksourceandk sampleswhichareexpectedtobefromsimilarshapeparts(seeFig.1).mTothisend,foreachk,wedefineasetofsafemapgenera-tors,G(k),whichcontainsallpairsofk-tuples,onetuplefromthesourcesamplesetandtheotherfromthe,suchthatanymapbetweenthesetuplesispotentiallysafe.Wede-noteeachofthesepairsofsampletuplesbyG(k)∈G(k)form∈[1,|G(k)|].Apairofk-tuplesisidentifiedasasafemapgeneratorifitsatisfiesthegeodesicconsistencyconditionmthattheaverageofpairwisenormalizedgeodesicsbetweensourcesamplesisclosetothatofbetween Wenormalizethegeodesicswiththe umgeodesicdistancebetweenthesamplesofthegiventuple.NotethatInput:ExtremitysamplesetsSInput:ExtremitysamplesetsSandOutput:One-to-one §?:S→————–Ranking————G(k)fork=3,4,5:safemapgenerators,i.e.,allpairsofk-tuplesofextremitiesfromthesourceand withsimilarintrinsics;Foreachsi∈SEstimated?iso(si,tj)?tj∈Tbasedon{G(k)}viaQualifythematch(si,tk)forvotingifdiso(si,tk)beforethefirstsignificantjumpinthesorteddistortionplotof————–Voting————Γ:Votematrixwithallentriesγijinitializedto0;Form=1to|G(3)|IfG(3)=((s,s,s),(t,t,t))∈G(3)m§(3)={(si,tj),(si,tj),(si,tj)}whereallpairsarei1i2 j1j2l1 2 3Bringmeshestothesamescaleby κ=(g(si1,si2)+g(si1,si3)+g(si2,si3)g(tj1,tj2 g(tj1,tj3 g(tj2,tj3SetSl={si1,si2,si3}andTl={tj1,tj2,tj3Computeregionsofinterest,SlandTl,onsourceand Spread～100densesamples,S?landT?l,onregionsofinterest;Findthedensemap§?l:S?l→T?l;Voteupconfidenceofextremitymatch(si,tj)∈§(3)γij=γij+exp(?diso(si,tj,§?l————–Combining———SetthecostmatrixC?=lc=1?γijforhigh-confidencematches?i,t§?=minimum-weightperfectmatchingonLet(sa,tb)betheleast-confidentmatchinUntilthereisnojumpinconfidencesofthematchesinc?=mmalthoughallk!mapsgeneratedfromagivenG(k)arere-ferredtoaspotentiallysafe,onlyasmallportionofthemareactuallycorrectmapsbetweentwosimilarparts.Hencewhileevaluatingaquerymatch(si,tj)viaEq.3,takingthemminimumhelpseliminatingthecontributionofthepartialWecreateteratorsetsG(k)incrementallyfork=getsamplestomeetthegeodesicconsistency(|S|)(|T

pairwisetripletcombinations,20%?30%makeinto inourexperiments,whereclosenessthresholdismanuallysetas0.15byexperiment-ing.Fork=4,5,weincrementallybuildG(k)fromIneachcase,apairofsource samplestoanexistinggeneratorGmtriggersanewgeodesicsistencytestandtypically2%?4%ofallpossiblepairwisecombinationsareselected.SomesafemapgeneratorsfromG(3)aredemonstratedinFig.2.Figure2:Threedifferenttripletpairs(safemapgenerators)fromG(3)areindicatedwithlargegreenspheresonthreetheremainingByreplacingS(k)inEq.3withthepotentiallysafeone-to-onemapsbasedonG(k),wenotonlyreducethesearchspacesignificantlybutalsoincreasetheaccuracybyexclud-ingunexpecteddistortionvalues.Theseunexpectedhighdis-tortionsareduetoevaluationof(si,tj)via(unsafe)maps modatessamplesfromirrelevantshapeparts.OncetheindividualdistortionsarecomputedviaEq.3,foreachsourcesamplesi,werankthepairs(si,tj)basedon

Figure3:TheoverallRAVACtheirindividualdistortions:Wesortallpossible|T|differentmatcheswithrespecttod?iso(si,tj)inascendingorderandqualifyonlytheoneswithadistortionvaluethatappearsbe-forethefirstsignificantjumpinthecorrespondingdistortionplot.Weassumethatasignificantjumpoccurswheredifferencebetweentwoconsecutivevalues eslargerthanthesumofthefirsttwodistortiondifferences,i.e.,thesumofthedifferencebetweenthefirstandthesecondval-ues,andthedifferencebetweenthesecondandthethirdval-uesinthesortedlist.Asimilarjumpthresholdingasin[ZSCO?08]fordeterminingtheoptimalfeatureandin[SY13]fortrackingsymmetricflips.Withthequal-ifiedmatches,thevotingmoduleisthenreadytostart,asdescribednext(seealsothepseudocodeinFig.3).Withtherankingofpossiblematchesinhand,onepossibil-itytosolvethecorrespondenceproblemistoselecttheleastdistortedmatchforeachsourcesample.Thisstraightforwardsolutionwouldgivea(possiblymany-to-one)mapthatwouldhoweversufferfromsymmetricflipsandmismatchesduetolownumberofextremitiesbeingmatched.Wethere-foreconsulttoavotingprocedurewhichismorerobust,thatreliesontherankingobtainedintheprevioussection.TheFigure4:AnexampleofthevotingprocessforageneratingpairofsampletripletsfromG(3).a)Twostepsthatdecideregionsofinterest(paintedred),b)evenly-spaceddensesamples(yellowspheres),andc)one-to-onemapbetweenthem(lines)tobeusedforcomputationofconfidencevotes.basicideaisasfollows.Weaccumulateconfidencevotesforallpossiblepairsofcorrespondencesbetweenextremi-tiesintoavotematrix.Theseconfidencevotesarecollectedbasedontheisometricdistortionsofthepairs.Thedistor-tionsarecomputedovermanypartsegmentationsgener-atedusingtripletsofextremitiesonthesourceand HencethevotingprocessconsidersonlyteratorsetG(3)(theothersarediscardedsimplyduetocomputationalreasons).Among3!potentiallysafemapsgeneratedmeachG(3)∈G(3),onlythosecontainingthematchesmlfiedintherankingphasearetakenintoaccount.Eachsuchsafemap§(3)definestworegionsofinterest,hencetwopartsegmentations,onthegiventwoshapes(aswillbeexplained(seeFig.4).Theresultingisometricdistortionisthenusedtovoteforthethreematchescontainedinthispotentiallysafemap.Thisisrepeatedforallqualifiedsafemapsandthere-sultingvotesareaccumulatedintoavotematrixwhereeachentryrepresentstheconfidenceofapotentialmatchbetweentwoshapeextremities.Inthesequel,wedescribethevotingalgorithmindetail.lFindingregionsof apotentially map

verticesthatareatmostg(s,s′)/2apartfroms′wheres∈Slofintereston shapedefinedbytheextremityTliscomputedDenseregionNext,wedistributeevenly-spaceddensesamplesinthere-gionsofinterest(seeFig.4b).Weresampleandpopulatetheregionofinterestonthesourceshapebyfirstselectingcorrespondingextremitiesasthefirstthreedensesamples.Giventheregionarea,weusethead-hocformulatoputetheradiusr=0.17A/πthatensuresevenlyofabout100densesamples[SY11].Thesamplingprocedureisasfollows.Whenanarbitraryregionvertexisselectedasadensesample,alltheregionverticeslyingwithinitspatchofradiusraremarked.Thenextdensesampleisthenselectedarbitrarilyfromtheunmarkedregionvertices.Whenthisisrepeateduntilnounmarkedregionvertexisleft,weobtainapartitioningoftheregionintodensesamplesthatareatleastrapartfromeachother[HSKK01].Asimilarevenly-spacedsamplingontheregionsofinterestofthescaledtar-getmeshusingthesamermakesthedensesamplesascon-sistentaspossibleonthetwosurfaces.Thisjointsamplingprocessyieldsconsistentsamples,especiallyifsourceandl G(3)=((s,s,s),(t,t,t

rsgisiiie§(3)= i1i2 j1j2

i,tj),(si,tj),(si,tj)}.Thevoting Tl, 1 2 3

Denseregionmeshwithafactorκ=

12

13

23 lllg(tj1,tj2 g(tj1,tj3 g(tj2,tj3lllbasedonthegeodesicdistanceratiosbetweenthesamplepoints,andthenfindstheregionsofinterestthattheseshapeextremitiesdetermine(seeFig.4a).Lettheex-tremitysamplesets{si1,si2,si3}and{tj1,tj2,tj3}bedenotedbySlandTl,respectively.TheregionofinterestonthesourceshapeincludesthesourcemeshverticesthatareclosetoSlanddistanttoS?Sl.Toimplementthis,wemarkavertexvasaregionvertexifg(s,v)<gl,max?s∈Sl,wheregl,maxistheumgeodesicbetweenextremitysamplesinSl(seeFig.4a-left).Tomeetthesecondrequirement,eaaximalextremitys′∈S?Sl,weunmarkthe

WematchSlandTlbyusingafastminimum-weightper-fectmatchingalgorithm[Kol09],anddenotetheresultingdensemapby§?l.Tofeedthealgorithm,webuildacostmatrixCwhereeachentrycpqistheisomet