Multi-part shape matching by simultaneous partial functional correspondence

Abstract

Non-rigid multi-part shape matching has proven to be essential and challenging in many applications. This paper analyzes the aforementioned problem and proposes a novel multi-part shape matching method to simultaneously compute correspondences between a full shape and its multiple parts undergoing a non-rigid deformation. The main idea is to simultaneously integrate the Hamiltonian eigenvalue equivalence strategy as a part regularization term being fully spectral with the partial functional map. Moreover, we introduce a new upsampling refinement approach based upon ZoomOut in conjunction with the regularized point-wise map recovery algorithm to obtain high-quality partial matches. Our method naturally handles various challenges and noise that commonly occur in real scans, like non-rigid deformations, strong partiality, topological noise, and symmetric ambiguity. Finally, we demonstrate superior qualitative and quantitative results on several datasets. We show that our method produces more accurate, smoother results than other competing methods in realistic scenarios.

1 Introduction

Shape correspondence between 3D shapes is a fundamental problem in computer graphics and computer vision. Different flavors of this problem arise in a variety of applications ranging from animation [1], texture transfer [2], statistical shape analysis [3, 4], and shape retrieval [5], to robotic vision [6] and computational archaeology [7, 8].

Finding dense matches among multi-part shapes is a research topic that has received much attention in recent years [9, 10]. Particularly, challenging settings of this problem include: non-rigid correspondence, where the near-isometric shape undergoes certain degrees of elastic deformations [11]; partial matching, where a subset of the shape has to be matched to another full shape; and multiple part shape correspondence, where a reference shape is given and multiple parts partially matching the reference. Each of these parts may contain overlapping parts and have additional clutter.

In general, such multi-part shape matching problems, which can be described as solving multiple pairwise partial matching problems simultaneously, are more computationally difficult than pairwise matching issues. Practical scenarios combine the above settings and clutter and topological noise, which are notoriously hard. Most existing methods for computing correspondence within shape collections can only be suitable for full shapes and do not consider these practical scenarios.

While working in the same general setting, we proposed a novel method for computing a detailed, high-quality correspondence between non-rigid multiple parts and full shape in the collection. Our work is motivated by the fact that this formulation can be used as a first step toward automatic reconstruction of the deformable shapes, in which one tries to match multiple scans to a near-isometric general model. Examples of applications include computational archaeology (assembly of fractured objects). Additional uses are assisting orthopedic surgeons in putting fragmented bones back together using a healthy bone 3D model. We have conducted extensive evaluations on various benchmark datasets. Experimental results show that the proposed algorithms significantly outperform existing state-of-the-art partial matching techniques of shape collections.

The main contributions of our work can be summarized as follows:

• (1) We propose a new part regularization term with a purely spectral nature to promote the localizing accuracy in the simultaneous partial functional maps framework, based on the fully spectral partial matching (FSPM) [12] technology.

• (2) We introduce a new refinement scheme for map recovery that combines the regularized point-wise map recovery (RPMR) [13] algorithm and the iterative upsampling technique dubbed ZoomOut [14] while leading to a significant improvement in accuracy in several challenging cases.

2 Related work

In its full generality, shape matching is an extremely well-studied area of computer graphics and computer vision [15]. Its complete overview is beyond the scope of our paper. Therefore, below we review the methods most closely related to ours, concentrating on techniques to produce correspondences within non-rigid partial shapes and shape collections. We refer the interested readers to recent surveys, including [1, 16] for more in-depth discussions.

2.1 Functional correspondence

Our method fits within the functional map representation, initially introduced in [17], modeling correspondences as linear operators between spaces of functions on manifolds. This framework’s key innovation can express maps as small matrices encoded on a reduced basis, significantly simplifying the associated optimization problems. However, because the basis consists of the first few eigenfunctions of the Laplace–Beltrami operator, functional maps can only transfer sufficiently smooth functions, leaving out high-frequency details. It severely limits the applicability of the functional map.

Several authors have proposed extensions of the functional map framework. Pokrass et al. [18] improved the framework by employing sparsity-based priors and extended it to solve the unknown permutation of the unordered inputs. Gasparetto et al. [19] defined a novel approach to compute a continuous bijective map between two surfaces moving from the low rank spectral representation to a sparse spatial representation. In [20], the authors presented a spectral formulation for the generalized multi-dimensional scaling method. Further, Yang et al. [21] calculated shape correspondences using functional maps by calibrating the basis matrix between 3D geometric shapes. Nevertheless, the above methods’ common deficiency is that they always fail to compute correspondence under moderate non-isometries.

Recently, some approaches have extended this framework to computing non-isometric matching. Eynard et al. [22] exploited functional maps in different directions to make their method more robust to non-isometric deformations. This approach enforces orthonormality as a hard constraint, which is unlikely to hold on a reduced basis and leads to a non-convex problem. Ezuz et al. [23] formulate a non-isometric correspondence optimization problem, aiming to minimize the energy that tries to preserve a given landmark correspondence or functional correspondence while penalizing the Dirichlet energies of the forward and backward maps. In follow-up work [24], the authors used similar reversibility energy to obtain more accurate non-isometric maps. This energy is composed of nonlinear membrane energy that favors isometry and bending energy that is rotation invariant and promotes feature alignment. However, this method needs to deal with the bijective matching problem to get the membrane and elastic energies, leading to more massive computation than [23].

As another possible remedy, several recent works considered alternatives to the Laplace–Beltrami basis. Melzi et al. [25] introduced a new framework for local spectral shape analysis. The key idea is to construct localized bases by spectral decomposition of a modified Laplacian operator, crafted primarily to provide eigenfunctions with local support. This approach’s limitation is that the region information may not be available in specific unsupervised applications to carry out the localized spectral analysis. Closely related to [25] is the recent approach of Wang et al. [26]. Using the Steklov operator as an extrinsic alternative to the Laplace–Beltrami operator, they introduced a practical and mathematically justified spectral system to extrinsic geometry for shape analysis. Nevertheless, the most prominent drawback is that the primary boundary element method may fail when triangle meshes self-overlap.

Indeed, despite these methods’ success, recovering a point-to-point map from its functional representation is still considered a common requirement in many practical applications. In [27], the authors showed that by representing descriptors as linear operators acting on functions through point-wise multiplication, it is possible to improve the quality of the recovered functional map significantly. Unlike [27], which has always restricted the functional subspaces to linear combinations of basis functions, Nogneng et al. [28] showed that they could construct a much richer space by exploiting point-wise products of basis functions. However, this method suffers from the restrictive assumptions about the inputs and only uses low-order product pairs of basis functions. Rodolà et al. [13] introduced a simple probabilistic model for map recovery and refinement. Nevertheless, it cannot achieve high-quality transfer accuracy while dealing with partial correspondence.

2.2 Partial correspondence

Iterative closest point (ICP)-like approaches [29, 30] have tackled early rigid partial correspondence problems arising from fusion or completion of multiple 3D scans. In recent years, people attempt to extend these ideas to the non-rigid case in single nonlinear optimization [11]. Unfortunately, it requires an excellent initial input to guarantee that the final map is smooth or bijective in most cases.

Most recent works addressing the partial dense correspondence problem can cope with non-rigid shapes. Bronstein et al. [31] used generalized multi-dimensional scaling to embed one mesh in another for partial matching. In follow-up work, Bronstein et al. [32] combined metric distortion minimization proposed by [31] with optimization over regular matching parts, showing an algorithm that maximizes the regularity of corresponding parts in the given shapes. Being a superior mathematical formulation, the methods mentioned above rely upon repeatedly computing geodesic distances between arbitrary pairs of points on a mesh, and so it is expensive to calculate. Windheuser et al. [33] studied a framework for non-rigid three-dimensional shape matching, which is geometrically consistent because it uses discrete graph surfaces to induce continuous and orientation-preserving matchings. It shows that although this method allows dealing with partiality, it depends on the assumption of mesh water tightness, which is hugely complex to compute. Sahillioğlu et al. [34] proposed a voting-based formulation to match shape extremities, which are assumed to be preserved by the partiality transformation. However, conventional ways of computing geodesic distances, which the techniques rely on, become invalid on noisy surfaces with holes and gaps.

Several works tried to employ machine learning methods to compute partial correspondence. Convolutional neural networks (CNNs) on non-Euclidean domains were first considered by Masci et al. [35] who introduced the geodesic CNN model, a deep learning framework for computing dense correspondences between deformable and deformed shapes. Nevertheless, a vital drawback of this method lies in its emphasis on learning a descriptor. The learning process remains agnostic to compute the final correspondence, and costly post-processing steps are often necessary to obtain accurate solutions from the learned descriptors. Wei et al. [36] employed a deep CNN architecture that finds exact and dense correspondences between clothed human body shapes with partial input data. Although successful in the presence of sufficient training data, this approach can lead to artifacts, such as outliers, requiring post-processing to achieve high-quality maps.

