\section{Problem Setting}
\label{sec:problem_setting}
Shape correspondence serves as an umbrella term encompassing multiple problem formulations. We begin by providing a unified overview of these problems and discuss key properties that differentiate specific instances with respect to their input and output. We then introduce topological aspects of maps between surfaces, laying the foundation for the methods surveyed later.
\subsection{Shape Correspondence}
\label{subsec:shape_corres_unified}
While shape correspondence problems may vary in formulation, assumptions, and objectives,
they all operate on a common object of interest: a relation defined between two or more input surfaces \({\surfaceZero, ... , \surfaceN}\). For a pair of surfaces \(\surfaceA\) and \(\surfaceB\), this relation can be formally defined as
%
\begin{align*}
\corresRelation_{\surfaceA\surfaceB} = \{(s_i, s_j) \mid s_i \in \surfaceA,\ s_j \in \surfaceB,\ \text{s.t. } s_i \text{ corresponds to } s_j\}, 
\end{align*}
%
which associates a point \(s_i\) from surface \(\surfaceA\) with a corresponding point \(s_j\) on \(\surfaceB\).

While this formalism captures all correspondences between surfaces, it is often more natural to interpret a correspondence as a \emph{map} from a source shape \(\surfaceA\) to a target shape \surfaceB. This view is more restrictive and inherently directional, as it excludes one-to-many and symmetric correspondence relations.

\subsection{Input}
Methods have different assumptions about the input data they require, \eg, regarding representation, similarity, and user input.

\subsubsection*{Input Surfaces}\
Some methods are capable of operating on point clouds or triangle soups, \ie, collections of disconnected triangles. If a richer representation is necessary, the most prevalent choice is a well-defined 2-manifold surface, typically discretized as a connected triangle mesh. 

Beyond representation, the methods vary in their \emph{geometric assumptions} about the relation between the input surfaces. Some approaches are restricted to near-isometric deformations, whereas others can accommodate highly non-isometric cases.

Further, the methods differ in their \emph{topological assumptions} about the input surfaces. Many algorithms are constrained to surfaces with arbitrary but identical genus. Further, some algorithms solely operate on surfaces with specific topologies, such as spherical or disk-like structures, restricting their applicability.

\subsubsection*{Level of Automation}\
While fully automatic methods only take the surfaces as input, other methods need additional user input to produce meaningful results. Some methods can optionally incorporate guidance. User input often takes the form of user-defined constraints, such as a sparse set of point correspondences, commonly referred to as \emph{landmarks}. These specify matches between selected surface points, and are treated as hard or soft constraints. Alternatively, the user may provide a dense but imprecise initial map. In data-driven methods, a preferred solution is often indicated by roughly aligning the shapes in ambient space or by prescribing a canonical orientation. Such setups are commonly referred to as \emph{weakly supervised}.

\subsection{Output}
The properties of a method's output can be categorized in different ways, \eg, dense or sparse, complete or partial, soft or sharp, and pairwise or groupwise. The structure is determined by the characteristics of the input data (in particular, the surface representation), the problem’s formulation, and the paradigm used to establish the correspondence. \Cref{sec:paradigm_overview} surveys existing paradigms in more detail. Here, we take a step back and examine the broader landscape of shape correspondence, outlining the key axes of variation.

\subsubsection*{Dense vs. Sparse}\
The task of establishing a \emph{dense} correspondence, which is typically the main objective in shape correspondence research, is commonly referred to as \emph{shape matching}. 
Many methods work with a discrete representation of the correspondence, where the granularity may differ: 
some compute \emph{vertex-to-vertex} maps, while others compute \emph{element-to-element} maps. 
A special case of a discrete correspondence occurs when both surfaces are decomposed into a set of segments, and the correspondence is established between those segments.
Some approaches go beyond the discrete nature of these representations and compute dense \emph{point-to-point} maps, assigning for every point on surface \(\surfaceA\) a corresponding point on surface \(\surfaceB\). Point-to-point maps are often realized via piecewise-linear functions, starting from a vertex-to-vertex map. For an arbitrary vertex-to-vertex map, the trivial piecewise-linear extension is generally not embedded in the surface. The challenge is to find a \emph{common triangulation} containing the vertices of both surfaces with embedded edges, \eg, overlay meshes, see \Cref{subsec:overlay_meshes}.

Some methods compute correspondences only for a small subset of surface points. These \emph{sparse} correspondences can often serve as landmarks for subsequent dense matching methods. Although dense correspondence is required for most applications, it is advantageous to compute a sparse correspondence first: Since methods for sparse correspondence operate on a small subset of input vertices, they can often give optimality guarantees. As numerous shape matching methods only find local optima, they benefit from such meaningful initializations.

