Baixe o app para aproveitar ainda mais
Prévia do material em texto
Geometry of Multiple Views 2/5/2012 Geometry of Multiple Views 1 Raul Queiroz Feitosa Objetive This chapter elucidates the geometric and algebraic constraints that hold among two views 2/5/2012 Geometry of Multiple Views 2 algebraic constraints that hold among two views of the same scene. Geometry of Multiple Views Contents: � Epipolar Geometry � The Calibrated Case � The Uncalibrated Case 2/5/2012 Geometry of Multiple Views 3 � The Uncalibrated Case � Computing E and F � The 8-point Algorithm � The Luong linear method � The Luong non linear method � The Hartley method Epipolar Geometry define the epipolar plane virtual image plane virtual image plane 2/5/2012 Geometry of Multiple Views 4 epipolar lines baseline epipoles ^ ^ ^ ^ Epipolar Geometry The Epipolar Constraint The point corresponding to p on the right camera lies necessarily over the epipolar line l´ of p. ^ ^ 2/5/2012 Geometry of Multiple Views 5 ^ ^ ^ ^ ^ ^ The Calibrated Case The epipolar constraint implies that [ ] [ ] [ ] 0ˆˆˆˆ0ˆˆ0ˆˆ ==⋅⇒=×⋅⇒=′′×′⋅ ''' pp pt ppt p ERR T pOOOpO ^ ^ ^ ^ ^ 2/5/2012 Geometry of Multiple Views 6 where = (u,v,1)T is the homogeneous image coordinate vector of = (u’,v’,1)T is the homogeneous image coordinate vector of ’ t is the coordinate vector of the translation from O to O’ R is the rotation matrix relating both cameras [t×] is the skew symmetric matrix such that [t×] a = t × a [ ] [ ] [ ] 0ˆˆˆˆ0ˆˆ0ˆˆ ==⋅⇒=×⋅⇒=′′×′⋅ × ''' pp pt ppt p ERR T pOOOpO pˆ p′ˆ pˆ pˆ The Calibrated Case The epipolar constraint implies that [ ] [ ] [ ] 0ˆˆˆˆ0ˆˆ0ˆˆ ==⋅⇒=×⋅⇒=′′×′⋅ ''' pp pt ppt p ERR T pOOOpO ^ ^ 2/5/2012 Geometry of Multiple Views 7 recall that [ ] [ ] [ ] 0ˆˆˆˆ0ˆˆ0ˆˆ ==⋅⇒=×⋅⇒=′′×′⋅ × ''' pp pt ppt p ERR T pOOOpO if t =[ tx ty tz]T then [t×] = 0 -tz ty tz 0 -tx -ty tx 0 The Essential Matrix � Definition: E = [t×] R Properties: The Calibrated Case ˆˆ = 'T 2/5/2012 Geometry of Multiple Views 8 � � E ′ (ET ) is the vector that represents the epipolar line associated to the point ′ ( ) on the left (right) image. � E is singular with two equal nonzero singular values. � the eigenvector of E (E T ) associated to eigenvalue equal to zero is the coordinate vector of the epipole e ′ (e) of the left (right) camera. 0ˆˆ ='pp ET pˆpˆ pˆpˆ ^ ^ The Uncalibrated Case From the previous chapter This implies that p p p p ′′=′= ˆ and ˆ KK 2/5/2012 Geometry of Multiple Views 9 where F = K-T E K′-1 is the fundamental matrix. 0='pp FT The Uncalibrated Case The Fundamental Matrix � Definition: F = K-T E K′-1 Properties: = 'T 2/5/2012 Geometry of Multiple Views 10 � � F p ′ (FT p ) is the vector that represents the epipolar line associated to the point p′ (p) on the left (right) image. � F has rank equal to 2. � the eigenvector of F (F T ) associated to eigenvalue equal to zero is the coordinate vector of the epipole e ′ (e) of the left (right) camera (why?). 0='pp FT The Uncalibrated Case � F is defined up to a scale factor ( ) � F has rank 2 → det (F )=0 � Thus F admits seven independent parameters. � F can be parameterized this way: 0='pp FT 2/5/2012 Geometry of Multiple Views 11 � F can be parameterized this way: where e=(α,β) and e´=(α´,β´) are the epipoles. ′+′+′−′−′−′′−′ +−− −− = αααβαβββαβαβ αβ αβ badcacbd dccd baab F (eq 10.6) Forsyth Computing E and F The Eight-point Algorithm From the previous slide ( ) 010 232221 131211 = ′ ′ ⇒= v u v,u,T FFF FFF F 'pp 2/5/2012 Geometry of Multiple Views 12 since this equation is homogeneous in the coefficients of F we can set F33=1 (scale ambiguity eliminated), and use eight point correspondences ( ) 1333231 232221 FFF FFFF For exactly 8 pairs of corresponding points: Computing E and F The Eight-point Algorithm ′′′′′′ ′′′′′′ 1 111111111111111 F F vuvvvuvuvuuu vuvvvuvuvuuu 2/5/2012 Geometry of Multiple Views 13 Note that the rank 2 property of F is ignored! ⋅⋅⋅ −= ⋅⋅⋅ ′′′′′′ ⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅ ′′′′′′ 1 1 32 12 888888888888 222222222222 F F vuvvvuvuvuuu vuvvvuvuvuuu For more than 8 pairs of corresponding points, apply least square to minimize which leads to the overconstrained homogeneous system Computing E and F The Eight-point Algorithm ( )∑ = ′ p 1 i T i i pp 2F 2/5/2012 Geometry of Multiple Views 14 which leads to the overconstrained homogeneous system Note that the rank 2 property of F is ignored! 0= ⋅⋅⋅ ⋅⋅⋅ ′′′′′′ ⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅ ′′′′′′ ′′′′′′ 11 1 1 12 11 222222222222 111111111111 F F pppppppppppp vuvvvuvuvuuu vuvvvuvuvuuu vuvvvuvuvuuu =1i Step 1: Starting with F produced by the eight-point algorithm, Computing E and F The Luong linear method 2/5/2012 Geometry of Multiple Views 15 Starting with F produced by the eight-point algorithm, use least square to find the epipoles e=(α,β) and e´=(α´,β´) that minimize |F T e|2 and |F e´|2 . Recall that e (e´) is the eigenvector of F(F T ) corresponding to the zero eingenvalue. Step 2: Substitute α, β, α´ and β´ in equation 10.6 below Computing E and F The Luong linear method −− αβ baab 2/5/2012 Geometry of Multiple Views 16 This leads to a linear parameterization of the matrix F in a, b, c and d. ′+′+′−′−′−′′−′ +−− −− = αααβαβββαβαβ αβ αβ badcacbd dccd baab F Step 3 : Estimate a, b, c and d using least square by minimizing Computing E and F The Luong linear method 2/5/2012 Geometry of Multiple Views 17 Estimate a, b, c and d using least square by minimizing Recall that the parameterization of eq. 10.6 guarantees the rank-2 property! ( )∑ = ′ p 1 i T i i pp 2F Minimize Computing E and F The Luong non linear method ( ) ( )[ ]∑ ′+′p iTii pppp FF ,d,d 22 2/5/2012 Geometry of Multiple Views 18 where � denotes the (signed geometric distance between the point p and the line l, and � Fp and FTp´ are the epipolar lines associated to p and p´ . The result of the eight point algorithm is a good starting solution. ( ) ( )[ ]∑ =1i iii FF ( )lp ,d The geometric distance in this case will be given by: Computing E and F The Luong non linear method ( ) ( )( ) ( )22 2 2 ,d iiii pp pppp ′+′ ′ =′ FF F F 2/5/2012 Geometry of Multiple Views 19 where the subscript indicates the component of a vector. ( ) ( ) ( )2221,d iiii pppp ′+′=′ FFF ( ) ( )( ) ( ) ( ) ( ) ( )2221 2 2 2 2 1 2 2 ,d i T i T ii i T i T i T i i T i pp pp pp pppp FF F FF F F + ′ = + ′ =′ Thus the function to be minimized is Computing E and F The Luong non linear method 2/5/2012 Geometry of Multiple Views 20 ( ) ( ) ( ) ( ) ( )∑ ′ + + ′+′ p i ii i T i T ii 2 2 2 2 1 2 2 2 1 11 pp pppp F FFFF Step 1:Transform the image coordinates using appropriate translation and scaling operator: Computing E and F The Hartley method 2/5/2012 Geometry of Multiple Views 21 translation and scaling operator: so that they are centered at the origin and have average distance to the origin equal to . What are these transforms? ii pp T=~ ii pp ′′=′ T~ 2 Step 2: Use linear least square to compute minimizing Step 3: Computing E and F The Hartley method F ~ ( )∑ = ′ p 1 i T i i pp 2 ~ ~ ~ F 2/5/2012 Geometry of Multiple Views 22 Construct the singular value decomposition of ; assuming that S=diag (r,s,t) , where t ≤ s ≤ r, compute Step 4: Compute the final estimate T USVF = ~ ( ) Tr,s,0 V UF diag= TFTF ′= T Computing E and F 2/5/2012 Geometry of Multiple Views 23 Computing E and F Using RANSAC to deal with outliers: Determine: n=9 – the smallest number of points required k – the number of iterations required t – the Sampson distance threshold (pixels) to identify a point that fits well d – the number of nearby points required Until k iterations have occurred 2/5/2012 Geometry of Multiple Views 24 Until k iterations have occurred Draw a sample of n points from the data uniformly and at random Apply some algorithm to compute the Fundamental Matrix that best fits to that set of n points For each data point outside the sample Compute the geometric distance (slide 19) to the epipolar lines and test it against t end If there are d or more points close to the function, then there is a good fit Refit the geometric Matrix using these points end Use the best fit from this collection, using the fitting error as criterion. Next Topic Stereopsis 2/5/2012 Geometry of Multiple Views 25 Stereopsis
Compartilhar