People Tracking with Anonymous and ID-Sensors Using Rao-Blackwellised Particle Filters

1 Introduction

Accurate and reliable tracking of people using sensors placed throughout an environment is a fundamental problem relevant to several research communities. Knowing the locations of people is of critical importance for research investigating high­ level state estimation, plan recognition, and learning of human activity patterns for applications such as work flow enhance­ ment and health monitoring.

Over the years, many location estimation approaches have been introduced using sensors such as cameras, laser range­ finders, infrared and ultrasound sensors, and wireless net­ working infrastructure [Hightower and Borriello, 2001]. A crucial aspect of these sensors is whether they provide ex­ plicit information about the identity of a person. Anony­ mous sensors such as radar, reflective ultrasound transducers, and scanning laser range-finders provide accurate location and appearance information, but do not provide explicit identity information. !d-sensors like infrared and ultrasound badge systems do provide explicit object identity information, but with relatively coarse location information [Want eta/., 1992; Priyantha et al., 2000]. Various techniques have been pro­ posed for tracking with multiple anonymous sensors or multi­ ple id-sensors, but the problem of integrating anonymous and id sensor information has not been addressed so far. In this paper we present an approach that combines the accuracy ben­ efits of anonymous sensors with the identification certainty of id-sensors.

Our approach uses Rao-Biackwellised particle filters to ef­ ficiently estimate the locations and identities of multiple ob­ jects. Each particle represents a history of associations be­ tween object tracks and observations. For each particle, the individual objects are tracked using Kalman filters. Since the initial id uncertainty makes a sample-based representation of id assignments extremely inefficient, our approach starts by tracking objects using only anonymous sensors and ef­ ficiently representing estimates over object id's by keeping track of sufficient statistics. Once the id estimates are cer­ tain enough, the approach switches to sampling id assignments as well resulting in a fully Rao-Biackwellised particle filter over both object tracks and id assignments. When applied to anonymous sensors only, our method results in a new Rao­ Blackwellised approach to multi-hypothesis tracking, which has gained substantial attention in the target tracking commu­ nity [Bar-Shalom and Li, 1995].

This paper is organized as follows: Section 2 clarifies the problem. Section 3 then presents our Rao-Blackwellised par­ ticle filter approach to tracking multiple objects using only anonymous sensor information and Section 4 extends the ap­ proach to incorporate id-sensors. Our implementation and ex­ perimental results are presented in Section 5, followed by a discussion.

2 Problem Description

Figure 1 illustrates the problem of tracking multiple people with anonymous and id-sensors. The solid and dotted lines are the trajectories of person A and B, respectively. In the beginning, the identity of the two people is not known. As they walk, the anonymous sensor observes their locations fre­ quently. Since the people are far enough apart, their positions can be tracked reliably using the anonymous sensor. How­ ever, until they reach id-sensor areas 3 and 4, both trajectories have the same probability of belonging to either person A or B. Hence there are two different hypotheses for the id's of the two trajectories. After passing through the coverage of id-sensors 3 and 4, the ambiguity is resolved and both trajectories' id's are determined. Then, after the paths cross there is confusion about the continuation of the two tracks. When the people leave the light gray area the anonymous sensor can not deter­ mine which observations to associate with which trajectory. This problem is known as the data association problem in the multitarget tracking community [Bar-Shalom and Li, 1995]. Were there no id-sensors, it would be impossible to resolve this ambiguity. In our scenario, the ambiguity can be resolved as soon as the people reach the areas covered by id-sensors 5 and 6. To do so, however, it is necessary to maintain the hy­ potheses for both possible track continuations, A going down and B going up, orB going down and A going up.

The use of a combination of anonymous and id-sensors re­ quires us to solve two types of data association problems. The first problem is the classic multitarget tracking problem of assigning anonymous observations to object tracks. This data association problem has to be solved at each point in time, resulting in m!k possible associations for tracks oflength k involving m people. Fortunately, the probability distribu­ tions over these anonymous assignments are typically highly peaked, thereby allowing an efficient, sample-based represen­ tation of assignments. The second problem is the one of es­ timating the id of individual objects/tracks. As with anony­ mous assignments there are m! possible assignments ofid's to tracks. Fortunately, the number of id assignments does not in­ crease over time since the identity of objects does not change. However, due to the low spatial resolution of id-sensors, the posterior over id assignments is almost uniform during early stages of the estimation process (see Figure 1). For such "flat" distributions, a sample-based representation requires in the or­ der of m! samples, which is certainly not feasible for online tracking.

