US5379044A — Efficient multi-target tracking method

Claim 1

Independent Claim 134 words

A method for multi-target tracking of targets for a sensor system generating a sequence of successive data frames, each comprising a set of observations representing data collected by the sensor system during a sensing period, comprising a sequence of the following steps: receiving the first frame and setting up a set of tracks in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data regarding said previously received frames; processing the observations in the new frame to generate a new set of tracks based on said new set of observations as well as observations received from previous frames; and generating a fresh set of hypotheses each comprising a set of tracks such that no two tracks within any hypothesis have any observations in common.

Claim 2

Independent Claim 134 words

A method for multi-target tracking of targets for a sensor system generating a sequence of successive data frames, each comprising a set of observations representing data collected by the sensor system during a sensing period, comprising a sequence of the following steps: receiving the first frame and setting up a set of tracks in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data regarding said previously received frames; processing the observations in the new frame to generate a new set of tracks based on said new set of observations as well as observations received from previous frames; and generating a fresh set of hypotheses each comprising a set of tracks such that no two tracks within any hypothesis have any observations in common.

Claim 3

Dependent Claim 29 words

The method of claim 1 wherein said step of deleting stale data comprises deleting the hypotheses, if any, generated for the previous frame, leaving an unstructured collection of tracks.

Claim 4

Dependent Claim 29 words

The method of claim 1 wherein said step of processing new observations comprises creating a set of K track records, one for each new observation comprising the new frame.

Claim 5

Dependent Claim 49 words

The method of claim 1 wherein said step of generating new tracks comprises considering all possible assignments of observations to tracks, assigning a score to each track indicative of the quality of the associations of the respective observations to the respective track, and recording the score for each track.

Claim 6

Dependent Claim 18 words

The method of claim 4 wherein said step of generating hypotheses comprises sorting the tracks in score order.

Claim 7

Dependent Claim 42 words

The method of claim 4 further characterized in that the score is a function mapping the tracks at frame n into non-negative score numbers, and in that each hypothesis has a score which is the sum of the scores of its tracks.

Claim 8

Dependent Claim 24 words

The method of claim 4 further comprising the step of harvesting said new set of tracks to eliminate relatively low scoring tracks from consideration.

Claim 9

Dependent Claim 53 words

The method of claim 1 wherein said tracks form a set Z, and further comprising the step of forming clusters (X(i)) of said tracks, wherein said clusters X(i) are subsets of Z, and, for i not equal to j, no track in cluster X(i) shares any observations with a track in cluster X(j).

Claim 10

Dependent Claim 111 words

The method of claim 8 wherein said step of forming clusters comprises: setting up a first file containing a list of each track, for each such track and for each frame of a discrete set of frames, a pointer to another track which shares the same observation for the frame, and for each track a cluster label representing the cluster to which said track will be or has been assigned; and searching said track list for tracks which have not been assigned to a cluster, and assigned each such track to a cluster including tracks which share an observation in any one of said frames with an observation comprising such track.

Claim 11

Dependent Claim 30 words

The method of claim 9 wherein a frame pointer of a track which does not share any observations with any other track for a given frame points to that track.

Claim 12

Dependent Claim 27 words

The method of claim 10 wherein said step of searching said track list comprises searching said pointers to find other tracks to be added to said cluster.

Claim 13

Dependent Claim 22 words

The method of claim 1 wherein each observation comprises first and second data address values, said first address value describing the quadrant.

Claim 14

Independent Claim 164 words

A method for multi-target tracking of targets for a sensor system generating a sequence of successive data frames, each comprising a set of observations representing data collected by the sensor system during a sensing period, comprising a sequence of the following steps: receiving the first frame and setting up a set of tracks in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data regarding said previously received frames; processing the observations in the new frame to generate a new set of tracks based on said new set of observations as well as observations received from previous frames; adaptively selecting one hypotheses generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; and generating a fresh set of hypotheses by use of said selected algorithm, each hypothesis comprising a hypothesis set of tracks such that no two tracks within any hypothesis have any observations in common.

Claim 15

Independent Claim 164 words

A method for multi-target tracking of targets for a sensor system generating a sequence of successive data frames, each comprising a set of observations representing data collected by the sensor system during a sensing period, comprising a sequence of the following steps: receiving the first frame and setting up a set of tracks in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data regarding said previously received frames; processing the observations in the new frame to generate a new set of tracks based on said new set of observations as well as observations received from previous frames; adaptively selecting one hypotheses generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; and generating a fresh set of hypotheses by use of said selected algorithm, each hypothesis comprising a hypothesis set of tracks such that no two tracks within any hypothesis have any observations in common.

Claim 16

Dependent Claim 29 words

