Keywords

1 Introduction

Geometry is historically the field of mathematics dealing with objects and their properties: length, angle, volume, shape, position and transform. The word Geometry stems from the ancient greek words for Earth and Measure. Geometry was the science of shapes and numbers as practical tool for measuring fields, distances between far away places, volumes for commerce, etc. For centuries, properties were proven and geometric objects were constructed based on construction rules. Euclid with his manuscripts Elements, revolutionized geometry with his formalization of abstract reasoning in mathematics and more significantly in geometry. The second revolution was brought upon by René Descartes with the introduction of coordinates. This marked a profound change in the way geometry was considered. It established a link between Euclidean geometry and algebra: Analytical Geometry was born. Many advances were now possible in astronomy, physics, engineering, etc. Many different forms of geometries have since been proposed such as Differential geometry, Algebraic geometry, etc.

Digital Geometry is one of the most recent forms of geometry. It can be broadly defined as the geometry of digital objects and transforms in a digital space. In this paper we are mainly considering digital points with integer coordinates (points in \(\mathbb {Z}^n\)). Digital Geometry has the particularity of, usually, not being an independent geometry but a digital counterpart of Euclidean geometry. Digital objects are supposed to behave and look as much as possible as their continuous counterpart. This question of representing/coding the continuous world in a finite computer is, of course, not limited to digital geometry. From the beginning, when sensors went from analog to digital and when the display mode went from continuous (vector monitor) to digital (raster graphics), the fundamental question of object and space definition has been raised. It proved more elusive than initially thought [49]. Elementary rules of topology or geometry, that seem so obvious that they have been raised to the axiomatic status by Euclid, have proven to be false in Digital Geometry [20]: two, non identical, parallel 2D digital straight lines can have an infinite number of intersection points while two orthogonal 2D digital straight lines may have no intersection point. Particular versions of the Jordan theorem had to be divised that are in some sense specific to digital geometry [55].

This confrontation between the digital and the continuous worlds has given birth to various theories. One way of solving this hiatus is to consider the digital information as a sampled version of continuous information. The digital world is an approximation where information has been lost. Signal Theory provides the theoretical toolkit. Although one of the most efficient approaches when it comes to handling digital information (image processing, image analysis), it does little in helping defining actual geometry. It does not really provide any tool if one wants to draw, for instance, a line on a screen. We are considering another approach that finds its origins in the question of drawing digital equivalents of continuous objects on a raster screen (or earlier on, on a plotter). Digital Geometry is, in this sense, more closely linked to computer graphics or arithmetics. As for the continuous geometry, digital geometry started out focusing on very concrete and basic questions: how can one generate a digital analog of a continuous object for visualization purposes? This algorithmic approach has prevailed for many decades, with algorithms such as the Bresenham Digital Straight line drawing algorithm or Arie Kaufman et al. that proposed many digital primitive generation algorithms [40–42, 47, 48, 61]. The main drawback of such an algorithmic approach is that it is difficult to ensure global properties from the local construction scheme. The other problem with a definition by construction is that you can only generate finite digital objects. As an alternative, researchers tried to describe and categorize digital objects not as a result of an algorithm but as digital classes with properties, be it geometrical or, more generally, topological [34, 38, 44, 45, 51, 56]. This allows to define (classes of) digital objects that are infinite and without boundaries such as planes or surfaces in general. This approach proved useful to construct object classes with desired properties but it proved difficult to ensure tightness for the classes. And, as for the continuous geometry, analytical characterization of digital objects has proven to be effective in describing objects and the related transforms. It is a bit early to claim that it will revolutionize Digital Geometry but it allowed new insight and brought new tools for the definition of digital objects, in pattern recognition and design of digital transforms. Consider this paper as a short introduction paper into digitization transforms in general and Digital Analytical Geometry in particular.

In Sect. 2, we are going to discuss different types of digitizations. In Sect. 3 we are going to focus on digital analytical objects. We will then conclude and propose some perspectives.

2 Digitization

2.1 Notations

