Kamel Mekhnacha
email: kamel.mekhnacha@probayes.com

Yong Mao
email: yong.mao@inrialpes.fr

David Raulo

Christian Laugier

Bayesian occupancy filter based "Fast Clustering-Tracking" algorithm

It has been shown that the dynamic environment around the mobile robot can be efficiently and robustly represented by the Bayesian occupancy filter (BOF) [1]. In the BOF framework, the environment is decomposed into a gridbased representation in which both the occupancy and the velocity distributions are estimated for each grid cell. In such a representation, concepts such as objects or tracks do not exist and the estimation is achieved at the cell level. However, the object-level representation is mandatory for applications needing high-level representations of obstacles and their motion.

To achieve this, a natural approach is to perform clustering on the BOF output grid in order to extract objects. We present in this paper a novel clustering-tracking algorithm. The main idea is to use the prediction result of the tracking module as a form of feedback to the clustering module, which reduces drastically the complexity of the data association. Compared with the traditional joint probabilistic data association filter (JPDAF) approach, the proposed algorithm demands less computational costs, so as to be suitable for environments with large amount of dynamic objects. The experiment result on the real data shows the effectiveness of the algorithm.

I. INTRODUCTION

Perceiving of the surrounding physical world reliably is a major demanding of the driving assistant systems and the autonomous mobile robots. The dynamic environment need to be perceived and modeled according to the sensor measurements which could be noisy. This problem is normally treated within the estimation framework. The major requirement for such a system is a robust target tracking system. Most of the existing target tracking algorithms [START_REF] Shalom | Tracking and Data Association[END_REF] use an object-based representation of the environment. However, these existing techniques have to take into account explicitly data association and occlusion problems which are major challenges of the performances. In view of these problems, a grid based framework, the Bayesian occupancy filter (BOF) [START_REF] Tay | An Efficient Formulation of the Bayesian Occupation Filter for Target Tracking in Dynamic Environments[END_REF] [3] [START_REF] Coue | Bayesian occupancy filtering for multitarget tracking: an automotive application[END_REF] has been presented in our previous works.

In the BOF framework, concepts such as objects or tracks do not exist. It decompose the environment into a grid based representation. A Bayesian filter [START_REF] Thrun | Probabilistic robotics[END_REF] based recursive prediction and estimation paradigm is employed to estimate an occupancy probability and a velocity distribution for each grid cell. Thanks to the grid decomposition, the complicated data association and occlusion problems do not exist. The BOF is extremely convenient for applications where no object-level representation is needed. Another advantage of the BOF is that the multiple sensor fusion task could be easily achieved. In some situations, using information from multiple sensors could provide more reliable and robust information of the environment. However, in traditional multiple sensor fusion techniques, data association problem could be further complicated. The associations between the two consecutive time instances from the same sensor as well as the associations among the tracks of different sensors will have to be take into account at the same time. Fortunately, these difficulties do not exist in the grid based approaches [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF] which deal with the data association problems in a more feasible way. Uncertainties of multiple sensors are specified in the sensor models and are fused into the BOF grid naturally with solid mathematical ground. Despite of the aforementioned advantages, a lot of applications demand the explicit object-level representation. In our former work, we suggested a layer structure for these systems. A joint probabilistic data association filter (JPDAF) [START_REF] Shalom | Tracking and Data Association[END_REF] based object detecting and tracking method was implemented above the BOF layer. However, when there are enormous amount of dynamic objects in the environment, the number of hypothesises generated by the JPDAF increases rapidly, which makes the method suffers from the computational cost. Regarding to this problem, a novel fast object detecting and tracking algorithm is proposed. A simple and naive clustering algorithm is used to extract objects from the BOF grid. By taking the prediction result of the tracking module as a form of feedback to the clustering module, the clustering algorithm avoids searching in the entire grid which guarantees the performance. A re-clustering and merging strategy is employed only when the ambiguous data association occurs. The computational cost of this approach is linear to the number of dynamic objects detected, so as to be suitable for scenes in cluttered environment. Our approach has been tested on the real data collected on real cars in highway and cluttered urban environments (Fig. 1), and also on our Cycab experimental platform (Fig. 2).

In classical tracking methodology [START_REF] Shalom | Tracking and Data Association[END_REF], the problem of data association and state estimation are major problems to be addressed. The two problems are highly coupled with each other and an error in either portion leads to erroneous outputs. The BOF makes it possible to decompose this highly coupled relationship by avoiding the sensor data association problem, in the sense that data association is to be handled at a higher level of abstraction.

We propose to use a hierarchical approach in which two filtering levels are used (Fig. 3):

(i) Robust grid-level sensing.

(ii) Robust object-level tracking. In a such architecture, the output grid of the BOF grid filter (i.e, the probability distribution on the occupancy of the cell, and the probability distribution on the velocity of the cell occupancy) is used as input for the object tracker by extracting object hypothesis from the grid (Fig. 3).

The paper is organized as follows. In the next section, the BOF framework is briefly described. The object detecting and tracking approach is presented in section III. In section IV, the experimental result of our approach on the real data collected by the Cycab platform is provided. Finally, conclusions are drawn in section V.

II. BAYESIAN OCCUPANCY FILTER (BOF)

The Bayesian Occupancy Filter (BOF) is represented as a two dimensional planar grid based decomposition of the environment. Each cell of the grid contains two probability distributions. A probability distribution on the occupancy of the cell, and the probability distribution on the velocity of the cell occupancy.

Given a set of input sensor readings, the BOF algorithm allows to update the occupancy/velocity estimates of each grid cell.

BOF is a special implementation of the Bayesian filter approach [START_REF] Jazwinsky | Stochastic Processes and Filtering Theory[END_REF]. This approach addresses the general problem of recursively estimating the probability distribution, P(X k | Z k ), of the state X of a system conditioned on its observation Z. This expression is also known as the posterior distribution. The posterior distribution is obtained in two stages: prediction and estimation. The prediction stage computes an a priori prediction of the target's current state known as the prior distribution. The estimation stage then computes the posterior distribution by using the prediction with the current measurement of the sensor.

In the case of the BOF, using this prediction/estimation scheme allows filtering out false alarms, miss-detections, and localization errors in sensors data readings. Figure 1 shows an example of BOF output using a computer vision car detector. The input of the BOF in this case is, for each time step, a set of bounding boxes corresponding to the detected vehicles (red boxes). The output represents a grid of occupancy probability (blue-to-red mapped color) and mean velocity (red arrows) estimates.

The Bayesian model presented in the following text is a reformulation of the one we presented in [START_REF] Tay | An Efficient Formulation of the Bayesian Occupation Filter for Target Tracking in Dynamic Environments[END_REF]. The aim of this reformulation is to make clearer the strong link between the discretization of the space and the discretization of the velocity, which reduces the number of the used random variables and makes the model easier to explain.

The key idea of the model is to represent the 2D space using a regular grid. Given this space discredization and assuming that objects do not overlap, the velocity of a given c cell at a time t is directly linked to the identity of its antecedent cell A c from which the content of cell c moved between t -1 and t. In other words, we can define the velocity of a given cell by providing the index of its antecedent.

