Justin Salez

Every totally real algebraic integer is a tree eigenvalue

Keywords: adjacency matrix, tree, eigenvalue, totally real algebraic integer 2010 MSC: 05C05, 05C25, 05C31, 05C50

Graph eigenvalues are examples of totally real algebraic integers, i.e. roots of real-rooted monic polynomials with integer coefficients. Conversely, the fact that every totally real algebraic integer occurs as an eigenvalue of some finite graph is a deep result, conjectured forty years ago by Hoffman, and proved seventeen years later by Estes. This short paper provides an independent and elementary proof of a stronger statement, namely that the graph may actually be chosen to be a tree. As a by-product, our result implies that the atoms of the limiting spectrum of n×n symmetric matrices with independent Bernoulli c n entries (c > 0 is fixed as n → ∞) are exactly the totally real algebraic integers. This settles an open problem raised by Ben Arous (2010).

Introduction

By definition, the eigenvalues of a finite graph G = (V, E) are the roots of its characteristic polynomial Φ G (x) := det(xI -A), where A = {A i,j } i,j∈V is the adjacency matrix of G:

A i,j = 1 if {i, j} ∈ E 0 otherwise.
Those eigenvalues capture a considerable amount of information about G.

For a detailed account, see e.g. [START_REF] Cvetković | Spectra of graphs[END_REF][START_REF] Brouwer | Spectra of graphs[END_REF]. It follows directly from this definition that any graph eigenvalue is a totally real algebraic integer, i.e. a root of some real-rooted monic polynomial with integer coefficients. Remarkably enough, URL: http://www.proba.jussieu.fr/∼salez/ (Justin Salez)

Preprint submitted to Elsevier September 4, 2014 the converse is also true: every totally real algebraic integer is an eigenvalue of some finite graph. This deep result was conjectured forty years ago by Hoffman [START_REF] Hoffman | Eigenvalues of graphs[END_REF], and established seventeen years later by Estes [START_REF] Estes | Eigenvalues of symmetric integer matrices[END_REF], see also [START_REF] Bass | Eigenvalues of symmetric matrices and graphs[END_REF].

The present paper provides an independent, elementary proof of a stronger statement, namely that the graph may actually be chosen to be a tree.

Theorem 1. Every totally real algebraic integer is an eigenvalue of some finite tree.

Trees undoubtedly play a special role in many aspects of graph theory. We therefore believe that the strengthening provided by Theorem 1 may be of independent interest, beyond the fact that it provides a simpler proof of Hoffman's conjecture. In addition, Theorem 1 settles an open problem raised by Ben Arous [START_REF]Open problems of the 2010 AIM Workshop on random matrices[END_REF]Problem 14], namely that of determining the set Σ of atoms of the limiting spectral distribution of n × n symmetric matrices with independent Bernoulli c n entries (c > 0 is fixed and n → ∞). Indeed, it follows from the log-Hölder continuity of the spectrum of integer matrices at algebraic numbers (see e.g. [START_REF] Veselić | Spectral analysis of percolation Hamiltonians[END_REF]Section 6]) that Σ is contained in the set of totally real algebraic integers. On the other hand, Σ is easily seen to contain all tree eigenvalues, as noted by Ben Arous. Theorem 1 precisely states that those inner and outer bounds coincide, thereby settling the question.

Outline of the proof

Let T be a finite tree with a distinguished vertex o (the root). Removing o naturally yields a decomposition of T into smaller rooted trees T 1 , . . . , T d (d ∈ N) as depicted in the following diagram:

o | | | | | | | | Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q T 1 T 2 • • • T d
To such a rooted tree, let us associate the rational function

f T (x) = 1 - Φ T (x) xΦ T \o (x) = 1 - Φ T (x) xΦ T 1 (x) • • • Φ T d (x) . (1)
Expressed in terms of this function, the classical recursion for the characteristic polynomial of trees (see e.g. [2, Proposition 5.1.1]) simply reads

f T (x) = 1 x 2 d i=1 1 1 -f T i (x) , (2)
the sum being interpreted as 0 when empty (i.e. when T is reduced to o). Now fix λ ∈ C \ {0}. In view of (1), the problem of finding a (minimal) tree with eigenvalue λ is equivalent to that of finding T such that f T (λ) = 1. Thanks to the recursion (2), this task boils down to that of generating the number 1 from the initial seed 0 using repeated applications of the maps

(α 1 , . . . , α d ) -→ 1 λ 2 d i=1 1 1 -α i (d ∈ N).
As an example, consider the golden ratio λ = 1+ √ 5

2 . Iterating 4 times the map α → 1 λ 2 (1-α) and using the identity λ 2 = λ + 1 yields successively:

0 -→ 1 λ 2 -→ 1 λ 2 -1 = 1 λ -→ 1 λ 2 -λ = 1
, which shows that λ is an eigenvalue of the linear tree T = P 4 . Remarkably enough, this seemingly specific argument can be extended in a systematic way to any totally real algebraic integer λ, and the numbers that may be produced in this way can be completely determined. To formalize this, let us fix a totally real algebraic integer λ = 0, and introduce the rational function

Ψ(x) = 1 λ 2 (1 -x) . (3)
Define F ⊆ R as the smallest set containing 0 and satisfying for all d ≥ 1,

α 1 , . . . , α d ∈ F \ {1} =⇒ Ψ(α 1 ) + • • • + Ψ(α d ) ∈ F . (4)
We will prove that F is nothing but the field generated by λ 2 :

F = P (λ 2 ) Q(λ 2 ) : P, Q ∈ Z[x], Q(λ 2 ) = 0 =: Q(λ 2 ). (5)
In particular, 1 ∈ F , and Theorem 1 follows. The remainder of the paper is devoted to the proof of ( 5). The detailed argument is given in Section 4, while Section 3 provides the necessary background on algebraic numbers.

Algebraic preliminaries

