Main Content

Introduction to Using the Global Nearest Neighbor Tracker

Open Script

This example shows how to configure and use the global nearest neighbor (GNN) tracker.

Motivation

The trackerGNN is a global nearest neighbor (GNN), single-hypothesis tracker. The trackerGNN allows you to:

  1. Choose the assignment algorithm to associate detections with tracks.

  2. Use either history-based or score-based track logic for confirmation and deletion of tracks.

  3. Use any kind of tracking filter, including an interacting multiple model filter.

  4. Connect the tracker to scanning and managed sensors that update only a subset of the tracks managed by the tracker.

  5. Predict tracks into the future without modifying their internal state. This allows you to display the predicted state of the tracks or to provide track predictions to a sensor resource manager.

Construct and Use the trackerGNN

You can construct the trackerGNN and choose one of the assignment algorithms. By default, the trackerGNN uses the 'Munkres' algorithm, which guarantees an optimal assignment, but may take more time to compute. You can use 'Auction' or 'Jonker-Volgenant' or provide a 'Custom' function of your own. In this example, you choose the 'Auction' algorithm.

tracker = trackerGNN('Assignment','Auction')

tracker = 

  trackerGNN with properties:

                  TrackerIndex: 0
       FilterInitializationFcn: 'initcvekf'
                  MaxNumTracks: 100
              MaxNumDetections: Inf
                 MaxNumSensors: 20

                    Assignment: 'Auction'
           AssignmentThreshold: [30 Inf]
          AssignmentClustering: 'off'

                  OOSMHandling: 'Terminate'

                    TrackLogic: 'History'
         ConfirmationThreshold: [2 3]
             DeletionThreshold: [5 5]

            HasCostMatrixInput: false
    HasDetectableTrackIDsInput: false
               StateParameters: [1x1 struct]

             ClassFusionMethod: 'None'

                     NumTracks: 0
            NumConfirmedTracks: 0

        EnableMemoryManagement: false

The main way of using the trackerGNN is by calling it with new detections at each simulation step. A detection is an objectDetection input or a struct with similar fields. You must specify the time of the detection and its measurement. The other properties have default values. For example:

detections = {objectDetection(0,[1;2;3]); % Using default values on the detection ...
    objectDetection(0, [10;0;0], 'ObjectClassID', 2)}; % Using a non-default object class
disp(detections{1})

  objectDetection with properties:

                     Time: 0
              Measurement: [3x1 double]
         MeasurementNoise: [3x3 double]
              SensorIndex: 1
            ObjectClassID: 0
    ObjectClassParameters: []
    MeasurementParameters: {}
         ObjectAttributes: {}


time = 0;
[confirmedTracks, tentativeTracks] = tracker(detections, time);
disp(confirmedTracks)
disp(tentativeTracks)

  objectTrack with properties:

                     TrackID: 2
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 0
                         Age: 1
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 2
    ObjectClassProbabilities: 1
                  TrackLogic: 'History'
             TrackLogicState: [1 0 0 0 0]
                 IsConfirmed: 1
                   IsCoasted: 0
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 0
                         Age: 1
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 0
    ObjectClassProbabilities: 1
                  TrackLogic: 'History'
             TrackLogicState: [1 0 0 0 0]
                 IsConfirmed: 0
                   IsCoasted: 0
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

Two types of tracks are created: confirmed and tentative. A confirmed track is a track that is considered to be an estimation of a real target, while a tentative track may still be a false target. The IsConfirmed flag distinguishes between the two. The track created by the second detection has a nonzero ObjectClassID field and is immediately confirmed, because the sensor that reported it has been able to classify it and thus it is considered a real target. Alternatively, a track can be confirmed if there is enough evidence of its existence. In the history-based confirmation logic used here, if the track has been assigned 2 detections out of 3 it will be confirmed. This is controlled by the ConfirmationThreshold property. For example, the next detection is assigned to the tentative track and confirms it:

