用于鲁棒点匹配的分解全局优化方法：低维分支策略

《Image and Vision Computing》：Decomposed global optimization for robust point matching with low-dimensional branching

　　**魏连|崔哲森|马飞|潘航|左王梦|张建梅**
**山西长治大学计算机科学系，046011**

**摘要**
在任意变换和部分重叠的情况下，点集对齐仍然是一个基本挑战。本文提出了RPM-BP（基于双线性规划的鲁棒点匹配）这一新颖的确定性全局优化框架，用于解决RPM问题。我们发现，通过策略性的变量替换，可以将原始的三次RPM目标简化为更易处理的双线性-线性形式。利用紧凸包和回代方法，我们推导出一个二次-线性下界估计器，将优化问题分解为一个标准的线性分配问题（LAP）和一个低维凸二次规划（CQP）。这种简化被嵌入到一个分支定界（BnB）算法中，该算法仅在变换空间内进行分支，有效地剪除了次优区域。在2D和3D数据集（例如3DMatch）上的实验结果表明，RPM-BP通常比传统的全局求解器快一到两个数量级。值得注意的是，在特征贫乏和非刚性场景下，它的性能优于现有的深度学习方法。通过确保全局最优性并具有高计算效率，RPM-BP为机器人技术和自主导航等安全关键应用提供了可靠的解决方案。

**引言**
点集配准，即将两个点集对齐到统一坐标系中的过程，是计算机视觉、机器人技术和增强现实中的基本任务。传统的算法（如迭代最近点（ICP）算法）对初始对齐非常敏感，并且经常陷入局部最小值，尤其是在处理显著的异常值或部分重叠时。这一根本限制凸显了需要能够可靠收敛到正确解的全局最优算法的必要性。
分支定界（BnB）框架已成为实现全局最优性的强大工具。许多现有工作应用BnB来解决寻找最优对应关系P={pij}和变换T(?|θ)的耦合问题，这通常被表述为以下混合线性分配-最小二乘问题：
**minP,θE(P,θ) = ∑i,j pij∥yj?T(xi|θ)∥2**
其中xi和yj分别表示源集和目标集中的点，pij∈{0,1}是表示对应关系的二进制变量，θ参数化了空间变换。早期尝试[1]通过在P或θ的空间中分支来解决问题，但由于搜索空间庞大且边界方案效率低下而效果不佳。后续研究主要分为两种策略：

(i) **仅对应关系方法**：这些方法消除了变换变量θ，将方程(1)简化为仅涉及对应关系的问题。虽然这可以揭示适合BnB优化的低秩凹结构[2]，[3]，但代价是初期方法要么局限于子集对齐[2]，要么缺乏变换不变性[3]。后续工作[4]、[5]成功恢复了变换不变性，但无法克服这种方法的核心限制：在对应变量的高维投影空间中分支。这种大的搜索空间导致收敛速度慢，使得这些方法不适用于较大规模的问题。

(ii) **变换空间方法**：这种更有前景的策略保留了变换参数θ，并在维度较低的变换参数空间内进行分支。一个代表性的方法是[6]，它将方程(1)视为三次多项式，并使用三线性松弛来推导下界。虽然这种方法在处理部分重叠和保持不变性方面有效，但需要复杂的函数重构以确保三线性单项式中的一个变量包含原点在其范围内。
尽管像[6]这样的最新求解器也从减少的分支空间中受益，但它们仍然受到三线性松弛中固有的原点依赖性约束的阻碍。在本文中，我们引入了一种分层松弛策略，从根本上规避了这些要求。通过将三次RPM目标简化为更易处理的双线性-线性形式，我们推导出一个紧致的二次-线性下界估计器，提供了更清晰的优化框架和更高的剪枝效率，而无需先前三线性方法所需的特殊重构。

**本文的主要贡献总结如下：**
(i) **双线性-线性重构**：我们发现，通过新颖的变量替换，可以将复杂的三次RPM目标转换为更易处理的双线性-线性形式。这消除了三线性方法所需的复杂目标重构，显著简化了优化框架。
(ii) **高效确定性求解器**：我们证明了下界优化的高效率。它将问题分解为两个行为良好的子问题：一个用于确定对应关系的经典线性分配问题（LAP）和一个用于更新变换的低维凸二次规划（CQP）。这两个子问题都可以以最小的计算开销求得全局最优解。
(iii) **极端场景下的鲁棒性**：通过广泛的2D和3D基准测试，我们证明RPM-BP在特征贫乏和非刚性变形环境中始终优于现有方法。我们的无训练方法为深度学习模型经常失败的安全关键应用提供了可靠且可证明的替代方案（见图1）。

