S T Éphane

J Ér

Ôme Saracco

SUPERVISED AND UNSUPERVISED CLASSIFICATION USING MIXTURE MODELS

This chapter is dedicated to model-based supervised and unsupervised classification. Probability distributions are defined over possible labels as well as over the observations given the labels. To this end, the basic tools are the mixture models. This methodology yields a posterior distribution over the labels given the observations which allows to quantify the uncertainty of the classification. The role of Gaussian mixture models is emphasized leading to Linear Discriminant Analysis and Quadratic Discriminant Analysis methods. Some links with Fisher Discriminant Analysis and logistic regression are also established. The Expectation-Maximization algorithm is introduced and compared to the K-means clustering method. The methods are illustrated both on simulated datasets as well as on real datasets using the R software.

Introduction

Classification is an important field of statistical learning which is usually divided into two main tasks. First, in the supervised learning approach, the goal is to estimate a function from inputs x to outputs y given a training set {(x i , y i ), i = 1, . . . , n} where n is the number of examples. In most cases, x ∈ R p and x is referred to as the features or the covariates. If the response variable is real-valued, then the estimation of the link function is a regression problem, see Fraix-Burnet and Valls-Gabaud (2014) for application to astrophysics. If the response variable is categorical, it is rather denoted by z, and it takes its value in a finite set: z ∈ {1, . . . , K}. The estimation problem is called supervised classification, or discriminant analysis. Second, in the unsupervised learning approach, one only has {x i , i = 1, . . . , n}. In this case, the goal is not so well defined, it can be summarized as finding interesting patterns in the data. Unsupervised dimension reduction or unsupervised classification (also called clustering) can enter in this framework. We refer to [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF] and [START_REF] Hastie | Elements of Statistical Learning[END_REF] for accounts on statistical learning.

This chapter is dedicated to model-based supervised and unsupervised classification. We shall define a (prior) probability distribution p(z) over possible labels z as well as over the observations x given the labels z, denoted by p(x|z). To this end, the basic tools are the mixture models. This will allow us to build a posterior distribution p(z|x) over the labels given the observations and thus to quantify the uncertainty of the classification. Supervised classification is addressed in Section 2. The role of Gaussian mixture models is emphasized leading to Linear Discriminant Analysis and Quadratic Discriminant Analysis methods. Some links with Fisher Discriminant Analysis and logistic regression are also established. Section 3 is dedicated to unsupervised classification. The Expectation-Maximization algorithm is introduced and compared to the K-means clustering method. Finally, some extensions are presented in Section 4.

Supervised classification

Recall that the dataset is denoted by {(x 1 , z 1 ), . . . , (x n , z n )} where x i ∈ R p and z i ∈ {1, ..., K} for all i = 1, . . . , n. It is assumed that this dataset is already split into K groups C 1 , . . . , C K . The labels are thus supposed to be known and z i = k means x i ∈ C k for all i = 1, . . . , n and k = 1, . . . , K. The goal of supervised classification is to affect a new data point x ∈ R p to one of the K groups in an optimal way. Some further notations are introduced in the next subsubsection.

2.1. Notations. For all k = 1, . . . , K, let us consider:

• the number of observations in class C k : n k = ♯{i = 1, . . . , n s.t.

z i = k}, • the mean xk ∈ R p of class C k defined as xk = 1 n k zi=k x i ,
• the sample mean x ∈ R p which can be calculated using two equivalent formulas:

x = 1 n n i=1 x i = 1 n K k=1 n k xk ,
• the sample p × p covariance matrix associated with class C k defined as:

V k = 1 n k zi=k (x i -xk )(x i -xk ) t ,
• the within-class p × p covariance matrix which is defined as the mean of the previous covariance matrices:

W = 1 n K k=1 n k V k ,
• the between-class p × p covariance matrix which is defined as the covariance matrix of the class means:

B = 1 n K k=1 n k (x k -x)(x k -x) t ,
• the sample p × p covariance matrix which can be calculated using two equivalent formulas:

V = 1 n n i=1 (x i -x)(x i -x) t = B + W.
2.2. Fisher Discriminant Analysis. The goal of Fisher Discriminant Analysis (FDA) is to project the data in a subspace of dimension d ≪ p in order to visualize the classes structure. Let us denote by a 1 , . . . , a d the d axes in R p spanning the Fisher discriminant subspace.

2.2.1. Idea of the method in the case d = 1. In this simplified framework, the Fisher discriminant subspace is one dimensional, and is spanned by only one axis a 1 . The idea is find a 1 ∈ R p such that the projected observations a t 1 x i belonging to different classes are well-separated. In other words, the goal is to maximize the ratio between the between projected variance and the sample projected variance. Mathematically, the sample projected variance on an axis a ∈ R p is obtained as

var(a t x 1 , . . . , a t x n ) = 1 n n i=1 [(a t x i ) -(a t x)] 2 = 1 n n i=1 [a t (x i -x)] 2 = 1 n n i=1 a t (x i -x)(x i -x) t a = a t 1 n n i=1 (x i -x)(x i -x) t a = a t V a.
A similar formula holds for the between projected variance and therefore, the axis a 1 is obtained by solving the following optimization problem:

a 1 = argmax a∈R p a t Ba a t V a .
It is easily shown that the solution is closed-form: a 1 is the eigenvector of the matrix V -1 B associated with the largest eigenvalue. Remark. The dimension of the optimal projection subspace is at most K -1.

This property is a consequence of Rank(B) ≤ K -1 (since B is the covariance matrix of K observations) which implies Rank(V -1 B) ≤ K -1.

Remark. Both matrices V -1 B and W -1 B have the same (ordered) eigenvectors.

This fact can be proved as follows. Let a be an eigenvector of V -1 B associated with the eigenvalue λ. Thus V -1 Ba = λa which is equivalent to Ba = λV a. Recalling that

V = W + B, we have Ba = λ(B + W )a or equivalently W -1 Ba = (1 -λ) -1 a.
As a consequence of the two above remarks, when there are K = 2 classes, Fisher discriminant subspace is one dimensional and is spanned by

a 1 = W -1 (x 1 -x2 ),
since, in such a case, the eigenvector associated to the unique non-zero eigenvalue is closed form. [START_REF] Jolliffe | Principal component analysis[END_REF]. It aims at finding the linear subspace maximizing the sample projected variance. Similarly, it can be shown that it amounts to performing the eigendecomposition of V . PCA is usually an efficient way to reduce the dimension (van der Maaten et al., 2009) but it may be sub-optimal in the supervised classification framework since it does not take into account the label information. As a comparison, FDA can be considered as a supervised dimension reduction method whereas PCA is unsupervised. This difference is illustrated on the USPS digit database, a standard dataset for handwritten digit recognition. It can be downloaded at http://statweb.stanford.edu/ ~tibs/ElemStatLearn/data.html. Each of the n = 7291 observations is a 16×16 grey-level image obtained by scanning a handwritten digit. The images are encoded as vectors of dimension p = 16 × 16 = 256. The original dataset is made of K = 10 classes corresponding to the digits 0, 1, . . . , 9.

Fisher Discriminant Analysis versus Principal Component Analysis. Principal Component Analysis (PCA) is a dimension reduction technique, see for instance

Here, we focus on the three classes associated with the digits 3, 5 and 8 (see the top panel of Figure 1). The two-dimensional projections of the dataset obtained by PCA and FDA are compared on the bottom panel. The class structure is much clearer on the FDA projection than on the PCA one. 2.3. Mixture model.

2.3.1.

Definition. The observations x 1 , . . . , x n are supposed to be independent realizations from a random vector X ∈ R p while the labels z 1 , . . . , z n are assumed to be drawn from a discrete random variable Z ∈ {1, . . . , K}. The distribution of the random pair (X, Z) is built assuming that:

• Z follows a multinomial distribution with parameters π 1 , . . . , π K called mixing proportions, i.e. P(Z = k) = π k , k = 1, . . . , K. The mixing proportions should verify the constraints π k ∈ [0, 1] for all k = 1, . . . , K and

K k=1 π k = 1. • Given Z = k, X
has a density denoted by f (•, θ k ), where θ k represents the parameter (possibly multidimensional) of f . For the sake of simplicity, it is assumed here that the parametric form of f does not depend on the mixture component k. This assumption could be nevertheless easily be dropped.

From the law of total probability, one can show that the density of X is a linear combination of the densities associated with the K mixture components:

(1)

f (•) = K k=1 π k f (•, θ k ).
An illustration in dimension p = 1 is provided in Figure 2 in case of Gaussian densities. We refer to [START_REF] Mclachlan | Finite Mixture Models[END_REF] for a general account on mixture models.

2.3.2.

Sampling from a mixture. Sampling from a mixture model is an easy task which involves two steps:

• Pick a component k with probability π k , • Draw a sample from the density f (•, θ k ).
An illustration is given in Figure 3, where the previous algorithm is implemented in R code on the same mixture model as in Figure 2.

2.3.3.

A priori vs a posteriori probabilities. For all k = 1, . . . , K, the mixing proportion π k = P(Z = k) can be interpreted as the a priori probability that an observation x belongs to the class C k . Here, a priori means without using the observation x of the random variable X. At the opposite, the conditional probability P(Z = k|X = x) is called the a posteriori probability that an observation x belongs to C k . These two probabilities are linked through Bayes rule:

(2)

P(Z = k|X = x) = P(Z = k)f (x|Z = k)/f (x) = π k f (x, θ k )/f (x).
P(Z = k|X = x) = argmax k=1,...,K π k f (x, θ k )/f (x), from (2)
. Remarking that the denominator does not depend on k, Bayes decision rule can be simplified as

