Least squares model for visual element selection and matching

Get Complete Project Material File(s) Now! »

Spectral signatures

In most cases, one can recover all the intrinsic information about a shape using the eigen-values and eigen-functions of the Laplace-Beltrami operator on the shape [97]. These eigen-functions are the generalization of the Fourier basis on general manifolds. They are closely related to several physical phenomena, including vibration modes, which are shown figure 3.2. The two most important spectral signatures, the Global Point Signature (GPS) and Heat Kernel Signature (HKS) are presented in this section. The Wave kernel Signature (WKS), presented in chapter 3 falls into the same category of spectral descriptors. Section 3.1.3 presents in more detail the mathematical aspects of spectral shape analysis.
Global Point signature (GPS): The first spectral point signature was developed by Rustamov [148]. To each point of a shape, the Global Point Signature associates a vector. Its kth component is the value of the kth eigen-function at the described point divided by the square root of the norm of kth eigen-value. This division gives more importance to the eigen-vectors associated to the low frequencies. The main drawback of the GPS is that if a shape is slightly modified, the order of the eigen-functions may be changed, resulting in two completely diﬀerent signatures.
Heat Kernel Signature (HKS): The Heat Kernel Signature [168] is widely con-sidered the state of the art shape signature. Similar to the GPS it is defined using the eigen-decomposition of the Laplace-Beltrami operator on the shape. However the HKS does not separate the eigen-functions but combines them in a way that naturally arises from the analysis of heat diﬀusion on the shape surface. A particular value of the HKS for several shapes is visualized on figure 2.4. More technical details about the HKS are given in 3.1.3.2. There have been several extensions of the HKS. In partic-ular, Bronstein et al. [37] modified HKS to be scale invariant and Raviv et al. [142] considered the heat diﬀusion in the shape volume rather than on its surface, defining a volumetric HKS.
Wave Kernel Signature (WKS): The Heat Kernel Signature presented in chapter 3 extends the idea of combining the eigen-function introduced in HKS. Using a pertur-bation analysis of the eigen-values of the Laplace-Beltrami operator, it combines them in a way that is optimal under some hypothesis. The WKS improves the precision of 3D shape matching is the problem of finding a point to point correspondence between two diﬀerent shapes. There are two main approaches to tackle this problem. The one most related to this thesis is to define for each point a descriptor that will be discriminative but also robust to some transformations of the shape and then find a matching that preserves L2 distance between the descriptors. Another popular strategy is to minimize the distortion induced by the mapping. This section gives an overview of those approaches. For a more detailed survey the reader can refer to [171] and [173].

Metric approaches

Iterative closest point methods were the first introduced to solve rigid 3D shape match-ing [29, 41]. They were later extended to cope with some non-rigid deformations [8] by iteratively rigidly aligning the shapes and deforming them using a non-rigid parametric transformation. This idea however can only work with limited deformations in terms of Euclidean distance in the 3D space.
For shape matching, the intrinsic properties of the shape, such as geodesic distances, are more meaningful. Indeed they are mostly preserved under usual deformations. For example, the geodesic distance between the two hands of a human body will remain approximately the same even if their distance in the 3D space changes a lot. This leads to the idea of viewing the shapes as metric spaces and the problem of aligning them as finding an isometry that minimize the distance between those spaces. If the distance used is the Euclidean distance in the ambient 3D space the natural distance between the shapes is the Hausdorﬀ distance in the Euclidean 3D space and the standard ICP algorithm can be used to find a locally optimal alignment. However other distances such as the geodesic distance are more meaningful.
Using the geodesic or diﬀusion distance on the shapes makes the problem of finding an optimal isometry much harder. The first challenge is to find a metric space in which the two shapes can be meaningfully compared. Elad et al. [57] embed the shapes in a nearly isometric way in a finite dimension Euclidean space using multidimensional scaling (MDS) [46]. They then perform ICP in this new space and thus recover corre-spondences between the initial shapes. However, in [57] the metric space toward which the embedding is done and in which the Hausdorﬀ distance is minimized is selected in an arbitrary way. Memoli and Sapiro [125] solve this problem by applying to 3D shape analysis the ideas of the Gromov-Hausdorﬀ distance [78]. They compare the shapes us-ing their isometric embedding in a metric space that minimizes the Hausdorﬀ distance between them. This idea was further developed for shape matching using geodesic [36] and diﬀusion distances [35].
Windheuser et al. [177] use a related approach and find a deformation minimizing the elastic energy cost of the deformation rather than the Gromov-Hausdorﬀ distance. Their formulation has the advantage that it leads to a binary linear program that can be eﬃciently solved.

READ Eleven steps to a gender equal recruitment process

Feature-based approaches

Inspired by the success of feature based methods in 2D alignment, many papers have used local descriptors to match shapes. For example Gelfand et al.[72] use putative correspondences of points with very discriminative features to propose candidate rigid transformations and each transformation is then evaluated. The best transformation is then used as an initialization to an ICP algorithm. Similarly Brown and Rusinkiewicz [38] use local feature correspondences to initiate their non-rigid ICP.

Table of contents :

1 Introduction
1.1 Goals
1.2 Motivation
1.3 Challenges
1.3.1 3D local descriptors
1.3.2 Instance-level 2D-3D alignment
1.3.3 Category-level 2D-3D object recognition
1.4 Contributions
1.4.1 Wave Kernel Signature
1.4.2 3D discriminative visual elements
1.5 Thesis outline
1.6 Publications
2 Background
2.1 3D shape analysis
2.1.1 From the ideal shapes to discrete 3D models
2.1.2 3D point descriptors
2.1.3 3D shape alignment methods
2.2 Instance-level 2D-3D alignment
2.2.1 Contour-based methods
2.2.2 Local features for alignment
2.2.3 Global features for alignment
2.2.4 Relationship to our method
2.3 Category-level 2D-3D alignment
2.3.1 2D methods
2.3.2 3D methods
2.3.3 Relationship to our method
3 Wave Kernel Signature
3.1 Introduction
3.1.1 Motivation
3.1.2 From Quantum Mechanics to shape analysis
3.1.3 Spectral Methods for shape analysis
3.2 The Wave Kernel Signature
3.2.1 From heat diffusion to Quantum Mechanics
3.2.2 Schr¨odinger equation on a surface
3.2.3 A spectral signature for shapes
3.2.4 Global vs. local WKS
3.3 Mathematical Analysis of the WKS
3.3.1 Stability analysis
3.3.2 Spectral analysis
3.3.3 Invariance and discrimination
3.4 Experimental Results
3.4.1 Qualitative analysis
3.4.2 Quantitative evaluation
3.5 Applications
3.6 Conclusion
4 Painting-to-3D Alignment
4.1 Introduction
4.1.1 Motivation
4.1.2 From locally invariant to discriminatively trained features
4.1.3 Overview
4.2 3D discriminative visual elements
4.2.1 Learning 3D discriminative visual elements
4.2.2 Matching as classification
4.3 Discriminative visual elements for painting-to-3D alignment
4.3.1 View selection and representation
4.3.2 Least squares model for visual element selection and matching
4.3.3 Calibrated discriminative matching
4.3.4 Filtering elements unstable across viewpoint
4.3.5 Robust matching
4.3.6 Recovering viewpoint
4.3.7 Summary
4.4 Results and validation
4.4.1 Dataset for painting-to-3D alignment
4.4.2 Qualitative results
4.4.3 Quantitative evaluation
4.4.4 Algorithm analysis
4.5 Conclusion
5 Seeing 3D Chairs
5.1 Introduction
5.1.1 Motivation
5.1.2 From instance-level to category-level alignment
5.1.3 Approach Overview
5.2 Discriminative visual elements for category-level 3D-2D alignment
5.2.1 Representing a 3D shape collection
5.2.2 Calibrating visual element detectors
5.2.3 Matching spatial configurations of visual elements
5.3 Experiments and results
5.3.1 Large dataset of 3D chairs
5.3.2 Qualitative results
5.3.3 Quantitative evaluation
5.3.4 Algorithm analysis
5.4 Conclusion
6 Discusion
6.1 Contributions
6.2 Future work
6.2.1 Anisotropic Laplace-Beltrami operators
6.2.2 Object compositing
6.2.3 Use of 3D shape collection analysis
6.2.4 Synthetic data for deep convolutional network training
6.2.5 Exemplar based approach with CNN features