Demetrios Xenides
email: xenides@uop.gr

Panaghiotis Karamanis
email: panagiotis.karamanis@univ-pau.fr

Dipole Polarizability of C 28 and its Counterparts Nb 4 B 18 and Ta 4 B 18 . Insights from a Density Functional Theory (DFT) Endeavour

We report on a preliminary investigation of the non linear optical (NLO) properties and in particular dipole polarizability. The target species are two perfect tetrahedral nanoclusters Nb4B18 and Ta4B18, along with their nanofullerene counterpart that is C28. Our study based on density functionals (DFs) that have gained popularity among the scientific community. In addition we performed Hartree-Fock calculations known for not including dynamic electron correlation. The DF obtained values are characterized by some dispersion, with maximal differences to be around 5 %, in all three cases. Given that the DFT introduces a fuzzy percentage of electron correlation sets the observed convergence of HF values to DFT ones is at least surprising. Furthermore, it should be said that though the values can be characterized as accurate their reliability should not be taken for granted. Last, we note the smooth convergence of LC-BLYP, LC-BP86, LC-BPW91 to LC-ωhPBE.

Introduction

The study of the field of nanoclusters emerged as a need to bridge the gap between molecules and matter. Species of this type are building blocks of larger architectures. As such Nb 4 B 18 and Ta 4 B 18 after self-assembling could form the respective face central crystals M 4 B 15 (M=Nb, Ta) [START_REF] Zhang | Perfect Spherical Tetrahedral Metallo-Borospherene Ta4B18 as a Superatom Following the 18-Electron Rule[END_REF].

On the other hand the importance of dipole polarizability (α αβ ) has been elegantly described in the excellent book by Bonin and Kresin [START_REF] Bonin | Electric-Dipole Polarizabilities of Atoms, Molecules, and Clusters[END_REF]. This list has been extended by studies relate it to hardness-softness [START_REF] Hati | Hardness and Electric Dipole Polarizability. Atoms and Clusters[END_REF], aromaticity [START_REF] Jartín | Can aromaticity be connected with molecular polarizability? A theoretical study of benzene isomers and five-membered heterocyclic molecules[END_REF], and other important natural phenomena such as electrostatic interactions that involve molecular polarization [START_REF] Israelachvili | Interactions Involving the Polarization of Molecules[END_REF].

For these reason we have put some effort in calculating dipole polarizablities of Nb 4 B 18 and Ta 4 B 18 in Density Functional Theory (DFT) levels of theory and for the shake of comparison at Hartree-Fock, as well. The DFT methods are still the only alternative as the size of the architecture grows. Therefore, it seems mandatory to check their accuracy and reliability in such calculations.

Computational Details

We have calculated dipole polarizability (α αβ /e 2 α 2 0 E -1 h ) via the Finite Field approach. To ensure the reliability of the method we have used carefully selected field strengths of 0.003 au.

Basis sets of TZVP quality have been used for B, C, Nb and Ta. For the latter two we have also implemented effective core potentials (ECPs) as to take into account the relativistic corrections related to the nature of the two heavy atoms. In particular, these two elements have been described by the def2-TZVP basis set obtained from Basis Set Exchange server [START_REF] Pritchar | A New Basis Set Exchange: An Open, Up-to-date Resource for the Molecular Sciences Community[END_REF]. All calculations have been performed with Gaussian 16 package [START_REF] Frisch | Gaussian[END_REF].

The methods used in the present study are Hartree-Fock (HF) [START_REF] Roothaan | New Developments in Molecular Orbital Theory[END_REF], B- [START_REF] Becke | Density-functional exchange-energy approximation with correct asymptotic-behavior[END_REF] and B3-{LYP,P86,PW91} [START_REF] Becke | Density-functional thermochemistry. III. The role of exact exchange[END_REF][START_REF] Lee | Development of the Colle-Salvetti correlation-energy formula into a functional of the electron density[END_REF][START_REF] Perdew | Density-functional approximation for the correlation energy of the inhomogeneous electron gas[END_REF][START_REF] Perdew | Atoms, molecules, solids, and surfaces: Applications of the generalized gradient approximation for exchange and correlation[END_REF], PBE1PBE [START_REF] Perdew | Generalized gradient approximation made simple[END_REF] and HSEH1PBE [START_REF] Heyd | Erratum: Hybrid functionals based on a screened Coulomb potential[END_REF], CAM-B3LYP [START_REF] Yanai | A new hybrid exchange-correlation functional using the Coulomb-attenuating method (CAM-B3LYP)[END_REF], LC-ωPBE [START_REF] Vydrov | Assessment of a long range corrected hybrid functional[END_REF] as well as LC-{BLYP, BP86, BPW91}, M05 [START_REF] Zhao | Exchange-correlation functional with broad accuracy for metallic and nonmetallic compounds, kinetics, and noncovalent interactions[END_REF] and M052x [START_REF] Zhao | Design of density functionals by combining the method of constraint satisfaction with parametrization for thermochemistry, thermochemical kinetics, and noncovalent interactions[END_REF], M06 and M062x [START_REF] Zhao | The M06 suite of density functionals for main group thermochemistry, thermochemical kinetics, noncovalent interactions, excited states, and transition elements: two new functionals and systematic testing of four M06-class functionals and 12 other functionals[END_REF], M08 [START_REF] Zhao | Exploring the limit of accuracy of the global hybrid meta density functional for main-group thermochemistry, kinetics, and noncovalent interactions[END_REF], ωB97xD [START_REF] Grimme | Semiempirical GGA-type density functional constructed with a long-range dispersion correction[END_REF] and BMK [START_REF] Boese | Development of Density Functionals for Thermochemical Kinetics[END_REF] In the case of C 28 ( 5 A 2 ) all the above methods have been applied at the restricted open (RO) formulation.

In Fig. 1 we have drawn the structure of the three nanoclusters under study. We further add a picture of the HOMO and LUMO orbitals of them as to gain information on the shape of the frontier orbitals.

Results and Discussion

