Trung-Dung Vu

Olivier Aycard

Laser-based Detection and Tracking Moving Objects using Data-Driven Markov Chain Monte Carlo

We present a method of simultaneous detection and tracking moving objects from a moving vehicle equipped with a single layer laser scanner. A model-based approach is introduced to interpret the laser measurement sequence by hypotheses of moving object trajectories over a sliding window of time. Knowledge of various aspects including object model, measurement model, motion model are integrated in one theoretically sound Bayesian framework. The data-driven Markov chain Monte Carlo (DDMCMC) technique is used to sample the solution space effectively to find the optimal solution. Experiments and results on real-life data of urban traffic show promising results.

I. INTRODUCTION

Recent years have seen many research works employing laser scanners to detect and track moving objects [START_REF] Wang | Simultaneous Localization, Mapping and Moving Object Tracking[END_REF], [START_REF] Vu | Online localization and mapping with moving object tracking in dynamic outdoor environment[END_REF], [START_REF] Petrovskaya | Model based vehicle tracking for autonomous driving in urban environments[END_REF], [START_REF] Darms | Classification and tracking of dynamic objects with multiple sensors for autonomous driving in urban environments[END_REF]. Existing methods usually separate the detection and tracking as two independent procedures. Since detection at one time instant usually results in ambiguities that make the data association become more difficult with missing detections and false alarms. We propose a probabilistic framework for simultaneous detection and tracking of objects which combines the detection and tracking together. This allows object detection to make use of temporal information and facilitates robust tracking of the objects.

On the other hand, state-of-the-art laser-based approaches to detect moving objects usually involves performing segmentation of laser points and representing objects by bounding-boxes of laser segments. These conventional approaches pose several problems. Firstly, since a laser scanner only sees parts of the object currently facing the scanner, as the object moves we get different contours (Fig. 1(a)) that leads to a significant degradation of tracking results (Fig. 1(b)). Secondly, due to occlusions or laser-absorbed surfaces (ex: glasses, black surfaces), an object can be divided into several segments (Fig. 1(d),(e)). This makes object detection and tracking much harder when dealing with object merging and track grouping. Here we take a modelbased approach and will discuss how using object models of several predefined classes to interpret the laser measurements can overcome these problems (Fig. 1(f)).

We formulate the detection and tracking problem as finding the most likely trajectories of moving objects given measurements over a sliding window of time (Fig. 2). A trajectory (track) is regarded as a sequence of object shapes produced over time by an object satisfying the constraint of an underlying measurement model and the smoothness in motion from frame to frame. In this way, our approach can be seen as a batch method searching for the global optimum solution in the spatio-temporal space. Due to the high computational complexity of such a scheme, we employ a data driven Markov chain Monte Carlo (DDMCMC) technique [START_REF] Zhu | Integrating Top-down/Bottom-up for object recognition by data driven markov chain monte carlo[END_REF] that enables traversing efficiently in the solution space.

The key contribution of this paper is designing a general framework to perform object detection and tracking at the same time with an explicit integration of various aspects including prior information, object model, measurement model, motion model in a theoretically sound formulation. We test the algorithm on real-life data of urban traffic and the results demonstrate the effectiveness of our approach.

The paper is organized as follows. The related work is reviewed in Section II. We formulate the general multiple object detection and tracking problem in Section III. In Section IV we present our algorithm to find the optimal trajectories of moving objects using a spatio-temporal MCMC sampling method. We discuss experiments and provide some initial results on real-life traffic datasets in Section V, followed by conclusions and future works.

II. RELATED WORKS

