Eric Andres
email: eric.andres@univ-poitiers.fr

DRAFT: Digital Analytical Geometry: How do I dene a digital analytical object?

Keywords:

This paper is meant as a short survey on analytically dened digital geometric objects. We will start by giving some elements on digitizations and its relations to continuous geometry. We will then explain how, from simple assumptions about properties a digital object should have, one can build mathematical sound digital objects. We will end with open problems and challenges for the future.

Introduction

Geometry is historically the eld 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 elds, 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 signicantly 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 dierent forms of geometries have since been proposed such as Dierential geometry, Algebraic geometry, etc.

Digital Geometry is one of the most recent forms of geometry. It can be broadly dened 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 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 nite 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 denition has been raised. It proved more elusive than initially thought [START_REF] Montanari | On limit properties in digitization schemes[END_REF]. 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 [START_REF] Chassery | Géométrie discrète en imagerie[END_REF]: two, non identical, parallel 2D digital straight lines can have an innite 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 specic to digital geometry [START_REF] Rosenfeld | Digital topology[END_REF]. 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 ecient approaches when it comes to handling digital information (image processing, image analysis), it does little in helping dening 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 nds 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 [START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF]. The main drawback of such an algorithmic approach is that it is dicult to ensure global properties from the local construction scheme. The other problem with a denition by construction is that you can only generate nite 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 [1015]. This allows to dene (classes of ) digital objects that are innite and without boundaries such as planes or surfaces in general. This approach proved useful to construct object classes with desired properties but it proved dicult to ensure tightness for the classes. And, as for the continuous geometry, analytical characterization of digital objects has proven to be eective 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 denition 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 section two, we are going to discuss dierent types of digitizations. In section three we are going to focus on digital analytical objects. We will then conclude and propose some perspectives.

Digitization

Notations

Let us denote n the dimension of space (digital or Euclidean) in this paper. Let {e 1 , . . . , e n } denote the canonical basis of the n-dimensional Euclidean vector space and O the center of the associated geometric coordinate system. Let Z n be the subset of R n that consists of all the integer coordinate points. A digital (resp. Euclidean) point is an element of Z n (resp. 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 coecients in R from which we retain only the integer coordinate solutions. A digital analytical object is a digital object dened as union and intersection of a nite set of digital inequalities. The family of sets over Z n (resp. R n ) is denoted P (Z n ) (resp. P (R n )). A digitization is a transform from sets in the Euclidean to sets in the digital world: ∆ :

P (R n ) → P (Z n ).
For all k ∈ {0, . . . , n-1}, two integer points v and w are said to be k-adjacent or k-neighbors, if for all i ∈ {1, . . . , n}, |v i -

w i | ≤ 1 and n j=1 |v j -w j | ≤ n -k.
In the 2-dimensional plane, the 0and 1-neighborhood notations correspond respectively to the classical 8and 4-neighborhood notations. In the 3-dimensional space, the 0-, 1and 2-neighborhood notations correspond respectively to the classical 26-,18-and 6-neighborhood notations [START_REF] Rosenfeld | Digital topology[END_REF][START_REF] Andres | Dening discrete objects for polygonalization: The standard model[END_REF][START_REF] Andres | Discrete linear objects in dimension n: the standard model[END_REF].

A k-path is a sequence of integer points such that every two consecutive points in the sequence are k-adjacent. A digital object E is k-connected if there exists a k-path in E between any two points of E. A maximum k-connected subset of E is called a k-connected component. Let us suppose that the complement of a digital object E, Z n \ E admits exactly two k-connected components F 1 and F 2 , or in other words that there exists no k-path joining integer points of F 1 and F 2 , then E is said to be k-separating in Z n . If there is no path from F 1 to F 2 then E is said to be 0-separating or simply separating. A point v of a k-separating object E is said to be a k-simple point if E \ {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 dened for digital surfaces without boundaries. See [START_REF] Cohen-Or | Fundamentals of surface voxelization[END_REF] for more general notions.

General remarks on Digitizations

Let us rst start with some general remarks about digitization methods. The digitization of objects is fundamentally an ill-dened problem [START_REF] Montanari | On limit properties in digitization schemes[END_REF]: any digital E. Andres 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 [1821]. See [START_REF] Chollet | Insight in discrete geometry and computational content of a discrete model of the continuum[END_REF][START_REF] Reveillès | Back and forth between continuous and discrete for the working computer scientist[END_REF] for a more formal presentation of a link between the continuous and the digital worlds based on non-standard analysis.

A digitization is dened 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 dened as digitization of specic classes of geometric objects [START_REF] Bresenham | Algorithm for computer control of a digital plotter[END_REF][START_REF] Bresenham | A linear algorithm for incremental digital display of circular arcs[END_REF][START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF]2434]: for instance, the Bresenham digital straight line segment generation algorithm [START_REF] Bresenham | Algorithm for computer control of a digital plotter[END_REF] 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 dened is also an important problem for pattern recognition: comparing two digital circle recognition algorithm supposes that the underlying digital circles are dened in the same way or otherwise it is like comparing apples to oranges. Other digitization transforms are dened only for linear objects [START_REF] Andres | Dening discrete objects for polygonalization: The standard model[END_REF][START_REF] Andres | Discrete linear objects in dimension n: the standard model[END_REF] and others still for all objects [START_REF] Andres | The supercover of an m-at is a discrete analytical object[END_REF].

Let us mention some classes of digitization transforms that are important: A general digitization is a digitization that is dened for all continuous objects. A coherent digitization transform ∆ veries the following property E ⊂ F ⇒ ∆(E) ⊂ ∆(F ).

Morphological Digitizations

Let us build a narrative for the construction of a general, coherent digitization transform ∆. For a geometric object E, how can we build its digital counterpart ∆(E) that ressembles E ? Simply considering that ∆(E) = E ∩ 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 ∆(E) = ∅. So let us consider points that are close to E:

∆(E) = {p ∈ Z n : d(p, E) ≤ r} , where d is a distance and r ∈ R (1)
There are some important immediate properties that go with such a denition:

∆(E ∪ F ) = ∆(E) ∪ ∆(F ) and E ⊂ F ⇒ ∆(E) ⊂ ∆(F ), which is a stronger
version of the coherence property. These are fundamental properties when it comes to digital modeling of complex objects. It denes 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 dened as a function. See [START_REF] Fiorio | Discrete circles: an arithmetical approach with non-constant thickness[END_REF][START_REF] Andres | Analytical description of digital circles[END_REF][START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF] for examples of digital objects dened 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 [START_REF] Chollet | Insight in discrete geometry and computational content of a discrete model of the continuum[END_REF][START_REF] Reveillès | Back and forth between continuous and discrete for the working computer scientist[END_REF].

If a point p veries d(p, E) ≤ r then a ball B d (r) of radius r, for the distance d, centered on p intersects E which leads to the following formulation:

∆(E) = {p ∈ Z n : (B d (r) ⊕ p) ∩ E = ∅} (2)
This type of digitization method is part of digitization methods called morphological digitization [3640] with 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 [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF].

Every digital adjacency relationship can be associated to a norm. Denition 1. For an integer k, 0

≤ k < n, the k-adjacency norm [•] k is dened as follows: ∀x ∈ R n , [x] k = max x ∞ , x 1 n-k .
These distances are interesting because they verify the following property [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF]:

Let p, q ∈ Z n , then, p and q are k-adjacent i [p -q] k ≤ 1. See Figure 1 for adjacency distance balls.

Fig. 1. 2D and 3D balls for the adjacency distances and the corresponding Flakes [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF].

For morphological digitizations [START_REF] Heijmans | Morphological image operators[END_REF][START_REF] Klette | Digital straightness -a review[END_REF][START_REF] Lincke | Surface digitizations by dilations which are tunnel-free[END_REF], the structuring element is not necessarily a distance ball as in formula (2). One can consider any continuous object F as structuring element and dene a digitization transform of a continuous object E by [START_REF] Lincke | Surface digitizations by dilations which are tunnel-free[END_REF]:

∆(E) = p ∈ Z n : F ⊕ p ∩ E = ∅ (3)
The region x ∈ R n : F ⊕ x ∩ E = ∅ is called the oset region. Formulation (3) has implicitly already been used in digitizations such as the grid intersection digitization [START_REF] Klette | Digital straightness -a review[END_REF] with half-open structuring elements. This is also the starting point for the analytical characterization of digital objects with the analytical description of the oset region. Note that, for an arbitrary structuring element F , it is the reection F that appears in formula (3).

Analytical Characterization of Digital Objects

Let us rst dene what we understand by analytical characterization of a digital object: a digital object is dened by a set of equations (inequalities typically).

A point belongs to the digital object i it veries 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 dened in comprehension and not Fig. 2. This gure has been proposed in [START_REF] Lincke | Surface digitizations by dilations which are tunnel-free[END_REF]. (a

) p ∈ Z 2 : F ⊕ p = ∅ (b) ( F ⊕E)∩Z 2 .
The region in gray in (b) is called the oset zone.

as a voxel enumeration. Innite digital objects can be represented. This was also one of the reasons for trying to dene digital objects based on topology [1015].

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 [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF], many papers have been proposed that describe or discuss properties of analytical digital objects. Those papers can be roughly classied into two groups:

Direct dened Analytical Digital Object: Papers that introduce an analytical denition of digital objects or classes of objects, or that analytically characterize previously known digital objects. Those objects are dened 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.

Direct dened Analytical Digital Objects

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

Digital Analytical Hyperplane: The rst class of digital object that has been analytically characterized has been the digital straight 2D line [START_REF] Brons | Linguistic methods for the description of a straight line on a grid[END_REF][START_REF] Coven | Sequences with minimal block growth[END_REF]. It was J-P. Reveilles that proposed an analytical description of a Digital Straight Line (DSL) 0 ≤ ax -by + c < ω [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF] with a thickness parameter ω that allows a parametrization of its topology. He also made an explicit link between digital straight lines, topology, quasi-ane transforms and arithmetics [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF]4446]. 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 [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF][START_REF] Debled-Renesson | A new approach to digital planes[END_REF][START_REF] Andres | Discrete analytical hyperplanes[END_REF] with the analytical characterization of digital hyperplanes:

H : 0 ≤ a 0 + n i=1 a i x i < ω. (4)
See [START_REF] Klette | Digital straightness -a review[END_REF][START_REF] Brimkov | Digital planarity -A review[END_REF] 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 dierent theoretical approaches together, was to establish a link between the thickness of digital hyperplanes and topology [START_REF] Andres | Discrete analytical hyperplanes[END_REF]: let us assume, w.l.o.g. that 0 ≤ a

1 ≤ . . . ≤ a n , the digital hyperplane 0 ≤ a 0 + n i=1 a i x i < ω is k-separating i ω ≥ n k+1 a i . With ω = n k+1 a i the digital
hyperplane is strictly k-separating, without simple points. Papers have been devoted to the study of dierent classes of digital hyperplanes such as naive hyperplanes [START_REF] Andres | Discrete analytical hyperplanes[END_REF], supercover hyperplanes [START_REF] Andres | Tunnel-free supercover 3d polygons and polyhedra[END_REF][START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF][START_REF] Andres | The supercover of an m-at is a discrete analytical object[END_REF], Graceful lines and planes [START_REF] Brimkov | Graceful planes and thin tunnel-free meshes[END_REF][START_REF] Brimkov | Graceful planes and lines[END_REF], etc. An interesting sequence of papers has focused on the connectivity of digital analytical hyperplanes [START_REF] Brimkov | Connectivity of discrete planes[END_REF][START_REF] Jamet | Minimal arithmetic thickness connecting discrete planes[END_REF][START_REF] Berthé | Critical connectedness of thin arithmetical discrete planes[END_REF]. The problem proved to be quite dicult when it comes to digital analytical (hyper)planes with irrational coecients. Several papers have dealt with topology especially in order to dene a notion of digital surface [START_REF] Francon | Discrete combinatorial surfaces[END_REF][START_REF] Francon | Arithmetic planes and combinatorial manifolds[END_REF].

Digital Analytical Hyperplanes have been dened 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 + n i=1 a i x i = 0, we dene ∆(H) = p ∈ Z n : ω 2 ≤ a 0 + n i=1 a i x i < ω 2 .
Note that the Bresenham line [22] is such a centered Reveilles line [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF]. There is the question of orientation of the digital hyperplane: with a denition such as 0 ≤ a 0 + n i=1 a i x i < ω, on which side do we put the ≤ and the <. One can easily switch side and obtain 0 < ω-a 0 + n i=1 (-a i )x i ≤ ω, so a choice has to be made. This question is somewhat dicult if we want coherent digitization models, so let us focus a moment on so called closed analytical digital hyperplanes 0 ≤ a 0 + n i=1 a i x i ≤ ω (with two ≤). Let us suppose that we have a digitization transform ∆ that is dened for hyperplanes such that, for a continuous hyperplane H :

a 0 + n i=1 a i x i = 0, we have ∆(H) = p ∈ Z n : ω 2 ≤ a 0 + n i=1 a i x i ≤ ω 2 .
Under some conditions, it is possible to take this as a starting point for the construction of a general, coherent morphological digitization transform: Denition 2. For some classes of digitization transforms ∆ dened for hyperplanes, one can extend ∆ as a general and coherent morphological digitization with a structuring element ∆(O) that is dened by:

For x ∈ R n , ∆(O) = ∀H⊃O ∆(H).
The idea behind this denition is basically the following: For a digitization transform to be coherent, it has to verify the condition E ⊂ F ⇒ ∆(E) ⊂ ∆(F ). ∆(O) has to belong to the digitization of all the hyperplanes that pass through E. Andres the coordinate center O. If we consider the equality, we basically dene the digitization of a point which in this case can serve as structuring element for the morphological digitization transform. The diculty lies in the choice of ω for the digitization transform: for a hyperplane H, we want ∆(H) to be equal to x∈H ∆(x) and that is of course not true for any random choice of ω. There are classes of digital hyperplane thickness that work, namely those that correspond to the optimal hyperplane thickness for it to be k-separating: ω is equal to the sum of the absolute values of the n -k biggest coecients of H. These thicknesses correspond to the adjacency norm [.] 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 Andres Hypersphere: The second class of digital objects that have been dened directly as digital objects are the so called Andres hyperpsheres [START_REF] Andres | The discrete analytical hyperspheres[END_REF][START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF]:

analytically
S = x ∈ Z n : ω 1 ≤ n i=1 (x i -c i ) 2 < ω 2
where c is the center of the digital hypersphere and

√ ω 2 -√ ω 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 [START_REF] Bresenham | A linear algorithm for incremental digital display of circular arcs[END_REF] in particular that is only dened for integer radius, integer coordinate center and that, at the time, did not have an analytical characterization. There is one now [START_REF] Andres | Analytical description of digital circles[END_REF][START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF]. 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 [START_REF] Mora | Pedagogic discrete visualization of electromagnetic waves[END_REF].

nD Straight Lines: Flats in general have not been studied that much with the notable exception of straight lines: 2D analytical lines [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF], 3D analytical lines [START_REF] Debled-Rennesson | Etude et reconnaissance des droites et plans discrets[END_REF][START_REF] Figueiredo | A contribution to 3d digital lines[END_REF], graceful lines [START_REF] Brimkov | Graceful planes and lines[END_REF], analytical nD lines [START_REF] Feschet | A generic approach for n-dimensional digital lines[END_REF]. The study of Digital Analytical Lines has gained a lot of traction in the arithmetical community [START_REF] Berthé | An arithmetic and combinatorial approach to threedimensional discrete lines[END_REF][START_REF] Berthé | An arithmetic and combinatorial approach to threedimensional discrete lines[END_REF] for its link to word theory. It is interesting to note that I. Debled-Rennesson's 3D line is dened as the intersection of two orthotropic naive 3D planes (thinnest planes without 6-connected holes) and thus is an analytically dened 26-connected object. However, contrary to what one could think, the 3D line one would obtain by considering naive planes and intersecting them to dene 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 dene such digital 3D lines.

It is an interesting question and it shows that direct analytical denitions for digital objects may lead to interesting topological properties.

Other Purely Analytically dened Digital Objects: There are other analytically dened objects that could be considered as purely analytically dened 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 [START_REF] Debled-Rennesson | Segmentation of discrete curves into fuzzy segments[END_REF] with applications in noisy digital object recognition. E.

Andres, M. Rodriguez et al. proposed a notion of analytically characterized digital perpendicular bisector [START_REF] Andres | Generalized perpendicular bisector and exhaustive discrete circle recognition[END_REF] 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 dened curves and surfaces, named Digital Level Layers [START_REF] Gérard | Introduction to digital level layers[END_REF]. Although based on a morphological digitization, the objects are purely analytically dened.

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 [START_REF] Bresenham | Algorithm for computer control of a digital plotter[END_REF] that has been shown to be a Reveilles straight line segment [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF]. In the same way, in [START_REF] Andres | Analytical description of digital circles[END_REF], most notions of digital circles that have been introduced have been analytically characterized [START_REF] Bresenham | A linear algorithm for incremental digital display of circular arcs[END_REF][START_REF] Mcilroy | Best approximate circles on integer grids[END_REF]. An extension to higher dimensions has been proposed in [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF] with an explicit mention of Morphological Digitizations. Let us start with morphological digitization transforms.

