CS6670 Computer Vision Noah Snavely Lecture 11 Structure from motion part 2 Announcements Project 2 due tonight at 11 59pm Artifact due tomorrow Friday at 11 59pm Questions Final project Form your groups and submit a proposal Work on final project Final project presentations the last few classes Final report due the last day of classes Final project One person project implement a recent research paper Example one person projects Seam carving SIGGRAPH 2007 Example one person projects What does the sky tell us about the camera Lalonde et al ECCV 2008 Other ideas Will post more ideas online Look at recent ICCV CVPR ECCV SIGGRAPH papers Example two three person projects Automatic calibration of your camera s clock In roughly what year was a given photo taken Matching historical images to modern day images Matching images on news sites blogs for article matching Will post others online soon Final projects Think about your groups and project ideas Proposals will be due on Tuesday Oct 27 Scene reconstruction Feature detection Pairwise feature matching Correspondence estimation Incremental structure from motion Feature detection Detect features using SIFT Lowe IJCV 2004 Feature detection Detect features using SIFT Lowe IJCV 2004 Feature detection Detect features using SIFT Lowe IJCV 2004 Feature matching Match features between each pair of images Feature matching Refine matching using RANSAC Fischler Bolles 1987 to estimate fundamental matrices between pairs Image connectivity graph graph layout produced using the Graphviz toolkit http www graphviz org Incremental structure from motion Incremental structure from motion Incremental structure from motion Problem size Trevi Fountain collection 466 input photos 100 000 3D points very large optimization problem Photo Tourism overview Scene reconstruction Input photographs Photo Explorer Photo Explorer Can we reconstruct entire cities Gigantic matching problem 1 000 000 images 500 000 000 000 pairs Matching all of these on a 1 000 node cluster would take more than a year even if we match 10 000 every second And involves TBs of data The vast majority 99 of image pairs do not match There are better ways of finding matching images more on this later Gigantic SfM problem Largest problem size we ve seen 15 000 cameras 4 million 3D points more than 12 million parameters more than 25 million equations Huge optimization problem Requires sparse least squares techniques Building Rome in a Day St Peter s Basilica Colosseum Trevi Fountain Rome Italy Reconstructed 150 000 in 21 hours on 496 machines Dubrovnik Dubrovnik Croatia Croatia 4 619 4 619images images out outofofan aninitial initial57 845 57 845 Total Totalreconstruction reconstructiontime time 23 23hours hours Number Numberofofcores cores 352 352 Dubrovnik Dubrovnik Croatia 4 619 images out of an initial 57 845 Total reconstruction time 23 hours Number of cores 352 San Marco Square San Marco Square and environs Venice 14 079 photos out of an initial 250 000 Total reconstruction time 3 days Number of cores 496 Questions A few more preliminaries Let s revisit homogeneous coordinates What is the geometric intuition a point in the image is a ray in projective space y x y 1 0 0 0 z x sx sy s image plane Each point x y on the plane is represented by a ray sx sy s all points on the ray are equivalent x y 1 sx sy s Projective lines What does a line in the image correspond to in projective space A line is a plane of rays through origin all rays x y z satisfying ax by cz 0 in vector notation x 0 a b c y z l p A line is also represented as a homogeneous 3 vector l Point and line duality A line l is a homogeneous 3 vector It is to every point ray p on the line l p 0 l p1 l1 p2 p l2 What is the line l spanned by rays p1 and p2 l is to p1 and p2 l p1 p2 l is the plane normal What is the intersection of two lines l1 and l2 p is to l1 and l2 p l1 l2 Points and lines are dual in projective space given any formula can switch the meanings of points Ideal points and lines y z a b 0 y sx sy 0 x image plane z x image plane Ideal point point at infinity p x y 0 parallel to image plane It has infinite image coordinates Ideal line l a b 0 parallel to image plane Corresponds to a line in the image finite coordinates goes through image origin principle point Two view geometry Where do epipolar lines come from 3d point lies somewhere along r epipolar line epipolar line epipolar plane 0 projection of r Fundamental matrix epipolar line epipolar line epipolar plane projection of ray 0 This epipolar geometry is described by a special 3x3 matrix called the fundamental matrix Epipolar constraint on corresponding points The epipolar line of point p in image J is Fundamental matrix epipolar line epipolar line epipolar plane projection of ray 0 Two special points e1 and e2 the epipoles projection of one camera into the other Fundamental matrix 0 Two special points e1 and e2 the epipoles projection of one camera into the other Rectified case Images have the same orientation t parallel to image planes Where are the epipoles Epipolar geometry demo Fundamental matrix 0 Why does F exist Let s derive it Fundamental matrix calibrated case 0 intrinsics of camera 1 intrinsics of camera 2 rotation of image 2 w r t camera 1 ray through p in camera 1 s and world coordinate system ray through q in camera 2 s coordinate system Fundamental matrix calibrated case 0 and are coplanar epipolar plane can be represented as Fundamental matrix calibrated case 0 Fundamental matrix calibrated case 0 One more substitution Cross product with t can be represented as a 3x3 matrix Fundamental matrix calibrated case 0 Fundamental matrix calibrated case 0 the Essential matrix Fundamental matrix uncalibrated case 0 the Fundamental matrix Properties of the Fundamental Matrix is the epipolar line associated with T is the epipolar line associated with and is rank 2 How many parameters does F have 55