Improving the accuracy of atom interferometers with ultracold sources R. Karcher, 1 A. Imanaliev, 1 S. Merlet, 1 and F. Pereira Dos Santos 1 1 LNE-SYRTE, Observatoire de Paris, Université PSL, CNRS, Sorbonne Université, 61 avenue de l'Observatoire 75014 Paris (Dated: April 11, 2018) We report on the implementation of ultracold atoms as a source in a state of the art atom gravimeter. We perform gravity measurements with 10 nm/s 2 statistical uncertainties in a so-far unexplored temperature range for such a high accuracy sensor, down to 50 nK. This allows for an improved characterization of the most limiting systematic effect, related to wavefront aberrations of light beam splitters. A thorough model of the impact of this effect onto the measurement is developed and a method is proposed to correct for this bias based on the extrapolation of the measurements down to zero temperature. Finally, an uncertainty of 13 nm/s 2 is obtained in the evaluation of this systematic effect, which can be improved further by performing measurements at even lower temperatures. Our results clearly demonstrate the benefit brought by ultracold atoms to the metrological study of free falling atom interferometers. By tackling their main limitation, our method allows reaching record-breaking accuracies for inertial sensors based on atom interferometry.

Atom gravimeters constitute today the most mature application of cold atom inertial sensors based on atom interferometry. They reach performances better than their classical counterparts, the free fall corner cube gravimeters, both in terms of short term sensitivity [1,2] and long term stability [3]. They offer the possibility to perform high repetition rate continuous measurements over extended periods of time [3,4], which represents an operation mode inaccessible to other absolute gravimeters. These features have motivated the development of commercial cold atom gravimeters [5], addressing in particular applications in the fields of geophysics. Nevertheless, the accuracy of these sensors is today slightly worse. Best accuracies in the 30 -40 nm/s 2 range have been reported [3,4] and validated through the participation of these instruments to international comparisons of absolute gravimeters since 2009 [6,7], to be compared with the accuracy of the best commercial state of the art corner cube gravimeters, of order of 20 nm/s

2 [START_REF]FG5-X specifications[END_REF].

The dominant limit in the accuracy of cold atom gravimeters is due to the wavefront distortions of the lasers beamsplitters. This effect is related to the ballistic expansion of the atomic source through its motion in the beamsplitter laser beams, as illustrated in figure 1, and cancels out at zero atomic temperature. In practice, it has been tuned by increasing the atomic temperature [4] and/or by using truncation methods, such as varying the size of the detection area [START_REF] Schkolnik | [END_REF] or of the Raman laser beam [10]. Comparing these measurements with measured or modelled wavefronts allows to gain insight on the amplitude of the effect, and estimate the uncertainty on its evaluation. It can be reduced by improving the optical quality of the optical elements of the interferometer lasers, or by operating the interferometer in a cavity [11], which filters the spatial mode of the lasers, and/or by compensating the wavefront distortions, using for instance a deformable mirror [12].

The strategy we pursue here consists in reducing the atomic temperature below the few µK limit imposed by cooling in optical molasses in order to study the temper-ature dependence of the wavefront aberration bias over a wider range, and down to the lowest possible temperature. For that, we use ultracold atoms produced by evaporative cooling as the atomic source in our interferometer. Such sources, eventually Bose-Einstein condensed, show high brightness and reduced spatial and velocity spread. These features allow for a drastic increase in the interaction time, on the ground [13] or in space [14] and for the efficient implementation of large momentum transfer beam splitters [15][16][17]. The potential gain in sensitivity has been largely demonstrated (for instance, by up to two orders of magnitude in [13]). But it is only recently that a gain was demonstrated in the measurement sensitivity of an actual inertial quantity [18], when compared to best sensors based on the more traditional approach exploiting two photon Raman transitions and laser cooled atoms. Here, implementing such a source in a state of the art absolute gravimeter, we demonstrate that ultracold atom sources also improve the accuracy of atom interferometers, by providing an ideal tool for the precise study of their most limiting systematic effect.

We briefly detail here the main features of our cold atom gravimeter. A more detailed description can be found in [4]. It is based on an atom interferometer [19] based on two-photon Raman transitions, performed on free-falling 87 Rb atoms. A measurement sequence is as follows. We start by collecting a sample of cold or ultracold atoms, which is then released in free fall. After state preparation, a sequence of three Raman pulses drives a Mach Zehnder type interferometer. These pulses, separated by free evolution times of duration T = 80 ms, respectively split, redirect and recombine the matter waves, creating a two-wave interferometer. The total duration of the interferometer is thus 2T = 160 ms. The populations in the two interferometer output ports N 1 and N 2 are finally measured by a state selective fluorescence detection method, and the transition probability P is calculated out of these populations (P = N 1 /(N 1 + N 2 )). This transition probability depends on the phase difference accumulated by the matter waves along the two arms of the interferometer that is, in our geometry, given by Φ = k. gT 2 , where k is the effective wave vector of the Raman transition and g the gravity acceleration. Gravity measurements are then repeated in a cyclic manner. Using laser cooled atoms, repetition rates of about 3 Hz are achieved which allows for a fast averaging of the interferometer phase noise dominated by parasitic vibrations. We have demonstrated a best short term sensitivity of 56 nm.s -2 at 1 s measurement time [1], which averages down to below 1 nm.s -2 . These performances are comparable to the ones of the two other best atom gravimeters developed so far [2,3]. The use of ultracold atoms reduces the cycling rate due to the increased duration of the preparation of the source. Indeed, we first load the magneto-optical trap for 1 s (instead of 80 ms only when using laser cooled atoms) before transferring the atoms in a far detuned dipole trap realized using a 30 W fibre laser at 1550 nm. It is first focused onto the atoms with a 170 µm waist (radius at 1/e 2 ), before being sent back at a 90 • angle and tightly focused with a 27 µm waist, forming a crossed dipole trap in the horizontal plane. The cooling and repumping lasers are then switched off, and we end up with about 3 × 10 8 atoms trapped at a temperature of 26 µK. Evaporative cooling is then implemented by decreasing the laser powers from 14.5 W and 8 W to 2.9 W and 100 mW typically in the two arms over a duration of 3 s. We finally end up with atomic samples in the low 100 nK range containing 10 4 atoms. Changing the powers at the end of the evaporation sequence allows to vary the temperature over a large temperature range, from 50 nK to 7 µK. The total preparation time is then 4.22 s, and the cycle time 4.49 s, which reduces the repetition rate down to 0.22 Hz. Furthermore, at the lowest temperatures, the number of atoms is reduced down to the level where detection noise becomes comparable to vibration noise. The short term sensitivity is thus significantly degraded and varies in our experiment in the 1200-3000 nm.s -2 range at 1 s, depending on the final temperature of the sample. The red line is a fit to the data with a subset of five Zernike polynomials and the filled area the corresponding 68% confidence area.

We performed differential measurements of the gravity value as a function of the temperature of the source, which we varied over more than two orders of magnitude. The results are displayed as black circles in figure 2, which reveals a non-trivial behaviour, with a fairly flat behaviour in the 2-7 µK range, consistent with previous measurements obtained with optical molasses [4], and a rapid variation of the measurements below 2 µK. This shows that a linear extrapolation to zero temperature based on high temperature data taken with laser cooled atoms would lead to a significant error. These measurements have been performed for two opposite orientations of the experiment (with respect to the direction of the Earth rotation vector) showing the same behaviour, indicating that these effects are not related to Coriolis acceleration [4]. Moreover, the measurements are performed by averaging measurements with two different orientations of the Raman wavevector, which suppresses the effect of many systematic effects, such as differential light shifts of the Raman lasers that could vary with the temperature [4].

To interpret these data, we have developed a Monte Carlo model of the experiment, which averages the con-tributions to the interferometer signal of atoms randomly drawn in their initial position and velocity distributions. It takes into account the selection and interferometer processes, by including the finite size and finite coupling of the Raman lasers, and the detection process, whose finite field of view cuts the contribution of the hottest atoms to the measured atomic populations [20]. This model is used to calculate the effect of wavefront aberrations onto the gravity measurement as a function of the experimental parameters. For that, we calculate for each randomly drawn atom its trajectory and positions at the three pulses in the Raman beams, and take into account the phase shifts which are imparted to the atomic wavepackets at the Raman pulses: δφ = kδz i , where δz i is the flatness defect at the i-th pulse. We sum the contributions of a packet of 10 4 atoms to the measured atomic populations to evaluate a mean transition probability. The mean phase shift is finally determined from consecutive such determinations of mean transition probabilities using a numerical integrator onto the central fringe of the interferometer, analogous to the measurement protocol used in the experiment [4]. With 10 4 such packets, we evaluate the interferometer phase shifts with relative uncertainties smaller than 10 -3 . We decompose the aberrations δz onto the basis of Zernike polynomials Z m n , taking as a reference radius the finite size of the Raman beam (set by a 28 mm diameter aperture in the optical system). Assuming that the atoms are initially centred on the Raman mirror and in the detection zone, the effect of polynomials with no rotation symmetry (m = 0) averages to zero, due to the symmetry of the position and velocity distributions [12]. We thus consider here only Zernike polynomials with no angular dependence that correspond to the curvature of the wavefront (or defocus) and to higher order spherical aberrations.

To illustrate the impact of finite size effects, we display in figure 3 calculated gravity shifts corresponding to different cases, for a defocus (Z 0

2 ) with a peak-to-peak amplitude of 2a 0 = 20 nm across the size of the reference radius, which corresponds to δz(r) = a 0 (1 -2r 2 ), with r the normalized radial distance. The black squares corresponds to the ideal case of infinite Raman laser radius size and detection field of view and give a linear dependence versus temperature. The circles (resp. triangles) correspond to the case of finite beam waist and infinite detection field of view (resp. infinite beam waist and finite detection field of view), and finally diamonds include both finite size effects. Deviations from the linear behaviour arise from the reduction or suppression of the contribution of the hottest atoms. The effect of the finite Raman beam waist is found to be more important than the effect of the finite detection area. Finally, we calculate for this simple study case a bias of -63 nm/s 2 at the temperature of 1.8 µK, for a peak-to-peak amplitude of 20 nm. This implies that, at the temperature of laser cooled samples and for a pure curvature, a peak-to-peak amplitude of less than 3 nm (λ/260 PV) over a reference diameter of 28 mm is required for the bias to be smaller than 10 nm/s 2 .

We then calculate the effect of the 7 first Z 0 n polynomials (for even n ranging from 2 and 14) for the same peak-to-peak amplitude of 2a 0 = 20 nm as a function of the atomic temperature. Figure 4 displays the results obtained, restricted for clarity to the first five polynomials. All orders exhibit as common features a linear behaviour at low temperatures and a trend for saturation at high temperatures. Interestingly, we find non monotonic behaviours in the temperature range we explore and the presence of local extrema.

