Random set-based cluster tracking

• US 7,193,557 B1
• Filed: 04/29/2004
• Issued: 03/20/2007
• Est. Priority Date: 04/29/2003
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Casaletto, Thomas R, Kovacich, Michael A
• Primary Examiner(s): Sotomayor; John B.
• Application Number:
  US10/835,968
• Time in Patent Office: 1,055 Days
• Field of Search: 342 89- 99, 342/107, 342/108, 342/115, 342/189, 342/194, 342/195
• US Class Current: 342/89
• CPC Class Codes: G01S 13/726 Multiple target tracking
• CPC Class Codes: G01S 3/7864 T.V. type tracking systems
• CPC Class Codes: G01S 5/0018 Transmission from mobile station to base station
• CPC Class Codes: G01S 5/02521 using a radio-map

Abstract

Tracking objects by receiving a dataframe from a detection sensor device, the dataframe containing a timestamp and data corresponding to each detected object, generating new observation nodes for each detected object, propagating group track state parameters to obtain posterior observable positions and projecting them onto the received dataframe, generating gates for the posterior observable positions and projecting them onto the received dataframe, determining feasible track node and feasible observation node assignments based on the proximity of the new observation nodes to the gates, updating track node state parameters and corresponding scores, performing a multi-frame resolution algorithm to resolve group track nodes into subtrack nodes, determining a set of feasible composite assignments for composite sets of track nodes and observation nodes, updating track node state parameters and corresponding scores, and determining a selected set of joint assignments based on the feasible composite assignments and their respective scores.

Claims

1. A system for performing random-set based cluster tracking of observable objects, the system comprising:

a plurality of detection sensor devices, each of which generates a series of dataframes, each dataframe containing a timestamp and containing location data and amplitude data corresponding to each detected observable object in the dataframe;

a tracking processor unit which receives dataframes from one or more of the detection sensor devices, the tracking processor unit including a memory and at least one processing unit, the memory storing scene nodes, track nodes and observation nodes, and also storing program steps for execution by the processing unit, the program steps including;

an observation node generation step of generating a new observation node for each observable object location data contained in a received dataframe;

a propagating step of propagating forward, to a time value of the timestamp, a set of state parameters of a group track node to obtain a set of posterior observable positions, a plurality of previously-generated track nodes being assigned to the group track node;

a projecting step of projecting the posterior observable positions onto a field of regard of the received dataframe;

a gate generation step of generating a gate for each posterior observable position and projecting each gate over each respective posterior observable position on the received dataframe;

a feasible track assignment step of determining a set of feasible track assignments for the dataframe which correlate each one of a plurality of new track nodes to at least one of the new observation nodes based on the proximity of each new observation node to at least one of the gates over the posterior observable positions, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible track assignments, and generating a probability score for the feasible track assignments;

a feasible observation assignment step of determining a set of feasible observation assignments for the dataframe which correlate each new observation node to at least one new track node based on the proximity of each new observation node to at least one of the gates over the posterior observable positions, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible observation assignments, and generating a probability score for the feasible observation assignments;

a feasible composite assignment step of determining a set of feasible composite assignments for a composite set of track nodes and observation nodes which correspond to at least the received dataframe, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible composite assignments, and generating a probability score for each feasible composite assignment based on the probability scores for the feasible track assignments and the feasible observation assignments corresponding to the track nodes and observation nodes in the composite set; and

a joint assignment determination step of determining a set of joint assignments based on the set of feasible composite assignments and their respective probability scores by using a loss minimization algorithm and a set of constraints, the selected set of joint assignments including at least one of the feasible composite assignments.

2. A system according to claim 1, further comprising:

a multi-frame resolution step of analyzing all group track nodes and resolving one or more of the group track nodes into one or more new track nodes, based on a set of group track parameters for each group track node, the parameters including a group track history, a group track probability score and a number of observation nodes assigned to the group track node.

3. A system according to claim 1, further comprising:

a pruning step of pruning all track nodes by deleting selected track nodes, the selection being based on whether the probability score of each track node is below a predetermined marginal acore and on the application of a loss minimization algorithm to each track node.

4. A system according to claim 1, wherein, in the feasibility track assignment step, the feasibility observation assignment step and the feasibility composite assignment step, the update of the state parameters for all track nodes assigned to the group track node, and the generation of a probability score, include:

a track node update step of updating the state parameters of each track node assigned to the group track node;

a group track extent update step of determining an updated value of an extent for the group track node based on the location data corresponding to each observable object in the received dataframe and on a sensor resolution in the received dataframe;

a group track centroid update step of determining an updated value of a centroid for the group track node based on the location data corresponding to each observable object in the received dataframe and on a sensor resolution in the received dataframe;

a group track extend scoring step of determining an extent probabilty score for the group track node based on the group track extent; and

a group track centroid scoring step of determining a centroid probability score for the group track node based on the group track centroid.

5. A system according to claim 4, wherein the group track extent update step further includes:

a group location extent update step of determining an updated value of a location extent for the group track node based on the location data corresponding to each observable object in the received dataframe;

a group amplitude extent update step of determining an updated value of an amplitude extent for the group track node based on the amplitude data corresponding to each observable object in the received dataframe; and

a group track extent calculation step of calculating the group track extent based on the group location extent and the groupa mplitude extent, using separate weight factors for the group location extent and the group amplitude extent, respectively.

6. A system according to claim 5, wherein the group track extent scoring step further includes:

a group track location extent scoring step of determining a group location extent probability score for the group track node based on the group track location extent;

a group track amplitude extent scoring step of determining a group amplitude extent probability score for the group track node based on the group track amplitude extent; and

a group extent score calculation step of calculating the group extent probability score based on the group location extent probability score and the group amplitude extent probability, using separate weight factors for the group location extent probability score and the group amplitude extent probability score, respectively.

7. A system according to claim 4, wherein the group track centroid update step further includes:

a group location centroid update step of determining an updated value of a location centroid for the group track node based on the location data corresponding to each observable object in the received dataframe;

a group amplitude centroid update step of determining an updated value of an amplitude centroid for the group track node based on the amplitude data corresponding to each observable object in the received dataframe; and

a group track centroid calculation step of calculating the group track centroid based on the group location centroid and the group amplitude centroid, using separate weight factors for the group location centroid and the group amplitude centroid, respectively.

8. A system according to claim 7, wherein the group track centroid scoring step further includes:

a group track location centroid scoring step of determining a group location centroid probability score for the group track node based on the group track location centroid;

a group track amplitude centroid scoring step of determining a group amplitude centroid probability score for the group track node based on the group track amplitude centroid; and

a group centroid score calculation step of calculating the group centroid probability score based on the group location centroid probability score and the group amplitude centroid probability, using separate weight factors for the group location centroid probability score and the group amplitude centroid probability score, respectively.

9. A system according to claim 1, wherein the joint assignment determination step of determining a set of joint assignments further includes:

a feasible joint assignment determination step of determining a set of feasible joint assignments based on the set of feasible composite assignments and on the probability scores for the feasible composite assignments, the determination based on a posterior feasibility loss minimization algorithm subject to a set of feasibility resource constraints;

a joint assignment selection step of selecting a set of joint assignments from the set of feasible joint assignments based on a selection less minimization algorithm subject to a set of selection resource constraints; and

an elimination step of eliminating each feasible joint assignment that was not selected in the joint assignment selection step.

10. A system according to claim 1, wherein the plurality of detection sensor devices are respectively mounted on a plurality of platforms.

11. A system according to claim 10, wherein the plurality of platforms are a plurality of satellites, each of which is positioned in an earth orbit.

12. A system according to claim 10, wherein at least two detection sensors are included in each detection sensor device.

13. A system according to claim 12, wherein the at least two detection sensors include an infrared (IR) detection sensor and a radio frequency (RF) detection sensor.

14. A system according to claim 1, wherein, in the projecting step, the posterior observable positions are transformed from an earth-based coordinate system to a sensor-based coordinate system that corresponds to the detection sensor which generated the received dataframe.

15. A system according to claim 1, wherein, in the gate generation step, the generation of each gate is based on a covariance value of the respective posterior observable positions.

16. A system according to claim 1, wherein the tracking processor unit comprises a plurality of processors.

17. A system according to claim 1, wherein the plurality of processors are distributed over a plurality of platforms.

18. A method for performing random-set based cluster tracking of observable objects in a system having a plurality of detection sensor devices, each of which generates a series of dataframes, and a tracking processor unit which receives dataframes from one or more of the detection sensor devices, the method comprising:

a receiving step of receiving a dataframe from one of the detection sensor devices, the dataframe including a timestamp, and location data and amplitude data corresponding to each detected observable object in the dataframe;

an observation node generation step of generating a new observation node for each observable object location data contained in the received dataframe;

a propagating step of propagating forward, to a time value of the timestamp, a set of state parameters of a group track node to obtain a set of posterior observable positions, a plurality of previously-generated track nodes being assigned to the group track node;

a projecting step of projecting the posterior observable positions onto a field of regard of the received dataframe;

a gate generation step of generating a gate for each posterior observable position and projecting each gate over each respective posterior observable position on the received dataframe;

a feasible track assignment step of determining a set of feasible track assignments for the dataframe which correlate each one of a plurality of new track nodes to at least one of the new observation nodes based on the proximity of each new observation node to at least one of the gates over the posterior observable positions, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible track assignments, and generating a probability score for the feasible track assignments;

a feasible observation assignment step of determining a set of feasible observaiton assignments for the dataframe which correlate each new observation node to at least one new track node based on the proximity of each new observation node to at least one of the gates over the posterior observable positions, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible observation assignments, and generating a probability score for the feasible observation assignments;

a feasible composite assignment step of determining a set of feasible composite assignments for a composite set of track nodes and observation nodes which correspond to at least the received dataframe, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible composite assignments, and generating a probability score for each feasible composite assignment based on the probability scores for the feasible track assignments and the feasible observation assignments corresponding to the track nodes and observation nodes in the composite set; and

a joint assignment determination step of determining a set of joint assignments based on the set of feasible composite assignments and their respective probability scores by using a loss minimization algorithm and a set of constraints, the selected set of joint assignments including at least one of the feasible composite assignments.

19. A method according to claim 18, further comprising:

a multi-frame resolution step of analyzing all group track nodes and resolving one or more of the group track nodes into one or more new track nodes, based on a set of group track parameters for each group track node, the parameters including a group track history, a group track probability score and a number of observation nodes assigned to the group track node.

20. A method according to claim 18, further comprising:

a pruning step of pruning all track nodes by deleting selected track nodes, the selection being based on whether the probability score of each track node is below a predetermined marginal score and on the application of a minimum loss algorithm to each track node.

21. A method according to claim 18, wherein, in the feasibility track assignment step, the feasible observation assignment step and the feasibility composite assignment step, the update of the state parameters for all track nodes assigned to the group track node, and the generation of a probability score, include:

a track node update step of updating the state parameters of each track node assigned to the group track node;

a group track extent update step of determining an updated value of an extent for the group track node based on the location data corresponding to each observable object in the received dataframe and on a sensor resolution in the received dataframe;

a group track centroid update step of determining an updated value of a centroid for the group track node based on the location data corresponding to each observable object in the received dataframe and on a sensor resolution in the received dataframe;

a group track extent scoring step of determining an extent probability score for the group track node based on the group track extent; and

a group track centroid scoring step of determining a centroid probability score for the group track node based on the group track centroid.

22. A method according to claim 21, wherein the group track extent update step further includes:

a group location extent update step of determining an updated value of a location extent for the group track node based on the location data corresponding to each observable object in the received dataframe;

a group amplitude extent update step of determining an updated value of an amplitude extent for the group track node based on the amplitude data corresponding to each observable object in the received dataframe; and

a group track extent calculation step of calculating the group track extent based on the group location extent and the group amplitude extent, using separate weight factors for the group location extent and the group amplitude extent, respectively.

23. A method according to claim 22, wherein the group track extent scoring step further includes:

a group track location extent scoring step of determining a group location extent probability score for the group track node based on the group track location extent;

a group track amplitude extent scoring step of determining a group amplitude extent probability score for the group track node based on the group track amplitude extent; and

a group extent score calculation step of calculating the group extent probability score based on the group location extent probability score and the group amplitude extent probability, using separate weight factors for the group location extent probability score and the group amplitude extent probability score, respectively.

24. A method according to claim 21, wherein the group track centroid update step further includes:

a group location centroid update step of determining an updated value of a location centroid for the group track node based on the location data corresponding to each observable object in the received dataframe;