Most of the partial correspondence methods, as mentioned above, are point-wise. Follow-up work [37] showed that functional maps could also deal with specific settings with missing parts. Rodolà et al. [38] extended the functional correspondence framework to deal with partial correspondence, dubbed partial functional maps (PFMs). Nevertheless, the primary deficiency of PFM is its explicit model of the part, requiring a somewhat cumbersome solver alternating between optimization in the spatial domain and the spectral domain. To address this challenge, Litany et al. [12] proposed an efficient method called fully spectral partial matching (FSPM), computing a dense intrinsic correspondence between non-rigid partial and full shapes in the entire spectral domain. This approach suffers from the requirement of a proper initialization in the spectral domain or will lead to an inaccurate part-to-full correspondence. More recently, Wu et al. [39] introduced a novel approach using fully spectral eigenvalue alignment (FSEA) and upsampling refinement (UR), dubbed FSEAUR, for partial computing correspondence, demonstrating noticeable improvement upon the classical partial matching method FSPM.

2.3 Multiple shape correspondence

While most rigid shape correspondence techniques concentrate on the pairwise setting, several methods have been proposed to find correspondences in the context of shape collections. The authors of [8] presented an algorithm for assembling fractured surfaces. They can generate a collection of cycle-consistent maps from maps associated with a spanning tree in the model graph. However, this approach only optimizes the spanning trees greedily and locally, often resulting in sub-optimal solutions. Torsello et al. [40] cast the multi-view registration problem into the diffusion of rigid transformations over the graph of adjacent scans. It only transfers the registration errors between coordinate frames but does not update the correspondences through the registration process. Litany et al. [41] proposed an approach to address simultaneous matching and segmentation of multiple shapes. The authors gave a reference shape and used the approach to match multiple parts to the reference. Litany et al. [42] extended PFM [38] to the multiple partial shape correspondence, which can be considered as a non-rigid generalization of the problem of the rigid puzzles solved in [41] dubbed as non-rigid puzzles (NRP). While coming with significant advantages, the restriction of this work is still the complicated alternating optimization. At the same time, Cosmo et al. [43] proposed a method for dense matching of deformable objects in cluttered 3D scenes, which is the first attempt at solving this problem in a fully deformable setting. This method’s main limitation is that it relies on local features to initialize the pipeline, and the presence of clutter and missing parts result in distorted distance values.

Sahillioğlu et al. [44] explicitly minimize the average isometric distortion over all possible pairs of collection shapes via dynamic programming efficiently without any initial set of maps. Still, it is limited to provide only a sparse correspondence. In [45], the authors constructed a consistent functional map framework that discovers shared structures within heterogeneous shape collections. Nevertheless, this work cannot deal with partial correspondence. Yang et al. [46] presented a method to obtain correspondence in the non-rigid model cluster based on the functional map framework and cycle consistency constraints. While showing impressive quality in challenging settings, the work needs to adjust the parameters manually during the calculation. Cohen et al. [47] proposed a method to automatically match two shape collections with a similar shape space structure and compute the collections’ inter-maps. However, this approach requires the parallel variations within each cluster, and the non-symmetric shape space embeddings, which is slow. Further, Huang et al. [48] formulated a novel multi-scale synchronization approach and extended the basic functional map synchronization. This work suffers at the quality of the initial maps and cannot provide theoretical guarantees on processing collections of partial shapes.

3 Background

3.1 Manifolds

We model shapes as smooth two-dimensional Riemannian manifolds S embedded into ${\mathbb{R}}^{3}$. We further equip the manifold with area elements ds induced by the standard metric. Given the intrinsic gradient $\nabla_{S}$, we consider the positive semidefinite Laplace–Beltrami operator $\Delta_{S}$ as the divergence of the gradient

$$ \Delta_{S} = {\text{div}}_{S} (\nabla_{S} ), $$

(1)

which provides us with all the tools of Fourier analysis on the manifold.

We define two scalar functions $h_{1} ,\;h_{2} :S \to {\mathbb{R}}$, and the standard inner product is $\left\langle {h_{1} ,\left. {h_{2} } \right\rangle } \right._{S} { = }\int_{S} {h_{1} h_{2} {\text{d}}s}$. At each point x, the Laplace–Beltrami operator admits an orthonormal eigendecomposition on the compact manifold S

$$ \Delta_{S} \phi_{i} (x) = \lambda_{i} \phi_{i} (x)\quad x \in {\text{int}} (S), $$

(2)

$$ \phi_{i} (x) = 0\quad x \in \partial S, $$

(3)

with homogeneous Dirichlet boundary conditions (3), where int(S) and $\partial S$ denote the interior and boundary of S, respectively. Here, $\{0 = \lambda_{1} \le \lambda_{2} \le \ldots \}$ are eigenvalues and $\phi_{1} ,\;\phi_{2} , \ldots$ are the corresponding eigenfunctions, forming the orthonormal basis of square-integrable functions space $L^{2} (S) = \{ h:S \to {\mathbb{R}}\left| {\left\langle {h,\;\left. h \right\rangle } \right.} \right._{S} < \infty \}$ on S. We can represent any function $h \in L^{2} (S)$ via the Fourier series expansion

$$ h(x) = \sum\limits_{i \ge 1} {\left\langle {h,\;\phi_{i} } \right\rangle_{S} } \phi_{i} (x). $$

(4)

3.2 Functional map

We build our work upon the functional map representation [17] and its estimation pipeline. Suppose a pair of shapes X and Y consists of n₁ and n₂ points, respectively. Let $T:X \to Y$ be a bijective mapping. The functional map’s essential view is to identify correspondences between shapes by a linear operator $T_{F} :\;L^{2} (X) \to L^{2} (Y)$, mapping functions on X to functions on Y by the composition. T_F is the functional representation of the mapping T. The basic pipeline of the functional map for computing correspondences between X and Y consists of the following general steps:

• (1) Construct a set of basis functions on both X and Y. The most common basis choice is the Laplace–Beltrami eigenfunctions, which satisfy the critical requirements of choosing a basis for functional maps: compactness and stability. Compute sets $k_{1} \ll n_{1}$, $k_{2} \ll n_{2}$ of basis functions $\{ \phi_{i} \}_{i \ge 1}$, $\{ \psi_{j} \}_{j \ge 1}$ on each shape by taking the first few eigenfunctions of the respective Laplace–Beltrami operators, and store them as columns of matrices ${{\varvec{\Phi}}}{ = (}\phi_{{1}} , \ldots ,\phi_{{k_{1} }} {)}$ and ${{\varvec{\Psi}}}{ = (}\psi_{{1}} , \ldots ,\psi_{{k_{2} }} {)}$, of sizes n₁ × k₁ and n₂ × k₂, respectively.

• (2) Assume given a set of q corresponding descriptor (also called scalar) functions $\{ f_{1} , \ldots ,f_{q} \} \subseteq L^{2} (X)$ and $\{ g_{1} , \ldots ,g_{q} \} \subseteq L^{2} (Y)$ on the shapes. The descriptor functions (e.g., heat kernel signature (HKS) [49], wave kernel signature (WKS) [50], and average mixing kernel signature (AMKS) [51]) identify each point uniquely and are approximately preserved by the mapping. Express them in the given (Laplace–Beltrami) basis and store their coefficients as columns of matrices ${\mathbf{A}} = (\left\langle {f,\phi_{i} } \right\rangle_{X} )$ and ${\mathbf{B}} = (\left\langle {g,\psi_{j} } \right\rangle_{Y} )$, of sizes k₁ × q and k₂ × q, respectively.

