A Bayesian Computer Vision System for Modeling Human Interactions.
AbstractWe describe a real-time computer vision and machine learning system for modeling and recognizing human behaviors in a visual surveillance task [1]. The system is particularly concerned with detecting when interactions between people occur and classifying the type of interaction. Examples of interesting interaction behaviors include following another person, altering one's path to meet another, and so forth. Our system combines top-down with bottom-up information in a closed feedback loop, with both components employing a statistical Bayesian approach [2]. We propose and compare two different state-based learning architectures, namely, HMMs and CHMMs for modeling behaviors and interactions. The CHMM model is shown to work much more efficiently and accurately. Finally, to deal with the problem of limited training data, a synthetic Alife-style training system is used to develop flexible prior models for recognizing human interactions. We demonstrate the ability to use these a priori models to accurately classify real human behaviors and interactions with no additional tuning or training.
Introduction
We describe a real-time computer vision and machine
learning system for modeling and recognizing human
behaviors in a visual surveillance task. The system
is particularly concerned with detecting when interactions
between people occur, and classifying the type
of interaction.
Over the last decade there has been growing interest
within the computer vision and machine learning
communities in the problem of analyzing human behavior
in video ([10],[3],[20], [8], [17], [14],[9], [11]).
Such systems typically consist of a low- or mid-level
computer vision system to detect and segment a moving
object - human or car, for example -, and a
higher level interpretation module that classifies the
motion into 'atomic' behaviors such as, for example, a
pointing gesture or a car turning left.
However, there have been relatively few efforts to
understand more human behaviors that have substantial
extent in time, particularly when they involve interactions
between people. This level of interpretation
is the goal of this paper, with the intention of
building systems that can deal with the complexity of
multi-person pedestrian and highway scenes.
This computational task combines elements of
AI/machine learning and computer vision, and
presents challenging problems in both domains: from
a Computer Vision viewpoint, it requires real-time, accurate
and robust detection and tracking of the objects
of interest in an unconstrained environment; from a
Machine Learning and Artificial Intelligence perspective
behavior models for interacting agents are needed
to interpret the set of perceived actions and detect
eventual anomalous behaviors or potentially dangerous
situations. Moreover, all the processing modules
need to be integrated in a consistent way.
Our approach to modeling person-to-person interactions
is to use supervised statistical learning techniques
to teach the system to recognize normal single-person
behaviors and common person-to-person inter-
actions. A major problem with a data-driven statistical
approach, especially when modeling rare or
anomalous behaviors, is the limited number of examples
of those behaviors for training the models. A
major emphasis of our work, therefore, is on efficient
Bayesian integration of both prior knowledge (by the
use of synthetic prior models) with evidence from data
(by situation-specific parameter tuning). Our goal is
to be able to successfully apply the system to any normal
multi-person interaction situation without additional
training.
Another potential problem arises when a completely
new pattern of behavior is presented to the
system. After the system has been trained at a few
different sites, previously unobserved behaviors will be
(by definition) rare and unusual. To account for such
novel behaviors the system should be able to recognize
such new behaviors, and to build models of the
behavior from as as little as a single example.
We have pursued a Bayesian approach to modeling
that includes both prior knowledge and evidence from
data, believing that the Bayesian approach provides
the best framework for coping with small data sets and
novel behaviors. Graphical models [6], such as Hidden
Markov Models (HMMs) [21] and Coupled Hidden
Markov Models (CHMMs) [5, 4], seem most appropriate
for modeling and classifying human behaviors
because they offer dynamic time warping, a well-understood
training algorithm, and a clear Bayesian
semantics for both individual (HMMs) and interacting
or coupled (CHMMs) generative processes.
To specify the priors in our system, we have found it
useful to develop a framework for building and training
models of the behaviors of interest using synthetic
agents. Simulation with the agents yields synthetic
data that is used to train prior models. These prior
models are then used recursively in a Bayesian frame-work
to fit real behavioral data. This approach provides
a rather straightforward and flexible technique
to the design of priors, one that does not require strong
analytical assumptions to be made about the form of
the priors 1 . In our experiments we have found that by
combining such synthetic priors with limited real data
we can easily achieve very high accuracies of recognition
of different human-to-human interactions. Thus,
our system is robust to cases in which there are only
a few examples of a certain behavior (such as in interaction
described in section 5.1) or even no
examples except synthetically-generated ones.
The paper is structured as follows: section 2
presents an overview of the system, section 3 describes
the computer vision techniques used for segmentation
and tracking of the pedestrians, and the statistical
models used for behavior modeling and recognition are
described in section 4. Section 5 contains experimental
results with both synthetic agent data and real video
data, and section 6 summarizes the main conclusions
and sketches our future directions of research. Finally
a summary of the CHMM formulation is presented in
the appendix.
System Overview
Our system employs a static camera with wide field-of-
view watching a dynamic outdoor scene (the extension
to an active camera [1] is straightforward and planned
for the next version). A real-time computer vision system
segments moving objects from the learned scene.
The scene description method allows variations in
lighting, weather, etc., to be learned and accurately
discounted.
1 Note that our priors have the same form as our posteriors,
namely they are Markov models.
For each moving object an appearance-based description
is generated, allowing it to be tracked though
temporary occlusions and multi-object meetings. An
Extended Kalman filter tracks the objects location,
coarse shape, color pattern, and velocity. This temporally
ordered stream of data is then used to obtain
a behavioral description of each object, and to detect
interactions between objects.