Let us denote n the dimension of space (digital or Euclidean) in this paper. Let \(\{{e_1},\dots ,{e_n}\}\) denote the canonical basis of the n-dimensional Euclidean vector space and O the center of the associated geometric coordinate system. Let \(\mathbb {Z}^n\) be the subset of \(\mathbb {R}^n\) that consists of all the integer coordinate points. A digital (resp. Euclidean) point is an element of \(\mathbb {Z}^n\) (resp. \(\mathbb {R}^n\)). We denote by \(x_i\) the i-th coordinate, associated to \(e_i\), of a point or a vector x. A digital (resp. Euclidean) geometric object is a set of digital (resp. Euclidean) points. A digital inequality is an inequality with coefficients in \(\mathbb {R}\) from which we retain only the integer coordinate solutions. A digital analytical object is a digital object defined as union and intersection of a finite set of digital inequalities. The family of sets over \(\mathbb {Z}^n\) (resp. \(\mathbb {R}^n\)) is denoted \(\mathfrak {P}\left( \mathbb {Z}^n\right) \) (resp. \(\mathfrak {P}\left( \mathbb {R}^n\right) \)). A digitization is a transform from sets in the Euclidean to sets in the digital world: \(\varDelta :\mathfrak {P}\left( \mathbb {R}^n\right) \rightarrow \mathfrak {P}\left( \mathbb {Z}^n\right) \).

For all \(k\in \{0,\dots ,n-1\}\), two integer points v and w are said to be k-adjacent or k-neighbors, if for all \(i\in \{1,\dots ,n\}\), \(|v_i-w_i|\le 1\) and \(\sum _{j=1}^{n}|v_j-w_j|\le n-k\). In the 2-dimensional plane, the 0- and 1-neighborhood notations correspond respectively to the classical 8- and 4-neighborhood notations. In the 3-dimensional space, the 0-, 1- and 2-neighborhood notations correspond respectively to the classical 26- ,18- and 6-neighborhood notations [5, 6, 55].

A k-path is a sequence of integer points such that every two consecutive points in the sequence are k-adjacent. A digital object \(\mathrm {E}\) is k-connected if there exists a k-path in \(\mathrm {E}\) between any two points of \(\mathrm {E}\). A maximum k-connected subset of \(\mathrm {E}\) is called a k-connected component. Let us suppose that the complement of a digital object \(\mathrm {E}\), \(\mathbb {Z}^n\setminus \mathrm {E}\) admits exactly two k-connected components \(\mathrm {F}_1\) and \(\mathrm {F}_2\), or in other words that there exists no k-path joining integer points of \(\mathrm {F}_1\) and \(\mathrm {F}_2\), then \(\mathrm {E}\) is said to be k-separating in \(\mathbb {Z}^{n}\). If there is no path from \(\mathrm {F}_1\) to \(\mathrm {F}_2\) then \(\mathrm {E}\) is said to be 0-separating or simply separating. A point v of a k-separating object \(\mathrm {E}\) is said to be a k-simple point if \(\mathrm {E}\setminus \{{v}\}\) is still k-separating. A k-separating object that has no k-simple points is said to be strictly k-separating. The notion of k-separation is defined for digital surfaces without boundaries. See [24] for more general notions.

For A and B two subsets of \(\mathbb {R}^n\), \(A \oplus B = \left\{ a+b: a\in A, b\in B\right\} \) is the Minkowski sum of A and B. Let us denote \(\check{A}=\left\{ -a : a\in A\right\} \) the reflection set of A. Let us denote \(\overline{A}\) the flat of smallest dimension containing A. For a distance d, then the let us denote \(\mathcal {B}_{d}(r)=\left\{ x \in \mathbb {R}^n: d(x,O) \le r\right\} \), the ball of radius r for the distance d. Let us denote \(d_1\), \(d_2\), \(d_\infty \) respectively the Manhattan, Euclidean and Chebychev distance. Let us denote \(\Vert x \Vert _k\) the corresponding norm (with \(k=1,2,\infty \)).

2.2 General Remarks on Digitizations

Let us first start with some general remarks about digitization methods. The digitization of objects is fundamentally an ill-defined problem [49]: any digital objects can be considered as the digitization of any continuous object. Usually the goal is to have digital objects that ressemble the continuous object. The resulting digital objects may keep some, but not all, properties of the continuous object [21, 24, 52, 53]. See [21, 53] for a more formal presentation of a link between the continuous and the digital worlds based on non-standard analysis.

