Camera pose estimation from 2D-to-3D feature correspondences is a fundamental problem in computer vision. Existing methods typically decompose this into two sequential steps: first establishing correspondences, then estimating the pose robustly using RANSAC or similar methods. This paper proposes a globally-optimal method that simultaneously solves for camera pose and feature correspondences by maximising the cardinality of the inlier set. The approach uses a branch-and-bound algorithm over the space of camera rotations, guaranteeing a globally-optimal solution without requiring initial correspondences.

The Perspective-n-Point (PnP) problem — estimating camera pose from n 2D-3D point correspondences — is central to visual localisation, structure-from-motion, and augmented reality. Standard pipelines first extract and match local features (e.g., SIFT, ORB), then apply RANSAC to find an inlier set consistent with a geometric model. However, the quality of the initial correspondences critically affects the final pose accuracy, and RANSAC provides only probabilistic guarantees of finding the optimal solution.

The authors argue that decoupling correspondence estimation from pose estimation is suboptimal because errors in the first stage propagate irreversibly to the second. They propose to jointly optimise both problems by searching for the camera pose that maximises the number of geometrically consistent feature matches. This formulation naturally handles ambiguous and many-to-many correspondences that arise in practice, particularly in scenes with repetitive structures or textureless regions.

RANSAC and its variants (PROSAC, LO-RANSAC, USAC) remain the dominant paradigm for robust estimation in geometry problems. These methods randomly sample minimal sets, compute model hypotheses, and evaluate consensus. While highly practical, they lack deterministic optimality guarantees. Branch-and-bound (BnB) methods have been applied to rotation search and registration problems, providing certifiable global optimality. However, prior BnB approaches for pose estimation require known correspondences as input.

Given a set of 2D image features and a set of 3D scene points, the goal is to find the camera rotation R and translation t that maximise the number of geometrically consistent 2D-3D matches. A match is considered an inlier if the reprojection error is below a threshold. Unlike standard PnP, the correspondences are not given a priori — the method must determine them simultaneously with the pose. The search space is the rotation group SO(3), with translation solved analytically for each rotation candidate.

The rotation space SO(3) is parameterised using the angle-axis representation and partitioned into nested cubes in the pi-ball. For each rotation subcube, an upper bound on the inlier count is computed by relaxing the geometric consistency constraint. The branch-and-bound algorithm recursively subdivides the most promising subcubes and prunes those whose upper bound is below the current best solution. This guarantees convergence to the globally-optimal rotation — the one that admits the largest inlier set — without exhaustive enumeration.

A critical component is the upper bound computation. For a given rotation subcube, the bound counts the maximum number of potentially consistent matches by considering the worst-case reprojection within the angular uncertainty of the subcube. The bound is tight in the sense that it converges to the true inlier count as the subcube shrinks. Additionally, the authors introduce efficient data structures and early termination criteria to accelerate the search in practice, achieving runtimes from seconds to minutes depending on problem size.

Experiments are conducted on both synthetic data with controlled noise levels and real datasets for visual localisation. On synthetic data, the method consistently finds the true globally-optimal solution, while RANSAC-based methods occasionally miss it, especially under high outlier ratios (above 80%). On real localisation benchmarks, the approach achieves higher pose accuracy than state-of-the-art methods, particularly in challenging scenarios with repetitive textures and wide baselines. The runtime scales reasonably with problem size, making the method suitable for offline applications requiring high reliability.

This paper presents a globally-optimal approach to simultaneously estimating camera pose and feature correspondences by maximising the inlier set cardinality over the rotation space using branch-and-bound. The method provides deterministic optimality guarantees that RANSAC-based approaches cannot offer. Experiments demonstrate superior accuracy in challenging scenarios with high outlier ratios and ambiguous correspondences. The work opens avenues for certifiable algorithms in geometric vision tasks where reliability is paramount.