Lecture 12: Structure from motionCS6670: Computer VisionNoah SnavelyLecture 13: Multi-view stereoCS6670: Computer VisionNoah SnavelyAnnouncements• Project 2 voting open later today• Final project page will be released after class• Project 3 out soon• Quiz 2 on Thursday, beginning of classReadings• Szeliski, Chapter 11.6Fundamental matrix – calibrated case0{the Essential matrixFundamental matrix – uncalibrated case0the Fundamental matrixProperties of the Fundamental Matrix• is the epipolar line associated with• is the epipolar line associated with • and • is rank 2• How many parameters does F have?7THow many parameters?• Matrix has 9 entries– -1 due to scale invariance– -1 due to rank 2 constraint• 7 parameters in total8Rectified caseRectified caseifStereo image rectification• reproject image planes onto a common• plane parallel to the line between optical centers• pixel motion is horizontal after this transformation• two homographies (3x3 transform), one for each input image reprojection C. Loop and Z. Zhang. Computing Rectifying Homographies for Stereo Vision. IEEE Conf. Computer Vision and Pattern Recognition, 1999.Rectifying homographies• Idea: compute two homographiesand such thatRectifying homographiesEstimating F• If we don’t know K1, K2, R, or t, can we estimate F?• Yes, given enough correspondencesEstimating F – 8-point algorithm• The fundamental matrix F is defined byfor any pair of matches p and q in two images.• Let p=(u,v,1)Tand q=(u’,v’,1)T,333231232221131211fffffffffFeach match gives a linear equation0''''''333231232221131211 fvfuffvfvvfuvfufvufuu8-point algorithm01´´´´´´1´´´´´´1´´´´´´333231232221131211222222222222111111111111fffffffffvuvvvvuuuvuuvuvvvvuuuvuuvuvvvvuuuvuunnnnnnnnnnnn• In reality, instead of solving , we seek unit vector f that minimizesleast eigenvector of • need at least 8-correspondences0Af2AfAA8-point algorithm• To enforce that F is rank 2, we replace F with F’ that minimizes subject to the rank constraint. 'FF• This is achieved by SVD. Let , where , let then is the solution.  VUF Σ321000000Σ0000000Σ'21 VUF Σ''8-point algorithm% Build the constraint matrixA = *x2(1,:)‘.*x1(1,:)' x2(1,:)'.*x1(2,:)' x2(1,:)' ...x2(2,:)'.*x1(1,:)' x2(2,:)'.*x1(2,:)' x2(2,:)' ...x1(1,:)' x1(2,:)' ones(npts,1) ]; [U,D,V] = svd(A);% Extract fundamental matrix from the column of V % corresponding to the smallest singular value.F = reshape(V(:,9),3,3)';% Enforce rank2 constraint [U,D,V] = svd(F);F = U*diag([D(1,1) D(2,2) 0])*V';8-point algorithm• Pros: – linear, easy to implement and fast• Cons: – minimizes an algebraic, rather than geometric error– susceptible to noise01´´´´´´1´´´´´´1´´´´´´333231232221131211222222222222111111111111fffffffffvuvvvvuuuvuuvuvvvvuuuvuuvuvvvvuuuvuunnnnnnnnnnnnProblem with 8-point algorithm~10000~10000~10000 ~10000~100~1001~100 ~100!Orders of magnitude differencebetween column of data matrix least-squares yields poor resultsNormalized 8-point algorithm(0,0)(700,500)(700,0)(0,500)(1,-1)(0,0)(1,1)(-1,1)(-1,-1)115002107002normalized least squares yields good resultsTransform image to ~[-1,1]x[-1,1]Normalized 8-point algorithmA = *x2(1,:)‘.*x1(1,:)' x2(1,:)'.*x1(2,:)' x2(1,:)' ...x2(2,:)'.*x1(1,:)' x2(2,:)'.*x1(2,:)' x2(2,:)' ...x1(1,:)' x1(2,:)' ones(npts,1) ]; [U,D,V] = svd(A);F = reshape(V(:,9),3,3)';[U,D,V] = svd(F);F = U*diag([D(1,1) D(2,2) 0])*V';% DenormaliseF = T2'*F*T1;[x1, T1] = normalise2dpts(x1);[x2, T2] = normalise2dpts(x2);Results (ground truth)Results (8-point algorithm)Results (normalized 8-point algorithm)What about more than two views?• The geometry of three views is described by a 3 x 3 x 3 tensor called the trifocal tensor• The geometry of four views is described by a 3 x 3 x 3 x 3 tensor called the quadrifocal tensor• After this it starts to get complicated…• No known closed-form solution to the general structure from motion problemQuestions?Multi-view stereoStereoMulti-view stereoMulti-view StereoCMU’s 3D RoomPoint Grey’s Bumblebee XB3Point Grey’s ProFusion 25Multi-view StereoMulti-view StereoFigures by Carlos HernandezInput: calibrated images from several viewpointsOutput: 3D object modelFua Narayanan, Rander, KanadeSeitz, Dyer1995 1997 1998Faugeras, Keriven1998Hernandez, Schmitt Pons, Keriven, Faugeras Furukawa, Ponce2004 2005 2006Goesele et al.2007Stereo: basic ideaerrordepthwidth of a pixelChoosing the stereo baselineWhat’s the optimal baseline?– Too small: large depth error– Too large: difficult search problemLarge Baseline Small Baselineall of thesepoints projectto the same pair of pixelsThe Effect of Baseline on Depth Estimationzwidth of a pixelwidth of a pixelzpixel matching scoreMultibaseline StereoBasic Approach– Choose a reference view– Use your favorite stereo algorithm BUT• replace two-view SSD with SSSD over all baselinesLimitations– Only gives a depth map (not an “object model”)– Won’t work for widely distributed views:Some Solutions• Match only nearby photos [Narayanan 98]• Use NCC instead of SSD,Ignore NCC values > threshold [Hernandez & Schmitt 03]Problem: visibilityPopular matching scores• SSD (Sum Squared Distance)• NCC (Normalized Cross Correlation)– where – what advantages might NCC have?The visibility problemInverse Visibilityknown imagesUnknown SceneWhich points are visible in which images?Known SceneForward Visibilityknown sceneVolumetric stereoScene VolumeVInput Images(Calibrated)Goal: Determine occupancy, “color” of points in VDiscrete formulation: Voxel ColoringDiscretized Scene VolumeInput Images(Calibrated)Goal: Assign RGBA values to voxels in Vphoto-consistent with imagesComplexity and computabilityDiscretized Scene VolumeN voxelsC colors3All Scenes