**本文的其余部分组织如下。**第2节回顾了相关工作。第3节介绍了我们的下界理论框架。第4节详细描述了我们的目标函数，第5节描述了优化策略。我们在第6节和第7节分别应用该算法于2D相似性和仿射配准以及3D刚性配准。最后，我们在第8节展示了实验结果，并在第9节进行总结。

**相关工作**
关于点集配准的全面调查可以在[7]中找到。在本节中，我们回顾了与我们的工作最相关的方法，并强调了我们在技术上的偏离。为了提供清晰的概述，我们在表1中总结了现有类别的特点和主要缺点。

**局部和鲁棒优化。**迭代最近点（ICP）算法[8]及其变体[14]仍然是局部配准的主要工具。为了处理异常值，**双线性凸包线性化**
推导出一个紧凑且计算效率高的下界估计器对BnB算法的性能至关重要。我们的方法利用了双线性单项式的凸包——即最紧凑的凸下界估计器，通常称为McMcCormick包[37]。对于限制在矩形域[x?,xˉ]×[y?,yˉ]内的两个标量变量x和y，xy的凸包由两个仿射函数的最大值给出：
**max(x?y + xy? ? x?y?, xˉy + xy? ? xˉy? ≤ xy)**

**问题表述**
为了确保全局优化的可行性，我们采用空间变换的线性参数化：**T(xi|θ) = J(xi)θ**。这种表述足够通用，可以涵盖2D/3D相似性和仿射模型。为了处理部分重叠和异常值，我们施加了一个具有预定基数np的一对一匹配约束。对应矩阵P的可行集Ω定义为：
**Ω = {P ∈ {0,1}?×? | P??y ≤ 1?, 1?x?P ≤ 1?, 1?x?P??y = np}**，其中1?表示n维单位矩阵。

**分支定界优化**
本节详细介绍了我们的全局优化策略。我们首先通过双线性松弛推导出一个紧致的线性下界估计器，证明得到的子问题可以分解为两个独立可解的任务。然后我们概述了保证确定性收敛的分支和剪枝规则。

**应用1：2D相似性和仿射配准**
我们框架的一个主要优点是其处理任何可以表示为线性形式T(x|θ) = J(x)θ的变换的灵活性。2D相似性和仿射模型都遵循这种结构，允许我们直接应用该框架。对于考虑各向同性缩放、旋转和平移的2D相似性变换，参数?は以下の通りです：
**T(x|θ) = θ??θ?θ?θ?x?x? + θ?θ? = x??x?21θ**
在这个模型中，θ∈R?，其中[θ?,θ?]?是平移向量。

**应用2：3D刚性配准**
虽然我们的方法理论上支持完整的12参数3D仿射变换：**T(x|θ) = θ?θ?θ?θ?θ?θ?θ?θ?θ?x?x?x? + θ??θ?1θ?? = x???1??x???1??x???1θ**，但由于分支空间的高维度（d=12），计算复杂性显著增加。因此，对于3D场景，我们优先考虑刚性变换（6自由度），这是点云配准中最常见的要求。

**实验和结果**
在本节中，我们通过广泛的2D和3D配准任务评估了所提出的RPM-BP算法的性能。该算法在MATLAB R2023b中实现，并在配备Intel Core i7-8700 CPU（3.2 GHz）和32 GB RAM的工作站上执行。
配准准确性通过变换后的源内点与其真实目标对应点之间的均方根误差（RMSE）来量化。为了在理论全局最优性和实际可行性之间保持平衡……

**结论**
在本文中，我们介绍了RPM-BP，这是一种基于新颖双线性松弛的鲁棒点匹配的确定性全局优化框架。通过将耦合的RPM目标重构为双线性-线性结构，我们为分支定界（BnB）搜索推导出了一个更紧且计算效率更高的下界。我们的分析证实，这种重构显著提高了剪枝率，实现了全局最优解，而不会产生典型的指数级复杂性。

**作者贡献声明**
魏连：撰写——原始草稿。崔哲森：数据整理。马飞：研究。潘航：项目管理。左王梦：验证。张建梅：撰写——审稿与编辑。

**利益冲突声明**
作者声明他们没有已知的利益冲突或个人关系可能影响本文报告的工作。

**致谢**
本工作得到了山西省自然科学基金（编号202403021221231、202303021222271）、长治市智能人机协同操作重点实验室（编号2024sy008）、长治市基本研究计划（编号JC202401）和山西省教育厅（编号2024L351）的支持。作者还感谢山西重型设备流体动力部件与系统重点实验室提供的支持。