Supercover digitization: One of the rst analytically characterized digitization model that has been proposed is the supercover digitization (also called outer Jordan digitization [START_REF] Klette | Digital straightness -a review[END_REF][START_REF] Jordan | Remarques sur les intégrales dénies[END_REF]) based on the Chebychev distance d ∞ [START_REF] Chassery | Géométrie discrète en imagerie[END_REF][START_REF] Cohen-Or | Fundamentals of surface voxelization[END_REF][START_REF] Lincke | Surface digitizations by dilations which are tunnel-free[END_REF][START_REF] Stelldinger | Digitization of non-regular shapes in arbitrary dimensions[END_REF][START_REF] Klette | Digital straightness -a review[END_REF][START_REF] Jordan | Remarques sur les intégrales dénies[END_REF][START_REF] Sankar | Grid intersect quantization schemes for solid object digitization[END_REF][START_REF] Andres | Tunnel-free supercover 3d polygons and polyhedra[END_REF][START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF][START_REF] Andres | The supercover of an m-at is a discrete analytical object[END_REF]. The supercover digitization is well-known for a long time because it has a natural geometric interpretation. The unit ball for the distance

B d∞ 1
2 is a hypercube of side one. If we denote V(p) the voxel centered on p, Formula (2) for the Chebychev distance is the same as {p ∈ Z n : V(p) ∩ E = ∅}: a point belongs to the supercover of a continuous object E i 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 [START_REF] Jordan | Remarques sur les intégrales dénies[END_REF]) before the link to the Chebychev distance has been made.

We will not recall all the details on the supercover model: see [START_REF] Cohen-Or | Fundamentals of surface voxelization[END_REF] for general properties of the digitization transform. In [START_REF] Andres | Tunnel-free supercover 3d polygons and polyhedra[END_REF][START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF][START_REF] Andres | The supercover of an m-at is a discrete analytical object[END_REF] for the analytical characterization of the supercover digitization of m-simplice and m-ats in dimension n. In [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF], the reader will nd 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 [START_REF] Andres | Tunnel-free supercover 3d polygons and polyhedra[END_REF][START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF][START_REF] Andres | The supercover of an m-at is a discrete analytical object[END_REF]. The supercover of a hyperplane, for instance, is (n -1)connected but with possibly simple points. For theoretical [START_REF] Francon | Discrete combinatorial surfaces[END_REF][START_REF] Francon | Arithmetic planes and combinatorial manifolds[END_REF][START_REF] Francon | Sur la topologie d'un plan arithmétique[END_REF] 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 denition of a voxel [START_REF] Cohen-Or | Fundamentals of surface voxelization[END_REF] but that does not work [START_REF] Andres | Dening discrete objects for polygonalization: The standard model[END_REF][START_REF] Andres | Discrete linear objects in dimension n: the standard model[END_REF]. There is however a way to solve this problem [START_REF] Andres | Dening discrete objects for polygonalization: The standard model[END_REF][START_REF] Andres | Discrete linear objects in dimension n: the standard model[END_REF]. The idea is the following: the supercover S(H) of a hyperplane H : a 0 + n i=1 a i x i = 0 is given by S(H) :

- n i=1 |ai| 2 ≤ a 0 + n i=1 a i x i ≤ n i=1 |ai| 2 .
It is (n-1)-connected, tunnel-free but it might have simple points (bubbles). The analytical hyperplane -

n i=1 |ai| 2 ≤ a 0 + n i=1 a i x i < n i=1 |ai| 2 is (n-1)-connected,
tunnel-free and strictly separating (without bubbles). The only dierence comes from the " ≤ " 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 " ≤ " into a " < ". We dene therefore an orientation convention: A halfspace H : a 0 + n i=1 a i x i ≤ 0 is said to have a standard orientation i a 1 > 0 or a 1 = 0 and a 2 > 0 or . . . if a 1 = . . . = a n-1 = 0 and a n > 0. Otherwise the halfspace is said to have a supercover orientation.

Since the dening structuring element for the supercover digitization transform is a unit hypercube, it is easy to see that the oset zone for a supercover linear object is a polytope dened as intersection of a nite sequence of digital

