Method and system for tracking multiple regional objects by multi-dimensional relaxation
First Claim
1. A system for tracking objects comprising:
- means for repeatedly scanning a region containing a set of at least one moving object;
means for generating M sequential images or data-sets of said region using an output from said means for repeatedly scanning, wherein a plurality of points in said images or data-sets provide positional information for said at least one object in said set;
means for providing at least one track in a collection of tracks, wherein said at least one track tracks said at least one object in said set;
means for defining first optimization problem having a computational complexity, M dimensions and a first objective function, wherein said first objective function is specified using a plurality of costs for extending said at least one track using said points;
means for reducing said computational complexity of said first optimization problem to a second optimization problem, wherein a said second optimization problem is m-dimensional, where 2<
=m<
M;
means for solving said second optimization problem;
means for defining third optimization problem using a solution of said second optimization problem wherein said third optimization problem has M-m+1 dimensions;
means for solving said third optimization problem; and
means for recovering an optimal or near-optimal solution to said first optimization problem using a solution to said third optimization problem.
3 Assignments
0 Petitions
Accused Products
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 objects 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.
-
Citations
58 Claims
-
1. A system for tracking objects comprising:
-
means for repeatedly scanning a region containing a set of at least one moving object; means for generating M sequential images or data-sets of said region using an output from said means for repeatedly scanning, wherein a plurality of points in said images or data-sets provide positional information for said at least one object in said set; means for providing at least one track in a collection of tracks, wherein said at least one track tracks said at least one object in said set; means for defining first optimization problem having a computational complexity, M dimensions and a first objective function, wherein said first objective function is specified using a plurality of costs for extending said at least one track using said points; means for reducing said computational complexity of said first optimization problem to a second optimization problem, wherein a said second optimization problem is m-dimensional, where 2<
=m<
M;means for solving said second optimization problem; means for defining third optimization problem using a solution of said second optimization problem wherein said third optimization problem has M-m+1 dimensions; means for solving said third optimization problem; and
means for recovering an optimal or near-optimal solution to said first optimization problem using a solution to said third optimization problem. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A method for tracking objects, comprising:
-
repeatedly scanning a region containing a set consisting of one or more moving objects and generating M sequential images or data sets of said region, a plurality of points 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 points to one of said tracks; solving a first optimization problem for determining a first optimal or near-optimal assignment of said plurality of points to said tracks, said first optimization problem having; (A1) a first objective function defined using said plurality of costs, and (A2) an M-dimensional constraint set wherein constraints of said M-dimensional constraint sets determine a limit on a number of said tracks for assigning said points; said step of solving including performing steps (B1) through (B4); (B1) partitioning said M-dimensional constraint set into a plurality of lower dimensional constraint sets, said plurality of lower dimensional constraint sets, including a second constraint set and a third constraint set, wherein said second constraint set has m dimensions and said third constraint set has M-m+1 dimensions, where m=2; (B2) solving a second optimization problem for a second solution, said second optimization problem having a constraint set including said second constraint set, and having a second objective function incorporating each constraint in said third constraint set; (B3) solving a third optimization problem for a third solution, said third optimization problem having a constraint set including at least one constraint from said third constraint set, and having a third objective function having terms dependent on said second solution; (B4) recovering said first optimal or near-optimal assignment for said first optimization problem using said third solution. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 58)
-
33. A method as claimed in claim 23, wherein said second optimization problem can be computed optimally using a two-dimensional optimization problem solving technique.
-
34. A method as claimed in claim 23, wherein said second objective function includes components of a multiplier or penalty vector in said terms incorporated into said second objective function, wherein said multiplier or penalty vector is used in compensating for said second optimization problem having fewer than M-dimensions.
-
35. A method as claimed in claim 33, wherein said second objective function is specified using a relaxed Lagrangian reduction technique on multiple dimensions simultaneously.
- 36. A method as claimed in claim 23, wherein said second objective function is
- space="preserve" listing-type="equation">Maximize {Φ
.sub.mM (u.sup.m+1, . . . , u.sup.M);
u.sup.k ε
.sup.M.sbsp.k.sup.+1 ;
k=m+1, . . . , M}, 2<
=m;
}.
- space="preserve" listing-type="equation">Maximize {Φ
-
-
37. A method as claimed in claim 23, wherein said step of solving includes providing for each point in said plurality of points, a related constraint in said M-dimensional constraint set of constraints, wherein said related constraint determines a limit on a number of said tracks for assigning said point.
-
38. A method as claimed in claim 23, wherein no auxiliary function of a multiplier or penalty vector is used in determining a solution to said second optimization problem.
-
39. A method as claimed in claim 23, wherein said step (B2) of solving includes using all constraints in said second constraint set in determining a feasible solution for said second objective function.
-
40. A method as claimed in claim 23, wherein said step (B2) of solving said second optimization problem includes using a Lagrangian Relaxation technique for incorporating said terms related to said third constraint set into said second objective function.
-
41. A method as claimed in claim 23, wherein said step (B3) of solving includes formulating said third optimization problem as an assignment problem having M-m+1 dimensions.
-
42. A method as claimed in claim 23, wherein said step (B3) for solving said third optimization problem includes iteratively performing said steps of specifying said first optimization problem and solving said first optimization problem with progressively smaller dimensioned optimization problems for said first optimization problem.
-
43. A method as claimed in claim 23, further including a step of identifying a subset of said plurality of points which should be assigned to a subset of said tracks based on said plurality of costs.
-
44. A method as claimed in claim 43, further including separately assigning said subset of points to tracks of said subset of said plurality of tracks.
-
45. A method as claimed in claim 23, wherein said step (B2) of solving said second optimization problem includes reducing complexity from that of said first optimization problem by permitting at least a point of said plurality of points to be assigned to more than one track.
-
46. A method as claimed in claim 45, wherein said step (B2) of solving said second optimization problem includes reducing complexity from that of said first optimization problem by permitting points from M-m of the M sequential images or data sets to be assigned to more than one track.
-
47. A method as claimed in claim 23, wherein said constraint set for said third optimization problem includes every constraint of said third constraint set.
-
48. A method as claimed in claim 23, wherein said step (B3) of solving includes determining a plurality of factors for said terms of said third objective function wherein each factor includes a cost of said plurality of costs, said cost chosen using said second solution.
-
49. A method as claimed in claim 23, wherein said step of recovering includes determining zn as said optimal or near-optimal assignment, wherein:
- ##EQU48## where ##EQU49## such that wm is said second solution and (i1j, . . . , imj)≠
(0, . . . ,
0); and
where y is said third solution.
- ##EQU48## where ##EQU49## such that wm is said second solution and (i1j, . . . , imj)≠
-
58. A method as claimed in claim 33, wherein said two-dimensional assignment solving technique uses a bundle trust method.
-
50. A method for tracking objects, comprising:
-
repeatedly scanning a region containing a set consisting of one or more moving objects and generating M sequential images or data sets of said region, a plurality of points 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 points to one of said tracks; solving a first optimization problem for determining a first optimal or near-optimal assignment of said plurality of points to said tracks, said first optimization problem having an M-dimensional first plurality of constraints, wherein constraints of said first plurality of constraints determine a limit on a number of said tracks for assigning said points; wherein said step of solving includes the steps (B1) and (B2); (B1) determining a maximum value for
space="preserve" listing-type="equation">{Φ
.sub.mM (u.sup.m+1, . . . , u.sup.M);
u.sup.k ε
.sup.M.sbsp.k.sup.+1 ;
k=m+1, , . . . , M}, 2<
=m;(B2) recovering said first optimal or near-optimal assignment for said first optimization problem using said maximum value. - View Dependent Claims (51, 52, 53, 54)
-
-
55. A method for tracking objects, comprising:
-
repeatedly scanning a region containing a set consisting of one or more moving objects and generating M sequential images or data sets of said region, a plurality of points 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 points to one of said tracks; solving a first optimization problem for determining a first optimal or near-optimal assignment of said plurality of points to said tracks, said first optimization problem having; (C1) a first objective function created using said plurality of costs, said first objective function receiving first input data indicating an assignment of said plurality of points to said plurality of tracks, said first objective function outputting a cost; (C2) an M-dimensional first plurality of constraints, wherein constraints of said first plurality of constraints determine a limit on a number of said tracks for assigning said points; wherein said step of solving includes specifying a second objective function, said second objective function derived from said first objective function by incorporating a set of constraints from said first plurality of constraints into said first objective function, said set of constraints including constraints on the assignments of points in at least two of said images or data sets; and solving a second optimization problem having said second objective function and having all constraints of said first optimization problem except the constraints in said set of constraints; recovering said first optimal or near-optimal assignment for said first optimization problem using a solution to said second optimization problem.
-
-
56. A method for tracking at least one object, comprising:
-
repeatedly scanning a region containing a set consisting of one or more moving objects and generating M sequential images or data sets of said region, a plurality of points in said images or data sets providing positional information for objects in said set; providing at least one track in a collection of tracks for each object in said set, said at least one track related to said positional information for the object; specifying an initial optimization problem for determining a track extension for each track of said collection of tracks, each said track extension determined using points from a plurality of points representing positional information for each object being tracked, wherein said initial optimization problem has M constraint dimensions, each constraint dimension constraining a different set of points in said plurality of points; solving said initial optimization problem by; (A1) solving at least one optimization problem derived from said initial optimization problem by simultaneously relaxing at least two constraint dimensions; and (A2) using a solution to each optimization problem solved in (A1) to obtain an optimal or near-optimal solution to sad initial optimization problem.
-
-
57. A method for tracking at least one object, comprising:
-
providing at least one track in a collection of tracks, wherein, for each object being tracked said collection of tracks includes a track related to the object; specifying an initial optimization problem for determining a track extension for each track of said collection of tracks, each said track extension determined using points from one of M-1 and M sequential images or data-sets of a region, said points representing positional information for each object being tracked, wherein said initial optimization problem has one of M and M+1 constraint dimensions, respectively, each of at least some of said constraint dimensions constraining points from different said images or data-sets; solving said initial optimization problem by; (A1) solving at least one optimization problem derived from said initial optimization problem by simultaneously relaxing at least two constraint dimensions; and (A2) using a solution to each optimization problem solved in (A1) to obtain an optimal or near-optimal solution to said initial optimization problem.
-
Specification