\add{To better handle the computational complexity of most shape matching algorithms, a commonly applied technique is \emph{map refinement}. The idea is to start with a sparse correspondence, which is then successively refined until a dense matching is obtained. In many cases, the refinement step is local, effectively decomposing the problem into multiple smaller subproblems. Algorithms using such multiscale approaches include \cite{VestnerLRBC17-ProductManifoldFilter, Vestner2017-KernelMatching}.}


\subsubsection*{Full vs. Partial}\
Correspondences can be classified based on the \emph{coverage} of the surfaces. \emph{Full} correspondences ensure that the complete shape is covered by the correspondence. \emph{Partial} correspondences, by contrast, cover only a subset of points on one or both surfaces, leaving some regions unmapped. Correspondences can be categorized as \emph{full-to-full, full-to-partial}, and \emph{partial-to-partial}. \add{Algorithms establishing partial correspondences include \cite{Sahillioglu2014-ShapeExtremities, Ganapathi-Subramanian16-stableRegionCorres, litany2016-nonRigidPuzzles, attaiki2021fm-dpfm, wu2023fm-multiPartShapeMatching}.} % EntropicMetricAlignment was nonRigidPuzzles

Partial correspondences are useful when some features (topological or geometrical) of one surface are absent in the other, \eg, a mug and a glass, where the mug has a handle that the glass lacks, or when the input shapes have defects such as missing parts or holes. In general, partial correspondences are more challenging as they require identifying not only the correspondence itself but also the parts that are missing in one shape compared to the other. 

Important to note is that coverage is \emph{independent} of density: a correspondence can cover the whole shape in a sparse fashion, assigning only a few representative points per region.

\subsubsection*{Sharp vs. Soft}\
Another way correspondences can be classified concerns the \emph{sharpness} of the correspondence. \emph{Sharp} correspondences assign a point on one surface to exactly one point on the other, while \emph{soft} correspondences allow a single point to correspond to multiple points, \add{\eg, \cite{sahilliouglu2012minimum-dist-EM,Solomon2012-SoftMaps}}.
They can encode uncertainty or symmetries by associating probabilities \add{(\eg, \cite{Solomon2016-EntropicMetricAlignment})} with potential matches, representing multiple plausible correspondences simultaneously.

\subsubsection*{Surface Homeomorphisms}\
Surface homeomorphisms offer a mathematically \emph{rigorous and unambiguous}  notion of correspondence between shapes. They are widely regarded as the gold standard due to their beneficial properties, \ie, bijectivity and continuity, which guarantee consistent, invertible, and well-behaved correspondences. For certain applications, \eg, texture or template transfer, these properties are desirable or even crucial for success. In literature, such correspondences are referred to as \emph{inter-surface maps} \( \mapPhi\).

Note that an inter-surface map can only exist between surfaces that share the \emph{same} Euler--Poincaré characteristic, which encodes the genus of the surface, as dictated by the \emph{classification theorem} \cite{gallier2013-classificationTheorem}.

\subsubsection*{Geometric Consistency}\
Since vertex-to-vertex or element-to-element correspondences are not trivially extendable to inter-surface maps, a discrete analogue of homeomorphisms is required to assess the structural quality of the correspondence. Enforcing \emph{geometric consistency} \cite{windheuser2011-geometricConsistency} provides such an analogue.

Conceptually, a geometrically consistent map preserves the local proximity structure of surface elements, ensuring that neighborhoods are mapped to neighborhoods in a coherent manner (see \Cref{fig:geometric_consistency}). The exact constraints, however, depend on the specific problem formulation, see \Cref{sec:geometric_consistency}.

\begin{figure}[htbp]
    \centering
    \include{fig/geometric-consistency}
    \vspace{-1cm} % optional tweak to pull figure closer to text
    \caption{Geometric consistency provides a discrete analogue for surface homeomorphisms. The map between vertices is indicated by dotted lines. A geometric consistent correspondence preserves the local neighborhood structure. Based on \cite{roetzer2024in-discomatch}.}
    \label{fig:geometric_consistency}
\end{figure}

