Certified Left–Right Decisions in Globally Optimal Shape Matching

Matching two deformable 3D shapes means deciding which point on one shape corresponds to which point on the other, for example a person standing and the same person sitting. The most reliable cues for this, distances measured along the surface, do not change when the shape bends. They also do not change when the shape is mirrored. A left hand and a right hand look identical to these measurements, so matchers regularly swap limbs. Methods that solve the matching exactly as an integer linear program, an optimization over yes/no correspondence variables with linear constraints, can prove that a map is the best one under a given cost. They cannot say whether that cost could tell left from right at all. When the cost is mirror-symmetric, the "certified optimum" is certified only up to a coin flip.

We propose to make this left–right decision an explicit, separately certified quantity. The matching problem is split on a single binary orientation choice. Each half is written as an assignment problem, meaning each point on one shape is paired with exactly one point on the other, and the two halves are coupled to linear orientation constraints on triangles. Each half is solved with exact lower bounds whose inner step is a standard Hungarian assignment solve. The output is a correspondence plus a flip margin: a proven gap between the best orientation-consistent map and the best mirrored map. When the margin is large, the left–right decision is certified. When it is near zero, the method reports that the data cannot decide, instead of guessing.

Core Claim

The claim has two parts. The first is a mechanism for a known computational symptom. Suppose the matching cost is invariant under the target's intrinsic reflection $\sigma$. Then the relaxed linear program, the continuous version of the integer program, is invariant too. If $x^\ast$ is optimal, so is $\tfrac12(x^\ast + \sigma x^\ast)$, a half-left, half-right blend of the true map and its mirror. Interior-point and dual-averaging solvers tend to return exactly such blended points. We therefore predict that a large share of the fractional, uncertified instances in exact shape matchers come from reflection symmetry rather than from general hardness. Splitting on the orientation bit removes the symmetric blend from each branch, and each branch should be close to integral.

The second part is a new kind of output. For each instance we report lower and upper bounds for both branches and define

$$\Delta = L_{\text{flip}} - U_{\text{direct}},$$

where $U_{\text{direct}}$ is the cost of the best found orientation-preserving map and $L_{\text{flip}}$ is a proven lower bound on the cost of any orientation-reversing map. The rule is:

  • $\Delta > 0$: no mirrored map can beat the returned one under this cost, so the left–right decision is certified.
  • $\Delta \le 0$: the cost itself is ambiguous. This is expected under self-contact, where learned chirality features blur.

Relation to Prior Work

Motivating work: exact matchers. Three lines of work solve shape matching exactly and motivate the gap.

  • DiscoMatch solves a product-space integer program with GPU dual decomposition. It certifies optimality in 90% of instances, using learned features.
  • SpiderMatch maps a space-filling curve of the source onto the target with Gurobi. It avoids flips through continuity and no-new-self-intersection constraints, but is limited to about 1,000 triangles.
  • ΣIGMA solves a sparse keypoint mixed-integer program with an orientation-aware regularizer. It certifies 56 of 71 TOSCA pairs within an hour.

None of the three reports whether its certificate would survive a mirror swap, or which uncertified instances are symmetry-stuck. We keep their global-optimality stance and add a certificate that is specific to the symmetry.

Supplying the orientation mechanism. The orientation idea comes from two earlier papers.

  • Windheuser et al. enforced orientation inside a triangle-patch integer program. They found that the relaxation was integral in only 13% of runs without descriptors and in 56% with Wave Kernel Signatures. Their comparison method, GMDS, inverted orientation in 12 of 30 pairs.
  • Poulenard et al. defined orientation through the sign of $(\nabla f\times\nabla g)\cdot\mathbf n$.

We borrow the triangle-orientation idea. Unlike Windheuser et al., we keep the assignment polytope as the backbone, restrict the problem to sparse keypoints, and read the orientation split as a certificate rather than only a regularizer.

Supplying the cost features. Two sources provide chirality-aware costs, and one of them also sets a constraint on the design.

  • Chirality disentanglement extracts a per-vertex left–right signal from 2D foundation models. It reaches 91.84%–96.59% accuracy on BeCoS, where standard features sit near chance (~50%). The authors report failures under occlusion and when symmetric parts touch.
  • Deep orientation-aware functional maps resolve flips with complex functional maps, reaching a mean geodesic error of 4.8 on SMAL, but provide no certificate.

The failure regime in the first paper is exactly where our margin should detect ambiguity. That rules out designs that trust chirality features unconditionally.

Supplying the solver ingredient. Optimal bipartite assignment, which is solvable exactly in polynomial time and is the workhorse in text alignment (Jalili Sabet et al.) and in hallucination detection (Chan et al.), supplies the inner step of our bound computation. Sultan et al. explain why it beats greedy matching. Its known weakness is that it treats every pairing independently, so it cannot express surface continuity. We keep it only as the exactly solvable piece and move all coupling into dualized constraints, where it cannot break correctness.

Research Program

Formulation. We work at the level of sparse keypoints, with 100–400 per shape obtained by farthest-point sampling on a coarse mesh. This is the regime where ΣIGMA and DiscoMatch operate, and the ambiguity is fully present there.

  • Variables. Binary assignment variables $x_{ij}$ pair source keypoint $i$ with target keypoint $j$, under one-to-one constraints. Edge variables pair neighboring keypoint pairs. Face variables pair oriented source triangles of the keypoint triangulation with target triangles.
  • Consistency. Marginal-consistency constraints link faces to edges and edges to assignments.
  • Orientation split. A branch variable $z\in\{0,1\}$ selects which target triangles are admissible. With $z=1$ only same-orientation triangles are allowed; with $z=0$ only opposite-orientation triangles.
  • Cost. The cost combines geodesic distortion on edges with a descriptor term. The descriptor is either reflection-invariant or chirality-augmented, and this choice is an experimental factor.
  • Candidate sets. Candidates are limited to the top $k$ target keypoints per source keypoint. The candidate set is always closed under the target's estimated reflection, so pruning can never silently delete the correct side.
  • Estimating the reflection. We estimate $\sigma$ by solving the target-to-itself problem in the $z=0$ branch.

