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:
|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 our environment 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 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