跳转至

Certifiably Optimal Anisotropic Rotation Averaging

会议: ICCV 2025
arXiv: 2503.07353
代码: 无
领域: 3D视觉
关键词: rotation averaging, anisotropic optimization, semidefinite programming, convex relaxation, structure from motion

一句话总结

提出了一种新的SDP松弛方法，通过强制解落在SO(3)的凸包conv(SO(3))内，首次实现了各向异性代价下的可证明全局最优旋转平均，解决了传统O(3)松弛在各向异性场景下完全失效的问题。

背景与动机

旋转平均（Rotation Averaging）是SfM和SLAM中的核心子问题：给定一组相机对之间的相对旋转测量，估计所有相机的绝对朝向。现有的可证明最优方法几乎都聚焦于各向同性（isotropic）的弦距离（chordal distance），即假设每个相对旋转测量在所有方向上的不确定性相同。

但现实中，两视图相对位姿估计的不确定性通常是高度各向异性的——例如平面内旋转通常比平面外旋转约束得更好。最近的经验结果（如Zhang et al. CVPR 2023）已表明，在局部优化中考虑各向异性可以显著提升重建质量。然而，如何在全局优化框架中处理各向异性代价，一直是个未解的难题。

核心问题

  1. 各向同性假设的局限：标准chordal distance忽略了测量的方向性不确定性，导致对高不确定性方向的测量给予了不当的权重。
  2. O(3)松弛在各向异性下失效：传统SDP松弛通过丢弃行列式约束det(R)=1，在O(3)上优化。对于各向同性代价这通常是安全的（因为最优解自然满足det=1），但对于各向异性代价，O(3)上的最优解会系统性地偏向det=-1的"反射"解，导致松弛完全无法恢复rank-3解。作者在1000个合成问题实例中发现，标准松弛没有任何一个能给出rank-3解。
  3. 如何在保持凸性的前提下加入行列式约束？——det(R)=1是非凸的，直接加入会破坏SDP的凸结构。

方法详解

整体框架

方法分三步走：将各向异性不确定性编码为加权矩阵 → 分析为什么O(3)松弛失败 → 提出基于conv(SO(3))的更强松弛。

Step 1: 各向异性代价的构造

对每对相机(i,j)，从两视图BA的Hessian矩阵 \(H_{ij}\) 出发，通过 \(M_{ij} = \frac{\text{tr}(H_{ij})}{2}I - H_{ij}\) 构造一个加权矩阵。目标函数从各向同性的 \(-\langle \tilde{R}_{ij}, R_j R_i^\top \rangle\) 变为各向异性的 \(-\langle M_{ij}\tilde{R}_{ij}, R_j R_i^\top \rangle\)。这个代价等价于Langevin分布的负对数似然，也近似等价于轴角空间中 \(\mathcal{N}(0, H_{ij}^{-1})\) 的高斯模型，因此有清晰的统计学解释。

Step 2: O(3)松弛为何失败

关键定理（Theorem 1）：当 \(M_{ij}\) 是不定的（即最小特征值 \(\lambda_3 < 0\)，这在实际数据中77%-100%的情况下成立），在O(3)上最小化 \(-\langle M\tilde{R}, R \rangle\) 的最优解是一个行列式为-1的矩阵，其目标值比真实解 \(\tilde{R}\) 低 \(2|\lambda_3|\)。这意味着O(3)松弛会被"引诱"到错误的反射解上去。

Step 3: conv(SO(3))松弛

核心思想：虽然不能直接强制 \(R \in SO(3)\)（非凸），但可以强制 \(R \in \text{conv}(SO(3))\)（凸包，是凸的）。通过Corollary 1证明，线性目标函数在conv(SO(3))上的最小值等于在SO(3)上的最小值（因为线性函数的极值在极点取到，conv(SO(3))的极点恰好是SO(3)）。

关键设计

具体实现上，引入辅助变量 \(Q_{ij} = R_i R_j^\top\)，将 \(Q_{ij} \in SO(3)\) 的约束通过拉格朗日对偶和双共轭技术转化为 \(X_{ij} \in \text{conv}(SO(3))\) 的凸约束。最终的SDP程序（SDP-cSO(3)）为：

\[\min_{X \succeq 0} -\text{tr}(NX) \quad \text{s.t.} \quad X_{ii} = I, \quad X_{ij} \in \text{conv}(SO(3))\]

其中 \(X_{ij} \in \text{conv}(SO(3))\) 等价于一个4×4的半正定约束 \(\mathcal{A}(X_{ij}) + I \succeq 0\)（基于Saunderson等人的结果），因此整个程序仍然是一个标准SDP。

损失函数 / 训练策略

这不是学习方法，而是一个纯优化方法。使用Julia中的锥分裂求解器（SCS）通过JuMP接口求解SDP。实现细节包括： - 代价矩阵按场景中Hessian最大特征值的均值做归一化 - 绝对/相对可行性分别设为 \(10^{-5}\) 和 \(10^{-6}\) - 最大迭代50万次，实际远未用满

实验关键数据

合成实验

在2-100个相机、0%-90%数据缺失比例的设置下，SDP-cSO(3)+各向异性代价一致取得最低旋转误差，且求解速度反而更快（因为conv(SO(3))约束减少了一阶SDP求解器的振荡）。

