CSE 554 Lecture 9: Laplacian Deformation Fall 2016 CSE554 Laplacian Deformation Slide 1 Review Source Alignment Registering source to target by Input rotation and translation Target Rigid-body transformations Methods Aligning principle directions (PCA) After PCA Aligning corresponding points (SVD) Iterative improvement (ICP) Initialize with PCA Alternate between finding After ICP correspondences and SVD CSE554

Laplacian Deformation Slide 2 Non-rigid Registration Rigid alignment cannot account for shape variance Non-rigid deformation is needed for improved fitting Source Target Rigid alignment CSE554 After non-rigid deformation Laplacian Deformation Slide 3 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 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 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 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 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 Deformed locations of source points: p1,,pn Source q2 p3=q3 p1=q1 p2 An example with 3 handles, two of which are stationary (red) CSE554 Laplacian Deformation Slide 8 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 Fitting Term Sum of squared distances to target handle locations m Ef pi ' qi 2 i 1 q2 p2 CSE554 Laplacian Deformation Slide 10 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 L pi pi 1 Ni pi pj jNi where Ni are indices of neighboring vertices of pi pi1 p i2 p i1 p i2 2 Recall that in fairing, we minimizes this vector to smooth out bumps CSE554 Laplacian Deformation Slide 11 Distortion Term

Minimizing changes in Laplacians during deformation Over all source points n Ed L pi ' i 2 i 1 i: Laplacian at pi before deformation pi ' pi i CSE554 L pi ' Laplacian Deformation Slide 12 Putting Together Finding deformed locations pi that minimize:

E Ef Ed m pi ' qi i1 2 n L pi ' i 2 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 Quadratic Minimization A general form of quadratic minimization: k

min aiT x bi 2 i1 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 Quadratic Minimization Re-writing our minimization in the general form E Ef Ed m pi ' qi i1 2 n

L pi ' i 2 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 Quadratic Minimization The ai and bi in the fitting term m Ef pi ' qi i1 2 m

pix ' qix 2 m i1 2 i1 There are 2m quadratic terms 2 m piy ' qiy aiT x bi x p1x ' , , p nx ', p 2y ' , , p ny ' 2 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 Quadratic Minimization The ai and bi in the fitting term m Ef 2 pi ' qi i1 m pix ' qix 2 m i1 2

piy ' qiy i1 There are 2m quadratic terms 2 m aiT x bi 2 i 1 Example with 3 vertices and 2 fitting constraints (n=3; m=2): a1T a2T a3T a4T CSE554 1 0 0 0 0 1

0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 x p1x p2x p3x p1y p2y p3y ' ' ' ' ' '

b1 q1x b2 q2x b3 q1y b4 q2y Laplacian Deformation 3 1 1 2 2 Slide 17 Quadratic Minimization The ai and bi in the distortion term: n Ed 1 L pi L pi ' i 2 i1 n

i 1 There are 2n quadratic terms ix L p iy ' iy pj j Ni 2 i 1 2 n aiT x bi i1 The first set of n terms: 2 Ni n

L pix ' pi x 2 p 1x ' , , p nx ' , p 2y ' , , p ny ' For i=1,,n, ai is all zero except the (i)th entry is 1, the (j)th entries are -1/|Ni| for all jNi, 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 jNi, and bi+n=iy CSE554 Laplacian Deformation Slide 18 Quadratic Minimization 1 L pi The ai and bi in the distortion term: n Ed i

L pi ' 2 n i1 i 1 There are 2n quadratic terms 2 n ix 2 Ni n L pix ' pi

aiT x bi L p iy ' iy pj j Ni 2 i 1 2 i1 Example with 3 vertices (n=3): a1T a2T a3T a4T a5 T a6T CSE554 1 1

2 1 2 1 2 1 1 2 1 2 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 1 2 1 2

1 1 2 1 2 1 2 1 x p1x p2x p3x p1y p2y p3y ' ' ' ' ' ' Laplacian Deformation b1 b2 b3 b4 b5 b6

