PaperlayerView exact revision on arXiv

Source-linked AI summary

Certifiably Optimal Anisotropic Rotation Averaging

Carl Olsson, Yaroslava Lochman, Johan Malmport, Christopher Zach

arXiv:2503.07353v2cs.CV

TL;DR

Certifiable rotation averaging with anisotropic costs remains challenging because standard relaxations may not be tight. This paper develops an anisotropic SDP and a stronger relaxation that empirically recovers global minima and yields more accurate reconstructions in most cases.

  • Problem

    For anisotropic rotation averaging, directly modifying the standard objective yields an SDP that rarely provides a tight lower bound because optimization over O(3) can violate SO(3).

    Source: §1 · p. 2

  • Method

    The paper formulates anisotropic chordal rotation averaging as a certifiably optimal SDP and strengthens the relaxation to constrain solutions to conv(SO(3)).

    Source: §1 · pp. 1–2

  • Results

    The relaxation recovered global minima on synthetic and real datasets, while anisotropic methods produced more accurate reconstructions than isotropic methods in most cases.

    Source: §1 · p. 2, §6 · p. 7

  • Takeaways & Limitations

    The work provides an entry point for further investigation of anisotropic rotation averaging.

    Source: §6 · p. 7

    The stronger SDP often increases optimization cost, and designing a dedicated efficient algorithm remains future work.

    Source: §6 · p. 8

Abstract

from arXiv · show

Rotation averaging is a key subproblem in applications of computer vision and robotics. Many methods for solving this problem exist, and there are also several theoretical results analyzing difficulty and optimality. However, one aspect that most of these have in common is a focus on the isotropic setting, where the intrinsic uncertainties in the measurements are not fully incorporated into the resulting optimization task. Recent empirical results suggest that moving to an anisotropic framework, where these uncertainties are explicitly included, can result in an improvement of solution quality. However, global optimization for rotation averaging has remained a challenge in this scenario. In this work we show how anisotropic costs can be incorporated in certifiably optimal rotation averaging. We also demonstrate how existing solvers, designed for isotropic situations, fail in the anisotropic setting. Finally, we propose a stronger relaxation and empirically show that it recovers global optima in all tested datasets and leads to more accurate reconstructions in almost all scenes.

1. Introduction

The paper extends certifiably optimal rotation averaging to anisotropic costs, arguing that uncertainty-aware optimization requires a stronger relaxation because ordinary O(3)-based relaxations are often not tight.

1. Introduction

  • Rotation averaging is challenging because rotations lie on nonlinear SO(3), and local optimization can encounter bad minima depending on measurement noise and graph algebraic connectivity.Local methods use explicit parametrizations and descent directions, which may reach a global optimum in sufficiently nice situations.Source: §1 · p. 1
  • SDP relaxations of rotation-averaging QCQPs often drop the determinant constraint, replacing SO(3) with O(3), although theory indicates the relaxation gap can vanish and yield certifiably correct solutions.An explicit bound relates this tightness to measurement noise and graph algebraic connectivity.Source: §1 · p. 1
  • Existing certifiably correct methods minimize isotropic chordal distance and ignore relative rotation uncertainties, while anisotropic chordal distance incorporates uncertainties from local two-view optimization.Prior empirical results suggest that accounting for these uncertainties can largely improve reconstruction quality.Source: §1 · p. 1
  • Directly modifying the objective for anisotropic costs rarely yields a tight SDP, because optimization over O(3) can produce solutions outside SO(3); the proposed relaxation constrains solutions to conv(SO(3)).The determinant constraint cannot be dropped when tight semidefinite relaxations are desired in this setting.Source: §1 · pp. 1–2
  • Across synthetic and real datasets, the stronger relaxation recovered global optima in all tested instances, while the anisotropic model generally produced more accurate solutions than the isotropic chordal penalty.The authors report that their formulation is the first to yield tight relaxations.Source: §1 · p. 2

2. Related Work

Related work spans rotation representations, anisotropic and alternative rotation distances, and optimization methods. The paper uses matrix representations and assumes point estimates with unimodal Gaussian observation noise.

  • The paper uses matrix representations; vectors [6, 33] and quaternions are alternatives, but unit quaternions double-cover SO(3), making distances less straightforward and requiring sign optimization.The passage notes advantages of quaternions but says a second optimization step is needed to determine appropriate signs.Source: §2 · p. 2
  • Prior work certifiably optimizes anisotropic chordal distance using Cayley-based SDP relaxations, but its relation to this formulation is unclear and it adds redundant constraints for tightness.The passage suggests the constraints may result from enforcing only O(3) membership, in light of this paper's analysis and.Source: §2 · p. 2
  • Alternative rotation distances include geodesic costs [47] and robustified distances [46], while SDP formulations handle outliers through auxiliary variables [8] [38].Robust formulations aim to make solutions less susceptible to outliers.Source: §2 · p. 2
  • Rotation averaging solvers include coordinate descent [36], primal-dual updates [28], global-coordinate/local-step methods [12], eigenvectors, and the Riemannian staircase [16].SDP relaxations can also be solved by general-purpose solvers such as; the staircase increases block-matrix dimension until finding a global optimum.Source: §2 · p. 2
  • Like most rotation-averaging work, this paper assumes point estimates and unimodal Gaussian observation noise; particle-based marginals [4] and cycle-consistency constraints [42] address perceptual aliasing.The particle-based approach provides more expressive marginals for multimodal input data.Source: §2 · p. 2

