Optimizing polynomial solvers for minimal geometry problems

In recent years polynomial solvers based on algebraic geometry techniques, and specifically the action matrix method, have become popular for solving minimal problems in computer vision. In this paper we develop a new method for reducing the computational time and improving numerical stability of al...

Full description

Saved in:
Bibliographic Details
Main Authors: Naroditsky, O., Daniilidis, K.
Format: Conference Proceeding
Language:English
Subjects:
Eigenvalues and eigenfunctions
Matrix decomposition
Numerical stability
Optimization
Polynomials
Vectors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years polynomial solvers based on algebraic geometry techniques, and specifically the action matrix method, have become popular for solving minimal problems in computer vision. In this paper we develop a new method for reducing the computational time and improving numerical stability of algorithms using this method. To achieve this, we propose and prove a set of algebraic conditions which allow us to reduce the size of the elimination template (polynomial coefficient matrix), which leads to faster LU or QR decomposition. Our technique is generic and has potential to improve performance of many solvers that use the action matrix method. We demonstrate the approach on specific examples, including an image stitching algorithm where computation time is halved and single precision arithmetic can be used.
ISSN:1550-5499
2380-7504
DOI:10.1109/ICCV.2011.6126341