(3) δ ⋆ (x) = argmax k=1,...,K π k f (x, θ k ).
In practice, the parameters π k and θ k have to be estimated: πk = n k /n and θk is the maximum likelihood estimator computed on the class C k given by θk = argmax

θ zi=k f (x i , θ) = argmax θ zi=k log f (x i , θ) =: argmax θ L(θ, x 1 , . . . , x n ).
In the previous equation, L(θ, x 1 , . . . , x n ) denotes the log-likelihood which is usually more convenient to optimize than the likelihood. The estimated Bayes decision rule is then obtained by plugging the estimated parameters in (3):

(4) δ⋆ (x) = argmax k=1,...,K n k f (x, θk ).
2.3.5. Binary classification. In the particular case of K = 2 classes, the posterior probabilities P(Z = 1|X = x) and P(Z = 2|X = x) can be simplified. Since they sum to one, let us focus on the first one:

P(Z = 1|X = x) = π 1 f (x, θ 1 ) π 1 f (x, θ 1 ) + π 2 f (x, θ 2 ) = 1 1 + π2f (x,θ2) π1f (x,θ1) = Ψ(S(x)), (5)
where Ψ is called the logistic function defined by Ψ(t) = 1/(1 + exp(-t)) for all t ∈ R and where S is the so-called score defined for x ∈ R p by ( 6)

S(x) = log π 1 f (x, θ 1 ) π 2 f (x, θ 2 ) .
The previous result is usually stated as "the posterior probability is a logistic function of the score". A straightforward consequence is that Bayes decision rule can be rewritten as δ ⋆ (x) = 1 if and only if S(x) > 0.

2.4. Gaussian Mixture Model.

2.4.1. Quadratic Discriminant Analysis. In the Gaussian Mixture Model (GMM), it is further assumed that, for all k = 1, . . . , K, the density f (•, θ k ) is a Gaussian density with mean µ k and covariance matrix Σ k . We thus have

θ k = (µ k , Σ k ). Letting L k (• • • ) = -2 log(π k f (•, θ k ))
, Bayes decision rule (3) can be rewritten as

δ * (x) = argmin k=1,...,K L k (x)
where

L k (x) = (x -µ k ) t Σ -1 k (x -µ k ) + log(det Σ k ) -2 log(π k ) + C.
Here, and in the sequel, C is a constant which does not depend on k. This classification method is referred to as Quadratic Discriminant Analysis (QDA). Note that (x-µ k ) t Σ -1 k (x-µ k ) can be interpreted as the Mahalanobis distance between x and µ k . Bayes decision rule is, in this case, a quadratic function of the observation x.

Linear Discriminant Analysis.

To reduce the number of parameters to estimate, one may assume that all classes share the same covariance matrix Σ k = Σ for all k = 1, . . . , K. This amounts to supposing that the K classes have the same shape. This assumption yields

L k (x) = µ t k Σ -1 µ k -2µ t k Σ -1 x -2 log(π k ) + C
. This is the so-called Linear Discriminant Analysis (LDA) method where the associated Bayes decision rule is linear with respect to the observation x. Let us highlight, that, in high dimension (i.e. if p is large), inverting Σk or Σ may be an issue, see [START_REF] Bergé | HDclassif: An R package for model-based clustering and discriminant analysis of high-dimensional data[END_REF] or the chapter by C. Bouveyron in this book.

When several models are available (for instance LDA and QDA), a natural way to choose one of them is to use a cross-validation procedure to select the model that minimizes a sample based estimate of future miss-classification risk. See [START_REF] Bensmail | Regularized Gaussian discriminant analysis through eigenvalue decomposition[END_REF] for an application to the selection of parsimonious Gaussian models.

2.4.4. Binary Linear Discriminant Analysis. We consider the particular case where K = 2 and Σ 1 = Σ 2 = Σ. In such a situation, the score ( 6) is linear and is given by

S(x) = 1 2 (L 2 (x) -L 1 (x)) = x t Σ -1 (µ 1 -µ 2 ) - 1 2 (µ 1 + µ 2 ) t Σ -1 (µ 1 -µ 2 ) + log(π 2 /π 1 ). ( 7
)
Once the parameters are estimated, the classification rule becomes δ⋆ (x) = 1 if and only if

x t W -1 (x 1 -x2 ) > (x 1 + x2 ) t W -1 (x 1 -x2 ) + log(n 2 /n 1 ) x t a 1 > (x 1 + x2 ) t W -1 (x 1 -x2 ) + log(n 2 /n 1 ),
where a 1 is the Fisher discriminant axis, see Paragraph 2.2. It thus appears that Binary LDA reduces to comparing the projection x t a 1 of the data x to classify on the Fisher discriminant axis a 1 with a threshold (x 1 +x 2 ) t W -1 (x 1 -x 2 )+log(n 2 /n 1 ) depending on the geometry of the problem.

Binary logistic regression.

As previously mentioned, in case of binary classification (K = 2), the probability to affect x to the first class is P(Z = 1|X = x) = Ψ(S(x)), see [START_REF] Bouguila | Novel mixtures based on the Dirichlet distribution: application to data and image classification[END_REF]. If, moreover, it is assumed that Σ 1 = Σ 2 = Σ, then the score S(x) is a linear function of x, see [START_REF] Bergé | HDclassif: An R package for model-based clustering and discriminant analysis of high-dimensional data[END_REF]. This is the binary LDA method described above. Binary logistic regression directly assumes that there exist β 0 ∈ R and β ∈ R p such that P(Z = 1|X = x) = Ψ(β 0 + β t x) without any other hypothesis. The estimation of β 0 and β is performed by maximizing the conditional likelihood:

(8) zi=1 Ψ(β 0 + β t x i ) zi=2 (1 -Ψ(β 0 + β t x i )).
The advantage of binary logistic regression is to be potentially more general than binary LDA since it does not make any Gaussian assumption. The computation of the estimators is however more difficult since the maximization of (8) requires numerical procedures.

Unsupervised classification

Recall that the goal is to split a dataset x 1 , . . . , x n of n observations in R p into K homogeneous groups C 1 , . . . , C K . The labels are still denoted by z 1 , . . . , z n but are not observed. In a first time, the number K of clusters is supposed to be known. The choice of K is addressed in Paragraph 3.3.

3.1. K-means algorithm. Each cluster C k is represented by a vector µ k ∈ R p called prototype for all k = 1, . . . , K. The binary numbers r ik = I{z i = k}, i = 1, . . . , n, k = 1, . . . , K indicating the class membership of the observations are called responsibilities. It is assumed that each observation x i belongs to one and only one cluster so that K k=1 r ik = 1 for all i = 1, . . . , n. K-means algorithm translates the clustering problem as the computation of the vector of prototypes and responsibilities θ := (µ k , r ik ) i=1,...,n, k=1,...,K . To this end, the following optimization problem is introduced:

(9) min θ n i=1 k k=1 r ik x i -µ k 2
under the constraints: r ik ∈ {0, 1} and K ℓ=1 r iℓ = 1 for all i = 1, . . . , n, k = 1, . . . , K. Since this problem has no explicit solution, the principle of K-means algorithm is to perform an alternate minimization, see [START_REF] Hartigan | A K-means clustering algorithm[END_REF]:

• Minimization with respect to the responsibilities, assuming that the prototypes are known. The solution is given by: r ik = 1 if and only if µ k is the closest prototype of x i , i = 1, . . . , n, k = 1, . . . , K. This amounts to partitioning the observations according to the Voronoi diagram generated by the prototypes. • Minimization with respect to the prototypes, assuming that the responsibilities are known. The solution is given by: µ k is the mean of the x i affected to the cluster C k , that is

(10) µ k = n i=1 r ik x i n i=1 r ik ,
for all k = 1, . . . , K. In practice, it is recommended to standardize the data before running the algorithm. It has been proved that each iteration of K-means algorithm decreases the criterion to minimize [START_REF] Biernacki | Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models[END_REF]. The algorithm thus converges to a local minimum and the result may depend on the initialization. However, since the algorithm is usually very fast, it is possible to run it multiple times with different starting conditions.

K-means algorithm suffers from some drawbacks. First, the hard assignment of data points x i to clusters C k may be unstable: A small change of a data point can move it to another cluster. Second, the choice of the number of clusters K is difficult. In the following subsubsection, we shall work in the GMM framework. This will allow us to replace hard assignments by "soft" probabilistic assignments.

3.2.

Maximum likelihood in the GMM. In the unsupervised framework, both the model parameters θ k = (π k , µ k , Σ k ) and the labels z ik , i = 1, . . . , n, k = 1, . . . , K are unknown. Denoting the unknown (multidimensional) parameter by θ = (θ 1 , . . . , θ K ), the inference is still based on the log-likelihood

L(θ, x 1 , . . . , x n ) = n i=1 log K k=1 π k f (x i , µ k , Σ k ) .
Recall that f (•, µ, Σ) is the p-dimensional Gaussian density with mean µ and covariance matrix Σ. Since there is a sum in the logarithm, the maximum likelihood estimator of θ is not explicit. Let us however consider the gradient of the loglikelihood with respect to µ k , k = 1, . . . , K:

∇ µ k L = - n i=1 π k f (x i , µ k , Σ k ) K j=1 π j f (x i , µ j , Σ j ) Σ -1 k (x i -µ k ) = - n i=1 P(Z = k|X = x i )Σ -1 k (x i -µ k ),
in view of ( 1) and ( 2). Annulling the previous gradient yields, for all k = 1, . . . , K,

(11) μk = n i=1 P(Z = k|X = x i ) x i n i=1 P(Z = k|X = x i )
.

It appears that μk is a weighted mean of the observations. Let us precise that μk is not a proper estimator of µ k since the weights i.e. the posterior probabilities P(Z = k|X = x i ) are unknown. Comparing to the K-means formula [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF], the binary weights are replaced by real values in the unit interval. Similar calculations yield, for all k = 1, . . . , K:

(12) Σk = n i=1 P(Z = k|X = x i ) (x i -µ k )(x i -µ k ) t n i=1 P(Z = k|X = x i )
, with a similar interpretation. Using a Lagrange multiplier technique to take into account the constraint

K k=1 π k = 1 entails: (13) πk = 1 n n i=1 P(Z = k|X = x i ).
The intuitive idea of the Expectation-Maximization (EM) algorithm is to alternate the calculations ( 11)-( 13) with an update of the posterior probabilities according to ( 14)

P(Z = k|X = x i ) = π k f (x i , µ k , Σ k ) K j=1 π j f (x i , µ j , Σ j ) , see (1)
and ( 2). The EM algorithm is however based on a more general maximization principle and is not limited to Gaussian mixtures, see [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. In our considered framework, the algorithm can be summarized as follows.

EM algorithm.

• Initialization: Initial guess for the model parameters.

• E Step: Estimation of t ik := P(Z = k|X = x i ) using tik = πk f (x i , μk , Σk ) K j=1 πj f (x i , μj , Σj ) • M
Step: Maximization of log-likelihood yielding the previous formulas:

μk = n i=1 tik x i n i=1 tik , Σk = n i=1 tik (x i -μk )(x i -μk ) t n i=1 tik , πk = 1 n n i=1
tik .

• Repeat until convergence.

It can be shown that the EM algorithm increases the likelihood at each iteration. This property allows some monitoring of the convergence. In practice, the iterations are stopped when the increase of the log-likelihood is behind a small threshold. EM algorithm converges to a local maxima of the likelihood, the initialization is thus an important issue, addressed for instance in [START_REF] Biernacki | Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models[END_REF]. The most common practice is to initialize the EM algorithm with K-means clustering. Stochastic and classification versions of EM have been developed (G. Celeux and G. Govaert, 1992). Either the a posteriori probabilities t ik are used to randomly select the class belongings (random assignment), or are binarized (hard assignment). A simple implementation of the EM algorithm in R is provided in Figure 4. In this toy case, we limit ourselves to the situation already considered in Figure 2 and Figure 3 where K = 2 and p = 1. The algorithm is initialized with µ

(0) 1 = 0, µ (0) 2 = 1, π (0) 1 = π (0) 2 = 1/2 and σ (0) 1 = σ (0) 2
are set to the sample standarddeviation. The number of iterations is fixed by the user. An example of result is depicted in Figure 5. The EM algorithm has been run with 100 iterations on a sample simulated from the model considered in Figure 2 and Figure 3. The estimated parameters are π1 = 0.48, π2 = 0.52, μ1 = 0.46, μ2 = 1.98, σ2 1 = 2.94 and σ2 2 = 0.82. The true and estimated densities look very similar. Note that the results may depend on the simulated data.

Links with K-means algorithm.

Let us consider the GMM, with common and spherical covariance matrices i.e. Σ k = εI p for all k = 1, . . . , K. Replacing in ( 14), the a posteriori probabilities are given by

t ik = π k exp -1 2ε x i -µ k 2 K j=1 π j exp -1 2ε x i -µ j 2 = 1 1 + j =k πj π k exp 1 2ε ( x i -µ k 2 -x i -µ j 2 )
.

Letting ε → 0, t ik becomes a binary number: t ik = I{ x i -µ k < x i -µ j , for all j = k}, and we find back the K-means algorithm. K-means can thus be interpreted as a particular case of EM. This suggests that K-means is well adapted to mixtures where all the clusters share a common spherical shape. As an illustration, let us consider the clustering of the Old Faithful geyser dataset. Old Faithful is a geyser located in Yellowstone National Park (USA). It is one of the most predictable geographical features on Earth, erupting every 40 to 100 minutes. This dataset can be downloaded at http://www.stat.cmu. edu/ ~larry/all-of-statistics/=data/faithful.dat and is also included in the mclust package, see [START_REF] Fraley | Enhanced software for model-based clustering, density estimation, and discriminant analysis: MCLUST[END_REF]. This dataset includes n = 272 observations described by p = 2 variables (duration of the eruption, waiting time between eruptions). In this subsubsection, the number of classes is arbitrarily set to K = 2. In Figure 6, it appears that the clustering obtained with the K-means model (equal and diagonal covariance matrices) and the clustering with the QDA model (free covariance matrices) are identical.

3.3.

Selecting the number of clusters. Various criteria have been introduced to measure the suitability of a model by balancing its goodness of fit and its complexity. Here, we focus on criteria based on a penalization of the log-likelihood (computed for the optimal parameter):

IC = L( θ, x 1 , . . . , x n ) -ν(K)ϕ(n)
where θ is the maximum likelihood estimator, ν(K) is the number of (free) parameters in the model and ϕ(n) is a function of n. The most famous examples are the Akaike Information Criteria (AIC), see [START_REF] Akaike | A new look at the statistical model identification[END_REF], where ϕ(n) = 1 and the Bayesian Information Criteria (BIC), see [START_REF] Schwarz | Estimating the dimension of a model[END_REF] where ϕ(n) = log(n)/2. Further details and theoretical developments on AIC and BIC can be found respectively in [START_REF] Aitkin | Estimation and hypothesis testing in finite mixture models[END_REF] and [START_REF] Kass | Bayes factors[END_REF]. In practice, it has been remarked that, usually, BIC works better than AIC on mixtures [START_REF] Bouveyron | Intrinsic dimension estimation by maximum likelihood in isotropic probabilistic PCA[END_REF] but none of them takes into account the classification purpose. Alternative criteria have been introduced, such as ICL (Integrated Completed Likelihood), see [START_REF] Biernacki | Assessing a mixture model for clustering with the integrated completed likelihood[END_REF], to overcome this limitation. The principle of ICL is to introduce an additional penalization on overlapping classes in BIC.

As an illustrated, let us consider the clustering of the Old Faithful geyser dataset. In Figure 6, the clustering was achieved assuming K = 2. Here, we use the BIC criterion to select K in the set {1, . . . , 5} and to choose between common covariance matrices (LDA model) or free covariance matrices (QDA model). It appears in Figure 7 that the largest value of BIC is obtained with K = 3 components associated with the LDA model. The corresponding clustering is also depicted in Figure 7 on a visualization space different from the original one (Figure 6), see the package documentation. Let us highlight that the decision boundaries are linear, see Paragraph 2.4.

Conclusion, recent developments

As a conclusion, mixture models are an efficient tool for both supervised and unsupervised classifications. They offer a nice theoretical framework for model selection and for computing classification probabilities. They also encompass geometric methods as particular cases. From the practical point of view, we have seen that they are naturally multiclass and that efficient algorithms are available. It is also possible to deal with missing data thanks to the EM algorithm.

In this chapter, we focused on Gaussian mixture models, but a lot of other models are available in the statistical literature. First, in case of discrete data, multinomial models can be used, see for instance [START_REF] Bouguila | Novel mixtures based on the Dirichlet distribution: application to data and image classification[END_REF], [START_REF] Celeux | Clustering criteria for discrete data and latent class models[END_REF] or [START_REF] Goldstein | Discrete discriminant analysis[END_REF]. Second, to tackle the case of heavytailed or asymmetric data, several extensions of Gaussian models have been recently introduced: Skew normal distribution [START_REF] Vilca | Multivariate skew-normal generalized hyperbolic distribution and its properties[END_REF] [START_REF] Wraith | Location and scale mixtures of Gaussians with flexible tail behaviour: Properties, inference and application to multivariate clustering[END_REF]. Finally, an extension of the Gaussian mixture model to non quantitative data has been proposed by [START_REF] Bouveyron | Kernel discriminant analysis and clustering with parsimonious Gaussian process models[END_REF]. The introduction of a kernel function permits to deal with various kind of data including categorical data, functional data or networks. # m i x t u r e p a r a m e t e r s p i <-0 . 4 mu1 <-0 ; sigma1 <-1 . 5 mu2 <-2 ; sigma2 <-1 # v i s u a l i z a t i o n p a r a m e t e r s l e f t <--4.5 ; r i g h t <-6 ; top <-0 . 5 grd <-seq ( from=l e f t , t o=r i g h t , length =100) # p l o t s plot ( grd , dnorm( grd , mean=mu1 , sd=sigma1 ) , typ e=" l " , c o l =2 , xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , l t y=" dashed " , lwd=4) par (new=TRUE) plot ( grd , dnorm( grd , mean=mu2 , sd=sigma2 ) , typ e=" l " , c o l =1 , xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , l t y=" d o t t e d " , lwd=4) par (new=TRUE) plot ( grd , p i * dnorm( grd , mean=mu1 , sd=sigma1)+

(1-p i ) * dnorm( grd , mean=mu2 , sd=sigma2 ) , typ e=" l " , c o l =4 , xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , lwd=2) Figure 2. Top: Density of a GMM with K = 2 components and p = 1 variable. The parameters are given by µ 1 = 0, µ 2 = 2, σ 1 = 1.5, σ 2 = 2, π 1 = π and π 2 = 1 -π. From left to right, the proportion π is varying in {0.4, 0.6, 0.8}. Red dashed curve:

f (•, µ 1 , σ 2 1 ), Black dotted curve: f (•, µ 2 , σ 2
2 ), Blue solid curve: density of the mixture. Bottom: The corresponding R code for π = 0.4. # v i s u a l i z a t i o n p a r a m e t e r s l e f t <--4.5 ; r i g h t <-6 ; top <-0 . 4 grd <-seq ( from=l e f t , t o=r i g h t , length =100) # sample s i z e n <-1000 # g e n e r a t e a sample from t h e m i x t u r e g e n e r a t e d . smple