Figure 2 shows the graphical model for this tracking prob­ lem. Here, time is indexed by subscripts and the current time is denoted by k. xk := { xl, x~, .. . , x;n are the current po­ sitions of them people being tracked. Following standard no­ tation in the tracking community, observations are denoted by zk and the complete sequence of observations up to time k is given by zl:k (we use hat and tilde to distinguish anonymous from id observations). The associations between object tracks X~ and observations are given by assignment matrices Bk and ek. For instance, Bk(i,j) is one ifBk assigns anonymous ob­ servation z~ to object xi, and zero otherwise. The observa­ tions only depend on the current object positions and assign­ ments.

The goal of tracking is to estimate the posterior over the state Xk based on all sensor information available up to time k. A factored representation of this tracking problem allows us to use Rao-Blackwellised particle filters (RBPF) which sample assignments and track the objects using a bank of m Kalman filters for each sample [Doucet eta/., 2000]. However, due to the large number of anonymous assignments and the "flat" distributions over id assignments, a straightforward implemen­ tation of RBPFs would require a prohibitive number of sam­ ples. In the next section we describe how to efficiently sample anonymous assignments over time. The resulting algorithm, MHT-RBPF (multi-hypothesis tracking RBPF), can track mul­ tiple objects using anonymous sensor information. Then, in section Section 4, we will describe how to extend MHT-RBPF to incorporate id-sensors.

3 MHT-RBPF: Rao-Blackwellised Particle Filters for Multi-hypothesis Tracking

Since the assignments between observations and ob­ jects/tracks are not given, we need to estimate the posterior over both object states Xk and assignments el:k. This joint posterior can be factorized by conditioning the state Xk on the assignments el:k:

The key idea ofRao-Blackwellised particle filters is to com­ pute (1) by sampling assignments fromp(Bl:k I Zl:k) and then computing the state Xk conditioned on each sample. More specifically, each sample represents a history of data associ­ ations {)l:k and is annotated with a bank of m Kalman fil­ ters, one for each tracked person. The Kalman filters are conditioned on the data associations provided by the sample and thus can be updated efficiently using standard Kalman filter update rules for known data association [Bar-Shalom and Li, 1995]. The Kalman filter estimates, or tracks, tk = (f.L1, L:i};=1, .. . ,m are represented by the mean and covariance of the persons' locations.

RBPF generate assignments incrementally by maintaining sample sets containing assignment histories distributed ac­ cording to the posterior given by the rightmost term in ( 1 ). More specifically, at time k a sample set sk = { s~"), wi") I 1 :::; ~ :::; N} contains N weighted samples, where each sample s~") = (t~"), en) consists of a history of assignments and the current position estimates for the m objects. The generic RBPF algorithm generates a set Sk from the previous sample set Sk_1 and an observation zk by first generating new assignments {)k distributed according to the posterior p(Bl:k I zk). Each such assignment specifies which observations in Zk be­ long to which object track. The final step consists of updating the Kalman filter tracks of each sample using the observations assigned to them by the sample [Doucet eta/., 2000].

3.1 Importance Sampling with Lookahead

The efficiency of RBPFs strongly depends on the number of samples needed to represent the posterior p( el:k I Zl:k) . In this section we will devise an efficient algorithm for generat­ ing such assignments/samples. Due to the sequential nature of the estimation process, samples must be generated from the assignments of the previous time step. The posterior at time k is given by

Here, (2) follows from Bayes rule, and (3) follows from (2) since the position tracks tk_1 of the objects are sufficient statistics for the previous observations Z1 :k-1 and assignments e1:k-1·

