Partial Functional Correspondence

Emanuele Rodolà; Luca Cosmo; Michael M. Bronstein; Andrea Torsello; Daniel Cremers

Source-linked AI summary

Partial Functional Correspondence

Emanuele Rodolà, Luca Cosmo, Michael M. Bronstein, Andrea Torsello, Daniel Cremers

arXiv:1506.05274v2Jun 17, 2015cs.CV

TL;DR

Partial correspondence between non-rigid shapes is difficult because observed data may contain only part of a deformed shape. The paper extends functional maps by jointly optimizing corresponding parts and a perturbation-derived spectral prior, reporting effective performance on challenging settings and introducing new benchmark datasets.

Problem
Partial correspondence must match a subset of a deformed shape to a full model, while standard functional maps are not suitable for this setting.
Method
The method jointly optimizes an indicator-function part model and a weighted functional correspondence regularized by Laplacian-eigenfunction behavior under part removal.
Results
The approach handles very challenging partial correspondence settings and produces more accurate solutions as functional-map rank increases, unlike the compared baseline.
Takeaways & Limitations
The framework provides an automatic dense-feature method for partial functional correspondence and introduces datasets with hundreds of shapes to support further research.
Takeaways & Limitations
The formulation focuses on partiality rather than general deformations and does not explicitly address topological changes or inter-class similarity; multiple optima can also arise from intrinsic symmetries.

Abstract

from arXiv · show

In this paper, we propose a method for computing partial functional correspondence between non-rigid shapes. We use perturbation analysis to show how removal of shape parts changes the Laplace-Beltrami eigenfunctions, and exploit it as a prior on the spectral representation of the correspondence. Corresponding parts are optimization variables in our problem and are used to weight the functional correspondence; we are looking for the largest and most regular (in the Mumford-Shah sense) parts that minimize correspondence distortion. We show that our approach can cope with very challenging correspondence settings.

1. Introduction

The paper addresses partial correspondence between non-rigid shapes, where missing shape regions must be matched despite deformation. It extends functional correspondence with optimized part modeling and spectral regularization motivated by Laplacian perturbation analysis.

1. Introduction: Partial correspondence matches an observed shape subset to a deformed full shape, arising frequently from missing regions in 3D sensor data.Non-rigid correspondence is challenging because deformations are allowed, typically under an approximate-isometry assumption.
1. Introduction: Existing point-wise approaches include ICP variants, metric distortion minimization, sparse correspondences, extremity matching, descriptor matching, and product-space formulations.These methods differ in their assumptions and outputs, including approximate rigid initialization, regularized parts, sparse matches, or orientation-preserving solutions.
1. Introduction: Functional maps represent shape correspondence as a linear operator between function spaces, reducing correspondence estimation to an algebraic problem.Recent functional-map methods can handle missing or incomplete data, but the framework is described as unsuitable for partial correspondence overall.
1. Introduction: The proposed extension optimizes an explicit corresponding-part model alongside spectral regularization derived from how part removal changes Laplacian eigenfunctions.The paper also provides a perturbation-based theoretical study and introduces a benchmark with hundreds of shapes and ground-truth information.

2. Background

The background formulates shapes through Laplace-Beltrami eigenfunctions and functional maps, then discretizes the operators on triangular meshes. Functional correspondence becomes a finite linear system in truncated spectral bases.

