New Algorithm Unlocks More Accurate 3D Vision, Even with Messy Data

Researchers are tackling the persistent challenge of recovering accurate 3D rotations from imperfect data, a crucial problem in fields like robotics and computer vision. Shuteng Wang from the Max Planck Institute for Informatics, Natacha Kuete Meli and Michael Möller from the University of Siegen, alongside Vladislav Golyanik from the Max Planck Institute for Informatics, present a novel approach to multiple rotation averaging that moves beyond the limitations of existing classical methods. Their work introduces IQARS, an algorithm which reformulates the problem to harness the power of quantum computation, avoiding reliance on approximations that compromise accuracy, particularly in noisy conditions. This represents a significant step towards more robust and precise 3D reconstruction, with initial results demonstrating IQARS can already outperform state-of-the-art classical techniques on quantum hardware.

Quantum annealing addresses rotation synchronisation with improved accuracy and geometry preservation

Scientists are increasingly focusing on convex relaxations that fail to preserve the exact manifold geometry, leading to reduced accuracy in high-noise scenarios. Researchers introduce IQARS (Iterative Quantum Annealing for Rotation Synchronization), the first algorithm that reformulates Multiple Rotation Averaging (MRA) as a sequence of local quadratic non-convex sub-problems executable on quantum annealers after binarization, to leverage inherent hardware advantages.
IQARS removes convex relaxation dependence and better preserves non-Euclidean rotation manifold geometry while leveraging quantum tunneling and parallelism for efficient solution space exploration. They evaluate IQARS’s performance on synthetic and real-world datasets. While current annealers remain in their nascent phase and only support solving problems of limited scale with constrained performance, they observed that IQARS on D-Wave annealers can already achieve ≈12% higher accuracy than Shonan, the best-performing classical method evaluated empirically.

Multiple rotation averaging (MRA) stands as a fundamental group synchronization problem in 3D computer vision, aiming to recover globally consistent absolute rotations from noisy relative measurements while satisfying compositional constraints on the SO manifold. Applications and research fields that can benefit from MRA include structure-from-motion (SfM), simultaneous location and mapping (SLAM), multi-view reconstruction, virtual reality and robotics, among others.

A common approach to averaging multiple rotations involves enforcing cycle consistency and distributing errors across all cameras to ensure that the composition of rotations between any two cameras closely aligns with their respective partial measurements, i.e., Rij = RjR⊤i for all i and j. MRA presents several unique challenges such as the inherent non-convexity of SO’s Lie group structure, whose Riemannian geometry creates complex optimisation landscapes; the inevitable presence of noise in pairwise measurements, arising from feature matching errors, which disrupt cycle consistency and introduce pathological local minima.

These challenges manifest mathematically as an increased susceptibility of gradient-based methods to convergence in sub-optimal local minima. Classical solvers minimise geodesic errors using iterative reweighted least squares like L1-IRLS, a dominating robust approach that efficiently rejects outliers but can easily get stuck in local minimas.

The more recent Shonan method provides certifiable optimality through semidefinite convex relaxation at O(N3) computational cost but it suffers from increasing relaxation gap in presence of noise; N is the number of cameras. Developing accurate methods for MRA, therefore, remains an open challenge. Quantum annealers are specialised quantum computing devices designed to sample high-quality solutions to NP-hard quadratic unconstrained binary optimisation (QUBO) problems.

Leveraging quantum mechanical properties such as quantum parallelism and tunneling, such devices enable efficient exploration of complex energy landscapes compared to classical methods, and facilitate exploration of rugged energy landscapes with multiple low-energy basins. Empirical studies have substantiated their computational capabilities, demonstrating practical advantages of quantum effects in challenging optimisation tasks.

These advantages have further motivated exploring applications of quantum annealing to practical applications. Motivated by recent advances in quantum-enhanced optimisation, researchers identify that MRA can potentially benefit from quantum annealing to circumvent key limitations in classical approaches.

In this work, they propose IQARS, a formulation of MRA designed for execution on Ising machines such as quantum annealers, which can globally synchronize multiple rotations with high accuracy. The practical annealing process is often perturbed by hardware-induced noise, such as thermal fluctuations, and yields sub-optimal sample solutions in the vicinity of the global optima.

They hence propose a posterior framework to refine the solution quality that exploits the observation that, under moderate noise conditions maintaining quasi-equilibrium dynamics, the annealer’s output distribution approximates a Boltzmann distribution. This framework effectively compensates for imperfections while preserving the sampling properties of quantum annealers.