Therefore, estimating the velocity of a given cell is equivalent to estimating a probability table over its all possible antecedents. Possible antecedents of a cell are defined by providing a neighbourhood from which the cell is reachable in a time step. This model applies also to velocities needing more than one time step for a neighbour cell to reach c. However, for simplicity we will assume only one-step velocities (neighbours reaching c in one time step).

The BOF model is described as follows:

A. Variables

For a given cell having c ∈ Y as index in the grid, let:

• A t c ∈ A c ⊂ Y represents each possible antecedent of cell c over all the cells in the grid domain Y . The set of antecedent cells of cell c is denoted by A c and is defined as a neighbourhood of the cell c.

• A t-1 c ∈ A c ⊂ Y is same as A t c but for the previous time step. • O t c ∈ O ≡ {0
, 1} is a boolean variable representing the state of the cell in terms of occupancy at time t, either

[O c = 1] if occupied, [O c = 0] if empty.
Given the independency hypothesis, the occupancy of each cell at time t is considered apart from the occupancy of its neighbouring cells at time t.

• Z t i ∈ Z , 1 ≤ i ≤ S ∈ N
, is a generic notation for measurements yielded by each sensor i, considering a total of S sensors yielding a measurement at the considered time instant.

B. Joint distribution factors

The following expression gives the decomposition of the joint distribution of the relevant variables according to Bayes' rule and dependency assumptions:

P(A t-1 c A t c O t c Z t 1 • • • Z t S ) = P(A t-1 c )P(A t c | A t-1 c )P(O t c | A t-1 c ) S ∏ i=1 P(Z t i | A t c O t c ). (1)
The parametric form and semantics of each component of the joint decomposition are as follows:

• P(A t-1 c ) is the probability for a given neighbouring cell A c to be the antecedent of c at time t -1. In order to represent the fact that cell c is a priori equally reachable from all possible antecedent cells in the considered neighbourhood, this probability table is initialized as uniform and is update in each time step.

• P(A t c | A t-1 c
) is the distribution over antecedents at time t given the antecedent of cell c at t -1. It represents the prediction (dynamic) model over velocity. If we assure a perfect constant velocity hypothesis between the two time frames t -1 and t, this distribution is just:

P(A t c | A t-1 c ) = P(A t-1 A t-1 c
).

In other words, the predicted probability is just the probability at the preceding time instant for the antecedent at t -1.

Considering imperfect constant velocity hypothesis may be done by introducing:

-E ∈ {0, 1} ≡ "There was a prediction error", -P(E) = ε the probability of violating the constant velocity hypothesis (a parameter of the model). If we define:

-P(A t c | A t-1 c ¬E) = P(A t-1 A t-1 c ), -P(A t c | A t-1 c E) = U (A t c ):
Uniform predicted antecedent (velocity) when constant velocity hypothesis is violated, then, P(A t c | A t-1 c ) may be written as a mixture:

P(A t c | A t-1 c ) = P(¬E)P(A t c | A t-1 c ¬E) + P(E)P(A t c | A t-1 c E)
Which leads to:

P(A t c | A t-1 c ) = (1 -ε)P(A t-1 A t-1 c ) + ε U (A t c ) = (1 -ε)P(A t-1 A t-1 c ) + ε/ A c . • P(O t c | A t-1 c
) is the distribution over occupancy given the antecedent of cell c at t -1. It represents the prediction (dynamic) model over occupancy. If we assure a perfect constant velocity hypothesis between the two time frames t -1 and t, this distribution is just:

P(O t c | A t-1 c ) = P(O t-1 A t-1 c
).

In other words, the predicted probability is just the probability at the preceding time instant for the antecedent at t -1.

When considering imperfect constant velocity hypothesis, P(O t c | A t-1 c ) may be written as a mixture:

P(O t c | A t-1 c ) = P(¬E)P(O t c | A t-1 c ¬E) + P(E)P(O t c | A t-1 c E)
Which leads to:

P(O t c | A t-1 c ) = (1 -ε)P(O t-1 A t-1 c ) + ε U (O t c ) = (1 -ε)P(O t-1 A t-1 c ) + ε/2. • P(Z t i | A t c O t c
) is the direct model for sensor i. It yields the probability of a measurement given the occupancy O t c and the antecedent (velocity) A t c of cell c. Measurements for all sensors are assumed to have been taken independently from each other. For sensors providing measurements depending exclusively of occupancy, this distribution can be written as

P(Z t i | O t c
). In the same manner, for sensors providing measurements depending exclusively of velocity, this distribution can be written as

P(Z t i | A t c ).

C. Occupancy and velocity estimation using the BOF model