Multiple object tracking (MOT) has been an active research topic over decades. When object observations are known, object tracking becomes a data association problem. Among popular data association methods, multiple hypothesis tracking (MHT) [START_REF] Blackman | Multiple hypothesis tracking for multiple target tracking[END_REF] is widely used. MHT is a multi-frame tracking method that is capable of handling ambiguities in data association by propagating hypotheses until they can be solved when enough observations are collected. The main disadvantage of MHT is its computational complexity since the number of hypotheses grows exponentially over time. The joint probabilistic data association (JPDA) filter [START_REF] Schulz | Tracking multiple moving targets with a mobile robot using particle filters and statistical data association[END_REF] is more efficient but prone to make erroneous decision since only single frame is considered and the association made in the past is not reversible. Other sequential approaches using particle filters [START_REF] Smith | Using particles to track varying numbers of objects[END_REF] share the same weakness that they cannot reverse time back when ambiguities exist. Recently, batch MOT methods [START_REF] Oh | Markov chain monte carlo data association for general multiple-target tracking problems[END_REF], [START_REF] Yu | Multiple target tracking using spatiotemporal markov chain monte carlo data association[END_REF] attracted research attentions. Based on a powerful MCMC technique [START_REF] Zhu | Integrating Top-down/Bottom-up for object recognition by data driven markov chain monte carlo[END_REF], the entire solution space can be explored in an efficient way to find the global optimum. Oh et al. [START_REF] Oh | Markov chain monte carlo data association for general multiple-target tracking problems[END_REF] used MCMC to organize the temporal association between objects and punctual observations over time. This method is extended in [START_REF] Yu | Multiple target tracking using spatiotemporal markov chain monte carlo data association[END_REF] to solve the data association in a spatio-temporal space.

Taking object detection result as input for tracking, trackers are different by detection methods. In [START_REF] Schulz | Tracking multiple moving targets with a mobile robot using particle filters and statistical data association[END_REF], Schulz introduced a simple method only to detect people using the local minimal caused by legs. Wang [START_REF] Wang | Simultaneous Localization, Mapping and Moving Object Tracking[END_REF], followed by Vu [START_REF] Vu | Online localization and mapping with moving object tracking in dynamic outdoor environment[END_REF] proposed a more general approach which build an online occupancy grid representing the local map and moving parts of objects can be detected when they enter object-free regions. However, ambiguities occur when objects appear in unexplored regions, it is difficult to say it is moving or static. Moreover, using laser impact contours to represent objects, this approach encounters problems of tracking degradation and object splitting as mentioned in the introduction section.

Our approach here emphasizes on the use of object models like that of [START_REF] Petrovskaya | Model based vehicle tracking for autonomous driving in urban environments[END_REF] to overcome known problems of laser-based tracking. We propose to solve at the same time both the detection and tracking using a MCMC technique to search for the optimum solution in the spatio-temporal space. In this way, temporal information will help to reduce ambiguities and false alarms for detection at one time instant and facilitate a more robust tracking. The moving object detection result in our previous work [START_REF] Vu | Online localization and mapping with moving object tracking in dynamic outdoor environment[END_REF] is employed to generate object hypotheses that helps to drive the MCMC search more efficiently. In addition, we introduce a new way to model the temporal prior and the likelihood that takes the whole considered measurement sequence into account.

III. MULTIPLE OBJECT TRACKING FORMULATION

We consider tracking in a sliding window of time comprised of T ∈ N + last frames. Let Z be the set of all measurements within the time interval [1, T ] and Z t denote the laser measurement at time t. The current time corresponds to t = T . Assume that within [1, T ] there are K unknown number of moving objects appear in the vehicle sensing range.

Not like [START_REF] Petrovskaya | Model based vehicle tracking for autonomous driving in urban environments[END_REF] only considering vehicles, we distinguish four classes of moving objects: bus, car, bike, pedestrian (motorcycles and bicycles belong to the class bike). We use the box model of fixed sizes to represent bus, car, bike and the point model to represent pedestrian. For the box model, object is parameterized by M = {c, x, y, θ , w c , l c } which are object class, object center position, orientation, width and length respectively. Herein w c and l c are constants with We cast the detection and tracking problem as interpreting the given observation set Z by an unknown number of K tracks ω = {τ 1 , τ 2 , ..., τ K }. Each track τ k in ω is defined as a sequence of moving objects of the same class τ k = {τ k (t 1 ), ..., τ k (t |τ k | )} where t i ∈ [1, T ], τ k (t) is a moving object detected at time t and is either of form {c, x, y, θ , w, l} or {c, x, y}. Since missing detection may happen 1 ≤ (t i+1t i ) ≤ t max . We introduce the notation ω t = K k=1 τ k (t) that is the set of moving objects detected at time t.

