Supervised Descriptor Learning for Non-Rigid Shape Matching

Get Complete Project Material File(s) Now! »

Context in Differential Geometry and its Discrete Equivalents

This chapter introduces the main mathematical tools that will be used throughout the thesis. A brief overview of differential geometry focused on intrinsic geometry is provided. We put emphasis on the role of the metric tensor and the pullback metric in the definitions of differential operators. This chapter also provides a brief remainder of the Finite Element Method applied to the discretization of common differential operators. This chapter can be skipped by readers familiar with the continuous theory.

Differential Geometry

The study of surface deformations is central in this thesis. Therefore some notions and terminology from differential geometry are recalled here. The aim of this section is to introduce the notions of metric tensor and more importantly of pullback metric by a diffeomorphism. The pullback metric accounts for the intrinsic distortion underlying a mapping between shapes. This will be a key tool for our analysis of surface deformations as it allows a classification of mappings according to their impact on the local structure.
To represent diffeomorphisms and distortions as operators on functions, we will need some basic differential operators such as gradients and Laplacians. We will focus on the change of variables which is equivalent to a change of metric in differential operators. This remark allows us to construct operators provably informative of the intrinsic structure and explain the leading role of the Laplace-Beltrami operator in geometry processing.
This basic introduction to differential geometry is greatly inspired by [78, 103]. The Einstein summation convention is sometimes used to lighten the notations. Repeated indices imply a summation, i.e. gij fj means j gij fj . Moreover when dealing with tensors upper indices denote an element of the inverse matrix Aij = (A−1)ij .

Manifold

In practice we will most of the time deal with surfaces in R3. However, operations on intrinsic informations (e.g. transport, composition of distortion) may lead to metric tensors which do not correspond to embedded surfaces and are only meaningful for general manifolds. Thus, it is important to start with abstract definitions.
A topological manifold M is a space such that each point has a neighborhood diffeomorphic to Rn. To introduce differential calculus, it is necessary to always refer to the Euclidean space where derivatives are well-defined. To do so we introduce a local parametrization of M called an atlas. An atlas on M is a countable collection of pairs (Uα, ψα) named charts where Uα are sets covering M and ψα : Uα → Rn are homeomorphisms acting as local parametrizations.
Since the sets Uα cover the entire manifold some points maybe found in two different charts. If Uα and Uβ overlap then one can change the coordinate system by means of the transition map:
ψβα = ψβ ◦ ψα−1 : ψα(Uα ∩ Uβ) → ψβ(Uα ∩ Uβ).
Note that ψβα maps an open set of Rn to an open set of Rn, so at a point p in Uα ∩ Uβ one can decompose this mapping in terms of coordinates (x1(p), . . . , xn(p)) with respect to Uα and (y1(p), . . . , yn(p)) with respect to Uβ . Two systems of coordinates are linked by: yi(p) = ψβα(x1(p), . . . , xn(p))i.
A transition map and two coordinate systems are represented in Figure 3.1.
This formulation is convenient as it allows us to use standard differential calculus in Rn to study the properties of a curved surface. In particular the Jacobian matrix of ψβα will appear in coordinate change for vector fields (Section 3.1.3).
The charts introduce a local structure on the manifold. However, to have a differential manifold we need to ensure that the local properties are consistent among themselves.
Definition 3.1.1 A topological manifold M equipped with an atlas S = (Uα, ψα) is called differential manifold if all its coordinate changes ψβα are C∞ maps.

Tangent Vectors and Local Coordinates

Tangent vectors are a first step to introduce local intrinsic structure on a manifold. Let f : M → R be a real valued function on a differential manifold. If, for all coordinate systems (U, ψ) in an atlas, f ◦ ψ−1 : ψ(U ) ⊂ Rn → R is a C∞ function on ψ(U ) then f is by definition a C∞ function on M .
Now let (U, ψ) be a coordinate system around a point p ∈ M and (x1, . . . , xn) the coordinate functions with respect to U . The derivative of f in the direction xi denoted ∂if is naturally defined as:
∂if = ∂(f ◦ ψ−1) ◦ ψ ∈ C∞(M ). ∂xi
In case of a surface in R3, the gradient of a function is tangent to this surface. Moreover, the set of all possible directions for function derivatives defines the set of all tangent vectors. By analogy, the application Vp : C∞(M ) → R acting on differentiable functions at point p ∈ M : Vp(f ) = Vi(p)∂if |p, (3.1) is understood as a vector tangent to the manifold. The local coordinates of the vector Vi(p) ∈ R depend on the chart (U, ψ) and correspond to the derivative in the canonical directions ∂ . We denote TpM , the set of all tangent vectors at point p, defined as ∂xi the set of all linear combinations of the basis ∂ . The canonical basis satisfies the ∂xi p i property ∂xj = δij . ∂xi
A vector field on M is a smooth assignment of a tangent vectors Vp ∈ TpM at each point p. Namely V is a C∞ vector field if:
V (f ) ∈ C∞(M ), ∀f ∈ C∞(M ).
We denote the set of smooth vector fields V(M ).

