Digital Voronoi Covariance Measure and geometry estimation

Table of Contents

• Voronoi Covariance Measure
• Computing the Voronoi Covariance Measure of a point set
• Voronoi Covariance Measure of a digital surface
  • The class VoronoiCovarianceMeasureOnDigitalSurface
  • The class VCMDigitalSurfaceLocalEstimator

Author(s) of this documentation:

Jacques-Olivier Lachaud

Part of the Geometry package.

This part of the manual describes classes and functions related to the Voronoi Covariance Measure (VCM) of a set of points in arbitrary dimension. The VCM is a covariance tensor related to a distance function to the input data points. It was introduced by Mérigot, Ovsjanikov and Guibas [88]. The digital version of the VCM was studied by Cuel, Lachaud, and Thibert [40]. Stability and multigrid convergence results have been established. This documentation presents the implementation of the digital VCM. The VCM is useful for the following tasks:

• normal cone estimation: Given a set of digital points approximating a surface, the VCM estimates robustly the normal vector to this underlying surface.
• geometry estimation: Given a digital surface approximating some surface, the VCM can estimate robustly the oriented normal vector and the principal directions of the underlying surface.
• feature detection: Given a set of digital points approximating a surface, the eigenvalues of the VCM can be combined to define a robust feature detector.

Related examples are geometry/volumes/dvcm-2d.cpp, geometry/surfaces/dvcm-3d.cpp, geometry/surfaces/dvcm-2d-curvature.cpp.

Voronoi Covariance Measure

The Voronoi covariance measure (VCM) has been introduced in [88] for normals and curvature estimations. Let K be a compact subset of \(\mathbb{R}^3\) and \(d_K\) the distance function to K, i.e. the map \( d_K(x) := \min_{p\in K} \|p-x\| \). A point p where the previous minimum is reached is called a projection of x on K. Almost every point admits a single projection on K, thus definining a map \( p_K: \mathbb{R}^3 \to K \) almost everywhere. The R-offset of K is the R-sublevel set of \( d_K\), i.e. the set \(K^R:=d_K^{-1}(]-\infty, R[)\). The VCM maps any integrable function \(\chi:\mathbb{R}^3 \to \mathbb{R}^+\) to the matrix

\[ \mathcal{V}_{K,R}(\chi) := \int_{K^R}(x-p_K(x))(x-p_K(x))^{\mathbf{t}} \chi(p_K(x)) d x. \]

Voronoi Covariance Measure of a point set in the plane.

Note

The stability result of [88] implies that information extracted from the covariance matrix such as normals or principal directions are stable with respect to Hausdorff perturbation.

Advanced:

Remark that this definition matches the definition introduced in [88] : when \(\chi\) is the characteristic function of a ball, one recovers a notion similar to the convolved VCM.

Computing the Voronoi Covariance Measure of a point set

Let K be some point set. In this case, the computation of the VCM can be split into isolated calculations in each Voronoi cell of K. In the digital setting, the Voronoi cells can be efficiently computed by repeated scans of the domain (see nD Volumetric Analysis using Separable Processes). That's exactly how is computed the VCM. The computational complexity of the VCM is thus the computational complexity of the Voronoi map in nD. The templated class VoronoiCovarianceMeasure is the one taking of the computation. It requires two type parameters:

• TSpace: the digital space (any model of CSpace), like SpaceND.
• TSeparableMetric: the metric used for computing the Voronoi map (any model of CSeparableMetric), like ExactPredicateLpSeparableMetric<TSpace, 2> for the Euclidean metric.

The instantiation of the class VoronoiCovarianceMeasure requires the following parameters:

• R the offset radius for the set of points. Voronoi cells are intersected with this offset. The unit corresponds to a step in the digital space.
• r (an upper bound of) the radius of the support of forthcoming kernel functions ( \( \chi \)). The unit corresponds to a step in the digital space. This parameter is used for preparing the data structure that answers to proximity queries.
• aMetric an instance of the chosen metric.

Then, the set of input points is specified by a range of input iterators given to the method VoronoiCovarianceMeasure::init. This method computes the VCM of each Voronoi cell determined by the given points.

typedef Z2i::Space Space;
typedef Z2i::Point Point;
typedef ExactPredicateLpSeparableMetric<Space, 2> Metric; // L2-metric
typedef VoronoiCovarianceMeasure<Space,Metric> VCM;
Point tbl[] = { { 0, 1 }, { 3, 2 }, { 5, 3 } };
Metric l2;
VCM vcm( R, ceil( r ), l2, true ); // last parameter is verbose mode
vcm.init( tbl, tbl + 3 );

