Abstract | ||
---|---|---|
This paper presents a general method, based on Galois Theory, for establishing that a problem can not be solved by a 'machine' that is capable of the standard arithmetic operations, extraction of radicals (that is, m-th roots for any m), as well as extraction of roots of polynomials of degree smaller than n, but no other numerical operations.The method is applied to two well known structure from motion problems: five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial [6], and L-2-optimal two-view triangulation, which can be realized by solving a sixth degree polynomial [3]. It is shown that both these solutions are optimal in the sense that an exact solution intrinsically requires the solution of a polynomial of the given degree (10 or 6 respectively), and cannot be solved by extracting roots of polynomials of any lesser degree. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1109/CVPR.2007.383089 | 2007 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOLS 1-8 |
Keywords | Field | DocType |
computer vision,singular value decomposition,polynomials,structure from motion,computer science,arithmetic,galois theory,degree polynomial,visualization,motion compensation,exact solution,galois fields | Structure from motion,Singular value decomposition,Discrete mathematics,Finite field,Polynomial,Separable polynomial,Degree of a polynomial,Triangulation (social science),Galois theory,Mathematics | Conference |
Volume | Issue | ISSN |
2007 | 1 | 1063-6919 |
Citations | PageRank | References |
7 | 0.89 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Nistér | 1 | 2265 | 118.02 |
Richard I. Hartley | 2 | 9809 | 986.81 |
Henrik Stewenius | 3 | 2777 | 165.83 |