A digitization is defined broadly as a transform from the family of Euclidean sets to the family of the digital sets. However, most of the literature deals with digital objects defined as digitization of specific classes of geometric objects [1, 2, 9, 12, 13, 15, 26, 27, 30–32, 40–42, 47, 48, 61–63]: for instance, the Bresenham digital straight line segment generation algorithm [12] works only for continuous straight line segments between two digital points. In this case, the digitization transform is usually implicit. The fact that the digitization scheme is not explicitely defined is also an important problem for pattern recognition: comparing two digital circle recognition algorithm supposes that the underlying digital circles are defined in the same way or otherwise it is like comparing apples to oranges. Other digitization transforms are defined only for linear objects [5, 6] and others still for all objects [7].

Let us mention some classes of digitization transforms that are important: A general digitization is a digitization that is defined for all continuous objects. A coherent digitization transform \(\varDelta \) verifies the following property \(E \subset F \Rightarrow \varDelta (E) \subset \varDelta (F)\).

2.3 Morphological Digitizations

Let us build a narrative for the construction of a general, coherent digitization transform \(\varDelta \). For a geometric object E, how can we build its digital counterpart \(\varDelta (E)\) that ressembles E? Simply considering that \(\varDelta (E)=E \cap \mathbb {Z}^n\) is not a good idea. There are no particular reasons for E to pass through digital points and we may end up with \(\varDelta (E)=\varnothing \). So let us consider points that are close to E:

$$\begin{aligned} \varDelta (E)=\left\{ p \in \mathbb {Z}^n: d(p,E) \le r\right\} , \text { where } d \text { is a distance and } r \in \mathbb {R} \end{aligned}$$
(1)

There are some important immediate properties that go with such a definition: \(\varDelta (E \cup F) = \varDelta (E) \cup \varDelta (F)\) and \(E \subset F \Rightarrow \varDelta (E) \subset \varDelta (F)\), which is a stronger version of the coherence property. These are fundamental properties when it comes to digital modeling of complex objects. It defines a general, coherent digitization transform. There are two parameters to work with: the distance d and a thickness parameter r. Let us note that the parameter r can also be defined as a function. See [9, 32, 63] for examples of digital objects defined with a non-constant thickness. Considering the points that are close to the original continuous object seems reasonable if we want the digital object to look like the original. There are also theoretical reasons for such a choice [21, 53].

If a point p verifies \(d(p,E)\le r\) then a ball \(\mathcal {B}_{d}(r)\) of radius r, for the distance d, centered on p intersects E which leads to the following formulation:

$$\begin{aligned} \varDelta (E)=\left\{ p \in \mathbb {Z}^n: \left( \mathcal {B}_{d}(r) \oplus p\right) \cap E \ne \varnothing \right\} \end{aligned}$$
(2)

This type of digitization method is part of digitization methods called morphological digitization [37, 46, 54, 59, 60] with \(\mathcal {B}_{d}(r)\) as structuring element.

Classically, the distances that have been considered are the Manhattan, the Euclidean and the Chebychev distances. An interesting set of distances well adapted for digitization transforms is the set based on adjacency norms [63]. Every digital adjacency relationship can be associated to a norm.

Definition 1

For an integer k, \(0 \le k <n\), the k-adjacency norm \( {[\cdot ]}_k\) is defined as follows: \(\forall x\in \mathbb {R}^n, {[x]}_k=\max \left\{ {\Vert x\Vert }_\infty ,\frac{{\Vert x\Vert }_1}{n-k}\right\} \).

These distances are interesting because they verify the following property [63]: Let \(p,q\in \mathbb {Z}^n\), then, p and q are k-adjacent iff \({[p-q]}_k\le 1\). See Fig. 1 for adjacency distance balls.

Fig. 1.
figure 1

2D and 3D balls for the adjacency distances and the corresponding Flakes [63].

Full size image

For morphological digitizations [37, 43, 46], the structuring element is not necessarily a distance ball as in formula (2). One can consider any continuous object F as structuring element and define a digitization transform of a continuous object E by [46]:

$$\begin{aligned} \varDelta (E)=\left\{ p \in \mathbb {Z}^n: \left( \check{F} \oplus p\right) \cap E \ne \varnothing \right\} \end{aligned}$$
(3)

The region \(\left\{ x \in \mathbb {R}^n: \left( \check{F} \oplus x\right) \cap E \ne \varnothing \right\} \) is called the offset region. Formulation (3) has implicitly already been used in digitizations such as the grid intersection digitization [43] with half-open structuring elements. This is also the starting point for the analytical characterization of digital objects with the analytical description of the offset region. Note that, for an arbitrary structuring element F, it is the reflection \(\check{F}\) that appears in formula (3) (Fig. 2).

Fig. 2.
figure 2

This figure has been proposed in [46]. (a) \(\left\{ p \in \mathbb {Z}^2: F\oplus p \ne \varnothing \right\} \) (b) \((\check{F} \oplus E)\cap \mathbb {Z}^2\). The region in gray in (b) is called the offset zone.

Full size image

3 Analytical Characterization of Digital Objects

Let us first define what we understand by analytical characterization of a digital object: a digital object is defined by a set of equations (inequalities typically). A point belongs to the digital object iff it verifies the set of equations. The cardinality of the set of equations should be independent of the number of digital points of the object. The analytical characterization of digital objects has a great interest in digital geometry. A digital object is defined in comprehension and not as a voxel enumeration. Infinite digital objects can be represented. This was also one of the reasons for trying to define digital objects based on topology [34, 38, 44, 45, 51, 56]. The key to the analytical characterization is that it allows a characterization of digital objects with interesting topological properties.

Since Reveilles proposed the analytical characterization of digital straight lines [52], many papers have been proposed that describe or discuss properties of analytical digital objects. Those papers can be roughly classified into two groups:

  • Direct defined Analytical Digital Object: Papers that introduce an analytical definition of digital objects or classes of objects, or that analytically characterize previously known digital objects. Those objects are defined directly in the digital space without being explicitely associated to a digitization transform.

  • Digitized Analytical Objects: papers that introduce a digitization transform that allows an analytical characterization of digital objects.

3.1 Direct Defined Analytical Digital Objects

Let us first list some of the digital objects that have been directly analytically defined in the digital space without an explicite reference to a digitization transform. The list is of course not exhaustive.

Digital Analytical Hyperplane: The first class of digital object that has been analytically characterized has been the digital straight 2D line [19, 25]. It was J-P. Reveilles that proposed an analytical description of a Digital Straight Line (DSL) \(0 \le ax-by+c < \omega \) [52] with a thickness parameter \(\omega \) that allows a parametrization of its topology. He also made an explicit link between digital straight lines, topology, quasi-affine transforms and arithmetics [10, 23, 39, 52]. Many papers have been devoted to its study. Indeed, the structure of digital straight lines is rich, with immediate links to word theory, the Stern-Brocot tree, the Farey sequence, etc. It allows a natural extension to higher dimensions [1, 27, 52] with the analytical characterization of digital hyperplanes:

$$\begin{aligned} H: 0 \le a_0+\sum _{i=1}^{n}a_i x_i < \omega . \end{aligned}$$
(4)

See [18, 43] for a survey of digital linearity and planarity with interesting historical perspectives and useful comments and references on digital analytical lines and hyperplanes. An important step in bringing different theoretical approaches together, was to establish a link between the thickness of digital hyperplanes and topology [1]: let us assume, w.l.o.g. that \(0 \le a_1\le \ldots \le a_n\), the digital hyperplane \(0 \le a_0+\sum _{i=1}^{n}a_i x_i < \omega \) is k-separating iff \(\omega \ge \sum _{k+1}^{n}a_i\). With \(\omega = \sum _{k+1}^{n}a_i\) the digital hyperplane is strictly k-separating, without simple points. Papers have been devoted to the study of different classes of digital hyperplanes such as naive hyperplanes [1], supercover hyperplanes [3, 4, 7], Graceful lines and planes [15, 16], etc. An interesting sequence of papers has focused on the connectivity of digital analytical hyperplanes [8, 17, 39]. The problem proved to be quite difficult when it comes to digital analytical (hyper)planes with irrational coefficients. Several papers have dealt with topology especially in order to define a notion of digital surface [33, 34].

