Patent EP0660134A2 successfully refreshed from Google Patents.
EP0660134A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Efficient multi-target tracking method
Assignee: Raytheon Co
•
Filing: 1994-12-22
•
Granted: —
•
Expires: 2014-12-22
Abstract
Abstract The method involves receiving a first frame and setting up a set of tracks in dependence on a data contg the first frame. Then following steps are performed for each successive received frame such as deleting stale data regarding the previously received frames, processing the observation in a new frame to generate a new set of tracks based on the new set of observations received from previous frames. Subsequently it is followed by generating a fresh set of hypothesis each comprising a set of tracks such that no two tracks within any hypothesis have any observations in common.
Inventors
- 👤 Robert C. Carlson
- 👤 Robert A. Rosen
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 16:33
CPC Classifications
G; G01; G01S; G01S13/00; G01S13/66; G01S13/72; G01S13/723; G01S13/726
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
141 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 observatins representing data collected by the sensor system during a sensing period, characterized by a sequence of the following steps: receiving the first frame (60) and setting up a set of tracks (62) in dependence on the data comprising said first frame; for each successive frame received, performing the following steps: deleting stale data (64) regarding said previously received frames; processing the observations (68) in the new frame to generate a new set of tracks (70) based on said new set of observations as well as observations received from previous frames; and generating a fresh set of hypotheses (78) each comprising a set of tracks such that no two tracks within any hypothesis have any observations in common.
Claim 2
Dependent Claim
32 words
The method of claim 1, characterized in that said step of deleting stale data (64) comprises deleting the hypotheses, if any, generated for the previous frame, leaving an unstructured collection of tracks.
Claim 3
Dependent Claim
33 words
The method of claim 1 or 2, characterized in that said step of processing new observations (68) comprises creating a set of K track records, one for each observation comprising the new frame.
Claim 4
Independent Claim
56 words
The method of any of claims 1 to 3, characterized in that said step of generating new tracks (70) 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 5
Dependent Claim
21 words
The method of claim 4, characterized in that said step of generating hypotheses (78) comprises sorting the tracks in score order.
Claim 6
Dependent Claim
43 words
The method of claim 4 or 5, 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 7
Independent Claim
30 words
The method of any of claims 4, 5 or 6, characterized by the step of harvesting (72) said new set of tracks to eliminate relatively low scoring tracks from consideration.
Claim 8
Independent Claim
60 words
The method of any of claims 1 to 7, characterized in that said tracks form a set Z, and further comprising the step of forming clusters (X(i)) of said tracks (74), 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 9
Dependent Claim
114 words
The method of claim 8, characterized in that said step of formig clusters (74) 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 10
Dependent Claim
32 words
The method of claim 9, characterized in that 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 11
Dependent Claim
29 words
The method of claim 10, characterized in that said step of searching said track list comprises searching said pointers to find other tracks to be added to said cluster.
Claim 12
Independent Claim
28 words
The method of any of claims 1 to 11, characterized in that each observation comprises first and second data address values, said first address value describing the quadrant.
Claim 13
Independent Claim
78 words
The method of any of claims 1 to 12, characterized in that said step of generating a fresh set of hypotheses comprises: adaptively selecting (76) one hypotheses generation algorithm from a plurality of available algorithms in dependence on the number of tracks in said set; using said selected algorithm for generating a fresh set of hypotheses with each hypothesis comprising a hypothesis set of tracks such that no two tracks within any hypothesis have any observations in common.
Claim 14
Dependent Claim
38 words
The method of claim 13, characterized in that 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 15
Dependent Claim
61 words
The method of claim 13 or 14, characterized in that 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 16
Dependent Claim
76 words
The method of claim 15, characterized in that 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 17
Dependent Claim
20 words
The method of claim 16, characterized in that after each iteration, the hypotheses are harvested to eliminate duplicate partial hypotheses.
Claim 18
Independent Claim
29 words
The method of any of claims 13 to 17, characterized in that said plurality of available algorithms includes an algorithm for providing an optimal assignment for a single hypothesis.
Claim 19
Independent Claim
39 words
The method of any of claims 13 to 18, characterized in that 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 20
Dependent Claim
142 words
The method of claim 1 or 2, characterized in that for each successive frame received, the following additional steps are performed: 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)); using said selected algorithm for generating a fresh set of hypotheses, with each hypothesis comprising a hypothesis set of tracks such that no two tracks within any hypothesis have any observations in common.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.