Mappings

Along this thesis we will study relations between manifolds through mappings. Let M and N be two differential manifolds, ϕ : N → M is a map between them. Since the map is not real-valued we have to take into account the parametrizations from M and N to introduce a differential structure.
Definition 3.1.2 The map ϕ : N → M is a C∞ map if for all charts (U, ψ) on N and (V, ϑ) on M , the functions ϑ ◦ ϕ ◦ ψ−1 : Rn → Rn are of class C∞(Rn).
Local coordinate systems (x1(p), . . . , xn(p)) around p ∈ N and (y1(ϕ(p)), . . . , yn(ϕ(p))) around q = ϕ(p) ∈ M are linked by the mapping ϕ: yi(ϕ(p)) = ϑ ◦ ϕ ◦ ψ−1(x1(p), . . . , xn(p))i. (3.2)
C∞ map not only describes pointwise correspondences but also map tangent vectors from one surface to another. The distortion of a tangent space is determined by the Jacobian of the mapping dϕp.
Using the chain rules for derivatives, Equation (3.2) yields a change of coordinates formula or pushforward of tangent vector fields: dϕp ∂ = n ∂yj ∂ , (3.3)
where dϕ denote the differential map or Jacobian of the transformation. Therefore, a map not only relates points but also tangent spaces. The differential map defines a linear mapping between the tangent space on N at point p and the tangent space on M at point ϕ(p):
dϕp : TpN → Tϕ(p)M.
Categories of mappings
Mappings are categorized according to the properties of the differential map:
• Immersion: At each point p ∈ N the Jacobian is injective. It implies that the image of the manifold ϕ(N ) can intersect itself so it may not be a submanifold of M .
• Embedding: ϕ is immersion and also a homeomorphism from N onto ϕ(N ). In this case no self-intersection can occur and the image ϕ(N ) is a submanifold of M .
• Diffeomorphism: ϕ : N → M is a bijection and its inverse ϕ−1 : M → N is a C∞ map. These requirements are stronger than for embeddings, in particular it implies that the Jacobian is bijective and that N, M have the same intrinsic dimension.

Riemannian Manifold

