Efficient Deformable Shape Correspondence via Kernel Matching

Introduction

• The task is to find meaningful correspondences between non-rigid 3D shapes, with applications including shape comparison, texture transfer, and shape interpolation.The shapes are modeled as compact two-dimensional Riemannian manifolds.Source: §1 · p. 1
• Meaningful maps should be bijective, continuous in both directions, and place similar points together; the paper represents discrete bijections with permutation matrices.The introduction assumes equal-size, consistently sampled shapes and defers unequal sample counts to the algorithmic section.Source: §1 · p. 1
• Pointwise descriptors supply matching fidelity, while pairwise descriptors encode global or local relations that regularize correspondence continuity.The objective balances these terms; the permutation constraint guarantees bijectivity.Source: §1 · p. 2

Related work

• Pairwise matching can yield NP-hard QAPs, and relaxations produce approximate solutions; supervised deep methods lead benchmarks but require annotated data.Geodesic pairwise descriptors are also computationally expensive and noise-sensitive [20].Source: §1 · p. 2

Contribution

• The paper proposes high-quality regular correspondence for non-isometric shapes, reporting runtime and scalability improvements over [53] and extensions to partial shapes and multiscale matching.It interprets smoothing and projection as an alternating diffusion process.Source: §1 · p. 2

2.1. Pointwise descriptors

• Pointwise descriptors match vertices by feature similarity, but intrinsic features can fail under non-isometry and leave discontinuities around symmetries.The pointwise formulation is a linear assignment problem; intrinsic features may not capture non-isometric shapes or distinguish symmetric counterparts.Source: §2.1 · pp. 2–3

2.2. Pairwise descriptors

• Pairwise matching uses relations between vertex pairs, but geodesic distances bias toward far-apart points, are sensitive to topological noise, and yield costly, non-convex optimization.The relaxed pairwise objective is convex only when both descriptor matrices have strictly positive eigenvalues; under that condition, its optimum matches the original combinatorial problem.Source: §2.2 · p. 3
• Heat kernels are positive-definite pairwise descriptors, satisfying the sufficient condition for exact relaxation that distance matrices do not.The paper advocates kernels over distances; the cited spectrum figure compares the two matrices for several heat-diffusion times.Source: §2.2 · pp. 3–4, Figure 2 · p. 3

2.3. Bijective maps and functional maps

• Functional maps replace pointwise recovery with a linear map between function spaces, but a band-limited map does not guarantee that its recovered pointwise map is continuous or smooth.The map can be approximated in a truncated low-frequency Laplacian basis, with pointwise recovery obtained through ICP-like procedures.Source: §2.3 · p. 4

3.1. Optimization

• The DC-inspired iterations solve linear assignment problems, increase the objective, and keep every iterate a permutation matrix.The objective combines pointwise descriptor fidelity with positive-definite heat-kernel terms and is optimized over bistochastic matrices.Source: §3.1 · pp. 4–5

3.2. Partial matching using slack variables

• Partial matching pads a rectangular assignment matrix with constant-valued slack variables, then discards matches assigned to those slacks.The constant must avoid ambiguity with actual vertices; with many slacks, (nX − nY)! optimal solutions can worsen runtime.Source: §3.2 · p. 5

3.3. Multiscale acceleration

• The multiscale approach solves a seed bijection first, then expands correspondences within transferred Voronoi cells until all points are sampled.It is proposed because each iteration's linear assignment has super-quadratic complexity; 1000 seed correspondences orient cells consistently across iterations.Source: §3.3 · p. 5

4.1. Alternating diffusion

• After three iterations, the partial-match example corrects a deliberately noisy hand-to-foot match that initially creates a discontinuity at the woman's hand.The example uses Gaussian kernels; heat-kernel boundary conditions are left for future work.Source: Figure 5 · p. 6
• The multiscale procedure transfers coarse correspondence groups to the target, adds finer vertices to their groups, and solves separately for each group.This refines a coarse correspondence without solving the full fine-scale problem at once.Source: Figure 6 · p. 6
• Diffusing source indicators, transporting them through the current mapping, and diffusing on the target produces correspondence scores shaped by both kernels.Success assumes enough uniformly distributed correct initial matches; diffusion time trades local accuracy against the reach of information and fine-scale ambiguity.Source: §4.1 · pp. 5–6

4.2. Iterated blurring and sharpening

• In the spectral view, each iteration smooths a functional map and projects it onto permutations; in the product-space view, kernels on the previous correspondence graph define a distribution to maximize.The latter interpretation uses heat kernels, in contrast to the geodesic Gaussian kernels noted for the related method.Source: §4.2 · pp. 6–7, §4.3 · p. 7

Experiments

