Transcript ppt - Center for Machine Perception

A Minimal Solution for Relative Pose with Unknown Focal
Length
Henrik Stewenius, David Nister, Fredrik Kahl, Frederik Schaffalitzky
Presented by Zuzana Kukelova
Center for Machine Perception
Department of Cybernetics, Faculty of Electrical Engineering
Czech Technical University in Prague
Six-point solver (Stewénius et al)
– posing the problem
 The linear equations from the epipolar constraint
miT Fmi  0 i  1,..,6
 Parameterize the fundamental matrix with three unknowns
F  xF1  yF2  zF3
 Fi – basic vectors of the null-space
 Solve for F up to scale => x = 1
Zuzana Kúkelová [email protected]
2/11
Six-point solver (Stewénius et al)
– posing the problem
 Substitute this representation of F into the rank constraint
det  F   0
 and the trace constraint
2 EE T E  trace  EE T  E  0 
2 FQF T QF  trace  FQF T Q  F  0

1 0 0 
T
where K FK  E and Q   0 1 0  , w  f 2
 0 0 w


Zuzana Kúkelová [email protected]
3/11
Six-point solver (Stewénius et al)
– posing the problem
 10 polynomial equations in 3 unknowns – y,z,w (1 cubic and 9 of
degree 5)
 10 equations can be written in a matrix form
M . X  0,
 where M is a 10x33 coefficient matrix and X is a vector of 33 monomials
Zuzana Kúkelová [email protected]
4/11
Six-point solver (Stewénius et al)
- computing the Gröbner basis
 Compute the Gröbner basis using Gröbner basis elimination
procedure
 Generate polynomials from the ideal
 Add these polynomials to the set of original polynomial equations
 Perform Gauss-Jordan elimination
 Repeat and stop when a complete Gröbner basis is obtained
 These computations (Gröbner basis elimination procedure) can be
once made in a finite prime field
p
to speed them up - offline
 The same solver (the same sequence of eliminations) can be then
applied to the original problem in
Zuzana Kúkelová [email protected]
- online
5/11
Six-point solver (Stewénius et al)
- elimination procedure
 9 equations from trace constraint and det  F  , w det  F  and w2 det  F .
Zuzana Kúkelová [email protected]
6/11
Six-point solver (Stewénius et al)
- elimination procedure
 The previous system after a Gauss-Jordan step and adding new
equations based on multiples of the previous equations.
Zuzana Kúkelová [email protected]
7/11
Six-point solver (Stewénius et al)
- elimination procedure
 The previous system after a Gauss-Jordan step and adding new
equations based on multiples of the previous equations.
Zuzana Kúkelová [email protected]
8/11
Six-point solver (Stewénius et al)
- elimination procedure
 Gauss-Jordan eliminated version of the previous system. This set of
equations is a Gröbner basis.
Zuzana Kúkelová [email protected]
9/11
Six-point solver (Stewénius et al)
- action matrix
 Construction of the 15x15 action matrix for multiplication by one of
the unknowns M z
 extracting the correct elements from the eliminated 18x33 matrix and
organizing them
Zuzana Kúkelová [email protected]
10/11
Six-point solver (Stewénius et al)
- extract solutions
 The eigenvectors of the action matrix give solutions for y, z, w
 Using back-substitution we obtain solutions for F and f
 We obtain 15 complex solutions
Zuzana Kúkelová [email protected]
11/11