Figure

1 depicts the processing loop and main functional
units of our ultimate system.
1. The real-time computer vision input module detects
and tracks moving objects in the scene, and
for each moving object outputs a feature vector
describing its motion and heading, and its spatial
relationship to all nearby moving objects.
2. These feature vectors constitute the input to
stochastic state-based behavior models. Both
HMMs and CHMMs, with varying structures depending
on the complexity of the behavior, are
then used for classifying the perceived behaviors.

Figure

1: Top-down and bottom-up processing loop
Note that both top-down and bottom-up streams of
information are continuously managed and combined
for each moving object within the scene. Consequently
our Bayesian approach offers a mathematical frame-work
for both combining the observations (bottom-up)
with complex behavioral priors (top-down) to provide
expectations that will be fed back to the perceptual
system.
3 Segmentation and Tracking
The first step in the system is to reliably and robustly
detect and track the pedestrians in the scene.
We use 2-D blob features for modeling each pedes-
trian. The notion of "blobs" as a representation for
image features has a long history in computer vision
[19, 15, 2, 25, 18], and has had many different mathematical
definitions. In our usage it is a compact set of
pixels that share some visual properties that are not
shared by the surrounding pixels. These properties
could be color, texture, brightness, motion, shading,
a combination of these, or any other salient spatio-temporal
property derived from the signal (the image
sequence).
3.1 Segmentation by Eigenbackground
subtraction
In our system the main cue for clustering the pixels
into blobs is motion, because we have a static background
with moving objects. To detect these moving
objects we build an adaptive eigenspace that models
the background. This eigenspace model describes
the range of appearances (e.g., lighting variations over
the day, weather variations, etc.) that have been ob-
served. The eigenspace can also be generated from
a site model using standard computer graphics techniques

The eigenspace model is formed by taking a sample
of N images and computing both the mean - b
background image and its covariance matrix C b . This
covariance matrix can be diagonalized via an eigenvalue
decomposition
b , where \Phi b is the
eigenvector matrix of the covariance of the data and
L b is the corresponding diagonal matrix of its eigen-
values. In order to reduce the dimensionality of the
space, in principal component analysis (PCA) only M
eigenvectors (eigenbackgrounds) are kept, corresponding
to the M largest eigenvalues to give a \Phi M matrix.
A principal component feature vector I
then formed, where is the mean normalized
image vector.
Note that moving objects, because they don't appear
in the same location in the N sample images and
they are typically small, do not have a significant contribution
to this model. Consequently the portions of
an image containing a moving object cannot be well
described by this eigenspace model (except in very unusual
cases), whereas the static portions of the image
can be accurately described as a sum of the the various
eigenbasis vectors. That is, the eigenspace provides a
robust model of the probability distribution function
of the background, but not for the moving objects.
Once the eigenbackground images (stored in a matrix
called
hereafter) are obtained, as well as their
mean - b , we can project each input image I i onto
the space expanded by the eigenbackground images
X i to model the static parts of the scene,
pertaining to the background. Therefore, by comput-
Figure

2: Background mean image, blob segmentation
image and input image with blob bounding boxes
ing and thresholding the Euclidean distance (distance
from feature space DFFS [16]) between the input image
and the projected image we can detect the moving
objects present in the scene: D
where t is a given threshold. Note that it is easy to
adaptively perform the eigenbackground subtraction,
in order to compensate for changes such as big shad-
ows. This motion mask is the input to a connected
component algorithm that produces blob descriptions
that characterize each person's shape. We have also
experimented with modeling the background by using
a mixture of Gaussian distributions at each pixel,
as in Pfinder [26]. However we finally opted for the
eigenbackground method because it offered good results
and less computational load.
3.2 Tracking
The trajectories of each blob are computed and saved
into a dynamic track memory. Each trajectory has
associated a first order Extended Kalman filter that
predicts the blob's position and velocity in the next
frame. Recall that the Kalman Filter is the 'best linear
unbiased estimator' in a mean squared sense and that
for Gaussian processes, the Kalman filter equations
corresponds to the optimal Bayes' estimate.
In order to handle occlusions as well as to solve the
correspondence between blobs over time, the appearance
of each blob is also modeled by a Gaussian PDF
in RGB color space. When a new blob appears in
the scene, a new trajectory is associated to it. Thus
for each blob the Kalman-filter-generated spatial PDF
and the Gaussian color PDF are combined to form a
joint image space and color space PDF. In subsequent
frames the Mahalanobis distance is used to
determine the blob that is most likely to have the same
identity.
4 Behavior Models
In this section we develop our framework for building
and applying models of individual behaviors and
person-to-person interactions. In order to build effective
computer models of human behaviors we need to
address the question of how knowledge can be mapped
onto computation to dynamically deliver consistent interpretations