In the case of C 28 the majority of DFT methods produce dipole polarizability values that are greater than the respective RO-HF ones. However, there are the LC-BLYP, LC-BP86, LC-BPW91 and LC-ωhPBE methods that diverge from the trend of the rest of DFT ones. That is the LC correction strongly affects the predictive capability of DF methods. Surprisingly enough the values of the LC methods are closer to ROHF ones, as it can be seen in Fig. 2. In particular the ROHF value is 246.4 when the LC-{BLYP, BP86, BPW91, and ωhPBE} are 246.9, 247.7, 245.5 and 246.2, respectively. The others are lying in the vicinity of 255 as it can be also seen in Table 1. The same trend had been observed in a study by Sekino et al [START_REF] Kirtman | Calculation of electric dipole (hyper)polarizabilities by long-range-correction scheme in density functional theory: A systematic assessment for polydiacetylene and polybutatriene oligomers[END_REF] on dipole (hyper)polarizablities of polydiacetylene and polybutatriene. What we have seen from the above made analysis is that in all three cases DFs methods caused a positive (enhancement) or negative (lowering) of the respective HF dipole polarizability values. Furthermore, it is known that DFs methods introducing a (fuzzy) percentage of dynamic electron correlation. That is the reason of gaining their popularity (along with the fact that they need moderate computational resources). In the present study the DFs produced results differ by the most of 5 % from the HF ones. Moreover, it is the nature of them that does not allow for naming one of them as method of preference. That, probably, justifies the question of whether there is a need of a calculation of DFT type when a HF one produces similar results, without the accompanying uncertainty of the DFT methods.

Last but not least, we note the remarkably similarity of dipole polarizability of both M 4 B 18 (M=Nb, Ta). Thus, it is fair to assume that the nature of the heavy atom has a negligible effect on this interesting property.

Conclusion

Having performed restricted open shell calculations on the C 28 ( 5 A 1 ) fullerene we found that most of the functionals enhance the value of dipole polarizability. In striking difference is the LC-({BLYP, BP86, BPW91, ωhPBE}) family of functionals that produces results similar to ROHF ones. The inverse has been observed in M 4 B 18 (M=Nb, Ta) nanoclusters. In particular DF methods lower the value of Hartree-Fock polarizability. This is most intense in the case of LC family. However, in all cases the DFT values are around 5 % lower or greater than the HF ones. This could raise the question whether there is a need of calculation of DF type instead of a pure HF one, that it is known for its limitations. Last, we note that both heavy metal including moieties are characterized by almost identical dipole polarizability values. Therefore, it is fair to assume that there is a negligible effect of the nature of heavy atom on the value of dipole polarizability.

Figure 1 .

 1 Figure 1. Structure and HOMO LUMO orbitals of and C 28 Nb 4 B 18 and Ta 4 B 18 .

  methods are restricted open (RO) ROHF value of 246.4

Figure 2 .

 2 Figure 2. Dipole polarizabilities of Nb 4 B 18 , Ta 4 B 18 and C 28 .

Table 1 .

 1 Dipole polarizability values of C 28 , Nb 4 B 18 , and Ta 4 B 18 at HF and DFT levels of theory (restricted open (RO) shell calculations have been performed in the case of C 28 ). We note that in contrast to the rest of the methods BLYP(364.56) and BMK(367.39) values are larger than the HF ones. The LC correction affected the most the obtained values. This can be seen as a sharp lowering of the obtained values. In particular LC-{BLYP, BP86, BPW91 and ωhPBE} values are 352.24, 349.32, 345.74 and 347.57, respectively. The M05 method produces a value of 353.38, that is the one being close to the LC family. The other functionals produce values that are in between 355 and 360 au.For M being Ta, the BP86(361.98), B3LYP(361.91), M06(361.46) and ωB97xD(362.98) are the ones that are noticeable proximal to HF(362.09) one. A smooth convergence of LC-BLYP,

		C 28	Nb 4 B 18 Ta 4 B 18
	HF	246.4 362.82	362.09
	BLYP	263.9 364.56	364.95
	BP86	264.5 361.15	361.98
	BPW91	262.0 357.07	357.95
	LC-BLYP	246.9 352.24	351.92
	LC-BP86	247.7 349.32	349.49
	LC-BPW91	245.5 345.74	345.99
	B3LYP	260.0 361.49	361.91
	B3P86	259.7 356.96	357.87
	B3PW91	258.6 355.89	356.69
	CAM-B3LYP 254.2 358.40	358.47
	PBE1PBE	257.3 355.56	356.12
	LC-ωhPBE	246.2 347.57	347.79
	HSEH1PBE	258.3 356.84	357.45
	ωB97xD	255.5 361.95	362.98
	BMK	259.8 367.39	369.41
	M05	252.1 353.38	352.77
	M052x	256.5 356.75	357.81
	M06	261.4 360.19	361.46
	M062x	257.5 355.74	356.81
	M08	255.1 354.97	355.86
	Quite opposite is the behaviour of the methods in the case of M 4 B 18 (M=Nb, Ta)
	nanoclusters.
	When M=Nb the BLYP(364.56), BP86(361.15), B3LYP(361.49) and ωB97xD(361.95) values
	are quite close to the HF(362.82).


L Provot
email: provot@loria.fr

I Debled-Rennesson

Geometric Feature Estimators for Noisy Discrete Surfaces ⋆

We present in this paper robust geometric feature estimators on the border of a possibly noisy discrete object. We introduce the notion of patch centered at a point of this border. Thanks to a width parameter, attached to a patch, the noise on the border of the discrete object can be considered, and an extended flat neighborhood of a border point is computed. Stable geometric features are then extracted around this point. A normal vector estimator is proposed as well as a detector of convex and concave parts on the border of a discrete object.

Introduction

Geometric feature estimation on the surface of a discrete object is very important in digital geometry. For instance, in computer vision, rendering algorithms rely on the normal vector estimation on the surface of an object to produce a realistic view of this object. In image analysis, features such as area or curvature can be used for producing classification functions able to sort objects by shape or by size. In bioinformatics, in the protein-protein docking framework, one tries to associate two proteins according to their geometrical complementarity. Thus, it is important to locate critical areas on the surface, like holes (concave parts) and knobs (convex parts) or even big flat areas.

Several studies [START_REF] Yagel | Normal estimation in 3d discrete space[END_REF][START_REF] Thürmer | Normal computation for discrete surfaces in 3d space[END_REF][START_REF] Lenoir | Fast estimation of mean curvature on the surface of a 3d discrete object[END_REF][START_REF] Papier | Évaluation de la normale au bord d'un objet discret 3d[END_REF][START_REF] Tellier | 3d discrete normal vectors[END_REF][START_REF] Coeurjolly | Multigrid convergence and surface area estimation[END_REF][START_REF] Hermann | Multigrid analysis of curvature estimators[END_REF] have been done on different types of estimators but the estimated geometric features are by definition very local. Thus, the noise introduced by acquisition tools like scanners or MRI, even weak, is disturbing for the estimator, and classical algorithms of digital geometry which rely on the regularity of discrete primitives do not always yield good results.

