Image Warping and Morphing Alexey Tikhonov 15 463 Computational Photography Alexei Efros CMU Fall 2008 Women in Art video http youtube com watch v nUDIoN Hxs Image Warping in Biology D Arcy Thompson http www groups dcs st and ac uk history Miscellaneous darcy html http en wikipedia org wiki D Arcy Thompson Importance of shape and structure in evolution Slide by Durand and Freeman Recovering Transformations T x y y y x f x y x g x y What if we know f and g and want to recover the transform T e g better align images from Project 1 willing to let user provide correspondences How many do we need Translation correspondences T x y y y x x How many correspondences needed for translation How many Degrees of Freedom What is the transformation matrix 1 0 p x px M 0 1 p y p y 0 0 1 Euclidian correspondences T x y y y x x How many correspondences needed for translation rotation How many DOF Affine correspondences T x y y y x x How many correspondences needed for affine How many DOF Projective correspondences T x y y y x x How many correspondences needed for projective How many DOF Example warping triangles B B T x y A Source C C A Destination Given two triangles ABC and A B C in 2D 12 numbers Need to find transform T to transfer all pixels from one to the other What kind of transformation is T How can we compute the transformation matrix x a b c x y d e f y 1 0 0 1 1 warping triangles Barycentric Coordinaes 0 1 1 1 0 0 T B Inverse change of basis 1 0 T2 B change of basis C A Source C A Destination Don t forget to move the origin too Very useful for Project 3 hint hint nudge nudge Image warping T x y y y x f x y x g x y Given a coordinate transform x y T x y and a source image f x y how do we compute a transformed image g x y f T x y Forward warping T x y y y x f x y x g x y Send each pixel f x y to its corresponding location x y T x y in the second image Q what if pixel lands between two pixels Forward warping T x y y y x f x y x g x y Send each pixel f x y to its corresponding location x y T x y in the second image Q what if pixel lands between two pixels A distribute color among neighboring pixels x y Known as splatting Check out griddata in Matlab Inverse warping T 1 x y y y x f x y x g x y Get each pixel g x y from its corresponding location x y T 1 x y in the first image Q what if pixel comes from between two pixels Inverse warping T 1 x y y y x f x y x g x y Get each pixel g x y from its corresponding location x y T 1 x y in the first image Q what if pixel comes from between two pixels A Interpolate color value from neighbors nearest neighbor bilinear Gaussian bicubic Check out interp2 in Matlab Forward vs inverse warping Q which is better A usually inverse eliminates holes however it requires an invertible warp function not always possible Morphing Object Averaging The aim is to find an average between two objects Not an average of two images of objects but an image of the average object How can we make a smooth transition in time Do a weighted average over time t How do we know what the average object looks like We haven t a clue But we can often fake something reasonable Usually required user artist input Averaging Points Q What s the average of P and Q v Q P P Linear Interpolation Affine Combination New point aP bQ defined only when a b 1 So aP bQ aP 1 a Q P 0 5v P 0 5 Q P 0 5P 0 5 Q P 1 5v P 1 5 Q P 0 5P 1 5 Q extrapolation P and Q can be anything points on a plane 2D or in space 3D Colors in RGB or HSV 3D Whole images m by n D etc Idea 1 Cross Dissolve Interpolate whole images Imagehalfway 1 t Image1 t image2 This is called cross dissolve in film industry But what is the images are not aligned Idea 2 Align then cross disolve Align first then cross dissolve Alignment using global warp picture still valid Dog Averaging What to do Cross dissolve doesn t work Global alignment doesn t work Cannot be done with a global transformation e g affine Any ideas Feature matching Nose to nose tail to tail etc This is a local non parametric warp Idea 3 Local warp then cross dissolve Morphing procedure for every t 1 Find the average shape the mean dog local warping 2 Find the average color Cross dissolve the warped images Local non parametric Image Warping Need to specify a more detailed warp function Global warps were functions of a few 2 4 8 parameters Non parametric warps u x y and v x y can be defined independently for every single location x y Once we know vector field u v we can easily warp each pixel use backward warping with interpolation Image Warping non parametric Move control points to specify a spline warp Spline produces a smooth vector field Warp specification dense How can we specify the warp Specify corresponding spline control points interpolate to a complete warping function But we want to specify only a few points not a grid Warp specification sparse How can we specify the warp Specify corresponding points interpolate to a complete warping function How do we do it How do we go from feature points to pixels Triangular Mesh 1 Input correspondences at key feature points 2 Define a triangular mesh over the points Same mesh in both images Now we have triangle to triangle correspondences 3 Warp each triangle separately from source to destination How do we warp a triangle 3 points affine warp Just like texture mapping Triangulations A triangulation of set of points in the plane is a partition of the convex hull to triangles whose vertices are the points and do not contain other points There are an exponential number of triangulations of a point set An O n3 Triangulation Algorithm Repeat until impossible Select two sites If the edge connecting them does not intersect previous edges keep it Quality Triangulations Let T 1 2 3t be the vector of angles in the triangulation T in increasing order A triangulation T1 will be better than T2 if T1 T2 lexicographically The Delaunay triangulation is the best Maximizes smallest angles good bad Improving a Triangulation In any convex quadrangle an edge flip is possible If this flip improves the triangulation …
View Full Document