Joint Conditional Random Field Filter for Multi-Object Tracking

Abstract

Object tracking can improve the performance of mobile robot especially in populated dynamic environments. A novel joint conditional random field Filter (JCRFF) based on conditional random field with hierarchical structure is proposed for multi-object tracking by abstracting the data associations between objects and measurements to be a sequence of labels. Since the conditional random field makes no assumptions about the dependency structure between the observations and it allows non-local dependencies between the state and the observations, the proposed method can not only fuse multiple cues including shape information and motion information to improve the stability of tracking, but also integrate moving object detection and object tracking quite well. At the same time, implementation of multi-object tracking based on JCRFF with measurements from the laser range finder on a mobile robot is studied. Experimental results with the mobile robot developed in our lab show that the proposed method has higher precision and better stability than joint probabilities data association filter (JPDAF).

Keywords

conditional random fields object tracking object detection information fusion

1. Introduction

Since object tracking can improve the performance of the robot in such tasks as person following, obstacle avoidance, map building and robot localization, etc. in dynamic environments by estimating the motion pattern of moving objects to predict their positions ahead of time, it has been regarded as one of the basic abilities the mobile robot should have.

Multi-object tracking is to estimate the states of unknown number of objects. The main difficulty in multi-object tracking comes from that it has to simultaneously solve the two problems: data association and state estimation. The approaches used widely for multi-object tracking include Nearest Neighbor (NN) approch, Joint Probabilitic Data Association Filter (JPDAF) (Fortmann, T.; Bar-Shalom, Y. & Scheffe, M., 1983), Multi-Hypothesis Tracking (MHT) (Cox, J. I. & Hingorani, L. S., 1996) and Particle Filter (PF) (Arulampalam, S.; Maskell, S.;Gordon, N. & Clapp, T., 2002) (Li, S. J.; Wang, H. & Chai, T.Y., 2006). Using only the observations closest to the predicated state, NN approach may be the simplest approach but it is not robust enough in many situations. JPDAF, extension of probabilistic data association filter to multi-object tracking, estimates the state by a sum of all the associations weighted by the probabilities that a measurement is associated to an object. In JPDAF only associations at one time period are considered and the number of objects is supposed to be known and fixed during the tracking process. Recently, Schluz proposed sample-based JPDAF to deal with tracking of variable number of objects by integrating JPDAF with particle filter (Schluz, D.; Burgard, W. & Fox, D. etc., 2003). MHT recursively estimates the association hypothesis and assumes that each measurement can be issued by a new object. Thereby MHT handles the entire life-cycle of tracks from creation and confirmation to deletion (Arras, K.; Grzonka, S.; Luber, M. & Burgard, W., 2008). PF-based approach estimates the states of objects by a set of weighted samples, so it is able to handle highly non-linear and non-Gaussian models (Khan, Z.; Balch, T. & Dellaert, F., 2005) (Hue, J. P.; Cadre, L. & Perez, P., 2002), but PF needs a large size of samples with the increasing of tracked objects, which will be intractable. Because these approaches are based on generative models which assume measurements are independent given the states of objects, they are not convenient to use the special and temporal inherent dependents among observation information.

Conditional Random Field model (CRF), a kind of discriminative model, is originally proposed for sequential data labeling (Lafferty, J., McCallum, A. & Pereira, F., 2001). Since CRF directly models the dependency between concurrent state and observation, it can be extended by introducing more general relationships between state and observations. CRF and its derivations have been successfully used for information extraction (Sunita, S. & William, W. C., 2005), image segmentation (Wang, Y.; Loe, K. F. & Wu, J. K. 2006) and action recognition (Wang, Y. & Mori, G., 2009). Some researchers have also tried to use CRF to solve the state estimation problems in a discriminative way. Limketkai proposed a novel version of discriminative PF called CRF-Filters and applied CRF-Filters to robot localization (Limketkai, B., Fox, D. & Liao, Lin., 2007). Hess proposed a discriminative method to train PF for multi-object tracking (Hess, R. & Fern, A., 2009). And Taycher combined CRF and grid filters for people tracking (Taycher, L., Demirdjian, D., Darrell, T. & Shakhnarovich, G., 2006).