Using the phase shifts calculated at the temperatures of the measurements, the data of figure 2 can now be adjusted, using a weighted least square adjustment, by a combination of the contribution of the first Zernike polynomials, which then constitute a finite basis for the decomposition of the wavefront. The adjustment was realized for increasing numbers of polynomials, so as to assess the impact of the truncation of the basis. We give in table I the values of the correlation coefficient R and the extrapolated value at zero temperature as a function of the number of polynomials. We obtain stable values for both R and the extrapolated value to zero temperature, of about -55 nm/s 2 for numbers of polynomials larger than 5. This indicates that the first 5 polynomials are enough to faithfully reconstruct a model wavefront that well reproduces the data. When increasing the number of polynomials, we indeed find that the reconstructed wavefront is dominated by the lowest polynomial orders. The results of the adjustment with 5 polynomials is displayed as a red line in figure 2 and the 68% confidence bounds as a filled area. The flatness of the reconstructed wavefront at the centre of the Raman laser beam is found to be as small as 20 nm PV (Peak Valley) over a diameter of 20 mm. The bias due to the optical aberrations at the reference temperature of 1.8 µK, which corresponds to the temperature of the laser cooled atom source, is thus 56(13) nm/s 2 . Its uncertainty is three times better than its previous evaluation [4], which in principle will improve accordingly our accuracy budget.

On the other hand, interatomic interactions in ultracold sources can induce significant phase shifts [21,22] and phase diffusion [23], leading to bias and loss of contrast for the interferometer. Nevertheless, the rapid decrease of the atomic density when interrogating the atoms in free fall reduces drastically the impact of interactions [24][25][26]. To investigate this, we have performed a differential measurement for two different atom numbers at the temperature of 650 nK. The number of atoms was varied from 25000 to 5000 by changing the efficiency of a microwave pulse in the preparation phase, which leaves the spatial distribution and temperature unchanged. We measured an unresolved difference of -7(12) nm/s 2 . This allows us to put an upper bound on the effect of interactions, which we find lower than 1 nm/s 2 per thousand atoms.

The uncertainty in the evaluation of the bias related to optical aberrations can be improved further by performing measurements at even lower temperatures, which will require in our set-up to improve the efficiency of the evaporative cooling stage. A larger number of atoms would allow to limit the degradation of the short term sensitivity and to perform measurements with shorter averaging times. More, absorption imaging with a vertical probe beam would allow for spatially resolved phase measurements across the cloud [13], which would allow for improving the reconstruction of the wavefront. The temperature can also be drastically reduced, down to the low nK range, using delta kick collimation techniques [27,28]. In addition to a reduced ballistic expansion, the use of ultracold atoms also offers a better control of the initial position and mean velocity of the source with respect to laser cooled sources, which suffer from fluctuations induced by polarisation and intensity variations of the cooling laser beams. Such an improved control reduces the fluctuations of systematic effects related to the transverse motion of the atoms, such as the Coriolis acceleration and the bias due to aberrations, and thus will improve the long term stability [26].

With the above-mentioned improvements, and after a careful re-examination of the accuracy budget [7], accuracies better than 10 nm/s 2 are within reach. This will make quantum sensors based on atom interferometry the best standards in gravimetry. Furthermore, the improved control of systematics and the resulting gain in stability will open new perspectives for applications, in particular in the field of geophysics [29]. Finally, the method proposed here can be applied to any atomic sensor based on light beamsplitters, which are inevitably affected by distortions of the lasers wavefronts. The improved control of systematics it provides will have significant impact in high precision measurements with atom interferometry, with important applications to geodesy [30,31], fundamental physics tests [14,32,33] and to the development of highest grade inertial sensors [34].

FIG. 1 .

 1 FIG.1. (color online) Scheme of the experimental setup, illustrating the effect of wavefront aberrations. Due to their ballistic expansion across the Raman beam, the atoms sample different parasitic phase shifts at the three π/2 -π -π/2 pulses due to distortions in the wavefront (displayed in blue as a distorted surface). This leads to a bias, resulting from the average of the effect over all atomic trajectories, filtered by finite size effects, such as related to the waist and clear aperture of the Raman beam and to the finite detection field of view.

FIG. 2 .

 2 FIG. 2. (color online)Gravity measurements as a function of the atom temperature. The measurements, displayed as black circles, are performed in a differential way, with respect to a reference temperature of 1.8 µK (displayed as a red circle). The red line is a fit to the data with a subset of five Zernike polynomials and the filled area the corresponding 68% confidence area.

FIG. 3 .

 3 FIG. 3. (color online) Calculation of the impact of the size of the Raman beam waist (RB) and of the detection field of view (DFoV) on the gravity shift induced by a defocus as a function of the atomic temperature. The peak-to-peak amplitude of the defocus is 20 nm. The results correspond to four different cases, depending on whether the sizes of the Raman beam waist and detection field of view are taken as or infinite.

ACKNOWLEDGMENTS

We acknowledge the contributions from X. Joffrin, J. Velardo and C. Guerlin in earlier stages of this project. We thank R. Geiger and A. Landragin for useful discussions and careful reading of the manuscript.


María Cumplido

On the minimal positive standardizer of a parabolic subgroup of an Artin-Tits group

The minimal standardizer of a curve system on a punctured disk is the minimal positive braid that transforms it into a system formed only by round curves. In this article, we give an algorithm to compute it in a geometrical way. Then, we generalize this problem algebraically to parabolic subgroups of Artin-Tits groups of spherical type and we show that, to compute the minimal standardizer of a parabolic subgroup, it suffices to compute the pn-normal form of a particular central element.

Introduction

Let D be the disk in C with diameter the real segment [0, n + 1] and let D n = D \ {1, . . . , n} be the n-punctured disk. The n-strand braid group, B n , can be identified with the mapping class group of D n relative to its boundary ∂D n . B n acts on the right on the set of isotopy classes of simple closed curves in the interior of D n . The result of the action of a braid α on the isotopy class C of a curve C will be denoted by C α and it is represented by the image of the curve C under any automorphism of D n representing α. We say that a curve is non-degenerate if it is not homotopic to a puncture, to a point or to the boundary of D n , in other words, if it encloses more than one and less than n punctures. A curve system is a collection of isotopy classes of disjoint non-degenerate simple closed curves, that are pairwise non-isotopic.

Curve systems are very important as they allow to use geometric tools to study braids. From Nielsen-Thurston theory [START_REF] Thurston | On the geometry and dynamics of diffeomorphisms of surfaces[END_REF], every braid can be decomposed along a curve system, so that each component becomes either periodic or pseudo-Anosov. The simplest possible scenario appears when the curve is standard : Definition 1. A simple closed curve in D n is called standard if it is isotopic to a circle centered at the real axis. A curve system containing only isotopy classes of standard curves is called standard.

Every curve system can be transformed into a standard one by the action of a braid, as we shall see. Let B + n be the submonoid of B n of positive braids, generated by σ 1 , . . . , σ n-1 [START_REF] Artin | Theory of Braids[END_REF]. We can define a partial order on B n , called prefix order, as follows: for α, β ∈ B n , α β if there is γ ∈ B + n such that αγ = β. This partial order endows B n with a lattice structure, i.e., for each pair α, β ∈ B n , their gcd α ∧ β and their lcm α ∨ β with respect to exist and are unique. Symmetrically, we can define the suffix order as follows: for α, β ∈ B n , β α if there is γ ∈ B + n such that γα = β. We will focus on B n as a lattice with respect to , and we remark that B + n is a sublattice of B n . In 2008, Lee and Lee proved the following: Theorem 2 ([17, Theorem 4.2]). Given a curve system S in D n , its set of standardizers

St(S) = {α ∈ B + n : S α is standard } 1 INTRODUCTION
2 is a sublattice of B + n . Therefore, St(S) contains a unique -minimal element.

The first aim of this paper is to give a direct algorithm to compute the -minimal element of St(S), for a curve system S. The algorithm, explained in Section 4, is inspired by Dynnikov and Wiest's algorithm to compute a braid given its curve diagram [START_REF] Dynnikov | On the complexity of braids[END_REF] and the modifications made in [START_REF] Caruso | Algorithmes et généricité dans les groupes de tresses[END_REF].

The second aim of the paper is to solve the analogous problem for Artin-Tits groups of spherical type. Definition 3. Let Σ be a finite set of generators and M = (m s,t ) s,t∈Σ a symmetric matrix with m s,s = 1 and m s,t ∈ {2, . . . , ∞} for s = t. The Artin-Tits system associated to M is (A, Σ), where A is a group (called Artin-Tits group) with the following presentation A = Σ | sts . . . ms,t elements = tst . . . ms,t elements ∀s, t ∈ Σ, s = t, m s,t = ∞ .

For instance, B n has the following presentation [START_REF] Artin | Theory of Braids[END_REF] B n = σ 1 , . . . , σ n-1 σ i σ j = σ j σ i , |i -j| > 1 σ i σ j σ i = σ j σ i σ j , |i -j| = 1 .

The Coxeter group W associated to (A, Σ) can be obtained by adding the relations s 2 = 1: If W is finite, the corresponding Artin-Tits group is said to have spherical type. We will just consider Artin-Tits groups of spherical type, assuming that a spherical type Artin-Tits system is fixed. If A cannot be decomposed as direct product of non-trivial Artin-Tits groups, we say that A is irreducible. Irreducible Artin-Tits groups of spherical type are completely classified [START_REF] Coxeter | The complete enumeration of finite groups of the form r 2 i = (r i r j ) k ij = 1[END_REF].

W = Σ | s 2 =
Let A be an Artin-Tits group of spherical type. A standard parabolic subgroup, A X , is the subgroup generated by some X ⊆ Σ. A subgroup P is called parabolic if it is conjugate to a standard parabolic subgroup, that is, P = α -1 A Y α for some standard parabolic subgroup A Y and some α ∈ A. Notice that we may have P = α -1 A Y α = β -1 A Z β for distinct Y, Z ⊂ Σ and distinct α, β ∈ A. We will write P = (Y, α) to express that A Y and α are known data defining the parabolic subgroup P .

There is a natural way to associate a parabolic subgroup of B n to a curve system. Suppose that A = B n and let A X be the standard parabolic subgroup generated by {σ i , σ i+1 , . . . , σ j } ⊆ {σ 1 , . . . , σ n-1 }. Let C be the isotopy class of the circle enclosing the punctures i, . . . , j + 1 in D n . Then A X fixes C and we will say that that A X is the parabolic subgroup associated to C. Suppose that there is some curve system C , such that C = C α for some α ∈ B n . Then α -1 A X α fixes it and we say that α -1 A X α is its associated parabolic subgroup. The parabolic subgroup associated to a system of non-nested curves is the direct sum of the subgroups associated to each curve. Notice that this is a well defined subgroup of B n , as the involved subgroups commute. Therefore, we can talk about parabolic subgroups instead talking about curves. Most of the results for curves on D n that can be translate in terms of parabolic subgroups can also be extend to every Artin-Tits group of spherical type. That is why parabolic subgroups play a similar role, in Artin-Tits groups, to the one played by systems of curves in B n .