2. Background: Shapes are modeled as compact connected 2-manifolds, possibly with boundary, with square-integrable functions equipped with the manifold inner product.The intrinsic gradient and positive semidefinite Laplace-Beltrami operator generalize gradient and Laplacian notions to manifolds.
2. Background: Laplace-Beltrami eigenfunctions form an orthonormal basis of L2(M), enabling Fourier expansions of functions on the manifold.For manifolds with boundaries, the formulation uses homogeneous Neumann boundary conditions.
2. Background: Functional correspondence models a map between shapes as a linear operator that transforms Fourier coefficients between chosen function bases.Truncating to the first k coefficients represents the operator by a k × k matrix C.
2. Background: Given q corresponding functions and their Fourier coefficients, the functional map matrix C is obtained from a linear system solved in the least-squares sense when q ≥ k.The coefficient structure depends on the bases; Laplace-Beltrami eigenfunctions provide a convenient basis and low-pass filtering through truncation.
2. Background: For approximately isometric shapes, the functional-map matrix can exhibit exploitable structure rather than requiring all k^2 coefficients.With isometric shapes and simple spectrum, corresponding eigenfunctions satisfy Tφi = ±ψi, yielding cij = ±δij.
2. Background: On a triangular mesh, the discrete Laplacian is an n × n sparse matrix constructed with the cotangent formula using interior and boundary edges.The first k eigenfunctions are computed by generalized eigendecomposition, and Fourier coefficients by a = Φ⊤Sf.

3. Laplacian eigenvectors and eigenvalues under partiality

Under partiality, the spectral correspondence retains an approximately slanted-diagonal structure whose slope reflects the relative area of the part, while cut geometry controls spectral perturbation and eigenfunction mixing.

3.1. Block-diagonal case: When approximate isometry fails because one shape has missing parts, the functional-map matrix C still exhibits exploitable structure.The paper studies a full shape M, a part N, and the unseen remainder under part-to-whole matching.
3.1. Block-diagonal case: In the disconnected case, the full-shape Laplacian spectrum interleaves eigenpairs from the observed and missing blocks, with eigenvectors zero-padded to the full shape.Only the first r of the observed part’s first k eigenvalues may appear among the full shape’s first k eigenvalues.
3.1. Block-diagonal case: The partial functional map has a slanted diagonal with slope r/k, and its last k−r columns are zero because r = rank(C).The value r can be estimated by comparing the spectra; Weyl’s law relates the slope to relative surface area.
3.2. Perturbation analysis: Joining the parts perturbs the block-diagonal Laplacian only in a boundary band, while the diagonal angle depends on relative area and sharpness depends on cut position and length.For cotangent Laplacians, cutting an edge changes entries associated with the edge’s endpoint vertices and neighboring triangle edges.
3.2. Perturbation analysis: Theorem 1 shows that first-order eigenvalue changes depend on boundary Dirichlet energy, so eigenvalues vary with the cut’s length and position.This perturbation enables approximate matching between part and full-shape eigenvalues and estimation of the functional-map slope.
3.2. Perturbation analysis: Theorem 2 attributes eigenfunction changes to eigenspace mixing: missing-region completion comes from one term, while near-boundary modifications and higher-frequency amplification come from another.Mixing is stronger for eigenvectors with boundary copresence and for similar eigenvalues; it can be reduced by shorter or weaker-interaction cuts.

4. Partial functional maps

The method jointly optimizes a partial functional correspondence and the matching part, using spectral structure and regularization to model partial maps.

The query shape N is an approximately isometric deformation of a part M′ of a full model M.
An indicator function v models the unknown part, while the functional correspondence is represented by coefficients C weighted through B(v).The mask ignores regions outside v = 1 when expressing the partial correspondence.
The optimization jointly solves for correspondence C and part v, using an L2,1 norm to handle outliers through column sparsity.
Part regularization favors a region with query-like area and a short boundary, using an intrinsic Mumford-Shah functional for soft membership.
The correspondence penalty encodes a slanted-diagonal structure with a weight matrix W that is small on the expected diagonal and large elsewhere.
Orthogonality is promoted through C⊤C, while low-rank behavior is modeled because partiality produces an almost-zero block and only some singular values are non-zero.
An alternating scheme repeatedly optimizes correspondence C and part v; an example alternates corresponding parts and functional correspondence using 30 eigenfunctions.

5. Implementation

The implementation uses manifold optimization with nonlinear conjugate gradients, alternating initialization, and a nearest-neighbor refinement step for noisy data.

