Interior-Point Local Refinement for RANSAC: Keeping Camera Estimates Physically Valid

Robust camera estimation works by guessing and checking. RANSAC (random sample consensus) repeatedly picks a minimal random subset of point matches, solves for candidate camera models with a minimal solver (a hand-built polynomial routine that runs in microseconds), counts how many matches agree with each candidate, and then polishes the best candidates with a short continuous optimization called local optimization (LO). The solver community has worked hard on making the guessing step fast and on discarding physically impossible answers early. The polishing step, however, is still unconstrained. Nothing stops it from sliding into a camera with negative focal length, a lens-distortion coefficient that folds the image over itself, or a pose that puts inlier points behind the camera. This proposal makes the polishing step respect physics. We replace unconstrained Levenberg–Marquardt or reweighted least squares with a small interior-point refinement: a logarithmic barrier, a penalty that grows to infinity at the edge of the allowed region, with its push scaled by a parameter $\mu$, keeps every iterate strictly inside the allowed region. The work is engineered so that it adds only tens of microseconds per call.

Two results from outside vision make this practical rather than academic. A one-shot barrier with a single small $\mu$ is enough for near-optimal complexity, so no outer loop that gradually shrinks $\mu$ is required. Separately, a smooth "barrier extension" can start from slightly infeasible points, which happen constantly when pixel noise flips a near-plane point to negative depth. Before building anything, though, we must first measure whether unconstrained refinement actually produces infeasible models often enough to matter. That measurement is the first deliverable, and a negative answer would redirect the project.

Core Claim

For refinement problems where the feasible set couples many variables, the main case being cheirality (every inlier point must have positive depth $z_i(\theta)>0$ in every camera, where $\theta$ collects pose, focal length and distortion), a fixed-$\mu$ barrier-extension Gauss–Newton step solves the same small dense linear system as Levenberg–Marquardt, plus cheap diagonal and rank-$N$ terms. It should therefore cost about the same per iteration. We claim it removes most physically invalid final models on hard data (wide baselines, fisheye lenses, near-planar scenes) and lowers pose error there, without hurting easy data. The objective refined around each RANSAC hypothesis is

$$ \Phi(\theta) = \sum_{i} w_i\,\rho\big(r_i(\theta)\big) \;+\; \mu\Big[\sum_{i \in \mathcal{I}} \psi\big(z_i(\theta)\big) + \psi\big(f-f_{\min}\big) + \psi\big(f_{\max}-f\big) + \psi\big(1+\lambda r_{\max}^2\big)\Big]. $$

The symbols are as follows. $r_i$ is the reprojection or Sampson residual of match $i$. $\rho$ and $w_i$ are the robust kernel and weights used by MAGSAC++. $\mathcal{I}$ is the set of matches whose weight exceeds a threshold. $f$ is focal length. $\lambda$ is the division-model distortion coefficient, and $r_{\max}$ is the largest image radius, so the last term keeps the undistortion map one-to-one over the image. $\psi(s)$ is the log-barrier extension of Constrained Deep Networks: Lagrangian Optimization via Log-Barrier Extensions: it equals $-\ln s$ inside the region and continues as a steep linear function once $s$ falls below a small positive threshold.

The novelty is not "barriers exist." The new elements are three. We apply them to coupled geometric inequalities inside a microsecond-scale robust-estimation loop. We use the one-shot result to drop the $\mu$ schedule. We give an analysis of when the barrier's guarantees actually transfer to camera geometry.

Relation to Prior Work

Prior work on minimal solvers motivates the proposal by showing that physical admissibility pays off in speed. Making minimal solvers fast converts the solver's action matrix into a characteristic polynomial and uses Sturm sequences to extract only roots inside a known interval. Real-Time Solution to the Absolute Pose Problem with Unknown Radial Distortion and Focal Length gets a 2 µs P5Pfr solver that returns a mean of 1.7 real solutions. Both prune at the solver stage, and both handle only a single scalar variable or the minimal sample. Neither touches the refinement over hundreds of inliers, which is where this proposal acts. Related elimination work, A Clever Elimination Strategy for Efficient Minimal Solvers, A Sparse Resultant Based Method for Efficient Minimal Solvers and Efficient Solution of Point-Line Absolute Pose, shrinks solver templates. It sets the time scale we must respect, but it is orthogonal to our contribution.

