DGtal
1.0.beta
|
This documentation page is dedicated to distance and metric computation in DGtal. As discussed in nD Volumetric Analysis using Separable Processes, distance functions play an important role in volumetric analysis of shapes (distance transformation, Voronoi maps, medial axis,...). We formalize here the concepts related to such function. First of all, let us start with main definitions:
When performing some geometry processing, one may consider additional requirements on the metric and thus norms:
(homogeneity) \( \forall \lambda\in\mathbb{R}, \quad g(\lambda\cdot\vec{x}) = |\lambda|\cdot g(\vec{x})\)
\(d(a,b):= g(b-a)\) is the metric induced by the norm \(g\).
In the following, we restrict our attention to metric spaces even if some of them are induced by norms.
In DGtal, the concept of CMetricSpace is associated with metric space definition. A first refinement of this concept is the concept of CDigitalMetricSpace whose models implement distance functions on integer numbers (i.e. \((\mathbb{Z}^n, \mathbb{Z}, d)\))). For example,
For instance, CMetricSpace requires to have a binary operator to compute the distance between any two points of the digital space. Furthermore, it requires to have a method he closest(origin,p,q) which returns the closest point from p and q to the origin. Such closest method can be easily implemented from the binary distance operator. However, for some metric, more efficient implementation can be obtained to answer to closest() requests.
Similarly to metric models, Power Metrics are important for reverse distance reconstruction and medial axis extraction. For \( l_2\) metric, the power distance between a point \( x\) and a ball \((y,r)\) with centger \(y\) and radius \(r\), is defined by
\[ pow(x,y) = \| x - y\|_2^2 - r \]
Power function are no more positive but the geometry of the distance (convex unit balls,...) are relevant in volumetric analysis.
We perform volumetric analysis using separable approaches (see nD Volumetric Analysis using Separable Processes), additional properties are required for the model of metrics (see [57], [42], [27]).
Such properties are related to a monotonicity property of the metric. In dimension 2, consider two points \( p(x,y)\), \(q(x',y')\) with \(x<x'\). Let \(r( x'',0)\) be a point on the x-axis such that \(d(p,r) = d(q,r)\) and \( s(u,0)\) be another point on the x-axis. A metric \( d\) is monotonic if
\[ u < x'' \implies d(p,s) \leq d(q,s) \]
and
\[ u > x'' \implies d(p,s) \geq d(q,s) \]
As discussed in [42], any metric induced by a norm with axis symmetric unit ball is monotonic. Hence, all \(l_p\) are monotonic, as well as most path based norms (chamfer norms, neighborhood sequence norms,...). Such properties are implemented in the concept of CSeparableMetric. Similarly, CPowerSeparableMetric can be defined as a refinement of CPowerMetric with monotonicity property of the power metric.
The Separable metric concept is a refinement of the CMetricSpace (resp. CPowerMetric) concept in which we require models to implement a method hiddenBy(u,v,w,startingPoint,endPoint,dim): given three digital points u, v, w and an isothetic segment defined by the pair [startingPoint, endPoint] along the dimension dim, such method returns true if Voronoi cells of u and w hide the Voronoi cell if v on the segment. Such predicate can be illustrated as follows:
CPowerSeparableMetric concepts is a similar refinement of the CPowerMetric concept. Indeed, CPowerSeparableMetric models must implement an hiddenByPower(u, wu,v,wv,w,ww,startingPoint,endPoint,dim) on triplet of weighted points {(u,wu),(v,wv),(w,ww)}.
The class SeparableMetricAdapter adapts any model of CMetricSpace which is monotonic to a model of CSeparableMetric. Please refer to the following table for computational costs.
Main models of CSeparableMetric and CPowerSeparableMetric are:
As discussed in nD Volumetric Analysis using Separable Processes, both VoronoiMap and PowerMap (and their associated subclasses) are parametrized by a generic separable metric (model of CSeparableMetric or CPowerSeparableMetric). If \( C \) corresponds to the cost of the closest() or closestPower() methods for the given metric, and \( H \) the cost of the hiddenBy() or hiddenByWeigthed(), the computational costs of the separable metrics can be summarized as follows:
Models of CSeparableMetric/CPowerSeparableMetric | C | H | Note |
---|---|---|---|
\( O(log(p)) \) | \( O(log(p)log(n)) \) | Exact computations | |
ExactPredicateLpSeparableMetric specialized for p=2 | \( O(1) \) | \( O(1) \) | Exact computations |
ExactPredicateLpSeparableMetric specialized for p=1 | \( O(1) \) | \( O(log(n)) \) | Exact computations |
InexactPredicateLpSeparableMetric with p at construction | \( O(1) \) | \( O(log(n)) \) | Inexact computations since std::pow on double is used (supposed to be \( O(1) \)) |
\( O(log(p)) \) | \( O(log(p)log(n)) \) | Exact computations | |
ExactPredicateLpPowerSeparableMetric specialized for p=2 | \( O(1) \) | \( O(1) \) | Exact computations |
SeparableMetricAdapter of a metric aMetric | \( O(m) \) | \( O(mlog(n)) \) | relies on aMetric(p,q) computations |
experimental::ChamferNorm2D | \( O(log(p)) \) | \( O(log^2(n)) \) | [27] |
Following this table, VoronoiMap, DistanceTransformation, PowerMap, ReverseDistanceTransformation have the following computational cost:
\[ O(d\cdot n^d\cdot (C+H)) \]
For example, for the \( l_2 \) metric, all algorithms are in \( \Theta(dn^d)\).