Hedged Global Registration: Keeping 2D Mistakes Out of Certified 3D Alignment

Aligning two partial 3D scans of the same place means finding the rotation and translation that bring them into register. With no starting guess, this is a global search. There are exact methods for it, which search the whole space of poses and prove that no pose scores better than the one returned. These methods are geometric: they break down when the scans overlap only a little, or when the scene is made of flat walls that look the same from many poses. Cameras can resolve that ambiguity, because a door and a wall with the same shape are easy to tell apart in color. The difficulty is that camera evidence comes from a 2D network, and that network is sometimes wrong. If its outputs are treated as fact, a single wrong label can steer an exact search to a confidently wrong answer. The proof of optimality then certifies the wrong thing.

This note proposes a global registration method in which each 3D point carries a small calibrated set of possible semantic labels from the 2D segmenter, rather than one label. The search also scores a physical constraint, that an aligned scan must not place surfaces in space the other sensor saw as empty, and this constraint enters the search's bounds directly. It is not used only as an afterthought filter. The claim, stated plainly, is that errors in the 2D input can then shift the certified optimum only by an amount set by a chosen error rate $\delta$. As the segmenter gets worse, the method should fall back to geometry-only performance instead of failing outright. Meanwhile, missing geometry costs nothing, and only contradictions with observed free space are penalized.

Core Claim

Exact registration by branch-and-bound works by repeatedly splitting the space of poses into boxes, bounding the best score achievable inside each box, and discarding boxes whose bound cannot beat the best pose found so far. Go-ICP established this for 3D point sets and supplies our bounding machinery: uncertainty radii for pose boxes and fast lookup tables of distances. GOGMA showed that a correspondence-free density objective is far more robust on partially overlapping laser scans. It reports a 99.7% inlier rate on STAIRS against roughly 20% for Go-ICP. Both use geometry only. Our contribution is an objective that adds uncertain 2D evidence without letting that evidence dictate the answer.

Write $T$ for a candidate pose and $p_i$ for the source points. Each point gets a label set $L_i$, the smallest set of classes whose projected softmax mass exceeds a threshold. That threshold is chosen by conformal calibration (a distribution-free procedure that sets thresholds on held-out data) so that the true class falls in $L_i$ with probability at least $1-\delta$. We maximize

$$J(T)=\sum_i \mathbf{1}\big[d_{L_i}(Tp_i)\le\epsilon\big]\;-\;\lambda\sum_i \mathbf{1}\big[Tp_i\in F\big].$$

Here $d_{L_i}(x)$ is the distance from $x$ to the nearest target point whose label lies in $L_i$, $\epsilon$ is an inlier threshold, $F$ is the free space swept by the target sensor's lines of sight, and $\lambda$ weights violations.

For a pose box with uncertainty radius $r$, an upper bound on $J$ comes from two relaxations. The first loosens $\epsilon$ to $\epsilon+r$. The second subtracts only violations that hold for every pose in the box, meaning the point lies deeper than $r$ inside $F$. Both terms can be read from precomputed distance tables, one per label and one for free space, so the cost per box stays as in Go-ICP. The consequence for 2D errors follows directly. Under the true pose, a true inlier is wrongly discarded only when its true class is missing from its set. So in expectation the true pose loses at most about a $\delta$ fraction of its inliers, whatever the segmenter does elsewhere. With hard argmax labels, that loss has no bound.

Relation to Prior Work

Four lines of prior work bear on this proposal.

The first motivates it. Consensus Maximization for Semantic Region Correspondences runs an exact search over semantic regions (windows, doors) approximated as ellipsoids. It tolerates 75% outlier matches at very low overlap, but it depends entirely on the upstream segmenters: a missed or distorted window drops out of the consensus. The same cascade appears elsewhere. Kim, Xu and Savarese show that 3D recall is capped by 2D detector recall, and they partly escape the cap by keeping several hypothetical foreground masks. Feng et al. find that mesh-and-pose optimization is misled by bad 2D masks. Wei et al. argue that the image context needed to fix an error is thrown away at the 2D-to-3D interface. Our label sets generalize the multiple-hypothesis idea from Kim et al. and give it a calibrated error rate. The search is dense and correspondence-free, where Speciale et al. use a few convex regions.

The second supplies the physical constraint. The Sight View Constraint rejects poses that put source points in the target sensor's observed free space. Used as a filter, it lifts GeoTransformer from 78% to 82% registration recall on 3DLoMatch, and SC2 from 58.6% to 67.7%. It cannot recover a pose that the upstream generator never proposed. We move the same constraint inside the bound, so it prunes whole regions of pose space rather than a list of candidates.

The third is the strongest learned competitor. CoFF fuses per-pixel and per-patch image features into 3D matching. It reaches 95.9% registration recall on 3DMatch and 81.6% on 3DLoMatch, and it beats geometry-only matchers by over 10% on 3DLoMatch_Planar. It offers no global guarantee and assumes exact camera calibration. Label errors at object boundaries and misprojection under occlusion are exactly the failures that would widen our label sets, so our method should soften where CoFF's features are least reliable.