真实数据

数据集 指标 (∑‖Ri−Ri*‖²) SDP-O(3)-iso SDP-cSO(3) (本文) 提升
LU Sphinx (70相机) 旋转误差 0.0944 0.0740 21.6%
Round Church (92相机) 旋转误差 0.1399 0.1267 9.4%
UWO (114相机) 旋转误差 0.3142 0.2274 27.6%
Tsar Nikolai I (89相机) 旋转误差 0.1170 0.0534 54.4%
King's College (77相机) 旋转误差 0.1656 0.0796 51.9%
Museum Barcelona (133相机) 旋转误差 0.2255 0.1310 41.9%
Temple Singapore (157相机) 旋转误差 0.2646 0.1696 35.9%
Kronan (131相机) 旋转误差 0.2149 0.3892 -81.1%（唯一退步）

注意：SDP-O(3)-aniso（各向异性代价+传统O(3)松弛）在所有数据集上都完全失效（rank=6-7，误差14-30），验证了论文的理论分析。

消融实验要点

  • 单独切换代价 vs 约束：合成实验中4种组合（iso/aniso × O(3)/cSO(3)）清晰表明，两个组件（各向异性代价 + conv(SO(3))约束）都是必要的，缺一不可。
  • 不定矩阵比例：真实数据中77%-100%的 \(M_{ij}\) 是不定的，印证了O(3)松弛在各向异性下的系统性失败。
  • Mahalanobis距离评估：考虑不确定性的Mahalanobis误差中，SDP-cSO(3)在大多数场景优势更为显著（如Tsar Nikolai I的Mahalanobis距离从0.687降到0.188）。

亮点 / 我学到了什么

  1. 极为漂亮的理论-实践闭环：Theorem 1精确解释了O(3)松弛为何在各向异性下失败（\(\lambda_3 < 0\) 导致det=-1解更优），而conv(SO(3))正好解决这个问题——这种"诊断问题→精确修复"的风格值得学习。
  2. conv(SO(3))的巧妙利用：通过凸包代替原始约束，在保持凸性的同时排除了错误的反射解。关键insight是线性目标在凸包上的最优值等于在原集上的最优值。
  3. 统计建模的严谨性：从两视图BA的Hessian出发，经由Laplace近似和一阶不确定性传播，得到Langevin分布形式的代价，整个推导环环相扣。
  4. 反直觉发现：更强的松弛（更多约束）反而让求解器更快收敛，因为它减少了解空间的振荡。

局限性 / 可改进方向

  1. 计算效率：虽然SDP是多项式时间的，但对于大规模场景（>150相机），conv(SO(3))约束引入的额外半正定约束使求解时间显著增加（Temple Singapore需要628秒 vs 基线的31秒）。论文自己也承认，设计高效的专用求解器是重要的未来方向。
  2. 缺乏紧性的理论保证：论文只在经验上验证了松弛的紧性（所有测试实例都得到rank-3解），但没有给出理论上松弛何时紧的显式界。
  3. 鲁棒性未涉及：论文假设没有outlier，但实际SfM中异常的相对旋转很常见。如何将各向异性代价与鲁棒损失结合是值得探索的方向。
  4. Kronan数据集的退步：在该数据集上各向异性方法反而更差，论文仅归因为"单次噪声实例的随机性"，但可能暗示着模型的某些局限。

与相关工作的对比

  • vs Zhang et al. (CVPR 2023)：提出了各向异性代价用于局部优化，但无法保证全局最优。本文将其推广到可证明最优的全局优化框架。
  • vs Barfoot et al. / Holmes et al.：基于Cayley映射的各向异性SDP松弛，需要引入大量冗余约束来获得"还算紧"的松弛。本文分析认为其问题同样在于仅强制O(3)成员资格。
  • vs Dellaert et al. (ECCV 2020, Shonan)：Riemannian staircase方法在各向同性下非常高效，但其推广到各向异性并不直接（因为严重依赖O(d)的性质，不足以保证SO(3)成员资格）。
  • vs Eriksson et al. (TPAMI 2021)：给出了各向同性下松弛紧性的理论界（依赖图的代数连通性），本文的各向异性情况更复杂，理论界尚待建立。

与我的研究方向的关联

本文是纯几何优化方向的工作，与深度学习方法的研究范式不同。但其核心思想——将不确定性显式建模到优化目标中——对任何涉及位姿估计的下游任务都有启发。例如，在学习型位姿估计或可微渲染框架中，如果能预测旋转的各向异性不确定性并在loss中对应加权，可能会提升精度。此外，conv(SO(3))约束的SDP表示可能在需要旋转正则化的神经网络方法中找到应用。

评分

  • 新颖性: ⭐⭐⭐⭐ — conv(SO(3))松弛解决O(3)在各向异性下失效的问题，理论分析优雅且新颖
  • 实验充分度: ⭐⭐⭐⭐ — 合成+11个真实SfM数据集，消融全面，但缺少与局部优化方法的直接对比
  • 写作质量: ⭐⭐⭐⭐⭐ — 数学推导严谨清晰，从问题动机到定理再到算法的逻辑链条堪称教科书级别
  • 对我的价值: ⭐⭐ — 与我当前的研究方向关联较弱，但"不确定性→代价加权"的思路有迁移价值