Our second purpose in this paper is to give a fast and simple algorithm to compute the minimal positive element that conjugates a given parabolic subgroup to a standard parabolic subgroup. The central Garside element of a standard parabolic subgroup A X will be denoted by c X and is to be defined in the next section.

Having a generic parabolic subgroup, P = (X, α), the central Garside element will be denoted by c P . We also define the minimal standardizer of the parabolic subgroup P = (X, α) to be the minimal positive element that conjugates P to a standard parabolic subgroup. The existence and uniqueness of this element will be shown in this paper. Keep in mind that the pn-normal form of an element is a particular decomposition of the form ab -1 , where a and b are positive and have no common suffix. The main result of this paper is the following:

Theorem 37 Let P = (X, α) be a parabolic subgroup. If c P = ab -1 is in pn-normal form, then b is the minimal standardizer of P .

Thus, the algorithm will take a parabolic subgroup P = (X, α) and will just compute the normal form of its central Garside element c P , obtaining immediately the minimal standardizer of P .

The paper will be structured in the following way: In Section 2 some results and concepts about Garside theory will be recalled. In Sections 3 and 4 the algorithm for braids will be explained. In Section 5 the algorithm for Artin-Tits groups will be described and, finally, in Section 6 we will bound the complexity of both procedures.

Preliminaries about Garside theory

Let us briefly recall some concepts from Garside theory (for a general reference, see [START_REF] Dehornoy | Gaussian Groups and Garside Groups, two Generalisations of Artin Groups[END_REF]). A group G is called a Garside group with Garside structure (G, P, ∆) if it admits a submonoid P of positive elements such that P ∩ P -1 = {1} and a special element ∆ ∈ P, called Garside element, with the following properties:

• There is a partial order in G, , defined by a b ⇔ a -1 b ∈ P such that for all a, b ∈ G it exists a unique gcd a ∧ b and a unique lcm a ∨ b with respect to . This order is called prefix order and it is invariant under left-multiplication.

• The set of simple elements [1, ∆] = {a ∈ G | 1 a ∆} generates G.

• ∆ -1 P∆ = P.

• P is atomic: If we define the set of atoms as the set of elements a ∈ P such that there are no non-trivial elements b, c ∈ P such that a = bc, then for every x ∈ P there is an upper bound on the number of atoms in a decomposition of the form x = a 1 a 2 • • • a n , where each a i is an atom.

The conjugate by ∆ of an element x will be denoted τ (x) = x ∆ = ∆ -1 x∆.

In a Garside group, the monoid P also induces a partial order invariant under rightmultiplication, the suffix order . This order is defined by a b ⇔ ab -1 ∈ P, and for all a, b ∈ G there exists a unique gcd (a ∧ b) and a unique lcm (a ∨ b) with respect to . We say that a Garside group has finite type if [1, ∆] is finite. It is well known that Artin-Tits groups of spherical type admit a Garside structure of finite type [START_REF] Brieskorn | Artin-gruppen und Coxeter-gruppen[END_REF][START_REF] Dehornoy | Gaussian Groups and Garside Groups, two Generalisations of Artin Groups[END_REF]. Moreover: We say that x

= ∆ k x 1 • • • x r is in left normal form if k ∈ Z, x i / ∈ {1
, ∆} is a simple element for i = 1, . . . , r, and x i x i+1 is in left normal form for 0 < i < r.

Analogously,

x = x 1 • • • x r ∆ k is in right normal form if k ∈ Z, x i / ∈ {1
, ∆} is a simple element for i = 1, . . . , r, and x i x i+1 is in right normal form for 0 < i < r.

It is well known that the normal form of an element is unique [START_REF] Dehornoy | Gaussian Groups and Garside Groups, two Generalisations of Artin Groups[END_REF]Corollary 7.5]. Moreover, the numbers r and k do not depend on the normal form (left or right). We define the infimum, the canonical length and the supremum of x respectively as inf(x) = k, (x) = r and sup(x) = k +r.

Let a and b be two simple elements such that a • b is in left normal form. One can write its inverse as b -1 a -1 = ∆ -2 ∂ -3 (b)∂ -1 (a). This is in left normal form because ∂ -1 (b)∂(a) is in normal form by definition and τ = ∂ 2 preserves . More generally (see [START_REF] Elrifai | Algorithms for positive braids[END_REF]

), if x = ∆ k x 1 • • • x r is in left normal form, then the left normal form of x -1 is x -1 = ∆ -(k+r) ∂ -2(k+r-1)-1 (x r )∂ -2(k+r-2)-1 (x r-1 ) • • • ∂ -2k-1 (x 1 )
For a right normal form, x = x 1 • • • x r ∆ k , the right normal form of x -1 is:

x -1 = ∂ 2k+1 (x r )∂ 2(k+1)+1 (x r-1 ) • • • ∂ 2(k+r-1)+1 (x 1 )∆ -(k+r) Definition 7 ([5, Theorem 2.6]). Let a, b ∈ P, then x = a -1 b is said to be in np-normal form if a ∧ b = 1. Similarly, we say that x = ab -1 is in pn-normal form if a ∧ b = 1. Definition 8. Let ∆ k x 1 • • • x r
with r > 0 be the left normal form of x. We define the initial and the final factor respectively as ι(x) = τ -k (x 1 ) and ϕ(x) = x r . We will say that x is rigid if ϕ(x) • ι(x) is in left normal form or if r = 0. Definition 9 ( [START_REF] Elrifai | Algorithms for positive braids[END_REF], [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF]Definition 8]). Let ∆ k x 1 • • • x r with r > 0 be the left normal form of x. The cycling of x is defined as

c(x) = x ι(x) = ∆ k x 2 • • • x r ι(x).
The decycling of x is d(x) = x (ϕ(x) -1 ) = ϕ(x)∆ k x 1 . . . x r-1 . We also define the preferred prefix of x as p(x) = ι(x) ∧ ι(x -1 ).

The cyclic sliding of x is defined as the conjugate of x by its preferred prefix:

s(x) = x p(x) = p(x) -1 xp(x).
Let G be a Garside group. For x ∈ G, inf s (x) and sup s (x) denote respectively the maximal infimum and the minimal supremum in the conjugacy class x G .

• The super summit set [START_REF] Elrifai | Algorithms for positive braids[END_REF][START_REF] Picantin | The Conjugacy Problem in Small Gaussian Groups[END_REF]

of x is SSS(x) = {y ∈ x G | is minimal in x G } = {y ∈ x G | inf(y) = inf
SC(x) = {y ∈ x G | s m (y) = y for some m ≥ 1}
These sets are finite if the set of simple elements is finite and their computation is very useful to solve the conjugacy problem in Garside groups. They satisfy the following inclusions:

SSS(x) ⊇ U SS(x) ⊇ SC(x).

The braid group, B n

A braid with n strands can be seen as a collection of n disjoint paths in a cylinder, defined up to isotopy, joining n points at the top with n points at the bottom, running monotonically in the vertical direction.

Each generator σ i represents a crossing between the strands in positions i and i + 1 with a fixed orientation. The generator σ -1 i represents the crossing of the same strands with the opposite orientation. When considering a braid as a mapping class of D n , these crossings are identified with the swap of two punctures in D n (See Figure 1).

σ 1 σ -1 2 Figure 1: The braid σ 1 σ -1
2 and how it acts on a curve in D 3 .

Remark 10. The standard Garside structure of the braid group

B n is (B n , B + n , ∆ n ) where ∆ n = σ 1 ∨ • • • ∨ σ n-1 = (σ 1 σ 2 • • • σ n-1 )(σ 1 σ 2 • • • σ n-2 ) • • • (σ 1 σ 2 )σ 1
The simple elements in this case are also called permutation braids [START_REF] Elrifai | Algorithms for positive braids[END_REF], because the set of simple braids is in one-to-one correspondence with the set of permutations of n elements. Later we will use the following result:

Lemma 11 ([11, Lemma 2.4]).
Let s be a simple braid. Strands j and j + 1 cross in s if and only if σ j s.

Detecting bending points

In order to describe a non-degenerate closed curve C in D n , we will use a notation introduced in [START_REF] Fenn | Ordering the braid groups[END_REF]. Recall that D n has diameter [0, n + 1] and that the punctures of D n are placed at 1, 2, . . . , n ∈ R. Choose a point on C lying on the real axis and choose an orientation for C. We will obtain a word W (C) representing C, on the alphabet { , , 0, 1, . . . , n}, by running along the curve, starting and finishing at the chosen point. We write down a symbol for each arc on the lower half plane, a symbol for each arc on the upper half plane, and a number m for each intersection of C with the real segment (m, m + 1). An example is provided in Figure 2. For an isotopy class of curves C, W (C) is the word associated to a reduced representative C red , i.e., a curve in C which has minimal intersection with the real axis. C red is unique up to isotopy of D n fixing the real diameter setwise [START_REF] Fenn | Ordering the braid groups[END_REF], and W (C) is unique up to cyclic permutation and reversing.

Remark 12. Notice that if a curve C does not have minimal intersection with the real axis, then W (C) contains a subword, up to reversal and cylic permutation, of the form p p or p p . Hence, the curve can be isotoped by "pushing" this arc in order not to intersect the real axis. This is equivalent to removing the subword mentioned before from W (C). In fact, we will obtain W (C) by removing all subwords of this kind from W (C). The process of removing p p (resp. p p ) from W (C) is called relaxation of the arc p p (resp. p p).

Definition 13. Let C be a non-degenerate simple closed curve. We say that there is a bending point (resp. reversed bending point) of C at j if we can find in W (C), up to cyclic permutation and reversing, a subword of the form i j k (resp. i j k) for some 0 ≤ i < j < k ≤ n (Figure 3).

We say that a curve system has a bending point at j if one of its curves has a bending point at j.

i + 1 j j + 1 k C Figure 3: A bending point at j in a curve C.
The algorithm we give in Section 4 takes a curve system S and "untangles" it in the shortest (positive) way. That is, it gives the shortest positive braid α such that S α is standard, i.e., the minimal element in St(S). Bending points are the key ingredient of the algorithm. We will show that if a curve system S has a bending point at j, then σ j is a prefix of the minimal element in St(S). This will allow to untangle S by looking for bending points and applying the corresponding σ j to the curve until no bending point is found. The aim of this section is to describe a suitable input for this algorithm and to show the following result. Proposition 14. A curve system is standard if and only if its reduced representative has no bending points.

Dynnikov coordinates

We have just described a non-degenerate simple closed curve in D n by means of the word W (C). There is a different and usually much shorter way to determine a curve system S in D n : its Dynnikov coordinates [8, Chapter 12]. The method to establish the coordinates of C is as follows. Take a triangulation of D n as in Figure 4 and let x i be the number of times the curve system S intersects the edge e i . The Dynnikov coordinates of the curve system are given by the t-uple (x 0 , x 1 , . . . , x 3n-4 ). There exists a reduced version of these coordinates, namely (a 0 , b 0 , . . . , a n-1 , b n-1 ), where

a i = x 3i-1 -x 3i 2 , b i = x 3i-2 -x 3i+1 2 , ∀i = 1, ..., n -2
and a 0 = a n-1 = 0, b 0 = -x 0 and b n-1 = x 3n-4 . See an example in Figure 5.

1 2 3 n -1 n e 0 e 3n-4
e 2 e 5 e 3n-7

e 1 e 3 e 4 e 6 e 3n-6 e 3n-5 Furthermore, there are formulae determining how these coordinates change when applying σ ±1 j , to the corresponding curve, for 0 < j < n. Proposition 15 ([7, Proposition 8.5.4]). For c = (a 0 , b 0 , . . . , a n-1 , b n-1 ), we have

c σ -1 k = (a 0 , b 0 , . . . , a n-1 , b n-1 ),
with a j = a j , b j = b j for j ∈ {k -1, k}, and

a k-1 = a k-1 + (δ + + b k-1 ) + , a k = a k -(δ + -b k ) + , b k-1 = b k-1 -(-δ ) + + δ + , b k = b k + (-δ ) + -δ + , where δ = a k -a k-1 , δ = a k -a k-1 and x + = max(0, x).
We also have

c σ k = c λσ -1 k λ with (a 1 , b 1 , . . . , a n-1 , b n-1 ) λ = (-a 1 , b 1 , . . . , -a n-1 , b n-1 ).
Remark 16. Notice that the use of σ -1 k in the first equation above is due to the orientation of the strands crossings that we are taking for our braids (see Figure 1), which is the opposite of the orientation used in [START_REF] Dehornoy | Why are braids orderable?[END_REF].

, a 1 , b 1 , a 2 , b 2 , a 3 , b 3 ) = (0, -1, 1, -2, 3, -3, 0, 6).
Let us see how to detect a bending point of a curve system S with these coordinates. First of all, notice that there cannot be a bending point at 0 or at n. It is easy to check that there is a bending point at 1 if and only if x 2 < x 3 (Figure 6a). Actually, if R is the number of subwords of type 0 1 k for some 1 < k ≤ n, then x 3 = x 2 + 2R. Symmetrically, there is a bending point at n -1 if and only if x 3n-6 < x 3n-7 . A bending point at i, for 1 < i < n -1, is detected by comparing the coordinates a i-1 and a i (Figure 6b). Notice that arcs not intersecting e 3i-2 affect neither a i-1 nor a i , and arcs not intersecting the real line do not affect the difference a i-1 -a i . Hence, there is a bending point of S at i if and only if a i-1 -a i > 0. Using a similar argument we can prove that there is a reversed bending point of S at i if and only if a i-1 -a i < 0. Moreover, each bending point (resp. reversed bending point) at i increases (resp. decreases) by 1 the difference a i-1 -a i . We have just shown the following result: Lemma 17 (Bending point with Dynnikov coordinates). Let S be a curve system on D n with reduced Dynnikov coordinates (a 0 , b 0 , . . . , a n-1 , b n-1 ). For j = 1, . . . , n -1 there are exactly R ≥ 0 bending points (resp. reversed bending points) of S at j if and only if a j-1 -a j = R (resp. a j-1 -a j = -R) .