Therefore, for the last few years, the interest around the geometry of noisy objects has grown [START_REF] Veelaert | Uncertain geometry in computer vision[END_REF][START_REF] Debled-Rennesson | Linear segmentation of discrete curves into fuzzy segments[END_REF][START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF][START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. New discrete primitives such as blurred segments and blurred pieces of discrete planes have been introduced and, thanks to a width parameter, enable to take into account the noise in data while controlling the approximation. Encouraging results have been obtained in 2D for the curvature estimation, relying on blurred segments [START_REF] Nguyen | Curvature estimation in noisy curves[END_REF].

In this paper we deal with the 3D case. In section 2, after recalling the definition of blurred pieces of discrete planes, we introduce the notion of a widthν patch centered at p. In section 3, we then present some features (normal vector, area, outline) of a width-ν patch centered at p. With this material we develop, in section 4, an estimator able to distinguish between points that belong to concave, convex or flat parts of the surface of a possibly noisy discrete object. The paper ends up with some conclusions and perspectives in section 5.

Basic Notions and Definitions

Hereafter we denote by O b a possibly noisy 6-connected discrete object. We call surface or border of O b the set of points B b which have a 6-neighbor that does not belong to O b .

Before presenting the notion of a width-ν patch centered at p, we recall the definition of a width-ν blurred piece of discrete plane [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF], which is the underlying discrete primitive of the patch.

Blurred Pieces of Discrete Planes

One can see a blurred piece of discrete plane as an arithmetic discrete plane for which some points are missing. More formally: Definition 1. Let N be a norm on R 3 and E a set of points in Z 3 . We say that the discrete plane P(a, b, c, µ, ω)1 is a bounding plane of E if all the points of E belong to P, and we call width of P(a, b, c, µ, ω), the value ω-1 N (a,b,c) . A bounding plane of E is said optimal if its width is minimal.

Definition 2.

A set E of points in Z 3 is a width-ν blurred piece of discrete plane if and only if the width of its optimal bounding plane is less than or equal to ν.

Two recognition algorithms of blurred pieces of discrete planes have been proposed in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. The first one considers the Euclidean norm and, for a set of points P in Z 3 , it solves the recognition problem by using the geometry of the convex hull of P . The second one considers the infinity norm and uses methods from linear programming to solve the recognition problem.

In the following sections, the results we present have been obtained by using the geometrical approach which uses the Euclidean norm.

Width-ν Discrete Patches

Here we are interested in the computation of different geometric features of a possibly noisy discrete surface, such as the normal vector, the area or the curvature. Numerous methods exist in the literature to compute such features in the discrete space. One can refer to [START_REF] Yagel | Normal estimation in 3d discrete space[END_REF][START_REF] Lenoir | Fast computation of the normal vector field of the surface of a 3-d discrete object[END_REF][START_REF] Thürmer | Normal computation for discrete surfaces in 3d space[END_REF][START_REF] Papier | Évaluation de la normale au bord d'un objet discret 3d[END_REF][START_REF] Tellier | 3d discrete normal vectors[END_REF] for normal vectors estimation and [START_REF] Lenoir | Fast estimation of mean curvature on the surface of a 3d discrete object[END_REF][START_REF] Hermann | Multigrid analysis of curvature estimators[END_REF] for curvature estimators.

The problem is that these geometric features are by definition very local. And most of the defined estimators are very noise sensitive. But if we know that we are working on a noisy surface, we would like to use estimators that take into account the irregularity of this surface. A way to estimate these features at a point p of the noisy surface is to use the information of the points lying in a neighborhood of p. The notion of patch we present hereafter takes place in this framework, considering an adaptive neighborhood around p. Definition 3. Let B b be the border of a discrete object and p a point in B b . Let T be a scan process of the neighboring points of p in B b and ν the greatest real value allowed. We call width-ν patch centered at p, and denote by Γ ν (p), a width-ν blurred piece of discrete plane incrementally recognized from p by adding points of B b following the scan process T .

About the Incremental Recognition:

We construct a width-ν patch centered at p using the incremental recognition algorithm of blurred pieces of discrete planes introduced in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. We add the points following the scan process T and as soon as the width of the blurred piece of discrete plane becomes greater than ν we stop the recognition process.

About the Scan Process T : To uniformly spread the patch in all directions the best solution would be to scan the neighborhood of p according to a geodesic distance. Nevertheless, for efficiency, we have chosen to scan this neighborhood according to a chamfer mask 3, 4, 5 which is a good approximation of the geodesic distance [START_REF] Thiel | Chamfer masks : discrete distance functions, geometrical properties and optimization[END_REF][START_REF] Borgefors | On digital distance transforms in three dimensions[END_REF]. The aim is to have a well-balanced patch around p which looks almost circular. To implement this behaviour we use a priority queue Q. This method has originaly been proposed by Verwer et al. [START_REF] Verwer | An efficient uniform cost algorithm applied to distance transforms[END_REF] and first used by Coeurjolly on digital surfaces [START_REF] Coeurjolly | Visibility in discrete geometry: An application to discrete geodesic paths[END_REF]. We start by pushing p into the queue with a weight equals to zero. Then, while we do not exceed the limit width ν, we pop out of Q the point v with the lowest weight w and we add v to the blurred piece of discrete plane we are recognizing. We then add the border voxels of the 26-neighborhood of v into the priority queue as follows:

the 6-neighbors are added in Q with a weight of w + 3, -the strict 18-neighbors are added in Q with a weight of w + 4, -and finally the strict 26-neighbors are added in Q with a weight of w + 5.

To stay homeomorphic to a topological disk, we take care to add a point only if it does not create a hole in the patch, by using the technique described in [START_REF] Provot | Segmentation of noisy discrete surfaces[END_REF]. With this method we obtain patches like those in Fig. 2. 3 Patch Features

Intuition

A patch Γ ν (p), as previously defined, characterizes the planarity of the surface around p (with respect to the width ν). Thus, the more the patch is spread, the lesser the surface around p is bent.

In addition, if the growth of Γ ν (p) stopped, it means that the close neighboring points outside Γ ν (p) would bend the patch too much if they were added. In that case the patch could no longer be regarded as flat. Therefore, it is possible to deduce a conformation of the discrete surface around p by studying the patches centered along the points of the outline of Γ ν (p).

To quantify these observations we have to compute the patch area, extract the outline of Γ ν (p) and study the lie of the patches in the neighborhood of Γ ν (p). This is what we present in the following sections.

Width-ν Normal

With the previous intuition we can see that the normal vector of Γ ν (p) is a good estimation of the normal at p. Thus, assimilating the normal vector of Γ ν (p) to the normal of the surface at p, we define a normal vector estimator for each point of the surface of a possibly noisy discrete object. Definition 4. Let B b be the border of a discrete object and p a point of B b . We call width-ν normal at p the normal vector

-→ n ν (p) = -→ n (Γ ν (p))
where -→ n (Γ ν (p)) is the normal vector of the patch Γ ν (p).

Other normal estimators have been proposed before. For instance, L. Papier [START_REF] Papier | Évaluation de la normale au bord d'un objet discret 3d[END_REF] estimates the normal vector at a point p of the surface using a weighted mean of the elementary unit normals of the surfels in the neighborhood of p (umbrella of order n). The size of the neighborhood around p can be set with the parameter n. In [START_REF] Lenoir | Fast computation of the normal vector field of the surface of a 3-d discrete object[END_REF], A. Lenoir uses the slices of the object along the three canonical planes. He first computes tangential lines through p in these slices using partial derivatives computation (implemented by convolution products). He then gives a normal vector estimation using these tangential lines. The size of the neighborhood around p can be set with a scale factor. Although these methods can deal with noise, the considered neighborhood is not adaptive, contrary to our approach which fits the shape of the surface. Some results on noisy and non-noisy spheres (see Fig. 3) of different radius are presented in Tab. 1.

To synthetize noisy spheres we start to generate a discrete sphere (i.e. the set of points (x, y, z) ∈ Z 3 | x2 + y 2 + z 2 < r(r + 1) where r is the radius of the sphere). We then add noise by randomly moving outward a border voxel of the sphere. To add more noise we just repeat the last step.

We have compared the estimated normal vectors to the theoretical normal vectors 2 at p. The mean angular value δ moy , in degrees, the maximal angular value δ max and the standard deviation σ are presented in Tab 1.

We can see that with our method the greater the radius of the spheres is, the better the estimation is, contrary to the method based on the 26-neighborhood where there is no real improvement. It is due to the fact that our method is adaptive and considers a wider neighborhood when the sphere radius increases. It behaves like this because when the sphere radius increases the surface around p tends to be flat. For a given width the patch can thus spread more around p. Moreover, when the noise level increases the estimation of the normal vector is less accurate. The bad results obtained when ν = 1 can be attributed to the tiny size of patches which do not always cover the 26-neighborhood of the point p. But when the width of the patches increases, say ν = 2 or 3, the results are better than those obtained with the 26-neighborhood approach, and it is the case for noisy spheres as well as for non-noisy ones.

Width-ν Patch Area

Here we use the notations from [START_REF] Coeurjolly | Multigrid convergence and surface area estimation[END_REF]. Let S be an Euclidean surface and { -→ n } its normal vector field. We can compute the area of S in the continuous space with the formula:

A(S) = S -→ n (s) ds
Now, if we consider a digitization D(S) of S, we can replace the integral over S by a finite sum over the surfels s of D(S), the vector -→ n (s) by an estimation of the normal vector at s and ds by a dot product with the unit orthogonal vector of s pointing outward. The idea is to compute the contribution of each surfel to the global area of D(S) by projecting the surfel according to the direction of the normal vector. The discrete version of the previous equation is:

E A (D(S)) = s∈D(S) -→ n * (s). -→ n el (s)
where -→ n * (s) is an estimation of the normal vector associated to the surface element s in D(S) and -→ n el (s) is the elementary normal vector of s. This method was first proposed in 3D by A. Lenoir in [START_REF] Lenoir | Fast computation of the normal vector field of the surface of a 3-d discrete object[END_REF]. Then, in [START_REF] Coeurjolly | Multigrid convergence and surface area estimation[END_REF], Coeurjolly et al. proved that this estimator is convergent if and only if the normal vector estimation is convergent.

In our case we can use the normal estimator proposed in section 3.2 with the previous formula to obtain an estimation of the area for the surface of a width-ν patch:

E A (Γ ν (p)) = s∈S Γν (p) -→ n ν (p). -→ n el (s) = -→ n ν (p). s∈S Γν (p) -→ n el (s)
where S Γν (p) denotes the set of surface surfels of Γ ν (p).

Patch Outline

To study the surrounding patches of Γ ν (p), we have to clarify the notion of surrounding. We have chosen to study the conformation of the patches which are centered on points belonging to the outline of Γ ν (p). Let B b be the border of a discrete object O b . We denote by S b the set of surfels of B b which are incident to a point that does not belong to O b , and S Γν (p) the subset of S b that belongs to Γ ν (p). A point q belongs to the outline of Γ ν (p) if the voxel representation of q has a surfel s ∈ S Γν (p) and if there exists a surfel s ′ ∈ S b \ S Γν (p) such that s and s ′ are adjacent by edge. An example of the outline of a patch is shown in Fig. 5.

Shape

Concave and Convex Parts

With the different notions defined in the previous sections, we present an estimator that permits to characterize the shape (concave, convex or flat) around a border point of a discrete object.

The idea is to start by spreading a patch Γ ν (p) and to compute its outline C. For each point q i,1≤i≤|C| in C, we then develop the neighboring patches Γ ν (q i ). From these patches we obtain a vector field { -→ n ν (q i )} on the outline C. This vector field is shown in Fig. 6 for a convex and a concave area.

Observation : In the concave parts the vector field { -→ n ν (q i )} points towards the normal vector -→ n ν (p) of the central patch, but in the convex parts the vector field has the reverse tendency. It is thus possible to distinguish concave and convex parts with the value of the oriented angle between the normal vector -→ n ν (p) and the vectors { -→ n ν (q i )}. Our estimator is based on this observation. Let C be the set of points that belong to the outline of Γ ν (p). Our shape estimator of the surface around a point p is then given by the formula :

F ν (p) = 1 |C| ∀q∈C ( -→ n ν (p), -→ n ν (q)) • E A (Γ ν (q)) E A (Γ ν (p))
where ( -→ n ν (p), -→ n ν (q)) is the oriented angle value between the two normal vectors. So, the estimator F ν (p) is a weighted mean of the angle values between -→ n ν (p) and the -→ n ν (q i ) 1≤i≤|C| .

Angle Orientation : We determine the sign of the angle value ( -→ n ν (p), -→ n ν (q)) as shown in Fig 7 . To implement this process, we compute the cross products -→ n ν (p) ∧ -→ pq and -→ n ν (p) ∧ -→ n ν (q). If the two resulting vectors more or less point

( -→ n ν (p) ∧ -→ pq) • ( -→ n ν (p) ∧ -→ n ν (q)
) is positif) then the angle value is counted positively, otherwise the angle value is counted negatively. The computation of the previous cross products are feasible only if the vectors are not collinear. And the scalar product also does not have to be nil. Usually, these conditions are always verified. But sometimes, especially when the patch is very small, some degenerate cases can occur. Because they do not bring a useful shape information we can easily get rid of these cases by ignoring them and going on with the next point of the outline.