From a strict computational viewpoint there are
two key problems when processing the continuous
flow of feature data coming from a stream of input
video: (1) Managing the computational load imposed
by frame-by-frame examination of all of the agents
and their interactions. For example, the number of
possible interactions between any two agents of a set
of N agents is N   (N \Gamma 1)=2. If naively managed this
load can easily become large for even moderate N ; (2)
Even when the frame-by-frame load is small and the
representation of each agent's instantaneous behavior
is compact, there is still the problem of managing all
this information over time.
Statistical directed acyclic graphs (DAGs) or probabilistic
inference networks (PINs) [7, 13] can provide
a computationally efficient solution to these problems.
HMMs and their extensions, such as CHMMs, can be
viewed as a particular, simple case of temporal PIN or
DAG. PINs consist of a set of random variables represented
as nodes as well as directed edges or links between
them. They define a mathematical form of the
joint or conditional PDF between the random vari-
ables. They constitute a simple graphical way of representing
causal dependencies between variables. The
absence of directed links between nodes implies a conditional
independence. Moreover there is a family of
transformations performed on the graphical structure
that has a direct translation in terms of mathematical
operations applied to the underlying PDF. Finally
they are modular, i.e. one can express the joint global
PDF as the product of local conditional PDFS.
PINs present several important advantages that are
relevant to our problem: they can handle incomplete
data as well as uncertainty; they are trainable and
easier to avoid overfitting; they encode causality in a
natural way; there are algorithms for both doing prediction
and probabilistic inference; they offer a frame-work
for combining prior knowledge and data; and
finally they are modular and parallelizable.
In this paper the behaviors we examine are generated
by pedestrians walking in an open outdoor envi-
ronment. Our goal is to develop a generic, compositional
analysis of the observed behaviors in terms of
states and transitions between states over time in such
a manner that (1) the states correspond to our common
sense notions of human behaviors, and (2) they
are immediately applicable to a wide range of sites and
viewing situations. Figure 3 shows a typical image for
our pedestrian scenario.

Figure

3: A typical image of a pedestrian plaza
Observations
States
O
O
O'
States
Observations S'

Figure