<-rep ( 0 , n ) f o r ( i i n 1 : n ) { aux <-runif ( 1 ,min=0 ,max=1) i f ( aux<p i ) { # s i m u l a t e from component 1 g e n e r a t e d . smple [ i ] <-rnorm ( 1 ,mean=mu1 , sd=sigma1
) } e l s e { # s i m u l a t e from component 2 g e n e r a t e d . smple [ i ] <-rnorm ( 1 ,mean=mu2 , sd=sigma2 ) } } # h i s t o g r a m o f t h e sample and t r u e d e n s i t y o f t h e m i x t u r e h i s t ( g e n e r a t e d . smple , f r e q=FALSE, xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , main=" " ) par (new=TRUE) plot ( grd , p i * dnorm( grd , mean=mu1 , sd=sigma1)+

(1-p i ) * dnorm( grd , mean=mu2 , sd=sigma2 ) , typ e=" l " , c o l =4 , xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , lwd=2) The parameters are given by µ

1 = 0, µ 2 = 2, σ 1 = 1.5, σ 2 = 2, π 1 = π and π 2 = 1 -π.
Here, the proportion is fixed to π = 0.4. Bottom: The corresponding R code. # run t h e EM a l g o r i t h m w i t h 100 i t e r a t i o n s . r e s <-EM( g e n e r a t e d . smple , nb . i t e r =100) # v i s u a l i z a t i o n p a r a m e t e r s l e f t <--4.5 ; r i g h t <-6 ; top <-0 . 5 grd <-seq ( from=l e f t , t o=r i g h t , length =100) # p l o t s plot ( grd , dnorm( grd , mean=r e s $mu [START_REF] Akaike | A new look at the statistical model identification[END_REF] , sd=sqrt ( r e s $ v a r i [ 1 ] ) ) , typ e=" l " , c o l =2 , xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , l t y=" dashed " , lwd=4) par (new=TRUE) plot ( grd , dnorm( grd , mean=r e s $mu [START_REF] Aitkin | Estimation and hypothesis testing in finite mixture models[END_REF] , sd=sqrt ( r e s $ v a r i [START_REF] Aitkin | Estimation and hypothesis testing in finite mixture models[END_REF] ) ) , typ e=" l " , c o l =1 , xlim=c ( l e f t , r i g h t ) , ylim=c ( 0 , top ) , x l a b=" " , y l a b=" " , l t y=" d o t t e d " , lwd=4) par (new=TRUE) plot ( grd , r e s $prp [START_REF] Akaike | A new look at the statistical model identification[END_REF] * dnorm( grd , mean=r e s $mu [START_REF] Akaike | A new look at the statistical model identification[END_REF] ,

sd=sqrt ( r e s $ v a r i [START_REF] Akaike | A new look at the statistical model identification[END_REF] ) ) +r e s $prp [START_REF] Aitkin | Estimation and hypothesis testing in finite mixture models[END_REF] * dnorm( grd , mean=r e s $mu [START_REF] Aitkin | Estimation and hypothesis testing in finite mixture models[END_REF] , sd=sqrt ( r e s $ v a r i [START_REF] Aitkin | Estimation and hypothesis testing in finite mixture models[END_REF] ) ) , typ e =" l " , c o l =4 , xlim=c ( l e f t , r i g h t ) , ylim =c ( 0 , top ) , x l a b=" " , y l a b=" " , lwd=2)

Figure 5. Top left (reproduced from Figure 2): Density of a GMM with K = 2 components and p = 1 variable. The parameters are given by µ 1 = 0, µ 2 = 2, σ 1 = 1.5, σ 2 = 2, π 1 = π and π 2 = 1 -π with π = 0.4. Red dashed curve: f (•, µ 1 , σ 2 1 ), Black dotted curve: f (•, µ 2 , σ 2 2 ), Blue solid curve: density of the mixture. Top right: Estimated densities with the EM algorithm (Figure 4) on the simulated sample (Figure 3). Bottom: The corresponding R code for plotting the top right figure. # c l u s t e r i n g w i t h 2 g r o u p s and K-means model r e s 1 <-Mclust ( f a i t h f u l ,G=2 ,modelNames="EEI" ) # p l o t t h e c l u s t e r i n g plot ( r e s 1 , what=" c l a s s i f i c a t i o n " ) # c l u s t e r i n g w i t h 2 g r o u p s and QDA r e s 2 < -Mclust ( f a i t h f u l ,G=2 ,modelNames="VVV" ) # p l o t t h e c l u s t e r i n g plot ( r e s 2 , what=" c l a s s i f i c a t i o n " )

Figure 1 .

 1 Figure 1. Top: A sample from the USPS dataset. Bottom: Twodimensional projections (left: PCA axes, right: FDA axes).

2. 3 . 4 .

 34 Bayes decision rule. The aim of supervised classification is to build a decision rule i.e. a function δ : R p → {1, . . . , K} which affects a label k ∈ {1, . . . , K} to each observation x ∈ R p . It is possible to show that the rule which minimizes the probability of miss-classification is Bayes decision rule given by δ ⋆ (x) = argmax k=1...,K

2. 4 . 3 .

 43 GMM in practice. The estimation of the parameters is simple. We still have πk = n k /n and the maximum likelihood estimators are closed-form: μk = xk is the sample mean of C k , Σk = V k is the sample covariance matrix of C k and Σ = n/(n-K)W where W is the within-class covariance matrix, see Paragraph 2.1.

Figure 3 .

 3 Figure 3. Top: Density of a GMM with K = 2 components and p = 1 variable (blue) superimposed to the histogram of a dataset of n = 1000 observations simulated from the same model (black). The parameters are given byµ 1 = 0, µ 2 = 2, σ 1 = 1.5, σ 2 = 2, π 1 = π and π 2 = 1 -π.Here, the proportion is fixed to π = 0.4. Bottom: The corresponding R code.

Figure 4 .

 4 Figure 4. EM algorithm for GMM coded in R in the onedimensional case (p = 1) and for two clusters (K = 2).

  s t a l l and l o a d t h e m c l u s t p a c k a g e i n s t a l l . packages ( " m c l u s t " ) l i b r a r y ( m c l u s t )

