The Non-Tightness of a Convex Relaxation to Rotation Recovery.

Area of Science:

• Computer Vision
• Robotics
• Optimization Theory

Background:

• The Perspective-n-Point (PNP) problem is crucial for determining camera pose (rotation and translation) in 3D computer vision.
• Semidefinite programming (SDP) with polynomial sum-of-squares (SOS) relaxations, particularly the Lasserre Hierarchy, is a standard approach for solving PNP.
• The tightness of these convex relaxations is critical for accurate solutions.

Purpose of the Study:

• To investigate the theoretical limitations of polynomial SOS relaxations for the PNP problem.
• To demonstrate cases where the Lasserre Hierarchy provides a non-tight convex relaxation for PNP.
• To provide practical insights for practitioners using these optimization techniques.

Main Methods:

• Utilizing polynomial optimization and convex relaxation theory.
• Applying concepts from real algebraic geometry.
• Leveraging Matlab optimization toolboxes for experimental validation.
• Analyzing the Lasserre Hierarchy at second and third levels for PNP instances.

Main Results:

• Demonstrated that polynomials relevant to PNP can be non-negative but not sum-of-squares (SOS).
• Provided a concrete example where the second and third levels of the Lasserre Hierarchy yield a non-tight relaxation for PNP.
• Empirically showed that increasing the Lasserre Hierarchy level reduces the failure probability.

Conclusions:

• The commonly used SOS relaxation approach for PNP is not guaranteed to be tight and can fail.
• Practitioners should be aware of the potential failure modes of this method.
• Higher levels of the Lasserre Hierarchy offer improved robustness for PNP camera pose estimation.