US7974814B2 - Multiple sensor fusion engine - Google Patents

Abstract

A method and system for of fusing the outputs of multiple sensors. The output of each sensor including a sensor class probability vector based on each sensor's classification database is input to a fusion engine which estimates a base class probability vector based on the sensor class probabilities output by the sensors and a preconfigured base database including base classes.

Description

FIELD OF THE INVENTION

This subject invention relates to sensors including but not limited to radar systems used in missile defense applications.

BACKGROUND OF THE INVENTION

Two or more sensors are often used to detect different or even the same parameters. In one non-limiting example, a Forward Based X-Rand Radar subsystem may be used in a missile defense application to detect, track, and discriminate threats. Other radar subsystems such as a Sea-Based X-Band Radar may also be used in the missile defense application.

When a threat is launched, the missile and its warheads and decoys are tracked. A battle management center then receives the output from the various radar subsystems and deploys, sometimes automatically, an interceptor to destroy any threats. The radar subsystems output kinematic data (e.g., the number of detected objects, their location, speed, and trajectory) as well as classification data with assigned probabilities.

The classification data may discriminate, as between numerous detected objects, whether they are lethal or not, friend or foe, and their type (e.g., re-entry vehicle, decoy, and the like), among other classification criteria.

Each radar subsystem includes a unique database and software which outputs class probability vectors which are a function of the measurements obtained from the radar itself and the database of that radar subsystem. As between a Forward Based X-Band Radar subsystem and a Sea-Based X-Band Radar subsystem, for example, the respective measurements may be different for a given target. The respective radar databases may also be configured differently. And, the software based analysis carried out by each subsystem to analyze their measurements as a function of their respective databases may be different. This is especially true for radar subsystems supplied by different vendors and/or at different times or as between different versions in a product development effort.

So, one radar subsystem may provide, to the battle management center, a sensor class probability vector P₁ as a function of its measurements Y₁ and its database D₁ and a different radar subsystem may provide a different sensor class probability vector P₂ as a function of its measurements Y₂ and its database D₂.

It would be advantageous, then, to configure the different radar subsystems to transmit their actual measurements to the battle management center and classify potential threats based on all the incoming measurements. Currently, because of the configuration of the various radar subsystems, this is not possible. Also, the data communications interfaces would have to change.

Multiplying and normalizing the probability vectors from each radar subsystem does not work because correlations are ignored. Other possible solutions either fail to yield accurate results or are difficult to implement.

SUMMARY OF THE INVENTION

It is therefore an object of this invention to provide a new method of and system for resolving and fusing the output of multiple sensors.

It is a further object of this invention to provide such a method and system which can be used not only in a missile defense application but also in other applications.

It is a further object of this invention to provide such a method and system which, when employed in a missile defense application, provides better protection.

It is a further object of this invention to provide such a method and system which, in any environment, is more accurate and more reliable.

It is a further object of this invention to provide such a method and system which is fairly simple, fast, and which operates in real time.

It is a further object of this invention to provide such a method and system which improves the discrimination of multi-sensor data.

It is a further object of this invention to provide such a method and system which does not require a change to the communication interfaces.

It is a further object of this invention to provide such a method and system which requires less memory and computational effort.

The subject invention results from the realization that by fusing the outputs of multiple sensors using a preconfigured base database and a mapping approach wherein an ideal classifier function is approximated, the method and system of this invention heuristically chooses a way to parameterize the classifier function which is then optimized according to a cost function. But, the typically computation intensive optimization is performed off-line and, as such, mapping can occur in real time. The result is a feasible, real time system and method using a minimal amount of computational effort and which yields good results.

The subject invention, however, in other embodiments, need not achieve all these objectives and the claims hereof should not be limited to structures or methods capable of achieving these objectives.

The subject invention features a method of fusing the outputs of multiple sensors. The preferred method includes inputting to a fusion engine the output of each sensor including a sensor class probability vector based on each sensor's classification database and estimating a base class probability vector based on the sensor class probabilities output by the sensors and a preconfigured mapping function.

In one example, the sensor class probability vector is converted to log-space. The typical mapping function includes anchor points and estimating may include finding the differences between the log-space probability vectors and the anchor points. The typical mapping function also includes mapping matrices and estimating may include mapping each difference using the mapping matrices. The mapping function may further include reference points and estimating may then include adding reference points to the mapped differences.

Estimating typically includes weighting and summing the mapped differences, converting the weighted and summed mapped differences back to probability space to produce the probability vector, and normalizing the probability vector.

The subject invention also features a system for fusing the output of multiple sensors. The preferred system comprises multiple sensors each including a classification database and each outputting a sensor class probability vector based on its classification database. A fusion engine is responsive to the output of each sensor. A base database includes base classes and the fusion engine is configured to estimate a base class probability vector based on the sensor outputs and the base database classes.

The typical fusion engine is configured to convert the sensor class probability vectors to log-space. A preferred mapping function includes anchor points and the fusion engine is configured to find the differences between the log-space probability vectors and the anchor points. The mapping function may include mapping matrices and the fusion engine is then configured to map each difference using the mapping matrices. If the mapping function includes reference points, the fusion engine can be configured to add reference points to the mapped differences.

The preferred fusion engine is configured to weigh and sum the mapped differences, to convert the weighted and summed mapped differences back to probability space to produce the probability vector, and to normalize the probability vector.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Other objects, features and advantages will occur to those skilled in the art from the following description of a preferred embodiment and the accompanying drawings, in which:

FIG. 1 is a highly schematic view showing an example of an application of a method of fusing the outputs of multiple sensors in accordance with the subject invention;

