Method and system for tracking multiple regional objects by multi-dimensional relaxation

• US 5,959,574 A
• Filed: 07/16/1996
• Issued: 09/28/1999
• Est. Priority Date: 12/21/1993
• Status: Expired

• Current Assignee: Colorado State University Research Foundation (Colorado State University System)
• Original Assignee: Colorado State University Research Foundation (Colorado State University System)
• Inventors: Poore, Aubrey B. Jr.
• Primary Examiner(s): Hellner, Mark
• Application Number:
  US08/682,904
• Time in Patent Office: 1,169 Days
• Field of Search: 342/96
• US Class Current: 342/96
• CPC Class Codes: G01S 13/726 Multiple target tracking
• CPC Class Codes: G01S 3/7864 T.V. type tracking systems

Abstract

A method and system for real-time tracking of objects is disclosed. A region is repeatedly scanned providing a plurality of images or data sets having points corresponding to ojbects in the region to be tracked. Given a previously determined track for each object in the region, an M-dimensional combinatorial optimization assignment problem is formulated using the points from M-1 of the images or data sets, wherein each point is preferably used in extending at most one track. The M-dimensional problem is subsequently solved for an optimal or near-optimal assignment of the points to the tracks, extending the tracking of the objects so that a response to each object can be initiated by the system in real-time. Speed and accuracy is provided by an iterative Lagrangian Relaxation technique wherein a plurality of constraint dimensions are relaxed simultaneously to yield a reduced dimensional optimization problem whose solution is used to formulate an assignment problem of dimensionality less than M. The iterative reducing of dimensions terminates when exact solutions are determined for two-dimensional cases. A recovery procedure is used for determining a higher dimensional assignment problem solution from a problem having one less dimension. The procedure is useful when the reduced dimensional optimizational problem has two constraint dimensions.

Claims

1. A method for tracking a plurality of objects, comprising:

repeatedly scanning a region containing a set consisting of one or more moving objects and generating N sequential images or data sets of said region, a plurality of observations in said images or data sets providing positional information for objects in said set;

determining a plurality of tracks, at least one track for each object in said set;

determining a plurality of costs, wherein each cost is for assigning one of said observations to one of said tracks;

defining a linear programming problem;

##EQU130## wherein each c_i.sbsb.1 .sub.. . . i.sbsb.N is included in said plurality of costs, each M_i, i=1, . . . ,N, being one of;

(a) a number of observations in an i^th image or data set of said N sequential images or data sets;

(b) a sum of a number of tracks in said plurality of tracks, and a number of said observations in the i^th image or data set not assigned to one of said tracks; and

(c) a number of tracks in said plurality of tracks;

solving said linear programming problem for values of z_i.sbsb.1 .sub.. . . i.sbsb.N for each i1 . . . iN;

determining a value z_i.sbsb.1 .sub.. . . i.sbsb.N in {0,1} for each i1 . . . iN corresponding to each z_i.sbsb.l .sub.. . . i_N, wherein said values zi1 . . . iN provide an optimal or near optimal solution to said linear programming problem;

taking one or more of the following actions based on said optimal or near-optimal assignment of said plurality of points to said plurality of tracks;

sending a warning to aircraft or a ground or sea facility,

controlling air traffic,

controlling anti-aircraft or anti-missile equipment,

taking evasive action,

working on one of said one or more objects, surveilling one of said one or more objects.