detections = {objectDetection(1,[1.1;2.2;3.3])};
time = time + 1; % Time must increase from one update of the tracker to the next
confirmedTracks = tracker(detections,time);
confirmedTracks(1)

ans = 

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 1
                         Age: 2
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 0
    ObjectClassProbabilities: 1
                  TrackLogic: 'History'
             TrackLogicState: [1 1 0 0 0]
                 IsConfirmed: 1
                   IsCoasted: 0
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

Use a Score-Based Confirmation and Deletion Logic

In many cases, the history-based confirmation and deletion logic is considered too simplistic, as it does not take into account statistical metrics. These metrics include the sensor's probability of detection and false alarm rate, the likelihood of new targets to appear, or the distance between a detection and the estimated state of the track assigned to it. A score-based confirmation and deletion logic takes into account such metrics and provides a more suitable statistical test.

To convert the tracker to a score-based confirmation and deletion logic, first release the tracker and then set the tracker's TrackLogic to 'Score':

release(tracker)
tracker.TrackLogic = 'Score'

tracker = 

  trackerGNN with properties:

                  TrackerIndex: 0
       FilterInitializationFcn: 'initcvekf'
                  MaxNumTracks: 100
              MaxNumDetections: Inf
                 MaxNumSensors: 20

                    Assignment: 'Auction'
           AssignmentThreshold: [30 Inf]
          AssignmentClustering: 'off'

                  OOSMHandling: 'Terminate'

                    TrackLogic: 'Score'
         ConfirmationThreshold: 20
             DeletionThreshold: -7
          DetectionProbability: 0.9000
                FalseAlarmRate: 1.0000e-06
                        Volume: 1
                          Beta: 1

            HasCostMatrixInput: false
    HasDetectableTrackIDsInput: false
               StateParameters: [1x1 struct]

             ClassFusionMethod: 'None'

                     NumTracks: 0
            NumConfirmedTracks: 0

        EnableMemoryManagement: false

Notice that the confirmation and deletion thresholds have changed to scalar values, which represent the score used to confirm and delete a track. In addition, several more properties are now used to provide the parameters for the score-based confirmation and deletion.

Now, update the tracker to see the tracks confirmation.

detections = {objectDetection(0,[1;2;3]); % Using default values on the detection ...
    objectDetection(0, [10;0;0], 'ObjectClassID', 2)}; % Using a non-default object class
time = 0;
tracker(detections, time); % Same as the first step above
detections = {objectDetection(1,[1.1;2.2;3.3])};
time = time + 1; % Time must increase from one update of the tracker to the next
[confirmedTracks, tentativeTracks] = tracker(detections,time);
confirmedTracks

confirmedTracks = 

  objectTrack with properties:

                     TrackID: 2
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 1
                         Age: 2
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 2
    ObjectClassProbabilities: 1
                  TrackLogic: 'Score'
             TrackLogicState: [11.4076 13.7102]
                 IsConfirmed: 1
                   IsCoasted: 1
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

Because the confirmed track was not assigned to any detection in this update, its score decreased. You can see that by looking at the TrackLogicState field and seeing that the first element, the current score, is lower than the second element, the maximum score. If the track continues to decrease relative to the maximum score, by more than the DeletionThreshold value, the track is deleted.

tentativeTracks

tentativeTracks = 

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 1
                         Age: 2
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 0
    ObjectClassProbabilities: 1
                  TrackLogic: 'Score'
             TrackLogicState: [17.7217 17.7217]
                 IsConfirmed: 0
                   IsCoasted: 0
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

If the tracks are not assigned to any detections, they will first be coasted and after a few 'misses' they will be deleted. To see that, call the tracker with no detections:

for i = 1:3
    time = time + 1;
    [~,~,allTracks] = tracker({},time)
end

allTracks = 

  2x1 objectTrack array with properties:

    TrackID
    BranchID
    SourceIndex
    UpdateTime
    Age
    State
    StateCovariance
    StateParameters
    ObjectClassID
    ObjectClassProbabilities
    TrackLogic
    TrackLogicState
    IsConfirmed
    IsCoasted
    IsSelfReported
    ObjectAttributes