Figure 6 .Figure 7 .

 67 Figure 6. Clustering of the Old Faithful geyser dataset. Top: results obtained with diagonal and equal covariance matrices (Kmeans model encoded as EEI in mclust). Center: results obtained with free covariance matrices (referred to as QDA in the supervised framework and encoded as VVV in mclust). The density level sets are depicted in grey. Bottom: The corresponding R code.

  , t-distributions (Andrews and McNicholas, 2012 or Forbes and Wraith, 2014), asymmetric Laplace distribution (Franczak et al., 2014) and skew t-distributions (Lee and McLachlan, 2013 or


R Omar Chavez-Garcia
email: ricardo.chavez-garcia@imag.fr

Olivier Aycard
email: oliver.aycard@imag.fr

Multiple Sensor Fusion and Classification for Moving Object Detection and Tracking

Keywords: Intelligent vehicles, Sensor fusion, Classification algorithms, Vehicle detection, Vehicle Safety Preprocessing SLAM Environment Model Moving Object Detection Tracking DATMO Object Classification

The accurate detection and classification of moving objects is a critical aspect of Advanced Driver Assistance Systems (ADAS). We believe that by including the objects classification from multiple sensors detections as a key component of the object's representation and the perception process, we can improve the perceived model of the environment. First, we define a composite object representation to include class information in the core object's description. Second, we propose a complete perception fusion architecture based on the Evidential framework to solve the Detection and Tracking of Moving Objects (DATMO) problem by integrating the composite representation and uncertainty management. Finally, we integrate our fusion approach in a real-time application inside a vehicle demonstrator from the interactIVe IP European project which includes three main sensors: radar, lidar and camera. We test our fusion approach using real data from different driving scenarios and focusing on four objects of interest: pedestrian, bike, car and truck.

I. INTRODUCTION

I NTELLIGENT vehicles have moved from being a robotic application of tomorrow to a current area of extensive research and development. The most striking characteristic of an intelligent vehicle system is that it has to operate in increasingly unstructured environments, which are inherently uncertain and dynamic.

ADAS help drivers to perform complex driving tasks to avoid dangerous situations. Assistance tasks include: warning messages in dangerous driving situations (e.g., possible collisions), activation of safety devices to mitigate imminent collisions, autonomous manoeuvres to avoid obstacles, and attention-less driver warnings.

Perceiving the environment involves the selection of different sensors to obtain a detailed description of the environment and an accurate identification of the objects of interest. Vehicle perception is composed of two main tasks: simultaneous localization and mapping (SLAM) which generates a map of the environment while simultaneously localizing the vehicle within the map given all the measurements from sensors; and DATMO which detects and tracks the moving objects surrounding the Figure 1. General architecture of the perception task and its two main components: SLAM and DATMO. Perception provides a model of the environment usually composed by the vehicle's location, map of static objects, and a list of moving objects.

Management of incomplete information is an important requirement for perception systems. Incomplete information can be originated from sensor-related reasons, such as calibration issues, hardware malfunctions, uncertain detections and asynchronous scans; or from scene perturbations, like occlusions, weather issues and object shifting. The tracking process assumes that its inputs correspond uniquely to moving objects, and then focus on data association and tracking problems. However, in most of the real outdoor scenarios, these inputs include non-moving detections, such as noisy detections or static objects. Correctly detecting moving objects is a critical aspect of a moving object tracking system. Usually, many sensors are part of such systems.

Knowing the class of objects surrounding the egovehicle provides a better understanding of driving situations. Classification is seen as a separate task within the DATMO task or as an aggregate information for the final perception output [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF], [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF]. Classification can help to enrich the detection stage by including information from different sensor views of the environment, e.g. impact points provided by lidar and image patches provided by camera. Evidence about the class of objects can provide hints to discriminate, confirm and question data associations. Moreover, knowing the class of a moving object benefits the motion model learning and tracking. We believe that classification information about objects of interest gathered from different sensors at early stages can improve their detection and tracking, by reducing false positive detections and mis-classifications [START_REF] Wang | Simultaneous localization, mapping and moving object tracking[END_REF], [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF].

Regarding the state of the art approaches, we assume the SLAM stage as a solved task, and focus on the detection, classification and tracking of moving objects. Precisely, we include object's class as the key compo-nent of an Evidential fusion approach that includes uncertainty management from sensor detections. The goal is to improve the results of the perception task, i.e. a more reliable list of moving objects of interest represented by their dynamic state and appearance information. Therefore, we address the problems of sensor data association, sensor fusion for object detection, and tracking. We assume that a richer list of tracked objects can improve future stages of an ADAS and enhance the final application.

The rest of this paper is organized as follows. Section II reviews the related works. Section III introduces the concepts behind the Evidential framework. Sections IV and V describe the vehicle demonstrator and the software architecture of our real vehicle application inside the interactIVe project. Section VI describes our proposed strategies to extract classification information from the different sensors. In Section VIII, we present our fusion approach at detection level, and the tracking of moving objects. Experimental results are presented in Section IX. Finally, conclusion and perspectives are presented in Section X.

II. RELATED WORK

Fig. 2 shows the different fusion levels inside a perception system. Whilst low level fusion is performed within SLAM component, detection and track level fusions are performed within DATMO component. At detection level, fusion is performed between lists of moving object detections provided by individual sensors. At track level, lists tracks from individual sensor modules are fused to produce the final list of tracks. Promising SLAM results obtained in [START_REF] Wang | Simultaneous localization, mapping and moving object tracking[END_REF], [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF] and [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF] motivated our focus on the DATMO component. Whilst Vu [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF] and Wang [START_REF] Wang | Simultaneous localization, mapping and moving object tracking[END_REF] use an almost deterministic approach to perform the association in tracking, we use an evidential approach based on mass distributions over the set of different class hypotheses.

Low Level Fusion

Track Level Fusion

Detection Level Fusion

Raw

In order to narrow the vast variety of related works, we focus on the fusion methods inside DATMO that use lidar, camera and radar sensors. This decision comes from our sensor set-up described in Section IV.

Multi-sensor fusion at track level requires a list of updated tracks from each sensor. Then, the fusion process must get a combined list of tracks. This process has to solve the association problem between lists of tracks and implement a mechanism to combine the related objects. By using an effective fusion strategy at this level, false tracks can be reduced. Usually, this level is characterized by including classification information as complementary to the final output [START_REF] Mertz | Moving Object Detection with Laser Scanners[END_REF], [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF], [START_REF] Fayad | Detection and Recognition confidences update in a multi-sensor pedestrian tracking system[END_REF].

Fusion at detection level focus on gathering and combining early data from sensor detections to reduce the number of mis-detections that can lead to false tracks. Several works focus on data redundancy from active and passive sensors, and follow physical or learning constrains to increase the certainty of object detection. These works do not include all the available kinetic and appearance information [START_REF] Perrollaz | Long Range Obstacle Detection Using Laser Scanner and Stereovision[END_REF], [START_REF] Labayrade | Obstacle Detection Based on Fusion Between Stereovision and 2D Laser Scanner[END_REF]. Moreover, at this level, appearance information from sensor measurements is not considered as important as the kinetic data to discriminate moving and static objects [START_REF] Skutek | A precrash system based on sensor data fusion of laser scanner and short range radars[END_REF].

When classification is considered as an independent module inside the perception solution, this is often implemented as a single-class (e.g., only classifies pedestrians) or single-sensor based classification process [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF], [START_REF] Fayad | Detection and Recognition confidences update in a multi-sensor pedestrian tracking system[END_REF]. This excludes valuable discriminative data from multiple sensor views that can generate multi-class modules. Research perspectives point-out the improvement of the data association and tracking tasks as a direct enhancement when classification information is managed at early levels of perception [START_REF] Fayad | Detection and Recognition confidences update in a multi-sensor pedestrian tracking system[END_REF], [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF], [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF].

The most common approaches for multi-sensor fusion are based on probabilistic methods [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF], [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF]. However, methods based on the Evidential framework proposed an alternative not only to multi-sensor fusion but to many modules of vehicle perception [START_REF] Labayrade | Obstacle Detection Based on Fusion Between Stereovision and 2D Laser Scanner[END_REF], [START_REF] Fayad | Detection and Recognition confidences update in a multi-sensor pedestrian tracking system[END_REF], [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF]. These methods highlight the importance of incomplete and imprecise information which is not ussually present in the probabilistic approaches.

An advantage of our fusion approach at the detection level is that the description of the objects can be enhanced by adding knowledge from different sensor sources. For example, lidar data can give a good estimation of the distance to the object and its visible size. In addition, classification information, usually obtained from camera images, may allow to make assumptions about the class of detected object. An early enrichment of objects' description could allow the reduction of the number of false detections and to involve classification as a key element rather than only an add-on to the perception output.

III. EVIDENTIAL FRAMEWORK

The Evidential framework is a generalization of the Bayesian framework of subjective probability [START_REF] Smets | Data fusion in the transferable belief model[END_REF]. Evidential theory (ET) allows us to have degrees of belief for a related question according to the available evidence. ET represents the world in a set of mutually exclusive propositions known as the frame of discernment (Ω). It uses belief functions to distribute the evidence about the propositions over 2 Ω . The distribution of mass beliefs is done by the function m : 2 Ω → [0, 1] , also known as Basic Belief Assignment (BBA):

m(∅) = 0, ∑ A⊆Ω m(A) = 1.
(1)

Yager's rule combines two sources of evidence while avoiding counter-intuitive results, which are present when there is a considerable degree of conflict (m(∅)) [START_REF] Yager | O the Relationship of Methods og Aggregating Evidence in Expert Systems[END_REF]. In this rule, the conflict value is distributed among all the elements of the frame of discernment rather than only the elements with intersections of the combining masses:

m(A) = ∑ X i ∩Y j =A m 1 (X i )m 2 (Y j ), A = ∅, A = Ω, m(Ω) = ∑ X i ∩Y j =Ω m 1 (X i )m 2 (Y j )+ K ∑ X i ∩Y j =∅ m 1 (X i )m 2 (Y i ) . (2)
A. Evidential Theory for Vehicle perception ET has the ability to represent incomplete evidence, total ignorance and the lack of a need for a priori probabilities. We can encode implicit knowledge in the definition of the structure of the frame of discernment. In addition, discounting factors are an important mechanism to integrate the reliability of the sources of evidence, such as sensor performance. Moreover, combination rules are useful tools that integrate information from different bodies of evidence. Late stages of intelligent systems, such as reasoning & decision, can integrate evidence distributions into the decision making process [START_REF] Smets | Data fusion in the transferable belief model[END_REF].

When the number of hypotheses is large, ET becomes less computationally tractable because the belief is distributed over the power set of all the hypotheses, 2 Ω . However, the application domain may allow to make assumptions to transform Ω into a reduced version of the set of possible hypotheses.

IV. VEHICLE DEMONSTRATOR

We used the CRF (Fiat Research Center) demonstrator, from the the interactIVe European project, to obtain datasets from different driving scenarios. In order to accomplish the Continuous Support functionalities, the Lancia Delta car (see Fig. 3) is equipped with processing units, driver interaction components, and the following front-facing set of sensors: TRW TCAM+ camera gathers B&W images and has a FOV of ±21 • ; TRW AC100 medium range radar provides information about moving targets. It has a detection range up to 150m, velocity range up to 250kph, FOV of ±12 • (close range) or ±8 • (medium range), and angular accuracy of 0.5 • ; and an IBEO Lux laser scanner provides a 2D list of impact points, it has a range up to 200m with an angular and distance resolution of 0.125 • and 4cm respectively, and a FOV of 110 • .

V. SOFTWARE ARCHITECTURE

Our contribution insde the interactIVe project takes place at the Perception System (PS) that aims at improving the efficiency and quality of sensor data fusion, focusing on object detection and classification. In the PS, multiple functions are developed for continuous driver support, and also for executing active interventions for collision avoidance and collision mitigation.

Fig. 4 shows the schematic of our proposed PS, and the interaction between the detection and classification modules. The PS aims at detecting, classifying and tracking a set of moving objects of interest that may appear in front of the vehicle. The inputs of the fusion module are three lists of detected objects from three sensors: lidar, radar and camera. Each object is represented by its position, size and an evidence distribution of class hypotheses. Class information is obtained from the shape, relative speed and visual appearance of the detections. Lidar and radar data are used to perform moving object detection and, in cooperation with image data they extract object classification. Three list of composite object descriptions are taken by our fusion approach and delivered to our tracking algorithm. The final output of the fusion method comprises a fused list of object detections that will be used for the tracking module to estimate the moving object states and deliver the final output of our DATMO solution.

Radar

VI. MOVING OBJECT DETECTION

Here, we review the moving object detection methods for each sensor. In Section VII, we describe the process for object classification.

A. LIDAR processing

We consider the LIDAR (LIght Detection And Ranging) scanner as the main sensor in our configuration due to the its high resolution and accuracy to detect obstacles. In addition, it powers the SLAM component of our perception solution. The main goal of the lidar processing is to get precise measurements of the shape of the moving obstacles in front of the vehicle.

1) SLAM component solution: Although our main contributions are focused on the DATMO component, we solve the SLAM component in order to obtain the map and the vehicleś localization. Following the idea proposed in [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF], we employ lidar data (z 1:t ) for populating a two-dimensional Bayesian occupancy grid map. Each cell in the map M is associated with a measurement indicating the probability that the cell is occupied or not by an obstacle. Vehicle's location is found by a Maximum Likelihood approach. It consists of finding the best vehicle tracks estimates (ω * ) according to a shape model (P(ω|z 1:t )), prior model (P(ω)) and likelihood model (P(z 1:t |ω)) (Equation 3). Afterwards, this method uses the pose estimate and the latest sensor measurements to update the grid [START_REF] Chavez-Garcia | Fusion at detection level for frontal object perception[END_REF].