Regularization terms are discretized as described in Appendix A.
The framework is implemented in Matlab/C++ with nonlinear conjugate gradients for each optimization step.
The alternating scheme initializes v∗ as ones and C as W, converging in 3–5 outer iterations in the reported experiments.A pair of shapes took around 5 minutes in these experiments.
After each C-step, refinement alternates nearest-neighbor assignments with correspondence updates while retaining the µ4 and µ5 regularizers.The assignment uses n nearest-neighbor searches in Rk.

6. Experimental results

Experiments evaluate partial correspondence on remeshed TOSCA shapes, regular cuts, irregular holes, range images, and point clouds. The method remains effective as partiality increases and as functional-map rank grows, including qualitative matches near boundaries.

Datasets: The evaluation uses 76 TOSCA base shapes remeshed to 10K vertices, with regular-cut, irregular-hole, range-image, and point-cloud partial-shape datasets.Regular cuts produce 456 partial shapes; irregular holes produce 684, with area budgets retaining 40%, 70%, or 90% of the surface.
Evaluation: The method is compared with full functional maps, elastic net, and voting using dense local SHOT descriptors and the Princeton benchmark protocol.The protocol measures mean geodesic error relative to ground-truth point-wise correspondences.
Comparisons: As partiality increases, competing methods show significant performance degradation, whereas the proposed method’s correspondence quality is nearly constant.Figure 11 reports mean geodesic error as a percentage of diameter across increasing partiality levels.
Representation: Qualitative examples show accurate matching near boundaries on meshes and point clouds despite noisy descriptors.The method is also demonstrated on simulated point clouds and depth maps using a discrete Laplacian for point clouds.
Sensitivity analysis: As functional-map rank increases, the proposed method becomes more accurate, while the baseline method exhibits the opposite trend.The comparison uses 20 regular-cut pairs from the cat and victoria classes and the same dense descriptors for both methods.
Comparisons: At little or no partiality, the approach converges toward the functional-maps method of Ovsjanikov et al.; increasing partiality exposes that baseline’s sensitivity.The comparison is reported on cuts and holes datasets containing 200 shape pairs in total.

7. Discussion and conclusions

The paper presents an automatic functional-map framework for dense matching of deformable shapes under partiality. It reports challenging-case results and releases two datasets, while identifying multiple optima and broader deformation settings as limitations.

Conclusions: The framework adapts functional maps to partial correspondence and combines dense local features with a perturbation-derived prior on the functional correspondence.The optimization targets partial matching under partiality transformations.
Conclusions: The method is fully automatic and reports remarkable results on very challenging partial matching cases.The conclusion characterizes dense local features as the method’s similarity measure.
Conclusions: The authors introduce two datasets comprising hundreds of shapes to support further research on partial functional correspondence.The datasets accompany the proposed framework as an additional contribution.
Limitations: Multiple optima can arise from non-trivial self-isometries, potentially producing inconsistent matchings on intrinsically symmetric shapes.The authors suggest smoothness priors as a possible way to obtain better-behaved solutions.
Limitations: The formulation focuses on partiality and does not explicitly address topological changes, inter-class similarity, or matching entire shape collections.The authors list these settings as directions for extension or future research.

Appendix A - Discretization

The appendix discretizes scalar functions, gradients, Laplacians, and functional-map quantities on triangle meshes. It also defines the rank-informed weight matrix and regularization terms used by the partial correspondence model.