Lemma 18. Let S be a curve system as above. Then S is symmetric with respect to the real axis if and only if a i = 0, for 0 < i < n.

Proof. Just notice that a symmetry with respect to the real axis does not affect b-coordinates and changes the sign of every a i , for 0 < i < n. Lemma 19. A curve system is standard if and only if it is symmetric with respect to the real axis.

Proof. For every m = 0, . . . , n, we can order the finite number of elements in S ∩ (m, m + 1) from left to right, as real numbers. Given an arc a b in W (S), suppose that it joins the i-th element in S ∩ (a, a + 1) with the j-th element in S ∩ (b, b + 1). The symmetry with respect to the real axis preserves the order of the intersections with the real line, hence the image a b of the above upper arc will also join the i-th element in S ∩ (a, a + 1) with the j-th element in S ∩ (b, b + 1). This implies that both arcs a b and a b form a single standard curve a b . As this can be done for every upper arc in S, it follows that S is standard.

Proof of Proposition 14. If the curve system is standard, then it clearly has no bending points. Conversely, if it has no bending points, by Lemma 17 the sequence a 0 , . . . , a n-1 is nondecreasing, starting and ending at 0, so it is constant. By Lemmas 18 and 19, the curve system is standard.

Standardizing a curve system

We will now describe an algorithm which takes a curve system S, given in reduced Dynnikov coordinates, and finds the minimal element in St(S). The algorithm will do the following: Start with β = 1. Check whether the curve has a bending point at j. If so, multiply β by σ j and restart the process with S σ j . A simple example is provided in Figure 7. The formal way is described in Algorithm 1. The minimality of the output is guaranteed by the following theorem, which shows that σ j is a prefix of the minimal standardizer in St(S), provided S has a bending point at j. Theorem 20. Let S be a curve system with a bending point at j. Then σ j is a prefix of α, for every positive braid α such that S α is standard.

β = σ 2 σ 1 σ 1 σ 2 σ 1 σ 1
To prove the theorem we will need a result from [START_REF] Calvez | Dual Garside structure and reducibility of braids[END_REF]. Definition 21. We will say that a simple braid s is compatible with a bending point at j if the strands j and j + 1 of s do not cross in s. That is, if σ j s (by Lemma 11). Let s 1 and s 2 be two simple braids such that s 1 s 2 is in left normal form. Let C be a curve with a bending point at j compatible with s 1 . Then, there exists some bending point of C s 1 compatible with s 2 .

Remark 23. The previous lemma holds also for a curve system, with the same proof.

Proof of Theorem 20. Suppose that α ∈ B + n is such that S α is standard and σ j α. Let s 1 • • • s r be the left normal form of α. Notice that there is no ∆ p in the normal form. Otherwise, σ j would be a prefix of α, because it is a prefix of ∆. By Lemma 11, the strands j and j + 1 of s 1 do not cross because σ j is not a prefix of α. Thus, s 1 is compatible with a bending point at j and by Lemma 22, S s 1 has a bending point compatible with s 2 . By induction, S s 1 •••sm has a bending point compatible with s m+1 , for m = 2, . . . , r, where s r+1 is chosen to be such that s r • s r+1 is in left normal form. Hence, S α has a bending point, i.e., it is not standard, which is a contradiction.

In Algorithm 1 we can find the detailed procedure to compute the minimal element in St(S). Notice that, at every step, either the resulting curve has a bending point, providing a new letter of the minimal element in St(S), or it is standard and we are done. The process stops as B + n has homogeneous relations (actually, atomicity suffices to show that the process stops), so all positive representatives of the minimal element have the same length, which is precisely the number of bending points found during the process.

Notice that Theorem 20 guarantees that the output of Algorithm 1 is a prefix of every standardizer of S. This provides an alternative proof of the existence and uniqueness of a minimal element in St(S).

Standardizing a parabolic subgroup

Now we will give an algorithm to find the minimal standardizer of a parabolic subgroup P = (X, α) of an Artin-Tits group A of spherical type. The existence and uniqueness of this element will be shown by construction.

Proposition 24 ([18]

). A parabolic subgroup A X of an Artin-Tits group of spherical type is an Artin-Tits group of spherical type whose Artin-Tits system is (A X , X).

Proposition 25 ([2, Lemma 5.1, Theorem 7.1]). Let (A Σ , Σ) be an Artin-Tits system where A Σ is of spherical type. Then, a Garside element for A Σ is:

∆ Σ = s∈Σ s = s∈Σ s,
and the submonoid of positive elements is the monoid generated by Σ. Moreover, if A Σ is irreducible, then (∆ Σ ) e generates the center of A Σ , for some e ∈ {1, 2}. Definition 26. Let A X be an Artin-Tits group of spherical type. We define its central Garside element as c X = (∆ X ) e , where e is the minimal positive integer such that (∆ X ) e ∈ Z(A X ). We also define c X,α := αc X α -1 .

Proposition 27 ([16, Proposition 2.1]). Let X, Y ⊆ Σ and g ∈ A. The following conditions are equivalent,

1. g -1 A X g ⊆ A Y ; 2. g -1 c X g ∈ A Y ;
3. g = xy where y ∈ A Y and x conjugates X a subset of Y .

The above proposition is a generalization of [19, Theorem 5.2] and implies, as we will see, that conjugating standard parabolic subgroups is equivalent to conjugating their central Garside elements. This will lead us to the definition of the central Garside element for a non-standard parabolic subgroup as given in Proposition 34. In order to prove the following results, we need to define an object that generalizes to Artin-Tits groups of spherical type some operations used in braid theory:

Definition 28. Let X ⊂ Σ, t ∈ Σ. We define r X,t = ∆ X∪{t} ∆ -1
X . Remark 29. In the case t / ∈ X, this definition is equivalent to the definition of positive elementary ribbon [START_REF] Godelle | Normalisateur et groupe d'Artin de type sphérique[END_REF]Definition 0.4]. Notice that if t ∈ X, r x,t = 1. Otherwise, notice that ∆ X∪{t} is simple, and that a simple element cannot be written as a word with two consecutive repeated letters [2, Lemma 5.4]. As ∆ X can start with any letter of X, it follows that if t / ∈ X, the only possible final letter of r X,t is t. In particular r X,t t.

Proposition 30. There is a unique Y ⊂ X ∪ {t} such that r X,t X = Y r X,t .

Proof. Given Z ⊂ Σ, conjugation by ∆ Z permutes the elements of Z. Let us denote by Y the image of X under the permutation of X ∪ {t} induced by the conjugation by ∆ X∪{t} . Then

r X,t Xr -1 X,t = ∆ X∪{t} ∆ -1 X X∆ X ∆ -1 X∪{t} = ∆ X∪{t} X∆ -1 X∪{t} = Y.
Artin-Tits groups of spherical type can be represented by Coxeter graphs. Recall that such a group, A, is defined by a symmetric matrix M = (m i,j ) i,j∈S and the finite set of generators Σ. The Coxeter graph associated to A is denoted Γ A . The set of vertices of Γ A is Σ, and there is an edge joining two vertices s, t ∈ Σ if m s,t ≥ 3. The edge will be labelled with m s,t if m s,t ≥ 4. We say that the group A is indecomposable if Γ A is connected and decomposable otherwise. If A is decomposable, then there exists a non-trivial partition Σ = X