Digital Analytical Hyperplanes have been defined as purely analytical digital objects. It is however quite easy to associate a digitization transform to digital analytical hyperplanes. The most obvious way is to center a digital hyperplane on the continuous hyperplane: for \(H: a_0+\sum _{i=1}^{n}a_i x_i=0\), we define \(\varDelta (H)= \left\{ p \in \mathbb {Z}^n: \frac{\omega }{2} \le a_0+\sum _{i=1}^{n}a_i x_i < \frac{\omega }{2}\right\} \). Note that the Bresenham line [12] is such a centered Reveilles line [52]. There is the question of orientation of the digital hyperplane: with a definition such as \(0 \le a_0+\sum _{i=1}^{n}a_i x_i < \omega \), on which side do we put the “’\(\le \)” and the “\(<\)”. One can easily switch side and obtain \(0< \omega -a_0 +\sum _{i=1}^{n}(-a_i) x_i \le \omega \), so a choice has to be made. This question is somewhat difficult if we want coherent digitization models, so let us focus a moment on so called closed analytical digital hyperplanes \(0 \le a_0+\sum _{i=1}^{n}a_i x_i \le \omega \) (with two “\(\le \)”). Let us suppose that we have a digitization transform \(\varDelta \) that is defined for hyperplanes such that, for a continuous hyperplane \(H:a_0+\sum _{i=1}^{n}a_i x_i =0\), we have \(\varDelta (H)= \left\{ p \in \mathbb {Z}^n: \frac{\omega }{2} \le a_0+\sum _{i=1}^{n}a_i x_i \le \frac{\omega }{2}\right\} \). Under some conditions, it is possible to take this as a starting point for the construction of a general, coherent morphological digitization transform:

Definition 2

For some classes of digitization transforms \(\varDelta \) defined for hyperplanes, one can extend \(\varDelta \) as a general and coherent morphological digitization with a structuring element \(\varDelta (O)\) that is defined by:

$$\text {For }x \in \mathbb {R}^n,\varDelta (O) = \bigcap _{\forall H \supset O} \varDelta (H).$$

The idea behind this definition is basically the following: For a digitization transform to be coherent, it has to verify the condition \(E\subset F \Rightarrow \varDelta (E)\subset \varDelta (F)\). \(\varDelta (O)\) has to belong to the digitization of all the hyperplanes that pass through the coordinate center O. If we consider the equality, we basically define the digitization of a point which in this case can serve as structuring element for the morphological digitization transform. The difficulty lies in the choice of \(\omega \) for the digitization transform: for a hyperplane H, we want \(\varDelta (H)\) to be equal to \(\bigcup _{x \in H}\varDelta (x)\) and that is of course not true for any random choice of \(\omega \). There are classes of digital hyperplane thickness that work, namely those that correspond to the optimal hyperplane thickness for it to be k-separating: \(\omega \) is equal to the sum of the absolute values of the \(n-k\) biggest coefficients of H. These thicknesses correspond to the adjacency norm \(\left[ .\right] _k\) based digitization transforms. It is interesting to note that, for these digitizations, the structuring element is a polytope and therefore all the linear objects, at least, can be described analytically as linear digital objects (with linear inequalities). The best known of such digitization transforms is the Supercover model [3, 4, 7, 20, 22, 24, 43, 46, 57, 59]. One other thickness that works is \(\omega = \sqrt{\sum _{i=1}^{n}{a_{i}^2}}\). The corresponding structuring element \(\varDelta (O)\) is the unit hypersphere. The associated norm is the Euclidean norm. What other thicknesses work is an interesting open question.