1x 2x 3x 1y 2y 3y p3 p1 p2 Slide 19 Quadratic Minimization To solve: k min aiT x bi 2 i1 Re-write in matrix form: min

A x B where A B CSE554 2 a1T akT b1 bk is a k by s matrix is a length-k vector Laplacian Deformation Slide 20 Quadratic Minimization The minimizer is where the partial derivatives are all zero 0 Ax B 2 x 2 AT A x 2 AT B

AT A x AT B To solve for x in this equation: Taking matrix inverse (good for small s, but numerically unstable for large s) x AT A 1 AT B Using specialized linear system solver (LinearSolve in Mathematica, Eigen/TNT/LAPACK in C) CSE554 Laplacian Deformation Slide 21 Summary Compute Laplacians (i) Construct coefficients (ai, bi) Put them into matrices (A,B) Solve (x) CSE554 AT A x AT B x

p1x ', , pnx ', p2y ', , pny ' Laplacian Deformation Slide 22 Results Deformed A small deformation CSE554 Laplacian Deformation Slide 23 Results Deformed A larger deformation CSE554 Laplacian Deformation Slide 24 Results Deformed Stretching CSE554 Laplacian Deformation

Slide 25 Results Deformed Shrinking CSE554 Laplacian Deformation Slide 26 Results Deformed Rotation CSE554 Laplacian Deformation Slide 27 Discussion Limitations Local features dont 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 L pi CSE554

L pi L pi ' Laplacian Deformation pi ' L pi ' Slide 28 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 Ed n L pi ' Ti i 2

i1 CSE554 Laplacian Deformation Slide 29 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 Ed L pi ' Ti i 2 i1 We will focus in the derivations of the 2D case 3D results will be briefly presented at the end CSE554 Laplacian Deformation Slide 30 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 Transformation Matrices (2D) Translation Cartesian coordinates: vector addition p 'x p 'y vx vy px py Homogeneous coordinates: matrix product p 'x p 'y 1 CSE554

1 0 vx 0 1 vy 0 0 1 px py 1 Laplacian Deformation Slide 32 Transformation Matrices (2D) Isotropic scaling Cartesian coordinates: vector scaling p 'x p 'y s px py Homogeneous coordinates: matrix product p x px s 0 0 p 0 s 0 p y 1

CSE554 y 0 0 1 1 Laplacian Deformation Slide 33 Transformation Matrices (2D) Rotation Cartesian coordinates: matrix product p 'x p 'y Cos Sin Sin Cos px py

Homogeneous coordinates: matrix product p 'x p 'y 1 CSE554 Cos Sin 0 Sin Cos 0 Laplacian Deformation 0 0 1 px py 1 Slide 34 Transformation Matrices (2D) Summary of elementary similarity transformations

To perform a sequence of transformations: multiple the corresponding matrices in order Trs v p 'x p 'y 1 M px py 1 Scl s Rot CSE554 Cos Sin 0 Laplacian Deformation 1 0 vx 0 1 vy 0 0 1

s 0 0 0 s 0 0 0 1 Sin Cos 0 0 0 1 Translation by vector v Scaling by scalar s Rotation by angle Slide 35 Similarity Transforms (2D) General similarity transformations T a w tx w a ty 0 0 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 w a ty 0 0 1 Trs tx, ty .Scl a2 w2 .Rot ArcTan a w Note that a and w cant be both zero CSE554 Laplacian Deformation Slide 36 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 min Ti pi pi ' 2 Ti pj pj '

2 jNi pi CSE554 Ti Laplacian Deformation pi ' Slide 37 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 min Ti pi pi ' 2 Ti pj pj ' 2 jNi This is a quadratic minimization problem for entries of T i E.g., a, w, tx, ty

CSE554 Laplacian Deformation Slide 38 Computing Ti (2D) The matrix form of the minimization is: min C a w tx ty pix ' piy ' pi1x ' pi1y ' pix piy where C piy pix 1 0 0 1 pi1x pi1y 1 0