Fig. 2 shows an example of four laser scans and one possible interpretation of moving objects which is comprised of seven tracks of five cars, one bus and one pedestrian.

The moving object detection and tracking problem is formulated as maximizing a posterior (MAP) of an interpretation of tracks ω, given the set of observations Z over T frames:

ω * = argmax ω P(ω|Z) (1)
Following the Bayes rule, the posterior probability is decomposed into a prior term and a likelihood term:

P(ω|Z) ∝ P(ω)P(Z|ω) (2)
In the following sections, we discuss the prior and the likelihood model used in our framework.

A. Prior Distribution

Assuming that the occurrence of an object is independent of the others, we define the prior of a solution ω is the product of the probabilities of individual tracks:

P(ω) = K ∏ k=1 P(τ k ) (3)
The probability P(τ k ) encodes the probability of the appearance of objects independent over time P O (.) and the temporal consistency of objects within track P T (.). The probability P T (.) controls the inner-smoothness of each track independently (Fig. 3). However, without an a priori knowledge of the number of targets, the inner-smoothness constraint will favor shorter paths, and therefore will split a trajectory into a large number of sub-tracks. To overcome this overfitting problem, we add the prior term P L (.) which encodes the preference of long track. We can write:

P(τ k ) = P L (τ k )P O (τ k )P T (τ k ) (4) 1)
We adopt an exponential model of the length of each track:

P L (τ k ) ∝ exp(λ L |τ k |) (5)
2) The probability of appearance of objects in track independent of time:

P O (τ k ) = |τ k | ∏ i=1 P(τ k (t i )) = P(c k ) |τ k | ∏ i=1 P(x i , y i )P(θ i ) (6)
where P(c k ), P(x i , y i ) and P(θ i ) are the prior probabilities over the object class, object position and object orientation respectively. In our current implementation, we set these prior probabilities as uniform distributions. However, knowledge of road type and road border, if available can be added for better performance. 3) There remains how to model the temporal consistency within each track P T (τ k ). This term is measured by the smoothness of object motion according to its underlying dynamics model. Since in urban scenarios objects are high maneuvers, we opt for multiple model approach [START_REF] Zhao | Qualitative and quantitative car tracking from a range image sequence[END_REF] to model object dynamics. For classes of bus, car, bike, four modes of dynamics are used: constant velocity, constant acceleration, turning and stationary mode. For pedestrians, we force the acceleration to zero and only one constant velocity model is used. Box-model dynamic states are (x, y, θ , θ , v, a) with the velocity v and acceleration a are always in the direction θ of the longer edge l. Dynamic states for point-model objects are (x, y, v x , v y ).

We apply a IMM filter similar to [START_REF] Zhao | Qualitative and quantitative car tracking from a range image sequence[END_REF] to estimate states of objects in the track sequentially: τk (t 1 ), ..., τk (t |τ k | ) and their corresponding covariances: cov( τk (t 1 )), ..., cov( τk

(t |τ k | )). Set cov(τ k ) = cov( τk (t |τ k | )).
A smaller value of cov(τ k ) implies that the track is more consistent to the dynamics model. The temporal consistency of a track is then calculated by:

P T (τ k ) ∝ exp(-λ T cov(τ k )) (7)

B. Likelihood Probability

The likelihood P(Z|ω) reflects the probability we observe the measurement Z given ω which contains the states of all moving objects over the time interval [1, T ].