ω * = arg max ω∈Ω P(ω|z 1:t ), for P(ω|z 1:t ) ∝ P(w)P(z 1:t |ω) (3)
2) LIDAR-based Detection: As described [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF], [START_REF] Chavez-Garcia | Fusion at detection level for frontal object perception[END_REF], we focus on identifying the inconsistencies between free and occupied cells within the grid map M while incrementally building such map. If an occupied measurement is detected on a location previously set as free, then it belongs to a moving object. If a free measurement is observed on a location previously occupied then it probably belongs to a static object.

Using a distance-based clustering process we identify clouds of cells that could belong to moving objects. This process provides information about the visible shape of the possible moving object, an estimation of its size, and the distance to the object. Fig. 5 shows an example of the evolution of the lidar-based moving object detection process. Measurements detected as parts of a moving object are not used to update the map in SLAM.

B. Camera images

In order to extract information regarding the visual appearance of the objects from camera images, we have to be able to represent these objects using visual features.

1) Visual representation: The Histograms of Oriented Gradients (HOG) descriptor has shown promising results in vehicle and pedestrian detection [START_REF] Dollár | Pedestrian detection: an evaluation of the state of the art[END_REF]. We decided to take this descriptor as the core of our vehicle and pedestrian visual representation. The goal of object representation is to generate visual descriptors of areas of the image to be used in future stages to determine whether these areas contain an object of interest or not.

We propose sparse version of HOG descriptor (S-HOG) that focuses on specific areas of an image patch. This allows us to reduce the common high-dimensional HOG descriptor [START_REF] Chavez-Garcia | Fusion at detection level for frontal object perception[END_REF]. Fig. 6 illustrates some of the blocks we have selected to generate the descriptors for different object classes: pedestrian, bike, car and truck. These blocks correspond to meaningful regions of the object (e.g., head, shoulder and legs for pedestrians). To accelerate S-HOG feature computation, we followed an integral image scheme [START_REF] Viola | Robust real-time object detection[END_REF]. 2) Object classification: Due to performance constraints, we did not implement a visual-based moving object detection. We used the regions of interest (ROI) provided by lidar detection to focus on specific regions of the image.For each ROI, visual features are extracted, and a classifier is applied to decide if an object of interest is inside the ROI. The choice of the classifier has a substantial impact on the resulting speed and quality. We implemented a boosting-based learning algorithm, discrete Adaboost [START_REF] Friedman | Additive logistic regression: A statistical view of boosting[END_REF]. It combines many weak classifiers to form a powerful one, where weak classifiers are only required to perform better than chance.

For each class of interest (pedestrian, bike, car, truck), a binary classifier was trained to identify object (positive) and non-object (negative) patches. For the off-line training stage, positive images were collected from public (such as the Daimler dataset) and manually labelled datasets containing objects of interest from different object's viewpoints (frontal, rear, profile) [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF].

Off-line classifiers are used by the on-line object classification stage in a sliding-window scheme. Fig. 7 shows examples of the pedestrian and car detection results (green and red boxes respectively) before merging into the final objects. We estimate the confidence of object classification for each possible object. Generally, the greater the number of positive areas (containing an object of interest), the higher the confidence that the object belongs to that specific class.

C. Radar targets

The radar sensor uses a built-in mechanism to detect moving obstacles (targets), specially those with a crosssection similar to a car. The list of n targets is delivered as input to the perception approach. Each element of the list includes the range, azimuth and relative speed of the detected target. As the sensor will produce a return for each object with a significant radar cross section, targets may correspond to static objects or other moving obstacles, producing false positives. In a similar way, weak objects like pedestrians can not always be detected, consequently producing mis-detections. Due to different dyanmics defining the objects of interest, we track every target using and Interactive Multiple Model (IMM) represented by constant velocity, constant acceleration and turning models. IMM provides a tradeoff between a Generalized Pseudo Bayesian method of first (GPB1) and second (GPB2) degree [START_REF] Civera | Interacting multiple model monocular slam[END_REF], [START_REF] Wang | Simultaneous localization, mapping and moving object tracking[END_REF]. It only computes k Gaussians as in GPB1 but it still having as output an mixture of k Gaussians as in GPB2. Data association between targets is achieved by a prunned Multi Hypothesis Tracking approach.

VII. MOVING OBJECT CLASSIFICATION

We enhanced the common kinetic representation by including class information within fusion at the detection level. This information can help to improve detection associations, better estimate object's motion, and reduce the number of false tracks. However, at detection level, there is not enough certainty about the object's class and keeping only one class hypothesis disables the possibility of rectifying a premature decision.

Our composite representation is formed by two parts: kinetic + appearance. The former includes position and shape information in a two dimensional space, inferred from the moving object detection process. The latter includes an evidence distribution m(2 Ω ) for all possible class hypotheses, where Ω = {pedestrian, bike, car, truck} is the frame of discernment representing the classes of interest. This representation is used by the fusion approach to deliver a fused list of object detections, and to perform tracking.

A. Lidar sensor

The first part of the object representation can be obtained by analysing the shape of the detected moving objects. In the case of large detections this object is modelled by a box {x, y, w, l, c}, where x and y are the center of the box, w and l are the width and length according to the class of object c. For small detections (mainly pedestrians) a point model {x, y, c} is used, where x, y and c represent the object center and class of the object, respectively. The position and size of the object is obtained by measuring the detected objects in the 2D occupancy grid. The class of the object is inferred from the visible size of the object and follows a fixed fitting-model approach. However, no precise classification decision can be made due to the temporary visibility of the moving objects. For example, if the width of a detected object is less than a threshold ω small , we may think the object is a pedestrian or a bike but we are not sure of the real size of the object.

To define the typical size of the classes of interest, we used a priori knowledge from the distribution of the physical dimensions of several passenger cars, trucks and motorbikes sold in Europe [START_REF] Dietmayer | Model Based Object Classification and Tracking in Traffic Scenes from Range Images[END_REF]. However, instead of keeping only one class decision, we define a basic belief assignment m l (A) (Equation 4) for each A ∈ Ω, which describes an evidence distribution for the class of the moving object detected by lidar. We include classrelated factors (α p , α b , α c and α t ) to represent the lidar's performance to detect pedestrians, bikes, cars and trucks, respectively. Also we use discounting factors (γ b and γ c ) to indicate the uncertainty of the lidar processing for mis-detecting a bike or car.

When a bike is detected, due to visibility issues the detected object can still be a part of a car or a truck, for that reason evidence is also put in {b, c, t}. For the same reason, when a truck is detected, we are almost sure it cannot be a smaller object. In all the cases, the ignorance hypothesis Ω represents the lack of knowledge and the general uncertainty about the class.

m l (A) =                                          m l ({p}) = α p if class = p m l (Ω) = 1 -α p m l ({b}) = γ b α b if class = b m l ({b, c, t}) = γ b (1 -α b ) m l (Ω) = 1 -γ b m l ({c}) = γ c α c if class = c m l ({c, t}) = γ c (1 -α c ) m l (Ω) = 1 -γ c m l ({t}) = α t if class = t m l (Ω) = 1 -α t (4)

B. Camera sensor

Camera images offer discriminative visual information which leads to obtain another evidence distribution for the object classes. We follow the image processing described in Section VI-B2. For hypotheses generation, we first build a S-HOG descriptor for each section of the image we want to classify. For hypothesis verification, we use the built classifiers to classify the different objects.

The camera-based classification generates several sub regions inside each ROI, provided by lidar, in order to cover many possible scale and size configurations. Sometimes a ROI can contain more than one object of interest. Once we have obtained the object classification for each ROI, we generate a basic belief assignment m c following the Equation 5. This belief assignment represents the evidence distribution for the classes hypotheses in Ω of each object detected for camera processing, where α p , α c and α t are confidence factors and c c represents the camera sensor's precision.

m c (A) =                                                  m c ({p}) = α p c c if class = p m c ({p, b}) = α p (1 -c c ) m c (Ω) = 1 -α p m c ({b}) = α b c c if class = b m c ({p, b}) = α b (1 -c c ) m c (Ω) = 1 -α b m c ({c}) = α c c c if class = c m c ({c, t}) = α c (1 -c c ) m c (Ω) = 1 -α c m c ({t}) = α t c c if class = t m c ({c, t}) = α t (1 -c c ) m c (Ω) = 1 -α t (5)

C. Radar sensor

Radar targets are considered as preliminary moving object detections. Therefore, to obtain the object's class, we use the relative target speed deliver by the sensor. Speed threshold S p is statitically stimated using recorded data from the slowest scenario for vehicles, urban areas. We apply the basic belief assignment m r (Equation 6), where α and β are confidence factors for specific classes.

m r (A) =            m r (Ω) = α if object speed < S p m r ({p, b}) = 1 -α m r (Ω) = 1 -β if object speed > S p m r ({c, t}) = β (6)

VIII. FUSION APPROACH