pi1y pi1x 0 1 CSE554 2 is a 2|Ni|+2 by 4 matrix, and Ni={i1, i2,} are indices of neighboring vertices of pi Laplacian Deformation Slide 39 Computing Ti (2D) By quadratic minimization: a w tx ty CT C 1 CT pix ' piy ' pi1x ' pi1y '

Linear expressions of variables (pix , piy) CSE554 Laplacian Deformation Slide 40 Distortion Term (2D) Two parts of each distortion term: Transformed Laplacian: Ti i D a w tx ty D CT C 1 CT pix ' piy ' p i1x ' p i1y ' Ti i

L pi ' 2 where D ix iy 0 0 iy ix 0 0 1 Ni 0 ... 0 1 Ni Laplacian of the deformed locations: L pi ' pix ' piy ' L pi1x ' pi1y ' 1 0 where L

0 1 CSE554 Laplacian Deformation ... is a 2 by 2|Ni| +2 matrix Slide 41 Distortion Term (2D) Putting together: n Ed L pi ' 2 Ti i i1 pix ' piy ' n

H 1 i1 p i1x ' p i1y ' 2 n H 2 i1 pix ' piy ' pi1x ' pi1y ' 2 where H L D CT C 1

CT and H 1 , H 2 are its rows 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 Results (2D) Old distortion term New distortion term CSE554 Laplacian Deformation Slide 43 Results (2D) Old distortion term CSE554 Laplacian Deformation New distortion term Slide 44

Results (2D) Old distortion term New distortion term CSE554 Laplacian Deformation Slide 45 Results (2D) Old distortion term New distortion term CSE554 Laplacian Deformation Slide 46 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 Result CSE554 After rigid alignment 1 iteration of Laplacian 7 iterations of Laplacian Overlaying all curves Laplacian Deformation Slide 48 Result Weighting the distortion term E Ef w Ed large w medium w small w CSE554 Laplacian Deformation Slide 49

Similarity Transforms (3D) Elementary transformation matrices To perform a sequence of transformations: take the product of these matrices p 'x p 'y p 'z 1 Trs v M px py pz 1 Scl s Rot X, CSE554 1 0 0 Cos 0 Sin 0 0 Laplacian Deformation

1 0 0 0 s 0 0 0 0 1 0 0 0 vx 0 vy 1 vz 0 1 0 s 0 0 0 Sin Cos 0 0 0 s 0

0 0 0 1 0 0 0 1 Translation by vector v Scaling by scalar s Rotation by angle around X axis Slide 50 Similarity Transforms (3D) General similarity transformations in 3D T s h3 h2 tx h3 s h1 ty h2 h1 s tz 0 0 0 1 Approximates the product of a set of elementary matrices

Up to a small rotation angle May introduce skewing for large rotations CSE554 Laplacian Deformation Slide 51 Computing Ti (3D) Assuming known deformation, by quadratic minimization: s h1 h2 h3 tx ty tz CT C 1 CT pix ' piy ' piz ' pi1x ' pi1y ' pi1z ' where C

pix 0 piz p iy piy piz 0 pix piz piy pix 0 p i1x 0 p i1z p i1y p i1y p i1z 0 pi1x p i1z p i1y p i1x 0 1 0 0 1 0 0 0 1 0 0 1

0 0 0 1 0 0 1 Linear expressions of the deformed points pi C is a 3|Ni|+3 by 7 matrix CSE554 Laplacian Deformation Slide 52 Distortion Term (3D) Constructing transformed Laplacian: Ti i D s h1 h2 h3 tx ty tz D 1 0

iy iz iz CSE554 CT C piz ' where CT pi1x ' pi1y ' pi1z ' ix where D pix ' piy ' iy iz iy 1 0 0 0 ix 0 1 0 ix 0 0 0 1

Laplacian Deformation Slide 53