Unfortunately, in most cases it is impossible to sample di­ rectly from (3). The approach most commonly used in particle filters is to evaluate (3) from right to left in a three stage process [Doucet eta/., 2001] : First, draw samples s~") from the previous sample set using the importance weights, then draw for each such sample a new sample from the predictive distribution p(Bk I t~"~ 1 ) , and finally weight these samples pro­ portional to the observation likelihood p(zk I ei"), t~"~1). The last step, importance sampling, adjusts for the fact that sam­ ples are not drawn from the actual target distribution. This approach has two main sources of inefficiency. First, the samples of the previous sample set are distributed according to p(Bl:k- 1 I Zl:k- d and not the desired p(Bl:k- 1 I zl:k), the rightmost term of the target distribution (3) [Morales­ Menendez et a/., 2002]. The second source of inefficiency is that sampling from the predictive distribution in the sec­ ond sampling step can be very inefficient if the observation likelihood p(zk 1 ek, tk-d is highly peaked compared to the predictive distribution p( ek I tk- I) [Pitt and Shephard, 1999]. The second problem is extremely severe in our context since the predictive distribution for assignments is virtually uniform while the posterior is typically concentrated on a small set of assignments [Bar-Shalom and Li, 1995].

MCMC Sampling from the optimal distribution

Let us first discuss how to address the second problem, i.e. the problem of drawing samples from the posterior distribu­ tion (3), given the previous sample set. Conditioned on a specific assignment e~~L 1' the optimal sampling distribution fol­ lows from (3) as

It is possible to efficiently generate samples from this dis­ tribution using Markov Chain Monte Carlo (MCMC) tech­ niques [ Gilks et a/., 1996]. We apply a version of the Metropolis-Hastings algorithm that has been adapted specif­ ically to the data association problem [Dellaert eta/., 2003]. Here, the idea of Metropolis-Hastings is to sample states from an ergodic Markov chain with the posterior as stationary distri­ bution. Such a Markov chain is constructed by first choosing a candidate for the next state s' given the current state s accord­ ing to a proposal distribution q( s' I s) . This state transition is accepted with probability

where n( s) is the intended stationary distribution. In our case the states are the possible assignments {)k and n( s) is the optimal sampling distribution (4). The efficiency of the Metropolis-Hastings method strongly depends on the choice of the proposal distribution q. We use an efficient approach called smart chain flipping. Smart chain flipping permutes the assignments of a subset of the objects on each transi­ tion, where the actual choice already takes the individual as­ signment likelihoods into account. This approach has been shown to result in improved mixing rates on assignment prob­ lems [Dellaert eta/., 2003].

Assignment lookahead

As mentioned above, another source of inefficiency is the fact that the previous sample set does not consider the most recent observation. This problem can be greatly reduced by using the most recent observation to re-weight the sam­ ples of the previous sample set [Pitt and Shephard, 1999; Morales-Menendez et a/., 2002]. The weight for a sample s~"~ 1 is given by dividing the target distribution p(Bl:k- 1 I zl:k) by the sampling distribution p(Bl:k-1 I Zl:k-1), which can be shown to result in

Table 1: MHT-RBPF algorithm.

That is, the importance weight of a sample is given by the abil­ ity of the tracks associated with the sample to predict the next observation. Accurate computation of the right term in (6) requires summation over all possible next assignments Bk> as done by [Morales-Menendez et al., 2002]. Since in our case the number of assignments can be prohibitively large, we esti­ mate (6) using the samples generated in the MCMC step. Unfortunately, computing p(zk I t~"~ 1 ) is equivalent to comput­ ing the normalization factor of a Markov chain, which is not possible in general [Gilks et a!., 1996]. In our case, however, we do not need the absolute value of the normalization con­ stant for each chain, but only the value relative to the normal­ izers of the other Markov chains. Since the distributions (4) have similar shapes for all chains (they are highly peaked), we can estimate the relative normalization constants by the aver­ age probabilities of the samples in the different Markov chains.

More specifically, let M samples be drawn from each '(< m) Markov chain. Let Bk ' denote the m-th sample drawn from the Markov chain associated with sample s ~·~ 1 . Then the up­ dated weight w~·~ 1 of this sample is given by

where proportionality is such that all weights sum up to one.

MHT-RBPF Algorithm

The algorithm is summarized in Table 1. In step 4, new sam­ ples are generated from the previous sample set. The aver­ age probability of these samples is used to estimate the looka­ head/predictive weights of each sample of the previous set (step 6). This step also involves a normalization so that the weights sum up to one. In step 8, a sample is drawn from the previous sample set Sk- 1. Then, for each sample drawn from sk-1, we draw an assignment e~·) from the posterior re-using the samples generated in the Markov chains in step 4. Step 10 updates the actual position estimates for the individual objects, using the corresponding assignment e~·).

