3D VisionStereo VisionEpipolar GeometrySlide 4Slide 5Essential MatrixSlide 7Fundamental MatrixSlide 9Computing F: The Eight-point AlgorithmLocating the Epipoles from FStereo RectificationSlide 13Slide 14Slide 15Slide 16Correspondence problemCorrelation ApproachSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Feature-based ApproachSlide 26Slide 27Slide 28Advanced TopicsSlide 30Slide 31Slide 323D Reconstruction ProblemReconstruction by TriangulationReconstruction up to a Scale FactorReconstruction up to a Projective TransformationSummaryNext3D Computer Visionand Video Computing3D Vision3D Vision Topic 7 of Part 2 Stereo Vision (II)CSC I6716Spring 2004Zhigang Zhu, NAC 8/203Ahttp://www-cs.engr.ccny.cuny.edu/~zhu/VisionCourse-2004.html3D Computer Visionand Video ComputingStereo VisionStereo VisionEpipolar GeometryWhere to search correspondencesEpipolar plane, epipolar lines and epipolesEssential matrix and fundamental matrixCorrespondence ProblemCorrelation-based approachFeature-based approach 3D Reconstruction ProblemBoth intrinsic and extrinsic parameters are knownOnly intrinsic parametersNo prior knowledge of the cameras3D Computer Visionand Video ComputingEpipolar GeometryEpipolar GeometryNotationsPl =(Xl, Yl, Zl), Pr =(Xr, Yr, Zr) Vectors of the same 3-D point P, in the left and right camera coordinate systems respectivelyExtrinsic ParametersTranslation Vector T = (Or-Ol) Rotation Matrix Rpl =(xl, yl, zl), pr =(xr, yr, zr)Projections of P on the left and right image plane respectivelyFor all image points, we have zl=fl, zr=frT)R(PPlrlPplllZfrrrrZfPp plprPOlOrXlXrPlPrflfrZlYlZrYrR, T3D Computer Visionand Video ComputingEpipolar GeometryEpipolar GeometryMotivation: where to search correspondences?Epipolar PlaneA plane going through point P and the centers of projection (COPs) of the two camerasConjugated Epipolar Lines Lines where epipolar plane intersects the image planesEpipolesThe image in one camera of the COP of the otherEpipolar ConstraintCorresponding points must lie on conjugated epipolar linesplprPOlOrelerPlPrEpipolar PlaneEpipolar LinesEpipoles3D Computer Visionand Video ComputingEpipolar GeometryEpipolar GeometryMotivation: where to search correspondences?Epipolar PlaneA plane going through point P and the centers of projection (COPs) of the two camerasConjugated Epipolar Lines Lines where epipolar plane intersects the image planesEpipolesThe image in one camera of the COP of the otherEpipolar ConstraintCorresponding points must lie on conjugated epipolar linesplprPOlOrelerPlPrEpipolar PlaneEpipolar LinesEpipoles3D Computer Visionand Video ComputingEssential MatrixEssential MatrixEquation of the epipolar planeCo-planarity condition of vectors Pl, T and Pl-TEssential Matrix E = RS 3x3 matrix constructed from R and T (extrinsic only)Rank (E) = 2, two equal nonzero singular values0llPTT)(PT000xyxzyzTTTTTTS333231232221131211rrrrrrrrrRRank (R) =3Rank (S) =2T)R(PPlr0lTrEPP0lTrEpplPplllZfrrrrZfPp 3D Computer Visionand Video ComputingEssential MatrixEssential MatrixEssential Matrix E = RS A natural link between the stereo point pair and the extrinsic parameters of the stereo system One correspondence -> a linear equation of 9 entriesGiven 8 pairs of (pl, pr) -> EMapping between points and epipolar lines we are looking forGiven pl, E -> pr on the projective line in the right planeEquation represents the epipolar line of either pr (or pl) in the right (or left) image Note: pl, pr are in the camera coordinate system, not pixel coordinates that we can measure0lTrEpp3D Computer Visionand Video ComputingFundamental MatrixFundamental MatrixMapping between points and epipolar lines in the pixel coordinate systemsWith no prior knowledge on the stereo systemFrom Camera to Pixels: Matrices of intrinsic parametersQuestions: What are fx, fy, ox, oy ?How to measure pl in images?0lTrpFp1lrEMMFTl1llpMprrrpMp110000int yyxxofofM0lTrEppRank (Mint) =33D Computer Visionand Video ComputingFundamental MatrixFundamental MatrixFundamental Matrix Rank (F) = 2Encodes info on both intrinsic and extrinsic parametersEnables full reconstruction of the epipolar geometryIn pixel coordinate systems without any knowledge of the intrinsic and extrinsic parameters Linear equation of the 9 entries of F0lTrpFp1lrEMMFT01333231232221131211)1()()()()(rimrimlimlimyxfffffffffyx3D Computer Visionand Video ComputingComputing F: The Eight-point AlgorithmComputing F: The Eight-point AlgorithmInput: n point correspondences ( n >= 8)Construct homogeneous system Ax= 0 fromx = (f11,f12, ,f13, f21,f22,f23 f31,f32, f33) : entries in FEach correspondence give one equationA is a nx9 matrixObtain estimate F^ by SVD of Ax (up to a scale) is column of V corresponding to the least singular valueEnforce singularity constraint: since Rank (F) = 2Compute SVD of F^Set the smallest singular value to 0: D -> D’Correct estimate of F : Output: the estimate of the fundamental matrix, F’Similarly we can compute E given intrinsic parameters0lTrpFpTUDVA TUDVF ˆTVUDF' '3D Computer Visionand Video ComputingLocating the Epipoles from FLocating the Epipoles from FInput: Fundamental Matrix FFind the SVD of FThe epipole el is the column of V corresponding to the null singular value (as shown above)The epipole er is the column of U corresponding to the null singular value (similar treatment as for el)Output: Epipole el and erTUDVF el lies on all the epipolar lines of the left image0lTrpFp0lTreFpF is not identically zeroFor every pr0leFplprPOlOrelerPlPrEpipolar PlaneEpipolar LinesEpipoles3D Computer Visionand Video ComputingStereo RectificationStereo RectificationRectification Given a stereo pair, the intrinsic and extrinsic parameters, find the image transformation to achieve a stereo system of horizontal epipolar linesA simple algorithm: Assuming calibrated stereo camerasp’lp’rPOlOrX’rPlPrZ’lY’lY’rTX’lZ’rStereo System with Parallel Optical AxesEpipoles are at