Samir Hachour
email: samir_hachour@ens.univ-artois.fr

David Mercier
email: david.mercier@univ-artois.fr

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

Multi-target tracking with credal classification and kinematic data

Keywords: Multi-target tracking, credal classification, data assignment, targets management

This article proposes a method to classify multiple maneuvering targets at the same time. This task is a much harder problem than classifying a single target, as sensors do not know how to assign captured measurements to known targets. This article extends previous results scattered in the literature and unifies them in a single global framework with belief functions. Through two examples, it is shown that the full algorithm using belief functions improves results obtained with standard Bayesian classifiers and that it can be applied to a large variety of applications.

Introduction

The problem of joint multi-target tracking and classification, which is as old as the invention of radars, is a much more complex task than the problem of tracking one target. Indeed it includes a step, called the assignment problem, where sensors have to associate known objects to new captured measurements. A full multi-target tracking solution includes several interlaced components such as the tracking component, the assignment component, the hypothesis rejection (new or disappeared targets...) and finally the classification step. Probability-based solutions already exist in the literature [START_REF] Bar-Shalom | Automatic track formation in clutter with a recursive algorithm[END_REF][START_REF] Bar-Shalom | Estimation with applications to tracking and navigation[END_REF][START_REF] Blackman | Multiple-target tracking with radar applications[END_REF][START_REF] Bar-Shalom | Tracking and data association[END_REF][START_REF] Blackman | Multiple hypothesis tracking for multiple target tracking[END_REF][START_REF] Ristic | On target classification using kinematic data[END_REF][START_REF] Mei | A second-order uncertainty model for target classification using kinematic data[END_REF].

For about 40 years, other uncertainty models based on non-additive measures have been developed, in particular the Transferable Belief Model [START_REF] Smets | The Transferable Belief Model[END_REF] based on belief functions [START_REF] Dempster | A generalization of Bayesian inference[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF] which is sometimes referred to as the credal model. Applications of this model can be found for example in classification tasks and decision support systems [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF]. Direct comparisons with Bayesian solutions are presented in [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF][START_REF] Ristic | The TBM global distance measure for the association of uncertain combat ID declarations[END_REF] with discrete variables or in [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF] with continuous variables.

Applications of this theory to multi-target tracking and classification problems are scattered through several articles presenting different approaches. In [START_REF] Mercier | Object association with belief functions, an application with vehicles[END_REF][START_REF] Ristic | The TBM global distance measure for the association of uncertain combat ID declarations[END_REF] and in [START_REF] Wartelle | Classification de scènes à nombre d'objets inconnu[END_REF] various distances between belief functions are used to tackle the assignment problem. Reference [START_REF] Mercier | Object association with belief functions, an application with vehicles[END_REF] has been recently improved in [START_REF] Zoghby | Optimal object association from pairwise evidential mass functions[END_REF], but these two references only tackles the assignment problem with uncertain measurements and do not cope with the tracking problem. In [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF] a solution to track and classify a single dynamical target is proposed, but no extension to multi-target tracking is proposed.

The aim of this article is to gather these scattered results, to unify them in a single and consonant framework based on belief functions, and to propose a solution for multi target tracking using belief functions when no one exists in the recent literature. The proposed solution also includes a step of hypothesis rejection, which means that it manages new and disappeared targets.

The result is a complete solution to multi-target tracking and classification in a cluttered environment. It mimics the standard and well accepted Bayesian solutions, but it extends them, when possible, with belief functions. A short preliminary version of this article was presented in [START_REF] Hachour | Tracking and identification of multiple targets[END_REF].

The well known Interacting Multiple Model (IMM) algorithm is used to track multiple targets. The assignment problem of real measurements with known targets is resolved by the means of a generalized Global Nearest Neighbor algorithm. Target management is ensured by a score function representing the quality of target tracks. Finally, the classification step is realized with the Transferable Belief Model instead of a classical Bayesian solution.

This article is organized as follows. An introduction to belief function theory is presented in Section 2. Section 3 deals with tracking problems. Assignment and hypothesis rejection problems are tackled in Section 4. Bayesian and proposed algorithms are summarized in Section 5. Finally, two application examples are detailed in Section 6. The first one involves an academic example on aircraft classification with constant classes, it allows a comparison with a Bayesian solution. The second example concerns a pedestrian activity recognition, it highlights a first extension of the proposed algorithm to time varying classes.

Belief functions

Main functions

This section introduces basic notions on belief function theory, which was firstly introduced by Dempster in [START_REF] Dempster | A generalization of Bayesian inference[END_REF] and extended by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] and Smets [START_REF] Smets | The Transferable Belief Model[END_REF]. Knowledge is expressed on a discrete set C = {c 1 , c 2 , ..., c nc } of nc mutually exclusive and exhaustive hypotheses. Frame C is called the frame of discernment. A mass m(A) with A ⊆ C is the part of belief supporting A that, due to a lack of information, cannot be given to any strict subset of A [START_REF] Smets | The Transferable Belief Model[END_REF]. A mass function m (or basic belief assignment) has to satisfy: A⊆C m(A) = 1 .

(

) 1
Throughout this article, 2 C represents all the subsets of C. A set A such that m(A) > 0 is called a focal element of m.

In addition to the mass function, two other functions are defined in the following manner. The plausibility function Pl represents the total amount of belief that may be given to a subset A of C with further pieces of evidence:

Pl(A) = A∩B ∅ m(B) . (2)
Unlike the plausibility function, the belief function Bel represents the amount of belief that is certain and cannot be reduced:

Bel(A) = A⊇B m(B) . (3)
These functions are in one-to-one correspondence [START_REF] Shafer | A mathematical theory of evidence[END_REF], so they are used indifferently with the same term belief function when the context is clear.

A belief function whose focal elements are singletons is called a Bayesian belief function, it corresponds to a probability distribution and respects the property of additivity:

Pl(A ∪ B) = Pl(A) + Pl(B) , (4)
with (A, B) ⊆ 2 C and A ∩ B ∅. In general, this relation is false and belief functions are non-additive measures.

A belief function such that m(C) = 1 respects Pl(A) = 1 for all A subsets of C, A ∅. Denoted by m 0 , it is called the vacuous belief function and represents the full ignorance.

Fusion rule and discounting

When more than one mass function is expressed on the same frame of discernment, they can be fused to obtain a single representation. The conjunctive combination used in this work assumes independent and absolutely reliable sources. Let m 1 and m 2 be two mass functions provided by two distinct sources and expressed on the same frame of discernment C, their conjunctive combination is defined as follows:

m 12 (A) = (m 1 ∩ m 2 )(A) = A 1 ∩A 2 =A m 1 (A 1 )m 2 (A 2 ) . (5)
Equation ( 5) is the unnormalized rule, the normalized rule is referred to as Dempster's rule of combination, and is defined by:

m 12 (A) = A 1 ∩A 2 =A m 1 (A 1 )m 2 (A 2 ) 1 - A 1 ∩A 2 =∅ m 1 (A 1 )m 2 (A 2 ) . ( 6
)
This rule is used in order to update a priori beliefs with online measurements, as in the following Section 2.4.