You may then access to the following elements:

• the voronoi map giving for any point the closest point in K is accessed through method VoronoiCovarianceMeasure::voronoiMap.
• the Voronoi Covariance Matrix of each Voronoi cell as a map Point -> Matrix is returned by method VoronoiCovarianceMeasure::vcmMap.
• the \( \chi \) VCM is returned by method VoronoiCovarianceMeasure::measure, where a kernel function must be specified. The type of the kernel function can be functors::HatPointFunction or functors::BallConstantPointFunction, but you may define your own.

Example geometry/volumes/dvcm-2d.cpp gives the full code for computing the \( \chi \)-VCM of an arbitrary set of digital points, and then estimating the normal vector as well as detecting corners.

Normal vector and feature detection with Voronoi Covariance Measure.

Voronoi Covariance Measure of a digital surface

In the case where the input data is a digital surface, we provide several classes that helps the computation and the usage of the VCM. Furthermore, having as input data a volume or a set of oriented surfels allows us to orient the normal direction given by the VCM. The main classes are VoronoiCovarianceMeasureOnDigitalSurface and VCMDigitalSurfaceLocalEstimator.

The class VoronoiCovarianceMeasureOnDigitalSurface

The class VoronoiCovarianceMeasureOnDigitalSurface is templated by the following types:

• TDigitalSurfaceContainer the type of digital surface container (model of concepts::CDigitalSurfaceContainer), e.g. an ImplicitDigitalSurface.
• TSeparableMetric a model of concepts::CSeparableMetric used for computing the Voronoi map (e.g. Euclidean metric is DGtal::ExactPredicateLpSeparableMetric<TSpace, 2> )
• TKernelFunction the type of the kernel function \( \chi \) used for integrating the VCM, a map: Point -> Scalar, e.g. functors::HatPointFunction or functors::BallConstantPointFunction, but you may define your own.

At instanciation, you have to precise several parameters:

• surface the digital surface that is aliased in this. The user can secure the aliasing by passing a CountedConstPtrOrConstPtr.
• surfelEmbedding the chosen embedding for surfels (Pointels, InnerSpel, OuterSpel). This embedding defines the digital points that are used in the computation of the VCM (see VoronoiCovarianceMeasure).
• R the offset radius for the set of points. Voronoi cells are intersected with this offset. The unit corresponds to a step in the digital space.
• r (an upper bound of) the radius of the support of forthcoming kernel functions ( \( \chi \)). The unit corresponds to a step in the digital space. This parameter is used for preparing the data structure that answers to proximity queries.
• chi_r the kernel function whose support has radius less or equal to r.
• t the radius for the trivial normal estimator, which is used for finding the correct orientation inside/outside for the VCM.
• aMetric an instance of the chosen metric.

The following piece of code shows how to wrap a VCM around a digital surface surface.

  typedef ExactPredicateLpSeparableMetric<Space, 2> Metric;          // L2-metric type
  typedef functors::HatPointFunction<Point,double>  KernelFunction;  // chi function type
  typedef VoronoiCovarianceMeasureOnDigitalSurface< DigitalSurfaceContainer, Metric,
                                                    KernelFunction > VCMOnSurface;
  typedef VCMOnSurface::Surfel2Normals::const_iterator S2NConstIterator;

  Surfel2PointEmbedding embType = Pointels; // Could be Pointels|InnerSpel|OuterSpel;
  Metric l2;                                // Euclidean L2 metric
  KernelFunction chi( 1.0, r );             // hat function with support of radius r
  VCMOnSurface vcm_surface( surface, embType, R, r,
                            chi, trivial_r, l2, true /* verbose */ );

The whole VCM computation is done in the constructor. Once this is done, you may access to the whole VCM tensor information with the methods:

• VoronoiCovarianceMeasureOnDigitalSurface::mapSurfel2Normals returns the map associating to each surfel a structure containing both the normal estimated by VCM and the normal estimated from the trivial surfel normals.
• VoronoiCovarianceMeasureOnDigitalSurface::mapPoint2ChiVCM returns the map associating with each admissible digital point (so depending on the surfelEmbedding) the eigenstructure of the VCM tensor (principal directions, eigenvalues).
• VoronoiCovarianceMeasureOnDigitalSurface::getChiVCMEigenvalues outputs the eigenvalues at the specified surfel.
• VoronoiCovarianceMeasureOnDigitalSurface::getChiVCMEigenStructure outputs the whole eigenstructure at the specified surfel.