allTracks = 

  2x1 objectTrack array with properties:

    TrackID
    BranchID
    SourceIndex
    UpdateTime
    Age
    State
    StateCovariance
    StateParameters
    ObjectClassID
    ObjectClassProbabilities
    TrackLogic
    TrackLogicState
    IsConfirmed
    IsCoasted
    IsSelfReported
    ObjectAttributes


allTracks = 

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 4
                         Age: 5
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 0
    ObjectClassProbabilities: 1
                  TrackLogic: 'Score'
             TrackLogicState: [10.8139 17.7217]
                 IsConfirmed: 0
                   IsCoasted: 1
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

The second track was deleted because it was not assigned any detections in 4 updates. This caused its score to fall by more than 7, the value of the DeletionThreshold. The first track is still not deleted, but its score is now lower and close to the deletion threshold.

Use Any Tracking Filter

The trackerGNN supports any tracking filter that implements the tracking filter interface. The selection of filter initialization function is defined using the FilterInitializationFcn property of the trackerGNN. This provides the following flexibility:

  1. You can use any filter initialization function available in the product. Some examples include initcvekf (default), initcvkf , initcvukf , initcvckf , initcaekf , etc.

  2. You can write your own filter initialization function and use any tracking filter. These include trackingABF , trackingEKF , trackingKF , trackingUKF , trackingCKF , trackingPF , trackingMSCEKF , trackingGSF , and trackingIMM.

  3. You can write a tracking filter that inherits and implements the interface defined by the abstract matlabshared.tracking.internal.AbstractTrackingFilter class.

The following example shows how to use an interacting motion model (IMM) filter that has 3 types of motion models: constant velocity, constant acceleration and constant turn rate.

Modify the tracker to use an IMM filter

release(tracker) % Release the tracker
tracker.FilterInitializationFcn = 'initekfimm'

tracker = 

  trackerGNN with properties:

                  TrackerIndex: 0
       FilterInitializationFcn: 'initekfimm'
                  MaxNumTracks: 100
              MaxNumDetections: Inf
                 MaxNumSensors: 20

                    Assignment: 'Auction'
           AssignmentThreshold: [30 Inf]
          AssignmentClustering: 'off'

                  OOSMHandling: 'Terminate'

                    TrackLogic: 'Score'
         ConfirmationThreshold: 20
             DeletionThreshold: -7
          DetectionProbability: 0.9000
                FalseAlarmRate: 1.0000e-06
                        Volume: 1
                          Beta: 1

            HasCostMatrixInput: false
    HasDetectableTrackIDsInput: false
               StateParameters: [1x1 struct]

             ClassFusionMethod: 'None'

                     NumTracks: 0
            NumConfirmedTracks: 0

        EnableMemoryManagement: false

Next, update the tracker with a detection and observe the three motion models that comprise it. You can see which model is used by looking at the StateTransitionFcn of each filter.

% Update the tracker with a single detection to get a single track
detection = {objectDetection(0, [1;2;3], 'ObjectClassID', 2)};
time = 0;
tracker(detection, time);

Use the getTrackFilterProperties method to view the TrackingFilters property. It returns a cell array that contains the TrackingFilters property: {filter1;filter2;filter3} 

filters = getTrackFilterProperties(tracker,1,'TrackingFilters');
for i = 1:numel(filters{1})
    disp(filters{1}{i})
