Final Class: Range Data registrationThe ProblemData TypesMotivationSlide 5Range ScannersAligning 3D DataIterative Closest Point AlgorithmCorresponding Point Set AlignmentSlide 10Slide 11Slide 12Slide 13Slide 14Closest PointFinding MatchesFinding MatchesThe AlgorithmConvergence TheoremICP VariantsSlide 21Slide 22Slide 23Slide 24Rejecting PairsSlide 26Error metric and minimization3D Surface-to-surface Motion AnalysisSlide 29BackgroundSlide 31From World to Local CoordinateProblem StatementSlide 34Slide 35ExperimentsTongue Motion AnalysisSlide 38Slide 39Evaluation of Structure and Nonrigid MotionFace Motion ApplicationREVIEWThank you!Final Class: Range Data registrationCISC4/689Credits: Tel-Aviv UniversityThe Problem•Align two partially-overlapping meshesgiven initial guessfor relative transformData Types•Point sets•Line segment sets (polylines)•Implicit curves : f(x,y,z) = 0•Parametric curves : (x(u),y(u),z(u))•Triangle sets (meshes)•Implicit surfaces : s(x,y,z) = 0•Parametric surfaces (x(u,v),y(u,v),z(u,v)))Motivation•Shape inspection•Motion estimation•Appearance analysis•Texture Mapping•Labeling (atlas registration)Motivation•Range images registrationRange ScannersAligning 3D DataIterative Closest Point Algorithm•Also called ICP algorithm proposed in 1992.•Many variants have come into existence after the original algorithm proposed by Besl and Mackay.Corresponding Point Set Alignment•Let M be a model point set. •Let S be a scene point set.We assume :1. NM = NS.2. Each point Si correspond to Mi .Corresponding Point Set AlignmentThe objective function :The alignment is :SSNiTiRiSNiiiSqsqRmNqfTranssRotmNTRf1212)(1)()(1),(),(),,( SMdtransrotmseAligning 3D Data•If correct correspondences are known, can find correct relative rotation/translationAligning 3D Data•How to find correspondences: User input? Feature detection? Signatures?•Alternative: assume closest points correspondAligning 3D Data•How to find correspondences: User input? Feature detection? Signatures?•Alternative: assume closest points correspondAligning 3D Data•Converges if starting position “close enough“Closest Point•Given 2 points r1 and r2 , the Euclidean distance is:• Given a point r1 and set of points A , the Euclidean distance is:2212212212121)()()(),( zzyyxxrrrrd ),(min),(1..11 iniardArdFinding Matches•The scene shape S is aligned to be in the best alignment with the model shape M.•The distance of each point s of the scene from the model is :smdMsdMmmin),(Finding Matches •Finding each match is performed in O(NM) worst case.•Given correspondence, Y we can calculate alignment•S is updated to be :),(),,( YSdtransrot transSrotSnew )(The AlgorithmInit the error to ∞Calculate correspondenceCalculate alignmentApply alignmentUpdate errorIf error > thresholdY = CP(M,S),e(rot,trans,d)S`= rot(S)+transd` = dConvergence Theorem•Correspondence error :•Alignment error:SNiikikSksyNe121SNikiokikSkTranssRo tyNd12)(1ICP Variants•Variants on the following stages of ICPhave been proposed:1. Selecting sample points (from one or both meshes)2. Matching to points in the other mesh3. Weighting the correspondences4. Rejecting certain (outlier) point pairs5. Assigning an error metric to the current transform6. Minimizing the error metric w.r.t. transformationICP Variants1. Selecting sample points (from one or both meshes).2. Matching to points in the other mesh.3. Weighting the correspondences.4. Rejecting certain (outlier) point pairs.5. Assigning an error metric to the current transform.6. Minimizing the error metric w.r.t. transformation.ICP Variants1. Selecting sample points (from one or both meshes).2. Matching to points in the other mesh using invariants.3. Weighting the correspondences.4. Rejecting certain (outlier) point pairs.5. Assigning an error metric to the current transform.6. Minimizing the error metric w.r.t. transformation.ICP Variants1. Selecting sample points (from one or both meshes).2. Matching to points in the other mesh.3. Weighting the correspondences.4. Rejecting certain (outlier) point pairs.5. Assigning an error metric to the current transform.6. Minimizing the error metric w.r.t. transformation.ICP Variants1. Selecting sample points (from one or both meshes).2. Matching to points in the other mesh.3. Weighting the correspondences.4. Rejecting certain (outlier) point pairs.5. Assigning an error metric to the current transform.6. Minimizing the error metric w.r.t. transformation.Rejecting PairsInconsistent Pairsp1p2q2q1ICP Variants1. Selecting sample points (from one or both meshes).2. Matching to points in the other mesh.3. Weighting the correspondences.4. Rejecting certain (outlier) point pairs.5. Assigning an error metric to the current transform.6. Minimizing the error metric w.r.t. transformation.Error metric and minimization•Sum of squared distances between corresponding points .There exist closed form solutions for rigid body transformation :1. SVD2. Quaternions3. Orthonoraml matrices4. Dual quaternions.3D Surface-to-surface Motion Analysis•Direct Shape-based method:–J. S. Duncan, et al. 1991–J. Feldmar, et al. 1996–Y. Wang, et al. 2000–D. Meier, et al. 2002 Curvature differenceNormal difference• Nonrigid Shape-based method:Nonrigid Shape-based method: • Nonrigid shape relationship between the before-motion and after-Nonrigid shape relationship between the before-motion and after-motion surfaces is described by the undergoing nonrigid motion.motion surfaces is described by the undergoing nonrigid motion.• C. Kambhamettu, et al. CVPR 1992C. Kambhamettu, et al. CVPR 1992• C. Kambhamettu, et al. CVGIP:IU 1994C. Kambhamettu, et al. CVGIP:IU 1994• C. Kambhamettu, et al. IVC 2003C. Kambhamettu, et al. IVC 2003• P. Laskov, et al. PAMI 2003P. Laskov, et al. PAMI 20033D Surface-to-surface Motion Analysis•Previous Nonrigid Shape-based Methods–A local coordinate system is constructed at each point of interest•Defined motion has no explicit physical meaning–Each point of interest is looking for its corresponding point independently•Motion consistency can not be guaranteed• New Approach of Nonrigid Shape-based MethodNew Approach of Nonrigid Shape-based Method• Nonrigid motion is modeled with a Nonrigid motion is modeled with a single single spline-based spline-based motion field