When a robot or a camera rig rebuilds a scene one frame at a time, small errors in each frame-to-frame motion estimate add up. A straight corridor slowly bends, and when the camera comes back to where it started, the map does not meet itself. The standard fix is to add "loop closures", which are measurements linking the current frame to a much earlier one, and then solve for all poses together. That fix only works if the loop closures are correct. Appearance matching often produces false ones, and one false closure can wreck a map. Deciding which measurements to trust is a discrete yes/no choice for every edge of the pose graph, the network whose nodes are camera poses and whose edges are measured relative motions. Current methods make that choice with continuous surrogates such as robust losses, annealing, or message passing, and none of them can say whether they made it correctly.
We propose to treat loop-closure selection as an integer program and to make it work by studying its relaxation gap: the difference between the best fractional solution, which is easy to compute, and the best yes/no solution, which is what we want. Each edge gets a binary trust variable. Every cycle whose composed rotation fails to return close to the identity must contain at least one distrusted edge. The key observation is that drift links the two research directions. The cycles that carry the most evidence are long loops, because those are the ones that reveal accumulated drift. Long loops are also where the fractional relaxation is least informative: it can spread a tiny fraction of "distrust" over many edges and satisfy every inconsistent cycle without naming a culprit. We propose cutting planes and a separation procedure built for this long-cycle regime. The output is a selected inlier set together with a lower bound on how many measurements must be wrong. When that bound matches the solution found, the selection is certified.
Core Claim
The claim has three parts. First, discrete outlier selection on pose graphs and camera graphs, written as a weighted cover of inconsistent cycles, can be tightened enough that its fractional bound certifies the selected inlier set on realistic graphs. Second, the consistency threshold for a cycle has to grow with cycle length, because legitimate measurement noise accumulates along a loop. Third, getting both the threshold and the tightening right matters most on the sparse, corridor-like graphs where existing global methods break down.
The formulation is as follows. Let $x_e \in \{0,1\}$ indicate that edge $e$ is trusted, and let $w_e > 0$ be the prior cost of distrusting it. Odometry edges get a high cost and appearance-based loop closures a low one. Let $R_C$ be the rotation obtained by composing the measured relative rotations around cycle $C$. The problem is
$$\min_x \sum_e w_e (1 - x_e) \quad \text{s.t.} \quad \sum_{e \in C} (1 - x_e) \ge 1 \;\; \text{for every cycle } C \text{ with } \angle(R_C) > \tau(|C|),$$
where $\angle(R_C)$ is the rotation angle of $R_C$ and $\tau(|C|) = \kappa \sigma \sqrt{|C|}$. Here $\sigma$ is the per-edge rotational noise level and $\kappa$ sets the confidence level. The $\sqrt{|C|}$ comes from treating small independent per-edge rotation errors as a random walk along the loop. Because systematic drift grows closer to linearly, we will also test a linear threshold.
There are exponentially many cycle constraints, so they are added lazily. This is how subtour constraints are handled in routing problems. Once the trusted set is fixed, rotations and translations are estimated with the two-stage scheme whose rotation step Convex Relaxations for Pose Graph Optimization With Outliers found empirically tight.
Relation to Prior Work
Three papers motivate the proposal by documenting where continuous methods leave the discrete problem unresolved. Convex Relaxations for Pose Graph Optimization With Outliers relaxes robust pose graph optimization to a semidefinite program, a convex problem over positive semidefinite matrices. It finds the one-stage relaxation that handles outliers jointly is not tight in practice, while the rotation-only stage is tight. It also reports that general-purpose solvers do not scale past about 50 poses. We keep its tight rotation stage. We move the outlier decision, the part where its relaxation fails, into a combinatorial program that linear and integer solvers can handle at scale.
TEASER shows that tightness at extreme outlier rates is achievable for pairwise registration. It does this by pruning correspondences with a maximum-clique search on a compatibility graph, followed by a certified rotation solve. Our cycle cover plays the same role across a whole trajectory: it is a discrete pruning step over multi-step loops rather than within a single pairwise alignment.
Graduated Non-Convexity for Robust Spatial Perception anneals from a convex surrogate toward the true robust cost. It works well on INTEL and CSAIL, but its authors concede it is a heuristic with no certificate, and it never measures the gap between its surrogate and the discrete inlier assignment. We aim to produce exactly that measurement.
On the camera-graph side, three global methods replace incremental chaining with joint solves. Cycle-Sync runs message passing over 3-cycles. Global Fusion of Relative Motions uses an $l_\infty$ linear program over camera triplets, wrapped in RANSAC (random sampling to reject outliers). A Global Linear Method for Camera Pose Registration solves a triplet null-space system. All three depend on dense short cycles, and Cycle-Sync explicitly degrades when 3-cycles are rare. Our formulation uses cycles of any length with a length-aware threshold, so it targets exactly the forward-moving and corridor graphs these methods handle badly. These papers therefore constrain where we must show a gain.
The discrete-optimization literature supplies the tightening machinery. Improved Encodings of Acyclicity shows that encodings based on vertex elimination and feedback vertex sets shrink weak acyclicity relaxations toward the integer hull, solving 184/588 optimization instances against 124/588 for the older translation. Our cycle cover is a feedback-set-type problem, so these encodings are a natural source of extended formulations. Multi-cover inequalities shows how to strengthen a relaxation by reasoning over groups of overlapping covering constraints. We adapt that idea to bundles of long loops that share a corridor segment. A New Relaxation for Tree-Based Problems uses dynamic programs over paths with limited "memory" (ng-arbs) that forbid short repeated cycles cheaply. We reuse this design to separate violated long cycles, meaning to find them efficiently without enumerating all cycles. Finally, Machine Learning for Optimization-Based Separation of MIR Cuts shows that a learned filter on the separation problem can match or beat full separation in gap closed. We hold this in reserve in case separation becomes the bottleneck.
Research Program
The work has three parts, and the first is a measurement that can stop the project early.
The first part asks whether the relaxation gap is real. We would build the cycle-cover program on synthetic grid and Manhattan pose graphs and on INTEL and CSAIL, injecting false loop closures at controlled rates and with controlled loop lengths. For each instance we record four things: the fractional bound, the integer optimum, the fraction of edges left fractional, and the root-node gap after a commercial solver's generic cuts. The hypothesis is that the gap and the number of fractional edges grow with loop length and with the number of false closures that share a corridor segment. If generic solver cuts already close the gap, the cutting-plane part of the project is dropped. The contribution then becomes the formulation, the drift-aware threshold, and the certificate, and the proposal says so.
The second part, which applies only if the gap is real, develops problem-specific tightening. One family of cuts composes two inconsistent cycles that share a path. When cycles $C_1$ and $C_2$ overlap on a segment $P$ and their symmetric difference is itself inconsistent, an inequality over $C_1 \cup C_2$ excludes the fractional solution that puts weight only on $P$. A second family is multi-cover inequalities for corridor bundles. Separation is posed as a search for a cycle that has low current fractional distrust but large composed-rotation error. Because rotation composition is not additive, we approximate the rotation error with an ng-memory dynamic program over a discretized rotation state. The memory forbids short revisits, which are the cycles that cause false violations.
The third part delivers the certificate and integrates it into a mapping pipeline. The optimality gap reported by the integer solver is published per map region. The inlier set is then passed to the two-stage pose solve. We test whether a nonzero certified gap predicts large final trajectory error. If it does, the gap becomes a usable trigger for an online system: the system can hold back a loop closure until its region is certified.
Baselines
The naive reference point is incremental reconstruction with periodic global bundle adjustment, meaning a joint nonlinear refinement of all poses and points, as in COLMAP Structure-from-Motion Revisited. It reports a median pose error of 0.85 m on Quad, against 0.89 m for VisualSFM and 1.01 m for Bundler. It runs on raw images with its own verification, so on SfM benchmarks we compare final camera-location error against ground truth. Matching its accuracy while producing a certificate is the minimum bar. Beating it on long-loop and corridor subsets is the real test.
The strongest pose-graph competitor is graduated non-convexity applied to pose graph optimization Graduated Non-Convexity for Robust Spatial Perception, which is reported robust to 70 to 80% outliers on INTEL and CSAIL. The file contains no precision or recall figure for its outlier detection, so we will compute those ourselves. GNC and our method get identical relative measurements, the same noise model $\sigma$, and the same downstream translation solver. GNC's truncation threshold and our $\kappa$ are tuned on the same held-out graphs. We count it as beaten if we achieve higher outlier-detection F1, lower trajectory error at outlier rates above 70%, or a certificate on instances where both reach the same answer, all within a matched wall-clock budget.
The strongest camera-graph competitor is Cycle-Sync. It reports a median location error below 0.05 on ETH3D, about 70% improvement over LUD, and exact recovery with up to 80% of edges corrupted in synthetic tests. We run it on the same 1DSfM and ETH3D relative-pose graphs we feed our method. We count it as beaten if we match it on dense graphs and reduce location error on sparsified, corridor-like versions of the same graphs where 3-cycles are rare. We will not claim a win on the dense graphs unless the numbers show one.
The two-stage semidefinite solver of Convex Relaxations for Pose Graph Optimization With Outliers serves as a gold reference on graphs with fewer than 50 poses, where it runs. It tells us whether our discrete selection loses accuracy relative to a fully convex treatment.
Three ablations isolate the key ingredients. The first is the cycle-cover program solved by the integer solver with lazy cycle constraints and only its generic cuts, which isolates our cutting planes. The second uses a fixed, length-independent consistency threshold, which isolates the drift-aware $\tau(|C|)$. The third keeps only 3-cycles, which isolates the value of long loops and connects our results directly to Cycle-Sync's limitation.
Why not just…?
Why not just run graduated non-convexity, which already handles 70 to 80% outliers? This is the most serious threat. On well-connected graphs GNC may match our accuracy at a fraction of the cost. The difference is that GNC returns no certificate, and its own authors call it a heuristic. Our gap measurements will show directly whether GNC's chosen inlier set is the discrete optimum, and how often it is not as loop length grows. If GNC's selections turn out to be almost always optimal, the remaining contribution is the certificate alone. We will report it that way.
Why not just use cycle-consistency message passing or a triplet linear solver? Cycle-Sync and A Global Linear Method are fast and accurate when short cycles are plentiful, and both degrade when they are not. Global Fusion of Relative Motions has to be wrapped in RANSAC because its continuous objective admits false triplets. The 3-cycle-only ablation, run on the sparsified graphs, will show whether long-loop evidence is what makes the difference.
Why not just hand the naive cycle-cover program to an integer solver and stop? This may well be enough. That is why it is the first ablation and why the gap measurement comes first. Our cuts have to earn their place by reducing root gap, node count, or solve time on long-loop instances. If they do not, we drop them.
Why not just use incremental reconstruction with periodic bundle adjustment? On Castle, Global Fusion of Relative Motions reports 66 to 300 mm error for incremental systems, compared with 22 to 25 mm for its global method, along with loop-closure failures. Bundle adjustment started from a drifted state is a local method and can settle into a wrong solution. Our corridor experiments test this case directly.
Proposed Experiments and Decisive Checks
The first decisive check is the gap study on synthetic Manhattan graphs, INTEL, and CSAIL. It plots root gap and fractional-edge count against loop length and false-closure overlap, with and without our cuts. A flat curve would falsify the motivation for the cutting planes.
The second check is accuracy and certification on 1DSfM, ETH3D, and their sparsified corridor variants, compared against Cycle-Sync, GNC, and COLMAP. We report median location error, outlier F1, certified fraction, and runtime. We will also run Strecha Castle, where the loop-closure numbers from Global Fusion of Relative Motions give a fixed reference point.
The third check tests whether the certificate is useful in practice. Across all instances we test whether a nonzero certified gap predicts trajectory error above a fixed threshold, measured by the area under the ROC curve (AUC). An AUC near chance would mean the certificate is mathematically valid but useless as a drift alarm. A clearly better-than-chance AUC would justify using it to gate loop closures online.
The fourth check compares the square-root threshold with a linear one. Its result tells us whether real drift on these benchmarks behaves like accumulated random noise or like systematic bias, which bears directly on how sequential error accumulation should be modeled.
References
- Convex Relaxations for Pose Graph Optimization With Outliers
- TEASER: Fast and Certifiable Point Cloud Registration
- Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection
- Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization
- Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion
- A Global Linear Method for Camera Pose Registration
- Improved Encodings of Acyclicity for Translating Answer Set Programming into Integer Programming
- Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
- A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees
- Machine Learning for Optimization-Based Separation of Mixed-Integer Rounding Cuts
- Structure-from-Motion Revisited