At each time step, the estimation of the occupancy and velocity of a cell is answered through Bayesian inference on the model given in Equation ( 1). This inference leads to a Bayesian filtering process (Fig. 4). In this context, the prediction step propagates cell occupancy and antecedent (velocity) distributions of each cell in the grid the get the prediction P(O

(O t c A t c | [Z t 1 • • • Z t S ]
). This allows by marginalization to compute

P(O t c | [Z t 1 • • • Z t S ]) and P(A t c | [Z t 1 • • • Z t S ]
) that will be used for prediction in the next iteration.

It's important to notice that the distribution P(A t c ) over velocity is updated even when no velocity sensors are available. Indeed, suppose we have only one occupancy sensor described by the model

P(Z t OCC | O t c ). The a posteriori distribution P(A t c | [Z t OCC ]
) leads to the formula:

P(A t c | [Z t OCC ]) ∝ (2)
∑ A t-1 c ∈A c P(A t-1 c )P(A t c | A t-1 c ) ∑ O t c ∈{0,1} P(O t c | A t-1 c )P([Z t OCC ] | O t c ).
This allows to update the velocity distribution even when no velocity sensors are available. In this case, the update is based exclusively on the occupancy observations. When an additional velocity sensor

P(Z t VEL | A t c
) is available, it should be used to update the estimate (2) as follows:

P(A t c | [Z t OCC Z t VEL ]) ∝ P(A t c | [Z t OCC ])P([Z t VEL ] | A t c ).

III. THE "FAST CLUSTERING-TRACKING" ALGORITHM

In many applications, the object-level representation are demanded. We propose to use a layer architecture as shown in Fig. 3 to obtain this representation. In our former work [START_REF] Tay | An Efficient Formulation of the Bayesian Occupation Filter for Target Tracking in Dynamic Environments[END_REF], the object-level presentation is obtained by a classical JPDAF algorithm. However, in the cluttered environment with enormous moving objects, the JPDAF suffers from the combinational explosion of hypothesises. To overcome this problem, we propose a novel object detecting and tracking algorithm. This algorithm could be roughly divided into a clustering module, an ambiguous association handling module and a tracking and track management module.

A. Clustering

The clustering module takes the occupancy/velocity grid of the BOF as the input and extracts object level reports from it. A natural algorithm to achieve this is to connect the eight-neighbor cells according to an occupancy threshold occ threshold. In addition to the occupancy values, a threshold of the Mahalanobis distance between the velocity distributions vel threshold is also employed to distinguish the objects that are close to each other but with different moving velocities.

From the implementation point of view, we use an ID grid with the same scale of the input occupancy/velocity grid to store the IDs of the associated targets. The ID grid value is initialized to zero(non-associated) and then is set to the ID of the associated target. In order to avoid searching for clusters in the whole grid, we use the predicted targets' states as a form of feedback. For a given target with ID id, the predicted state is used to define a region of interest (ROI) in which the clustering process starts. After a starting point with an occupancy probability value greater than the occ threshold is found in the ROI, the id is propagated in the ID grid using the connectivity criterion among the non-associated cells (cells with ID = 0).

A report for the tracker is a 4-dimentional observation corresponding to the position and the velocity of an extracted cluster.

The 2D position component of this vector is computed as the mass center of the region corresponding to the cluster pixels (cells) set. We also compute the corresponding covariance matrix representing the uncertainty of the observed position.

The 2D velocity component is just the weighted mean of the estimated velocities of all cells of the cluster. It comes also with a covariance matrix representing the uncertainty of the observation velocity.

B. Re-clustering and tracks merging

During the clustering process, three possible situation need to be considered.

• case 1: no cell with P(occ = 1) ≥ occ threshold is found. The target has not been observed and no association is needed. • case 2: a cluster C of non-associated cells having ∀c(i, j) ∈ C, P(occ(i, j) = 1) ≥ occ threshold is extracted. These cells are then associated to the target id: ∀c(i, j) ∈ C, ID(i, j) = id, where ID(i, j) is the corresponding ID grid. This situation occurs when there is no ambiguity in the association. This is an advantageous situation allowing a fast clustering-association procedure. Fortunately, this case is the most frequent one when using the algorithm to the real data sets. • case 3: cells having P(occ(i, j) = 1) ≥ occ threshold exist. However, they have already been assigned to other IDs. In this conflicted case, an observation (cluster) could be possibly generated by two (or more) different targets. The first two cases are normal cases, however, the third case is refered as an ambiguous association case which need to be dealt with in a special manner. The ambiguous association could occur in the following two situations :

• Different targets are being too close to each other and the observed cluster is in fact the union of the more than one observations generated by different targets. • The different tracked targets are corresponding to a single object and should be merged into one. We take a re-clustering strategy to deal with the first situation and a cluster merging strategy to deal with the second one.

Suppose when an ambiguous association occurs, a set of tracks T 1 , T 2 , • • • , T m are the potential candidates to be associated to the the observed cluster. We have to cut up the extracted cluster and generate a sub-cluster (possibly empty) for each candidate. This re-clustering is achieved by a kmeans [START_REF] Bishop | Pattern recognition and machine learning[END_REF] algorithm using a simple Cartesian distance. The considered distance is taken between the center of the subcluster and a given cell. In this way, the first cause of the ambiguous association is handled.

To deal with the second cause of the ambiguous association, we introduce a concept of "alias" which is in the form of a two-tuples to represent the duplicated tracks. When an ambiguous association between two tracks T i and T j is detected, an alias ALIAS(T i , T j ) is initialized and added to a potential alias list.

At each frame, the tracker updates this list by confirming or disproving the existence of each alias hypothesis ALIAS(T i , T j ) according to the observation of the ambiguous association.

At a given time step t, if the ambiguous association occurs between T i and T j , and the alias ALIAS(T i , T j ) is found in the potential alias list, the probability P t (S(T i , T j )) is updated by a confirming step using a Bayesian filtering approach as follows:

P t (S | F) = P t-1 (S) × P(F | S) P t-1 (S) × P(F | S) + [1 -P t-1 (S)] × P(F | ¬S)
where:

• S ≡ "the T i and T j tracks are alias for the same object".

• F ≡ "an ambiguous association between the tracks T i and T j is observed". The probability values P(F | S) and P(F | ¬S) are constant parameters of the tracker. The former denotes the probability of observing an ambiguous association when the two concerned tracks are alias of the same object and is set to a constant value 0.8. The second denotes the probability of falsely observing an ambiguous association and is set to 0.1.

When ALIAS(T i , T j ) is found in the potential alias list but is not observed as an ambiguous association, its probability is disproved in a similar manner:

P t (S |¬F) = P t-1 (S) × P(¬F | S) P t-1 (S) × P(¬F | S) + [1 -P t-1 (S)] × P(¬F | ¬S)
Then, according to the probability P t (S(T i , T j )), the decision of merging of tracks T i and T j could be made.

C. Tracks creation

For new targets creation, we introduce a concept "cluster seed" to define a cell in the BOF grid where we will try to find, for each step, a new (non-associated) cluster. Indeed, the searching for potential new targets is after all the existing tracks are processed. Thus, only non-associated cells will be processed to extract clusters as the observations for the potential new targets. The "cluster seed" concept is general and can be implemented via various strategies. The simplest strategy is to insert a possible seed in each cell of the grid. However, more sophisticated strategies could be more efficient. For example, cluster seeds could be inserted only in entrance regions of the monitored area.

D. Tracks deleting

The deleting of tracks is also achieved in a Bayesian manner. If an existing track T is associated with a given report (cluster), its existence probability is increased using the following formula:

P t (E | O) = P t-1 (E) × P(O | E) P t-1 (E) × P(O | E) + [1 -P t-1 (E)] × P(O | ¬E)
where:

• E ≡ "the target T exists".

• O ≡ "the target T has been observed (associated)". The parameters P(¬O | E) and P(O | ¬E) are the tracker miss-detections and false alarms probabilities respectively.

If an existing target is not associated with any report (cluster), its existence probability is decreased in the similar way:

P t (E | ¬O) = P t-1 (E) × P(¬O | E) P t-1 (E) × P(¬O | E) + [1 -P t-1 (E)] × P(¬O | ¬E)
According to the existence probability, the track deleting operation is achieved by applying a deleting threshold on it. However, in order to increase the robustness for occlusions, we also introduce an occlusion calculation procedure. It allows us to decide if a given target is possibly occluded or not. If the target is regarded as being occluded, its existence probability is not decreased even if no observation is associated to it. As a consequence, the target will be kept for longer time without being observed.

E. Tracks updating

In our work, the prediction and estimation of the targets are accomplished by attaching a Kalman filter with each track. Once associated to a given track, a report (Gaussian distributions for both position and velocity) corresponding to an extracted cluster is used as an observation to re-estimate the position and velocity of the track in a prediction-update step. For non-observed tracks, only a prediction step is taken by applying the dynamic model to the estimation result of the precedent time step.

IV. EXPERIMENTAL RESULT

The proposed approach has been applied in several driving assistance projects and achieved satisfied results in conditions including both highway and cluttered urban environments. The used sensor modalities include:

• multi-layer lidars,

• Computer Vision detection algorithms (Fig. 1),

• Stereovision-based 3D sensors.

However, according to the confidentiality agreements of the on-going projects, the results could not be published. Here, we provide some recent experiment results on our Cycab platform.

The Cycab platform is equipped with SICK lidar, GPS, mono-camera and odometer. To demonstrate the accuracy of the tracking algorithm, we used several GPS which are carried by pedestrians or vehicles. Because the experiments were carried out in the parking area of Inria Rhone-Alpes, within this limited range, the precision of the GPS is highly reliable, which provides us the ground truths of the locations of the moving objects. During the experiment, the SICK lidar served as the main sensor, the camera data was not used by the algorithm right now.

The object of the proposed algorithm is to track the moving objects in scene robustly and efficiently. However, in a normal environment (except the extremely cluttered environment) most of the sensor readings are come from stational objects. Thus, if we update the BOF with all the lidar datas and apply the tracking algorithm directly, large amount of statical objects will be detected and tracked. Basically we could apply two different straight-forward methods to overcome this problem. The first idea is to remove objects with a speed below a given threshold. This could be achieved by making use of the velocity estimations of the objects given by the tracker and the ego-motion estimation given by the odometer model. Unfortunately, because of the BOF has a potentially underestimate the cell velocity characteristic which is caused by the unsynchronized update scheme of velocity layers, and because of the inaccuracy of the egomotion estimation, this method tends to remove the low speed moving objects, i.e. pedestrians, by mistake.

The second idea is to divide the lidar data into a statical set and a dynamical set, and only use the dynamical set to update the BOF. We applied the second method in the experiment. The division of the lidar data is achieved by maintaining a well discretized occupancy grid map [START_REF] Thrun | Probabilistic robotics[END_REF] centered at the Cycab and moved along with it. Each cell in this map represents an occupancy probability. If the occupancy probability exceeds an given threshold, this cell is regarded as a statical cell, and the lidar data fall into this cell are removed from updating of the BOF. Different from the BOF, the occupancy grid map is implemented in a global coordinate, thus, the ego-motion of the Cycab is also needed to be estimated. We applied the odometer motion model to predict the location and used an iterative closest point( ICP) [START_REF] Besl | A method for registration of 3-D shapes[END_REF] algorithm to update it. In our experiment, this scheme has shown high accuracy. 6 show the results using the full dataset as the input to the BOF and tracker. There exist about 10 targets being detected and tracked. However, only one of them are the real moving object we are interested in. The second column are the results using only the dynamic dataset abtained from the aforementioned data division algorithm. It is clearly shown that all the statical objects are removed, and the moving object is correctly tracked.

The result shown in Fig. 7 to Fig. 9 demonstrates the accuracy of the tracker compared with a NNJPDA tracker. The moving car before the Cycab is detected and tracked consistently for 35 seconds. The relative position between the Cycab and the target comes from the GPS data is taken as the ground truth and is compared with that estimated by the trackers. The comparison of x relative position is shown in Fig. 7, while the y relative positions are compared in Fig. 8. The distance error of the estimated target position to the GPS data is shown in Fig. 9. As could be seen in the figures, our algorithm succeeded in tracking of the target consistently. However, from 21 seconds to 22 seconds, the NNJPDA tracker lost the target. The average distance error is 0.39 meters for our algorithm compares with 0.37 meters of the NNJPDA tracker. Consider the scale of the target car (roughly 1.5 meters by 2.5 meters), these results show that the precision of both the algorithms are satisfied in this application.

The implementation of the BOF and the tracker is in the C++ programming language without optimization. Experi-Fig. 6. Comparason of the results with and without dividing the lidar data into statical and dynamical data sets ments were performed on a laptop with an Intel Centrino processor with a clock speed of 1.6GHz. The time consumption of the grid map methods depends on the discretization and the discretization of the velocities. In our experiment, we represents the ground plane with a dimension of 30 meters by 16 meters, with a discretization resolution 0.4 meters by 0.4 meters. The occupancy grid map represents the ground plane around the vehicle with a dimension of 30 meters by 30 meters, with a discretization resolution 0.15 meters by 0.15 meters. The algorithm processes with an average frame rate of 6.2 frames/sec. The BOF consumes with an average of 0.11 seconds per frame, while the ICP algorithm uses 0.017 seconds and the updating of the occupancy grid map uses up to 0.078 seconds per frame. The average time consumption In Fig. 12, after the occlusion occurs for several frames and finishes, both of the targets are detected and tracked again. Note that, the ID of the occluded object remains the same before and after the occlusion, which is shown by the same color of the drawn target. This means the BOF framework and the proposed tracker are able to manage the targets properly during the short time occlusion, which is an important characteristic for a wide range of applications.

V. CONCLUSIONS

In this paper, we presented a novel object detecting and tracking algorithm for the BOF framework. This algorithm takes the occupancy/velocity grid of the BOF as input and extracts the objects from the grid with a clustering module which takes the prediction of the tracking module as a feedback to reduce the computational cost. A re-clustering and merging module is proposed to deal with the ambiguous

Fig. 1 .Fig. 2 .

 12 Fig. 1. Example of BOF output using a computer vision car detector as input (red boxes): The images are provided by a camera mounted on the moving ego-vehicle. The BOF output is projected back on the image. It represents a grid of occupancy probability (blue-to-red mapped color) and the mean velocity (red arrows) estimates.

Fig. 3 .

 3 Fig. 3. Sensing/Tracking system architecture.

Fig. 4 .

 4 Fig. 4. Bayesian filtering in the estimation of occupancy and velocity distribution in the BOF grids

Fig. 5 .

 5 Fig. 5. Experiment scene

Fig. 7 .Fig. 8 .

 78 Fig. 7. The x relative position of the target compared with the GPS data

Fig. 9 .

 9 Fig. 9. The distance error of the target to the GPS data.

Fig. 10 .

 10 Fig. 10. The two persons are walking towards each other in the perpendicular direction to the Cycab

Fig. 11 .

 11 Fig. 11. An occlusion takes place


Goal : Enable small and mid-sized farmers and food producers to scale up and expand production of nutritious food through competitive intermediate value chains at the regional level

What is FAIRCHAIN about ? • Multi-actor approach, with a consortium including scientific and private partners, and involving all relevant stakeholders along the case-study specific value chains in the different Case Studies

• Co-creation process, throughout the entire duration of the project, with a active actors who will provide knowledge, data and experience

FAIRCHAIN methodology

Séminaire IDEAS -1 oct, 2021

Case Studies

Séminaire IDEAS -1 oct, 2021

The French Case study • Proposer des modes de distribution 'zéro déchet' adaptés

• à des produits "non stables bactériologiquement" (boissons à base de lactosérum)

• à des petits / moyens volumes de produits • à des modes de distribution régionaux • Proposer des modes de distribution 'zéro déchet' adaptés

• à des produits "non stables bactériologiquement" (boissons à base de lactosérum)

• à des petits / moyens volumes de produits • à des modes de distribution régionaux

• Réduire les coûts de transports et les impacts environnementaux des lactosérums produits par les petites / moyennes fromageries Résultats attendus (1/2)

• Développer de nouvelles boissons fermentées à base de lactosérum • Goal-defining workshop

• What are the most pressing concerns for the respective case study? • What do you want the case study to achieve?

• Which of the various alternative options should be chosen and why? • How can a fair distribution of benefits and risks for all affected stakeholders and a more sustainable value chain be achieved with the chosen option(s)?

• Implementation workshops

• What support exist already?

• Which support would be helpful?

• For what more creative exchange is needed?

• Which actors are active where and when/how should they be involved? • Which adjustments are possible and useful?

• Where could we learn from the other case studies?

• Final review workshops:

• Which goals have been achieved/not achieved?

• Were the goals set appropriately?

• Which intended and unintended outputs, outcomes and impacts have been achieved?

• What were supporting/hindering factors?

• How can sustainable and long-lasting impacts be achieved?

• How can the achievements be disseminated and transferred to other contexts?

Séminaire IDEAS -1 oct, 2021

+ Business models workshop

• CS-France • Goal-defining Workshop Concrètement … Séminaire IDEAS -1 oct, 2021
• Identification des parties prenantes

• Affectation des parties prenantes aux catégories PESTEL et étape de la chaîne de valeur. Parties prenantes dans toutes les catégories de manière aussi complète que possible.  « as many as possible in all categories» • Influence des parties prenantes • Les acteurs pertinents peuvent fournir des informations sur l'état actuel, les initiatives existantes, les ressources nécessaires, les idées, les projets comparables, les voies de développement possibles (...) ET / OU peuvent contribuer à la mise en oeuvre, par exemple en tant que décideurs, promoteurs ou similaires.

Etapes préalables (1/2) Séminaire IDEAS -1 oct, 2021

• Echanges téléphoniques avec les parties prenantes identifiées: Présentation du projet, attentes, déroulement, … • Envoi aux parties prenantes • 1/ Quels sont les obstacles que vous identifiez qui pourraient freiner :

• La valorisation du lactosérum par fermentation avec fruits & Légumes ?

• La distribution (zéro déchet) pour des produits fermentés ciblés ?

• Quelles sont les questions actuelles en matière de recherche et de développement ?

• 2/ Qu'aimeriez-vous voir accomplir par le cas d'études ?

• Qu'est-ce qui ne devrait pas se produire ? Discussion 1 : Freins / moteurs Démarche 1. Les participants réfléchissent pendant 10 min à des idées pour les deux questions ci-dessus. 2. Les participants présentent brièvement leurs idées pendant que les 2 secrétaires de groupe prennent des notes.

  Intermediate Food Value Chaino Cooperation of small and mid-sized actors -from farmers, to processors, distributors, retailers, supporting organizations and other enterprises o Network or strategic alliance in order to supply fresh, sustainable and high-quality food products to consumers beyond the local market in greater quantities -often on a regional level.o Trusted and transparent relationships and an equal distribution of value created among the involved actors

• 6

 6 Case studies Séminaire IDEAS -1 oct, 2021 o 6 Case Studies covering a large range of agri-food systems across 6 countries Swi, Fr, Swe, Bel, Gre, Aus o Each Case study represents a value chain  involving small or mid-sized actors (may also include large actors) , at the proposal stage, we defined o the baseline ("unsatisfactory situation") o the major expectations of the actors / partners o the identification of technological, organisational and social innovations that could be included in the CS to support the farmers /producers to:  Scale up from short value chains to intermediate value chains  Sustain their so far weak position in the intermediate value chain  Scale down from large supply chains to intermediate value chains  Create a whole intermediate value chain FAIRCHAIN = in-depth analysis of the CS development of innovations, implement of innovations through the co-creation process re-design and assessment of innovative solutions.

-

  Case study coordinator Expertise in dairy processing and microbiology Cheese cooperative + associated farmers. Demonstration and implementation of solutions at industrial scale Expert in Biotechnology, in preservation and fermented products. Selection and production of selected strains at industrial scale Expertise in implementation of circular packaging management Skills in technology and microbiology of food products, in sensory and consumer science (consumers studies and food innovations) Integrate expertise from different stakeholders -Include and address stakeholders and actors across the entire value chain  mutual learning -Generate new perspectives on each of the case studies -Continuous exchange between the different FAIRCHAIN case studies to provide new insights from other areas of expertise and can lead to spill-overs. -Foster collaboration and partnerships among stakeholders that can thrive and grow during and beyond the duration of the project. -Design new/reconfigured intermediate value chains in each case study -Ensure fair(er) distribution of benefits and risks along the value chain (win-win situation)

•

  What are new partners needed for? • What are the next steps specifically required? • Which steps, actions and competencies are required by which actor to achieve the goals and implement the innovation? • What are the tasks and responsibilities of each actor? Methodology overview The workshops at a glance • Interim review workshops • What are the experiences of the first 2 years?

••••

  Document décrivant le projet, le cas d'études • Document expliquant les arrangements pratiques • Document de consentement (données personnelles, photos, vidéos, Définition des objectifs (cas d'étude Français) • Facilitation / encouragement des parties prenantes Workshop en lui-même Séminaire IDEAS -1 oct, 2021 Impliquer l'expertise de différents acteurs dans le développement et la distribution (sans déchet) de nouvelles boissons à base de lactosérum produit par les petites et moyennes fromageries Enquêter sur les besoins actuels et futurs du secteur laitier concerné, avec une collaboration avec le secteur des fruits et légumes Déterminer les objectifs et les buts à poursuivre pour developper et distribuer (sans déchet) la boisson innovante du cas d'étude Français Workgroups of 4-6 people (introductions and casual talk) • 1 Moderator, 1 Recorder per group • Introduce Topic (i.e. sector concerns) • Share the voice (has everyone contributed?) • Visibly record key ideas, issues Encourage people to write their own ideas on the whiteboard. • Record key elements of discussion.

  3. Une idée par post-it 4. Les participants discutent sur la base des post-its sur le Miro-board. Quels objectifs l'étude de cas français doit atteindre en 4 ans ? Pour mon entreprise/organisation ou pour la communauté ou les secteurs concernés par le cas d'étude Comment surpasser les freins identifiés précédemment pour le succès du projet ? A partir des freins identifiés précédemment, quels challenges poursuivre ? Que pourrions nous "réussir" à faire ? Discussion 2 -Perspectives d'exploitation Démarche 1. Les participants réfléchissent pendant 10 min à des idées pour la question ci-dessus. 2. Les participants présentent brièvement leurs idées pendant que les 2 secrétaires de groupe prennent des notes. 3. Une idée par post-it 4. Les participants discutent sur la base des post-its sur le Miro-board. • A réfléchir au montage du projet • Equilibre entre description les tâches du projet et co-création • Dans FAIRCHAIN : définition de CS et identification des innovations • Équilibre entre développement méthodologique de co-création / utilisation de méthodes et demande de soutien méthodologique 01/10/2021 Key aspects for a successful co-creation (1/3) Séminaire IDEAS -1 oct, 2021 • Stakeholders • Représentativité: identification implication selon les catégories PESTEL, affectation, influence, couvrant toutes les étapes de la chaîne de valeurs • Implication très tôt dans le projet, pour leur donner la possibilité d'avoir un rôle dans la construction du projet : cas d'études • Communication claire sur les attentes des parties prenantes depuis le début (et tout au long) du projet : Bien expliquer les modalités (contextuelles, temporelles, financières) • Communication claire sur les objectifs des ateliers de co-création : bien préciser les objectifs, ce qui est négociable, ce qui ne l'est pas. Bien expliquer les attentes, • Faciliter le dialogue (temps de question, discussion, pas d'enregistrement, …) • Prévoir un budget (réunions, déplacements, dédommagements) 01/10/2021 Key aspects for a successful co-creation (2/3) Séminaire IDEAS -1 oct, 2021

01/10/2021

• Restitution sommaire des points forts pour partenaires (template)

• Enquête de satisfaction pour partenaires

• Aviez-vous des attentes concernant l'atelier ? Si oui, comment les décririez-vous ?

• Dans quelle mesure ces attentes ont-elles été satisfaites ?

• Pensez-vous que tous les acteurs ou parties prenantes concernés ont été représentés de manière appropriée lors de l'atelier ? Sinon, quels manques ?


Kamel Mekhnacha

Yong Mao

David Raulo

Christian Laugier

The "Fast Clustering-Tracking" algorithm in the Bayesian Occupancy Filter framework

It has been shown that the dynamic environment around the mobile robot can be efficiently and robustly represented by the Bayesian occupancy filter (BOF) [1]. In the BOF framework, this environment is decomposed into a gridbased representation in which both the occupancy and the velocity distributions are estimated for each grid cell. In a such representation, concepts such as objects or tracks do not exist and the estimation is achieved at the cell level. However, the object-level representation is mandatory for applications needing high-level representations of obstacles and their motion.

To achieve this, a natural approach is to perform clustering on the BOF output grid in order to extract objects. We present in this paper a novel clustering-tracking algorithm. The main idea is to use the prediction result of the tracking module as a form of feedback to the clustering module, which reduces drastically the complexity of the data association. Compared with the traditional joint probabilistic data association filter (JPDAF) approach, the proposed algorithm demands less computational costs, so as to be suitable for environments with large amount of dynamic objects. The experiment result on the real data shows the effectiveness of the algorithm.

I. INTRODUCTION

Perceiving of the surrounding physical world reliably is a major demanding of the driving assistant systems and the autonomous mobile robots. The dynamic environment need to be perceived and modeled according to the sensor measurements which could be noisy. This problem is normally treated within the estimation framework. The major requirement for such a system is a robust target tracking system. Most of the existing target tracking algorithms [START_REF] Shalom | Tracking and Data Association[END_REF] use an object-based representation of the environment. However, these existing techniques have to take into account explicitly data association and occlusion problems which are major challenges of the performances. In view of these problems, a grid based framework, the Bayesian occupancy filter (BOF) [START_REF] Tay | An Efficient Formulation of the Bayesian Occupation Filter for Target Tracking in Dynamic Environments[END_REF] [3] [START_REF] Coue | Bayesian occupancy filtering for multitarget tracking: an automotive application[END_REF] has been presented in our previous works.

In the BOF framework, concepts such as objects or tracks do not exist. It decompose the environment into a grid based representation. A Bayesian filter [START_REF] Thrun | Probabilistic robotics[END_REF] based recursive prediction and estimation paradigm is employed to estimate an occupancy probability and a velocity distribution for each grid cell. Thanks to the grid decomposition, the complicated data association and occlusion problems do not exist. The BOF is extremely convenient for applications where no object-level representation is needed. Another advantage of the BOF is that the multiple sensor fusion task could be easily achieved. In some situations, using information from multiple sensors could provide more reliable and robust information of the environment. However, in traditional multiple sensor fusion techniques, data association problem could be further complicated. The associations between the two consecutive time instances from the same sensor as well as the associations among the tracks of different sensors will have to be take into account at the same time. Fortunately, these difficulties do not exist in the grid based approaches [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF] which deal with the data association problems in a more feasible way. Uncertainties of multiple sensors are specified in the sensor models and are fused into the BOF grid naturally with solid mathematical ground. Despite of the aforementioned advantages, a lot of applications demand the explicit object-level representation. In our former work, we suggested a layer structure for these systems. A joint probabilistic data association filter (JPDAF) [START_REF] Shalom | Tracking and Data Association[END_REF] based object detecting and tracking method was implemented above the BOF layer. However, when there are enormous amount of dynamic objects in the environment, the number of hypothesises generated by the JPDAF increases rapidly, which makes the method suffers from the computational cost. Regarding to this problem, a novel fast object detecting and tracking algorithm is proposed. A simple and naive clustering algorithm is used to extract objects from the BOF grid. By taking the prediction result of the tracking module as a form of feedback to the clustering module, the clustering algorithm avoids searching in the entire grid which garantees the performance. A re-clustering and merging strategy is employed only when the ambiguous data association occurs. The computational cost of this approach is linear to the number of dynamic objects detected, so as to be suitable for scenes in cluttered environment. Our approach has been tested on the real data collected on real cars in highway and cluttered urban environments (Fig. 1), and also on our Cycab experimental platform (Fig. 2).

In classical tracking methodology [START_REF] Shalom | Tracking and Data Association[END_REF], the problem of data association and state estimation are major problems to be addressed. The two problems are highly coupled together and an error in either portion leads to erroneous outputs. The BOF makes it possible to decompose this highly coupled relationship by avoiding the sensor data association problem, in the sense that data association is to be handled at a higher level of abstraction.

We propose to use a hierarchical approach in which two filtering levels are used (Fig. 3):

(i) Robust grid-level sensing. (ii) Robust object-level tracking. In a such architecture, the output grid of the BOF grid filter (i.e, the probability distribution on the occupancy of the cell, and the probability distribution on the velocity of the cell occupancy) is used as input for the object tracker by extracting object hypothesis from the grid (Fig. 3).

The paper is organized as follows. In the next section, the BOF framework is briefly described. The object detecting and tracking approach is presented in section III. In section IV, the experimental result of our approach on the real data collected by the Cycab platform is provided. Finally, conclusions are drawn in section V.

II. BAYESIAN OCCUPANCY FILTER (BOF)

The Bayesian Occupancy Filter (BOF) is represented as a two dimensional planar grid based decomposition of the environment. Each cell of the grid contains two probability distributions. A probability distribution on the occupancy of the cell, and the probability distribution on the velocity of the cell occupancy.

Given a set of input sensor readings, the BOF algorithm allows to update the occupancy/velocity estimates of each grid cell.

BOF is a special implementation of the Bayesian filter approach [START_REF] Jazwinsky | Stochastic Processes and Filtering Theory[END_REF]. This approach addresses the general problem of recursively estimating the probability distribution, P(X k | Z k ), of the state X of a system conditioned on its observation Z. This expression is also known as the posterior distribution. The posterior distribution is obtained in two stages: prediction and estimation.The prediction stage computes an a priori prediction of the target's current state known as the prior distribution. The estimation stage then computes the posterior distribution by using the prediction with the current measurement of the sensor.

In the case of the BOF, using this prediction/estimation scheme allows filtering out false alarms, miss-detections, and localization errors in sensors data readings. Figure 1 shows an example of BOF output using a computer vision car detector. The input of the BOF in this case is, for each time step, a set of bounding boxes corresponding to the detected vehicles (red boxes). The output represents a grid of occupancy probability (blue-to-red mapped color) and mean velocity (red arrows) estimates.

The Bayesian model presented in the following text is a reformulation of the one we presented in [START_REF] Tay | An Efficient Formulation of the Bayesian Occupation Filter for Target Tracking in Dynamic Environments[END_REF]. The aim of this reformulation is to make clearer the strong link between the discretization of the space and the discretization of the velocity, which reduces the number of the used random variables and makes the model easier to explain.

The key idea of the model is to represent the 2D space using a regular grid. Given this space discredization and assuming that objects do not overlap, the velocity of a given c cell at a time t is directly linked to the identity of its antecedent cell A c from which the content of cell c moved between t -1 and t. In other words, we can define the velocity of a given cell by providing the index of its antecedent.

Therefore, estimating the velocity of a given cell is equivalent to estimating a probability table over its all possible antecedents. Possible antecedents of a cell are defined by providing a neighbourhood from which the cell is reachable in a time step. This model applies also to velocities needing more than one time step for a neighbour cell to reach c. However, for simplicity we will assume only one-step velocities (neighbours reaching c in one time step).

A. The BOF model 1) Variables: For a given cell having c ∈ Y as index in the grid, let:

• A t c ∈ A c ⊂ Y
represents each possible antecedent of cell c over all the cells in the grid domain Y . The set of antecedent cells of cell c is denoted by A c and is defined as a neighbourhood of the cell c.

• A t-1 c ∈ A c ⊂ Y is same as A t c but for the previous time step. • O t c ∈ O ≡ {0
, 1} is a boolean variable representing the state of the cell in terms of occupancy at time t, either

[O c = 1] if occupied, [O c = 0] if empty.
Given the independency hypothesis, the occupancy of each cell at time t is considered apart from the occupancy of its neighbouring cells at time t.

• Z t i ∈ Z , 1 ≤ i ≤ S ∈ N
, is a generic notation for measurements yielded by each sensor i, considering a total of S sensors yielding a measurement at the considered time instant.

2) Joint distribution factors:

The following expression gives the decomposition of the joint distribution of the relevant variables according to Bayes' rule and dependency assumptions:

P(A t-1 c A t c O t c Z t 1 • • • Z t S ) = P(A t-1 c )P(A t c | A t-1 c )P(O t c | A t-1 c ) S ∏ i=1 P(Z t i | A t c O t c ). (1)
The parametric form and semantics of each component of the joint decomposition are as follows:

• P(A t-1 c ) is the probability for a given neighbouring cell A c to be the antecedent of c at time t -1. In order to represent the fact that cell c is a priori equally reachable from all possible antecedent cells in the considered neighbourhood, this probability table is initialised as uniform and is update in each time step.