Solver. Within each branch we dualize the edge and face consistency constraints with Lagrange multipliers. What remains is a linear assignment problem, solved exactly by the Hungarian method, so every iteration yields a valid lower bound. The multipliers are updated by subgradient steps. We then compare against running the same program in Gurobi and in DiscoMatch's dual solver. If those solvers are just as fast at this scale, the solver is not a contribution, and we will say so. The analysis claims do not depend on it.

Analysis. We will study empirically, and prove where possible, when the reflection-averaged point is optimal for the unsplit relaxation. We will also measure how often each branch becomes integral, extending the 13%→56% integrality analysis of Windheuser et al. to symmetry-breaking terms.

Dense output. Dense maps are produced by propagating the certified sparse map along geodesics, restricted to the same side.

Baselines

Naive reference. The simplest reference is plain Hungarian assignment on descriptor similarity. We run it twice: once with reflection-invariant features, and once with the chirality features of Wang et al. appended. It uses the same keypoints and candidate sets and involves no tuning beyond feature weight, chosen on the same validation split we use. It shows how far exact but structure-blind matching gets. We expect it to scatter correspondences but occasionally fix flips.

Strongest exact competitor. The strongest competitor is DiscoMatch. It is exact, uses geometric consistency constraints, and its reported number is certified optimality in 90% of tested instances. The file lists no per-dataset geodesic error for it. We run it at the same mesh resolution, with the same learned features and the same wall-clock budget per instance, in two configurations: its original features, and features augmented with chirality. Beating it means one or both of the following:

  • a higher certified rate on symmetric shapes;
  • a lower flip rate at comparable geodesic error.

We also compare to ΣIGMA on TOSCA, where its reported figure is 56 of 71 pairs certified within one hour. We use the same one-hour limit.

Strongest continuous competitor. The strongest continuous competitor is Deep orientation-aware functional maps, with a reported mean geodesic error of 4.8 on SMAL. We do not expect to beat it on raw error. The comparison is on flip rate, and on whether our margin flags the instances where it fails.

Ablations. Three ablations isolate the key ingredient:

  • the same program with orientation constraints but no branch split, so no margin is computed;
  • the split without orientation constraints, with chirality entering only through cost;
  • a landmark-branching baseline that breaks symmetry by enumerating assignments of one designated keypoint.

Why not just…?

Why not just add chirality features to DiscoMatch's cost? This is the most serious threat. It may remove most flips on clean, well-separated poses. If it does, our accuracy gains will be small there, and we will report that. It cannot, however, tell the user when it is wrong. Wang et al. report that the features blur when symmetric parts touch, and a single certified optimum under blurred features looks exactly as confident as a correct one. Our margin is designed to be informative precisely in that regime. The experiment stratified by self-contact below settles which system is more useful.

Why not just use orientation-aware deep functional maps? They are fast and accurate on SMAL (4.8 mean geodesic error). They offer no bound, and points are extracted afterwards by nearest-neighbor search, which Roetzer et al. associate with jittery, inconsistent maps. We treat them as a strong accuracy reference and test only whether our certificate predicts their failures. It would be sufficient, and still useful, if our margin works as a failure detector on top of their output.

Why not just solve the integer program twice, once per orientation? Operationally, that is what our split does, and we say so plainly. What the split adds is threefold:

  • linear triangle-orientation constraints that make each half well-defined on an assignment backbone;
  • candidate sets closed under reflection, so neither half is pruned into infeasibility;
  • the interpretation of the two bound pairs as a certificate.

A naive version that does not use reflection-closed candidates appears among the ablations.

Why not just fix one landmark to break the symmetry? Pinning a single left-hand correspondence breaks the reflection. It requires knowing which landmark is correct, or else enumerating many candidates, whereas branching on the orientation bit needs only two branches. The landmark-branching ablation measures this directly.

Proposed Experiments

Data. We use four benchmarks:

  • FAUST (Bogo et al.), including real scans with self-contact; a reported reference is 2.51 cm average error in Litany et al.;
  • SMAL;
  • TOSCA;
  • BeCoS, where left–right ground truth is available.

Metrics.

  • mean geodesic error;
  • flip rate, the fraction of limb keypoints mapped to the opposite side;
  • certified-optimality rate;
  • integrality rate of the relaxation;
  • for the margin, precision and recall of $\Delta\le 0$ as a detector of flipped outputs.

First decisive check: does symmetry explain non-integrality? Among the instances where the unsplit relaxation or DiscoMatch fails to certify, we measure how many have fractional solutions near the reflection-averaged point. We then test whether splitting on orientation makes them integral. If symmetry explains only a small minority of these instances, the computational half of the claim is wrong.

Second decisive check: is the margin calibrated? On FAUST scans and BeCoS we split pairs by self-contact. The margin should be large and correct on separated poses, and near zero exactly where chirality-augmented DiscoMatch flips. If the margin is uncorrelated with actual flips, the certificate is useless and the proposal fails.

Third check: the cost of certification. We report runtime against DiscoMatch and Gurobi under equal budgets.