DGtal
0.9.3beta

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 [50]. The digital version of the VCM was studied by Cuel, Lachaud, and Thibert [24]. 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:
Related examples are geometry/volumes/dvcm2d.cpp, geometry/surfaces/dvcm3d.cpp, geometry/surfaces/dvcm2dcurvature.cpp.
The Voronoi covariance measure (VCM) has been introduced in [50] 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} \px\ \). 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 Roffset of K is the Rsublevel 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}(xp_K(x))(xp_K(x))^{\mathbf{t}} \chi(p_K(x)) d x. \]
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:
The instantiation of the class VoronoiCovarianceMeasure requires the following parameters:
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.
You may then access to the following elements:
Example geometry/volumes/dvcm2d.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.
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 is templated by the following types:
At instanciation, you have to precise several parameters:
The following piece of code shows how to wrap a VCM around a digital surface surface
.
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:
Example geometry/surfaces/dvcm3d.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.
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:
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.
Example geometry/surfaces/dvcm2dcurvature.cpp shows how to extract the curvature field (in absolute value) of a digital contour with VCMDigitalSurfaceLocalEstimator templated by functor functors::VCMAbsoluteCurvatureFunctor.