Weighting Factor : It is clear that a wide patch Γ ν (p) means that the surface around p tends to be flat (according to the width ν). Thus, the wider Γ ν (p) is, the lesser the influence of the surrounding patches is to consider. Hence, the weighting factor

1 E A (Γν (p)) is used in F ν (p).
On the other hand, if a neighboring patch Γ ν (q i ) is wider than another neighboring patch Γ ν (q j ), then it means that the surface around q i is a little more stable than the surface around q j . Thus we choose to lend more influence to information given by bigger patches. Therefore, we associate the weighting factor E A (Γ ν (q)) to the angle value ( -→ n ν (p), -→ n ν (q)) in the formula F ν (p).

Interpretation : As a result, F(p) is positive when the surface around p is rather convex and F(p) is negative when the surface around p is rather concave. An increasing value of |F(p)| means that the surface around p is more strongly concave or convex. If Γ ν (p) is big, a value F(p) close to 0 means that the area around p is almost flat (according to the width ν we chose). If Γ ν (p) is small, then the border around p is strongly distorted, but in a way we can neither qualify concave, nor qualify convex (a saddle point for instance). Some results obtained with this estimator are given in Fig. 8. To render the object we have associated to each face of a voxel v the normal -→ n ν (v).

Conclusion

In this paper we have introduced a new notion related to a point on a discrete surface : the width-ν patch centered at p. From this patch we have designed a robust normal vector estimator at the surface of a possibly noisy discrete object.