Once we have performed moving object detection for each sensor input, and defined a composite object representation, the next task is the fusion of object detections and tracking. We propose a multi-sensor fusion framework placed at the detection level. Although this approach is presented using three main sensors, it can be extended to work with more sources of evidence by defining extra detection modules that are able to deliver the object representation previously defined.

A. Data association

When working with many sources of evidence, as in the object detection level, it is important to consider the problem of finding which object detections are related among the different lists of detections provided by the sensors (sources of evidence).

The combination of information at the detection level has the advantage of increasing the reliability of the detection result by reducing the influence of inaccurate, uncertain, incomplete, or conflicting information from sensor measurements or object classification modules.

Let us consider two sources of evidence S 1 and S 2 . Each of these sources provides a list of detections A = {a 1 , a 2 , .., a b } and B = {b 1 , b 2 , ..b n }, respectively. In order to combine the information of these sources we need to find the associations between the detections in A and B. All possible associations can be expressed as a matrix of magnitude |A × B| where each cell represents the evidence m a i ,b j about the association of the elements a i and b j for i ≤ |A| and j ≤ |B|. We can define three propositions regarding the possible association P(a i , b j ):

• 1 : if a i and b j are the same object.

• 0 : if a i and b j are not the same object.

• Ω : ignorance about the association (a i , b j ).

Let us define Ω d = {1, 0} as the frame of discernment to represent the aforementioned propositions. Therefore, m a i ,b j ({1}) and m a i ,b j ({0}) quantify the evidence supporting the proposition P(a i , b j ) = 1 and P(a i , b j ) = 0 respectively, and m a i ,b j ({1, 0}) stands for the ignorance, i.e., evidence that cannot support the other propositions. These propositions can be addressed by finding similarity measures between detections in A and B.

Sensors S 1 and S 2 can provide detections of a different kind. These detections can be represented by a position, shape, or appearance information, such as class. Hence, m a i ,b j has to be able to encode all the available similarity information. Let us define m a i ,b j in terms of its similarity value as follows:

m a i ,b j ({1}) = α i,j , m a i ,b j ({0}) = β i,j , m a i ,b j ({1, 0}) = 1 -α i,j -β i,j , (7)
where α i,j and β i,j quantify the evidence supporting the singletons in Ω d for the detections a i and b j , i.e., the similarity measures between them. We can define m a i ,b j as the fusion of all possible similarity measures to associate detections a i and b j . Therefore, we can assume that individual masses of evidence carry specific information about these two detections. Let us define m p as the evidence measures about the position similarity between detections in A and B provided by sources S 1 and S 2 respectively; and m c as the evidence measures about the appearance similarity.

Following the analysis made in Section III-A, we use Yagers's combination rule defined in Equation 2

m a i ,b j (A) = ∑ B∩C=A m p a i ,b j (B)m c a i ,b j (C), K a i ,b j = ∑ B∩C=∅ m p a i ,b j (B)m c a i ,b j (C), m a i ,b j ({Ω d }) =m a i ,b j ({Ω d }) + K a i ,b j , (8)
where m p a i ,b j and m c a i ,b j represent the evidence about the similarity between detections a i and b j according to position and class information, respectively.

Once matrix M A,B is built, we can analyse the evidence distribution m a i ,b j for each cell to decide if there is an association (m a i ,b j (1)), there is not(m a i ,b j (0)), or we have not enough evidence to decide (m a i ,b j (1, 0)) which can probably be due to noisy detections. In the next sections we will describe how to calculate these fused evidence distributions using similarity evidence from detections.

When two object detections are associated, the method combines the object representations by fusing the evidence distributions for class information. This fusion is achieved by applying the combination rule described in Equation 2. The fused object representation (kinetic + appearance) is passed as input to the tracking stage to be considered in the objects motion model estimation. Nonassociated object detections are passed as well expecting to be deleted by the tracking process if they are false detections or to be verified as real objects in case there is future evidence that confirms it.

It is important to notice that not all the sensors provide the same amount and type of information. For example, while radar data do not include information about the shape of the target, lidar data provide information about the position and the shape of the object. If two associated detections have complementary information, this is passed directly to the fused object representation; if the information is redundant, it is combined according to its type. For the position, we use the Bayesian based fusion presented in [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF], which combines the position information of two detections by integrating their covariance matrices. Shape information is usually provided only by the lidar. As stated above, class information is combined using the evidential combination rule from Equation 2.

In the next section we review our proposed methods to extract similarity information from the position and class of the detections. This information is included in Equation 8 to decide if two detections are associated.

1) Position similarity: According to the position of two detections a i and b j , we encode their similarity evidence in m p a i ,b j . Based on their positions, we can define function d a i ,b j as a distance function that satisfies the properties of a pseudo-distance metric. We choose Mahalanobis distance due to its ability to include the correlations of the set of distances. Therefore, a small value of d a i ,b j indicates that detections a i and b j are part of the same object; and a large value indicates the opposite. All the propositions for m p a i ,b j belong to the frame of discernment Ω d . Hence, the BBA for m p a i ,b j is described as follows:

m p a i ,b j ({1}) = α f (d a i ,b j ), m p a i ,b j ({0}) = α(1 -f (d a i ,b j )), m p a i ,b j ({1, 0}) =1 -α, (9)
where α ∈ [0, 1] is an evidence discounting factor and f (d a i ,b j ) → [0, 1]. The smaller the distance, the larger value given by function f . In our case we choose f as:

f (d a i ,b j ) = exp(-λd a i ,b j ), ( 10
)
where λ is used as a threshold factor that indicates the border between close and far distances.

2) Class dissimilarity: Contrary to the evidence provided by position, class information does not give direct evidence that supports the proposition P(a i , b j ) = 1. This means that even if two detections are identified with the same class, one can not affirm that they are the same object. This is due to the fact that there can be multiple different objects of the same class in the current driving scenario. However, it is clear that if two detections have different classes it is more likely that they belong to different objects. Hence, we use the class to provide evidence about the dissimilarity between detections: m c a i ,b j . The frame of discernment for the class evidence distribution is the set Ω = {p, b, c, t}. The frame of discernment for detections' association is Ω d and was described in Section VIII-A. Hence, we transfer the evidence from in Ω to Ω d as follows:

m c a i ,b j ({1}) =0, m c a i ,b j ({0}) = ∑ A∩B=∅ m c a i (A)m c b j (B), ∀A, B ⊂ Ω, m c a i ,b j ({1, 0}) =1 -m c a i ,b j ({0}), (11)
which means that we fuse the mass evidences where no common class hypothesis is shared between detections in lists A and B. m c a i and m c b j represent the BBAs for the class hypotheses of detections in lists A and B. However, as we have no information about the possible relation of detections with the same class, we place the rest of the evidence in the ignorance hypothesis {1, 0}.

B. Moving object tracking

Using the combined list of object detections provided by our fusion approach, we modified the model-based moving object tracking approach described in [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF]. We adapted a MCMC sampling process using our composite representation to find the best trajectories of tracks (hypotheses) in a sliding window of time. Generated object hypotheses are then put into a top-down process taking into account all the object dynamics models, sensor model, and visibility constraints. However, instead of searching in all the possible neighbour hypotheses, we use the class evidence distribution of each object detection to reduce the search space by considering the hypotheses with more mass evidence. Two objects have similar classes if their classes belong to the same general set. Two sets of classes are defined as general: vehicle = {c, t} and person = {p, b}.

If an object has a high evidence mass in the hypothesis {c}, we only sample the possible hypotheses for c and t. When the highest mass evidence is placed in a nonsingleton hypothesis, such as vehicle, the search space is expanded to include c and t samples alike.

We perform a dynamic fusion strategy, as described in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF], to associate the object's current state delivered by our fusion approach, and the object description of the current track. This allows to keep the object class information upto-date each time new sensor data is available. Hence, the final output of our DATMO solution is composed of a list of moving objects described by their kinetic information and by a set of all the possible class hypotheses represented by masses of evidence.

IX. EXPERIMENTAL RESULTS

Using the sensor set-up described in Section IV, we gathered four datasets from real scenarios: two datasets from urban areas and two data sets from highways. Both data sets were manually tagged in order to provide a ground truth reference. We analysed the degree of improvement achieved by early inclusion of class information within the DATMO component. Moreover, we performed a comparison between the fusion approach at tracking level described in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF] and our fusion approach at detection level using the same experimental scenarios.

In our DATMO solution at detection level, we first performed SLAM for the lidar sensor measurements (see Section VI-A) to detect the possible moving entities. Among the 2D position state for each detection, we define the frame of discernment Ω = {p, b, c, t} for its evidence class distribution. Therefore, 2 Ω is the number of all the possible class hypotheses for each detection. Then, the object representations for lidar, radar and camera detections are extracted following the methodologies presented in Sections VI and VII. Once we obtained the object representations, we perform the fusion at detection level and the tracking of the fused list of objects as detailed in Section VIII.

Fig. 8 shows two output examples of our complete PS in highway and urban areas. Both scenarios are considered as high-traffic scenarios due to the large number of moving objects around the vehicle. In both cases, all vehicles, including oncoming ones, are well detected, tracked and correctly classified: several cars and two trucks in the highway; and several cars, one truck and one pedestrian in the urban area. Additionally, static objects (such as barriers) are also reported and correctly identified as static obstacles using the method described in Section VI-A1. In the top view of these examples moving objects velocity is estimated by the model-based tracking module which takes advantage of the composite object representation to deliver speed and orientation. In the early fusion stage, the radar Doppler velocity information helps to improve the target speed estimated by the lidar after its moving direction is known. Also, the class of the object is improved by the fused information from the three different sensors providing a more reliable class hypothesis in the form of a class distribution. The continuous support applications use this class distribution to decide the correct actions.