The robust-estimation baseline we modify is MAGSAC++, a Fast, Reliable and Accurate Robust Estimator. It refines models by reweighted least squares under a marginalized noise kernel, with no feasibility constraints. We keep its weights and kernel and change only the refinement geometry.

Three optimization results supply the method. A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees proves that a single small $\mu$ suffices for bound-constrained nonconvex problems. We borrow the fixed-$\mu$ design. We do not borrow its Hessian-free conjugate-gradient machinery, because our problems have 6 to 10 unknowns and a dense solve is cheaper. Claiming high-dimensional relevance here would be dishonest. The log-barrier extension paper supplies infeasible-start handling, and it reports the barrier extension clearly beating penalties (Dice 0.945 vs 0.712 for quadratic penalties on synthetic circles). That evidence comes from segmentation, so it motivates our approach but does not settle the question for vision geometry.

On convex optimization without convex representation constrains what we may claim. Barrier stationary points converge to global minimizers when the feasible set is convex and constraint gradients do not vanish on its boundary, even if the individual constraints are not concave. For absolute pose with fixed rotation, each depth $z_i = r_3^\top X_i + t_3$ is linear in translation, with gradient never zero. The cheirality set in translation is therefore a convex polyhedron, and Lasserre's theorem applies on these slices. Relative pose has no such structure: triangulated depths are nonlinear in $(R,t,f)$. We treat it as the case where spurious interior stationary points may appear, and we measure them.

GeLoc3r: Enhancing Relative Camera Pose Regression with Geometric Consistency Regularization adds geometric consistency to a pose-regression network only at training time. It is a different paradigm with no hard inference-time constraints, and we use it only as context.

Research Program

The first stage is a measurement study, and the go/no-go decision rests on it. We instrument MAGSAC++'s refinement and a standard Levenberg–Marquardt refinement on relative pose with unknown focal length and on absolute pose with focal length and distortion. We record how often an intermediate or final refined model violates any constraint. The constraints checked are positive depth for inliers, focal bounds, and one-to-one distortion. We also record how often the violation changes the winning model or worsens its error. If violations of final models occur in well under one percent of frames, and also on the hard subsets, the claim fails. In that case we narrow the project to the cases where violations do occur (we expect fisheye distortion and focal estimation near-planar scenes) or stop.

The second stage builds the refiner in C++. Each iteration forms the Gauss–Newton normal matrix of the robust residual term and adds the barrier's gradient and curvature. For the cheirality terms the curvature is a sum of rank-one outer products of depth gradients, which is cheap because the parameter dimension is small. A backtracking line search rejects steps that cross the extension threshold. Then $\mu$ is fixed per problem class, scaled to the residual magnitude so that a fixed $\mu$ biases the optimum by an amount comparable to pixel noise. The one-shot theory sets the form of this choice, but not its constant, which we tune on held-out synthetic data. Matches that remain in the infeasible linear part of the extension after convergence are reported as cheirality outliers and removed from $\mathcal{I}$. This recognizes that a match putting a point behind the camera is evidence against that match.

The third stage is analysis. On synthetic scenes we sample many starting points around the truth and count distinct interior stationary points of the barrier objective. We compare absolute pose with rotation held fixed (convex feasible set in translation, where Lasserre predicts no spurious minima) against full relative pose (nonconvex). This is the empirical answer to whether barrier guarantees transfer to camera geometry.

Baselines

The naive reference point is MAGSAC++ with no local refinement at all, using raw minimal-solver hypotheses scored by the robust kernel. It shows how much any refinement contributes.

The strongest existing method is MAGSAC++ with its native reweighted-least-squares refinement, as described in MAGSAC++, a Fast, Reliable and Accurate Robust Estimator. It is the strongest competitor because it is both the fastest and the most accurate published robust estimator in the file. The paper reports KITTI processing time dropping from about 117 ms to 8 ms relative to the original MAGSAC, and median error on Tanks and Temples falling from 6.3 px for RANSAC to 3.9 px. For ExtremeView the paper gives no numeric accuracy: no reported result found on Lacuna for an ExtremeView error value. We rerun MAGSAC++ ourselves on the same matches, with the same minimal solvers, sampler, iteration cap and wall-clock budget. Only the refinement routine differs. Its hyperparameters get the same tuning budget on the same held-out split as ours. Beating it means fewer infeasible final models and lower pose error (rotation, translation, focal) on the hard subsets, with no statistically significant regression on the easy subsets, and with total per-frame time within 10 percent.

