Incremental functional maps for accurate and smooth shape correspondence

Abstract

Incorporating multiscale spectral manifold wavelets preservation into the functional map framework for shape correspondence achieves great results in terms of both efficiency and effectiveness. However, fixing the dimension of the spectral embedding strategy in iterations of optimization is troublesome, such as missing high-frequency information when the dimension is small or getting trapped in local minima at a high dimension. In this paper, we present a simple and efficient method for refining correspondences from low frequency to high frequency with a theoretical guarantee. We formulate a strong constraint where the multiscale spectral manifold wavelets should be preserved at each scale correspondingly in the case of the arbitrary dimension of spectral embeddings. To solve the formula, we deduce two relaxed optimization subproblems and propose an incremental alternating iterative algorithm between the spatial and spectral domains via spectral up-sampling and filtering, computing the functional maps and pointwise maps in turn. Our results demonstrate that our method is robust to noisy initialization and scalable with regard to shape resolutions. The deformable shape correspondence benchmark experiments show our method produces more accurate and smoother results than state of the arts.

1 Introduction

Establishing geometrically meaningful correspondences or maps between deformable shapes is a long-standing problem in computer graphics, computer vision, and related areas, which is a fundamental operation across innumerable applications including shape interpolation and retrieval, texture transfer, symmetry detection, and statistical shape modeling, to mention a few [34].

In recent decades, an enormous amount of literature has been discussed on how to find the correspondences across shapes efficiently and accurately. Among these works, the functional map framework [27] is one of the most influential tools. In addition, it has been extended to quite a lot of follow-up works both in axiomatic [10, 15, 36, 44] and in learning-based [6, 7] setting.

Although the functional map framework is flexible, these works usually require high-quality descriptors or sophisticated regularizers. The computational efficiency is always not compatible well with the correspondence accuracy. [13] recently proposed a novel iterative method via multiscale spectral manifold wavelet preservation (MWP) in the functional map framework, which alleviated the problem to a certain extent. However, the results are heavily reliant upon the sizes of spectral embedding of the shapes in the calculation process. On the one hand, the use of higher dimensionality of spectral embedding, encoding smaller-scale details, is not merely computationally expensive, but also unstable. On the other hand, a lower-dimensional one, featuring larger-scale information, i.e., the overall pose of the shape, loses medium- and high-frequency features, and its adoption often leads to some significant artifacts in practical applications. The authors used the spectral embedding of fixed dimension (the dimension is 100) during iterations in MWP [13], which may produce undesirable results, especially starting with a small functional map. As shown in Fig. 1, each dotted line represents the result obtained by MWP [13] with a designated dimension of the spectral embedding during iteration, and MWP has limited optimization capability.

In this paper, rather than using spectral embedding with a fixed scale, we adjust the dimensionality reflected incisively and vividly in the optimization problem and solution. In that case, all information about the shape, including low, medium, and high frequency, is encoded by the multiscale spectral manifold wavelets, which helps comprehensively analyze the shape with the use of global and local features. For the purpose of addressing the defined optimization problem simply and efficiently, we adopt the alternating iterative strategy between the spatial and frequency domain and gradually increase the dimension of the spectral embedding in each iteration. Moreover, when we employ proper filters, the calculation of the large linear equations is avoided and two relaxed problems are deduced. Furthermore, we demonstrate that our algorithm achieves state-of-the-art results over various shape correspondence tasks, including complete shape matching, the matching between a shape existing topological noise and a full shape. What’s more, our method is robust to the noisy input since we carry out filtering to the coarse functional map via a low-pass and a set of band-pass filters. The step greatly improves the quality of results in the aspect of both accuracy and smoothness. Another superior property exhibited by our technique is scalability. In other words, our method is not sensitive to the resolution of mesh and can efficiently compute the correspondence between a pair of shapes with different resolutions.

Contributions. We summarize the main contributions as follows:

• 1) We formulate a constraint that preserves intrinsic multiscale spectral manifold wavelets with changed dimensionality of spectral embedding at each scale into the functional map framework.

• 2) To solve the optimization problem more efficiently, we deduce two relaxed subproblems from the original problem, making full use of the special properties of the Parseval wavelet frames.

• 3) Using the simple but useful spectral up-sampling technique, we propose an approach that updates the computation of functional maps with increasing size and pointwise maps alternatively. We filter the coarse functional maps via a low-pass and a set of band-pass filters in the spectral domain, which facilitates producing more accurate and smoother results.

Fig. 1

Comparisons of map quality between MWP and ours on a pair of shapes belonging to FAUST dataset, where starting from a $10 \times 10$ functional map estimated by [27] with WKS descriptors and 4 landmarks. Here MWP uses the unchanged spectral embedding with different sizes, respectively. Our method increases the spectral embedding from 10 to 110 with $k_{step}=5$. All CQC curves are shown on the left plot and the right one gives the average error of each situation during the iterative process

2 Related work

Finding a correspondence between two shapes is a well-studied project in the field of digital geometry processing over the past several decades. We refer the interested readers to the recent survey [34] for a more in-depth overview of shape correspondence problems. In the following, we primarily give a review of methods that are most closely related to ours.

Point-based spectral methods. Lots of methods for shape correspondence directly optimized the pointwise matching. To eliminate the influence of extrinsic information like the XYZ-coordinates of deformed shapes, a common strategy is to obtain the features that are isometrically invariant and robust to small perturbations. Therefore, there appeared plenty of methods based on spectral techniques. The early spectral methods optimized point-to-point maps between spectral embeddings that were based on either adjacency or Laplacian matrices of triangle meshes and graphs [14, 39]. These methods often lead to complex combinatorial problems. The authors later suggested solving the Procrustes matching problem by using a convex semidefinite programming relaxation in [21], but the method is limited to around one hundred points and remains high time complexity. Another kind of matching technique was to design the handcrafted spectral pointwise descriptors [2, 38] and learning-based one [20, 42] firstly. Then, the matches were obtained by a simple nearest neighbor search algorithm in the embedding space of descriptors, or by computing a linear assignment problem (LAP) if injectivity was required. But LAP lacks consideration of the geometric relationship between points, so the correspondences are not smooth enough. Along with the study of spectral pairwise descriptors, such as kernel functions [37, 40], it usually led to an NP-hard quadratic assignment problem subsequently. To address the problem, although recently various relaxation approaches [24] or sparsity control strategy [43] were proposed, they often remained computationally expensive.

Functional map-based methods. Our method is based on the functional map framework, which was initially introduced by Ovsjanikov et al. [27]. This work abandoned computing pointwise correspondences directly, instead of modeling the correspondence as a liner operator (named functional map) between spaces of real-valued functions across two shapes. Compared with the point-based method, functional map representation is more flexible and allows to incorporate additional constraints such as the preservation of geometric quantities (descriptors, pointwise landmarks, or region correspondences) easily. Lately, the vast majority of follow-up works tried to improve the framework including optimization for the harmonicity and reversibility [9], informative descriptor preservation via commutativity [26], product preservation[25], discrete optimization [30], among many others. (We refer to the reference [28] for an overview.) However, there still exist several drawbacks in correspondence quality and computing efficiency. Firstly, it is not a common task to obtain a collection of informative, robust, and linearly independent descriptor functions. Secondly, although the quality of correspondence can be enhanced by adding more forceful constraints or regularizers, the computational complexity always increases tremendously.