The last example in this article involves the discounting of a source of information. Such a discounting assumes that you can estimate the reliability of a source by a factor λ ∈ [0, 1]. If λ = 1, the source is considered as absolutely reliable, while if λ = 0, the source must be discarded and replaced by a vacuous belief. Thus the discounting m λ of a source m is defined by:

m λ (A) = λ m(A) if A C , m λ (C) = λ m(C) + 1 -λ otherwise. ( 7
)
If several sources of information m i have to be fused, each one with its own reliability λ i , a classical approach is to first discount all of them, and then to conjunctively fuse them using Equation [START_REF] Blackman | Multiple hypothesis tracking for multiple target tracking[END_REF]. Several other fusion rules are defined, and for a review, readers can refer to [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF]. For example, contextual data can be included also in the fusion process, see [START_REF] Mercier | Belief functions contextual discounting and canonical decompositions[END_REF], and reliability factors can be adapted online [START_REF] Delmotte | Detection of defective sources in the setting of possibility theory[END_REF], although this is not used in this article.

Decision rule

Several belief function interpretations exist, among them the Upper/Lower Probabilities (ULP), usually called imprecise probabilities, and the Transferable Belief Model (TBM) of Smets. Basically these models are equal when considering static knowledge, but differ when conditioning steps are involved. Readers interested in this topic can refer to [START_REF] Smets | What is Dempster-Shafer's model[END_REF]. In a few words, within an ULP model, conditioning requires to condition every probability measure P(A) compatible with the bounds defined by Bel(A) ≤ P(A) ≤ Pl(A). Then, the new bounds Bel(.|.) and Pl(.|.) must be recomputed by checking every conditioned probability measures, and taking the new maximum and minimum, while within the TBM it suffices to condition only the original Bel(A) and Pl(A). Thus, the ULP model is more computationally demanding. In a recent article [START_REF] Benavoli | Classification with imprecise likelihoods: A comparison of TBM, random set and imprecise probability approach[END_REF], the ULP model has been advocated in a classification problem. But the authors of this article do not find the provided examples conclusive and the advantage of the ULP model over the TBM remains unclear. Since it is more complex to use, the TBM has been chosen in this article, as in [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF] for instance.

The TBM represents and manages knowledge with a two level model. The first one, referred to as the credal level, concerns the representation and the manipulation of the data. It is the place where data are encoded, combined and updated with belief functions without assuming probability measures [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF]. Decisions are made when necessary at a second level called the pignistic level, where belief functions are transformed into a probability measures using the pignistic transformation justified in [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF] through rationality requirements and basic axioms. Pignistic probability BetP is defined by:

BetP({c i }) = c i ∈A m(A) | A | (1 -m(∅)) . ( 8
)
Let us remark that other decision rules have been introduced for belief functions, among them the maximum of plausibility [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF]. Comparing the drawbacks and advantages of all the decision rules is outside the scope of this article, see for instance [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF].

Generalized Bayes Theorem

Bayes theorem enables to compute the a posteriori probability from an a priori one. With likelihoods l(c i |z) = P(z|c i ), where z is a measure provided by a sensor, each probability P(c i |z) can be computed by:

P(c i |z) = l(c i |z)P(c i ) c j l(c j |z)P(c j ) . (9)
In a recursive scheme, P(c i ) becomes P k (c i ) and P(c i |z) = P k (c i |z), where the index k represents a given time step. Initialization, without any further information, is usually carried out with the uniform probability measure.

With the same ideas, Smets introduces a Generalized Bayesian Theorem (GBT) [START_REF] Smets | Belief functions: the disjunctive rule of combination and the Generalized Bayesian Theorem[END_REF] allowing the recursive calculation of mass functions. The GBT requires two steps. Based on likelihoods l(c i |z), a conditional mass function m(A|z) for each A ⊆ C is firstly calculated as follows:

m(A|z) = c i ∈A l(c i |z) c i ∈ Ā(1 -l(c i |z)) . ( 10
)
Formulated in a recursive manner, the second step consists in conjunctively merging a priori and conditional beliefs with Equation ( 5):

m k = m k (.|z) ∩ m k-1 . (11)
The a priori belief is initialized with the vacuous belief m 0 . GBT applications are numerous [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF][START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF][START_REF] Le Duy | A study on updating belief functions for parameter uncertainty representation in Nuclear Probabilistic Risk Assessment[END_REF][START_REF] Aregui | Constructing consonant belief functions from sample data using confidence sets of pignistic probabilities[END_REF][START_REF] Capelle | Evidential segmentation scheme of multi-echo MR images for the detection of brain tumors using neighborhood information[END_REF].

Target state and measurement models

Measurement model

The final goal of the credal algorithms presented in this article is to find each target class, which belongs to C, from a series of measurements. For simplicity reasons, targets measurements z j k , with j = 1, 2, ..., m where m represents the number of measurements acquired at time k, are considered linearly dependent on the target state vectors x i k , with i = 1, 2, ..., n, where n is the number of known targets at time k. Target state vectors evolutions are described by Equation [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF] and measurements are taken according to Equation [START_REF] Ristic | The TBM global distance measure for the association of uncertain combat ID declarations[END_REF].

x i k = F(c s )x i k-1 + Bu i k + w i k , (12)
z j k = Hx i k + v k known target originated measurement, Hx i k + v k new target or noise originated measurement, (13)
where:

• x i k ∈ R p is the i th target state vector with i ∈ {1, 2, ..., n} representing the index of the target at time step k.

• F(c s ) is a p × p state matrix depending on class c s , with s ∈ {1, 2, ..., nc}.

• u i k is the i th target deterministic input at time step k and w k is a state Gaussian noise with covariance matrix Q. The input matrix is denoted B.

• z j k ∈ R q is the j th received observation at time step k, with j ∈ {1, 2, ..., m}. • H is a q × p time invariant observation matrix and v k is the measurement error, it is considered as a Gaussian noise with zero mean value and covariance matrix R.

The number of targets n is not constant over time and a given measurement z j k at time step k can come from a known target i, a new target i or even from noise.

The state model parameters < F, B, u, w > are given in a general manner in Equation [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF]. In maneuvering targets case, there will be r different model parameters sets, where r is the number of different evolution modes.

The optimal Bayesian estimation of the i th target state and class at time step k requires the calculation of the following probability density function:

p(x i k , c s |Z i k ), i = 1, ..., n (14)
where

Z i k = z i 1 , z i 2 , .
.., z i k represents the cumulated measurement for the target i until the time step k.

Discussion about the filters used to track

