Last lectureTodayEpipolar geometry & fundamental matrixThe epipolar geometrySlide 5Slide 6Slide 7Slide 8Slide 9The fundamental matrix FSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Estimation of F — 8-point algorithm8-point algorithmSlide 19Slide 20Slide 21Problem with 8-point algorithmNormalized 8-point algorithmSlide 24Slide 25NormalizationRANSACResults (ground truth)Results (8-point algorithm)Results (normalized 8-point algorithm)From F to R, TTriangulationSlide 33Slide 34Structure from motionSlide 36ApplicationsSlide 38Slide 39Structure from MotionSlide 41Slide 42Example : Photo TourismFactorization methodsProblem statementSFM under orthographic projectionfactorization (Tomasi & Kanade)FactorizationMetric constraintsResultsExtensions to factorization methodsBundle adjustmentSlide 53Bundle AdjustmentLots of parameters: sparsityRobust error modelsStructure from motion: limitationsIssues in SFMTrack lifetimeSlide 61Slide 62Nonlinear lens distortionSlide 64Prior knowledge and scene constraintsSlide 66Applications of Structure from MotionJurassic parkPhotoSynthLast 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'''1xMp0)()'(11xMExM'0'1xEMM'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'TF 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 FT is 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 by 0Fxx'for any pair of matches x and x’ in two images.•Let x=(u,v,1)T and x’=(u’,v’,1)T,333231232221131211fffffffffFeach match gives a linear equation0''''''333231232221131211 fvfuffvfvvfuvfufvufuu8-point algorithm01´´´´´´1´´´´´´1´´´´´´333231232221131211222222222222111111111111fffffffffvuvvvvuuuvuuvuvvvvuuuvuuvuvvvvuuuvuunnnnnnnnnnnn•In reality, instead of solving , we seek f to minimize , least eigenvector of . 0AfAfAA8-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 matrix A = [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´´´´´´333231232221131211222222222222111111111111fffffffffvuvvvvuuuvuuvuvvvvuuuvuuvuvvvvuuuvuunnnnnnnnnnnnProblem 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ˆ0Fxx'0ˆ'ˆ1xFTTx'FˆNormalized 8-point algorithm A = [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'; % Denormalise F = T2'*F*T1;[x1, T1] = normalise2dpts(x1);[x2, T2] = normalise2dpts(x2);Normalizationfunction [newpts, T] = normalise2dpts(pts) c = mean(pts(1:2,:)')'; % Centroid newp(1,:) = pts(1,:)-c(1); % Shift origin to
View Full Document
Unlocking...