4: Graphical representation of HMM and
CHMM rolled-out in time
4.1 Visual Understanding via Graphical
Models: HMMs and CHMMs
Hidden Markov models (HMMs) are a popular probabilistic
framework for modeling processes that have
structure in time. They have a clear Bayesian seman-
tics, efficient algorithms for state and parameter esti-
mation, and they automatically perform dynamic time
warping. An HMM is essentially a quantization of a
system's configuration space into a small number of
discrete states, together with probabilities for transitions
between states. A single finite discrete variable
indexes the current state of the system. Any information
about the history of the process needed for future
inferences must be reflected in the current value of this
state variable. Graphically HMMs are often depicted
'rolled-out in time' as PINs, such as in figure 4.
However, many interesting systems are composed
of multiple interacting processes, and thus merit a
compositional representation of two or more variables.
This is typically the case for systems that have structure
both in time and space. With a single state vari-
able, Markov models are ill-suited to these problems.
In order to model these interactions a more complex
architecture is needed.
Extensions to the basic Markov model generally increase
the memory of the system (durational model-
ing), providing it with compositional state in time.
We are interested in systems that have compositional
state in space, e.g., more than one simultaneous state
variable. It is well known that the exact solution of
extensions of the basic HMM to 3 or more chains is
intractable. In those cases approximation techniques
are needed ([22, 12, 23, 24]). However, it is also known
that there exists an exact solution for the case of 2 interacting
chains, as it is our case [22, 4].
We therefore use two Coupled Hidden Markov Models
(CHMMs) for modeling two interacting processes,
in our case they correspond to individual humans. In
this architecture state chains are coupled via matrices
of conditional probabilities modeling causal (tempo-
ral) influences between their hidden state variables.
The graphical representation of CHMMs is shown in
figure 4. From the graph it can be seen that for each
chain, the state at time t depends on the state at time
both chains. The influence of one chain on the
other is through a causal link. The appendix contains
a summary of the CHMM formulation.
In this paper we compare performance of HMMs
and CHMMs for maximum a posteriori (MAP) state
estimation. We compute the most likely sequence of
states -
S within a model given the observation sequence
ng. This most likely sequence is obtained
by -
In the case of HMMs the posterior state sequence
probability P (SjO) is given by
Y
(1)
is the set of discrete states,
corresponds to the state at time t. P ijj
is the state-to-state transition probability
(i.e. probability of being in state a i at time t given
that the system was in state a j at time t \Gamma 1). In
the following we will write them as P s t js
. The prior
probabilities for the initial state are P i
are the
output probabilities for each state, (i.e. the probability
of observing given state a i at time t).
In the case of CHMMs we need to introduce another
set of probabilities, P s t js 0
, which correspond to the
probability of state s t at time t in one chain given that
the other chain - denoted hereafter by superscript 0
- was in state s 0
These new probabilities
express the causal influence (coupling) of one
chain to the other. The posterior state probability for
CHMMs is given by
(2)
\Theta
Y
js
t denote states and observations for
each of the Markov chains that compose the CHMMs.
We direct the reader to [4] for a more detailed description
of the MAP estimation in CHMMs.
Coming back to our problem of modeling human
behaviors, two persons (each modeled as a generative
process) may interact without wholly determining
each others' behavior. Instead, each of them has its
own internal dynamics and is influenced (either weakly
or strongly) by others. The probabilities
and
js
describe this kind of interactions and CHMMs
are intended to model them in as efficient a manner
as is possible.
5 Experimental Results
Our goal is to have a system that will accurately interpret
behaviors and interactions within almost any
pedestrian scene with little or no training. One critical
problem, therefore, is generation of models that
capture our prior knowledge about human behavior.
The selection of priors is one of the most controversial
and open issues in Bayesian inference. To address
this problem we have created a synthetic agents modeling
package which allows us to build flexible prior
behavior models.
5.1 Synthetic Agents Behaviors
We have developed a framework for creating synthetic
agents that mimic human behavior in a virtual en-
vironment. The agents can be assigned different behaviors
and they can interact with each other as well.
Currently they can generate 5 different interacting behaviors
and various kinds of individual behaviors (with
no interaction). The parameters of this virtual environment
are modeled on the basis of a real pedestrian
scene from which we obtained (by hand) measurements
of typical pedestrian movement.
One of the main motivations for constructing such
synthetic agents is the ability to generate synthetic
data which allows us to determine which Markov
model architecture will be best for recognizing a new
behavior (since it is difficult to collect real examples
of rare behaviors). By designing the synthetic agents
models such that they have the best generalization
and invariance properties possible, we can obtain flexible
prior models that are transferable to real human
behaviors with little or no need of additional training.
The use of synthetic agents to generate robust behavior
models from very few real behavior examples is of
special importance in a visual surveillance task, where
typically the behaviors of greatest interest are also the
most rare.
In the experiments reported here, we considered five
different interacting behaviors: (1) Follow, reach and
walk together (inter1), (2) Approach, meet and go on
separately (inter2), (3) Approach, meet and go on together
(inter3), (4) Change direction in order to meet,
approach, meet and continue together (inter4), and
Change direction in order to meet, approach, meet
and go on separately (inter5).
Note that we assume that these interactions can
happen at any moment in time and at any location,
provided only that the precondititions for the interactions
are satisfied.
For each agent the position, orientation and velocity
is measured, and from this data a feature vector
is constructed which consists of: -
d 12 , the derivative
of the relative distance between two agents; ff
or degree of alignment of the agents,
and
the magnitude of their
velocities. Note that such feature vector is invariant
to the absolute position and direction of the agents
and the particular environment they are in.

Figure

5 illustrates the agents trajectories and associated
feature vector for an example of interaction
2, i.e. an 'approach, meet and continue separately'
behavior.
-0.4
-0.2Alignment
Relative distance
Derivative of Relative distance

Figure

5: Example trajectories and feature vector for
interaction 2, or approach, meet and continue separately
behavior.
5.1.1 Comparison of CHMM and HMM
architectures
We built models of the previously described interactions
with both CHMMs and HMMs. We used 2
or 3 states per chain in the case of CHMMs, and 3
to 5 states in the case of HMMs (accordingly to the
complexity of the various interactions). Each of these
architectures corresponds to a different physical hy-
pothesis: CHMMs encode a spatial coupling in time
between two agents (e.g., a non-stationary process)
whereas HMMs model the data as an isolated, stationary
process. We used from 11 to 75 sequences
for training each of the models, depending on their
complexity, such that we avoided overfitting. The optimal
number of training examples, of states for each
interaction as well as the optimal model parameters
were obtained by a 10% cross-validation process. In
all cases, the models were set up with a full state-to-
state connection topology, so that the training algorithm
was responsible for determining an appropriate
state structure for the training data. The feature vector
was 6-dimensional in the case of HMMs, whereas
in the case of CHMMs each agent was modeled by
a different chain, each of them with a 3-dimensional
feature vector.
To compare the performance of the two previously
described architectures we used the best trained models
to classify 20 unseen new sequences. In order
to find the most likely model, the Viterbi algorithm
was used for HMMs and the N-heads dynamic programming
forward-backward propagation algorithm
for CHMMs.