4 Tracking with Anonymous and ID-Sensors

In principle, MHT-RBPF's can be readily extended to include id-sensors. Instead of only sampling anonymous assignments, it is possible to sample both anonymous and id assignments. Such a straightforward extension, however, results in an infea­ sible increase in the number of samples needed during early stages of the estimation process. This has two reasons. First, each hypothesis (sample) of MHT-RBPF has m! possible as­ signments ofid's to object tracks. Second, due to the low spa­ tial resolution of id-sensors, the posterior over id assignments is initially very uncertain and sample-based representations of such flat distributions are inherently inefficient. To overcome these difficulties we instead use a two-stage estimation pro­ cess. During the initial stage, only anonymous sensors are used for object tracking while the id-sensors are simply used to estimate the identity of the different objects. Once these esti­ mates are certain enough, the process moves into the full Rao­ Blackwellisation phase, during which both anonymous and id assignments are sampled. The two phases are discussed below.

Identity estimation phase

During this phase only anonymous sensors are used to track the objects. The id-sensors are used to estimate the identity of the different objects. More specifically, for each hypothesis of the MHT-RBPF, there are m! possible assignments iJk of identities to tracks. In order to avoid estimating distributions over this potentially too large number of assignments, we only keep track of sufficient statistics that allow us to recover distri­ butions over assignments. Such sufficient statistics are given by the m 2 individual assignments iJk ( i, j) of id's j to tracks t~ . The probabilities of these individual assignments can be updated recursively using the most recent id observation:

Here, z£ is an id observation corresponding to person j . To determine the assignment probabilities, we have to normalize these values by considering all possible assignments:

Again, B' ( i, j) is one if B' assigns id j to object track i, and zero otherwise. The computational complex computa­ tion of (9) can be avoided by sampling id assignmen~s using Metropolis-Hastings, based on the individual values Bk ( i, j). This approach works identical to the method used to sample anonymous assignments in the MHT-RBPF algorithm.

