Transcript PresentationPackage - Center For Machine Perception (Cmp)

MAKING MINIMAL SOLVERS FAST
Zuzana Kukelova, Martin Bujnak, Tomas Pajdla
Center for Machine Perception
Department of Cybernetics, Faculty of Electrical Engineering
Czech Technical University in Prague
Motivation
2/24
Robotics
Placeholder text
Recognition &
Tracking
Placeholder text
Augmented reality
3D Reconstruction
Motivation
3/24
Camera geometry problems - calibration, relative/absolute pose estimation
Systems of polynomial equations
x1
R,t
x2
Camera geometry problems
Properties
Conclusion
 all “non-degenerate” instances
of the problem result in systems
of equations of the same form consisting of the same
polynomials and differing only
in coefficients
4/24
Requirements
 Contaminated input
measurements => problems
have to be solved for many
different inputs (RANSAC)
 High or even real-time
performance
Solve many instances of the same problem, of the same system of
polynomial equations only with different coefficients, very fast
Complicated systems
5/24
5-point relative pose problem
f 1 = 0:058x + 0:331y ¡ 0:671z + 0:698y2 ¡ 0:813z2 ¡ 0:057xy ¡ 0:036xz +
0:653yz + 0:534x 3 ¡ 0:167y3 ¡ 0:323z3 + 0:633xyz ¡ 0:282x 2 y + 0:770x 2 z ¡
0:974xy2 ¡ 0:146xz2 + 0:584y2 z + 0:239yz2 ¡ 0:170 + 0:593x 2
f 2 = 4:68x + 6:62y + 2:25z + 1:81 + 6:68y2 ¡ 0:806z2 + 12:6xy + 4:03xz +
6:99yz + 1:01x 3 + 2:04y3 ¡ 0:873z3 + 6:13xyz + 5:53x 2 y + 1:94x 2 z + 6:95xy2 ¡
1:13xz2 + 4:27y2 z ¡ 0:130yz2 + 4:53x 2
f 3 = 0:866x + 2:28y + 3:10z + 3:50y2 + 3:04z2 + 4:15xy + 6:07xz + 8:09yz ¡
0:076x 3 + 1:34y3 + 0:497z3 + 8:03xyz + 3:05x 2 y + 1:88x 2 z + 4:69xy2 + 3:40xz2 +
5:24y2 z + 4:21yz2 + 0:402 + 0:199x 2
: ::
f 10 = 5:35x + 4:46y + 3:06z + 3:85y2 + 1:48 + 2:57z2 + 9:21xy + 8:05xz +
7:16yz + 1:41x 3 + 0:991y3 + 1:09z3 + 8:06xyz + 4:06x 2 y + 4:06x 2 z + 3:83xy2 +
3:50xz2 + 3:68y2 z + 2:60yz2 + 5:72x 2
General methods
Existing software – well known general Grőbner basis or
resultant algorithms
6/24
Specific methods
• Design special algorithms to achieve numerical robustness and
computational efficiency
• Intersection ellipse-line
• No need to use general algorithms
• Closed form solution
7/24
Specific methods
8/24
Offline phase
•
•
•
Online solver
•
•
•
Efficient solver for
solving systems of
polynomial equations
of one form
Not general but fast
This is what the user
call
•
Study the problem
Solve it in some finite
prime field
Design a specific
efficient solver
Needs to be
performed only once
Grőbner basis specific methods
Parameters identification
•
•
Elimination template
design
Number of solutions, basis
Computations in finite prime field
- fast, stable
•
Eigenvalue
computations
•
Computation of
eigenvalues and
eigenvactors of the
action matrix created
from the eliminated
template
9/24
Which polynomials
should be multiplied with
which monomials and
eliminated to obtain the
solution
G-J elimintation of the
found template
•
With concrete
coefficients
Offline phase

10/24
Offline phase & Elimination template – hard to understand and
implement
15min

Requires knowledge from algebraic geometry
25min
Automatic generator
11/24
Equations List of
unknowns
List of
known
coeffs
Offline phase
Final “online”
solver
How to make the final solver fast
12/24
Reduce the size of the
elimination template
•
The slowest part
•
•
Idea: Exchange it for
computation of roots
of a single-variable
polynomial using
Sturm-sequences
Bujnak M., Kukelova
Z., Pajdla T., Making
Minimal Solvers Fast,
CVPR 2012.
Kukelova Z., Bujnak M.,
Pajdla T., Automatic
Generator of Minimal
Problem Solvers, ECCV
2008, Marseille, France,
October 12-18, 2008.
Sparse G-J
elimintation of the
found template
Grőbner bases of the ideal
13/24
• System of input polynomial equations
• The ideal generated by f 1 ; : : : ; f m is a set I of all polynomials that can
be generated as polynomial combinations of
f 1; : : : ; f m
I = f
P
m
i= 1 f i
hi : hi 2 C [x 1 ; :::; x n ]g
where h i are arbitrary polynomials from
I
𝒇𝟏
𝑓1 ℎ1 +𝑓2 ℎ2
𝑓1 ℎ1
…
𝒇𝒎
𝒇𝟐
Grőbner bases of the ideal
14/24
• An ideal can be generated by many different sets of generators which all
share the same solutions
I
I
𝒇𝟏
𝒈𝟏
𝑓1 ℎ1 +𝑓2 ℎ2
𝑓1 ℎ1
𝒇𝟐
=
𝑔1 ℎ1 +𝑔2 ℎ2 +𝑔3 ℎ3
…
𝒇𝒎
…
𝒈𝒎
• Grőbner bases - special bases
• Useful in solving system of polynomial equations
𝒈𝟐
Grőbner bases of the ideal
Lexicographic GB