The Gaussian assumption on the state and measurement noises allows the probability density function of n maneuvering targets, represented by Equation [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF], to be optimally estimated by Kalman filter based Interacting Multiple Model (IMM) algorithm. Each IMM algorithm is dedicated to track one target, it handles its r possible evolution models. Details on the derivation of the targets motion models can be found in [START_REF] Blackman | Design and analysis of modern tracking systems[END_REF][START_REF] Watson | IMM algorithm for tracking targets that maneuver through coordinated turns[END_REF][START_REF] Singer | Estimating optimal tracking filter performance for manned maneuvering targets[END_REF]. More information on IMM algorithm can also be found in [START_REF] Blackman | Design and analysis of modern tracking systems[END_REF][START_REF] Bar-Shalom | Variable dimension filter for maneuvering target tracking[END_REF]. Different than the IMM algorithm proposing an analytic estimation of the a posteriori probability density in Equation ( 14), other more recent methods exist. Based on Monte Carlo approximation of the a posteriori density, they are called either Probability Hypothesis Density (PHD) [START_REF] Li | PHD filter for multi-target tracking with glint noise[END_REF][START_REF] Li | A new multiple extended target tracking algorithm using PHD filter[END_REF][START_REF] Vo | Sequential Monte Carlo implementation of the PHD filter for multi-target tracking[END_REF] filters with different Monte Carlo sampling methods, or also Particle Filter (PF) [START_REF] Ho | Object tracking by exploiting adaptive region-wise linear subspace representations and adaptive templates in an iterative particle filter[END_REF][START_REF] Mukherjee | Likelihood function modeling of particle filter in presence of non-stationary non-Gaussian measurement noise[END_REF]. The approximation of the a posteriori probability density, in these methods, is done by performing a set of N weighted Monte Carlo samples. The approximation is almost optimal when N tends to infinity. The major advantage of Monte Carlo based methods is the capacity to estimate the a posteriori probability density in Equation ( 14), regardless the nature of the variable x (linear or non-linear) and regardless the nature of the noise affecting the targets evolution and measurement models (Gaussian or non-Gaussian). However, these approaches need a high number of samples (particles) N to achieve an acceptable approximation. For example, Caron et al. in [START_REF] Caron | Least committed basic belief density induced by a multivariate Gaussian: Formulation with applications[END_REF] use N = 250 particles to achieve the performance of the same kinematic data based classification presented in [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF] for one target classification, and used in the first simulation example of Section 6 for multi-target classification. In their work, Caron et al. use the so-called Rao-Blackwellised filter, the particles in this filter are simply Kalman estimators where each Kalman estimator handles a target linear model. This means that for a kinematic data based classification problem, it is better to have a set of different linear models describing targets evolutions instead of unified non-linear one. Regarded this circumstance, Kalman filter based IMM algorithm appears much more efficient in the case of Gaussian noises.

In a simple example of linear signal estimation illustrated in Figure 1, the Kalman filter estimation error averaged on 100 different simulations has a mean value of 5.5721, while the obtained mean error with a particle filter for N = 150 is about 7.1466. Knowing that one particle is approximately equivalent to a Kalman filter in terms of computation complexity, this example illustrates the great need on computation resource of the particle filter. The estimation error in this comparison is calculated by: (xx) 2 , where the real state x and the estimated one x are scalars. This article is mainly devoted to the classification task. To simplify the problem only linear models are considered. Of course, if non linear models are required to describe the targets dynamic, Kalman filters, therefore IMMs, would be out performed by such particle or PHD filters. This would not impact the classification stage where only likelihoods of targets models are needed.

Difference between single object and multiple object classifications

This article deals with multiple object classification, where the difference between the number of known targets n and the number of measurements m could be strictly greater than 1.

As illustrated by the following examples, this task is much more complex in a multitarget context as the classifier has to infer the association of captured measurements z k with already known targets.

When only one object has to be classified, the Bayesian approach provides directly the solution using Bayes rule (Equation ( 9)) as it can be observed in Figure 2 with P k-1 representing the a priori probabilities and P k the a posteriori ones.

As illustrated in Figure 3, with more than one target to track and classify, Bayes rule can no more be applied directly and an association step is needed to assign new measurements to known targets. A solution to the assignment problem is presented in Section 4.

Remark.

As readers can notice it, states and measurements equations presented in this section are based on real numbers. This is in contrast with the work of Smets and Ristic [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF] on single dynamical target classification. Indeed in their approach, the authors have decided to use belief functions at every step of the classification chain. So, they have introduced continuous belief functions to describe targets states. Generalized Kalman filters were used to handle continuous belief functions at that stage. This is not the case here, since classical Kalman Filter based IMMs are used. But, as readers will be able to check it, results proposed in simulation Section 6 behave similarly as the ones of Smets and Ristic. The major improvement over the Bayesian classification seems to lie in the use of belief functions at the classification stage and in particular the use of the Generalized Bayesian Theorem. The crucial importance of this component when trying to classify objects from measurements was also studied in [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF].

Assignment problem with targets appearances and disappearances management

Assignment problem and targets management is an intermediate step between the prediction and the update steps of the IMMs. It is supplied by a set of predicted measurements and their corresponding covariance matrices, respectively, ẑi and S i , with i = {1, 2, ..., n}, of the n already known targets. For each target i, the quantities ẑi and S i are aggregations of the corresponding IMM models predicted quantities, namely ẑi l and S i l , where l = 1, ..., r and r is the number of models in the IMM, see [30, pages 225-226] for detailed information.

Targets predicted measurements ẑi , with i = {1, 2, ..., n}, are compared with a set of m real measurements z j , j = {1, 2, ..., m} received at time step k, then an assignment problem is resolved in such a way to answer the following questions:

• How to assign the m received real measurements z j to the n already predicted measurements ẑi ?

• How to manage targets appearances, reappearances and disappearances?

The answers that should be given to the above questions are:

• Targets that have received an observation are updated following the IMMs update process.

• Targets that have not received any observation are considered as non-detected.

• The non-assigned measurements are used to initialize new targets.

The following paragraphs discuss the main existing assignment solutions in literature, and the adopted solution to obtain the above expected answers.

Overview of assignment solutions for multi-target tracking

The problem of false assignments in multi-target tracking and recognition is treated by researchers from various application domains. Namely, in the domain of artificial vision where the problem becomes less difficult since complementary information (texture, color, etc.) can help to distinguish the kinematic observations of the objects and get less conflicting assignment problem. Readers can refer for example to [START_REF] Yang | An online learned crf model for multi-target tracking[END_REF] where appearance information (color, texture) are added to distinguish tracked people in a video, this increases the robustness to false assignments. The same method benefits of the low calculation complexity of the Hungarian algorithm used to resolve the assignment problem, which makes it feasible online. Other works in artificial vision using complementary information (color and sound characterizing the targets) to distinguish the targets observations can be found in [START_REF] Megherbi | Multimodal data association based on the use of belief functions for multiple target tracking[END_REF][START_REF] Royère | Data association with belief theory[END_REF].

In this work, the only available data are the kinematic ones. In this context, several categories of approaches have been developed principally with probability measures, deterministic approaches and Monte Carlo sampling based approaches.