Andres Hypersphere: The second class of digital objects that have been defined directly as digital objects are the so called Andres hyperpsheres [2, 63]: \(S=\left\{ x\in \mathbb {Z}^n: \omega _1 \le \sum _{i=1}^{n} \left( x_i-c_i\right) ^2 < \omega _2 \right\} \) where c is the center of the digital hypersphere and \(\sqrt{\omega _2}-\sqrt{\omega _1}\) its (Euclidean) thickness. The same method (as for the hyperplanes) of centering the spherical shell can be used to associate a digitization transform. The Andres hypersphere has been proposed to overcome the limitation of the Bresenham circle [13] in particular that is only defined for integer radius, integer coordinate center and that, at the time, did not have an analytical characterization. There is one now [9, 63]. An interesting property of such Andres hyperspheres is that concentric Andres hyperspheres pave digital space. This is quite useful for applications such as simulation of wave propagation [50].

n D Straight Lines: Flats in general have not been studied that much with the notable exception of straight lines: 2D analytical lines [52], 3D analytical lines [28, 31], graceful lines [16], analytical nD lines [30]. The study of Digital Analytical Lines has gained a lot of traction in the arithmetical community [11] for its link to word theory. It is interesting to note that I. Debled-Rennesson’s 3D line is defined as the intersection of two orthotropic naive 3D planes (thinnest planes without 6-connected holes) and thus is an analytically defined 26-connected object. However, contrary to what one could think, the 3D line one would obtain by considering naive planes and intersecting them to define a morphological digitization is usually not 26-connected. The choice of the two planes among three possible orthotropic planes depends on the orientation of the 3D line. I am not quite sure that there exists a corresponding 3D plane thickness (and thus a corresponding general digitization transform) that would define such digital 3D lines. It is an interesting question and it shows that direct analytical definitions for digital objects may lead to interesting topological properties.

Other Purely Analytically Defined Digital Objects: There are other analytically defined objects that could be considered as purely analytically defined digital objects. Let us just mention some approaches that are particularly interesting: The team around I. Debled-Rennesson proposed the notion of Blurred analytical objects [29] with applications in noisy digital object recognition. E. Andres, M. Rodriguez et al. proposed a notion of analytically characterized digital perpendicular bisector [8] which allowed to tackle the problem of the computation of a circumcenter of several pixels and the recognition of fuzzy circles. One could add Y. Gerard and L. Provost that proposed a notion of analytically defined curves and surfaces, named Digital Level Layers [36]. Although based on a morphological digitization, the objects are purely analytically defined.

3.2 Digitized Analytical Objects

In this section, we are going to take a look at digitized objects that have been analytically characterized. An immediate example is the Bresenham Straight line Segment [12] that has been shown to be a Reveilles straight line segment [52]. In the same way, in [9], most notions of digital circles that have been introduced have been analytically characterized [13, 47]. An extension to higher dimensions has been proposed in [63] with an explicit mention of Morphological Digitizations. Let us start with morphological digitization transforms.

Supercover Digitization: One of the first analytically characterized digitization model that has been proposed is the supercover digitization (also called outer Jordan digitization [22, 43]) based on the Chebychev distance \(d_{\infty }\) [3, 4, 7, 20, 22, 24, 43, 46, 57, 59]. The supercover digitization is well-known for a long time because it has a natural geometric interpretation. The unit ball for the distance \(\mathcal {B}_{d_{\infty }}\left( \frac{1}{2}\right) \) is a hypercube of side one. If we denote \(\mathcal {V}(p)\) the voxel centered on p, Formula (2) for the Chebychev distance is the same as \(\left\{ p \in \mathbb {Z}^n: \mathcal {V}(p) \cap E \ne \varnothing \right\} \): a point belongs to the supercover of a continuous object E iff the corresponding voxel is cut by E. The union of all the voxels of the supercover of a continuous object covers the continuous object, thus the name supercover. This geometric interpretation is so natural that it has been considered long (actually as early as the 19th century [22]) before the link to the Chebychev distance has been made. We will not recall all the details on the supercover model: see [24] for general properties of the digitization transform. In [3, 4, 7] for the analytical characterization of the supercover digitization of m-simplice and m-flats in dimension n. In [63], the reader will find an analytical characterization of supercover 2D circles and 3D spheres.