In this paper a novel filter based on Conditional Random Field model (CRF) called Joint Conditional Random Field Filter (JCRFF) is proposed for multi-object tracking by abstracting the data associations to be a sequence of labels. Making no assumptions about the dependency structure between observations and allowing non-local dependencies between the state and observations, JCRFF can not only fuse multiple cues including shape information and motion information to improve the stability of tracking, but also integrate moving object detection and object tracking quite well.

2. Problem Definition

The objective of multi-object tracking is to estimate the states of the objects, but during the process of state estimation, the data association problem which determines the corresponding relation between observations and objects has to be solved simultaneously. In multi-object tracking approaches such as JPDAF and MTH, an implicit variable is used to represent data association. In order to fully utilize the spatial and temporal information of the observations to improve the performance of the tracking algorithm, data association is treated in an explicit way in this paper.

Suppose there are k objects that should be tracked at time step t. The state of the system can be x_t = {x¹_t, ηηη, x_t^k} where xⁱ_t is state of the ith object. And the observation sequence from time step 1 to time step t is z_1:t = {z₁, ηηη, z_t}, where z_t = {z¹_t, ηηη, z^v_t} represents the observation at time step t. The multi-object tracking problem can be defined as to estimate the state x_t of the k objects and the data association variable θ_t according to the observation sequence z_1:t, i.e. to estimate the probability distributions p(x_t, θ_t | z_1:t), where θ_t = {θ¹_t, θ²_t, ηηη, θ^v_t}. The value of variable θ^j_t that represents the label of the jth measurement z^j_t is from the set {-1, 0, 1, ηηη, k}. So θ_t is also called data association label sequence in this paper. If θ^j_t = −1, it means that z^j_t is issued from a new object. If θ^j_t = 0, it means that z^j_t is issued from background. And if θ^j_t > 0, it means that z^j_t is issued from an object whose label is θ^j_t.

According to the rules of conditional distribution, p(x_t, θ_t | z_1:t) can be decomposed:

p (x_{t}, θ_{t} | z_{1 : t}^{​}) = p (x_{t} | θ_{t}, z_{1 : t}^{​}) p (θ_{t} | z_{1 : t}^{​})

(1)

Since the state space of θ_t is very large for even a small number of objects, to solve equation (1) is not a trivial problem. In this paper a novel discriminative filter called joint conditional random filter is proposed to solve the multi-object tracking problem.

3. Joint Conditional Random Field Filter

Conditional Random Field model (CRF) is an undirected graphical model developed for labeling sequence data. Since CRF directly models the conditional distribution over the hidden variables given observations, CRF can handle arbitrary dependencies between the observations. In this section, a conditional random field model called joint conditional random field is designed to explain the calculation of the two conditional probabilities p(x_t | θ_t, z_1:t) and p(θ_t | z_1:t) in equation (1).

3.1 Joint Conditional Random Field (JCRF)

The undirected graph model of joint conditional random field proposed in this paper is shown in Fig.1. In the model, besides the observation data layer z there are two random fields: object state random field x and data association random field θ.

Figure 1.

Joint conditional random field

According to the model in Fig.1 and the definition of random field, the conditional probability p(θ_t | z_1:t) can be expressed as:

\begin{array}{l} p (θ_{t}^{​} | z_{1 : t}^{​}) = \frac{1}{Ω_{t}^{1}} \exp {\sum_{j = 1}^{v} [φ_{s}^{​} (θ_{t}^{j} | z_{1 : t}^{​}) + \\ \sum_{l \in N_{j}^{​}} φ_{r}^{​} (θ_{t}^{j}, θ_{t}^{l} | z_{1 : t}^{​})]} \end{array}

(2)

where Ω¹_t is a normalization parameter, N_j is the set of neighbors of node θ^j_t, φ_s(θ^j_t | z_1:t) is a potential function which reflects the information from a single node θ^j_t, and the potential function φ_r(θ^j_t, θ^l_t | z_1:t) imposes the spatial constraint from two neighbor nodes θ^j_t and θ^l_t. The detailed undirected sub-graph of random field for data association is shown in Fig.2.

Figure 2.

Random field for data association

According to Fig.2, the potential function φ_s (θ^j_t | z_1:t) in equation (2) can be:

\begin{array}{l} φ_{s} (θ_{t}^{j} | z_{1 : t}) = \frac{1}{| M_{j}^{​} |} \sum_{m \in M_{j}} \sum_{θ_{t - 1}^{m}} φ_{s}^{​} (θ_{t}^{j} | θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) φ_{s}^{​} (θ_{t - 1}^{m} | z_{1 : t - 1}^{​}) \\ \begin{matrix} ​ & ​ & ​ & = \end{matrix} \frac{1}{| M_{j}^{​} |} \sum_{m \in M_{j}} \sum_{θ_{t - 1}^{m}} ​ φ_{s}^{​} (θ_{t}^{j} | θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) φ_{s}^{​} (θ_{t - 1}^{m} | z_{1 : t - 1}^{​}) \end{array}

(3)

where M_j is the set of neighbors of node θ^j_t in temporal space and |η| represents the size of the set. Potential function φ_s(θ^j_t | θ^m_t-1, z_t, z_t-1) reflects the compatibility of observation data at time steps t and t-1; and φ_s (θ^m_t-1|z_1:t-1) reflects the information from the previous time steps.

And the potential function φ_r(θ^j_t, θ^l_t | z_1:t) in equation (2) can be:

φ_{r}^{​} (θ_{t}^{j}, θ_{t}^{l} | z_{1 : t}^{​}) = φ_{r}^{​} (θ_{t}^{j}, θ_{t}^{l}) + φ_{r}^{​} (z_{t}^{j}, z_{t}^{l} | θ_{t}^{j}, θ_{t}^{l})

(4)

where the potential function φ_r(θ^j_t,θ^l_t) reflects the utility that objects with label θ^j_t and θ^l_t are neighbors, and the potential function reflects the likelihood of z^j_t and z^l_t if their labels are θ^j_t and θ^l_t respectively.

3.2 JCRF Filter (JCRFF)

The conditional probability p(x_t | θ_t, z_1:t) means estimating the states of the objects with the information of observation data z_1:t and data association label sequence θ_t. In this paper a grid based approach is applied to partition the continuous space of state x_t into discrete grid space as is shown in Fig.3. Each grid is connected to all the nodes in field θ_t and the observations. According to this model p(x_t | θ_t, z_1:t) can be:

p (x_{t}^{​} | z_{1 : t}^{​}, θ_{t}^{​}) = \frac{1}{Ω_{t}^{2}} \exp {\sum_{i = 1}^{k} {\sum_{s = 1}^{n_{i}} φ_{s}^{​} (L_{t}^{i, s} | z_{1 : t}^{​}, θ_{t}^{​})}

(5)

Figure 3.

Random field for state estimation

where Ω²_t is a normalization parameter, n_i is the number of grids in influencing region of the ith object, L^i,s_t represents that the ith object is in grid g^s i.e. xⁱ_t ∈ g^s, it also means that the label of g^s is i.

The potential function φ_s(L^i,s_t | z_1:t, θ_t) can be defined as:

φ_{s}^{​} (L_{t}^{i, s} | z_{1 : t}^{​}, θ_{t}^{​}) = φ_{s}^{​} (z_{t}^{​} | L_{t}^{i, s}, θ_{t}^{​}) φ_{s}^{​} (L_{t}^{i, s} | z_{1 : t - 1}^{​})

(6)

where potential function φ_s(L^i,s_t | z_1:t-1) can be:

φ_{s}^{​} (L_{t}^{i, s} | z_{1 : t - 1}^{​}) = \frac{1}{{|M}_{s}^{​} |} \sum_{c \in M_{s}^{​}} φ_{s}^{​} (L_{t}^{i, s} | L_{t - 1}^{i, c}) φ_{s}^{​} (L_{t - 1}^{i, c} | z_{1 : t - 1}^{​})

(7)

Where M_s is the set of neighbors of grid g^s in time step t-1, and the potential function φ_s (L^i,s_t | L^i,c_t-1) reflects the motion constraint of the ith object.

The potential function φ_s (z_t | L^i,s_t, θ_t) in equation (6) reflects the utility of getting observation data z_t if xⁱ_t ∈ g^s. It can be:

φ_{s}^{​} (z_{t}^{​} | L_{t}^{i, s}, θ_{t}^{​}) = \sum_{j = 1}^{v} φ_{s}^{​} (z_{t}^{j} | L_{t}^{i, s}, θ_{t}^{j})

(8)

3.3 Inference of JCRFF

The objective of inference is to estimate the state of the objects and the data association sequence simultaneously according to the observation sequence z_1:t. In order to reduce the computational burden of JCRFF so that it can run in real time, an approximate inference algorithm based on belief propagation (Felzenszwalb, F. P. & Huttenlocher P. D., 2007) is proposed for JCRFF. The main idea of the inference algorithm is to decompose the random field into trees and estimate the belief of data association sequence θ_t and that of state x_t in turns. The inference algorithm is described in algorithm 1.

In algorithm 1 the function createTree(r) will return a tree whose root is node r, and whose children are the nodes directly connected to node r. For example, the root of the tree returned by createTree(θ¹_t) is node θ¹_t and its children are nodes connected to node θ¹_t by red edges in Fig.2. And the root of the tree returned by createTree(g^s) is grid g^s, and its children are the nodes that connected to grid g^s by red edges in Fig.3. The function label(g^s) returns the set of labels of objects that may be in grid g^s.

Algorithm 1. Inference of JCRFF

Input: z_1:t; // observation sequence Output: x_t, //state of objects θ_t; //data association sequence 1. steps:=0, th := 10; //initialization 2. while(th>ɛ & steps<MML:MaxStep) 3. for j: = 1 to v 4. T^j_t := createTree(θ^j_t); //create the tree of θ^j_t 5. doBP(T^j_t); // run belief propagation 6. end for 7. for s := 1 to Ng // Ng is the number of grids 8. if(label(g^s)∩{1,2,…,k} !=φ) 9. T^s_t := createTree(g^s); 10. doBP(T^s_t); //run belief propagation 11. end if 12. end for 13. th := checkConvergence(); // check for convergence 14. steps++; 15. end while 16. < x_t, θ_t > := getResults(); //return results

3.4 Parameter Learning

In JCRFF the potential function will be composed of some feature functions and parameters according to the application systems. The feature functions and parameters of JCRFF for multi-object tracking with laser range finder will be explained in section 4.

In parameter learning, the training data includes observation sequence z_1:t, actual state of the tracked object x^*_1:t = {x¹_1:t, x²_1:t, ηηη, xⁿ_1:t} and data association sequence θ^*_0:t. The objective of parameter learning is to learn the parameters which will maximize the logarithmic likelihood log p(x^*_1:t | z_1:t, θ^*_1:t)p(θ^*_1:t | z_1:t). The piecewise pseudo-likelihood based method (Sutton, C. & McCallum A., 2007) is applied to training in this paper.

3.5 New Object and Object Disappearance Detection

New object detection and object disappearance detection, two difficult problems in multi-object tracking, can be solved conveniently using JCRFF.

Usually the appearance of a new object will blot out the background or other objects. So in JCRFF, the detection of new objects is to concern the regions in data association sequence θ_t whose labels become −1 at time t. And if the size of the region is larger than a threshold T, the region will be considered a candidate of new object.

In process of multi-object tracking, an object may disappear due to going out the range of sensor view or the occlusion of other objects. So in JCRFF, the disappearance detection of the ith object is to check whether the size of the region with label i in data association sequence θ_t is larger than threshold T.

4. Multi-object Tracking with Laser Range Finder

Because laser range finder can get precise range information of objects, it has been widely used in modern robot system. In this section the implementation details of JCRFF-based multi-object tracking with laser range finder will be discussed.

4.1. Preprocessing of Laser Readings

The observation data from laser range finder can be represented by sequence z_t = {z¹_t, ηηη, z^v_t}, where v is the number of laser readings. And z^j_t = {α^j_t, d^j_t} is a 2-dimensional vector where α^j_t ∈ [-90°, +90°] is the angle of the jth reading and d^j_t is the distance of the jth reading. One of the laser scan data is shown in Fig.4 (a). Because the label set size of each laser reading i.e. the number of candidate labels of each node in field θ_t will affect the computational burden of JCRFF greatly, some special techniques are used to preprocess the laser readings.

Figure 4.

Laser reading

Since the laser readings corresponding to objects will form concave regions, the concave regions will be segmented out in preprocessing step and called candidate object regions which are portrayed in red in Fig.4 (b). Suppose the set of candidate object regions is Ψ_t = {Ψ¹_t, ηηη, Ψ^c_t}, the subset of candidate object regions Φⁱ_t = {Ψ^{e
₁}_t, ηηη, Ψ^{e
_n}_t} that corresponds to the ith object will be determined by checking whether the candidate object regions are in the influencing region of the ith object according to state xⁱ_t-1, where e_i ∈ {1, ηηη, c} and c is the size of set Φⁱ_t. The label set of each laser reading will be determined by algorithm 2. In algorithm 2 function doSegment(z_t) will return the set of candidate object regions Ψ_t = {Ψ¹_t, ηηη, Ψ^c_t} and the set Φ_t = {Φ¹_t,…, φ^k_t}. Function isInSet will return whether or not laser reading z^j_t belong to any element of a set of candidate object region.

Algorithm 2. Preprocess of Laser Readings

Input: z_t; // observation data Output: l_t = {l¹_t,…, l^v_t}; // label set of laser readings 1. <Ψ_t, Φ_t > =doSegment(z_t); // segmentation of z_t 2. for j := 0 to v 3. l^j_t := {0}; // init of l^j_t // testing if z^j_t belong to an elememt of Ψ_t 4. b := isInSet(z^j_t, Ψ_t); 5. if(b) 6. l_t^j = l_t^j ∪{-1}; // jth reading may be new object 7. end if 8. for i:= 0 to k 10. b:= isInSet(z^j_t, φⁱ_t); 11. if (b) 12. l_t^j = l^j_t∪{i}; 13. end if 14. end for // end for i 15. end for // end for j

4.2 Neighborhood Relation in Temporal Space

In JCRFF based multi-object tracking, the temporal neighbors of label node θ^j_t at time step t must be determined before inference, since it is the base to calculate potential function φ_s(θ^j_t | z_1:t) in equation (3). In this paper, the neighborhood is determined according to the motion information of the robot. Suppose the motion information from the odometer at time t is I^r_t = (Δx,Δy,Δβ), where Δx and Δy are the distance that the robot moved in x direction and y direction respectively and Δβ is the angle that the robot turned from time t-1 to t. The temporal neighbors of label node θ^j_t will be determined by the following two steps:

Project laser readings z_t from frame R_t to frame R_t-1 according to motion information I^r_t, where R_t and R_t-1 are frames of the robot at time step t and t-1 respectively:

{\tilde{z}}_{t}^{j} = [\begin{array}{l} d_{t}^{j} \cos α_{t}^{j} \\ d_{t}^{j} \sin α_{t}^{j} \end{array}] [\begin{array}{l} \cos △ β \sin △ β \\ - \sin △ β \cos △ β \end{array}] + [\begin{array}{l} △ x \\ △ y \end{array}]

The laser reading z^p(j)_t-1 from z_t-1 nearest to z˜^j_t will be found, and the label nodes corresponding to the laser readings of z_t-1 that are in a window with size w by w that is centered at p(j) will be the neighbors of node θ^j_t.

4.3 System Models

Design of system models is to design the detail format of potential functions in JCRFF according to the properties of the applied sensor, i.e. laser ranger finder in this paper.

1) Potential function φ_s(θ_t^j | θ^m_t-1, z_t, z_t-1) :