Metric tensor
The metric tensor extends the notion of scalar product in Rn to tangent vectors. It is important to recall that general metric tensors can be arbitrarily chosen and are not necessarily induced by the embedding of a surface. The choice of the metric determines the specifying of the tangent plane, thus, specifying distances on the manifold and many differential operators.
Definition 3.1.3 A Riemannian metric is a family of bilinear forms defined at each point p of the differential manifold M by: gp : TpM × TpM → R.
As Euclidean scalar products the metric should be symmetric, positive definite at each point. Moreover, a Riemannian metric varies smoothly on the manifold: for all differentiable vector fields V, U on M , p gp(Vp, Up) is a smooth function from M to R.
Given a system of local coordinates (x1, . . . , xn) around p, the set ∂ ,…, ∂
a basis of the tangent space TpM . So, the metric can be written as a matrix of Rn×n: gij (p) := gp ∂ , ∂ .
Thus, the metric tensor can be interpreted as a Gramian matrix of tangent vectors. Geometrically the square root of the determinant is the volume of the parallelotope defined by the basis ∂x∂i . Therefore, the quantity det(g) can be understood as a local volume or area on the manifold.
Given two tangent vectors V, U ∈ TpM their scalar product is computed as a usual bilinear form within the coordinate system: gp(V, U ) = Vigij Uj .
An important example that will be frequently used in this thesis is the case where M is an embedded surface of R3. In this configuration, the ambient Euclidean scalar product ., . naturally induces a metric on the surface. Given a chart (U, ψ) in the neighborhood of p ∈ M , the mapping F = ψ−1 : ψ(U ) ⊂ R2 → U ⊂ M ⊂ R3 maps an open subset of R2 to an open subset of R3. Therefore ∂F (p) is a vector of R3 tangent to the surface at ∂xi p and can be identified with a basis of TpM . The induced metric in this basis is: gij (p) = ∂F (p), ∂F (p) . (3.4) ∂xi ∂xj
Many local coordinates expressions can be replaced by vectors in the ambient space.
For instance the scalar product g(V, U ) can be replaced by ¯ ¯ ¯ is the tangent V , U where V
vector V expressed in the global coordinate system. To avoid heavy notations we will consider the change of coordinates implicit when using the ambient scalar product.
Geodesic distance
The metric is a local quantity determining lengths of vectors. It induces a global structure on the manifold enabling us to measure distances between points. The geodesic distance is defined as the shortest path between two points on a manifold.
The application c : [0, 1] → M is a parametrized curve on M . Its velocity c′ is a tangent vector whose length can be computed with the metric g. The arc length L(c) of the curve c is defined by similarity with the Euclidean case: L(c) := gc(t)(c′(t), c′(t))dt.
The geodesic distance d : M × M → [0, +∞) is the minimum over all curves on M : d(p, q) := min L(c)
subject to c(0) = p, c(1) = q. c:[0,1]→M
Figure 3.2 shows an example of geodesic distance field on a surface.
Figure 3.2 – Isolines of the geodesic distance, computed with the spectral method [34].
The pullback metric
The pullback metric is a key tool for analyzing metric distortion. Namely, given an immersion ϕ : N → M between the differential manifolds M and N , we are able to express gM , the metric tensor on M , as a distorted metric on N . This new tensor encodes the distortion of the tangent space by the underlying deformation ϕ.
Definition 3.1.4 The pullback of a metric on M , denoted ϕ⋆gM , is defined as the action of the tensor on the pushforward tangent vectors: (ϕ⋆gM )p(V, U ) = gϕM(p)(dϕ(V ), dϕ(U )), ∀V, U ∈ TpN.
Given a coordinate system, Equation (3.3) leads to a local expression of the pullback metric:
⋆ M ∂yk M ∂yl (ϕ g )ij (p) = gkl (ϕ(p)) . ∂xi ∂xj
The Jacobian of the immersion distorts the bilinear form in a symmetric way. If ϕ is an immersion, the tensor ϕ⋆gM is a metric on N .
Three types of mappings are defined according to the intrinsic properties they preserve (local areas, angles, geodesic distances). Figure 3.3 shows examples of deformation of the plane.
• Area preserving map. A diffeomorphism is said to be area preserving if local areas are preserved:
det(ϕ⋆gM )p = det(gN )p, ∀p ∈ N.
• Conformal map. A diffeomorphism ϕ : N → M is said to be conformal if there exists a positive function h ∈ C∞(M ), sometimes called the conformal factor, such that:
h(q)(ϕ⋆gM )p = gpN ∀p ∈ N.
Such deformations preserve angles between curves but affect local areas. A classical example of such deformation are the Möbius transformations which span all the bijective conformal maps from the sphere to itself.
• Isometry. A conformal and area preserving diffeomorphism is an isometry. In this case, the pullback metric agrees with the metric on N : (ϕ⋆gM )p = gpN ∀p ∈ N.
A map is an isometry if and only if geodesic distances are preserved, namely dM (ϕ(p), ϕ(q)) = dN (p, q), as proven by the Myers–Steenrod theorem [83].
(a) Initial grid (b) Area-preserving (c) Conformal (d) Isometry
Figure 3.3 – Three categories of mapping according to the intrinsic property they preserve.

Integral on Manifold

Area preserving maps are naturally related to integral on manifold. In fact, a change of variables in integral is equivalent to using the measure induced by the pullback metric [78].
Volume form
First, we introduce the volume form dµG defined locally by: dµG = det(g) dx1 • • • dxn.
The volume form induces a Borel measure µG: µG(U ) = dµG, ∀U ⊂ M.
Note that µ will abusively stand for the local area det(g) instead of the measure.
Given a chart (Uα, ψα) and a coordinate system (x1, . . . , xn) the integral is then defined through its mapping to the Euclidean space: f (p) dµG(p) = (f det(g)) ◦ ψα−1(x1, . . . , xn) dx1 . . . dxn.
Uα ψα(Uα)
Pushforward measure
Let ϕ : N → M be a diffeomorphism between two manifolds and gN a metric on N . The pushforward measure ϕ⋆µGN is a measure on M standing for the change of variables: f d(ϕ⋆µGN ) := f ◦ ϕ dµGN Applying the change of coordinate formula for volume form [78] leads to Proposition 3.1.5.
Proposition 3.1.5 The volume form induced by the pushforward measure is the volume form corresponding to the pullback metric:
d(ϕ⋆µGN ) = dµ(ϕ−1)⋆GN .
When ϕ is area preserving, integrals are left untouched by a change of variables: f dµGM = f ◦ ϕ dµGN , ∀f integrable.
Inner product
Let f, g : M → R be smooth functions on M . The space of square integrable functions with respect to the volume form dµG is defined as: L2(M, g) = f : M → R integrable : M f 2 dµG < ∞ .
This space is equipped with the inner product f, g (M,2 G) := M fg dµG inducing the 1 L (M,G) (M,G) 2 norm f L2 := f, f L2 . Mention of the metric and the manifold is sometimes omitted to avoid heavy notation

Gradient, Divergence and Laplacian