To model this likelihood, first we identify dynamic measurements which are caused by moving objects in ω. Fig. 4 shows a box-model object (solid rectangle) and its dilated bounding box (dotted rectangles). The laser ray Az is considered as being caused by the object if it has the impact lying on BD that corresponds to the measurement on visible sides. We notice that if the impact lies on the segment AB, the object is occluded. If the impact lies on the ray Dz and it is not a maximum range reading, the visibility constraint is violated (rays seeing through glasses or black surfaces are not the case)For the point-model object, it is dilated by a circle of a fixed diameter and all measurements fall inside the circle are considered as dynamic measurements. Let Z (d) denote all dynamic measurements of Z. We have Z (s) = Z -Z (d) the remained measurements that are supposed to be caused by static objects. The notations Z (d) t and Z (s) t are dynamic and static measurements at time t respectively. In this way, besides information about dynamic objects, ω partitions Z into dynamic and static measurements. From frame to frame, these measurements should be coherent with each others. We can therefore decompose the likelihood into the product of two terms:

p(Z|ω) = T ∏ i, j=1 P(Z i |ω j ) T ∏ i, j=1 P(Z i |Z (s) j ) (8)
where the first term encodes the likelihood of measurements at each time step given observations of dynamic objects and the second term encodes the consistency of the measurements with the static parts of the environment. The first term is then further decomposed:

T ∏ i, j=1 P(Z i |ω j ) = ∏ i P(Z i |ω i ) ∏ i = j P(Z i |ω j ) = ∏ i P M 1 (Z (d) i |ω i )P M 2 (Z (s) i |ω i ) ∏ i = j P M 3 (Z (s) i |ω j ) (9)
The second term in ( 8) is rewritten as:

T ∏ i, j=1 P(Z i |Z (s) j ) = ∏ i = j P M 4 (Z i |Z (s) j ) (10)
The meaning of each probability component is as follows. P M 1 scores the fitness of dynamic measurements to the moving objects. P M 2 , P M 3 and P M 4 penalizes the violation of laser visibility constraint. In particularly, P M 2 penalizes situations that laser can see through dynamic objects. P M 3 penalizes the situations where moving objects are detected at position that has seen static objects. P M 4 penalizes the situations where laser can see through static objects. Fig. 5, in order from left to right, illustrates the meanings of probabilities P M 1 , P M 2 , P M 3 and P M 4 respectively. Note that here we do not consider maximum range laser readings so that rays caused by glasses or black surfaces will not be penalized. In the following, we discuss how to model these probabilities:

1) Assuming that Z

(d) i is comprised of N dynamic mea- surements Z (d) i = {z 1 i , ..., z N i }.
We consider measurements obtained along each laser ray independent of each other. The measurement likelihood P M 1 factors as:

P M 1 (Z (d) i |ω i ) = N ∏ n=1 P(z n i |ω i ) (11)
Each measurement z n i corresponds to a laser beam that hits an object in ω i where the laser impact lies on the segment BD (Fig. 4). We model each ray's likelihood as a zero-mean Gaussian with respect to the distance d n from the impact to the ideal measurement point C:

P(z n i |ω i ) ∝ exp(-λ 1 d n ) (12)
2) For each object in ω i , we count the number of nonmaximal measurements Z (s)

i that fall behind the object model, call c 2 is the total number.

P M 2 (Z (s) i |ω i ) ∝ exp(-λ 2 c 2 ) (13)
P M 2 supports the remark following: If there exists such a violation of visibility constraint, there is unlikely a moving object appeared at that position. 3) Similarly, we count c 3 the number of measurements Z (s) i that fall inside occupied areas of the objects in ω j .

P M 3 (Z (s) i |ω j ) ∝ exp(-λ 3 c 3 ) (14)
P M 3 is in favor of the fact that if there is a moving object appeared at one time step then all measurements backward or afterward falling inside the object area should be dynamic measurements. 4) In the same way, let c 4 be the total number of violated measurements:

P M 4 (Z i |Z (s) j ) ∝ exp(-λ 4 c 4 ) (15)
P M 4 holds the observation that if there are measurements in one frame observed passing through other measurements in another frame then the later measurements are likely dynamic measurements.

C. Posterior Probability

By combining the above likelihood and the prior probability, we get the posterior probability function as:

P(ω|Z) ∝ exp{ λ L S len -λ T S mot -λ 1 S ms1 -λ 2 S ms2 - λ 3 S ms3 -λ 4 S ms4 } (16)
where λ L , λ T , λ 1 , λ 2 , λ 3 , λ 4 are positive real constants and:

S len = K ∑ k=1 |τ k | S mot = K ∑ k=1 cov(τ k ) S ms1 = T ∑ i=1 N ∑ n=1 d i n S ms2 = T ∑ i=1 c i 2 (17) S ms3 = ∑ i = j c i j 3 S ms4 = ∑ i = j c i j

IV. EFFICIENT POSTERIOR PROBABILITY COMPUTATION

Although the problem is restricted within a sliding window, searching in the solution space for Eq. ( 1) is still challenging. We employ a MCMC method to solve this problem. The basic idea of MCMC is as follows. A Markov chain can be designed to sample a probability distribution π(ω) (in our case π(ω) = P(ω|Z)). At each iteration, we sample a new state ω from the current state ω following the proposal distribution q(ω |ω). The new candidate state ω is accepted with the following probability A(ω, ω ) where

A(ω, ω ) = min(1, π(ω )q(ω|ω ) π(ω)q(ω |ω) ) (18)
otherwise the sampler stay at ω. The overview of MCMC algorithm is shown in Algorithm 1.

Algorithm 1 MCMC Sampler 1: Input: Z, n mc , ω * = ω 0 Output: ω * 2: for n = 1 to n mc do 3:

Propose ω according to q(ω |ω n-1 )

4: Sample U from Uni f orm[0, 1] 5: if U < A(ω, ω ) then 6:
ω n = ω ω n = ω n-1 10: end for This is the well-known Metropolis-Hasting algorithm. It is proved that the Markov chain constructed this way has its stationary distribution equal to π(), independent of the choice of the proposal probability q() and the initial state ω 0 [START_REF] Tierney | Markov chain concepts related to sampling algorithms[END_REF]. However, the choice of the proposal probability q() can affect the efficiency of the MCMC significantly. A random proposal probability will lead to very slow convergence rate while a proposal probability designed with domain knowledge [START_REF] Zhu | Integrating Top-down/Bottom-up for object recognition by data driven markov chain monte carlo[END_REF] will make the Markov chain traverse the solution space more efficiently. If the proposal probability is informative enough so that each sample can be thought of as a hypothesis, then the MCMC approach can be though of as a stochastic version of the hypothesize and test approach that is also named the data-driven MCMC method (DDMCMC).

A. Moving object hypothesis proposals

To make the proposals more informative, we take advantage of the detection module in our previous work [START_REF] Vu | Online localization and mapping with moving object tracking in dynamic outdoor environment[END_REF] which can help to identify moving parts of dynamic objects. Combined with suitable object models, all possible object hypotheses are generated at location of these detected motion evidences. The principle is that we want to keep the detection rate high and accept false alarms to cover as many potential moving objects as possible. These rough hypotheses provide initial proposals for the MCMC sampler (Algorithm 1) that performs a finer search over the spatio-temporal space to find the most likely trajectories of moving objects with a maximum of posterior probability. We detail the moving object hypotheses generation process in the following.

Firstly, as presented in [START_REF] Vu | Online localization and mapping with moving object tracking in dynamic outdoor environment[END_REF], we incrementally constructs an online occupancy grid representing a local map of the vehicle environment based on good vehicle localization obtained by a fast scan matching technique. Moving parts of dynamic objects are then detected when objects enter object-free regions. In this paper, the detection condition is loosened to include the situations when objects are observed in unexplored regions that could be static or new moving objects. Taking all these as dynamic evidences increases the detection rate and false alarms as well. Result of this step is a set of dynamic segments corresponding to potential moving objects. Note that objects can be divided into several parts so that several segments might be related to the same object.

Fig. 6 illustrates our detection process. In the figure, the bottom image describes a situation when the host vehicle moving along the street seeing two cars moving ahead, another car coming out of the left turn and two pedestrians walking on the left pavement. The image on top left shows the local grid map constructed around the host vehicle (blue box). In red color is the current laser scan. Laser impacts that fall into free or unexplored regions are detected as dynamic measurements and are displayed in the top right image. Dynamic measurements are then grouped into segments represented in green boxes corresponding to moving objects. Note that the car coming from the left turn is divided into two segments.Two false alarms are also displayed.