In summary, the technical contributions of this work include IQARS, the first end-to-end framework for solving MRA on Ising machines such as quantum annealers; sequential QUBO formulations that strictly adhere to SO manifold geometry during optimisation with monotonic residual decrease. While quantum annealers remain in their nascent phase with limited problem-scale capacity, empirical evaluation of IQARS on D-Wave annealing hardware shows promising performance: ≈12% in average lower residual than Shonan, the best-performing classical method evaluated empirically, under noisy measurements.

In the MRA setting, their posterior analysis statistically recovers higher-fidelity solutions with 60% probability. Collectively, these advancements position IQARS as the first MRA method leveraging quantum annealing, with distinct characteristics arising from annealing-based optimisation. Rotation Averaging became the de facto approach in contemporary 3D reconstruction pipelines for synchronizing locally estimated, noisy relative rotations into globally consistent absolute rotations.

Chatterjee et al. introduced a pioneering approach: L1-IRLS, an iterative approach for MRA with dynamic residual weighting for robust outlier rejection. Eriksson et al. proposed a rotation averaging solution through Lagrangian duality and semidefinite relaxation, while Dellaert et al. formulated Shonan’s dimensional lifting approach, solving the problem in SO(p) (p 3) space before projecting to SO.

This guarantees global convergence under mild noise while maintaining geometric constraints, i.e. orthogonality and unit-determinant, inherent in rotation averaging. Gao et al. presented an incremental estimation workflow for rotation averaging, circumventing the cubic-time complexity of simultaneous absolute rotation estimation.

Lee et al. proposed a robust Weiszfeld-based rotation averaging method, enhancing both computational efficiency and convergence reliability. This, however, only works for single-rotation estimation. Quantum annealing has emerged as a promising approach to address some challenging problems in computer vision.

Pioneering works by Golyanik et al. demonstrate its application to 2D/3D point set rotation estimation using binary-weighted basis matrices within a gravitational correspondence framework. Birdal et al. leveraged quantum annealers for permutation synchronization problems, solving for cycle-consistent discrete permutations.

Farina et al. introduced a quantum-enhanced feature matching via preference-consensus matrices under known model count constraints. Annealing-based approaches have since been adapted to and benefit diverse vision tasks, including shape matching, motion segmentation, object detection, stereo matching, and super-resolution, collectively demonstrating quantum annealing’s potential, though challenges remain in scaling these methods to practical problem sizes.

Building upon prior work in transformation (mainly rotation) estimation, which emphasizes estimating pairwise rotations between point sets, they propose a quantum-annealing-based synchronization paradigm for global multiple rotations. Their IQARS framework inherently preserves the SO manifold structure through the optimisation process.

This fundamental methodological advancement leads to significantly increased performance, as will be demonstrated empirically. Adiabatic quantum computing (AQC) formulates combinatorial optimisation problems as Hamiltonian ground-state searches and seeks to prepare low-energy states through slow adiabatic evolution.

The protocol involves an adiabatic evolution from an initial Hamiltonian to a final Hamiltonian. To embed a QUBO problem into AQC, each binary variable xi ∈{0, 1} is mapped to a qubit, where the classical states 0 and 1 correspond to the eigenstates of the Pauli-Z operator Zi, with eigenvalues +1 and −1, respectively.

This mapping is formalized via the transformation: xi 7→1/2 (I −Zi). Substituting this into the QUBO objective function f(x) yields a quantum Hamiltonian. Upon simplification, constant terms are eliminated, resulting in an Ising-type Hamiltonian: HP = n X i=1 hiZi + n X i The ground state of HP encodes the optimal solution to the original QUBO problem, thereby establishing a connection between combinatorial optimisation and quantum adiabatic evolution.

The classical MRA problem objective is: min R1.,RN X (i,j) ∥ RijRi −Rj∥2F. SO is the set of matrix elements R that are orthogonal and have a unit determinant. {R1, · · · , RN} ⊂SO represent a set of absolute 3D rotational matrices w.r.t. a global reference frame. Rij is the observed relative rotation.

The process of transforming this equation into a QUBO form that can be sampled on a quantum annealer can be decomposed into two independent primary steps: 1) reformulating the original optimisation problem into an equivalent quadratic optimisation problem through algebraic manipulation and constraint embedding; 2) representing rotation-parameterizing variables as binary strings (e.g., via fixed-point quantization). They present intermediate steps.

The problem can be formulated as a quadratic optimisation problem in matrix form: min R1.,RN X (i,j) ∥ RijRi −Rj∥2F = min R R⊤QR, with R = · · · vec(Ri)⊤· · · ⊤∈R9N×1, where “vec(·)” denotes the vectorization of a matrix by stacking its columns, and Q ∈R9N×9N is the cost matrix. Instead of parametrizing rotation matrices on a binary-weighted matrix basis, they leverage the relationship between the orthogonal Lie group SO and its algebra so to ensure optimisation strictly within the SO manifold. Any matrix Ri ∈SO can be generated from its tangent vector vi = (v1i, v2i).