half-spaces S(E) = p ∈ k i=1 H i ∩ Z n ; H i : a i,0 + n j=1 a i,j x j ≤ 0
where k is the cardinality of the set of halfspaces {H i } dening the supercover of E. For such a set of halfspaces, we replace each halfspace H i : a i,0 + n j=1 a i,j x j ≤ 0 that has a standard orientation by H i : a i,0 + n j=1 a i,j x j < 0 in the analytical characterization of the digital object. If the halfspace has a supercover orientation, it is not modied. This denes the standard digitization transform St(E) of a linear Euclidean object E. It has been shown in [START_REF] Brimkov | Object discretizations in higher dimensions[END_REF] that the standard digitization produces (n -1)-connected, tunnel-free and strictly separating objects. See Grid Intersection digitization: A popular digitization scheme is called grid intersection digitization [START_REF] Sankar | Grid intersect quantization schemes for solid object digitization[END_REF]. For a continuous object E, the intersection points of E and the grid lines (all the straight lines x i = k, k ∈ 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 0, . . . , 0, ± 1 2 , 0, . . . , 0, ± 1 2 , 0, . . . , 0 . 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 dened for all k-dimensional objects, k > 0. Bresenham line [START_REF] Bresenham | Algorithm for computer control of a digital plotter[END_REF] is such an object and its characterization has been given in [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF] by JP. Reveilles. In [START_REF] Andres | Analytical description of digital circles[END_REF][START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF] there is the analytical characterization of d 1 digital circles and spheres.

Flake Digitization [START_REF] Toutant | Implicit digital surfaces in arbitrary dimensions[END_REF][START_REF] Sekiya | On connectivity of discretized 2d explicit curve. Mathematical Progress in Expressive Image Synthesis[END_REF]: The analytical characterization of the supercover of a sphere S is quite complicated [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF]. Most (in the geometric sense) of the oset region corresponds however simply to a translation of the continuous sphere S. Indeed, the outer and inner boundary of B d∞ ⊕ S is in great part determined by the vertices of the ball. Let us call V ∞ the set of vertices of B d∞ then V ∞ ⊕ S corresponds largely to the same surface than the boundary of B d∞ ⊕ S. If we consider a structuring element F composed of straight line segments that join the vertices v of B d∞ to its reverse v then F ⊕ S is (n -1)-connected and tunnel-free if S is big enough (details of S need to be bigger than a voxel [START_REF] Toutant | Implicit digital surfaces in arbitrary dimensions[END_REF][START_REF] Sekiya | On connectivity of discretized 2d explicit curve. Mathematical Progress in Expressive Image Synthesis[END_REF]). 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 dened 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 dened by such an implicit equation f (x) = 0, x ∈ 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 dene the Flake F formed by the straight lines joining the vertices v i to its symmetric vi (See Figure 1). Then (F ⊕ S) ∩ Z n is analytically characterized by: p ∈ Z n :

n min i=1 (f (v i )) ≤ 0 ∧ n max i=1 (f (v i )) ≥ 0 (5)
The idea is actually very simple: as morphological digitization, the surface S cuts a structuring element F ⊕ p i there are vertices on each side of the surface dened by the implicit equation. The so-dened Flake digitization transform (F ⊕ S) ∩ Z n is similar to (F ⊕ S) ∩ Z n except may be on places where S does not t some regularity properties [START_REF] Toutant | Implicit digital surfaces in arbitrary dimensions[END_REF]. The ake digital object keeps the topological properties of the original object. This is a way of dening implicit digital objects is straightforward way with the limitation that it is dened only for (n -1)-dimensional surfaces that are regular enough. See Figure 4 for an exemple of a implicitly dened quadric digitized with all three 3D adjacency akes.

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 prot greatly of the analytical characterizations of digital objects. For the transforms, let us just cite the Quasi-Ane Transforms [START_REF] Coeurjolly | Quasi-ane transformation in 3-d: Theory and algorithms[END_REF] among many others. For Object Recognition, having mathematical denitions 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.

For

  A and B two subsets of R n , A ⊕ B = {a + b : a ∈ A, b ∈ B} is the Minkowski sum of A and B. Let us denote Ǎ = {-a : a ∈ A} the reection set of A. Let us denote A the at of smallest dimension containing A. For a distance d, then the let us denote B d (r) = {x ∈ R n : d(x, O) ≤ r}, the ball of radius r for the distance d. Let us denote d 1 , d 2 , d ∞ respectively the Manhattan, Euclidean and Chebychev distance. Let us denote x k the corresponding norm (with k = 1, 2, ∞).

Figure3

  Figure3 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 dened only for linear objects. There is however a caution. Contrary to the supercover digitization, in general, St(E) = x∈E St(x). The standard digitization is dened as a nite rewriting of the inequalities dening the supercover of a linear object. It does not hold for an innite sequence of inequalities.

Fig. 3 .

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

Fig. 4 .

 4 Fig. 4. Flake digitizations of the quadric 9x 2 -4y 2 -36z -180 = 0.

  as linear digital objects (with linear inequalities). The best known of such digitization transforms is the Supercover model[START_REF] Chassery | Géométrie discrète en imagerie[END_REF][START_REF] Cohen-Or | Fundamentals of surface voxelization[END_REF][START_REF] Lincke | Surface digitizations by dilations which are tunnel-free[END_REF][START_REF] Stelldinger | Digitization of non-regular shapes in arbitrary dimensions[END_REF][START_REF] Klette | Digital straightness -a review[END_REF][START_REF] Jordan | Remarques sur les intégrales dénies[END_REF][START_REF] Sankar | Grid intersect quantization schemes for solid object digitization[END_REF][START_REF] Andres | Tunnel-free supercover 3d polygons and polyhedra[END_REF][START_REF] Andres | Supercover of straight lines, planes and triangles[END_REF][START_REF] Andres | The supercover of an m-at is a discrete analytical object[END_REF]. One other thickness that works is ω =

	n i=1 a 2 i . The corresponding

structuring element ∆(O) is the unit hypersphere. The associated norm is the Euclidean norm. What other thicknesses work is an interesting open question.


Fatma Marzouk
email: fatmarzouk@gmail.com

Rachid Zagrouba
email: rachid.zagrouba@cristal.rnu.tn

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Leila Azzouz Saidane

An empirical study of Unfairness and Oscillation in ETSI DCC

Keywords: component; CAM, DCC, VANET, ETSI-ITS I

Performance of Vehicular Adhoc Networks (VANETs) in high node density situation has long been a major field of studies. Particular attention has been paid to the frequent exchange of Cooperative Awareness Messages (CAMs) on which many road safety applications rely. In the present paper, se focus on the European Telecommunications Standard Institute (ETSI) Decentralized Congestion Control (DCC) mechanism, particularly on the evaluation of its facility layers component when applied in the context of dense networks. For this purpose, a set of simulations has been conducted over several scenarios, considering rural highway and urban mobility in order to investigate unfairness and oscillation issues, and analyze the triggering factors. The experimental results show that the latest technical specification of the ETSI DCC presents a significant enhancement in terms of fairness. In contrast, the stability criterion leaves room for improvement as channel load measurement presents (i) considerable fluctuations when only the facility layer control is applied and (i.i) severe state oscillation when different DCC control methods are combined.

INTRODUCTION

In recent years, the interest in using Intelligent Transportation Systems (ITS) has grown considerably. A wide range of vehicular ITS applications are based on the periodic exchange of Cooperative Awareness Messages (CAMs). In such messages, vehicles periodically send information related to their own position, speed and heading [1]. Receiving CAMs from its neighbors should provide a node with an accurate assessment relevant image of its neighborhood. However several studies [START_REF] Breu | A quantitative study of Cooperative Awareness Messages in production VANETs[END_REF] [START_REF] Breu | Analysis of Cooperative Awareness Message rates in VANETs[END_REF] have pointed out that the channel can quickly become congested due to the massive exchange of such status messages. This situation may worsen as VANETs become increasingly common.

Many standardization activities have been carried out by ETSI in Europe and IEEE in North America in order to specify how the channel should be accessed and to establish rules regarding the frequency and dissemination of periodic safety messages.

In terms of physical (PHY) and medium access (MAC) specifications, both standards are based on IEEE802.11p [START_REF]IEEE standard for Information technology--telecommunications and information exchange between systems--local and metropolitan area networks--specific requirements Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications : Amendment 6: Wireless access in vehicular environments[END_REF]. While WAVE uses a fixed 10Hz frequency for disseminating CAMs during the slots dedicated to safety messages as specified by the alternating access scheme [START_REF]IEEE standard for wireless access in vehicular environments (WAVE) multi-channel operation[END_REF] with the enhanced distributed channel access (EDCA), the European standard follows a different approach for generating CAMs with a frequency ranging from 1Hz to 10Hz depending on the mobility conditions of the vehicles and the current channel load, as will be detailed in this paper.

In addition, IEEE WAVE and ETSI ITS G5, can support congestion control algorithms [START_REF] Subramanian | Congestion control for vehicular safety: synchronous and asynchronous MAC algorithms[END_REF] and enhancements so as not to compromise the application requirement level.

Our work aims to analyze the behavior of a real-life dense network scenario where the DCC facility layer component has been implemented, in order to study unfairness and oscillation issues that have been reported in the latest technical specifications of the DCC mechanisms.

II. RELATED WORK

The congestion control problem for safety message traffic was initially tackled using three different strategies. The first one consists in controlling the transmission power among nodes so that each vehicle can perceive a less occupied channel. One of the proposals put forward in [START_REF] Torrent-Moreno | Distributed fair transmit power adjustment for vehicular ad hoc networks[END_REF] [START_REF] Torrent-Moreno | Vehicle-to vehicle communication: fair transmit power control for safety-critical information[END_REF] is to dynamically and fairly control the transmission power and to piggyback the transmission power in beacon messages in order to make the global channel load converge to a target threshold. While the effectiveness of the algorithm depends on the beacon frequency used, the overhead induced cannot be neglected.

The second class aims to adapt the transmission rate of CAMs messages. In [START_REF] Bansal | LIMERIC: A Linear Adaptive Message Rate Algorithm for DSRC Congestion Control[END_REF] the authors present an adaptive approach for rate adjustment to reach a target based on a mathematical expression is presented, showing. They provide results in terms of adaptation to the network"s dynamic and convergence to the targeted rate. In contrast, in [START_REF] Park | Application-Level Frequency Control of Periodic Safety Messages in the IEEE WAVE[END_REF] the rate is adapted according to the number of neighboring vehicles.

The last category contains algorithms and frameworks where hybrid adaptation methods are used. For instance, in [START_REF] Zemouri | Smart adaptation of beacons transmission rate and power for enhanced vehicular awareness in VANETs[END_REF] rate control is firstly performed, then it is followed can by power control once the minimal beacon transmit frequency has been reached and the channel load remains high.

As regards congestion, DCC is characterized by cross-layer architecture which is implemented within the ITS-Station. The core of DCC is a finite state machine composed of 3 states (Relaxed, Active, and Restrictive). In each state, the DCC components set different values for the station parameters: DCC-Access [START_REF][END_REF] acting on transmission Power, transmit Rate, and CCA sensitivity threshold. DCC-Facility operates on CAM [START_REF] Röck | Intelligent Transport Systems (ITS); Vehicular Communications; Basic Set of Applications; Part 2: Specification of Cooperative Awareness Basic Service[END_REF] and DENM. DCC-Management [START_REF] Cross | Intelligent Transport Systems (ITS); Cross Layer DCC Management Entity for operation in the ITS G5A and ITS G5B medium[END_REF] operates as a cross layer entity. Finally, the DCC-Network provides the vehicle with global information (DCC parameters Received from neighboring vehicles). That is important for parameters evaluation.

Several studies have focused on the evaluation of DCC. In [START_REF] Eckhoff | A performance study of cooperative awareness in ETSI ITS G5 and IEEE WAVE[END_REF] the authors conclude that it induces a considerable local and global oscillations in channel load measurements. Similarly, in [START_REF] Cross | Cross Layer DCC Management Entity for operation in the ITS G5A and ITS G5B medium; Report on Cross layer DCC algorithms and performance evaluation[END_REF] where the same observation was explained by the lack of simulation resources to reach a high CL sampling rate. In addition simulations in [START_REF] Kuk | Preventing Unfairness in the ETSI Distributed Congestion Control[END_REF] show through a set of simulation a remarkable unfairness problem among neighboring node. The divergence between these two results is due to by the two different strategies of extracting the channel load (CL). While in the first one, accessing the CL measurement is done at a synchronized time for all nodes, the procedure is done asynchronously in the third study. The second approach is feasible as the nodes" measurements can be insured by tracking the GPS time. So it is obvious that the second approach is more rational as the vehicles will have different CAM transmission rate (time?). The Unfairness problem was tackled in [START_REF] Kim | Resolving the Unfairness of Distributed Rate Control in the IEEE WAVE Safety Messaging[END_REF] and [START_REF] Kuk | Preventing Unfairness in the ETSI Distributed Congestion Control[END_REF] by piggybacking channel load measurements and the state of each node in each beacon sent. Furthermore, the reported oscillation problem occurred in scenarios where at least 3 DCC parameters were regulated.simultaneously

III. DCC FACILITY LAYER

The specification of the DCC CAM facility component stipulates that a vehicle generates CAMs under to two main conditions: First, if the time elapsed since the last CAM generation is equal to or greater than a period set by the DCC state machine T_GenCam_Dcc and one of the ITS-S dynamics related conditions is triggered i.e the absolute difference in heading, distance or speed included in previous CAMs exceeds 4°,4 m,and 0,5 m/s respectively. Due to the second condition, the time elapsed since the last CAM generation will be equal to or greater than the period representing the currently valid upper limit of the CAM generation interval T_GenCam and equal to or greater than T_GenCam_Dcc.

The CAM generation mobility condition is checked after T_GenCam_Dcc at least in order to trigger a sending event if valid according to condition 1).otherwise, the transmission occurs according to condition 2) at the latest 1s after at the last send time. Fig 1 shows the T_GenCam_Dcc depending on the current finite state of the vehicle. The latest version of the standard [START_REF] Röck | Intelligent Transport Systems (ITS); Vehicular Communications; Basic Set of Applications; Part 2: Specification of Cooperative Awareness Basic Service[END_REF] advocates a value of 0.1 s as the shortest CAM generation period for the relaxed state rather than 0.04s in previous version. It also specifies that, after triggering a number N_GenCam of consecutive CAMs due to condition 2), T_GenCam will be set to 1s. As shown in Figure .1 transitions from a state i to state i+1 can take place if the minimum channel load during 1 second exceeds a corresponding threshold. The reverse transitions may occur after a period of 5s.

