Growing Least Squares for the Analysis of Manifolds in Scale‐Space

Nicolas Mellado, Inria - Univ. Bordeaux - IOGS - CNRS
Gael Guennebaud, Inria - Univ. Bordeaux - IOGS - CNRS
Pascal Barla, Inria - Univ. Bordeaux - IOGS - CNRS
Patrick Reuter, Inria - Univ. Bordeaux - IOGS - CNRS
Christophe Schlick, Inria - Univ. Bordeaux - IOGS - CNRS

Symposium on Geometry Processing 2012, Computer Graphics Forum


We present a novel approach to the multi-scale analysis of point-sampled manifolds of co-dimension 1. It is based on a variant of Moving Least Squares, whereby the evolution of a geometric descriptor at increasing scales is used to locate pertinent locations in scale-space, hence the name Growing Least Squares. Compared to existing scale-space analysis methods, our approach is the first to provide a continuous solution in space and scale dimensions, without requiring any parametrization, connectivity or uniform sampling. An important implication is that we identify multiple pertinent scales for any point on a manifold, a property that had not yet been demonstrated in the literature. In practice, our approach exhibits an improved robustness to change of input, and is easily implemented in a parallel fashion on the GPU. We compare our method to state-of-the-art scale-space analysis techniques and illustrate its practical relevance in a few application scenarios

Key contributions

  • A simple yet efficient multiscale geometric descriptor,
  • A new continuous mesure to detect pertinent scales on point clouds.
A maintained implementation is available in the Patate library.

Geometric descriptor

The Growing Least Squares descriptor is computed on point clouds by fitting algebraic hyperspheres at multiple scales (see online demo here). In order to describe the geometry with meanfuyl parameters, we provided a reparametrization of the algebraic hypersphere using the 3 following parameters: τ, η and κ.

Use the demo below to manipulate an algebraic circle, click on each parameter for more details. The circle is expressed relatively to the visible oriented point visible (black dot). The inside volume represented by the circle is shown in gray.

Your browser does not support the canvas element.

Pertinent scale extraction

The key idea behind our pertinent scale extraction is to compute, for a given position, a Geometric Variation function, that is low when the fit is stable over scale variation and have hight values when it change.
In the following video, we display the fitted circle for a given input point while the scale is growing up. This visualization illustrates our assumption that, when fitting is stable over scale variation, the associated scale interval can be considered as pertinent, at this location. On this current example, fitting is stable during two intervals: a small one that characterize the bump, and a large one that is related to the global shape of the object.

Related papers

See publication list for more details.
  • Relative scale estimation: Nicolas Mellado, Matteo Dellepiane, Roberto Scopigno. "Relative Scale Estimation and 3D Registration of Multi-Modal Geometry Using Growing Least Squares", IEEE Transactions on Visualization & Computer Graphics vol. 22 no. 9, p. 2160-2173, 2016,
  • Estimation of robust geometric variation flows: Nicolas Mellado. "Analysis of 3D objects at multiple scales: application to shape matching", PhD Thesis, 2012,
  • Curvature estimation for rendering: Nicolas Mellado, Pascal Barla, Gael Guennebaud, Patrick Reuter, Gregory Duquesne. "Screen-space Curvature for Production-quality Rendering and Compositing", ACM SIGGRAPH Talks, 2013.