UW-Madison CS 766 - Epipolar Geometry & Fundamental Matrix

Unformatted text preview:

Last lecture• Passive Stereo• Spacetime StereoToday• Structure from Motion: Given pixel correspondences, how to compute 3D structure and camera motion?Slides stolen from Prof Yungyu ChuangEpipolar geometry & fundamental matrixThe epipolar geometryC,C’,x,x’ and X are coplanarepipolar geometry demoThe epipolar geometryWhat if only C,C’,x are known?The epipolar geometryAll points on  project on l and l’The epipolar geometryFamily of planes  and lines l and l’ intersect at e and e’The epipolar geometryepipolar plane = plane containing baselineepipolar line = intersection of epipolar plane with imageepipolar pole= intersection of baseline with image plane = projection of projection center in other imageepipolar geometry demoThe fundamental matrix FCC’T=C’-CRpp’T)-R(p'p Two reference frames are related via the extrinsic parameters0)( pTXThe equation of the epipolar plane through X is 0)()'( pTTpRThe fundamental matrix F0)()'( pTpRSppT 000xyxzyzTTTTTTS0)()'( SppR0))('( SpRp0' Eppessential matrixThe fundamental matrix FCC’T=C’-CRpp’0' EppThe fundamental matrix F0' EppLet M and M’ be the intrinsic matrices, thenxMp1'''1xMp0)()'(11xMExM'0'1xEMM'x0' Fxxfundamental matrixThe fundamental matrix FCC’T=C’-CRpp’0' Epp0' FxxThe fundamental matrix F• The fundamental matrix is the algebraic representation of epipolar geometry• The fundamental matrix satisfies the condition that for any pair of corresponding points x↔x‘ in the two images0Fxx'T 0l'x'TF is the unique 3x3 rank 2 matrix that satisfies x’TFx=0 for all x↔x’1. Transpose: if F is fundamental matrix for (P,P’), then FTis fundamental matrix for (P’,P)2. Epipolar lines: l’=Fx & l=FTx’3. Epipoles: on all epipolar lines, thus e’TFx=0, x e’TF=0, similarly Fe=04. F has 7 d.o.f. , i.e. 3x3-1(homogeneous)-1(rank2)5. F is a correlation, projective mapping from a point x to a line l’=Fx (not a proper correlation, i.e. not invertible)The fundamental matrix FThe fundamental matrix F• It can be used for – Simplifies matching– Allows to detect wrong matchesEstimation of F — 8-point algorithm• The fundamental matrix F is defined by0Fxx'for any pair of matches x and x’ in two images.• Let x=(u,v,1)Tand x’=(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 f to minimize , least eigenvector of . 0AfAfAA8-point algorithm• To enforce that F is of rank 2, F is replaced by F‘ that minimizes subject to . 'FF0'det F• It 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: it is linear, easy to implement and fast• Cons: 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 algorithm1. Transform input by ,2. Call 8-point on to obtain3.iiTxx ˆ'i'iTxx ˆ'iixxˆ,ˆTFTFˆΤ'Fˆ0Fxx'0ˆ'ˆ1xFTTx'Fˆ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);Normalizationfunction [newpts, T] = normalise2dpts(pts)c = mean(pts(1:2,:)')'; % Centroidnewp(1,:) = pts(1,:)-c(1); % Shift origin to centroid.newp(2,:) = pts(2,:)-c(2);meandist = mean(sqrt(newp(1,:).^2 + newp(2,:).^2));scale = sqrt(2)/meandist;T = [scale 0 -scale*c(1)0 scale -scale*c(2)0 0 1 ];newpts = T*pts;RANSACrepeatselect minimal sample (8 matches)compute solution(s) for Fdetermine inliersuntil (#inliers,#samples)>95% or too many timescompute F based on all inliersResults (ground truth)Results (8-point algorithm)Results (normalized 8-point algorithm)From F to R, T0'1xEMM'x0' FxxFMM'EIf we know camera parameters ][TREHartley and Zisserman, Multiple View Geometry, 2ndedition, pp 259Richard Szeliski CSE 576 (Spring 2005): Computer Vision32Triangulation• Problem: Given some points in correspondenceacross two or more images (taken from calibrated cameras), {(uj,vj)}, compute the 3D location XRichard Szeliski CSE 576 (Spring 2005): Computer Vision33Triangulation• Method I: intersect viewing rays in 3D, minimize:• X is the unknown 3D point• Cjis the optical center of camera j• Vjis the viewing ray for pixel (uj,vj)• sjis unknown distance along Vj• Advantage: geometrically intuitiveCjVjXRichard


View Full Document

UW-Madison CS 766 - Epipolar Geometry & Fundamental Matrix

Documents in this Course
Load more
Download Epipolar Geometry & Fundamental Matrix
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 Epipolar Geometry & Fundamental Matrix 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 Epipolar Geometry & Fundamental Matrix 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?