\begin{array}{l} φ_{s}^{​} (θ_{t}^{j} | θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) = λ_{d}^{​} f_{d}^{​} (θ_{t}^{j}, θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) \\ \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} ​ & ​ \end{matrix} & ​ \end{matrix} & ​ \end{matrix} & ​ & ​ \end{matrix} + λ_{a}^{​} f_{a}^{​} (θ_{t}^{j}, θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) \end{array}

(9)

where Λ_i(i ∈ {d,a}) is parameter, f_i (η)(i ∈ {d, a}) is feature function.

f_{d}^{​} (θ_{t}^{j}, θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) = {\begin{cases} \begin{matrix} - d & i f_{​} θ_{t}^{j} = θ_{t - 1}^{m} \end{matrix} \\ \begin{matrix} \frac{- 1}{(d + δ)} & i f_{​} θ_{t}^{j} \neq θ_{t - 1}^{m} \land θ_{t}^{j} \in {0, - 1} \end{matrix} \\ 0 \begin{matrix} ​ & ​ & e l s e \end{matrix} \end{cases}

where d =|z˜^j_t - P(z^m_t-1)| and function P(z^m_t-1) returns the orthogonal coordinates of z^m_t-1 in the frame of robot, and δ is a constant parameter. This feature function means that if θ^j_t = θ^m_t-1 we will get larger utility with smaller difference between z^j_t and z^m_t-1; and if θ^j_t ≠ θ^m_t-1 and θ^j_t is background or new object, we will get larger utility with larger difference between z^j_t and z^m_t-1; otherwise this feature function will not affect the potential.

f_{a}^{​} (θ_{t}^{j}, θ_{t - 1}^{m}, z_{t}^{​}, z_{t - 1}^{​}) = {\begin{cases} \begin{matrix} - d' & ​ & \begin{matrix} i f_{​} θ_{t}^{j} = θ_{t - 1}^{m} \end{matrix} \end{matrix} \\ \begin{matrix} \frac{- 1}{d' + δ} & i f_{​} θ_{t}^{j} \neq θ_{t - 1}^{m} \end{matrix} \land θ_{t}^{j} \in {0, - 1} \\ 0 \begin{matrix} \begin{matrix} \begin{matrix} ​ & ​ \end{matrix} & ​ \end{matrix} & e l s e \end{matrix} \end{cases}

where d' =| (z^j+u_t - z^j-u_t) - (z^m+u_t-1 - z^m-u_t-1) | and u is a constant parameter. This feature function means that if θ^j_t = θ^m_t-1, we will get larger utility with smaller difference between local shapes around z^j_t and z^m_t-1; and if θ^j_t is background or new object but θ^m_t-1 is not, we will get larger utility with larger difference between the local shapes around z^j_t and z^m_t-1; otherwise this feature function will not affect the potential.

2) Potential function φ_r (z^j_t, z^l_t | θ^j_t, θ^l_t):