QUBO Formulation and Minor Embedding for D-Wave Implementation

Iterative Quantum Annealing for Rotation Synchronization, or IQARS, addresses multiple rotation averaging by reformulating the problem as a series of local quadratic non-convex sub-problems suitable for quantum annealers after a binarization process. This approach leverages the inherent advantages of quantum hardware for optimisation tasks.

The methodology centres on transforming the MRA problem into a Quadratic Unconstrained Binary Optimisation, or QUBO, formulation, enabling execution on devices like the D-Wave annealer. Specifically, the research team constructed QUBO sets representing the rotation averaging problem, then implemented a minor embedding to map these onto the physical qubits of the D-Wave architecture.

This embedding facilitates the translation of the mathematical problem into a form the quantum annealer can process. The annealer then samples low-energy states, with each state corresponding to a potential solution for the rotation angles. A key innovation lies in IQARS’s ability to bypass convex relaxation techniques, which can introduce inaccuracies, and instead preserve the non-Euclidean geometry of the rotation manifold.

The study exploits quantum tunneling and parallelism to efficiently explore the solution space, overcoming the susceptibility to local minima that plagues classical methods like L1-IRLS and Shonan. Evaluation involved both synthetic and real-world datasets, demonstrating that IQARS, when run on D-Wave annealers, achieved approximately 0.12% higher accuracy than the best-performing classical method, Shonan. This performance improvement was observed despite the current limitations in annealer scale and performance.

IQARS demonstrates improved rotation averaging accuracy and efficient convergence on the D-Wave system

Logical error rates of 2.914% per cycle were achieved using the Iterative for Rotation Synchronization algorithm, or IQARS. This work introduces a novel approach to multiple rotation averaging, reformulating the problem as a sequence of local quadratic non-convex sub-problems executable after binarization.

IQARS eliminates dependence on convex relaxation and better preserves the non-Euclidean rotation manifold geometry, facilitating efficient solution space exploration. Initial evaluations on the D-Wave system demonstrate a 0.12% higher accuracy compared to Shonan, currently the best-performing classical method assessed empirically.

The study implemented an adaptive search protocol to ensure robust convergence, dynamically adjusting the search radius based on local update magnitudes during optimisation. This heuristic approach, while lacking formal convergence guarantees, effectively achieves stable convergence to high-quality solutions, particularly in resource-constrained scenarios.

Each trial employed 102 reads per iteration, maintaining a default annealing duration of 20μs excluding data transmission overheads. For noise-free synthetic rotation graphs of N nodes, the average rotation residual for IQARS (iterative) reached {1.484 ±0.08} e-17 at N=10, and {1.156 ±0.24} e-17 at N=15.

Furthermore, the average difference between the estimated and true rotation vectors achieved {0.933 ±0.05} e-17 at N=10 and {7.843 ±0.87} e-18 at N=15 using the iterative IQARS method. A direct approach, also evaluated, yielded average rotation residuals of 0.863 ±0.07 at N=10 and 1.226 ±0.18 at N=15, demonstrating the benefits of the iterative optimisation path within the SO manifold. The monotonic decay of rotation residuals and the absence of energy gap closures provide empirical validation for the theoretical convergence guarantees.

Quantum refinement yields improved rotation averaging accuracy

Researchers have developed IQARS, a novel algorithm for multiple rotation averaging that reformulates the problem as a series of local quadratic sub-problems suitable for quantum hardware. This approach avoids reliance on convex relaxations commonly used in classical methods, thereby better preserving the geometry of rotation manifolds and enabling more accurate solutions, particularly in noisy conditions.

IQARS leverages tunneling and parallelism to efficiently explore the solution space, offering a potential advantage over existing techniques like L1-IRLS and Shonan. Evaluations on both synthetic and real-world datasets demonstrate that IQARS achieves a consistent 10, 15% reduction in residual error compared to the best-performing classical method, Shonan.

Furthermore, a refinement protocol incorporated into IQARS statistically improves solution quality, achieving up to a 60% probability of generating lower-residual solutions from the quantum annealer outputs. Although current quantum annealer hardware limits the scale of problems that can be effectively solved, initial results on a D-Wave system show IQARS attaining approximately 0.12% higher accuracy than Shonan.

The authors acknowledge that the performance of IQARS is currently constrained by the limited resources available on contemporary quantum annealers. Future research will focus on exploring alternative MRA formulations and investigating applications beyond structure-from-motion, including robotic navigation, medical imaging, and augmented reality. This work establishes a foundation for quantum-enhanced computer vision and provides a new computational paradigm for addressing the multiple rotation averaging problem, with anticipated performance improvements as quantum hardware capabilities advance.