Image Warping15-463: Computational PhotographyAlexei Efros, CMU, Fall 2007Some slides from Steve Seitzhttp://www.jeffrey-martin.comImage Warpingimage filtering: change range of imageg(x) = T(f(x))fxTfxfxTfximage warping: change domain of imageg(x) = f(T(x))Image WarpingTTffggimage filtering: change range of imageg(x) = h(T(x))image warping: change domain of imageg(x) = f(T(x))Parametric (global) warpingExamples of parametric warps:translationrotationaspectaffineperspectivecylindricalParametric (global) warpingTransformation T is a coordinate-changing machine:p’ = T(p)What does it mean that T is global?• Is the same for any point p• can be described by just a few numbers (parameters)Let’s represent T as a matrix:p’ = MpTp = (x,y) p’ = (x’,y’)⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxyxM''ScalingScaling a coordinate means multiplying each of its components by a scalarUniform scaling means this scalar is the same for all components:× 2Non-uniform scaling: different scalars per component:ScalingX × 2,Y × 0.5ScalingScaling operation:Or, in matrix form:byyaxx==''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxbayx00''scaling matrix SWhat’s inverse of S?2-D Rotationθ(x, y)(x’, y’)x’ = x cos(θ) - y sin(θ)y’ = x sin(θ) + y cos(θ)2-D Rotationx = r cos (φ)y = r sin (φ)x’ = r cos (φ + θ)y’ = r sin (φ + θ)Trig Identity…x’ = r cos(φ) cos(θ) – r sin(φ) sin(θ)y’ = r sin(φ) cos(θ) + r cos(φ) sin(θ)Substitute…x’ = x cos(θ) - y sin(θ)y’ = x sin(θ) + y cos(θ)θ(x, y)(x’, y’)φ2-D RotationThis is easy to capture in matrix form:Even though sin(θ) and cos(θ) are nonlinear functions of θ,• x’ is a linear combination of x and y• y’ is a linear combination of x and yWhat is the inverse transformation?• Rotation by –θ• For rotation matrices()()() ()⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡yxyxθθθθcossinsincos''TRR=−1R2x2 MatricesWhat types of transformations can be represented with a 2x2 matrix?2D Identity?yyxx==''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxyx1001''2D Scale around (0,0)?ysyxsxyx*'*'==⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxssyxyx00''2x2 MatricesWhat types of transformations can be represented with a 2x2 matrix?2D Rotate around (0,0)?yxyyxx*cos*sin'*sin*cos'Θ+Θ=Θ−Θ=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡ΘΘΘ−Θ=⎥⎦⎤⎢⎣⎡yxyxcossinsincos''2D Shear?yxshyyshxxyx+=+=*'*'⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxshshyxyx11''2x2 MatricesWhat types of transformations can be represented with a 2x2 matrix?2D Mirror about Y axis?yyxx=−=''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡yxyx1001''2D Mirror over (0,0)?yyxx−=−=''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−−=⎥⎦⎤⎢⎣⎡yxyx1001''2x2 MatricesWhat types of transformations can be represented with a 2x2 matrix?2D Translation?yxtyytxx+=+=''Only linear 2D transformations can be represented with a 2x2 matrixNO!All 2D Linear TransformationsLinear transformations are combinations of …•Scale,• Rotation,• Shear, and• MirrorProperties of linear transformations:• Origin maps to origin• Lines map to lines• Parallel lines remain parallel• Ratios are preserved• Closed under composition⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxdcbayx''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxlkjihgfedcbayx''Linear Transformations as Change of BasisAny linear transformation is a basis!!!• What’s the inverse transform? • How can we change from any basis to any basis?• What if the basis are orthogonal?j =(0,1)i =(1,0)pp=4i+3j = (4,3) p’=4u+3vpx’=4ux+3vxpy’=4uy+3vyv =(vx,vy)u=(ux,uy)p’pp⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=yyxxyyxxvuvuvuvu34'Homogeneous CoordinatesQ: How can we represent translation as a 3x3 matrix?yxtyytxx+=+=''Homogeneous CoordinatesHomogeneous coordinates• represent coordinates in 2 dimensions with a 3-vector⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎯⎯⎯⎯⎯→⎯⎥⎦⎤⎢⎣⎡1coords shomogeneouyxyxHomogeneous CoordinatesAdd a 3rd coordinate to every 2D point• (x, y, w) represents a point at location (x/w, y/w)• (x, y, 0) represents a point at infinity• (0, 0, 0) is not allowedConvenient coordinate system to represent many useful transformations1212(2,1,1)or (4,2,2) or (6,3,3)xyHomogeneous CoordinatesQ: How can we represent translation as a 3x3 matrix?A: Using the rightmost column:⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1001001yxttranslationTyxtyytxx+=+=''TranslationExample of translation⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡++=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡1110010011''yxyxtytxyxttyxtx= 2ty= 1Homogeneous CoordinatesBasic 2D TransformationsBasic 2D transformations as 3x3 matrices⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡ΘΘΘ−Θ=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡11000cossin0sincos1''yxyx⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110010011''yxttyxyx⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110001011''yxshshyxyxTranslateRotate Shear⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110000001''yxssyxyxScaleAffine TransformationsAffine transformations are combinations of …• Linear transformations, and• TranslationsProperties of affine transformations:• Origin does not necessarily map to origin• Lines map to lines• Parallel lines remain parallel• Ratios are preserved• Closed under composition• Models change of basis⎥⎥⎦⎤⎢⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡wyxfedcbawyx100''Projective TransformationsProjective transformations …• Affine transformations, and• Projective warpsProperties of projective transformations:• Origin does not necessarily map to origin• Lines map to lines• Parallel lines do not necessarily remain parallel• Ratios are not preserved• Closed under composition• Models change of basis⎥⎥⎦⎤⎢⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡wyxihgfedcbawyx'''Matrix CompositionTransformations can be combined by matrix multiplication⎥⎥⎦⎤⎢⎢⎣⎡⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛⎥⎥⎦⎤⎢⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡ΘΘΘ−Θ⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡wyxsysxtytxwyx10000001000cossin0sincos1001001'''p’ =
View Full Document