• (3) The correspondence between X and Y can be written simply as CA = B, where C is the functional representation of the map. Compute the optimal functional map k1 × k₁ matrix C by solving the following optimization problem:

  $$ \begin{aligned} {\mathbf{C}} & = \mathop {\arg \min }\limits_{{{\mathbf{C}}_{XY} }} E_{desc} ({\mathbf{C}}_{XY} ) + E_{reg} ({\mathbf{C}}_{XY} ), \\ & = \mathop {\arg \min }\limits_{{{\mathbf{C}}_{XY} }} \left\| {{\mathbf{C}}_{XY} {\mathbf{A}} - \left. {\mathbf{B}} \right\|} \right.^{2} + \varsigma \left\| {{{\varvec{\Lambda}}}_{Y} } \right.{\mathbf{C}}_{XY} - \left. {{\mathbf{C}}_{XY} {{\varvec{\Lambda}}}_{X} } \right\|^{2} , \\ \end{aligned} $$

  (5)

  where ${{\varvec{\Lambda}}}_{X}$ and ${{\varvec{\Lambda}}}_{Y}$ are diagonal matrices of Laplace–Beltrami eigenvalues on the two shapes and $\varsigma$ is a small scalar weighting parameter. Unless stated otherwise, it is common to use the Frobenius norm $\left\| \cdot \right\|$ to compute these matrices’ distance. The first term $E_{desc} ({\mathbf{C}}_{XY} )\;{ = }\; \left\| {{\mathbf{C}}_{XY} {\mathbf{A}} - \left. {\mathbf{B}} \right\|} \right.^{2}$ is the general form of functional correspondence problem. The second term $E_{reg} ({\mathbf{C}}_{XY} ) \;{ = }\; \varsigma \left\| {{{\varvec{\Lambda}}}_{Y} } \right.{\mathbf{C}}_{XY} - \left. {{\mathbf{C}}_{XY} {{\varvec{\Lambda}}}_{X} } \right\|^{2}$ regularizes the map by promoting its overall correctness, which is associated with the standard assumption that the sought map should be approximately intrinsically isometric [52,53,54].

• (4) Recovering point-wise map from the functional map C. This post-processing step (i.e., the refinement process) can be performed via map reconstruction approaches, such as ICP or the deblurring and denoising approach [55].

3.3 Fully spectral partial matching

The functional map framework can handle uncertainty and incomplete information more gracefully but is not designed to address partial correspondences in principle and require more information (e.g., point landmarks) to obtain accurate results. FSPM is an efficient spectral domain method for calculating partial dense correspondence proposed by Litany et al. [12], build on PFM [38] and joint approximate diagonalization (JAD) of Laplacians [56].

Assume given a partial shape X and a full shape Y, nearly isometric to sub-part $X^{\prime} \subseteq Y$. The manifolds X and Y are discretized as triangular meshes with n₁ and n₂ vertices, respectively. We aim at calculating partial functional map $T_{F} :L^{2} (X) \to L^{2} (Y)$ mapping functions supported on X to functions in the region $X^{\prime}$. Truncating the Fourier series at the first k coefficients, we give the first k Laplace–Beltrami eigenvalues of the partial shape X and the full shape Y, respectively. In other words, the first k terms are a low-pass approximation of the full map. Since X and $\overline{X}$ are disjoint parts, the n₂ × n₂ Laplacian matrix ${{\varvec{\Delta}}}_{Y}$ is composed of n₁ × n₁ ${{\varvec{\Delta}}}_{X}$ and (n₂-n₁) × (n₂-n₁) ${{\varvec{\Delta}}}_{{\overline{X} }}$. The eigenvalues of ${{\varvec{\Delta}}}_{Y}$ form a mixed sequence composed of the eigenvalues from ${{\varvec{\Delta}}}_{X}$ and ${{\varvec{\Delta}}}_{{\overline{X} }}$, so only the first $r < k$ eigenvalues of ${{\varvec{\Delta}}}_{X}$ will exist in the first k eigenvalues of ${{\varvec{\Delta}}}_{Y}$ (see Fig. 1).

Fig. 1

The eigenvalues and eigenfunctions of ${{\varvec{\Delta}}}_{Y}$ consist of those of the blocks ${{\varvec{\Delta}}}_{X}$ and ${{\varvec{\Delta}}}_{{\overline{X} }}$

Note that different from the full-to-full setting, the eigenfunctions $\{ \phi_{i} \}_{i \ge 1}$ of partial shape X correspond to the “full” eigenfunctions $\{ \psi_{j} \}_{j \ge 1}$ of Y with $j \ge i$. Under this result, it can derive that the matrix ${\mathbf{C}} = (\left\langle {T_{F} (\phi_{i} ),\psi_{j} } \right\rangle )$ of the partial functional map has a slanted–diagonal structure, whose diagonal slope is obtained using the following approximate form:

$$ \theta { = }\frac{r}{k} $$

(6)

Let ${\mathbf{A}} = (\left\langle {f,\phi_{i} } \right\rangle_{X} )$ and ${\mathbf{B}} = (\left\langle {g,\psi_{j} } \right\rangle_{Y} )$ be the k × q matrices of the respective Fourier coefficients. The partial functional correspondence has the form

$$ {\mathbf{CA}} = {\mathbf{B}}(v), $$

(7)

where the soft indicator function v is defined as

