Multiple hypothesis tracking using maximum weight independent set

• US 9,291,708 B2
• Filed: 03/09/2012
• Issued: 03/22/2016
• Est. Priority Date: 03/09/2012
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Ploplys, Nicholas J., Kenefic, Richard J.
• Primary Examiner(s): Barker, Matthew M
• Application Number:
  US13/416,069
• Publication Number:
  US 20130234882A1
• Time in Patent Office: 1,474 Days
• Field of Search: 342/96
• US Class Current: 1/1
• CPC Class Codes: G01S 13/726 Multiple target tracking
• CPC Class Codes: G01S 15/66 Sonar tracking systems
• CPC Class Codes: G01S 17/66 Tracking systems using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 7/295 Means for transforming co-ordinates or for evaluating data, e.g. using computers

Abstract

The technology described herein includes a system and/or a method for multiple hypothesis tracking. In some examples, a multiple hypothesis tracking system includes a receiver, an array generation module, and a local search move module. The receiver is configured to receive tracking data associated with one or more target families from one or more sensors. The array generation module is configured to generate a matrix array based on the tracking data. The local search move module is configured to perform one or more local search moves on one or more cells in the matrix array to increase a global hypothesis score for the tracking data.

Claims

1. A multiple hypothesis tracking apparatus for identifying accurate track hypotheses for one or more moving target objects from tracking data acquired by a radar, sonar or optical sensor, the apparatus comprising:

a receiver configured to receive tracking data associated with one or more target object families from one or more radar, sonar or optical sensors;

an array generation processor configured to generate a matrix array using the tracking data, wherein each cell in the matrix array is associated with a subject target object family of the one or more target object families identified in the tracking data;

a global hypothesis score processor configured to generate a global hypothesis score using the matrix array, the global hypothesis score providing an indication of the tracking accuracy of the one or more target object families by the apparatus;

a local search move processor configured to perform one or more local search moves on one or more cells in the matrix array to increase the global hypothesis score for the tracking data, wherein the one or more local search moves includes at least one of;

exchanging cells, removing a subject cell, adding at least one cell in the matrix array; and

a track identification processor configured to identify a track for a target object based on the matrix array.

2. The apparatus of claim 1, wherein the one or more local search moves comprises exchanging cells associated with a same target object family in the matrix array, exchanging cells associated with different target object families in the matrix array, removing a cell in the matrix array, adding a cell in the matrix array, or any combination thereof.

3. The apparatus of claim 1, wherein the array generation processor is further configured to:

identify target object families in the tracking data; and

associate the identified target object families with a cell in the matrix array.

4. The apparatus of claim 1, wherein each target object family in the one or more target families is associated with a target object.

5. The apparatus of claim 4, wherein each associated target object is a ground vehicle, an air vehicle, a space vehicle, a water vehicle, or any combination thereof.

6. In a multiple hypothesis tracking apparatus, a method for identifying accurate track hypotheses for one or more moving target objects from tracking data acquired by a radar, sonar or optical sensor, the method executed by one or more processors and comprising:

receiving, at a receiver, tracking data associated with one or more target object families from one or more radar, sonar or optical sensors;

generating, by one or more processors comprising the apparatus, a matrix array based on the tracking data, wherein each cell in the matrix array is associated with a subject target object family of the one or more target object families identified in the tracking data, and a global hypothesis score using the matrix array, the global hypothesis score providing an indication of the tracking accuracy of the one or more target object families by the apparatus;

performing, by the one or more processors, one or more local search moves on one or more cells in the matrix array to increase the global hypothesis score for the tracking data, wherein the one or more local search moves includes at least one of;

exchanging cells, removing a subject cell, adding at least one cell in the matrix array; and

identifying a track for a target object based on the matrix array.

7. The method of claim 6, wherein the one or more local search moves comprises exchanging cells in the matrix array, removing a cell in the matrix array, adding a cell in the matrix array, or any combination thereof.

8. The method of claim 7, wherein the cells in the matrix array are associated with a same target object family.

9. The method of claim 6, wherein the generating step further comprises converting, by the one or more processors, the tracking data into a plurality of vertices, each vertex in the plurality of vertices is associated with a target object track.

10. The method of claim 6, wherein each cell in the matrix cell array is associated with a target object family in the one or more target object families and each target object family in the one or more target object families is associated with one or more compatible target object tracks.

11. The method of claim 6, wherein each target object family in the one or more target object families is associated with a target object.

12. The method of claim 11, wherein each associated target object is a ground vehicle, an air vehicle, a space vehicle, a water vehicle, or any combination thereof.

13. A non-transitory computer program product, tangibly embodied in a non-transitory information carrier, the computer program product including instructions being operable to cause a multiple hypothesis tracking apparatus coupled to one or more radar, sonar or optical sensors and including a data processing apparatus, that when executed by the data processing apparatus, cause the data processing apparatus to:

receive tracking data associated with one or more target object families from one or more radar, sonar or optical sensors;

generate a matrix array using the tracking data, wherein each cell in the matrix array is associated with a subject target object family of the one or more target object families identified in the tracking data;

generate a global hypothesis score using the matrix array, the global hypothesis score providing an indication of the tracking accuracy of the one or more target families by the data processing apparatus; and

perform one or more local search moves on one or more cells in the matrix array to increase the global hypothesis score for the tracking data, wherein the one or more local search moves includes at least one of;

exchanging cells, removing a subject cell, adding at least one cell in the matrix array; and

identify a track for a target object based on the matrix array.