IV. EVALUATION EXPERIMENTS

The Ns3 simulator was used for the implementation and evaluation of the DCC facility layer. It is an open-source event based simulation environment written in C++, which provides a number of useful features. A rural highway scenario and an urban scenario with large number of intersections were selected. In order to provide a realistic case study, we used to SUMO [START_REF] Liu | ACM Digital Library, ACM-Sigmetrics, and ACM Special Interest Group on Simulation and Modeling, Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques[END_REF] to set the vehicular traffic over a snippet of the two-lane highway linking the cities of Sousse and Sfax (Tunisia) and an urban area located in the town of Ariana (Tunisia). Figure 2 shows the map of the highway, downloaded from OpenStreetMap (OSM) and edited using Java OpenStreetMap Editor (JOSM). Figure 3 shows the urban region.

Fig.3 SUMO Simulation of the urban area in Ariana

In both scenarios the region size is equal to 1.3km×1.3km. We studied fluctuations in a dense region with 600 vehicles in both scenarios. Because we are mainly interested in the impact of urban and rural mobility, we used a long-distance path loss model with an exponent of 3 for both scenarios to simulate simple radio propagation, without taking into account most of the PHY layer effects such as shadowing, multipath propagation, etc. The simulation parameters are summarized in Table I.

The first set of simulations aimed to investigate the existence of the reported DCC unfairness between nodes. As already discussed in the previous section, this situation might be encountered when the vehicles have different times to read CL measurements and that in the network was subject to oscillation. As perfect synchronization in CL measurement wouldn"t reflect the real channel occupation (sending CAM messages occurs at different times) this case is excluded from the scope of our study. Thus, to examine the two situations, we applied different jitter values to the nodes so that the time that their first CAM was sent belonged in the interval of [0, jitter value]. We started with relatively small values of jitter. Then we measured the effect of raising the value. Over 300 seconds of simulation using values of 2s, 4s, 6s, 12s ,25s and 50s no divergence between the nodes was observed. Performing another simulation using the same scenario and values of jitter while adopting the former specification for the DCC facility layer [1] yielded quite different experimental results. Using 6 seconds of jitter was enough to trigger a polarization between node states. This stems from the fact that the previous DCC specification stipulates that the vehicles "initial state is Active with a rate of 2Hz. As a consequence of this relatively low rate, vehicles react by lowering their state to Relaxed .Figure 7 illustrates the case where node ID =164 and node ID =159 are initially in the active state when the simulation begins. When node 159 must read CL numerical value, it switches to the relaxed state to recover with 0.04s CAM generation period. Node 164 does the opposite rate adjustment, since the time gap between the two vehicles measurements was enough for this node to perceive that the minimal Channel Busy Ratio (CBR) exceeded 40%. The same pattern continues as other neighboring nodes react to the latest restriction by switching their states from active to relaxed, and so on. The probability and the speed with which this situation propagates greatly depends on the probability of gaining channel access by the vehicle that has just taken the decision to enter one of the extreme states (Relaxed or restrictive), and hence on the value of the minimal and maximal contention windows (CW).

The comparison between the two DCC versions highlighted the importance of reducing the set of time gaps between the nodes" CL measurements by reducing the lower limit of the CAM interval generation and thus the impact of changing the initial DCC state.