15/24
Graded Reverse Lex GB
g1 (x 1 )
q1 (x 1 ; : : : ; x n )
g2 (x 1 ; x 2 )
q2 (x 1 ; : : : ; x n )
:::
:::
gn (x 1 ; : : : ; x n )
ql (x 1 ; : : : ; x n )
Contains polynomial in one
variable

Very expensive to compute

Not feasible for computer
vision problems
Doesn’t contain a single
variable polynomial

Special multiplication matrix
– eigenvalues & eigenvectors
give solutions

Easier to compute

Used to solve CV problems

We have
1. FGLM conversion algorithm
• We have the Graded Reverse Lexicographic GB and multiplication
(action) matrix
q1 (x 1 ; : : : ; x n )
q2 (x 1 ; : : : ; x n )
:::
Solution
We want
ql (x 1 ; : : : ; x n )
• We want the variable polynomial from the Lexicographic GB
g1 (x 1 )
• Well known FGLM algorithm for converting grevlex GB to Lexicographic
GB
• Needs polynomial division
• Doesn’t bring a speed up over eigenvalue computations
16/24
Trick
• Replace time consuming polynomial division performed in standard FGLM
algorithm with efficient matrix-vector multiplication using the action matrix
Algorithm
17/24
• New Matrix FGLM algorithm
• To obtain a single variable polynomial for a system with 𝑠 solutions
• ≤ 𝑠 matrix-vector multiplications
• Solve system of 𝑠 linear equations in 𝑠 unknowns
• Solve single variable polynomial using efficient Sturm-sequences
Positives
New Matrix FGLM algorithm
• Significant speedup over the eigenvalue computation
• Only feasible solutions – positive feasible focal lengths, depths or radial
distortion coefficients
Solution
We want
We have
2. Characteristic polynomial method
• We have a multiplication (action) matrix 𝑀𝑥 for multiplying with some
variable 𝑥
• Eigenvalues of this action matrix give solutions to 𝑥
• We want a single variable polynomial
g (x)
• Characteristic polynomial of the action matrix
• Krylov’s method
• Faddeev-Leverrier method
• Danilevsky method
18/24
Faddeev
• Faddeev-Leverrier method
• Well-known method, compute traces of matrices
• Suffers from a large numerical instability
Krylov
• Krylov’s method
• Based on Cayley-Hamilton theorem
• Equivalent to the proposed matrix FGLM algorithm
• Computes 𝑀 𝑠 - for some matrices may be unstable
Solution
2. Characteristic polynomial method
• Danilevsky method
• Transforms input matrix to its companion matrix by s − 1 similarity
transformations
• very efficient and numerically stable
19/24
Speedup over the eigenvalue method
20/24
• 5-point relative pose problem
Nister
GB+eig
Faddeev
mFGML
Danilevsky
• 10.6μs
• 61.2μs
• 17.2μs
• 13.7μs
• 14.2μs
• Nister – SOTA “closed form solution”
• GB+eig – standard Grőbner basis solution with eigenvalue
computation
• New “single variable polynomial”solutions –
• ~5x speedup over GB+eig
• Comparable to the closed form solution
Speedup over the eigenvalue method
• 6-point focal length relative pose problem
GB+eig
mFGML
Danilevsky
• 176.3μs
• 21.3μs
• 22.6μs
• New “single variable polynomial”solutions
• ~8x speedup over GB+eig
21/24
Speedup over the eigenvalue method
22/24
• P4P+f absolute pose problem
GB+eig
Sparse GB
Faddeev
mFGML
Danilevsky
• 127.4μs
• 82.9μs
• 51.2μs
• 46.2μs
• 47.4μs
• New “single variable polynomial”solutions –
• ~3x speedup over GB+eig
Conclusion
• Many problems in computer vision and other fields require fast solvers of
systems of polynomial equations
• General methods – not feasible
• Specific solvers – not general but fast
• Automatic generator of Grőbner basis solvers
• New methods for speeding up Grőbner basis solvers
• Matrix FGLM method + Sturm sequences
• Characteristic polynomial method + Sturm sequences
• Significant speed up over existing GB solvers
23/24
http://cmp.felk.cvut.cz/minimal
THANK YOU FOR YOUR ATTENTION
24/24