After computing a functional map representation, a classic method to recover the point-to-point map is to perform a nearest-neighbor search in the embedded functional space [27]. Recently, the work of [33] introduced a probabilistic model to the reconstruction of the pointwise map, and the auction algorithm [3] was used to maximize kernel density in [40, 41]. Although these works achieved accuracy improvement in some challenging cases, the efficiency was a bit slow, especially when the shape has tens of thousands of vertices, and the auction algorithm was not robust to a change in the discretization of the model. More recently, Pai et al. [29] formulated the spectral embedding alignment as a linear assignment problem and used the modified Sinkhorn algorithm based on the optimal transport theory. They demonstrated that this algorithm improves the accuracy and bijectivity of maps with acceptable time and memory complexity compared to other methods, but the partial similarity setting cannot be applied.

With the purpose of further improving accuracy, adding a post-processing step to refine the functional map is a better remedy. The simplest map refinement method is the iterative closest point (ICP) proposed by [27]. Recently, more and more powerful refinement methods have been developed, including bijective and continuous iterative closest point (BCICP) [31], ZoomOut [22], MWP [13]. Differing from these works, we formulate the constraints preserving the multiscale spectral manifold wavelets under every dimension of spectral embedding at all scales into the functional map framework, rather than a fixed dimension. On the other hand, our method processes the coarse functional map via a set of filters on the spectral domain so that we can produce smoother and more accurate correspondence than other methods. We further discuss methods that are closest related to ours in Sect. 4.3.

3 Background and notation

In this paper, a shape is modeled as a continuous, smooth, and compact 2-dimensional Riemannian manifold with or without boundaries in the continuous setting and as a triangle mesh in the discrete setting.

For a manifold $\mathcal {M}$ with area element $\text {d}\mu$ in the continuous setting, we denote square-integrable real-valued functions space by ${{\mathcal {L}}^2}\left( \mathcal {M} \right) = \left\{ f: \mathcal {M}\rightarrow \mathbb {R}, \int _{\mathcal {M}}{f^{2}{{\left( x \right) }}} \text {d}\mu < \infty \right\}$, and use the standard ${{\mathcal {L}}^{2}}\left( \mathcal {M} \right)$ inner product ${{\left\langle f, g \right\rangle }_{{{\mathcal {L}}^{2}}\left( \mathcal {M} \right) }}=\int _{\mathcal {M}}{f \left( x \right) g \left( x \right) \text {d}\mu }$ for any two functions $f, g\in {{\mathcal {L}}^{2}}\left( \mathcal {M} \right)$. The space $\left( \mathcal {M}, \mu \right)$ features the positive semi-definite Laplace–Beltrami Operator (LBO) ${{\Delta }_{\mathcal {M}}}$. Particularly, the operator admits a real eigen-decomposition ${{\Delta }_{\mathcal {M}}}{{\phi }_{i}}\left( x \right) =-{{\lambda }_{i}}{{\phi }_{i}}\left( x \right) ,i=1,2,...,$ with nonnegative and ordered eigenvalues $0={{\lambda }_{1}}\le {{\lambda }_{2}}\le \cdots$ and corresponding eigenfunctions ${{\left\{ {{\phi }_{i}} \right\} }_{i\ge 1}}$ which form an orthonormal basis on ${{\mathcal {L}}^{2}}\left( \mathcal {M} \right)$, i.e., ${{\left\langle {{\phi }_{i}},{{\phi }_{j}} \right\rangle }_{{{\mathcal {L}}^{2}}\left( \mathcal {M} \right) }}={{\delta }_{ij}}$, where ${{\delta }_{ij}}$ is the Kronecker delta. Moreover, the eigenvalues ${{\left\{ {{\lambda }_{i}} \right\} }_{i\ge 1}}$ and the associated eigenfunctions ${{\left\{ {{\phi }_{i}} \right\} }_{i\ge 1}}$ are often referred to as frequencies and Fourier bases for the space ${{\mathcal {L}}^{2}}\left( \mathcal {M} \right)$. Therefore, it allows us to expand any smooth function $f\in {{\mathcal {L}}^{2}}\left( \mathcal {M} \right)$ as a Fourier bases $f\left( x \right) =\sum \limits _{i\ge 1}{{{\left\langle f,{{\phi }_{i}} \right\rangle }_{{{\mathcal {L}}^{2}}\left( \mathcal {M} \right) }}{{\phi }_{i}}\left( x \right) }$, where the inner product ${{\left\langle f,{{\phi }_{i}} \right\rangle }_{{{\mathcal {L}}^{2}}\left( \mathcal {M} \right) }}$ is called the manifold Fourier coefficient.

For a triangle mesh $\mathcal {M}$ with m vertices, LBO can be represented as a positive semi-definite matrix ${{\mathbf {L}}_{\mathcal {M}}}$ of size $m \times m$. We denote the truncated k-dimensional spectral embedding of shape $\mathcal {M}$ as $\varvec{\Phi }_{\mathcal {M}}^{k}\in {{\mathbb {R}}^{m\times k}}$, whose every row is the first k eigenfunctions of LBO evaluated at each point, i.e., $\left\{ \left[ \phi _{1}^{\mathcal {M}}\left( x \right) ,\phi _{2}^{\mathcal {M}}\left( x \right) ,...,\phi _{k}^{\mathcal {M}}\left( x \right) \right] \left| x \in \mathcal {M} \right. \right\}$.

3.1 Functional maps

Given a point-to-point map $T:\mathcal {M}\rightarrow \mathcal {N}$ from shapes $\mathcal {M}$ to $\mathcal {N}$ (either continuous or discrete), it induces a linear functional map ${{T}_{F}}:{{\mathcal {L}}^{2}}\left( \mathcal {M} \right) \rightarrow {{\mathcal {L}}^{2}}\left( \mathcal {N} \right)$. More precisely, if given a function $f\in {{\mathcal {L}}^{2}}\left( \mathcal {M} \right)$, we can obtain a corresponding function $g\in {{\mathcal {L}}^{2}}\left( \mathcal {N} \right)$ via composition $g={{T}_{F}}\left( f \right) =f\circ {{T}^{-1}}$. For completeness, we briefly review the pipeline involved in calculating the functional map as summarized in [28]:

1) Compute k-dimensional spectral embedding on shape $\mathcal {M}$ and $\mathcal {N}$ with m and n vertices, respectively, where k satisfies $k<<m$, $k<<n$.

2) Construct a set of pairs of the descriptor functions ${{f}^{\left( p \right) }}\in {\mathcal {L}^{2}}\left( \mathcal {M} \right) ,\ {{g}^{\left( p \right) }}\in {\mathcal {L}^{2}}\left( \mathcal {N} \right)$, $p\in \left\{ 1,2,...,P \right\}$ both on the shapes $\mathcal {M}$ and $\mathcal {N}$. Their manifold Fourier coefficients are stored as columns of matrices $\mathbf {B}_{1}$ and $\mathbf {B}_{2}$, both with the size of $k\times P$.

3) Estimate the unknown functional map $\mathbf {C}$ by solving the following optimization problem:

$\mathbf {C}=\underset{\mathbf {X}}{\mathop {\arg \min }} \left\| \mathbf {XB}_1-\mathbf {B}_2 \right\| _{F}^{2}+\alpha \left\| {{\Delta }_{\mathcal {N}}}\mathbf {X}-\mathbf {X}{{\Delta }_{\mathcal {M}}} \right\| _{F}^{2}$, where $\alpha$ is a scalar weight parameter, and $\left\| \cdot \right\| _{F}$ is the Frobenius norm. The second term of the above problem is a regularizer commuting with the LBOs.

4) Recover the point-to-point map T from the functional map $\mathbf {C}$.

3.2 Spectral manifold wavelets

As an extension of classical wavelets on graphs, Hammond et al. [11] introduced the spectral graph wavelets, which retain most of the excellent nature of the classical wavelets. They not only are local both in the frequency and spatial domain but also possess a fast computing speed and multiscale nature. Based on the spectral graph wavelets, [12, 13] replaced graph Laplacian with LBO and defined the spectral manifold wavelets.

To be more details, given a kernel function $g:{{\mathbb {R}}^{+}}\rightarrow {{\mathbb {R}}^{+}}$, acting on a band-pass filter, the spectral manifold wavelet at a scale s and located at a point y is defined as follows:

$$\begin{aligned} {{\psi }_{s,y}}\left( x \right) =\sum \limits _{i\ge 1}{g\left( s{{\lambda }_{i}} \right) \phi _{i}\left( y \right) \phi _{i}^{{}}\left( x \right) }, \end{aligned}$$

(1)

where the positive real parameter s determines the support interval of the band-pass filter $g\left( \lambda \right)$, ${{\lambda }_{i}}$ and $\phi _{i}^{{}}\left( \cdot \right)$ are the $i\text {-th}$ eigenvalue and its related eigenfunction of the LBO on the associated shape, respectively. To represent stably the low-frequency content of the signal, the authors of [11] introduced another real-value function $h:{{\mathbb {R}}^{+}}\rightarrow \mathbb {R}$. In the same way, the scaling function at a point y is then given as:

$$\begin{aligned} {{\varphi }_{y}}\left( x \right) =\sum \limits _{i\ge 1}{h\left( {{\lambda }_{i}} \right) \phi _{i}\left( y \right) \phi _{i}\left( x \right) }. \end{aligned}$$

(2)

As a note, Eq. (1) tells us that every spectral manifold wavelet located at one point depends on the continuous scale parameter s. Along with the increase of scale s, the spectral manifold wavelets encode the neighbor information of one shape with a larger radius and allow the diffusion to have a farther spread on the shape. The parameter s needs to be sampled into a limited number, denoted as L, of scales in the practical applications. For the sake of convenience, we rewrite the scale function ${{\varphi }_{y}}\left( x \right)$ in Eq. (2) as ${{\psi }_{{{s}_{0}},y}}\left( x \right)$, the function $h\left( \lambda \right)$ as $g\left( {{s}_{0}}\lambda \right)$, by setting the scale parameter index of the spectral manifold wavelets $l=0$. Then, we obtain $L+1$ wavelets $\left\{ \psi _{s_l,y} \left( x \right) \right\} _{l=0}^L$ located at the point y.

As shown in the reference [13, 19], under the isometric map, the information of each frequency band is fully preserved by the multiscale spectral manifold wavelets at each scale, respectively. Combining the functional map theory, the functional map ${{T}_{F}}$ induced by the isometric map T satisfies

$$\begin{aligned} {{T}_{F}}\left( \psi _{{{s}_{l}},y}^{\mathcal {M}} \right) =\psi _{{{s}_{l}},T\left( y \right) }^{\mathcal {N}},l=0,1,\ldots ,L \end{aligned}$$

(3)

for any point $y\in \mathcal {M}$.

Moreover, the spectral manifold wavelets catch the features of a shape in different frequency bands efficiently, ranging from a smaller neighborhood around each point to a larger neighborhood along with the rise of scale.

4 Method

The main goal of our work is to strive to efficiently find an accurate, reliable correspondence or mapping between a pair of shapes with nearly isometric deformation, even in the presence of a small, noisy, or approximate functional map. Next, we describe our method in detail from three aspects: optimization problem, solution, and differences between our method and other closely related methods.

4.1 Optimization problem

In the discrete setting, given a pair of shapes $\mathcal {M}$ and $\mathcal {N}$ consisting of m and n vertices, respectively. The LBOs of the shapes $\mathcal {M}$ and $\mathcal {N}$ are denoted as matrices $\mathbf {L}_{\mathcal {M}}=\mathbf {A}_{\mathcal {M}}^{-1} \mathbf {W}_{\mathcal {M}}$ and $\mathbf {L}_{\mathcal {N}}=\mathbf {A}_{\mathcal {N}}^{-1} \mathbf {W}_{\mathcal {N}}$, discretized by the method of [23], where $\mathbf {A}_{\mathcal {M}}$ is the diagonal matrix of lumped area elements and $\mathbf {W}_{\mathcal {M}}$ is the cotangent weight matrix on the shape $\mathcal {M}$. Let $\varvec{\Lambda }_{\mathcal {M}}^{k}=\mathrm{diag} \left( \lambda _1^{\mathcal {M}},\lambda _2^{\mathcal {M}},...,\lambda _k^{\mathcal {M}}\right)$ and $\varvec{\Lambda }_{\mathcal {N}}^{k}=\mathrm{diag} \left( \lambda _1^{\mathcal {N}},\lambda _2^{\mathcal {N}},...,\lambda _k^{\mathcal {N}}\right)$ represent the k leading eigenvalues of $\mathbf {L}_{\mathcal {M}}$ and $\mathbf {L}_{\mathcal {N}}$, the corresponding eigenvectors are stored in $\varvec{\Phi }_{\mathcal {M}}^k$ and $\varvec{\Phi }_{\mathcal {N}}^k$. Since eigenfunctions of LBO are orthonormal each other with respect to the area-weighted inner product, we have $\left( \varvec{\Phi }_{\mathcal {M}}^k \right) ^\mathrm {T}\mathbf {A}_{\mathcal {M}} \varvec{\Phi }_{\mathcal {M}}^k = \mathbf {I}_k$, where $\mathbf {I}_k$ is an identity matrix of size $k\times k$, equivalently to $\left( \varvec{\Phi }_{\mathcal {M}}^k \right) ^{+}=\left( \varvec{\Phi }_{\mathcal {M}}^k \right) ^\mathrm {T}\mathbf {A}_{\mathcal {M}}$, and here $^{+}$ represents the Moore–Penrose pseudo-inverse. We encode the point-to-point map T from shape $\mathcal {M}$ to $\mathcal {N}$ as a binary matrix $\mathbf {P} \in \mathbb {R}^{m \times n}$ so that $\mathbf {P}\left( i,j \right) =1$, if ${T}\left( i \right) =j$ and 0 otherwise, where i and j are the vertex indices on the shapes $\mathcal {M}$ and $\mathcal {N}$. The functional map matrix $\mathbf {C}_k$ of size $k\times k$ can be obtained by projecting the mapping matrix $\mathbf {P}$ onto the corresponding manifold Fourier basis:

$$\begin{aligned} \mathbf {C}_k={{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}. \end{aligned}$$

(4)

Given a set of filters $g_{\mathcal {M}}(\cdot )$ and $g_{\mathcal {N}}\left( \cdot \right)$ on the shapes ${\mathcal {M}}$ and ${\mathcal {N}}$, under the first k truncated eigenfunctions, we can quickly get two wavelet matrices at scale $s_l$: $\varvec{\Psi }_{{s}_{l},k}^{\mathcal {M}}=\varvec{\Phi }_{\mathcal {M}}^{k}g_{\mathcal {M}}\left( {{s}_{l}}{{\varvec{\Lambda }}_{\mathcal {M}}^k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}\in {{\mathbb {R}}^{m\times m}}$ and $\varvec{\Psi }_{{{s}_{l}},k}^{\mathcal {N}}=\varvec{\Phi }_{\mathcal {N}}^{k}g_{\mathcal {N}}\left( {{s}_{l}}{{\varvec{\Lambda }}_{\mathcal {N}}^k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\in {{\mathbb {R}}^{n\times n}},l=0,1,...,L$, according to Eqs. (1) and (2), where the $i\text {-th}$ column corresponds to the spectral manifold wavelet at the scale ${{s}_{l}}$ of the $i\text {-th}$ point on the shape under k-dimensional spectral embedding. Then, we get that $g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}$ and $g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}$ are the manifold Fourier coefficient of two wavelet matrices, respectively.

In order to comprehensively analyze the shape using both low-frequency and high-frequency features, we desire to explore a pointwise mapping matrix $\mathbf {P}$ and its each functional map matrix ${{\mathbf {C}}_{k}}$ of size $k\times k$ preserving the wavelet constraints at each scale ${{s}_{l}}$. Thus, we define an optimization problem as follows:

$$\begin{aligned} \begin{aligned} \underset{{{\mathbf {P},{\mathbf {C}_k}}}}{\mathop {\min }}\,&\sum \limits _{k}{\sum \limits _{l=0}^{L}{\left\| {{\mathbf {C}}_{k}} g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}\!-\!g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}_{{}}^\mathrm {T} \right\| _{F}^{2}}}, \\&\mathrm {s.t.}\ \quad {{\mathbf {P}}}\mathbf {1}=\mathbf {1}. \end{aligned} \end{aligned}$$

(5)

where $\mathbf {1}$ is a vector and its all elements are 1.

4.2 Solution

To solve the optimization problem in Eq. (5), first of all, we pay attention to a single term inside the first sum. In other words, for a certain fixed k, the above problem (5) turns to be the following optimization problem:

$$\begin{aligned} \begin{aligned} \underset{{{\mathbf {P}}, {\mathbf {C}_k}}}{\varvec{\min }}\,&\sum \limits _{l=0}^{L}{\left\| {{\mathbf {C}}_{k}}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}-g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T} \right\| _{F}^{2}}, \\&\mathrm {s.t.}\ \ {{\mathbf {P}}} \mathbf {1}=\mathbf {1}. \end{aligned} \end{aligned}$$

(6)

Unfortunately, the optimization problem in Eq. (6) is still challenging. It is a non-convex problem and is difficult to optimize as the unknown functional map matrix ${{\mathbf {C}}_{k}}$ and the pointwise mapping matrix $\mathbf {P}$ influence each other. To overcome the challenges, we try to approach this problem approximately using the alternating optimization strategy.

Pointwise map. Firstly, we intend to fix the functional map matrix ${{\mathbf {C}}_{k}}$ and solve for the pointwise mapping matrix $\mathbf {P}$. In another word, we need to reconstruct the original pointwise map from the functional map representation. Here, we consider the below subproblem:

$$\begin{aligned} \begin{aligned} \underset{{{\mathbf {P}}}}{\varvec{\min }}\,&\sum \limits _{l=0}^{L}{\left\| {{\mathbf {C}}_{k}}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}-g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T} \right\| _{F}^{2}}, \\&\mathrm {s.t.}\ \ {{\mathbf {P}}} \mathbf {1}=\mathbf {1}. \end{aligned} \end{aligned}$$

(7)

But then again, finding the optimal solution satisfying the constraint condition of subproblem (7) remains a complicated task. As mentioned in [12, 18], if the filters form a tight (or Parseval) wavelets frame, they have the important property of energy conservation between the original and the transformed domains. Surprisingly, when we apply this kind of filter, subproblem (7) can be relaxed properly.

To facilitate derivation, we abandon the constraint condition in problem (7) temporarily, and the analytical solution can be obtained via solving the linear equations:

$$\begin{aligned} \begin{aligned} {{\mathbf {C}}_{k}}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}=g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right)&{{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}, \\&l=0,1,......,L. \end{aligned} \end{aligned}$$

(8)

Here, the pointwise mapping matrix $\mathbf {P}$ is unknown, while the functional map matrix ${{\mathbf {C}}_{k}}$ is the known one.

Let’s recall that for any shape $\mathcal {X}$, if the filters $g(\cdot )$ satisfy the Parseval wavelets frame, then the quantity $G\left( \lambda \right) =\sum \limits _{l=0}^{L}{{{g}^{2}}\left( {{s}_{l}}\lambda \right) }\equiv 1,\lambda \in [0,{{\lambda }_{max}}]$, where ${{\lambda }_{max}}$ is the maximum eigenvalue of LBO on the shape $\mathcal {X}$. We directly get

$$\begin{aligned} \sum \limits _{l=0}^{L}{g^2\left( {{s}_{l}}\varvec{\Lambda }^k \right) }\equiv \mathbf {I}_k, \end{aligned}$$

(9)

where $\mathbf {I}_k$ is the identity matrix of size $k \times k$, $\varvec{\Lambda }^k$ is the set of k leading eigenvalues of LBO on shape $\mathcal {X}$.

Multiplying $g\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right)$ on the left and right sides of Eq.(8), then

$$\begin{aligned} g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\mathbf {C}}_{k}}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) \left( \varvec{\Phi }_{\mathcal {M}}^{k}\right) ^{+} =g_{\mathcal {N}}^{2}&\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}, \\&l=0,1,......,L. \end{aligned}$$

Summing the above equations, we obtain

$$\begin{aligned}&\sum \limits _{l=0}^{L}{g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\mathbf {C}}_{k}}g_{\mathcal {M}}{{\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) }}\left( \varvec{\Phi }_{\mathcal {M}}^{k}\right) ^{+}}\\&\quad =\sum \limits _{l=0}^{L}{g^{2}_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}}. \end{aligned}$$

