Abstract:
In one aspect, a method to assign observations includes receiving first observations of a first sensor system, receiving second observations of a second sensor system and assigning a set of pairs of the first and second observations predicted to correspond to the same physical position. The assigning includes using a likelihood function that specifies a likelihood for each assigned pair. The likelihood is dependent on the assignment of any other assigned pairs in the set of assigned pairs. The assigning also includes determining the set of assigned pairs for the first and second observations based on the likelihood function. The likelihood function uses a gate value determined from estimating a true volume using nearest neighbor distances determined from the first and second observations.

Description:
BACKGROUND 
     In multi-sensor tracking systems a process of associating sets of observations from at least two sensor systems is problematic in the presence of bias, random errors, false observations, and missed observations. For example, one tracking system may share data with the other system and transmit its current set of its observations to the other sensor system. The second sensor system determines which data points received from the first sensor system correspond to the airplanes it is also tracking. In practice, the process is difficult because each sensor system has an associated error, making it problematic to assign a data point from one sensor system to the other sensor system. Examples of errors may include misalignment between the two sensor systems, different levels of tolerances, and/or one sensor system may observe certain types of airplanes while the other sensor system does not observe the same types of aircraft. Therefore, based on each particular sensor system having errors due to bias, random errors, false observations, and missed observations, it is difficult to use a set of data received from the first sensor system and directly overlay it with a set of data from the second sensor system. 
     SUMMARY 
     In one aspect, a method to assign observations includes receiving first observations of a first sensor system, receiving second observations of a second sensor system and assigning a set of pairs of the first and second observations predicted to correspond to the same physical position. The assigning includes using a likelihood function that specifies a likelihood for each assigned pair and determining the set of assigned pairs for the first and second observations based on the likelihood function. The likelihood function uses a gate value determined from estimating a true volume using nearest neighbor distances determined from the first and second observations. 
     In another aspect, an article includes a machine-readable medium that stores executable instructions to assign observations. The instructions cause a machine to receive first observations of a first sensor system, receive second observations of a second sensor system and assign a set of pairs of the first and second observations predicted to correspond to the same physical position. The instructions causing a machine to assign includes instructions causing a machine to use a likelihood function that specifies a likelihood for each assigned pair and determine the set of assigned pairs for the first and second observations based on the likelihood function. The likelihood function uses a gate value determined from estimating a true volume using nearest neighbor distances determined from the first and second observations. 
     In a further aspect, an apparatus includes circuitry to receive first observations of a first sensor system, receive second observations of a second sensor system and assign a set of pairs of the first and second observations predicted to correspond to the same physical position. The circuitry to assign includes circuitry to use a likelihood function that specifies a likelihood for each assigned pair and determine the set of assigned pairs for the first and second observations based on the likelihood function. The likelihood function uses a gate value determined from estimating a true volume using nearest neighbor distances determined from the first and second observations. 
    
    
     
       DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a diagram of a multi-sensor system. 
         FIG. 2  is a diagram of assigning observations using the multi-sensor system of  FIG. 1 . 
         FIG. 3  is a flow chart of a process to associate observations. 
         FIG. 4  is a block diagram of an example of a computer on which the process of  FIG. 3  may be implemented. 
     
    
    
     DETAILED DESCRIPTION 
     Referring to  FIG. 1 , a multi-sensor system  10  includes a sensor system  12  and a sensor system  14  each of which is configured to observe the position and velocity of objects (e.g., airplanes  16 ). The multi-sensor system  10  also includes a multi-sensor processing system  26 . Observations may occur through sensing, prediction, or a combination of sensing and prediction. In one example, the sensor system  12  and the sensor system  14  are radar systems. In other examples, one or more of the sensor systems  12 ,  14  may be an electro-optic sensor system, an infrared sensor system and so forth. For simplicity, not all airplanes  16  that are used herein are depicted in  FIG. 1 . 
     Associated with, or included within, the sensor system  12  is a representation  18  of positions of airplanes  16  that are observed by sensor system  12 . Sensor system  14  is associated with a similar representation  20 . Representations  18  and  20  may differ for a variety of reasons. For example, there may be a misalignment between the sensor systems  12  and  14 , errors between the sensor systems  12  and  14 , or one sensor system may not observe all of airplanes  16  that the other sensor system observes. The errors for either sensor system  12  or  14  may be due to bias, random errors, false observations, missed observations, or other sources. Representation  18  includes observations  22  representing positions of the corresponding airplanes  16  observed by the sensor system  12 . Representation  20  includes observations  24  representing positions of the corresponding airplanes  16  observed by the sensor system  14 . The physical position of any airplane  16  is an example of a physical parameter, observation of which is represented by observations  22  and  24 . 
     In one example, the sensor system  12  may provide the observations  22  to the sensor system  14 . A problem may arise with the sharing of observations when correlating which the observations  24  correspond to which the observations  22 . This may be particularly difficult in the situation where the sensor system  12  includes the observations  22  corresponding to airplanes  16  that the sensor system  14  does not also observe. Persistent bias within or between sensor systems  12  and  14  also makes this problem particularly difficult. 
     The observations  22  are assigned to observations  24  by calculating a likelihood function indicative of differences between observations  22  and observations values  24  using the multi-sensor processing system  26 . 
     Prior attempts to determine the likelihood function relied on Global Nearest Neighbor (GNN) techniques, but the GNN techniques do not take in to account the random and correlated bias components. On the other hand, a Global Nearest Pattern (GNP) technique determines a likelihood function that does account for the random and correlated bias components. For example, one such method to determine the likelihood function using a GNP technique is described in U.S. Pat. No. 7,092,924 which is assigned to the same assignee as this patent application and is incorporated herein in its entirety. An observation assignment using GNP accounts for persistent errors and the possibility that observations to be assigned may not constitute a perfect subset of the observation set to which they are being assigned. 
     Referring to  FIG. 2 , a data set  28  includes observations  22 , observations  24 , and assignments  32  corresponding to associations made between observations  22  and observations  24  predicted to correspond to the same physical parameter. In this embodiment, the assignments in the data set  28  account for both random and correlated bias components. The assignments  32  of data set  28  are made based on errors having both random and correlated bias components, generating a common pattern, and assigning observations  22  to observations  24  accordingly. In this example, a persistent offset exists between observations  22  and observations  24 , as indicated in  FIG. 2 . 
     The likelihood function of the GNP assumes that there are N objects (airplanes  16  in this example) in space being observed by sensor system A (e.g., sensor system  12  in the example of  FIG. 1 ) and sensor system B (e.g., sensor system  14  in the example of  FIG. 1 ), and each sensor system observes a potentially different subset of the objects. Sensor system A determines observations (observations  22  in the example of  FIG. 1 ) on m of these, sensor system B determines observations (observations  24  in the example of  FIG. 1 ) on n of these subject to:
 
