Non-rigid correspondences between surfaces embedded in 3D

Surface

Continuous setting In the continuous setting, a surface M will be represented as a 2D manifold embedded in 3D. This means that M is a subset of R3 such that for each x ∈ M there exists an open subset of M, Ux, and a smooth map mx : Ux → R2 such that mx is a diffeomorphism between Ux and an open set of R2 [34]. The degree of smoothness that applies to all the maps mx and m−1x defines the degree of smoothness of the manifold M. For simplicity, we typically assume smooth manifolds, for which all diffeomorphisms involved are infinitely differentiable.
Discrete setting In the discrete setting a continuous surface may be approximated using a point cloud, where each point is represented using three floating point coordinates in practice. In addition the point cloud is often converted to a triangular mesh, see for example [79] for a survey on algorithms that perform this conversion. In order to obtain a triangular mesh, the point cloud should be equipped with a set of triangles that covers the point cloud. Each endpoint of a triangle has to be a point of the point cloud, and a good triangulation should be such that the triangles follow the original surface. For instance, the normal of these triangles should closely match the normals of the represented surface at points that shown in red are near the triangle. A triangulation will be stored as a finite set of triplets of integers (i, j, k), where i, j and k are the respective indices of the points in the point cloud that correspond to the endpoints of the triangle. In addition we will often assume that our triangle meshes should be connected, manifold and possibly without boundary. For the triangle mesh to be manifold, all edges should be adjacent to at most two triangles (exactly two if we do not allow boundaries). For each vertex we should be able to order its adjacent triangles in a cycle of triangles that share exactly one edge, and all triangles adjacent to a given vertex should not intersect anywhere else than at the shared edge, as discussed in [16]. In my thesis each surface will be represented as a triangle mesh, I will not work directly on point clouds.

Goal

   As mentionned in the previous chapter, our goal is to study problems related to finding correspondences and relations between items in 3D. An item in 3D is represented by its surface, that may have been scanned using recent technological tools such as Microsoft Kinect or a CT scan. After scanning the surface we get a triangle mesh, for example using surface reconstruction techniques mentionned above. We consider two items that can naturally be mapped to each other. This means that each part of one item has a meaningfully corresponding part on the other. Our main problem consists in finding, for each vertex of one item, the best corresponding vertex on the other. For example if one of the surface represents a sitting cat and another represents a standing cat, then a good solution should be a correspondence that maps the tip of the left paw of the sitting cat to the tip of the left paw of the standing cat, the nose of the sitting cat to the nose of the standing cat, etc. We measure our error using geodesic distances: a good correspondence will preserve geodesic distances as well as possible. Theoretically it is possible to exactly preserve geodesic distances if and only if the shapes are isometric (we mean non-rigid isometry). Ideally our method should be as general as possible. For example we should also be able to find a correspondence between a cat and a dog, since both animals have similar body parts: four legs, a head, a tail, etc. Pushing this idea further, we may want to find (at least partial) correspondences between a cat and a human for instance. There are multiple reasons why we may be interested in finding such a correspondence. Shape matching has a wide range of applications ranging fr

Changing the dimension of the reduced space

  In our second range of experiments, we show the dependence of the results on the number of functions used in the basis for functional maps. Here, rather than changing the number of descriptor functions, we fix the descriptor set and change the dimensionality of the basis and evaluate the quality of the approximation of the point-to-point correspondences using the functional map pipeline. In Figure 2.4 we show the average correspondence error between a subset of shapes in the FAUST dataset [13], using the same pipeline described in the previous section, for a fixed number (in this case two) of descriptor functions. In particular, we used the Wave Kernel Signature for a single energy value, along with a single descriptor function that is aimed at segment preservation using the Wave Kernel Map with a fixed energy value. This gives us two descriptor functions, which we incorporate into the functional map energy using either the standard descriptor preservation constraints, as done in [69] or using our commutativity-based approach. We then convert the estimated functional map to a point-to-point correspondence and evaluate its accuracy using the distance to the ground truth. We plot the average pointwise map error, computed the same way as in the previous experiment, across the shape pairs for a varying number of basis functions.

Function approximation and transfer

   In our first application, we evaluate the utility of our function transfer procedure using both ground truth (arising from known pointwise maps) and computed functional maps. Namely, given a set of pairs of (source, target) shapes and a collection of different functions on each source, we evaluate: i) the approximation of each function on the source shape, and ii) the transfer of a function between the source and the target shape. Figure 3.7 shows a qualitative example of approximation and transfer of a real-valued function, with the original function shown on the left. This function is generated as a combination of an indicator function (on the left leg) a gaussian around a point (top of the right leg) a sine function of the y coordinate (on the tail) and a continuously increasing function (on the ears). We compare the standard approach (std) vs. our extended method (prod), for both function approximation and transfer onto a different pose of the same shape.

HKS and WKS approximation and transfer

   One interesting observation related to our method is that both the Heat Kernel Signature and the Wave Kernel Signature functions are of the form ht(x, x) = PkMi=1 αiφ2i(x), for some scalar coefficients αi. In other words, they are constructed explicitly using squares of eigenfunctions and therefore it must be possible to represent and transfer them exactly in our extended basis. Therefore, they provide a good test for the correctness of both our extended function approximation and transfer methods. To demonstrate the difference between the transfer of these functions using the standard and the extended basis we show in Figure 3.11 the transfer error using the ground truth functional map of size kN × kM for increasing kN . Note that for large values of kN we can approximate the transfer of all kM basis functions from the source well, which means that we would expect our extended transfer method to produce progressively better results.

Table des matières

1 Introduction to non-rigid shape matching 
1.1 Surface
1.1.1 Continuous setting
1.1.2 Discrete setting
1.1.3 Discretization of a function and its gradient
1.1.4 Area weights
1.2 Laplace-Beltrami operator
1.2.1 Continuous setting
1.2.2 Discrete setting
1.3 Goal
1.4 Related work 
1.5 Partial correspondences
1.6 Overview of the Functional Maps Framework 
1.6.1 Setup
1.7 Definitions and Notations 
2 Informative descriptor preservation via commutativity for shape matching 
2.1 Introduction 
2.2 Related work 
2.3 Overview 
2.4 Novel Approach for Functional Correspondences 
2.4.1 Motivation
2.4.2 Our constraints
2.4.3 Properties
2.5 Experiments
2.5.1 Using few descriptors
2.5.2 Changing the dimension of the reduced space
2.6 Conclusion, Limitations & Future work
3 Improved functional mappings via product preservation 
3.1 Introduction
3.2 Related Work
3.3 Motivation and Overview
3.4 Method Description 
3.4.1 Function Representation
3.4.2 Extended Functional Basis
3.4.3 Extended Function Transfer
3.4.4 Function Comparison and Pointwise Map Recovery
3.5 Results
3.5.1 Function approximation and transfer
3.5.2 HKS and WKS approximation and transfer
3.5.3 Point-to-point map recovery
3.5.4 Joint quadrangulation
3.6 Conclusion, Limitations and Future Work 
3.7 Appendix 
3.7.1 Additional Results
3.7.2 Proof of Lemma 2
3.7.3 Proof of Theorem 3.4.1
3.7.4 Future work
4 Deep learning for non linear function approximation and mapping 
4.1 Introduction
4.2 Related Work 
4.3 Background 
4.4 Main Idea 
4.5 Description 
4.6 Parameters
4.7 Results 
4.8 Conclusion
4.9 Future work
5 Miscellaneous 
5.1 A new analysis method for evolutionary optimization of dynamic and noisy objective functions 
5.2 On semiring complexity of Schur polynomials 
5.2.1 Schur polynomial
5.2.2 Main result
5.3 Scheduling with gaps: New models and algorithms
6 General Conclusion 
6.1 Summary
6.2 Future work
6.3 Position of the work in the community 
Bibliography

Télécharger le rapport complet