Search

International audience; Inspired by the strengths of quadric error metrics initially designed for mesh decimation, we propose a concise mesh reconstruction approach for 3D point clouds. Our approach proceeds by clustering the input points enriched with quadric error metrics, where the generator of each cluster is the optimal 3D point for the sum of its quadric error metrics. This approach favors the placement of generators on sharp features, and tends to equidistribute the error among clusters. We reconstruct the output surface mesh from the adjacency between clusters and a constrained binary solver. We combine our clustering process with an adaptive refinement driven by the error. Compared to prior art, our method avoids dense reconstruction prior to simplification and produces immediately an optimized mesh.

Previous works on lexicographic optimal chains have shown that they provide meaningful geometric homology representatives while being easier to compute than their l 1-norm optimal counterparts. This work presents a novel algorithm to efficiently compute lexicographic optimal chains with a given boundary in a triangulation of 3-space, by leveraging Lefschetz duality and an augmented version of the disjoint-set data structure. Furthermore, by observing that lexicographic minimization is a linear operation, we define a canonical basis of lexicographic optimal chains, called critical basis, and show how to compute it. In applications, the presented algorithms offer new promising ways of efficiently reconstructing open surfaces in difficult acquisition scenarios.

In this paper, we study the spectrum and the eigenvectors of radial kernels for mixtures of distributions in $\mathbb{R}^n$. Our approach focuses on high dimensions and relies solely on the concentration properties of the components in the mixture. We give several results describing of the structure of kernel matrices for a sample drawn from such a mixture. Based on these results, we analyze the ability of kernel PCA to cluster high dimensional mixtures. In particular, we exhibit a specific kernel leading to a simple spectral algorithm for clustering mixtures with possibly common means but different covariance matrices. We show that the minimum angular separation between the covariance matrices that is required for the algorithm to succeed tends to $0$ as $n$ goes to infinity.

We introduce a total order on n-simplices in the n-Euclidean space for which the support of the lexicographic-minimal chain with the convex hull boundary as boundary constraint is precisely the n-dimensional Delaunay triangulation, or in a more general setting, the regular triangulation of a set of weighted points. This new characterization of regular and Delaunay triangulations is motivated by its possible generalization to submanifold triangulations as well as the recent development of polynomial-time triangulation algorithms taking advantage of this order.

National audience; Notre approche consiste à considérer le nuage de points en entrée comme une mesure discrète (une distribution de masses), et à construire une approximation par une mesure continue (et constante par morceaux)sur les faces d’un complexe simplicial. La distance entre les deux mesures est calculée par une approximation du transport optimal obtenue par programmation linéaire, et le complexe simplicial est obtenu par décimation et optimisation d’une triangulation de Delaunay initialisée avec un sous-ensemble des points en entrée. La distance utilisée est robuste à la fois au bruit et aux données aberrantes, et préserve les arêtes vives et les bords des formes à reconstruire. Cette distance peut également servir comme outil de post-traitement sur des surfaces lisses reconstruites avec des méthodes par fonction implicite.

We propose a robust, feature-preserving surface reconstruction algorithm which turns a point set with noise and outliers into a low triangle-count simplicial complex. Our approach starts with a simplicial complex filtered from a 3D Delaunay triangulation of the input points. This initial approximation is iteratively simplified based on the optimal cost to transport the point set to the simplicial complex, both seen as measures (or mass distributions). Our optimal transport formulation allows the recovery of sharp features even in the presence of a large amount of outliers and/or noise in the input set.; Nous proposons une méthode robuste de reconstruction de surface qui préserve les bords et les arêtes vives. Cette méthode part d'un nuage de points bruités et contenant des points aberrants pour reconstruire un complexe simplicial parcimonieux. Notre approche débute par la construction d'un complexe simplicial par filtrage d'une triangulation de Delaunay des points initiaux. Cette approximation initiale est ensuite itérativement simplifiée en se basant sur le coût de transport entre le nuage de points et le complexe simplicial, ceux-ci étant vus comme des distributions de masse. Cette formulation basée sur le transport optimal entre les deux distributions permet de retrouver les arêtes vives même en présence de nombreux points aberrants ou de bruit dans le nuage de points initial.

International audience; Data often comes in the form of a point cloud sampled from an unknown compact subset of Euclidean space. The general goal of geometric inference is then to recover geometric and topological features (Betti numbers, curvatures,...) of this subset from the approximating point cloud data. In recent years, it appeared that the study of distance functions allows to address many of these questions successfully. However, one of the main limitations of this framework is that it does not cope well with outliers nor with background noise. In this paper, we show how to extend the framework of distance functions to overcome this problem. Replacing compact subsets by measures, we introduce a notion of distance function to a probability distribution in $\R^n$. These functions share many properties with classical distance functions, which makes them suitable for inference purposes. In particular, by considering appropriate level sets of these distance functions, it is possible to associate in a robust way topological and geometric features to a probability measure. We also discuss connections between our approach and non parametric density estimation as well as mean-shift clustering.

Reconstruire un modèle à partir d'échantillons est un problème central se posant en médecine numérique, en ingénierie inverse, en sciences naturelles, etc. Ces applications ont motivé une recherche substantielle pour la reconstruction de surfaces, la question de la reconstruction de modèles plus généraux n'ayant pas été examinée. Ce travail présente an algorithme visant à changer le paradigme de reconstruction en 3D comme suit. Premièrement, l'algorithme reconstruit des formes générales--des ensembles compacts et non plus des surfaces. Sous des hypothèses appropriées, nous montrons que la reconstruction a le type d'homotopie de l'objet de départ. Deuxièmement, l'algorithme ne génère pas une seule reconstruction, mais un ensemble de reconstructions plausibles. Troisièmement, l'algorithme peut être couplé à la persistance topologique, afin de sélectionner les traits les plus stables du modèle reconstruit. Enfin, en cas d'échec de la reconstruction, la méthode permet une identification aisée des régions sous-echantillonnées, afin éventuellement de les enrichir. Ces points clefs sont illustrés sur des modèles difficiles, et devraient permettre de mieux tirer parti de leurs caractéristiques dans les application sus-citées.

This work adresses the problem of the approximation of the normals of the offsets of general compact sets in euclidean spaces. It is proven that for general sampling conditions, it is possible to approximate the gradient vector field of the distance to general compact sets. These conditions involve the $\mu$-reach of the compact set, a recently introduced notion of feature size. As a consequence, we provide a sampling condition that is sufficient to ensure the correctness up to isotopy of a reconstruction given by an offset of the sampling. We also provide a notion of normal cone to general compact sets which is stable under perturbation.

National audience; Des siècles durant, les mathématiciens ont étudié la courbure des surfaces lisses. Pour être traitées aujourd’hui par ordinateur, les surfaces sont représentées par des maillages, constitués de petits triangles et ne sont donc pas lisses. Les théories développées par les mathématiciens doivent donc être adaptées au cas des maillages.