A Gromov-Hausdorff Framework with Diffusion Geometry for Topologically-Robust Non-rigid Shape Matching

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.     

Conformal geometry and its applications on 3D shape matching, recognition, and stitching

Three-dimensional shape matching is a fundamental issue in computer vision with many applications such as shape registration, 3D object recognition, and classification. However, shape matching with noise, occlusion, and clutter is a challenging problem. In this paper, we analyze a family of quasi-conformal maps including harmonic maps, conformal maps, and least-squares conformal maps with regards to 3D shape matching. As a result, we propose a novel and computationally efficient shape matching framework by using least-squares conformal maps. According to conformal geometry theory, each 3D surface with disk topology can be mapped to a 2D domain through a global optimization and the resulting map is a diffeomorphism, i.e., one-to-one and onto. This allows us to simplify the 3D shape-matching problem to a 2D image-matching problem, by comparing the resulting 2D parametric maps, which are stable, insensitive to resolution changes and robust to occlusion, and noise. Therefore, highly accurate and efficient 3D shape matching algorithms can be achieved by using the above three parametric maps. Finally, the robustness of least-squares conformal maps is evaluated and analyzed comprehensively in 3D shape matching with occlusion, noise, and resolution variation. In order to further demonstrate the performance of our proposed method, we also conduct a series of experiments on two computer vision applications, i.e., 3D face recognition and 3D nonrigid surface alignment and stitching.     

Globally optimal surface mapping for surfaces with arbitrary topology

Computing smooth and optimal one-to-one maps between surfaces of same topology is a fundamental problem in computer graphics and such a method provides us a ubiquitous tool for geometric modeling and data visualization. Its vast variety of applications includes shape registration/matching, shape blending, material/data transfer, data fusion, information reuse, etc. The mapping quality is typically measured in terms of angular distortions among different shapes. This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art inter-surface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is sorely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt towards numerically computing globally optimal maps. Consequently, our mapping framework offers a powerful computational tool for graphics and visualization tasks such as data and texture transfer, shape morphing, and shape matching.     

Geodesic Matching with Free Extremities

In this paper, we describe how to use geodesic energies defined on various sets of objects to solve several distance related problems. We first present the theory of metamorphoses and the geodesic distances it induces on a Riemannian manifold, followed by classical applications in landmark and image matching. We then explain how to use the geodesic distance for new issues, which can be embedded in a general framework of matching with free extremities. This is illustrated by results on image and shape averaging and unlabeled landmark matching. Laurent Garcin is a former student of the Ecole Polytechnique. He obtained his Ph.D. in 2004 at the Ecole Normale de Cachan, working on matching methods for landmarks and images. He is an engineer at the French National Geographic Institute. Laurent Younes is a former student of the Ecole Normale Superieure in Paris. He was awarded the Ph.D. from the University Paris Sud in 1989, and the thesis advisor certification from the same university in 1995. He works on the statistical analysis of images and shapes, and on modeling shape deformations and shape spaces. Laurent Younes entered CNRS, the French National Research Center in October 1991, in which he has been a “Directeur de Recherche" until 2003. He is now a professor at the Department of Applied Mathematics and Statistics Department and the Center for Imaging Science at Johns Hopkins University in July 2003.     

Heat method of non-uniform diffusion for computing geodesic distance on images and surfaces

This paper presents a non-uniform heat method to calculate geodesic distance and geodesic curves on the images and surfaces. Different from the varadhan’s formula-based heat method, our non-uniform heat method first finds the direction of distance increases by heat diffusion, and then recovers the geodesic distance by solving a Poisson equation. Various heat diffusion metrics obtained from different potentials and tensors, such as intensity-based metrics, gradient-based metrics, and anisotropy metrics et., describe the differences of geodesic distances in various regions. Combined with automatic geodesic segmentation technology, our heat method can be effectively and quickly applied to centerlines extraction and salient curves detection in images, skeleton extraction of shapes, and 3D path planning on surfaces. Two categories of discretization algorithms on scattered points and triangle meshes are more flexible and can often be used to more complicated cases. The algorithm is robust and simple to implement since it is based on solving a pair of standard sparse linear systems. Pre-calculation also greatly reduces time consumption and memory footprint.

     

On bending invariant signatures for surfaces

Isometric surfaces share the same geometric structure, also known as the "first fundamental form." For example, all possible bendings of a given surface that includes all length preserving deformations without tearing or stretching the surface are considered to be isometric. We present a method to construct a bending invariant signature for such surfaces. This invariant representation is an embedding of the geometric structure of the surface in a small dimensional Euclidean space in which geodesic distances are approximated by Euclidean ones. The bending invariant representation is constructed by first measuring the intergeodesic distances between uniformly distributed points on the surface. Next, a multidimensional scaling technique is applied to extract coordinates in a finite dimensional Euclidean space in which geodesic distances are replaced by Euclidean ones. Applying this transform to various surfaces with similar geodesic structures (first fundamental form) maps them into similar signature surfaces. We thereby translate the problem of matching nonrigid objects in various postures into a simpler problem of matching rigid objects. As an example, we show a simple surface classification method that uses our bending invariant signatures.     