• P(A t c | A t-1 c
) is the distribution over antecedents at time t given the antecedent of cell c at t -1. It represents the prediction (dynamic) model over velocity. If we assure a perfect constant velocity hypothesis between the two time frames t -1 and t, this distribution is just:

P(A t c | A t-1 c ) = P(A t-1 A t-1 c
).

In other words, the predicted probability is just the probability at the preceding time instant for the antecedent at t -1.

Considering imperfect constant velocity hypothesis may be done by introducing:

-E ∈ {0, 1} ≡ "There was a prediction error", -P(E) = ε the probability of violating the constant velocity hypothesis (a parameter of the model).

If we define:

-

P(A t c | A t-1 c ¬E) = P(A t-1 A t-1 c
),

-P(A t c | A t-1 c E) = U (A t c ):
Uniform predicted antecedent (velocity) when constant velocity hypothesis is violated, then, P(A t c | A t-1 c ) may be written as a mixture:

P(A t c | A t-1 c ) = P(¬E)P(A t c | A t-1 c ¬E) + P(E)P(A t c | A t-1 c E)
Which leads to:

P(A t c | A t-1 c ) = (1 -ε)P(A t-1 A t-1 c ) + ε U (A t c ) = (1 -ε)P(A t-1 A t-1 c ) + ε/ A c . • P(O t c | A t-1 c
) is the distribution over occupancy given the antecedent of cell c at t -1. It represents the prediction (dynamic) model over occupancy. If we assure a perfect constant velocity hypothesis between the two time frames t -1 and t, this distribution is just:

P(O t c | A t-1 c ) = P(O t-1 A t-1 c
).

In other words, the predicted probability is just the probability at the preceding time instant for the antecedent at t -1. When considering imperfect constant velocity hypothesis, P(O t c | A t-1 c ) may be written as a mixture:

P(O t c | A t-1 c ) = P(¬E)P(O t c | A t-1 c ¬E) + P(E)P(O t c | A t-1 c E)
Which leads to:

P(O t c | A t-1 c ) = (1 -ε)P(O t-1 A t-1 c ) + ε U (O t c ) = (1 -ε)P(O t-1 A t-1 c ) + ε/2. • P(Z t i | A t c O t c
) is the direct model for sensor i. It yields the probability of a measurement given the occupancy O t c and the antecedent (velocity) A t c of cell c. Measurements for all sensors are assumed to have been taken independently from each other. For sensors providing measurements depending exclusively of occupancy, this distribution can be written as

P(Z t i | O t c
). In the same manner, for sensors providing measurements depending exclusively of velocity, this distribution can be written as P(Z t i | A t c ). 3) Occupancy and velocity estimation using the BOF model: At each time step, the estimation of the occupancy and velocity of a cell is answered through Bayesian inference on the model given in Equation ( 1). This inference leads to a Bayesian filtering process (Fig. 4). In this context, the prediction step propagates cell occupancy and antecedent

