Keywords

1 Introduction

Whatever the quality of the sensor of the acquisition device, digital images are always intrisically noisy because no device can reproduce exactly the result of a mathematically well-defined digitization framework that converts a mathematical object into a set of pixels. When image analysis focuses on the objects contained in images, the segmentation step used to extract the objects further increases this phenomenon. Many approaches have been proposed over the years in order to deal with the noise during digital objects analysis. Some approaches introduce a global “thickness” parameter that is used to twarth the noise effect [6]. This has two important drawbacks: first, digital objects with non uniform amount of noise are not handled correctly because of the global parameter - important details in smooth parts of the object may be lost; second, cancelling the noise effect is somehow a loss of information as an ill-defined denoised object is implicitely studied. Even if methods using adaptive thickness instead of a global constant parameter have been proposed [17], the result is always a unique structuring of the curve, that can be seen as a “denoised” curve (the noise is hidden in the structure). Instead of analysing one possible denoised object, why not analysing all the possible objects at once?

In the last decade, many researches have been conducted on imprecise or uncertain data and related geometric problems. The terms “imprecise” [13] and “uncertain” [8] or “fuzzy” [12, 15] data can be found in the literature: uncertain or fuzzy data is endowed with a probabilistic information, while imprecise data only contains geometric information. In this work, we will focus on imprecise data: each point is then replaced by a region that models the imprecision.

Dealing with imprecise data has been an active field in computational geometry recently [13]. Results concern for instance upper and lower bounds on geometric quantities (smallest enclosing balls, area of convex hull), or pre-processing of geometric structures (Delaunay triangulation). In digital geometry, geometric predicates on digital segments (concurrency, parallelism) were introduced in the context of imprecise data in [16].

In this paper, we present a general framework that lays the foundations for a geometrical analysis of imprecise digital contours and imprecise digital objects by integrating the imprecision instead of discarding it. In Sect. 2, we show how to compute an imprecise digital object from an imprecise closed digital contour. Then, in a second part, we show how to define a family of objects from an imprecise digital object, and how to encode this family.

2 From an Imprecise Digital Contour to an Imprecise Digital Object

In this work, digital objects live in the 2D cellular grid space [11]. Thus, a digital object is a set of 2-cells - the pixels - together with an adjacency relation (4 or 8 adjacency). The contour of a digital object can be defined as an ordered sequence of 1-cells - the linels - such that the intersection of two consecutive linels is a 0-cell - a pointel. In the following, pointels will be refered to as digital points or points for short, whereas the term pixel will be used for 2-cells.

2.1 Imprecise Digital Contour

Given a curve \(\mathscr {C}\) in \(\mathbb {R}^2\) and a digitization process \(\mathbb {D}\) on \(\mathbb {Z}^2\) (e.g. Gauss digitization), we call perfect digitization of \(\mathscr {C}\) the curve \(\mathbb {D}(\mathscr {C})\). Let \(\mathcal {C}\) be a simple closed 4-connected digital curve. In our framework we assume that the digitization process that led to \(\mathcal {C}\) (image acquisition, image segmentation) from a curve \(\mathscr {C}\) is not perfect, so that the perfect digitization \(\mathcal {C}_0\) of \(\mathscr {C}\) lies somewhere more or less close to \(\mathcal {C}\).

