Source-linked AI summary
Product Manifold Filter: Non-Rigid Shape Correspondence via Kernel Density Estimation in the Product Space
Matthias Vestner, Roee Litman, Emanuele Rodolà, Alex Bronstein, Daniel Cremers
TL;DR
Deformable-shape correspondence methods may rely on near-isometry or produce maps lacking bijectivity and smoothness. This paper models correspondence recovery as kernel density estimation in the product space and applies a filter that yields smooth bijections without an isometry assumption. The authors report improved input-match accuracy and better sparse-match quality when fewer than ten matches are provided.
Problem
Deformable-shape methods may rely on isometry assumptions or produce correspondences that lack bijectivity and smoothness.
Source: §1 · p. 1Method
PMF treats noisy or sparse matches as samples of a correspondence manifold in the product space and filters them, using a linear assignment problem to enforce bijectivity.
Source: §2 · pp. 2–3, §4 · p. 7Results
PMF increases the accuracy of all input matchings, and yields better-quality maps than with fewer than ten matches and comparable quality when more are available.
Source: §3.1 · p. 5, §3.2 · p. 6Takeaways & Limitations
Product-space correspondence denoising is presented as a perspective applicable to other smooth-correspondence problems, including optical flow.
Source: §4 · pp. 7–8The noisy input matches are modeled as having a separable i.i.d. Gaussian density.
Source: §2 · p. 3
Abstract
from arXiv · showhide
Many algorithms for the computation of correspondences between deformable shapes rely on some variant of nearest neighbor matching in a descriptor space. Such are, for example, various point-wise correspondence recovery algorithms used as a post-processing stage in the functional correspondence framework. Such frequently used techniques implicitly make restrictive assumptions (e.g., near-isometry) on the considered shapes and in practice suffer from lack of accuracy and result in poor surjectivity. We propose an alternative recovery technique capable of guaranteeing a bijective correspondence and producing significantly higher accuracy and smoothness. Unlike other methods our approach does not depend on the assumption that the analyzed shapes are isometric. We derive the proposed method from the statistical framework of kernel density estimation and demonstrate its performance on several challenging deformable 3D shape matching datasets.
1. Introduction
Existing deformable-shape correspondence methods can achieve high pointwise accuracy but may depend on near-isometry or lack bijectivity and smoothness. The paper introduces a product-space filtering method for recovering smooth bijections without assuming isometry, including from sparse or imperfect input matches.
1. Introduction
- High pointwise accuracy can require an isometry assumption, while computed maps may lack bijectivity or smoothness.Bijectivity means each point on either shape has exactly one corresponding point on the other; smoothness means nearby points match to nearby points.Source: §1 · p. 1
1.1. Related works
- Prior approaches use distortion minimization, embeddings, soft correspondences, or product-space optimization, but often yield noisy or poorly surjective maps or incur prohibitive computational cost.Product-space integer linear programming can encode smoothness and surjectivity, but its computational complexity is prohibitive even for modest problems.Source: §1.1 · pp. 1–2
1.2. Main contributions
- PMF filters sparse matches or imperfect dense maps into smooth bijective correspondences using a linear assignment problem, without requiring near-isometry.The method is designed for general deformations and can also handle shapes of different dimensionality.Source: §1 · p. 1, §1.2 · p. 2
- The paper reports that PMF consistently improves correspondences from different algorithms and can interpolate sparse input matches.The reported evaluations include pointwise recovery methods used in functional-map pipelines.Source: §1.2 · p. 2
2. A probabilistic framework
The framework estimates a latent shape correspondence from noisy matches using kernel density in the product space, then selects a bijective map that regularizes the correspondence. Its discretized assignment and multiscale variant make the optimization tractable while constraining matches across scales.
2. A probabilistic framework
- The method estimates the latent correspondence manifold from noisy, possibly sparse matches with product-space kernel density, then maximizes density under bijectivity to obtain a more regular map.The shapes need not be isometric; the paper describes the filter as having an area-reduction effect on the correspondence manifold.Source: §2 · pp. 2–3
2.1. Discretization
- Discretizing the bijective estimator over shape samples represents the map as a permutation matrix and turns its optimization into a linear assignment problem.The assignment is optimized over n × n permutation matrices.Source: §2.1 · p. 4
2.2. Multiscale
- The multiscale scheme uses hierarchies of farthest-point samples and local regularity to restrict feasible permutations, reducing assignment size while preserving neighborhood consistency.It recursively applies a PMF variant to coarser-scale matches; the feasible moves allow an adjacent Voronoi cell to accommodate errors between scales.Source: §2.2 · pp. 4–5
- For sufficiently large shapes, storing projected distance matrices and reconstructing distances on demand addresses memory limits, with the cited prior work reporting negligible reconstruction error.The method stores projections on the first r Laplacian eigenfunctions.Source: §2.2 · p. 4
3. Experiments
The experiments assess PMF for sparse-match recovery, refinement of noisy functional-map correspondences, and multiscale recovery on high-resolution shapes.
3.1. Recovery from sparse correspondences
- With fewer than ten landmarks, PMF gives better maps than Tutte, and comparable maps with more; Figure 5 reports a few minutes versus ~1 hour.PMF also remains meaningful with one or two matches and is invariant to input ordering.Source: §3.1 · p. 5, Figure 5 · p. 6
3.2. Recovery from noisy input
- Noisy-input tests compared methods on 71 SCAPE pairs and 100 FAUST pairs, using low-rank functional-map approximations as inputs.The low-rank maps were constructed from ground-truth correspondences; PMF used σ^2 set to 2% of target-shape area.Source: §3.2 · pp. 5–6
- The accuracy of all input matchings increased with PMF; among the tested methods, coherent point drift showed the most dramatic runtime increase.The experiments cover 71 SCAPE pairs and 100 FAUST pairs.Source: §3.2 · p. 6
3.3. Recovering high-resolution correspondences using multiscale
- On 27,894-point cat shapes, correspondence accuracy improves at finer scales, and solving the finest-scale LAP took less than 9 minutes.The multiscale procedure solved constrained LAPs at six scales.Source: §3.3 · pp. 6–7, Figure 8 · p. 7
- On FAUST, four-scale correspondences match single-scale accuracy while reducing runtime; kernel-density matrices took about 4 minutes and LAPs around 18 seconds.Figure 10 shows intermediate-scale error curves against the single-scale PMF solution.Source: Figure 10 · p. 7, §3.3 · p. 7
4. Discussion and conclusion
The Product Manifold Filter treats correspondence recovery as kernel density estimation in the product space and uses a linear assignment problem to enforce bijectivity. Its inputs can include sparse or imperfect matches, and the discussion highlights soft-map handling and potential use in optical flow.
4. Discussion and conclusion
- PMF views correspondence recovery as kernel density estimation in the product space and uses a linear assignment problem to enforce bijectivity.It filters matches from existing algorithms, including methods that do not guarantee bijectivity or produce sparse correspondences.Source: §4 · p. 7
- On near-isometric SCAPE pairs, filtering nearest-neighbor results outperformed the state-of-the-art method with a fraction of its runtime; bijective-NN initialization achieved better results at affordable runtimes.Figure 11 compares geodesic-error histograms for 70 shape pairs using 20 and 50 eigenfunctions.Source: Figure 11 · p. 8
- Applying PMF to nearest-neighbor or coherent point drift matches produced guaranteed bijections with high accuracy and improved smoothness.The qualitative comparison visualizes transferred texture, unmatched points, and geodesic error on the target shape.Source: Figure 12 · p. 8
- Samples need not be distinct per shape, and weighting factors allow PMF to work directly with soft maps; the authors also identify optical flow as a possible application.They also suggest lifting the product space to encode local similarity, for example with descriptors.Source: §4 · p. 8