Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets
This work addresses point set alignment for applications requiring invariance to transformations, offering incremental improvements in robustness and efficiency.
The paper tackles the problem of aligning partially overlapping point sets by minimizing the robust point matching objective, which is reformulated as a cubic polynomial and solved using a branch-and-bound algorithm with convex envelopes. The method demonstrated better robustness against non-rigid deformation, noise, and outliers, with competitive efficiency and scalability compared to state-of-the-art approaches.
In many applications, we need algorithms which can align partially overlapping point sets and are invariant to the corresponding transformations. In this work, a method possessing such properties is realized by minimizing the objective of the robust point matching (RPM) algorithm. We first show that the RPM objective is a cubic polynomial. We then utilize the convex envelopes of trilinear and bilinear monomials to derive its lower bound function. The resulting lower bound problem has the merit that it can be efficiently solved via linear assignment and low dimensional convex quadratic programming. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently. Experimental results demonstrated better robustness of the proposed method against non-rigid deformation, positional noise and outliers in case that outliers are not mixed with inliers when compared with the state-of-the-art approaches. They also showed that it has competitive efficiency and scales well with problem size.