Example geometry/surfaces/dvcm-3d.cpp gives the full code for computing the \( \chi \)-VCM of an arbitrary digital surface, and then estimating the normal vector as well as detecting corners. Here is a small piece of code that extracts the VCM normal for each surfel.

for ( S2NConstIterator it = vcm_surface.mapSurfel2Normals().begin(), 
        itE = vcm_surface.mapSurfel2Normals().end(); it != itE; ++it )
  {
    Surfel s     = it->first;            // gets surfel
    RealVector n = it->second.vcmNormal; // gets the estimated VCM normal vector
  }

Normal vector and feature detection with Voronoi Covariance Measure.

The class VCMDigitalSurfaceLocalEstimator

The class VCMDigitalSurfaceLocalEstimator adapts a VoronoiCovarianceMeasureOnDigitalSurface to be a model of concepts::CDigitalSurfaceLocalEstimator. It uses the Voronoi Covariance Measure to estimate geometric quantities. The template type TVCMGeometricFunctor specifies what is the estimated quantity. Standard geometric functors for VCM are defined in file DGtal/geometry/surfaces/estimation/VCMGeometricFunctors.h. For instance, functors::VCMNormalVectorFunctor returns the estimated VCM surface outward normal for given surfels, functors::VCMAbsoluteCurvatureFunctor returns the absolute curvature (see namespace functors:: and those functors starting with VCM).

In order to fulfill concept requirements, a VCMDigitalSurfaceLocalEstimator can be instantiated in several ways:

• it can be default constructed. In this case, the object is not valid and further methods must be called (first VCMDigitalSurfaceLocalEstimator::attach to attach a digital surface to the estimator, then VCMDigitalSurfaceLocalEstimator::setParams to specify all required parameters in the VCM) before calling VCMDigitalSurfaceLocalEstimator::init.
• it can be copy constructed. In this case, the object is valid or invalid depending on the cloned object. Further methods may be called afterwards like VCMDigitalSurfaceLocalEstimator::attach or VCMDigitalSurfaceLocalEstimator::setParams.
• it can be constructed from a surface. In this case, the object is still invalid. You have to call VCMDigitalSurfaceLocalEstimator::setParams to specify all required parameters in the VCM before calling VCMDigitalSurfaceLocalEstimator::init.
• it can be constructed from a VoronoiCovarianceMeasureOnDigitalSurface object. In this case, the object is directly valid. You may call VCMDigitalSurfaceLocalEstimator::init directly.

Once a VCMDigitalSurfaceLocalEstimator is instantiated, you have to call its init method like all estimators (VCMDigitalSurfaceLocalEstimator::init). Note that for the VCM this method does nothing (except checking that the object is valid). Indeed, the VCM is necessarily computed for the whole surface, since it depends on a global distance transform.

Note

The digital surface and the VCM on this surface are referenced in the estimator by smart pointers. While this avoids duplication, it also allows you to have duplication on demand if you handle a CountedPtr either at instantiation or when calling VCMDigitalSurfaceLocalEstimator::attach or VCMDigitalSurfaceLocalEstimator::setParams.

typedef VCMDigitalSurfaceNormalEstimator<SurfaceContainer,Metric,KernelFunction> VCMNormalEstimator;
typedef functors::VCMNormalVectorFunctor<VCMOnSurface> NormalVectorFunctor;
typedef VCMDigitalSurfaceLocalEstimator<SurfaceContainer,Metric,
                                        KernelFunction, NormalVectorFunctor> VCMNormalEstimator;
CountedConstPtrOrConstPtr<Surface> ptrSurface( new Surface( surfaceContainer ) ); // acquired
KernelFunction chi( 1.0, 7.0 );
CountedPtr<VCMOnSurface> vcm_surface( new VCMOnSurface( ptrSurface, Pointels, 
                                      15.0, 7.0, chi, 7.0, l2, true ) ); // avoid duplications
VCMNormalEstimator estimator( vcm_surface );
estimator.init( 1.0, ptrSurface->begin(), ptrSurface->end() );
for ( typename Surface::ConstIterator it = ptrSurface->begin(), 
        itE = ptrSurface->end(); it != itE; ++it )
  {
    RealVector n_est  = estimator.eval( it );
  }

Example geometry/surfaces/dvcm-2d-curvature.cpp shows how to extract the curvature field (in absolute value) of a digital contour with VCMDigitalSurfaceLocalEstimator templated by functor functors::VCMAbsoluteCurvatureFunctor.

Absolute curvature estimation with Voronoi Covariance Measure.