FIG. 2 is a block diagram showing an example of a fusion node in accordance with the subject invention;

FIG. 3 is a plot of entropy over the simplex in three-dimensional probability space;

FIG. 4 is a plot of entropy over the simplex in log-space in accordance with the subject invention;

FIG. 5 is a flow chart depicting the primary steps associated with the programming of the fusion node of FIG. 2;

FIG. 6 is a graph showing the base and sensor class distributions for an example when the method of the subject invention was implemented;

FIGS. 7A-7C are plots showing the normalized surprisals for 200 sample points for an example of the implementation of the subject invention showing, respectively, probability fusion, mapping, and feature fusion;

FIG. 8 is a graph showing the base and sensor class distributions for a second example of the implementation of the method of the subject invention;

FIGS. 9A-9C are graphs showing the normalized surprisals of 200 sample points for the second example referred to with respect to FIG. 8 for mapping (LS), mapping, and feature fusion, respectively;

FIG. 10 is a graph showing the base and sensor class distributions for a third example of the implementation of the method of the subject invention;

FIGS. 11A-11C are plots of the normalized surprisals of 200 sample points for the third example of FIG. 10 showing mapping (LS), mapping, and feature fusion, respectively; and

FIG. 12 is a flow chart describing how mapping may be accomplished in accordance with the subject invention.

DETAILED DESCRIPTION OF THE INVENTION

Aside from the preferred embodiment or embodiments disclosed below, this invention is capable of other embodiments and of being practiced or being carried out in various ways. Thus, it is to be understood that the invention is not limited in its application to the details of construction and the arrangements of components set forth in the following description or illustrated in the drawings. If only one embodiment is described herein, the claims hereof are not to be limited to that embodiment. Moreover, the claims hereof are not to be read restrictively unless there is clear and convincing evidence manifesting a certain exclusion, restriction, or disclaimer.

FIG. 1 shows multiple sensor subsystems in a ballistic missile defense application in accordance with an example of the subject invention. The multiple sensors include Forward Based X-Band Radar subsystem 10, Sea-Based X-Band Radar subsystem 12, Aegis sensor 14, early warning radar 16, early warning satellite 18, and the like all of which assist in tracking and classifying threat 20 and re-entry vehicles 22 and decoys 24 deployed by missile 20.

The probability vectors (sensor class probabilities) output by each sensor subsystem are transmitted to battle management center 30 which deploys, sometimes automatically, kill vehicle 32 to intercept any targets likely to be threats.

As explained in the Background section above, the different sensors may output different sensor class probabilities to battle management center 30. For example, sensor 10, FIG. 2 (e.g., a Forward Based X-Band Radar subsystem) may output, as shown, sensor class probability vector P₁ which is a function of its measurements (Y₁) and its database (D₁). Sensor 12 (e.g., a Sea-Based X-Band Radar subsystem) may output, as shown, a different sensor class probability vector P₂ which is a function of its measurements (Y₂) and its database (D₂). Each sensor's measurements Y, in turn, are typically a function of the features detected, the sensor parameters, and sensor noise.

The respective measurements may differ for a given target. The respective databases D₁ and D₂ may also be configured differently. And, the software based analysis of each subsystem's measurements as a function of their respective databases may be different.

In the subject invention, fusion node 50 (which may be implemented in a computer located at battle management center 30, FIG. 1) includes software which receives as an input the classification results (P₁, P₂) output by each sensor based on each sensor's database (D₁, D₂). Software within fusion node 50 is configured to estimate a classification result {circumflex over (q)} as a function of P₁, P₂, and D₀, a preconfigured base database populated with base classes as described below.

As explained in the Background Section above, multiple sensor discrimination/fusion is hindered by the current scheme of passing only class probabilities. By passing probabilities rather than features, information is lost. Database mismatch and correlations between features should be accounted for when fusing. The problems with passing only probabilities include the fact that sensors 10 and 12 may have different databases, D₁ and D₂. Comparing probability vectors from the two would be like comparing apples and oranges. Also, the sensors might measure different sets of features that are correlated. Performance can degrade severely if only one sensor's probabilities are used, or if the two probability vectors are fused as if they are independent. One solution according to this invention recovers much of the performance that would be lost if a simple probability fusion were performed.

One or more sensors 10, 12 take measurements of a target's attributes. The sensors can measure different sets of attributes, have different noise variances, and have different measurement parameters (e.g., aspect angle). Rather than passing the measurements to fusion node 50, they each run their own classifier, and pass the resulting probability vector p. The sensors have their own databases D₁ and D₂, which may be different from each other. Fusion node 50 is configured to estimate the probabilities of classes in its own database D₀ which is not necessarily common to any of the sensor databases. The classes of database D₀ are herein called base classes.

Bayes' law optimally classifies from a set (vector) of features as follows:

$\begin{array}{cc}{q}_i\left(y\right)\equiv \mathrm{Pr}\left(c_i|y\right)=\frac{f\left(y|c_i\right)\mathrm{Pr}\left(c_i\right)}{\sum _{i}f\left(y|c_i\right)\mathrm{Pr}\left(c_i\right)}& \left(1\right)\end{array}$

The equation has the same form for a set of class probabilities:

$\begin{array}{cc}{q}_i\left(p\right)\equiv \mathrm{Pr}\left(c_i|p\right)=\frac{f\left(p|c_i\right)\mathrm{Pr}\left(c_i\right)}{\sum _{i}f\left(p|c_i\right)\mathrm{Pr}\left(c_i\right)}& \left(2\right)\end{array}$