In the output of our perception approach, a moving object is represented by several pieces of information: location, geometry, object class, speed, and moving direction that cannot be provided by only one individual sensor. The size of the bounding box is updated using the visible lidar measurements, the fixed-size class models and the lateral information from camera classification. The height of a bounding box is set according to the class of the detected object and to the result from camera classifiers.

Tables I andII show a comparison between the results obtained by the proposed fusion approach at detection level and our previous fusion approach at tracking level presented in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF]. It takes into account the erroneous classifications of moving objects. We use four datasets to conduct our experiments: 2 datasets from highways and 2 datasets from urban areas. We can see that the improvement of the fusion at detection level in highways with respect to the tracking level fusion is not considerable. However, in high-speed situations, the certainty about the moving vehicles is quite important. Hence, this small improvement is very useful for the final applications, such as continuous support systems. Urban areas represent a modern challenge for vehicle perception. The improvement of the fusion approach at detection level was considerable compared to our other fusion approach. Here, the richer representation of sensor detections and the data association relations allowed the early detection of real moving vehicles.

Regarding the pedestrian classification results, we obtained similar improvements to those obtained for vehicle detections. The problem of small clusters detected by lidar as moving obstacles but without the certainty of being classified as pedestrians is mainly overcome by the early combination of class information from radar and camera-based classification. Furthermore, the classification of moving objects (not only pedestrians) in our proposed approach takes on average less sensor scans than the compared fusion approach described in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF]. This is due to the early integration of the knowledge about the class of detected objects placed in m c a and m c b , which is directly related to the reduced search space for the shape and motion model discovering process performed by the MCMC technique.

A. On-line evaluation

Based on the running-time statistics of our PS, in urban areas (the most challenging scenario), the average computing time is 40ms which fulfils the processing time requirement of the designed real-time platform (75ms). In rural areas and highways, the processing of the whole PS can be reduced to 30ms.

Table III summarizes the results collected after testing our PS with on-line data in four different scenarios. Correct detections represent true moving objects. False detections represent detections wrongly recognized as moving objects. Correct classifications represent well classified moving objects. False classifications are selfexplanatory. For clarity sake, the number of correct and false detections, and classifications are also represented by percentages. Four objects of interest were taken into account: pedestrians, bikes, cars and trucks.

In test track scenarios, where only few cars and pedestrians are present, the detection and classification rate of pedestrians and cars are nearly perfect (96-100%). This scenario does not contain many common driving situations, such as several moving objects and high traffic dynamics. However, it allows us to test specific components of the PS, e.g., pedestrian and vehicle classification, and moving vehicle tracking.

In highways, the detection rate of vehicles is also very good: car (97.8%), truck (96.4%) where the missed detections are due mainly to inherently noisy and cluttered data (e.g., lidar impacts on the ground). The large size of the truck makes the truck detection not as accurate as car detection since it is sometimes confused with the barrier. The false detection rate (2.2%) is due mainly to the reflection in raw lidar data which creates ghost objects and the noisy radar target detection. However, the fusion approach allows the ability to obtain a highly correct classification rate for both cars or trucks whilst keeping a very low false classification rate.

In urban areas, vehicle detection and classification is still high, considering the increased number of moving obstacles and the cluttered environment. However, the false detection rate is higher than in highway scenarios. This increase is due to the highly dynamic environment and to the reduced field of view in high traffic situations. Moreover, the pedestrian false classifications commonly appears when the classifiers mis-classify traffic posts as pedestrians. These mis-classifications suggest the construction of more robust visual classifiers or the implementation of more discriminating visual descriptors.

In Rural roads, several moving objects of interest may appear, but high traffic dynamics are not present. Besides, there are less traffic landmarks. The falseclassification rates obtained in this scenario are higher than the ones obtained from the other three scenarios. This is due to the increasing number of natural obstacles, such as bushes and trees. The common object false classifications are due to false moving objects (mainly bushes) preliminary classified as trucks or pedestrians. One solution could be to implement a dedicated classifier to discard this type of obstacles.

X. CONCLUSIONS AND PERSPECTIVES

In this paper we have reviewed the problem of intelligent vehicle perception. Specifically, we have focus on the DATMO component of the perception task. We have proposed the use of classification information as a key element of a composite object representation, where not only kinetic information but appearance information plays an important role in the detection, classification and tracking of moving objects of interest. We have analysed the impact of our composite object description by performing multi-sensor fusion at detection level. We used three main sensors to define, develop, test and evaluate our fusion approach: lidar, radar, and camera. Moreover, our complete perception solution was evalu- ated using on-line and off-line data from a real vehicle of the interactIVe European project.

Integrating class information at the detection level, allowed the fusion to improve the detection by considering an evidence distribution over the different class hypotheses of the detected objects. This improvement directly reduces the number of false detections and false classifications at early levels of the DATMO component. Moreover, the tracking stage benefits from the reduction of mis-detections and from the more accurate classification information to accelerate the tracking process.

A. Perspectives

A 3D-based representation (e.g., voxels segments) can provide more information about the shape/class of the obstacles surrounding the vehicle demonstrator, such as objects of interest, and common obstacles that generate false classifications (e.g., trees, bushes and poles).

Section IX has shown that sometimes the classification precision varies according to the current driving scenario. Promising results on the field of scene classification can power context-based learning methods to estimate parameters in the detection and classification modules, thus generating reliability factors closer to the real driving situation.

Figure 2 .

 2 Figure 2. Fusion levels within the SLAM and DATMO components interaction.

Figure 3 .

 3 Figure 3. Left: images of the CRF vehicle demonstrator. Right: Field of view of the three frontal sensors used as inputs to gather datasets for our proposed fusion approach detailed in Sections VI, VII and VIII.

Figure 4 .

 4 Figure 4. Schematic of our multiple sensor perception system, also known as Frontal Object Perception (FOP) -Moving Object Detection (MOC) module. Kinetic and appearance information are extracted from lidar and radar sensors, and only appearance information from camera.

Figure 5 .

 5 Figure 5. Occupancy grid representation obtained by processing raw lidar data. From left to right: Reference image; static occupancy grid M t-1 after applying the SLAM solution; current lidar scan; detection of the moving objects (green bounding boxes).

Figure 6 .

 6 Figure 6. Informative blocks for each object class patch, from left to right: pedestrian, car, and truck. Histograms of gradients are computed over these sparse blocks and concatenated to form S-HOG descriptors. Average size of the descriptors for pedestrians, bikes, cars and trucks are 216, 216, 288 and 288 respectively.

Figure 7 .

 7 Figure 7. Examples of successful detection of pedestrians (left) and cars (right) from camera images.

  to represent m a i ,b j in terms of m p a i ,b j and m c a i ,b j as follows:

Figure 8 .

 8 Figure 8. Results of the PS for highway (1) and urban areas (2). Several objects of interest are detected. Left side shows the camera image and the identified moving objects. Yellow boxes represent moving objects, red dots represent lidar hits and red circles represent radar detections. Right side displays the top view of the same scene. Tags identify detected object's classes. Video demonstrations of our results can be found in http://goo.gl/FuMBC2.

Table I FUSION

 I RESULTS. NUMBER OF c AND t MIS-CLASSIFICATIONS.

	Dataset	Moving objects	Number of vehicle mis-classifications Tracking level Detection level
	Highway 1 110	6 5.4%	4 3.6%
	Highway 2 154	7 4.5%	5 3.2%
	Urban 1	195	20 10.2%	10 5.1%
	Urban 2	233	24 10.3%	9 3.8%
			Table II
	FUSION RESULTS. NUMBER OF p AND b MIS-CLASSIFICATIONS.
	Dataset	Moving objects	Number of pedestrian mis-classifications Tracking level Detection level
	Urban 1	52	11 21.1%	6 11.53%
	Urban 2	58	14 24.13%	7 12%

Table III RESULTS

 III OF OUR PS IN FOUR SCENARIOS: HIGHWAY, URBAN AREA, RURAL ROAD AND TEST TRACK. FOUR OBJECTS OF INTEREST ARE CONSIDERED: pEDESTRIAN, bIKE, cAR, AND tRUCK.

								Detections						Classifications
	Scenario		Total objects			Correct		False		Correct			False
		p	b	c	t	p	b	c	t	all	p	b	c	t	p	b	c	t
	Highway	0	0	702	281	n/a n/a	n/a n/a	687 97.8%	271 96.4%	22 2.2%	n/a n/a	n/a n/a	669 95.2%	251 89.3%	0 0%	0 0%	4 0.5%	0 0%
	Urban	65	7	619	97	57 87.6%	6 85.7%	580 93.6%	88 90.7%	17 2.1%	57 87.6%	6 85.7%	570 92.0%	78 80.4%	9 13.8%	1 14.2%	6 0.9%	5 5.1%
	Rural	9	0	68	6	9 100%	n/a n/a	62 91.1%	5 83.3%	9 10.8%	9 100%	n/a n/a	60 88.2%	5 100%	3 33.3%	0 0%	5 7.3%	2 33.3%
	Test track	248	0	301	0	247 99.6%	n/a n/a	300 100%	n/a n/a	1 0.1%	240 96.7%	n/a n/a	300 100%	n/a n/a	0 0%	0 0%	0 0%	0 0%

scale integrating project part of the FP7-ICT for Safety and Energy Efficiency in Mobility.

Olivier Aycard is an Associate Professor in the Computer Science Department at University of Grenoble1 (UJF) and member of the AMA team at the LIG laboratory. He received his PhD in Computer Science from University of Nancy1 in June 1998 and his Accreditation to Supervise Research from University of Greno-ble1 in December 2010. His research focus on probabilistic and machine learning techniques for sensor data analysis and interpretation. In the last decade he has been involved in several European projects in the field of perception for ADAS and has cooperated with international car manufacturers.