1 • • • X k such that A is isomorphic to A X 1 × • • • × A X k , where each A X j is indecomposable (each X j is just the set of vertices of a connected component of Γ X ). Each A X j is called an indecomposable component of A. Lemma 31. Let X, Y ⊂ Σ and let X = X 1 • • • X n and Y = Y 1 • • • Y m be
the partitions of X and Y , respectively, inducing the indecomposable components of A X and A Y . Then, for every g ∈ A, the following conditions are equivalent:

1. g -1 A X g = A Y .
2. m = n and g = xy, where y ∈ A Y and the parts of Y can be reordered so that we have

x -1 X i x = Y i for i = 1, . . . , n.

3. m = n and g = xy, where y ∈ A Y and the parts of Y can be reordered so that we have

x -1 A X i x = A Y i for i = 1, . . . , n.
Proof. Suppose that g -1 A X g = A Y . By Proposition 27, we can decompose g = xy where y ∈ A Y and x conjugates the set X to a subset of the set Y . Since conjugation by y induces an automorphism of A Y , it follows that x conjugates A X isomorphically onto A Y , so it conjugates X to the whole set Y . Since the connected components of Γ X (resp. Γ Y ) are determined by the commutation relations among the letters of X (resp. Y ), it follows that conjugation by x sends indecomposable components of X onto indecomposable components of Y . Hence m = n and x -1 X i x = Y i for i = 1, . . . , n (reordering the indecomposable components of Y in a suitable way), as we wanted to show. Thus, statement 1 implies statement 2. Statement 2 implies 3 trivially and finally the third statement implies the first one as

A X = A X 1 × • • • × A Xn and A Y = A Y 1 × • • • × A Yn . Lemma 32. Let X, Y ⊆ Σ, g ∈ A. Then, g -1 A X g = A Y ⇐⇒ g -1 c X g = c Y .
Proof. Suppose that g -1 c X g = c Y . Then, by Proposition 27, we have g -1 A X g ⊆ A Y and also gA Y g -1 ⊆ A X . As conjugation by g is an isomorphism of A, the last inclusion is equivalent to A Y ⊆ g -1 A X g. Thus, g -1 A X g = A Y , as desired.

Conversely, suppose that g -1 A X g = A Y . By using Lemma 31, we can decompose g = xy where y ∈ A Y and x is such that x -1 A X i x = A Y i , where A X i and A Y i are the indecomposable components of A X and A Y for i = 1, . . . , n. As the conjugation by x defines an isomorphism between A X i and A Y i , we have that

x -1 Z(A X i )x = Z(A Y i ). Hence, we have x -1 c X i x = ∆ k Y i
for some k ∈ Z, because the center of irreducible Artin-Tits groups of spherical type is cyclic (Proposition 25). Let

c X i = ∆ 1 X i and c Y i = ∆ 2 Y i .
As A X i and A Y i are isomorphic, 1 = 2 . Also notice that in an Artin-Tits group of spherical type the relations are homogeneous and so

k = 1 = 2 , having x -1 c X i x = c Y i . Let = max{ i | c X i = ∆ i X i } = max{ i | c Y i = ∆ i Y i },
and denote d

X i = ∆ X i and d Y i = ∆ Y i for i = 1, . . . , n. Notice that d X i is equal to either c X i or (c X i ) 2
, and the same happens for each

d Y i , hence x -1 d X i x = d Y i for i = 1, . . . , n. Then, as c X = n i=1 d X i and c Y = n i=1 d Y i , it follows that x -1 c X x = c Y . Therefore, g -1 c X g = y -1 (x -1 c X x)y = y -1 c Y y = c Y .
Lemma 33. Let P = (X, α) be a parabolic subgroup and A Y be a standard parabolic subgroup of an Artin-Tits group A of spherical type. Then we have

g -1 P g = A Y ⇐⇒ g -1 c X,α g = c Y . Proof. If P = (X, α), it follows that g -1 P g = A Y if and only if g -1 αA X α -1 g = A Y . By Lemma 32, this is equivalent to g -1 αc X α -1 g = c Y , i.e., g -1 c X,α g = c Y .
Proposition 34. Let P = (X, α) = (Y, β) be a parabolic subgroup of an Artin-Tits group of spherical type. Then c X,α = c Y,β and we can define c P := c X,α to be the central Garside element of P .

Proof. Suppose that g is a standardizer of P such that g -1 P g = A Z . By using Lemma 33, we have that c Z = g -1 c X,α g = g -1 c Y,β g. Thus, c X,α = c Y,β .

By Lemma 33, a positive standardizer of a parabolic subgroup P = (X, α) is a positive element conjugating c P to some c Y . Let

C + A Σ (c P ) = {s ∈ P | s = u -1 c P u, u ∈ A Σ }
be the set of positive elements conjugate to c P (which coincides with the positive elements conjugate to c X ). The strategy to find de minimal standardizer of P will be to compute the minimal conjugator from c P to C + A Σ (c P ). That is, the shortest positive element u such that u -1 c X,α u ∈ P.

Proposition 35. If x = ab -1 is in pn-normal form and x is conjugate to a positive element, then b is a prefix of every positive element conjugating x to C + A Σ (x).

Proof. Suppose that ρ is a positive element such that ρ -1 xρ is positive. Then 1 ρ -1 xρ. Multiplying from the left by x -1 ρ we obtain x -1 ρ ρ and, since ρ is positive, x -1 x -1 ρ ρ. Hence x -1 ρ or, in other words ba -1 ρ. On the other hand, by the definition of pn-normal form, we have a

∧ b = 1, which is equivalent to a -1 ∨ b -1 = 1 [14, Lemma 1.3]. Multiplying from the left by b, we obtain ba -1 ∨ 1 = b.
Finally, notice that ba -1 ρ and also 1 ρ. Hence b = ba -1 ∨ 1 ρ. Since b is a prefix of ρ for every positive ρ conjugating x to a positive element, the result follows.

Lemma 36. Let A X be a standard parabolic subgroup and t ∈ Σ. If α∆ k X t, then α r X,t , for every k > 0.

Proof. Since the result is obvious for t ∈ X (r X,t = 1), suppose t / ∈ X. Trivially, α∆ k X ∆ X . As α∆ k X t, we have that α∆ k X ∆ X ∨ t. By definition, ∆ X ∨ t = ∆ X∪{t} = r X,t ∆ X . Thus, α∆ k X r X,t ∆ X and then α∆ k-1 r X,t , because is invariant under right-multiplication. As r X,t t (see Remark 29), the result follows by induction.

Theorem 37. Let P = (X, α) be a parabolic subgroup. If c P = ab -1 is in pn-normal form, then b is the -minimal standardizer of P .

Proof. We know from Proposition 35 that b is a prefix of any positive element conjugating c P to a positive element, which guarantees its -minimality. We also know from Lemma 33 that any standardizer of P must conjugate c P to a positive element, namely to the central Garside element of some standard parabolic subgroup. So we only have to prove that b itself conjugates c P to the central Garside element of some standard parabolic subgroup. We assume α to be positive, because there is always some k ∈ N such that ∆ 2k α is positive and, as ∆ 2 lies in the center of A, P = (X, α) = (X, ∆ 2k α).

The pn-normal form of c P = αc X α -1 is obtained by cancelling the greatest common suffix of αc X and α. Suppose that t ∈ Σ is such that α t and αc X t.

If t / ∈ X, then r X,t = 1 and by Lemma 36 we have that α r X,t , i.e., α = α 1 r X,t for some

α 1 ∈ A Σ . Hence, αc X α -1 = α 1 r X,t c X r -1 X,t α -1 1 = α 1 c X 1 α -1 1
for some X 1 ⊂ Σ. In this case, we reduce the length of the conjugator (by the length of r X,t ). If t ∈ X, t commutes with c X , which means that

αc X α -1 = α 1 tc X t -1 α -1 1 = α 1 c X 1 α -1 1 ,
where α 1 is one letter shorter than α and X 1 = X. We can repeat the same procedure for α i c X i α -1 i , where X i ⊂ Σ, t i ∈ Σ such that α i t i and α i c X i t i . As the length of the conjugator decreases at each step, the procedure must stop, having as a result the pn-normal form of c P , which will have the form:

c P = (α k c X k )α -1 k , for k ∈ N, X k ⊂ Σ.
Then, α k = b clearly conjugates c P to c X k , which is the central Garside element of a standard parabolic subgroup, so b is the -minimal standardizer of P .

We end this section with a result concerning the conjugacy classes of elements of the form c P . As all the elements of the form c Z , Z ⊆ X, are rigid (Definition 8), using the next theorem we can prove that the set of sliding circuits of c P is equal to its set of positive conjugates.

Theorem 38 ([15, Theorem 1]). Let G be a Garside group of finite type. If x ∈ G is conjugate to a rigid element, then SC(x) is the set of rigid conjugates of x.

Corollary 39. Let P = (X, α) be a parabolic subgroup of an Artin-Tits group of spherical type. Then

C + A Σ (c P ) = SSS(c P ) = U SS(c P ) = SC(c P ) = {c Y | Y ∈ Σ, c Y conjugate to c X }.
Proof. By Theorem 38, it suffices to prove that C + A Σ (c P ) is composed only of rigid elements of the form c Z . Let P = (X, β) and suppose that c P ∈ C + A Σ (c P ). Let b be the minimal standardizer of c P . By Proposition 35, Theorem 37 and Lemma 33, b is the minimal positive element conjugating c P to C + A Σ (c P ), which implies that b = 1, so P is standard. Hence, all positive conjugates of c P are equal to c Y for some Y , therefore they are rigid.

Corollary 40. Let P = (X, α) be a parabolic subgroup of an Artin-Tits group of spherical type. Then the set of positive standardizers of P ,

St(P ) = {α ∈ A + Σ , | c α P = c Y , for some Y ⊆ Σ},

Complexity

In this section we will describe the computational complexity of the algorithms which compute minimal standardizers of curves and parabolic subgroups. Let us start with Algorithm 1, which computes the minimal standardizer of a curve system. The complexity of Algorithm 1 will depend on the length of the output, which is the number of steps of the algorithm. To bound this length, we will compute a positive braid which belongs to St(S). This will bound the length of the minimal standardizer of S.

The usual way to describe the length (or the complexity) of a curve system consists in counting the number of intersections with the real axis, i.e., (S) = #(S ∩ R). For integers 0 ≤ i < j < k ≤ n, we define the following braid (see Figure 8):