Shorter jitter values of were used in order to observe the effect of short time delays between CL measurements. As shown in Figure 4, the average channel load of all the vehicles in simulation (sharing the same Clear Channel assessment range normal traffic on the road all the vehicles move smoothly and upon encountering a bottleneck they enter a deceleration step, and then resume their movement at a lower speed. A better illustration of CL oscillation in the context of an urban highway pattern is given in Figure 9. As we can see, the nodes read a CBR numerical value each 100ms. The number of nodes in the dense highway scenario is represented with 5 nodes. Each of the vehicles sends its first CAM message during the first 100 ms. After 100 ms has elapsed nodes conclude about CBR measurement supposedly equal to 40% for each one, as 4 busy time samples were detected out of a total of 10 samples. Assuming also that the CAM mobility condition was triggered for the nodes 5 CAM messages were sent by each one. Let us now suppose that front vehicles 1 and 2 suddenly started decelerating upon approaching a congested highway exit. This would lead to the same ratio of channel busy time for the next 100 ms but would not lead to a CAM sending event. The CBR value for the subsequent interval will be 0, 0, 10, 20 and 20 for each of the five nodes respectively, which leads to an average value of the CL that drops from 40 to 10. On the other hand, according to the hypothesis, vehicles sharing the CCA range in an urban multi lane and multi intersection scenario might present a higher variation in gaps between nodes stopping at traffic lights, maneuvering a turn, moving on a single congested lane, or on a fast lane, which will also differ local CBR perception and so present less risk of oscillation. In order to investigate our hypothesis, we conducted a simulation of a highway scenario with the same number of vehicles. We began by defining the turning and stopping probability for each group of nodes. Figure.8 shows that using the same amount of jitter time (4s) the average channel load for the urban scenario presents a lower value compared to the highway scenario. Oscillations are also reduced. Nevertheless, we still cannot confirm or reject any of the two hypotheses.

V. CONCLUSION AND FUTURE WORK

In this paper we discussed the network behavior under the latest ETSI DCC rate CAM control specification, in order to investigate its performance in terms of effectiveness, fairness, and stability, taking into account different jitter values, simulating a variety of penetration rates in dense networks. After observing the CL behavior we can confirm the influence on DCC stability of combining the CAM generation period with transmission power, queuing time and CCA threshold control. Thus, the stability aspects of the DCC algorithm should be further scrutinized taking into account the granularity of different mobility scenarios, in order to achieve robust improvements.

Fig. 1

 1 Fig.1 DCC state Machines

Fig. 2

 2 Fig.2 Rural highway scenario: Sousse-Sfax highway

Fig. 9

 9 Fig.9 Illustration of CL oscillation reason in rural highway scenario The average channel load starts rising considerably once the jitter value time has been reached. Even though the overall highest and lowest CBR values are quite similar during the first second of the simulations, the 4s jitter scenario presents a visible fluctuation in CL measurements as indicated in Figure.4. The oscillation effect of smaller jitter values is illustrated in later simulation times, as shown by Figure 5. Interestingly, this oscillation does not only take place in a global context, but also on a local scale, as is obvious on a randomly chosen vehicle ID (see Figure.6). In terms of state oscillation, the significant global and local CBR fluctuation when only the DCC latest facility layer specification is

Fig. 7 Fig. 4 Fig. 5 Fig. 6

 7456 Fig.7 Polarization of states in former DCC version

TABLE I SIMULATION

 I SETTING


Rita Zrour
email: rita.zrour@univ-poitiers.fr

Gaelle Largeteau-Skapin
email: gaelle.largeteau.skapin@univ-poitiers.fr

Eric Andres
email: eric.andres@univ-poitiers.fr

DRAFT : Optimal Consensus set for nD Fixed Width Annulus Fitting

This paper presents a method for fitting a nD fixed width spherical shell to a given set of nD points in an image in the presence of noise by maximizing the number of inliers, namely the consensus set. We present an algorithm, that provides the optimal solution(s) within a time complexity O(N n+1 log N ) for dimension n, N being the number of points. Our algorithm guarantees optimal solution(s) and has lower complexity than previous known methods.

Introduction

Shape fitting is a general problem that is of very practical nature, namely extracting features from data with a high level of noise. This problem has been widely addressed in very different fields spanning from computer graphics and image processing to data mining in large dimensional databases [START_REF] Agarwal | Automatic subspace clustering of high dimensional data for data mining applications[END_REF]. In this paper we are looking into the problem of optimal fitting an nD annulus of fixed width in an image in the presence of outliers. The set of points which fits a model is called a consensus set. Note that an annulus in higher dimensions is sometimes referred to as n-sphere shell. We preferred to use the common denomination annulus for all dimensions. This paper aims at finding the optimal consensus set (maximal number of inliers) inside a fixed width nD annulus, where the center and the radius are unknowns. Most annuli fitting methods try to minimize the thickness of the fitted annuli [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Berg | Computing constrained minimum-width annuli of point sets[END_REF][START_REF] Smid | On the width and roundness of a set of points in the plane[END_REF]. In our case, we are interested in digital circles and spheres and more specifically Andres digital circles and hyperspheres [START_REF] Andres | The discrete analytical hyperspheres[END_REF] or k-Flake digital circles-spheres [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF]. In those cases, the thickness is directly linked with topological properties. The most common fitting methods are based on variants of the RANdom Sample Consensus (RANSAC) algorithm [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF], which is a robust parameter estimation algorithm widely used in the field of computer vision. However RANSAC is inherently probabilistic in its approach and does not guarantee any optimality. In this paper we are looking for (all the) optimal solutions in order to generate base solutions to which we can compare and validate other, non exact, methods. It is also a problem when looking for multiple fittings in the same image.

In [START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF] and [START_REF] Andres | Optimal consensus set and preimage of 4-connected circles in a noisy environment[END_REF], brute force algorithms were proposed to compute the optimal consensus set respectively for Andres digital circles [START_REF] Andres | The discrete analytical hyperspheres[END_REF] (defined as digital points inside a classical annulus of fixed width) and 0-Flake digital circles [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF] (8connected circles) with a time complexity of O(N 4 ) where N is the number of points. A new method was proposed in [START_REF] Largeteau-Skapin | O(n 3 log n) time complexity for the optimal consensus set computation for 4-connected digital circles[END_REF] for fitting 0-Flake digital circles that has a complexity O(N 3 log N ). Our main contribution in this article is the extension of the fitting problem proposed in [START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF] to nD and reformulating it using a space transformation similar to the one proposed by [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF] which was used in [START_REF] Largeteau-Skapin | O(n 3 log n) time complexity for the optimal consensus set computation for 4-connected digital circles[END_REF]. However the major difference with [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF] is that the width is fixed and the parameter we want to maximize is the number of inliers.

The simpler problem of fitting circles and spheres is a largely studied problem. Most common approaches are based on least squares [START_REF] Robinson | Fitting spheres by the method of least squares[END_REF] or adapted Hough Transforms [START_REF] Kimme | Finding circles by an array of accumulators[END_REF]. Those are however not adapted for annulus fitting. The circle fitting method proposed by O'Rourke et al. [START_REF] O'rourke | Computing circular separability[END_REF][START_REF] Roussillon | On three constrained versions of the digital circular arc recognition problem[END_REF] that transforms a circle separation problem into a plane separability problem, is also not well suited because the fixed width of the digital circles translates into non fixed vertical widths for the planes. In this case, the problem is complicated (See [START_REF] Phan | Efficient robust digital annulus fitting with bounded error[END_REF] for some ideas on how to handle this difficulty). For annuli detection, various approaches have been proposed. Most of these methods are probabilistic approaches that minimize the width of the annuli. Among these algorithms, some consider that no noise is present in the image, and concentrate only on the problem of recognition instead of the fitting problem [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Berg | Computing constrained minimum-width annuli of point sets[END_REF][START_REF] Smid | On the width and roundness of a set of points in the plane[END_REF]. However noise in real world is omnipresent in the input and so many algorithms dealing with outliers have been proposed [START_REF] Dunagan | Optimal outlier removal in high-dimensional spaces[END_REF][START_REF] Har-Peled | Shape fitting with outliers[END_REF][START_REF] Matousek | On enclosing k points by a circle[END_REF]; in these algorithms, the number of outliers is usually predefined [START_REF] Har-Peled | Shape fitting with outliers[END_REF][START_REF] Matousek | On enclosing k points by a circle[END_REF] which is not always realistic.

The idea of the 2D algorithm is the following: given a set S, we consider all the annuli that have two specific points of S on the border of the annulus. All the annuli centers with those two points on the border are then located on a straight line. This straight line is taken as a parametric axis. We then determine when a point of S enters and leaves the annulus while the center moves along the axis. This allows us to compute the intervals where the number of inliers is maximized. By considering all the combinations of points, we are able to compute the exhaustive set of all optimal consensus sets in O(N 3 log N ). See [START_REF] Zrour | Optimal consensus set for digital line and plane fitting[END_REF] for a similar approach for line and plane fitting. The nD algorithm works in a similar way than the 2D algorithm [START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF]. However, we show that the annulus can de defined by n specific points that are all on the external border. This characterization allows to greatly simplify both the proof of the characterization of annuli and the computation of the parametric axis defined by annuli centers. The final algorithm has an O(N n+1 log N ) time complexity and leads to the exact optimal solutions for the problem of fixed width annulus fitting.

The paper is organized as follows: in Section 2 we expose the problem of annulus fitting and present some properties of the annuli with fixed width. Section 3 presents the dual space we use and provide the algorithm for finding the optimal nD annuli. Section 4 presents some 2D and 3D experiments. Finally Section 5 states some conclusion and perspectives.

Annulus fitting

A nD annulus A(C, R, ω) of width ω and radius R centered at C(c 1 , c 2 , ..., c n ), is defined by the set of points in R n satisfying two inequalities:

A(C, R, ω) = (p 1 , p 2 , ..., p n ) ∈ R n : R 2 ≤ n i=1 (p i -c i ) 2 ≤ (R + ω) 2 (1)
where

C(c 1 , c 2 , ..., c n ) ∈ R n and R, ω ∈ R + .
Using the above annulus model, our fitting problem is then described as follows: given a finite set S = {P i , i ∈ [1, N ], ∈ R n } of N nD points we would like to find the parameters (center and radius) of an annulus A of given width ω that contains the maximum number of points in S. Points P i ∈ S ∩ A in nD are called inliers; otherwise they are called outliers. We also say that the annulus A covers the set S ∩A. We denote B i (C, R) (respectively B e (C, R+ω)) the internal (resp. external) border of the annulus A(C, R, ω), i.e. the set of points located at distance R (resp. R + ω) from C.

Annulus Characterization

Our approach is focused on inlier sets, also called consensus sets. Since S is finite, the number of different consensus sets for the annulus is finite as well although too big to consider them all. However, as we are looking for the biggest consensus set(s), only the annuli that contain a minimum number of n + 1 points, uniquely defining an annuli, are considered. For all the different consensus sets C, with at least n + 1 points from a given set S, we are going compute the size of each one. The center and radius are actually a side result of this search. We present in this section some characterization of nD annuli that will allow us to explore all those concensus sets and further on to build an optimal fitting algorithm for annuli.

nD Annular characterizations

In [START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF], we proposed a brute force algorithm for fitting fixed width annuli in 2D. We showed that if an optimal solution exists then there exists an equivalent optimal solution (with the same set of inliers) having three points on the border (internal and/or external). Testing all the configurations of three points and counting the inliers leads therefore to all the possible optimal solutions. This brute force method leads however to an O(N 4 ) complexity for N the number of points to fit. Its extension to nD is straight forward and needs n + 1 points to be on the border (either internal or external), but it also leads to an O(N n+2 ) complexity.

In this article we need only n points instead of n+1 points in nD; however the restriction is that the n points must be on the external border of the annulus. The last point is found in O(N log N ) using a dual space, which will be presented in section 3.1. Using such a dual space, the algorithm has an overall time complexity of O(N n+1 log N ). Note that we are looking for the exact optimal solutions, this complexity is, so far, the best to our knowledge to solve this problem.

The following theorem states that given an annulus A of width ω covering a set of points S, with |S| ≥ n, there exists at least one other annulus A of same width, that also covers S with at least n points of S on its external border B e . Proof. Let S be a finite set of N (N ≥ n) points in R n . Let A = (C, R, ω) be an annulus that covers S. The theorem proof is given as follows :

Theorem 1. Let S be a finite set of N (N ≥ n) points in R n . Let A = (C, R, ω) be an annulus covering S. Then it exists A = (C , R , ω) covering S such that: ∃! Q 1 , Q 2 , ..., Q n ∈ S ∩ B e (C , R + ω). w C a) w C C' b) Q1 d) Q1 w Q2 w Q1 C 2 C ' 2 C ' 2 C '' 2 c)
A. If the internal radius of the annulus is 0, the problem is reduced to the problem of a hyper-sphere of fixed radius. The hypersphere can either be translated towards the closest point of S if there are no point on the external border already (Figure 1a,b and Figure 3a,b) either it can be rotated around the axis formed by the already known points until reaching another point (Figure 1c,d and Figure 3c,d). This last step is done until n points lie on B e . B. If the internal radius is greater than 0, the building process consists in decreasing the radius while keeping the width fixed until reaching the points on the external border B e :

-If there is no point on the border, the radius is decreased while the center is fixed until reaching a point on B e (Figure 2a and Figure 4a).

-If there is one point Q 1 on the border, the radius is decreased while the center moves along the straight line

CQ 1 towards Q 1 (which keep Q 1 on B e )
until reaching a second point on B e (Figure 2b, Figure 4b).

-If there are already k > 1 points on B e then, we consider the barycenter B of those k points. We can now consider the straight line ∆ passing through B and C. By moving the center of the annulus along ∆ towards B we can reduce the radius of B e while keeping these k points on B e (Figure 4c). It should be noted that these steps are repeated until reaching n points on B e or having an annulus with width 0 which leads to case A.

Fitting algorithm

Let us define an equivalence class of all the annuli that cover the same consensus set. We suppose that there are more than n points in the image, otherwise all the points can be covered and the problem is somewhat trivial. The annulus characterization in Theorem 1 ensures that the optimal consensus set has always at least n points. It also shows that we can always find a representative of the equivalent class with n points of S on the outer border. Let us find now, among the representatives of the equivalent classes of consensus sets with at least n points, the annulus that cover(s) the maximum number of points of S.

The idea behind our fitting method is inspired by [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF] where the authors maximize the width of an empty annulus in 2D. In [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF], the authors look for the biggest empty annulus in a dual space based on the distance to the center. For each couple of points (Q 1 , Q 2 ), the possible positions for the center of a 2D annulus passing through Q 1 and Q 2 is the bisector of both points which then forms the abscissa axis of the dual space. Each other point is associated to a curve that represents its distance to the possible centers. Using this specific space, they find when each point enters or leaves the annulus. A sorting of these intervals leads to the maximal empty annulus passing through Q 1 and Q 2 . A comparison among all the possible couples of points leads to the general result. In [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF], the authors do not represent an annulus in their parameter space but only circles and the width ω of the annulus is maximized. Our purpose in this work is different since, in our problem, we tried to maximize the number of inliers inside an annulus with fixed width, so we have two concentric circles with a fixed distance ω between them. Moreover, we have adapted this method to nD. As we will see, their idea of taking the axes where the possible centers of the annuli are located can be adapted to our case. We first describe the dual space (Section 3.1) and then explain how we obtain the optimal consensus set(s) (Section 3.2).

Dual space and annulus fitting in nD

According to Theorem 1, in nD, an annulus has at least n unique critical points Q 1 , .., Q n located on its external border. Such an annulus has necessarily its center on a straight line, denoted ∆, that passes through the barycenter B of the points Q 1 , .., Q n and that is orthogonal to the hyperplane H (of dimension n -1) induced by those same points (see Figure 5a for an example in 2D). Let us define a 2D dual space as follows:

-The origin O dual (0, 0) corresponds to the barycenter B of the points Q 1 , .., Q n .

-The abscissa X axis represents the possible locations of the center (it is a representative of ∆): a center C is associated to C dual (dist(C, B), 0) (Figure 5b).

-The ordinate Y axis represents the euclidean distance: each point T (t 1 , ...t n ) in the original nD space is associated in the dual space with a curve that represents the distance between T and every point of ∆.

In this dual space, the points Q i , i ∈ [1, n] are all represented by the same curve L 0 Q since they are all equidistant from each point of ∆ (Figure 5b). We consider that all the points Q i , i ∈ [1, n] are on the external border of the annulus, therefore L 0 Q represents the external radius (R e ) variation with respect to the center position. An annulus of width ω passing through the points Q i , i ∈ [1, n] is represented by a vertical segment of length ω having one of its endpoints on L 0 Q . The X coordinate of the segment corresponds to the annulus center coordinate on ∆.

The translation of L 0

Q by (0, -ω) is denoted by L 1 Q which represents the internal radius variation with respect to the center position.

In the dual space, an annulus A of center C(c , 0) with points Q i , i ∈ [1, n] on its external border corresponds to the vertical line segment For every point T in the image, it is possible to see if it is inlier or outlier to an annulus of width ω centered on C and having the n points Q i on its external border by examining its associated curve L T . The point T is inlier if, in the dual space, L T intersects the vertical segment 6). Q at σ 0 T and the curve L 1 Q at σ 1 T . The point T is thus inlier to the annulus having Q1 and Q2 on its external border between σ 0 T and σ 1 T and becomes outlier otherwise. The point T is outlier to the annulus centered at C(-1, 0) and inlier to the one centered at C(1, 0).

[L 0 Q (c ), L 1 Q (c )] of length ω.
[L 0 Q (c ), L 1 Q (c )] with c = dist(C, B) since in this case it is between L 0 Q (c ) = R e and L 1 Q (c ) = R i (Figure
p(0,3) q(0,-3) r(-1/2,2) t(2,2) u(-1/2,-1/2) v(4,

Maximum inliers

Center C(0,3) Rmax = dist(p,C)=4.24

x axis Distance to the point (x,0) Fig. 7. 2D example: six points p=Q1, q=Q2, r, u, v, and t in the primal space and their corresponding curves. The maximum number of inliers for an annulus having p and q on Be is reached when the center has an x-value around 3.

Finding the largest consensus set in a strip for a given

(Q 1 ,Q 2 ,...,Q n )
In order to know the number of inliers within any annulus defined by n points Q 1 ... Q n , we check for every point T in the image, the intersections σ 0 T and σ 1 T of L T with the strip boundaries L 0 Q and L 1 Q . This check is important since any annulus corresponding to a vertical segment between the two intersections σ 0 T and σ 1 T in the strip always contains T as an inlier; outside this interval, T is always an outlier (Figure 6).

When checking the intersections of every L T with L 0 Q and L 1 Q , we use two values f i T for i = 0, 1, which is set to 1 if L T enters the strip from L i Q , and -1 if L T leaves the strip from L i Q . Once the intersections σ i T , and the associated values f i T for i = 0, 1 are calculated, we sort all the intersections in increasing order. As for determining the location(s) of the maximum number of inliers, a function F (x) is used; initially we set F (x) = n for every x, since we already know that Q 1 ,...Q n are inliers. Then the value f i r is added to F (x) following the sorted order. By looking for the maximum value of F (x), we obtain the center location(s) in the dual space corresponding to the maximum optimal consensus set(s). Figure 7 shows an example in 2D of this algorithm; the annulus in the primal space having p = Q 1 and q = Q 2 on its external border is optimal in terms of inliers at a center around 3 between σ 0 v and σ 1 t when all the dual curves are inside L 0 Q and L 1 Q (i.e. when all the points are inliers). This procedure is repeated for all the combination of n points in the image until finding the right center(s) of the annulus (annuli) having n points on B e that maximizes the number of inliers. Since a sorting of complexity O(N log N ) of the intersection is needed and since the algorithm is repeated for every couple of n points, the final complexity is O(N n+1 log N ).

Algorithm

Algorithm 1 gives an example of the nD annulus fitting algorithm. The inputs are a set S of nD points and a width ω. Output is a set V of centers and radius of the best annuli.

Degenerate cases

There are degenerate cases that must be treated carefully when examining the number of inliers and outliers. They can be summarized as follows :

-Invalid radius : L 1 Q represents the internal border of the annulus; when it is negative the annulus is not valid. An example of such invalid radius is seen in Figure 8a, in this figure T becomes inlier at σ 1 T and at σ 0 T instead of σ 0 T since at σ 0 T the radius is negative. -Intersection of L T with L 0 Q and L 1 Q : When both L 0 Q and L 1 Q are each intersected once we have the regular case explained in the Algorithm 1. The degenerate cases occur when one of the two curves is not intersected or when it is intersected twice. These cases can be explained as follows:

• L T and L 0 Q have no common point: in this case the intersection of L T with L 1 Q must be verified. If L 1 Q is not intersected, we must check if L T is between the two curves, in this case T is always inlier, otherwise T is always outlier (Figure 8b). If L 1 Q is intersected once, L T is inside the two curves and T is always inlier (Figure 8c). If L 1 Q is intersected twice, this means that L T is between the two curves and thus the point T is inlier before the first intersection σ 1

T of L T and after the second intersection σ 2

T as seen in Figure 9a. T for i = 0, 1;

9 if σ 0 T < σ 1 T then 10 set f 0 T = 1, f 1 T = -1; 11 else 12 set f 0 T = -1, f 1 T = 1;
13 set the pair (σ i T , f i T ), for i = 0, 1, in AR[2j + i]; • L T has one intersection σ 0 T with L 0 Q : If L T has no intersection with L 1 Q , and L T is inside the two curves before the intersection σ 0 T , then T is inlier before the intersection σ 0 T and becomes outlier after this intersection (Figure 9b); otherwise T is outlier before the intersection σ 0 T and becomes inlier after this intersection. If L T has two intersections with L 1 Q , then we have two cases: T is inlier before the intersection σ 1 T and between σ 2 T and σ 0 T and becomes outlier otherwise (Figure 9c) or T is inlier between the two intersections σ 0 T and σ 1

T and after the intersection σ 2 T and is outlier otherwise.

Experiments

This section presents the 2D and 3D experiments. Q is negative between the two vertical dashed lines; the point T is inlier between σ 1

L 0 Q L T 1 T 0 T 0 T' L 1 Q x-axis y-axis (a) x-axis y-axis L 0 Q L T L 1 Q (b) x-axis y-axis 1 T L 0 Q L T L 1 Q (c)
T and σ 0 T . b) T is always outlier. c) T is always inlier.

x-axis y-axis 13b 151 (0,0,0) 6 3 116

1 T 2 T L 0 Q L T L 1 Q (a) 0 T x-axis y-axis L 0 Q L T L 1 Q (b) 0 T x-axis y-axis 1 T 2 T L 0 Q L T L 1 Q (c)

Example for a 2D Real Image

We tested our method on a real test image, as shown in Figure 10a, whose size is 140x69. Before applying our method, edge detection and mathematical morphological filtering have been performed on the image; the number of points in the image after this preprocessing is 646 points. Our method is then applied to fit an annulus to the set of points. Figure 10b shows the optimal consensus set, which includes 291 inliers. The width of the annulus is fixed to 3.

Example on 2D noisy images

We then applied our method for 2D noisy digital Andres circles (points for Andres circles and noise are generated randomly for 2D as well as for 3D experiments) as shown in Figure 11a, 11b, 12a. For each of these set of points, an annulus of width ω = 1, ω = 1 and ω = 6 is used respectively. Table 1 show the number of points, the optimal consensus set size as well as the center position and the radius R of the inner circle obtained after the fitting.

3D noisy images

We applied our method for 3D noisy digital Andres spheres as shown in Figure 12a, 13a, 13b. For each of these set of points, an annulus of width ω = 3, ω = 1 and ω = 3 is used respectively. The last three lines of Table 1 shows the number of points, the optimal consensus set size as well as the center position and the radius R of the inner sphere obtained after the fitting.

Conclusion and Perspectives

In this paper we have proposed a new approach for fitting nD annulus to a set of points while fixing the width of the annulus. The main advantage of our approach is that it guarantees optimal and exhaustive results from the point of view of the optimal (maximal) consensus set: we are guaranteed to fit an annulus with the least amount of outliers. We are also guaranteed to find all the optimal consensus sets. One of the future works concerns conic fitting such as ellipse, parabola and hyperbola. We also plan to implement a fast 2D/3D algorithm for fitting annulus; such algorithm does not guarantee optimality but guarantees local maximality of inliers in the sense of the set inclusion and thus has a lower time complexity. We also plan to adapt the nD characterization of annulus for k -F lake digital hyperspheres [START_REF] Toutant | Digital circles, spheres and hyperspheres: From morphological models to analytical characterizations and topological properties[END_REF] as an extension of [START_REF] Andres | Optimal consensus set and preimage of 4-connected circles in a noisy environment[END_REF][START_REF] Largeteau-Skapin | O(n 3 log n) time complexity for the optimal consensus set computation for 4-connected digital circles[END_REF].

Fig. 1 .

 1 Fig. 1. Case A of the proof in 2D : a) While decreasing the radius of the annulus (colored black) to reach a first point Q1 we may arrive to an internal radius of 0 (annulus in red) without any point on Be, in this case a translation is needed as shown in b) to reach a point Q1 on Be. c) While Decreasing the radius of the annulus (colored black) by moving the center along axis C2Q1 to reach a second point Q2, we may arrive to an internal radius of 0 and no point Q2 on Be (annulus in red), in this case a rotation is done as shown in d) until reaching a second point Q2 on Be.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Case B of the proof in 2D : a) Decreasing the radius until reaching a point Q1 on Be. b) Decreasing the radius by moving the center along axis CQ1 until reaching a second point Q2.

