Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets
<|reference_start|>Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets: 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.<|reference_end|>
@article{lian2024variable,
    title={Variable Substitution and Bilinear Programming for Aligning Partially
  Overlapping Point Sets},
    author={Wei Lian, Zhesen Cui, Fei Ma, Hang Pan, Wangmeng Zuo},
    journal={arXiv preprint arXiv:2405.08589},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.08589},
    primaryClass={cs.CV}
}