$$ v(x) = \left\{ {\begin{array}{*{20}c} 1 & \; {x \in X^{^{\prime}} } \\ 0 & \; {x \notin X^{^{\prime}} } \\ \end{array} } \right.. $$

(8)

${\mathbf{B}}{(}v{) = (}\left\langle {v \cdot g,\;\psi_{j} } \right\rangle_{Y} {)}$ is the r × q matrix of Fourier coefficients weighted by v, which acts as a mask restricted to the area $X^{\prime}$. From Eq. (7), we obtain that it gives rise to a k × k matrix C encoding the partial functional correspondence.

In light of the previous analysis, it can conclude that the computation of C by the functional map framework relies on a pair of coefficient matrices on shapes. On the contrary, FSPM tacitly assumes that C is an identity matrix and then calculates the transformation coefficients matrix, as we elucidate in the following.

Equation (7) can be formulated as

$$ {\mathbf{C}}^{{\text{T}}} {\mathbf{CA}} = {\mathbf{C}}^{{\text{T}}} {\mathbf{B}}(v). $$

(9)

Since the matrix C would manifest a slanted diagonal structure with most off-diagonal elements close to zero, ${\mathbf{W}} = {\mathbf{C}}^{{\text{T}}} {\mathbf{C}}{ = }\left[ {\begin{array}{*{20}c} {{\mathbf{I}}_{r} } & 0 \\ 0 & 0 \\ \end{array} } \right]_{k \times k}$, where I_r is an identity matrix of size r × r. To make WA containing the first r rows of A, W is cut to a $r \times k$ matrix ${\mathbf{W}}_{r \times k} { = [}\begin{array}{*{20}c} {{\mathbf{I}}_{r} } & 0 \\ \end{array} {]}_{r \times k}$. The key novelty of FSPM is to search for a new basis locating at the potential part of the full shape instead of computing the partial functional map between shapes. To this end, they replace the matrix C by Q and rewrite Eq. (9) as

$$ {\mathbf{W}}_{r \times k} {\mathbf{A}} = {\mathbf{Q}}^{{\text{T}}} {\mathbf{B}}(v), $$

(10)

where the r × k matrix Q is not considered as the functional representation of the map, but a transformation coefficients matrix for the basis [12]. Further, the new basis is constructed as $\widehat{\psi }_{i} = \sum\nolimits_{j = 1}^{k} {q_{ji} \psi_{j} }$, where q_ji is the elements of the matrix Q^T. In a nutshell, ${\mathbf{U}}(v) = {\mathbf{Q}}^{{\text{T}}} {\mathbf{B}}(v)$ is the transformation coefficients of $\{ g_{i} \}_{i = 1}^{q}$ restricted to the area indicated by v in the new bases $\{ \widehat{\psi }_{j} \}_{j \ge 1}$ and leads to the following equation:

$$ {\mathbf{U}}(v) = \left( {\left\langle {v \cdot g,\;\widehat{\psi }_{j} } \right\rangle_{Y} } \right). $$

(11)

Without loss of generality, the new basis functions $\{ \widehat{\psi }_{j} \}_{j \ge 1}$ must be localized; thus, $\widehat{\psi }_{j} = v \cdot \widehat{\psi }_{j}$ for all j. Thus, we get to

$$ {\mathbf{U}}(v) = {\mathbf{U}}, $$

(12)

and absorb the indicator function v into the new bases. The equality in (10) becomes

$$ {\mathbf{W}}_{r \times k} {\mathbf{A}}{ = }{\mathbf{U = Q}}^{{\text{T}}} {\mathbf{B}}. $$

(13)

For the modified basis ${\text{\{ }}\widehat{\psi }_{j} {\text{\} }}_{j \ge 1}$ to behave more like eigenfunctions for ${{\varvec{\Delta}}}_{Y}$, it has to satisfy a constraint that the Dirichlet energy

$$ \sum\limits_{i}^{k} {\left\langle {{{\varvec{\Delta}}}_{Y} \widehat{\psi }_{i} ,\widehat{\psi }_{i} } \right\rangle_{Y} = } {\text{trace(}}{\mathbf{Q}}^{{\text{T}}} {{\varvec{\Lambda}}}_{Y} {\mathbf{Q}}{)} $$

(14)

should converge to a minimum, where trace() is the trace of a square matrix denoting the sum of the matrix’s eigenvalues and ${{\varvec{\Lambda}}}_{Y} {\text{ = diag(}}\xi_{1} , \ldots ,\xi_{i} {)}$ is a diagonal matrix containing the first k eigenvalues of ${{\varvec{\Delta}}}_{Y}$. Ideally, this behavior is explained by the fact that $\left\langle {{{\varvec{\Delta}}}_{Y} \widehat{\psi }_{i} ,\widehat{\psi }_{j} } \right\rangle_{Y} { = }\xi_{i} \delta_{ij}$, where $\xi_{i}$ are the eigenvalues of the full shape Y.

Replacing the trace term by an off-diagonal penalty ${\text{off(}}{\mathbf{E}}{)} = \sum\nolimits_{i \ne j} {\left| {e_{ij} } \right|^{2} }$, where e_ij denotes the elements of matrix E, we consider to solve the following optimization problem:

$$ \mathop {\arg \min }\limits_{{{\mathbf{Q}} \in S\left( {r,k} \right)}} \alpha \left\| {{\mathbf{W}}_{r \times k} {\mathbf{A}} - {\mathbf{Q}}^{{\text{T}}} {\mathbf{B}}} \right\|_{2,1} + {\text{off}}\left( {{\mathbf{Q}}^{{\text{T}}} {{\varvec{\Lambda}}}_{Y} {\mathbf{Q}}} \right){,} $$

(15)

where optimization is done over the Stiefel manifolds $S(r,k) = \{ {\mathbf{P}} \in {\mathbb{R}}^{r \times k} :\;{\mathbf{P}}^{{\text{T}}} {\mathbf{P}} = {\mathbf{I}}_{k} \}$ and $\alpha$ denotes a weight. The L_2,1 norm $\left\| {\mathbf{E}} \right\|_{2,1} = \sum\nolimits_{i} {\left\| {e_{i} } \right\|}_{2}$, where e_i is the ith column of E, affects the optimal value insensitive to outlier functional correspondences and promotes column-wise sparsity.

It is important to remark that, while the transformation coefficients matrix Q is the solution to Eq. (15)’s optimization problem, this is not the only aim as it directly deduces matrix B to obtain functional map C. This way, it would be natural to calculate the partial correspondence entirely in the spectral domain.

3.4 Fully spectral eigenvalue alignment

The main drawback of FSPM is the lack of localized behavior in the spatial domain, leading to an inaccurate part-to-full correspondence. One of the main contributions of our work is a significant improvement allowing us to introduce an effective and straightforward part regularization term into the optimization problem, endowing our solutions with guarantees of high localizing accuracy. Our technique bears a resemblance to Hamiltonian spectrum alignment [57], dubbed fully spectral eigenvalue alignment (FSEA) [39]. Still, it has a significant difference that Rampini et al. [57] designed the spectral alignment algorithm to detect similar regions among deformable shapes, not to solve for partial correspondence. We aim to use a new part regularization to be fully spectral, viewed as an extension of the Hamiltonian spectrum alignment, which will promote localizing accuracy in the partial correspondence method.

3.4.1 Hamiltonian operator

The basis defined by the classical Hamiltonian operator from quantum mechanics is a new choice for shape analysis in many senses [58]. Furthermore, we can use the basis defined by the Hamiltonian to solve partial correspondences between non-rigid shapes. The scenario we consider concerns matching an approximately isometric deformation of part X to the full shape Y. One can obtain a Hamiltonian operator H_Y on the manifold Y by adding a potential function to the Laplacian. Then, the Hamiltonian operator H_Y has the elliptic operators form

$$ H_{Y} = {{\varvec{\Delta}}}_{Y} + \beta , $$

(16)

with the Laplace–Beltrami operator ${{\varvec{\Delta}}}_{Y}$ and the scalar potential function $\beta :Y \to {\mathbb{R}}$. That is, $\beta$ is also a Heaviside step function that places zero energy density on a subset $X^{\prime}$ of Y and $\tau > 0$ on the complement $\overline{X^{\prime}}$. Formally,

$$ \beta (x) = \left\{ {\begin{array}{*{20}c} 0 & \; {x \in X^{^{\prime}} } \\ \tau & \; {x \in \overline{{X^{^{\prime}} }} } \\ \end{array} } \right.. $$

(17)

Since ${{\varvec{\Delta}}}_{Y}$ and $\beta$ are self-adjoint, the resulting Hamiltonian H_Y as a sum of them is also self-adjoint. We can almost directly derive its spectral theory from the regular Laplacian. Thus, the Hamiltonian H_Y admits a spectral decomposition:

$$ H_{Y} \varepsilon_{i} (x) = \mu_{i} \varepsilon_{i} (x), $$

(18)

where the eigenvalues $\mu_{i}$ form a discrete spectrum $\{ \mu_{1} ,\mu_{2} , \ldots \}$ and the eigenfunctions $\varepsilon_{1} ,\varepsilon_{2} , \ldots$ form an orthonormal basis.

From Eqs. (17) and (18), we note that the Hamiltonian eigenfunctions $\varepsilon_{i}$ denote the particle’s energy, and the finite step potential function $\beta$ divides the region Y into two constant potential spaces. In the null potential energy region where $\beta (x) = 0$, the particle is free to pass, and the approximate equality $H_{Y} \approx {{\varvec{\Delta}}}_{Y}$ holds for all $x \in X^{\prime}$. On the other hand, for the high potential region where $\beta (x) = \tau$ $\forall x \in \overline{X^{\prime}}$, the particle cannot penetrate and its eigenenergy $\varepsilon_{i}$ decays exponentially and vanishes when the corresponding eigenvalues $\mu_{i} < \tau$. As analyzed above, the scalar potential function $\beta (x)$ ensures that the eigenfunctions corresponding to eigenvalues $\mu_{i} < \tau$ are restricted to the null potential energy region, akin to the soft indicator function v mentioned above.

3.4.2 Generalized eigenproblem

To compute the Hamiltonian eigenvalues and eigenvectors, we should solve a generalized eigenvalue problem. At the moment, one can do this job by analyzing the discrete operator for reconstructing triangle meshes [59, 60].

In the discrete setting, we approximate the shape Y by manifold triangle mesh sampled at vertices $\{ p_{i} \}_{i = 1}^{{n_{2} }}$. The discrete Hamiltonian operator of the shape Y assumes the form of a matrix

$$ H_{Y} \; { = } \; {\mathbf{S}}_{Y}^{{ - 1}} {\mathbf{M}}_{Y} {\text{ + diag(}}{\mathbf{V}}{)} $$

(19)

with an n₂-dimensional vector V containing the values of the potential $\beta$ at each vertex, where S_Y is a diagonal matrix of local area elements s_i and M_Y is a stiffness matrix of cotangent weights, defined in terms of the discrete metric as

$${m_{ij}} = \left\{ {\begin{array}{*{20}{l}}{{{{\rm{ - (}}\cot {\theta _{ij}} + \cot {\eta _{ij}}{\rm{)}}} \mathord{\left/ {\vphantom {{{\rm{ - (}}\cot {\theta _{ij}} + \cot {\eta _{ij}}{\rm{)}}} 2}} \right. \kern-\nulldelimiterspace} 2}}&\quad {{\rm{if}}\;{\rm{ }}i\;{\rm{ and}}\;{\rm{ }}j\;{\rm{ are }}\;{\rm{adjacent}}}\\{\sum\limits_{h \ne i} {{{(\cot {\theta _{ih}} + \cot {\eta _{ih}})} \mathord{\left/ {\vphantom {{(\cot {\theta _{ih}} + \cot {\eta _{ih}})} 2}} \right. \kern-\nulldelimiterspace} 2}} }&\quad {{\rm{if}}\;{\rm{ }}i = j}\\{{\rm{ }}0}&\quad {{\rm{otherwise}}}\end{array}} \right.$$

(20)

Figure 2 depicts our notation. s_i is the area of the shaded region in the same figure.

Fig. 2

Discretization of the Hamiltonian operator on a triangular mesh

In the case of the Laplacian, the generalized eigenproblem thus takes the form:

$$ {\mathbf{S}}_{Y}^{{ - 1}} {\mathbf{M}}_{Y} {{\varvec{\Phi}}} = {{\varvec{\Phi}}}{\text{diag(}}{{\varvec{\uplambda}}}{)}, $$

(21)

where ${{\varvec{\Phi}}} = (\phi_{1} , \ldots ,\phi_{k} )$ is a matrix containing the first k Laplacian eigenfunctions as columns and ${{\varvec{\uplambda}}}{\text{ = \{ }}\lambda_{1} , \ldots ,\lambda_{k} {\text{\} }}$ is a k-dimensional vector of the corresponding Laplacian eigenvalues.

In the case of the Hamiltonian, the generalized eigenproblem

$$ ({\mathbf{S}}_{Y}^{{ - 1}} {\mathbf{M}}_{Y} {\text{ + diag(}}{\mathbf{V}}{)}){\mathbf{\rm E}} = {\mathbf{\rm E}}{\text{diag(}}{{\varvec{\upmu}}}{)} $$

(22)

is solved for computing the Hamiltonian eigenfunctions and eigenvalues. ${\mathbf{\rm E}} = (\varepsilon_{1} , \ldots ,\varepsilon_{k} )$ and ${{\varvec{\upmu}}}{\text{ = \{ }}\mu_{1} , \ldots ,\mu_{k} {\text{\} }}$ are the first k eigenpairs. We readily obtain the Hamiltonian eigenvalues of Eq. (22) as ${{\varvec{\upmu}}}{(}{\mathbf{S}}_{Y}^{{ - 1}} {\mathbf{M}}_{Y} {\text{ + diag(}}{\mathbf{V}}{))}$.

3.4.3 Eigenvalue alignment

Let $\{ (\mu_{i} ,\varepsilon_{i} )\}_{i = 1}^{k}$ and $\{ (\lambda_{i} ,\phi_{i} )\}_{i = 1}^{k}$ be the first k Hamiltonian eigenpairs of the full shape Y and the first k Laplacian eigenpairs of the partial shape X with the homogeneous Dirichlet boundary conditions, respectively. We consider that the partial shape X corresponds to the region $X^{\prime} \subseteq Y$ on the full shape Y up to isometry.

From (16) and (18), we can expand the eigendecomposition of H_Y as

$$ \begin{aligned} H_{Y} \varepsilon_{i} (x) & = {{\varvec{\Delta}}}_{Y} \varepsilon_{i} (x) + \beta (x)\varepsilon_{i} (x) \\ & = \mu_{i} \varepsilon_{i} (x). \\ \end{aligned} $$

(23)

In light of our previous analysis, if $x \in X^{\prime}$, the approximate equality $H_{Y} \approx {{\varvec{\Delta}}}_{X^{\prime}}$ holds point-wise. We can write Eq. (23) as

$$ {{\varvec{\Delta}}}_{X^{\prime}} \varepsilon_{i} (x) = \mu_{i} \varepsilon_{i} (x). $$

(24)

If we make the partial shape X an excellent localization to the corresponding latent region $X^{\prime} \subseteq Y$, $\phi_{i}$ of ${{\varvec{\Delta}}}_{X}$ has the same values as $\varepsilon_{i}$ of ${{\varvec{\Delta}}}_{X^{\prime}}$ at corresponding points with the Dirichlet boundary (i.e., $\phi_{i} (x) = 0$ for $x \in \partial M$). Thus,

$$ {{\varvec{\Delta}}}_{X^{\prime}} \varepsilon_{i} (x) = {{\varvec{\Delta}}}_{X} \phi_{i} (x). $$

(25)

According to Eq. (24) and ${{\varvec{\Delta}}}_{X} \phi_{i} (x){ = }\lambda_{i} \phi_{i} (x)$, equality in (25) becomes

$$ \mu_{i} \varepsilon_{i} (x) = \lambda_{i} \phi_{i} (x). $$

(26)

Therefore, we draw the following conclusion:

$$ \mu_{i} \;{ = }\; \lambda_{i} . $$

(27)

We conclude from the above analysis that under the assumption of providing an indicator for the correspondence region on a full shape, one can align the Hamiltonian eigenvalues on the full shape Y with the eigenvalues of the Dirichlet Laplacian on the partial shape X [57].

3.4.4 Part regularization

We rely upon the eigenvalue alignment to implement the partial shape localization via optimization over the potential function region on the full shape. Along this line of thought, we utilize the eigenvalues of Eq. (22) and boil down the eigenvalue alignment to the following problem:

$$\mathop {\min }\limits_{{{\mathbf{V}} > 0}} \left\| {\varvec{\mu}{\mathbf{ (S}}_{Y}^{{ - 1}} {\mathbf{M}}_{Y} {\text{ + diag(}}{\mathbf{V}}{)}{\mathbf{)}} - {{{\lambda}}}} \right\|_{\omega }^{2} $$

(28)

where we seek the minimum between the Hamiltonian eigenvalues on the full shape and the Laplacian eigenvalues on the partial shape to localize the partial shape to the correct region. We use the $\omega$-norm $\left\| {{{\varvec{\upmu}}} - {{\varvec{\uplambda}}}} \right\|_{\omega }^{2} { = }\sum\nolimits_{i = 1}^{k} {\frac{1}{{\lambda_{i}^{2} }}} (\mu_{i} - \lambda_{i} )^{2}$ (equal to the weighted L2 norm) to make a balanced penalty for all frequencies, promoting the robustness property. Using the $\omega$-norm in Eq. (28) could lead to an accurate shape localization: An optimum can be reached by correctly aligning eigenvalues.

Equation (28) gives us a straightforward way to model part $X^{\prime} \subseteq Y$ using the potential vector V, which confines the sought region $X^{\prime}$ on Y corresponding to the approximately isometric partial shape X. That is, the eigenfunctions with associated eigenvalue $\mu_{i} < \tau$ are isolated in the area where V = 0. Our goal is to introduce the eigenvalue alignment as a partial shape localization technology to regularize the partial matching in the optimization problem (15). To make Eq. (28) act as a part regularization term R_part, we express this equation as

$$ R_{{{\text{part}}}} (\sigma (z)) = \mathop {\min }\limits_{z} \left\| {{{\mu (\mathbf{S}}}_{Y}^{{ - 1}} {\mathbf{M}}_{Y} {\text{ + diag}}(\sigma (z)){\mathbf{)}} - {{\varvec{\uplambda}}}} \right\|_{\omega }^{2} , $$

(29)

where $\sigma (z){ = }\frac{\tau }{2}(\tanh (z) + 1)$ is a saturation function used to restrict the value of ${\mathbf{V}} = \sigma (z)$ to the range (0, $\tau$), s.t. $\mu_{i} < \tau$.

In Fig. 3, we illustrate the localization behavior of the new part regularization term under different inputs. Here, we use the intersection over union (IoU) between the located region and the ground truth under each full shape to reflect the localization accuracy. As we show in this experiment, it is sufficient to use fully spectral eigenvalue alignment technology to get a sound localization to the corresponding latent region.

Fig. 3

Results of eigenvalue alignment technology on four different classes from the SHREC’16 Partial Correspondence benchmark. We show the partial shape and its sought localization on the full shape (in maroon). Below each result, we report the intersection over union (IoU) scores w.r.t. the ground-truth regions

4 Multi-part shape matching

4.1 Optimization problem

As stated before, throughout the paper, we consider the setting where we are given a full model shape Y and a collection of non-overlapping partial shapes $\{ X_{i} \}_{i = 1}^{m}$ that correspond to the non-rigid deformed parts $\{ X_{i} ^{\prime} \subseteq Y\}_{i = 1}^{m}$. Our goal is to match the parts to the full shape utilizing non-rigid mappings $\{ T_{i} :X_{i} \to X_{i} ^{\prime}\}_{i = 1}^{m}$ such that the matching regions $\{ X_{i} ^{\prime} \subseteq Y\}_{i = 1}^{m}$ are non-overlapping and might not cover Y entirely. As we demonstrate in Fig. 4, $X_{0} ^{\prime}$ can be seen as a “null segment,” i.e., a missing part.

Fig. 4

Multi-part matching with missing parts. The parts {X_i} are matched to the reference shape Y

We propose a practical method of the so-called simultaneous partial functional correspondence (SPFC) based on the previous analysis. Combining the data term (15) and the part regularization term (29), we formulate the above problem of simultaneous multi-part matching as

$$ \begin{gathered} \mathop {\arg \min }\limits_{{{\mathbf{Q}}_{i} ,z_{i} }} \sum\limits_{i = 1}^{m} \alpha \left\| {{\mathbf{W}}_{r \times k} {\mathbf{A}}_{i} - {\mathbf{Q}}_{i}^{{\text{T}}} {\mathbf{B}}_{i} (\eta (z_{i} ))} \right\|_{2,1} + \sum\limits_{i = 1}^{m} {{\text{off(}}{\mathbf{Q}}_{i}^{{\text{T}}} {{\varvec{\Lambda}}}_{Y} {\mathbf{Q}}_{i} {)}} \hfill\\ + \gamma_{1} \sum\limits_{i = 1}^{m} {R_{{{\text{part}}}} (\sigma (z_{i} ))} { + }\gamma_{2} \sum\limits_{i = 0}^{m} {R_{{\text{Mumford - Shah}}} \left( {\eta (z_{i} )} \right)} \hfill \\ {\text{s.t.}}\left\{ {\begin{array}{*{20}l} {\sum\limits_{i = 0}^{m} {\eta (z_{i} )} = 1} \hfill \\ {{\text{area(}}X_{i} {)} = {\mathbf{s}}_{Y}^{{\text{T}}} \eta (z_{i} )} \hfill \\ \end{array} } \right., \hfill \\ \end{gathered} $$

(30)

where $\eta (z) = \frac{1}{2}(\tanh (z) + 1)$ saturates the part indicator function with values in the range (0, 1) and $\sigma (z){ = }\tau \eta (z)$, $\gamma_{1}$ and $\gamma_{2}$ are weights, and s_Y denotes the vectors of discrete area elements on Y. $R_{{\text{Mumford - Shah}}} (\eta (z)){ = }\int_{Y} {\delta (\eta (z) - 0.5)} \left\| {\nabla_{Y} \eta (z)} \right\|dx$ is an intrinsic version of the Mumford–Shah functional [61], measuring the length of the boundary of a part by a saturation function. We find the located region on the model closest to the partial shape and with the shortest boundary. Since the null segment $X_{0} ^{\prime}$ does not correspond to any of the X_i’s, it has no data term and does have a Mumford–Shah functional term.

Note that the first aggregate $\sum\nolimits_{i = 1}^{m} {\alpha \left\| {{\mathbf{W}}_{r \times k} {\mathbf{A}}_{i} - {\mathbf{Q}}_{i}^{{\text{T}}} {\mathbf{B}}_{i} (\eta (z_{i} ))} \right\|_{2,1} }$ constitutes the data term measuring the proximity of the parts ${\mathbf{W}}_{r \times k} {\mathbf{A}}_{i}$ to the corresponding transformed segments ${\mathbf{Q}}_{i}^{{\text{T}}} {\mathbf{B}}_{i} (\eta (z_{i} ))$ on the reference shape, while the second aggregate $\sum\nolimits_{i = 1}^{m} {{\text{off(}}{\mathbf{Q}}_{i}^{{\text{T}}} {{\varvec{\Lambda}}}_{N} {\mathbf{Q}}_{i} {)}}$ and the third aggregate $\sum\nolimits_{i = 0}^{m} {R_{{{\text{part}}}} (\sigma (z_{i} ))}$ are the regularization terms measuring the sought localization of each part. We use this efficient optimization scheme (30) to perform the matching of multiple shapes simultaneously.

4.1.1 Alternating scheme

The problem (30) is solved by employing the manifold alternating direction method of multipliers (MADMM) algorithm [62] in Algorithm 1. Since the MADMM algorithm does not support constraints inherently, the constraints in the problem (30) were replaced by large quadratic penalties.

As noted above, we use the transformation coefficients matrix Q to calculate the new basis $\widehat{\psi }_{i}$, from which it is thus natural to obtain functional map C by deducing B.

4.2 Post-processing

The functional map pipeline outlined above demonstrates that reconstructing point-wise correspondences is key to the functional correspondence framework. To convert the functional map C to a higher-quality point-wise dense correspondence, we formulate a novel map refinement approach, which can be seen as a combination of ZoomOut [14] and RPMR [13] algorithm, called Regularized ZoomOut.

For simplicity, we assume that the bases $\{ \phi_{i} \}_{i = 1}^{k}$ and $\{ \widehat{\psi }_{i} \}_{i = 1}^{k}$ are the first k eigenfunctions of the Laplace–Beltrami operators of the partial shape X and the full shape Y under homogeneous Neumann boundary conditions. ${{\varvec{\Phi}}}$ and $\widehat{{{\varvec{\Psi}}}}$ are matrices containing $\{ \phi_{i} \}_{i = 1}^{k}$ and $\{ \widehat{\psi }_{i} \}_{i = 1}^{k}$ as their columns, of sizes n₁ × k and n₂ × k, respectively.

In this section, we take account of the point-wise map $T:X \to Y$ by means of a permutation matrix

$${\varvec{\Pi}} {\mathbf{(}}i,j{\mathbf{)}} = \left\{ {\begin{array}{*{20}c} 1 & \; {T(i) = j} \\ 0 & \; {T(i) \ne j} \\ \end{array} } \right.,$$

(31)

where i and j are vertex indices on shape X and Y, respectively. Note that the n₁ × n₁ matrix ${{\varvec{\Pi}}}$ encodes the map T. By analogy to the simple representation of matrix ${\mathbf{C}} = (\left\langle {T_{F} \left( {\phi_{i} } \right),\widehat{\psi }_{j} } \right\rangle )$ on orthonormal bases, the expression for C built upon T can be compactly written as

$$ {\mathbf{C}} = (\widehat{{{{\Psi}}}})^{{\text{T}}} {\varvec{\Pi \Phi }}.$$

(32)

Along the same line of thought, we get the map T from the following problem:

$$ T(i) = \mathop {\arg \min }\limits_{i} \left\| {{\mathbf{C}}({{\varvec{\Phi}}}(i))^{{\text{T}}} - (\widehat{{{\varvec{\Psi}}}}(j))^{{\text{T}}} } \right\|^{2} , $$

(33)

with ${{\varvec{\Phi}}}(i)$ and $\widehat{{{\varvec{\Psi}}}}(j)$ being the ith row of the matrix ${{\varvec{\Phi}}}$ and jth row of the matrix $\widehat{{{\varvec{\Psi}}}}$, respectively.

Traditionally, we solve the problem (33) by the approximate nearest neighbor (ANN) algorithm or the k-nearest neighbor (k-NN) algorithm. Rodolà et al. [13, 63] considered the point-wise map recovery problem as a point cloud alignment problem and introduced a regularized probabilistic model to solve the problem (33). Combining the RPMR [13] algorithm with the objective function, we formulate Eq. (33) as

$$\begin{aligned} & \mathop {\arg \min }\limits_{{{{{\Pi}}} \in \{ 0,1\}^{{n_{1} \times n_{1} }} }} D_{{{\text{KL}}}} ({\mathbf{C}\varvec{\Phi}}^{{\text{T}}} ,\widehat{{{{\Psi}}}}^{{\text{T}}} {{{\Pi}}})\\ &\quad\quad + \rho \left\| {\Gamma ({\mathbf{C}\varvec{\Phi }}^{{\text{T}}} - \widehat{{{{\Psi}}}}^{{\text{T}}} {{{\Pi}}})} \right\|^{2} \\ &\quad\quad\,\,{\text{s}}.{\text{t}}.\,\,{{{\Pi}}}^{\rm T} {\mathbf{1}} = {\mathbf{1}}.\,\,\left( {{\text{a}}\,{\text{vector}}\,{\text{of}}\,n_{{1}} \,{\text{ones}}} \right),\end{aligned} $$

(34)

where D_KL denotes the Kullback–Leibler divergence between a continuous GMM distribution (represented by ${\mathbf{C }\varvec{\Phi}}^{{\text{T}}}$) and a mixture of Dirac distributions (represented by $\widehat{{{\varvec{\Psi}}}}^{{\text{T}}}$) and $\rho > 0$ controls the regularity of the assignment. Here, $\left\| \Gamma \right\|^{2}$ is the Tikhonov regularizer, where $\Gamma$ denotes a low-pass operator promoting smooth velocity vectors. Such regularizer is supported by the motion coherence theory (MCT) [64], which states that points close to one another tend to move coherently, and the displacement (i.e., velocity) function between the point sets should be smooth [65]. We employ the expectation maximization (EM) algorithm to solve the problem (34). This publicly available code comes from the coherent point drift (CPD) [65] method.

The key novelty of the ZoomOut method comes from its capability to iterate the refinement procedure to obtain progressively larger functional maps $\{ {\mathbf{C}}_{i} \}_{i \ge 0}$ until i reaches the threshold r. This way, as the functional map grows, the point-wise map T becomes both more smooth and accurate.

Our approach is based on the ZoomOut, in which we utilize the RPMR algorithm to recover and refine the point-wise map. To summarize, it includes the following steps:

• (1) Initialize i = k₀, j = 0 and C₀ = (diag(1,…,1))_k0×k0.

• (2) Compute ${{\varvec{\Pi}}}_{j}$ by alternately using the RPMR algorithm [i.e., utilizing the EM algorithm to solve the problem (34)] or k-NN algorithm. We observed that it typically works better if we used the two algorithms interchangeably in the code loop.

• (3) Compute ${\mathbf{C}}_{j} = (\widehat{{{\varvec{\Psi}}}}^{i} )^{{\text{T}}} {{\varvec{\Pi}}}_{j} {{\varvec{\Phi}}}^{i}$, where ${{\varvec{\Phi}}}^{i}$ and $\widehat{{{\varvec{\Psi}}}}^{i}$ denote the submatrix of ${{\varvec{\Phi}}}$ and $\widehat{{{\varvec{\Psi}}}}$ consisting of the first i columns, respectively. Set i = i + 1, j = j + 1.

• (4) Repeat the loop body, until i > r.

Figure 5 shows the accuracy compared to the ICP refinement method from the SHREC’16 Partial Correspondence benchmark. We applied our technique and ICP to refine maps between the partial and full shapes and encoded corresponding points in a similar color. Our approach builds upon the feature “upsampling” in the Regularized ZoomOut framework that introduces additional frequencies or equivalently directly adds samples in the spectral domain at every iteration. Initializing the functional map to size 10 × 10 (second row), we show the point-wise maps visualized via color transfer throughout the upsampling iterations of our approach in the figure. Note that as the correspondence matrix grows, the resulting matrix is more diagonal, and the map becomes more smooth and more semantically accurate. We also show the result of ICP in 20 outer iterations for a map of size 31 × 31 (bottom row), which nevertheless leads to a low-quality dense point-wise correspondence result. Therefore, we encourage the reader to compare the work of ICP to ours, which provides visual proof that our approach upsampling the map to the same size leads to a significant improvement.

Fig. 5

Comparison of map quality of our method with ICP in 20 outer iterations. Our approach leads to better results, as can be seen, e.g., on the belly and leg

5 Implementation

5.1 Preprocessing

The robustness of the chosen descriptor fields in the shapes directly affects correspondence quality. Compared to other classical local descriptors, such as HKS and WKS, the SHOT [66] descriptor capturing the local normal vector orientations is highly descriptive, computationally efficient, and robust to noise. In all experiments below, we used 352-dimensional SHOT descriptors with ten bins and a SHOT radius roughly chosen to 9% of the maximal pairwise geodesic distance, which means 352 descriptor functions on each shape.

5.2 Eigenvalue number

Roughly speaking, we can estimate the slope of the partial functional map C as r/k, where r and k denote the eigenvalue numbers of the partial shape X and the full shape Y, respectively. In our experiments, we initialize k = 90 and estimate the value of r, directly related to the rank of C, from

$$ r = \max \left\{ {i|\lambda_{i} < \mathop {\max }\limits_{j = 1}^{k} \mu_{j} } \right\}, $$

(35)

where we write $\lambda_{i}$ and $\mu_{j}$ to denote the eigenvalues of the partial shape and the full shape, respectively.

5.3 Step potential

In Sect. 3.4, the potential $\beta$ confines all eigenfunctions with associated eigenvalues $\mu_{i} < \tau$ within the region where $\sigma (z){ = }0$. If $\mu_{i} > \tau$, it means there is a probability for the particle to penetrate the potential region where $\sigma (z) \; { = } \; \tau$. In our experiments, we set the step of magnitude $\tau { = 8}\mu_{k}$, which can get excellent quality of localization.

5.4 Error measure

We use the quantitative criterion introduced in [67] to evaluate point-wise maps’ quality. Given the ground-truth match $(x,y^{*} ) \in X \times Y$, the error of the calculated match $(x,y) \in X \times Y$ is computed by the geodesic distance between y and y* and normalized by the area of Y:

$$ e(x) = \frac{{d_{Y} (y,y^{*} )}}{{\sqrt {{\text{area(}}Y{)}} }}, $$

(36)

where d_Y is the geodesic distance on Y and area(Y) is the area of the shape Y.

6 Experimental results

We performed a wide range of real and synthetic data experiments to demonstrate our method’s efficacy and carried out qualitative and quantitative comparisons to the state-of-the-art algorithms on several recent benchmarks.

6.1 Datasets

We selected four datasets that have a large variety of objects with ground-truth correspondences.

The SHREC’16 Partial Correspondence benchmark [68] uses shapes from the TOSCA [69] dataset, consisting of nearly isometrically deformed shapes from eight classes, with different removed parts. The benchmark’s two types of partiality are cuts (consists of shapes undergoing a single cut) and holes (contains irregular holes and multiple cuts). In each class, the point-wise ground-truth correspondence between the partial and full shape is given.

The SHREC’16 Topology benchmark [70] includes modified shapes from the KIDS set [71], containing 25 shapes of the same class undergoing near-isometric deformations in addition to massive topological shortcuts.

The SCAPE dataset [72] contains 72 clean shapes of scanned humans in different poses.

The FAUST dataset [4] contains 100 human scans belonging to 10 different individuals, partitioned into two classes: 60 requiring intra-subject matching and 40 requiring inter-subject matching.

6.2 Qualitative results

In Fig. 6, we show examples of the correct localization of each part with respect to the full shape. The input data are several non-overlapping pieces taken from the full shape’s non-rigid deformations in the SHREC’16 Partial Correspondence benchmark, forming a covering set. We compare the state-of-the-art multi-part shape matching algorithm NRP [42] and partial shape matching algorithm FSPM [12]. Since FSPM is not a partial matching method of shape collections, for fair comparisons, we perform it to each part separately, resulting in corresponding independent partial matching problems. Note that for better comparison results, we report the area ratio IoU between the detected region and the ground truth below each partial shape and plot the identified areas corresponding to parts with different colors in the full shapes. Results show that our method has a more superior partial localization performance and is more precise than the one obtained with other approaches. Although there is an explicit model of parts in the architecture, the NRP does not perform well in the partial localization. Unlike the NRP, FSPM circumvents the need to compute the unknown parts explicitly but lacks partially localized behavior; thus, localization accuracy is low. As noted in our discussion, our localization feature is based on the simultaneous partial functional map framework and the eigenvalue equivalence technique, penalizing the sought localization that lies outside of the correct corresponding region, which intuitively means that no spurious localization should be created.

Fig. 6

Comparison between NRP, FSPM, and our method on the SHREC’16 Partial Correspondence benchmark in the multiple part setting. For each example, we show the partial shapes, the NRP solution, the FSPM solution, and our solution. Corresponding regions between partial and full shapes are indicated with the same color. The numerical score below each partial shape denotes the IoU w.r.t. the ground-truth regions from different methods

In Fig. 7, we display examples of the dense correspondence that NRP, FSPM, FSEAUR[39], and our algorithm generate, where dense maps between shapes are color-coded such that matching points have the same color. Note that, for FSPM, since each part is matched independently, different parts’ correspondence results may cover the wrong areas on the boundary leading to overlapping (e.g., the woman’s belly and the horse’s four legs). FSEAUR has the same problem (e.g., the woman’s right arm and the horse’s right two legs). Our method leverages the simultaneous functional map algorithm to resolve this problem so that all parts are matched jointly to a whole shape. We exploit it as a regularizing effect on the correspondence to remove this ambiguity. In the NRP solution, the horse’s hind legs are swapped, and the woman and the horse’s belly are mapped to the back. Due to symmetry ambiguity, the algorithm fails to produce a good map with consistent orientation. To disambiguate possible symmetric correspondences, we introduce the new part regularization via the eigenvalue equivalence technique for estimating functional maps by promoting the localizing accuracy in a novel way. Moreover, our framework takes Regularized ZoomOut as map refinement, making processing smaller initial functional maps easier to compute and avoiding getting trapped in symmetry ambiguity. We provide comparisons with FSEAUR, which is also based on the ZoomOut. We show that our method’s post-processing step Regularized ZoomOut leads to a significant boost in performance. Therefore, our method provides the smoothest maps and exhibits the smallest color distortion, close to the ground truth.

Fig. 7

An example of multi-part dense correspondence was obtained using different methods from the SHREC’16 Partial Correspondence benchmark. Correspondence is visualized via color transfer from the rightmost full shape

In Fig. 8, we use various datasets for the evaluation, including the SHREC’16 Topology benchmark, the FAUST, and the SCAPE datasets. Qualitatively evaluating multi-part dense correspondence on these datasets is challenging since their settings include non-rigid surface deformation, symmetric ambiguity, and the presence of topological noise. In this experiment, we fragment their model into three parts, give a reference shape, and perform these parts partially matching the reference. We visualize the solution by color coding on the reference and transfer it to the parts using the point-wise maps.

Fig. 8

Examples of multi-part dense correspondence obtained with NRP, FSPM, and our method from various datasets. Notice that compared to other competing approaches, our method correctly identifies non-overlapping subregions on the reference matching all the parts, providing the most accurate and smooth map

In the SHREC’16 Topology benchmark, the shapes undergo topological changes due to the coalescence of spatially close surface regions, e.g., the hands on the child’s face in the figure. As shown in Fig. 8, NRP demonstrates poor performance in this challenging setting. The child’s right hand is the same color as his face, and his left hand is mapped to the right hand. Moreover, FSPM is less accurate and more unstable than our method. In contrast with FSEAUR, we can obtain high-quality functional maps across each shape collection.

The shapes of FAUST and SCAPE contain artifacts such as scanning noise and symmetric ambiguity. When compared to these state-of-the-art methods, an essential advantage of our method is the map refinement process. It makes the resulting maps of our approach typically less noisy and more globally consistent, even though it is not designed to optimize this problem, which also helps obtain a more accurate partial functional map.

In Fig. 9, we visualize the match results by transferring a texture from reference to multiple parts via the recovered dense map, which provides good visualization for the resulting maps’ local distortion. NRP has a massive distortion on all parts of the woman and the horse and gives a flipped left to right map in the woman’s head. The map produced by FSPM has a heavily overall error when compared to the ground truth. Note that the continuity and quality of the maps obtained using our method are significantly better than other techniques. These qualitative results illustrate that our method produces smooth, guaranteed bijective solutions. We also observe that our method is the only algorithm that can reliably recover multiple high-quality non-rigid maps in the collection. The results of FSEAUR recover fewer high-quality maps. For example, the correspondences obtained by FSEAUR in the woman’s buttocks and the horse’s legs show noticeable artifacts.

Fig. 9

Comparisons of multi-part matching results are shown by texture transfer

6.3 Quantitative results

We perform an extensive quantitative evaluation of the proposed method on the SHREC’16 Partial Correspondence benchmark, the SHREC’16 Topology benchmark, the FAUST, and the SCAPE datasets. We compare with the state-of-the-art multi-part matching method NRP and partial correspondence approaches, including PFM, FSPM, and FSEAUR.

Cumulative curves are plotted in Fig. 10, reading the fraction (y-axis) of computed correspondences that fall within certain (normalized) geodesic distance to the ground-truth ones (x-axis). Note that when compared to the baseline method NRP, our approach achieves 18.9% improvement on the SHREC’16 Partial Correspondence benchmark, 8.8% on the SHREC’16 Topology benchmark, 4.1% on the FAUST, and 35.7% on the SCAPE on average. On the SHREC’16 Partial Correspondence and SHREC’16 Topology benchmark, our method (black curve) detects over 90% correct correspondences for a small threshold of 0.05. It converges to finding almost all correct correspondences within geodesic error 0.075. Moreover, even for the FAUST and SCAPE, our solution obtains a higher percentage of correct correspondences within a small geodesic diameter and saturates earlier than other methods.

Fig. 10

Correspondence quality of different methods on the SHREC’16 Partial Correspondence benchmark, the SHREC’16 Topology benchmark, the FAUST dataset, and the SCAPE dataset

Although shapes in the SHREC’16 Topology benchmark are still synthetic, self-occlusion poses are merged in the geometry, making it more challenging. We can see that even though the accuracy curve on this dataset does not significantly improve our method over FSPM and FSEAUR, our results are more accurate, smoother, and consistent. By nature of the acquisition process, the shapes on the FAUST and SCAPE are affected by several artifacts, resulting in a challenging testbed for shape matching. The low accuracy of FSEAUR in SCAPE is motivated by its refinement approach. Our approach significantly outperforms other methods consistently across these two datasets, whose Regularized ZoomOut refines the FSEAUR solutions even further.

6.4 Ablation study

In this section, we present the extensive ablation study of all the vital components of our algorithm, including FSEA and Regularized ZoomOut. We run our algorithm in four different settings on 30 random pairs from the SHREC’16 Partial Correspondence benchmark, where one part of the method changes each time while the rest remains identical. These settings contain our method, ours without FSEA, ours without Regularized ZoomOut (use the ICP algorithm to refine map), and ours without any two components (use the ICP algorithm to refine map). We evaluate the results via visualization of color and texture transfer in Fig. 11. To get a better view, we enlarge the texture details of the corresponding regions in the shapes. The central insight is that our method’s different components have an intricate interplay, and the accuracy drops significantly if any part is removed. Our FSEA algorithm can find the correct region corresponding to the partial shape in most cases, even in the presence of large amounts of partiality of the inputs. The figure’s fourth and sixth columns show that Regularized ZoomOut makes the map smoother and more accurate semantically.

Fig. 11

Ablation study example. Note that we consider four different settings: ours without FSEA and Regularized ZoomOut, ours without Regularized ZoomOut, ours without FSEA, and ours. We then visualize the maps via color (first row) and texture transfer (second row)

We assess the effect of the different components of our method shown in Fig. 12. We turn off certain parts of the method and report the correspondence quality in terms of the average geodesic error in % of the diameter obtained by different settings at increasing partiality levels. It demonstrates the importance of all individual blocks and ascertains that all these components are needed to achieve optimal performance with our solution. In particular, the FSEA strategy is vital. Without it, our average geodesic error is over 0.07 at different partiality levels. Remarkably, even when the Regularized ZoomOut strategy is replaced with ICP, the average geodesic error is higher than ours.

Fig. 12

Comparative results for the different ablations of our method

6.5 Runtime

We tested our algorithm, NRP, FSPM, and PFM on a workstation with Intel Core i9 3.6 GHz processor and 64 GB memory. We conducted the experiments on 30 random pairs from the SHREC’16 Partial Correspondence benchmark and showed in Fig. 13 a runtime comparison on meshes of sizes 1−10 k vertices. Similar to NRP and PFM, our method used the Mumford–Shah functional term in the optimization problem. The most computationally expensive part of them is the cumbersome optimization over the spectral and spatial domains. Note that our method is significantly faster than PFM and the currently best multi-part matching method NRP. The main reason is that our method’s FSEA can quickly find the correct localization of the partial shape and allows the optimization to converge fast. At the same time, FSPM performs all the calculations in the spectral domain. Therefore, FSPM is the significant fastest over all methods.

Fig. 13

Runtime of matching shapes with the varying number of vertices using our algorithm, compared to NRP, FSPM, and PFM

Our technique adopts the Regularized ZoomOut strategy in the post-processing step, and the computational cost is higher than FSPM’s refinement method ICP. In the typical case where the number of vertices n = 10 k, the CPU implementation of our strategy takes on average 30 s to converge, while ICP only 5 s. Our method’s runtime complexity grows linearly with shape size.

7 Discussion and conclusions

This paper formulated a novel approach for computing partial correspondences between non-rigid multiple parts and full shape. In this setting, the parts are jointly matched to the full shape. We firstly introduced a new part regularization term based on Hamiltonian spectrum alignment for the simultaneous partial functional map framework, promoting the accuracy of region localization directly in the spectral domains. Unlike existing work that utilizes complex regularizers, our technique adopts a simple localization technique calculating entirely in the spectral domain while yielding qualitatively better results at a fraction of the time cost. We then extended the ZoomOut pipeline using the RPMR algorithm, which can be seen as a non-rigid alignment between the two shapes’ spectral embeddings, leading to a significant improvement in recovering the point-wise correspondence. We demonstrated our method’s advantages by comparing it to several current state-of-the-art methods on well-known test datasets. Contrarily to these approaches, our method can tackle topological noise, strong partiality, missing pieces, and symmetric ambiguity, making it amenable for application in the scenario that frequently occurs when dealing with real data.

Our method still comes with multiple limitations. First, our FSEA strategy needs a larger k of the first few eigenvalues to discriminate parts that only differ at medium and high frequencies. To solve this problem, we have to increase the value of k and bear a higher calculation cost. Second, the post-processing step depends on some parameters that have to be tuned for some shapes. Specifically, we require to identify C₀ in the initialization and the step size of upsampling. Finally, due to the RPMR as a search algorithm, the Regularized ZoomOut obtains an accurate correspondence at a high computational cost.

In the future, we would like to investigate a partial correspondence approach that is suitable for non-isometric pairwise shapes, even multiple shapes. Even though this problem has received surprisingly little interest, we believe that it is a promising direction that makes it possible to accommodate the practical application. Moreover, it would be rewarding to research how deep learning approaches can solve designing a partial functional map.