s(i, j, k) = (σ j σ j-1 • • • σ i+1 )(σ j+1 σ j • • • σ i+2 ) • • • (σ k-1 σ k-2 • • • σ i+k-j ) C 1 2 3 4 5 6
Figure 8: Applying s(0, 3, 6).

Lemma 41. Applying s = s(i, j, k) to a curve system S, when i j k is a bending point, decreases the length of the curve system at least by two.

Proof. We will describe the arcs of the curves of S in a new way, by associating a real number c p ∈ (0, n + 1) to each of the intersections of S with the real axis, where p is the position of the intersection with respect to the other intersections: c 1 is the leftmost intersection and c (S) is the rightmost one. We will obtain a set of words representing the curves of S, on the alphabet { , , c 1 , . . . , c (S) }, by running along each curve, starting and finishing at the same point. As before, we write down a symbol for each arc on the lower half plane, and a symbol for each arc on the upper half plane. We also define the following function that sends this alphabet to the former one:

L : { , , c 1 , . . . , c (S) } -→ { , , 0, . . . , n}

L( ) = , L( ) = , L(c p ) = c p .
Take a disk D such that its boundary ∂(D) intersects the real axis at two points, x 2 and x 3 , which are not punctures and do not belong to S. Consider another point x 1 , which should not be a puncture or belong to S, on the real axis such that L(x 1 ) < L(x 2 ). Suppose that there are no arcs of S on the upper-half plane intersecting the arc x 1 x 2 and there are no arcs of S on the lower-half plane intersecting the arc x 2 x 3 . We denote I 1 = (0, x 1 ), I 2 = (x 1 , x 2 ), I 3 = (x 2 , x 3 ) and I 4 = (x 3 , n + 1) and define |I t | as the number of punctures that lie in the interval I t .

We consider an automorphism of D n , called d = d(x 1 , x 2 , x 3 ), which is the final position of an isotopy that takes D and moves it trough the upper half-plane to a disk of radius centered at x 1 , which contains no point c p and no puncture, followed by an automorphism which fixes the real line as a set and takes the punctures back to the positions 1, . . . , n. This corresponds to "placing the interval I 3 between the intervals I 1 and I 2 ". Firstly, we can see in Figure 9 that the only modifications that the arcs of S can suffer is the shifting of their endpoints. By hypothesis, there are no arcs in the upper half-plane joining I 2 with I j for j = 2, and there are no arcs in the lower half-plane joining I 3 with I j for j = 3. Any other possible arc is transformed by d into a single arc, so every arc is transformed in this way. Algebraically, take an arc of S,

I 1 I 2 I 3 I 4 I 1 I 2 I 3 I 4 x 1 x 2 x 3
(a) d acting on the arcs in the upper half plane

I 1 I 2 I 3 I 4 I 1 I 2 I 3 I 4 x 1 x 2 x 3 (
L(c p ) =    p if c p ∈ I 1 , I 4 , p + |I 3 | if c p ∈ I 2 , p -|I 2 | if c p ∈ I 3 , for p = a, b.
After applying this automorphism, the curve could fail to be reduced, in which case relaxation of unnecessary arcs could be done, reducing the complexity of S. Now, given a bending point i j k of S, consider the set

B = {c p c q c r | L(c p ) < L(c q ) < L(c r ) and L(c q ) = j}
and choose the element of B with greatest sub-index q, which is also the one with lowest p and r. Define x 1 , x 2 and x 3 such that x 1 ∈ (c p-1 , c p ) ∩ (L(c p ), L(c p ) + 1), x 2 ∈ (c q , c q+1 ) ∩ (j, j + 1) and x 3 ∈ (c r-1 , c r ) ∩ (L(c r ), L(c r ) + 1). Then, the braid s(L(c p ), j, L(c r )) is represented by the automorphism d(x 1 , x 2 , x 3 ) (see Figure 10). Notice that the choice of the bending point from B guarantees the non-existence of arcs of C intersecting x 1 x 2 or x 2 x 3 . After the swap of I 2 and I 3 , the arc c q c r will be transformed into c q c r , where L(c q ) = L(c r ) = L(c r ), and then relaxed, reducing the length of S at least by two. i j k

I 1 I 2 I 3 I 4
Figure 10: Applying s(i, j, k) to a curve is equivalent to permute their intersections with the real axis and then make the curve tight.

The automorphism s = s(i, j, k) involves at most (k -j) • (j -i) generators and this number is bounded by 1 4 n 2 , because (k -j) + (j -i) ≤ n and (u + v) 2 ≤ 4uv for every u, v ≤ 1. Then, the output of our algorithm has at most 1 8 (S)n 2 letters, because we have proven that s reduces the length of the curve system at each step. Let us bound this number in terms of the input of the algorithm, i.e., in terms of reduced Dynnikov coordinates.

Definition 42. We say that there is a left hairpin (resp. a right hairpin) of C at j if we can find in W (C), up to cyclic permutation and reversing, a subword of the form i j -1 k (resp. i j k) for some i, k > j -1 (resp. i, k < j) (see Figure 11).

Proposition 43. Let S be a curve system on D n represented by the reduced Dynnikov coordinates (a 0 , b 0 , . . . , a n-1 , b n-1 ). Then (S)

≤ n-1 i=0 (2|a i | + |b i |).
Proof. Notice that each intersection of a curve C with the real axis corresponds to a subword of W (C) of the form i j k or i j k. If i < j < k the subword corresponds to a bending point or a reversed bending point respectively. If i, k > j, there is a left hairpin at j + 1. Similarly, if i, k < j, there is a right hairpin at j. Recall that Lemma 17 already establishes how to detect bending points with reduced Dynnikov coordinates. In fact, there are exactly R bending points (including reversed ones) at i if and only if |a i-1 -a i | = R. We want to detect also hairpins in order to determine (S). Observe in Figure 11 that the only types of arcs that can appear in the region between the lines e 3j-5 and e 3j-2 are left or right hairpins and arcs intersecting both e 3j-5 and e 3j-2 . The arcs intersecting both e 3j-5 and e 3j-2 do not affect the difference x 3j-5 -x 3j-2 whereas each left hairpin decreases it by 2 and each right hairpin increases it by 2. Notice that in the mentioned region there cannot be left and right hairpins at the same time. Then, there are exactly R left (resp. right) hairpins at j if and only if b j-1 = -R (resp. b j-1 = R). Hence, as a 0 = a n-1 = 0, we have: Corollary 44. Let S be a curve system on D n represented by the reduced Dynnikov coordinates (a 0 , b 0 , . . . , a n-1 , b n-1 ). Then, the length of the minimal standardizer of S is at most

1 8 n-1 i=0 (2|a i | + |b i |) • n 2 .
Proof. By Lemma 41, the length of the minimal standardizer of S is at most 1 8 (S)n 2 . Consider the bound for (S) given in Proposition 43 and the result will follow.

Remark 45. To check that this bound is computationally optimal we need to find a case where at each step we can only remove a single bending point, i.e., we want to find a family of curve systems {S k } k>0 such that the length of the minimal standardizer of S k is quadratic on n and linear on (S). Let n = 2t + 1, t ∈ N. Consider the following curve system on D n , S 0 = {t n } and the braid α = s(0, t, n -1). Now define S k = (S 0 ) α -k . The curve S k is called a spiral with k half-twists (see Figure 12) and is such that (S k ) = 2(k + 1). Using Algorithm 1, we obtain that the minimal standardizer of this curve is α k , which has k • t 2 factors. Therefore, the number of factors of the minimal standardizer of S k is of order O( (S k ) • n 2 ).

t n To find the complexity of the algorithm which computes the minimal standardizer of a parabolic subgroup P = (X, α) of an Artin-Tits group A, we only need to know the cost of computing the pn-normal form of c P . If x r • • • x 1 ∆ -p with p > 0 is the right normal form of c P , then its pn-normal form is (x r • • • x p+1 )(x p • • • x 1 ∆ -p ). Hence, we just have to compute the right normal form of c P in order to compute the minimal standardizer. It is well known that this computation has quadratic complexity (for a proof, see [9, Lemma 3.9 & Section 6 ]). Thus, we have the following: Proposition 47. Let P = (X, α) be a parabolic subgroup of an Artin-Tits group of spherical type, and let = (α) be the canonical length of α. Computing the minimal standardizer of P has a cost of O( 2 ).

Definition 4 .Definition 6 .

 46 We define the right complement of a simple element a as ∂(a) = a -1 ∆ and the left complement as ∂ -1 (a) = ∆a -1 . Remark 5. Observe that ∂ 2 = τ and that, if a is simple, then ∂(a) is also simple, i.e., 1 ∂(a) ∆. Both claims follow from ∂(a)τ (a) = ∂(a)∆ -1 a∆ = ∆ since ∂(a) and τ (a) are positive. Given two simple elements a, b, the product a • b is said to be in left (resp. right) normal form if ab ∧ ∆ = a (resp. ab ∧ ∆ = b). The latter is equivalent to ∂(a) ∧ b = 1 (resp. a ∧ ∂ -1 (b) = 1).

  s (y) and sup(y) = sup s (y)} • The ultra summit set of x [13, Definition 1.17] is U SS(x) = {y ∈ SSS(x) | c m (y) = y for some m ≥ 1} • The set of sliding circuits of x [15, Definition 9] is

Figure 2 :

 2 Figure 2: W (C) = 0 6 4 2 1 4 5 1 .

Figure 4 :

 4 Figure 4: Triangulation used to define Dynnikov coordinates.

Figure 5 :

 5 Figure 5: The Dynnikov coordinates and reduced Dynnikov coordinates of C are, respectively, (x 0 , . . . , x 8 ) = (1, 2, 4, 2, 6, 9, 3, 12, 6); (a 0 , b 0 , a 1 , b 1 , a 2 , b 2 , a 3 , b 3 ) = (0, -1, 1, -2, 3, -3, 0, 6).

  A bending point at i.

Figure 6 :

 6 Figure 6: Detecting bending points with Dynnikov coordinates.

Figure 7 :

 7 Figure 7: A simple example of how to find the minimal standardizer of a curve.

Algorithm 1 :

 1 Standardizing a curve system Input : The reduced coordinates (a 0 , b 0 , . . . , a n-1 , b n-1 ) of a curve system S on D n . Output: The -minimal element of St(S). c = (a 0 , b 0 , . . . , a n-1 , b n-1 ); β = 1; j = 1; while j < n do if c[a j ] < c[a j-1 ] then c = c σ j ; (use Proposition 15) β = β • σ j ; j = 1; else j = j + 1; return β; Lemma 22 ([3, Lemma 8]).

  Let s 1 and s 2 be two positive standardizers of P and let α := s 1 ∧ s 2 and β := s 1 ∨ s 2 . By Corollary 39 and, for example, [15, Proposition 7, Corollary 7 & 8], we have that c α P = c Y and c β P = c Z for some Y, Z ⊆ Σ. Hence α, β ∈ St(P ), as we wanted to show.

  c a c b (resp. c a c b ), such that L(c a ) = ã and L(c b ) = b. Then, its image under d is c a c b (resp. c a c b ) where

