Awesome Global Solvers for 3D Vision

Advances in Global Solvers for 3D Vision: A Comprehensive Survey

Zhenjun Zhao¹ Heng Yang² Bangyan Liao³ Yingping Zeng⁴ Shaocheng Yan⁵
Yingdong Gu⁵ Peidong Liu³ Yi Zhou⁴ Haoang Li⁶ Javier Civera¹

¹University of Zaragoza ²Harvard University ³Westlake University
⁴Hunan University ⁵Wuhan University ⁶HKUST(GZ)

Taxonomy of our survey on global solvers for 3D vision

🌟 If you find this repository useful, please consider giving it a STAR ⭐ and citing our survey paper!

🙋 Please let us know if you find any mistakes or have suggestions! Feel free to open an issue or submit a pull request.

🏠 Introduction

This repository serves as a comprehensive resource hub accompanying our survey paper Advances in Global Solvers for 3D Vision.

Scope: The survey systematically reviews global optimization methods across 3 major paradigms and 10 fundamental 3D vision tasks, covering 400+ papers spanning from 1960 to 2025.

Paradigms	Tasks
🔹 Branch-and-Bound (BnB)	Wahba Problem · Vanishing Point Estimation Absolute Pose Estimation · Relative Pose Estimation 3D Registration · Rotation Averaging Translation Averaging · Triangulation Pose Graph Optimization · Bundle Adjustment
🔹 Convex Relaxation (Shor's / Moment-SOS / Others)
🔹 Graduated Non-Convexity (GNC)

What's included:

📚 Curated paper list: Systematic organization of 250+ papers on global optimization methods for 3D vision
💻 Companion tutorial code: Hands-on examples demonstrating convex relaxation formulations using the SPOT package
🎓 Educational resources: Workshops, tutorials, lectures, and talks from leading researchers

Please feel free to send us pull requests or email to add papers, suggest improvements, or contribute resources!

🔥 News

[2025/02] 📮 Our survey paper Advances in Global Solvers for 3D Vision is available on arXiv!
[2025/02] 🚀 This repository is publicly released with 250+ curated papers and companion tutorial code.

📝 Citation

If you find our survey helpful for your research, please consider citing:

@article{zhang2025advances,
  title={Advances in Global Solvers for 3D Vision},
  author={Zhao, Zhenjun and Heng, Yang and Liao, Bangyan and Zeng, Yingping and Yan, Shaocheng and Gu, Yingdong and Liu, Peidong and Zhou, Yi and Li, Haoang and Civera, Javier},
  journal={arXiv preprint arXiv:2602.14662},
  year={2025}
}

Theory

Branch-and-Bound (BnB)

Foundational Papers

Year	Venue	Paper	Links
1960	Econometrica	An Automatic Method of Solving Discrete Programming Problems	[Paper]
1966	Operations Research	Branch-and-Bound Methods: A Survey	[Paper]
1999	-	Branch and Bound Algorithms-Principles and Examples	[Paper]
2016	Discrete Optimization	Branch-and-Bound Algorithms: A Survey of Recent Advances in Searching, Branching, and Pruning	[Paper]
2019	J. Global Optim.	A Generic Interval Branch and Bound Algorithm for Parameter Estimation	[Paper]

General Frameworks for Multiple Tasks

Year	Venue	Paper	Links
2006	ECCV	Practical Global Optimization for Multiview Geometry	[Paper]
2008	IJCV	Practical Global Optimization for Multiview Geometry	[Paper]
2009	ICCV	Optimal Correspondences from Pairwise Constraints	[Paper]
2009	IJCV	Global Optimization through Rotation Space Search	[Paper]
2009	ICCV	Consensus Set Maximization with Guaranteed Global Optimality for Robust Geometry Estimation	[Paper]
2011	CVPR	Deterministically Maximizing Feasible Subsystem for Robust Model Fitting with Unit Norm Constraint	[Paper]
2022	IJCV	Globally Optimal Linear Model Fitting with Unit-Norm Constraint	[Paper]
2024	TPAMI	Accelerating Globally Optimal Consensus Maximization in Geometric Vision	[Paper]
2026	arXiv	Global Truncated Loss Minimization for Robust and Threshold-Resilient Geometric Estimation	[Paper]

Shor's Relaxation

Foundational Papers

Year	Venue	Paper	Links
2000	Handbook of SDP	Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization	[Paper]
2003	Math. Programming	A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization	[Paper]
2006	SIAM J. Optim.	Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework	[Paper]
2010	Signal Process. Mag.	Semidefinite Relaxation of Quadratic Optimization Problems	[Paper]
2012	Math. Programming	On Convex Relaxations for Quadratically Constrained Quadratic Programming	[Paper]
2015	Math. Program. Comput.	SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for SDP with Nonnegative Constraints	[Paper]
2016	NeurIPS	The Non-Convex Burer-Monteiro Approach Works on Smooth Semidefinite Programs	[Paper]
2018	Found. Comput. Math.	Random Laplacian Matrices and Convex Relaxations	[Paper]
2019	arXiv	Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints	[Paper]
2020	WAFR	Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception	[Paper]
2022	Math. Programming	On the Local Stability of Semidefinite Relaxations	[Paper]
2022	RAL	Accelerating Certifiable Estimation with Preconditioned Eigensolvers	[Paper]
2024	RSS Workshop	An Overview of the Burer-Monteiro Method for Certifiable Robot Perception	[Paper]
2024	TRO	Toward Globally Optimal State Estimation Using Automatically Tightened Semidefinite Relaxations	[Paper] [Code]
2024	WAFR	Exploiting Chordal Sparsity for Fast Global Optimality with Application to Localization	[Paper]
2024	ICML	Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching	[Paper] [Code]

General Frameworks for Multiple Tasks

Year	Venue	Paper	Links
2022	JMIV	On the Tightness of Semidefinite Relaxations for Rotation Estimation	[Paper]
2024	TRO	On Semidefinite Relaxations for Matrix-Weighted State-Estimation Problems in Robotics	[Paper]
2025	ICRA Workshop	Simplifying Certifiable Estimation: A Factor Graph Optimization Approach	[Paper] [Code]

Moment-SOS Relaxation

Foundational Papers

Year	Venue	Paper	Links
2001	SIAM J. Optim.	Global Optimization with Polynomials and the Problem of Moments	[Paper]
2003	Math. Programming	Semidefinite Programming Relaxations for Semialgebraic Problems	[Paper]
2006	SIAM J. Optim.	Convergent SDP-Relaxations in Polynomial Optimization with Sparsity	[Paper]
2008	Emerging App. Alg. Geom.	Sums of Squares, Moment Matrices and Optimization Over Polynomials	[Paper]
2010	APJOR	SDP Relaxations for Quadratic Optimization Problems Derived from Polynomial Optimization Problems	[Paper]
2014	Math. Programming	Optimality Conditions and Finite Convergence of Lasserre's Hierarchy	[Paper]
2022	OL	Convergence of Lasserre's hierarchy: the general case	[Paper]
2025	Math. Programming	Finding Global Minima via Kernel Approximations	[Paper]

General Frameworks for Multiple Tasks

Year	Venue	Paper	Links
2005	ICCV	Globally Optimal Estimates for Geometric Reconstruction Problems	[Paper]
2007	IJCV	Globally Optimal Estimates for Geometric Reconstruction Problems	[Paper]
2019	ICCV	Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision	[Paper]
2020	NeurIPS	One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers	[Paper] [Code]
2022	TPAMI	Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization	[Paper] [Code]

Other Relaxation Techniques

Year	Venue	Paper	Links
2004	CVPR	$L_\infty$ Minimization in Geometric Reconstruction Problems	[Paper]
2005	ICCV	Multiple View Geometry and the $L_\infty$-Norm	[Paper]
2006	CVPR	Removing Outliers Using the $L_\infty$ Norm	[Paper]
2007	ICCV	Efficient Optimization for $L_\infty$-problems Using Pseudoconvexity	[Paper]
2007	ICCV	A Fast Method to Minimize $L_\infty$ Error Norm for Geometric Vision Problems	[Paper]
2007	TPAMI	Quasiconvex Optimization for Robust Geometric Reconstruction	[Paper]
2008	CVPR	Fast Algorithms for $L_\infty$ Problems in Multiview Geometry	[Paper]
2008	CVPR	A Polynomial-time Bound for Matching and Registration with Outliers	[Paper]
2008	TPAMI	Multiple-View Geometry Under the $L_\infty$-Norm	[Paper]
2009	CVPR	Efficient Reduction of L-infinity Geometry Problems	[Paper]
2010	CVPR	Outlier Removal Using Duality	[Paper] [Code]
2017	CVPR	Consensus Maximization with Linear Matrix Inequality Constraints	[Paper]
2024	RAL	FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator	[Paper] [Code]

Graduated Non-Convexity (GNC)

Year	Venue	Paper	Links
1996	IJCV	On the Unification Line Processes, Outlier Rejection, and Robust Statistics with Applications in Early Vision	[Paper]
2015	CVPRW	On the Link between Gaussian Homotopy Continuation and Convex Envelopes	[Paper]
2020	RAL	Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection	[Paper] [Code]
2023	CVPR	Adaptive Annealing for Robust Geometric Estimation	[Paper]
2024	ECCV	Adaptive Annealing for Robust Averaging	[Paper]
2025	ICCV	SAC-GNC: SAmple Consensus for adaptive Graduated Non-Convexity	[Paper]

Robust Variants: Adaptive Trimming (ADAPT)

Year	Venue	Paper	Links
2019	IROS	Outlier-Robust Spatial Perception: Hardness, General-Purpose Algorithms, and Guarantees	[Paper]
2021	TRO	Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications	[Paper] [Code]

Consensus Maximization

Year	Venue	Paper	Links
2015	CVPR	Efficient Globally Optimal Consensus Maximisation with Tree Search	[Paper]
2018	ECCV	Robust Fitting in Computer Vision: Easy or Hard?	[Paper]
2018	ECCV	Deterministic Consensus Maximization with Biconvex Programming	[Paper] [Code]
2019	ICCV	Consensus Maximization Tree Search Revisited	[Paper] [Code]
2019	TPAMI	Deterministic Approximate Methods for Maximum Consensus Robust Fitting	[Paper]
2019	TRO	Efficient Algorithms for Maximum Consensus Robust Fitting	[Paper]

Application

Geometric illustration of the 10 fundamental 3D vision tasks covered in our survey

Wahba Problem

BnB for Wahba Problem

Year	Venue	Paper	Links
2012	ACCV	Globally Optimal Consensus Set Maximization through Rotation Search	[Paper]
2014	CVPR	Fast Rotation Search with Stereographic Projections for 3D Registration	[Paper]
2016	TPAMI	Fast Rotation Search with Stereographic Projections for 3D Registration	[Paper]

Shor's Relaxation for Wahba Problem

Year	Venue	Paper	Links
2011	CDC	Semidefinite Relaxation of a Robust Static Attitude Determination Problem	[Paper]
2012	TSP	A Semidefinite Relaxation-Based Algorithm for Robust Attitude Estimation	[Paper]
2016	TOG	Point Registration via Efficient Convex Relaxation	[Paper] [Code]
2017	SIAM J. Optim.	Exact Recovery with Symmetries for Procrustes Matching	[Paper]
2019	ICCV	A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers	[Paper]
2021	arXiv	Near-Optimal Bounds for Generalized Orthogonal Procrustes Problem via Generalized Power Method	[Paper]
2022	ECCV	Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search: Tight or Not	[Paper]
2022	arXiv	Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search	[Paper]

Robust Preprocessing

Year	Venue	Paper	Links
2015	ICCV	Guaranteed Outlier Removal for Rotation Search	[Paper]
2022	CVPR	ARCS: Accurate Rotation and Correspondence Search	[Paper] [Code]

Vanishing Point Estimation

BnB for Vanishing Point Estimation

Year	Venue	Paper	Links
2012	CVPR	Globally Optimal Line Clustering and Vanishing Point Estimation in Manhattan World	[Paper]
2016	CVPR	Globally Optimal Manhattan Frame Estimation in Real-time	[Paper]
2018	TPAMI	Robust and Globally Optimal Manhattan Frame Estimation in Near Real Time	[Paper]
2018	CVPR	Globally Optimal Inlier Set Maximization for Atlanta Frame Estimation	[Paper]
2019	TPAMI	Globally Optimal Inlier Set Maximization for Atlanta World Understanding	[Paper]
2019	ICCV	Quasi-globally Optimal and Efficient Vanishing Point Estimation in Manhattan World	[Paper]
2020	ECCV	Globally Optimal and Efficient Vanishing Point Estimation in Atlanta World	[Paper]
2020	TPAMI	Globally Optimal Vertical Direction Estimation in Atlanta World	[Paper] [Code]
2022	TPAMI	Quasi-globally Optimal and Near/True Real-time Vanishing Point Estimation in Manhattan World	[Paper]

Shor's Relaxation for Vanishing Point Estimation

Year	Venue	Paper	Links
2025	CVPR	Convex Relaxation for Robust Vanishing Point Estimation in Manhattan World	[Paper] [Code]

Absolute Pose Estimation (PnP)

BnB for PnP

Year	Venue	Paper	Links
2006	ICPR	Optimal Estimation of Perspective Camera Pose	[Paper]
2008	ECCV	Robust Optimal Pose Estimation	[Paper]
2010	WCICA	Linear Relaxation for Global Pose Estimation	[Paper]
2015	ICCV	Globally Optimal 2D-3D Registration from Points or Lines Without Correspondences	[Paper]
2017	ICCV	Globally-Optimal Inlier Set Maximisation for Simultaneous Camera Pose and Feature Correspondence	[Paper]
2018	TPAMI	Globally-Optimal Inlier Set Maximisation for Camera Pose and Correspondence Estimation	[Paper]
2018	TIP	2D-3D Point Set Registration Based on Global Rotation Search	[Paper]
2019	CVPR	The Alignment of the Spheres: Globally-Optimal Spherical Mixture Alignment for Camera Pose Estimation	[Paper]
2019	PR	A Family of Globally Optimal Branch-and-Bound Algorithms for 2D-3D Correspondence-Free Registration	[Paper]
2019	Remote Sensing	A Novel Method for the Absolute Pose Problem with Pairwise Constraints	[Paper]
2020	RAL	Globally Optimal Camera Orientation Estimation from Line Correspondences by BnB algorithm	[Paper]
2021	TPAMI	Efficient and Outlier-Robust Simultaneous Pose and Correspondence Determination by BnB and Transformation Decomposition	[Paper]
2023	TCSVT	Absolute Pose Estimation With a Known Direction by Motion Decoupling	[Paper] [Code]
2024	RAL	Efficient and Globally Optimal Camera Orientation Estimation With Line Correspondences	[Paper] [Code]
2025	RAL	BnB-Based Robust PnP Pose Estimation Method for Outliers	[Paper]

Shor's Relaxation for PnP

Year	Venue	Paper	Links
2010	Image Vis. Comput.	Optimal Non-Iterative Pose Estimation via Convex Relaxation	[Paper]
2023	JMIV	CvxPnPL: A Unified Convex Solution to the Absolute Pose Estimation Problem from Point and Line Correspondences	[Paper] [Code]

Moment-SOS Relaxation for PnP

Year	Venue	Paper	Links
2008	BMVC	Globally Optimal O(n) Solution to the PnP Problem for General Camera Models	[Paper]
2020	Access	Certifiably Optimal and Robust Camera Pose Estimation From Points and Lines	[Paper]
2021	Sensors	The Non-Tightness of a Convex Relaxation to Rotation Recovery	[Paper]

Other Relaxation for PnP

Year	Venue	Paper	Links
2014	ICRA	Convex Relaxations of SE(2) and SE(3) for Visual Pose Estimation	[Paper]
2016	TIP	Non-Iterative Rigid 2D/3D Point-Set Registration Using Semidefinite Programming	[Paper]
2020	ECCV	A Consistently Fast and Globally Optimal Solution to the Perspective-n-Point Problem	[Paper] [Code]
2023	RAL	Efficient Solution to PnP Problem Based on Vision Geometry	[Paper]
2024	SIAM J. Imaging Sci.	Fast Certifiable Algorithm for the Absolute Pose Estimation of a Camera	[Paper]

GNC for PnP

Year	Venue	Paper	Links
2020	Access	Certifiably Optimal and Robust Camera Pose Estimation From Points and Lines	[Paper]
2024	IET CV	Outliers Rejection for Robust Camera Pose Estimation using Graduated Non-Convexity	[Paper]

Relative Pose Estimation

BnB for Relative Pose Estimation

Year	Venue	Paper	Links
2007	ICCV	Global Optimization through Searching Rotation Space and Optimal Estimation of the Essential Matrix	[Paper]
2008	CVPR	Motion Estimation for Multi-Camera Systems using Global Optimization	[Paper]
2009	BMVC	Two View Geometry Estimation with Outliers	[Paper]
2009	ICCV	Globally Optimal Affine Epipolar Geometry from Apparent Contours	[Paper]
2009	TPAMI	Motion Estimation for Nonoverlapping Multicamera Rigs: Linear Algebraic and $L_\infty$ Geometric Solutions	[Paper]
2011	CVPR	A Branch and Contract Algorithm for Globally Optimal Fundamental Matrix Estimation	[Paper]
2013	ICCV	Direct Optimization of Frame-to-Frame Rotation	[Paper]
2014	ECCV	Optimal Essential Matrix Estimation via Inlier-Set Maximization	[Paper]
2014	ECCV	Globally Optimal Inlier Set Maximization With Unknown Rotation and Focal Length	[Paper]
2015	CVPR	Practical Robust Two-View Translation Estimation	[Paper]
2016	CVPR	Optimal Relative Pose with Unknown Correspondences	[Paper]
2020	ICRA	Efficient Globally-Optimal Correspondence-Less Visual Odometry for Planar Ground Vehicles	[Paper]
2020	ICRA	Globally Optimal Relative Pose Estimation for Camera on a Selfie Stick	[Paper]
2021	RAL	Globally Optimal Consensus Maximization for Relative Pose Estimation With Known Gravity Direction	[Paper] [Code]
2022	Front. Neurorobot.	Globally-Optimal Inlier Maximization for Relative Pose Estimation Under Planar Motion	[Paper]

Shor's Relaxation for Relative Pose Estimation

Year	Venue	Paper	Links
2018	CVPR	A Certifiably Globally Optimal Solution to the Non-Minimal Relative Pose Problem	[Paper]
2020	CVPR	A Certifiably Globally Optimal Solution to Generalized Essential Matrix Estimation	[Paper]
2020	IROS	Robot-to-Robot Relative Pose Estimation based on Semidefinite Relaxation Optimization	[Paper]
2021	IVC	Certifiable Relative Pose Estimation	[Paper]
2021	JMIV	Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras	[Paper] [Code]
2022	TPAMI	An Efficient Solution to Non-Minimal Case Essential Matrix Estimation	[Paper] [Code]
2022	JMIV	A Tighter Relaxation for the Relative Pose Problem Between Cameras	[Paper] [Code]
2023	ICCV	Essential Matrix Estimation using Convex Relaxations in Orthogonal Space	[Paper] [Code]
2023	-	Fast Certifiable Relative Pose Estimation with Gravity Prior	[Paper] [Code]
2024	CVPR	From Correspondences to Pose: Non-minimal Certifiably Optimal Relative Pose without Disambiguation	[Paper] [Code] [Project]
2024	CVIU	Certifiable Planar Relative Pose Estimation with Gravity Prior	[Paper] [Code]

Moment-SOS Relaxation for Relative Pose Estimation

Year	Venue	Paper	Links
2002	TPAMI	Estimating the Fundamental Matrix via Constrained Least-Squares: A Convex Approach	[Paper]
2009	TPAMI	Camera Displacement via Constrained Minimization of the Algebraic Error	[Paper]
2010	ICCASM	New Fundamental Matrix Estimation Method Using Global Optimization	[Paper]
2015	JMIV	Rank-Constrained Fundamental Matrix Estimation by Polynomial Global Optimization Versus the Eight-Point Algorithm	[Paper]
2015	CVPR	A Convex Optimization Approach to Robust Fundamental Matrix Estimation	[Paper]
2019	AIAM	Non-Minimum Essential Matrix Estimation Using Sum of Square Method	[Paper]
2022	JIN	SPLP: A Certifiably Globally Optimal Solution to the Relative Pose Estimation Problem Using Points and Line Pairs	[Paper]

Other Relaxation for Relative Pose Estimation

Year	Venue	Paper	Links
2007	ACCV	Visual Odometry for Non-Overlapping Views Using Second-Order Cone Programming	[Paper]

3D Registration

BnB for 3D Registration

Year	Venue	Paper	Links
2006	CVPR	The Registration Problem Revisited: Optimal Solutions From Points, Lines and Planes	[Paper]
2007	ICCV	The 3D-3D Registration Problem Revisited	[Paper]
2008	TPAMI	Branch-and-Bound Methods for Euclidean Registration Problems	[Paper]
2013	ICCV	Go-ICP: Solving 3D Registration Efficiently and Globally Optimally	[Paper] [Code]
2015	TPAMI	Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration	[Paper] [Code]
2015	ICCV	Robust and Optimal Sum-of-Squares-Based Point-to-Plane Registration of Image Sets and Structured Scenes	[Paper]
2016	CVPR	GOGMA: Globally-Optimal Gaussian Mixture Alignment	[Paper]
2016	TPAMI	An Efficient Globally Optimal Algorithm for Asymmetric Point Matching	[Paper]
2017	CVPR	Efficient Global Point Cloud Alignment using Bayesian Nonparametric Mixtures	[Paper]
2018	ECCV	Efficient Global Point Cloud Registration by Matching Rotation Invariant Features Through Translation Search	[Paper]
2018	IJCV	Robust and Optimal Registration of Image Sets and Structured Scenes via Sum-of-Squares Polynomials	[Paper]
2018	arXiv	Fast and Globally Optimal Rigid Registration of 3D Point Sets by Transformation Decomposition	[Paper]
2019	ISPRS J.	Practical Optimal Registration of Terrestrial LiDAR Scan Pairs	[Paper]
2019	arXiv	A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints	[Paper]
2021	JMIV	Globally Optimal Point Set Registration by Joint Symmetry Plane Fitting	[Paper]
2022	CVPR	Deterministic Point Cloud Registration via Novel Transformation Decomposition	[Paper]
2023	CAGD	A Chebyshev Metamodel Based BnB Approach to Efficiently Search Global Optimum for 3D ICP Point Set Registration	[Paper]
2023	ISPRS J.	Fast and Deterministic (3+1)DOF Point Set Registration with Gravity Prior	[Paper] [Code]
2024	CVPR	Scalable 3D Registration via Truncated Entry-wise Absolute Residuals	[Paper] [Code]
2024	TPAMI	Efficient and Robust Point Cloud Registration via Heuristics-Guided Parameter Search	[Paper] [Code]
2024	TIV	Efficient and Deterministic Search Strategy Based on Residual Projections for Point Cloud Registration with Correspondences	[Paper]
2025	TII	Hierarchical and Validated Branch-and-Bound Method for Global Point Cloud Registration	[Paper]
2025	arXiv	Fast Globally Optimal Truncated Least Squares Point Cloud Registration with Fixed Rotation Axis	[Paper]
2025	arXiv	Robust Point Cloud Registration via Geometric Overlapping Guided Rotation Search	[Paper] [Code]
2026	arXiv	DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming	[Paper]

Shor's Relaxation for 3D Registration

Year	Venue	Paper	Links
2008	ICPR	Solving Quadratically Constrained Geometrical Problems using Lagrangian Duality	[Paper]
2015	SIAM J. Optim.	Global Registration of Multiple Point Clouds Using Semidefinite Programming	[Paper]
2017	CVPR	Convex Global 3D Registration with Lagrangian Duality	[Paper] [Code]
2019	RSS	A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates	[Paper]
2020	CVPR	Global Optimality for Point Set Registration Using Semidefinite Programming	[Paper]
2020	TRO	TEASER: Fast and Certifiable Point Cloud Registration	[Paper] [Code]
2024	ECCV	GlobalPointer: Large-Scale Plane Adjustment with Bi-Convex Relaxation	[Paper] [Code] [Project]

Other Relaxation for 3D Registration

Year	Venue	Paper	Links
2017	ICIP	Global multiview registration using non-convex ADMM	[Paper]

GNC for 3D Registration

Year	Venue	Paper	Links
2023	CVPR	On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation	[Paper] [Code]

Robust Preprocessing for 3D Registration

Year	Venue	Paper	Links
2017	TPAMI	Guaranteed Outlier Removal for Point Cloud Registration with Correspondences	[Paper]
2023	TPAMI	QGORE: Quadratic-Time Guaranteed Outlier Removal for Point Cloud Registration	[Paper]

Rotation Averaging

Shor's Relaxation for Rotation Averaging

Year	Venue	Paper	Links
2011	Appl. Comput. Harmon. Anal.	Angular Synchronization by Eigenvectors and Semidefinite Programming	[Paper]
2012	3DIMPVT	Global Motion Estimation from Point Matches	[Paper]
2012	ACCV	Simultaneous Multiple Rotation Averaging Using Lagrangian Duality	[Paper]
2017	Math. Programming	Tightness of the Maximum Likelihood Semidefinite Relaxation for Angular Synchronization	[Paper]
2018	SIAM J. Optim.	Near-Optimal Bounds for Phase Synchronization	[Paper]
2018	CVPR	Rotation Averaging and Strong Duality	[Paper]
2019	TPAMI	Rotation Averaging with the Chordal Distance: Global Minimizers and Strong Duality	[Paper]
2020	ECCV	Shonan Rotation Averaging: Global Optimality by Surfing $SO(p)^n$	[Paper] [Code] [Project]
2021	CVPR	Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging	[Paper] [Code]
2021	CVPR	Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach	[Paper] [Code]
2021	ICCV	Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs	[Paper] [Code]
2024	arXiv	Rotation Averaging: A Primal-Dual Method and Closed-Forms in Cycle Graphs	[Paper] [Code]
2025	IJRR	Certifiably Optimal Rotation and Pose Estimation Based on the Cayley Map	[Paper]
2025	ICCV	Certifiably Optimal Anisotropic Rotation Averaging	[Paper] [Code] [Project]

Moment-SOS Relaxation for Rotation Averaging

Year	Venue	Paper	Links
2014	IHMSC	Globally Optimal Estimates for Rotation Averaging Problems	[Paper]

Other Relaxation for Rotation Averaging

Year	Venue	Paper	Links
2010	MTNS	Rotation Averaging and Weak Convexity	[Paper]
2013	Inf. Inference	Exact and Stable Recovery of Rotations for Robust Synchronization	[Paper]
2014	CDC	Semidefinite Relaxations for Optimization Problems over Rotation Matrices	[Paper]
2017	JPRS	Global Robust Image Rotation from Combined Weighted Averaging	[Paper]
2022	ICML	Robust Group Synchronization via Quadratic Programming	[Paper] [Code]

Translation Averaging

Shor's Relaxation for Translation Averaging

Year	Venue	Paper	Links
2015	SIAM J. Imaging Sci.	Stable Camera Motion Estimation Using Convex Programming	[Paper]

Other Relaxation for Translation Averaging

Year	Venue	Paper	Links
2006	CVPR	Recovering Camera Motion Using $l_{\infty}$ Minimization	[Paper]
2013	ICCV	Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion	[Paper]
2015	CVPR	Robust Camera Location Estimation by Convex Programming	[Paper]
2016	ECCV	ShapeFit and ShapeKick for Robust, Scalable Structure from Motion	[Paper]
2018	CVPR	Baseline Desensitizing in Translation Averaging	[Paper]

Translation Averaging with Structure (a.k.a. Known Rotations)

Year	Venue	Paper	Links
2009	NeurIPS	L1-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry	[Paper]
2018	arXiv	Efficient Outlier Removal in Large Scale Global Structure-from-Motion	[Paper]

Triangulation

BnB for Triangulation

Year	Venue	Paper	Links
2007	ACCV	A Fast Optimal Algorithm for $L_2$ Triangulation	[Paper]
2008	JMIV	Triangulation of Points, Lines and Conics	[Paper]

Shor's Relaxation for Triangulation

Year	Venue	Paper	Links
2010	CVPR	Multi-View Structure Computation without Explicitly Estimating Motion	[Paper]
2012	ECCV	A QCQP Approach to Triangulation	[Paper]
2021	SIAM	A Convex Relaxation to Compute the Nearest Structured Rank Deficient Matrix	[Paper] [Code]
2023	CVPR	Semidefinite Relaxations for Robust Multiview Triangulation	[Paper] [Code]

Other Relaxation for Triangulation

Year	Venue	Paper	Links
2007	CVPR	A Practical Algorithm for $L_\infty$ Triangulation with Outliers	[Paper]
2010	AICI	L-Infinity Norm Minimization in the Multiview Triangulation	[Paper]
2010	ICINFA	Triangulation in Omnidirectional Vision under the $L_\infty$-Norm	[Paper]
2014	PR	Robust multiview $L_2$ triangulation via optimal inlier selection and 3D structure refinement	[Paper]
2023	RAL	Certifiable Solver for Real-Time N-View Triangulation	[Paper] [Code]

Pose Graph Optimization

Shor's Relaxation for Pose Graph Optimization

Year	Venue	Paper	Links
2012	IROS	A Convex Optimization based Approach for Pose SLAM Problems	[Paper]
2015	IROS	Lagrangian Duality in 3D SLAM: Verification Techniques and Optimal Solutions	[Paper]
2015	RSS	On the Inclusion of Determinant Constraints in Lagrangian Duality for 3D SLAM	[Paper]
2015	arXiv	Pose Graph Optimization in the Complex Domain: Lagrangian Duality, Conditions For Zero Duality Gap, and Optimal Solutions	[Paper] [Code]
2015	ICRA	Duality-based verification techniques for 2D SLAM	[Paper]
2016	IROS	Fast Global Optimality Verification in 3D SLAM	[Paper] [Code]
2016	SOIA	Lagrangian Duality in Complex Pose Graph Optimization	[Paper]
2016	TRO	Planar Pose Graph Optimization: Duality, Optimal Solutions, and Verification	[Paper]
2017	ICRA	Initialization of 3D Pose Graph Optimization Using Lagrangian Duality	[Paper]
2017	RAL	Cartan-Sync: Fast and Global SE(d)-Synchronization	[Paper] [Code]
2018	RAL	Convex Relaxations for Pose Graph Optimization With Outliers	[Paper]
2019	IROS	CPL-Sync: Efficient and Guaranteed Planar Pose Graph Optimization Using the Complex Number Representation	[Paper] [Code]
2019	RAL	Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models	[Paper]
2019	IJRR	SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group	[Paper] [Code]
2019	TRO	Distributed Certifiably Correct Pose-Graph Optimization	[Paper] [Code]
2023	RAL	An Efficient Global Optimality Certificate for Landmark-Based SLAM	[Paper]
2024	RAL	SIM-Sync: From Certifiably Optimal Synchronization over the 3D Similarity Group to Scene Reconstruction with Learned Depth	[Paper]
2024	TRO	Certifiably Correct Range-Aided SLAM	[Paper] [Code]
2025	ICRA	Distributed Certifiably Correct Range-Aided SLAM	[Paper] [Code]
2026	ICRA	Implementing Robust M-Estimators with Certifiable Factor Graph Optimization	[Paper] [Code]
2026	arXiv	Certifiable Estimation with Factor Graphs	[Paper]

Moment-SOS Relaxation for Pose Graph Optimization

Year	Venue	Paper	Links
2019	ICRA	Guaranteed Globally Optimal Planar Pose Graph and Landmark SLAM via Sparse-Bounded Sums-of-Squares Programming	[Paper]

Other Relaxation for Pose Graph Optimization

Year	Venue	Paper	Links
2015	ICRA	A Convex Relaxation for Approximate Global Optimization in Simultaneous Localization and Mapping	[Paper]
2023	ICRA	SCORE: A Second-Order Conic Initialization for Range-Aided SLAM	[Paper] [Code]

Bundle Adjustment

Shor's Relaxation for Bundle Adjustment

Year	Venue	Paper	Links
2025	RSS	Building Rome with Convex Optimization	[Paper] [Code] [Project]

Other Global Method for Bundle Adjustment

Year	Venue	Paper	Links
2016	ECCV	Projective Bundle Adjustment from Arbitrary Initialization using the Variable Projection Method	[Paper]
2018	CVPR	pOSE: Pseudo Object Space Error for Initialization-Free Bundle Adjustment	[Paper]
2023	CVPR	expOSE: Accurate Initialization-Free Projective Factorization using Exponential Regularization	[Paper]
2024	ECCV	Power Variable Projection for Initialization-Free Large-Scale Bundle Adjustment	[Paper] [Code]
2025	arXiv	Towards Initialization-free Calibrated Bundle Adjustment	[Paper]

Companion Tutorial Code

We provide practical tutorial code demonstrating how to formulate and solve convex relaxations for representative geometric vision problems. These tutorials are designed to be easy to use and educational, showing the step-by-step process from problem formulation to certification of global optimality.

💡 This is a unique feature of our repository — most survey repos do not include hands-on tutorial code!

Available Examples

The tutorials use the SPOT package developed by the Computational Robotics Group at Harvard University, which provides symbolic formulation of polynomial optimization problems and automatic generation of semidefinite programming (SDP) relaxations. For installation, documentation, and citation information, please visit the SPOT package.

Current tutorials include:

PnP (Perspective-n-Point): Outlier-free pose estimation with quadratic cost
Outlier-Robust Wahba: Rotation estimation with truncated least squares (TLS) cost and sparse Moment-SOS relaxation
Vanishing Point Estimation: With outlier handling capabilities

Key features:

🔧 Plug-and-play: Symbolically define problems using SymPy, SPOT handles the rest
🎯 Certifiable: Automatic extraction of solutions and global optimality verification
📚 Educational: Clear examples showing formulation, relaxation, and certification
⚡ Scalable: Sparse Moment-SOS formulations handle realistic problem sizes

Getting Started

Tutorial Repository: SPOT GeometricVision Examples

Quick start:

Install SPOT and its dependencies (MOSEK, SymPy)
Run example scripts (e.g., sdp_pnp.py, example_outlier-robust_wahba.py)
Modify for your own problems following the provided templates

Example usage (PnP):

import sympy as sp
from spot import SPOT

# Define problem symbolically
rotation = sp.symbols('r11:34')  # 3x3 rotation matrix
translation = sp.symbols('t1:4')  # 3D translation vector

# Define constraints (orthonormality, etc.)
# SPOT automatically generates SDP relaxation

# Solve and certify
result = spot_solver.solve()
is_optimal = verify_global_optimality(result)

Other Resources

Workshops

Year	Venue	Title	Links
2024	RSS	Frontiers of Optimization for Robotics	[Website]
2026	ICRA	Frontiers of Optimization for Robotics	[Website]

Tutorials

Year	Venue	Title	Links
2019	ICCV	Global Optimization for Geometric Understanding with Provable Guarantees	[Website]
2020	RSS	Certifiable Robot Perception: from Global Optimization to Safer Robots	[Website] [Video]
2020	CVPR	RANSAC in 2020	[Website]
2025	ICCV	RANSAC in 2025	[Website]

Lectures

Title	Links
Semidefinite Optimization and Relaxation	[Website]

Talks & Seminars

Title	Links
Towards Globally Optimal State Estimation	[Video]
Certifiable Outlier-Robust Geometric Perception	[Video]

🤝 Contributing

We welcome contributions from the community! If you'd like to add papers, fix errors, or suggest improvements:

Submit a Pull Request: Follow our PR guide
Open an Issue: Report errors or suggest new papers via GitHub Issues
Email us: ericzzj89@gmail.com

Acknowledgements

We thank all the researchers whose work is featured in this survey and repository. Special thanks to the Computational Robotics Group at Harvard University for developing the SPOT package used in our companion tutorial code.

Name		Name	Last commit message	Last commit date
Latest commit History 392 Commits
assets		assets
LICENSE		LICENSE
README.md		README.md
how-to-PR.md		how-to-PR.md

Year	Venue	Paper	Links
2014	arXiv	Semidefinite Descriptions of the Convex Hull of Rotation Matrices	[Paper]
2015	J. Guid. Control Dyn.	Linear-Matrix-Inequality-Based Solution to Wahba's Problem	[Paper]

Folders and files

Latest commit

History

Repository files navigation

Awesome Global Solvers for 3D Vision

Advances in Global Solvers for 3D Vision: A Comprehensive Survey

🏠 Introduction

🔥 News

📝 Citation

📖 Table of Contents

Theory

Branch-and-Bound (BnB)

Foundational Papers

General Frameworks for Multiple Tasks

Shor's Relaxation

Foundational Papers

General Frameworks for Multiple Tasks

Moment-SOS Relaxation

Foundational Papers

General Frameworks for Multiple Tasks

Other Relaxation Techniques

Graduated Non-Convexity (GNC)

Robust Variants: Adaptive Trimming (ADAPT)

Consensus Maximization

Application

Wahba Problem

BnB for Wahba Problem

Shor's Relaxation for Wahba Problem

Other Relaxation for Wahba Problem

Robust Preprocessing

Vanishing Point Estimation

BnB for Vanishing Point Estimation

Shor's Relaxation for Vanishing Point Estimation

Absolute Pose Estimation (PnP)

BnB for PnP

Shor's Relaxation for PnP

Moment-SOS Relaxation for PnP

Other Relaxation for PnP

GNC for PnP

Relative Pose Estimation

BnB for Relative Pose Estimation

Shor's Relaxation for Relative Pose Estimation

Moment-SOS Relaxation for Relative Pose Estimation

Other Relaxation for Relative Pose Estimation

3D Registration

BnB for 3D Registration

Shor's Relaxation for 3D Registration

Other Relaxation for 3D Registration

GNC for 3D Registration

Robust Preprocessing for 3D Registration

Rotation Averaging

Shor's Relaxation for Rotation Averaging

Moment-SOS Relaxation for Rotation Averaging

Other Relaxation for Rotation Averaging

Translation Averaging

Shor's Relaxation for Translation Averaging

Other Relaxation for Translation Averaging

Translation Averaging with Structure (a.k.a. Known Rotations)

Triangulation

BnB for Triangulation

Shor's Relaxation for Triangulation

Other Relaxation for Triangulation

Pose Graph Optimization

Shor's Relaxation for Pose Graph Optimization

Moment-SOS Relaxation for Pose Graph Optimization

Other Relaxation for Pose Graph Optimization

Bundle Adjustment

Shor's Relaxation for Bundle Adjustment

Other Global Method for Bundle Adjustment

Companion Tutorial Code

Available Examples

Getting Started

Other Resources

Workshops

Tutorials

Lectures

Talks & Seminars

🤝 Contributing

Acknowledgements

⭐ Star History

Packages