The difficulty is that there is no simple explicit form for the likelihoods. Even if the conditional distributions for the features are explicitly defined, the likelihoods won't be.

Three approaches are possible, but two have difficulties in implementation. All three of these approaches make no assumptions about the types of distributions in the databases. The distributions can have any form: Gaussian, Gaussian-sum, uniform, piecewise-linear, and the like. The classifiers can be treated as black boxes. It can help to think of them as arbitrary functions as opposed to classifiers that return probability vectors. Taking this view makes it apparent that the multi sensor fusion problem can be treated in the same way as the single sensor database-mismatch problem. The p vectors are stacked and then processed as usual, because they are nothing but data on which we want to condition our estimates of class probabilities.

One solution is to build a set of conditional histograms offline, one for each class. But, this approach has problems with feasibility. First, a class is chosen and a large number of points in feature space are drawn from that class. Then, the sensor's classifier is run on each point, which yields a p vector. A grid is formed probability space, and how many p vectors fall in each bin are counted. The resulting histogram is an estimate of the probability density function of p, given class i. After the histograms are built offline, they can be used to implement Bayes' law directly by looking up likelihoods in real time. One problem with this method is that it suffers a huge curse of dimensionality for resolution in probability space. For instance, in a problem with one sensor, five sensor classes, and a desired probability resolution of 1%, the number of bins is 100⁵=10¹⁰. To draw enough points to fill those bins without too much quantization might yield 10¹² points for each base class.

Another possible solution, inversion, involves inverting the p vector to find a conditional probability density function for the measurements/features. This method is not practical to implement. Given a p vector, if the sensor classifier function were inverted, the result would be one or more regions of measurement space. A classifier is generally a many to one function:
p=g(y)Y={y:g(y)=p}  (3)
f(y|p)=f(y|yεY)  (4)

Once the possible regions of measurement space are obtained, the ideal feature classifier can be integrated over it, to obtain the conditional class probabilities:

$\begin{array}{cc}\begin{array}{c}q\left(p\right)\equiv \mathrm{Pr}\left(c|p\right)\\ =\int \mathrm{Pr}\left(c|y\right)f\left(y❘p\right)dy\\ =\int q\left(y\right)f\left(y|y\in Y\right)dy\\ =\frac{{\int }_{y\in Y}q\left(y\right)f\left(y\right)dy}{{\int }_{y\in Y}f\left(y\right)dy}.\end{array}& \left(5\right)\end{array}$

This method would be difficult to implement, and would require a large amount of computation in real time.

The preferred approach, called mapping, turns out to be feasible and yields good results. Under certain conditions it can achieve optimal results. In mapping, an approximation is made of the ideal classifier function q(p). The method involves heuristically choosing a way to parameterize this function, and then optimizing it according to a cost function. The computation intensive optimization is preferably performed offline, and the real time application of the mapping uses a small amount of computation. Additionally, this method doesn't suffer the curse of dimensionality as badly as the histogram method because it exploits smoothness of distributions in measurement space. This is loosely analogous to approximating a time series by a truncated Fourier series. Herein the mapping approach is described in more detail.

One preferred cost function for optimizing an estimator of conditional probabilities is the expected value, taken over the data, of the cross-entropy between the optimal estimator and the existing estimator. Of course, the optimal estimator (q(p)) is not known. The cost has the important property that it is minimized by the optimal estimator. The cost function is defined in a form that is convenient for implementation, and can be expressed using the information theoretic terms mentioned above:

The table below defines the nomenclature of the equations also below:

c	The true class. Class definitions are consistent with the base database.
	When c appears as a subscript of a vector, it denotes taking the cth
	element of that vector.
p	The probability vector from a sensor. These classes are the sensor classes.
	For the case where there is more than one sensor, p is a
	larger, stacked vector of the sensors' probability vectors.
q(p)	The true conditional probability vector of the base classes. That is:
	qi(p) = Pr(c = i|p). This is the optimal estimator, which in general,
	is unrealizable.
{circumflex over (q)}(p)	The estimated conditional probability vector of the base classes. This
	function is what we need to define.
Ψ({circumflex over (q)}(·))	The cost of the selected {circumflex over (q)}(·) function. The argument is omitted
	because the cost is averaged over all p, and therefore the cost is not a
	function of p.
f(·)	A continuous probability density function. (A discrete pdf can be
	expressed as a continuous pdf by using delta functions.)
Ef(·)[·]	The expected value of [·] over f(·).
Hx(q(p), {circumflex over (q)}(p))	The cross entropy of {circumflex over (q)}(p) with respect to the true probability vector
	q(p).
H(q(p))	The entropy of q(p).
DKL(q(p)||{circumflex over (q)}(p))	The Kullback-Leibler divergence of {circumflex over (q)}(p) with respect to q(p).

$\begin{array}{cc}\Psi \left(\hat{q}(·)\right)\equiv E_{f\left(c,p\right)}\left[-\log \left({\hat{q}}_c\left(p\right)\right)\right]& \left(6\right)\\ ={\int }_c{\int }_p-\log \left({\hat{q}}_c\left(p\right)\right)f\left(c,p\right)dpdc& \left(7\right)\\ ={\int }_c{\int }_p-\log \left({\hat{q}}_c\left(p\right)\right)f\left(c|p\right)f\left(p\right)dpdc& \left(8\right)\\ ={\int }_{p}f\left(p\right)\sum _i\left[\mathrm{Pr}\left(c=i|p\right)\left[-\log \left({\hat{q}}_i\left(p\right)\right)\right]\right]dp& \left(9\right)\\ ={\int }_{p}f\left(p\right)q^T\left(p\right)\left[-\log \left(\hat{q}\left(p\right)\right)\right]dp& \left(10\right)\\ =E_{f\left(p\right)}\left[H_x\left(q\left(p\right),\hat{q}\left(p\right)\right)\right]& \left(11\right)\\ =E_{f\left(p\right)}\left[H\left(q\left(p\right)\right)\right]+E_{f\left(p\right)}[D_{\mathrm{KL}}\left(q\left(p\right)\hat{q}\left(p\right))\right]& \left(12\right)\end{array}$

