Lian Wei, Ma Fei, Cui Zhesen, Pan Hang
Department of Computer Science, Changzhi University, Changzhi, 046011, Shanxi, China.
Sci Rep. 2024 Dec 3;14(1):30044. doi: 10.1038/s41598-024-79744-x.
In many applications, there is a need for algorithms that can align partially overlapping point clouds while remaining invariant to corresponding transformations. This research presents a method that achieves these goals by minimizing a binary linear assignment-least squares (BLALS) energy function. First, we reformulate the BLALS problem as the minimization of a quadratic function with quadratic and linear constraints through variable substitution. By utilizing semidefinite relaxation and the convex envelope of bilinear monomials, we relax the problem to create a lower bound that can be solved using linear assignment and low-dimensional semidefinite programming. Additionally, we develop a branch-and-bound (BnB) algorithm that only branches over the transformation variable, which enhances convergence. Experimental results show that, compared to state-of-the-art approaches, the proposed method is robust against non-rigid deformation and outliers when the outliers are separate from the inliers. However, its robustness decreases when outliers are mixed with inliers. The run time of our method is relatively high due to the need to solve a semidefinite program in each iteration of the BnB algorithm.
在许多应用中，需要能够对齐部分重叠点云同时对相应变换保持不变的算法。本研究提出了一种通过最小化二元线性分配 - 最小二乘（BLALS）能量函数来实现这些目标的方法。首先，我们通过变量代换将BLALS问题重新表述为具有二次和线性约束的二次函数的最小化问题。通过利用半定松弛和双线性单项式的凸包络，我们对问题进行松弛以创建一个可以使用线性分配和低维半定规划求解的下界。此外，我们开发了一种仅在变换变量上进行分支的分支定界（BnB）算法，这增强了收敛性。实验结果表明，与现有方法相比，当离群点与内群点分离时，所提出的方法对非刚性变形和离群点具有鲁棒性。然而，当离群点与内群点混合时，其鲁棒性会降低。由于在BnB算法的每次迭代中都需要求解一个半定规划，我们方法的运行时间相对较高。
