123456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789_ IBMR Review Sheet: ======================== -Jack Tumblin 4/16/02 Specify positions on a 2D Euclidean image plane by (x,y). 2D homogeneous coordinates: -points have 3 params, but only 2DOF, given by (x1,x2,x3) in a column vector -In P2 space (2D projective space), x3 is a scaling factor, not a position specifier -Convert 2D homogen. coords to 2D Euclidean coords (x,y) = (x1/x3, x2/x3). -Convert 2D Euclidean coords to 2D Homogeneous coords by putting them at the 'central image plane'; (x1,x2,x3) = (x,y,1). -A point x,y in 2D Euclidean space specifies a unique ray from the origin in the 3D Euclidean space (NOT the projective space P2!) defined by the (x1,x2,x3) values (not coordinates!) used in 2D homogeneous coordinates. -Remember that (x1,x2,x3) describes a 2D space, not 3D! Even though you can visualize x1,x2,x3 values as locations in a 3D space, they are not--only x1,x2 describe position in P2, and x3 is just a scale factor. If you choose to plot (x1,x2,x3) as 3D, then realize that each ray from the origin describes a P2 point, AND every (x1,x2,x3) point on that ray describes the SAME point in P2 and (x,y). Points and lines in P2 using Homog. coordinates; -A 'line' in homog. coords is the set of all points that satisfy ax1 + bx2 + cx3 = 0. (a,b,c are coefficients) -A 'point' on that line is written as column vector (x1,x2,x3)T -The 'line' itself is written as the column vector (a,b,c)T -If a point p is on line l, then pT.l=0 (dot product). -Given two lines l1,l2, 3D cross-product finds intersection point p: p = l1 x l2 (works even for infinity points or line(s)) -Given two points p1, p2, the line l that connects them is: l = p1 x p2 (works even for infinity points or line(s)) Cross product: (a,b,c)x(d,e,f) = |i j k| (i,j,k = unit basis vectors) |a b c| |d e f| = (i(bf-ce),j(cd-af),k(ae-bd)) -(x,y,0) = = 'Ideal Point', a point at infinity -(0,0,1) = L_inf = 'Infinity line' = the line at infinity -Two parallel lines intersect at an ideal point (x,y,0) (Example: (a,b,c)x(a,b,d) = (bd-cb),(ca-ad),(ab-ba)) = -b(c-d), a(c-d), 0 -Line (a,b,c) has 2D normal vector direction of (-b/c,a/c) -Duality: Because both lines and points are 3-vectors, for every point theorem there is a line theorem, & vice versa. 1D Projective Transformations using Homog. coordinates; -a 'side view' of 2D projective transforms--now we look at points on lines. -Cross-ratio of distances between points is always the same no matter how we transform the points. 2D Projective Transformations using Homog. coordinates; -A Homogeneous transformation H is a 3x3 matrix applied to homog. coordinate points and lines. -Convention: 'H' transforms a point x to make x': -Points: to transform point x to make x' : x' = Hx -Lines: to transform a line in the same way: L' = H^-T L or equivalently, L' = L^T H^-1 -Point Conics: transform C to make C' : C' = H^-T C H^-1 -Line Conics: transform C* to make C*' : C*' = H C* H^T -The projective transformation drowns in jargon; broken into three pieces, H = H_S H_A H_P. H_S,H_A are purely planar manipulations; they have no effect on x3, while H_P is purely projective, and ONLY affects x3. --H_S ==Similarity Trans.(4DOF): 2D trans., rot., uniform scale. --H_A ==Affine Trans. (2DDF): non-uniform scale at angle theta --H_P ==Projective Trans.(2DOF): 3D rot (changes x3 values) Undoing H: VANISHING POINT METHOD I: -Define matrix H by: World_space*H = image_space -Given the image of a 'ground-plane', find 2 parallel line pairs at different angles. -Find their vanishing points--their intersections in image space; -Find the horizon line Lh that connects these two points in image space; -Note that the horizon line in image space l_h is the result of transforming the Infinity line L_inf from world space: L_h = H^-T L_inf -If we ignore all the but H_P part of H (that is, assume H_S, H_A are the identity matrix) or in CV jargon 'find H up to an affinity', then we can write H_P from the L_h components: H_P = [ 1 0 0 ] [ 0 1 0 ] [l_h1 l_h2 l_h3] Undoing H: VANISHING POINT METHOD II: -Same as method 1, but find the 2 vanishing points using cross-ratio. Find 2 different non-parallel lines in world space, and choose 3 points a,b and c on each line whose world-space distance ratios are known (e.g. a-to-b / b-to-c). Consider those lines in 1D homog. world space; their positions are a=(0,1) b=[a-to-b,1] c=[b-to-c,1], and vanishing point is d=[1,0] (a 1D 'ideal point' at infinity). Compute their cross ratio. Next, find the same 2 sets of three collinear points a',b',c' in image space. To find a vanishing point on a line, just find the d' on that line whose cross-ratio matches its world-space value. Find both image-space vanishing points, and construct the line lh that connects them. Then the H_P that converted world space to image space is given in 'Vanishing Point Method I' above. Conics in 2D homog. coordinates; (WHY? projected conic = another conic) ===Point conic C : -all points X = (x1,x2,x3) on a conic curve will satisfy X^T C x = 0, where C is the 3x3 matrix C = [ a b/2 d/2] [b/2 c e/2] [d/2 3/2 f ] -all conic curves in P2 have only FIVE DOF; homog. scaling is ignored. -To find a point conic matrix C from 5 points: -write C as a column vector c = [a b c d e f]^T -write matrix P from a stack of 5 row vectors containing [x^2 xy y^2 x y 1] or if you have homog. coords, stack up [(x1/x3)^2 (x1x2/x3^2 (x2/x3)^2 x1/x3 x2/x3 x3] -Solve Pc=0 (Use SVD; find input nullspace; answer is the column of V (!not V^T!) whose singular value is zero.) -Tangents: to find a line l that is tangent to a point conic at point X, l = Cx -Circles: --A circle of radius r at the origin: x^2 + y^2 - r^2 = 0, so the point conic matrix is: Cc =[1 0 0 ] It is always invertible. [0 1 0 ] [0 0 -r^2] --You can offset point x by xc,yc using this translation matrix M = [1 0 xc] . To offset a point conic, use C'= M^T C M [0 1 yc] [0 0 1 ] -Intersection of conic C and line L: Intersection point(s) xa, xb will have corresponding tangent lines: C xa = la, C xb = lb. intersection of line L and la,lb will be points xa,xb, so xa = L cross (C xa), which becomes a quadratic ===Line Conic C* or 'Conic Envelopes': -A 'point conic' C is defined by points on the curve: x^TCx=0. -A 'line conic' C* is defined by it's tangent lines: L^T C L = 0. -Every point conic has a corresponding line conic. -If a line conic (or point conic) is full rank, then C* = C^-1 -all lines L = (l1,l2,l3) tangent to a conic curve will satisfy L C* L = 0 -Just like point conics, C* is symmetric 3x3 matrix, 6 free variables - but only 5DOF because homog. scaling is ignored. -To find a line conic matrix C* from 5 lines, -write C as a column vector c* = [a b c d e f]^T -Find the homog. coords for the 5 lines L=(l1,l2,l3) (don't know l3? then write the line using x,y coords: ax + by +1 = 0 and then use l1=a,l2=b,l3=1. ) -write matrix Q from a stack of 5 row vectors, one per line. if you only know a,b values for the line, write: [a^2 ab b^2 a b 1] But if you have homog. coords for the lines, stack up [(l1/l3)^2 (l1l2/l3^2 (l2/l3)^2 l1/l3 l2/l3 l3] -Solve Qc*=0 (Use SVD; find input nullspace; answer is the column of V (!not V^T!) whose singular value is zero.) -Tangents: to find a point x that is tangent to a line conic at line L, x = C* L Conic Weirdness: -Two 'circular points' I,J are imaginary points at infinity, at the two (complex) axes of the 2D image plane: I=(1,i,0) J=(1,-i,0) -The SVD Summary: -Accepts ANY input matrix A; A = MxN, (rows x columns) (Many implementations require M>=N; if MN, S has some zero rows; Msmall (top->bottom). If not, you can rearrange 'til they are: swap cols (i,j) in U, rows (i,j) in V. SVD Review: -Think of matrix columns(rows) as vectors, as new 'coordinate axes' (that might NOT be perpendicular to each other, and might even be pointing in the same direction (degenerate)). -Matrix multiply is a 'change of coordinate axes' for vectors. -'Orthogonal vectors' are perpendicular to each other: x^T y=0 (note lines and points are orthogonal in P^2) -'Orthonormal vectors' are orthogonal & unit length: X^T X=1, Y^T Y=1 -'Orthogonal matrix': all column (row) vector pairs are orthogonal, -'Orthonormal matrix': all column (row) vector pairs are orthonormal. -Let Ax=b always mean that: A is an MxN matrix A, (postmultiplied by x to make b, where) x is an Nx1 column vector in an N-dimensional 'input space', b is an Mx1 column vector in an M-dimensional 'output space'. -Think of A as a mapping that links input space to output space by doing a series of dot products. Each column of A is a 'coordinate axis'. -SVD decomposes A into 3 matrices:A=USV^T. SVD is great because it gives you orthonormal basis functions for BOTH the input space (in the V matrix) AND the output space (in the U matrix), and then gives you a single scale factor (the 'singular values' in S matrix) that links each input 'axis' to just one output 'axis'. -Input 'Null Space': Matrix A may map SOME of the N input-space dimensions to zero in the M output dimensions. Null space== all x values that satisfy Ax=0. --SVD finds this input null space: matrix V columns are orthonormal basis vectors for input space. If the corresponding singular value is zero, it's a NULL space vector, else non-null. -Output 'Null Space': The M output-space dimensions may be more than the dimensions spanned by computing Ax (this is ALWAYS true if input dimensions N < output dimensions M). --SVD finds this output null space: matrix U columns are orthonormal basis vectors for output space. If the corresponding singular value is zero, it's a NULL space vector, else non-null. -'Condition': the set of all x vectors with unit length (x^Tx=1) forms an N-dimensional unit sphere in the 'input space'. Use Ax=b to computes an output-space ellipsoid. If we have the SVD of A, we know the shape of that ellipsoid; its major/minor axes are given by the columns of U (the output-space basis vectors) and the ellipsoid lengths are given by the singular values If the ellipsoid has any zero- or near-zero-sized axes (due to noise), then matrix A isn't really 'full rank'--it is almost singular. Put more formally, A is 'ill conditioned' it has a large 'Condition Number' = max(s)/min(s).