3-Points Convex Hull Matching (3PCHM) for Fast and Robust Point Set Registration
Abstract—Pointsetregistrationplaysacrucialroleinnumerouscomputervisionapplications.Thispaperproposes
a novelandgeneralapproachcalledthree-pointconvexhullmatching(3PCHM)forregisteringtwopoint
sets withsimilaritytransform.First,convexhullsareextractedfrombothpointsets.Triangularpatches
on thesurfaceofconvexhullsarespecified bypredefining theirnormalvectors,thusguaranteeingthat
all pointsarelocatedonthesamesideofanyrandomlyselectedtriangleplane.Second,thepotential
similar trianglepairsetisobtainedbycomparingthelengthratiooftheedgesonthetwoextracted
convexhulls.Thereafter,thetransformationparametersforeachpairwisetrianglearecalculatedby
minimizing theEuclideandistancebetweenthecorrespondingvertexpairs.Furthermore,ak-
dimensional (k-d)treeisusedtoacceleratetheclosestpointsearchforthewholepointsets.Third,
outliers thatmayleadtosignificant errorsarediscardedbyintegratingtherandomsampleconsensus
algorithm forglobaloptimization.Experimentsshowthattheproposed3PCHMisrobustevenwiththe
existenceofnoiseandoutliersandiseffectiveincasesofpart-to-partregistrationandpart-to-whole
registration.