Fig. 4 .

 4 Fig. 4. Case B of the proof in 3D : a) Decreasing the radius until reaching a first point Q1 on Be. b) Decreasing the radius while maintaining Q1 on the border until reaching a second point Q2. c) Case B of the proof in 3D: moving the center along the bisector of Q1Q2 until reaching a third point Q3.

Fig. 5 .

 5 Fig. 5. a) The 2D annulus having Q1 and Q2 as border point has its centers on the bisector ∆ of the line segment Q1Q2. b) All annuli for which Q1 and Q2 are on Be correspond to the set of all the vertical line segments of length ω having one of its endpoints on L 0 Q and the other on L 1 Q .

Fig. 6 .

 6 Fig.6. 2D example: the point T represented in the dual space by the curve LT intersects the curve L 0 Q at σ 0 T and the curve L 1 Q at σ 1 T . The point T is thus inlier to the annulus having Q1 and Q2 on its external border between σ 0 T and σ 1 T and becomes outlier otherwise. The point T is outlier to the annulus centered at C(-1, 0) and inlier to the one centered at C(1, 0).

Algorithm 1 : 2 initialize

 12 nD Annulus Fitting input : A set S of N grid points and a width ω output: A list V of centers and radius of the best fitted annuli 1 begin M ax = 0; 3 foreach n-uplet ∈ S do 4 compute the barycenter of the n-uplet; 5 initialize the array AR[k] for k = 1, . . . , 2N + 2;

