OutlineIntroductionWhat is ICP?MotivationAssumptionsMathematics of ICPDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationIterative Closest Point AlgorithmICP OverviewLimitationsExperimentResultsQuestionsBibliographyOutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographySummary of ”A Method for Registration of 3-DShapes”Original Article by Paul J. BeslTianhe YangOptics DepartmentUniversity of MichiganTianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliography1 Outline2 IntroductionWhat is ICP?MotivationAssumptions3 Mathematics of ICPDistance to a...Point to Parametric EntityImplicit EntitiesRegistration4 Iterative Closest Point AlgorithmICP OverviewLimitations5 ExperimentResults6 Questions7 BibliographyTianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyWhat is ICP?MotivationAssumptionsWhat is Iterative Closest Point?DefinitionAn ICP algorithm attempts to match two sets of points. One of thesesets might be a reference image, while the other is a set of data pointsdescribing the ranges to certain points on an object.Basic ICP StepsIn general ICP has to select some set of points in one or both meshes,match these points to samples in the other set, assigning a definition forerror, minimizing that definition of error by iteration. The model shapecan be a point set, a set of polylines, a set of parametric curves, a set ofimplicit curves, or a set of implicit surfaces.Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyWhat is ICP?MotivationAssumptionsGoalsGiven3D data in a sensor coordinate system.Model shape in model coordinate system.Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyWhat is ICP?MotivationAssumptionsGoalsProduceOptimal rotation or translation that aligns model shape and datashape.This ”alignment” is called registration.Goal is to minimize the distance between model shape and datashape.The error is measured by a mean-square distance metric.Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyWhat is ICP?MotivationAssumptionsApplicationRegister (align) digitized data from rigid objects with an idealizedmodel (CAD, etc.)Inspect to see if shape of object is within specs.Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyWhat is ICP?MotivationAssumptionsDepth MeasurementUsing high-accuracy measurement tools over a shallow depth offield, uncertainty in different points does not change very much.Measurement device doesn’t generate bad data; no outliers.Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationThe NormDistance Between Two PointsThe distance d(~r1,~r2) where ~r1= {x1, y1, z1} and ~r2= {x 2, y2, z 2} is:d(~r1,~r2) =p(x2− x1)2+ (y2− y1)2+ (z2− z1)2) (1)This is just the equation for the norm of a vector.Distance to a Set of PointsThe distance to a set of Napoints, A, from a point ~p is the distance tothe closest point in A. A = {ai}d(~p, A) = mini∈{1,...,Na}d(~p, ~ai) (2)Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationFor a LineDistance to a LineFor a line segment l connecting two points ~r1and ~r2, the distancebetween the point ~p (typo in the paper) and the line segment l is:d(~p, l) = minu+v =1ku~r1+ v~r2−~pk (3)where u ∈ [0, 1], v ∈ [0, 1].r1r2d(p,l)Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationFor NlLinesFor a set of Nllines, LNlline segments are denoted by li, and L = {li} for i = 1, . . . , Nl. Thedistance between point ~p and the line segments L is thus:d(~p, L) = mini∈{1,...,Nl}d(~p, li) (4)Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationFor a TriangleDistance Between a Point and a TriangleWe can similarly state that the distance between a point ~p and a trianglet is:d(~p, t) = minu+v +w=1ku~r1+ v~r2+ w~r3−~pk (5)where u ∈ [0, 1], v ∈ [0, 1], and w ∈ [0, 1].Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationFor NtTrianglesDistance Between a Point and a Set of TrianglesLet T be a set of Nttriangles denoted ti, and let T = {ti} fori = 1, . . . , Nt. The distance between a point ~p and the set of triangles Tcan be written as:d(~p, T ) = mini∈{1,...,Nt}d(~p, ti) (6)Tianhe Yang Summary of ”A Method for Registration of 3-D Shapes”OutlineIntroductionMathematics of ICPIterative Closest Point AlgorithmExperimentQuestionsBibliographyDistance to a...Point to Parametric EntityImplicit EntitiesRegistrationReview of Parametric CurvesWhy Use Parametric Curves?For simple functions such as y = mx + b, there is no need for parametricfunctions to describe this object. However, as curves get more complex,we may not be able to describe them in this form. For example, considera sphere (x2+ y2= r2). To describe the whole sphere, we need at leasttwo equations (x =pr2− y2for the right side, and x = −pr2− y2)for the left side.Parametric CurvesInstead of defining a variable as a function of another variable, we candefine the other variable as a function.