In addition, ${{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}\varvec{\Phi }_{\mathcal {M}}^{k}=\mathbf {I}_k$ holds, since eigenfunctions of LBO on each shape are orthonormal.

Let $\mathbf {C}_k^{*} = \sum \limits _{l=0}^{L}{g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\mathbf {C}}_{k}}g_{\mathcal {M}}{{\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) }}}$; then, we get ${{\mathbf {C}}_{k}^{*}}={{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}$. After adding the constraint condition, subproblem (7) turns to the relaxed optimization problem:

$$\begin{aligned} \begin{aligned} \underset{{{\mathbf {P}}}}{\varvec{\min }}\,&{\left\| {{\mathbf {C}}_{k}^{*}}-{{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{F}^{2}}, \\&\mathrm {s.t.}\ \ {{\mathbf {P}}} \mathbf {1}=\mathbf {1}. \end{aligned} \end{aligned}$$

(10)

Similarly to the reference [8, 22], we consider adding a regularizer $\mathcal {R} \left( \mathbf {P} \right) = \left\| \left( {\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+} - \mathbf {I} \right) \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{A_\mathcal {N}}^{2}$, where we use the weighted matrix norm $\left\| \mathbf {X} \right\| _{A_\mathcal {N}} = trace \left( \mathbf {X}^\mathrm {T} \mathbf {A}_\mathcal {N} \mathbf {X} \right)$, $\mathbf {A}_\mathcal {N}$ is the area matrix of shape $\mathcal {N}$ and $\mathbf {I}$ is the identity of size $n \times n$. Mathematically, this regularizer penalizes the image of $\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}$ that is orthogonal to $\varvec{\Phi }_{\mathcal {N}}^{k}$, which intuitively means that no spurious high-frequency information should be introduced. Eventually, it can be shown that subproblem (10) with the additional term $\mathcal {R} \left( \mathbf {P} \right)$ is equivalent to the optimization problem (see proof in appendix A):

$$\begin{aligned} \begin{aligned} \underset{{{\mathbf {P}}}}{\varvec{\min }}\,&{\left\| {{{ \varvec{\Phi }_{\mathcal {N}}^{k} }}{\mathbf {C}}_{k}^{*}}-\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{F}^{2}}, \\&\mathrm {s.t.}\ \ {{\mathbf {P}}} \mathbf {1}=\mathbf {1}. \end{aligned} \end{aligned}$$

(11)

To obtain a more accurate and smoother pointwise correspondence, we consider using the fast Sinkhorn filter algorithm recently introduced by [29] to solve problem (11).

Functional map. Next, we hold the matrix $\mathbf {P}$ fixed and solve the problem in Eq. (6) depending on ${{\mathbf {C}}_{k}}$, and then, we minimize

$$\begin{aligned} \underset{{{\mathbf {C}}_{k}}}{\mathop {\min }}\,\sum \limits _{l=0}^{L}{\left\| {{\mathbf {C}}_{k}}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}-g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T} \right\| _{F}^{2}}. \end{aligned}$$

(12)

Inspired by the reference [13], when we select the filters forming the Parseval wavelets frame, we also obtain a relaxation of subproblem (12). Subsequently, solving the large linear systems can be circumvented, and the relaxed solution becomes simpler and more efficient, as demonstrated in Remark 1. The proof is referred to Appendix B.

Remark 1

Supposing that spectral manifold wavelet sets $\left\{ \psi _{{{s}_{l}},{{x}_{i}}}^{\mathcal {M}} \right\} _{l=0,i=1}^{L,m}$ and $\left\{ \psi _{{{s}_{l}},{{y}_{j}}}^{\mathcal {N}} \right\} _{l=0,j=1}^{L,n}$ are generated by the special filters $g_{\mathcal {M}}\left( \cdot \right)$ and $g_{\mathcal {N}}\left( \cdot \right)$, which form a Parseval wavelet frame of the functional spaces on the shapes $\mathcal {M}$ and $\mathcal {N}$ with m and n vertices, respectively, then we can obtain the relaxed solution ${{\mathbf {C}}_{k}}$ of problem (12) as

$$\begin{aligned} {\mathbf {C}_{k}}=\sum \limits _{l=0}^{L}{g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda } _{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}} \varvec{\Phi } _{\mathcal {M}}^{k}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda } _{\mathcal {M}}^{k} \right) . \end{aligned}$$

(13)

It is noteworthy that compared with the general form of functional map matrix ${{\mathbf {C}}_{k}}={{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}$, as outlined in the reference [22] and Eq. (4), ${{\mathbf {C}}_{k}}$ obtained via Eq. (13) is equivalent to perform a low-pass and a series of band-pass filtering operations via the filters $g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }^k_{\mathcal {M}} \right)$ and $g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }^k_{\mathcal {N}} \right)$, $l=0,1,......,L$ to the general functional map matrix. Here we call the general one as the coarse functional map. More interestingly, when the point-to-point map from the shapes $\mathcal {M}$ to $\mathcal {N}$, whose Laplacian matrices have the same eigenvalues and each of them are non-repeating, is an isometry, the general and filtered functional map are equivalent as proved in Appendix C. This observation was not found in [13]. As stated in [27], for a near-isometric map, we pursuit the functional map matrix to be close to diagonal, and the filtering operations dovetail nicely with the aim.

In this paper, particularly, we adopt the Meyer tight wavelet frame provided by [18] in the practical calculation because it computes the adaptive bandwidth according to the eigenvalues of LBO on the shape and has a better ability to capture geometric information [13].

In the above analysis, we assume that the dimension of the functional map matrix is fixed. We begin with a given value ${{k}_{0}}$ and then gradually increase it during the iteration in practice. The idea is triggered by the fact that if $\mathbf {C}_k$ is already preserved by the spectral manifold wavelets, the step provides a very strong initialization for the larger sub-problem solving $\mathbf {C}_{k+1}$. Finally, our overall pipeline is summarized in Algorithm 1.

As shown in Algorithm 1, the initialization of our pipeline is a functional map ${{\mathbf {C}}_{0}}$ of size ${{k}_{0}}\times {{k}_{0}}$, which can be obtained by the existing methods like [27, 31] among others. Besides that, during the entire procedure, we start at a small functional map ${{\mathbf {C}}_{0}}$ and up-sample to a large-size and high-quality map ${{\mathbf {C}}_{{{k}_{max }}}}$.

Table 1 Quantitative comparisons of refinement for complete shape matching across different metrics on the FAUST and SCAPE datasets. Here only refinement runtime is counted

Similar to ZoomOut [22], our algorithm can also be further accelerated. In line 4 of Algorithm 1, we increase by one for the dimension k at each iteration to support the theoretical analysis. In practice, we can utilize a larger step size varying from 2 to 10 (see Fig. 4). During the alternative iteration (lines 5–7 of Algorithm 1), as a matter of fact, we can perform subsampling technology and only involves using spectral embedding of some sampling points to renew the pointwise map and the functional map until $k={{k}_{max}}$. Here the sampling points can be obtained by the Euclidean farthest point sampling strategy starting at a random seed point. In the end, we reconstruct the dense point-to-point correspondence from the final functional map by using the spectral embedding of all points only once (line 9 of Algorithm 1).

4.3 Comparisons to other related techniques

There exist many techniques that are closely related to ours, but our approach is different from theirs fundamentally.

ICP. ICP refinement strategy serves as a post-processing iterative method in the functional map frame originally proposed by [27]. The major difference between ours and ICP is that our method allows processing a small-scale functional map, which is easier to compute and more stably to express the rough correspondence than a large-size one and achieves a final larger functional map using a simple spectral up-sampling strategy. In addition, we do not require to perform the singular value decomposition and enforce that the singular value of the functional map matrix equals 1 when calculating the functional map.

Kernel Matching (KM). KM [40] solves an ocean of relaxed optimization problems with the auction algorithm, and the method achieved great results in some challenging cases. However, it is not robust to the change in the mesh resolution. What’s worse, when the number of vertices on the shape increases to a certain extent, the computational efficiency of the auction algorithm exhibits a sharp decline. Moreover, compared with the heat kernel in the kernel matching, whose filters are all low-pass, both low-pass and band-pass filters are used in spectral manifold wavelets in our method, which can capture geometric features of a shape better.