To summarize, in the identity estimation phase, each sa~­ ple s(') consists of m Kalman filters ~nd an m x m matrix ek representing the sufficient statistics ek ( i , j) of the id assign­ ments. Whenever needed, the posterior over id assignments can be computed using MCMC sampling. The id estimation stage is ended as soon as the posterior over id assignments is sufficiently peaked to allow an accurate representation with a reasonable number of samples. Currently, we estimate this condition by determining the average number of hypotheses in the Markov chains run for id assignments.

Full Rao-Blackwellisation phase

Once the id's are estimated accurately enough, we begin es­ timating the joint posterior of both anonymous and id assignments. This posterior is given by: · _

Note that id assignments are sampled only once during the complete estimation process, since after an id assignment is sampled, the identities of the attached object tracks are fixed. From then on, id observations serve two purposes: First they provide information of object positions, and, second, they provide information for weighting anonymous hypotheses, thereby improving the object estimates considerably.

5 Experiments

To validate our approach we captured trace logs of six peo­ ple simultaneously walking around the cubical areas of the office environment outlined in Figure 3. Each person was wearing a small id-sensor track-pack consisting of two in­ frared badges and an ultrasound badge. Infrared and ultra­ sound receivers were installed throughout the ceiling. The entire scene was continually observed by two wall-mounted laser range-finders scanning at chest height just above the cu­ bical partitions. The duration of the Jog was 10 minutes, dur­ ing which the individual people moved between 230 meter and 410 meter. In this challenging data Jog, the paths of people fre­ quently crossed each other and there were situations in which up to 4 people were occluded by others. To validate our track­ ing algorithm quantitatively, we carried out a series of exper­ iments based on this data Jog and on additional simulation runs (see www. cs. washington. edu/robotics/people­ tracking/ for visualizations).

Tracking ability

The path of the six people as estimated by our system is shown in Figure 3. This result was obtained with an MHT-RBPF us­ ing 1000 samples and Markov chains of length 100. With this setting, the algorithm was able to reliably track the six people if no lookahead was used. After determining these parame­ ters, we carried out trial runs for different variants of our al­ gorithm. A run was considered successful if at the end the sample set contained at least one hypothesis with correct loca­ tions and identities. Each method was tested on 10 trial runs using the real data set. Without identity estimation phase, the algorithm was never able to successfully complete the data set. Next, we tested the approach when not switching to the full Rao-Blackwellisation phase, i.e. the algorithm remained in the identity estimation phase. Without lookahead, the update times of the approach were prohibitively large (more than 10 times real time). The lookahead resulted in significant speedup and the results are shown in the first row of the table below. Finally, we tested our two-phase approach with and without Jookahead. The algorithms were able to successfully track the complete data in most cases, as can be seen in the first col­ umn. The other three columns give average time, standard de­ viation, and maximum time per update in seconds. The results demonstrate that both the Jookahead and the two-stage process improve the performance of the tracking algorithm.

In another set of experiments, we compared our MCMC based assignment generation to a deterministic sampling scheme, as used in traditional MHT algorithms. Here, as­ signments are enumerated in decreasing order wrt. their like­ lihood [Cox and Hingorani, 1996]. Note that generating as­ signments by decreasing likelihood results in estimates that are strongly biased towards more likely assignments. We per­ formed extensive tests using real data and data simulating 20 people and found that our approach is slightly more efficient while achieving the same robustness. Since such results de­ pend on implementational details, we did not consider them significant enough. However, the fact that smart chain flipping works at least as good as ranked assignments in practice is very encouraging, since the MCMC approach results in much Jess biased estimates.

MCMC weight estimation

In Section 3.1, we introduced an apporach to using the most recent observation in order to weight samples before drawing them for the next time step. So far it is not clear whether this estimation based on the probabilities of samples drawn from the Markov chains is a valid approximation. To test the qual­ ity of this approximation, we computed the optimal predictive weights by enumerating all possible assignments of the next time step. Figure 4 shows the MCMC sample weights com­ puted in (7) plotted against the optimal weights. The similarity to y = x suggests that our method of estimating Markov chain normalizers results in accurate weight estimates.

6 Conclusions and Future Work

We have presented a solution to the problem of tracking mul­ tiple people using a combination of anonymous and id sen­ sors. The approach inherits the advantages of both sensor types, thereby being able to accurately track people and es­ timate their identity. Our technique uses Rao-Blackwellised particle filters to make the estimation problem tractable. We introduced several improvements to the vanilla particle filter. First, the estimation process is separated into two stages, a first stage of identity estimation and a second stage of full Rao­ Blackwellisation. A second improvement is in using the most recent observation before sampling from the previous sample set. In contrast to [Morales-Menendez eta/., 2002], the state space of our problem can become too large to allow an accu­ rate estimate of the predictive quality of samples. Therefore, we estimate this quality using Markov chains generating sam­ ples distributed according to the posterior. We demonstrate the robustness of our approach in a challenging experiment in­ volving six people walking through a confined office environ­ ment. We also show that our MCMC prediction is an accurate approximation of the optimal weighting function.

The approach introduced in this paper is just the first step towards a reliable and efficient tracking system. Currently, the transition between the identity estimation stage and the full Rao-Blackwellisation stage is based on a simple heuris­ tic, namely the average number of different assignments in the Markov chains. We intend to replace this measure by a more fundamental approach such as the overall complexity of the distribution [Fox, 2002]. Another source of potential improve­ ment lies in the handling of hypotheses. In our current system, the number of hypotheses grows extremely fast whenever sev­ eral people are close to each other. We intend to overcome this problem by clustering people into groups for which we do not attempt to estimate the individual id's, as already introduced in a similar context by [Rosencrantz eta/., 2003]. Finally, the recovery from tracking failures is another important issue for future research. Especially in the full Rao-Blackwellisation phase, the current approach can not recover from losing the correct id hypothesis, since id assignments do not change over time.

Acknowledgments

This work has partly been supported by the National Science Foundation under grant number IIS-0093406, and by DARPA's SDR Programme (contract number NBCHC020073). We are also very grateful for the help of various people at the Intel Research Lab Seattle for collecting the data needed for our experimental evaluation.