Using galois theory to prove structure from motion algorithms are optimal

David Nistér; Richard Hartley; Henrik Stewénius

doi:10.1109/CVPR.2007.383089

Using galois theory to prove structure from motion algorithms are optimal

David Nistér^*, Richard Hartley, Henrik Stewénius

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

18 Citations (Scopus)

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₂-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.

Original language	English
Title of host publication	2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07
DOIs	https://doi.org/10.1109/CVPR.2007.383089
Publication status	Published - 2007
Event	2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07 - Minneapolis, MN, United States Duration: 17 Jun 2007 → 22 Jun 2007

Publication series

Name	Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISSN (Print)	1063-6919

Conference

Conference	2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07
Country/Territory	United States
City	Minneapolis, MN
Period	17/06/07 → 22/06/07

Access to Document

10.1109/CVPR.2007.383089

Cite this

Nistér, D., Hartley, R., & Stewénius, H. (2007). Using galois theory to prove structure from motion algorithms are optimal. In 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07 Article 4270114 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition). https://doi.org/10.1109/CVPR.2007.383089

@inproceedings{0d01d776e97c4693ada55f25fbd90190,

title = "Using galois theory to prove structure from motion algorithms are optimal",

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 L2-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.",

author = "David Nist{\'e}r and Richard Hartley and Henrik Stew{\'e}nius",

year = "2007",

doi = "10.1109/CVPR.2007.383089",

language = "English",

isbn = "1424411807",

series = "Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition",

booktitle = "2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07",

note = "2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07 ; Conference date: 17-06-2007 Through 22-06-2007",

}

Nistér, D, Hartley, R & Stewénius, H 2007, Using galois theory to prove structure from motion algorithms are optimal. in 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07., 4270114, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07, Minneapolis, MN, United States, 17/06/07. https://doi.org/10.1109/CVPR.2007.383089

Using galois theory to prove structure from motion algorithms are optimal. / Nistér, David; Hartley, Richard; Stewénius, Henrik.
2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07. 2007. 4270114 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Using galois theory to prove structure from motion algorithms are optimal

AU - Nistér, David

AU - Hartley, Richard

AU - Stewénius, Henrik

PY - 2007

Y1 - 2007

N2 - 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 L2-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.

AB - 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 L2-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.

UR - http://www.scopus.com/inward/record.url?scp=34948883499&partnerID=8YFLogxK

U2 - 10.1109/CVPR.2007.383089

DO - 10.1109/CVPR.2007.383089

M3 - Conference contribution

SN - 1424411807

SN - 9781424411801

T3 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

BT - 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07

T2 - 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR'07

Y2 - 17 June 2007 through 22 June 2007

ER -

Using galois theory to prove structure from motion algorithms are optimal

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this