The fourth covers completion methods, XMFnet and CDPNet. These fill in missing geometry from images. XMFnet explicitly identifies intermediate 3D lifting as a source of cascaded error. Both assume the scan and the image are already aligned. We take the opposite stance on incompleteness: we do not hallucinate missing surfaces, and we score only what was actually observed, occupied or empty.

Research Program

The method has three components.

The first component is label sets. A pretrained 2D semantic segmenter runs on each RGB-D frame, and its softmax outputs are projected onto the fragment's points and averaged across frames. The conformal threshold is set on held-out labeled indoor frames at several values of $\delta$. We will report how the set sizes are distributed, and we expect them to grow near object boundaries and under occlusion parallax (a background point projecting onto a foreground pixel).

The second component is free space. We rasterize each target fragment's lines of sight on a sphere around its sensor origin, as the Sight View Constraint does, and precompute a signed distance table into free space.

The third component is the search. It is a nested rotation-then-translation branch-and-bound in the style of Go-ICP, run on the GPU as in GOGMA, over roughly 2–5k downsampled points. It uses the bound above and a local refinement step to tighten the best score.

We will also analyze the theory. The goal is to state and verify empirically the bound on how much the true pose's score can drop. We will also characterize when free-space pruning helps most: we expect this at low overlap, where many wrong poses match a few points by chance but push other points into observed empty space.

Baselines

The naive reference points are Go-ICP and GOGMA run on the same downsampled points with geometry alone. They show what an exact search achieves without images, and they bound the fallback our method should reach when the segmenter is useless.

The strongest existing method is CoFF. Its reported 81.6% registration recall on 3DLoMatch and its reported 3DLoMatch_Planar margin are the numbers to beat. We will rerun its released configuration on our splits so the comparison uses identical fragments and images.

The strongest filter-based competitor is GeoTransformer with the Sight View Constraint, reported at 82% on 3DLoMatch. We will also apply the constraint to CoFF's hypotheses, which gives the strongest version of "good learned matcher plus physics check."

Four ablations isolate the key ingredient. The first is our search with hard argmax labels, which is the cascade-prone version. The second removes semantics entirely. The third drops the free-space term. The fourth applies the free-space term only as a final filter over the top-$k$ poses from the search. All variants share the same point budget, the same time limit per pair, and the same $\epsilon$. $\lambda$ and $\delta$ are tuned on the 3DMatch validation split only, with the same number of trials given to each variant.

Beating the baselines would mean higher registration recall than CoFF+constraint on 3DLoMatch and 3DLoMatch_Planar at equal image input. Failing that, it would mean matching it on average while strictly dominating on the pairs where the learned hypothesis pool contains no correct pose. In the corruption study, success means the hard-label ablation falls below the geometry-only floor while the set-valued method stays at or above it.

Why not just…?

Why not just add the Sight View Constraint to CoFF? This is the most serious threat, since each ingredient already works on its own. The question is how often the correct pose is missing from the candidate pool. We will measure oracle recall, meaning whether any candidate in the pool is correct, for CoFF and GeoTransformer on 3DLoMatch. If oracle recall is close to the achieved recall, the filter approach is enough and our method adds only certification. We will report this honestly and shift the claim to the 2D-corruption regime, where learned hypotheses degrade together with the image features.

Why not just run an exact robust estimator on CoFF's correspondences? Doing so certifies the best pose given the matches, but at low overlap the matches are mostly wrong, and they are wrong in a correlated way when image features fail. Our objective is scored over every point in the scan rather than over a list of matches, so it has no such bottleneck. The comparison can be run directly, and we include it as an extra baseline, using consensus maximization in the style of Speciale et al. over CoFF matches.

Why not just complete both scans first and then register? Completion methods need a known pose between image and scan and have been evaluated on synthetic ShapeNet data. The surfaces they hallucinate would act as confident false inliers, which recreates the cascade that XMFnet itself warns about. We will test registration on XMFnet-completed fragments to show whether this helps or hurts.

Proposed Experiments

The main evaluation measures registration recall, rotation error and translation error on 3DMatch, 3DLoMatch and 3DLoMatch_Planar, all of which come with RGB-D source frames. We report wall-clock time per pair against CoFF. Registration recall is used as CoFF and the Sight View Constraint paper use it, so the numbers are comparable. Pairs are also bucketed by overlap ratio.

The decisive check is a controlled corruption study. We degrade the segmenter with blur, noise and small calibration offsets of a few pixels, then plot recall against segmenter mIoU for three variants: hard labels, label sets, and geometry only. The hypothesis fails if label sets do not stay at or above the geometry floor under corruption. It also fails if the free-space term gives no gain inside the bound beyond its use as a filter. A secondary check tests the theory directly: using ground-truth poses, we measure how much the true pose's score drops and compare it to the predicted $\delta$ fraction.

Two limitations will be reported. First, 3DMatch fragments are fused from many frames, so the choice of a single sensor origin is approximate. Second, the search will be slower than learned matchers, likely by seconds per pair.