Mesh parametrization: A triangle mesh is parameterized by affine coordinates over each triangle, with vertex coordinates defining the local 3D chart.Each triangle uses α ∈ [0,1] and β ∈ [0,1−α].
Mesh parametrization: Each triangle’s discrete metric tensor is determined by edge lengths and their inner product, which also defines the triangle’s volume element.The coefficients are E_j, F_j, and G_j from the three vertex coordinates.
Scalar functions: Piecewise-linear scalar functions are integrated over each triangle from their three vertex values.The integral is expressed using the triangle area and the sum of vertex values.
Gradients: For piecewise-linear functions, the intrinsic gradient is constant within each triangle and can be integrated using local metric coefficients.The appendix derives the gradient components and their norm in local coordinates.
Spectral representation: The partial and full shapes contribute their first k Laplacian eigenvalues, while the functional map C has size k×k.The notation distinguishes the partial shape N from the full shape M.
Regularization: The appendix combines area, Mumford-Shah, weight, and orthogonality terms into the discretized optimization formulation.The Mumford-Shah term regularizes the selected parts, while orthogonality is handled with a shared coefficient for practical reasons.
Weight matrix: The rank estimate r determines the slope of the weight matrix’s slanted diagonal, whose funnel spread is controlled by σ.The experiments use σ = 0.03.

Appendix B - Gradients

The appendix derives gradients for optimization over the functional map and the partial-shape indicator. It expresses data, area, Mumford-Shah, weight, and orthogonality derivatives in discrete form.

Optimization: Local solutions are computed with nonlinear conjugate gradient optimization over the terms in the partial correspondence objective.The appendix provides detailed gradient derivations for implementation.
Optimization variables: Gradients are computed with respect to either the discretized part variable v or the functional map C, depending on the optimization step.The implementation models v as an n-dimensional vector.
Data term: The data term uses corresponding functions on the partial and full shapes and differentiates the residual CA−B(η(v)).F and G contain the sampled functions, while A and B contain their projections onto the functional bases.
Area term: The area-term derivative uses the local area elements associated with corresponding vertices on the full and partial meshes.The derivative of η(v_p) is supplied separately in the appendix.
Mumford-Shah term: The Mumford-Shah gradient differentiates the part-weight function ξ(v) and includes a zero contribution where the gradient of v vanishes.The resulting gradient is assembled from the partial derivatives of ξ(v).
Discrete geometry: The derivative expressions use triangle-neighborhood quantities K_j and account for possible changes in local vertex ordering.The notation allows the ordering of triangle vertices to vary across incident triangles.
Functional-map gradients: The appendix separately gives derivatives for the data, weight-matrix, and orthogonality terms with respect to C.These derivatives complement the derivatives with respect to v.

Appendix C - Perturbation Analysis

The appendix derives how Laplace–Beltrami eigenvalues and eigenvectors vary under shape-part removal, using matrix perturbation analysis and simplifying spectral assumptions. It also introduces boundary interaction strength to quantify eigenbasis variation caused by the boundary split.

Perturbation analysis: Theorem 1 expresses the perturbed operator through eigenvalues and eigenvectors, providing the basis for differentiating spectral quantities under part removal.The operator is represented as L_N + tP_N = Φ(t)^⊤Λ(t)Φ(t), with Λ(t) diagonal and Φ(t) containing the corresponding eigenvectors.
Perturbation analysis: Classical symmetric-matrix perturbation analysis computes eigenvalue derivatives by differentiating the eigendecomposition and projecting through the eigenbasis.The derivation left-multiplies by Φ^⊤, uses Φ′ = ΦB, and relies on the skew-symmetry of B to obtain zero diagonal entries.
Spectral assumptions: The analysis assumes that the relevant operators have no repeated eigenvalues, including distinctness between non-zero eigenvalues of the two complementary subshapes.These assumptions enable the derivative formulas for both eigenvalues and non-constant eigenvectors.
Spectral decomposition: At the zero-perturbation limit, the full operator’s spectrum combines the spectra of the retained and removed parts, while eigenvectors are padded with zeros on missing regions.This decomposition connects spectral behavior of the subshapes to the perturbation analysis of the original shape.
Boundary interaction strength: Boundary interaction strength measures how the eigenbasis varies as the boundary splits the shape into retained and removed regions.The appendix frames this variation as a function of the boundary separating the two parts.