• The evaluation spans four benchmarks and compares complete matching pipelines with learning-based approaches; post-processing is reported to boost performance significantly.SHOT and HKS are used with default parameters, and heat kernels are computed from 500 Laplacian eigenfunctions.Source: §5 · p. 7

FAUST

• Up to 50% improvement over raw deep-learning outputs is reported on FAUST, though body-part swaps in some shapes prevent reaching 100%.Figure 10 compares deep-learning methods (dashed curves) with the same methods post-processed by this approach (solid curves).Source: Figure 10 · p. 8, §5 · p. 8

SCAPE and TOSCA

• SCAPE and TOSCA are also evaluated, with quantitative correspondence-accuracy results shown in Figures 8 and 9, respectively.SCAPE contains clean human scans in different poses; TOSCA includes human and animal classes at varying resolutions.Source: §5 · pp. 7–8, Figure 8 · p. 7, Figure 9 · p. 8

SHREC’16 Topology

• SHREC’16 Topology tests shapes with near-isometric deformations and topological shortcuts, using SHOT because HKS is not robust to topology changes.The reported evaluation is shown in Figure 11.Source: §5 · p. 8, Figure 11 · p. 8

6. Conclusions

• The method formulates smooth, possibly partial matching between non-isometric shapes as a QAP over point-wise and pair-wise descriptors.Positive-definite kernel matrices as pair-wise descriptors yield an exact relaxation over bistochastic matrices, optimized by projected descent motivated by DC programming.Source: §6 · p. 8
• Each iteration reduces to a linear assignment problem solved with a multiscale auction algorithm, and the algorithm scales to hundreds of thousands of vertices.The conclusion also interprets the updates as alternating diffusion, blurring and sharpening, and kernel-density estimation.Source: §6 · p. 8
• Experiments on varied datasets show significant improvement over the output of existing correspondence methods.Source: §6 · p. 8

A. Details about the DC algorithm

• Each iterate can be chosen as a permutation matrix, and the objective increases strictly until convergence.The weak inequality in the derivation follows directly from equation (29).Source: A. Details about the DC algorithm · p. 11
• The DC steps use the gradient of a convex differentiable objective and the convex indicator of the bistochastic set, with the second step expressed through a subgradient condition.The appendix invokes convex-conjugate and subgradient identities to derive the equivalent steps.Source: A. Details about the DC algorithm · p. 11
• Because linear functions on the bistochastic polyhedron attain extrema at its vertices, the maximizer can be chosen as a permutation matrix.The appendix notes that strict convexity of the objective supports the resulting increase in objective value.Source: A. Details about the DC algorithm · p. 11

• A seed bijection from farthest-point samples initializes transferred Voronoi cells, which are refined with additional samples until all points have been sampled.The initial seed count can be set to the solver’s vertex limit or reduced when runtime is crucial.Source: B. Details on multiscale acceleration · pp. 11–12
• Small maxP makes the method faster but less robust, whereas small k makes it slower but more robust.Source: B. Details on multiscale acceleration · p. 11
• Eight FAUST cases swapped upper-body left and right, producing non-continuous correspondences.Source: Figure 12 · p. 11
• Each iteration solves corresponding cells separately, adds matched points to the seed sets, and rebuilds cells; 1,000 initial matches help align cell boundaries.Some points may remain unmatched within a cell, even when the shapes began with the same vertex count.Source: B. Details on multiscale acceleration · p. 12
• For partial shapes, unmatched initial seeds are marked forbidden and given their own cells so that forbidden status spreads only to neighboring points.The initial sample counts can be chosen according to the shapes’ area or vertex-count ratio.Source: B. Details on multiscale acceleration · p. 12

• Runtime tests used nine pairs from high- and low-resolution TOSCA meshes and the FAUST registration set, with varying vertex counts.Source: C. Run time comparison · p. 12
• Tests ran in Matlab 2016b on a 2.5 GHz Intel Core i7 MacBook Pro with 16 GB RAM.Source: C. Run time comparison · p. 12
• All tests used SHOT descriptors and 10 iterations with α = 1/108; heat kernels used 400 eigenvectors, with time parameters logarithmically scaled between 400 and 10.Source: C. Run time comparison · p. 12

• The paper presents additional results for a pair of dramatically non-isometric shapes (Fig.13), pairs from the Tosca dataset (Fig.14), and failure cases (Figs.12,15).Source: D. More results, Failure cases · p. 12
• A TOSCA cat pair matches, while a centaur pair fails with swapped front legs and only a few unmatched points.Source: Figure 14 · p. 13
• On SCAPE, front-to-back leg mapping disrupts torso continuity and multiscale matching leaves large unmatched regions; SHREC’16 failures involve missing parts or distorted texture and merged hands or feet.Source: Figure 15 · p. 13