Moreover, based on the computation of the patch area, we have proposed an estimator that characterizes the shape (concave, convex or flat) of the surface around the point p. Although the approaches presented in this paper give plausible results, more formal studies on the notion of noise have to be led. A work on the convergence of the estimators could then be envisaged.

In addition more comparative studies with other methods have to be done to confirm the reliability of these estimators. In a theoretical point of view it would be interesting to see the relation of our shape estimator with the classical notion of surface curvature.

Fig. 1 .

 1 Fig. 1. (a) A width-3 blurred piece of discrete plane and (b) its optimal bounding plane P(4, 8, 19, -80, 49), using the Euclidean norm.

Fig. 2 .

 2 Fig. 2. An example of width-2 patches spread on the surface of different noisy objects. (a) A sphere of radius 20, (b) a 150 × 6 × 200 box and (c) a cube of edge 25.

Fig. 3 .

 3 Fig. 3. A discrete sphere of radius 10 (a) without noise, (b) weakly noisy and (c) strongly noisy.

Fig. 4 .

 4 Fig. 4. Normal vector estimation on a weakly noisy sphere of radius 20 (a) using only the 26-neighborhood and (b) using the patch based approach with ν = 3.

Fig. 5 .

 5 Fig. 5. The outline (in dark grey) of a width-2 grey patch centered at the black point.

Fig. 6 .

 6 Fig. 6. Vectors layout on the outline of a patch (a, c) in a convex area and (b, d) in a concave area.

Fig. 7 .

 7 Fig. 7. Angle orientation.

Fig. 8 .

 8 Fig. 8. Concave, convex and flat areas (according to the color scale on the left) on different objects using width-3 patches.

Table 1 .

 1 Comparison between the proposed normal vector estimator and the one using only the 26-neighborhood. Angle values δ are in degrees • .

	Tested spheres	Without noise	Weakly noisy	Strongly noisy
		Radius		10	20	40	10	20	40	10	20	40
			δmoy 3.66 2.05 1.04 10.36 9.08 9.04 15.30 14.10 14.33
		ν = 1 δmax 8.21 6.10 3.25 52.53 91.25 101.24 95.46 101.42 117.80
			σ	1.83 1.07 0.58 7.70 7.50 7.82 12.46 11.90 11.95
			δmoy 2.33 1.25 0.77 3.66 2.39 1.46 5.65 4.57	4.35
	Width	ν = 2 δmax 9.92 3.35 2.94 16.86 10.16 5.83 46.98 40.54 52.57
			σ	1.49 0.61 0.44 2.19 1.35 0.78 3.77 3.33	3.97
			δmoy 1.85 1.17 0.70 2.75 1.74 1.02 3.29 2.37	1.70
		ν = 3 δmax 6.49 3.93 2.58 8.90 7.46 3.89 14.63 8.80	7.32
			σ	0.98 0.69 0.40 1.54 0.92 0.55 1.90 1.30	0.93
			δmoy 4.61 4.50 4.22 7.55 7.50 7.51 8.83 8.69	8.57
	26-neighborhood	δmax 9.45 15.34 17.19 28.35 25.34 31.14 24.29 37.15 33.80
			σ	2.70 2.75 2.81 4.19 4.10 4.19 4.52 4.87	4.80

An arithmetic discrete plane P(a, b, c, µ, ω) is the set of integer points (x, y, z) verifying µ ≤ ax + by + cz < µ + ω, where (a, b, c) ∈ Z 3 is the normal vector of the plane. µ ∈ Z is named the translation constant and ω ∈ Z the arithmetical thickness.

The theoretical normal vector is the vector starting from the center of the sphere to p

⋆ This work is supported by the ANR in the framework of the GEODIB project.


L Provot
email: provot@loria.fr

I Debled-Rennesson

Segmentation of Noisy Discrete Surfaces

We propose in this paper a segmentation process that can deal with noisy discrete objects. A flexible approach considering arithmetic discrete planes with a variable width is used to avoid the oversegmentation that might happen when classical segmentation algorithms based on regular discrete planes are used to decompose the surface of the object. A method to choose a seed and different segmentation strategies according to the shape of the surface are also proposed.

Introduction

Three-dimensional discrete objects are widely used in medical area. Due to their internal structure and their huge size, the manipulation of such objects is not an easy task. Rendering algorithms for instance, cannot apply usual techniques to obtain a nice visualization of the objects. A general idea to address this problem is to transform the discrete volume into a Euclidean polyhedra. The segmentation of the border of such objects into discrete primitives is thus a natural first step and several studies have been led on the subject.