14 j 18 F = F + f k ; 19 if F > M ax then 20 set

 14181920 = j + 1; 15 sort the pair elements (σ k , f k ) for k = 1, . . . , 2j in AR with the values σ k as keys; 16 initialize F = 0; 17 for k = 1, . . . , 2j do M ax = F , Erase V and set it to the interval [σ k , σ k+1 ]; 21 [σ k , σ k+1 ] if F = M ax then 22 add the interval [σ k , σ k+1 ] to V; 23 return V;

Fig. 8 .

 8 Fig. 8. Degenerate cases : a) The value of L 1Q is negative between the two vertical dashed lines; the point T is inlier between σ 1T and σ 0 T . b) T is always outlier. c) T is always inlier.

Fig. 9 .

 9 Fig. 9. Degenerate cases : a) T is inlier before σ 1 T and after σ 2 T . b) T is inlier before σ 0 T . c) T is inlier before σ 1 T and between σ 2 T and σ 0 T .

Fig. 10 .

 10 Fig. 10. An original image in a) and its optimal consensus set colored red in b).

Fig. 11 .

 11 Fig. 11. a) Annulus fitting for a noisy digital Andres circle of width 1. b) Annulus fitting for a digital Andres circle of width 1.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. a) Annulus fitting for a noisy digital Andres circle of width 6. b) Annulus fitting for noisy 3D data; a width w = 3 is used.

Table 1 .

 1 The number of points and the optimal consensus set size.

	Figures Number of points Center	R width Opt. cons. set size
	Figure 10b 646	(104.992,31.017)	28.163 3 291
	Figure 11a 225	(40.871,41)	19.522 1 113
	Figure 11b 65	(31.109,31.109)	14.425 1 65
	Figure 12a 1127	(51,51.008)	26.992 6 1120
	Figure 12b 56	(0.878,1.244,1.976) 1.916	3 51
	Figure 13a 109	(-4,-4,-4)	2.742	1 90
	Figure

Acknowledgments

The authors express their thanks to Mr. Pierre Boulenguez, who contributed in the implementation of a part of the 3D Fitting. The work for this paper was partly financed by Egide, franco-Japanese PHC Sakura project n o 27608XJ and by the Poitou Charentes region project n o 11/RPC-R-051.