Unformatted text preview:

Lecture 11: Structure from motionAnnouncementsReadingsEnergy minimization via graph cutsSlide Number 5Other uses of graph cutsPanoramic stitchingPanoramic stitchingPanoramic stitchingPanoramic stitchingPhotographing long scenes with multi-viewpoint panoramasToday: DriftGlobal optimizationGlobal optimizationGlobal optimizationGlobal optimizationAmbiguity in global locationSolving for camera parametersSolving for camera rotationSolving for rotationsSolving for rotations3D rotationsRevisiting stereoSolving for rotations and translationsSlide Number 25Structure from motionSlide Number 27SfM objective functionSolving structure from motionExtensions to SfMPhoto TourismPhoto TourismScene reconstructionFeature detectionFeature detectionFeature detectionFeature matchingFeature matchingImage connectivity graphIncremental structure from motionIncremental structure from motionIncremental structure from motionLecture 11: Structure from motionCS6670: Computer VisionNoah SnavelyAnnouncements• Project 2 out, due next Wednesday, October 14– Artifact due Friday, October 16• Questions?Readings• Szeliski, Chapter 7.2• My thesis, Chapter 3 http://www.cs.cornell.edu/~snavely/publications/thesis/thesis.pdfEnergy minimization via graph cutsLabels (disparities)d1d2d3edge weightOther uses of graph cutsAgarwala et al., Interactive Digital Photo Montage, SIGGRAPH 2004Other uses of graph cutsPanoramic stitching• Problem: copy every pixel in the output image from one of the input images (without blending)• Make transitions between two images seamlessPanoramic stitching• Can be posed as a labeling problem: label each pixel in the output image with one of the input imagesInput images:Output panorama:Panoramic stitching• Number of labels: k = number of input images• Objective function (in terms of labeling L)Input images:Output panorama:Panoramic stitchingInfinite cost of labeling a pixel (x,y) with image I if I doesn’t cover (x,y)Else, cost = 0Photographing long scenes with multi‐viewpoint panoramasToday: Driftcopy of first image(xn,yn)(x1,y1)– add another copy of first image at the end– this gives a constraint: yn= y1– there are a bunch of wa ys to solve this problem• add displacement of (y1–yn)/(n ‐ 1) to each image after the first• compute a global warp: y’ = y + ax• run a big optimization problem, incorporating this constr aint– best solution, but more complicated– known as “bundle adjustment”Global optimization• Minimize a global energy function:– What are the variables?• The translation tj= (xj, yj) for each image Ij– What is the objective function?• We have a set of matched features pi,j= (ui,j, vi,j)– We’ll call these tracks• For each point match (pi,j, pi,j+1): pi,j+1– pi,j= tj+1– tjI1I2I3I4p1,1p1,2p1,3p2,2p2,3p2,4p3,3p3,4p4,4p4,1trackGlobal optimizationI1I2I3I4p1,1p1,2p1,3p2,2p2,3p2,4p3,3p3,4p4,4p4,1p1,2– p1,1= t2– t1p1,3– p1,2= t3– t2p2,3– p2,2= t3– t2…v4,1– v4,4= y1– y4minimizewij= 1 if track i is visible in images j and j+10otherwiseGlobal optimizationI1I2I3I4p1,1p1,2p1,3p2,2p2,3p2,4p3,3p3,4p4,4p4,1A2m x 2n2n x 1x2m x 1bGlobal optimizationDefines a least squares problem: minimize• Solution:• Problem: there is no unique solution for ! (det = 0)• We can add a global offset to a solution and get the same errorA2m x 2n2n x 1x2m x 1bAmbiguity in global location• Each of these solutions has the same error• Called the gauge ambiguity• Solution: fix the position of one image (e.g., make the origin of the 1stimage (0,0))(0,0)(‐100,‐100)(200,‐200)Solving for camer a parametersProjection equation()1333100'0'0xxcycxyfsxfsssvsup txR+⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=Recap: a camera is described by several parameters• Translation t of the optical center from the origin of world coords• Rotation R of the image plane• focal length f, principle point (x’c, y’c), pixel size (sx, sy)• blue parameters are called “extrinsics,” red are “intrinsics”KSolving for camer a rotation• Instead of spherically warping the images and solving for translation, we can directly solve for the rotation Rjof each camer a• Can handle tilt / twistSolving for rotationsR1R2fI1I2p12= (u12, v12)p11= (u11, v11)(u11, v11, f) = p11R1p11R2p22Solving for rotationsminimize3D rotations• How many degrees of freedom are there?• How do we represent a rotation?– Rotation matrix (too many degrees of freedom)– Euler angles (e.g. yaw, pitch, and roll) –bad idea– Quaternions (4‐vector on unit sphere)• Usually involves non‐linear optimizationRevisiting stereo• How do we find the epipolar lines?• Need to calibrate the cameras (estimate relative position, orientation)pp'epipolar lineImage IImage JSolving for rotations and translations• Structure from motion (SfM)• Unlike with panoramas, we often need to solve for structure (3D point positions) as well as motion (camera parameters)p1,1p1,2p1,3Image 1Image 2Image 3x1x4x3x2x5x6x7R1,t1R2,t2R3,t3Structure from motion• Input: images with points in correspondence pi,j= (ui,j,vi,j)• Output• structure: 3D location xifor each point pi• motion: camera parameters Rj, tj• Objective function: minimize reprojection errorReconstruction (side)(top)p1,1p1,2p1,3Image 1Image 2Image 3x1x4x3x2x5x6x7R1,t1R2,t2R3,t3SfM objective function• Given point x


View Full Document
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?