Secondly, starting from identified dynamic segments, we generate hypotheses by fitting predefined object models to each segment. The objective is to generate all possible hypotheses corresponding to potential moving objects. The model fitting is carried out as follows. For each segment, a minimum bounding box is computed and corresponding sides of the segment are extracted. We remark that at one time instant, maximum two sides of a segment can be seen by the laser scanner. Providing that the size of a segment bounding box is larger than a threshold, the segment is classified as a L-shape if it has two visible sides, as an I-shape if only one side is visible. Otherwise it is classified as a "mass point"-shape. Depending on the shape and size of segments, object hypotheses are generated using suitable models. Lshape segments will generate bus, car hypotheses, I-shape segments create bus, car, bike hypotheses and "mass-point" segments will generate pedestrian hypotheses. Fig. 7 shows possible hypotheses of an object as a box model given L-shape and I-shape segments of different sizes. Note that by fitting object models to segments in this way, models can cover segments nearby so that naturally overcome object splitting problem caused by laser measurement discontinuities. In subsequent sections we discuss how using the MCMC sampler to search for the solution from the space of moving object hypotheses. To make the sampling easier, we introduce a neighborhood graph structure as described next.

B. Neighborhood graph of hypotheses

We use a graph representation V, E of all moving object hypotheses within the time interval [1, T ]. Let h i t denote the i-th hypothesis generated at time t. Each hypothesis h i t is represented by a node in V . We define the neighborhood between two nodes in the graph by edges of two types: sibling edge and parent-child edge. Sibling edges are defined by: E sb = {(h i t , h j t )} with the condition that h i t and h j t have spatial overlap. Parent-child edges are defined by: E pc = {(h i t 1 , h j t 2 )} with the condition that h i t 1 and h j t 2 are of the same object class and h i t 1 (x, y)h j t 2 (x, y) < |t 1t 2 |v max , where . is the Euclidean distance, 1 ≤ |t 1t 2 | ≤ t max and v max is the maximum speed of the object class. Sibling edges represent exclusion relationship between hypotheses that are generated from the same moving evidence so that if one is selected then the other are excluded. Parent-child edges reflect possible temporal association between hypotheses.

We use N(.) to denote the neighbor set of a hypothesis in the graph structure, i.e. N(

h i t 1 ) = {h j t 2 |(h i t 1 , h j t 2 ) ∈ E}. Hypothesis h j t 2 ∈ N(h i t 1 ) belongs to the parent set N p (h i t 1 ), child set N c (h i t 1 )
, sibling set N s (h i t 1 ), when t 2 < t 1 , t 2 > t 1 and t 2 = t 1 respectively. Using the neighborhood graph helps the MCMC sampler to traverse the solution space effectively.

C. Markov chain dynamics

The Markov chain dynamics correspond to sampling the proposal distribution q(ω |ω n-1 ) described in Algorithm 1 (line 3). We assume that in the (n -1)-th iteration we have a sample ω n-1 = {τ 1 , ..., τ K } and now propose a candidate ω for the n-th iteration. Let V * denote the set of all unselected hypotheses and do not share any sibling edge with nodes in ω n-1 . In order for the Markov chain to traverse the solution space, we design the following reversible dynamics.

Track Extension/Reduction: The purpose of the extension/reduction move is to extend or shorten the estimated trajectories. For a forward extension, we select uniformly at random (u.a.r) a track τ k . Let τ k (end) denote the last node in the track τ k . Then select u.a.r node h ∈ {N c (τ k (end)) ∩V * } and append the new hypothesis h to τ k . Similarly, for a backward extension, we take a node h ∈ {N p (τ k (start)) ∩ V * }. We keep on extending the track τ k with a probability γ ∈ [0, 1].

The reduction move consists of randomly shortening a track τ k by selecting a cutting index r u.a.r from {2, ..., |τ k |-1}. In the case of a forward reduction the track τ k is shortened to {τ k (t 1 ), ..., τ k (t r )}, while in a backward reduction we take the sub-track {τ k (t r ), ..., τ k (t |τ k | )}.