In [START_REF] Françon | Polyhedrization of the boundary of a voxel object[END_REF], L. Papier and J. Françon propose a segmentation of the surface of a discrete object into pieces of standard arithmetic discrete planes. These standard planes are recognized using a Fourier-Motskin elimination algorithm [START_REF] Françon | Recognizing arithmetic straight lines and planes[END_REF] and are forced to be homeomorphic to a topological disk in order to be used in a polyhedrization process. They state that the resulting segmentation heavily depends on the choice of the seed to start the recognition of a new face and the tracking order of the points chosen for enlarging the current face, but do not address these problems.

In [START_REF] Burguet | Strong thinning and polyhedrization of the surface of a voxel object[END_REF], J. Burguet and R. Malgouyres have developed a polyhedrization algorithm based on the computation of a topological Voronoï diagram. Seeds are distributed on the surface of the discrete object according to its curvature [START_REF] Lenoir | Fast estimation of mean curvature on the surface of a 3d discrete object[END_REF] and a thinning algorithm is used to generate the skeleton of this surface without the seeds. The resulting Voronoï regions can then be seen as a segmentation of the surface.

In the framework of surface area estimation [START_REF] Klette | Digital planar segment based polyhedrization for surface area estimation[END_REF], R. Klette and H.J. Sun have proposed a segmentation of the surface into digital planar segments (DPS) -This work is supported by the ANR in the framework of the GEODIB project.

which are actually pieces of standard discrete planes. To incrementally check whether a set of points is a DPS, they compute the convex hull of this set to retrieve a specific pair of parallel planes for which the main diagonal distance has to be less than √ 3. A breadth-first search of the surfel graph representing the surface is used to incrementally add points into the DPS.

In [START_REF] Sivignon | Decomposition of a three-dimensional discrete object surface into discrete plane pieces[END_REF], I. Sivignon et al. have compared different tracking processes to decompose the surface of a discrete object into naive discrete planes. A dual-space approach is used to incrementally recognize the pieces of planes [START_REF] Vittone | Recognition of digital naive planes and polyhedrization[END_REF]. In [START_REF] Sivignon | Discrete surface segmentation into discrete planes[END_REF] the authors have also studied the relation between a segmentation into naive and standard discrete planes depending on the considered surface definition.

Although these methods are reversible and behave well with regular discrete objects, they might lead to an over-segmentation with noisy ones. In this paper we try to be more flexible and address the problem by considering a segmentation into pieces of discrete planes with a variable width. A first pre-processing step is done to compute geometric features of the surface of a possibly noisy discrete object. We then use these goemetric features to take into account the shape of the object to choose the seeds and to guide the incremental growth of the segments.

In section 2, after recalling the definition of blurred pieces of discrete planes, we summarize results from [START_REF] Provot | Geometric feature estimators for noisy discrete surfaces[END_REF] about geometric features for noisy discrete surfaces. The different steps of the segmentation process are then described in section 3, followed by some results on noisy and non-noisy objects. The paper ends up with a conclusion and some perspectives in section 4.

Background

We recall in this section the definition of a width-ν blurred piece of discrete plane, an arithmetical discrete primitive introduced in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF], that allows to deal with noisy discrete data. Relying on this primitive, we present the notion of a width-ν patch centered at a border point of a discrete objet and some features of the border obtained from this patch. More details about the construction of the patch and the study of different features of the border can be found in [START_REF] Provot | Geometric feature estimators for noisy discrete surfaces[END_REF].

Blurred Pieces of Discrete Planes

One can see a blurred piece of discrete plane as an arithmetic discrete plane for which some points are missing. More formally: Definition 1. Let N be a norm on R 3 and E a set of points in Z 3 . We say that the discrete plane P(a, b, c, µ, ω) 1 is a bounding plane of E if all the points of E belong to P, and we call width of P(a, b, c, µ, ω), the value ω-1 N (a,b,c) . A bounding plane of E is said optimal if its width is minimal. Definition 2. A set E of points in Z 3 is a width-ν blurred piece of discrete plane if and only if the width of its optimal bounding plane is less than or equal to ν. Two recognition algorithms of blurred pieces of discrete planes have been proposed in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. The first one considers the Euclidean norm and, for a set of points P in Z 3 , it solves the recognition problem by using the geometry of the convex hull of P . The second one considers the infinity norm and uses methods from linear programming to solve the recognition problem.

Thereafter, we denote by O b a possibly noisy 6-connected discrete object. We call surface or border of O b the set of points B b which have a 6-neighbor that does not belong to O b . All the results we present on this type of objects have been obtained by considering the geometrical approach which uses the Euclidean norm.

Width-ν Discrete Patches

If we are working on a noisy discrete surface and need to extract some of its local geometric features, such as the normal vector or the curvature, it is wise to use estimators that take into account the irregularity of this surface to compute these kinds of features. A way to achieve this task at a point p of the surface is to gather the information of points lying in an extended neighborhood of p. The notion of patch we present hereafter takes place in this framework, considering an adaptative neighborhood around p. Definition 3. Let B b be the border of a discrete object, p a point in B b and ν the greatest real value allowed. Let d be a distance. At each point q ∈ B b we associate the weighting factor d p (q) = d(p, q). We call width-ν patch centered at p, and denote by Γ ν (p), a width-ν blurred piece of discrete plane incrementally recognized from p by adding points q of B b following the increasing values of d p (q). About the Incremental Recognition: We construct a width-ν patch centered at p using the incremental recognition algorithm of blurred pieces of discrete planes introduced in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. We add the points following the increasing values of d p and, as soon as the width of the blurred piece of discrete plane becomes greater than ν, we stop the recognition process.

About the Distance d:

To uniformly spread the patch in all directions, the best solution would be to use a geodesic distance. Nevertheless, for efficiency, we have chosen to rely on a distance based on a chamfer mask 3, 4, 5 which is a good approximation of the geodesic distance [START_REF] Borgefors | On digital distance transforms in three dimensions[END_REF]. The aim is to have a wellbalanced patch around p which looks almost circular. With this method we obtain patches like those in Fig. 2.

Patch Features

A patch Γ ν (p), as previously defined, characterizes the planarity of the surface around p (with respect to the width ν). Thus, the more the patch is spread, the less the surface around p is bent.

In addition, if the growth of Γ ν (p) stopped, it means that the close neighboring points outside Γ ν (p) would bend the patch too much if they were added. In that case the patch could no longer be regarded as flat. Therefore, it is possible to deduce a conformation of the discrete surface around p by studying the patches centered along the points of the outline of Γ ν (p).

