Information Assimilation

The goal of our *MPI-Video* infrastructure is to
provide a means to integrate many algorithms that deal with dynamic
systems, such as Kalman filters, extended Kalman filter, probabilistic
data association filters, and HMM estimation, into a single,
integrated system. For this discussion we set aside the
details of these dynamic systems, and focus on how
these algorithms are implemented within the
*MPI-Video*
infrastructure, and how
assimilation of information between layers occurs in the system.

The iterative paradigm of algorithms that estimate the state of dynamic systems.

Algorithms for estimating the state of a dynamic systems share a common paradigm, described in the figure above. The algorithm iteratively performs the operations tabulated below:

Operation | Description |
---|---|

Extrapolate |
This is where knowledge of the dynamic behavior of the system
comes into play. A dynamic model allows the system to
extrapolate its current state in order to predict its future state. |

Update |
This is where measurements and other information are considered in the estimate of the state. |

Summary of operations performed in the estimation of the state of a dynamic system

This paradigm forms the basis for information assimilation in an
*MPI-Video system*. The Kalman filter
is a perfect example of an algorithm that
estimates state using the extrapolation/update paradigm. It maintains
the probability distributions of state variables in a dynamic system.
The assumption that the state is continuous and normally distributed
means that the distribution may be represented completely by its first
and second moments, and the first moments provide a convenient
estimate of the state. These assumptions are too restrictive for the
EM. Fortunately, as algorithms for the estimation of HMMs
demonstrate, the paradigm works equally well for nominal states, and
arbitrary probability distributions. The following description of
information assimilation in our *MPI-Video* infrastructure first
describes the assimilation as a Kalman filter, and then extrapolates
to HMM methods.

Refer to figure above. Let be an
*n*-dimensional continuous state vector for time interval *t*.
The estimate of that state, ,
has an associated error covariance matrix .
The first stage extrapolates
and based on a system model to get the
intermediate values and
. The update
stage updates the intermediate values based on new data,
, to get
and .

In its basic form, the Kalman filter estimates a single dynamic state
variable based on a sequence of measurements of that state. However,
the EM is not limited to a single state vector. A layer of the EM can
contain a list of state vectors, e.g., the three-dimensional object
tracker (see
parking lot surveillance example)
has a list of object states.
Furthermore, state vectors in different types of layers represent
different quantities. In place of the single state vector
, the EM has sets of vectors
, where
is the
estimated state vector for object *i* in layer *l*.
As illustrated in the
figure below, extrapolation for the EM is done for
all states in all layers.

The iterative paradigm of ourenvironment model. It shares the same paradigm used for most dynamic systems, however, state updates not only use data that are measurements from sensors, but uses states in other layers as data.

In addition, the EM updates state vectors
using not only new measurements from sensors, but also using data from
other layers in the EM. In place of a single measurement,
, we have the set
. There is no need for the EM to distinguish
between data from a sensor and data from another layer. If
is the set, at time *t*,
of all index pairs *(k,j)* for
states that match object *i* in layer *l*, then updates are performed
for all states, in all layers, for all matches. The equations on the
left-hand side of the table below show the form of the
extrapolation and update for continuous states in the EM. The
right-hand side of the table shows the counterparts for
nominal variables and arbitrary probability distributions. In the
nominal case, the state vectors, ,
become vectors of random variables,
. The system model, *F*
represents the state transition probabilities. The probability
distribution of the nominal version is equivalent to the state
estimate and covariance of the Kalman filter.

Kalman Filter (continuous) | HMM Estimation (nominal) |
---|---|

The duality of the Kalman filter (continuous states, Gaussian distributions) and the HMM (nominal states, arbitrary distribution) equivalent. In the continuous case, F is a linear dynamic system model Q is the system error covariance, H is a measurement model that relates the states in one layer to states in another, and R is the measurement error covariance. K is the Kalman gain matrix. In the nominal case, F is the set of probabilities that one state will make a transition to another.

This gives us a powerful system for data assimilation that has the following properties:

- The system is strongly coupled because the Kalman filter does not care if different measurements are from the same sensor at different times or the different sensors at the same time.
- Layers in the EM may include
*a priori*knowledge, treating it as an additional source of measurement data. - The modular nature of the system makes it easy to add and remove layers and sensors allowing easy configuration of the system to suit various tasks, and handling of failure or variable performance of sensors.
- The modular architecture raises the possibility of a dynamic EM that adds and deletes layers as the needs of the EM clients change.

The upward migration of data in the
parking lot surveillance example
implements a feed-forward system only. A recurrent
system requires that data move both up and down in the EM. Potential
exists downward migration of data. For example,
the known posture of a person (see ECM posture estimation)
can aid stochastic
segmentation at a lower level by indicating where a person occludes the
background. Sworder *et al.* [Sworder97] suggest another
downward path in which high-level recognition of a maneuver aids in
low-level tracking of an object.

MPI VSAM Home Page --
Executive Summary --
Our Vision --
Project Information --

Papers --
Investigators --
Administrative Staff --
Related Links

*Web page design by
Jeffrey E. Boyd
*