Signal Processing
Tracking. Strong noise and man-made interferences, including electronic counter measure (i.e., jamming), can lead the signal processing and detection process to wrong conclusions about the presence of objects. A track record on a nonexisting object is called a false return. An application that examines all the track records in order to sort out false returns from real ones and update the trajectories of detected objects is called a tracker.10 Using the jargon of the subject area, we say that the tracker assigns each measured value (i.e., the tuple of position and velocity contained in each of the track records generated in a scan) to a trajectory. If the trajectory is an existing one, the measured value assigned to it gives the current position and velocity of the object moving along the trajectory. If the trajectory is new, the measured value gives the position and velocity of a possible new object. In the example in Figure 1–6, tracker runs on one or more data processors which communicate with the signal processors via the shared memory.
Gating. Typically, tracking is carried out in two steps: gating and data association [Bogl]. Gating is the process of putting each measured value into one of two categories depending on whether it can or cannot be tentatively assigned to one or more established trajectories. The gating process tentatively assigns a measured value to an established trajectory if it is within a threshold distance G away from the predicted current position and velocity of the object moving along the trajectory. (Below, we call the distance between the measured and predicted values the distance of the assignment.) The threshold G is called the track gate. It is chosen so that the probability of a valid measured value falling in the region bounded by a sphere of radius G centered around a predicted value is a desired constant.
Figure 1–7 illustrates this process. At the start, the tracker computes the predicted position (and velocity) of the object on each established trajectory. In this example, there are two established trajectories, L1 and L2. We also call the predicted positions of the objects on these tracks L1 and L2. X1, X2, and X3 are the measured values given by three track records. X1 is assigned to L1 because it is within distance G from L1. X3 is assigned to both L1 and L2 for the same reason. On the other hand, X2 is not assigned to any of the trajectories. It represents either a false return or a new object. Since it is not possible to distinguish between these two cases, the tracker hypothesizes that X2 is the position of a new object. Subsequent radar data will allow the tracker to either validate or invalidate this hypothesis. In the latter case, the tracker will discard this trajectory from further consideration.
Data Association. The tracking process completes if, after gating, every measured value is assigned to at most one trajectory and every trajectory is assigned at most one measured value. This is likely to be case when (1) the radar signal is strong and interference is low (and hence false returns are few) and (2) the density of objects is low. Under adverse conditions, the assignment produced by gating may be ambiguous, that is, some measured value is assigned to more than one trajectory or a trajectory is assigned more than one measured value. The data association step is then carried out to complete the assignments and resolve ambiguities.
There are many data association algorithms. One of the most intuitive is the the nearest neighbor algorithm. This algorithm works as follows:
1. Examine the tentative assignments produced by the gating step.
a. For each trajectory that is tentatively assigned a single unique measured value, assign the measured value to the trajectory. Discard from further examination the trajectory and the measured value, together with all tentative assignments involving them.
b. For each measured value that is tentatively assigned to a single trajectory, discard the tentative assignments of those measured values that are tentatively assigned to this trajectory if the values are also assigned to some other trajectories.
2. Sort the remaining tentative assignments in order of nondecreasing distance.
3. Assign the measured value given by the first tentative assignment in the list to the corresponding trajectory and discard the measured value and trajectory.
4. Repeat step (3) until the list of tentative assignments is empty.
In the example in Figure 1–7, the tentative assignment produced by the gating step is ambiguous. Step (1a) does not eliminate any tentative assignment. However, step (1b) finds that X1 is assigned to only L1, while X3 is assigned to both L1 and L2. Hence, the assignment of X3 to L1 is discarded from further consideration. After step (1), there still are two tentative assignments, X1 to L1 and X3 to L2. Step (2) leaves them in this order, and the subsequent steps make these assignments. X2 initiates a new trajectory. If during subsequent scans, no measured values are assigned to the new trajectory, it will be discarded from further consideration.
The nearest neighbor algorithm attempts to minimize a simple local objective function: the distance (between the measured and predicted values) of each assignment. Data association algorithms of higher time complexity are designed to optimize some global, and therefore more complicated, objective functions, for example, the sum of distances of all assignments and probability of errors. The most complex in both time and space is the class of multiple hypothesis tracking algorithms. Often it is impossible to eliminate some assignments from further consideration by looking at the measured values produced in one scan. (An example is when the distances between a measured value to two or more predicted values are essentially equal.) While a single-hypothesis tracking algorithm (e.g., the nearest neighbor algorithm) must choose one assignment from equally good assignments, a multiple-hypothesis tracking algorithm keeps all of them. In other words, a trajectory may be temporally branched into multiple trajectories, each ending at one of many hypothesized current positions. The tracker then uses the data provided in future scans to eliminate some of the branches. The use of this kind of algorithms is confined to where the tracked objects are dense and the number of false returns are large (e.g., for tracking military targets in the presence of decoys and jamming).
Complexity and Timing Requirements. In contrast to signal processing, the amounts of processor time and memory space required by the tracker are data dependent and can vary widely.When there are n established trajectories and m measured values, the time complexity of gating is O(nm logm). (This can be done by first sorting the m measured values according to their distances from the predicted value for each of the established trajectories and then comparing the distances with the track gate G.) In the worst case, all m measured values are tentatively assigned to all n trajectories in the gating step. The nearest neighbor algorithm must sort all nm tentative assignments and hence has time complexity O(nm lognm). The amounts of time and space required by multiple-hypothesis tracking grow exponentially with the maximum number of hypotheses, the exponent being the number of scans required to eliminate each false hypothesis. Without modern fast processors and large memory, multiplehypothesis tracking would not be feasible.
Figure 1–6 shows that the operation of the radar is controlled by a controller that executes on the data processor. In particular, the controller may alter the search strategy or change the radar operation mode (say from searching to tracking an object) depending on the results found by the tracker. (As we mentioned earlier, a phase-array radar can redirect its beam in any direction in less than a millisecond. This capability makes it possible to dynamically adapt the operation of the radar system to changes in the detected scenario.) Similarly, the controller may alter the signal processing parameters (e.g., detection threshold and transform type) in order to be more effective in rejecting interferences and differentiating objects. The responsiveness and iteration rate of this feedback process increase as the total response time of signal processing and tracking decreases. For this reason, the developers of these applications are primarily concerned with their throughputs and response times.