Track Birth/Death: This move controls the creation of new track or termination of an existing trajectory. In a birth move, we select u.a.r a node h ∈ V * , associate it to a new track and increase the number of tracks K = K +1. The birth move is always followed by an extension move. From the node h we select the extension direction forward or backward u.a.r to extend the track τ K . If |τ K | < 2 the move is rejected.

For a death move, we simply choose u.a.r a track τ k and delete it.

Track Split/Merge: For a split move, we u.a.r select a track τ k with |τ k | ≥ 4 and a split point s ∈ {2, ..., |τ k | -2}. And we split τ k into two new tracks τ s 1 = {τ k (t 1 ), ..., τ k (t s )} and τ s 2 = {τ k (t s+1 ), ..., τ k (t |τ k | )} and increase the number of tracks K = K + 1.

Often, due to missing detection or erroneous detection, trajectories of objects are fragmented. The merge move provides the ability to link these fragmented sub-tracks. If a tracks's (τ k 1 ) end node is in the parent set of another track's (τ k 2 ) start node, this pair of two tracks is candidate for a merge move. We select u.a.r a pair of tracks from candidates and merge the two tracks into a new track τ k = {τ k 1 } ∪ {τ k 2 } and reduce the number of tracks K = K -1.

Track Switch: If there exist two break points p, q in two tracks τ k 1 , τ k 2 such that τ k 1 (t p ) ∈ N p (τ k 2 (t q+1 )) and τ k 2 (t q ) ∈ N p (τ k 1 (t p+1 )) as well, this pair of nodes is one candidate for a switch move. We u.a.r select a candidate and define two new tracks as:

τ k 1 = {τ k 1 (t 1 ), ..., τ k 1 (t p ), τ k 2 (t q+1 ), ..., τ k 2 (t |t k 2 | )} and τ k 2 = {τ k 2 (t 1 ), ..., τ k 2 (t q ), τ k 1 (t p+1 ), ..., τ k 1 (t |t k 1 | )}.
Track Diffusion: Randomly select a track τ k and an index d from {1, ..., |τ k |} and update the position and orientation of the object τ k (t d ) under some random noise.

Four first types of moves are temporal dynamics and the last one is a spatial dynamics. The temporal moves help to form tracks (data association) and the spatial move helps to improve the detection results. In each iteration, one of the above dynamics is chosen randomly. It is guaranteed that the Markov chain designed this way is ergodic (i.e., any state is reachable from any other state within finite number of iterations) and aperiodic (i.e., the Markov chain does not oscillate in a fixed pattern) since all of moves are stochastic.

D. Incremental computation

For each MCMC move, we need to compute the ratio π(ω ) π(ω) = P(ω |Z) P(ω|Z) in (18). In one iteration, our algorithm only changes maximum two tracks. Thus the new posterior probability can be computed more efficiently by incrementally computing it only within the related terms in (17). This is in contrast to the particle filters where the evaluation of each particle (joint state) needs the computation of the full joint likelihood. One more interesting property of the MCMC approach is that, it only needs to keep one hypothesis in the memory at one time instant compared with all hypotheses have to be maintained in case of tracking with MHT. Moreover, the execution time can be controlled by the number of sampling iterations n mc .

V. EXPERIMENTAL RESULTS

We test our approach described above using the Navlab datasets [START_REF] Wang | Navlab slammot datasets[END_REF]. The datasets were collected using a SICK laser scanner mounted on a moving vehicle. The vehicle was driven in urban streets with real-life traffics. The data was collected at 37.5 Hz with 0.5 degree resolution. The maximum measurement range of the scanner is 80 m.

We have implemented the described algorithm as an online process within a sliding window which contains T = 10 frames and only moving object hypotheses generated within this sliding window are stored in the graph structure. Actually, our tracking process is performed for every four "original" scans so that the data cycle time from frame to frame in our program is about 100 ms. For each time step when new measurements arrive, the solution obtained in the previous step is used to initialize a new MCMC search. Tracks are confirmed if their length are greater than three, otherwise they are considered false alarms. The MCMC sampler is run for a total of 250 iterations. The average computational time for the total detection and tracking process is about 60 ms on P4 3.0 GHz PC with unoptimized codes so that it can fulfill the real time requirement.

