CS664 Computer Vision5. Image GeometryDan Huttenlocher2First Assignment Wells paper handout for question 1 Question 2 more open ended– Less accurate approximations• Simple box filtering doesn’t work– Anisotropic, spatially dependent3Image WarpingTTffgg Image filtering: change range of imageg(x) = T¸f(x) Image warping: change domain of imageg(x) = f(T(x))4Feature Detection in Images Filtering to provide area of support– Gaussian, bilateral, … Measures of local image difference– Edges, corners More sophisticated features are invariant to certain transformations or warps of the image– E.g., as occur when viewing direction changes5Parametric (Global) Warping Examples of parametric warps:translationrotationaffineprojectivecylindrical6Parametric (Global) Warpingp’ = T(p)  What does it mean that T is global?– Same function for any point p– Described by a few parameters, often matrixTp = (x,y)p’ = (x’,y’)⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxyxM''p’ = M*p7Scaling Scaling a coordinate means multiplying each of its components (axes) by a scalar Uniform scaling means this scalar is the same for all components:× 28 Non-uniform scaling: different scalars per component:ScalingX × 2,Y × 0.59Scaling Scaling operation: Or, in matrix form:byyaxx==''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxbayx00''scaling matrix SWhat’s inverse of S?102-D Rotationθ(x, y)(x’, y’)x’ = x cos(θ) - y sin(θ)y’ = x sin(θ) + y cos(θ)About origin112-D Rotation This 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 y Inverse transformation, rotation by –θ– For rotation matrices, det(R) = 1 and()()() ()⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡yxyxθθθθcossinsincos''TRR=−1R122x2 Transformation Matrices What types of transformations can be represented with a 2x2 matrix?2D Identity? (A rotation)yyxx==''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxyx1001''2D Scale around (0,0)?ysyxsxyx*'*'==⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxssyxyx00''132x2 Transformation Matrices What 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''142x2 Transformation Matrices What types of transformations can be represented with a 2x2 matrix?2D Mirror about Y axis?yyxx=−=''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡yxyx1001''2D Mirror over (0,0)?yyxx−=−=''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−−=⎥⎦⎤⎢⎣⎡yxyx1001''15All 2D Linear Transformations Linear transformations are combinations of …– Scale,– Rotation,– Shear, and– Mirror Properties of linear transformations:– Origin maps to origin– Lines map to lines– Parallel lines remain parallel– Ratios are preserved– Closed under composition⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxdcbayx''⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡yxlkjihgfedcbayx''16Linear Transformations as Change of Basis Any linear transformation is a basis!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'172x2 Transformation Matrices What types of transformations can be represented with a 2x2 matrix?2D Translation?yxtyytxx+=+=''Only linear 2D transformations can be represented with a 2x2 matrixNO!18Homogeneous Coordinates How can we represent translation as matrix? Homogeneous coordinates– Represent coordinates in 2 dimensions with a 3-vector⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎯⎯⎯⎯→⎯⎥⎦⎤⎢⎣⎡1coords shomogeneouyxyxyxtyytxx+=+=''19Homogeneous Coordinates Add a 3rd coordinate to every 2D point– (x, y, w) represents a point at 2D location (x/w, y/w)– (x, y, 0) represents a point at infinity– (0, 0, 0) is not allowed1212(2,1,1)or (4,2,2) or (6,3,3)xy20Homogeneous Coordinates⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1001001yxttranslationTyxtyytxx+=+='' How can we represent translation as matrix? Last column of homogeneous matrix21Translation Example of translation in homogeneous coordinates⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡++=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡1110010011''yxyxtytxyxttyxtx= 2ty= 122Homogeneous 2D Transformations Basic 2D transformations as 3x3 matrices⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡ΘΘΘ−Θ=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡11000cossin0sincos1''yxyx⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110010011''yxttyxyx⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110001011''yxshshyxyxTranslateRotate Shear⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110000001''yxssyxyxScale23Affine Transformations Affine transformations are …– Linear transformations, and– Translations Properties 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– Maps any triangle to any triangle (or parallelogram)⎥⎥⎦⎤⎢⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡wyxfedcbawyx100''24Projective Transformations Projective transformations …– Affine transformations, and– Projective warps Properties 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– Maps any quadrilateral to any quadrilateral⎥⎥⎦⎤⎢⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡wyxihgfedcbawyx'''25Matrix Composition Transformations can be combined (composed) by matrix