(O t c A t c | [Z t 1 • • • Z t S ]
). This allows by marginalization to compute

P(O t c | [Z t 1 • • • Z t S ]) and P(A t c | [Z t 1 • • • Z t S ]
) that will be used for prediction in the next iteration.

It's important to notice that the distribution P(A t c ) over velocity is updated even when no velocity sensors are available. Indeed, suppose we have only one occupancy sensor described by the model

P(Z t OCC | O t c ). The a posteriori distribution P(A t c | [Z t OCC ]
) leads to the formula:

P(A t c | [Z t OCC ]) ∝ (2)
∑ A t-1 c ∈A c P(A t-1 c )P(A t c | A t-1 c ) ∑ O t c ∈{0,1} P(O t c | A t-1 c )P([Z t OCC ] | O t c ).
This allows to update the velocity distribution even when no velocity sensors are available. In this case, the update is based exclusively on the occupancy observations. When an additional velocity sensor

P(Z t VEL | A t c
) is available, it should be used to update the estimate (2) as follows:

P(A t c | [Z t OCC Z t VEL ]) ∝ P(A t c | [Z t OCC ])P([Z t VEL ] | A t c ).

III. THE "FAST CLUSTERING-TRACKING" ALGORITHM

In many applications, the object-level representation are demanded. We propose to use a layer architecture as shown in Fig. 3 to obtain this representation. In our former work [START_REF] Tay | An Efficient Formulation of the Bayesian Occupation Filter for Target Tracking in Dynamic Environments[END_REF], the object-level presentation is obtained by a classical JPDAF algorithm. However, in the cluttered environment with enormous moving objects, the JPDAF suffers from the combinational explosion of hypothesises. To overcome this problem, we propose a novel object detecting and tracking algorithm. This algorithm could be roughly divided into a clustering module, an ambiguous association handling module and a tracking and track management module.

A. Clustering

The clustering module takes the occupancy/velocity grid of the BOF as the input and extracts object level reports from it. A natural algorithm to achieve this is to connect the eight-neighbor cells according to an occupancy threshold occ threshold. In addition to the occupancy values, a threshold of the Mahalanobis distance between the velocity distributions vel threshold is also employed to distinguish the objects that are close to each other but with different moving velocities.