Fig. 8 shows an example of our detection and tracking algorithm in action. In the ego-vehicle's view, the detected moving objects and their trajectories are shown in pink color with current laser scan is in blue color. Moving objects in the situation include a bus moving in the opposite direction on the left, three cars moving ahead, two pedestrians walking on the left pavement and the other two pedestrians passing the intersection. The bus is divided into several segments and pedestrians are easy to be confused with noises and other small objects that make the detection and tracking challenging. However, thanks to our approach, the bus model helps connecting the discontinued segments and temporal information helps to distinguish pedestrians with noises and reduce ambiguities. All moving objects are identified and tracked successfully.

With initial evaluations, the MCMC detection and tracking outperforms the detection and tracking using MHT in our previous work [START_REF] Vu | Grid-based localization and local mapping with moving objects detection and tracking[END_REF] in terms of a higher detection rate and less false alarms. Particularly pedestrians are tracked successfully. In addition, with the use of object models, segmented objects caused by laser discontinuities are no longer a problem and tracking results are more accurate. Note that in our model-based approach moving objects are naturally classified. The readers can refer to: http://emotion.inrialpes.fr/˜tdvu/videos/ for more resulting videos.

VI. CONCLUSIONS AND FUTURE WORKS

We have presented a general framework for simultaneous detection, classification and tracking moving objects in real time using a laser scanner. The success of our approach mainly lies in the combination of a top-down analysis process and a bottom-up detection method that takes advantages of the computational efficiency of the detection and retains the optimality and robustness of the Bayesian formation from the global view. A model-based approach is introduced to help overcoming existing problems of detection and tracking using laser scanners. Experiments and initial evaluations on challenging real-life data show promising results.

Future works include a quantitative evaluation of our algorithm. We intend to integrate a road detection procedure in order to provide prior information on moving objects that certainly improve the effectiveness of the detection and tracking process. An optimization of code is ongoing.

VII. ACKNOWLEDGMENTS

Fig. 1 .

 1 Fig. 1. Known problems with laser-based detection and tracking. (a) an example of a car approaching the laser scanner; (b) car tracking using centers of laser impact bounding-boxes leads to incorrect result; (c) correct tracking using car model; (d)(e) objects can be divided into several segments making tracking harder that requires object merging, track grouping; (f) using car model can overcome these problems.

Fig. 2 .

 2 Fig. 2. Example of an interpretation of moving objects from laser data. (a) four scans consecutive: in blue is current scan and in green are scans in the past; (b) one possible solution including seven tracks of four cars and one bus represented by red boxes and one pedestrian represented by red dots which are imposed on the range data; (c) situation reference.

Fig. 3 .

 3 Fig. 3. Temporal consistency of a track. Obviously the arrangement of cars on the right is more relevant to a correct motion than that on the left.

Fig. 4 .

 4 Fig. 4. Object measurement likelihood computation.

Fig. 5 .

 5 Fig. 5. Four types of constraint used to compute the likelihood. The red dots are measurements that violate the laser visibility constraint.

7 :

 7 if P(ω n |Z) > P(ω * |Z) then ω * = ω n

Fig. 6 .

 6 Fig. 6. Object detection based on occupancy grid.

Fig. 7 .

 7 Fig. 7. Illustration of fitting object box model (green) to L-shape and Ishape segments (red). The last two shapes show that using box model helps connecting discontinued segments.

Fig. 8 .

 8 Fig. 8. Moving object detection and tracking in action.

http://www.prevent-ip.org/profusion

We thank Chieh-Chih Wang and members at Navlab group, the Robotics Institute, CMU, Pittsburgh, PA, U.S.A for providing the public dataset [3] which is used in this research for testing purpose. The work is supported by the European project PReVENT-ProFusion 1 .