Translation Averaging as Global Discrete Inference on the Sphere

Reconstructing a scene from images requires knowing where each photo was taken. Once camera orientations are fixed, the remaining step is translation averaging: estimating all camera positions given, for many camera pairs, the unit-length direction from one camera toward the other. These directions come from imperfect image matching, so a large fraction are not merely noisy but completely wrong (outlier). Existing solvers break down because none decides which measurements to trust: convex relaxations tolerate roughly a third of wrong directions, and robust local optimisers only refine their initial guess. Discrete optimisation is the classical remedy (give each variable a finite set of candidates and search globally for the combination explaining the most data, so the correct majority outvotes the wrong minority) but it needs a bounded candidate set, and camera positions live in unbounded 3D space. Our key idea is to change the question. A camera's position is unbounded, but the direction in which it is seen from a fixed reference point lies on the unit sphere, a bounded surface we cover with a fixed grid of cells. We plant $K$ reference points and, for each, globally assign to every camera the cell in which it appears from that point. Each assignment pins every camera to a ray, and robustly intersecting a camera's $K$ rays returns its 3D position. The proposed solver halves the median error of state-of-the-art solvers on synthetic graphs, and widens that margin to $4$–$6\times$ at the outlier levels where convex relaxations break down. As a drop-in replacement for the global-positioning stage of the GLOMAP structure-from-motion pipeline, it improves or matches GLOMAP on every benchmark we test, wins end-to-end on ETH3D even after bundle adjustment, and, unlike its randomly initialised competitors, returns the same solution on every run. The code will be made public.