Table

5.1.1 illustrates the accuracy for each of the
two different architectures and interactions. Note the
superiority of CHMMs versus HMMs for classifying
the different interactions and, more significantly, identifying
the case in which there are no interactions
present in the testing data.
Accuracy on synthetic data
HMMs CHMMs

Table

1: Accuracy for HMMs and CHMMs on synthetic
data. Accuracy at recognizing when no inter-action
occurs ('No inter'), and accuracy at classifying
each type of interaction: 'Inter1' is follow, reach and
walk together; 'Inter2' is approach, meet and go on;
'Inter3' is approach, meet and continue together; 'In-
ter4' is change direction to meet, approach, meet and
go together and 'Inter5' is change direction to meet,
approach, meet and go on separately
Complexity in time and space is an important issue
when modeling dynamic time series. The number
of degrees of freedom (state-to-state probabili-
ties+output means+output covariances) in the largest
best-scoring model was 85 for HMMs and 54 for
CHMMs. We also performed an analysis of the accuracies
of the models and architectures with respect
to the number of sequences used for training. Figure
5.1.1 illustrates the accuracies in the case of interaction
4 (change direction for meeting, stop and continue
together). Efficiency in terms of training data
is specially important in the case of on-line real-time
learning systems -such as ours would ultimately be-
and/or in domains in which collecting clean labeled
data may be difficult.
901030507090number of sequences used for training
accurancy
Single HMMs
Coupled HMMs
curve for synthetic data CHMMs
False alarm rate
Detection
rate

Figure