Standard Digitization: The supercover digitization transform has many interesting topological properties. In particular, a supercover digitization of a connected object is always \((n-1)\)-connected and tunnel-free but not strictly separating. When E crosses and edge or a vertex of a grid voxel then all the grid points whose voxel share this edge or vertice belong to the digitization. This is called a bubble [3, 4, 7]. The supercover of a hyperplane, for instance, is \((n-1)\)-connected but with possibly simple points. For theoretical [33–35] as well as practical reasons, it is interesting to have a model without bubble. Various methods have been proposed to solve this problem such as modifying the definition of a voxel [24] but that does not work [5, 6]. There is however a way to solve this problem [5, 6]. The idea is the following: the supercover \(\mathbb {S}(H)\) of a hyperplane \(H:a_0+\sum _{i=1}^{n}a_i x_i = 0\) is given by \(\mathbb {S}(H): -\frac{\sum _{i=1}^{n}\left| a_i\right| }{2} \le a_0+\sum _{i=1}^{n}a_i x_i \le \frac{\sum _{i=1}^{n}\left| a_i\right| }{2}\). It is \((n-1)\)-connected, tunnel-free but it might have simple points (bubbles). The analytical hyperplane \(-\frac{\sum _{i=1}^{n}\left| a_i\right| }{2} \le a_0+\sum _{i=1}^{n}a_i x_i < \frac{\sum _{i=1}^{n}\left| a_i\right| }{2}\) is \((n-1)\)-connected, tunnel-free and strictly separating (without bubbles). The only difference comes from the “\(\le \)" for the hyperplane supercover that is replaced by a “\(<\)" for the analytical hyperplane. So transforming one into the other comes down to choosing a side on which we change a “\(\le \)" into a “\(<\)". We define therefore an orientation convention: A halfspace \(H:a_{0}+\sum _{i=1}^{n}a_{i} x_i \le 0\) is said to have a standard orientation iff \(a_1>0\) or \(a_1=0\) and \(a_2>0\) or \(\ldots \) if \(a_1=\ldots =a_{n-1}=0\) and \(a_n>0\). Otherwise the halfspace is said to have a supercover orientation.