From the implementation point of view, we use an ID grid with the same scale of the input occupancy/velocity grid to store the IDs of the associated targets. The ID grid value is initialized to zero(non-associated) and then is set to the ID of the associated target. In order to avoid searching for clusters in the whole grid, we use the predicted targets' states as a form of feedback. For a given target with ID id, the predicted state is used to define a region of interest (ROI) in which the clustering process starts. After a starting point with an occupancy probability value greater than the occ threshold is found in the ROI, the id is propagated in the ID grid using the connectivity criterion among the non-associated cells (cells with ID = 0).

A report for the tracker is a 4-dimentional observation corresponding to the position and the velocity of an extracted cluster.

The 2D position component of this vector is computed as the mass center of the region corresponding to the cluster pixels (cells) set. We also compute the corresponding covariance matrix representing the uncertainty of the observed position.

The 2D velocity component is just the weighted mean of the estimated velocities of all cells of the cluster. It comes also with a covariance matrix representing the uncertainty of the observation velocity.

B. Re-clustering and tracks merging

During the clustering process, three possible situation need to be considered.

• case 1: no cell with P(occ) ≥ occ threshold is found.

The target has not been observed and no association is needed.

• case 2: a cluster C of non-associated cells having ∀c(i, j) ∈ C, P(occ(i, j)) ≥ occ threshold is extracted. These cells are then associated to the target id: ∀c(i, j) ∈ C, ID(c i , c j ) = id.. This situation occurs when there is no ambiguity in the association. This is an advantageous situation allowing a fast clustering-association procedure. Fortunately, this case is the most frequent one when using the algorithm to the real data sets. • case 3: cells having P(occ(i, j)) ≥ occ threshold exist.

However, they have already been assigned to other IDs. In this conflicted case, an observation (cluster) could be possibly generated by two (or more) different targets. The first two cases are normal cases, however, the third case is refered as an ambiguous association case which need to be dealt with in a special manner. The ambiguous association could occur in the following two situations :

• Different targets are being too close to each other and the observed cluster is in fact the union of the more than one observations generated by different targets. • The different tracked targets are corresponding to a single object and should be merged into one. We take a re-clustering strategy to deal with the first situation and a cluster merging strategy to deal with the second one.

Suppose when an ambiguous association occurs, a set of tracks T 1 , T 2 , • • • , T m are the potential candidates to be associated to the the observed cluster. We have to cut up the extracted cluster and generate a sub-cluster (possibly empty) for each candidate. This re-clustering is achieved by a kmeans [START_REF] Bishop | Pattern recognition and machine learning[END_REF] algorithm using a simple Cartesian distance. The considered distance is taken between the center of the subcluster and a given cell. In this way, the first cause of the ambiguous association is handled.

To deal with the second cause of the ambiguous association, we introduce a concept of "alias" which is in the form of a two-tuples to represent the duplicated tracks. When an ambiguous association between two tracks T i and T j is detected, an alias ALIAS(T i , T j ) is initialized and added to a potential alias list.

At each frame, the tracker updates this list by confirming or disproving the existence of each alias hypothesis ALIAS(T i , T j ) according to the observation of the ambiguous association.

At a given time step t, if the ambiguous association occurs between T i and T j , and the alias ALIAS(T i , T j ) is found in the potential alias list, the probability P t (S(T i , T j )) is updated by a confirming step using a Bayesian filtering approach as follows:

P t (S | F) = P t-1 (S) × P(F | S) P t-1 (S) × P(F | S) + [1 -P t-1 (S)] × P(F | ¬S)
where:

• S ≡ "the T i and T j tracks are alias for the same object".

• F ≡ "an ambiguous association between the tracks T i and T j is observed". The probability values P(F | S) and P(F | ¬S) are constant parameters of the tracker. The former denotes the probability of observing an ambiguous association when the two concerned tracks are alias of the same object and is set to a constant value 0.8. The second denotes the probability of falsely observing an ambiguous association and is set to 0.1.

When ALIAS(T i , T j ) is found in the potential alias list but is not observed as an ambiguous association, its probability is disproved in a similar manner:

P t (S |¬F) = P t-1 (S) × P(¬F | S) P t-1 (S) × P(¬F | S) + [1 -P t-1 (S)] × P(¬F | ¬S)
Then, according to the probability P t (S(T i , T j )), the decision of merging of tracks T i and T j could be made.

C. Tracks creation

For new targets creation, we introduce a concept "cluster seed" to define a cell in the BOF grid where we will try to find, for each step, a new (non-associated) cluster. Indeed, the searching for potential new targets is after all the existing tracks are processed. Thus, only non-associated cells will be processed to extract clusters as the observations for the potential new targets. The "cluster seed" concept is general and can be implemented via various strategies. The simplest strategy is to insert a possible seed in each cell of the grid. However, more sophisticated strategies could be more efficient. For example, cluster seeds could be inserted only in entrance regions of the monitored area.

D. Tracks deleting

The deleting of tracks is also achieved in a Bayesian manner. If an existing track T is associated with a given report (cluster), its existence probability is increased using the following formula:

P t (E | O) = P t-1 (E) × P(O | E) P t-1 (E) × P(O | E) + [1 -P t-1 (E)] × P(O | ¬E)
where:

• E ≡ "the target T exists".

• O ≡ "the target T has been observed (associated)". The parameters P(¬O | E) and P(O | ¬E) are the tracker miss-detections and false alarms probabilities respectively.

If an existing target is not associated with any report (cluster), its existence probability is decreased in the similar way: P t (E | ¬O) = P t-1 (E) × P(¬O | E) P t-1 (E) × P(¬O | E) + [1 -P t-1 (E)] × P(¬O | ¬E) According to the existence probability, the track deleting operation is achieved by applying a deleting threshold on it. However, in order to increase the robustness for occlusions, we also introduce an occlusion calculation procedure. It allows us to decide if a given target is possibly occluded or not. If the target is regarded as being occluded, its existence probability is not decreased even if no observation is associated to it. As a consequence, the target will be kept for longer time without being observed.

E. Tracks updating

In our work, the prediction and estimation of the targets are accomplished by attaching a Kalman filter with each track. Once associated to a given track, a report (Gaussian distributions for both position and velocity) corresponding to an extracted cluster is used as an observation to re-estimate the position and velocity of the track in a prediction-update step. For non-observed tracks, only a prediction step is taken by applying the dynamic model to the estimation result of the precedent time step.

IV. EXPERIMENTAL RESULT

We have already applied our approach on the real data and achieved satisfied results in several conditions. The proposed algorithms have been used in several driving assistance projects in both highway and cluttered urban environments. The used sensor modalities include:

Fig. 1 .

 1 Fig. 1. Example of BOF output using a computer vision car detector as input (red boxes): The images are provided by a camera mounted on the moving ego-vehicle. The BOF output is projected back on the image. It represents a grid of occupancy probability (blue-to-red mapped color) and the mean velocity (red arrows) estimates.

Fig. 2 .

 2 Fig. 2. The Cycab Platform.

Fig. 3 .

 3 Fig. 3. Sensing/Tracking system architecture.

Fig. 4 .

 4 Fig. 4. Bayesian filtering in the estimation of occupancy and velocity distribution in the BOF grids