First figure: Accuracies of CHMMs (solid
line) and HMMs (dotted line) for one particular in-
teraction. The dashed line is the accuracy on testing
without considering the case of no interaction, while
the dark line includes this case. Second figure: ROC
curve on synthetic data.
The cross-product HMMs that result from incorporating
both generative processes into the same joint-
product state space usually requires many more sequences
for training because of the larger number of
parameters. In our case, this appears to result in a accuracy
ceiling of around 80% for any amount of training
that was evaluated, whereas for CHMMs we were
able to reach approximately 100% accuracy with only
a small amount of training. From this result it seems
that the CHMMs architecture, with two coupled generative
processes, is more suited to the problem of the
behavior of interacting agents than a generative process
encoded by a single HMM.
In a visual surveillance system the false alarm rate
is often as important as the classification accuracy.
In an ideal automatic surveillance system, all the targeted
behaviors should be detected with a close-to-
zero false alarm rate, so that we can reasonably alert a
human operator to examine them further. To analyze
this aspect of our system's performance, we calculated
the system's ROC curve. Figure 5.1.1 shows that it
is quite possible to achieve very low false alarm rates
while still maintaining good classification accuracy.
5.2 Pedestrian Behaviors
Our goal is to develop a framework for detecting, classifying
and learning generic models of behavior in a
visual surveillance situation. It is important that the
models be generic, applicable to many different situa-
tions, rather than being tuned to the particular viewing
or site. This was one of our main motivations
for developing a virtual agent environment for modeling
behaviors. If the synthetic agents are 'similar'
enough in their behavior to humans, then the same
models that were trained with synthetic data should
be directly applicable to human data. This section
describes the experiments we have performed analyzing
real pedestrian data using both synthetic and site-specific
models (models trained on data from the site
being monitored).
5.2.1 Data collection and preprocessing
Using the person detection and tracking system described
in section 3 we obtained 2D blob features for
each person in several hours of video. Up to 20 examples
of following and various types of meeting behaviors
were detected and processed.
The feature vector - x coming from the computer
vision processing module consisted of the 2D (x; y)
centroid (mean position) of each person's blob, the
Kalman Filter state for each instant of time, consisting
of (-x; -
y), where -: represents the filter estimation,
and the (r; components of the mean of the Gaussian
fitted to each blob in color space. The frame-rate
of the vision system was of about 20-30 Hz on an SGI
R10000 O2 computer. We low-pass filtered the data
with a 3Hz cutoff filter and computed for every pair
of nearby persons a feature vector consisting of: -
derivative of the relative distance between two per-
sons, jv i norm of the velocity vector for each
person, or degree of alignment
of the trajectories of each person. Typical trajectories
and feature vectors for an 'approach, meet and continue
separately' behavior (interaction 2) are shown in
figure 7. This is the same type of behavior as the one
displayed in figure 5 for the synthetic agents. Note the
similarity of the feature vectors in both cases.
5.2.2 Behavior Models and Results
CHMMs were used for modeling three different be-
haviors: meet and continue together (interaction 3);
meet and split (interaction 2) and follow (interaction
1). In addition, an interaction versus no interaction
detection test was also performed. HMMs performed
1.5Velocity Magnitudes
100 200 300
-1.4
-1.2
-0.4
-0.2Alignment
Relative distance
100 200 300
Derivative of Relative
distance

Figure

7: Example trajectories and feature vector for
interaction 2, or approach, meet and continue separately
behavior.
much worse than CHMMs and therefore we omit reporting
their results.
We used models trained with two types of data:
1. Prior-only (synthetic data) models: that is, the
behavior models learned in our synthetic agent
environment and then directly applied to the
real data with no additional training or tuning
of the parameters.
2. Posterior (synthetic-plus-real data) models: new
behavior models trained by using as starting
points the synthetic best models. We used 8 examples
of each interaction data from the specific
site.
Recognition accuracies for both these 'prior' and 'pos-
terior' CHMMs are summarized in table 5.2.2. It is
noteworthy that with only 8 training examples, the
recognition accuracy on the real data could be raised
to 100%. This results demonstrates the ability to accomplish
extremely rapid refinement of our behavior
models from the initial prior models.
Finally the ROC curve for the posterior CHMMs is
displayed in figure 8.
One of the most interesting results from these experiments
is the high accuracy obtained when testing
the a priori models obtained from synthetic agent
simulations. The fact that a priori models transfer
so well to real data demonstrates the robustness of
the approach. It shows that with our synthetic agent
training system, we can develop models of many different
types of behavior - avoiding thus the problem
of limited amount of training data - and apply these
models to real human behaviors without additional
parameter tuning or training.
Parameters sensitivity In order to evaluate the
sensitivity of our classification accuracy to variations
in the model parameters, we trained a set of models
where we changed different parameters of the agents'
Testing on real pedestrian data
Prior Posterior
CHMMs CHMMs
No-inter 90.9 100

Table

2: Accuracy for both untuned, a priori models
and site-specific CHMMs tested on real pedestrian
data. The first entry in each row is the interaction
vs no-interaction accuracy, the remaining entries are
classification accuracies between the different interacting
behaviors. Interactions are: 'Inter1' follow, reach
and walk together; 'Inter2' approach, meet and go on;
'Inter3' approach, meet and continue together.
curve for pedestrian data CHMM
False alarm rate
Detection
rate

Figure

8: ROC curve for real pedestrian data
dynamics by factors of 2:5 and 5. The performance
of these altered models turned out to be virtually the
same in every case except for the 'inter1' (follow) inter-
action, which seems to be sensitive to people's relative
rates of movement.
6 Summary and Conclusions
In this paper we have described a computer vision system
and a mathematical modeling framework for recognizing
different human behaviors and interactions in
a visual surveillance task. Our system combines top-down
with bottom-up information in a closed feedback
loop, with both components employing a statistical
Bayesian approach.
Two different state-based statistical learning archi-
tectures, namely HMMs and CHMMs, have been proposed
and compared for modeling behaviors and in-
teractions. The superiority of the CHMM formulation
has been demonstrated in terms of both training efficiency
and classification accuracy. A synthetic agent
training system has been created in order to develop
flexible and interpretable prior behavior models, and
we have demonstrated the ability to use these a priori
models to accurately classify real behaviors with
no additional tuning or training. This fact is specially
important, given the limited amount of training data
available.

Acknowledgments

We would like to sincerely thank Michael Jordan, Tony
Jebara and Matthew Brand for their inestimable help
and insightful comments.


Appendix

A: Forward (ff) and
Backward (fi) expressions for CHMMs
In [4] a deterministic approximation for maximum a
posterior (MAP) state estimation is introduced. It enables
fast classification and parameter estimation via
expectation maximization, and also obtains an upper
bound on the cross entropy with the full (combina-
toric) posterior which can be minimized using a sub-space
that is linear in the number of state variables.
An "N-heads" dynamic programming algorithm samples
from the O(N ) highest probability paths through
a compacted state trellis, with complexity O(T (CN
for C chains of N states apiece observing T data
points. For interesting cases with limited couplings
the complexity falls further to O(TCN 2 ).
For HMMs the forward-backward or Baum-Welch
algorithm provides expressions for the ff and fi vari-
ables, whose product leads to the likelihood of a sequence
at each instant of time. In the case of CHMMs
two state-paths have to be followed over time for each
chain: one path corresponds to the 'head' (represented
with subscript 'h') and another corresponds to the
'sidekick' (indicated with subscript 'k') of this head.
Therefore, in the new forward-backward algorithm the
expressions for computing the ff and fi variables will
incorporate the probabilities of the head and sidekick
for each chain (the second chain is indicated with 0 ).
As an illustration of the effect of maintaining multiple
paths per chain, the traditional expression for the ff
variable in a single HMM:
will be transformed into a pair of equations, one for
the full posterior ff   and another for the marginalized
posterior ff:
ff
jh
ff
jh
ff
The fi variable can be computed in a similar way by
tracing back through the paths selected by the forward
analysis. After collecting statistics using N-heads dynamic
programming, transition matrices within chains
are re-estimated according to the conventional HMM
expression. The coupling matrices are given by:



--R

Active perception vs. passive per- ception
The representation space paradigm of concurrent evolving object de- scriptions
Computers seeing action.
Coupled hidden markov models for modeling interacting processes.
Alex Pent- land
Operations for learning with graphical models.
A guide to the literature on learning probabilistic networks from data.
Advanced visual surveillance using bayesian networks.
What is going on?
Active gesture recognition using partially observable markov decision processes.
Building qualitative event models automatically from visual input.
Factorial hidden Markov models.
A tutorial on learning with bayesian networks.
Automatic symbolic traffic scene analysis using belief networks.
An unsupervised clustering approach to spatial preprocessing of mss imagery.
Probabilistic visual learning for object detection.
From image sequences towards conceptual descriptions.
Lafter: Lips and face tracking.
Classification by clustering.
Modeling and prediction of human behavior.
A tutorial on hidden markov models and selected applications in speech recognition.
Boltzmann chains and hidden Markov models.
Probabilistic independence networks for hidden Markov probability models.
Mean field networks that learn to discriminate temporally distorted strings.


--TR

--CTR
Koichi Sato , Brian L. Evans , J. K. Aggarwal, Designing an Embedded Video Processing Camera Using a 16-bit Microprocessor for a Surveillance System, Journal of VLSI Signal Processing Systems, v.42 n.1, p.57-68, January   2006
Lang Congyan , Xu De, An event detection framework in video sequences based on hierarchic event structure perception, Proceedings of the 5th WSEAS International Conference on Signal Processing, Robotics and Automation, p.307-312, February 15-17, 2006, Madrid, Spain
A. Pentland, Learning Communities  Understanding Information Flow in Human Networks, BT Technology Journal, v.22 n.4, p.62-70, October 2004
Michael Cheng , Binh Pham , Dian Tjondronegoro, Tracking and video surveillance activity analysis, Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia, November 29-December 02, 2006, Kuala Lumpur, Malaysia
Iain McCowan , Daniel Gatica-Perez , Samy Bengio , Guillaume Lathoud , Mark Barnard , Dong Zhang, Automatic Analysis of Multimodal Group Actions in Meetings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.305-317, March 2005
Alberto Avanzi , Franois Brmond , Christophe Tornieri , Monique Thonnat, Design and assessment of an intelligent activity monitoring platform, EURASIP Journal on Applied Signal Processing, v.2005 n.1, p.2359-2374, 1 January 2005
Longin Jan Latecki , Roland Miezianko , Dragoljub Pokrajac, Reliability of motion features in surveillance videos, Integrated Computer-Aided Engineering, v.12 n.3, p.279-290, July 2005
Lucjan Pelc , Bogdan Kwolek, Recognition of action meeting videos using timed automata, Machine Graphics & Vision International Journal, v.15 n.3, p.577-584, January 2006
Sangho Park , J. K. Aggarwal, Recognition of two-person interactions using a hierarchical Bayesian network, First ACM SIGMM international workshop on Video surveillance, November 02-08, 2003, Berkeley, California
Sangho Park , Mohan M. Trivedi, Analysis and query of person-vehicle interactions in homography domain, Proceedings of the 4th ACM international workshop on Video surveillance and sensor networks, October 27-27, 2006, Santa Barbara, California, USA
Maja Mateti , Slobodan Ribari , Ivo Ipi, Qualitative Modelling and Analysis of Animal Behaviour, Applied Intelligence, v.21 n.1, p.25-44, July-August 2004
Antoine Manzanera , Julien C. Richefeu, A new motion detection algorithm based on - background estimation, Pattern Recognition Letters, v.28 n.3, p.320-328, February, 2007
Rita Cucchiara , Costantino Grana , Andrea Prati , Roberto Vezzani, Computer vision techniques for PDA accessibility of in-house video surveillance, First ACM SIGMM international workshop on Video surveillance, November 02-08, 2003, Berkeley, California
Donatello Conte , Pasquale Foggia , Jean-Michel Jolion , Mario Vento, A graph-based, multi-resolution algorithm for tracking objects in presence of occlusions, Pattern Recognition, v.39 n.4, p.562-572, April, 2006
Somboon Hongeng , Ram Nevatia , Francois Bremond, Video-based event recognition: activity representation and probabilistic recognition methods, Computer Vision and Image Understanding, v.96 n.2, p.129-162, November 2004
Amit Sethi , Mandar Rahurkar , Thomas S. Huang, Event detection using "variable module graphs" for home care applications, EURASIP Journal on Applied Signal Processing, v.2007 n.1, p.111-111, 1 January 2007
Alex Pentland , Tanzeem Choudhury , Nathan Eagle , Push Singh, Human dynamics: computation for organizations, Pattern Recognition Letters, v.26 n.4, p.503-511, March 2005
Albert Ali Salah , Ethem Alpaydin , Lale Akarun, A Selective Attention-Based Method for Visual Pattern Recognition with Application to Handwritten Digit Recognition and Face Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.3, p.420-425, March 2002
Dong Zhang , Daniel Gatica-Perez , Samy Bengio , Iain McCowan , Guillaume Lathoud, Multimodal group action clustering in meetings, Proceedings of the ACM 2nd international workshop on Video surveillance & sensor networks, October 15-15, 2004, New York, NY, USA
Maria Cecilla Mazzaro , Mario Sznaier , Octavia Camps, A Model (In)Validation Approach to Gait Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.11, p.1820-1825, November 2005
Daniel DeMenthon , David Doermann, Video retrieval using spatio-temporal descriptors, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
Ying Luo , Tzong-Der Wu , Jenq-Neng Hwang, Object-based analysis and interpretation of human motion in sports video sequences by dynamic Bayesian networks, Computer Vision and Image Understanding, v.92 n.2-3, p.196-216, November/December
Rokia Missaoui , Roman M. Palenichka, Effective image and video mining: an overview of model-based approaches, Proceedings of the 6th international workshop on Multimedia data mining: mining integrated media and complex data, p.43-52, August 21-21, 2005, Chicago, Illinois
Ruth Aguilar-Ponce , Ashok Kumar , J. Luis Tecpanecatl-Xihuitl , Magdy Bayoumi, A network of sensor-based framework for automated visual surveillance, Journal of Network and Computer Applications, v.30 n.3, p.1244-1271, August, 2007
Yaser Sheikh , Mubarak Shah, Bayesian Modeling of Dynamic Scenes for Object Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.11, p.1778-1792, November 2005
Youfu Wu , Jun Shen , Mo Dai, Traffic object detections and its action analysis, Pattern Recognition Letters, v.26 n.13, p.1963-1984, 1 October 2005
Datong Chen , Jie Yang , Howard D. Wactlar, Towards automatic analysis of social interaction patterns in a nursing home environment from video, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA
Cen Rao , Mubarak Shah , Tanveer Syeda-Mahmood, Invariance in motion analysis of videos, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
Tao Xiang , Shaogang Gong, Model Selection for Unsupervised Learning of Visual Context, International Journal of Computer Vision, v.69 n.2, p.181-201, August    2006
Tao Xiang , Shaogang Gong, Beyond Tracking: Modelling Activity and Understanding Behaviour, International Journal of Computer Vision, v.67 n.1, p.21-51, April     2006
Ulf Ekblad , Jason M. Kinser, Theoretical foundation of the intersecting cortical model and its use for change detection of aircraft, cars, and nuclear explosion tests, Signal Processing, v.84 n.7, p.1131-1146, July 2004
Rmer Rosales , Stan Sclaroff, A framework for heading-guided recognition of human activity, Computer Vision and Image Understanding, v.91 n.3, p.335-367, September
Gianluca Antonini , Santiago Venegas Martinez , Michel Bierlaire , Jean Philippe Thiran, Behavioral Priors for Detection and Tracking of Pedestrians in Video Sequences, International Journal of Computer Vision, v.69 n.2, p.159-180, August    2006
Datong Chen , Jie Yang , Robert Malkin , Howard D. Wactlar, Detecting social interactions of the elderly in a nursing home environment, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.3 n.1, p.6-es, February 2007
Sudeep Sarkar , Daniel Majchrzak , Kishore Korimilli, Perceptual organization based computational model for robust segmentation of moving objects, Computer Vision and Image Understanding, v.86 n.3, p.141-170, June 2002
Alper Yilmaz , Omar Javed , Mubarak Shah, Object tracking: A survey, ACM Computing Surveys (CSUR), v.38 n.4, p.13-es, 2006
Thomas B. Moeslund , Adrian Hilton , Volker Krger, A survey of advances in vision-based human motion capture and analysis, Computer Vision and Image Understanding, v.104 n.2, p.90-126, November 2006
Hidden Markov Models;tracking;visual surveillance;human behavior recognition;people detection