In many applications, the demand arises for algorithms capable of aligning partially overlapping point sets while remaining invariant to the corresponding transformations. This research presents a method designed to meet such requirements through minimization of the objective function of the robust point matching (RPM) algorithm. First, we show that the RPM objective is a cubic polynomial. Then, through variable substitution, we transform the RPM objective to a quadratic function. Leveraging the convex envelope of bilinear monomials, we proceed to relax the resulting objective function, thus obtaining a lower bound problem that can be conveniently decomposed into distinct linear assignment and low-dimensional convex quadratic program components, both amenable to efficient optimization. Furthermore, a branch-and-bound (BnB) algorithm is devised, which solely branches over the transformation parameters, thereby boosting convergence rate. Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, particularly in scenarios where outliers remain distinct from inliers, when compared with prevailing state-of-the-art approaches.

本研究介绍了一种能够对部分重叠点集进行对齐的算法，具有对相应变换保持不变性的功能。通过最小化稳健点匹配（RPM）算法的目标函数，我们展示了RPM目标函数是一个三次多项式。通过变量替换，我们将RPM目标函数转化为一个二次函数。利用双线性单项式的凸包，我们进一步放松了得到的目标函数，从而得到一个便于分解为不同线性分配和低维凸二次规划组件的下界问题，两者都可以进行高效优化。此外，我们设计了一种分支定界（BnB）算法，该算法仅在变换参数上进行分支，从而提高了收敛速度。经验评估表明，与现有的最先进方法相比，所提出的方法在非刚性变形、位置噪声和异常值等方面具有更好的鲁棒性，尤其是在异常值与内点保持不同的情况下。

变量替代和线性规划用于对齐部分重叠点集