The method of claim 13 wherein said step of deleting stale data comprises deleting the hypotheses, if any, generated for the previous frame, leaving an unstructured collection of tracks.

Claim 17

Dependent Claim 29 words

The method of claim 13 wherein said step of processing new observations comprises creating a set of K track records, one for each new observation comprising the new frame.

Claim 18

Dependent Claim 49 words

The method of claim 13 wherein said step of generating new tracks comprises considering all possible assignments of observations to tracks, assigning a score to each track indicative of the quality of the associations of the respective observations to the respective track, and recording the score for each track.

Claim 19

Dependent Claim 18 words

The method of claim 16 wherein said step of generating hypotheses comprises sorting the tracks in score order.

Claim 20

Dependent Claim 42 words

The method of claim 16 further characterized in that the score is a function mapping the tracks at frame n into non-negative score numbers, and in that each hypothesis has a score which is the sum of the scores of its tracks.

Claim 21

Dependent Claim 24 words

The method of claim 16 further comprising the step of harvesting said new set of tracks to eliminate relatively low scoring tracks from consideration.

Claim 22

Dependent Claim 36 words

The method of claim 13 wherein said plurality of available algorithms comprises an exhaustive generation algorithm selected when the number of tracks is small, said exhaustive generation algorithm for generating all hypotheses consistent with said tracks.

Claim 23

Dependent Claim 55 words

The method of claim 13 wherein said plurality of available algorithms includes a bounded search algorithm for generating multiple hypotheses, wherein partial hypotheses are grown by an iterative process, and the number of iterations is no more than (N+K), where N is the number of old tracks and K is the number of new observations.

Claim 24

Dependent Claim 74 words

The method of claim 21 wherein: during each iteration L, all forming hypotheses are paired with each track, increasing the hypotheses size by one; as each track is paired with a growing hypothesis, a score for each pairing is computed, and a decision is made to add such track to this growing hypothesis in dependence on the pairing score; and after L iterations, each growing hypothesis has a length of at most L tracks.

Claim 25

Dependent Claim 18 words

The method of claim 22 wherein after each iteration, the hypotheses are harvested to eliminate duplicate partial hypotheses.

Claim 26

Dependent Claim 23 words

The method of claim 13 wherein said plurality of available algorithms includes an algorithm for providing an optimal assignment for a single hypothesis.

Claim 27

Dependent Claim 33 words

The method of claim 13 wherein said plurality of available algorithms includes an algorithm selected when the number of tracks is large, and which produces a relatively quick generation of a plausible hypothesis.

Claim 28

Independent Claim 229 words

A method for multi-target tracking of targets for a sensor system generating a sequence of successive data frames, each comprising a set of observations representing data collected by the sensor system during a sensing period, comprising a sequence of the following steps: receiving the first frame and setting up a set of tracks in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data regarding said previously received frames; processing the observations in the new frame to generate a new set of tracks based on said new set of observations as well as observations received from previous frames; for each cluster (X(i)), adaptively selecting one hypotheses generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; for each cluster (X(i(), adaptively selecting one hypothesis generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; and forming clusters (X(i)) of said tracks, wherein said clusters X(i) are subsets of Z, and, for i not equal to j, no track in cluster X(i) shares any observations with a track in cluster X(j); generating a fresh set of hypotheses by use of said selected algorithm, each hypothesis comprising a hypothesis set of tracks such that no two tracks within any hypothesis have any observations in common.

Claim 29

Independent Claim 229 words

A method for multi-target tracking of targets for a sensor system generating a sequence of successive data frames, each comprising a set of observations representing data collected by the sensor system during a sensing period, comprising a sequence of the following steps: receiving the first frame and setting up a set of tracks in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data regarding said previously received frames; processing the observations in the new frame to generate a new set of tracks based on said new set of observations as well as observations received from previous frames; for each cluster (X(i)), adaptively selecting one hypotheses generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; for each cluster (X(i(), adaptively selecting one hypothesis generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; and forming clusters (X(i)) of said tracks, wherein said clusters X(i) are subsets of Z, and, for i not equal to j, no track in cluster X(i) shares any observations with a track in cluster X(j); generating a fresh set of hypotheses by use of said selected algorithm, each hypothesis comprising a hypothesis set of tracks such that no two tracks within any hypothesis have any observations in common.

Claim 30

Dependent Claim 29 words

The method of claim 26 wherein said step of deleting stale data comprises deleting the hypotheses, if any, generated for the previous frame, leaving an unstructured collection of tracks.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-01-02	1998-07-04	1999-01-03	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-01-02	2002-07-04	2003-01-03	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-01-02	2006-07-04	2007-01-03	$7700.00	Window Closed / Lapsed

Efficient multi-target tracking method

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag