A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of 'shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model, prior to shape inspection. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces. > <s> BIB001 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> We study the problem of creating a complete model of a physical object. Although this may be possible using intensity images, we here use images which directly provide access to three dimensional information. The first problem that we need to solve is to find the transformation between the different views. Previous approaches either assume this transformation to be known (which is extremely difficult for a complete model), or compute it with feature matching (which is not accurate enough for integration). In this paper, we propose a new approach which works on range data directly and registers successive views with enough overlapping area to get an accurate transformation between views. This is performed by minimizing a functional which does not require point-to-point matches. We give the details of the registration method and modelling procedure and illustrate them on real range images of complex objects. <s> BIB002 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> In this paper, we propose a new method, the RANSAC-based DARCES method (data-aligned rigidity-constrained exhaustive search based on random sample consensus), which can solve the partially overlapping 3D registration problem without any initial estimation. For the noiseless case, the basic algorithm of our method can guarantee that the solution it finds is the true one, and its time complexity can be shown to be relatively low. An extra characteristic is that our method can be used even for the case that there are no local features in the 3D data sets. <s> BIB003 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> We present a 3D shape-based object recognition system for simultaneous recognition of multiple objects in scenes containing clutter and occlusion. Recognition is based on matching surfaces by matching points using the spin image representation. The spin image is a data level shape descriptor that is used to match surfaces represented as surface meshes. We present a compression scheme for spin images that results in efficient multiple object recognition which we verify with results showing the simultaneous recognition of multiple objects from a library of 20 models. Furthermore, we demonstrate the robust performance of recognition in the presence of clutter and occlusion through analysis of recognition trials on 100 scenes. <s> BIB004 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> The ICP (Iterative Closest Point) algorithm is widely used for geometric alignment of three-dimensional models when an initial estimate of the relative pose is known. Many variants of ICP have been proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy. We enumerate and classify many of these variants, and evaluate their effect on the speed with which the correct alignment is reached. In order to improve convergence for nearly-flat meshes with small features, such as inscribed surfaces, we introduce a new variant based on uniform sampling of the space of normals. We conclude by proposing a combination of ICP variants optimized for high speed. We demonstrate an implementation that is able to align two range images in a few tens of milliseconds, assuming a good initial guess. This capability has potential application to real-time 3D model acquisition and model-based tracking. <s> BIB005 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Measuring the similarity between 3D shapes is a fundamental problem, with applications in computer graphics, computer vision, molecular biology, and a variety of other fields. A challenging aspect of this problem is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes.In this paper, we propose and analyze a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as a shape distribution sampled from a shape function measuring global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence, or model fitting.We find that the dissimilarities between sampled distributions of simple shape functions (e.g., the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g., cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, mirrors, tessellations, simplifications, and model degeneracies. They can be evaluated quickly, and thus the proposed method could be applied as a pre-classifier in a complete shape-based retrieval or analysis system concerned with finding similar whole objects. The paper describes our early experiences using shape distributions for object classification and for interactive web-based retrieval of 3D models. <s> BIB006 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> The description of 3D shapes with features that possess descriptive power and invariant under similarity transformations is one of the most challenging issues in content based 3D model retrieval. Spherical harmonics-based descriptors have been proposed for obtaining rotation invariant representations. However, spherical harmonic analysis is based on latitude-longitude parameterization of a sphere which has singularities at each pole. Consequently, features near the two poles are over represented while features at the equator are under-sampled, and variations of the north pole affects significantly the shape function. In this paper we discuss these issues and propose the usage of spherical wavelet transform as a tool for the analysis of 3D shapes represented by functions on the unit sphere. We introduce three new descriptors extracted from the wavelet coefficients, namely: (1) a subset of the spherical wavelet coefficients, (2) the L1 and, (3) the L2 energies of the spherical wavelet sub-bands. The advantage of this tool is three fold; First, it takes into account feature localization and local orientations. Second, the energies of the wavelet transform are rotation invariant. Third, shape features are uniformly represented which makes the descriptors more efficient. Spherical wavelet descriptors are natural extension of 3D Zernike moments and spherical harmonics. We evaluate, on the Princeton Shape Benchmark, the proposed descriptors regarding computational aspects and shape retrieval performance. <s> BIB007 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> An efficient algorithm for isometry-invariant matching of surfaces is presented. The key idea is computing the minimum-distortion mapping between two surfaces. For this purpose, we introduce the generalized multidimensional scaling, a computationally efficient continuous optimization algorithm for finding the least distortion embedding of one surface into another. The generalized multidimensional scaling algorithm allows for both full and partial surface matching. As an example, it is applied to the problem of expression-invariant three-dimensional face recognition. <s> BIB008 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> The description of 3D shapes using features that possess descriptive power and are invariant under similarity transformations is one of the most challenging issues in content-based 3D model retrieval. Spherical harmonics-based descriptors have been proposed for obtaining rotation invariant representations. However, spherical harmonic analysis is based on a latitude-longitude parameterization of the sphere which has singularities at each pole, and therefore, variations of the north pole affect significantly the shape function. In this paper we discuss these issues and propose the usage of spherical wavelet transforms as a tool for the analysis of 3D shapes represented by functions on the unit sphere. We introduce three new descriptors extracted from the wavelet coefficients, namely: (1) a subset of the spherical wavelet coefficients, (2) the L1 and, (3) the L2 energies of the spherical wavelet sub-bands. The advantage of this tool is threefold; First, it takes into account feature localization and local orientations. Second, the energies of the wavelet transform are rotation invariant. Third, shape features are uniformly represented which makes the descriptors more efficient. Spherical wavelet descriptors are natural extensions of spherical harmonics and 3D Zernike moments. We evaluate, on the Princeton Shape Benchmark, the proposed descriptors regarding computational aspects and shape retrieval performance. <s> BIB009 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> We introduce a new framework for the automatic selection of the best views of 3D models based on the assumption that models belonging to the same class of shapes share the same salient features. The main issue is learning these features. We propose an algorithm for computing these features and their corresponding saliency value. At the learning stage, a large set of features are computed from every model and a boosting algorithm is applied to learn the classification function in the feature space. AdaBoost learns a classifier that relies on a small subset of the features with the mean of weak classifiers, and provides an efficient way for feature selection and combination. Moreover it assigns weights to the selected features which we interpret as a measure of the feature saliency within the class. Our experiments using the LightField (LFD) descriptors and the Princeton Shape Benchmark show the suitability of the approach to 3D shape classification and best-view selection for online visual browsing of 3D data collections. <s> BIB010 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> A deformation invariant representation of surfaces, the GPS embedding, is introduced using the eigenvalues and eigenfunctions of the Laplace-Beltrami differential operator. Notably, since the definition of the GPS embedding completely avoids the use of geodesic distances, and is based on objects of global character, the obtained representation is robust to local topology changes. The GPS embedding captures enough information to handle various shape processing tasks as shape classification, segmentation, and correspondence. To demonstrate the practical relevance of the GPS embedding, we introduce a deformation invariant shape descriptor called G2-distributions, and demonstrate their discriminative power, invariance under natural deformations, and robustness. <s> BIB011 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> We introduce 4PCS, a fast and robust alignment scheme for 3D point sets that uses wide bases, which are known to be resilient to noise and outliers. The algorithm allows registering raw noisy data, possibly contaminated with outliers, without pre-filtering or denoising the data. Further, the method significantly reduces the number of trials required to establish a reliable registration between the underlying surfaces in the presence of noise, without any assumptions about starting alignment. Our method is based on a novel technique to extract all coplanar 4-points sets from a 3D point set that are approximately congruent, under rigid transformation, to a given set of coplanar 4-points. This extraction procedure runs in roughly O(n2 + k) time, where n is the number of candidate points and k is the number of reported 4-points sets. In practice, when noise level is low and there is sufficient overlap, using local descriptors the time complexity reduces to O(n + k). We also propose an extension to handle similarity and affine transforms. Our technique achieves an order of magnitude asymptotic acceleration compared to common randomized alignment techniques. We demonstrate the robustness of our algorithm on several sets of multiple range scans with varying degree of noise, outliers, and extent of overlap. <s> BIB012 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> In this paper we investigate on how the choice of similarity measures affects the performance of content-based 3D model retrieval (CB3DR) algorithms. In CB3DR, shape descriptors are used to provide a numerical representation of the salient features of the data, while similarity functions capture the high level semantic concepts. In the first part of the paper, we demonstrate experimentally that the Euclidean distance is not the optimal similarity function for 3D model classification and retrieval. Then, in the second part, we propose to use a supervised learning approach for automatic selection of the optimal similarity measure that achieves the best performance. Our experiments using the Princeton Shape Benchmark (PSB) show significant improvements in the retrieval performance. <s> BIB013 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Non-rigid 3D shape correspondence is a fundamental and difficult problem. Most applications which require a correspondence rely on manually selected markers. Without user assistance, the performances of existing automatic correspondence methods depend strongly on a good initial shape alignment or shape prior, and they generally do not tolerate large shape variations. We present an automatic feature correspondence algorithm capable of handling large, non-rigid shape variations, as well as partial matching. This is made possible by leveraging the power of state-of-the-art mesh deformation techniques and relying on a combinatorial tree traversal for correspondence search. The search is deformation-driven, prioritized by a self-distortion energy measured on meshes deformed according to a given correspondence. We demonstrate the ability of our approach to naturally match shapes which differ in pose, local scale, part decomposition, and geometric detail through numerous examples. <s> BIB014 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Deformable objects are ubiquitous in the world surrounding us, on all levels from micro to macro. The need to study such shapes and model their behavior arises in a wide spectrum of applications, ranging from medicine to security. In recent years, non-rigid shapes have attracted growing interest, which has led to rapid development of the field, where state-of-the-art results from very different sciences - theoretical and numerical geometry, optimization, linear algebra, graph theory, machine learning and computer graphics, to mention several - are applied to find solutions. This book gives an overview of the current state of science in analysis and synthesis of non-rigid shapes. Everyday examples are used to explain concepts and to illustrate different techniques. The presentation unfolds systematically and numerous figures enrich the engaging exposition. Practice problems follow at the end of each chapter, with detailed solutions to selected problems in the appendix. A gallery of colored images enhances the text. This book will be of interest to graduate students, researchers and professionals in different fields of mathematics, computer science and engineering. It may be used for courses in computer vision, numerical geometry and geometric modeling and computer graphics or for self-study. <s> BIB015 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Content-based 3D model retrieval (CB3DMR) aims at augmenting the text-based search with the ability to search 3D data collections by using examples, sketches, as well as geometric and structural features... <s> BIB016 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> We propose a novel point signature based on the properties of the heat diffusion process on a shape. Our signature, called the Heat Kernel Signature (or HKS), is obtained by restricting the well-known heat kernel to the temporal domain. Remarkably we show that under certain mild assumptions, HKS captures all of the information contained in the heat kernel, and characterizes the shape up to isometry. This means that the restriction to the temporal domain, on the one hand, makes HKS much more concise and easily commensurable, while on the other hand, it preserves all of the information about the intrinsic geometry of the shape. In addition, HKS inherits many useful properties from the heat kernel, which means, in particular, that it is stable under perturbations of the shape. Our signature also provides a natural and efficiently computable multi-scale way to capture information about neighborhoods of a given point, which can be extremely useful in many applications. To demonstrate the practical relevance of our signature, we present several methods for non-rigid multi-scale matching based on the HKS and use it to detect repeated structure within the same shape and across a collection of shapes. <s> BIB017 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> In this paper, the problem of non-rigid shape recognition is studied from the perspective of metric geometry. In particular, we explore the applicability of diffusion distances within the Gromov-Hausdorff framework. While the traditionally used geodesic distance exploits the shortest path between points on the surface, the diffusion distance averages all paths connecting the points. The diffusion distance constitutes an intrinsic metric which is robust, in particular, to topological changes. Such changes in the form of shortcuts, holes, and missing data may be a result of natural non-rigid deformations as well as acquisition and representation noise due to inaccurate surface construction. The presentation of the proposed framework is complemented with examples demonstrating that in addition to the relatively low complexity involved in the computation of the diffusion distances between surface points, its recognition and matching performances favorably compare to the classical geodesic distances in the presence of topological changes between the non-rigid shapes. <s> BIB018 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Spectral methods for mesh processing and analysis rely on the eigenvalues, eigenvectors, or eigenspace projections derived from appropriately defined mesh operators to carry out desired tasks. Early work in this area can be traced back to the seminal paper by Taubin in 1995, where spectral analysis of mesh geometry based on a combinatorial Laplacian aids our understanding of the low-pass filtering approach to mesh smoothing. Over the past 15 years, the list of applications in the area of geometry processing which utilize the eigenstructures of a variety of mesh operators in different manners have been growing steadily. Many works presented so far draw parallels from developments in fields such as graph theory, computer vision, machine learning, graph drawing, numerical linear algebra, and high-performance computing. This paper aims to provide a comprehensive survey on the spectral approach, focusing on its power and versatility in solving geometry processing problems and attempting to bridge the gap between relevant research in computer graphics and other fields. Necessary theoretical background is provided. Existing works covered are classified according to different criteria: the operators or eigenstructures employed, application domains, or the dimensionality of the spectral embeddings used. Despite much empirical success, there still remain many open questions pertaining to the spectral approach. These are discussed as we conclude the survey and provide our perspective on possible future research. <s> BIB019 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> In this paper, we propose a new algorithm for pairwise rigid point set registration with unknown point correspondences. The main properties of our method are noise robustness, outlier resistance and global optimal alignment. The problem of registering two point clouds is converted to a minimization of a nonlinear cost function. We propose a new cost function based on an inverse distance kernel that significantly reduces the impact of noise and outliers. In order to achieve a global optimal registration without the need of any initial alignment, we develop a new stochastic approach for global minimization. It is an adaptive sampling method which uses a generalized BSP tree and allows for minimizing nonlinear scalar fields over complex shaped search spaces like, e.g., the space of rotations. We introduce a new technique for a hierarchical decomposition of the rotation space in disjoint equally sized parts called spherical boxes. Furthermore, a procedure for uniform point sampling from spherical boxes is presented. Tests on a variety of point sets show that the proposed registration method performs very well on noisy, outlier corrupted and incomplete data. For comparison, we report how two state-of-the-art registration algorithms perform on the same data sets. <s> BIB020 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> During the last years a wide range of algorithms and devices have been made available to easily acquire range images. The increasing abundance of depth data boosts the need for reliable and unsupervised analysis techniques, spanning from part registration to automated segmentation. In this context, we focus on the recognition of known objects in cluttered and incomplete 3D scans. Locating and fitting a model to a scene are very important tasks in many scenarios such as industrial inspection, scene understanding, medical imaging and even gaming. For this reason, these problems have been addressed extensively in the literature. Several of the proposed methods adopt local descriptor-based approaches, while a number of hurdles still hinder the use of global techniques. In this paper we offer a different perspective on the topic: We adopt an evolutionary selection algorithm that seeks global agreement among surface points, while operating at a local level. The approach effectively extends the scope of local descriptors by actively selecting correspondences that satisfy global consistency constraints, allowing us to attack a more challenging scenario where model and scene have different, unknown scales. This leads to a novel and very effective pipeline for 3D object recognition, which is validated with an extensive set of experiments and comparisons with recent techniques at the state of the art. <s> BIB021 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> During the last decade, a significant attention has been paid, by the computer vision and the computer graphics communities, to three dimensional (3D) object retrieval. Shape retrieval methods can be divided into three main steps: the shape descriptors extraction, the shape signatures and their associated similarity measures, and the machine learning relevance functions. While the first and the last points have vastly been addressed in recent years, in this paper, we focus on the second point; presenting a new 3D object retrieval method using a new coding/pooling technique and powerful 3D shape descriptors extracted from 2D views. For a given 3D shape, the approach extracts a very large and dense set of local descriptors. From these descriptors, we build a new shape signature by aggregating tensor products of visual descriptors. The similarity between 3D models can then be efficiently computed with a simple dot product. We further improve the compactness and discrimination power of the descriptor using local Principal Component Analysis on each cluster of descriptors. Experiments on the SHREC 2012 and the McGill benchmarks show that our approach outperforms the state-of-the-art techniques, including other BoF methods, both in compactness of the representation and in the retrieval performance. <s> BIB022 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> 3D object recognition in cluttered scenes is a rapidly growing research area. Based on the used types of features, 3D object recognition methods can broadly be divided into two categories-global or local feature based methods. Intensive research has been done on local surface feature based methods as they are more robust to occlusion and clutter which are frequently present in a real-world scene. This paper presents a comprehensive survey of existing local surface feature based 3D object recognition methods. These methods generally comprise three phases: 3D keypoint detection, local surface feature description, and surface matching. This paper covers an extensive literature survey of each phase of the process. It also enlists a number of popular and contemporary databases together with their relevant attributes. <s> BIB023 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Data acquisition in large-scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state-of-the-art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present Super 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an 'instance problem' and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory-efficient, and fast. We demonstrate that Super 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/. <s> BIB024 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> Several descriptors have been proposed in the past for 3D shape analysis, yet none of them achieves best performance on all shape classes. In this paper we propose a novel method for 3D shape analysis using the covariance matrices of the descriptors rather than the descriptors themselves. Covariance matrices enable efficient fusion of different types of features and modalities. They capture, using the same representation, not only the geometric and the spatial properties of a shape region but also the correlation of these properties within the region. Covariance matrices, however, lie on the manifold of Symmetric Positive Definite (SPD) tensors, a special type of Riemannian manifolds, which makes comparison and clustering of such matrices challenging. In this paper we study covariance matrices in their native space and make use of geodesic distances on the manifold as a dissimilarity measure. We demonstrate the performance of this metric on 3D face matching and recognition tasks. We then generalize the Bag of Features paradigm, originally designed in Euclidean spaces, to the Riemannian manifold of SPD matrices. We propose a new clustering procedure that takes into account the geometry of the Riemannian manifold. We evaluate the performance of the proposed Bag of Covariance Matrices framework on 3D shape matching and retrieval applications and demonstrate its superiority compared to descriptor-based techniques. <s> BIB025 </s> A Survey on Non-rigid 3D Shape Analysis <s> Landmark-based elastic registration <s> State-of-the-art 3D shape classification and retrieval algorithms, hereinafter referred to as shape analysis, are often based on comparing signatures or descriptors that capture the main geometric and topological properties of 3D objects. None of the existing descriptors, however, achieve best performance on all shape classes. In this article, we explore, for the first time, the usage of covariance matrices of descriptors, instead of the descriptors themselves, in 3D shape analysis. Unlike histogram -based techniques, covariance-based 3D shape analysis enables the fusion and encoding of different types of features and modalities into a compact representation. Covariance matrices, however, are elements of the non-linear manifold of symmetric positive definite (SPD) matrices and thus ${\BBL_2}$ metrics are not suitable for their comparison and clustering. In this article, we study geodesic distances on the Riemannian manifold of SPD matrices and use them as metrics for 3D shape matching and recognition. We then: (1) introduce the concepts of bag of covariance (BoC) matrices and spatially-sensitive BoC as a generalization to the Riemannian manifold of SPD matrices of the traditional bag of features framework, and (2) generalize the standard kernel methods for supervised classification of 3D shapes to the space of covariance matrices. We evaluate the performance of the proposed BoC matrices framework and covariance -based kernel methods and demonstrate their superiority compared to their descriptor-based counterparts in various 3D shape matching, retrieval, and classification setups. <s> BIB026
In this class of methods, 3D shapes are treated as sets of landmarks sampled from their surfaces. The problem of finding correspondences between two surfaces f 1 and f 2 is then reduced to the problem of matching landmarks across the surfaces using some optimality criteria. The sampling of landmarks can be either uniform or adaptive to cope with the varying surface complexity BIB006 , BIB015 , BIB023 . For instance, in the case of triangulated meshes, each vertex can be treated as a landmark. In the case of parameterized surfaces, f : S 2 → R 3 , then one can sample points s i from the domain S 2 and use f (s i ) = f i as landmarks. A popular approach for putting in correspondence the landmarks is the Iterative Closest Point (ICP) algorithm, proposed in BIB001 , BIB002 , which iterates between two steps: (1) a matching step where correspondences are estimated either by nearest-neighbor search using point-to-point BIB001 or point-to-plane BIB002 distances, or using some local descriptors, and (2) an optimal alignment step using the estimated correspondences. Since its introduction, many variants of the ICP algorithm have been proposed. They aimed at improving various aspects, such as speed and quality of convergence, of the original algorithm, by, for example, combining multiple distance measures with some local descriptors BIB005 . Nevertheless, ICP algorithm and its variants provide good results when the poses of the shapes being aligned are close to each other. When the difference in pose is large, the search space for correspondences is very large. In theory, however, three pairs of corresponding points are sufficient to define a rigid transformation. This fact has been used in BIB003 , BIB020 , BIB021 to derive RANSACbased solutions. Their complexity is, however, high, of order O(l 3 ), where l is the number of points being aligned. Aiger et al. BIB012 introduced the four point congruent sets (4PCS) algorithm, which reduced the complexity of RANSAC algorithms to O(l 2 ). It has been later optimized to achieve a complexity of order O(l) BIB024 . Another approach for finding correspondences is to characterize the shape's geometry around the landmarks using some descriptors BIB004 , BIB007 , BIB025 , BIB026 , BIB022 , BIB009 , BIB016 and then match each landmark to its closest one in terms of a distance measure in the descriptor space BIB013 , BIB010 . The main difficulty, however, is that in the vast majority of applications, one is required to put in correspondence two or more 3D objects that undergo non-rigid deformations that affect the geometry of the local regions. When restricting the analysis to surfaces that only undergo isometric deformations, i.e. bending, which is a subclass of nonrigid deformations, one can design methods or descriptors that only capture the intrinsic properties of shapes, i.e. the properties that remain unchanged after changes due to bending are factored out. Examples of such approaches include Generalized Multidimensional Scaling (GMDS) BIB008 , spectral analysis based on Laplace-Beltrami eigenfunctions BIB011 , BIB019 , and Heat Kernel Signatures (HKS) BIB017 , BIB018 . Several papers have attempted to relax the isometry constraint so that 3D objects can be put in correspondence even when they undergo stretching. Zhang et al. BIB014 , for example, put two objects in correspondence by finding the optimal bending and stretching that is needed to align one shape onto another. In this work, bending is measured in terms of changes in the direction of the normal vectors while stretching is measured in terms of changes in edge lengths. Thus, the approach uses a metric that is similar to those presented in Section 3.