Surprise on ONR Contact Fusion

The work described here is part of an ONR project whose goal is to accelerate the post mission analysis process and compress MCM timelines through the development of a flexible, modular approach for fusing data. Due to sensitivity of the project, the data shown here are synthetically generated and some parts of the algorithm are deliberately withheld.



In a typical mine-hunting mission, multiple sensors, e.g a side-scan sonar, may detect the same object several times due to overlapping tracks designed to illuminate the target.  Thus, over the course of a survey, the same object may be detected many times, resulting in numerous detections that must be combined into a single label.

We have automated the contact fusion by probabilistically modeling sensor and sensing platform information via graphical models known as dynamic trees (DT), which provide a flexible, analytical, multi-scale framework for decision making. This approach, though, requires a training set to learn the parameters, which are limited, thus hampering its performance. Furthermore, the DT structure and parameters have to remain constant during operation.

In a real environment though, new contacts are encountered constantly. The DTs need to adapt to accommodate them. This would enhance the statistical models and improve performance. However, if it is not handled with care, the models created in the training set can become corrupted and hinder performance.


Surprise DT Update

DTs need to retain previously stored material while learning new information. Surprise is used to monitor the information available in an observation and its effect on the state of the system. This will prevent outliers from incorrectly modifying the DTs, but allow interesting observations to improve the system knowledge.

Setup: Consider each existing DT model M as a mixture of Gaussians M=\{m_i\}^\mathbb{M}_{i=1}, where each model is represented as follows:


where \pi^t_{i}, \mu^t_{i0}, and \Sigma^t_{i0} denote the initial mixture coefficient, mean, and covariance matrix at time t for the i^{th} component of the model M.

Initialization: At time t=0, \{\pi^0_{i}, \mu^0_{i0}, \Sigma^0_{i0}\}^\mathbb{M}_{i=1} are calculated directly from the existing library. (Note: initial parameters may not be very accurate.)

Compute Surprise: When a new sample x_n arrives at t, calculate the surprise, S(x_n,M^t), for model M^t=\{m^t_i\}^\mathbb{M}_{i=1} as:

S(x_n,M^t) = D_{CS}(p(x|M^t),p(x|x_n,M^t)),

where p(x|M^t) is obtained from the EM algorithm. The term p(x|x_n,M^t) is also a mixture of Gaussians updated when the new sample x_n is added into the model.

Update DTs: Once the surprise value is computed, check the three conditions:

  • Outlier: S(x_n, M) > T_{out}, the new sample x_n is an outlier and is stored in the outlier buffer. If multiple samples are considered as outliers and they are similar, a new model will be created.
  • Interesting: T_{out} \geq S(x_n, M) \geq T_{par}, x_n belongs to an existing cluster, and all the parameters are updated according to the new sample.
  • Redundant: T_{par} > S(x_n, M), x_n belongs to an existing cluster, however posterior parameters are not updated to prevent overfitting.

This allows us to more intuitively find the summarized location and uncertainty of each cluster/object i from \mu_{i0} and \Sigma_{i0} respectively.


Experiments and Results

A dataset was generated to simulate a real environment scenario where the objects are viewed from several tracks resulting in multiple observations per object as shown in the figure below, where true object locations are shown using red stars and the observation positions are shown in blue dots. We focus on each group individually, since discrepancies usually occur among those observations.

Data Description
The dataset consists of five groups of objects where groups 1, 2, and 3 have objects belonging to the same object type, and groups 4 and 5 have objects of different object type. These groups of objects are placed on three different backgrounds with several variations allowing us to generate three distinctive sets of scenarios: same, similar, and different background types. For each target, there are 24 observations from the different tracks. Their positions are simulated from three distribution types: normal, uniform, and beta, with various degrees of difficulty. To remove object location bias, each group is placed on all five cluster locations, and the object order is permuted. This results in a total of 27,000 scenarios.

Three key components were used for feature extraction: location, background, and object. Location features are x and y geographic position. Background features are texture correlation length in x and y direction, and K-distribution shape parameter. Object features are similarity measures to the three most common object shapes. (details of these features are omitted).

Experiments: Comparison to other data models
Four different cluster modeling systems were used to compare performance:

  • Gaussian Model
  • Gaussian Mixture Model
  • Non-parametric PDF estimation
  • Dynamic Trees

The table below shows the results of comparing these methods on scenarios containing different object types lying on different background types (best discrimination). The unassigned column shows the percentage of samples that the models, using surprise, were unable to categorize; these samples were considered as outliers. Online DT performs better than the other methods in correctly classifying most of the samples. Mixture of Gaussians is not shown in the table because it performed very poorly (due to limited number of samples). Online DT performs better than offline DT because it is a semi-supervised method.

Model                     Correct            Incorrect         Unassigned     
Offline DT 88.82% 11.18% n/a
Single Gaussian 86.40% 2.25% 11.35%
Nonparametric 91.50% 2.07% 6.43%
Online DT 95.74% 2.97% 1.29%


Experiments: DT on different scenario types
Below, we show results of using surprise on DT on all the scenarios for the three location distributions: normal, beta, and uniform. Each table summarizes the results of six different scenario cases: three background types \times two object types. As can be seen from the results, the most difficult scenarios are those where both the objects and the background are of the same type (top-left), and the easiest those where they are of different types (bottom-right).


Normal Distribution

Object Same Type Different Type
Background         Correct Incorrect Unasgnd Correct Incorrect Unasgnd
Same Type 92.11% 5.50% 2.39% 92.28% 1.27% 0.45%
Similar Type 93.44% 4.53% 2.04% 98.31% 1.37% 0.32%
Different Type 94.12% 3.98% 1.89% 98.13% 1.41% 0.45%


Beta Distribution

Object Same Type Different Type
Background         Correct Incorrect Unasgnd Correct Incorrect Unasgnd
Same Type 84.47% 11.20% 4.32% 92.44% 4.95% 2.60%
Similar Type 86.83% 9.19% 3.98% 92.26% 5.34% 2.40%
Different Type 89.23% 7.62% 3.16% 93.38% 4.45% 2.17%


Uniform Distribution

Object Same Type Different Type
Background         Correct Incorrect Unasgnd Correct Incorrect Unasgnd
Same Type 86.64% 9.49% 3.87% 95.27% 3.15% 1.58%
Similar Type 88.87% 7.57% 3.56% 95.55% 3.16% 1.29%
Different Type 90.31% 6.69% 3.00% 95.86% 2.92% 1.22%