Which Pixels Must Be Measured? Resolving Sets for Sparse Metric Depth Anchors

A single camera image cannot tell a toy car up close from a real car far away. Modern depth networks therefore predict depth only up to an unknown scale, and practical systems fix the scale with a handful of true distance measurements, called "anchors." These come from a few LiDAR beams or from points tracked by visual-inertial odometry (VIO), which estimates camera motion from video plus an inertial sensor. Today nobody chooses where those anchors fall. LiDAR scan lines sit wherever the hardware puts them, and VIO points land wherever corner features happen to be detected. This proposal asks a sharper question: given a budget of, say, 20 to 150 measurements, which pixels must be measured so that every part of the scene can receive its own scale correction?

Our claim is that a common class of anchor-propagation methods has a hidden failure mode that graph theory names exactly. These methods spread corrections outward from anchors, as with triangulation scaffolds or edge-aware interpolation. If two image regions sit at the same graph distances from every anchor, any such method gives them the same correction, even when their true scale errors differ. Avoiding this requires the anchors to form a resolving set, meaning a set of landmark vertices whose distance profiles tell every vertex apart, on a graph of image regions. We will test whether this condition predicts where real depth-completion systems fail. If it does, we will use it to place anchors better than uniform, coverage-based, or uncertainty-based sampling at the same budget.

Core Claim

Build a region graph from the relative depth map. Its vertices are superpixels or planar segments. Edges join regions that touch along a smooth depth boundary, and edges are cut at occlusion boundaries, where the depth jumps between foreground and background. Consider any refiner that computes the correction for region $v$ as a function $F$ of the anchor depth values and the truncated graph distances $d_k(v,r)=\min\{d(v,r),k+1\}$ from $v$ to each anchor $r$ in the anchor set $R$, where $k$ is the propagation horizon. Such a refiner can assign different corrections to two regions $u \neq v$ only if

$$\big(d_k(u,r)\big)_{r\in R} \neq \big(d_k(v,r)\big)_{r\in R}.$$

This is exactly the definition of a $k$-truncated resolving set from Truncated metric dimension for finite graphs, which introduced $d_k$ to model bounded detection horizons.

The idea transfers to vision with one honest caveat. Learned refiners also see image appearance, and appearance could break ties that distances cannot. Whether it actually does is the empirical heart of the proposal. The geometric part has a concrete reading through the "twin rule" surveyed in Getting the Lay of the Land in Discrete Space. Regions with identical neighborhoods cannot be told apart by any outside anchor. A typical case is several small patches that all border only one large wall. Each such patch needs its own measurement, or the patches must accept a shared correction.

The hardness side is a direct corollary, not a new theorem. Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs II proves that metric dimension, the size of the smallest resolving set, is NP-complete even on interval graphs of diameter 2. Interval graphs are the overlap graphs of segments on a line and form one of the most structured subfamilies of perfect graphs. The truncated-dimension paper shows $\beta_k(G)=\beta(G)$ whenever $k \ge \mathrm{diam}(G)$. It follows that optimal truncated anchor selection with $k\ge 2$ is NP-hard even when the region graph comes from a single scanline strip, which is the most interval-like structure an image offers. So structure will not save us here, unlike the perfect-graph colouring case. Exact optima are still computable for small instances. Two routes are available: integer linear programming, as used in Resolvability of Hamming Graphs, and the $2^{O(k^4)}n$ dynamic program on interval graphs from Foucaud et al., which is practical because anchor budgets are small. Exact solutions let us measure how far fast heuristics fall from the optimum instead of guessing.

Relation to Prior Work

Three systems motivate the gap. LiDARTouch feeds fewer than 100 points from 4 fixed LiDAR beams into a depth network and eliminates infinite-depth failures. It reports that thin structures missed by the beams stay poorly scaled, and the beam layout is never optimized. Monocular Visual-Inertial Depth Estimation aligns a relative depth map to VIO points with a global scale and shift fit. It then refines per pixel with ScaleMapLearner (SML), a small network fed a triangulated scaffold built from the anchors, and finds accuracy depends on point count. Unsupervised Depth Completion From Visual Inertial Odometry uses a similar scaffold and introduced the VOID dataset. All three take the anchor locations as given. We change only where anchors go and keep their refiners.

The graph papers supply the method and the constraints. The metric dimension survey supplies the greedy entropy heuristic (ICH) with a $1+\ln n$ approximation guarantee. The interval and permutation graph paper and the truncated dimension paper supply the hardness and exact algorithms used above. Centroidal bases in graphs studies identification from proximity order only. It shows that order-only identification cannot be approximated within $o(\ln n)$ and needs $\Omega(\sqrt{m})$ landmarks on graphs where few paths connect each pair of vertices. This acts as a warning. It suggests that refiners which use only the ordering of anchor proximities may need far more anchors than distance-based ones, and we treat that as a testable side prediction rather than a premise.

Foundation models such as Metric3D v2, UniDepth and MoGe-2 address the same scale ambiguity without measurements. Metric3D v2, for example, requires known focal length. They serve here as the source of relative depth and as a no-anchor competitor, not as the object of study.

Research Program

The first component is construction. We segment the relative depth map from DPT or Metric3D v2 into regions and mark occlusion edges where the depth gradient is large. The output is a region graph of a few hundred to a few thousand vertices, which avoids the all-pairs shortest-path cost on raw pixels that would make greedy selection infeasible at frame rate.

