Convex Global 3D Registration With Lagrangian Duality

Jesus Briales, Javier Gonzalez-Jimenez; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 4960-4969

The registration of 3D models by a Euclidean transformation is a fundamental task at the core of many application in computer vision. This problem is non-convex due to the presence of rotational constraints, making traditional local optimization methods prone to getting stuck in local minima. This paper addresses finding the globally optimal transformation in various 3D registration problems by a unified formulation that integrates common geometric registration modalities (namely point-to-point, point-to-line and point-to-plane). This formulation renders the optimization problem independent of both the number and nature of the correspondences. The main novelty of our proposal is the introduction of a strengthened Lagrangian dual relaxation for this problem, which surpasses previous similar approaches [32] in effectiveness. In fact, even though with no theoretical guarantees, exhaustive empirical evaluation in both synthetic and real experiments always resulted on a tight relaxation that allowed to recover a guaranteed globally optimal solution by exploiting duality theory. Thus, our approach allows for effectively solving the 3D registration with global optimality guarantees while running at a fraction of the time for the state-of-the-art alternative [34], based on a more computationally intensive Branch and Bound method. [32] C. Olsson and A. Eriksson, "Solving Quadratically Constrained Geometrical Problems using Lagrangian Duality," in Proc. 19th Int. Conf. Pattern Recognition (ICPR2008), pp. 1-5. [34] C. Olsson, F. Kahl, and M. Oskarsson. "Branch-and-Bound Methods for Euclidean Registration Problems," in IEEE Trans. Pattern Anal. Mach. Intell., 31(5):783-794, 2009.