Buscar

The Geometry of Multiple Views

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 25 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 25 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 25 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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

Outros materiais