Gradient, divergence and Laplacian are three fundamental differential operators to study intrinsic geometry. Their definitions entirely rely on the underlying metric tensor. Moreover, as we will see later, they also fully specify the metric structure of the manifold. For this reason, the Laplacian is a key tool in geometry processing and computer graphics.
In particular it has been used for: fairing and compression (e.g. [59]), geodesic computation (e.g. [34]) and global descriptors (e.g. [99, 119, 5]) to name just few applications. Two properties explain this success: its invariance under isometric deformation and its eigenfunctions comparable to a Fourier basis on manifolds.
For a more comprehensive study of the Laplace-Beltrami operator in differential geometry we refer the interested reader to [103].

Table of contents :

1 Introduction
2 Introduction en français
3 Context in Differential Geometry and its Discrete Equivalents
3.1 Differential Geometry
3.1.1 Manifold
3.1.2 Tangent Vectors and Local Coordinates
3.1.3 Mappings
3.1.4 Riemannian Manifold
3.1.5 Integral on Manifold
3.1.6 Gradient, Divergence and Laplacian
3.2 Discretization
3.2.1 Discrete Manifold
3.2.2 Finite Element Method and Cotangent Weight Formula
3.2.3 Discrete Local Coordinates
4 Operator Representation 
4.1 Functional Map
4.1.1 Mathematical Properties
4.1.2 Discrete Functional Maps
4.2 Shape Differences
4.2.1 Definition
4.2.2 Fundamental Properties
4.2.3 Algebraic Properties
4.2.4 Discrete Shape Differences
4.3 Organization of the Thesis
I Shape to Deformation
5 Supervised Descriptor Learning for Non-Rigid Shape Matching
5.1 Introduction
5.1.1 Related Work
5.2 Consistent Functional Maps
5.2.1 Functional Map Representation
5.2.2 Main Challenge
5.2.3 Algorithm Outline
5.3 Selection of the Best Functional Correspondences
5.3.1 Weighting the probe functions
5.3.2 Finding the best weights
5.4 Basis function extraction
5.4.1 Identifying stable subspaces
5.4.2 Functional map to a test shape using a reduced basis
5.5 Experimental Results
5.5.1 Functional correspondences
5.5.2 Isometric Shape Matching
5.5.3 Non-Isometric Shape Matching
5.6 Conclusion
6 Continuous Matching via Vector Field Flow
6.1 Introduction
6.2 Related Work
6.3 Functional Maps Conversion
6.3.1 Main Challenges
6.3.2 Algorithm Overview
6.4 Family of Diffeomorphisms
6.5 Optimal vector field
6.5.1 Optimization Problem
6.5.2 Properties
6.5.3 Practical Choice of the Norm
6.6 Vector Field Flow on Manifold
6.7 Results
6.7.1 Symmetry Blending
6.7.2 Error using a computed functional map
6.7.3 Parameters Dependence
6.7.4 Performance
6.8 Conclusion, Limitations and Future Work
II Deformation to Shape
7 Functional Characterization of Intrinsic and Extrinsic Geometry
7.1 Introduction
7.2 Related Work
7.3 Overview
7.4 Structure of Discrete Inner Products
7.4.1 Discrete Inner Products
7.5 Encoding Extrinsic Structure
7.5.1 Extrinsic Alternatives
7.5.2 Offset Surfaces
7.5.3 Recovery of Embedding
7.5.4 Discussion
7.6 From Inner Products to Shape Differences
7.6.1 Discrete Shape Differences
7.6.2 Source-Truncated Correspondence
7.6.3 Source- and Target-Truncated Correspondence
7.7 Recovery of Intrinsic and Extrinsic Structure
7.7.1 Triangle Area Computation
7.7.2 Edge Length Computation
7.7.3 Global Extrinsic Reconstruction
7.8 Experiments
7.8.1 Shape Space
7.8.2 Effects of Truncation
7.8.3 Intrinsic Recovery
7.8.4 Reconstruction
7.8.5 Timings
7.9 Discussion & Conclusion
8 Functional Characterization of Deformation Fields
8.1 Introduction
8.2 Related Work
8.3 Overview
8.4 Extrinsic Vector Fields as Operators
8.4.1 Isometric Shape Difference Operator
8.4.2 Infinitesimal Deformations as Operators
8.4.3 Main Properties of Infinitesimal Shape Differences
8.5 Discrete Setting
8.5.1 Discrete unified shape difference
8.5.2 Infinitesimal shape difference
8.5.3 Properties
8.6 Representation in basis
8.6.1 Basis for the Function Space
8.6.2 Vector field basis
8.7 Experiments
8.7.1 Deformation transfer
8.7.2 Functional map inference
8.8 Conclusion and Future Work
9 Conclusion
Bibliography

GET THE COMPLETE PROJECT