a group amplitude centroid update step of determining an updated value of an amplitude centroid for the group track node based on the amplitude data corresponding to each observable object in the received dataframe; and

a group track centroid calculation step of calculating the group track centroid based on the group location centroid and the group amplitude centroid, using separate weight factors for the group location centroid and the group amplitude centroid, respectively.

25. A method according to claim 24, wherein the group track centroid scoring step further includes:

a group track location centroid scoring step of determining a group location centroid probability score for the group track node based on the group track location centroid;

a group track amplitude centroid scoring step of determining a group amplitude centroid probability score for the group track node based on the group track amplitude centroid; and

a group centroid score calculation step of calculating the group centroid probability score based on the group location centroid probability score and the group amplitude centroid probability, using separate weight factors for the group location centroid probability score and the group amplitude centroid probability score, respectively.

26. A method according to claim 18, wherein the joint assignment determination step of determining a set of joint assignments further includes:

a feasible joint assignment determination step of determining a set of feasible joint assignments based on the set of feasible composite assignments and on the probability scores for the feasible composite assignments, the determination based on a posterior feasibility loss minimization algorithm subject to a set of feasibility resource constraints;

a joint assignment selection step of selecting a set of joint assignments from the set of feasible joint assignments based on a selection loss minimization algorithm subject to a set of selection resource constraints; and

an elimination step of eliminating each feasible joint assignment that was not selected in the joint assignment selection step.

27. A method according to claim 18, wherein the plurality of detection sensor devices are respectively mounted on a plurality of platforms.

28. A method according to claim 27, wherein the plurality of platforms are a plurality of satellites, each of which is positioned in an earth orbit.

29. A method according to claim 27, wherein at least two detection sensors are included in each detection sensor device.

30. A method according to claim 29, wherein the at least two detection sensors include an infrared (IR) detection sensor and a radio frequency (RF) detection sensor.

31. A method according to claim 18, wherein, in the projecting step, the posterior observable positions are transformed from an earth-based coordinate system to a sensor-based coordinate system that corresponds to the detection sensor which generated the received dataframe.

32. A method according to claim 18, wherein, in the gate generation step, the generation of each gate is based on a covariance value of the respective posterior observable position.

33. A method according to claim 18, wherein the tracking processor unit comprises a plurality of processors.

34. A method according to claim 33, wherein the plurality of processors are distributed over a plurality of platforms.

35. A system for performing random-set based cluster tracking of observable objects, the system comprising:

a plurality of detection sensor means, each sensor means for generating a series of dataframes;

tracking processor means which receives dataframes from one or more of the detection sensor devices;

receiving means for receiving a dataframe from one of the detection sensor devices, the dataframe including a timestamp, and location data and amplitude data corresponding to each detected observable object in the dataframe;

observation node generation means for generating a new observation node for each observable object location data contained in the received dataframe;

propagating means for propagating forward, to a time value of the timestamp, a set of state parameters of a group track node to obtain a set of posterior observable positions, a plurality of previously-generated track nodes being assigned to the group track node;

projecting means for projecting the posterior observable positions onto a field of regard of the received dataframe;

gate generation means for generating a gate for each posterior observable position and projecting each gate over each respective posterior observable position on the received dataframe;

feasible track assignment means for determining a set of feasible track assignments for the dataframe which correlate each one of a plurality of new track nodes to at least one of the new observation nodes based on the proximity of each new observation node to at least one of the gates over the posterior observable positions, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible track assignments, and generating a probability score for the feasible track assignments;

feasible observation assignment means for determining a set of feasible observation assignments for the dataframe which correlate each new observation node to at least one new track node based on the proximity of each new observation node to at least one of the gates over the posterior observable positions, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible observation assignments, and generating a probability score for the feasible observation assignments;

feasible composite assignment means for determining a set of feasible composite assignments for a composite set of track nodes and observation nodes which correspond to at least the received dataframe, updating a set of state parameters for each track node assigned to the group track node based on the determined set of feasible composite assignments, and generating a probability score for each feasible composite assignment based on the probability scores for the feasible track assignments and the feasible observation assignments corresponding to the track nodes and observation nodes in the composite set; and

joint assignment determination means for determining a set of joint assignments based on the set of feasible composite assignments and their respective probability scores by using a loss minimization algorithm and a set of constraints, the selected set of joint assignments including at least one of the feasible composite assignments.