Probabilistic approaches update each target with a weighted sum of the observations falling within its neighborhood. The weights represent the a posteriori probabilities that the observations are originated from the considered targets. Examples are Joint Probability Data Association (JPDA), Integrated Probability Data Association (IPDA) [START_REF] Fortmann | Multi-target tracking using joint probabilistic data association[END_REF][START_REF] Musicki | Integrated probabilistic data association[END_REF][START_REF] Blom | Combining IMM and JPDA for tracking multiple maneuvering targets in clutter[END_REF], etc. These approaches consider as a new target the observation having a low probability to be assigned to all the existing targets, and consider as a non-detected target, the one going to be updated with a low weighted sum of observations. Multi-Hypotheses Tracking (MHT) algorithm [START_REF] Blackman | Multiple hypothesis tracking for multiple target tracking[END_REF] has a different principle, it is a multi-scan approach that holds off the assignment decision until having more clear and non-conflicting data. Considered as the best approach, it is also the most computationally demanding. MHT, JPDA and IPDA computational complexities increase rapidly with the number of targets and observations. Their performances are known to be weak in a dense targets environment.

Deterministic approaches, like Nearest Neighbor (NN) which updates each target with its nearest neighbor and Global Nearest Neighbor (GNN) [START_REF] Blackman | Multiple-target tracking with radar applications[END_REF][START_REF] Konstantinova | A study of a target tracking algorithm using global nearest neighbor approach[END_REF] take the optimal solution which minimizes the global distance between the targets and observations. Credal versions of the GNN algorithm are proposed in [START_REF] Mercier | Object association with belief functions, an application with vehicles[END_REF] and [START_REF] Zoghby | Optimal object association from pairwise evidential mass functions[END_REF] but have not yet been tested in a tracking context where sensors noises are permanently changing over time. Deterministic approaches are known to present some weakness when it comes to track nearby or crossing targets (see Section 6.2). However, they are well suited for real time applications, given their simplicity, low computational complexity and their efficiency to handle appearances and disappearances, even in a dense targets environments.

More recently, Markov Chain Monte Carlo (MCMC) based methods [START_REF] Khan | MCMC-based particle filtering for tracking a variable number of interacting targets[END_REF][START_REF] Septier | On MCMC-based particle methods for Bayesian filtering: Application to multitarget tracking[END_REF][START_REF] Hue | Sequential Monte Carlo methods for multiple target tracking and data fusion[END_REF]] have been proposed to resolve the assignment problem. They are sub-optimal methods that do not carry on the statistical distribution of the variables. Their performances tend to the optimal one, when the number of performed Monte Carlo samples tends to infinity. The problem of false assignments still remains even in MCMC based methods. For example, the approach proposed in [START_REF] Khan | MCMC-based particle filtering for tracking a variable number of interacting targets[END_REF] presents a low rate of false assignments for multiple interacting ants tracking, thanks to the use of a targets interacting model and extended information such as ants orientations before and after crossing. MCMC methods are preferred for their general aspect (no assumption on variables statistics) but they are known to be computationally very complex.

To avoid the assignment problem in multi-target tracking, other conceptions of the problem have emerged. For example, the work presented in [START_REF] Baum | Association-free tracking of two closely spaced targets[END_REF] presents a so-called "One State Filter" method. It gathers all state vectors of the tracked targets in one extended state vector, modify accordingly all measurements models and then a single unified estimator can be designed, be it an Extended Kalman Filter (EKF) or an Unscented Kalman Filter (UKF). This way, explicit data association methods (GNN, JPDA, MHT, etc..) can be disregarded. Although very interesting, this method suffers from a major issue, as recognized by the authors: currently this approach can handle two targets only, and it seems difficult to generalize it to more. A second issue, as mentioned in [START_REF] Baum | Association-free tracking of two closely spaced targets[END_REF], is that identities of crossing or nearby targets are lost. This means that in a context of kinematic data based classification approach, like the one proposed here, this approach can not be applied, because each target is classified based on its own explicit observations.

Adopted assignment solution: GNN algorithm

In a few recent references [START_REF] Ristic | The TBM global distance measure for the association of uncertain combat ID declarations[END_REF][START_REF] Blackman | Design and analysis of modern tracking systems[END_REF], the standard GNN algorithm is presented based on a square matrix representing the distances between the n predicted states and the m measurements with n = m.

To use the standard Munkres solution with a varying number of targets (which means that possibly n m), a more general GNN algorithm is considered in this article. Its resolution is performed by the generalized Munkres algorithm [START_REF] Bourgeois | An extension of the Munkres algorithm for the assignment problem to rectangular matrices[END_REF] in such a way to handle rectangular assignment matrices. The Generalized GNN algorithm is composed of two main steps: the generalized affectation matrix calculation and its resolution.

A general formulation of the assignment matrix is given in Table 1. In this table, [D j,i ] ∈ R m×n represents a special case of Mahalanobis distance (normalized Euclidean distance), which follows a χ 2 distribution with a degree of freedom q (dimension of the measurement vector) [START_REF] Gj | Mahalanobis distance[END_REF]. The distance is calculated as follows:

D j,i = (z j -ẑi ) T (S i ) -1 (z j -ẑi ), (15)
with j = {1, 2, ..., m}, i = {1, 2, ..., n} where S i represents target i expected measurement error covariance matrix. It is related to the covariance matrices of the Kalman filters in the corresponding IMM. Threshold T in Table 1 is drawn from the χ 2 table based on an a priori probability that the measurement corresponds to a new target with the degree of freedom q. Initials NT stands for New Target.

♠♠♠ Give equation to deduce or compute T: it will be great to avoid ambiguities Real measurements n known targets m possible new targets ẑ1 ẑ2 . . . ẑn Using modified Munkres algorithm [START_REF] Bourgeois | An extension of the Munkres algorithm for the assignment problem to rectangular matrices[END_REF], the assignment problem can be efficiently resolved and the result is used in the following manner:

NT 1 NT 2 . . . NT m z 1 D 1,1 D 1,2 . . . D 1,n T ∞ . . . ∞ z 2 D 2,
• Measurements assigned to known targets are processed by the targets corresponding IMM algorithms.

• Measurements assigned to NT are used to initialize new IMMs. Let us note that a measurement assigned to NT is either originated by a real new target or by noise, so the measurement is not immediately confirmed as a new target. The confirmation is done by the means of a score function described in the following paragraph.

• Target which does not receive any measurement is updated by its predicted one (trajectory prediction). Its score will decrease up to the point it will be considered as a disappeared target. This action is ensured by the score function.

In some previous works [START_REF] Blackman | Design and analysis of modern tracking systems[END_REF], targets are confirmed or deleted depending on how often they are detected or not.

A more efficient manner to validate and delete targets is to use a score function which represents the quality of the targets tracks.

Targets appearances and disappearances management

The score function is a sequential probability ratio test. The test was first introduced by Wald in [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF] and its use in the targets tracking framework is clearly detailed in [30, pages 327 -334]. Since it is well known and clearly presented in textbooks, only the outline of the test is given next. They are two hypothesis for each tracked target: a true one, or a false one.

The log-likelihood ratio L i (k) for each target i at time step k is updated sequentially by:

L i (k) = L i (k -1) + ∆L i (k) . ( 16
)
Once the ratio is calculated, it is compared to two thresholds T 1 and T 2 which depend on the false target confirmation and true target deletion probabilities. Then either a target is confirmed, deleted, or the test continues until a decision is made. Example of multi-target appearances and disappearances management. This simulated scenario is based on the model described in Section 6.1.1 Equation [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF]. Figures 4 and5 show respectively the y direction evolutions of four targets and the evolutions of their score functions. Difficulties managed in this simulation are summarized hereafter:

• Targets 3 and 4 appear respectively at time steps 15 and 45. Their respective score functions are initialized at the same time (cf Figure 5).

• Targets 2, 3 and 4 are not detected respectively at time steps 35, 55 and 90. Their score functions adopt a decreasing evolution. It is possible to see that target 2 is deleted at time step 100, when its score function reaches the deletion threshold T 1 . In real life the missing detection can be caused among other things by a remoteness targets or a possible occlusion.

• Target 3 reappeared at time step 69 after a missing detection period, its corresponding score function increases again after a decreasing period. Figure 6 gives an overall view of the global architecture for multi-target tracking which is used in this article. In this figure, "IMM n Update ?", for example, means that target n is updated only if an observation is associated to it, else it is considered as non-detected.

Next section deals with the last step of the global algorithm which is the classification step.

Targets classification

A kinematic data based classification is considered. The problem is firstly studied for a single target problem [START_REF] Ristic | On target classification using kinematic data[END_REF] where the provided solution is based on Bayesian model. Using the credal formalism, the Bayesian solution was then enhanced in [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF]. The idea is based on the discretization of the state space in the IMMs (set of linear models), this allows the characterization of the different behaviors of the different targets types. It is considered that the IMM algorithms contain an exhaustive list of all the possible evolutions models of the considered targets. The list of models is given by:

M = [m 1 , m 2 , ..., m r ] , (17)
where r represents the total number of models.

Based on an a priori knowledge, the different models are clustered so that each group of models corresponds to a specific behavior. Finally, knowing the behavior(s) of a given target, its class can be determined.

The set of possible behaviors can be defined by

B = [b 1 , b 2 , ..., b nb ],
where nb is the number of behaviors. The set of models belonging to behavior b i is defined by M b i ⊆ M, with i = 1, ..., nb. The number of models in M b i is noted by r b i .

As an example, in pedestrian recognition, if the set M contains 5 constant velocity models in an increasing order, the behavior of slowly walking mode can gather the 2 first models, which can correspond to the class of old persons for instance.

Bayesian and credal classification methodologies used in this article are now described in the sequel. Note that for simplicity reasons, targets indices have been removed.

Bayesian classification

Behaviors likelihoods calculation

At each time step k, each IMM provides the a posteriori probability µ j and the likelihood Λ j concerning the r different models m j in M, where j = 1, . . . , r. Models likelihoods for each given target evolution are calculated as follows:

Λ j = exp[-d 2 j /2] (2π) q |S j | , (18)
where d 2 j is a squared Euclidean distance between the j th model predicted measurement ẑ j and its assigned real measurement, it is calculated as in Equation [START_REF] Mercier | Object association with belief functions, an application with vehicles[END_REF], q is the measurement dimension and S j is the j th model expected measurement error covariance matrix.

Once the probabilities and likelihoods of the models are obtained, the clustering described above is adopted to determine the behaviors likelihoods l b i :

l b i = j:m j ∈M b i µ j Λ j , i = 1, ..., nb , (19)
with:

µ j = µ j l:m l ∈M b i µ l , l = 1, ..., r b i . (20)
Based on the already calculated behaviors likelihoods and an a priori probability distribution P(b i |Z k-1 ), the a posteriori probabilities P(b i |Z k ) of the behaviors can be calculated using Bayes inference rule given by Equation [START_REF] Dempster | A generalization of Bayesian inference[END_REF].

In order to calculate probabilities on the set C = {c 1 , c 2 , ..., c nc } of nc possible classes, a projection of the behaviors probabilities on the classes space is realized. This operation is referred to as probabilities conditioning.

Probabilities conditioning

The probabilities conditioning is necessary in the case where the behaviors set B and classes set C are not in one-to-one correspondence. As explained in [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF], the conditioning step can be performed using the following equation:

P(C) = M × P(B), (21)
where P(C) is an nc dimension vector containing the probabilities of C elements, P(B) is an nb dimension vector containing the probabilities of B elements and M is an nc × nb matrix expressing the behaviors and classes relations (conditional probabilities P(c i |b j )). For example, if the slowly walking mode behavior probability is equal to 1, by knowing that a slowly walking person can correspond to an old person or a middleaged person, the conditional probabilities can be expressed by: P(old person|slowly walking mode) = 1/2 and P(middleaged person|slowly walking mode) = 1/2. As it can be remarked, the conditioning step depends on the considered application, therefore more details are provided in the proposed simulation examples in Section 6.

Classification within the TBM

As in the Bayesian classification, the credal classification uses the IMM models probabilities µ j and likelihoods Λ j to calculate behaviors plausibilities computed as behaviors likelihoods in the Bayesian case by:

Pl({b i }) = j:m j ∈M b i µ j Λ j i = 1, ..., nb , (22)
where likelihoods Λ j are calculated using Equation ( 18) and µ j are normalized as in Equation [START_REF] Mercier | Belief functions contextual discounting and canonical decompositions[END_REF]. Once the plausibility Pl({b i }) of each behavior (b i ∈ B) is obtained, mass functions on B can be computed using the Generalized Bayesian Theorem [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the Generalized Bayesian Theorem[END_REF] with Equations ( 10) and [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF]. The Generalized Bayesian Theorem provides a mass function on the behaviors set B. In order to obtain the targets classes, the behaviors mass function has to be projected on the classes space C.

Belief function conditioning

The conditioning step is crucial in the new classification chain when the relation between behaviors and classes are known. In the credal classification method, it is more precise than in the Bayesian case. It transfers mass functions defined on B to mass functions defined on C using the following equation:

m C = M × m B , ( 23
)
where M is a matrix expressing the relations between behaviors and classes, it contains masses m(A|D), with A ⊆ C and D ⊆ B. For example, if m B (slowly walking mode) = 1, the corresponding conditioning for this simple example can be expressed as follows: m({old person, middleaged person}|slowly walking mode) = 1, because, even old and middle-aged persons can walk slowly. This conditioning example illustrates a big difference between belief function and Bayesian models. With belief functions, it is not required to estimate the respective a priori frequencies of the two classes old and middleaged when walking (1/2 with the Bayesian approach).

Decision making

The resulting cumulated mass function m k is supposed having all the available information. In order to make a decision about the tracked targets classes, the cumulated mass function is simply transformed into a pignistic probability using Equation [START_REF] Smets | The Transferable Belief Model[END_REF].

Bayesian and credal classification schemes are respectively illustrated in Figure 7 and in Figure 8. In this simulation, targets dynamic models are chosen in the same manner as those used in the works of Ristic et al. [START_REF] Ristic | On target classification using kinematic data[END_REF], Ristic and Smets [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF], and Caron et al. [START_REF] Caron | Least committed basic belief density induced by a multivariate Gaussian: Formulation with applications[END_REF] which treat the case of a single target tracking and classification problem.

The state vector of all the targets is given by: x = x ẋ y ẏ . It represents the position and the velocity in (x, y) directions. The state vector of each target evolves according to the following equation:

x k = F x k-1 + Bu k + w k , (24)
where:

F =               1 ∆T 0 0 0 1 0 0 0 0 1 ∆T 0 0 0 1               , B =               (∆T ) 2 /2 0 ∆T 0 0 (∆T ) 2 /2 0 ∆T               ,
with ∆T the sampling time. The state noise covariance matrix is taken equal to 0.005(B× B ), where B is matrix B transpose.

Targets measurements are taken according to Equation ( 13), with a measurement noise variance equal to 0.2 and H = 1 0 0 0 0 0 1 0 .

Vector u = a x a y T in Equation ( 24) represents a given acceleration mode. The acceleration limitations for the a priori known targets classes are expressed as follows:

-L i ≤ {a x , a y } ≤ L i , ( 25
)
where L i = 0g, 2g and 4g are respectively the acceleration limits of the classes c 1 , c 2 and c 3 , with g = 9.81 m/s 2 being the gravitational acceleration. The different acceleration modes, in this example, are initially defined in [START_REF] Ristic | On target classification using kinematic data[END_REF]. Their distribution over possible classes are illustrated in Figure 9. Let us denote the set of models in Figure 9 by M = {m 1 , ..., m 13 }. Based on a priori knowledge, the behaviors models sets M b i ⊆ M can be defined. In this example, three different behaviors are defined:

• Behavior 1 (b 1 ) corresponds to targets evolving with constant velocity only (e.g. liners). The models set M b 1 = {m 1 } contains the only model corresponding to a zero acceleration (u = [0 0] T ).

• Behavior 2 (b 2 ) concerns targets evolving with constant velocity and performing medium maneuvers (e.g. bombers). The models set of behavior b 2 is given by: M b 2 = {m 1 , ..., m 5 }, it contains the models whose acceleration is limited to 2g.

• Behavior 3 (b 3 ) is associated to targets evolving with constant velocity and performing both medium and sharp maneuvers (e.g. fighters). Models set of behavior b 3 is given by: M b 3 = {m 1 , ..., m 13 }, it contains all the possible evolution models.

Classes conditioning

Tracked targets are classified according to the set of classes C = {c 1 , c 2 , c 3 } with:

• Class 1 (c 1 ): liners class.

• Class 2 (c 2 ): bombers class.

• Class 3 (c 3 ): fighters class.

Beliefs/probabilities on the set of classes C can be obtained by converting the behaviors beliefs/probabilities using the following relations:

• relation 1: a target with behavior 1 can correspond to a liner, a bomber or a fighter. All of them can evolve with a constant velocity. This relation can be written as:

b 1 = {c 1 , c 2 , c 3 }.
• Relation 2: a target with behavior 2 performs a medium maneuver, may correspond to a bomber or a fighter. Liners are supposed unable to perform any maneuver. This relation can be written as b 2 = {c 2 , c 3 }.

• Relation 3: a target in behavior 3 performs a sharp maneuver, it can only be a fighter, because liners and bombers can not perform sharp maneuvers. This relation can be written as b 3 = {c 3 }.

For the Bayesian classification task, the conditioning is performed using the Equation [START_REF] Delmotte | Detection of defective sources in the setting of possibility theory[END_REF], according to the relations above. The corresponding conditioning matrix M is given by:

M =           1/3 0 0 1/3 1/2 0 1/3 1/2 1           .
which corresponds to the following conditions:

• if P(b 1 ) = 1 =⇒ P(c 1 |b 1 ) = 1 3 , P(c 2 |b 1 ) = 1 3 , P(c 3 |b 1 ) = 1 3 . • If P(b 2 ) = 1 =⇒ P(c 1 |b 2 ) = 0, P(c 2 |b 2 ) = 1 2 , P(c 3 |b 2 ) = 1 2 . • If P(b 3 ) = 1 =⇒ P(c 1 |b 3 ) = 0, P(c 2 |b 3 ) = 0, P(c 3 |b 3 ) = 1.
For the credal classification, a different conditioning is made following Equation [START_REF] Benavoli | Classification with imprecise likelihoods: A comparison of TBM, random set and imprecise probability approach[END_REF]. It transfers beliefs expressed on the set of behaviors B to the set of classes C such that:

• m k ({c 1 , c 2 , c 3 }|b 1 ) = 1 (cf Relation 1) • m k ({c 2 , c 3 }|b 2 ) = 1 (cf Relation 2) • m k ({c 1 , c 2 , c 3 }|{b 1 , b 2 }) = 1 (cf Relations 1 and 2) • m k (c 3 |b 3 ) = 1 (cf Relation 3) • m k ({c 1 , c 2 , c 3 }|{b 1 , b 3 }) = 1 (cf Relations 1 and 3) • m k ({c 2 , c 3 }|{b 2 , b 3 }) = 1 (cf Relations 2 and 3) • m k ({c 1 , c 2 , c 3 }|{b 1 , b 2 , b 3 }) = 1 (cf Relations 1, 2 and 3)
The corresponding complete conditioning matrix M has a size (2 3 = 8) × (2 3 = 8), and is given by:

M =                                   
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1

                                   .
Belief conditioning, in this example is similar to those performed in [START_REF] Smets | Kalman filter and joint tracking and classification based on belief functions in the TBM framework[END_REF] for single target classification. This matrix enables to compute the mass functions on the classes space C in order to perform the credal classifications. In this scenario, 4 targets are involved and perform some maneuvers in (x, y) space. Measurements and estimations are presented in Figures 10 and11.

Simulation results

For example, it can be noticed that targets 3 and 4 respectively appear at time steps 30 and 70.

Target 2 evolves firstly with a constant velocity in order to minimize fuel use and then performs two maneuvers: a first medium acceleration in x direction during time period 50-54, and a sharp deceleration during time period 70-75. Finally it disappears at time step 100. The algorithm continues to predict its trajectory until the end of the simulation at time step 120 because its score function has not yet reached the deletion threshold.

According to this scenario, a full ignorance is expected on the true class of target 2 before its first medium maneuver (as it has only flown with a constant velocity), then a complete doubt between the bomber and fighter classes is expected after the first medium maneuver and before the sharp maneuver. Finally after this second maneuver, only the fighter class remains possible.

The evolution of target 2 behaviors likelihoods and probabilities are, respectively, presented in Figures 12 and13. These results correspond to averages of 20 Monte Carlo simulations. Behaviors likelihoods/plausibilities are calculated using Equation [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF] (or [START_REF] Smets | What is Dempster-Shafer's model[END_REF]). It can be remarked that the likelihood/plausibility of behavior b 1 drops to zero during the two performed maneuvers and the likelihood/plausibility of behavior b 2 drops to zero during the sharp maneuver.

More significantly, it can be observed that during the period of time preceding the first maneuver the likelihood/plausibility of behavior b 1 is slightly more important than the likelihoods/plausibilities of behaviors b 2 and b 3 . As a consequence, it can be seen in Figure 13 that during this same period of time before the first maneuver, the probability corresponding to behavior b 1 tends to grow while all behaviors are supposed to be equally probable.

This deviation is due to the fact that as the behaviors are nested (b 1 ⊂ b 2 ⊂ b 3 ) and behavior b 1 is composed of the least number of models (only m 1 ), its likelihood during the period of constant velocity is less influenced by non-concerned models unlike behaviors b 2 and b 3 . Formally it can be observed from Equation [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF]. The same explanation can be adopted after the second maneuver where b 2 is also unjustifiably advantaged over b 3 because the number of models in behavior b 2 is less than the number of models in behavior b 3 .

Figure 13 is based on Bayes rule and does not concern the credal classification. The conditioning operations described above are used to correct such an issue. Using Bayesian conditioning on the behaviors probabilities in Figure 13, classes probabilities are obtained as shown in Figure 14. It can be seen that, even if the target is finally classified as a fighter (which is the truth), the Bayesian classifier fails in doubt situations. On the other hand, the pignistic probabilities derived from the conditioned classes mass function, given in Figure 15, shows that the credal classifier succeeds to manage the imprecisions on behaviors and classification results are as expected.

It can also be mentioned that after time step 100, when target 2 is not detected, the behaviors likelihoods are still constant because the target is updated with its predicted measurement. In the non-detection time, the classifiers (Bayesian and credal) still believe that target 2 is a fighter.

Results presented in this section shows therefore that the credal model improves the Bayesian classification results obtained in [START_REF] Ristic | On target classification using kinematic data[END_REF]. They also illustrate the strength of the credal classification in a multi-target context by assuming that each target is at each time updated with its corresponding measurement.

Influences on the classification of false assignments are presented in Section 6.2.

Tracking and classification of nearby targets

The problem of crossing and nearby targets is addressed in this section which aims at studying the robustness of the tracking algorithm, especially the assignment step ensured here by the generalized GNN algorithm.

Case of two targets evolving very closely

The extreme situation of two targets evolving very closely is considered. The goal is to measure the rate of false assignments by varying sensor noise variance. In this simulation, sensor noise varies from 0% to 200% of the distance between the two targets. For each value of noise variance, an average value, of the false assignments rate on 100 Monte Carlo simulations, is calculated. Results are presented in Figure 16. It can be observed that the rate of false assignments is relatively low even for an extreme scenario of targets evolving closely and sensor noise exceeding the distance between the targets.

The false assignment rate would be more important if the measurements were assigned to the targets estimates of time step k -1. The capacity of the IMMs to predict the expected measurements of the targets at time step k allows the reduction of the false assignment rate.

Case of a fighter crossing an unknown target and evolving closely

In this section, a simple scenario is considered to illustrate what can be the impact of false assignments on the proposed multi-target classification. A fighter and an unknown aircraft evolve in (x, y) space according to the previously described models. Figure 17 illustrates the time evolution of the targets according to the y direction (the scenario is the same in x direction). Targets pass each other and then evolve closely. The same figure shows the false assignment happened at time step 38. The influence of this false assignment on the two targets classifications is presented in Figure 18. Note that in this example, during all the surveillance period, target 2 evolves only with a constant velocity while target 1 starts its movement with a constant velocity and makes two strong maneuvers, namely, acceleration and deceleration around time steps 23 and 35. Given this information, target 1 is expected to be classified as a fighter (class c 3 ) after its strong maneuvers, and a perfect doubt concerning the classification of target 2 is expected.

Figure 18 gives the credal classification results of targets 1 and 2 respectively. As expected, it can be seen that target 1 is correctly classified as a fighter after its first strong maneuver and its classification is not influenced by the false assignment occurred at time step 38 (a target classified in the third class can not be brought into doubt). On the other hand, it can be seen that the false assignment at time step 38 This article is focused on the classification stage, so only a simple assignment algorithm is used, i.e. the GNN algorithm. It could be replaced by any advanced assignment algorithm like JPDA and MHT to overcome such problem of conflicting situations. Some credal solutions [START_REF] Mercier | Object association with belief functions, an application with vehicles[END_REF][START_REF] Zoghby | Optimal object association from pairwise evidential mass functions[END_REF][START_REF] Megherbi | Multimodal data association based on the use of belief functions for multiple target tracking[END_REF][START_REF] Ayoun | Data association in multi-target detection using the Transferable Belief Model[END_REF][START_REF] Lemeret | Improvement of an association algorithm for obstacle tracking[END_REF][START_REF] Daniel | Multi-object association decision algorithms with belief functions[END_REF] can also be integrated to overcome the problem tackled in this section. This would enhance the results of the proposed classification strategy. This section proposes a classification problem concerning pedestrian activity recognition. The structure of the dynamical models is close to the one used in the previous aircraft tracking example. Indeed, this example is designed to be interesting, not for the tracking issue, but for the classification stage.

However, compared to the previous examples based on aircraft targets, two important differences are introduced. First, two classes of pedestrians are considered. They contain a common pedestrian behavior and a distinct one (there is no relation of strict inclusion as in the aircraft example). Secondly, pedestrians classes are not constant over time which conducts to a different classification problem.

With slight adaptations, the credal classification algorithm is shown to provide correct results, demonstrating that the methodology presented in this article can be applied to a wide variety of applications. As in the former example, the state vector consists in the position and velocity on x and y directions. The dynamical model is given by:

x k = A(s x , s y )x k-1 + w k , (26)
with:

A(s x , s y ) =               1 s x ∆T 0 0 0 1 0 0 0 0 1 s y ∆T 0 0 0 1              
, where s x and s y represent the targets speeds (meter/second) according to x and y directions, respectively. According to different values of s x and s y , a set M = {m 1 , m 2 , ..., m 7 } of 7 different models are designed and used by each target IMM to track its movement. Pedestrians behaviors are defined according to the set of models M as follows:

• behavior 1 (b 1 ) corresponds to the static mode. Behavior 1 models set is given by: M b 1 = {m 1 }, where m 1 corresponds to the matrix A(s x , s y ) with, (s x , s y ) = (0, 0).

• Behavior 2 (b 2 ) corresponds to a walking mode. 2 models set is given by: M b 2 = {m 2 , m 3 , m 4 }, it corresponds to the speed models (s x , s y ) = {(2, 0), (0, 2), (2, 2)}.

• Behavior 3 (b 3 ) corresponds to a running mode. Behavior 3 models set is given by: M b 3 = {m 5 , m 6 , m 7 }, it corresponds to the speed models (s x , s y ) = {(6, 2), (2, 6), (6, 6)}.

Classes conditioning

According to the behaviors described above, the problem consists in distinguishing among the pedestrians, the ramblers and the sportsmen. This means to decide on the set C = {c 1 , c 2 } which corresponds to C = {ramblers, sportsmen}. The conditioning step in this example is done according to the following relations:

• Relation 1: ramblers with static and walking behaviors (c 1 = {b 1 , b 2 }).

• Relation 2: sportsmen with walking and running behaviors (c 2 = {b 2 , b 3 }).

These relations show that the two classes are overlapping. Both ramblers and sportsmen can adopt a walking mode. It is supposed that sportsmen do not stay static and ramblers do not run.

In order to obtain a mass function on the classes space, a mass function on behaviors space B is conditioned according to Equation ( 21), with a matrix M expressing the following conditions from Relations 1 and 2:

• m k (c 1 |b 1 ) = 1 • m k ({c 1 , c 2 }|b 2 ) = 1 • m k ({c 1 , c 2 }|{b 1 , b 2 }) = 1 • m k (c 2 |b 3 ) = 1 • m k ({c 1 , c 2 }|{b 1 , b 3 }) = 1 • m k ({c 1 , c 2 }|{b 2 , b 3 }) = 1 • m k ({c 1 , c 2 }|{b 1 , b 2 , b 3 }) = 1
The complete conditioning matrix M transforms the belief mass on power set 2 3 of three behaviors on a power set 2 2 of two classes, it is given as follows:

M =              
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 1

              .
This conditioning provides a mass function on classes set C which is used to classify pedestrians as explained in credal classification section.

Simulation results

An example including two pedestrians is provided. Pedestrians evolve in (x, y) space. Pedestrians time evolutions according to y direction are exposed in Figure 19. Evolutions in x direction are identical. Pedestrian 1 first walks, then runs and then stops. It is then expected that after a doubt, Pedestrian 1 should be classified as a sportsman and after that as a rambler.

As this is shown in Figure 20, the standard classification algorithm described in Section 5.2 fails. In fact, it cannot even compute the pignistic probabilities after time step 120. This is due to the fact that the class of pedestrian 1 has converged to a sportsman, and suddenly at time step 120 the likelihoods are associated to another class, and there is an absolute conflict between the two belief masses in Equation [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF]. The credal classification algorithm exposed in Section 5.2 is not adapted for time varying classes. More generally, a discounting of both belief functions could be introduced simultaneously, with optimization of the discounting factors λ i , according to the dynamics of the targets classes and other factors. The fusion rule could also be changed. But these parameters would be very application dependent, and they cannot be studied further in this article.

To conclude this section, the pedestrian example shows that the standard algorithm proposed here can serve as a basis for more complex problems, since it can be adapted easily to handle various situations while providing satisfactory results.

Conclusion

Multi-target classification is a fundamental problem, when it comes to classify multiple targets simultaneously. It is much more complex than the single target classification problem, and even more when targets randomly appear and disappear for various reasons.

This article presents a solution for multi-target classification with belief functions exploiting the results provided by Interacting Multiple Model (IMM) algorithms in charge of the tracking of the targets. Including the generalized Global Nearest Neighbor (GNN) algorithm to solve assignment problems and a score function to handle targets appearances and disappearances, this full complete scheme for multi-target tracking and classification has been tested on two different kind of examples: one with constant class targets and one with time varying class targets. It has been shown that the full algorithm using belief functions outperforms standard Bayesian classifiers in both situations.

In future work, tests of the credal classification may be undertaken by replacing any elementary component of the decision chain by a more advanced one. For example, the tracking task can be handled by PHD or particular filters and in the same way the assignment task can be ensured by other solutions like JPDA, MHT and so on.

More deep investigations on time varying classes may be realized (for example, the automatic computation of the discounting rate). Likewise, the assignment problem

Figure 1 :

 1 Figure 1: Kalman filter vs Particle filter.

Figure 2 :

 2 Figure 2: Illustration of a single target classification task with a Bayesian approach.

Figure 3 :

 3 Figure 3: Illustration of the assignment question in a 2-target classification task.

Figure 4 :

 4 Figure 4: y-direction evolutions over time of 4 targets.

2 Figure 5 :

 25 Figure 5: Targets score functions.

Figure 6 :

 6 Figure 6: Multi-target tracking algorithm architecture.

Figure 7 :

 7 Figure 7: Bayesian classification.Figure 8: Credal classification.

Figure 8 :

 8 Figure 7: Bayesian classification.Figure 8: Credal classification.

Figure 9 :

 9 Figure 9: Acceleration modes over targets classes (standard example initially studied in [6] for a single target classification).

Figure 10 :

 10 Figure 10: Targets measurements and estimations on x and y positions.

Figure 11 :

 11 Figure 11: Targets measurements and estimations on x positions over time.

Figure 12 :

 12 Figure 12: Behaviors likelihoods/plausibilities of target 2.

Figure 13 :

 13 Figure 13: Behaviors probabilities of target 2.

Figure 14 :

 14 Figure 14: Target 2 Bayesian classification (after conditioning).

Figure 15 :

 15 Figure 15: Target 2 credal classification.

  0

Figure 16 :

 16 Figure 16: Rate of false assignments of GNN algorithm for two closely moving targets, with different sensor noise values.

Figure 17 :

 17 Figure 17: False assignment of the measurements of a fighter and an unknown aircraft.

Figure 18 :

 18 Figure 18: Credal classification results of two crossing targets: target 1 (on the left) and target 2 (on the right).

6. 3 .

 3 Pedestrians tracking and classification example 6.3.1. Description

Figure 22 :

 22 Figure 22: Cumulative belief (m k-1 ) discounting, with λ = 0.9.

Figure 23 :

 23 Figure 23: Instantaneous belief (m k ) discounting, with λ = 0.9.

Table 1 :

 1 1 D 2,2 . . . D 2,n ∞ General formulation of the assignment matrix.

	T	. . . ∞

Acknowledgement

The authors are very grateful to the anonymous reviewers for their valuable comments, which have helped them to improve the clarity and the quality of this article.

A simple solution to enable classification of such targets consists in adding a discounting operation of the instantaneous belief m k (.|z) in Equation [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF], which is obtained from the likelihoods and the Generalized Bayesian Theorem, before applying the conjunctive fusion rule. This way the conflict is lowered between old and new beliefs, and there is an adaptation of the inferred classes. This discounting phase, performed as described in Equation ( 7) with a value of λ = 0.3 (chosen small enough to provide smooth and slow transitions) allows the classifier to follow the pedestrian class even if it changes in time, as shown in Figure 21.

Let us also note that discounting the a priori belief m k-1 , in Equation ( 11), instead of m k (.|z) deduced from the GBT also enables to obtain a correct result, but only for a given time. Indeed, the likelihoods are favored in that scheme. They are associated to the doubt if the sportsman starts to walk again, depending on λ. Thus, sooner or later, the classification of pedestrian 1 converges to a doubt again. In Figures 22 and23, the previous simulation is continued so that a walking mode appears near time step 240. These figures show the differences in the classifications outputs based on the two distinct discountings. may be developed with belief functions.