Autonomous Driving

Radar Tracker

A radar tracker is a component of a radar system, or an associated command and control (C2) system, that associates consecutive radar observations of the same target into tracks. It is particularly useful when the radar system is reporting data from several different targets or when it is necessary to combine the data from several different radars or other sensors.

A classical rotating air surveillance radar system detects target echoes against a background of noise. It reports these detections (known as “plots”) in polar coordinates representing the range and bearing of the target. In addition, noise in the radar receiver will occasionally exceed the detection threshold of the radar’s Constant false alarm rate detector and be incorrectly reported as targets (known as false alarms). The role of the radar tracker is to monitor consecutive updates from the radar system (which typically occur once every few seconds, as the antenna rotates) and to determine those sequences of plots belonging to the same target, whilst rejecting any plots believed to be false alarms. In addition, the radar tracker is able to use the sequence of plots to estimate the current speed and heading of the target. When several targets are present, the radar tracker aims to provide one track for each target, with the track history often being used to indicate where the target has come from.

A radar track will typically contain the following information:

  1. Position (in two or three dimensions)
  2. Heading
  3. Speed
  4. Unique track number
  5. status
  6. Age – used in tracker initiation and maintenance

I would believe in the future, when 4D radar becomes popular, category of the object will definitely become an importannt information which can be provided by radar. They just the dense radar point cloud to train the neural network to classify the object type. Currently, the automotive radar only provides a parse reflection data point instead of a point cloud.

How to implement radar tracker

1. Plot to track association: Associate a radar plot with an existing track
2. Track smoothing: Update the track with this latest plot
3. Track initiation: Spawn new tracks with any plots that are not associated with existing tracks
4. Track maintenance: Delete any tracks that have not been updated, or predict their new location based on the previous heading and speed

Track association

Perhaps the most important step is the updating of tracks with new plots. All trackers will implicitly or explicitly take account of a number of factors during this stage, including:

  1. a model for how the radar measurements are related to the target coordinates
  2. the errors on the radar measurements
  3. a model of the target movement
  4. errors in the model of the target movement

When I got the time, I will post an article to update all the information above.

we can first take a very light sip on the first topic – how the radar measurements are related to the target coordinates.
A very famous clustering method in machine learning area – Kmeans clustering.

K means clustering

What is K means clustering ?
It is an unsupervised machine learning method used for clustering. It aims to partition n observations into k clusters in which each observation belongs to the cluster with the centroid. So the process of radar data point association is an X-means clustering. The reason I used X here is because we don`t know how many clusters will be there finally. But for K means clustering, we have to first define that there will be and only will be K clusters.

Here are the steps for k means clustering.

  1. Randomly generate k data points as centroids, these k data points must be within the range of the whole data set.
  2. Pick a data point from the data set, calculate the Euclidean distance between the data point and all the centroids, assign the data point to the one with the smallest Euclidean distance.
  3. Repeat step 2 for all the data points.
  4. We will get k clusters now, recalculate the centroids. Repeat step 2 and step 3.
  5. When the current centroids and previous centroids are close enough, end the process.
Step1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def kMeans(data,k=2):
    def _distance(p1,p2):
        """
        In order to speed up, actually we don`t necessarily to use Euclidean distance, we just get the square of Euclidean distance will be good enough, it can save a lot of computing power.
        """
        return np.sum((p1-p2)**2)

    def get_centroid(data,k):
        """Generate k center within the range of data set."""
        n = data.shape[1] # features
        centroids = np.zeros((k,n)) # init with (0,0)....
        for i in range(n):
            dmin, dmax = np.min(data[:,i]), np.max(data[:,i])
            centroids[:,i] = dmin + (dmax - dmin) * np.random.rand(k)
        return centroids
    
    def is_converged(centroid1, centroids):
         set1 = set([tuple(c) for c in centroid1])
         set2 = set([tuple(c) for c in centroid2])
         return (set1 == set2)
        
    
    n = data.shape[0] # number of entries
    centroids = _rand_center(data,k)
    label = np.zeros(n,dtype=np.int) # track the nearest centroid
    assement = np.zeros(n) # for the assement of our model
    converged = False
    
    while not converged:
        old_centroids = np.copy(centroids)
        for i in range(n):
            # determine the nearest centroid and track it with label
            min_dist, min_index = np.inf, -1
            for j in range(k):
                dist = _distance(data[i],centroids[j])
                if dist < min_dist:
                    min_dist, min_index = dist, j
                    label[i] = j
            assement[i] = _distance(data[i],centroids[label[i]])**2
        
        # update centroid
        for m in range(k):
            centroids[m] = np.mean(data[label==m],axis=0)
        converged = is_converged(old_centroids,centroids)    
    return centroids, label, np.sum(assement)

An obvious weakness of K means clustering is that it could converge to local optimal instead of global optimal. So we could run the algorithm multiple times in order to get a better result.

Tracking smoothing:

  1. Alpha-beta tracker
  2. Kalman filter
  3. Multiple hypothesis tracker(MHT)
  4. Interacting multiple model

We will talk more about Kalman filter and Multiple hypothesis tracker in the future. Because these two are widely used in the industry.

Tracking initiation:

Track initiation is the process of creating a new radar track from unassociated radar plots. When the radar tracker is first switched on, all of the initial radar plots are used to initialize new tracks. Once the radar tracker is running, only those plots are used to create a new track that couldn’t be used to update an existing one.

Typically a new track is given the status of tentative until plots from subsequent radar updates have been successfully associated with the new track. Tentative tracks are not shown to the operator and so they provide a means of preventing false tracks from appearing on the screen – at the expense of some delay in the first reporting of a track.

Once several updates have been received, the track is confirmed and displayed to the operator. The most common criterion for promoting a tentative track to a confirmed track is the “M-of-N rule”, which states that during the last N radar updates, at least M plots must have been associated with the tentative track – with M=3 and N=5 being typical values. More sophisticated approaches may use a statistical approach in which a track becomes confirmed when, for instance, its covariance matrix falls to a given size.

A clutter map may be used to prevent track initiation in areas of strong clutter echoes not suppressed by the Doppler processing. The clutter map may also keep track of large bird echoes, so as to not be reinitiating track on them, repeatedly. Track initiation in a dense clutter environment can be quite demanding on computer software and hardware resources.

Tracker maintenance:

Track maintenance is the process in which a decision is made about whether to end the life of a track. If a track was not associated with a plot during the plot to track association phase, then there is a chance that the target may no longer exist (for instance, an aircraft may have landed or flown out of radar cover).

Alternatively, however, there is a chance that the radar may have just failed to see the target at that update, but will find it again on the next update. Common approaches to deciding on whether to terminate a track include:

  1. If the target was not seen for the past M consecutive update opportunities (typically M=3 or so)
  2. If the target was not seen for the past M out of N most recent update opportunities
  3. If the target’s track uncertainty (covariance matrix) has grown beyond a certain threshold.

Reference:

  1. https://en.wikipedia.org/wiki/Radar_tracker
  2. https://www.advsolned.com/example_radar_tracking.html
  3. https://github.com/USNavalResearchLaboratory/TrackerComponentLibrary
  4. https://www.blighter.com/products/blightertrack/
  5. https://www.radartutorial.eu/10.processing/sp22.en.html