Equation 12 shows that the cost is equal to the expected entropy of the optimal estimator plus the expectation of the Kullback-Leibler divergence of our estimator with respect to the optimal estimator. This follows from Equation 11 because cross entropy can always be expressed as: entropy plus KL-divergence. Entropy and KL-divergence are both non-negative quantities, and KL-divergence takes a minimum value of zero when the two probability vectors are equal. The first term in Equation 12 is non-negative, and independent of our estimator—this term is the lower bound of the cost. The second term is also non-negative, and takes the value of zero when the estimator is equal to the optimal estimator. Therefore, the cost is minimized by the optimal estimator.

Equation 6 is interpreted as the expected surprisal of the true class, given the estimated probability vector. The surprisal of an event is defined as the negative logarithm of the probability of the event. Therefore, an occurrence of an event that is thought to have a low probability would have a high surprisal. Intuitively, it can indeed be thought of as how surprised one would be to observe an event. So, the preferred estimator provides class probabilities such that on average, if we were to observe the true class afterwards, we would be the least surprised.

The information-theoretic cost provides the best criteria to optimize our estimator, but it is also useful to use a simpler cost. The other cost is a least squares cost, which produces a relatively quick initial solution in closed form.

The set of all possible n-dimensional probability vectors forms a simplex in n-dimensional probability space. The simplex is the region of points whose elements are non-negative and sum to one. The mapped probability vector should also satisfy these constraints which can be done by either solving a constrained optimization problem, or by projecting the mapped result ({circumflex over ({tilde over (q)}) onto the simplex. The latter method is preferred because solving a constrained problem is more difficult, and the average performance tends to suffer as a result of the constraints. If all elements of {circumflex over ({tilde over (q)} are non-negative, then normalizing it (dividing by its sum) will project the point onto the simplex. If there are negative elements, then there is no satisfactory way to project onto the simplex. Mapping in log-space eliminates this problem. For convenience, define the transforms that go from probability space (FIG. 3) to log-space (FIG. 4) and vice versa:
S(x)≡−log(x), and  (13)
S ⁻¹(x)=exp(x).  (14)

The lowercase s with a subscript denotes a variable that is in log-space. So,
s _p =S(p), and  (15)
p=S ⁻¹(s _p)  (16)

The tilde (˜) signifies that a probability vector hasn't been normalized, i.e. doesn't lie on the simplex. The general form of the mapping function, and the post-mapping normalization are described as:

$\begin{array}{cc}{\stackrel{\widehat{~}}{s}}_q=\mathrm{map}\left(s_p\right),\mathrm{and}& \left(17\right)\\ \hat{q}=\frac{1}{\sum \stackrel{\widehat{~}}{q}}\stackrel{\widehat{~}}{q}.& \left(18\right)\end{array}$

The log function transforms the interval (0,∞) to (−∞,∞), so there are no longer “bad” regions to avoid. The mapping is now optimized with no constraints because any mapped point can be projected onto the simplex. Another reason for mapping in log-space is that distance is more intuitive in log-space. It captures the notion that for probabilities, the difference between 0 and 0.1 is more significant than the difference between 0.6 and 0.7.

We can define a least squares cost function that is the expected value of the distance in log-space between our estimate {circumflex over (q)}(p) and the (super-optimal) feature-fusion estimate q(y). It is unfair to compare our estimate to the feature-fusion estimate, because in general, the p vector contains less discrimination information than the features. However, since the optimal estimator q(p) is not known, q(y) is used in its place.

In the least squares cost, there is something to be considered about normalization and distance. Normalization in log-space is done by projecting a point along the direction of the ones vector 1=[1 1 . . . 1]^T onto the “log-simplex”. In three dimensions, the “log-simplex” is shaped somewhat like a cobweb in the corner of a room. Unlike the simplex, it is unbounded, and it stretches to infinity, asymptotically approaching the “walls” of the “room”. Since the points are normalized after mapping, any two mapped points that differ only by some scalar times the ones vector will result in the same probability vector. Therefore, it is beneficial to disassociate distance along the ones vector from the cost. The resulting least squares cost is:

$\begin{array}{cc}{\Psi }_{\mathrm{LS}}\left(\hat{q}(·)\right)\equiv E_{f\left(y\right)}\left[\Delta s^T{A}^{T}A\Delta s\right],\mathrm{and}& \left(19\right)\\ =E_{f\left(y\right)}\left[\Delta s^{T}A\Delta s\right],& \left(20\right)\\ \mathrm{where}\Delta s=S\left(\stackrel{\widehat{~}}{q}\left(p\right)\right)-S\left(q\left(y\right)\right).& \left(21\right)\end{array}$

The nomenclature of the above equations is described in the following table:

y	The vector of features.
p	The probability vector from a sensor. These classes are the sensor classes.
	For the case where there is more than one sensor, p is a larger, stacked
	vector of the sensors' probability vectors. This is a function of the features
	y, which were measured by the sensors.
q(y)	The ideal feature classifier. This operates on the features, and returns a
	probability vector of the base classes.
(p)	The un-normalized mapping function. This operates on the sensors' probability
	vectors, and returns the un-normalized estimated probability
	vector of the base classes.
S(·)	The conversion from probability space to log-space, defined by:
	S(p) = −log(p)
ΨLS({circumflex over (q)}(·))	The least-squares cost of the selected {circumflex over (q)}(·) function. The argument is
	omitted because the cost is averaged over all p, and therefore the cost is
	not a function of p.
f(·)	A continuous probability density function. (A discrete pdf can be
	expressed as a continuous pdf by using delta functions.)
Ef(·)[·]	The expected value of [·] over f(·).

The matrix A=I−(1/n)11^T is a projection onto the zero-sum plane. A is symmetric and idempotent, so A^TA=A. Remember that we know the deterministic function p(y). {circumflex over (q)}(p) is parameterized in a way that allows a solution for the parameters using least squares.

The function for estimating base class probabilities {circumflex over (q)}(p) is a nonlinear mixing of jointly optimized linear mappings in log-space. One element of the function is the use of “anchor points” to localize mappings to different regions of probability space. The localization involves a nonlinear function that weights the multiple linear mappings. The estimator function carried out by fusion node 50, FIG. 2, and as shown in FIG. 5, typically has nine steps:

In step 60, the probability vectors are stacked. If two or more sensors report probability vectors, they are made into one large vector by stacking them:

$\begin{array}{cc}p=\left[\begin{array}{c}{p}_1\\ {\mathrm{<figure-callout\; id="2"\; label="p"\; filenames="US07974814-20110705-D00000.png,US07974814-20110705-D00002.png"\; state="\{\{state\}\}">p</figure-callout>}}_2\\ ⋮\\ p_n\end{array}\right]& \left(22\right)\end{array}$

This stack is then converted to log-space, step 62. Conversion to log-space occurs by taking the negative natural logarithm of each element:
s _p=−log(p)  (23)

In step 66, the i^th difference (where i=1:n_a) is computed by subtracting the corresponding anchor point s _pi from s_p. The i^th difference is:
Δs _pi =s _p − s _pi  (24)

The weights are computed, step 64 by first finding the squared distance of the input s_p from each of the anchor points { s _pi}. Then, to compute the i^th weight the product is taken of the squared distances to each anchor point except the i^th. The equations for the vector of weights are:

$\begin{array}{cc}{\tilde{w}}_i=\prod _{j\ne i}{\left(s_p-{\stackrel{\_}{s}}_{\mathrm{pj}}\right)}^T\left(s_p-{\stackrel{\_}{s}}_{\mathrm{pj}}\right),\mathrm{and}& \left(25\right)\\ w=\frac{\tilde{w}}{\sum \tilde{w}}.& \left(26\right)\end{array}$

Each difference Δs_pi is mapped, step 68 by performing a matrix multiply with the corresponding mapping matrix M_i, to get the mapped differences:
Δs_qi=M_iΔs_pi  (27)

In step 70, the result of the i^th mapping is computed by adding the i^th reference point s _qi to the i^th mapped difference:
{tilde over (ŝ)} _qi = s _qi +Δs _qi  (28)

In step 72, the results of the individual mappings are combined by taking a weighted sum:

$\begin{array}{cc}{\stackrel{\widehat{~}}{s}}_q=\sum _{i=1}^n{w}_i{\stackrel{\widehat{~}}{s}}_{\mathrm{qi}}& \left(29\right)\end{array}$

In step 74, a transformation from log-space back to probabilities is performed by raising the natural base to the negative of each element of the combined mapping results:
{tilde over (q)}=exp(−{tilde over (ŝ)} _q)  (30)

Normalize the resulting probability vector, step 76, includes dividing each element by the sum of the elements:

$\begin{array}{cc}q=\frac{\tilde{q}}{\sum \tilde{q}}& \left(31\right)\end{array}$

The preconfigured data involved in the mapping function includes anchor points 80, mapping matrices 82, and reference points 84. The mapping matrices and reference points are a result of the optimization. How to determine the anchor points will be described later.

All mappings are solved simultaneously, and it helps to define the mapping in a form that can be written in a single matrix equation:
N=└M₁ M₂ . . . M_nw s _q1 s _q2 . . . s _qnw┘,  (32)
u=[w ₁(s _p − s _p1)^T w ₂(s _p − s _p1)^T . . . w _nw(s _p − s _p1)^T w ^T]^T, and  (33)
{tilde over (ŝ)}_q=Nu.  (34)

Here, n_w is the length of the weight vector (and the number of anchor points). The matrix N specifies the mapping matrices 82 and the reference points 84. The normalized mapped result in log-space is:

$\begin{array}{cc}{\hat{s}}_q={\hat{\tilde{s}}}_q+1\log \left(1^T{e}^{-{\hat{\tilde{s}}}_q}\right)& \left(35\right)\\ =\mathrm{Nu}+1\log \left(1^T{e}^{-\mathrm{Nu}}\right).& \left(36\right)\end{array}$

The mapping matrix N is optimized according to the information theoretic cost. This cost is a nonlinear function which might have multiple local minima, so numerical optimization is used. In the optimization, better results are obtained if there is a good initial guess. For the initial guess, a mapping that minimizes the least squares cost function is preferred.

The process of determining the mappings is described in FIG. 12. It typically includes six steps: build the base database D₀, step 100, run simulations, step 102, determine anchor points, step 104, determine least squares reference points, step 106, compute initial mapping, step 108, and compute final mapping, step 110.

As known in the art, step 100 involves choosing scenarios, threat types, and trajectories, and populating the database with them. The database should encompass all the variations that are expected to be encountered, such as object shapes, materials, deployment times, and trajectory types. Classes are defined, such as: RV, tank, decoy, debris, etc. Each object in the database is marked with its true class. For instance, one trajectory in the database may have 10 objects, consisting of 1 RV, 1 tank, 3 decoys, and 5 debris.

In step 102, radar simulations are run on all trajectories and objects (or a representative set) from the database, which simulate the radars measuring features of the objects, and classifying them using the sensor databases. Each sensor classifies the objects it measures, according to its own database, which may or may not match the base database. The result of this step is a set of training points. Each training point describes one object, and contains the object's true base class, the probability vector that came from each sensor, and the feature vector that each sensor used.

In step 104, the use of multiple anchor points (mappings) amounts to something similar to what is known as the “kernel trick”. The kernel trick is a way to make a nonlinear estimator without having to solve nonlinear equations. It is done by first nonlinearly transforming the input data into a higher dimensional space, and then solving for a linear estimator that operates on the transformed input data.

The anchor points are found by running each sensor's classifier (using that sensor's database) on the feature vector that comes from the mean of each base class distribution, stacking them, and then converting to log-space.

$\begin{array}{cc}p\left({\stackrel{\_}{y}}_i\right)=\left[\begin{array}{c}{\mathrm{<figure-callout\; id="1"\; label="p"\; filenames="US07974814-20110705-D00000.png,US07974814-20110705-D00001.png"\; state="\{\{state\}\}">p</figure-callout>}}_1\left({\stackrel{\_}{y}}_i\right)\\ {\mathrm{<figure-callout\; id="2"\; label="p"\; filenames="US07974814-20110705-D00000.png,US07974814-20110705-D00002.png"\; state="\{\{state\}\}">p</figure-callout>}}_2\left({\stackrel{\_}{y}}_i\right)\\ ⋮\\ p_{\mathrm{ns}}\left({\stackrel{\_}{y}}_i\right)\end{array}\right]& \left(37\right)\\ {\stackrel{\_}{s}}_{\mathrm{pi}}=-\log \left(p\left({\stackrel{\_}{y}}_i\right)\right)& \left(38\right)\end{array}$

At step 106, a least squares reference point will be computed for each training point. These will be used to define the least squares cost function when computing the initial mapping. The least squares reference points are found by running the optimal classifier with the base database on the feature vector contained in the training point, and then converting to log-space.
s _q*=log(q(y))  (39)

The least squares cost for a single point can be written in terms of the parameter matrix N as follows:

$\begin{array}{cc}{\Psi }_{\mathrm{LS}}\left(N\right)=E_{f\left(y\right)}\left[\Delta s^T{A}^{T}A\Delta s\right]& \left(40\right)\\ =E_{f\left(y\right)}\left[{\left({\hat{\tilde{s}}}_q-s_{q^{*}}\right)}^{T}A\left({\hat{\tilde{s}}}_q-s_{q^{*}}\right)\right]& \left(41\right)\\ =E_{f\left(y\right)}\left[{\hat{\tilde{s}}}_q^{T}A{\hat{\tilde{s}}}_q-2s_{q^{*}}^{T}A{\hat{\tilde{s}}}_q+s_{q^{*}}^T{\mathrm{As}}_{q^{*}}\right]& \left(42\right)\\ =E_{f\left(y\right)}\left[u^T{N}^T\mathrm{ANu}-2s_{q^{*}}^T\mathrm{ANu}+s_{q^{*}}^T{\mathrm{As}}_{q^{*}}\right]& \left(43\right)\end{array}$
where:

ΨLS(N)	The single point least-squares cost of the {circumflex over (q)}(·) function
	determined by N.
N	The matrix containing all mappings and reference points,
	described in equation 31.
Δs	The difference between the mapped result in log-space
	(pre-normalization) and the corresponding least squares
	reference point.
sq*	The least squares reference point. Each training point has one
	of these associated with it.
	The mapped result in log-space before normalization.
A	The matrix that projects a vector of length nq (the number of
	base classes) onto the zero-sum plane. A = I − (1/nq)11T
Ef(y)[·]	The expected value of [·] over f(y).
f(y)	The pdf of the feature vector.
u	The input vector of weighed differences and weights, as
	described in equation 32.

The partial derivatives of the least squares cost are:

$\begin{array}{cc}\frac{\partial {\Psi }_{\mathrm{LS}}}{\partial N}=E_{f\left(y\right)}\left[\frac{\partial }{\partial N}{u}^T{N}^T\mathrm{ANu}\right]-2E_{f\left(y\right)}\left[\frac{\partial }{\partial N}{s}_{q^{*}}^T\mathrm{ANu}\right]& \left(44\right)\\ \frac{\partial }{\partial N}{u}^T{N}^T\mathrm{ANu}=2{\mathrm{ANuu}}^T& \left(45\right)\\ \frac{\partial }{\partial N}{s}_{q^{*}}^T\mathrm{ANu}={\mathrm{As}}_{q^{*}}{u}^T& \left(46\right)\end{array}$

Setting the partial derivatives to zero gives us an equation that will define N:

$\begin{array}{cc}\frac{\partial {\Psi }_{\mathrm{LS}}}{\partial N}=0\Rightarrow {\mathrm{ANE}}_{f\left(y\right)}\left[{\mathrm{uu}}^T\right]={\mathrm{AE}}_{f\left(y\right)}\left[s_{q^{*}}{u}^T\right]& \left(47\right)\end{array}$

There is generally more than one solution, for a few reasons: A is not full rank and a feature that is critical to discriminating between two classes may not have been measured. A more general version of the second reason is the placement of the sensor classes could be such that the p vector doesn't help to discriminate between some base classes.

At step 108, by using the pseudo-inverse, we can solve for the minimum-norm solution:
N=pinv(A)AE _f(y) [s _q* u ^T ]pinv(E _f(y) [uu ^T])  (48)

The expected values are taken using Monte Carlo integration over the set of training points. Then N is computed via the previous equation. N defines the mappings and reference points. This is the initial mapping solution.

In the least squares cost, we were able to separate the mapping and normalization steps, which allowed us to optimize a linear function of N. The information based cost function is not a linear function of N because it requires the estimate of the vector q to be normalized before evaluating the cost. The normalization involves division by a function of N, which makes things nonlinear. We use numerical optimization to try to minimize the cost function.

At step 110, the “fminunc” function from MATLAB's optimization toolbox is used to minimize the cost function. Functions are provided to the fminunc function, which compute the cost and its gradient and Hessian. By taking the averages of the single point cost, gradient, and Hessian over the training points, the total cost and its derivatives are computed. Having analytic expressions for the partial derivatives (as opposed to using finite differencing), leads to faster optimization and better results. The equations for the single point cost, gradient, and Hessian are as follows:

$\begin{array}{cc}\mathrm{Cost}\text{:}\psi =a_c^T\left[-\log \left(\hat{q}\right)\right]& \left(49\right)\\ \mathrm{Gradient}\text{:}\frac{\partial \psi }{\partial N}=\left(a_c-\left(1^T{a}_c\right)\hat{q}\right)u^T& \left(50\right)\\ \mathrm{Gradient}\left(\mathrm{vectorized}\right)\text{:}\frac{\partial \psi }{\partial N(:)}u\otimes \left(a_c-\left(1^T{a}_c\right)\hat{q}\right)& \left(51\right)\\ \mathrm{Hessian}\text{:}\frac{{\partial }^2\psi }{\partial N(:)\partial N(:)}=\left({\mathrm{uu}}^T\right)\otimes \left(\mathrm{diag}\left(\left(1^T{a}_c\right)\hat{q}\right)-\left(1^T{a}_c\right)\hat{q}{\hat{q}}^T\right)& \left(52\right)\end{array}$
where:

ψ	The single point cost of the {circumflex over (q)}(·) function.
{circumflex over (q)}	The value of the {circumflex over (q)}(·) function at one training point. This
	is the normalized probability vector of base classes.
ac	The cth column of the identity matrix. Alternatively, it could
	be defined as the cth column of some arbitrary matrix,
	whose elements can be chosen to represent costs of various
	types of misclassification.
N	The matrix containing all mappings and reference points,
	described in equation 31.
u	The input vector of weighed differences and weights, as
	described in equation 32.
N(:)	The vectorized parameter matrix. It is formed by stacking
	the columns of N, in order. The (:) notation is borrowed
	from MATLAB.
$\frac{\partial \psi }{\partial N}$	The partial derivatives of the single point cost with respect to the parameter matrix N. This is a matrix that is the same size as N.
$\frac{\partial \psi }{\partial N\left(\text{:}\right)}$	The partial derivatives of the single point cost with respect to the vectorzied N. This is the same size as vectorized N.
$\frac{{\partial }^2\psi }{\partial N\left(\text{:}\right)\partial N\left(\text{:}\right)}$	The Hessian (2nd partial derivatives) of the single point cost function with respect to vectorzied N.
	The Kronecker product operator.
diag(·)	The function which forms a diagonal matrix from a vector
	(as implemented in MATLAB).

The following three examples show the performance of this system. The results are based on simulated data. We used Gaussian classes in the base and sensor databases. To evaluate the performance of the algorithm of FIG. 5, the surprisals for 200 sample points were plotted and the mean calculated, which is the cost. As the number of points approaches infinity, the mean surprisal approaches the expected cross entropy between the optimal estimator and our estimator. The surprisals are normalized, meaning that the logarithms are taken with the base equal to the number of base classes. The sample points are random draws from the joint distribution of class and measurements, and are drawn separately from the training points.

When using normalized surprisals, a uniform distribution always results in a surprisal of 1. While it is possible for the cost to be any positive number, 1 is the upper bound on the cost for a useful algorithm. One can always meet the performance of this bound by admitting total ignorance (a uniform distribution). If the cost is greater than 1, then we could do better by just ignoring the data, and declaring a uniform distribution. We also have a lower bound, which we get by evaluating the performance of feature fusion. Feature fusion is optimal, but it uses the features, so in general it has more information than our algorithm. As a result, the cost from feature fusion is a lower bound that, depending on the scenario, may not be possible to reach.

Example 1

The first example is designed to show how much we can improve performance, relative to probability fusion. The setup is as follows: 2 features, 2 base classes, and 2 sensors wherein sensor 1 measures feature 1, and sensor 2 measures feature 2. There is no database mismatch and the sensors have the correct marginals. 10,000 training points were used. See FIG. 6.

As shown in FIG. 7A-7C the two base classes have equal covariances, but their means differ in both dimensions. The covariances are oriented at 45°, and have aspect ratios of 10:1, so the two features are very correlated. Because of the large correlation, and relatively small difference in the means, both sets of marginals have a lot of overlap. Because of the overlap, the results from simple probability fusion are very conservative, meaning that the estimated class probabilities are nearly uniformly distributed. If we had the features, we would get much better performance, because having both features makes it easier to see the separation of the classes. In this case however, it is possible to recover the features, because the probability vectors from the sensors are monotonic functions, which makes them invertible. Our algorithm, while not explicitly inverting to get the measurements, does essentially just as well as feature fusion in this case. If we were to increase the number of training points, the performance would be even closer to that of feature fusion.

Example 2

The second example is designed to show a more complicated case, with multiple sensors and database mismatch. The setup is as follows: 2 features, 5 base classes, and 2 sensors wherein sensor 1 measures feature 1, sensor 2 measures feature 1 and feature 2. The sensors have badly mismatched distributions. 10,000 training points were used. See FIG. 8.

As shown in FIGS. 9A-9C, the five base class distributions vary in spread and correlation. Sensor 1 measures feature 1, and has three classes. Sensor 2 measures both features, but has only two highly overlapping classes. There would be no clear way to do simple probability fusion. So, instead of using the probability fusion results for comparison, we'll use the results from the mapping derived from the least squares cost. In this case, mapping performs far better than declaring uniform probabilities (ignorance), substantially better than the least squares cost mapping, and very close to feature fusion. This shows that we can fuse probability vectors from multiple sensors in the presence of database mismatch, and recover most of the performance, relative to feature fusion.

Example 3

The third example is the same as the second case, except that now we only have sensor 2. The setup is as follows: 2 features, 5 base classes, and 1 sensor (measures both features). The sensor has badly mismatched distributions. 10,000 training points were used. See FIG. 10.

As shown in FIGS. 11A-11C, the sensor measures both features, and has the same distributions as sensor 2 in the previous example. This example is designed to test the algorithm when there is a lot of missing information. It is obvious that it is impossible to do as well as feature fusion, because the two sensor classes, will not give much insight into feature 1, since they only differ significantly along feature 2. A good algorithm will admit uncertainty when there is insufficient information. The worst thing you can do is to be overconfident, favoring some classes too strongly, while ruling out other classes. Overconfidence is much worse than ignorance. Overconfidence leads to performance that is worse than if you were to ignore the data and declare uniform probabilities. An overconfident estimator causes leakage—the declaration of a lethal target as non-lethal. Our estimator is able to avoid overconfidence while discriminating aggressively, as this case shows. The results are substantially better than declaring ignorance. We don't do as well as feature fusion, but it is obvious that that is impossible in this example.

The result is a feasible and useful method of and system for estimating conditional class probabilities from arbitrary data, which performs well in the presence of missing information. It is able to discriminate aggressively without being overconfident. It has the desirable quality of seeking the optimal or true conditional class probabilities without assuming a decision rule for how the probabilities will be used. This is ideal for operating within a distributed control, multi-sensor network. The method we've developed provides a good discrimination/fusion solution for the existing data interface problem.

Although specific features of the invention are shown in some drawings and not in others, this is for convenience only as each feature may be combined with any or all of the other features in accordance with the invention. The words “including”, “comprising”, “having”, and “with” as used herein are to be interpreted broadly and comprehensively and are not limited to any physical interconnection. Moreover, any embodiments disclosed in the subject application are not to be taken as the only possible embodiments. Other embodiments will occur to those skilled in the art and are within the following claims.

In addition, any amendment presented during the prosecution of the patent application for this patent is not a disclaimer of any claim element presented in the application as filed: those skilled in the art cannot reasonably be expected to draft a claim that would literally encompass all possible equivalents, many equivalents will be unforeseeable at the time of the amendment and are beyond a fair interpretation of what is to be surrendered (if anything), the rationale underlying the amendment may bear no more than a tangential relation to many equivalents, and/or there are many other reasons the applicant can not be expected to describe certain insubstantial substitutes for any claim element amended.

Claims (16)

1. A method of fusing the outputs of multiple sensors, the method comprising:

inputting to a fusion engine the output of each sensor including a sensor class probability vector based on each sensor's classification database; and

estimating, using a microprocessor, a base class probability vector based on the sensor class probabilities output by the sensors and a mapping function.

2. The method of claim 1 in which estimating includes converting the sensor class probability vector to log-space.

3. The method of claim 2 in which the mapping function includes anchor points and estimating includes finding the differences between the log-space probability vectors and the anchor points.

4. The method of claim 3 in which the mapping function includes mapping matrices and estimating includes mapping each difference using the mapping matrices.

5. The method of claim 4 in which the mapping function includes reference points and estimating includes adding reference points to the mapped differences.

6. The method of claim 5 in which estimating includes weighting and summing the mapped differences.

7. The method of claim 6 in which estimating includes converting the weighted and summed mapped differences back to probability space to produce the probability vector.

8. The method of claim 7 in which the estimating includes normalizing the probability vector.

9. A system for fusing the output of multiple sensors, the system comprising:

multiple sensors each including a classification database and each outputting a sensor class probability vector based on its classification database;

a fusion engine responsive to the output of each sensor; and

a mapping function;

the fusion engine configured to estimate a base class probability vector based on the sensor outputs and the base database classes.

10. The system of claim 9 in which the fusion engine is configured to convert the sensor class probability vectors to log-space.

11. The system of claim 10 in which the mapping function includes anchor points and the fusion engine is configured to find the differences between the log-space probability vectors and the anchor points.

12. The system of claim 11 in which the mapping function includes mapping matrices and the fusion engine is configured to map each difference using the mapping matrices.

13. The system of claim 12 in which the mapping function includes reference points and the fusion engine is configured to add reference points to the mapped differences.

14. The system of claim 13 in which the fusion engine is configured to weight and sum the mapped differences.

15. The system of claim 14 in which the fusion engine is configured to convert the weighted and summed mapped differences back to probability space to produce the probability vector.

16. The system of claim 15 in which the fusion engine is configured to normalize the probability vector.

Images