Since the defining structuring element for the supercover digitization transform is a unit hypercube, it is easy to see that the offset zone for a supercover linear object is a polytope defined as intersection of a finite sequence of digital half-spaces \(\mathbb {S}(E)=\left\{ p \in \left( \bigcap _{i=1}^{k} H_i\right) \cap \mathbb {Z}^n; H_i:a_{i,0}+\sum _{j=1}^{n}a_{i,j} x_j \le 0\right\} \) where k is the cardinality of the set of halfspaces \(\left\{ H_i\right\} \) defining the supercover of E. For such a set of halfspaces, we replace each halfspace \(H_i:a_{i,0}+\sum _{j=1}^{n}a_{i,j} x_j \le 0\) that has a standard orientation by \(H'_i:a_{i,0}+\sum _{j=1}^{n}a_{i,j} x_j < 0\) in the analytical characterization of the digital object. If the halfspace has a supercover orientation, it is not modified. This defines the standard digitization transform \(\mathbb {S}t(E)\) of a linear Euclidean object E. It has been shown in [14] that the standard digitization produces \((n-1)\)-connected, tunnel-free and strictly separating objects. See Figure 3 for examples of the standard digitization of points and a 3D triangle. The standard model keeps most of the properties of the supercover model and as such is a coherent digitization. It is not general however as it is defined only for linear objects. There is however a caution. Contrary to the supercover digitization, in general, \(\mathbb {S}t(E) \ne \bigcup _{x \in E}\mathbb {S}t(x)\). The standard digitization is defined as a finite rewriting of the inequalities defining the supercover of a linear object. It does not hold for an infinite sequence of inequalities.

Fig. 3.
figure 3

Standard and Supercover digitization of points on the left and digitization of a 3D triangle on the right.

Full size image

Grid Intersection Digitization: A popular digitization scheme is called grid intersection digitization [57]. For a continuous object E, the intersection points of E and the grid lines (all the straight lines \(x_i=k, k\in \mathbb {Z}\)) are considered and the closest grid point to these intersection points forms the digital object. This is the same as considering a structuring element corresponding to the set of polygons with vertices \(\left( 0,\ldots ,0,\pm \frac{1}{2},0,\ldots ,0,\pm \frac{1}{2},0,\ldots ,0\right) \). It is very similar to the digitization with the Manhattan distance \(d_1\). While the unit ball for this distance is a diamond shaped polytope with all the above mentioned points as vertices. The digitization is defined for all k-dimensional objects, \(k>0\). Analytical characterization can be obtained by computing the intersection of the object with one of the orthotropic faces of the structuring element or by determining the analytical charcterization of the \(d_1\)-distance digitization. The Bresenham line [12] is such an object and its characterization has been given in [52] by JP. Reveilles. In [9, 63] there is the analytical characterization of \(d_1\) digital circles and spheres.

Flake Digitization [58, 62]: The analytical characterization of the supercover of a sphere S is quite complicated [63]. Most (in the geometric sense) of the offset region corresponds however simply to a translation of the continuous sphere S. Indeed, the outer and inner boundary of \(\mathcal {B}_{d_{\infty }} \oplus S\) is in great part determined by the vertices of the ball. Let us call \(V_\infty \) the set of vertices of \(\mathcal {B}_{d_{\infty }}\) then \(V_\infty \oplus S\) corresponds largely to the same surface than the boundary of \(\mathcal {B}_{d_{\infty }} \oplus S\). If we consider a structuring element F composed of straight line segments that join the vertices v of \(\mathcal {B}_{d_{\infty }}\) to its reverse \(\check{v}\) then \(F \oplus S\) is \((n-1)\)-connected and tunnel-free if S is big enough (details of S need to be bigger than a voxel [58, 62]). This is true, not only for the supercover model but for all structuring elements that are polytopes, especially those corresponding to adjacency norms. The distinctive advantage is that this digitization transform is very simple to characterize analytically if the surface S is defined by an implicit equation \(f(x)=0\) such that there is a side of the surface where \(f(x)<0\) and a side where \(f(x)>0\). Let us suppose we have a surface S defined by such an implicit equation \(f(x)=0\), \(x\in \mathbb {R}^n\). Let us suppose that we have a structuring element F which is a polytope, with central symmetry (for the sake of simplicity here). The vertices of F form the set \({v_i}\). Let us define the Flake \(F'\) formed by the straight lines joining the vertices \(v_i\) to its symmetric \(\check{v_i}\) (See Fig. 1). Then \((F' \oplus S)\cap \mathbb {Z}^n\) is analytically characterized by:

$$\begin{aligned} \left\{ p \in \mathbb {Z}^n: \min _{i=1}^{n}\left( f(v_i)\right) \le 0 \wedge \max _{i=1}^{n}\left( f(v_i)\right) \ge 0\right\} \end{aligned}$$
(5)

The idea is actually very simple: as morphological digitization, the surface S cuts a structuring element \(F' \oplus p\) iff there are vertices on each side of the surface defined by the implicit equation. The so-defined Flake digitization transform \((F' \oplus S)\cap \mathbb {Z}^n\) is similar to \((F \oplus S)\cap \mathbb {Z}^n\) except may be on places where S does not fit some regularity properties [62]. The flake digital object keeps the topological properties of the original object. This is a way of defining implicit digital objects is straightforward way with the limitation that it is defined only for \((n-1)\)-dimensional surfaces that are regular enough. See Fig. 4 for an example of a implicitly defined quadric digitized with all three 3D adjacency flakes.

Fig. 4.
figure 4

Flake digitizations of the quadric \(9x^2-4y^2-36z-180=0\).

Full size image

4 Conclusion and Perspectives

In this paper we propose a short survey on digital analytical geometry and show what the ideas are behind the analytical characterization of digital objects. There are two key points in digital analytical geometry that we have not addressed in this paper due to space: transforms and object recognition. Both profit greatly of the analytical characterizations of digital objects. For the transforms, let us just cite the Quasi-Affine Transforms [23] among many others. For Object Recognition, having mathematical definitions of objects changes many things. Much has not been said and many papers have been omitted in this short survey. We have proposed several open questions along the pages of this article and many others still remain. As concluding words, let us not forget that beyond digital analytical geometry, there are many other forms of digital geometry that still need to be invented or explored: parametric digital geometry, non-Euclidean digital geometry, multiscale digital geometry, etc.