3. Certifiably Optimal Rotation Averaging

Rotation averaging estimates absolute camera orientations from relative rotations; the section develops a semidefinite relaxation whose rank-three solutions certify global optimality.

  • Rotation averaging estimates absolute camera orientations from relative rotation measurements between calibrated camera pairs.The traditional formulation accounts for measurement error using chordal distance [16] [36].Source: §3 · p. 2
  • Replacing RR⊤ with a positive semidefinite matrix X yields a convex SDP relaxation with constraints Xii = I.The original rotation objective is made linear using the constant Frobenius norm of rotation matrices and the relative-rotation structure.Source: §3 · pp. 2–3
  • A rank-three SDP solution factors as X = RR⊤ and certifies that R is globally optimal for the original non-convex QCQP.The SDP objective then equals the QCQP objective, giving zero duality gap.Source: §3 · p. 3
  • Linear objectives are important for strong relaxations because their solutions can lie at low-rank extreme points of the feasible set.Prior work reports zero duality gaps for synchronization problems under various bounded-noise regimes [38].Source: §3 · p. 3

4. Anisotropic Rotation Averaging

Because reprojection errors can be less sensitive to rotations in some directions than others, the paper propagates relative-rotation uncertainty into averaging and develops a stronger relaxation to handle the resulting anisotropic costs.

4.1. Incorporating uncertainties

  • The anisotropic objective replaces each relative estimate with a Hessian-informed weighted estimate, using Mij based on the relative-pose Hessian Hij.Mij is generally not positive semidefinite; this commonly occurs when image-based rotation estimates are more certain in one direction than others.Source: §4.1 · p. 4

4.3. A stronger convex relaxation

  • Across 1,000 synthetic anisotropic instances, SDP-CSO(3) returned rank-3 solutions in every case, while the standard relaxation never did.Figure 2 reports the comparison between the proposed relaxation and standard convex relaxations.Source: §4.2 · p. 4, Figure 2 · p. 5, §4.3 · p. 6

4.2. Global solutions: O(3) vs. SO(3)

  • For indefinite costs, the O(3) minimizer can be incorrect: its objective is −2|λ3|, whereas the SO(3) estimate has objective 0.The O(3) result explains why the standard relaxation can favor solutions with incorrect determinants.Source: §4.2 · p. 5

4.3. A stronger convex relaxation

  • The proposed relaxation constrains auxiliary rotation variables to conv(SO(3)), ruling out incorrect-determinant solutions and making it stronger than SDP-O(3)-ISO.The convex-hull constraint is equivalent to a semidefinite constraint.Source: §4.3 · p. 6

5. Experiments

Experiments compare isotropic and anisotropic objectives with and without the proposed conv(SO(3)) constraints. The proposed method generally improves real-data estimates, while synthetic tests show lower errors and faster solving with the proposed relaxation.

5. Experiments

  • The comparison includes isotropic and anisotropic objectives, each evaluated with or without the conv(SO(3)) constraints.The four methods are SDP-O(3)-ISO, SDP-O(3)-ANISO, SDP-CSO(3), and SDP-CSO(3)-ISO; the last is included for completeness in the synthetic study.Source: §5 · p. 6

5.1. Synthetic experiments

  • The proposed method consistently yields lower rotation errors, and its relaxation is faster in the synthetic setting.Tests varied camera counts from 2 to 100 and missing-data proportions up to 90%, with 100 instances per configuration pair.Source: §5.1 · pp. 6–7, Figure 3 · p. 7

5.2. Real experiments

  • SDP-CSO(3) is more accurate on all but one dataset, matches SDP-O(3)-ISO’s speed on half, and shows that the standard relaxation fails with anisotropic costs.The paper cautions that a single real-data noise realization and potentially biased SfM ground truth prevent expecting better estimates for every realization.Source: §5.2 · p. 7

6. Conclusions

The paper incorporates anisotropic costs into certifiably optimal rotation averaging and proposes an SDP relaxation that enforces conv(SO(3)); evaluation reports recovered global minima and more accurate reconstructions in most cases.