φ_{r}^{​} (z_{t}^{j}, z_{t}^{l} | θ_{t}^{j}, θ_{t}^{l}) = λ_{c}^{​} f_{c}^{​} (θ_{t}^{j}, θ_{t}^{l}, z_{t}^{j}, z_{t}^{l})

(10)

where Λ_c is parameter, f_c (θ^j_t, θ^l_t, z_1:t) is feature function.

f_{c}^{​} (θ_{t}^{j}, θ_{t}^{l}, z_{t}^{j}, z_{t}^{l}) = {\begin{cases} - d_{c} \begin{matrix} \begin{matrix} i f_{​} \end{matrix} θ_{t}^{j} = θ_{t}^{l} & ​ \end{matrix} \\ \begin{matrix} - 1 / (d_{c} + δ) & i f θ_{t}^{j} \neq θ_{t}^{l} \end{matrix} \end{cases}

where d_c =| z^j_t - z^l_t|. This feature function means that we will get larger (smaller) utility with smaller difference between z^j_t and z^l_t if θ^j_t = θ^l_t (if θ^j_t ≠ θ^l_t).

3) Potential function φ_r (θ^j_t, θ^l_t):

φ_{r}^{​} (θ_{t}^{j}, θ_{t}^{l}) = {\begin{cases} \begin{matrix} λ_{n}^{​} & i f θ_{t}^{j} \neq θ_{t}^{l} \land (θ_{t}^{j} = 0 \lor θ_{t}^{l} = 0) \end{matrix} \\ \begin{matrix} λ_{n} | x_{t - 1}^{θ_{t}^{j}} - x_{t - 1}^{θ_{t}^{l}} | & e l s e \end{matrix} \end{cases}

This potential function means that utility that an object is adjacent to background is constant and that objects will be more likely to be adjacent to each other if the difference between x^{θ^j_t}_t-1 and x^{θ^l_t}_t-1 is smaller.

4) Potential function φ_s(L^i,s_t | L^i,c_t-1):

In this paper the state of moving objects is xⁱ_t = [xⁱ_t, yⁱ_t, vⁱ_x,t, vⁱ_y,t], where (xⁱ_t, yⁱ_t) represents the position of the ith object, vⁱ_x,t and vⁱ_y,t represent the velocity of object in x and y direction respectively.

φ_{s}^{​} (L_{t}^{i, s} | L_{t - 1}^{i, c}) = \sum_{d \in {x, y}} λ_{d}^{​} f_{d}^{​} (g_{​}^{s}, g_{​}^{c}, v_{d, t - 1}^{i})

(11)

where Λ_d and γ_d are parameters, and:

f_{d}^{​} (g_{​}^{s}, g_{​}^{c}, v_{d, t - 1}^{i}) = | (g_{d}^{s} - g_{d}^{c}) - v_{d, t - 1}^{i} |