3D anatomical shape atlas construction using mesh quality preserved deformable models

3D anatomical shape atlas construction has been extensively studied in medical image analysis research, owing to its importance in model-based image segmentation, longitudinal studies and populational statistical analysis, etc. Among multiple steps of 3D shape atlas construction, establishing anatomical correspondences across subjects, i.e., surface registration, is probably the most critical but challenging one. Adaptive focus deformable model (AFDM) [1] was proposed to tackle this problem by exploiting cross-scale geometry characteristics of 3D anatomy surfaces. Although the effectiveness of AFDM has been proved in various studies, its performance is highly dependent on the quality of 3D surface meshes, which often degrades along with the iterations of deformable surface registration (the process of correspondence matching). In this paper, we propose a new framework for 3D anatomical shape atlas construction. Our method aims to robustly establish correspondences across different subjects and simultaneously generate high-quality surface meshes without removing shape details. Mathematically, a new energy term is embedded into the original energy function of AFDM to preserve surface mesh qualities during deformable surface matching. More specifically, we employ the Laplacian representation to encode shape details and smoothness constraints. An expectation–maximization style algorithm is designed to optimize multiple energy terms alternatively until convergence. We demonstrate the performance of our method via a set of diverse applications, including a population of sparse cardiac MRI slices with 2D labels, 3D high resolution CT cardiac images and rodent brain MRIs with multiple structures. The constructed shape atlases exhibit good mesh qualities and preserve fine shape details. The constructed shape atlases can further benefit other research topics such as segmentation and statistical analysis.     

Isometric 3D Shape Partial Matching Using GD-DNA

Isometric 3D shape partial matching has attracted a great amount of interest, with a plethora of applications ranging from shape recognition to texture mapping. In this paper, we propose a novel isometric 3D shape partial matching algorithm using the geodesic disk Laplace spectrum (GD-DNA). It transforms the partial matching problem into the geodesic disk matching problem. Firstly, the largest enclosed geodesic disk extracted from the partial shape is matched with geodesic disks from the full shape by the Laplace spectrum of the geodesic disk. Secondly, Generalized Multi-Dimensional Scaling algorithm (GMDS) and Euclidean embedding are conducted to establish final point correspondences between the partial and the full shape using the matched geodesic disk pair. The proposed GD-DNA is discriminative for matching geodesic disks, and it can well solve the anchor point selection problem in challenging partial shape matching tasks. Experimental results on the Shape Retrieval Contest 2016 (SHREC’16) benchmark validate the proposed method, and comparisons with isometric partial matching algorithms in the literature show that our method has a higher precision.     

Elastic geodesic paths in shape space of parameterized surfaces

This paper presents a novel Riemannian framework for shape analysis of parameterized surfaces. In particular, it provides efficient algorithms for computing geodesic paths which, in turn, are important for comparing, matching, and deforming surfaces. The novelty of this framework is that geodesics are invariant to the parameterizations of surfaces and other shape-preserving transformations of surfaces. The basic idea is to formulate a space of embedded surfaces (surfaces seen as embeddings of a unit sphere in IR3) and impose a Riemannian metric on it in such a way that the reparameterization group acts on this space by isometries. Under this framework, we solve two optimization problems. One, given any two surfaces at arbitrary rotations and parameterizations, we use a path-straightening approach to find a geodesic path between them under the chosen metric. Second, by modifying a technique presented in [25], we solve for the optimal rotation and parameterization (registration) between surfaces. Their combined solution provides an efficient mechanism for computing geodesic paths in shape spaces of parameterized surfaces. We illustrate these ideas using examples from shape analysis of anatomical structures and other general surfaces.     

Scale Normalization for Isometric Shape Matching

We address the scale problem inherent to isometric shape correspondence in a combinatorial matching framework. We consider a particular setting of the general correspondence problem where one of the two shapes to be matched is an isometric (or nearly isometric) part of the other up to an arbitrary scale. We resolve the scale ambiguity by finding a coarse matching between shape extremities based on a novel scale‐invariant isometric distortion measure. The proposed algorithm also supports (partial) dense matching, that alleviates the symmetric flip problem due to initial coarse sampling. We test the performance of our matching algorithm on several shape datasets in comparison to state of the art. Our method proves useful, not only for partial matching, but also for complete matching of semantically similar hybrid shape pairs whose maximum geodesic distances may not be compatible, a case that would fail most of the conventional isometric shape matchers.     