\subsubsection{Pairwise vs. Groupwise}\
The desire to process multiple shapes simultaneously gives rise to correspondences within \emph{shape collections}, see \Cref{fig:shape_collection}, which depicts texture transfer among multiple quadrupeds. 
Using a straightforward approach, correspondences between every pair of surfaces are required. Given \(n\) surfaces and a (possibly non-symmetric) correspondence relation \(\corresRelation\), up to \(n \times (n-1)\) directed correspondence relations, \ie, maps, may be required, leading to quadratic complexity \(\mathcal{O}(n^2)\) in the number of surfaces. 

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\linewidth]{fig/Background/shape_collection.png}
    \caption{Shape correspondence for a shape collection. The correspondence is visualized via texture transfer. Taken from \cite{schmidt2023-adaptiveTriangulation}.}
    \label{fig:shape_collection}
\end{figure}

However, it is sufficient to compute a subset of \(n - 1\) \emph{invertible} maps between selected surfaces, reducing the complexity to \(\mathcal{O}(n)\). To obtain maps between all surfaces in a collection, the maps can be extended to a full set of \emph{cycle-consistent maps} via composition. Maps are cycle-consistent if for any sequence of surfaces 
\(\mathcal{S}_{1} \to \mathcal{S}_{2} \to \dots \to \mathcal{S}_{k} \to \mathcal{S}_{1}\), it holds
\[
\Phi_{\mathcal{S}_{k} \mathcal{S}_{1}} 
\circ \dots 
\circ \Phi_{\mathcal{S}_{1} \mathcal{S}_{2}} 
= \mathrm{id}.
\]
%
Strictly speaking, cycle-consistency requires that maps are invertible, making inter-surface maps particularly suitable for such applications. In practice, this requirement is often relaxed and the composition only needs to approximate the identity under a chosen error metric.

To find appropriate surfaces pairs for the subset of maps, the correspondence graph with the surfaces as nodes has to be considered. An edge in the correspondence graph indicates that a correspondence is computed for the pair of surfaces. In the correspondence graph, there needs to be a path between every surface pair. For \(n-1\) maps, this graph must not contain any cycles and thus is a spanning tree. Possible choices for the graph topology are \emph{ring topology} and \emph{star topology}. For the latter case, a reference surface is used, which is often called \emph{template}, and correspondences are computed between the template and every other surface. Note that distortion may accumulate along the composition path, making star topology the preferred choice.

Alternatively, a complete graph \cite{eisenberger2023in-gmsm} can be established and optimal paths within this graph are obtained while optimizing pairwise correspondences. \add{Cycle-consistency can also be used as regularizer with the goal to establish the full set of maps in such a way that the maps are \emph{consistent} \cite{sahilliouglu2014-dynamicProgrammingCC}, \ie, all possible map compositions between any two shapes yield the same map.} \add{Further, shape collections together with an initial set of maps can be refined by replacing outlier maps with higher-quality maps generated through map composition, thereby promoting cycle-consistency \cite{nguyen2011ImprovingCConsistency}.}

\subsection{Map Topology}
Beyond establishing geometric correspondences, surface homeomorphisms also encode the map's topological structure, identifying topological features, \eg, handles and tunnels, as well as the twisting of the map around them.

Given a pair of surfaces and two homeomorphisms between them, the maps are said to be \emph{homotopic} if one can be continuously deformed into the other while respecting correspondences but without introducing any discontinuities. Maps that are not homotopic belong to different \emph{homotopy classes}, meaning they wrap around the topological features in fundamentally different ways, see \Cref{fig:map_topology}.
%
\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\linewidth]{fig/Background/map_topology2.png}
    \caption{Two maps between the same pair of surfaces. As the maps \add{\(f\) and \(\tilde{f}\)} wrap around the handles of the surfaces differently, \del{as}indicated by the black arrow, the maps belong to different homotopy classes. Note that both results are valid, although the top map corresponds to the expected map in most scenarios. Adapted from \cite{born2021-mapHomologyInterference}.}
    \label{fig:map_topology}
\end{figure}

Additionally, fixed landmarks act as topological features by interpreting them as punctures in the surface. Thereby, the number of distinct homotopy classes for maps between the surfaces increases.

\section{Paradigm Overview}
\label{sec:paradigm_overview}
The problem of determining shape correspondences can be addressed from various perspectives, resulting in different paradigms. This section provides an overview of popular paradigms and presents them in a generic form. \Cref{sec:advances_in_shape_alignment,sec:advances_in_combinatorial_approaches,sec:advances_in_distortion_based_approaches,sec:advances_in_the_functional_maps_framework} examine each paradigm in more detail, highlighting recent advances. It is worth noting that specific algorithms may draw from multiple paradigms. 

