This paper tackles the resolution of the Relative Pose problem with optimality guarantees by stating it as an optimization problem over the set of essential matrices that minimizes the squared epipolar error. We relax this non-convex problem with its Shor’s relaxation, a convex program that can be solved by off-the-shelf tools. We follow the empirical observation that redundant but independent constraints tighten the relaxation. For that, we leverage equivalent definitions of the set of essential matrices based on the translation vectors between the cameras. Overconstrained characterizations of the set of essential matrices are derived by the combination of these definitions. Through extensive experiments on synthetic and real data, our proposal is empirically proved to remain tight and to require only 7 milliseconds to be solved even for the overconstrained formulations, finding the optimal solution under a wide variety of configurations, including highly noisy data and outliers. The solver cannot certify the solution only in very extreme cases, e.g.noise 100 pix and number of pair-wise correspondences under 15. The proposal is thus faster than other overconstrained formulations while being faster than the minimal ones, making it suitable for real-world applications that require optimality certification.