BCICP. BCICP [31] is an extension of ICP by adding a new orientation-preserving term. Additionally, for purpose of promoting the bijectivity, smoothness, and coverage of the shape correspondence, the authors use a sequence of complicated update steps. But, the expensive time cost of this technique cannot be ignored due to the computation of geodesic distance on the shape. What’s more, the same as ICP, it does not change the size of the spectral embedding during iterations.

ZoomOut. ZoomOut [22] is a recent approach for map refinement. Especially, our optimization problem defined in Eq. (5) is different from the one of ZoomOut designed in Eq. (3) in [22]. We introduce constraints of preserving the multiscale manifold wavelets with different scales of spectral embedding at all scales into the functional map framework, whereas the optimization goal of ZoomOut is to enforce orthonormality of every principal submatrix of the full functional map matrix. Our method adds a great number of filters to the functional map, enforcing the functional map matrix to be closer to diagonal, and it is of great benefit to improve the smoothness and accuracy of the correspondence across shapes. It also leads to our solution being less sensitive to the noise than ZoomOut, as shown in Fig. 3.

MWP. MWP [13] is another powerful technique for improving the quality of the point-to-point map. As the same as ours, the method combines the multiscale spectral manifold wavelets and the functional map framework. However, the scale of spectral embedding is unchanged in MWP [13]. When starting a small functional map, this method may bring some artifacts to the results. As shown in Fig. 1, the average error of our strategy quickly decreases, while MWP has a limited optimization ability and falls into a local minimum solution. In addition, although the two methods both filter for the coarse functional map, our method can produce smoother results, and the smoothness is nearly 3 times than MWP on the SCAPE dataset [1] from Table 1. Furthermore, theoretically, when fixing the functional map matrix, we deduce a relaxed problem still from the original problem (6), while the minimized energy is not the optimization problem (4) in [13]. Rather than the traditional nearest neighbor searching, we use the fast sinkhorn filter algorithm, a useful way for recovering accurate, and smooth pointwise correspondences from a functional map within a reasonable runtime, to solve the relaxed problem.

5 Results

In this section, we test comprehensive experiments on various datasets to evaluate the performance of our algorithm.

Datasets. Here we use the four benchmark datasets. The FAUST dataset [4] contains 100 human scans of 10 different individuals with 10 poses. The SCAPE dataset [1] has 71 shapes of the same person with varied postures. The TOSCA dataset [5] includes 76 shapes, which divides into 8 categories. In addition, considering the difference in the connectivity and the number of vertices across the scan shapes in real life, we use the re-mesh version of three datasets [6, 31] in our all experiments. These shapes do not share consistent connectivity and have different numbers of vertices. Furthermore, we also run our algorithm on the datasets with shape existing topological noise. SHREC’16 Topology dataset [17] contains 25 poses of an identical child with around 12k vertices, deforming near-isometrically with different topological shortcuts.

5.1 Performance

Firstly, we analyze the superior natures of our method, including the scalability as well as the stability.

Scalability. We test the scalability of our pipeline on a pair of shapes coming from the FAUST dataset [31], starting with a $10 \times 10$ functional map produced via the method of [31] with the orientation-preserving term and ending with the $80 \times 80$ functional map. As shown in Fig. 2, the target shapes have different mesh resolutions, as well as connectivity, while the source shape is the unchanged model with 5k vertices. When given a shape with 500 vertices as the target shape, where the details of the mesh such as the fingers and nose are simplified, the refinement result remains smooth and high quality. Conversely, even though the target shape has up to 150k vertices, which is equivalent to 30 times of the number of vertices on the source shape, our method still performs quite well similar to the one with 5k vertices.

Fig. 2

Scalability of our method. The far left one is the source shape with 5k vertices. The top row and the bottom row show the results of initialization (the numbers above the shapes indicate the numbers of vertices) and our results, respectively. As we can see that although there exists back-to-front on the legs or symmetry on the hands for the initialization, the results are smooth and excellent after the treatment of our method

Fig. 3

Stability test for our method and ZoomOut with the same noisy initializations. Here we run a total of 100 independent random tests, as shown in the gray dotted lines. The average error of 100 tests at each iteration is computed and visualized with the red solid line. Note that both in terms of robustness and accuracy, our method outperforms ZoomOut, a state-of-the-art map refinement method

Stability. In Fig. 3, we also assess the stability of our method against input with noise. A pair of shapes belonging to the TOSCA dataset [31] is used in these tests. Firstly, we compute a $10 \times 10$ functional map using the approach of [31]. Then, we add white Gaussian noise into the initial functional map independently and refine the maps using our method and ZoomOut with an iterative step size 10 for acceleration. The plot shows that our method effectively filters the noise after a small number of iterations. Moreover, we observe that 97% refined maps obtained by our refinement technology converge to the low-error level quickly, while only 2 cases of 100 refined maps don’t make the grade, where there exist left-to-right, back-to-front ambiguities of a large area in the initialization resulting from too much noise. Compared with ZoomOut, our method is more robust to noise in the input since we perform a sequence of filtering operations on the coarse functional maps during iterations.

5.2 Complete shape matching

Here we perform experiments on two benchmark datasets and compare our method with the recent five most similar mapping refinement methods, including ICP [27], kernel matching (KM) [40], BCICP [31], ZoomOut [22], MWP [13], both with respect to matching quality, computational efficiency, and smoothness of correspondence. For all competitors above except kernel matching, we use the wave kernel signatures (WKS) [2] with orientation-preserving operators [31] to estimate a functional map of size 20$\times$20 as their initialization. Kernel matching initializes its process by Signature of Histograms of OrienTations (SHOT) [35] as suggested by the authors.

Measurement. In our experiments, we measure the following metrics: accuracy, average runtime, and smoothness for the correspondence results between two shapes.

Accuracy. We measure the accuracy as the average per-vertex geodesic error with respect to the ground-truth correspondence, visualizing with the correspondence quality characteristics (CQC) curve [16].

Smoothness. For a given map T, we measure the smoothness by computing the Dirichlet energy of the transferred coordinate functions [29].

Fig. 4

Parameter analysis. We carry out experiments for analyzing the parameter on the FAUST dataset with three parameters, including the discrete scale $L+1$, iterative step size $k_{step}$ and the maximum dimension of spectral embedding $k_{max}$

Parameter setting. To find a balance between accuracy and efficiency, we test 30 pair shapes that belong to the FAUST dataset with different parameters, including the number of scales L, the iterative step size $k_{step}$ and the maximum dimension of spectral embedding $k_{max}$. The results under the different parameters are shown in Fig. 4, where the other parameter keeps constant when one parameter varies. We observe that the change of scale parameter L has little effect on time consumption, while the average error has little change if $L+1 \ge 7$. Moreover, along with the dimensionality $k_{max}$ increases, the time required for our method takes longer and the error tends to decrease. Therefore, here we set $L=6$ on all datasets, and $k_{max}$ can be selected from 50 to 150 for saving runtime. Additionally, when the iterative step gradually increases, the runtime becomes shorter and shorter and there is a small increase in error. Results produced by the steps smaller than 10 are within the acceptable error range.

Fig. 5

Our matching accuracies for two benchmark datasets including the FAUST (100 pairs) and SCAPE (71 pairs) datasets, in comparison with other state-of-the-art refinement methods

Fig. 6