\subsection{Shape Alignment}
A natural approach to shape correspondence is to compute a \emph{deformation} \(D_i(\surfaceI)\) of the input shapes to align them. One can either deform the source shape to align it with the target, or deform both shapes, often aligning them to a canonical pose or template, or conversely, aligning the template with the inputs. For a pair of surfaces, the correspondence task is typically formulated as an extrinsic optimization problem minimizing
%
{\begin{align}
E_{\text{align}}(D_\mathcal{A}(\surfaceA), D_\mathcal{B}(\surfaceB)) &=  E_{\text{dist}}(D_\mathcal{A}(\surfaceA), D_\mathcal{B}(\surfaceB)) \\
& \quad +\; \omega_{\text{reg}} \cdot E_{\text{reg}}(D_\mathcal{A}(\surfaceA), D_\mathcal{B}(\surfaceB)), \nonumber
\end{align}}
where \(E_{\text{dist}}(D_\mathcal{A}(\surfaceA), D_\mathcal{B}(\surfaceB))\) measures the distance between the two shapes in ambient space and \(E_{\text{reg}}(D_\mathcal{A}(\surfaceA), D_\mathcal{B}(\surfaceB))\) is a regularization term, weighted by \(\omega_{\text{reg}}\), that smoothes the deformation to avoid unrealistic results.

The chosen regularization term implicitly defines the underlying deformation model. Crucially, the deformation model determines the correspondence. The central challenge is to preserve local geometric features of the surfaces while finding a deformation process that yields accurate correspondences. Since such methods are extrinsic, the correspondence remains implicit and must be explicitly extracted after the deformation, typically by assigning each point to its closest point on the other surface.

\subsection{Combinatorial Optimization}
Shape correspondence can be approached from a \emph{combinatorial} perspective, where the goal is to find a permutation matrix \(P \in \Pi_n \subset [0,1]^{n \times n}\) that matches \(n\) vertices (or more generally, elements) of two input shapes \add{under a specific cost function}. This permutation matrix induces a map \(\varphi: \mathbb{N} \xrightarrow{} \mathbb{N} \), mapping vertex \(i\) of \(\surfaceA\) \chg{onto} vertex \(j\) \chg{of} \(\surfaceB\).

Such combinatorial problems are commonly \chg{cast} %
%referred to 
as \emph{assignment problems} and are well studied. For deeper insights, we refer to \cite{burkard2012-assignmentProblemBook}.

\subsubsection*{Linear Assignment Problem}\
A simple formulation is the \emph{linear assignment problem} (LAP) \cite{burkard2012-assignmentProblemBook}:
%
\begin{equation}
\min_{P \in \Pi_n} 
\sum_{i=1}^n \sum_{j=1}^n c_{ij}\;p_{ij},
\end{equation}
where \(C \in \reals^{n \times n}\) is a cost matrix, with entry \(c_{ij}\) representing the cost of assigning vertex \(i\) of shape \(\surfaceA\) to vertex \(j\) of shape \(\surfaceB\). This cost often encodes a similarity or dissimilarity measure between vertices, see \Cref{sec:eval}.

Standard approaches for solving LAPs include the Hungarian method \cite{kuhn1955-hungarianMethod} and the auction algorithm \cite{bertsekas1990-auctionAlgorithm}.

The LAP assumes that there are \(n\) elements on \(\surfaceA\) that are assigned to \(n\) elements on \(\surfaceB\). As this is not always the case, a generalization of the LAP is sometimes considered, known as \emph{transportation problem} \cite{bazaraa2011-linearProgrammingTransportationBook}.

The continuous extension of the LAP leads to \emph{optimal transport} formulations, where \(P\) is no longer restricted to a permutation matrix but can be a stochastic matrix with row and column sums equal to one. Then \(P\)  can be viewed as a soft map from \(\surfaceA\) to \(\surfaceB\).

\subsubsection*{Quadratic Assignment Problem}\
The LAP considers only unary costs, \ie, they are pointwise on \(\surfaceA\) and \surfaceB. To incorporate pairwise relationships, shape correspondence can instead be formulated as a \emph{quadratic assignment problem} (QAP), written as
%
\begin{align}
&\min_{P \in \Pi_n} 
\| D_{\surfaceA} - P D_{\surfaceB} P^\top \|_F^2 \\
= 
&\min_{P \in \Pi_n} 
\sum_{i=1}^n \sum_{j=1}^n 
\big( D_{\surfaceA}(i,j) - D_{\surfaceB}(\varphi(i), \varphi(j)) \big)^2, \nonumber
\end{align} 
where \(D_{\surfaceA}, D_{\surfaceB} \in \reals^{n \times n}\) encode pairwise relations (\eg, geodesic distances) of the two shapes respectively.