On the Geometry of Multivariate Generalized Gaussian Models

This paper concerns the geometry of the zero-mean multivariate generalized Gaussian distribution (MGGD) and the calculation of geodesic distances on the MGGD manifold. The MGGD is a suitable distribution for the modeling of multivariate (color, multispectral, vector and tensor images, etc.) image wavelet statistics. Expressions are derived for the Fisher-Rao metric for the zero-mean MGGD model. A closed-form expression is obtained for the geodesic distance on the submanifolds characterized by a fixed MGGD shape parameter. Suitable approximate solutions to the geodesic equations are presented in the case of MGGDs with varying shape parameters. An application to image texture similarity measurement in the wavelet domain is briefly discussed, comparing the performance of the geodesic distance and the Kullback-Leibler divergence.     

结合形状滤波和几何图像的3D人脸识别算法

表情变化是3维人脸精确识别面临的主要问题,为此提出一种新的对表情鲁棒的匹配方法。通过形状滤波器将人脸空域形状分成不同频率的3个部分：低频部分对应表情变化;高频部分代表白噪声;包含身份区分度最大的中频信息作为表情不变特征。再利用网格平面参数化,将人脸网格映射到边界为正四边形的平面区域内,经过线性插值采样得到3维形状的2维几何图像。最后通过图像匹配识别人脸。FRGC v2人脸数据库上的实验结果表明,使用形状滤波能显著提高算法的精度和鲁棒性。     

Comparative Visualization of Molecular Surfaces Using Deformable Models

The comparison of molecular surface attributes is of interest for computer aided drug design and the analysis of biochemical simulations. Due to the non‐rigid nature of molecular surfaces, partial shape matching is feasible for mapping two surfaces onto each other. We present a novel technique to obtain a mapping relation between two surfaces using a deformable model approach. This relation is used for pair‐wise comparison of local surface attributes (e.g. electrostatic potential). We combine the difference value as well as the comparability as derived from the local matching quality in a 3D molecular visualization by mapping them to color. A 2D matrix shows the global dissimilarity in an overview of different data sets in an ensemble. We apply our visualizations to simulation results provided by collaborators from the field of biochemistry to evaluate the effectiveness of our results.     

Mesh analysis using geodesic mean-shift

In this paper, we introduce a versatile and robust method for analyzing the feature space associated with a given mesh surface. The method is based on the mean-shift operator, which was shown to be successful in image and video processing. Its strength lies in the fact that it works in a single joint space of geometry and attributes called the feature-space. The mean-shift procedure works as a gradient ascend finding maxima of an estimated probability density function in feature-space. Our method for using the mean-shift technique on surfaces solves several difficulties. First, meshes as opposed to images do not present a regular and uniform sampling of domain. Second, on surface meshes the shifting procedure must be constrained to stay on the surface and preserve geodesic distances. We define a special local geodesic parameterization scheme, and use it to generalize the mean-shift procedure to unstructured surface meshes. Our method can support piecewise linear attribute definitions as well as piecewise constant attributes.     

A fast propagation scheme for approximate geodesic paths

Geodesic paths on surfaces are indispensable in many research and industrial areas, including architectural and aircraft design, human body animation, robotic path planning, terrain navigation, and reverse engineering. 3D models in these applications are typically large and complex. It is challenging for existing geodesic path algorithms to process large-scale models with millions of vertices. In this paper, we focus on the single-source geodesic path problem, and present a novel framework for efficient and approximate geodesic path computation over triangle meshes. The algorithm finds and propagates paths based on a continuous Dijkstra strategy with a two-stage approach to compute a path for each propagating step. Starting from an initial path for each step, its shape is firstly optimized by solving a sparse linear system and then the output floating path is projected to the surface to obtain the refined one for further propagation. We have extensively evaluated our algorithms on a number of 3D models and also compared their performance against existing algorithms. Such evaluation and comparisons indicate our algorithm is fast and produces acceptable accuracy.     

Robust structure from motion with affine camera via low-rank matrix recovery

We present a novel approach to structure from motion that can deal with missing data and outliers with an affine camera. We model the corruptions as sparse error. Therefore the structure from motion problem is reduced to the problem of recovering a low-rank matrix from corrupted observations. We first decompose the matrix of trajectories of features into low-rank and sparse components by nuclear-norm and l1-norm minimization, and then obtain the motion and structure from the low-rank components by the classical factorization method. Unlike pervious methods, which have some drawbacks such as depending on the initial value selection and being sensitive to the large magnitude errors, our method uses a convex optimization technique that is guaranteed to recover the low-rank matrix from highly corrupted and incomplete observations. Experimental results demonstrate that the proposed approach is more efficient and robust to large-scale outliers.