Figure 9 :

 9 Figure 9: How the automorphism d(x 1 , x 2 , x 3 ) acts on the arcs of C.

j e 3j- 4 e 2 (Figure 11 :

 4211 Figure 11: Detecting hairpins with Dynnikov coordinates.

(((

  |a i-1 | + |a i |) + 2|a i | + |b i |).

Figure 12 : 1 i=0( 2 n- 1 i=0(

 12121 Figure 12: The curve S 5 .

Acknowledgements. This research was supported by a PhD contract funded by Université Rennes 1, Spanish Projects MTM2013-44233-P, MTM2016-76453-C2-1-P, FEDER and French-Spanish Mobility programme "Mérimée 2015". I also thank my PhD advisors, Juan González-Meneses and Bert Wiest, for helping and guiding me during this research work.


Mohamed Boussaha
email: mohamed.boussaha@ign.fr

Bruno Vallet
email: bruno.vallet@ign.fr

Patrick Rives
email: patrick.rives@inria.fr

LARGE SCALE TEXTURED MESH RECONSTRUCTION FROM MOBILE MAPPING IMAGES AND LIDAR SCANS

Keywords: Urban scene, Mobile mapping, LiDAR, Oriented images, Surface reconstruction, Texturing

 is adapted to texture the reconstructed surface with the images acquired simultaneously, ensuring a high quality texture with no seams and global color adjustment. We evaluate our full pipeline on a dataset of 17 km of acquisition in Rouen, France resulting in nearly 2 billion points and 40000 full HD images. We are able to reconstruct and texture the whole acquisition in less than 30 computing hours, the entire process being highly parallel as each chunk can be processed independently in a separate thread or computer.

INTRODUCTION 1.1 Context

Mobile Mapping Systems (MMS) have become more and more popular to map cities from the ground level, allowing for a very interesting compromise between level of detail and productivity. Such MMS are increasingly becoming hybrid, acquiring both images and LiDAR point clouds of the environment. However, these two modalities remain essentially exploited independently, and few works propose to process them jointly. Nevertheless, such a joint exploitation would benefit from the high complementarity of these two sources of information:

• High resolution of the images vs high precision of the Li-DAR range measurement.

• Passive RGB measurement vs active intensity measurement in near infrared.

• Different acquisition geometries.

In this paper, we propose a fusion of image and LiDAR information into a single representation: a textured mesh. Textured meshes have been the central representation for virtual scenes in Computer Graphics, massively used in the video games and animation movies industry. Graphics cards are highly optimized for their visualization, and they allow a representation of scenes that holds both their geometry and radiometry. Textured meshes are now gaining more and more attention in the geospatial industry as Digital Elevation Models coupled with orthophotos, which were well adapted for high altitude airborne or space-borne acquisition, are not suited for the newer means of acquisition: closer range platforms (drones, mobile mapping) and oblique imagery.

We believe that this trend will accelerate, such that the geospatial industry will have an increasing need for efficient and high quality surface reconstruction and texturing algorithms that scale up to the massive amounts of data that these new means of acquisition produce.

This paper focuses on:

• using a simple reconstruction approach based on the sensor topology

• adapting the state-of-the-art texturing method of [START_REF] Waechter | Let there be color! Large-scale texturing of 3D reconstructions[END_REF] to mobile mapping images and LiDAR scans

We are able to produce a highly accurate surface mesh with a high level of detail and high resolution textures at city scale.

Related work

In this paper we present a visibility consistent 3D mapping framework to construct large scale urban textured mesh using both oriented images and georeferenced point cloud coming from a terrestrial mobile mapping system. In the following, we give an overview of the various methods related to the design of our pipeline.

From the robotics community perspective, conventional 3D urban mapping approaches usually propose to use LiDAR or camera separately but a minority has recently exploited both data sources to build dense textured maps [START_REF] Romanoni | Mesh-based 3d textured urban mapping[END_REF].

In the literature, both image-based methods [START_REF] Wu | Towards linear-time incremental structure from motion[END_REF][START_REF] Litvinov | Incremental solid modeling from sparse structure-from-motion data with improved visual artifacts removal[END_REF][START_REF] Romanoni | Incremental reconstruction of urban environments by edge-points delaunay triangulation[END_REF] and LiDARbased methods [START_REF] Hornung | Octomap: an efficient probabilistic 3d mapping framework based on octrees[END_REF][START_REF] Khan | Adaptive rectangular cuboids for 3d mapping[END_REF] often represent the map as a point cloud or a mesh relying only on Figure 1. The texturing pipeline geometric properties of the scene and discarding interesting photometric cues while a faithful 3D textured mesh representation would be useful for not only navigation and localization but also for photo-realistic accurate modeling and visualization.

The computer vision, computer graphics and photogrammetry communities have generated compelling urban texturing results. [START_REF] Sinha | Interactive 3d architectural modeling from unordered photo collections[END_REF]) developed an interactive system to texture architectural scenes with planar surfaces from an unordered collection of photographs using cues from structurefrom-motion. [START_REF] Tan | Large scale texture mapping of building facades. The International Archives of the Photogrammetry[END_REF] proposed an interactive tool for only building facades texturing using oblique images. [START_REF] Garcia-Dorado | Automatic urban modeling using volumetric reconstruction with surface graph cuts[END_REF] perform impressive work by texturing entire cities. Still, they are restricted to 2.5D scene representation and they also operate exclusively on regular block city structures with planar surfaces and treat buildings, ground, and buildingground transitions differently during texturing process. In order to achieve a consistent texture across patch borders in a setting of unordered registered views, [START_REF] Callieri | Masked photo blending: Mapping dense photographic data set on high-resolution sampled 3d models[END_REF][START_REF] Grammatikopoulos | Automatic multi-view texture mapping of 3d surface projections[END_REF] choose to blend these multiple views by computing a weighted cost indicating the suitability of input image pixels for texturing with respect to angle, proximity to the model and the proximity to the depth discontinuities. However, blending images induces strongly visible seams in the final model especially in the case of a multi-view stereo setting because of the potential inaccuracy in the reconstructed geometry.

While there exists a prominent work on texturing urban scenes, we argue that large scale texture mapping should be fully automatic without the user intervention and efficient enough to handle its computational burden in a reasonable time frame without increasing the geometric complexity in the final model. In contrast to the latter methods, [START_REF] Waechter | Let there be color! Large-scale texturing of 3D reconstructions[END_REF] proposed to use the multi-view stereo technique [START_REF] Frahm | Building rome on a cloudless day[END_REF][START_REF] Furukawa | Towards internet-scale multi-view stereo[END_REF] to perform a surface reconstruction and subsequently select a single view per face based on a pairwise Markov random field taking into account the viewing angle, the proximity to the model and the resolution of the image. Then, color discontinuities are properly adjusted by looking up the vertex' color along all adjacent seam edges. We consider the method of [START_REF] Waechter | Let there be color! Large-scale texturing of 3D reconstructions[END_REF] as a base for our work since it is the first comprehensive framework for texture mapping that enables fast and scalable processing.

In our work, we abstain from the surface reconstruction step for multiple reasons. As pointed out above, methods based on structure-from-motion and multi-view stereo techniques usually yield less accurate camera parameters, hence the reconstructed geometry might not be faithful to the underlying model compared to LiDAR based methods [START_REF] Pollefeys | Detailed real-time urban 3d reconstruction from video[END_REF] which results in ghosting effect and strongly visible seams in the textured model. Besides, such methods do not allow a direct and automatic processing on raw data due to relative parameters tuning for each dataset and in certain cases their computational cost may become prohibitive. [START_REF] Caraffa | 3d octree based watertight mesh generation from ubiquitous data[END_REF] proposed a generic framework to generate an octree-cell based mesh and texture it with the regularized reflectance of the LiDAR. Instead, we propose a simple but fast algorithm to construct a mesh from the raw LiDAR scans and produce photo-realistic textured models. In Figure 1, we depict the whole pipeline to generate large scale high quality textured models leveraging on the georeferenced raw data. Then, we construct a 3D mesh representation of the urban scene and subsequently fuse it with the preprocessed images to get the final model.

The rest of the paper is organized as follows: In Section 2 we present the data acquisition system. A fast and scalable mesh reconstruction algorithm is discussed in Section 3. Section 4 explains the texturing approach. We show our experimental results in Section 5. Finally, in Section 6, we conclude the paper proposing out some future direction of research. The used LiDAR scanner is a RIEGL VQ-250 that rotates at 100 Hz and emits 3000 pulses per rotation with 0 to 8 echoes recorded for each pulse, producing an average of 250 thousand points per second in typical urban scenes. The sensor records information for each pulse (direction (θ, φ), time of emission) and echo (amplitude, range, deviation).

DATA ACQUISITION

The MMS is also mounted with a georeferencing system combining a GPS, an inertial unit and an odometer. This system outputs the reference frame of the system in geographical coordinates at 100Hz. Combining this information with the information recorded by the LiDAR scanner and its calibration, a point cloud in (x, y, z) coordinates can be constructed. In the same way, using the intrinsic and extrinsic calibrations of each camera, each acquired image can be precisely oriented. It is important for our application to note that this process ensures that images and LiDAR points acquired simultaneously are precisely aligned (depending on the quality of the calibrations).

SENSOR TOPOLOGY BASED SURFACE RECONSTRUCTION

In this section, we propose an algorithm to extract a large scale mesh on-the-fly using the point cloud structured as series of line scans gathered from the LiDAR sensor being moved through space along an arbitrary path.

Mesh extraction process

During urban mapping, the mobile platform may stop for a moment because of external factors (e.g. road sign, red light, traffic congestion . . . ) which results in massive redundant data at the same scanned location. Thus, a filtering step is mandatory to get an isotropic distribution of the line scans. To do so, we fix a minimum distance between two successive line scans and we remove all lines whose distances to the previous (unremoved) line is less than a fixed threshold. In practice, we use a threshold of 1cm, close to the LiDAR accuracy.

Once the regular sampling is done, we consider the resulting point cloud in the sensor space where one dimension is the acquisition time t and the other is the θ rotation angle. Let θi be the angle of the i th pulse and Ei the corresponding echo. In case of multiple echoes, Ei is defined as the last (furthest) one, and in case of no return, Ei does not exist so we do not build any triangle based on it. In general, the number Np of pulses for a 2π rotation is not an integer so Ei has six neighbors Ei-1, Ei+1, Ei-n, Ei-n-1, Ei+n, Ei+n+1 where n = Np is the integer part of Np. These six neighbors allow to build six triangles. In practice, we avoid creating the same triangle more than once by creating for each echo Ei the two triangles it forms with echoes of greater indexes: Ei, Ei+n, Ei+n+1 and Ei, Ei+n+1, Ei+1 (if the three echoes exist) as illustrated in Figure 3. This allows the algorithm to incrementally and quickly build a triangulated surface based on the input points of the scans. In practice, the (non integer) number of pulses Np emitted during a 360 deg rotation of the scanner may slightly vary, so to add robustness we check if θi+n < θi < θi+n+1 and if it doesn't, increase or decrease n until it does.

Mesh cleaning

The triangulation of 3D measurements from a mobile mapping system usually comes with several imperfections such as elongated triangles, noisy unreferenced vertices, holes in the model, redundant triangles . . . to mention a few. In this section, we focus Figure 3. Triangulation based on the sensor space topology on three main issues that frequently occur with mobile terrestrial systems and affect significantly the texturing results if not adequately dealt with.

Elongated triangles filtering

In practice, neighboring echoes in sensor topology might belong to different objects at different distances. This generates very elongated triangles connecting two objects (or an object and its background). Such elongated triangles might also occur when the MMS follows a sharp turn. We filter them out by applying a threshold on the maximum length of an edge before creating a triangle, experimentally set to 0.5m for the data used in this study.

Isolated pieces removal

In contrast with camera and eyes that captures light from external sources, the LiDAR scanner is an active sensor that emits light itself. This results in measurements that are dependent on the transparency of the scanned objects which cause a problem in the case of semitransparent faces such as windows and front glass. The laser beam will traverse these objects, creating isolated pieces behind them in the final mesh. To tackle this problem, isolated connected components composed by a limited number of triangles and whose diameter is smaller than a user-defined threshold (set experimentally) are automatically deleted from the final model.

Hole filling

After the surface reconstruction process, the resulting mesh may still contain a consequent number of holes due to specular surfaces deflecting the LiDAR beam, occlusions and the non-uniform motion of the acquisition vehicle. To overcome this problem we use the method of (Liepa et al., 2003).

The algorithm takes a user-defined parameter which consists of the maximum hole size in terms of number of edges and closes the hole in a recursive fashion by splitting it until it gets a hole composed exactly with 3 edges and fills it with the corresponding triangle.

Scalability

The interest in mobile mapping techniques has been increasing over the past decade as it allows the collection of dense and very accurate and detailed data at the scale of an entire city with a high productivity. However, processing such data is limited by various difficulties specific to this type of acquisition especially the very high data volume (up to 1 TB by day of acquisition (Paparoditis et al., 2012)) which requires very efficient processing tools in terms of number of operations and memory footprint. In order to perform an automatic surface reconstruction over large distances, memory constraints and scalability issues must be addressed. First, the raw LiDAR scans are sliced into N chunks of 10s of acquisition which corresponds to nearly 3 million points per chunk. Each recorded point cloud (chunk) is processed separately as explained in the work-flow of our pipeline presented in Figure 4, allowing a parallel processing and faster production. Yet, whereas the aforementioned filtering steps alleviate the size of the processed chunks, the resulting models remain unnecessarily heavy as flat surfaces (road, walls) may be represented by a very large number of triangles that could be drastically reduced without loosing in detail. To this end, we apply the decimation algorithm of (Lindstrom and[START_REF] Lindstrom | Fast and memory efficient polygonal simplification[END_REF][START_REF] Lindstrom | Evaluation of memoryless simplification[END_REF]. The algorithm proceeds in two stages. First, an initial collapse cost, given by the position chosen for the vertex that replaces it, is assigned to every edge in the reconstructed mesh. Then, at each iteration the edge with the lowest cost is selected for collapsing and replacing it with a vertex. Finally, the collapse cost of all the edges now incident on the replacement vertex is recalculated. For more technical details, we refer the reader to (Lindstrom and[START_REF] Lindstrom | Fast and memory efficient polygonal simplification[END_REF][START_REF] Lindstrom | Evaluation of memoryless simplification[END_REF].

TEXTURING APPROACH

This section presents the used approach for texturing large scale 3D realistic urban scenes. Based on the work of [START_REF] Waechter | Let there be color! Large-scale texturing of 3D reconstructions[END_REF], we adapt the algorithm so it can handle our camera model (with five perspective images) and the smoothing parameters are properly adjusted to enhance the results. In the following, we give the outline of this texturing technique and its requirements. To work jointly with oriented images and LiDAR scans acquired by a mobile mapping system, the first requirement is that both sensing modalities have to be aligned in a common frame. Thanks to the rigid setting of the camera and the LiDAR mounted on the mobile platform yielding a simultaneous image and Li-DAR acquisition, this step is no more required. However, such setting entails that a visible part of the vehicle appears in the acquired images. To avoid using these irrelevant parts, an adequate mask is automatically applied to the concerned images (back and front images) before texturing as shown in Figure 5.

Typically, texturing a 3D model with oriented images is a twostage process. First, the optimal view per triangle is selected with respect to certain criteria yielding a preliminary texture. Second, a local and global color optimization is performed to minimize the discontinuities between adjacent texture patches. The two steps are discussed in Sections 4.2 and 4.3.

View selection

To determine the visibility of faces in the input images, a pairwise Markov random field energy formulation is adopted to compute a labeling l that assigns a view li to be used as texture for each mesh face Fi:

E(l) = F i ∈F aces E d (Fi, li) + F i ,F j ∈Edges
Es(Fi, Fj, li, lj)

(1) where

E d = - φ(F i ,l i ) ||∇(I l i )||2dp
(2)

Es = [li = lj] (3)
The data term E d (2) computes the gradient magnitude ||∇(I l i )||2 of the image into which face Fi is projected using a Sobel operator and sum over all pixels of the gradient magnitude image within face Fi's projection φ(Fi, li). This term is large if the projection area is large which means that it prefers close, orthogonal and in-focus images with high resolution. The smoothness term Es (3) minimizes the seams visibility (edges between faces textured with different images). In the chosen method, this regularization term is based on the Potts model ([.] the Iverson bracket) which prefers compact patches by penalizing those that might give severe seams in the final model and it is extremely fast to compute. Finally, E(l) (1) is minimized with graph-cuts and α-expansion [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF].

Color adjustment

After the view selection step, the obtained model exhibits strong color discontinuities due to the fusion of texture patches coming from different images and to the exposure and illumination variation especially in an outdoor environment. Thus, adjacent texture patches need to be photometrically adjusted. To address this problem, first, a global radiometric correction is performed along the seam's edge by computing a weighted average of a set of samples (pixels sampled along the discontinuity's right and left) depending on the distance of each sample to the seam edge extremities (vertices). Then, this global adjustment is followed by a local Poisson editing [START_REF] Pérez | Poisson image editing[END_REF] applied to the border of the texture patches. All the process is discussed in details in [START_REF] Waechter | Let there be color! Large-scale texturing of 3D reconstructions[END_REF] work.

Finally, the corrections are added to the input images, the texture patches are packed into texture atlases, and texture coordinates are attached to the mesh vertices.

EXPERIMENTAL RESULTS

Mesh reconstruction

In Figure 6, we show the reconstructed mesh based on the sensor topology and the adopted decimation process. In practice, we parameterize the algorithm such that the approximation error is below 3cm, which allows in average to reduce the number of triangles to around 30% of the input triangles.

Texturing the reconstructed models

In this section, we show some texturing result (Figure 7) and the influence of the color adjustment step on the final textured models (Figure 8). Before the radiometric correction, one can see several color discontinuities especially on the border of the door and on some parts of the road (best viewed on screen). More results are presented in the appendix to illustrate the high quality textured models in different places in Rouen, France.

Performance evaluation

We evaluate the performance of each step of our pipeline on a dataset acquired by Stereopolis II [START_REF] Paparoditis | Stereopolis ii: A multi-purpose and multi-sensor 3d mobile mapping system for street visualisation and 3d metrology[END_REF] 1, we present the required input data to texture a chunk of acquisition (10s); the average number of views and the number of triangles after decimation. Figure 9 shows the timing of each step in the pipeline to texture the described setting. Using a 16-core Xeon E5-2665 CPU with 12GB of memory, we are able to generate a 3D mesh of nearly 6 Million triangles in less than one minute compared to the improved version of Poisson surface reconstruction [START_REF] Kazhdan | Screened poisson surface reconstruction[END_REF] where they reconstruct a surface of nearly 20000 triangle in 10 minutes. Moreover, in order to texture small models with few images (36 of size (768 × 584)) in a context of super-resolution, [START_REF] Goldlücke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF] takes several hours (partially on GPU) compared to the few minutes we take to texture our huge models. Finally, all the dataset is textured in less than 30 computing hours. The sensor mesh reconstruction is quite novel but very simple.

We believe that such a textured mesh can find multiple applications, directly through visualization of a mobile mapping acquisition, or more indirectly for processing jointly image and LiDAR data: urban scene analysis, structured reconstruction, semantization, ...

PERSPECTIVES

This work leaves however important topics unsolved, and most importantly the handling of overlaps between acquired data, at intersections or when the vehicle passes multiple times in the same scene. We have left this issue out of the scope of the current paper as it poses numerous challenges:

• Precise registration over the overlaps, sometimes referred to as the loop-closure problem.

• Change detection between the overlaps.

• Data fusion over the overlaps, which is strongly connected to change detection and how changes are handled in the final model.

Moreover, this paper proposed a reconstruction from LiDAR only, but we believe that the images hold a pertinent geometric information that could be used to complement the LiDAR reconstruction, in areas occluded to the LiDAR but not to the cameras (which often happens as their geometries are different). Finally, an important issue that is partially tackled in the texturation: the presence of mobile objects. Because the LiDAR and images are most of the time not acquired strictly simultaneously, mobile objects might have an incoherent position between image and LiDAR, which is a problem that should be tackled explicitly.

Figure 2 .

 2 Figure 2. The set of images acquired by the 5 full HD cameras (left, right, up, in front, from behind)

Figure 4 .

 4 Figure 4. The proposed work-flow to produce large scale models

4. 1

 1 Figure 5. Illustration of the acquired frontal images processing

Figure 9 .

 9 Figure 9. Performance evaluation of a chunk of 10s of acquisition

  Figure 6. Decimation of sensor space topology mesh

Table 1 .

 1 Statistics on the input data per chunkIn Table

	dur-

ACKNOWLEDGEMENTS

We would like to acknowledge the French ANR project pLaT-INUM (ANR-15-CE23-0010) for its financial support.

APPENDIX

In this appendix, we show more texturing results obtained from the acquired data in Rouen, France. Due to memory constraints, we are not able to explicitly show the entire textured model (17Km). However, we can show a maximum size of 70s (350m) of textured acquisition (Figure 10).