m≦n≦N
 
False observations in sensor system A or sensor system B correspond to observations of a non-existent object. The observations are transformed to a D-dimensional common reference frame. The likelihood function in GNP is:
 
                     J   a     =       -     (           X   _     ⁡     (     CM   Bias     )         -   1       ⁢       X   _     T       )       -       ∑     i   =   1     m     ⁢       {             δ   ⁢           ⁢         X   i     ⁡     (     S   i     )         -   1       ⁢   δ   ⁢           ⁢     X   i   T       +     L   ⁢           ⁢     N   ⁡     (          S   i          )         -     L   ⁢           ⁢     N   ⁡     (     C   min     )                     G   -     L   ⁢           ⁢   N   ⁢           ⁢     (     C   min     )               }     ⁢           ⁢   if   ⁢           ⁢     {             a   ⁡     (   i   )       ≠   0                 a   ⁡     (   i   )       =   0           }                   (   1   )               
where α(i) is an association vector (i=1 to m) and is equal to an index of sensor system B object with which ith sensor system A object is associated (i.e., 0 for non-association). S i  is a residual error covariance equal to CM A (i)+CM B (α(i)), where CM A (i) is a D×D error covariance matrix for sensor system A and CM B (α(i)) is a D×D error covariance matrix for sensor system B.  X  is an estimate of the relative bias and
 
               X   _     =     [       ∑     i   =   1     m     ⁢       (         SV   A     ⁡     (   i   )       -         SV   B     ⁡     (     a   ⁡     (   i   )       )       ·       (     S   i     )       -   1           ]     ·       [         (     CM   BIAS     )       -   1       +       ∑     i   =   1     m     ⁢       (     S   i     )       -   1           ]       -   1                   
where each sum over those i for which a(i)≠0. SV A (i) is a D-dimensional state vector for sensor system A and SV B (α(i)) is a D-dimensional state vector for the sensor system B. δX i  is a state vector difference where δX i =SV A (i)−SV B (α(i))−  X . CM bias  is a D×D intersensor bias covariance matrix, G is a gate value. C min  is a minimum determinant of a residual error matrix where C min =MIN{1,MIN(|S i |) i } is a normalization constant.
 
     In prior art approaches, the gate value, G, (also known as a cost of non-association) is determined using: 
                   G   =     2   ⁢           ⁢   L   ⁢           ⁢     N   ⁡     [         β   T     ⁢     P   AB             (     2   ⁢   π     )       D   2       ⁢     β   NA     ⁢     β   NB         ]                 (   2   )               
where D is the dimensionality of the data space, β T  is a true object density, P AB =P A P B  and is a true probability that any given object is observed by both sensor system A and sensor system B, B NA =P B (1−P A ) β T +β FA  and is a true density of sensor system A observations having no corresponding sensor system B observations, B NB =P A (1−P B )β T +β B  and is a true density of sensor system B observations having no corresponding sensor system A observations, P A  is a true probability that any given object is observed by the sensor system A, P B  is a true probability that any given object is observed by the sensor system B, β FA  is a true false observation density of sensor system A and β FB  is a true false observation density of sensor system B.
 
     However, the equation for the gate value G in Equation (2) cannot be used in a practical application since most of the parameters used to determine the gate value are truth parameters which are unknown. Therefore, as described further herein, the prior art gate value is discarded in favor of a more useful gate value. In order to determine a more practical gate value, the following assumptions and analysis is made. 
     β FA  and β FB  are set to zero, on the assumption that no false tracks are likely, and P A  and P B  are estimated, based on a priori information, to be P′ A  and P′ B  respectfully so that 
     
       
         
           
             G 
             = 
             
               2 
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   LN 
                   [ 
                   
                     1 
                     
                       
                         
                           
                             
                               [ 
                               
                                 2 
                                 ⁢ 
                                 π 
                               
                               ] 
                             
                             
                               D 
                               / 
                               2 
                             
                           
                           ⁡ 
                           
                             [ 
                             
                               1 
                               - 
                               
                                 P 
                                 A 
                                 ′ 
                               
                             
                             ] 
                           
                         
                         ⁡ 
                         
                           [ 
                           
                             1 
                             - 
                             
                               P 
                               B 
                               ′ 
                             
                           
                           ] 
                         
                       
                       ⁢ 
                       
                         β 
                         T 
                       
                     
                   
                   ] 
                 
                 . 
               
             
           
         
       
     
     β T  is substituted with N T /V T  where N T  is the total number of truth objects and V T  is the true volume in which the truth objects are randomly distributed. N T  is approximated by N B /P′ B  where N B  is the number of objects observed by sensor system B so that 
     
       
         
           
             G 
             = 
             
               2 
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   LN 
                   [ 
                   
                     
                       
                         V 
                         T 
                       
                       ⁢ 
                       
                         P 
                         B 
                         ′ 
                       
                     
                     
                       
                         
                           
                             
                               [ 
                               
                                 2 
                                 ⁢ 
                                 π 
                               
                               ] 
                             
                             
                               D 
                               / 
                               2 
                             
                           
                           ⁡ 
                           
                             [ 
                             
                               1 
                               - 
                               
                                 P 
                                 A 
                                 ′ 
                               
                             
                             ] 
                           
                         
                         ⁡ 
                         
                           [ 
                           
                             1 
                             - 
                             
                               P 
                               B 
                               ′ 
                             
                           
                           ] 
                         
                       
                       ⁢ 
                       
                         N 
                         B 
                       
                     
                   
                   ] 
                 
                 . 
               
             
           
         
       
     
     V T  is the only unknown truth parameter, and is taken to be the volume over which the sensor B observations are distributed (V B ). V B  is estimated using the average, measured nearest neighbor distance of each observation of sensor B. Since the nearest neighbor distance does not seem to be calculable for mixed units (e.g., position and velocity) the total volume is represented as a product of position volume and velocity volume. Therefore, V T  is K V V B     —     pos V B     —     vel  where K V  is a proportionality constant, V B     —     pos  is the position volume and V B     —     vel  is the velocity volume (i.e., the volume in velocity space over which the truth objects are randomly distributed) so that 
     
       
         
           
             G 
             = 
             
               2 
               ⁢ 
               
                 
                   LN 
                   [ 
                   
                     
                       
                         K 
                         V 
                       
                       ⁢ 
                       
                         P 
                         B 
                         ′ 
                       
                       ⁢ 
                       
                         V 
                         B_pos 
                       
                       ⁢ 
                       
                         V 
                         B_vel 
                       
                     
                     
                       
                         
                           
                             
                               [ 
                               
                                 2 
                                 ⁢ 
                                 π 
                               
                               ] 
                             
                             
                               D 
                               / 
                               2 
                             
                           
                           ⁡ 
                           
                             [ 
                             
                               1 
                               - 
                               
                                 P 
                                 A 
                                 ′ 
                               
                             
                             ] 
                           
                         
                         ⁡ 
                         
                           [ 
                           
                             1 
                             - 
                             
                               P 
                               B 
                               ′ 
                             
                           
                           ] 
                         
                       
                       ⁢ 
                       
                         N 
                         B 
                       
                     
                   
                   ] 
                 
                 . 
               
             
           
         
       
     
     By an analysis of nearest neighbor distance in multi-dimensional space it has been determined that the position and velocity volumes can be determined according to 
                 V   B_pos     =       {               N   B     ⁡     [       d   B_pos       K   ⁡     (     D   pos     )         ]           D   pos     /   2               1         }     ⁢           ⁢   for   ⁢           ⁢     {             D   pos     &gt;   0                 D   pos     =   0           }         ,     
     ⁢   and                   V   B_vel     =       {               N   B     ⁡     [       d   B_vel       K   ⁡     (     D   vel     )         ]           D   vel     /   2               1         }     ⁢           ⁢   for   ⁢           ⁢     {             D   vel     &gt;   0                 D   vel     =   0           }         ,         
where K(D) is a constant equal to Γ(1+1/D)Γ 1/D (D/2+1)/√{square root over (π)} (where Γ( ) is the standard Gamma Function), and D pos  and D vel  are the number of position space and velocity space dimensions respectively. The average measured position space nearest neighbor distance, the average measured velocity space nearest neighbor distance for sensor B are calculated according to
 
                 d   B_pos     =         (     N   B     )       -   1       ⁢       ∑     i   =   1       N   B       ⁢           ⁢         d   ~     B_pos     ⁡     (   i   )             ,     
     ⁢   and                   d   B_vel     =         (     N   B     )       -   1       ⁢       ∑     i   =   1       N   B       ⁢           ⁢         d   ~     B_vel     ⁢     (   i   )             ,         
respectively, where d B     —     pos (i) is the measured nearest neighbor distance of ith sensor system B object in position space and equal to d B     —     pos (i)=Min{MAG[X B     —     pos (i)−X B     —     pos(i)]}   i=1:n , and X B     —     pos (i) is the sensor B measured position of the ith object. d B     —     vel (i) is a measured nearest neighbor distance of ith sensor system B object in velocity space and equal to d B     —     vel (i)=Min {MAG[X B     —     vel (i)−X B     —     vel (i)]} i=1:n  and X B     —     vel (i) is the sensor B measured velocity of the ith object.
 
     K V  is set equal to 1 based on an analysis of nearest neighbor distance and confirmed by simulation results. Thus, the gate value becomes 
                   G   =     2   ⁢           ⁢     LN   [         P   B   ′     ·     V   B_pos     ·     V   B_vel             [     2   ⁢           ⁢   π     ]       D   /   2       ·     [     1   -     P   A   ′       ]     ·     [     1   -     P   B   ′       ]     ·     N   B         ]               (   3   )               
where D=D pos +D vel . Note that the number of position space dimensions (D pos ) and the number of velocity space dimensions (D vel ) must either be equal to each other, or one must be zero.
 
     Thus, using equation (3), the cost function in equation (1) is based on known parameters. In one example, P′ A  and P′ B  may range from 50% to 100% with little affect on the results of the cost function. Applicants have determined that P′ A  and P′ B  of 70% is preferred. 
     In one example, the dimensionality parameter, D. is 6 for two radar system where three dimensions are position dimensions in x, y and z space and three dimensions are velocity dimensions in x, y and z space. In another example, when one of the sensor systems is an electro-optic system, D is equal to 2 for angle/angle dimensions (azimuth and elevation). 
     Referring to  FIG. 3 , in one example, a process to associate observations from multi-sensor systems is a process  100 . The multi-sensor processing system  26  receives observations from the sensor systems  12 ,  14  ( 102 ). Based on the observations received, the multi-sensor processing system  26  determines parameters ( 104 ). For example, the multi-sensor processing system  26  determines state vectors, SV A (i) and SV B (α(i)), and error covariance matrices, CM A (α(i)) and CM B (α(i). The multi-sensor processing system  26  determines intersensor bias covariance matrix, CM bias  ( 106 ). The multi-sensor processing system  26  determines the gate value ( 108 ). For example, equation (3) is used to determine the gate value. The multi-sensor processing system  26  determines associations ( 108 ). For example, the multi-sensor processing system  26  uses the parameters determined in processing blocks  104 ,  106  and  108  in the cost function in equation (1) to determine an association vector. 
     Referring to  FIG. 4 , the multi-sensor processing system  26  may be configured as a multi-sensor processing system  26 ′, for example. The multi-sensor processing system  26 ′ includes a processor  202 , a volatile memory  204  and a non-volatile memory  206  (e.g., hard disk). The non-volatile memory  206  stores computer instructions  214 , an operating system  210  and data  212 . In one example, the computer instructions  214  are executed by the processor  202  out of volatile memory  204  to perform the process  100 . 
     Process  100  is not limited to use with the hardware and software of  FIG. 4 ; it may find applicability in any computing or processing environment and with any type of machine or set of machines that is capable of running a computer program. Process  100  may be implemented in hardware, software, or a combination of the two. Process  100  may be implemented in computer programs executed on programmable computers/machines that each includes a processor, a storage medium or other article of manufacture that is readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device to perform process  100  and to generate output information. 
     The system may be implemented, at least in part, via a computer program product, (e.g., in a machine-readable storage device), for execution by, or to control the operation of, data processing apparatus (e.g., a programmable processor, a computer, or multiple computers)). Each such program may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the programs may be implemented in assembly or machine language. The language may be a compiled or an interpreted language and it may be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may be deployed to be executed on one computer or on multiple computers at one site or distributed across multiple sites and interconnected by a communication network. A computer program may be stored on a storage medium or device (e.g., CD-ROM, hard disk, or magnetic diskette) that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer to perform process  100 . Process  100  may also be implemented as a machine-readable storage medium, configured with a computer program, where upon execution, instructions in the computer program cause the computer to operate in accordance with process  100 . 
     The processes described herein are not limited to the specific embodiments described. For example, in the problem of associating sets of observations from multi-sensor systems in the presence of inter-sensor observation bias, random observations errors, false observations and missed observations, Global Nearest Pattern (GNP) association provides a preferred solution both for the association of one sensor&#39;s observations to those of the other (or to non-assignment), and for the unknown bias between the two sensors. Global Nearest Neighbor (GNN) association assumes no inter-sensor observation bias, and solves for an association of one sensor&#39;s observations to those of the other (or to non-assignment). In the absence of inter-sensor observation bias, GNN yields the same preferred association result as the GNP result. Thus, the gate value of equation 3 may be used by both GNN and GNP techniques. 
     In another example, the process  100  is not limited to the specific processing order of  FIG. 3 , respectively. Rather, any of the processing blocks of  FIG. 3  may be re-ordered, combined or removed, performed in parallel or in serial, as necessary, to achieve the results set forth above. 
     The processing blocks in  FIG. 3  associated with implementing the system may be performed by one or more programmable processors executing one or more computer programs to perform the functions of the system. All or part of the system may be implemented as, special purpose logic circuitry (e.g., an FPGA (field programmable gate array) and/or an ASIC (application-specific integrated circuit)). 
     Elements of different embodiments described herein may be combined to form other embodiments not specifically set forth above. Other embodiments not specifically described herein are also within the scope of the following claims.