Image Warping and Morphing15-463: Computational PhotographyAlexei Efros, CMU, Fall 2007© Alexey TikhonovD'Arcy Thompson http://www-groups.dcs.st-and.ac.uk/~history/Miscellaneous/darcy.htmlhttp://en.wikipedia.org/wiki/D'Arcy_ThompsonImportance of shape and structure in evolutionSlide by Durand and FreemanImage Warping in BiologyRecovering TransformationsWhat 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?xx’T(x,y)yy’f(x,y) g(x’,y’)?Translation: # correspondences?How many correspondences needed for translation?How many Degrees of Freedom?What is the transformation matrix?xx’T(x,y)yy’?⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−=100'10'01yyxxppppMEuclidian: # correspondences?How many correspondences needed for translation+rotation?How many DOF?xx’T(x,y)yy’?Affine: # correspondences?How many correspondences needed for affine?How many DOF?xx’T(x,y)yy’?Projective: # correspondences?How many correspondences needed for projective?How many DOF?xx’T(x,y)yy’?Example: warping trianglesGiven 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:T(x,y)?ABCA’C’B’Source Destination⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡11001''yxfedcbayxwarping triangles (Barycentric Coordinaes)Very useful for Project 3… (hint,hint,nudge,nudge)ABCA’C’B’Source Destination(0,0) (1,0)(0,1)changeof basisInverse changeof basisDon’t forget to move the origin too!2T11−TImage warpingGiven 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))?xx’T(x,y)f(x,y) g(x’,y’)yy’f(x,y) g(x’,y’)Forward warpingSend each pixel f(x,y) to its corresponding location (x’,y’) = T(x,y) in the second imagexx’T(x,y)Q: what if pixel lands “between” two pixels?yy’f(x,y) g(x’,y’)Forward warpingSend each pixel f(x,y) to its corresponding location (x’,y’) = T(x,y) in the second imagexx’T(x,y)Q: what if pixel lands “between” two pixels?yy’A: distribute color among neighboring pixels (x’,y’)– Known as “splatting”– Check out griddata in Matlabf(x,y) g(x’,y’)xyInverse warpingGet each pixel g(x’,y’) from its corresponding location (x,y)=T-1(x’,y’) in the first imagexx’Q: what if pixel comes from “between” two pixels?y’T-1(x,y)f(x,y) g(x’,y’)xyInverse warpingGet each pixel g(x’,y’) from its corresponding location (x,y)=T-1(x’,y’) in the first imagexx’T-1(x,y)Q: what if pixel comes from “between” two pixels?y’A: Interpolate color value from neighbors– nearest neighbor, bilinear, Gaussian, bicubic– Check out interp2 in MatlabForward vs. inverse warpingQ: which is better?A: usually inverse—eliminates holes• however, it requires an invertible warp function—not always possible...Morphing = Object AveragingThe 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 tHow 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 inputPQv = Q - PP + 0.5v= P + 0.5(Q – P)= 0.5P + 0.5 QP + 1.5v= P + 1.5(Q – P)= -0.5P + 1.5 Q(extrapolation)Linear Interpolation(Affine Combination):New point aP + bQ,defined only when a+b = 1So aP+bQ = aP+(1-a)QAveraging PointsP 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.What’s the averageof P and Q?Idea #1: Cross-DissolveInterpolate whole images:Imagehalfway= (1-t)*Image1+ t*image2This is called cross-dissolve in film industryBut what is the images are not aligned?Idea #2: Align, then cross-disolveAlign first, then cross-dissolve• Alignment using global warp – picture still validDog AveragingWhat 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) warpIdea #3: Local warp, then cross-dissolveMorphing procedure: for every t,1. Find the average shape (the “mean dog”☺)•local warping2. Find the average color• Cross-dissolve the warped imagesLocal (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-parametricMove control points to specify a spline warpSpline produces a smooth vector fieldWarp specification - denseHow can we specify the warp?Specify corresponding spline control points• interpolate to a complete warping functionBut we want to specify only a few points, not a gridWarp specification - sparseHow 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 Mesh1. Input correspondences at key feature points2. Define a triangular mesh over the points• Same mesh in both images!• Now we have triangle-to-triangle correspondences3. Warp each triangle separately from source to destination• How do we warp a triangle?• 3 points = affine warp!• Just like texture mappingTriangulationsA triangulation of set of points in the plane is a partitionof 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 AlgorithmRepeat until impossible:• Select two sites.• If the edge connecting them does not intersect previous edges, keep it.“Quality” TriangulationsLet α(T) = (α1, α2,.., α3t) be the vector of angles in the triangulation T in increasing order.A triangulation T1will be “better” than T2if α(T1) > α(T2) lexicographically.The Delaunay triangulation is the “best”• Maximizes smallest
View Full Document
Unlocking...