where g^s_d is the position of grid s in direction d.

5) Potential function φ_s(z_t^j | x^is_t, θ^j_t):

φ_{s}^{​} (z_{t}^{j} | L_{t}^{i, s}, θ_{t}^{j}) = {\begin{cases} \begin{matrix} λ_{s}^{​} (d_{x}^{​} + d_{y}^{​}) & i f θ_{t}^{j} = i \end{matrix} \\ \begin{matrix} 0 & e l s e \end{matrix} \end{cases}

(12)

where Λ_s is parameter, d_x =| g^s_x - d^j_t cos(α^j_t)| and d_y =| g^s_y - d^j_t sin(α^j_t)|.

4.4 Multi-object Tracking Algorithm

Multi-object tracking algorithm based on JCRFF is described in algorithm 3. In the algorithm function doPredict will predict the state of the objects using motion model of objects, i.e. will predict which grids may be occupied by the ith object; function detectNewObject and deletDisObject will detect new objects and delete disappeared objects respectively according to data association sequence θ_t.

Algorithm 3. Multi-object Tracking Algorithm

Input: z_t,// observation sequence Output: x_t, //state of objects at t θ_t; //data association sequence at t 1. z_1:t = z_1:t-1 ∪ z_t 2. doPredict(x_t-1); //predict the state of objects // do laser reading preprocess using algorithm 2 3. doPreprocess(z_t); //do inference using algorithm 1 4. <x_t, θ_t > :=Inference(z_1:t); 5. detectNewObject(θ_t);//detect new object 6. deletDisObject(θ_t); //delete disappeared objects

5. Experimental Results and Analysis

Experiments are carried out with a robot developed by our lab, as is shown in Fig. 5. The robot is equipped with a SICK laser range finder whose range of view angle is set 180 degree with the precision of 1 degree. And the frequency of the CPU of the processor computer is 2.4GHz. The experimental environment is two rooms in our lab building. At the same time the new object detection threshold T equals 4 and the size of the window w for temporal neighbor determination is 7.

Figure 5.

Robot used in experiments

Firstly, performance of new object detection using JCRFF is tested. There are two cases in new object detection: the first case (Case 1) is that the new object moves into sensor's view slowly, and the second case (Case 2) is that the new object has already existed in the view of the sensor but starts to move at some moment. In both cases the object will move randomly. The ratio of successful detection of new objects and the ratio of the false detection which labels static background to be a new object are tested. The experimental results in 30 times of test of JCRFF and JPDAF (Schluz, D.; Burgard, W. & Fox, D. etc., 2003) are compared in table 1. The experimental results demonstrate that for object detection in both cases JCRFF performs better than JPDAF, and that the performances in false detection of the two algorithms are similar.

Table 1.

Experimental results of new object detection

Method	Success ratio		False ratio
Method	Case 1	Case 2	False ratio
JCRFF	99%	93%	13%
JPDAF	87%	81%	16%

Secondly, the precision and success ratio of multi-object tracking are tested. In the test, the robot with SICK laser range finder called sick-Robot is commanded to track moving objects which are two other robots called target-robots. The sick-robot will follow one of the target-robots which run randomly in the environment and the other target-robot is regarded as an interferential object which will run into the view of the sick-robot randomly. In the tracking process, the odometer information of the robots which are supposed to be the precise state of the robots will be recorded. One of the experimental results is shown in Fig.6, in which the lines with circles and the red dashed lines represent the trajectory of objects estimated using JCRFF and odometer information respectively, and the wide real line represents the trajectory of the sick-robot. From the figure we can see that JCRFF can estimate the state of the objects fairly well. The object tracking errors of JCRFF and JPDAF that is the difference between objects' state estimated by object tracking algorithms and odometer information are shown in Fig.7, which shows that the tracking error of JCRFF is much smaller than that of JPDAF. And at the same time, in 30 times of experiments the success ratio of object tracking is 100% for JCRFF and 90% for JPDAF.

Figure 6.

Trace of tracked objects

Figure 7.

Trace error of objects in tracking

Lastly, the computational time of the multi-object tracking algorithms is tested. The computational time of JCRFF and JPDAF in tracking two moving objects are shown in Fig.8. From Fig.8 we can see that in the time steps before 200 when there are a few interferential regions in background, the computational time of JCRFF is larger than that of JPDAF, but after time step 200 when the interferential regions increase, the computational time of JCRFF is smaller than that of JPDAF. So JCRFF is preferable in complex environments.

Figure 8.

Computational time of each step in tracking

6. Conclusions

A new kind of joint conditional random field filter (JCRFF) based on conditional random field with hierarchical structure is proposed for multi-object tracking with a mobile robot system. JCRFF based multi-object tracking algorithm can not only simultaneously perform new object detection and object tracking but also integrate local shape and motion information of moving objects to improve the precision of state estimation. Experimental results of multi-object tracking with laser range finder sensor prove that JCRFF has higher precision and better stability than JPDAF in complex environments.

Footnotes

7. Acknowledgements

This paper is supported by the Fundamental Research Funds for the Central Universities(No. 2009ZM0123); the Science and Technology Planning Project of Guangdong Province, China (No. 2009A040300008) and the Educational Commission of Guangdong Province (No. x2jsN9090170).

References

Fortmann

Bar-Shalom

& Scheffe

(1983). Sonar tracking of multiple targets using joint probabilistic data association. IEEE Journal of Oceanic Engineering, Vol. 8, No.3, July 1983, pp. 173–184

Cox

J. I.

& Hingorani

L. S.

(1996). An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, No. 2, 1996, pp. 138–150

Arulampalam

Maskell

Gordon

& Clapp

(2002) “A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking,” IEEE Trans. Signal Processing, Vol. 50, No. 2, Feb. 2002, pp. 174–188

S. J.

Wang

& Chai

T. Y.

(2006). A t-Distribution Based Particle Filter for Target Tracking, Proc. of American Control Conference, pp. 2191–2196, June 14–16, 2006

Schluz

Burgard

& Fox

, etc. (2003). People tracking with a mobile robot using sample-based joint probabilistic data association filters. International Journal of Robotics Research, Vol. 22, No. 2, 2003, pp. 99–116.

Arras

Grzonka

Luber

& Burgard

(2008). Efficient people tracking in laser range data using a multi-hypothesis leg-tracker with adaptive occlusion probabilities, 2008 IEEE International Conference on Robotics and Automation, pp. 1710–1715, Pasadena, USA, May 19–23, 2008

Khan

Balch

& Dellaert

(2005). MCMC-based particle filtering for tracking a variable number of interacting targets. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 11, 2005, pp. 1801–1981

Hue

J. P.

Cadre

& Perez

(2002). Tracking multiple objects with particle filtering. IEEE Transactions on Aerospace and Electronic Systems, Vol. 38, No. 3, 2002, pp. 791–812

Lafferty

McCallum

& Pereira

(2001). Conditional random fields: probabilistic models for segmenting and labeling sequence data, Proc. of the International Conference on Machine Learning, pp. 282–289, 2001

10.

Sunita

& William

W. C.

(2005) Semi-Markov Conditional Random Fields for Information Extraction. In Advances in Neural Information Processing Systems, pp. 1185–1192 2004

11.

Wang

Loe

K. F.

& Wu

J. K.

(2006). A dynamic conditional random field model for foreground and shadow segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 28, 2006, pp. 279–289

12.

Wang

& Mori

(2009). Max-Margin Hidden Conditional Random Fields for Human Action Recognition, IEEE Conference on Computer Vision and Pattern Recognition, pp. 872–879, 2009

13.

Limketkai

Fox

& Liao

(2007). CRF-Filters: Discriminative Particle Filters for Sequential State Estimation. Proc. of the IEEE. International Conference on Robotics & Automation, pp. 3142–3147, 2007

14.

Hess

& Fern

(2009). Discriminatively trained particle filters for complex multi-object tracking. IEEE Conference on Computer Vision and Pattern Recognition, pp.240–247, 2009

15.

Taycher

Demirdjian

Darrell

& Shakhnarovich

(2006). Conditional Random People: Tracking Humans with CRFs and Grid Filters, Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 222–229, 2006

16.

Felzenszwalb

F. P.

& Huttenlocher

P. D.

(2006). Efficient Belief Propagation for Early Vision. International Journal of Computer Vision, Vol. 70, No. 1, October 2006, pp. 41–54

17.

Sutton

& McCallum

(2007). Piecewise pseudo-likelihood for efficient training of conditional random fields, Proc. of the 24th international conference on Machine learning, pp. 863–870, 2007