Abstract A unified framework for alignment and cor

AunifiedframeworkforalignmentandcorrespondenceBinLuoa,b,*andE.R.HancockaaDepartmentofComputerScience,UniversityofYork,YorkYO15DD,UKbTheKeyLabofIC&SP,AnhuiUniversity,ChinaReceived27July2001;accepted27June2003AbstractThispapercaststheproblemof2Dpoint-setalignmentandcorrespondencematchingintoaunifiedframework.Ouraiminprovidingthisunificationistoconstraintherecoveryofposeparametersusingrelationalconstraintsprovidedbythestructuralarrangementofthepoints.Thisstructuralinformationisprovidedbyaneighbourhoodgraphforthepoints.Wecha-racterisetheproblemusingdistinctprobabilitydistributionsforalignmenterrorsandcorre-spondenceerrors.Theutilitymeasureunderpinningtheworkisthecross-entropybetweenprobabilitydistributionsforalignmentandassignmenterrors.Thisstatisticalframeworkinterleavestheprocessesoffindingpointcorrespondencesandestimatingthealignmentpara-meters.Inthecaseofcorrespondencematching,theprobabilitydistributionmodelsdeparturesfromedgeconsistencyinthematchingoftheneighbourhoodgraphs.Weinvestigatetwodif-ferentmodelsforthealignmenterrorprocess.Inthefirstofthese,westudyProcrustesalign-ment.Hereweshowhowtheparametersofthesimilaritytransformandthecorrespondencematchescanbelocatedusingdualsingularvaluedecompositions.Thesecondalignmentpro-cessusesapoint-distributionmodel.Weshowhowthisaugmentedpoint-distributionmodelcanbematchedtounlabelledpoint-setswhicharesubjecttobothadditionalclutterandpointdrop-out.Experimentalresultsusingbothsyntheticandrealimagesaregiven.
2003ElsevierInc.Allrightsreserved.1.IntroductionPointpatternmatchingisaproblemofpivotalimportanceincomputervisionthatcontinuestoattractconsiderableinterest.TheproblemmaybeabstractedasComputerVisionandImageUnderstanding92(2003)26–55*Correspondingauthor.Fax:[phone].E-mailaddresses:[e-mail](B.Luo),[e-mail](E.R.Hancock).1077-3142/$-seefrontmatter
2003ElsevierInc.Allrightsreserved.doi:10.1016/S1077-3142(03)00097-3eitheralignmentorcorrespondence.Alignmentinvolvesexplicitlytransformingthepointpositionsunderapredefinedgeometrysoastomaximiseameasureofcor-relation.ExampleshereincludeProcrustesnormalisation[13,1],affinetemplatematching[27],deformablepointmodels[5]andvariousmethodsformatching2Dpoint-setsto3Dmodels[3,7,11].Correspondence,ontheotherhand,involvesrecov-eringaconsistentarrangementofpointassignmentlabels.Thecorrespondenceprob-lemcanbesolvedusingavarietyofpointassignment[20,22]andgraphmatching[2,9,14,28]algorithms.Theproblemofpointpatternmatchinghasattractedsustainedinterestinboththevisionandstatisticscommunitiesforseveraldecades.Forinstance,Kendall[13]hasgeneralisedtheprocesstoprojectivemanifoldsusingtheconceptofProcrustesdis-tance.Ullman[23]wasoneofthefirsttorecognisetheimportanceofexploitingri-gidityconstraintsinthecorrespondencematchingofpoint-sets.Recently,severalauthorshavedrawninspirationfromUllman
sideasindevelopinggeneralpurposecorrespondencematchingalgorithmsusingtheGaussianweightedproximitymatrix.ForinstanceScottandLonguet-Higgins[20]locatecorrespondencesbyfindingasin-gularvaluedecompositionoftheinter-imageproximitymatrix.ShapiroandBrady[21],ontheotherhand,matchbycomparingthemodaleigenstructureoftheintra-imageproximitymatrix.Infactthesetwoideasprovidesomeofthebasicground-workonwhichthedeformableshapemodelsofCootesetal.[5]andSclaroffandPentland[18]arebuilt.Thisworkontheco-ordinateproximitymatrixiscloselyakintothatofUmeyama[24]whoshowshowpoint-setsabstractedinastructuralman-nerusingweightedadjacencygraphscanbematchedusinganeigen-decompositionmethod.Theseideashavebeenextendedtoaccommodateparametrisedtransforma-tions[25]whichcanbeappliedtothematchingofarticulatedobjects[26].Morere-cently,therehavebeenseveralattemptsatmodellingthestructuraldeformationofpoint-sets.Forinstance,AmitandKong[2]haveusedagraph-basedrepresentation(graphicaltemplates)tomodeldeformingtwo-dimensionalshapesinmedicalim-ages.Ladesetal.[14]haveusedadynamicmeshtomodelintensity-basedappear-anceinimages.Belongieetal.[19]haveusedso-calledshapecontextsbasedonthechordlengthdistributionassociatedwithboundarypointstorecoverpointcor-respondencesandthenestimatethetransformationbetweentwoshapes.InarecentpaperCrossandHancock[6]developedaunifiedstatisticalframeworkforalignmentandcorrespondence.Themotivationfortheworkwasthatthedichot-omynormallydrawnbetweenthetwoprocessesoverlooksconsiderablescopeforsynergisticinterchangeofinformation.Inotherwords,theremustalwaysbeboundsonalignmentbeforecorrespondenceanalysiscanbeattempted,andviceversa.Theapproachadoptedindevelopingthisnewpoint-patternmatchingmethodwastoem-bedconstraintsonthespatialarrangementofcorrespondenceswithinanEMalgo-rithmforalignmentparameterrecovery.ThisprocesshasmanyfeaturesreminiscentofJordanandJacob
shierarchicalmixtureofexpertsalgorithm[10].Theobserva-tionunderpinningthispaperisthatalthoughthemethodprovedeffectiveitfailstoputthealignmentandcorrespondenceprocessesonasymmetricfooting.There-lationalconstraintsweresimplyusedtogatethecontributionstothelog-likelihoodfunctionforthealignmenterrors.B.Luo,E.R.Han