The following definitions give a formal quantization of all these observations.

Width-ν Normal With the previous intuition we can see that the normal vector of Γ ν (p) is a good estimation of the normal at p. Thus, assimilating the normal vector of Γ ν (p) to the normal of the surface at p, we define a normal vector estimator for each point of the surface of a possibly noisy discrete object.

Definition 4. Let B b be the border of a discrete object and p a point of B b . We call width-ν normal at p the normal vector

-→ n ν (p) = - → n (Γ ν (p))
where -→ n (Γ ν (p)) is the normal vector of the patch Γ ν (p).

Width-ν Patch Area Given a Euclidean surface S and its normal vector field { -→ n }, in the continuous space we can compute the area of S with the formula:

A(S) = S - → n (s) ds
The discrete version of this equation given in [START_REF] Coeurjolly | Multigrid convergence and surface area estimation[END_REF] has been adapted as follows to compute the area of the surface of a width-ν patch:

E A (Γ ν (p)) = s∈S Γν (p) -→ n ν (p). - → n el (s) = -→ n ν (p). s∈S Γν (p) - → n el (s)
where S Γν (p) is the set of surfels 2 of the patch surface, and -→ n el (s) the elementary normal vector of s. Let C be the set of points that belong to the outline of Γ ν (p). Our shape estimator of the surface around a point p is then given by the formula :

Shape Estimator

F ν (p) = 1 |C| ∀q∈C ( -→ n ν (p), -→ n ν (q)) • E A (Γ ν (q)) E A (Γ ν (p))
where ( -→ n ν (p), -→ n ν (q)) is the oriented angle value between the two normal vectors. So, the estimator F ν (p) is a weighted mean of the angle values between -→ n ν (p) and the -→ n ν (q i ) 1≤i≤|C| .

F ν (p) is positive when the surface around p is rather convex and F ν (p) is negative when the surface around p is rather concave. An increasing value of |F ν (p)| means that the surface around p is more strongly concave or convex. Moreover, if Γ ν (p) is big, a value F ν (p) close to zero means that the area around p is almost flat (according to the width ν we chose). If Γ ν (p) is small, then the area around p is strongly distorted, but in a way we can neither qualify concave, nor qualify convex (a saddle point for instance).

Segmentation

Introduction

The segmentation of a tridimensional discrete object we will describe in this section consists in partitioning the border of the object into pieces of discrete planes. Some studies have been led on the subject [START_REF] Klette | Digital planar segment based polyhedrization for surface area estimation[END_REF][START_REF] Sivignon | Decomposition of a three-dimensional discrete object surface into discrete plane pieces[END_REF][START_REF] Sivignon | Discrete surface segmentation into discrete planes[END_REF][START_REF] Burguet | Strong thinning and polyhedrization of the surface of a voxel object[END_REF][START_REF] Françon | Polyhedrization of the boundary of a voxel object[END_REF] but they all consider regular planes with a fixed width (mainly naive or standard arithmetic discrete planes). Although these methods give good results with regular discrete objects (Fig. 3(a)), it is not always the case when we have to deal with irregular or noisy discrete objects (Fig. 3(b)). In particular, irregularities force to create lots of small segments. The approach we present hereafter is more flexible and considers a segmentation into pieces of planes with a variable width, width-ν blurred pieces of discrete planes (denoted BP DP ν in the sequel) to be specific, to deal with noisy data.

Segmentation into Blurred Pieces of Discrete Planes

Firstly, a pre-processing step is done on the borber B b of the discrete object we want to segment. Given a real ν, for each point p ∈ B b we compute a width-ν patch centered at p as explained in section 2.2. At each point p we can thus associate the features presented in section 2.3, that is:

the normal vector -→ n ν (p), the area factor E A (Γ ν (p)), and the shape factor F ν (p).

Our segmentation process can be summed up to the following steps: a seed is chosen among points of B b to start a first BP DP ν recognition that grows through a process of accretion. An adjacent point is selected and added to BP DP ν if it satisfies some required criteria. The BP DP ν eventually stops growing when there are no more adjacent points that can be added without contradicting the criteria. This procedure is repeated from a new seed until all points of B b belong to a BP DP ν .

In the following paragraphs we will discuss more in details the different key points of this segmentation algorithm.

Seed Selection. The easiest way to choose a seed is to randomly pick a border point which does not belong to a BP DP ν and to start the recognition process from there. The problem with this approach is that we have no control over the segmentation. To segment a cube for instance, a bad choice would be to start from seeds that lie near an edge of the cube. This would result in an over-segmentation as shown in Fig 4.

A better choice is to start from seeds that are lying in flat areas. It is indeed more meaningful to give a higher priority to flat areas than to bent areas since the underlying primitive of a BP DP ν is an arithmetical discrete plane. Chances to have a better approximation are thus higher. Therefore we have chosen to rely on the area estimator E A (Γ ν (p)) to find the seeds. The idea is to pick the border point p (not yet processed) which has the highest E A (Γ ν (p)) value as the next seed.

BP DP ν Recognition. The algorithm used to incrementally recognize widthν blurred pieces of discrete planes is the geometrical one proposed in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF] by considering the Euclidean norm.

The spreading of a BP DP ν heavily depends on the way the neighborhood of the seed is visited as explained in [START_REF] Sivignon | Decomposition of a three-dimensional discrete object surface into discrete plane pieces[END_REF]. For the same reasons as before, the value E A (Γ ν (p)) is used in the accretion process. Points p adjacent to the evolving BP DP ν are added according to their decreasing E A (Γ ν (p)) values.

To implement this behaviour we use a priority queue Q. We start by pushing the seed into the queue with a weight equals to its area factor and mark this seed as visited. Then, while Q is not empty, we pop out of Q the point p with the highest weight w and we add p to the evolving BP DP ν if it satisfies the requiered criteria presented in the following paragraph. We then add the nonvisited 26-neighbours of p which belong to the border and their associated area factor into the priority queue Q and mark them as visited.

Using this technique the BP DP ν does not stop growing if a point cannot be added. Required Criteria. The first criterion that has to be satisfied is that the width of the evolving BP DP ν must not exceed ν when a point p is added. But this is implicitly checked in the recognition algorithm.

