This work addresses the problem of person tracking using additional background information. We augment a particle lter-based tracking algorithm with a rst-order probabilistic model expressed through Markov Logic Networks to tackle the data association problem in domains with a high occlusion rate. Using a high-level model description allows us to easily integrate additional information like a oor plan or goal information into a joint model and resolve occlusion situations that would otherwise result in the loss of association. We discuss the engineered model in detail and give an empirical evaluation using an indoor setting.
This work concerns the problem of providing
background-knowledge to the specialized application
of person tracking using a high-level probabilistic
model. We demonstrate that a hand-crafted model,
built using Markov Logic Networks (MLN)
[Ri
The usage of a rst-order probabilistic model like
MLNs allows for an easier modeling task, because
dependencies are represented by weighted rst-order
logical formulas instead of, e.g., conditional probability
tables for the case of directed models like Bayesian
Networks. In addition, the model is formulated in
a lifted form and can be instantiated for the desired
number of concurrent tracks or persons within the
scene, which is not possible when using completely
propositional models or specialized template models
like dynamic Bayesian networ
We motivate our work in the context of an indoor situation, where multiple persons move in a two-room ofce, containing the laser range nder and several areas of interest like a printer or a co ee maker. We measure the quality of our model by the extent to which it is able to correctly associate object tracks emerging from the tracking algorithm with the correct persons inside the scene.
The rest of the paper is laid out as follows. After we discuss related work, we give an overview of the applied tracking algorithm and introduce the concept of Markov Logic Networks. Then, we describe the investigated problem in detail and discuss the used MLN model. We give an empirical evaluation of the described setup and conclude with some possible extensions to the model and an overall discussion. 2
In multi-object tracking, state dependent detection
probabilities of objects are disregarded in most
applications. Thus, a track disappears shortly after
entering an occluded area and a new track is created
when the object leaves the occluded area again.
Consequently, one object is represented by di erent track
IDs. Especially in scenarios where persons interact
several times with a system, changed track IDs lead
to the loss of the objects history. The multi-object
Bayes lte
Markov Logic Networks have been u
Standard multi-object tracking algorithms often use
object individual single-object trackers like the
Kalman lter. The drawback of this multi-object
tracking approach is the need of a data association
step which assigns the received measurements to the
trackers using hard decisions or probabilistic
method
A rigorous approach to multi-object tracking is the
multi-object Bayes lte
Further, the multi-object Bayes lter allows to integrate state dependent detection probabilities into the ltering algorithm. In Reuter and Dietmayer [2011], an approach to calculate state dependent detection probabilities based on the occupancy grid mapping approach [Thrun et al., 2005] is proposed. Thus, it is possible to keep track of an object which is occluded for the sensor for a short period of time. Using constant detection probabilities would lead to a track loss, if an object is not visible to the sensor for a few measurement cycles. We use the state dependent tracking algorithm as a comparison for our nal results. But for input into the high-level model, we use state independent object tracking. This produces more track IDs for association, and in particular is less prone to false association, which we cannot correct in the upper stage.
An implementation of the multi-object Bayes lter is
possible using Sequential Monte Carlo (SMC) method
Since the multi-object Bayes lter does not perform
a measurement to track association, an extraction of
the individual objects out of the multi-object posterior
density function is necessary, e.g. using the k-
Markov Logic Networks [Ri
A Markov Logic Network L = f(f1; w1); : : : ; (fn; wn)g for n 2 N is a set of rst-order formulas f1; : : : ; fn with given weights w1; : : : ; wn 2 R. Together with a nite set of constants C, they de ne a probability distribution over all interpretations (or possible worlds). An interpretation maps each grounding of each predicate to a truth value. The interpretation of functions must be xed. Probabilistic functions can be emulated using predicates. Let gC (f ) be the set of groundings of formula f obtained by replacing the free variables in f by all combinations of constants from C. Given an interpretation x, then nC;i(x) d=ef jfg j g 2 gC (fi) and x j= ggj is the number of groundings of formula fi that are true under x. Then, the probability distribution PL;C that is de ned by the MLN L with constants C is given as PL;C (X = x) d=ef 1 Y exp winC;i(x) ;
Z i (1) where i ranges over all formulas in L, and Z is a normalizing constant.
Given a set of constants, a MLN can be converted to a Markov network, where nodes correspond to atoms and each ground formula induces a clique over all nodes whose atoms appear inside this formula. For practical reasons, a sorted (or typed) logical language is used to describe MLNs. Using sorted terms, we can limit the size of the grounded network. Also, in their basic form, MLNs do only allow restricted usage of logical functions. Usually functions are simulated by specially marked predicates, which enforce a functional dependency of one or more arguments on the remaining arguments. We notate functional arguments of predicates by underlining them. Such a predicate can be translated to a multi-valued random variable. 5
We consider an indoor scene which resembles an o ce
setting. The corresponding oor plan is depicted in
Figure 1a. A laser range nder is placed in one corner
of the main room and provides distance information
in a plane about one meter above ground. The beam
almost completely covers the main room, but there
exists a second room that has virtually no sensor
coverage. There is only one entrance to the room complex
and the separate room has only a single exit, which is
the door to the main room. The setting contains
several features that may serve as goal destinations for
persons navigating inside the scene; like a printer or
a co ee maker. Knowledge about destinations of
persons is taken as given; although it is easy to motivate
the existence of such information depending on the
application. Issued print jobs could be recognized by a
special program installed on the PC, or visits to the
co ee maker could be predicted from personal habits.
There are one to three persons inside the scene
simultaneously. Major occlusion caused by static objects,
like walls, occurs when people enter the second room.
Minor static occlusion can occur near the co ee maker.
During the scenes with more than one person, dynamic
occlusion occurs when persons are covered by other
persons standing between them and the sensor.
Using only the particle lter-based tracking algorithm
to process the output of the laser range nder,
problems arise when people produce no measures for an
extended period of time because they are inside the
separate room or because they are hidden by another
person. For shorter occlusion durations it is possible to
keep the track of a single occluded person alive for long
enough for the person to reappear and re-association is
completely handled by the tracking algorithm. If two
persons enter the same occlusion area, their estimated
positions begin to mix spatially and once they emerge
again, re-association becomes more and more
arbitrary with increasing occlusion duration. In these
scenarios, a direct integration of the Social Force model
into the prediction of the persons state of the tracking
algorithm may increase the performance of the
Figure 1b shows an example of the tracking results for one of the sequences with three persons. The trajectories are illustrated by solid lines. Since the results are generated without the usage of the state dependent detection probability, the trajectories are interrupted quite often in the area corresponding to region RA, where a dynamic occlusion occurs. 6
In this section, we describe the used MLN model and discuss some of the di culties and design choices we have encountered in its engineering. The complete model is factored into four modules. We begin with a discussion of two concepts that cannot be associated with distinct model parts but in uence nearly every aspect { the representation of space and time. Printer RC
-4 RB RA -3 -4 0
Co ee Living
Exit Laser Range Finder
-5
(a) Floor plan
-1
-1
0
(b) Example trajectories
From continuous to discrete space. The basic
MLN can only represent discrete random variables.
There exists an extension of MLNs to continuous
va
The tracking model. The basic functionality for interfacing with the tracking algorithm is provided by a MLN module that contains objects of the sorts Track and Person. To notate variables of some sort, we use the initial letter of the sort name in lower case. For the sort Track, the letter 'm' is used because of the ambiguity with sort Time. For both sorts Track and Time, there exist time-dependent predicates atT : Time Track Region and atP : Time Person Region that give the current location of a track or person, respectively. The timeindependent predicate a : Track ! Person associates Track objects to Person objects. The correspondence of tracks to persons inside the MLN is similar to the correspondence of measurements to tracks inside the tracking algorithm. The output of the tracking algorithm is converted to observations of the atT function and an additional completely observed predicate act : Time Track, whose purpose is mainly to be able to prune groundings of formulas that depend on inactive track IDs. The usage of this predicate is omitted for clarity. Information about goals of persons can attach to the location of the person objects. The core tracking model then consists of the following two formulas.
5 3 atT (t; m; r) ^ a(m; p) ) atP (t; p; l) a(m1; p) ^ a(m2; p) ^ m1 6= m2 (2) (3) Formula 2 probabilistically forces a person to be in the same region as its associated track. By design a track can only be associated to one person at a time because the last parameter of the predicate a is declared functional. Formula 3 probabilistically enforces the association to also be a one-to-one relation. The engineering of the formula weights is explained at the end of this section. This formula is limited to concurrently instantiated tracks using the act predicate (not listed).
The oor plan. We use the static predicate adj : Region Region to encode the connectedness of the regions. All instances are fully observed and adhere to the oor plan given in Figure 1a. A single formula forces persons to move between regions only according to the given layout: 1
atP (t; p; l1) ^ atP (t + 1; p; l2) ) adj(l1; l2) (4) This formula is deterministic to prevent persons from \teleporting" through the scene. If regions allow for a traversal in less than a second (one time step), this rule becomes invalid. But since the association of tracks to persons allows for some slack, a person in the model can \catch up" to the location of its real counterpart after some time steps, only violating Formula 2. The occlusion model. To prevent persons without an associated track from wandering across the scene (since no track in uences their current location), we need to express that persons usually have a track unless they are indeed occluded. In our setting both static and dynamic occlusions occur, being caused by walls or other persons, respectively. For our experiments, only static occlusion information is modeled. This is done by assigning a certain probability to each region that it may contain untracked persons. The probability is larger for areas of high static occlusion, like the separate room. We also assign a higher occlusion to regions that are more likely to be dynamically covered, like the region around the co ee maker. By assigning low occlusion probabilities to central regions that have a good sensor coverage we penalize persons silently slipping past the sensor. Formula 5 is provided once for each region r. The weight wr is the occlusion value, which is given in Figure 1a.
wr
atP (t; p; r) ^ :9m : (act(t; m) ^ a(m; p)) (5) Goals and their dynamics. The last model part handles the goals of persons. We associate goals with regions and add another time-dependent function goal : Time Person Region, where goals are also allowed to assume the special location NULL to signal that a person currently has no goal. The following formulas describe the dynamics of goals: goal(t; p; l) ^ :atP (t; p; l) ) goal(t + 1; p; l)(6) goal(t; p; l) ^ atP (t; p; l) ) goal(t + 1; p; l) _ goal(t + 1; p; NULL) (7) goal(t; p; NULL) (8) 1 1 0:1 Formulas 6 and 7 achieve that goals can only be cleared when a person reaches their associated region. Formula 8 encodes the urge of people to clear their goal. Stating this rule in this particular form results in persons trying to reach their goal as soon as possible, since otherwise the penalty accumulates over time. Another way to make people reach their goals is to make it more likely for a person to be inside the region of their goal. Both rules work equally well for our dataset but might make a di erence when applied to longer sequences or under a di erent setting.
Elicitation of weights. There exist two major ways
to determine the weights of the probabilistic formulas:
Learning from data and elicitation from experts; where
for common sense domains, like the one we are dealing
with, everyone is usually an expert. Both the
learning of weights and the direct speci cation approaches
have been followed in the literature. For the case of
our related work,
We go on and describe how tracking data is processed for input to the MLN model. After extraction of the individual objects in the multi-object Bayes lter, we obtain a set of single object particles Xmt for each track ID m and time step t. We then apply two data reduction steps. First, the MLN model works on a coarser time scale of 1.25 steps per second, while the tracking algorithm runs with 12.5 steps per second. We drop the intermediate steps without further processing. A di erent approach might aggregate them, e.g., by averaging, but this would also distort the meaning of the data, because it cannot be considered a snapshot of the situation anymore.
Depending on the quality of the tracking algorithm and the used object model, there can be many false positive tracks, e.g., when people spread their arms away from their body, crossing the plane of laser beams. To reduce these false tracks, we use the existence probability to eliminate insigni cant tracks. It is given by jXmtj=N ; the number of particles for track ID m divided by the total number of particles N . We drop all tracks from a time step whose existence probability is below 0:5. For our test sequences, the output of the tracking algorithm usually contains about thirty tracks per sequence, but only less than ten remain after applying both reduction processes.
For each time step t and each track ID m that survive the described process we add the track as active to our MLN model via observation of the act predicate. We then bin the single object particles into the discrete regions. Most of the time all particles are contained in a single region and we create an observation of the atT function. In cases where the particles of a track m spread over several regions we re ect this as probabilistic evidence by adding a formula (wl; atT (t; m; l)) for each location l and calculating the weight as the logarithmic odds wl = log 1 plpl , where pl is the relative frequency of a particle of track m being in region l. 8
Markov Logic Networks can be seen as template
models for undirected graphical mo
For our evaluation we perform exact inference on
the model by exploiting context-speci c
indepen
We recorded 9 sequences in total; three sequences with one, two and three persons, respectively. The duration of each sequence is about one minute. The course of events is the same among sequences with the same number of persons; the sequences vary during the part where multiple persons wander around the main room. The setups with one person only feature static occluSequence
Persons
Unassigned Tracks #pD = c #pD(x) S1-1532 S1-1640 S1-1737 S2-2056 S2-2207 S2-2329 S3-4628 S3-4734 S3-5306 sion caused by walls, caused by the single person staying inside the o ce for several seconds. This results in its track being reinvented upon entering the main room again. With two persons there is dynamic occlusion, where one person covers the other person. Both persons enter the o ce together and thus cannot be distinguished once they reappear. Goal information for one person can resolve this issue and we can obtain a good association again. In the scenes with three persons, one person enters the o ce while the two remaining persons stay inside the main room. Dynamic occlusion occurs while all three persons are walking around in front of the sensor. Tracks are lost and recreated often, which can also be observed in Figure 1b inside the area corresponding to region RA. When two persons are simultaneously shadowed by the third one, it is not possible to associate the reappearing tracks to the correct persons just by means of the sensor. In this case goal information can be used to identify the correct association.
We have evaluated three models that incorporate an increasing amount of domain knowledge. The rst model M uses only the basic tracking model and the oor plan. The second model MO comprises all of the rst model and the static occlusion model. The third model MOG adds information about personal goals. One person visits the co ee maker in each sequence. We assign the Coffee region as goal for this person in every sequence. All other persons have no goal assigned. The goal information is able to resolve confusions that happen before the designated person visits its goal region. This does not happen in every sequence. The MLN is instantiated for three persons in every setup, regardless of the number of persons appearing in the scene. For each model and each sequence, we observe the correct association for the rst track of each person and evaluate how well we can associate new tracks. In our dataset, the number of tracks that remain unassigned after labeling the starter tracks varies between one and seven.
The results of our evaluation are given in Table 1. For
each sequence, we give the number of false track
assignments of the most probably association. In
addition, we provide the probability of the correct joint
association. This is interesting for cases where no false
associations were made even with a simpler model, and
can show an improved signi cance of the correct
association when using a more sophisticated model.
To provide a baseline, the number of track confusions
and losses of a state-of-the-art multi-object Bayes
lter with state dependent detection probability (pD(x))
and the ones using the same lter with constant
detection probability (pD = c) are gi
We observe that the algorithm with the state dependent detection probability reduces the number of unassigned tracks dramatically in the scenarios with three persons, where a lot of short term occlusions occur. In the scenarios with one or two persons, where the long-term occlusions due to static objects dominate, the usage of the state dependent detection probability has nearly no in uence on the number of unassigned tracks. The high-level model MO using only the oor plan and the static occlusion model delivers results that are at least on par with the state dependent tracking algorithm. Using goal information for one person can further improve the results. By our judgment, this is not possible by relying solely on the data obtained from the laser range nder in general.
One of the two person sequences (S2-2207) shows very bad performance of the MLN model for all three cases. Our investigation has shown that an outstretched arm has caused a signi cant track that made it through the data reduction process. The relatively high weight on Formula 3 prevented the association of this track to the owner of the arm. Thus, a third person was forced by the model to appear at this spot and remained present over the course of the scene. 10
We have described an approach to solving the data association problem for person tracking with a highlevel probabilistic model described using Markov Logic Networks. We showed how to map the output of a regular tracking algorithm into a discrete spatial representation, which makes it easy to attach additional information, e.g., personal goals, and allows the use of inference techniques for discrete probabilistic models. Especially in scenarios with long-term occlusions, where even the multi-object Bayes lter is not able to continue to track hidden objects, the association using MLN outperforms the tracking-based approach when using exact evaluation. On the other hand, a sophisticated tracking algorithm is adequate in scenarios with occlusions of no more than one second and might be able to scale more easily to larger domains. In future, we plan to integrate more information out of the knowledge-base directly into the tracking algorithms like, e.g., probabilistically modeled destinations or goals of a person.
This work is done within the Transregional Collaborative Research Centre SFB/TRR 62 \CompanionTechnology for Cognitive Technical Systems" funded by the German Research Foundation (DFG).