Efficient Variants of the ICP Algorithm

TheICP (IterativeClosestPoint) algorithmis widelyusedfor geometric alignmentof three-dimensional modelswhenan initial estimateof therelativeposeis known.Manyvariantsof ICP have beenproposed,affectingall phasesof thealgorithmfromtheselection and matching of points to the minimizationstrategy. We enumer ateandclassifymanyof thesevariants,andevaluatetheir effect on the speedwith which the correct alignmentis reached. In order to improveconvergencefor nearly-flatmesheswith small features,such as inscribedsurfaces,we introducea new variant basedon uniformsamplingof thespaceof normals.We conclude by proposinga combinationof ICP variantsoptimizedfor high speed. We demonstr ate an implementationthat is able to align two range imagesin a few tensof milliseconds,assuminga good initial guess.Thiscapabilityhaspotentialapplicationto real-time 3D modelacquisitionandmodel-basedtracking. 1 Intr oduction – Taxonom y of ICP Variants TheICP(originally IterativeClosestPoint,thoughIterativeCorrespondingPointis perhapsabetterexpansionfor theabbreviation) algorithm hasbecomethe dominantmethodfor aligning threedimensional modelsbasedpurelyonthegeometry, andsometimes color, of themeshes.Thealgorithmis widely usedfor registering the outputsof 3D scanners, which typically only scanan object from one direction at a time. ICP startswith two meshesand an initial guessfor their relative rigid-body transform,anditeratively refinesthetransformby repeatedlygeneratingpairsof correspondingpointson themeshesandminimizing anerrormetric. Generatingtheinitial alignmentmaybedoneby avarietyof methods,suchas trackingscannerposition, identificationand indexing of surfacefeatures[Faugeras86, Stein92], “spin-image”surfacesignatures[Johnson97a], computingprincipalaxesof scans [Dorai 97], exhausti ve searchfor correspondingpoints[Chen98, Chen99], or userinput. In thispaper , we assumethata roughinitial alignmentis alwaysavailable. In addition,we focusonly on aligningasinglepairof meshes, anddonotaddresstheglobalregistrationproblem[Bergevin 96, Stoddart96, Pulli 97, Pulli 99]. Sincetheintroductionof ICP by ChenandMedioni [Chen91] andBesl andMcKay [Besl 92], many variantshave beenintroducedon thebasicICP concept.We may classifythesevariants asaffectingoneof six stagesof thealgorithm: 1. Selection of somesetof pointsin oneor bothmeshes. 2. Matching thesepointsto samplesin theothermesh. 3. Weighting thecorrespondingpairsappropriately . 4. Rejecting certainpairsbasedon looking at eachpair individually or consideringtheentiresetof pairs. 5. Assigninganerror metric basedon thepointpairs. 6. Minimizing theerrormetric. In this paper , we will look at variantsin eachof thesesix categories,andexaminetheir effectson theperformanceof ICP. Althoughour main focus is on the speedof convergence,we also considertheaccuracy of thefinal answerandtheability of ICP to reachthecorrectsolutiongiven“dif ficult” geometry. Ourcompar isonssuggesta combinationof ICP variantsthat is ableto aligna pair of meshesin a few tensof milliseconds,significantlyfaster thanmostcommonly-usedICP systems.Theavailability of such areal-timeICPalgorithmmayenablesignificantnew applications in model-basedtrackingand3D scanning. In this paper , we first presentthe methodologyusedfor comparingICP variants,andintroducea numberof testscenesused throughoutthepaper . Next, wesummarizeseveralICPvariantsin eachof the above six categories,andcomparetheir convergence performance.As part of the comparison,we introducethe conceptof normal-space-directed sampling,andshow thatit improves convergencein scenesinvolving sparse,small-scalesurfacefeatures. Finally, we examinea combinationof variantsoptimized for highspeed. 2 Comparison Methodology Our goal is to comparetheconvergencecharacteristicsof several ICPvariants.In orderto limit thescopeof theproblem,andavoid acombinatorialexplosionin thenumberof possibilities,weadopt themethodologyof choosinga baselinecombinationof variants, andexaminingperformanceasindividual ICP stagesarevaried. Thealgorithmwe will selectasour baselineis essentiallythatof [Pulli 99], incorporatingthefollowing features: Randomsamplingof pointsonbothmeshes. Matching eachselectedpoint to the closestsamplein the othermeshthathasanormalwithin 45degreesof thesource normal. Uniform (constant)weightingof pointpairs. Rejectionof pairscontainingedgevertices,aswell asa percentageof pairswith thelargestpoint-to-pointdistances. Point-to-planeerrormetric. The classic“select-match-minimize”iteration, rather than someothersearchfor thealignmenttransform. We pick this algorithm becauseit hasrecei ved extensi ve usein a productionenvironment[Levoy 00], andhasbeenfound to be robustfor scanneddatacontainingmany kindsof surfacefeatures. In addition, to ensurefair comparisonsamongvariants,we make thefollowing assumptions: Thenumberof sourcepointsselectedis always2,000.Since themesheswewill considerhave100,000samples, thiscorrespondsto a samplingrateof 1% permeshif sourcepoints areselectedfrom bothmeshes, or 2% if pointsareselected from only onemesh. All mesheswe usearesimpleperspecti ve rangeimages,as opposedto generalirregularmeshes, sincethisenablescomparisonsbetween“closestpoint” and“projectedpoint” variants(seeSection3.2). Surface normalsare computedsimply basedon the four nearestneighborsin therangegrid.