From: Robert_T_Collins@IUS5.IUS.cs.cmu.edu Sent: Monday, October 04, 1999 8:56 AM To: Steve Seitz Cc: rcollins@cs.cmu.edu; Robert_T_Collins@IUS5.IUS.cs.cmu.edu Subject: Re: vanishing points Hi Steve. All my code was in lisp, but it should be very easy for the students to implement, depending on what exactly you want to do. Grouping an arbitrary set of lines in the image into sets that converge to a vanishing point requires a fair amount of code. If you are already given the lines that converge, and just want to compute the vanishing point, that is easier. The basic idea (for the easy part) is the following: 1) specify each line's endpoints e1 and e2 in homogeneous coordinates e1 = (x1_i , y1_i, w) e2 = (x2_i , y2_i, w) where the constant w is often taken as 1, but you may want to use something else for better numerical conditioning (more on this later). 2) compute a homogenous coordinate vector representing the line as the cross product of its two endpoints (a_i,b_i,c_i) = e1 X e2 note that this resulting vector is just the parameters of the equation a_i x + b_i y + c_i = 0 of the 2D infinite line passing through the two endpoints 3) if you only have two lines, l1 and l2, you can compute a homogeneous coordinate vector V representing their point of intersection as the cross product of these two line vectors V = l1 X l2 scaling V so that the last coordinate is 1, i.e. (Vx, Vy, 1), and you have Vx and Vy as the point in the image that is the vanishing point. It is better to leave the vanishing point as a homogeneous coordinate vector, however, because the vanishing point could be very far off the image, or even at infinity (in which case the third component of V is 0, and you get a divide by zero when you try to scale). 4) if you have n lines l1, l2, ..., ln, you can get the "best_fit" vanishing point as follows: 4a) form the 3x3 "second moment" matrix M as [ a_i*a_i a_i*b_i a_i*c_i ] M = sum [ a_i*b_i b_i*b*i b_i*c_i ] [ a_i*c_i b_i*c_i c_i*c_i ] where the sum is taken for i = 1 to n. Note that M is a symmetric matrix 4b) perform an eigendecomposition of M, using the Jacobi method, from numerical recipes in C, for example. (Jacobi method is good for finding eigenvalues of a symmetric matrix) [I can supply the Jacobi matrix code from NR in C if you like] 4c) the eigenvector associated with the smallest eigenvalue is the vanishing point vector V One word about numerical conditioning is in order. If you just use image pixel coordinates directly, the problem will be horribly poorly conditioned. There is a good paper by Hartley on this topic, title something like "In defense of the Eight-point algorithm." If your lines are spread out throughout the image, you can get approximately the kind of well-conditioned approach he mentions by doing the following. 1) translate by (-imageX/2, -imageY/2) so that (0,0) is in the center of the image [I think Hartley's conditioning method would take the center of mass of the line endpoints as the origin]. 2) Scale coordinates so that the magnitude of all image point homogeneous coordinates is roughly 1 [Hartley says how to do this exactly, in his paper]. I used to do it approximately by just setting the constant w, mentioned during the first step of this algorithm, to be equal to half the image size in pixels. So if you had a 256x256 image, then you would have w = 128. IF the image width and height aren't the same, just take the average or something, before dividing by two. --Bob