Qualitative and quantitative examples on the FAUST (top row) and SCAPE (last row) datasets. The numbers below the shapes represent the average error of correspondence between the one with the source shapes (first column). Similar colors encode corresponding points. Note that our method obtains a more perfect correspondence than other methods from color to error

For complete shape matching, we set $k_{max}=100$. We compare our matching accuracy across two benchmark datasets with other refinement strategies, as visualized via CQC curves in Fig. 5. The three metrics of all methods are reported in Table 1. In Fig. 5 and Table 1, “Ours” represents that our method does not adopt any acceleration strategy, while “Ours*” reports the results of our method with the subsampling strategy with 500 vertices. Figure 6 illustrates more qualitative and quantitative results. In comparison with the best competing methods with respect to the accuracy across different datasets, our algorithm without acceleration achieves 51.95% improvement on 100 pair shapes from the FAUST dataset and 61.70% on 71 pair shapes from the SCAPE dataset. At the same time, since our method adopts a sequence of filtering operations on coarse functional maps, we also achieve 23.55% and 48.53% improvement on two datasets, respectively, in terms of smoothness. Moreover, our acceleration strategy with subsampling is powerful. Although the accuracy and smoothness of our method decrease a little after acceleration, more importantly, the results still outperform other methods and the time consumption is cut down nearly 25 times on a computer with a 3.7GHz Intel i5 CPU and 8.0GB RAM.

Fig. 7

Top: correspondence performance comparison on the SHREC’16 Topology benchmark with MWP, PFM and ZoomOut starting the same initialization. Bottom: qualitative and quantitative examples on the dataset

5.3 Topological noise

Our method also can be used to cope with shape matching where the target shape has topological noise relative to the source shape, such as they maybe have distinct genus due to self-contact. To perform filtering operation in a same range of frequencies of two shapes, we require to truncate the LBO’s eigenfunctions with different sizes. More detailedly, we firstly set $k_{ini}^{\mathcal {N}}=k_{ini}$, $k_{max}^{\mathcal {N}}\text {=}k_{max}$, and compute $k_{ini}^{\mathcal {M}}$ and $k_{max}^{\mathcal {M}}$ via $k_{ini}^{\mathcal {M}}=\max \nolimits _{i=1}^{k^{\mathcal {M}}}\left\{ i,\lambda _{i}^{\mathcal {M}}<\max \nolimits _{j=1}^{k_{ini}^{\mathcal {N}}}\lambda _{j}^{\mathcal {N}} \right\}$ and $k_{max }^{\mathcal {M}}=\max \nolimits _{i=1}^{k_{{}}^{\mathcal {M}}}\left\{ i,\lambda _{i}^{\mathcal {M}}<\max \nolimits _{j=1}^{k_{max }^{\mathcal {N}}}\lambda _{j}^{\mathcal {N}} \right\}$, where $\mathcal {M}$ and $\mathcal {N}$ are the shape with topological noise and the complete shape, respectively. Then, we determine the number of iterations ${{n}_{iter}}=k_{max }^{\mathcal {M}}-k_{ini}^{\mathcal {M}}+1$ . Next, ${{k}^{\mathcal {M}}}$ is increased one by one and ${{k}^{\mathcal {N}}}$ is increased uniformly from ${{k}^{\mathcal {N}}_{ini}}$ to ${{k}^{\mathcal {N}}_{max}}$ with iterative times ${{n}_{iter}}$. Here the initialization is brought with a $30 \times 30$ functional map computed by standard least squares with the SHOT descriptor [35]. Here we also use the parameters $k_{max}^{\mathcal {N}}=100$ and $L=6$. We compare our matching accuracy with other state-of-the-art matching methods including PFM [32], MWP and ZoomOut, see Fig. 7.

6 Conclusion

In this paper, we developed a simple and efficient incremental technique based on the functional map framework for shape correspondence. For the sake of analyzing the shapes comprehensively, we made full use of both local and global features as shown in the optimization problem and solution. First of all, we defined an optimization problem that aims to preserve the spectral manifold wavelets with different dimensionality of spectral embedding at all discrete scales. Then, to address the optimization problem, we found that when we adopted the Parseval wavelet frames, our solution became simpler and more flexible. With the help of the spectral up-sampling technique, we computed alternately the functional maps and point-to-point correspondences between the spatial space and spectral space. Experimental evaluations on various well-known datasets showed that our method has superior performance in terms of accuracy, as well as stability and smoothness.

Although the method is robust to the initialization with noise, it will bring undesirable results from an initialization existing left-to-right, back-to-front ambiguity, or the double flip self-symmetry with a large area, as shown in two failure cases in Fig. 3. Additionally, our method cannot work well on the partial shape correspondence task. In the future, we would like to investigate how to design and add an orientation-preserving process identifying the intrinsic symmetry to our framework and extend our algorithm to other applications such as multi-shape matching, and symmetry detection.

Appendices

Appendix

Equivalence of two optimization problems

Here we show the optimization problem (10) and (11) are equivalent when adding a regularizer represented as $\mathcal {R} \left( \mathbf {P} \right) = \left\| \left( {\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+} - \mathbf {I} \right) \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{A_\mathcal {N}}^{2}$ into problem (10).

To begin with, we give the result: for any matrix $\mathbf {X}$, $\mathbf {Y}$ and a matrix $\mathbf {B}$ satisfying $\mathbf {B}^\mathrm {T} \mathbf {A} \mathbf {B} = \mathbf {I}$, i.e., $\mathbf {B}^{+} = \mathbf {B}^\mathrm {T} \mathbf {A}$, where $\mathbf {A}$ is a symmetric positive-definite matrix, and let $\left\| \mathbf {X} \right\| _{A}^{2} = trace(\varvec{\mathbf {X}^\mathrm {T} \mathbf {AX}})$, and then, the following equation holds:

$$\begin{aligned} \left\| \mathbf {BX} - \mathbf {Y} \right\| _{F}^{2} + \left\| \left( \mathbf {BB}^{+} - \mathbf {I} \right) \mathbf {Y} \right\| _{A}^{2} = \left\| \mathbf {BX} - \mathbf {Y} \right\| _{A}^{2}. \end{aligned}$$

(14)

In fact, we observe that subtracting and adding the term $\mathbf {BB}^{+}\mathbf {Y}$ in the $\left\| \mathbf {BX} - \mathbf {Y} \right\| _{A}^{2}$, we get

$$\begin{aligned}&\left\| \mathbf {BX} - \mathbf {Y} \right\| _{A}^{2}\\&\quad = \left\| \mathbf {BX} - \mathbf {BB}^{+}\mathbf {Y} + \mathbf {BB}^{+}\mathbf {Y} -\mathbf {Y} \right\| _{A}^{2} \\&\quad = \left\| \mathbf {B} \left( \mathbf {X} - \mathbf {B}^{+} \mathbf {Y}\right) \right\| _{A}^{2} + \left\| \left( \left( \mathbf {BB}^{+} \right) - \mathbf {I} \right) \mathbf {Y} \right\| _{A}^{2} \\&\qquad + 2 trace\left( \left( \mathbf {B} \left( \mathbf {X} - \mathbf {B}^{+} \mathbf {Y} \right) \right) ^\mathrm {T} \mathbf {A} \left( \mathbf {BB}^{+} - \mathbf {I} \right) \mathbf {Y}\right) . \end{aligned}$$