The QAP is a well-studied combinatorial model and is known to be NP-hard \cite{Loiola2007-QAPSurvey, burkard2012-assignmentProblemBook}. Practical solutions typically rely on relaxations, heuristics, or approximate solvers to make the problem tractable.
%
\subsubsection*{Higher Order Matchings and General Cost Functions}\ 
\add{Cost functions involving higher-order interactions lead to higher-order assignment problems, which generalize the classical case. In the past, especially \emph{cubic assignment problems} have been studied \cite{Zeng2010-higherOrderMatching, Smeets2011-higherOrderMatching}. For fully \emph{general cost functions}, possibly non-polynomial and non-convex, the problem remains a permutation optimization, but falls outside the standard assignment problem framework. Such problems are typically approached using heuristic methods, often \emph{stochastic}, including genetic algorithms or simulated annealing. They explore the space of possible permutations stochastically, often without guaranteeing a global optimum.}
%
\subsection{Distortion-Based Approaches}
Instead of an extrinsic perspective, as in deformation-based approaches, shape correspondence can be addressed intrinsically, leading to \emph{distortion-based} methods. Rather than deforming one shape to match the other, this paradigm conceptualizes the correspondence as ``sliding'' one shape over the surface of the other via a map \(\Phi\). The goal is thus to minimize the distortion introduced by \(\Phi\) from source mesh \(\surfaceA\) to target \(\surfaceB\):
%
\begin{align}
    E_{\text{corres}}(\Phi(\surfaceA)) = E_{\text{distortion}}(\Phi(\surfaceA))
     &+ \omega_{reg} (E_{reg}(\Phi(\surfaceA)).
\end{align}
%
The correspondence is primarily guided by the distortion measure \(E_{\text{distortion}}\) (see \Cref{sec:eval} for a review). The regularization term \(E_{\text{reg}}\), weighted by \(\omega_{\text{reg}}\), serves two purposes: It guides the correspondence, \eg, via landmark correspondences, and ensures that the map representation remains \emph{valid}, \eg, bijective.

Since maps are inherently directional, it is common to optimize not only the map \(\Phi(\surfaceA)\) but also, when available, its inverse \(\Phi^{-1}(\surfaceB)\).


\subsection{Functional Maps}
Instead of matching surfaces directly, spectral methods establish correspondences in the spectral domain. A widely adopted spectral framework for this purpose are \emph{functional maps}~\cite{ovsjanikov2012fm-main}, with the goal of establishing correspondences between functions.

In the functional map framework, each surface $\surfaceI$ is equipped with a (truncated) orthonormal basis 
$\Phi_k^{\surfaceI} \in \reals^{n_{\surfaceI} \times k}$, where $n_i$ denotes the number of vertices of the surface. 
In practice, this truncated basis is typically chosen as the first $k$ eigenvectors of the Laplace--Beltrami 
operator (LBO). 

A functional map between two surfaces $\surfaceA$ and $\surfaceB$ can then be represented compactly 
by a matrix $C \in \reals^{k \times k}$. This matrix describes how coefficient vectors of functions 
transform between the two spectral bases. Specifically, if a function on $\surfaceA$ is represented 
in the truncated basis $\Phi_k^{\surfaceA}$ by the coefficient vector 
$\mathbf{a} = (a_1, \dots, a_k)^\top$, then the coefficients of the corresponding function on 
$\surfaceB$ in the truncated basis $\Phi_k^{\surfaceB}$ are given by

\[
\mathbf{b} = C \mathbf{a}.
\]

Since generally \(k \ll n_{\surfaceI}\), optimization and matching in the spectral domain are more efficient than operating directly on the surfaces. However, \(C\) encodes correspondences in the spectral domain rather than providing an explicit point-to-point map.

A central challenge in this framework is to constrain and regularize \(C\) such that it reflects desired structural properties such as bijectivity and locality. Further, functional map methods relying on the LBO basis assume (near-)isometric deformations as the operator is invariant under such deformations. In (near-)isometric scenarios, the invariance implies a one-to-one correspondence between the spectral eigenvectors. Recent work seeks to overcome this limitation and extend functional maps to non-isometric settings.

Moreover, while some applications (\eg, normal transfer) can operate directly with \(C\), other tasks (\eg, shape morphing) require an \emph{explicit} (vertex-to-vertex) correspondence. In such cases, the functional map must be converted into an explicit map representation aligning with the definition of correspondences in ~\Cref{subsec:shape_corres_unified}.

\color{black}