end

  trackingEKF with properties:

                          State: [6x1 double]
                StateCovariance: [6x6 double]

             StateTransitionFcn: @constvel
     StateTransitionJacobianFcn: @constveljac
                   ProcessNoise: [3x3 double]
        HasAdditiveProcessNoise: 0

                 MeasurementFcn: @cvmeas
         MeasurementJacobianFcn: @cvmeasjac
         HasMeasurementWrapping: 1
               MeasurementNoise: [3x3 double]
    HasAdditiveMeasurementNoise: 1

                MaxNumOOSMSteps: 0

                EnableSmoothing: 0

  trackingEKF with properties:

                          State: [9x1 double]
                StateCovariance: [9x9 double]

             StateTransitionFcn: @constacc
     StateTransitionJacobianFcn: @constaccjac
                   ProcessNoise: [3x3 double]
        HasAdditiveProcessNoise: 0

                 MeasurementFcn: @cameas
         MeasurementJacobianFcn: @cameasjac
         HasMeasurementWrapping: 1
               MeasurementNoise: [3x3 double]
    HasAdditiveMeasurementNoise: 1

                MaxNumOOSMSteps: 0

                EnableSmoothing: 0

  trackingEKF with properties:

                          State: [7x1 double]
                StateCovariance: [7x7 double]

             StateTransitionFcn: @constturn
     StateTransitionJacobianFcn: @constturnjac
                   ProcessNoise: [4x4 double]
        HasAdditiveProcessNoise: 0

                 MeasurementFcn: @ctmeas
         MeasurementJacobianFcn: @ctmeasjac
         HasMeasurementWrapping: 1
               MeasurementNoise: [3x3 double]
    HasAdditiveMeasurementNoise: 1

                MaxNumOOSMSteps: 0

                EnableSmoothing: 0

Interface with Scanning and Managed Sensors

By default, the tracker assumes that each step updates all the tracks managed by the tracker in a coverage area. This is not the case when sensors have limited coverage, and scan a small area, or when they are managed and cued to scan certain areas out of the total coverage area. If that is the case, the sensors should let the tracker know that some tracks were not covered by the sensors at that step. Otherwise, the tracker assumes that the tracks were supposed to be detected and will count a 'miss' against them, leading to their premature deletion.

The following example shows how the sensors signify that the track will not be detected, and how the track is not deleted.

Create a tracker that allows feedback from the sensors.

release(tracker) % Release the tracker
tracker.FilterInitializationFcn = 'initcvekf';
tracker.HasDetectableTrackIDsInput = true % Allows the tracker to get input about the track detectability by the sensors
% Update the tracker with a single detection to get a single track
detection = {objectDetection(0, [1;2;3], 'ObjectClassID', 2)};
time = 0;
trackIDs = []; % Initially, there are no tracks, so trackIDs has zero rows
track = tracker(detection, time, trackIDs)
% Update the tracker 2 more times without any detections. Let the tracker
% know that the track was not detectable by any sensor. Note how the
% TrackLogicState, shown as [currentScore, maxScore], does not change even
% though the track is not detected.
for i=1:2
    time = time + 1;
    trackIDs = [1, 0]; % Zero probability of detection means the track score should not decrease
    track = tracker({}, time, trackIDs) % No detections
end

tracker = 

  trackerGNN with properties:

                  TrackerIndex: 0
       FilterInitializationFcn: 'initcvekf'
                  MaxNumTracks: 100
              MaxNumDetections: Inf
                 MaxNumSensors: 20

                    Assignment: 'Auction'
           AssignmentThreshold: [30 Inf]
          AssignmentClustering: 'off'

                  OOSMHandling: 'Terminate'

                    TrackLogic: 'Score'
         ConfirmationThreshold: 20
             DeletionThreshold: -7
          DetectionProbability: 0.9000
                FalseAlarmRate: 1.0000e-06
                        Volume: 1
                          Beta: 1

            HasCostMatrixInput: false
    HasDetectableTrackIDsInput: true
               StateParameters: [1x1 struct]

             ClassFusionMethod: 'None'

                     NumTracks: 0
            NumConfirmedTracks: 0

        EnableMemoryManagement: false


track = 

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 0
                         Age: 1
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 2
    ObjectClassProbabilities: 1
                  TrackLogic: 'Score'
             TrackLogicState: [13.7102 13.7102]
                 IsConfirmed: 1
                   IsCoasted: 0
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]