On the one hand, since $\mathbf {B}^\mathrm {T} \mathbf {A} \mathbf {B} = \mathbf {I}$, we have

$$\begin{aligned}&\left\| \mathbf {B} \left( \mathbf {X} - \mathbf {B}^{+} \mathbf {Y}\right) \right\| _{A}^{2}\\&\quad = trace \left( \left( \mathbf {X} - \mathbf {B}^{+} \mathbf {Y} \right) ^\mathrm {T} \mathbf {B}^\mathrm {T} \mathbf {AB} \left( \mathbf {X} - \mathbf {B}^{+} \mathbf {Y} \right) \right) \\&\quad = \left\| \mathbf {X} - \mathbf {B}^{+} \mathbf {Y} \right\| _{F}^{2}. \end{aligned}$$

On the other hand, note that $\mathbf {B}^\mathrm {T}\mathbf {A} \left( \mathbf {BB}^{+} - \mathbf {I} \right) = \mathbf {B}^{+} - \mathbf {B}^{+} = 0$, where $\mathbf {B}^\mathrm {T} \mathbf {A} \mathbf {B} = \mathbf {I}$ and $\mathbf {B}^{+} = \mathbf {B}^\mathrm {T} \mathbf {A}$ are used.

Therefore, Eq. (14) is given. Let $\mathbf {X} = \mathbf {C}^{*}$, $\mathbf {B} = \varvec{\Phi }_{\mathcal {N}}^{k}$, $\mathbf {A} = \mathbf {A}_\mathcal {N}$, and $\mathbf {Y} = \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}$, we have

$$\begin{aligned} \begin{aligned}&\left\| \varvec{\Phi }_{\mathcal {N}}^{k}\mathbf {C}^{*} - \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{F}^{2} + \left\| \left( \varvec{\Phi }_{\mathcal {N}}^{k} \left( \varvec{\Phi }_{\mathcal {N}}^{k}\right) ^{+} - \mathbf {I} \right) \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{A_{\mathcal {N}}}^{2} \\&\quad = \left\| \varvec{\Phi }_{\mathcal {N}}^{k}\mathbf {C}^{*} - \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k} \right\| _{A_{\mathcal {N}}}^{2}. \end{aligned} \end{aligned}$$

As for the issue that

$$\begin{aligned} \begin{aligned}&\mathop {\arg \min }\limits _{\mathbf {P}} \left\| \varvec{\Phi }_{\mathcal {N}}^{k} \mathbf {C}^{*} - \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}\right\| _{F}^{2} \\&\quad = \mathop {\arg \min }\limits _{\mathbf {P}} \left\| \varvec{\Phi }_{\mathcal {N}}^{k} \mathbf {C}^{*} - \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}\right\| _{A_\mathcal {N}}^{2}, \end{aligned} \end{aligned}$$

both problems can be solved by finding the closest column between $\varvec{\Phi }_{\mathcal {N}}^{k} \mathbf {C}^{*}$ and $\varvec{\Phi }_{\mathcal {M}}^{k}$ since the matrix $\mathbf {P}$ is encoded by a pointwise map. To improve accuracy and smoothness of correspondences, we select fast Sinkhorn filter algorithm to solve this optimization problem.

Proof of Remark 1

Here we give the proof that (13) is a relaxed solution to problem (12) under certain conditions.

Proof

Indeed, the analytical solution of problem (12) exists by solving a series of linear equations as follows:

$$\begin{aligned} \begin{aligned} {{\mathbf {C}}_{k}}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {M}}^{k} \right) }^{+}}=g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right)&{{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}, \\&l=0,1,......,L. \end{aligned} \end{aligned}$$

Contrary to Eq. (8), here the point-to-point mapping matrix $\mathbf {P}$ is known, while the functional map matrix $\mathbf {C}_k$ is unknown and enforces no constrain.

Multiplying $g\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right)$ on the left and right sides of the above equations, then

$$\begin{aligned} \begin{aligned} {{\mathbf {C}}_{k}}g_{\mathcal {M}}^{2}{{\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) }}=g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}&\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) ,\\&l=0,1,......,L. \end{aligned} \end{aligned}$$

Summing the above equations, we obtain

$$\begin{aligned} \sum \limits _{l=0}^{L}{{{\mathbf {C}}_{k}}g_{\mathcal {M}}^{2}{{\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) }}}&=\sum \limits _{l=0}^{L}{g_{\mathcal {N}}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}} \\&\quad \times \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) . \end{aligned}$$

Taking $\mathbf {C}_{k}$ out of the summation on the left side of the equation, we get

$$\begin{aligned} {{\mathbf {C}}_{k}}\sum \limits _{l=0}^{L}{g_{\mathcal {M}}^{2}{{\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) }}}&=\sum \limits _{l=0}^{L}{g_{\mathcal {N}}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}} \\&\quad \times \mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) . \end{aligned}$$

According to Eq. (9), this implies the desired result with

$$\begin{aligned} {{\mathbf {C}}_{k}}=\sum \limits _{l=0}^{L}{g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {N}}^{k} \right) {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda }_{\mathcal {M}}^{k} \right) }. \end{aligned}$$

$\square$

Equivalence of two functional map representations

To derive the equivalence of two functional map representations if the pointwise correspondence from the shape $\mathcal {M}$ to the shape $\mathcal {N}$ is an isometry, where Laplacian eigenvalues of two shapes are same, none of which are repeating, we first give following result: if the diagonal matrices $\mathbf {A}_l, \mathbf {D}_l, l = 0...L$, satisfy $\sum _{l = 0}^L \mathbf {A}_l\mathbf {D}_l = \mathbf {I}$, $\sum _{l = 0}^L \mathbf {A}_l \mathbf {B}\mathbf {D}_l = \mathbf {B}$ holds for any diagonal matrix $\mathbf {B}$. To see that, we observe that if two diagonal matrices are multiplied, the commutative law of multiplication is satisfied, i.e., $\mathbf {B}\mathbf {D}_l = \mathbf {D}_l \mathbf {B}$. From this, it immediately follows that $\sum _{l = 0}^L \mathbf {A}_l \mathbf {B}\mathbf {D}_l = \sum _{l = 0}^L \mathbf {A}_l\mathbf {D}_l \mathbf {B} = \mathbf {B}$.

For one thing, under the condition of isometry, ZoomOut[22] proved the functional map matrix $\mathbf {C}_k$ is both orthonormal and diagonal. For another thing, when Laplacians of two shapes have same eigenvalues, none of which are repeating, we obtain that $g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda } _{\mathcal {N}}^{k} \right) = g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda } _{\mathcal {M}}^{k} \right)$, and all of them are diagonal. Thus, we get the equivalence of two functional map representations with $\mathbf {A}_l = g_{\mathcal {N}}\left( {{s}_{l}}\varvec{\Lambda } _{\mathcal {N}}^{k} \right)$, $\mathbf {D}_l = g_{\mathcal {M}}\left( {{s}_{l}}\varvec{\Lambda } _{\mathcal {M}}^{k} \right)$ and $\mathbf {B} = {{\left( \varvec{\Phi }_{\mathcal {N}}^{k} \right) }^{+}}\mathbf {P}^\mathrm {T}\varvec{\Phi }_{\mathcal {M}}^{k}$, which is a general functional map.