Communications: directive radio wave systems and devices (e.g. – Return signal controls radar system – Receiver
Reexamination Certificate
1999-05-14
2002-06-11
Hellner, Mark (Department: 3662)
Communications: directive radio wave systems and devices (e.g.,
Return signal controls radar system
Receiver
C342S090000
Reexamination Certificate
active
06404380
ABSTRACT:
BACKGROUND OF THE INVENTION
a. Field of the Invention
The invention relates generally to computerized techniques for processing data obtained from radar to track multiple discrete objects.
b. Description of the Background
There are many situations where the courses of multiple objects in a region must be tracked. Typically, radar is used to scan the region and generate discrete images or “snapshots” based on sets of returns or observations. In some types of tracking systems, all the returns from any one object are represented in an image as a single point unrelated to the shape or size of the objects. “Tracking” is the process of identifying a sequence of points from a respective sequence of the images that represents the motion of an object. The tracking problem is difficult when there are multiple closely spaced objects because the objects can change speed and direction rapidly and move into and out of the line of sight for other objects. The problem is exacerbated because each set of returns may result from noise as well as echoes from the actual objects. The returns resulting from the noise are also called false positives. Likewise, the radar will not detect all echoes from the actual objects and this phenomena is called a false negative or “missed detect” error. For tracking airborne objects, a large distance between the radar and the objects diminishes the signal to noise ratio so the number of false positives and false negatives can be high. For robotic applications, the power of the radar is low and as a result, the signal to noise ratio can also be low and the number of false positives and false negatives high.
In view of the proximity of the objects to one another, varied motion of the objects and false positives and false negatives, multiple sequential images should be analyzed collectively to obtain enough information to properly assign the points to the proper tracks. Naturally, the larger the number of images that are analyzed, the greater the amount of information that must be processed.
While identifying the track of an object, a kinematic model may be generated describing the location, velocity and acceleration of the object. Such a model provides the means by which the future motion of the object can be predicted. Based upon such a prediction, appropriate action may be initiated. For example, in a military application there is a need to track multiple enemy aircraft or missiles in a region to predict their objective, plan responses and intercept them. Alternatively, in a commercial air traffic control application there is a need to track multiple commercial aircraft around an airport to predict their future courses and avoid collision. Further, these and other applications, such as robotic applications, may use radar, sonar, infrared or other object detecting radiation bandwidths for tracking objects. In particular, in robotic applications reflected radiation can be used to track a single object which moves relative to the robot (or vice versa) so the robot can work on the object.
Consider the very simple example of two objects being tracked and no false positives or false negatives. The radar, after scanning at time t
1
, reports objects at two locations in a first observation set. That is, the radar returns a set of two observations {o
11
, o
12
}. At time t
2
the radar returns a similar set of two observations {o
21
, o
22
) from a second observation set. Suppose from prior processing that track data for two tracks T
1
and T
2
includes the locations at t
0
of two objects. Track T
1
may be extended through the points in the two sets of observations in any of four ways, as may track T
2
. The possible extensions of T
1
can be described as: {T
1
, o
11
, o
21
}, {T
1
, o
11
, o
22
}, {T
1
, o
12
, o
21
} and {T
1
, o
12
, o
22
}. Tracks can likewise be extended from T
2
in four possible ways, including {T
2
, o
12
, o
21
}.
FIG. 1
illustrates these five (out of eight) possible tracks (to simplify the problem for purposes of explanation). The five track extensions are labeled h
11
, h
12
, h
13
, h
14
, and h
21
wherein h
11
is derived from {T
1
, o
11
, o
21
}, h
12
is derived from {T
1
, o
11
, o
22
}, h
13
is derived from {T
1
, o
12
, o
21
}, h
14
is derived from {T
1
, o
12
, o
22
}, and h
21
is derived from {T
2
, o
11
, o
21
}. The problem of determining which such track extensions are the most likely or optimal is hereinafter known as the assignment problem.
It is known from prior art to determine a figure of merit or cost for assigning each of the points in the images to a track. The figure of merit or cost is based on the likelihood that the point is actually part of the track. For example, the figure of merit or cost may be based on the distance from the point to an extrapolation of the track.
FIG. 1
illustrates costs &dgr;
21
and &dgr;
22
for hypothetical extension h
21
and modeled target characteristics. The function to calculate the cost will normally incorporate detailed characteristics of the sensor, such as probability of measurement error, and track characteristics, such as likelihood of track maneuver.
FIG. 2
illustrates a two by two by two matrix, c, that contains the costs for each point in relation to each possible track. The cost matrix is indexed along one axis by the track number, along another axis by the image number and along the third axis by a point number. Thus, each position in the cost matrix lists the cost for a unique combination of points and a track, one point from each image.
FIG. 2
also illustrates a {0, 1} assignment matrix, z, which is defined with the same dimensions as the cost matrix. Setting a position in the assignment matrix to “one” means that the equivalent position in the cost matrix is selected into the solution. The illustrated solution matrix selects the {h
14
, h
21
} solution previously described. Note that for the above example of two tracks and two snapshots, the resulting cost and assignment matrices are three-dimensional. As used in this patent application, the term “dimension” means the number of axes in the cost or assignment matrix while size refers to the number of elements along a typical axis. The costs and assignments have been grouped in matrices to facilitate computation.
A solution to the assignment problem satisfies two constraints—first, the sum of the associated costs for assigning points to a track extension is minimized and, second, if no false positives or false negatives exist, then each point is assigned to one and only one track.
When false positives exist, however, additional hypothetical track extensions incorporating the false positives will be generated. Further note that the random locations of false positives will, in general, not fit well with true data and such additional hypothetical track extensions will result in higher costs. Also note that when false negative errors exist, then the size of the cost matrix must grow to include hypothetical track extensions formulated with “gaps” (i.e., data omissions where there should be legitimate observation data) for the false negatives. Thus, the second criteria must be weakened to reflect false positives not being as signed and also to permit the gap filler to be multiply assigned. With hypothetical cost calculated in this manner then the foregoing criteria for minimization will to materialize the false negatives and avoid the false positives.
For a three-dimensional problem, as is illustrated in
FIG. 1
, but with N
1
(initial) tracks, N
2
observations in scan 1, N
3
observations in scan 2, false positives and negatives assumed, the assignment problem can be formulated as:
(
a
)
Minimize:
∑
i
1
=
0
N
1
∑
i
2
=
0
N
2
∑
i
3
=
0
N
3
C
i
1
i
2
i
3
z
i
1
i
2
i
3
(
b
)
Subject to:
∑
i
2
=
1
N
2
∑
i
3
=
1
N
3
z
i
1
i
2
i
3
=
1
,
i
1
=
1
,
…
N
1
,
(
c
)
∑
i
Cochran William W.
Colorado State University Research Foundation
Hellner Mark
LandOfFree
Method and system for tracking multiple regional objects by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for tracking multiple regional objects by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for tracking multiple regional objects by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2929346