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

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.

Claim 2

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.

Claim 24

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.

Claim 25

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.

Claim 52

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 {Φ.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.

Claim 53

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 {Φ.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.

Claim 58

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.

Claim 59

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.

Claim 60

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.

Claim 61

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.

Claim 62

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.

Claim 63

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.