A second strong baseline is Levenberg–Marquardt with a revert rule. It refines unconstrained, checks cheirality and bounds at the end, and falls back to the unrefined hypothesis if the check fails. This is the cheapest honest way to guarantee valid output.

Two ablations isolate the key ingredient. In the first, the barrier is replaced by a quadratic penalty with equal tuning, which tests whether interior-ness itself matters or any constraint-aware term would do. In the second, the classical barrier is used without the extension, with infeasible starts discarded, which tests the value of infeasible-start handling. We also ablate a decreasing $\mu$ schedule against fixed $\mu$, to check that the one-shot design costs nothing in accuracy.

Why not just…?

Why not just reject infeasible models after refinement and keep the pre-refinement hypothesis? This is a real threat, because it is nearly free and guarantees validity. Its weakness is that it throws away refinement exactly on the frames that needed it most, leaving the coarse minimal-sample estimate. The Levenberg–Marquardt-with-revert baseline tests this directly. If it matches our pose error on the hard subsets, the barrier adds nothing, and we will report that.

Why not just reparameterize or clamp, for example optimizing $\log f$ and clamping $\lambda$? For simple bounds on focal length and distortion this is a perfectly good answer, and we will use it as the bound-handling component of a baseline. It cannot express cheirality, which is a joint condition on pose across hundreds of points, not a bound on any one variable. Clamping coupled quantities also breaks the gradient flow, which the boundary-oscillation results in Solving Constrained Variational Inequalities via a First-order Interior Point-based Method warn about. The experiments separate bound violations from cheirality violations, so it will be clear whether the barrier's value comes only from the coupled constraints.

Why not just keep MAGSAC++'s unconstrained refinement, since it is already accurate? If infeasible refinements are rare, this is the right answer. The stage-one measurement exists to find out. The proposal proceeds only on problem classes where violations measurably change the selected model.

Why not just use a quadratic penalty? A penalty lets iterates cross into the invalid region and then pulls them back. That is fine if the objective is benign over there, but harmful if residuals become meaningless behind the camera. The penalty ablation answers this. The segmentation evidence favoring barrier extensions over penalties suggests the barrier wins, but that evidence is not geometric and we do not rely on it.

Proposed Experiments

Synthetic experiments follow the random-cube protocol of Making minimal solvers fast and the 10,000-scene relative-pose setting with focal lengths in $[0.5, 5]$ of A Clever Elimination Strategy for Efficient Minimal Solvers. We add controlled stressors: outlier ratio, pixel noise, near-planar point layouts, and a forward-motion bias that puts many points near the camera plane. This is where we measure violation rates, stationary-point counts, and microseconds per refinement call against the 2 µs P5Pfr solver and the roughly 14 µs five-point solver as time references.

Real data covers KITTI, Tanks and Temples and ExtremeView for relative pose and fundamental-matrix fitting, following the MAGSAC++ protocol. The GoPro fisheye footage from the P5Pfr paper serves absolute pose with distortion. HPatches and the Grossmünster fisheye images serve distorted homographies, using the 0.6 µs solver of Radially Distorted Homographies, Revisited as the hypothesis generator. Metrics are fraction of frames with an infeasible final model, rotation and translation error with AUC at standard thresholds, focal and distortion error where ground truth exists, median reprojection error, and total time per frame.

The decisive check is a single comparison. On a pre-registered hard subset, defined before running our method as frames where unconstrained refinement produced a violation, barrier refinement must lower pose error relative to both MAGSAC++ and Levenberg–Marquardt-with-revert. On the complementary easy subset it must be statistically indistinguishable from them, and per-call refinement cost must stay within a small constant factor of Levenberg–Marquardt. If revert matches us on the hard subset, the project's conclusion is that feasibility checks belong at the end, not inside the optimizer.