Laplacian Deformation in Engineering and Applied Science
Laplacian deformation is a technique used in non-rigid registration to account for shape variance and improve fitting between source and target shapes. This method involves minimizing the distance and distortion terms to achieve accurate alignment. Intrinsic and extrinsic methods are discussed, where intrinsic deforms points on the source while extrinsic deforms all points around the source. Intrinsic registration involves relocating source points based on given handles to fit target points and achieve natural deformation. This process involves iterative improvement by finding correspondences and deformation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Washington University in St. Louis, School of Engineering and Applied Science CSE 554 Lecture 9: Laplacian Deformation Fall 2016 CSE554 Laplacian Deformation Slide 1
Washington University in St. Louis, School of Engineering and Applied Science Review Source Alignment Registering source to target by rotation and translation Input Target Rigid-body transformations Methods After PCA Aligning principle directions (PCA) Aligning corresponding points (SVD) Iterative improvement (ICP) Initialize with PCA After ICP Alternate between finding correspondences and SVD CSE554 Laplacian Deformation Slide 2
Washington University in St. Louis, School of Engineering and Applied Science Non-rigid Registration Rigid alignment cannot account for shape variance Non-rigid deformation is needed for improved fitting Source Target Rigid alignment After non-rigid deformation CSE554 Laplacian Deformation Slide 3
Washington University in St. Louis, School of Engineering and Applied Science Non-rigid Registration A minimization problem Minimizing the distance between the deformed source and the target Fitting term Minimizing the distortion to the source shape Distortion term CSE554 Laplacian Deformation Slide 4
Washington University in St. Louis, School of Engineering and Applied Science Intrinsic vs. Extrinsic Intrinsic methods Deforms points on the source curve/surface App: boundary curve or surface matching Extrinsic methods Deforms all points in the space around the source curve/surface App: image or volume matching CSE554 Laplacian Deformation Slide 5
Washington University in St. Louis, School of Engineering and Applied Science Intrinsic Registration Target Given a source and target shape Plus correspondences between some source points (called handles) and target points Handle Relocate source points such that: The handles move to their corresponding targets (fitting term) The rest of the shape deforms as naturally as possible (distortion term) ICP-style registration Alternate between finding correspondences (e.g., closest neighbors) and deformation CSE554 Laplacian Deformation Slide 6
Washington University in St. Louis, School of Engineering and Applied Science Laplacian-based Deformation An intrinsic method used in graphics/animation Simple and efficient (fitting/distortion terms are quadratic) Preserving local shape features Reference: Laplacian surface editing , by Sorkine et al., 2004 CSE554 Laplacian Deformation Slide 7
Washington University in St. Louis, School of Engineering and Applied Science Setup Input Source with n points: p1, ,pn For notation purpose, assume that the first m points are handles Target location of handles: q1, ,qm Output Deformed locations of source points: p1 , ,pn Deformed Source q2 p3=q3 p1=q1 p2 An example with 3 handles, two of which are stationary (red) CSE554 Laplacian Deformation Slide 8
Washington University in St. Louis, School of Engineering and Applied Science Overview Finding deformed locations pi that minimize: E Ef Ed Ef: fitting term Measures how close are the deformed handles to the target Ed: distortion term Measures how much the source shape is changed CSE554 Laplacian Deformation Slide 9
Washington University in St. Louis, School of Engineering and Applied Science Fitting Term Sum of squared distances to target handle locations m 2 Ef pi' qi i 1 q2 p2 CSE554 Laplacian Deformation Slide 10
Washington University in St. Louis, School of Engineering and Applied Science Distortion Term Q: How to measure shape locally? A: By bumpiness at each vertex Laplacian: vector from the centroid of neighbors to the vertex A linear operator over point locations pi 1 L pi pi pj Ni j Ni pi2 pi1 where Ni are indices of neighboring vertices of pi pi1 pi2 2 Recall that in fairing, we minimizes this vector to smooth out bumps CSE554 Laplacian Deformation Slide 11
Washington University in St. Louis, School of Engineering and Applied Science Distortion Term Minimizing changes in Laplacians during deformation Over all source points n 2 Ed L pi' i i 1 i: Laplacian at pi before deformation pi' pi L pi' i CSE554 Laplacian Deformation Slide 12
Washington University in St. Louis, School of Engineering and Applied Science Putting Together Finding deformed locations pi that minimize: E Ef Ed m n 2 2 pi' qi L pi' i i 1 i 1 A quadratic equation in terms of variables (pix , piy , piz ) qi, i are constants L[] is a linear operator CSE554 Laplacian Deformation Slide 13
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization A general form of quadratic minimization: k 2 aiTx min bi i 1 There are s variables: x=(x1, ,xs)T Each a1, , ak is a length-s column vector (linear coefficients) Each b1, , bk is a scalar (constant coefficients) k should be greater than s (so that the problem is over-constrained) CSE554 Laplacian Deformation Slide 14
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization Re-writing our minimization in the general form E Ef Ed m n 2 2 pi' qi L pi' i i 1 i 1 In 2D, there are s=2n variables: x = (p1x , , pnx , p1y , , pny )T In 3D, there are s=3n variables We will next re-write each quadratic term in 2D as (aix-bi)2 Can be extended easily to 3D CSE554 Laplacian Deformation Slide 15
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization The ai and bi in the fitting term m m m 2 2 2 Ef pi' qi pix' qix piy' qiy i 1 i 1 i 1 There are 2m quadratic terms x p1x', , pnx', p2y', , pny' 2 m 2 aiTx bi i 1 In the first set of m terms: For i=1, ,m, bi=qix, ai contains all zero, except its (i)th entry is 1. In the second set of m terms: For i=1, ,m, bi+m=qiy, ai+m contains all zero, except its (i+n)th entry is 1 CSE554 Laplacian Deformation Slide 16
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization The ai and bi in the fitting term m m m 2 2 2 Ef pi' qi pix' qix piy' qiy i 1 i 1 i 1 There are 2m quadratic terms 2 m 2 aiTx bi i 1 Example with 3 vertices and 2 fitting constraints (n=3; m=2): ?3 p1x' p2x' p3x' p1y' p2y' p3y' a1T a2T a3T a4T b1 b2 b3 b4 q1x q2x q1y q2y 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 x ?1 ?2 ?1 ?2 CSE554 Laplacian Deformation Slide 17
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization 1 The ai and bi in the distortion term: L pi pi pj Ni j Ni n n n 2 2 2 Ed L pi' L pix' L piy' i ix iy i 1 i 1 i 1 There are 2n quadratic terms 2 n 2 aiTx bi i 1 x p1x', , pnx', p2y', , pny' The first set of n terms: For i=1, ,n, ai is all zero except the (i)th entry is 1, the (j)th entries are -1/|Ni| for all j Ni, and bi=ix The second set of n terms: For i=1, ,n, ai+n is all zero except the (i+n)th entry is 1, the (j+n)th entries are -1/|Ni| for all j Ni, and bi+n=iy CSE554 Laplacian Deformation Slide 18
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization 1 The ai and bi in the distortion term: L pi pi pj Ni j Ni n n n 2 2 2 Ed L pi' L pix' L piy' i ix iy i 1 i 1 i 1 There are 2n quadratic terms 2 n 2 aiTx bi i 1 Example with 3 vertices (n=3): 1 2 1 1 2 1 2 1 0 0 0 a1T 1 0 0 0 p3 p1x' p2x' p3x' p1y' p2y' p3y' b1 b2 b3 b4 b5 b6 1x 1 2 1 2 a2T 0 0 0 2x 1 2 a3T 3x x 1y 1 2 1 1 2 1 2 1 a4T 0 0 0 1 p2 p1 2y 1 2 1 2 a5T 0 0 0 3y 1 2 a6T 0 0 0 CSE554 Laplacian Deformation Slide 19
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization To solve: k 2 aiTx min bi i 1 Re-write in matrix form: 2 min A x B a1T where A is a k by s matrix akT b1 is a length-k vector B bk CSE554 Laplacian Deformation Slide 20
Washington University in St. Louis, School of Engineering and Applied Science Quadratic Minimization The minimizer is where the partial derivatives are all zero 2 Ax B 0 x ATA x ATB 2 ATA x 2 ATB To solve for x in this equation: Taking matrix inverse (good for small s, but numerically unstable for large s) 1ATB ATA x Using specialized linear system solver (LinearSolve in Mathematica, Eigen/TNT/LAPACK in C) CSE554 Laplacian Deformation Slide 21
Washington University in St. Louis, School of Engineering and Applied Science Summary Compute Laplacians (i) Construct coefficients (ai, bi) Put them into matrices (A,B) Solve (x) ATA x ATB x p1x', , pnx', p2y', , pny' CSE554 Laplacian Deformation Slide 22
Washington University in St. Louis, School of Engineering and Applied Science Results Deformed A small deformation CSE554 Laplacian Deformation Slide 23
Washington University in St. Louis, School of Engineering and Applied Science Results Deformed A larger deformation CSE554 Laplacian Deformation Slide 24
Washington University in St. Louis, School of Engineering and Applied Science Results Deformed Stretching CSE554 Laplacian Deformation Slide 25
Washington University in St. Louis, School of Engineering and Applied Science Results Deformed Shrinking CSE554 Laplacian Deformation Slide 26
Washington University in St. Louis, School of Engineering and Applied Science Results Deformed Rotation CSE554 Laplacian Deformation Slide 27
Washington University in St. Louis, School of Engineering and Applied Science Discussion Limitations Local features don t rotate or scale with the model Reason: Laplacian is not invariant under rotation or scale Two bumps that differ by rotation or scale result in non-zero distortion pi' pi L pi' L pi L pi' L pi CSE554 Laplacian Deformation Slide 28
Washington University in St. Louis, School of Engineering and Applied Science A Better Distortion Term Not penalizing rotation and scaling of local features Estimating how the local neighborhood is transformed pi Ti pi' Transforming the original Laplacian vectors before comparing to the deformed Laplacians n 2 Ed L pi' Ti i i 1 CSE554 Laplacian Deformation Slide 29
Washington University in St. Louis, School of Engineering and Applied Science Catch 22 Q: How do we find Ti before we know the deformed shape? A: Represent Ti as a function of the unknown variables A linear function of pi , just like L n 2 Ed L pi' Ti i i 1 We will focus in the derivations of the 2D case 3D results will be briefly presented at the end CSE554 Laplacian Deformation Slide 30
Washington University in St. Louis, School of Engineering and Applied Science Transformation Matrices (2D) Homogeneous coordinates A 2D point: (x,y,1) A 2D vector: (x,y,0) A 3D point: (x,y,z,1) A 3D vector: (x,y,z,0) CSE554 Laplacian Deformation Slide 31
Washington University in St. Louis, School of Engineering and Applied Science Transformation Matrices (2D) Translation Cartesian coordinates: vector addition ' px py vx vy px py ' Homogeneous coordinates: matrix product ' px py 1 1 0 vx 0 1 vy 0 0 px py 1 ' 1 CSE554 Laplacian Deformation Slide 32
Washington University in St. Louis, School of Engineering and Applied Science Transformation Matrices (2D) Isotropic scaling Cartesian coordinates: vector scaling ' px py px py s ' Homogeneous coordinates: matrix product px py 1 px py 1 s 0 0 0 s 0 0 0 1 CSE554 Laplacian Deformation Slide 33
Washington University in St. Louis, School of Engineering and Applied Science Transformation Matrices (2D) Rotation Cartesian coordinates: matrix product ' px py px py Cos Sin Sin Cos ' Homogeneous coordinates: matrix product ' px py 1 px py 1 Cos Sin Sin Cos 0 0 1 ' 0 0 CSE554 Laplacian Deformation Slide 34
Washington University in St. Louis, School of Engineering and Applied Science Transformation Matrices (2D) Summary of elementary similarity transformations To perform a sequence of transformations: multiple the corresponding matrices in order 1 0 vx 0 1 vy 0 0 Trs v Translation by vector v ' 1 px py 1 px py 1 ' M s 0 0 0 s 0 0 0 1 Scaling by scalar s Scl s Cos Sin Sin Cos 0 0 1 Rotation by angle Rot 0 0 CSE554 Laplacian Deformation Slide 35
Washington University in St. Louis, School of Engineering and Applied Science Similarity Transforms (2D) General similarity transformations a w tx w a ty 0 0 T 1 The product of any set of similarity matrices can be written this way Any choice of (a, w, tx, ty) can be written as a sequence of rotation, isotropic scaling and translation a w tx a a2 w2 w a ty 0 0 Trs tx, ty .Scl .Rot ArcTan w 1 Note that a and w can t be both zero CSE554 Laplacian Deformation Slide 36
Washington University in St. Louis, School of Engineering and Applied Science Computing Ti (2D) Suppose we know the deformed locations pi Compute Ti as the similarity transform that best fits the neighborhood of pi to that of pi 2 2 min Tipi pi' Tipj pj' j Ni pi Ti pi' CSE554 Laplacian Deformation Slide 37
Washington University in St. Louis, School of Engineering and Applied Science Computing Ti (2D) Suppose we know the deformed locations pi Compute Ti as the similarity transform that best fits the neighborhood of pi to that of pi 2 2 min Tipi pi' Tipj pj' j Ni This is a quadratic minimization problem for entries of Ti E.g., a, w, tx, ty CSE554 Laplacian Deformation Slide 38
Washington University in St. Louis, School of Engineering and Applied Science Computing Ti (2D) The matrix form of the minimization is: 2 pix' piy' pi1x' pi1y' a w tx ty min C pix piy pi1x pi1y piy pix pi1y pi1x 1 0 0 1 1 0 0 1 where is a 2|Ni|+2 by 4 matrix, and Ni={i1, i2, } are indices of neighboring vertices of pi C CSE554 Laplacian Deformation Slide 39
Washington University in St. Louis, School of Engineering and Applied Science Computing Ti (2D) By quadratic minimization: pix' piy' pi1x' pi1y' a w tx ty 1CT CTC Linear expressions of variables (pix , piy ) CSE554 Laplacian Deformation Slide 40
Washington University in St. Louis, School of Engineering and Applied Science Distortion Term (2D) Two parts of each distortion term: 2 L pi' Ti i Transformed Laplacian: pix' piy' pi1x' pi1y' a w tx ty 0 0 ix iy ix0 0 1CT D CTC where Ti D D i iy Laplacian of the deformed locations: pix' piy' pi1x' pi1y' 1 1 0 0 ... Ni 0 where is a 2 by 2|Ni|+2 matrix L pi' L L 1 0 1 ... Ni CSE554 Laplacian Deformation Slide 41
Washington University in St. Louis, School of Engineering and Applied Science Distortion Term (2D) Putting together: n 2 Ed L pi' Ti i i 1 2 2 pix' piy' pi1x' pi1y' pix' piy' pi1x' pi1y' 1CT D CTC n n where H L H 1 H 2 and are its rows H 1 , H 2 i 1 i 1 They form 2n quadratic terms (aix-bi)2 for x = (p1x , , pnx , p1y , , pny )T All bi are zero Each ai can be extracted from H CSE554 Laplacian Deformation Slide 42
Washington University in St. Louis, School of Engineering and Applied Science Results (2D) Old distortion term New distortion term CSE554 Laplacian Deformation Slide 43
Washington University in St. Louis, School of Engineering and Applied Science Results (2D) New distortion term Old distortion term CSE554 Laplacian Deformation Slide 44
Washington University in St. Louis, School of Engineering and Applied Science Results (2D) Old distortion term New distortion term CSE554 Laplacian Deformation Slide 45
Washington University in St. Louis, School of Engineering and Applied Science Results (2D) Old distortion term New distortion term CSE554 Laplacian Deformation Slide 46
Washington University in St. Louis, School of Engineering and Applied Science Registration Use nearest neighbors as corresponding target locations Assuming the source is already close to the target Iterative closest point (ICP) 1. For each point on the source pi, treat it as a handle, and assign its closest point on the target as its target location qi. 2. Compute Laplacian-based deformation. 3. Repeat step (1) until a termination criteria is met. CSE554 Laplacian Deformation Slide 47
Washington University in St. Louis, School of Engineering and Applied Science Result After rigid alignment 1 iteration of Laplacian 7 iterations of Laplacian Overlaying all curves CSE554 Laplacian Deformation Slide 48
Washington University in St. Louis, School of Engineering and Applied Science Result Weighting the distortion term E Ef w Ed large w medium w small w CSE554 Laplacian Deformation Slide 49
Washington University in St. Louis, School of Engineering and Applied Science Similarity Transforms (3D) Elementary transformation matrices To perform a sequence of transformations: take the product of these matrices 1 0 0 vx 0 1 0 vy 0 0 1 vz 0 0 0 Translation by vector v Trs v ' px py pz 1 px py pz 1 1 ' M s 0 0 0 0 s 0 0 0 0 s 0 0 0 0 1 ' Scaling by scalar s Scl s 1 0 Cos 0 Sin 0 0 0 0 0 0 1 Rotation by angle around X axis Sin Cos Rot X, 0 0 CSE554 Laplacian Deformation Slide 50