The second component is diagnosis. On existing VIO and LiDAR anchor sets, we label each region as resolved or unresolved, meaning it shares its truncated distance vector with at least one other region. We then measure whether unresolved regions carry excess depth error after controlling for distance to the nearest anchor and for region size.

The third component is placement. We select anchors with a greedy truncated-resolving objective blended with a coverage term, and compare against exact ILP or dynamic-programming optima on small graphs.

The fourth component is deployment under realistic constraints. One setting simulates a steerable sensor that may sample any pixel with ground truth. The other is a VIO-constrained setting where we may only choose a subset of tracked features.

Baselines

The naive reference point is global least-squares scale-and-shift alignment with all available anchors and no local refinement. This is the "Global Alignment" stage of Wofk et al. It shows how much any local correction matters. Wofk et al. report that adding SML cuts iRMSE (root mean square error of inverse depth) by up to 30% relative to global alignment alone on their benchmarks.

The strongest existing method for the refinement itself is SML from Monocular Visual-Inertial Depth Estimation. It is the most relevant competitor because it is a scaffold-plus-appearance refiner trained on TartanAir. Wofk et al. report more than 50% lower iRMSE than KBNet with 150 points on VOID. The file gives no absolute iRMSE value for SML, so we record "no reported result found on Lacuna for SML absolute iRMSE on VOID" and will reproduce it with the released model. On KITTI, the ultra-sparse reference is LiDARTouch, which reports RMSE 2.504m with 4 beams versus 2.112m for 64-beam supervision, and a catastrophic distance rate of 0.0% versus 5.02% for Monodepth2. The no-anchor reference is Metric3D v2 with known intrinsics, which reports zero-shot Abs Rel 0.044 on KITTI and 0.047 on NYUv2.

Placement baselines all use the same anchor count, the same frozen SML or LiDARTouch refiner, and the same relative depth input. They are uniform random sampling, stratified grid sampling, farthest-point sampling in image space, and $k$-hop coverage (dominating-set) placement on the same region graph. The strongest placement baseline is uncertainty-driven sampling, which takes the regions with the highest predicted depth variance under test-time augmentation. It is the obvious active-sensing approach and we give it the same tuning budget as ours.

The key ablation separates resolvability from coverage. We compare placements matched on coverage, with the same fraction of regions within $k$ hops of an anchor, that differ only in how many regions are resolved. Beating the baselines means lower iRMSE and Abs Rel at matched budgets of 20, 50 and 150 anchors, with the gain concentrated in regions our method resolves and the baselines leave unresolved.

Why not just…?

Why not just spread anchors evenly or by coverage? This is the most serious threat. Good coverage may resolve most regions automatically, since distance vectors to well-spread anchors tend to differ. The coverage-matched ablation settles it directly. If resolvability adds nothing once coverage is fixed, the graph lens reduces to a domination problem and we will report that rather than defend the framing. The twin rule predicts gains specifically in cluttered scenes with many small patches bordering one large surface, so we stratify results by twin-class count.

Why not just let a learned refiner use appearance to tell regions apart? It may. SML sees the image, so its corrections are not purely distance functions. The resolved-versus-unresolved diagnostic on existing anchor sets tests this before any placement work. If unresolved regions show no excess error after controls, the necessary condition does not bind for learned refiners. The contribution would then shrink to a statement about pure propagation methods like Delaunay scaffolds, and we would pivot to those.

Why not just sample where the network is uncertain? Uncertainty points to regions whose depth is likely wrong but says nothing about whether a correction placed there can propagate distinctly to neighbors. We run uncertainty sampling, and a hybrid that ranks resolving candidates by uncertainty, at the same budget. If pure uncertainty matches ours, the answer is that the graph structure is redundant with what the network already knows.

Why not just use a metric foundation model and skip anchors? Metric3D v2 is strong when focal length is known, but it is the camera intrinsics, not physical measurement, that fix its scale. Forced-perspective or out-of-distribution sizes remain ambiguous for it. We include it as the no-anchor reference. Our question only matters in the regime where anchors are available and limited, which is the regime LiDARTouch and VIO systems already occupy.

Proposed Experiments

The decisive first experiment is the diagnostic on VOID with native VIO points and the released SML model. We regress per-region inverse-depth error on resolved status, nearest-anchor distance and region size. A significant positive coefficient on "unresolved" is the go/no-go signal for everything else.

Second, on VOID and NYUv2, we simulate steerable anchors by sampling dense ground truth at chosen pixels. Third, on KITTI we do the same, restricted to pixels with LiDAR ground truth. We compare all placements at 20, 50 and 150 anchors on iRMSE, RMSE and Abs Rel. Fourth, we report error on the subset of regions where placements disagree in resolved status.

Fifth, on graphs of up to a few hundred regions we compute exact truncated resolving sets by ILP. We also run the interval-graph dynamic program on single-scanline strips, which mimic one LiDAR beam. Together these report how far greedy selection falls from the optimum and whether closing that gap changes depth error at all. Finally, in the VIO-constrained setting we pick subsets of tracked features to test whether placement still helps when choices are limited to where features exist. As a side check, we compare an order-only variant of the refiner against the distance-based one to see whether the centroidal $\Omega(\sqrt{m})$ prediction shows up as a steeper anchor requirement.