A number ζ ∈ C is algebraic if there is P ∈ Q[x]
such that P (ζ) = 0. In that case, such P are exactly the multiples of a unique monic polynomial

P 0 ∈ Q[x], called the minimal polynomial of ζ. The algebraic number ζ is
• totally real if all the complex roots of P 0 are real ;

• totally positive if all the complex roots of P 0 are real and positive.

The following Lemma gathers the basic properties of algebraic numbers that will be used in the sequel. These are well-known (see e.g. [START_REF] Lang | Algebra[END_REF]) and follow directly from the fact that if P (x) = i (xα i ) and Q(x) = j (xβ j ) have rational coefficients, then so do the polynomials i,j

(x -α i -β j ), i x - 1 α i , i,j (x -α i β j ) i (x + α i ), i (x 2 -α 2 i ), i (x 2 -α i ).
Lemma 1 (Elementary algebraic properties).

a. The totally real algebraic numbers form a sub-field of R. b. The set of totally positive algebraic numbers is stable under +, ×, ÷. c. If α is totally real and β is totally positive, then α+nβ is totally positive for all sufficiently large n ∈ N. d. If α = 0 is totally real, then α 2 is totally positive.

We shall also use twice the following elementary result.

Lemma 2. Let ζ be algebraic with minimal polynomial P . Set n = deg P . Then for any q 1 > . . . > q n ∈ Q, there exist m 1 , . . . , m n ∈ Z such that

m 1 ζ -q 1 + • • • + m n ζ -q n ∈ N + = {1, 2, . . .}, (6)
and m k has the same sign as (-1) k P (q k ) for every k ∈ {1, . . . , n}.

Proof. For 1 ≤ k ≤ n, consider the rational number

r k := -P (q k ) j =k (q k -q j )
.

Note that r k has the same sign as (-1) k P (q k ), since q 1 > . . . > q n . Moreover,

r 1 k =1 (x -q k ) + • • • + r n k =n (x -q k ) = n k=1 (x -q k ) -P (x).
Indeed, both sides are polynomials of degree less than n, and they coincide at the n points q 1 , . . . , q n . Evaluating at x = ζ gives

r 1 ζ -q 1 + • • • + r n ζ -q n = 1,
and multiplying this by a large enough integer yields the result.

Proof

Before we start, let us make three simple observations which will be used several times in the sequel. First, by (4), we have for any k ∈ N,

1 λ 2 -k = Ψ    Ψ (0) + • • • + Ψ(0) k terms    ∈ F . (7)
Second, F is stable under internal addition:

α, β ∈ F =⇒ α + β ∈ F . (8)
Indeed, the conclusion is trivial if α = 0 or β = 0. Now if α, β are non-zero elements of F , then by construction they are of the form

α = Ψ(α 1 ) + • • • + Ψ(α n ) and β = Ψ(β 1 ) + • • • + Ψ(β m ),
for some n, m ≥ 1 and α 1 , . . . , α n , β 1 , . . . , β m in F \ {1}. But then,

α + β = Ψ(α 1 ) + • • • + Ψ(α n ) + Ψ(β 1 ) + • • • + Ψ(β m ),
which, by ( 4), shows that α+β ∈ F . Third, the field Q(λ 2 ) obviously contains 0 and satisfies (4). Since F is minimal with this property, we deduce that

F ⊆ Q(λ 2 ). ( 9
)
By part (a) of Lemma 2, we also get that all elements in F are totally real.

Step 1: F contains a positive integer

We may assume that 1 / ∈ F , otherwise there is nothing to prove. Consequently, we do not need to worry about divisions by zero when applying Ψ to an element α ∈ F . Let us first apply Lemma 2 to ζ = λ 2 with 7) and ( 8), it follows that the sum appearing in ( 6) is the difference of two elements in F . In other words, we have found ∆ ∈ N + and α with the following property:

q k = k, 1 ≤ k ≤ deg ζ. From (
α ∈ F and α -∆ ∈ F . (10)
As already noted, α is totally real. In fact we may even assume that 1α is totally positive, because α ′ = α + β also satisfies (10) for any β ∈ F , and choosing β = j λ 2 -k with j, k ∈ N large enough eventually makes 1α ′ totally positive, by parts (b) and (c) of Lemma 1. In turn, parts (b) and (d) now guarantee that

ξ := λ 2 (1 -α) is totally positive. ( 11
)
Now fix j, k ∈ N and set i = (∆ -1)j + 1. Since F is stable under addition, property (10) and the fact that

1 λ 2 = Ψ(0) ∈ F imply that α + • • • + α i terms + (α -∆) + • • • + (α -∆) j terms + 1 λ 2 + • • • + 1 λ 2 k terms ∈ F .
But this number equals 1 -(∆j + 1)(1α) + k λ 2 , so applying Ψ gives 1 (∆j + 1)ξk ∈ F .

Adding up ∆j + 1 copies of this last number, we finally arrive at

1 ξ -q ∈ F for any q ∈ Q := k ∆j + 1 : j, k ∈ N . (12)
We may now conclude: by (11), the minimal polynomial P of ξ has n := deg P pairwise distinct positive roots. Since Q is dense in [0, ∞), one can find q 1 > • • • > q n in Q that interleave those roots, in the sense that P (q k ) has sign (-1) k for every 1 ≤ k ≤ n. Consequently, Lemma 2 provides us with non-negative integers m 1 , . . . , m n such that

m 1 ξ -q 1 + • • • + m n ξ -q n ∈ N + .
On the other hand, this sum is in F by ( 12) and [START_REF] Lang | Algebra[END_REF]. Thus, F ∩ N + = ∅.

Step 2: (F, +) is a group

We know that F contains some d ∈ N + . Since d + d also belongs to F , we may assume without loss of generality that d = 1 to avoid divisions by zero below. Now fix α ∈ -F with α = 1. Since F is stable under addition,

d + (-α) + • • • + (-α) d-1 terms ∈ F .
Applying Ψ shows that -1 λ 2 (1-α)(d-1) ∈ F . Adding up (d -1) copies of this number, we conclude that -1 λ 2 (1-α) ∈ F . We have proved:

α ∈ (-F ) \ {1} =⇒ Ψ(α) ∈ -F .
In other words, -F is stable under Ψ. In view of ( 8), we deduce that -F satisfies (4). By minimality of F , we conclude that F ⊆ -F , i.e. that F is stable under negation. Thus, the monoid (F , +) is a group.

Step 3: F is the field Q(λ 2 ).

In view of (9), we only need to show that for P, Q

∈ Z[x] with Q(λ 2 ) = 0, P (λ 2 ) Q(λ 2 ) ∈ F . ( 13
)
Since λ 2 is an algebraic integer, we may assume that Q is monic with deg Q > deg P (otherwise, replace Q with Q + P deg P 0 , where P 0 denotes the minimal polynomial of λ 2 ). Let us prove the claim by induction over n = deg Q. The case n = 0 is simply the fact that 0 ∈ F . Now, assume that the claim holds for a certain n ∈ N, and consider

Q(x) = x n+1 + a n x n + • • • + a 0 ,
with a 0 , . . . , a n ∈ Z. Let us first prove (13) in the following two special cases:

• Case 1: P (x) = x n . By our induction hypothesis, 1 1+λ 2n ∈ F and hence

1 λ 2n+2 + 1 λ 2 = Ψ 1 1 + λ 2n ∈ F .
But F also contains 1 λ 2 , . . . , 1 λ 2n by our induction hypothesis. Since (F , +) is a group, one deduces that F contains

- a n λ 2 + • • • + a 0 λ 2n+2 = 1 - Q(λ 2 ) λ 2n+2 .
Finally, applying Ψ shows that λ 2n Q(λ 2 ) = P (λ 2 ) Q(λ 2 ) ∈ F , as desired.

• Case 2: P is monic of degree n with P (0) = 1. Then R(x) := P (x) -Q(x) -Q(0)P (x) x is a polynomial over Z with deg R < n. Thus, our induction hypothesis guarantees that F contains R(λ 2 ) P (λ 2 ) , hence R(λ 2 ) P (λ 2 ) -Q(0) λ 2 and hence also

Ψ R(λ 2 ) P (λ 2 ) - Q(0) λ 2 = P (λ 2 ) Q(λ 2 ) .
For the general case, note that every monomial x k (0 ≤ k ≤ n) may be written as a signed sum of polynomials P of the form considered in the two special cases above. Since (F , +) is a group, we conclude that (13) holds for all P ∈ Z[x] with deg P ≤ n, and the induction is complete.

Acknowledgment

The author warmly thanks Arnab Sen for pointing out Problem 14 in [START_REF]Open problems of the 2010 AIM Workshop on random matrices[END_REF].


Chunlei Yu
email: chunlei.yu@utc.frdomaine

Véronique Cherfaoui

Philippe Bonnifait

An Evidential Scheme for a Velodyne Ground Truth

Keywords: theorie évidentielle, vérité terrain, Velodyne Occupancy grid, evidential theory, ground truth, Velodyne

Papier soumis dans le

Introduction

A ground truth perception equipment is a key issue for the development of driving assistance systems and autonomous vehicles. Although the V elodyne lidar [START_REF] Inc | HDL-64E S2 and S2.1 High Definition Li-DAR Sensor User's Manual and Programming Guide[END_REF] provides rich and accurate information about the surrounding environment, an adapted sensor model to tackle its uncertainty and to fully profit its rich information is rarely discussed in the literature. To cope with errors and uncertainty for building occupancy grid maps in perception systems, Bayesian methods are the common background. Many extensions have been published in the literature, like the Bayesian Occupancy Filter (BOF) [START_REF] Coue | Bayesian occupancy filteing for multitarget tracking : an automotive application[END_REF] which estimates both the occupancy and the speed of the cells. [START_REF] Lefaudeux | Extended occupation grids for non-rigid moving objects tracking[END_REF] proposed an extended occupancy grid approach which can be used to track non-rigid moving objects. [START_REF] Weiss | Robust driving path detection in urban and highway scenarios using a laser scanner and online occupancy grids[END_REF] applied a Bayesian occupancy grid map to detect road boundaries. In this paper, we propose an evidential framework to build an occupancy grid map in the proximity of the host vehicle. We propose a tailored sensor model which interprets V elodyne data frames into a local 2D occupancy grid map in this work. A fusion process based on Dempster Shafer data fusion enhances the ground truth map by fusing data acquired at different locations. The paper is organized as follows: Section 2 details the evidential sensor model developed to merge high definition lidar sensor measurements into scan grid maps. Section 3 illustrates the fusion scheme based on the evidential framework. Section 4 shows the implementation details and experimental results.

An evidential sensor model for the Velodyne

In this section, an inverse sensor model for the V elodyne is developed. In our approach, we build 2D evidential occupancy grid map (denoted as scan grid) with data from the Velodyne by making a projection on the ground plane.

Evidential framework

The frame of discernment is defined as: Ω = {O, F }, the two singletons are the proposition O and the proposition F, indicating respectively that the specific cell is Occupied and F ree. One has to increase this set, by considering the power set which is defined as 2 Ω = {∅, F, O, Ω}. Ω indicates ignorance about the state of the cell (U nknown cell), and ∅ indicates that no proposition fits the cell.

The basic probability assignment (BP A) is a direct support for a proposition, which is denoted by function m.

Polar sensor model basic concepts

In order to be as close as possible to the sensor's rotating acquisition process, the scan grid map is created in a polar frame.

Figure 1: Space representation in Polar Coordinates, showing how measurements from V elodyne can be interpreted in the evidential framework. Green refers to free space, red refers to occupied space and dark refers to unknown space.

As shown in Figure 1, the whole space around the car is divided into angular sectors, while each sector in the space is divided into different cells. For the BP A assignment process, we consider the sectors independent from each other. Indeed, if the sampling of the grid is high enough and since the laser beam width is very small, this assumption is well verified. The state assignment respects the least commitment principle. Velodyne points provide information about the state of the scanned cells. Therefore, the space where there is no information is treated as U nknown.

Grid state assignment

Let define an elevation threshold denoted H which specifies the elevation of points considered as obstacles. The value of the threshold has to be chosen carefully in order to filter noise. When the elevation of an echo is above H, we consider the cell Occupied. Figure 2 illustrates the state assignment process. To differentiate the ground information from the above-ground information, we set up a scene where a human and a car are near our host vehicle. Nine beams from Velodyne are drawn for illustration. The four lowest green beams hit the ground, where G1, G2, G3 and G4 are respectively the intersections on the ground. The five red beams reach the human and the car in the distance, and their intersections are H1, H2, H3, H4 and H5. The grid on the bottom serves as an illustrating plot of the polar world model shown in Figure 2, in which the horizontal axis shows the range variation and the vertical axis represents the angle variation. One object O1 is designed near the host vehicle to illustrate the fact that there exists space that is not detectable with Velodyne installed on the roof. Thus the least commitment principle can guarantee the information integrity in the model. Based on the least commitment principle, the state allocation process obeys the following rules: the cells which contain the H3, H4 and H5 are marked O(Occupied), as these points are above the threshold; the cells which contain respectively G1, G2, G3 and G4 are marked as F (F ree), as these points are detected on the ground; although H1 is beneath the threshold H, abut the same cell also contains the H2, which is above the threshold, to eliminate the potential conflict, in our approach, we make an additional assumption: a detected obstacle is modeled as a vertical surf ace that is linked to the ground. This cell is marked Occupied. All the other cells are marked U (U nknown).

G1 G2 H1 H2 G3 H h H3 G4 H4 Range Angle O U U U F F F U F F U U U U U U 1

Backward free space propagation

One benefit of defining the threshold H is the extension of the F ree region by making a backward extrapolation to the host vehicle. The effect is illustrated in Figure 2. Considering the beam which intersects the ground at G4, one can deduce that there is no obstacle in the interval L which has an elevation superior to threshold H. In this case, the zone F ree corresponding to G4 is extended towards the host vehicle. The states of cell 8 is also set to F ree because we extrapolate at point G3. Cell 5 is not propagated to F ree because the extrapolation distance can not cover the whole cell, no state propagation is made.

Grid mass assignment

We need now to assign a BP A to the grid cells to quantify the belief. We propose a grid mass assignment model based on information accumulation. In Figure 2, cell 6, cell 9 and cell 12 are all set to F ree. However, we should have unequal amount of beliefs about their F ree state because in cell 6, there exist two points on the ground to support the state, whereas in cell 9 and cell 12, there exists only one point. The same stands for the Occupied cells, cell 15 and cell 19 should have unequal amount of beliefs about the occupied state. M ore points supporting one state should contribute to more belief s on the state. This accumulation concept reinforces the belief assigned to each proposition.

The BP A values are based on sensor uncertainties. Let α F A and α M D correspond to the the probability of false δs Beam divergence of Lidar projected on ground δg Angle resolution of polar grid Figure 3: Missed-detection illustration alarm and missed-detection. A false alarm is when the sensor issues an impact whereas there is nothing. It depends essentially on the sensor noise and on multipath propagation. A missed detection is mainly related to the reflexivity of the target and to the ratio between the cell size and the beam width. Figure 3 shows how this ratio results in missed-detection. δ s represents the divergence of Lidar (beam width), and δ g represents the angular resolution of the polar grid. In this circumstance, one beam of Lidar can not cover the whole sector. This beam can miss potential obstacles within its blind regions of the cell. The misseddetection effect thus has to be considered. The proposed model calculates the BP As with probabilistic approach. Based on the definition of false alarm, its probability α

m(O) = 0, m(F ) = 1-α n F M D , m(Ω) = 1-m(F ), m(∅) = 0
For an Occupied cell:

m(O) = 1-α n O F A , m(F ) = 0, m(Ω) = 1-m(O), m(∅) = 0
For an U nknown cell, the initial state is kept:

m(O) = 0, m(F ) = 0, m(Ω) = 1, m(∅) = 0
To keep the processing load reasonable, we suggest to extrapolate the free level m(F ) uniformly in the backward propagation with no decrease to the cells that have no echoes.

From polar to Cartesian

The approach merges the Velodyne scan data into occupancy grid map. This map is built in a polar coordinate system, but for the fusion purpose, we need to transform it into a Cartesian coordinate system. All the information collected has to be transformed into Cartesian coordinates, with the least loss. In our approach, we have adopted the bilinear interpolation algorithm introduced by [START_REF] Moras | Evidential perception grids for robotics navigation in urban environment[END_REF].

Ego-Map Grid Fusion

The scan grid map is not complete, because there exist uncertainties in the map due to unperceived space. With Dempster's conjunctive rule, the fusion of several successive scan grids allows to eliminate the uncertainties in the map. To make this fusion, the ego-motion of the host vehicle has to be compensated and then every new scan grid of the Velodyne is merged into a grid denoted EgoM apGrid. Figure 4 illustrates the whole approach. The fusion process is sequential. At time t, the new scan grid ScanGrid(t) updates EgoM apGrid(t -1) to provide a new EgoM apGrid(t).

To accommodate to the dynamic environment, we adopt the approach proposed by [START_REF] Moras | Moving objects detection by conflict analysis in evidential grids[END_REF] and use a decay factor for EgoM apGrid. The information in EgoM apGrid can become aged and not consistent with reality. This effect can be especially important when moving objects are in the scene. The equations below show how mass functions are discounted with a decay factor denoted β.

β m M (A) = β * m M (A), A ⊂ Ω β m M (Ω) = 1 -β + β * m M (Ω)
The fusion process adopts the Demster-Shafer conjunctive rule, as shown in Equation 1. For denotation purpose, let m M,t and m S,t represent respectively the mass functions of EgoM apGrid and ScanGrid at time t.

m M,t = β m M,t-1 ⊕ m S,t (1)
results

Experimental implementation

The approach was tested with the vehicle shown in Figure 5a. Figure 5b displays the trajectory. We have implemented the approach in C++. The V elodyne data was acquired at 10Hz frequency. The ego-motion between two scans is estimated using CAN data. For the purpose of demonstration, the scan grids of (72 * 72) meters are built with uniform cells of size(0.1 * 0.1) meters. In the polar grid map, the angular resolution is 0.5 degrees and the radius resolution is 0.1 meters.

For the tuning parameters, we have adopted α M D = 0.66, α F A = 0.15. α M D is based on the ratio of the beam divergence of V elodyne (estimated to 0.17 degrees by [START_REF] Lonjaret | Rapport d'essais de qualification de l'imageur laser[END_REF]) and the resolution of the grid (0.5 degrees). We have tuned α F A to 0.15 in order to consider the sensor noise and the multipath phenomenon. One typical scene is chosen where the host vehicle is in an urban road. The resultant scan grid is shown in Figure 6. H is set to 0.2 for illustration. Figure 7 shows the result of fusion. One can remark that the green level in the central part of the fusion result map is lower compared to the other surrounding parts of the F ree space. The reason for this phenomenon is that the sensor receives no information from this space in the present scan. The decay factor was set to 0.98 to slowly discount aged information. This effect is noticeable in the fusion result map: the right bottom part of the map shows darker green which means less evidence to be F ree. This can also be explained by the ScanGrid: the state of this space is U nknown in the ScanGrid. With no evidence supporting the space state, the system tends to gradually forget its past state. In this case, m(F ) decreases until the system totally forgets the state, and it becomes U nknown again.

Results

Conclusion

In this paper, we have proposed an evidential sensor model to interpret V elodyne data into scan grid maps. Based on the least commitment principle, the proposed model provides reliable grid state indications of the space. The principle of information accumulation enables to manage the sensor's uncertainties based on probabilistic approach, which greatly augments the accuracy of mass allocation. The resulting scan grid map is conservative so provides high reliability. The fusion process based on the evidential theory yields a complete occupancy grid map. Based on the real experiments, we have observed that the approach provides satisfactory results. In future work, this occupancy grid map can be used as ground truth to evaluate the performance of other perception schemes that use cheaper sensors.

Figure 2 :

 2 Figure 2: Sensor model for the scan grid construction process. Top, bird view of the host vehicle, x represents the motion direction. Middle, lateral visualization of the threshold scene and of the backward free extrapolation (short vertical lines, explained in section 2.4). Bottom, state assignment.

  F A = P (C = F | ξ 1 ), Where ξ 1 represents one obstacle impact in the cell, C stands for the state of the cell. If we suppose that errors are independent, the total false alarm probability in one cell given n O obstacle points are detected in this cell should be P (C = F | ξ 1 , ξ 2, ... , ξ N ) = α n O F A . Thus the probability of Occupied can be represented as: P (C = O | ξ 1 , ξ 2 , ..., ξ N ) = 1-α n O F A . Based on the same methodology, for F ree cells, the missed-detection probability α M D = P (C = O | ∆), where ∆ represents no above ground impact is returned to the sensor. If we assume n F ground points are detected in this cell, the total misseddetection probability should be α n F M D . Thus the probability of F ree should be represented as 1 -α n F M D . The BP A assignment thus follows the rules below: For a F ree cell:

Figure 4 :

 4 Figure 4: Workflow of the scan grid construction and fusion

Figure 5 :

 5 Figure 5: Experimental platform of Heudiasyc and Trajectory

Figure 6 :

 6 Figure 6: Occupancy scan grid with backward extrapolation, H = 0.2. Green represents F ree space, Red represents Occupied space, Dark represents U nknown space.

Figure 7 :

 7 Figure 7: Fusion result map of several scan grids.


Huijuan Xu

Yuju He

Xunsi Wang
email: xunsiwang@siom.ac.cn

Qiuhua Nie

Peiquan Zhang

Tiefeng Xu

Shixun Dai

Xianghua Zhang

Guangming Tao

Preparation of Low-loss Ge 15 Ga 10 Te 75 Chalcogenide Glass for Far-IR Optics Applications

Keywords: Chalcogenide glass, Optical loss, Purification

Ge 15 Ga 10 Te 75 (GGT) glass shows good transparency between 2 to 25 micron wavelengths, good chemical and thermal stability to be drawn into fiber, which appears to be a good candidate for developing far-IR fiber-optics devices, although there are strong absorption peaks caused by impurities in the glass. With the aim of decreasing the content of impurities and micro-crystal particles in prepared GGT glass samples, a rapid heating furnace and the fast distillation method based on vapor evaporation plus deposition under vacuum condition was adopted. Properties measurements including Differential Scanning Calorimeter (DSC), Vis-NIR and IR transmitting spectra were performed on the prepared glass samples. Dependence of optical loss on the types of oxygenic getters and their contents and glass quenching temperature was also studied. All these results show that the average optical losses of distilled glass samples were greatly improved by the designated purification processes. Besides, the quality of the glass samples can be improved with the optimized quenching temperature. In all, the optical loss of the glass can be reduced effectively. Minimum optical losses of 0.042 dB/cm at 9 µm and 0.037 2 dB/cm at 12 µm are obtained after a right purification process, which are the lowest loss of the GGT chalcogenide glass nowadays.

Introduction

The Darwin mission performed by the European Space Agency (ESA) aims at detecting life signs in extra solar terrestrial planet [1,2]. The mission will scan the nearby universe in order to get its accurate contents of CO 2 which is regarded as one of the most important spectral signatures of life. Remote optical detection of CO 2 involves monitoring of its two vibrational absorption bands at 4 µm and 16 µm [3,4]. In this mission, a nulling interferometer operating in the IR is crucial for filtering useful IR light from the planet, cutting off and occulting the blinding light coming from the central star. One of the key optical elements of the interferometer will be a single-mode (SM) IR optical fiber or planar waveguide operating in the window of 3 to 20 µm. Therefore, a special glass is crucial for achieving a satisfactory detection limit. Current materials suitable for designing the SM fibers are the polycrystalline silver halides [5,6] and the glassy materials that belong to the broad family of the so-called chalcogenide glasses (ChGs) [7,8], especially that of Tellurium (Te) enriched ChGs due to its heavier atomic mass. Consequently the intrinsic multi-phonon absorption of Te-based ChG is shifted to longer wavelength in comparison with sulfur-based or selenium-based glasses.

Up to now, some advances of Te-based ChGs containing some glass former such as elements of Ge, Ga, I and As, have been reported [9,10]. Among these glasses, Ge 15 Ga 10 Te 75 (GGT) glass is a very promising material for transmitting far-IR radiation and developing IR fiber-optics devices. Advantages of GGT glass are: nontoxic ingredients (no As), low phonon energy, good transparency between 2-25 µm, good chemical stability and good thermal stability to be drawn into fiber [11]. However, there is an intensive absorption peak around 15-20 µm band in the spectrum, which is assigned to a kind of Ga-O vibration, and it is very hard to be purified by common vacuum distilling method [12]. To decrease the intensity of oxide absorption peak, Zhang et al [13] prepared GGT glass mixed with oxygen getter Aluminum (Al) and obtained a loss of 0.6 dB/cm at 10 µm. However, the addition of metal getter would lead to an increase of scattering loss by impurities of oxides. Additionally, it is well known that Te-based ChGs are prone to devitrification as that Te has strong metallic character in comprison with S and Se, the presence of crystals will also increases optical scatter loss.

In this paper, a distilling method based on vapor evaporation plus deposition under vacuum condition was advanced with the aim of producing GGT glass with low impurity and high homogeneity. The results of purification, as well as optical loss spectra, were also investigated by using three different experimental conditions. These progresses appear as promising results in view of manufacturing high purity ChG glass containing Ga element. These glasses would also make preparations for the fabrication of optical fibers and planar waveguides.

Theory of vacuum distillation

In order to synthesize a GGT glass with low impurity level, it is necessary to remove impurities from raw materials. Vacuum distillation technique has attracted great attentions for its low cost and less pollution to our environment, as it drives high purity vapor flowing into target room from a raw material surface under vacuum. Besides, the boiling point of metal will decrease a lot under vacuum condition and that helps to speed up the distilling process.

Meanwhile, the efficiency of distillation is dependent on the maximum admissible temperature of container and the vapor pressure of raw material.

Generally, the vapor pressure varies among different metal or metal-oxide (such as impurity), therefore we can refine a certain metal according to the difference of vapor pressures between the metal and its impurities. The relationship between the vapor pressure of the metal and the temperature can be expressed by Clausius-Clapeyron equation [14,15]:

) ( 2 1 V V T L d d T p - = (1)
Where p is the vapor pressure of the metal, T is the temperature of the metal, L is the vaporizing latent heat of the metal. V 1 and V 2 represent the molar volume of gaseous metal and liquid metal, respectively. The value of (V 1 -V 2 ) is approximately of the molar volume of gaseous metal

(V 1 )
because V 1 is far larger than V 2 . Under low vapor pressure, Gas obeys ideal gas law:

V 1 =RT/p,
where R is a gaseous constant and equal to 4.575. Therefore, this equation can be rewritten as following equation:

2 T d R L p d T p ⋅ = (2)
The vaporizing latent heat (L) relates to the temperature of the metal: L=L 0 +aT+bT 2 +cT

D CT T B AT p + + + = - lg lg 1 (4)
Where A, B, C and D are four constants varying with different metals [START_REF] Dai | Fundamental theory and method of vacuum distillation[END_REF]. The vapor pressures of Ge, Ga, Te, Si and Fe at different temperatures are calculated based on equation ( 4) and are shown in Figure 1. Here,the critical P means the value of vapor pressure when distill starting, the critical T means the lowest requirements of the temperatures to reach the critical P, as it decided by the thermodynamic data of the metals or metal-oxides. As shown in Figure 1, it is clear that a high temperature of 1400 o C (1673K) is needed to vaporize and distill Ge and Ga at a vacuum of 10 -3 Pa in theory. In fact, a component containing Ge and Te will appear and the vapor pressure of Ge-containing compound will increase enormously so that Ge can be easily purified by distillation at a temperature of 1050 o C (1323K) [2], which is not the case for the Gacontaining glasses. As is known to all, quartz glass container can be used stably under 1050 o C(1323K), and the short-term maximum temperature can be up to 1450 o C (1723K). So it is needed to find a new way to fast vaporize metals and keep the stability of the quartz container at an ultimate temperature, meanwhile leave the oxides as residual (metallic oxides are usually more stable than the metals, such as Al 2 O 3 (boiling temperature is 3250 K), and Ga 2 O 3 (melting point is 2,173° C).

Glass preparation and purification

Appropriate amounts of high purity Ge (99.999%), Te (99.999%) and Ga (99.999%) were used as starting raw materials for glass synthesis. Three different experimental conditions (3 series) were adopted to prepare GGT glasses in this paper, as shown in Table I, and the details are illustrated in the followings:

Series A: the raw elements of 10 grams were loaded into two H-typed quartz tubes (Figure .   2). Different oxygenic getters were introduced into these two tubes: one (marked as G0) was doped with 500 ppm of Mg and another (marked as G1) with 500 ppm of Al. Both two tubes were sealed at position 1 after being evacuated down to about 2×10 -3 Pa. Next, a rapid heating furnace 2 (>1000 o C/min) was used to heat the mixtures in section A to 1400 o C and held for 10 minutes to guarantee that all the raw materials were distilled into section B, then the tubes were sealed at position 3. The oxide impurities (e.g. Al 2 O 3 , MgO) remained in section A because of their low vapor pressures. At last, the mixtures were melted at 900 o C using a rocking furnace and held for 18 hours before being lowered to 750 o C for quenching.

Series B: Two tubes (marked as G2, G3) both containing 10 g of raw materials and 500 ppm Al were prepared as series A before the temperatures of the furnaces were subsequently lowered to 600 o C (G2) and 900 o C (G3).

Series C: the raw elements of 10 grams were loaded into two H-typed quartz tubes.

Different contents of Al were introduced into these two tubes: one (marked as G4) was doped with 250 ppm of Al and another (marked as G5) with 400 ppm of Al. And the glass preparation process was the same as series A. Additional GGT glass (marked as G6) that hadn't been distilled was also prepared and its glass melting progress is the same as series A.

All seven tubes were quenched in water and annealed at the temperature of 160 o C for 5 hours before being cooled to room temperature slowly. The glass rods were then obtained by taking them out of the tubes. Glass rods were finally cut into disks and polished to a thickness of about 1 mm.

GGT glass and its optical loss

GGT glass characterizations

The thermal characteristics of the samples were measured by differential scanning calorimetry (DSC) in the temperature range of 50-350 o C at a heating rate of 10 o C/min. The glass transition temperature T g , the onset crystallization temperature T x and the differences ∆T=T x -T g for three glasses are reported in Table II. ∆T values of GGT glass samples are all over 100 o C, indicating that the GGT glass is stable against crystallization. A small improvement in the distilled glass samples is achieved comparing to the T x value of non-distilled GGT glass G6.

However, the purification process does not change the value of T g and ∆T as much as the variation of glass composition.

The Vis-NIR transmision spectra of samples were recorded in the range of 1600-2500 nm by using a PerkinElmer Lambda 950 UV-Vis-NIR spectrophotometer. The results are displayed in Figure 3, showing that the maximum transmittance of each glass sample varies with its thickness. However, the band-width of the transmission spectra of the seven glass samples are kept nearly the same, and there is no apparent absorption peak in this range because the absorption bands in ChGs caused by impurities are commonly located in the region of 2.5-20 µm.

Small variation in the cut off edge may be ascribed to the thickness variation of the glass samples in a certain extent.

Quantitative analysis was carried out by an Energy Dispersive Spectrometer (Tescan VEGA 3 SBH, Czech). Table III lists the compositions of the final glasses, the precision of the analysis, as well as the contents of the impurities in studied glass samples. It can be seen that the change of their compositions were not very noticeable. In addition, only two main impurities exist in the glasses. High carbon content dropped down obviously in the purified glasses. The contents of oxygen decreased from 0.91 wt. % to 0 followed the increasing of the added Al in series C. Here, the contents of the other impurities, such as Na, Si and so on, were too low to be detected.

Optical loss of GGT glass

The IR absorption spectra of glass samples were recorded in the range of 4000-400 cm -1 by using a Nicolet 380 Fourier Infrared spectrophotometer. To evaluate the optical loss, the absorbance of a same GGT glass rod with different thickness of about 4 mm was also measured and the optical loss was calculated by following equation:

) ( ) ( 10 ln 2 1 2 1 OD OD L L - × - = α ( 5
)
Where α is values of the optical loss, OD 1 and OD 2 are the absorbance of the GGT glass with a thickness of L 1 and L 2 , respectively (L 1 > L 2 ).

Figure 4 gives the optical losses of GGT glasses distilled with different oxygenic getters and non-distilled GGT glass (G6). Obviously, there is a broad absorption peak in 15-20 µm region caused by the impurities involving with Ga when the raw elements were not purified. The optical losses of distilled glasses are significantly lower than the glass without any treatment. Whereas,

500
+ → + + → + - - (6)
The relationship between optical losses and quenching temperature is illustrated in Figure 5.

It can be seen that the optical loss decreases with the increase of quenching temperature firstly, just as the comparison of G1 (750 o C) to G2 (600 o C). It can be explained that lower quenching temperature decreases the cooling rate which results in the formation of micro-crystals. Hence, the increase of quenching temperature reduces the amount of micro-crystals which is one of the sources for the scattering loss. Meanwhile, Higher quenching temperature than 750 can also increase the loss, just as the comparison of G3 (900 o C) to G1 (750 o C). It can be sourced from the inhomogeneity of the glass, as the quenching rate of outer part is quite different from that of inner part.

As shown in Figure 6, four glass samples distilled with different amounts of Al were prepared (the quenching temperatures of all glass samples are 750 o C). At least, 400 ppm Al rather than 250 ppm Al is essential to thoroughly eliminate the oxide impurities in the range of 15-20 µm. The lowest optical losses were very close to 0.042 dB/cm at 9 µm and 0.037 dB/cm at 12 µm.

Discussion

The GGT glasses with low content of oxygen were achieved by use of a combination of chemical and distillation methods. When raw materials of element were melted without any treatment of purification, there would be a broad absorption band in the range of 15-20 µm and the average optical loss was much higher than distilled GGT glasses. The low optical losses of distilled GGT glasses are due to the absence of water and oxide impurities as well as silica impurities in form of inclusions. At present, lowest optical losses of 0.042 dB/cm at 9 µm and 0.037 dB/cm at 12 µm are obtained, which are the lowest loss to the telluride chalcogenide glass nowadays. 750 o C is the optimized quenching temperature to preparing low loss GGT glass. Higher or lower quenching temperature could result in the increase of optical loss. 400 ppm wt. of Al is the minimum amount of oxygen getter to remove oxygen from the raw materials in our case.

The increase of optical losses in the short wavelength range is due to electronic transition.

The increase of optical losses in the long wavelength is due to intrinsic multi-phonon absorption [START_REF] Shiryaev | [END_REF]. These intrinsic absorptions can be reduced by modifying the glass composition.

As shown in equation ( 5), the optical losses of all glass samples depend on tested absorbance which would be influenced by the polishing level and glass optical homogeneity. In order to precisely estimate the optical losses of the investigated glasses, the dependence of the absorption coefficient on absorbance (OD) and the glass thickness (L) was expressed by the following equation:

aL R OD + - - = ⋅ ) 1 ln( 2 ) 10 ln( ( 7
)
Where R is the reflectivity of investigated glass. α value was the slope of the curve determined by plotting OD⋅ln(10) as a function of glass thickness L. Figure 7 shows the relationship between OD⋅ln(10) and L of glass G4 at two different wavelengths, all α values obtained from the curves are listed in Table IV. It can be seen that the values of OD⋅ln(10) and thickness L have a linear relationship. The minimal optical losses were 0.059 dB/cm at 9 µm and 0.053 dB/cm at 12 µm for the G0 sample. Additionally, we presume that two reflections always exist in equation ( 7), so the OD does not tend to zero when the glass thickness is 0.

Conclusions

A rapid heating furnace was adopted and the fast distillation method based on vapor evaporation plus deposition under vacuum condition proved to be effective in preparing high purified GGT glass samples. Then, the dependence of optical loss on the type of oxygenic getters and their contents and quenching temperature were investigated. The best result of optical loss of 0.037 dB/cm at 12 µm was obtained. The average optical losses of distilled glasses were far lower than the glass without purification process. Higher or lower quenching temperature could also result in optical loss. Reducing metal Al was much more functional to decrease the oxide content in the GGT glasses. Only with 400 ppm wt. of Al and vacuum fast distillation, it would be good enough to remove all oxide absorption bands, to expand the transmission spectrum and to flat the spectra without any obvious absorption peak in all the range of 8-20 µm.

In all, the results show that it is potential for developing a low-loss far-infrared fiber with the Gacontaining Te-based chalcogenide glasses, if that there is much more improvement of glass purification.

FIGURE CAPTIONS

Fig. 1 .Fig. 2 .

 12 Fig. 1. The vapor pressures of Ge, Ga, Te, Si and Fe at different temperatures

Fig. 3 .

 3 Fig. 3. The Vis-NIR transmission spectra of the glass samples.

Fig. 4 .

 4 Fig. 4. Optical losses of glass samples, G0: GGT glass distilled with 500 ppm Mg, G1: GGT

Fig. 5 .Fig. 6 .

 56 Fig. 5. Optical losses of glasses with different quenching temperatures (all glass samples were

Fig. 7 .

 7 Fig. 7. The relationship between OD⋅ln(10) and thickness L of glass G4 at two different

FIG. 1 .FIG. 3 .

 13 FIG. 1. The vapor pressures of Ge, Ga, Te, Si and Fe at different temperatures

FIG. 4 .

 4 FIG.4. Optical losses of glass samples, G0: GGT glass distilled with 500 ppm Mg, G1: GGT glass distilled with 500 ppm Al, G6: non-distilled GGT glass.

FIG. 5 .

 5 FIG.5. Optical losses of glasses with different quenching temperatures (all glass samples were distilled with 500 ppm Al, and the quenching temperature of G2 is 600 o C, G1 is 750 o C, G3 is 900 o C).

4

 4

  3

  ppm Mg is not enough for eliminating the oxide impurities as there is still strong absorption in 15-20 µm. While the oxide impurities were effectively removed after the same Al content being added, as that can be explained as the number of reducing valent state is 3 of Al, comparing 2 of Mg, just shown as equation 6.

	Al	2 3	O	2	AlO 3	/	2	e 3
	Mg	O	2		MgO		2	e

TABLE I

 I

Sample details of the GGT glasses prepared under different experimental conditions.

TABLE II

 II The thermal characterictics of studied glass samples.

TABLE III

 III Impurities content of the glass samples.

TABLE IV

 IV

Optical loss α of investigated glasses at two different wavelengths.

  FIG. 6. Optical losses of glass samples distilled with different content of Al.

	G6 8.67	0.32	5.7		0.22	44.08	2.21		6.28		1.03	0.91	0.23
	G4 11.74 G5 11.44 0..33 0.32	7.75 7.56	1	0.20 G6 G4 0.19	61.46 60.07	2.36 2.42		2.41 2.41		0.51 0.52	0.35 -	0.13 -
	0.1 Table IV Optical loss α of investigated glasses at two different wavelengths G5 G1 G1 11.61 0.34 6.08 0.22 58.47 2.78 3.14 Compositions α dB/cm (λ=9 µm) α dB/cm (λ=12 µm) G0 0.059±0.002 0.053±0.002 Optical loss(dB/cm) G1 0.063±0.005 0.060±0.006		0.76	-	-
	G2	0.072±0.006		0.067±0.005
	G3	0.01 0.125±0.025		0.125±0.024
	G4 G5	0.062±0.004 0.067±0.012	6	8 0.056±0.004 10 12 14 Wavelenth(µm) 0.063±0.012	16	18	20	22
	G6	0.183±0.019		0.178±0.018
				1.5	9 µm
					12 µm
				1.2
			OD⋅ln(10)	0.9
				0.6
				0	2	4	6	8		10
							L/mm
	FIG. 7. The relationship between OD⋅ln(10) and thickness L of glass G4 at two different wavelengths

Acknowledgments

This work was financially supported by the Natural Science Foundation of China (Grant Nos. 61377099 and 61177087), Scientific Research Fund of Zhejiang Provincial Education Department (R1101263), Natural Science Foundation of Ningbo (Grant No. 2013A610118), Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, P.R.C. Ningbo optoelectronic materials and devices creative team (2009B21007) , Scientific Research Foundation of Graduate School of Ningbo University and sponsored by K. C. Wong Magna Fund in Ningbo University.