Source-linked AI summary
Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis
Ivo Ivanov, Carsten Markgraf
TL;DR
Robust point-cloud registration with many outliers is difficult to solve to global optimality quickly. The paper presents OptiPose, combining a linear-time convex relaxation and a contractor to accelerate Branch-and-Bound. For rotation-only TLS registration, it is two orders of magnitude faster than STRIDE, while requiring a provided rotation axis.
Problem
Method
OptiPose uses a linear-time convex relaxation based on interval analysis and a contractor to reduce the Branch-and-Bound search space.
Source: §1 · p. 2Results
Two orders of magnitude faster than STRIDE on rotation-only TLS, OptiPose converged to the global minimum in all tested instances.
Source: §5.4 · p. 9Takeaways & Limitations
The solver formally proves global optimality and provides empirical validation using adversarial instances with local minima close to the global minimum.
Source: §1 · p. 2The solver cannot solve for the full 3D transform and instead requires the axis of rotation.
Source: §6 · p. 9
Abstract
from arXiv · showhide
Recent results showed that point cloud registration with given correspondences can be made robust to outlier rates of up to 95\% using the truncated least squares (TLS) formulation. However, solving this combinatorial optimization problem to global optimality is challenging. Provably globally optimal approaches using semidefinite programming (SDP) relaxations take hundreds of seconds for 100 points. In this paper, we propose a novel linear time convex relaxation as well as a contractor method to speed up Branch and Bound (BnB). Our solver can register two 3D point clouds with 100 points to provable global optimality in less than half a second when the axis of rotation is provided. Although it currently cannot solve the full 6DoF problem, it is two orders of magnitude faster than the state-of-the-art SDP solver STRIDE when solving the rotation-only TLS problem. In addition to providing a formal proof for global optimality, we present empirical evidence of global optimality using adversarial instances with local minimas close to the global minimum.
1. Introduction
Point cloud registration with many outliers is difficult to solve reliably, and heuristic methods lack global-optimality guarantees. This paper introduces OptiPose, combining a linear-time convex relaxation and a contractor to speed Branch-and-Bound while formally proving global optimality.
1. Introduction
- Feature-based matching can produce up to 95% outliers, making the resulting robust-estimation problems combinatorial and difficult to solve globally.Branch-and-Bound solvers can solve these problems but are usually too slow.Source: §1 · p. 1
- Semidefinite relaxations such as STRIDE take hundreds of seconds for 100 points, while heuristics offer no guarantee of global optimality.SDP relaxations can yield a global minimizer when tight; heuristic methods have nevertheless shown robustness to high outlier rates.Source: §1 · p. 1
- TLS and Maximum Consensus classify points as inliers or outliers using a fixed distance threshold; TLS minimizes truncated squared residuals.Both estimators have been shown robust to high outlier rates, with TLS yielding slightly better results [53].Source: §1 · pp. 1–2
- OptiPose solves TLS registration to formal global optimality in less than half a second when the rotation axis is provided.Its relaxation is based on interval analysis and is minimized using custom active-set solvers.Source: §1 · p. 2
- The paper’s contributions include a linear-time convex relaxation, custom active-set solvers, and a contractor that reduces the Branch-and-Bound search space.It also introduces synthetic adversarial instances with local minima close to the global minimum for empirical validation.Source: §1 · p. 2
2. Related Work
Prior work on robust point-cloud registration includes heuristic methods that handle substantial outlier rates and exact methods that seek global guarantees. The related-work discussion highlights limitations in both approaches, including runtime and scope.
2. Related Work
- The related-work section frames robust, certifiable registration as an active area whose long runtimes have kept it impractical for real-time applications.It reviews methods for known correspondences using TLS or Maximum Consensus.Source: §2 · p. 2
2.1. Heuristic algorithms
- Heuristic registration methods include RANSAC variants, TEASER++, and compatibility-graph approaches, but the globally optimal TEASER++ method certifies only rotation or translation subproblems at a time.Its global-optimality guarantee also relies on assumptions about instance difficulty that are unverifiable a priori [Assump. 2, 3 in Thm.17][53].Source: §2.1 · p. 2
- Compatibility-graph methods find maximal or maximum cliques, while dimensionality decomposition solves rotation and translation subproblems sequentially without proving equivalence to the original optimization.The passage notes that sequential solving likely breaks global optimality.Source: §2.1 · p. 2
2.2. Exact algorithms
- Exact methods based on Branch-and-Bound have been proposed for maximum consensus over rotations, but can be slow even for 2D rotation searches.Nested Branch-and-Bound is cited as an example of slow search.Source: §2.2 · p. 2
- STRIDE’s sparse SDP approach can solve synthetic full 6-DoF TLS instances with 100 points and up to 80% outliers to global optimality, but takes 200 seconds.Other SDP uses for multiple point-cloud registration also have large runtimes; Burer-Monteiro methods have not yet been successfully applied to problems with outliers.Source: §2.2 · pp. 2–3
3. Problem formulation
The paper formulates registration from noisy point correspondences as a TLS optimization problem over 3D rotations with a fixed axis. TLS truncates residuals above a threshold, but its non-convex objective can have multiple local minima.
3. Problem formulation
- The registration problem aligns two sequences of noisy 3D points with known correspondences, although up to 95% of those pairs may be outliers.Source: §3 · p. 3
- TLS truncates residuals above a fixed threshold ϵ, minimizing the sum of truncated squared residuals.The threshold ϵ represents the known measurement accuracy of each point and can be estimated from collected samples [13, p.8].Source: §3 · p. 3
- The optimization is over 3D rotations with a fixed axis n*, parameterized by angle θ through exp(θ[n*]×).The rotation angle ranges from −π to π.Source: §3 · p. 3
- The TLS objective is non-convex and combinatorial, and its multiple local minima make global minimization difficult.TLS has been reported robust even at 90% outliers [53].Source: §3 · p. 3, Figure 1 · p. 3
4. OptiPose: A fast BnB solver for the TLS registration
OptiPose is a Branch-and-Bound solver for TLS registration, using a linear-time convex relaxation and a contractor to bound the objective and reduce the search space. The paper proves the components needed for global optimality.
4. OptiPose: A fast BnB solver for the TLS registration
- OptiPose combines a linear-time convex relaxation with a contractor to reduce the search space in Branch-and-Bound for TLS registration.The relaxation supplies a lower bound on the TLS objective.Source: §4 · p. 3, §4.1 · p. 3, §4.4 · p. 5
4.1. WLS Relaxation: A simple linear time relaxation
- Interval analysis reweights convex residual terms so they remain below the truncation threshold across a search interval, yielding a convex relaxation of TLS.The relaxation is valid over the current search-space node and can be computed in linear time.Source: §4.1 · pp. 3–4, Figure 3
4.2. Interval analysis of different residuals
- For translation and rotation balls, the solver computes residual intervals in constant time; 3D-transform intervals follow by substituting the rotated point difference into the translation bound.The passage states that the calculations are practically fast because trigonometric functions can be eliminated.Source: §4.2 · p. 4
4.3. Minimizing the WLS convex relaxation
- The solver minimizes the WLS relaxation within the current BnB node using custom active-set solvers for its ball constraints.For the rotation constraint, it first checks the unconstrained SVD solution; if infeasible, it solves the equality-constrained case by finding the rotation axis at the fixed angle.Source: §4.3 · pp. 4–5
4.4. Contracting the search space
- The contractor preserves the intersection of a search node with the TLS feasible set while shrinking the node, and uses an upper bound to derive a lower bound on non-truncated residuals.A sweep-line algorithm finds the smallest rotation interval containing locations where at least that many residual intervals intersect, with O(N log N) sorting time.Source: §4.4 · pp. 5–6
4.5. Proof of global optimality
- OptiPose’s global-optimality proof establishes valid bounds, a complete contractor, containment of the global minimizer in the root node, and valid node partitions.The paper proves the relaxation is valid and minimized globally, and proves the contractor’s completeness property.Source: §4.5 · p. 6
5. Experimental evaluation
The evaluation tests OptiPose on synthetic registration problems, including fixed-axis registration, rotation-only comparison with STRIDE, and adversarial instances with nearby local minima. Results report fast runtimes, low rotation error, and global-optimality certificates, while showing that difficult adversarial cases can take longer to certify.
5.1.1. Runtime and scalability
- With a fixed rotation axis, OptiPose registers two point clouds of 100 points in near real time.The scalability experiment uses synthetic data with a 50% outlier rate.Source: §5.1.1 · p. 7, Figure 4 · p. 7
5.1.2. Comparison with SDP relaxation solver STRIDE
- In the rotation-only comparison, OptiPose achieves estimation error similar to STRIDE; the evaluation also measures relative suboptimality across outlier rates.The comparison uses synthetic instances, with five STRIDE trials and 20 OptiPose trials.Source: §5.1.2 · p. 7
5.2. Adversarial experiments
- Adversarial tests created instances with a second good local minimum near the global minimum to probe whether OptiPose could verify global optimality.The instances combine two point-cloud problems, with a factor controlling how close the second local optimum is to the global one.Source: §5.2 · pp. 7–8
- Across adversarial trials, OptiPose never reported a suboptimal solution as optimal, but nearby local minima increased runtime and made the 10-second limit more frequent.Those timeouts increased average η-suboptimality.Source: §5.2 · p. 8, Figure 8 · p. 8
5.3. Relaxation runtime
- The convex relaxation scales linearly with data size and takes 50 microseconds for 4,000 points.Its low per-iteration cost comes from fast computation and minimization of the relaxation.Source: §5.3 · p. 8, Figure 9 · p. 9
5.4. Discussion
- OptiPose registers 100 points in 100 ms and solves rotation-only TLS two orders of magnitude faster than STRIDE, while converging to the global minimum in all tested instances.STRIDE's suboptimality increases above a 90% outlier rate, whereas OptiPose's rotation error remains below one degree even above 90%.Source: Figure 5 · p. 7, §5.1.2 · p. 7, §5.4 · pp. 8–9
- Adversarial experiments found no invalid lower bound at termination, supporting implementation correctness; the instances also helped uncover implementation bugs during development.The experiments included cases with a second local optimum close to the global optimum.Source: §5.2 · p. 8, §5.4 · p. 9
6. Conclusion
OptiPose combines a convex relaxation with a contractor to solve TLS point-cloud registration globally, with lower average runtime than tight semidefinite relaxations. Its current scope requires a supplied rotation axis, and future work targets full 3D transforms.
6. Conclusion
- OptiPose solves robust point-cloud registration in the TLS formulation to global optimality using a convex relaxation and a contractor method.The relaxation yields simple weighted least-squares problems; the contractor reduces the Branch-and-Bound search space.Source: §6 · p. 9
- The method has lower average runtime than tight semidefinite relaxations, even when those relaxations are computed hundreds of times.Source: §6 · p. 9
- The solver requires the rotation axis rather than solving the full 3D transform; future work aims to extend the contractor to 3D rotations.The paper also identifies studying the tightness–computational-cost trade-off among convex relaxations as a future direction.Source: §6 · p. 9
A. WLS relaxation
The WLS relaxation uses an affine transformation of residuals to form a convex lower bound for the TLS objective. Its untruncated terms are convex, and the remaining weighted contribution is constant.
A. WLS relaxation
- The proof constructs an affine transform of each residual so the reweighted residual takes specified values at the minimum and maximum residual bounds.Source: A. WLS relaxation · p. 12
- For terms with o_k = 0, the transformed residuals remain untruncated and therefore convex; their sum is convex.Source: A. WLS relaxation · p. 12
- The weighted expression lies below the TLS objective over X, establishing it as a convex relaxation; the contribution for o_i = 1 is constant.Source: A. WLS relaxation · p. 12
B. Interval analysis of residuals under translation
The supplied passage identifies this subsection as the proof of Theorem 2 but provides no further proof content.
B. Interval analysis of residuals under translation
- This subsection is identified as the proof of Theorem 2.Source: B. Interval analysis of residuals… · p. 12
C. Interval analysis of residuals under rotation
The rotation analysis uses the isometry of rotations and bounds the relative rotation by the permitted angular distance. The maximum case follows by the same reasoning.
C. Interval analysis of residuals under rotation
- Using R := R_c∆R, the proof invokes the fact that a rotation is an isometry.Source: C. Interval analysis of residuals… · p. 12
- The relative rotation ∆R is bounded by the angular radius n_r, so the claim follows; the maximum case is handled similarly.Source: C. Interval analysis of residuals… · p. 12
D. Least-squares rotation estimation with equality-constrained angle
These proof sections develop rotation-estimation steps for fixed-angle or fixed-axis settings, minimize a weighted least-squares relaxation, and describe contractor and root-box constructions.
D. Least-squares rotation estimation with equality-constrained angle
- The equality-constrained-angle proof uses Davenport’s quaternion formulation of the Wahba problem, separates rotation axis from angle, and uses the fixed-angle constraint to establish equivalence to the original problem.The proof omits a constant trace term that does not affect the minimizer.Source: D. Least-squares rotation estimation… · p. 13
E. Least-squares rotation estimation with equality-constrained axis
- With a fixed rotation axis, the angle optimization is rewritten as a unit-norm vector problem and solved using the major eigenvector of P.The derivation again uses a quaternion formulation.Source: E. Least-squares rotation estimation… · p. 13
F. Minimizing the WLS relaxation
- The WLS relaxation becomes a least-squares problem with two ball constraints, and intersecting rotation balls can satisfy the translation-ball constraint, effectively eliminating it.The solution modifies Kabsch-Umeyama, solves for rotation first, then obtains translation using weighted centroids.Source: F. Minimizing the WLS relaxation · pp. 13–14
G. Contractor
- The contractor proof eliminates translation from each polynomial inequality and shows its feasible rotations form a rotation ball centered using the point and translated correspondence.The angular bound follows by applying cos(·) ∈ [−1, 1].Source: G. Contractor · p. 14
H. Computing the root box
- The globally optimal TLS translation lies within a box whose corner points are defined from the two point clouds.The supplied passage begins the corner-point definitions but does not provide their full expressions.Source: H. Computing the root box · p. 14