6. Conclusions

  • The proposed approach recovered global minima and produced more accurate reconstructions than isotropic methods in most cases.The evaluation covered synthetic and real datasets.Source: §6 · p. 7, Table 1 · p. 8
  • Existing solvers designed for chordal distances fail to provide sensible solutions because they ignore the determinant constraint.Source: §6 · p. 7
  • The new SDP formulation enforces conv(SO(3)) within the anisotropic rotation averaging framework.Source: §6 · p. 7
  • The stronger SDP formulation can make optimization more expensive, so designing a dedicated efficient algorithm remains an important future direction.The work focuses mainly on modeling and on shortcomings of existing relaxations while aiming to leverage standard SDP solvers.Source: §6 · p. 8

Supplementary Material · A. First-Order Uncertainty Propagation · B. Parameterization of R

The supplement derives a first-order uncertainty mapping from axis-angle perturbations to rotation matrices, then examines how alternative rotation parameterizations affect the anisotropic cost and its solutions.

A. First-Order Uncertainty Propagation

  • Laplace’s approximation treats the nonlinear least-squares Hessian as the posterior precision, up to positive scale, and first-order propagation maps axis-angle uncertainty to rotation-matrix coordinates.For small perturbations, the exponential map is approximated by I + [∆ω]×; its Jacobian induces the transformed covariance.Source: A. First-Order Uncertainty Propagation · p. 11
  • Because the Jacobian has rank 3, the covariance relation fixes 6 of 45 degrees of freedom, leaving 39 to make the covariance invertible and the maximum-likelihood objective linear in R.The linear objective is chosen to match ∆ω⊤H∆ω to first order.Source: A. First-Order Uncertainty Propagation · p. 11
  • CAS-derived relations between M and H specify the linearized cost, including M11 + M22 = H33, M11 + M33 = H22, M22 + M33 = H11, and Mij = −Hij for i ≠ j.The passages state these relations characterize the suitable matrix M.Source: A. First-Order Uncertainty Propagation · p. 11
  • Using [∆ω]× ≈ R˜R⊤ − I yields a cost equivalent to cost (9) in the main text.The supplement also states that factoring the skew-symmetric perturbation gives the same conditions on M.Source: A. First-Order Uncertainty Propagation · p. 11

B. Parameterization of R

  • Assuming R˜R⊤ ≈ I makes R and ˜R⊤ approximately commute, enabling analysis of the alternative parameterization R = e^[ω]× = e^[˜ω+∆ω]×.The supplement computes the induced two-view Hessian and first-order linear cost for this parameterization.Source: B. Parameterization of R · pp. 11–12
  • With α = 0, 1/2, or 1, anisotropic rotation averaging gives the same solution, but using the initial parameterization’s Hessian makes results vary; α = 1/2 is often best synthetically but does not outperform overall.The main paper uses α = 0.Source: B. Parameterization of R · p. 12

C. Spectral method for anisotropic costs

The spectral method extracts rotations from the three right singular vectors of N − I associated with its smallest singular values, because N need not have rank 3 even in the noise-free case.

C. Spectral method for anisotropic costs

  • The method obtains R from the three right singular vectors of N − I with the smallest singular values, since N need not have rank 3 even without noise.Results for this method are included in Table D.1, introduced in the next section.Source: C. Spectral method for anisotropic costs · p. 12

D. Experimental Details

The section provides complementary experimental results on synthetic and real datasets.

D. Experimental Details

D.1. Synthetic experiments

Synthetic experiments show that the proposed method handles anisotropic uncertainty better than the standard isotropic approach. Across additional observation fractions, the proposed objective lowers rotation errors and the proposed constraints speed up the SDP solver.

D.1. Synthetic experiments

  • The proposed method remains accurate as one relative rotation becomes increasingly uncertain, while the standard isotropic approach is negatively affected.The synthetic graph has three cameras; the varying uncertainty ranges from σ = 0.01 to 0.3 around one axis, while the other edges are certain.Source: §D.1 · p. 12
  • Across other fractions of observed relative rotations, the proposed objective leads to lower rotation errors.The results are shown as rotation error histograms.Source: §D.1 · p. 12
  • Across other fractions of observed relative rotations, the proposed constraints speed up the employed SDP solver.The results include runtime dependency on the number of cameras.Source: §D.1 · p. 12

D.2. Real experiments

Real experiments evaluate rotation estimates with uncertainty-aware and geometric error measures. The proposed method achieves much lower error in many cases.

  • Evaluation accounts for estimated uncertainty using the Mahalanobis distance between estimated and ground-truth axis-angle vectors.Source: §D.2 · p. 12
  • Figure D.1 shows camera configuration and rotation error as noise scale increases around one axis.Source: Figure D.1 · p. 12
  • Figure D.2 presents rotation-error histograms and solver runtimes as camera count increases, for different fractions of observed relative rotations.Source: Figure D.2 · p. 13
  • On real datasets, the proposed method has much lower error in many cases, evaluated by Mahalanobis distance and RMS angular errors (Table D.1).Source: Table D.1 · p. 13, §D.2 · p. 13

Related papers

Loading 2503.07353v2…