In order to model the result of this “imperfect” digitization process, we define the input data as follows. We suppose that each point \(p_i\) of the digital curve \(\mathcal {C}\) is endowed with a positive integer weight \(r_i\). Therefore, the input data is an ordered set of weighted or imprecise points \((p_i, r_i)\), \(i \in [0,n[\), \(p_i \in \mathbb {Z}^2\), \(r_i \in \mathbb {Z}^+\). The weight value stands for the confidence in the input data at each point: the greater the weight, the more imprecise the contour around this point. Points \(p_i\) for which the position is exact (point \(p_i\) belongs to \(\mathcal {C}_0\)) are assigned with a weight equal to one. More precisely, imprecise points are modeled as regions: the weight of the point p is the radius of an open Euclidean ball centered on p, such that the curve \(\mathcal {C}_0\) may actually go through the digital points in this ball. Other models could of course be considered. The digital curve \(\mathcal {C}\) together with the weights is called an imprecise digital contour (see Fig. 1 for an illustration).

In this part, we see how to define an imprecise digital object from this imprecise contour. The goal here is to identify each pixel as inside, outside, or uncertain, depending on whether the object enclosed by \(\mathcal {C}_0\) may include the pixel or not. A precise definition and characterization of these pixels need some more work, which is developed in the following pages.

Experimental validation will be performed on the data computed using the a posteriori computation of noise level (called meaningful scale) proposed in [9, 10]: the meaningful scale computed for each point of a digital contour stands for the imprecision at this point.

Fig. 1.
figure 1

(a) A synthetic imprecise digital contour, color indicates the imprecision value assigned to each point: point \(p_i\) is black when \(r_i=1\), green when \(r_i=2\) and blue when \(r_i=3\). (b) Corresponding balls: each ball is depicted by its set of digital points \(B_i(p_i,r_i)\) and the Euclidean ball enclosing it; for the sake of lisibility, the Euclidean ball depicted is not of radius \(r_i\), but of radius \(r'_i\) such that \(r'_i = \min \{r | B_i(p_i,r_i) \subset b(p_i,r) \} + \varepsilon \) (Color figure online).

Full size image

2.2 Family of Tours

We denote by \(B_i(p_i,r_i)\) the set of digital points included in the open Euclidean ball centered in \(p_i\) and of radius \(r_i\). Since the digital curves we consider are simple and closed, all indices on the points \(p_i\) are considered modulo n.

Observations

Since by hypothesis for all i \(p_i\) and \(p_{i+1}\) are 4-connected, and all \(r_i\) are integers, we have:

  • if \(r_i > r_{i+1}\) (or conversely), then \(B_{i+1} \subset B_i\) (or conversely);

  • if \(r_i = r_{i+1} =r\), then if \(r=1\), \(B_i \cap B_{i+1} = \emptyset \), otherwise \(B_i \cap B_{i+1} \ne \emptyset \) and \(B_i\) and \(B_{i+1}\) are not included in one another.

  • let \(x \in B_i\) and \(y \in B_{i+1}\) such that x and y are 4-connected. If \(r_i \ne 1\) or \(r_{i+1} \ne 1\), then either x or y (or both) belongs to \(B_i \cap B_{i+1}\).

Let \(\cup B = \cup _i B_i\). Given the knowledge of the curve \(\mathcal {C}\) and \(\cup B\), we now define the family of curves representing all the possible positions for the curve \(\mathcal {C}_0\). We call these curves tours.

A tour \(\gamma \) of \(\mathcal {C}\) is a closed simple curve included in \(\cup B\) that passes through the balls \(B_i\) in the “right order”, so that the original order on the points \(p_i\) is somehow preserved in the tour. The precise definition is given below.

Definition 1

(Tour). A tour of \(\mathcal {C}\) is a digital curve that:

  1. (i)

    is closed, simple, 4-connected and included in \(\cup B\);

  2. (ii)

    can be decomposed into parts \(X_0 \ X_1 \ \dots \ X_i \ \dots \ X_n \ X_0\), where for all i, \(X_i\) is connected, \(X_i \subset B_i\) and \(X_i \ne \emptyset \).

This notion of tour is similar, but more restrictive, than the one introduced in [13] in the context of computational geometry. The curve depicted in red in Fig. 1(b) is an example of a tour.

2.3 Definition of an Imprecise Object: Pixel Labeling

Since tours are closed simple curves, Jordan theorem applies and the complementary of each tour is composed of two connected components: the closed one is the object associated to the tour, the other one will be called its complementary. Any pixel in \(\mathcal {S}\) is in one of the following classes:

  • inside pixels: pixels that are in the object associated with a tour for any tour;

  • outside pixels: pixels that are in the complementary of the object associated with a tour for any tour;

  • uncertain pixels: pixels for which there exist two tours such that the pixel is in the object for one of the tours, and in its complementary for the other one.

From the definition, tours are oriented: they must go from ball to ball following the order of the points of \(\mathcal {C}\). In the following, we assume w.l.o.g. that the digital curve \(\mathcal {C}\) is counter-clockwise oriented.

Definition 2

(Valid Arc). A directed arc between two 4-connected digital points is valid if there exist a tour that uses this arc.

Definition 3

(Mandatory Arc). A directed arc xy is said to be mandatory if x belongs to a ball \(B_i\) of radius 1 and y belongs to a ball \(B_{i+1}\) of radius 1.

Proposition 1

(Necessary Conditions). A directed arc xy between two 4-connected points x and y is valid only if:

  1. (i)

    either xy is a mandatory arc (Note that the reverse arc yx is not valid);

  2. (ii)

    or x and y do not belong to any ball of radius one, and there exists an i such that either x and y belong to \(B_i\) or x belongs to \(B_i\) and y belongs to \(B_{i+1}\);

  3. (iii)

    or x belongs to a ball \(B_i\) of radius 1, y does not belong to any ball of radius 1 but belongs to the ball \(B_{i+1}\);

  4. (iv)

    or y belongs to a ball \(B_i\) of radius 1, x does not belong to any ball of radius 1 but belongs to the ball \(B_{i-1}\).

The arcs verifying one of these properties are called graph arcs.

Proof

Consider an arc a between two 4-connected points x and y in \(\cup B\), such that, by contradiction, a does not fulfill any of the conditions above. We prove that this arc is not valid considering the differents cases below.

  1. (a)

    Suppose that x and y belong to balls of radius 1. By (i), xy is not mandatory. Then x belongs to \(B_i\) of radius 1, and y belongs to \(B_j\) of radius 1 with \(j \ne i+1\). By Definition 1, any tour must go through \(B_i = x = X_i\) and the edge of source x must have its target in \(X_{i+1} \subset B_{i+1}\). Thus, no tour can go through xy, and xy is not valid.

  2. (b)

    Suppose that x and y do not belong to a ball of radius 1. By (ii), there is no i such that x and y belong to \(B_i\) or x belongs to \(B_i\) and y to \(B_{i+1}\). Thus, x and y neither belong to the same \(X_j\) nor to two consecutive \(X_j\) and \(X_{j+1}\) \(\forall j\). From Definition 1, the edge is not valid.

  3. (c)

    Suppose that x belongs to a ball \(B_i\) of radius 1, and y does not belong to any ball of radius 1 (or conversely). By (iii) (or (iv)), y does not belong either to the ball \(B_{i+1}\) (or conversely, x does not belong to \(B_{i-1}\)). Using a similar argument as in (a), xy cannot be valid.

   \(\square \)

Note that the reciprocal is not true: some graph arcs may not be valid arcs, which means that for some of them, there may not exist a valid tour taking this arc. However, we have the following property:

Property 1

Mandatory arcs are valid arcs.

Figure 2(a) is an illustration of graph arcs and mandatory arcs for an imprecise digital contour. We now introduce some properties that enable to classify the pixels using these graph arcs.

Proposition 2

(Initialization). Let a be a mandatory arc, let p be the pixel to the left of a, and q the pixel to the right of a. Then p is inside and q is outside.

Fig. 2.
figure 2

(a) Graph arcs in blue, mandatory arcs in red for the imprecise digital contour depicted in Fig. 1. (b)–(c) Inside pixels in blue, uncertain pixels in orange, outside pixels in white. In (c), the input imprecise digital contour is from [9, 10]: imprecision values are equal to the meaningful scale (Color figure online).

Full size image

Property 2

If the input curve \(\mathcal {C}\) is a simple closed 4-connected curve, there is no pixel p which is both to the left and to the right of mandatory arcs.

Proposition 3

(Diffusion). Let \(p'\) be a pixel 4-connected to an inside pixel p, such that the linel shared by p and \(p'\) does not support a graph arc. Then \(p'\) is inside. (similar property if \(q'\) is 4-connected to q which is outside).

Proof

Suppose \(p'\) is not inside. Then there exist a valid tour \(\gamma \) such that \(p'\) is outside. Since p is inside, p is in the object associated to \(\gamma \). Then, since \(\gamma \) is a valid tour, it is a simple closed curve, and thus a Jordan curve: any path between inside and outside must cross \(\gamma \). As a result, \(\gamma \) must go through the linel shared by \(p'\) and p, which is not possible since this linel does not support a graph arc.    \(\square \)

As a corollary, any pixel bounded by four non mandatory arcs will never be labeled using the diffusion of Proposition 3.

These two propositions directly lead to an algorithm (see Algorithm 1) to label the pixels. Note that if there is no mandatory arc to use Proposition 2, then the initialization can still be done if inside and outside pixels are known as part of the input. Results of this labeling are presented in Fig. 2(b)(c).

figure a

We denote by \(\mathcal {I}\) the set of inside pixels and \(\mathcal {U}\) the set of uncertain pixels, and call imprecise digital object the pair of sets \((\mathcal {I},\mathcal {U})\).

3 Volumetric Analysis

Any object bounded by a tour lies somewhere “in between” the digital object defined by \(\mathcal {I}\) and the digital object defined by \(\mathcal {I}\cup \mathcal {U}\). In the following, we present some tools to study this family of objects.

3.1 Preliminary Definitions

Toleranced balls were introduced in [3] in the context of computational geometry for molecular modelling. They are defined as follows.

Definition 4

(Toleranced Ball). A toleranced ball \(b(c,r^-,r^+)\) is a pair of concentric balls defined by a point c and two radii \(r^-\) and \(r^+\) such that \(0 \le r^- \le r^+\). We denote \(b^-\) (resp. \(b^+\)) the open ball of center c and radius \(r^-\) (resp. \(r^+\)).

In the original setting, the constraint on \(r^-\) and \(r^+\) was \(0 < r^- < r^+\). But as we will see in the next paragraph, we need to relax this constraint in our framework.

Given a collection \(\mathcal {B}\) of toleranced balls, let \(B^- = \cup _{b\in \mathcal {B}} b^-\) and \(B^+ = \cup _{b\in \mathcal {B}} b^+\). We define a filtration of the object \(B^+\) as a nested sequence of objects \(B^- = S^0 \subseteq S^1 \subseteq \dots \subseteq S^m = B^+\). The sequence of objects defining the filtration is parameterized using a function \(\lambda _\mathcal {B}: \mathbb {R}^2 \rightarrow \mathbb {R}\) (later on, the function will be restricted to \(\mathbb {Z}^2\)). For a given \(\lambda ^i \in \mathbb {R}\), let us define the \(\mathbf {\lambda ^i}\) -object as the set of points p such that \(\lambda _\mathcal {B}(p) < \lambda ^i\). For a given increasing sequence of values \(0 = \lambda ^0 < \lambda ^1 < \dots < \lambda ^m\), the \(\lambda ^i\)-objects define a filtration of \(B^+\) if and only if (i) \(\lambda ^0\)-object \(=B^-\), (ii) for all i, \(\lambda ^i\)-object \(\subseteq \lambda ^{i+1}\)-object, and (iii) \(\lambda ^m\)-object \(=B^+\).

The function \(\lambda _\mathcal {B}\) can be seen as a function that governs the way toleranced balls grow from \(b^-\) to \(b^+\). In the next section we show how to define (i) a collection \(\mathcal {B}\) of toleranced balls from an imprecise digital object and (ii) the function \(\lambda _\mathcal {B}\).

3.2 Toleranced Balls of an Imprecise Digital Object

Distance transformation is a classical tool in digital geometry and more generally image analysis for volumetric analysis. The distance transformation of a digital object \(\mathcal {S}\) consists in computing for each pixel of \(\mathcal {S}\) the distance to the closest pixel in \(\bar{\mathcal {S}}\). We denote \(dt_{\mathcal {S}}(p) = \min _{q \in \bar{\mathcal {S}}} (d(p,q))\), where d is a distance on \(\mathbb {Z}^2\). In [5], a very efficient algorithm is presented to compute the exact distance transformation according to the Euclidean distance.

In our setting, the digital object contour is imprecise, so that the distance between a pixel of the object and its complementary is also imprecise. In this context, we define two distance transformations: \(dt_{\mathcal {I}}\) and \(dt_{\mathcal {I}\cup \mathcal {U}}\). For each pixel p in \(\mathcal {I}\) these distance transformations provide information on the smallest and the greatest possible distance between p and a pixel in \(\bar{\mathcal {S}}\) for any object \(\mathcal {S}\) bounded by a tour. For any pixel p in \(\mathcal {U}\), the distance transformation \(dt_{\mathcal {I}\cup \mathcal {U}}(p)\) is the smallest distance between p and a pixel of \(\bar{\mathcal {S}}\) for any object \(\mathcal {S}\) bounded by a tour and that contains p.

We use these two distance transformations to define a toleranced ball for each pixel \(p \in \mathcal {I}\cup \mathcal {U}\) as follows. For any pixel p in \(\mathcal {I}\) we define the toleranced ball \(b(p,dt_{\mathcal {I}}(p),dt_{\mathcal {I}\cup \mathcal {U}}(p))\). Similarly, for any pixel p in \(\mathcal {U}\) we define the toleranced ball \(b(p,0,dt_{\mathcal {I}\cup \mathcal {U}}(p))\). Taking a look back at Definition 4, we note that in this case, we may have \(r^- = dt_{\mathcal {I}}(p) = dt_{\mathcal {I}\cup \mathcal {U}}(p) = r^+\), and for toleranced balls centered on uncertain pixels, we have \(r^- = 0\).

The collection of all the toleranced balls thus defined for a given imprecise digital object is denoted by \(\mathcal {B}\). By construction, for any \(b \in \mathcal {B}\), the open ball \(b^-(c,r^-) \subset I\) and the open ball \(b^+(c,r^+) \subset \mathcal {I}\cup \mathcal {U}\). With the notations introduced in the previous section, we have \(B^-=\mathcal {I}\) and \(B^+=\mathcal {I}\cup \mathcal {U}\) (see Fig. 4(a)).

3.3 Distances

In order to define the function \(\lambda _\mathcal {B}\) which governs the ball growing process, the first thing is to specify the distance between a toleranced ball and a point. Several distances can be defined. In [3], the additively-multiplicatively distance is used: each ball grows linearly with respect to the difference between \(r^-\) and \(r^+\). This definition assumes that \(r^- \ne r^+\).

Definition 5

(Additively-Multiplicatively Distance). Let \(b(c,r^-,r^+)\) a toleranced ball, p a point, and d the Euclidean distance between points of \(\mathbb {Z}^2\). Then \(d_{am}(b,p) = \frac{d(p,c) - r^-}{r^+ - r^-}\).

This signed distance is actually based on the additively weighted distance between a ball b(c, r) and a point p defined as \(d(c,p) - r\). The additively-multplicatively distance is associated with the so-called compoundly-weighted Voronoi diagram [14], which falls in the class of non-linear Voronoi diagrams (bissectors are not linear).

In our framework, some of the toleranced balls may have equal radii, so that we have to take this case into account in the distance definition. When the two radii of the toleranced ball are equal, the ball does not grow (nor deflate), and then can never touch a given point p which is not on its boundary.

Let \(d_b\) be a signed distance between a ball b and a point p, such that \(d_b(b,p) < 0\) if \(p \in b\), \(d_b(b,p) = 0\) si \(p \in \partial b\) and \(d_b(b,p) > 0\) if \(p \notin b\). We propose a new distance between a toleranced ball and a point, that generalizes the additively-multiplicatively distance and introduces a threshold.

Definition 6

Let \(b(c,r^-,r^+)\) a toleranced ball, p a point and \(d_b\) a distance between a ball and a point. Then the function \(d_{tb}: \mathcal {B}\times \mathbb {Z}^2 \rightarrow \mathbb {R}\) is defined as:

$$\begin{aligned} d_{tb}(b,p) = {\left\{ \begin{array}{ll} +\infty &{} \textit{if }p \notin b^+ \\ -\infty &{} \textit{if }p \in b^- \\ \frac{d_b(b^-,p)}{d_b(b^-,p) - d_b(b^+,p)} &{} \textit{if }b^- \ne b^+ \\ 0 &{} \textit{if }b^-=b^+ \textit{ and } d_b(b^-,p)=0 \\ \end{array}\right. } \end{aligned}$$

Note that his definition is quite general since many distances or even semimetrics \(d_b\) can be used. For instance, we recall that the power of a point p with respect to a ball b(c, r) is given by \(d(c,p)^2 - r^2\). Injecting this signed semimetric in the generalized distance defined above, we can make the balls grow linearly with respect to the difference between the squares of the two radii.

However, we have to keep in mind that there are two types of toleranced balls: some toleranced balls which center is in \(\mathcal {I}\) and others for which the center lies in \(\mathcal {U}\). If we make all these balls grow simulaneously using the \(d_{tb}\) distance, the balls centered on uncertain points will start to grow at the same time as the balls centered on inside points. So that if the distance \(d_{tb}\) is used straightforwardly to define \(\lambda _\mathcal {B}\), objects may grow in an unexpected way. In order to take into consideration these different types of balls, we introduce an index \(\eta \) which controls the moment a given toleranced ball begins to grow (see Fig. 4(b)).

Definition 7

(Index). Given a imprecise digital object \((\mathcal {I},\mathcal {U})\) and its collection of toleranced balls \(\mathcal {B}\), we define the index \(\eta : \mathcal {I}\cup \mathcal {U}\rightarrow \mathbb {Z}^+\) as:

$$\begin{aligned} \eta (p) = {\left\{ \begin{array}{ll} 0 &{} \textit{if }\exists b \in \mathcal {B},~ p \in b^-,\\ 1 &{} \textit{if }\exists b \in \mathcal {B}, ~b^- \ne \emptyset \textit{ and }p \in b^+ \setminus b^-\\ \mathop {\min }\nolimits _{b(c,r^-,r^+) \in \mathcal {B}} \{\eta (c) + 1 \ | \ p \in b^+\} &{} \textit{otherwise}. \end{array}\right. } \end{aligned}$$

For some specific pixels in \(\mathcal {U}\), the recursive definition above may not converge. Indeed, a very simple example is the following: consider a pixel \(p \in \mathcal {U}\) such that its toleranced ball is b(p, 0, 1) and p belongs to no other toleranced ball. In this case, the recursion loops. More generally, the only pixels p for which the recursion does not end are pixels in \(\mathcal {U}\) such that for all b containing p, the center of b is a pixel for which the recursion does not end either. An example of such pixels is given in Fig. 3. In order to prevent such configurations, we would have to make some hypothesis on the sets \(\mathcal {U}\) and \(\mathcal {I}\). To overcome this problem without constraining the construction of these sets, we define a maximal value \(\hat{\eta }\) for \(\eta \), which is equal to the maximum of the well defined values \(\eta (p)\) plus one.

Fig. 3.
figure 3

(a) Uncertain pixels in orange, inside pixels in blue, outside ones in white; (b) For the pixels in white the recursive definition of \(\eta \) does not end: the centers of the toleranced balls containing these pixels are never covered during the growing process (Color figure online).

Full size image

We put together the index and the distance \(d_{tb}\) to define a new distance \(\lambda \).

Definition 8

Let \(d_{tb}\) be the distance defined in Definition 6 and \(\eta \) the index map defined in Definition 7. Then the function \(\lambda : \mathcal {B}\times \mathbb {Z}^2 \rightarrow \mathbb {R}\) is defined as:

$$\begin{aligned} \lambda (b,p) = \eta (c) + d_{tb}(b,p). \end{aligned}$$
Fig. 4.
figure 4

(a) Set \(B^-\) in blue, \(B^+\) in orange and blue; (b) Indices: 0 for the green regions, 1 for the yellow ones, 2 for the orange ones and 3 for the red ones; (c) \(\lambda \)-objects using the additively weighted distance: for \(\lambda = 0\) in blue, \(\lambda = 0.5\) in purple and blue, \(\lambda = 1\) in pink, purple and blue and \(\lambda = 1.75\) in yellow, pink, purple and blue (Color figure online).

Full size image

3.4 Toleranced Balls Growing Process

We can now introduce the growth-governing function \(\lambda _\mathcal {B}\).

$$\begin{aligned} \lambda _\mathcal {B}:\mathbb {Z}^2&\rightarrow \mathbb {R}\\ p&\mapsto \min _{b \in \mathcal {B}} \lambda (b,p). \end{aligned}$$

Proposition 4

Given an imprecise object \((\mathcal {I},\mathcal {U})\) and the collection \(\mathcal {B}\) of its toleranced balls, the \(\lambda ^i\)-objects defined using function \(\lambda _\mathcal {B}\), with an increasing sequence of \(\lambda ^i\), with \(\lambda ^0 =0\) and \(\lambda ^m = \hat{\eta } +1\) defines a filtration of \(\mathcal {I}\cup \mathcal {U}\).

Proof

First, we prove that the \(\lambda ^0\)-object is equal to \(B^- = \mathcal {I}\). Let p be a pixel in \(\mathcal {I}\), and consider the toleranced ball \(b(p,r^-,r^+)\) centered on p. By definition, \(b \in \mathcal {B}\), and we have \(d_b(b^-,p) < 0\). Then, \(\lambda _\mathcal {B}(p) < 0\) and p belongs to the \(\lambda ^0\)-object. Conversely, let p be a pixel such that \(\lambda _\mathcal {B}(p) < 0\). This implies that there exist a toleranced ball \(b(c,r^-,r^+) \in \mathcal {B}\) such that \(d_{tb}(b,p) < 0\) and \(\eta (c) = 0\). Thus, p belongs to a ball \(b^-(c,r^-)\) with \(c \in \mathcal {I}\), which proves that p belongs to \(\mathcal {I}\).

Proving that for all i and \(\lambda ^i < \lambda ^{i+1}\), the \(\lambda ^i\)-object is included in the \(\lambda ^{i+1}\)-object is straightforward since a \(\lambda ^i\)-object is defined as threshold on the \(\lambda _\mathcal {B}\) function.

Last, we shall prove that the \(\lambda ^m\)-object with \(\lambda ^m = \hat{\eta } +1\) is equal to \(B^+ = \mathcal {I}\cup \mathcal {U}\). Let \(p \notin \mathcal {I}\cup \mathcal {U}\). Then for all \(b \in \mathcal {B}\), \(p \notin b^+\), so that \(d_{tb}(b,p) = +\infty \) for all b, and thus \(\lambda _\mathcal {B}(p) = +\infty \) and \(p \notin \lambda ^m\)-object. Conversely, let \(p \in \mathcal {I}\cup \mathcal {U}\). Then there exist \(b \in \mathcal {B}\) such that \(p \in b^+\). If \(p \in b^-\), then \(\lambda _\mathcal {B}(p) = -\infty \) and \(p \in \lambda ^m\)-object. Otherwise, for any \(b(c_0,r^-,r^+) \in \mathcal {B}\) such that \(p \in \mathcal {B}\), we have \(\eta (c_0) \le \hat{\eta }\) and \(d_{tb}(b,p) < 1\). As a result, \(\lambda _\mathcal {B}(p) < \hat{\eta } +1\) and \(p \in \lambda ^m\)-object.    \(\square \)

Let us study a little bit more in details which balls compose \(\lambda ^i\)-objects. Given a toleranced ball \(b(c,r^-,r^+)\), the ball b grown by a factor \(\alpha \) is defined as \(b_\alpha = \{p \ | \ d_{tb}(b,p) < \alpha \}\). If the distance between balls and pixels is the additively weighted distance, then \(b_\alpha = b(c,r^- + \alpha (r^+ - r^-))\). If the power distance is used, then \(b_\alpha = b(c,{r^-}^2 + \alpha ({r^+}^2 - {r^-}^2))\). Then we have:

Proposition 5

Given an imprecise object \((\mathcal {I},\mathcal {U})\) and the collection \(\mathcal {B}\) of its toleranced balls, the \(\lambda ^i\)-object is equal to

$$\begin{aligned} (\bigcup _{b \in \mathcal {B}, \eta (c) < \lfloor \lambda ^i \rfloor } b^+) \cup (\bigcup _{b \in \mathcal {B}, \eta (c) = \lfloor \lambda ^i \rfloor } b_{\lambda ^i - \lfloor \lambda ^i \rfloor }) \end{aligned}$$

Proof

Let p be a pixel in the \(\lambda ^i\)-object. This is equivalent to say that there exist a toleranced ball \(b(c,r^-,r^+) \in \mathcal {B}\) such that \(\eta (c) + d_{tb}(b,p) < \lambda ^i\). Only two cases are possible:

  1. 1.

    either \(\eta (c) < \lfloor \lambda ^i \rfloor \) and \(dt_{tb}(b,p) < 1\), so that \(p \in b^+\):

  2. 2.

    or \(\eta (c) = \lfloor \lambda ^i \rfloor \) and \(dt_{tb}(b,p) < \lambda ^i - \lfloor \lambda ^i \rfloor \) and thus \(p \in b_{\lambda ^i - \lfloor \lambda ^i \rfloor }\).

   \(\square \)

An illustration of a sequence of \(\lambda \)-objects for a given collection of toleranced balls is given in Fig. 4 (c), for \(\lambda ^0 = 0\), \(\lambda ^1 = 0.5\), \(\lambda ^2 = 1\) and \(\lambda ^3 = 1.75\). Figure 5(c) shows the \(\lambda \)-objects for the same sequence of \(\lambda ^i\) for the imprecise digital Star object. Moreover, in Fig. 5(a) and (b) we can see the difference between two growth models using the additively weighted distance in (a) and the power distance in (b) (for \(\lambda \) values equal to 0.2, 0.5, 0.7 and 0.9).

Fig. 5.
figure 5

(a)-(b) \(\lambda \)-objects obtained for \(\lambda \in \{0.2,0.5,0.7,0.9\}\) using the additively weighted distance in (a) and the power distance in (b); (c) \(\lambda \)-objects for \(\lambda \in \{0,0.5,1,1.75\}\) using the additively weighted distance; (d) Sites extracted from the \(\lambda \)-Voronoi Map based on the additively weighted distance. The colormap from blue to red and then yellow represents the level \(\tau \) of each site (Color figure online).

Full size image

3.5 Compact Representation of the Filtration

The \(\lambda _\mathcal {B}\) function defined in the previous section gives an information, for each pixel of the imprecise digital object, on the instant this pixel will be reached during the ball growing process. The collection \(\mathcal {B}\) of toleranced balls used in this process counts exactly one toleranced ball per pixel of the imprecise digital object. However, during the growing process, some of these toleranced balls may never be the first to reach a pixel of the object. As a result, these toleranced balls carry redundant information about the imprecise digital object and could be discarded.

Definition 9

( \(\lambda \) -Voronoi Map). Given a collection \(\mathcal {B}\) of toleranced balls, the \(\lambda \)-Voronoi region of a ball \(b \in \mathcal {B}\) is defined as \(R_b = \{p \ | \ \lambda (b,p) < \lambda (b',p) \ \forall b' \in ~\mathcal {B}\}\).

The \(\lambda \)-Voronoi Map is defined on the set of pixels \(B^+\) for a given collection of toleranced balls \(\mathcal {B}\). The set of regions is a tessellation of \(B^+\).

Definition 10

(Sites). Given a collection \(\mathcal {B}\) of toleranced balls, a site is a toleranced ball with a non empty \(\lambda \)-Voronoi region. The level \(\tau \) of a site \(b_s\) is defined as \(\tau (b_s) = min \{\lambda (b_s,p) \ | \ p \in R_{b_S}\}\).

This approach is similar to the extraction of the medial axis from the squared Euclidean distance transformation [5]: the points of the medial axis are the ones with a non empty region in the power diagram defined with all the balls computed from the distance transformation. Similarly to the medial axis, it is straightforward to show that any \(\lambda \)-object can be reconstructed from the set of sites (see Fig. 5(d) for an illustration).

Proposition 6

(Reconstruction). Given a collection \(\mathcal {B}\) of toleranced balls, any \(\lambda ^i\)-object can be reconstructed from the set of sites \(b_s\) such that \(\tau (b_s) < \lambda ^i\) using Proposition 5.

4 Discussion

In this paper, we introduced a new framework to undertake contour and volumetric analysis of digital objects taking into account the imprecision of the input data. To conclude, we would like to open the discussion on several key points and potential perspectives.

Model. Section 3 was devoted to the definition of a growth model based on the \(d_{tb}\) distance function. Using this function, the growth speed of each toleranced ball depends somehow on the difference between the two radii. We could easily define a similar function that would lead to a uniform growth speed for all the balls. With such a setting, we may build on well-known results on the Voronoi Diagram stability through growth process. Indeed, if the rule to grow each ball is to increase the square radius \(r^2\) to \(r^2 +t\) at time t, then the Power Voronoi Diagram of these balls is constant at all times [7].

Finally, every growth model leads to different \(\lambda ^i\)-objects and there is a need to define criteria (maybe depending on the application) to compare these models.

Algorithms. The results were obtained using brute-force algorithms, which leads to a worst-case complexity of \(\mathcal {O}(n^2)\) for an image with n pixels for all the computations (graph, \(\lambda \) values, sites). When volumetric analysis is concerned, all comes down to the computation of the \(\lambda \)-Voronoi Diagram for a collection of toleranced balls. Indeed, the \(\lambda \) values for each point can be easily retrieved from this diagram. Unfortunately, the distance \(\lambda \) used to compute the \(\lambda \)-Voronoi diagram is not separable [4] so that very efficient separable algorithms cannot be applied straightforwardly.

Implementation. Algorithms were implemented using the open-source libraries DGtal [1] for the digital geometry part, and Lemon [2] for the graph part. In particular, distance transformations according to the exact Euclidean distance were computed using the state-of-the-art algorithm from [5] available in DGtal. However, the distance introduced in this work involve non integer computations, that may lead to slightly incorrect results (for instance incorrect reconstruction) due to unintentional rounding operations.

To Go further. The second part of this work about volumetric analysis could actually be applied to other imprecise digital objects inputs: the only requirement is for the imprecise digital object to be defined as a pair of sets of inside and uncertain pixels. One could imagine to extract this kind of information using a segmentation algorithm on gray level images. Similarly, this volumetric study may also be extended to 3D imprecise digital objects quite easily.

Finally, an ultimate objective when volumetric analysis is concerned is to compute the medial axis of the object. A first step towards the definition of the medial axis of an imprecise digital object could be to compute the medial axis for well chosen sample of \(\lambda ^i\)-objects, and study the evolution of the positions and radii of the centers computed.