The Non-Tightness of a Convex Relaxation to Rotation Recovery

We study the Perspective-n-Point (PNP) problem, which is fundamental in 3D vision, for the recovery of camera translation and rotation. A common solution applies polynomial sum-of-squares (SOS) relaxation techniques via semidefinite programming. Our main result is that the polynomials which should b...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Yuval Alfassi, Daniel Keren, Bruce Reznick
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	PNP rotation recovery convex relaxation polynomial optimization Chemical technology TP1-1185
Acceso en línea:	https://doaj.org/article/353ad83b7f274009993f941f259ee0bc
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:353ad83b7f274009993f941f259ee0bc
record_format	dspace
spelling	oai:doaj.org-article:353ad83b7f274009993f941f259ee0bc2021-11-11T19:17:56ZThe Non-Tightness of a Convex Relaxation to Rotation Recovery10.3390/s212173581424-8220https://doaj.org/article/353ad83b7f274009993f941f259ee0bc2021-11-01T00:00:00Zhttps://www.mdpi.com/1424-8220/21/21/7358https://doaj.org/toc/1424-8220We study the Perspective-n-Point (PNP) problem, which is fundamental in 3D vision, for the recovery of camera translation and rotation. A common solution applies polynomial sum-of-squares (SOS) relaxation techniques via semidefinite programming. Our main result is that the polynomials which should be optimized can be non-negative but not SOS, hence the resulting convex relaxation is not tight; specifically, we present an example of real-life configurations for which the convex relaxation in the Lasserre Hierarchy fails, in both the second and third levels. In addition to the theoretical contribution, the conclusion for practitioners is that this commonly-used approach can fail; our experiments suggest that using higher levels of the Lasserre Hierarchy reduces the probability of failure. The methods we use are mostly drawn from the area of polynomial optimization and convex relaxation; we also use some results from real algebraic geometry, as well as Matlab optimization packages for PNP.Yuval AlfassiDaniel KerenBruce ReznickMDPI AGarticlePNProtation recoveryconvex relaxationpolynomial optimizationChemical technologyTP1-1185ENSensors, Vol 21, Iss 7358, p 7358 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	PNP rotation recovery convex relaxation polynomial optimization Chemical technology TP1-1185
spellingShingle	PNP rotation recovery convex relaxation polynomial optimization Chemical technology TP1-1185 Yuval Alfassi Daniel Keren Bruce Reznick The Non-Tightness of a Convex Relaxation to Rotation Recovery
description	We study the Perspective-n-Point (PNP) problem, which is fundamental in 3D vision, for the recovery of camera translation and rotation. A common solution applies polynomial sum-of-squares (SOS) relaxation techniques via semidefinite programming. Our main result is that the polynomials which should be optimized can be non-negative but not SOS, hence the resulting convex relaxation is not tight; specifically, we present an example of real-life configurations for which the convex relaxation in the Lasserre Hierarchy fails, in both the second and third levels. In addition to the theoretical contribution, the conclusion for practitioners is that this commonly-used approach can fail; our experiments suggest that using higher levels of the Lasserre Hierarchy reduces the probability of failure. The methods we use are mostly drawn from the area of polynomial optimization and convex relaxation; we also use some results from real algebraic geometry, as well as Matlab optimization packages for PNP.
format	article
author	Yuval Alfassi Daniel Keren Bruce Reznick
author_facet	Yuval Alfassi Daniel Keren Bruce Reznick
author_sort	Yuval Alfassi
title	The Non-Tightness of a Convex Relaxation to Rotation Recovery
title_short	The Non-Tightness of a Convex Relaxation to Rotation Recovery
title_full	The Non-Tightness of a Convex Relaxation to Rotation Recovery
title_fullStr	The Non-Tightness of a Convex Relaxation to Rotation Recovery
title_full_unstemmed	The Non-Tightness of a Convex Relaxation to Rotation Recovery
title_sort	non-tightness of a convex relaxation to rotation recovery
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/353ad83b7f274009993f941f259ee0bc
work_keys_str_mv	AT yuvalalfassi thenontightnessofaconvexrelaxationtorotationrecovery AT danielkeren thenontightnessofaconvexrelaxationtorotationrecovery AT brucereznick thenontightnessofaconvexrelaxationtorotationrecovery AT yuvalalfassi nontightnessofaconvexrelaxationtorotationrecovery AT danielkeren nontightnessofaconvexrelaxationtorotationrecovery AT brucereznick nontightnessofaconvexrelaxationtorotationrecovery
_version_	1718431576235180032

The Non-Tightness of a Convex Relaxation to Rotation Recovery

Ejemplares similares