Moreover, as we plan to use the segmentation in a future work to develop a polyhedrization algorithm for noisy discrete objects, the BP DP ν segments have to satisfy some constraints of good formation. In particular we want a BP DP ν segment to be 4-connected and without holes, i.e. homeomorphic to a topological disk, according to the main direction of the normal vector of its seed. To check these constraints we use a simplified version of a method proposed in [START_REF] Sivignon | De la caractérisation des primitives à la reconstruction polyédrique de surfaces en géométrie discrète[END_REF] (p.153). We work in the projection plane associated to the normal vector of the seed. We consider the 8-neighborhood of the point we are trying to add in the evolving BP DP ν and process the 8-neighbors in the order shown in Fig. 5(a). During the processing a zero-initialized counter is incremented at each time we go from a point which belongs to BP DP ν to a point which does not, and viceversa. At the end, if the counter value is greater than two it means that the point cannot be added whitout creating a hole. In the same time we check that at least one 4-neighbor belongs to BP DP ν . If a point does not pass these checks it is marked as non-visited to give the tracking process the opportunity to visit it later on. Some results obtained with this segmentation method are given in Fig. 6(a) and 6(b). On the one hand, if we look at the cube in Fig. 6(a), we can see that the segmentation is rather good and partition the object into six segments which correspond to the six faces of the cube. On the other hand, the segmentation of the sphere in Fig. 6(b) could be better. The problem with the sphere is its curved border. The tracking process of points described in section 3.2 has the opportunity to skirt round the points that cannot be added and on curved parts it tends to create rough-crescent-shaped BP DP ν . If we now use a width-ν patchbased segmentation, as described in section 2.2, we can see that the result is far better (see Fig. 6(c)). This is due to the chamfer-mask-based tracking process used to grow the patches.

Hybrid Method

Relying on the previous observations, we have developed an hybrid segmentation method. For seeds that lie in a flat part of the object we develop a BP DP ν segment as described in 3.2 and for seeds that lie in curved parts we develop a patch Γ ν (p) (see section 2.2).

To distinguish between flat parts and curved parts we use the shape factor F ν (p). As previously explained, an increasing value of |F ν (p)| means that the surface around p is more strongly bent. Thus, given a threshold value σ and a seed s, if |F ν (s)| < σ we develop a BP DP ν segment, otherwise we develop a patch Γ ν (s).

Results obtained with this method are shown in Fig. 7 and8. In Fig. 7 synthetical objects with different shapes have been segmented at different widths. We can see in Fig. 7(g) and 7(h) that the method still works for non-noisy objects. Furthermore, due to the hybrid approach, both the flat and the curved areas of the noisy half hallowed ellipsoid in Fig 7(c), 7(f) and 7(i), are well segemented. In Fig. 8 a real-life object -an old Dodge car, available on the TC18 website 3 -has been segmented with both, the DSD algorithm proposed by I. Sivignon and the hybrid approach. We can notice that, with the hybrid approach, the flat areas, i.e the roof, the parts of the hood and the windshield, are well segmented, with respect to the shape of the car and with a little number of segments. In curved areas the two segmentations are close, but it is difficult to decide what is a "good" segmentation in these areas. Note that, at this time, the threshold have to be set manualy, but we would like to investigate more to find a way to automaticaly choose a good value for σ.

In this paper we have presented a segmentation method to decompose a possibly noisy discrete object into pieces of discrete planes with a variable width. Different segmentation strategies have been proposed, guided by geometric features of the border of the object, computed in a pre-process step. Good results have been obtained for both noisy and non-noisy objects, but we still have to investigate more to automaticaly choose good values for the different parameters of the method. In a future work, we intend to use this segmentation to develop a smoothing and a polyhedrization algorithms for noisy discrete objects. But some work have to be done to propose a good definition for facets and to study the way to group

Fig. 1 .

 1 Fig. 1. (a) A width-3 blurred piece of discrete plane and (b) a piece of its optimal bounding plane P(4, 8, 19, -80, 49), using the Euclidean norm.

Fig. 2 .

 2 Fig. 2. An example of width-2 patches spread on the surface of different noisy objects. (a) A sphere of radius 20 and (b) a cube of edge 25.

  An estimator that enables the characterization of the shape (concave, convex or flat) of the surface around a border point of a possibly noisy discrete object has been developed. It is based on the study of the conformation of the patches which are centered on points belonging to the outline of Γ ν (p). Definition 5 (Patch Outline). Let B b be the border of a discrete object O b .We denote by S b the set of surfels of B b which are incident to a point that does not belong to O b , and S Γν (p) the subset of S b that belongs to Γ ν (p). A point q belongs to the outline of Γ ν (p) if the voxel representation of q has a surfel s ∈ S Γν (p) and if there exists a surfel s ∈ S b \ S Γν (p) such that s and s are adjacent by edge.

Fig. 3 .

 3 Fig. 3. Segmentation of (a) a regular cube of edge 25 and (b) a noisy counterpart by using the DSD algorithm (http://liris.cnrs.fr/isabelle.sivignon/DSD.html) proposed by I. Sivignon [13, 14].

Fig. 4 .Fig. 5 .

 45 Fig. 4.Over-segmentation due to randomly chosen seeds.

Fig. 6 .

 6 Fig. 6. Width-2 segmentation of a weakly (a) noisy cube of edge 30; (b) noisy sphere of radius 20 with the method presented in section 3.2. (c) Segmentation of the same sphere using only width-2 patches.

Fig. 7 .

 7 Fig. 7. Results of different segmentations by using the hybrid method on synthetical objects: (a, b) a width-2 segmentation of a weakly noisy sphere of radius 20; (d, e) a width-3 segmentation of a strongly noisy cube of edge 25; (g, h) a width-1 segmentation of non-noisy objects; and (c, f, i) a width-2 segmentation of an half hallowed ellipsoid.

Fig. 8 .

 8 Fig. 8. The segmentation of a car (a, c) by using the DSD algorithm of I. Sivignon; and (b, d) by using the width-2 hybrid method.

An arithmetic discrete plane P(a, b, c, µ, ω) is the set of integer points (x, y, z) verifying µ ≤ ax + by + cz < µ + ω, where (a, b, c) ∈ Z 3 is the normal vector of the plane. µ ∈ Z is named the translation constant and ω ∈ Z the arithmetical thickness.

http://www.cb.uu.se/~tc18/code_data_set/3D_images.html

them together to build a Euclidean polyhedron. The strategies used in [START_REF] Dexet | Invertible polygonalization of 3d planar digital curves and application to volume data reconstruction[END_REF] and in [START_REF] Coeurjolly | Optimization schemes for the reversible discrete volume polyhedrization using marching cubes simplification[END_REF] could help us in that way. We also intend to lead formal studies on the notion of noise to give a theoretical validation of the presented approach.