track = 

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 1
                         Age: 2
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 2
    ObjectClassProbabilities: 1
                  TrackLogic: 'Score'
             TrackLogicState: [13.7102 13.7102]
                 IsConfirmed: 1
                   IsCoasted: 1
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]


track = 

  objectTrack with properties:

                     TrackID: 1
                    BranchID: 0
                 SourceIndex: 0
                  UpdateTime: 2
                         Age: 3
                       State: [6x1 double]
             StateCovariance: [6x6 double]
             StateParameters: [1x1 struct]
               ObjectClassID: 2
    ObjectClassProbabilities: 1
                  TrackLogic: 'Score'
             TrackLogicState: [13.7102 13.7102]
                 IsConfirmed: 1
                   IsCoasted: 1
              IsSelfReported: 1
            ObjectAttributes: [1x1 struct]

As seen, the track score did not decrease and the track was not deleted by the tracker, even though it was not detected in 5 updates.

Predict the Tracks to a Certain Time

The last enhancement allows you to predict the tracks into the future without changing their internal state. There are two common use cases for this:

  1. Displaying the predicted tracks on a display.

  2. Passing the predicted tracks to a sensor system so that the sensor system can cue a search pattern to detect them.

You use the predictTracksToTime method to get the predicted tracks.

Update the tracker with more detections

time = time + 1;
detections = {objectDetection(time, [4,2,3]); ...
    objectDetection(time, [10;0;0])};
track = tracker(detections, time, trackIDs);
disp('State of track #1 at time 3:')
disp(track.State)

% Predict tracks to different time steps:
predictedTrack1 = predictTracksToTime(tracker,1, time+0.5); % Predict track number 1 half a second to the future
disp('State of track #1 at time 3.5:')
predictedTrack1.State
% Predict all the confirmed tracks 2 seconds to the future
predictedConfirmedTracks = predictTracksToTime(tracker, 'Confirmed', time+2);
disp('State of track #1 at time 5:')
predictedConfirmedTracks.State

% Predict all the tracks 0.3 seconds to the future
disp('State of all the tracks at time 3.3:')
predictedTracks = predictTracksToTime(tracker, 'all', time+0.3);
predictedTracks.State

State of track #1 at time 3:
    3.9967
    1.0030
    2.0000
         0
    3.0000
         0

State of track #1 at time 3.5:

ans =

    4.4982
    1.0030
    2.0000
         0
    3.0000
         0

State of track #1 at time 5:

ans =

    6.0027
    1.0030
    2.0000
         0
    3.0000
         0

State of all the tracks at time 3.3:

ans =

    4.2976
    1.0030
    2.0000
         0
    3.0000
         0


ans =

    10
     0
     0
     0
     0
     0

You can use the predictTracksToTime method to visualize the predicted state of the tracks.

% First, use a |theaterPlot| and a |trackPlotter| to plot the tracks.
thPlot = theaterPlot('XLimits',[-20 20], 'Ylimits', [-20 20]);
trPlotter = trackPlotter(thPlot, 'DisplayName', 'Predicted Track');
posSelector = [1 0 0 0 0 0; 0 0 1 0 0 0; 0 0 0 0 1 0];
velSelector = [0 1 0 0 0 0; 0 0 0 1 0 0; 0 0 0 0 0 1];

% Then, plot the predicted tracks every 0.1 seconds
for t = time+(0.1:0.1:5)
    predictedTracks = predictTracksToTime(tracker, 'Confirmed', t);
    [pos,cov] = getTrackPositions(predictedTracks,posSelector);
    vel = getTrackVelocities(predictedTracks,velSelector);
    plotTrack(trPlotter,pos,vel,cov);
    drawnow
end

Summary

In this example, you created a trackerGNN and used it to track multiple targets. You modified the tracker to use various assignment algorithms, two types of confirmation and deletion logic, and various tracking filters. In addition, you saw how to interface the tracker with a scanning radar and how to get the track predictions for display or sensor management.